Using branch probability to guide critical edge splitting.

[danielcdh]

Summary

The original heuristic to break critical edge during machine sink is relatively conservertive: when there is only one instruction sinkable to the critical edge, it is likely that the machine sink pass will not break the critical edge. This leads to many speculative instructions executed at runtime. However, with profile info, we could model the splitting benefits: if the critical edge has 50% taken rate, it would always be beneficial to split the critical edge to avoid the speculated runtime instructions. This patch uses profile to guide critical edge splitting in machine sink pass.

The performance impact on speccpu2006 on Intel sandybridge machines:

spec/2006/fp/C++/444.namd 25.3 +0.26%
spec/2006/fp/C++/447.dealII 45.96 -0.10%
spec/2006/fp/C++/450.soplex 41.97 +1.49%
spec/2006/fp/C++/453.povray 36.83 -0.96%
spec/2006/fp/C/433.milc 23.81 +0.32%
spec/2006/fp/C/470.lbm 41.17 +0.34%
spec/2006/fp/C/482.sphinx3 48.13 +0.69%
spec/2006/int/C++/471.omnetpp 22.45 +3.25%
spec/2006/int/C++/473.astar 21.35 -2.06%
spec/2006/int/C++/483.xalancbmk 36.02 -2.39%
spec/2006/int/C/400.perlbench 33.7 -0.17%
spec/2006/int/C/401.bzip2 22.9 +0.52%
spec/2006/int/C/403.gcc 32.42 -0.54%
spec/2006/int/C/429.mcf 39.59 +0.19%
spec/2006/int/C/445.gobmk 26.98 -0.00%
spec/2006/int/C/456.hmmer 24.52 -0.18%
spec/2006/int/C/458.sjeng 28.26 +0.02%
spec/2006/int/C/462.libquantum 55.44 +3.74%
spec/2006/int/C/464.h264ref 46.67 -0.39%

geometric mean +0.20%

Manually checked 473 and 471 to verify the diff is in the noise range.

[danielcdh]

update

[danielcdh]

Lower the splitting threshold and put it in an option.

[davidxl]

test/CodeGen/X86/phys_subreg_coalesce-2.ll

18

What is this change about?

test/CodeGen/X86/pr2659.ll

17

What is this change about?

[danielcdh]

test/CodeGen/X86/phys_subreg_coalesce-2.ll

18

This patch will sink the mov to critical path, which appears after loop body. So the updates in the test changes to check that there is not "mov" in the loop body, i.e. between "forbody" and "jbe"

test/CodeGen/X86/pr2659.ll

17

The movl $1 will be sinked to critical edge, which is layouted after the loop body.

[davidxl]

test/CodeGen/X86/phys_subreg_coalesce-2.ll

18

should you check there is no move between forcond.preheader and for.body.preheader instead?

[davidxl]

Renato, can you help take a look at the changes in ARM test cases?

David

[danielcdh]

test/CodeGen/X86/phys_subreg_coalesce-2.ll

18

The purpose of the original test is to test if all moves are hoisted from loop body to loop header. With this patch, one of the hoisted move is sinked to critical edge (still outside loop body), but there are still moves in the preheader thus it will be hard to check specific move has been sinked (as they could be assigned any register).

We have other tests to cover test cases where instructions should be sinked to critical edge, thus maybe in this patch, we just maintain the original check without adding new check for the machine sink?

[davidxl]

test/CodeGen/X86/phys_subreg_coalesce-2.ll

18

Ok. Perhaps just a comment that there is no mov in loop body.

[danielcdh]

update

[davidxl]

Can you also add an explicit test case ?

test/CodeGen/ARM/code-placement.ll

15–17

Can you change it to use lit variable for the label ?

35

The layout change in function 't2' is weird -- there are unnecessary branch back and forth introduced. Can you check why (not directly related to this patch -- but triggers some bugs).

[danielcdh]

update and add new test

[davidxl]

test/CodeGen/ARM/code-placement.ll

35

I looked at this a little more. The layout change is caused by loop rotation (in MBP) exposed. The loop rotation here is beneficial because the Freq of the outer loop's back edge is larger than the sum of the exit edge of the inner loop and the incoming edge of the outer loop.

[danielcdh]

oops, my original comment about t2 was unsubmitted...

I think the if-conversion leads to the loop rotation difference as observed by David?

test/CodeGen/ARM/code-placement.ll

35

For t2, there are originally 2 conditional jumps in level-1 loop. machine sink splitted one critical edge, making it able to be if-converted later (by machine if-converter). As a result, there is one less conditional jump in the level-1 loop, and thus the other conditional jump needs to become backedge, and thus need to have one unconditional branch from l-1 loop preheader to header.

[davidxl]

yes, loop rotation is caused by ifconvert. The cfg does not have an edge to the function with predicated exit sequence like this:

add r12, r12, #1
cmp r12, r0
moveq r0, r1
popeq {r4, pc}
b LBB0_1

