X86: Fold tail calls into conditional branches where possible (PR26302)

[hans]

Summary

When branching to a block that immediately tail calls, it is possible to fold the call directly into the branch if the call is direct and there is no stack adjustment, saving one byte.

Example:

define void @f(i32 %x, i32 %y) {
entry:
  %p = icmp eq i32 %x, %y
  br i1 %p, label %bb1, label %bb2
bb1:
  tail call void @foo()
  ret void
bb2:
  tail call void @bar()
  ret void
}

before:

f:
        movl    4(%esp), %eax
        cmpl    8(%esp), %eax
        jne     .LBB0_2
        jmp     foo
.LBB0_2:
        jmp     bar

after:

f:
        movl    4(%esp), %eax
        cmpl    8(%esp), %eax
        jne     bar
.LBB0_1:
        jmp     foo

I don't expect any significant size savings from this (on a Clang bootstrap I saw 288 bytes), but it does make the code a little tighter.

This patch only does 32-bit, but 64-bit would work similarly.

[hans]

+Maksim who I think mentioned at Euro-LLVM that he'd looked into this.

[hans]

forgot about the debug info

[joerg]

If there are multiple users of the tail call (e.g. via different incoming edges), this can actually create a size regression by replacing a byte-immediate jump with a 32bit jump?

[hans]

In D24108#531040, @joerg wrote:

If there are multiple users of the tail call (e.g. via different incoming edges), this can actually create a size regression by replacing a byte-immediate jump with a 32bit jump?

The transformation only occurs when there's a single edge to the tail call.

[maksfb]

@hans: I think it is safe to do this optimization while optimizing for size. If you do it by default it could be a performance regression if you reverse direction of the conditional branch. That's what we found out while testing on a micro benchmark. I believe it's related to the way BTB works on Intel's CPUs. The problem is that unless you are doing LTO or work at the binary level, you don't always know the new direction of the branch.

[mkuper]

Don't know a lot about tail call handling, so the review with a grain of salt.
(The large amount of new instructions seems unfortunate, but, as above, I don't know enough about this to say whether this is avoidable...)

In D24108#531998, @maksfb wrote:

@hans: I think it is safe to do this optimization while optimizing for size. If you do it by default it could be a performance regression if you reverse direction of the conditional branch. That's what we found out while testing on a micro benchmark. I believe it's related to the way BTB works on Intel's CPUs. The problem is that unless you are doing LTO or work at the binary level, you don't always know the new direction of the branch.

Is there a reason to believe the change in direction will cause worse performance, systematically?
Or is this just a random effect on that particular microbenchmark, and we may gain performance in other cases?

include/llvm/Target/TargetInstrInfo.h

1103

Perhaps add an assert that we never get here?

lib/Target/X86/X86InstrInfo.cpp

3964

What do you think about:

if (BranchCond[0].getImm() > X86::LAST_VALID_COND)
  return false;

Are there any valid condition codes you don't support?
Admittedly, the current version is safer, but I'm not sure there's a point to future-proofing this against X86 adding condition codes.

3986

Maybe check this before checking the condition? (This would seem to be the most common reason for failure)

4015

Shouldn't I be contained in BranchCond?

4016

Can you explain what guarantees this?
I didn't see a check in canMakeTailCallConditional().

test/CodeGen/X86/conditional-tailcall.ll

21

Why do we need an encoding check?
(Probably better document this in the test itself, too.)

[maksfb]

In D24108#532166, @mkuper wrote:

Don't know a lot about tail call handling, so the review with a grain of salt.
(The large amount of new instructions seems unfortunate, but, as above, I don't know enough about this to say whether this is avoidable...)

In D24108#531998, @maksfb wrote:

@hans: I think it is safe to do this optimization while optimizing for size. If you do it by default it could be a performance regression if you reverse direction of the conditional branch. That's what we found out while testing on a micro benchmark. I believe it's related to the way BTB works on Intel's CPUs. The problem is that unless you are doing LTO or work at the binary level, you don't always know the new direction of the branch.

Is there a reason to believe the change in direction will cause worse performance, systematically?
Or is this just a random effect on that particular microbenchmark, and we may gain performance in other cases?

It's hard to say, it will depend on the application. If we assume that the original branch direction was selected intentionally (based on compiler hints, profile, or otherwise) then we probably shouldn't expect a gain from reversing the direction. And in the micro benchmark the negative effect of the reversal severely outweighed a benefit from less instructions executed when direction was the same. Can't speculate beyond the micro benchmark as we weren't able to measure the effect on real-world applications beyond applying it to our jiited code in hhvm. But there we could guarantee the branch direction stayed the same.

[hans]

Addressing comments, doing optsize only and avoiding adding so many instructions.

I'm a little bit confused by the multiple levels of pseudo-instructions here actually. We have TCRETURNdi which is expanded in X86ExpandPseudo to a TCRETURNdi, but that is actually replaced by a JMP_1 when it comes to MC lowering. IIUC, this is because we want to put different flags and stuff on TCRETURNdi and JMP_1, but there can't be two real instructions with the same encoding, so the first one is marked isCodeGenOnly.

Anyway, I think this version of the patch is a little less messier than the first.

[hans]

Thanks very much for the review. New version uploaded.

lib/Target/X86/X86InstrInfo.cpp

3964

Thanks, that works great.

I was worried about special condition codes like COND_NE_OR_P, but LAST_VALID_COND handles that.

4015

Hmm, I'm not sure I'm following.

BranchCond is what we got from analyzeBranch() before. We don't really have a handle to the actual branch instruction, which is why we're searching for it here.

4016

BranchCond originally comes from X86InstrInfo::analyzeBranch(), and that one only puts one element in it.

I'll add the same assert to canMakeTailCallConditional().

[mkuper]

Thanks Hans, this looks much nicer!

lib/Target/X86/X86InstrInfo.cpp

4032

Sorry, I got confused.
X86InstrInfo::AnalyzeBranchImpl() also returns a vector of MachineInstructions, but the analyzeBranch() interface doesn't expose that, only the MachineOperands. How inconvenient.
Anything we can do about this, or do you think it would be better not to touch this?

lib/Target/X86/X86MCInstLower.cpp

508

Can you use X86::GetCondBranchFromCond()?

[hans]

Addressing comments.

lib/Target/X86/X86InstrInfo.cpp

4032

We could change analyzeBranch() I suppose, but it would probably break some out-of-tree backends, and I'm not sure it's worth it.

lib/Target/X86/X86MCInstLower.cpp

508

Ah yes, much nicer.

test/CodeGen/X86/conditional-tailcall.ll

22

(Forgot to reply to this the first time.)

When I worked on the patch, I initially forgot to change X86MCInstLower::Lower, which meant the printed assembly looked correct, but the binary instruction wasn't correct, so I wanted to test that.

I'll add a comment to the test.

[mkuper]

LGTM

lib/Target/X86/X86InstrInfo.cpp

4032

Yeah, you're right, I can't think of a really nice way to handle this, since the analyzeBranches() call is in in a generic part of this patch, not x86-specific. And the search here should normally be really short anyway.

But could you please leave a comment documenting this, in case someone decides to refactor this later.

test/CodeGen/X86/conditional-tailcall.ll

23

I'm a bit confused about this. Without the change to X86MCInstLower, I'd expect you to get complete nonsense, not a poorly encoded jmp.
Anyway, that's a problem with my understanding of this, not your patch. :-)

[hans]

lib/Target/X86/X86InstrInfo.cpp

4032

Adding a comment.

test/CodeGen/X86/conditional-tailcall.ll

23

Yes, the bits were garbage, but with the original version of my patch it still got printed as "jne" in the assembly. That wouldn't happen with the current version, but it still seems like a good idea to do a quick check of the encoding.

include/llvm/Target/TargetInstrInfo.h

public:
   virtual bool isPredicated(const MachineInstr &MI) const {
     return false;
   }
 
   /// Returns true if the instruction is a
   /// terminator instruction that has not been predicated.
   virtual bool isUnpredicatedTerminator(const MachineInstr &MI) const;
 
+  /// Returns true if MI is an unconditional tail call.
+  virtual bool isUnconditionalTailCall(const MachineInstr &MI) const {
+    return false;
+  }
+
+  /// Returns true if the tail call can be made conditional on BranchCond.
+  virtual bool
+  canMakeTailCallConditional(SmallVectorImpl<MachineOperand> &Cond,
+                             const MachineInstr &TailCall) const {
+    return false;
+  }
+
+  /// Replace the conditional branch in MBB with a conditional tail call.
+  virtual void replaceBranchWithTailCall(MachineBasicBlock &MBB,
+                                         SmallVectorImpl<MachineOperand> &Cond,
+                                         const MachineInstr &TailCall) const {}
+
   /// Convert the instruction into a predicated instruction.
   /// It returns true if the operation was successful.
   virtual bool PredicateInstruction(MachineInstr &MI,
                                     ArrayRef<MachineOperand> Pred) const;
 
   /// Returns true if the first specified predicate
   /// subsumes the second, e.g. GE subsumes GT.
   virtual

lib/CodeGen/BranchFolding.cpp

 using namespace llvm;
 
 #define DEBUG_TYPE "branchfolding"
 
 STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
 STATISTIC(NumBranchOpts, "Number of branches optimized");
 STATISTIC(NumTailMerge , "Number of block tails merged");
 STATISTIC(NumHoist     , "Number of times common instructions are hoisted");
+STATISTIC(NumTailCalls,  "Number of tail calls optimized");
 
 static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
                               cl::init(cl::BOU_UNSET), cl::Hidden);
 
 // Throttle for huge numbers of predecessors (compile speed problems)
 static cl::opt<unsigned>
 TailMergeThreshold("tail-merge-threshold",
           cl::desc("Max number of predecessors to consider tail merging"),
if (MBB->succ_empty() && !PriorCond.empty() && !PriorFBB &&
           MadeChange = true;
           ++NumBranchOpts;
           return MadeChange;
         }
       }
     }
   }
 