This looks like an unconditional loop backedge, which leads to MBP to consider this block a candidate to be loop top. With a better loop rotation algorithm, this opportunity should be discovered even when CFG is properly modeled.

[danielcdh]

Ping...

Renato, could you help take a look at this patch?

Thanks,
Dehao

[davidxl]

A related comment -- (no need to be addressed here):

If a instruction defines value that is used via more than one cold edges (split or to be split), the MachineSink should probably be enhanced to let it sunk. For instance in the attached the CFG, mov $0x8000000, %r12d should be sunk into La0, Lb0 and Lb7 from L40.

digraph foo {
node [shape=box]
size="11,8.5"
_exit_ [label="_exit_\n ", style=filled, color=gray]
L0000000000000000 [label="L0000000000000000\n<foo>: \n ", style=filled, color=gray]
L0 [label="L0\npush %rbp \n ", style=filled, color=gray]
L1 [label="L1\npush %r15 \npush %r14 \n ", style=filled, color=gray]
L5 [label="L5\npush %r13 \n ", style=filled, color=gray]
L7 [label="L7\npush %r12 \npush %rbx \n ", style=filled, color=gray]
La [label="La\nsub $0x18,%rsp \n ", style=filled, color=gray]
Le [label="Le\nmov %rcx,%r14 \nmov %esi,%ebp \ntest %ebp,%ebp \njle e7 <foo+0xe7>\n ", style=filled, color=gray]
L1b [label="L1b\n.. \n ", style=filled, color=gray]
L40 [label="L40\n..\nmov $0x80000000,%r12d \ntest %eax,%eax \njs a0 <foo+0xa0>\n ", style=filled, color=gray]
L52 [label="L52\n..\njs b0 <foo+0xb0>\n ", style=filled, color=gray]
L5f [label="L5f\n..\njs b7 <foo+0xb7>\n ", style=filled, color=gray]
L71 [label="L71\n..\nmov %eax,%r12d \nand $0x80000000,%r12d \n..jmp c0 <foo+0xc0>\n", style=filled, color=gray]
La0 [label="La0\nxor %ebx,%ebx \njmp c0 <foo+0xc0>\ndata32 data32 nopw\n ", style=filled, color=gray]
Lb0 [label="Lb0\nmov $0x1,%ebx \njmp c0 <foo+0xc0>\n ", style=filled, color=gray]
Lb7 [label="Lb7\nmov $0x2,%ebx \nnopl 0x0(%rax) \n ", style=filled, color=gray]
Lc0 [label="Lc0\nmov %ebx,%edi \nmov %r12d,%esi \ncallq ca <foo+0xca>\nxor %eax,%eax \n.. \njs df <foo+0xdf>\n ", style=filled, color=gray]
Ld5 [label="Ld5\nmov %ebx,%edi \nmov %r12d,%esi \ncallq df <foo+0xdf>\n ", style=filled, color=gray]
Ldf [label="Ldf\ndec %ebp \njne 40 <foo+0x40>\n ", style=filled, color=gray]
Le7 [label="Le7\nadd $0x18,%rsp \npop %rbx \npop %r12 \npop %r13 \npop %r14 \npop %r15 \npop %rbp \nretq \n ", style=filled, color=gray]
L0000000000000000 -> L0 ;
L0 -> L1 ;
L1 -> L5 ;
L5 -> L7 ;
L7 -> La ;
La -> Le ;
Le -> Le7 ;
Le -> L1b ;
L1b -> L40 ;
L40 -> La0 ;
L40 -> L52 ;
L52 -> Lb0 ;
L52 -> L5f ;
L5f -> Lb7 ;
L5f -> L71 ;
L71 -> Lc0 ;
La0 -> Lc0 ;
Lb0 -> Lc0 ;
Lb7 -> Lc0 ;
Lc0 -> Ldf ;
Lc0 -> Ld5 ;
Ld5 -> Ldf ;
Ldf -> L40 ;
Ldf -> Le7 ;
Le7 -> _exit_ ;
}

[danielcdh]

ping...

[davidxl]

lgtm

(The branch threshold may need to be more biased but we won't know for sure for now. May need to tune it ..)

[danielcdh]

update new failing testcase.

[danielcdh]

This introduced ppc build failure as MachineBranchProbabilityInfo has not be declared as dependency.

[danielcdh]

add dependency.

[danielcdh]

add machine-sink

[danielcdh]

reopen again for bug fixing...

[danielcdh]

fix the bug

[danielcdh]

The bug is fixed:

The assumption "From->isSuccessor(To)" is untrue before calling MBPI->getEdgeProbability(From, To). Add check to make sure From->To edge exists before checking edge probability.

lib/CodeGen/MachineSink.cpp

 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
+#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachinePostDominators.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
namespace {
   class MachineSinking : public MachineFunctionPass {
     const TargetInstrInfo *TII;
     const TargetRegisterInfo *TRI;
     MachineRegisterInfo  *MRI;     // Machine register information
     MachineDominatorTree *DT;      // Machine dominator tree
     MachinePostDominatorTree *PDT; // Machine post dominator tree
     MachineLoopInfo *LI;
     const MachineBlockFrequencyInfo *MBFI;
+    const MachineBranchProbabilityInfo *MBPI;
     AliasAnalysis *AA;
 
     // Remember which edges have been considered for breaking.
     SmallSet<std::pair<MachineBasicBlock*, MachineBasicBlock*>, 8>
     CEBCandidates;
     // Remember which edges we are about to split.
     // This is different from CEBCandidates since those edges
     // will be split.
public:
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       MachineFunctionPass::getAnalysisUsage(AU);
       AU.addRequired<AAResultsWrapperPass>();
       AU.addRequired<MachineDominatorTree>();
       AU.addRequired<MachinePostDominatorTree>();
       AU.addRequired<MachineLoopInfo>();
+      AU.addRequired<MachineBranchProbabilityInfo>();
       AU.addPreserved<MachineDominatorTree>();
       AU.addPreserved<MachinePostDominatorTree>();
       AU.addPreserved<MachineLoopInfo>();
+      AU.addPreserved<MachineBranchProbabilityInfo>();
       if (UseBlockFreqInfo)
         AU.addRequired<MachineBlockFrequencyInfo>();
     }
 
     void releaseMemory() override {
       CEBCandidates.clear();
     }
 
bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {
 
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
   DT = &getAnalysis<MachineDominatorTree>();
   PDT = &getAnalysis<MachinePostDominatorTree>();
   LI = &getAnalysis<MachineLoopInfo>();
   MBFI = UseBlockFreqInfo ? &getAnalysis<MachineBlockFrequencyInfo>() : nullptr;
+  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
   AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 
   bool EverMadeChange = false;
 
   while (true) {
     bool MadeChange = false;
 
     // Process all basic blocks.
bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr &MI,
   // through the function), then let's go ahead and break it. This means
   // sinking multiple "cheap" instructions into the same block.
   if (!CEBCandidates.insert(std::make_pair(From, To)).second)
     return true;
 
   if (!MI.isCopy() && !TII->isAsCheapAsAMove(MI))
     return true;
 
+  if (MBPI->getEdgeProbability(From, To) < BranchProbability(50, 100))
+    return true;
+
   // MI is cheap, we probably don't want to break the critical edge for it.
   // However, if this would allow some definitions of its source operands
   // to be sunk then it's probably worth it.
   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     const MachineOperand &MO = MI.getOperand(i);
     if (!MO.isReg() || !MO.isUse())
       continue;
     unsigned Reg = MO.getReg();

test/CodeGen/ARM/atomic-cmpxchg.ll

 ; CHECK-THUMB: push  {[[R2]]}
 ; CHECK-THUMB: pop {r0}
 
 ; CHECK-ARMV6-LABEL: test_cmpxchg_res_i8:
 ; CHECK-ARMV6-NEXT:  .fnstart
 ; CHECK-ARMV6-NEXT: uxtb [[DESIRED:r[0-9]+]], r1
 ; CHECK-ARMV6-NEXT: [[TRY:.LBB[0-9_]+]]:
 ; CHECK-ARMV6-NEXT: ldrexb [[LD:r[0-9]+]], [r0]
-; CHECK-ARMV6-NEXT: mov [[RES:r[0-9]+]], #0
 ; CHECK-ARMV6-NEXT: cmp [[LD]], [[DESIRED]]
-; CHECK-ARMV6-NEXT: bne [[END:.LBB[0-9_]+]]
+; CHECK-ARMV6-NEXT: movne [[RES:r[0-9]+]], #0
+; CHECK-ARMV6-NEXT: bxne lr
 ; CHECK-ARMV6-NEXT: strexb [[SUCCESS:r[0-9]+]], r2, [r0]
-; CHECK-ARMV6-NEXT: mov [[RES]], #1
 ; CHECK-ARMV6-NEXT: cmp [[SUCCESS]], #0
-; CHECK-ARMV6-NEXT: bne [[TRY]]
-; CHECK-ARMV6-NEXT: [[END]]:
-; CHECK-ARMV6-NEXT: mov r0, [[RES]]
-; CHECK-ARMV6-NEXT: bx lr
+; CHECK-ARMV6-NEXT: moveq [[RES]], #1
+; CHECK-ARMV6-NEXT: bxeq lr
+; CHECK-ARMV6-NEXT: b [[TRY]]
 
 ; CHECK-THUMBV6-LABEL: test_cmpxchg_res_i8:
 ; CHECK-THUMBV6:       mov [[EXPECTED:r[0-9]+]], r1
 ; CHECK-THUMBV6-NEXT:  bl __sync_val_compare_and_swap_1
 ; CHECK-THUMBV6-NEXT:  mov [[RES:r[0-9]+]], r0
 ; CHECK-THUMBV6-NEXT:  movs r0, #1
 ; CHECK-THUMBV6-NEXT:  movs [[ZERO:r[0-9]+]], #0
 ; CHECK-THUMBV6-NEXT:  cmp [[RES]], [[EXPECTED]]
 ; CHECK-THUMBV6-NEXT:  beq [[END:.LBB[0-9_]+]]
 ; CHECK-THUMBV6-NEXT:  mov r0, [[ZERO]]
 ; CHECK-THUMBV6-NEXT: [[END]]:
 ; CHECK-THUMBV6-NEXT:  pop {{.*}}pc}
 
 ; CHECK-ARMV7-LABEL: test_cmpxchg_res_i8:
 ; CHECK-ARMV7-NEXT: .fnstart
 ; CHECK-ARMV7-NEXT: uxtb [[DESIRED:r[0-9]+]], r1
-; CHECK-ARMV7-NEXT: [[TRY:.LBB[0-9_]+]]:
-; CHECK-ARMV7-NEXT: ldrexb [[LD:r[0-9]+]], [r0]
-; CHECK-ARMV7-NEXT: cmp [[LD]], [[DESIRED]]
-; CHECK-ARMV7-NEXT: bne [[FAIL:.LBB[0-9_]+]]
+; CHECK-ARMV7-NEXT: b [[TRY:.LBB[0-9_]+]]
+; CHECK-ARMV7-NEXT: [[HEAD:.LBB[0-9_]+]]:
 ; CHECK-ARMV7-NEXT: strexb [[SUCCESS:r[0-9]+]], r2, [r0]
-; CHECK-ARMV7-NEXT: mov [[RES:r[0-9]+]], #1
 ; CHECK-ARMV7-NEXT: cmp [[SUCCESS]], #0
-; CHECK-ARMV7-NEXT: bne [[TRY]]
-; CHECK-ARMV7-NEXT: b [[END:.LBB[0-9_]+]]
-; CHECK-ARMV7-NEXT: [[FAIL]]:
+; CHECK-ARMV7-NEXT: moveq [[RES:r[0-9]+]], #1
+; CHECK-ARMV7-NEXT: bxeq lr
+; CHECK-ARMV7-NEXT: [[TRY]]:
+; CHECK-ARMV7-NEXT: ldrexb [[LD:r[0-9]+]], [r0]
+; CHECK-ARMV7-NEXT: cmp [[LD]], [[DESIRED]]
+; CHECK-ARMV7-NEXT: beq [[HEAD]]
 ; CHECK-ARMV7-NEXT: clrex
 ; CHECK-ARMV7-NEXT: mov [[RES]], #0
-; CHECK-ARMV7-NEXT: [[END]]:
-; CHECK-ARMV7-NEXT: mov r0, [[RES]]
 ; CHECK-ARMV7-NEXT: bx lr
 
 ; CHECK-THUMBV7-LABEL: test_cmpxchg_res_i8:
 ; CHECK-THUMBV7-NEXT: .fnstart
 ; CHECK-THUMBV7-NEXT: uxtb [[DESIRED:r[0-9]+]], r1
 ; CHECK-THUMBV7-NEXT: b [[TRYLD:.LBB[0-9_]+]]
 ; CHECK-THUMBV7-NEXT: [[TRYST:.LBB[0-9_]+]]:
 ; CHECK-THUMBV7-NEXT: strexb [[SUCCESS:r[0-9]+]], r2, [r0]

test/CodeGen/ARM/code-placement.ll

 ; RUN: llc < %s -mtriple=armv7-apple-darwin | FileCheck %s
 ; PHI elimination shouldn't break backedge.
 ; rdar://8263994
 
 %struct.list_data_s = type { i16, i16 }
 %struct.list_head = type { %struct.list_head*, %struct.list_data_s* }
 
 define arm_apcscc %struct.list_head* @t1(%struct.list_head* %list) nounwind {
 entry:
 ; CHECK-LABEL: t1:
   %0 = icmp eq %struct.list_head* %list, null
   br i1 %0, label %bb2, label %bb
 
 bb:
-; CHECK: LBB0_2:
-; CHECK: bne LBB0_2
-; CHECK-NOT: b LBB0_2
+; CHECK: LBB0_1:
+; CHECK: bne LBB0_1
+; CHECK-NOT: b LBB0_1
 ; CHECK: bx lr
   %list_addr.05 = phi %struct.list_head* [ %2, %bb ], [ %list, %entry ]
   %next.04 = phi %struct.list_head* [ %list_addr.05, %bb ], [ null, %entry ]
   %1 = getelementptr inbounds %struct.list_head, %struct.list_head* %list_addr.05, i32 0, i32 0
   %2 = load %struct.list_head*, %struct.list_head** %1, align 4
   store %struct.list_head* %next.04, %struct.list_head** %1, align 4
   %3 = icmp eq %struct.list_head* %2, null
   br i1 %3, label %bb2, label %bb
 
 bb2:
   %next.0.lcssa = phi %struct.list_head* [ null, %entry ], [ %list_addr.05, %bb ]
   ret %struct.list_head* %next.0.lcssa
 }
 
 ; Optimize loop entry, eliminate intra loop branches
 ; rdar://8117827
 define i32 @t2(i32 %passes, i32* nocapture %src, i32 %size) nounwind readonly {
 entry:
 ; CHECK-LABEL: t2:
-; CHECK: beq LBB1_[[RET:.]]
   %0 = icmp eq i32 %passes, 0                     ; <i1> [#uses=1]
   br i1 %0, label %bb5, label %bb.nph15
 
-; CHECK: LBB1_[[PREHDR:.]]: @ %bb2.preheader
 bb1:                                              ; preds = %bb2.preheader, %bb1
-; CHECK: LBB1_[[BB1:.]]: @ %bb1
-; CHECK: bne LBB1_[[BB1]]
+; CHECK: LBB1_[[BB3:.]]: @ %bb3
+; CHECK: LBB1_[[PREHDR:.]]: @ %bb2.preheader
+; CHECK: blt LBB1_[[BB3]]
   %indvar = phi i32 [ %indvar.next, %bb1 ], [ 0, %bb2.preheader ] ; <i32> [#uses=2]
   %sum.08 = phi i32 [ %2, %bb1 ], [ %sum.110, %bb2.preheader ] ; <i32> [#uses=1]
   %tmp17 = sub i32 %i.07, %indvar                 ; <i32> [#uses=1]
   %scevgep = getelementptr i32, i32* %src, i32 %tmp17  ; <i32*> [#uses=1]
   %1 = load i32, i32* %scevgep, align 4                ; <i32> [#uses=1]
   %2 = add nsw i32 %1, %sum.08                    ; <i32> [#uses=2]
   %indvar.next = add i32 %indvar, 1               ; <i32> [#uses=2]
   %exitcond = icmp eq i32 %indvar.next, %size     ; <i1> [#uses=1]
   br i1 %exitcond, label %bb3, label %bb1
 
 bb3:                                              ; preds = %bb1, %bb2.preheader
-; CHECK: LBB1_[[BB3:.]]: @ %bb3
-; CHECK: bne LBB1_[[PREHDR]]
-; CHECK-NOT: b LBB1_
+; CHECK: LBB1_[[BB1:.]]: @ %bb1
+; CHECK: bne LBB1_[[BB1]]
+; CHECK: b LBB1_[[BB3]]
   %sum.0.lcssa = phi i32 [ %sum.110, %bb2.preheader ], [ %2, %bb1 ] ; <i32> [#uses=2]
   %3 = add i32 %pass.011, 1                       ; <i32> [#uses=2]
   %exitcond18 = icmp eq i32 %3, %passes           ; <i1> [#uses=1]
   br i1 %exitcond18, label %bb5, label %bb2.preheader
 
 bb.nph15:                                         ; preds = %entry
   %i.07 = add i32 %size, -1                       ; <i32> [#uses=2]
   %4 = icmp sgt i32 %i.07, -1                     ; <i1> [#uses=1]
   br label %bb2.preheader
 
 bb2.preheader:                                    ; preds = %bb3, %bb.nph15
   %pass.011 = phi i32 [ 0, %bb.nph15 ], [ %3, %bb3 ] ; <i32> [#uses=1]
   %sum.110 = phi i32 [ 0, %bb.nph15 ], [ %sum.0.lcssa, %bb3 ] ; <i32> [#uses=2]
   br i1 %4, label %bb1, label %bb3
 
-; CHECK: LBB1_[[RET]]: @ %bb5
-; CHECK: pop
 bb5:                                              ; preds = %bb3, %entry
   %sum.1.lcssa = phi i32 [ 0, %entry ], [ %sum.0.lcssa, %bb3 ] ; <i32> [#uses=1]
   ret i32 %sum.1.lcssa
 }

test/CodeGen/X86/clz.ll

; X64-CLZ-NEXT:    retq
   %tmp = call i64 @llvm.ctlz.i64( i64 %x, i1 true )
   ret i64 %tmp
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i8 @ctlz_i8_zero_test(i8 %n) {
 ; X32-LABEL: ctlz_i8_zero_test:
 ; X32:       # BB#0:
-; X32-NEXT:    movb {{[0-9]+}}(%esp), %cl
-; X32-NEXT:    movb $8, %al
-; X32-NEXT:    testb %cl, %cl
-; X32-NEXT:    je .LBB8_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    movzbl %cl, %eax
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %al
+; X32-NEXT:    testb %al, %al
+; X32-NEXT:    je .LBB8_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    movzbl %al, %eax
 ; X32-NEXT:    bsrl %eax, %eax
 ; X32-NEXT:    xorl $7, %eax
-; X32-NEXT:  .LBB8_2: # %cond.end
+; X32-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB8_1:
+; X32-NEXT:    movb    $8, %al
 ; X32-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ctlz_i8_zero_test:
 ; X64:       # BB#0:
-; X64-NEXT:    movb $8, %al
 ; X64-NEXT:    testb %dil, %dil
-; X64-NEXT:    je .LBB8_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB8_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    movzbl %dil, %eax
 ; X64-NEXT:    bsrl %eax, %eax
 ; X64-NEXT:    xorl $7, %eax
-; X64-NEXT:  .LBB8_2: # %cond.end
+; X64-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB8_1:
+; X64-NEXT:    movb    $8, %al
 ; X64-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: ctlz_i8_zero_test:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X32-CLZ-NEXT:    lzcntl %eax, %eax
 ; X32-CLZ-NEXT:    addl $-24, %eax
; X64-CLZ-NEXT:    retq
   %tmp1 = call i8 @llvm.ctlz.i8(i8 %n, i1 false)
   ret i8 %tmp1
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i16 @ctlz_i16_zero_test(i16 %n) {
 ; X32-LABEL: ctlz_i16_zero_test:
 ; X32:       # BB#0:
-; X32-NEXT:    movzwl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movw $16, %ax
-; X32-NEXT:    testw %cx, %cx
-; X32-NEXT:    je .LBB9_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    bsrw %cx, %ax
+; X32-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
+; X32-NEXT:    testw %ax, %ax
+; X32-NEXT:    je .LBB9_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    bsrw %ax, %ax
 ; X32-NEXT:    xorl $15, %eax
-; X32-NEXT:  .LBB9_2: # %cond.end
+; X32-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB9_1:
+; X32-NEXT:    movw    $16, %ax
 ; X32-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ctlz_i16_zero_test:
 ; X64:       # BB#0:
-; X64-NEXT:    movw $16, %ax
 ; X64-NEXT:    testw %di, %di
-; X64-NEXT:    je .LBB9_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB9_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    bsrw %di, %ax
 ; X64-NEXT:    xorl $15, %eax
-; X64-NEXT:  .LBB9_2: # %cond.end
+; X64-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB9_1:
+; X64-NEXT:    movw $16, %ax
 ; X64-NEXT:    # kill: %AX<def> %AX<kill> %EAX<kill>
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: ctlz_i16_zero_test:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    lzcntw {{[0-9]+}}(%esp), %ax
 ; X32-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: ctlz_i16_zero_test:
 ; X64-CLZ:       # BB#0:
 ; X64-CLZ-NEXT:    lzcntw %di, %ax
 ; X64-CLZ-NEXT:    retq
   %tmp1 = call i16 @llvm.ctlz.i16(i16 %n, i1 false)
   ret i16 %tmp1
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i32 @ctlz_i32_zero_test(i32 %n) {
 ; X32-LABEL: ctlz_i32_zero_test:
 ; X32:       # BB#0:
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl $32, %eax
-; X32-NEXT:    testl %ecx, %ecx
-; X32-NEXT:    je .LBB10_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    bsrl %ecx, %eax
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X32-NEXT:    testl %eax, %eax
+; X32-NEXT:    je .LBB10_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    bsrl %eax, %eax
 ; X32-NEXT:    xorl $31, %eax
-; X32-NEXT:  .LBB10_2: # %cond.end
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB10_1:
+; X32-NEXT:    movl    $32, %eax
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ctlz_i32_zero_test:
 ; X64:       # BB#0:
-; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    testl %edi, %edi
-; X64-NEXT:    je .LBB10_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB10_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    bsrl %edi, %eax
 ; X64-NEXT:    xorl $31, %eax
-; X64-NEXT:  .LBB10_2: # %cond.end
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB10_1:
+; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: ctlz_i32_zero_test:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    lzcntl {{[0-9]+}}(%esp), %eax
 ; X32-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: ctlz_i32_zero_test:
; X64-CLZ-NEXT:    retq
   %tmp1 = call i64 @llvm.ctlz.i64(i64 %n, i1 false)
   ret i64 %tmp1
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i8 @cttz_i8_zero_test(i8 %n) {
 ; X32-LABEL: cttz_i8_zero_test:
 ; X32:       # BB#0:
-; X32-NEXT:    movb {{[0-9]+}}(%esp), %cl
-; X32-NEXT:    movb $8, %al
-; X32-NEXT:    testb %cl, %cl
-; X32-NEXT:    je .LBB12_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    movzbl %cl, %eax
+; X32-NEXT:    movb {{[0-9]+}}(%esp), %al
+; X32-NEXT:    testb %al, %al
+; X32-NEXT:    je .LBB12_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    movzbl %al, %eax
 ; X32-NEXT:    bsfl %eax, %eax
-; X32-NEXT:  .LBB12_2: # %cond.end
+; X32-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB12_1
+; X32-NEXT:    movb $8, %al
 ; X32-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i8_zero_test:
 ; X64:       # BB#0:
-; X64-NEXT:    movb $8, %al
 ; X64-NEXT:    testb %dil, %dil
-; X64-NEXT:    je .LBB12_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB12_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    movzbl %dil, %eax
 ; X64-NEXT:    bsfl %eax, %eax
-; X64-NEXT:  .LBB12_2: # %cond.end
+; X64-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB12_1:
+; X64-NEXT:    movb $8, %al
 ; X64-NEXT:    # kill: %AL<def> %AL<kill> %EAX<kill>
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: cttz_i8_zero_test:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    movzbl {{[0-9]+}}(%esp), %eax
 ; X32-CLZ-NEXT:    orl $256, %eax # imm = 0x100
 ; X32-CLZ-NEXT:    tzcntl %eax, %eax
; X64-CLZ-NEXT:    retq
   %tmp1 = call i8 @llvm.cttz.i8(i8 %n, i1 false)
   ret i8 %tmp1
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i16 @cttz_i16_zero_test(i16 %n) {
 ; X32-LABEL: cttz_i16_zero_test:
 ; X32:       # BB#0:
-; X32-NEXT:    movzwl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movzwl {{[0-9]+}}(%esp), %eax
+; X32-NEXT:    testw %ax, %ax
+; X32-NEXT:    je .LBB13_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    bsfw %ax, %ax
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB13_1
 ; X32-NEXT:    movw $16, %ax
-; X32-NEXT:    testw %cx, %cx
-; X32-NEXT:    je .LBB13_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    bsfw %cx, %ax
-; X32-NEXT:  .LBB13_2: # %cond.end
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i16_zero_test:
 ; X64:       # BB#0:
-; X64-NEXT:    movw $16, %ax
 ; X64-NEXT:    testw %di, %di
-; X64-NEXT:    je .LBB13_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB13_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    bsfw %di, %ax
-; X64-NEXT:  .LBB13_2: # %cond.end
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB13_1:
+; X64-NEXT:    movw $16, %ax
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: cttz_i16_zero_test:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    tzcntw {{[0-9]+}}(%esp), %ax
 ; X32-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: cttz_i16_zero_test:
 ; X64-CLZ:       # BB#0:
 ; X64-CLZ-NEXT:    tzcntw %di, %ax
 ; X64-CLZ-NEXT:    retq
   %tmp1 = call i16 @llvm.cttz.i16(i16 %n, i1 false)
   ret i16 %tmp1
 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 define i32 @cttz_i32_zero_test(i32 %n) {
 ; X32-LABEL: cttz_i32_zero_test:
 ; X32:       # BB#0:
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X32-NEXT:    testl %eax, %eax
+; X32-NEXT:    je .LBB14_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    bsfl %eax, %eax
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB14_1
 ; X32-NEXT:    movl $32, %eax
-; X32-NEXT:    testl %ecx, %ecx
-; X32-NEXT:    je .LBB14_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    bsfl %ecx, %eax
-; X32-NEXT:  .LBB14_2: # %cond.end
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: cttz_i32_zero_test:
 ; X64:       # BB#0:
-; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    testl %edi, %edi
-; X64-NEXT:    je .LBB14_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB14_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    bsfl %edi, %eax
-; X64-NEXT:  .LBB14_2: # %cond.end
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB14_1:
+; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: cttz_i32_zero_test:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    tzcntl {{[0-9]+}}(%esp), %eax
 ; X32-CLZ-NEXT:    retl
 ;
 ; X64-CLZ-LABEL: cttz_i32_zero_test:

 ; Don't generate the cmovne when the source is known non-zero (and bsr would
 ; not set ZF).
 ; rdar://9490949
 ; FIXME: The compare and branch are produced late in IR (by CodeGenPrepare), and
 ;        codegen doesn't know how to delete the movl and je.
 define i32 @ctlz_i32_fold_cmov(i32 %n) {
 ; X32-LABEL: ctlz_i32_fold_cmov:
 ; X32:       # BB#0:
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    orl $1, %ecx
-; X32-NEXT:    movl $32, %eax
-; X32-NEXT:    je .LBB16_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    bsrl %ecx, %eax
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X32-NEXT:    orl $1, %eax
+; X32-NEXT:    je .LBB16_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    bsrl %eax, %eax
 ; X32-NEXT:    xorl $31, %eax
-; X32-NEXT:  .LBB16_2: # %cond.end
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB16_1
+; X32-NEXT:    movl $32, %eax
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ctlz_i32_fold_cmov:
 ; X64:       # BB#0:
 ; X64-NEXT:    orl $1, %edi
-; X64-NEXT:    movl $32, %eax
-; X64-NEXT:    je .LBB16_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB16_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    bsrl %edi, %eax
 ; X64-NEXT:    xorl $31, %eax
-; X64-NEXT:  .LBB16_2: # %cond.end
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB16_1:
+; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: ctlz_i32_fold_cmov:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X32-CLZ-NEXT:    orl $1, %eax
 ; X32-CLZ-NEXT:    lzcntl %eax, %eax
 ; X32-CLZ-NEXT:    retl

 }
 
 ; Generate a test and branch to handle zero inputs because bsr/bsf are very slow.
 ; FIXME: The compare and branch are produced late in IR (by CodeGenPrepare), and
 ;        codegen doesn't know how to combine the $32 and $31 into $63.
 define i32 @ctlz_bsr_zero_test(i32 %n) {
 ; X32-LABEL: ctlz_bsr_zero_test:
 ; X32:       # BB#0:
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl $32, %eax
-; X32-NEXT:    testl %ecx, %ecx
-; X32-NEXT:    je .LBB18_2
-; X32-NEXT:  # BB#1: # %cond.false
-; X32-NEXT:    bsrl %ecx, %eax
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
+; X32-NEXT:    testl %eax, %eax
+; X32-NEXT:    je .LBB18_1
+; X32-NEXT:  # BB#2: # %cond.false
+; X32-NEXT:    bsrl %eax, %eax
+; X32-NEXT:    xorl $31, %eax
 ; X32-NEXT:    xorl $31, %eax
-; X32-NEXT:  .LBB18_2: # %cond.end
+; X32-NEXT:    retl
+; X32-NEXT:  .LBB18_1:
+; X32-NEXT:    movl $32, %eax
 ; X32-NEXT:    xorl $31, %eax
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: ctlz_bsr_zero_test:
 ; X64:       # BB#0:
-; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    testl %edi, %edi
-; X64-NEXT:    je .LBB18_2
-; X64-NEXT:  # BB#1: # %cond.false
+; X64-NEXT:    je .LBB18_1
+; X64-NEXT:  # BB#2: # %cond.false
 ; X64-NEXT:    bsrl %edi, %eax
 ; X64-NEXT:    xorl $31, %eax
-; X64-NEXT:  .LBB18_2: # %cond.end
+; X64-NEXT:    xorl $31, %eax
+; X64-NEXT:    retq
+; X64-NEXT:  .LBB18_1:
+; X64-NEXT:    movl $32, %eax
 ; X64-NEXT:    xorl $31, %eax
 ; X64-NEXT:    retq
 ;
 ; X32-CLZ-LABEL: ctlz_bsr_zero_test:
 ; X32-CLZ:       # BB#0:
 ; X32-CLZ-NEXT:    lzcntl {{[0-9]+}}(%esp), %eax
 ; X32-CLZ-NEXT:    xorl $31, %eax
 ; X32-CLZ-NEXT:    retl

test/CodeGen/X86/phys_subreg_coalesce-2.ll

 forcond.preheader:    ; preds = %entry
   %cmp44 = icmp eq i32 %k, 0    ; <i1> [#uses=1]
   br i1 %cmp44, label %afterfor, label %forbody
 
 ifthen:   ; preds = %entry
   ret i32 0
 ; CHECK: forbody{{$}}
 ; CHECK-NOT: mov
+; CHECK: jbe
 forbody:    ; preds = %forbody, %forcond.preheader
   %indvar = phi i32 [ 0, %forcond.preheader ], [ %divisor.02, %forbody ]    ; <i32> [#uses=3]
   %accumulator.01 = phi i32 [ 1, %forcond.preheader ], [ %div, %forbody ]    ; <i32> [#uses=1]
   %divisor.02 = add i32 %indvar, 1    ; <i32> [#uses=2]
   %n.addr.03 = sub i32 %n, %indvar    ; <i32> [#uses=1]
   %mul = mul i32 %n.addr.03, %accumulator.01    ; <i32> [#uses=1]
   %div = udiv i32 %mul, %divisor.02   ; <i32> [#uses=2]
   %inc = add i32 %indvar, 2   ; <i32> [#uses=1]
   %cmp4 = icmp ugt i32 %inc, %k    ; <i1> [#uses=1]
   br i1 %cmp4, label %afterfor, label %forbody
 
 afterfor:   ; preds = %forbody, %forcond.preheader
   %accumulator.0.lcssa = phi i32 [ 1, %forcond.preheader ], [ %div, %forbody ]    ; <i32> [#uses=1]
   ret i32 %accumulator.0.lcssa
 }

test/CodeGen/X86/pr2659.ll

 ; RUN: llc < %s -march=x86 -mtriple=i686-apple-darwin9.4.0 -disable-branch-fold | FileCheck %s
 ; PR2659
 
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:128:128"
 target triple = "i686-apple-darwin9.4.0"
 
 define i32 @binomial(i32 %n, i32 %k) nounwind  {
 entry:
   %cmp = icmp ugt i32 %k, %n            ; <i1> [#uses=1]
   br i1 %cmp, label %ifthen, label %forcond.preheader
 
 forcond.preheader:              ; preds = %entry
   %cmp44 = icmp eq i32 %k, 0            ; <i1> [#uses=1]
   br i1 %cmp44, label %afterfor, label %forbody
 
 ; CHECK: %forcond.preheader
-; CHECK: movl $1
+; CHECK: testl
 ; CHECK-NOT: xorl
 ; CHECK-NOT: movl
 ; CHECK-NOT: LBB
 ; CHECK: je
 
 ; There should be no moves required in the for loop body.
 ; CHECK: %forbody{{$}}
 ; CHECK-NOT: mov