+  if (!IsEmptyBlock(MBB) && MBB->pred_size() == 1) {
+    MachineInstr &TailCall = *MBB->getFirstNonDebugInstr();
+    if (TII->isUnconditionalTailCall(TailCall)) {
+      MachineBasicBlock *Pred = *MBB->pred_begin();
+      MachineBasicBlock *PredTBB = nullptr, *PredFBB = nullptr;
+      SmallVector<MachineOperand, 4> PredCond;
+      bool PredAnalyzable =
+          !TII->analyzeBranch(*Pred, PredTBB, PredFBB, PredCond, true);
+
+      if (PredAnalyzable && !PredCond.empty() && PredTBB == MBB) {
+        // The predecessor has a conditional branch to this block which consists
+        // of only a tail call. Try to fold the tail call into the conditional
+        // branch.
+        if (TII->canMakeTailCallConditional(PredCond, TailCall)) {
+          TII->replaceBranchWithTailCall(*Pred, PredCond, TailCall);
+          ++NumTailCalls;
+          Pred->removeSuccessor(MBB);
+          MadeChange = true;
+          return MadeChange;
+        }
+      }
+      // If the predecessor is falling through to this block, we could reverse
+      // the branch condition and fold the tail call into that. However, after
+      // that we might have to re-arrange the CFG to fall through to the other
+      // block and there is a high risk of regressing code size rather than
+      // improving it.
+    }
+  }
+
   // Analyze the branch in the current block.
   MachineBasicBlock *CurTBB = nullptr, *CurFBB = nullptr;
   SmallVector<MachineOperand, 4> CurCond;
   bool CurUnAnalyzable =
       TII->analyzeBranch(*MBB, CurTBB, CurFBB, CurCond, true);
   if (!CurUnAnalyzable) {
     // If the CFG for the prior block has extra edges, remove them.
     MadeChange |= MBB->CorrectExtraCFGEdges(CurTBB, CurFBB, !CurCond.empty());

lib/Target/X86/X86ExpandPseudo.cpp

bool X86ExpandPseudo::ExpandMI(MachineBasicBlock &MBB,
                                MachineBasicBlock::iterator MBBI) {
   MachineInstr &MI = *MBBI;
   unsigned Opcode = MI.getOpcode();
   DebugLoc DL = MBBI->getDebugLoc();
   switch (Opcode) {
   default:
     return false;
   case X86::TCRETURNdi:
+  case X86::TCRETURNdicc:
   case X86::TCRETURNri:
   case X86::TCRETURNmi:
   case X86::TCRETURNdi64:
   case X86::TCRETURNri64:
   case X86::TCRETURNmi64: {
     bool isMem = Opcode == X86::TCRETURNmi || Opcode == X86::TCRETURNmi64;
     MachineOperand &JumpTarget = MBBI->getOperand(0);
     MachineOperand &StackAdjust = MBBI->getOperand(isMem ? 5 : 1);
     assert(StackAdjust.isImm() && "Expecting immediate value.");
 
     // Adjust stack pointer.
     int StackAdj = StackAdjust.getImm();
     int MaxTCDelta = X86FI->getTCReturnAddrDelta();
     int Offset = 0;
     assert(MaxTCDelta <= 0 && "MaxTCDelta should never be positive");
 
     // Incoporate the retaddr area.
-    Offset = StackAdj-MaxTCDelta;
+    Offset = StackAdj - MaxTCDelta;
     assert(Offset >= 0 && "Offset should never be negative");
 
+    if (Opcode == X86::TCRETURNdicc) {
+      assert(Offset == 0 && "Conditional tail call cannot adjust the stack.");
+    }
+
     if (Offset) {
       // Check for possible merge with preceding ADD instruction.
       Offset += X86FL->mergeSPUpdates(MBB, MBBI, true);
       X86FL->emitSPUpdate(MBB, MBBI, Offset, /*InEpilogue=*/true);
     }
 
     // Jump to label or value in register.
     bool IsWin64 = STI->isTargetWin64();
-    if (Opcode == X86::TCRETURNdi || Opcode == X86::TCRETURNdi64) {
-      unsigned Op = (Opcode == X86::TCRETURNdi)
-                        ? X86::TAILJMPd
-                        : (IsWin64 ? X86::TAILJMPd64_REX : X86::TAILJMPd64);
+    if (Opcode == X86::TCRETURNdi || Opcode == X86::TCRETURNdicc ||
+        Opcode == X86::TCRETURNdi64) {
+      unsigned Op;
+      switch (Opcode) {
+      case X86::TCRETURNdi:
+        Op = X86::TAILJMPd;
+        break;
+      case X86::TCRETURNdicc:
+        switch(static_cast<X86::CondCode>(MBBI->getOperand(2).getImm())) {
+        case X86::COND_E:  Op = X86::TAILJMPd_E;  break;
+        case X86::COND_NE: Op = X86::TAILJMPd_NE; break;
+        case X86::COND_L:  Op = X86::TAILJMPd_L;  break;
+        case X86::COND_LE: Op = X86::TAILJMPd_LE; break;
+        case X86::COND_G:  Op = X86::TAILJMPd_G;  break;
+        case X86::COND_GE: Op = X86::TAILJMPd_GE; break;
+        case X86::COND_B:  Op = X86::TAILJMPd_B;  break;
+        case X86::COND_BE: Op = X86::TAILJMPd_BE; break;
+        case X86::COND_A:  Op = X86::TAILJMPd_A;  break;
+        case X86::COND_AE: Op = X86::TAILJMPd_AE; break;
+        case X86::COND_S:  Op = X86::TAILJMPd_S;  break;
+        case X86::COND_NS: Op = X86::TAILJMPd_NS; break;
+        case X86::COND_P:  Op = X86::TAILJMPd_P;  break;
+        case X86::COND_NP: Op = X86::TAILJMPd_NP; break;
+        case X86::COND_O:  Op = X86::TAILJMPd_O;  break;
+        case X86::COND_NO: Op = X86::TAILJMPd_NO; break;
+        default:
+          assert(0 && "Unexpected tail call condition code.");
+        }
+        break;
+      default:
+        Op = IsWin64 ? X86::TAILJMPd64_REX : X86::TAILJMPd64;
+        break;
+      }
       MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(Op));
-      if (JumpTarget.isGlobal())
+      if (JumpTarget.isGlobal()) {
         MIB.addGlobalAddress(JumpTarget.getGlobal(), JumpTarget.getOffset(),
                              JumpTarget.getTargetFlags());
-      else {
+      } else {
         assert(JumpTarget.isSymbol());
         MIB.addExternalSymbol(JumpTarget.getSymbolName(),
                               JumpTarget.getTargetFlags());
       }
+
     } else if (Opcode == X86::TCRETURNmi || Opcode == X86::TCRETURNmi64) {
       unsigned Op = (Opcode == X86::TCRETURNmi)
                         ? X86::TAILJMPm
                         : (IsWin64 ? X86::TAILJMPm64_REX : X86::TAILJMPm64);
       MachineInstrBuilder MIB = BuildMI(MBB, MBBI, DL, TII->get(Op));
       for (unsigned i = 0; i != 5; ++i)
         MIB.addOperand(MBBI->getOperand(i));
     } else if (Opcode == X86::TCRETURNri64) {

lib/Target/X86/X86InstrControl.td

 
 // Tail call stuff.
 
 let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1,
     isCodeGenOnly = 1, SchedRW = [WriteJumpLd] in
   let Uses = [ESP] in {
   def TCRETURNdi : PseudoI<(outs),
                      (ins i32imm_pcrel:$dst, i32imm:$offset), []>;
+  def TCRETURNdicc : PseudoI<(outs),
+                     (ins i32imm_pcrel:$dst, i32imm:$offset, i32imm:$cond), []>;
   def TCRETURNri : PseudoI<(outs),
                      (ins ptr_rc_tailcall:$dst, i32imm:$offset), []>;
   let mayLoad = 1 in
   def TCRETURNmi : PseudoI<(outs),
                      (ins i32mem_TC:$dst, i32imm:$offset), []>;
 
   // FIXME: The should be pseudo instructions that are lowered when going to
   // mcinst.
   def TAILJMPd : Ii32PCRel<0xE9, RawFrm, (outs),
                            (ins i32imm_pcrel:$dst),
                            "jmp\t$dst",
                            [], IIC_JMP_REL>;
+
+  def TAILJMPd_O  : Ii32PCRel<0x80, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jo\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_NO : Ii32PCRel<0x81, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jno\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_B  : Ii32PCRel<0x82, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jb\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_AE : Ii32PCRel<0x83, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jae\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_E  : Ii32PCRel<0x84, RawFrm, (outs), (ins i32imm_pcrel:$dst), "je\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_NE : Ii32PCRel<0x85, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jne\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_BE : Ii32PCRel<0x86, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jbe\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_A  : Ii32PCRel<0x87, RawFrm, (outs), (ins i32imm_pcrel:$dst), "ja\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_S  : Ii32PCRel<0x88, RawFrm, (outs), (ins i32imm_pcrel:$dst), "js\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_NS : Ii32PCRel<0x89, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jns\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_P  : Ii32PCRel<0x8A, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jp\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_NP : Ii32PCRel<0x8B, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jnp\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_L  : Ii32PCRel<0x8C, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jl\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_GE : Ii32PCRel<0x8D, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jge\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_LE : Ii32PCRel<0x8E, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jle\t$dst", [], IIC_JMP_REL>;
+  def TAILJMPd_G  : Ii32PCRel<0x8F, RawFrm, (outs), (ins i32imm_pcrel:$dst), "jg\t$dst", [], IIC_JMP_REL>;
+
   def TAILJMPr : I<0xFF, MRM4r, (outs), (ins ptr_rc_tailcall:$dst),
                    "", [], IIC_JMP_REG>;  // FIXME: Remove encoding when JIT is dead.
   let mayLoad = 1 in
   def TAILJMPm : I<0xFF, MRM4m, (outs), (ins i32mem_TC:$dst),
                    "jmp{l}\t{*}$dst", [], IIC_JMP_MEM>;
 }
 
 

lib/Target/X86/X86InstrInfo.h

public:
   ///     FMA231 #3, #2, #1
   unsigned getFMA3OpcodeToCommuteOperands(const MachineInstr &MI,
                                           unsigned SrcOpIdx1,
                                           unsigned SrcOpIdx2,
                                           const X86InstrFMA3Group &FMA3Group) const;
 
   // Branch analysis.
   bool isUnpredicatedTerminator(const MachineInstr &MI) const override;
+  bool isUnconditionalTailCall(const MachineInstr &MI) const override;
+  bool canMakeTailCallConditional(SmallVectorImpl<MachineOperand> &Cond,
+                                  const MachineInstr &TailCall) const override;
+  void replaceBranchWithTailCall(MachineBasicBlock &MBB,
+                                 SmallVectorImpl<MachineOperand> &Cond,
+                                 const MachineInstr &TailCall) const override;
+
   bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB,
                      MachineBasicBlock *&FBB,
                      SmallVectorImpl<MachineOperand> &Cond,
                      bool AllowModify) const override;
 
   bool getMemOpBaseRegImmOfs(MachineInstr &LdSt, unsigned &BaseReg,
                              int64_t &Offset,
                              const TargetRegisterInfo *TRI) const override;

lib/Target/X86/X86InstrInfo.cpp

bool X86InstrInfo::isUnpredicatedTerminator(const MachineInstr &MI) const {
   // Conditional branch is a special case.
   if (MI.isBranch() && !MI.isBarrier())
     return true;
   if (!MI.isPredicable())
     return true;
   return !isPredicated(MI);
 }
 
+bool X86InstrInfo::isUnconditionalTailCall(const MachineInstr &MI) const {
+  switch (MI.getOpcode()) {
+  case X86::TCRETURNdi:
+  case X86::TCRETURNri:
+  case X86::TCRETURNmi:
+  case X86::TCRETURNdi64:
+  case X86::TCRETURNri64:
+  case X86::TCRETURNmi64:
+    return true;
+  default:
+    return false;
+  }
+}
+
+bool X86InstrInfo::canMakeTailCallConditional(
+    SmallVectorImpl<MachineOperand> &BranchCond,
+    const MachineInstr &TailCall) const {
+  switch (BranchCond[0].getImm()) {
+    default:
+      // Can't make a conditional tail call with this condition.
+      return false;
+    case X86::COND_E:
+    case X86::COND_NE:
+    case X86::COND_L:
+    case X86::COND_LE:
+    case X86::COND_G:
+    case X86::COND_GE:
+    case X86::COND_B:
+    case X86::COND_BE:
+    case X86::COND_A:
+    case X86::COND_AE:
+    case X86::COND_S:
+    case X86::COND_NS:
+    case X86::COND_P:
+    case X86::COND_NP:
+    case X86::COND_O:
+    case X86::COND_NO:
+      break;
+  }
+
+  if (TailCall.getOpcode() != X86::TCRETURNdi) {
+    // Only direct calls can be done with a conditional branch.
+    return false;
+  }
+
+  const X86MachineFunctionInfo *X86FI =
+      TailCall.getParent()->getParent()->getInfo<X86MachineFunctionInfo>();
+  if (X86FI->getTCReturnAddrDelta() != 0 ||
+      TailCall.getOperand(1).getImm() != 0) {
+    // A conditional tail call cannot do any stack adjustment.
+    return false;
+  }
+
+  return true;
+}
+
+void X86InstrInfo::replaceBranchWithTailCall(
+    MachineBasicBlock &MBB, SmallVectorImpl<MachineOperand> &BranchCond,
+    const MachineInstr &TailCall) const {
+  assert(canMakeTailCallConditional(BranchCond, TailCall));
+
+  MachineBasicBlock::iterator I = MBB.end();
+  while (I != MBB.begin()) {
+    --I;
+    if (I->isDebugValue())
+      continue;
+    if (!I->isBranch())
+      assert(0 && "Can't find the branch to replace!");
+
+    X86::CondCode CC = getCondFromBranchOpc(I->getOpcode());
+    assert(BranchCond.size() == 1);
+    if (CC != BranchCond[0].getImm())
+      continue;
+
+    break;
+  }
+
+  auto MIB = BuildMI(MBB, I, MBB.findDebugLoc(I), get(X86::TCRETURNdicc));
+  MIB->addOperand(TailCall.getOperand(0)); // Destination.
+  MIB.addImm(0); // Stack offset (not used).
+  MIB->addOperand(BranchCond[0]); // Condition.
+  MIB->addOperand(TailCall.getOperand(2)); // Regmask.
+
+  I->eraseFromParent();
+}
+
 // Given a MBB and its TBB, find the FBB which was a fallthrough MBB (it may
 // not be a fallthrough MBB now due to layout changes). Return nullptr if the
 // fallthrough MBB cannot be identified.
 static MachineBasicBlock *getFallThroughMBB(MachineBasicBlock *MBB,
                                             MachineBasicBlock *TBB) {
   // Look for non-EHPad successors other than TBB. If we find exactly one, it
   // is the fallthrough MBB. If we find zero, then TBB is both the target MBB
   // and fallthrough MBB. If we find more than one, we cannot identify the
   // fallthrough MBB and should return nullptr.

lib/Target/X86/X86MCInstLower.cpp

case X86::CATCHRET: {
     const X86Subtarget &Subtarget = AsmPrinter.getSubtarget();
     unsigned ReturnReg = Subtarget.is64Bit() ? X86::RAX : X86::EAX;
     OutMI = MCInst();
     OutMI.setOpcode(getRetOpcode(Subtarget));
     OutMI.addOperand(MCOperand::createReg(ReturnReg));
     break;
   }
 
-  // TAILJMPd, TAILJMPd64 - Lower to the correct jump instructions.
-  case X86::TAILJMPr:
+  // TAILJMPd, TAILJMPd64, TailJMPd_cc - Lower to the correct jump instructions.
+  { unsigned Opcode;
+  case X86::TAILJMPr:    Opcode = X86::JMP32r; goto SetTailJmpOpcode;
   case X86::TAILJMPd:
-  case X86::TAILJMPd64: {
-    unsigned Opcode;
-    switch (OutMI.getOpcode()) {
-    default: llvm_unreachable("Invalid opcode");
-    case X86::TAILJMPr: Opcode = X86::JMP32r; break;
-    case X86::TAILJMPd:
-    case X86::TAILJMPd64: Opcode = X86::JMP_1; break;
-    }
+  case X86::TAILJMPd64:  Opcode = X86::JMP_1; goto SetTailJmpOpcode;
+
+  case X86::TAILJMPd_O:  Opcode = X86::JO_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_NO: Opcode = X86::JNO_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_B:  Opcode = X86::JB_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_AE: Opcode = X86::JAE_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_E:  Opcode = X86::JE_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_NE: Opcode = X86::JNE_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_BE: Opcode = X86::JBE_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_A:  Opcode = X86::JA_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_S:  Opcode = X86::JS_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_NS: Opcode = X86::JNS_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_P:  Opcode = X86::JP_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_NP: Opcode = X86::JNP_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_L:  Opcode = X86::JL_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_GE: Opcode = X86::JGE_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_LE: Opcode = X86::JLE_1; goto SetTailJmpOpcode;
+  case X86::TAILJMPd_G:  Opcode = X86::JG_1; goto SetTailJmpOpcode;
 
+    SetTailJmpOpcode:
     MCOperand Saved = OutMI.getOperand(0);
     OutMI = MCInst();
     OutMI.setOpcode(Opcode);
     OutMI.addOperand(Saved);
     break;
   }
 
   case X86::DEC16r:
case X86::CATCHRET: {
     // Lower these as normal, but add some comments.
     OutStreamer->AddComment("CATCHRET");
     break;
   }
 
   case X86::TAILJMPr:
   case X86::TAILJMPm:
   case X86::TAILJMPd:
+  case X86::TAILJMPd_O:
+  case X86::TAILJMPd_NO:
+  case X86::TAILJMPd_B:
+  case X86::TAILJMPd_AE:
+  case X86::TAILJMPd_E:
+  case X86::TAILJMPd_NE:
+  case X86::TAILJMPd_BE:
+  case X86::TAILJMPd_A:
+  case X86::TAILJMPd_S:
+  case X86::TAILJMPd_NS:
+  case X86::TAILJMPd_P:
+  case X86::TAILJMPd_NP:
+  case X86::TAILJMPd_L:
+  case X86::TAILJMPd_GE:
+  case X86::TAILJMPd_LE:
+  case X86::TAILJMPd_G:
   case X86::TAILJMPr64:
   case X86::TAILJMPm64:
   case X86::TAILJMPd64:
   case X86::TAILJMPr64_REX:
   case X86::TAILJMPm64_REX:
   case X86::TAILJMPd64_REX:
     // Lower these as normal, but add some comments.
     OutStreamer->AddComment("TAILCALL");

test/CodeGen/X86/atom-pad-short-functions.ll

 
 bb2:
   ret i32 %b
 }
 
 define void @test_call_others(i32 %x) nounwind
 {
 ; CHECK: test_call_others
-; CHECK: je
   %tobool = icmp eq i32 %x, 0
   br i1 %tobool, label %if.end, label %true.case
 
-; CHECK: jmp external_function
+; CHECK: jne external_function
 true.case:
   tail call void bitcast (void (...)* @external_function to void ()*)() nounwind
   br label %if.end
 
 ; CHECK: nop
 ; CHECK: nop
 ; CHECK: nop
 ; CHECK: nop

test/CodeGen/X86/conditional-tailcall.ll

+; RUN: llc < %s -march=x86 -show-mc-encoding | FileCheck %s
+
+declare void @foo()
+declare void @bar()
+define void @f(i32 %x, i32 %y) {
+entry:
+  %p = icmp eq i32 %x, %y
+  br i1 %p, label %bb1, label %bb2
+bb1:
+  tail call void @foo()
+  ret void
+bb2:
+  tail call void @bar()
+  ret void
+}
+
+; CHECK-LABEL: f:
+; CHECK: cmp
+; CHECK: jne bar
+; CHECK: encoding: [0x75,A]
+
+; CHECK: jmp foo

test/CodeGen/X86/or-branch.ll

 ; RUN: llc < %s -mtriple=i386-unknown-unknown -jump-is-expensive=0 | FileCheck %s --check-prefix=JUMP2 --check-prefix=CHECK
 ; RUN: llc < %s -mtriple=i386-unknown-unknown -jump-is-expensive=1 | FileCheck %s --check-prefix=JUMP1 --check-prefix=CHECK
 
 define void @foo(i32 %X, i32 %Y, i32 %Z) nounwind {
 ; JUMP2-LABEL: foo:
 ; JUMP2-DAG:     jl
 ; JUMP2-DAG:     je
 ;
 ; JUMP1-LABEL: foo:
 ; JUMP1-DAG:     sete
 ; JUMP1-DAG:     setl
 ; JUMP1:         orb
-; JUMP1:         jne
+; JUMP1:         je
 entry:
   %tmp1 = icmp eq i32 %X, 0
   %tmp3 = icmp slt i32 %Y, 5
   %tmp4 = or i1 %tmp3, %tmp1
   br i1 %tmp4, label %cond_true, label %UnifiedReturnBlock
 
 cond_true:
   %tmp5 = tail call i32 (...) @bar( )
   ret void
 
 UnifiedReturnBlock:
   ret void
 }
 
 ; If the branch is unpredictable, don't add another branch
 ; regardless of whether they are expensive or not.
 
 define void @unpredictable(i32 %X, i32 %Y, i32 %Z) nounwind {
 ; CHECK-LABEL: unpredictable:
 ; CHECK-DAG:     sete
 ; CHECK-DAG:     setl
 ; CHECK:         orb
-; CHECK:         jne
+; CHECK:         je
 entry:
   %tmp1 = icmp eq i32 %X, 0
   %tmp3 = icmp slt i32 %Y, 5
   %tmp4 = or i1 %tmp3, %tmp1
   br i1 %tmp4, label %cond_true, label %UnifiedReturnBlock, !unpredictable !0
 
 cond_true:
   %tmp5 = tail call i32 (...) @bar( )

test/CodeGen/X86/sibcall.ll

 ; 32: calll {{_?}}t6
 ; 32: jmp {{_?}}bar
 
 ; 64-LABEL: t6:
 ; 64: jmp {{_?}}t6
 ; 64: jmp {{_?}}bar
 
 ; X32ABI-LABEL: t6:
+; X32ABI: jg {{_?}}bar
 ; X32ABI: jmp {{_?}}t6
-; X32ABI: jmp {{_?}}bar
   %0 = icmp slt i32 %x, 10
   br i1 %0, label %bb, label %bb1
 
 bb:
   %1 = add nsw i32 %x, -1
   %2 = tail call i32 @t6(i32 %1) nounwind ssp
   ret i32 %2
 

 
 declare i32 @foo4()
 
 define i32 @t11(i32 %x, i32 %y, i32 %z.0, i32 %z.1, i32 %z.2) nounwind ssp {
 ; In 32-bit mode, it's emitting a bunch of dead loads that are not being
 ; eliminated currently.
 
 ; 32-LABEL: t11:
+; 32: movl
+; 32: testl
 ; 32-NOT: subl ${{[0-9]+}}, %esp
-; 32: je
 ; 32-NOT: movl
 ; 32-NOT: addl ${{[0-9]+}}, %esp
-; 32: jmp {{_?}}foo5
+; 32: jne {{_?}}foo5
 
 ; 64-LABEL: t11:
 ; 64-NOT: subq ${{[0-9]+}}, %rsp
 ; 64-NOT: addq ${{[0-9]+}}, %rsp
 ; 64: jmp {{_?}}foo5
 
 ; X32ABI-LABEL: t11:
 ; X32ABI-NOT: subl ${{[0-9]+}}, %esp
 ; X32ABI-NOT: addl ${{[0-9]+}}, %esp
-; X32ABI: jmp {{_?}}foo5
+; X32ABI: jne {{_?}}foo5
 entry:
   %0 = icmp eq i32 %x, 0
   br i1 %0, label %bb6, label %bb
 
 bb:
   %1 = tail call i32 @foo5(i32 %x, i32 %y, i32 %z.0, i32 %z.1, i32 %z.2) nounwind
   ret i32 %1
 
 bb6:
   ret i32 0
 }
 
 declare i32 @foo5(i32, i32, i32, i32, i32)
 
 %struct.t = type { i32, i32, i32, i32, i32 }
 
 define i32 @t12(i32 %x, i32 %y, %struct.t* byval align 4 %z) nounwind ssp {
 ; 32-LABEL: t12:
 ; 32-NOT: subl ${{[0-9]+}}, %esp
 ; 32-NOT: addl ${{[0-9]+}}, %esp
-; 32: jmp {{_?}}foo6
+; 32: jne {{_?}}foo6
 
 ; 64-LABEL: t12:
 ; 64-NOT: subq ${{[0-9]+}}, %rsp
 ; 64-NOT: addq ${{[0-9]+}}, %rsp
 ; 64: jmp {{_?}}foo6
 
 ; X32ABI-LABEL: t12:
 ; X32ABI-NOT: subl ${{[0-9]+}}, %esp
 ; X32ABI-NOT: addl ${{[0-9]+}}, %esp
-; X32ABI: jmp {{_?}}foo6
+; X32ABI: jne {{_?}}foo6
 entry:
   %0 = icmp eq i32 %x, 0
   br i1 %0, label %bb2, label %bb
 
 bb:
   %1 = tail call i32 @foo6(i32 %x, i32 %y, %struct.t* byval align 4 %z) nounwind
   ret i32 %1
 

test/CodeGen/X86/xor-icmp.ll

 ; RUN: llc < %s -march=x86    | FileCheck %s -check-prefix=X32
 ; RUN: llc < %s -march=x86-64 | FileCheck %s -check-prefix=X64
 ; rdar://7367229
 
 define i32 @t(i32 %a, i32 %b) nounwind ssp {
 entry:
 ; X32-LABEL:     t:
 ; X32:     xorb
 ; X32-NOT: andb
 ; X32-NOT: shrb
 ; X32:     testb $64
-; X32:     je
+; X32:     jne
 
 ; X64-LABEL:     t:
 ; X64-NOT: setne
 ; X64:     xorl
 ; X64:     testb $64
 ; X64:     je
   %0 = and i32 %a, 16384
   %1 = icmp ne i32 %0, 0

 
 define i32 @t2(i32 %x, i32 %y) nounwind ssp {
 ; X32-LABEL: t2:
 ; X32: cmpl
 ; X32: sete
 ; X32: cmpl
 ; X32: sete
 ; X32-NOT: xor
-; X32: je
+; X32: jne
 
 ; X64-LABEL: t2:
 ; X64: testl
 ; X64: sete
 ; X64: testl
 ; X64: sete
 ; X64-NOT: xor
 ; X64: je