Tail merge size

[avt77]

Summary

The issue described here: https://bugs.llvm.org/show_bug.cgi?id=32802. I only changed the default value of tail-merge-size option from 2 to 3. As result several tests were changed but the main problem described in https://bugs.llvm.org/show_bug.cgi?id=27136 were successfully resolved.
The compilation time was increased by 3 sec only (from 2840 to 2843). The common size of executables inside bin folder was decreased by 1M.
I'm thinking we should use tail-merge-size=1 in case of size optimization: I'm ready to implement it quickly.

[RKSimon]

A few minors, but I'd prefer someone more knowledgable in this area to review it.

You may need to bring in some ARM/AMDGPU/PowerPC guys too ?

test/CodeGen/X86/loop-search.ll

1

Remove this line - we should only be generating with update_llc_test_checks.py

32–33

I think this comment can go now?

test/CodeGen/X86/tail-opts.ll

109

Keep these whitespace if you can - minimize diff

415

Keep these whitespace if you can - minimize diff

[spatel]

test/CodeGen/X86/loop-search.ll

1

I changed this (and several other test files) with rL305206, and I've specialized update_test_checks.py to only work with 'opt' to avoid this problem in the future (rL305208).

We could rename that script to have 'opt' in its name too, but that might be more trouble than its worth because we now have a ton of IR tests with the existing script name in a comment line as seen here.

[avt77]

The comments fixed.
New reviewers added.

[davide]

Do you know why that was 3? The choice could have been arbitrary, but better double check.

Also, the size of the binaries in bin/ decreased by 1M is a little misleading as metric [i.e. you might have an executable which size increased by 5M and another which decreased by 6M and you would have the same number :)]. Can you get a breakdown per-executable?
Last question: what you do you mean with "The compilation time was increased by 3 sec only?" What configuration are you talking about?

[paquette]

I agree with Davide on this. I think we really need to have a good reason to change thresholds like these; the impact of changing thresholds can be rather unpredictable. I'd like to understand why changing this threshold

(1) Fixes the problem
(2) Won't (likely) have a negative impact on other tests

I think per-test measurements + flags used etc. would help here.

[davide]

I don't think it's worth pursuing this path for the reason I outlined in my previous comment.

[avt77]

It seems nobody wants to change the default value of the switch.

lib/CodeGen/BranchFolding.cpp

TailMergeThreshold("tail-merge-threshold",
           cl::desc("Max number of predecessors to consider tail merging"),
           cl::init(150), cl::Hidden);
 
 // Heuristic for tail merging (and, inversely, tail duplication).
 // TODO: This should be replaced with a target query.
 static cl::opt<unsigned>
 TailMergeSize("tail-merge-size",
           cl::desc("Min number of instructions to consider tail merging"),
-                              cl::init(3), cl::Hidden);
+                              cl::init(2), cl::Hidden);
 
 namespace {
 
   /// BranchFolderPass - Wrap branch folder in a machine function pass.
   class BranchFolderPass : public MachineFunctionPass {
   public:
     static char ID;
 

test/CodeGen/AArch64/combine-comparisons-by-cse.ll

-; RUN: llc < %s -mtriple=aarch64-linux-gnu | FileCheck %s
+; RUN: llc < %s -mtriple=aarch64-linux-gnu -tail-merge-size=3 | FileCheck %s
 
 ; marked as external to prevent possible optimizations
 @a = external global i32
 @b = external global i32
 @c = external global i32
 @d = external global i32
 
 ; (a > 10 && b == c) || (a >= 10 && b == d)

test/CodeGen/AMDGPU/br_cc.f16.ll

-; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=GCN -check-prefix=SI %s
-; RUN: llc -march=amdgcn -mcpu=fiji -mattr=-flat-for-global -verify-machineinstrs < %s | FileCheck -check-prefix=GCN -check-prefix=VI %s
+; RUN: llc -march=amdgcn -verify-machineinstrs -tail-merge-size=3 < %s | FileCheck -check-prefix=GCN -check-prefix=SI %s
+; RUN: llc -march=amdgcn -mcpu=fiji -mattr=-flat-for-global -verify-machineinstrs -tail-merge-size=3 < %s | FileCheck -check-prefix=GCN -check-prefix=VI %s
 
 ; GCN-LABEL: {{^}}br_cc_f16:
 ; GCN: buffer_load_ushort v[[A_F16:[0-9]+]]
 ; GCN: buffer_load_ushort v[[B_F16:[0-9]+]]
 
 ; SI-DAG:  v_cvt_f32_f16_e32 v[[A_F32:[0-9]+]], v[[A_F16]]
 ; SI-DAG:  v_cvt_f32_f16_e32 v[[B_F32:[0-9]+]], v[[B_F16]]
 ; SI:  v_cmp_nlt_f32_e32 vcc, v[[B_F32]], v[[A_F32]]

test/CodeGen/ARM/code-placement.ll

 ; rdar://8117827
 define i32 @t2(i32 %passes, i32* nocapture %src, i32 %size) nounwind readonly {
 entry:
 ; CHECK-LABEL: t2:
   %0 = icmp eq i32 %passes, 0                     ; <i1> [#uses=1]
   br i1 %0, label %bb5, label %bb.nph15
 
 bb1:                                              ; preds = %bb2.preheader, %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_[[BB1:.]]: @ %bb1
 ; CHECK: bne LBB1_[[BB1]]
-; CHECK: b LBB1_[[BB3]]
+; CHECK: LBB1_[[BB3:.]]: @ %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]

test/CodeGen/PowerPC/memCmpUsedInZeroEqualityComparison.ll

 ; CHECK-NEXT:  # BB#1: # %loadbb1
 ; CHECK-NEXT:    ld 3, 8(3)
 ; CHECK-NEXT:    ld 4, 8(4)
 ; CHECK-NEXT:    cmpld 3, 4
 ; CHECK-NEXT:    li 3, 0
 ; CHECK-NEXT:    beq 0, .LBB1_3
 ; CHECK-NEXT:  .LBB1_2: # %res_block
 ; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    clrldi 3, 3, 32
-; CHECK-NEXT:    blr
 ; CHECK-NEXT:  .LBB1_3: # %endblock
 ; CHECK-NEXT:    clrldi 3, 3, 32
 ; CHECK-NEXT:    blr
   %call = tail call signext i32 @memcmp(i8* %x, i8* %y, i64 16)
   %not.tobool = icmp ne i32 %call, 0
   %. = zext i1 %not.tobool to i32
   ret i32 %.
 }

 ; CHECK-NEXT:  # BB#2: # %loadbb2
 ; CHECK-NEXT:    lbz 3, 6(3)
 ; CHECK-NEXT:    lbz 4, 6(4)
 ; CHECK-NEXT:    cmplw 3, 4
 ; CHECK-NEXT:    li 3, 0
 ; CHECK-NEXT:    beq 0, .LBB2_4
 ; CHECK-NEXT:  .LBB2_3: # %res_block
 ; CHECK-NEXT:    li 3, 1
-; CHECK-NEXT:    clrldi 3, 3, 32
-; CHECK-NEXT:    blr
 ; CHECK-NEXT:  .LBB2_4: # %endblock
 ; CHECK-NEXT:    clrldi 3, 3, 32
 ; CHECK-NEXT:    blr
   %call = tail call signext i32 @memcmp(i8* %x, i8* %y, i64 7)
   %not.lnot = icmp ne i32 %call, 0
   %cond = zext i1 %not.lnot to i32
   ret i32 %cond
 }

test/CodeGen/PowerPC/ppc-shrink-wrapping.ll

 ; CHECK: .[[LOOP_LABEL:LBB[0-9_]+]]: # %for.body
 ; Inline asm statement.
 ; CHECK: addi 14, 14, 1
 ; CHECK: bdnz .[[LOOP_LABEL]]
 ;
 ; Epilogue code.
 ; CHECK: li 3, 0
 ; CHECK-DAG: ld 14, -[[STACK_OFFSET]](1) # 8-byte Folded Reload
-; CHECK: nop
 ; CHECK: blr
 ;
 ; CHECK: [[ELSE_LABEL]]
 ; CHECK-NEXT: slwi 3, 4, 1
 ; DISABLE: ld 14, -[[STACK_OFFSET]](1) # 8-byte Folded Reload
 ; CHECK-NEXT: blr
 ; 
 define i32 @inlineAsm(i32 %cond, i32 %N) {

test/CodeGen/Thumb2/v8_IT_3.ll

 
 bb4:
 ; CHECK-PIC: cmp
 ; CHECK-PIC: cmp
 ; CHECK-PIC: cmp
 ; CHECK-PIC-NEXT: bne
 ; CHECK-PIC: %bb6
 ; CHECK-PIC-NEXT: movs
-; CHECK-PIC-NEXT: add
+; CHECK-PIC-NEXT: b
+; CHECK-PIC: add
 ; CHECK-PIC-NEXT: pop
   ret i32 0
 
 bb6:
   ret i32 1
 
 bb8:
   ret i32 -1

test/CodeGen/X86/2008-02-18-TailMergingBug.ll

 ; REQUIRES: asserts
-; RUN: llc < %s -march=x86 -mcpu=yonah -stats 2>&1 | grep "Number of block tails merged" | grep 16
+; RUN: llc < %s -march=x86 -mcpu=yonah -stats 2>&1 | grep "Number of block tails merged" | grep 22
 ; PR1909
 
 @.str = internal constant [48 x i8] c"transformed bounds: (%.2f, %.2f), (%.2f, %.2f)\0A\00"    ; <[48 x i8]*> [#uses=1]
 
 define void @minmax(float* %result) nounwind optsize {
 entry:
   %tmp2 = load float, float* %result, align 4    ; <float> [#uses=6]
   %tmp4 = getelementptr float, float* %result, i32 2    ; <float*> [#uses=5]

test/CodeGen/X86/loop-search.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=x86_64-apple-darwin | FileCheck %s
 
 ; This test comes from PR27136
 ; We should hoist loop constant invariant
 
 define zeroext i1 @search(i32 %needle, i32* nocapture readonly %haystack, i32 %count) {
 ; CHECK-LABEL: search:
 ; CHECK:       ## BB#0: ## %entry
 ; CHECK-NEXT:    testl %edx, %edx
 ; CHECK-NEXT:    jle LBB0_1
-; CHECK-NEXT:  ## BB#4: ## %for.body.preheader
+; CHECK-NEXT:  ## BB#3: ## %for.body.preheader
 ; CHECK-NEXT:    movslq %edx, %rax
 ; CHECK-NEXT:    xorl %ecx, %ecx
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  LBB0_5: ## %for.body
+; CHECK-NEXT:  LBB0_4: ## %for.body
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    cmpl %edi, (%rsi,%rcx,4)
-; CHECK-NEXT:    je LBB0_6
+; CHECK-NEXT:    je LBB0_5
 ; CHECK-NEXT:  ## BB#2: ## %for.cond
-; CHECK-NEXT:    ## in Loop: Header=BB0_5 Depth=1
+; CHECK-NEXT:    ## in Loop: Header=BB0_4 Depth=1
 ; CHECK-NEXT:    incq %rcx
 ; CHECK-NEXT:    cmpq %rax, %rcx
-; CHECK-NEXT:    jl LBB0_5
-;            ### FIXME: BB#3 and LBB0_1 should be merged
-; CHECK-NEXT:  ## BB#3:
-; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    ## kill: %AL<def> %AL<kill> %EAX<kill>
-; CHECK-NEXT:    retq
+; CHECK-NEXT:    jl LBB0_4
 ; CHECK-NEXT:  LBB0_1:
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    ## kill: %AL<def> %AL<kill> %EAX<kill>
 ; CHECK-NEXT:    retq
-; CHECK-NEXT:  LBB0_6:
+; CHECK-NEXT:  LBB0_5:
 ; CHECK-NEXT:    movb $1, %al
 ; CHECK-NEXT:    ## kill: %AL<def> %AL<kill> %EAX<kill>
 ; CHECK-NEXT:    retq
 entry:
   %cmp5 = icmp sgt i32 %count, 0
   br i1 %cmp5, label %for.body.preheader, label %cleanup
 
 for.body.preheader:                               ; preds = %entry
   %0 = sext i32 %count to i64
   br label %for.body
 
 for.cond:                                         ; preds = %for.body

test/CodeGen/X86/mul-constant-result.ll

 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; X86-NEXT:    testl %edx, %edx
 ; X86-NEXT:    je .LBB0_4
 ; X86-NEXT:  # BB#3:
 ; X86-NEXT:    movl %esi, %eax
 ; X86-NEXT:  .LBB0_4:
 ; X86-NEXT:    decl %ecx
 ; X86-NEXT:    cmpl $31, %ecx
-; X86-NEXT:    ja .LBB0_39
+; X86-NEXT:    ja .LBB0_41
 ; X86-NEXT:  # BB#5:
 ; X86-NEXT:    jmpl *.LJTI0_0(,%ecx,4)
 ; X86-NEXT:  .LBB0_6:
 ; X86-NEXT:    addl %eax, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_39:
+; X86-NEXT:  .LBB0_41:
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:  .LBB0_40:
+; X86-NEXT:  .LBB0_42:
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_7:
-; X86-NEXT:    leal (%eax,%eax,2), %eax
-; X86-NEXT:    popl %esi
-; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_8:
 ; X86-NEXT:    shll $2, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_9:
-; X86-NEXT:    leal (%eax,%eax,4), %eax
-; X86-NEXT:    popl %esi
-; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_10:
+; X86-NEXT:  .LBB0_8:
 ; X86-NEXT:    addl %eax, %eax
 ; X86-NEXT:    leal (%eax,%eax,2), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_11:
+; X86-NEXT:  .LBB0_9:
 ; X86-NEXT:    leal (,%eax,8), %ecx
-; X86-NEXT:    jmp .LBB0_12
-; X86-NEXT:  .LBB0_13:
+; X86-NEXT:    jmp .LBB0_10
+; X86-NEXT:  .LBB0_11:
 ; X86-NEXT:    shll $3, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_14:
-; X86-NEXT:    leal (%eax,%eax,8), %eax
-; X86-NEXT:    popl %esi
-; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_15:
+; X86-NEXT:  .LBB0_12:
 ; X86-NEXT:    addl %eax, %eax
 ; X86-NEXT:    leal (%eax,%eax,4), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_16:
+; X86-NEXT:  .LBB0_13:
 ; X86-NEXT:    leal (%eax,%eax,4), %ecx
 ; X86-NEXT:    leal (%eax,%ecx,2), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_17:
+; X86-NEXT:  .LBB0_14:
 ; X86-NEXT:    shll $2, %eax
 ; X86-NEXT:    leal (%eax,%eax,2), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_18:
+; X86-NEXT:  .LBB0_15:
 ; X86-NEXT:    leal (%eax,%eax,2), %ecx
 ; X86-NEXT:    leal (%eax,%ecx,4), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_19:
+; X86-NEXT:  .LBB0_17:
 ; X86-NEXT:    leal (%eax,%eax,2), %ecx
-; X86-NEXT:    jmp .LBB0_20
-; X86-NEXT:  .LBB0_21:
+; X86-NEXT:    jmp .LBB0_18
+; X86-NEXT:  .LBB0_20:
 ; X86-NEXT:    leal (%eax,%eax,4), %eax
 ; X86-NEXT:    leal (%eax,%eax,2), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_22:
+; X86-NEXT:  .LBB0_21:
 ; X86-NEXT:    shll $4, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_23:
+; X86-NEXT:  .LBB0_22:
 ; X86-NEXT:    movl %eax, %ecx
 ; X86-NEXT:    shll $4, %ecx
 ; X86-NEXT:    addl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_24:
+; X86-NEXT:  .LBB0_23:
 ; X86-NEXT:    addl %eax, %eax
+; X86-NEXT:  .LBB0_24:
 ; X86-NEXT:    leal (%eax,%eax,8), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_25:
 ; X86-NEXT:    leal (%eax,%eax,4), %ecx
 ; X86-NEXT:    shll $2, %ecx
-; X86-NEXT:    jmp .LBB0_12
+; X86-NEXT:    jmp .LBB0_10
 ; X86-NEXT:  .LBB0_26:
 ; X86-NEXT:    shll $2, %eax
 ; X86-NEXT:    leal (%eax,%eax,4), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_27:
 ; X86-NEXT:    leal (%eax,%eax,4), %ecx
 ; X86-NEXT:    leal (%eax,%ecx,4), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_28:
 ; X86-NEXT:    leal (%eax,%eax,4), %ecx
-; X86-NEXT:  .LBB0_20:
+; X86-NEXT:  .LBB0_18:
 ; X86-NEXT:    leal (%eax,%ecx,4), %ecx
 ; X86-NEXT:    addl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_29:
 ; X86-NEXT:    leal (%eax,%eax,2), %ecx
 ; X86-NEXT:    shll $3, %ecx
-; X86-NEXT:    jmp .LBB0_12
+; X86-NEXT:    jmp .LBB0_10
 ; X86-NEXT:  .LBB0_30:
 ; X86-NEXT:    shll $3, %eax
 ; X86-NEXT:    leal (%eax,%eax,2), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ; X86-NEXT:  .LBB0_31:
 ; X86-NEXT:    leal (%eax,%eax,4), %eax
+; X86-NEXT:  .LBB0_32:
 ; X86-NEXT:    leal (%eax,%eax,4), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_32:
+; X86-NEXT:  .LBB0_33:
 ; X86-NEXT:    leal (%eax,%eax,8), %ecx
 ; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
-; X86-NEXT:    jmp .LBB0_12
-; X86-NEXT:  .LBB0_33:
+; X86-NEXT:    jmp .LBB0_10
+; X86-NEXT:  .LBB0_34:
 ; X86-NEXT:    leal (%eax,%eax,8), %eax
+; X86-NEXT:  .LBB0_35:
 ; X86-NEXT:    leal (%eax,%eax,2), %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_34:
+; X86-NEXT:  .LBB0_36:
 ; X86-NEXT:    leal (%eax,%eax,8), %ecx
 ; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
 ; X86-NEXT:    addl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_35:
+; X86-NEXT:  .LBB0_37:
 ; X86-NEXT:    leal (%eax,%eax,8), %ecx
 ; X86-NEXT:    leal (%ecx,%ecx,2), %ecx
 ; X86-NEXT:    addl %eax, %ecx
 ; X86-NEXT:    addl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_36:
+; X86-NEXT:  .LBB0_38:
 ; X86-NEXT:    movl %eax, %ecx
 ; X86-NEXT:    shll $5, %ecx
 ; X86-NEXT:    subl %eax, %ecx
-; X86-NEXT:    jmp .LBB0_12
-; X86-NEXT:  .LBB0_37:
+; X86-NEXT:    jmp .LBB0_10
+; X86-NEXT:  .LBB0_39:
 ; X86-NEXT:    movl %eax, %ecx
 ; X86-NEXT:    shll $5, %ecx
-; X86-NEXT:  .LBB0_12:
+; X86-NEXT:  .LBB0_10:
 ; X86-NEXT:    subl %eax, %ecx
 ; X86-NEXT:    movl %ecx, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
-; X86-NEXT:  .LBB0_38:
+; X86-NEXT:  .LBB0_40:
 ; X86-NEXT:    shll $5, %eax
 ; X86-NEXT:    popl %esi
 ; X86-NEXT:    retl
 ;
 ; X64-HSW-LABEL: mult:
 ; X64-HSW:       # BB#0:
 ; X64-HSW-NEXT:    # kill: %EDI<def> %EDI<kill> %RDI<def>
 ; X64-HSW-NEXT:    cmpl $1, %esi
 ; X64-HSW-NEXT:    movl $1, %ecx
 ; X64-HSW-NEXT:    movl %esi, %eax
 ; X64-HSW-NEXT:    cmovgl %ecx, %eax
 ; X64-HSW-NEXT:    testl %esi, %esi
 ; X64-HSW-NEXT:    cmovel %ecx, %eax
 ; X64-HSW-NEXT:    addl $-1, %edi
 ; X64-HSW-NEXT:    cmpl $31, %edi
-; X64-HSW-NEXT:    ja .LBB0_36
+; X64-HSW-NEXT:    ja .LBB0_38
 ; X64-HSW-NEXT:  # BB#1:
 ; X64-HSW-NEXT:    jmpq *.LJTI0_0(,%rdi,8)
 ; X64-HSW-NEXT:  .LBB0_2:
 ; X64-HSW-NEXT:    addl %eax, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_36:
+; X64-HSW-NEXT:  .LBB0_38:
 ; X64-HSW-NEXT:    xorl %eax, %eax
-; X64-HSW-NEXT:  .LBB0_37:
+; X64-HSW-NEXT:  .LBB0_39:
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
 ; X64-HSW-NEXT:  .LBB0_3:
-; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax
-; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
-; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_4:
 ; X64-HSW-NEXT:    shll $2, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_5:
-; X64-HSW-NEXT:    leal (%rax,%rax,4), %eax
-; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
-; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_6:
+; X64-HSW-NEXT:  .LBB0_4:
 ; X64-HSW-NEXT:    addl %eax, %eax
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_7:
+; X64-HSW-NEXT:  .LBB0_5:
 ; X64-HSW-NEXT:    leal (,%rax,8), %ecx
-; X64-HSW-NEXT:    jmp .LBB0_8
-; X64-HSW-NEXT:  .LBB0_9:
+; X64-HSW-NEXT:    jmp .LBB0_6
+; X64-HSW-NEXT:  .LBB0_8:
 ; X64-HSW-NEXT:    shll $3, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_10:
-; X64-HSW-NEXT:    leal (%rax,%rax,8), %eax
-; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
-; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_11:
+; X64-HSW-NEXT:  .LBB0_9:
 ; X64-HSW-NEXT:    addl %eax, %eax
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_12:
+; X64-HSW-NEXT:  .LBB0_10:
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %ecx
 ; X64-HSW-NEXT:    leal (%rax,%rcx,2), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_13:
+; X64-HSW-NEXT:  .LBB0_11:
 ; X64-HSW-NEXT:    shll $2, %eax
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_14:
+; X64-HSW-NEXT:  .LBB0_12:
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %ecx
 ; X64-HSW-NEXT:    leal (%rax,%rcx,4), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_15:
+; X64-HSW-NEXT:  .LBB0_14:
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %ecx
-; X64-HSW-NEXT:    jmp .LBB0_16
-; X64-HSW-NEXT:  .LBB0_18:
+; X64-HSW-NEXT:    jmp .LBB0_15
+; X64-HSW-NEXT:  .LBB0_17:
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %eax
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_19:
+; X64-HSW-NEXT:  .LBB0_18:
 ; X64-HSW-NEXT:    shll $4, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_20:
+; X64-HSW-NEXT:  .LBB0_19:
 ; X64-HSW-NEXT:    movl %eax, %ecx
 ; X64-HSW-NEXT:    shll $4, %ecx
-; X64-HSW-NEXT:    jmp .LBB0_17
-; X64-HSW-NEXT:  .LBB0_21:
+; X64-HSW-NEXT:    jmp .LBB0_16
+; X64-HSW-NEXT:  .LBB0_20:
 ; X64-HSW-NEXT:    addl %eax, %eax
+; X64-HSW-NEXT:  .LBB0_21:
 ; X64-HSW-NEXT:    leal (%rax,%rax,8), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
 ; X64-HSW-NEXT:  .LBB0_22:
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %ecx
 ; X64-HSW-NEXT:    shll $2, %ecx
-; X64-HSW-NEXT:    jmp .LBB0_8
+; X64-HSW-NEXT:    jmp .LBB0_6
 ; X64-HSW-NEXT:  .LBB0_23:
 ; X64-HSW-NEXT:    shll $2, %eax
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
 ; X64-HSW-NEXT:  .LBB0_24:
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %ecx
 ; X64-HSW-NEXT:    leal (%rax,%rcx,4), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
 ; X64-HSW-NEXT:  .LBB0_25:
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %ecx
-; X64-HSW-NEXT:  .LBB0_16:
+; X64-HSW-NEXT:  .LBB0_15:
 ; X64-HSW-NEXT:    leal (%rax,%rcx,4), %ecx
-; X64-HSW-NEXT:    jmp .LBB0_17
+; X64-HSW-NEXT:    jmp .LBB0_16
 ; X64-HSW-NEXT:  .LBB0_26:
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %ecx
 ; X64-HSW-NEXT:    shll $3, %ecx
-; X64-HSW-NEXT:    jmp .LBB0_8
+; X64-HSW-NEXT:    jmp .LBB0_6
 ; X64-HSW-NEXT:  .LBB0_27:
 ; X64-HSW-NEXT:    shll $3, %eax
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
 ; X64-HSW-NEXT:  .LBB0_28:
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %eax
+; X64-HSW-NEXT:  .LBB0_29:
 ; X64-HSW-NEXT:    leal (%rax,%rax,4), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_29:
+; X64-HSW-NEXT:  .LBB0_30:
 ; X64-HSW-NEXT:    leal (%rax,%rax,8), %ecx
 ; X64-HSW-NEXT:    leal (%rcx,%rcx,2), %ecx
-; X64-HSW-NEXT:    jmp .LBB0_8
-; X64-HSW-NEXT:  .LBB0_30:
+; X64-HSW-NEXT:    jmp .LBB0_6
+; X64-HSW-NEXT:  .LBB0_31:
 ; X64-HSW-NEXT:    leal (%rax,%rax,8), %eax
+; X64-HSW-NEXT:  .LBB0_32:
 ; X64-HSW-NEXT:    leal (%rax,%rax,2), %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_31:
+; X64-HSW-NEXT:  .LBB0_33:
 ; X64-HSW-NEXT:    leal (%rax,%rax,8), %ecx
 ; X64-HSW-NEXT:    leal (%rcx,%rcx,2), %ecx
-; X64-HSW-NEXT:    jmp .LBB0_17
-; X64-HSW-NEXT:  .LBB0_32:
+; X64-HSW-NEXT:    jmp .LBB0_16
+; X64-HSW-NEXT:  .LBB0_34:
 ; X64-HSW-NEXT:    leal (%rax,%rax,8), %ecx
 ; X64-HSW-NEXT:    leal (%rcx,%rcx,2), %ecx
 ; X64-HSW-NEXT:    addl %eax, %ecx
-; X64-HSW-NEXT:  .LBB0_17:
+; X64-HSW-NEXT:  .LBB0_16:
 ; X64-HSW-NEXT:    addl %eax, %ecx
 ; X64-HSW-NEXT:    movl %ecx, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_33:
+; X64-HSW-NEXT:  .LBB0_35:
 ; X64-HSW-NEXT:    movl %eax, %ecx
 ; X64-HSW-NEXT:    shll $5, %ecx
 ; X64-HSW-NEXT:    subl %eax, %ecx
-; X64-HSW-NEXT:    jmp .LBB0_8
-; X64-HSW-NEXT:  .LBB0_34:
+; X64-HSW-NEXT:    jmp .LBB0_6
+; X64-HSW-NEXT:  .LBB0_36:
 ; X64-HSW-NEXT:    movl %eax, %ecx
 ; X64-HSW-NEXT:    shll $5, %ecx
-; X64-HSW-NEXT:  .LBB0_8:
+; X64-HSW-NEXT:  .LBB0_6:
 ; X64-HSW-NEXT:    subl %eax, %ecx
 ; X64-HSW-NEXT:    movl %ecx, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
-; X64-HSW-NEXT:  .LBB0_35:
+; X64-HSW-NEXT:  .LBB0_37:
 ; X64-HSW-NEXT:    shll $5, %eax
 ; X64-HSW-NEXT:    # kill: %EAX<def> %EAX<kill> %RAX<kill>
 ; X64-HSW-NEXT:    retq
   %3 = icmp eq i32 %1, 0
   %4 = icmp sgt i32 %1, 1
   %5 = or i1 %3, %4
   %6 = select i1 %5, i32 1, i32 %1
   switch i32 %0, label %69 [

test/CodeGen/X86/tail-dup-merge-loop-headers.ll

 ; merge_predecessor_split falls through to their shared successor:
 ; outer_loop_latch.
 ; The rest of the blocks in the function are noise unfortunately. Bugpoint
 ; couldn't shrink the test any further.
 
 ; CHECK-LABEL: loop_shared_header
 ; CHECK: # %entry
 ; CHECK: # %shared_preheader
-; CHECK: # %shared_loop_header
-; CHECK: # %inner_loop_body
+; CHECK: # %merge_other
 ; CHECK: # %outer_loop_latch
 ; CHECK: # %merge_predecessor_split
-; CHECK: # %outer_loop_latch
+; CHECK: # %shared_loop_header
+; CHECK: # %inner_loop_body
 ; CHECK: # %cleanup
 define i32 @loop_shared_header(i8* %exe, i32 %exesz, i32 %headsize, i32 %min, i32 %wwprva, i32 %e_lfanew, i8* readonly %wwp, i32 %wwpsz, i16 zeroext %sects) local_unnamed_addr #0 {
 entry:
   %0 = load i32, i32* undef, align 4
   %mul = shl nsw i32 %0, 2
   br i1 undef, label %if.end19, label %cleanup
 
 if.end19:                                         ; preds = %entry

test/CodeGen/X86/tail-opts.ll

return:
   ret void
 altret:
   call void @far(i32 1001)
   ret void
 }
 
 ; BranchFolding shouldn't try to merge the tails of two blocks
 ; with only a branch in common, regardless of the fallthrough situation.
 
 ; CHECK-LABEL: dont_merge_oddly:
 ; CHECK-NOT:   ret
 ; CHECK:        ucomiss %xmm{{[0-2]}}, %xmm{{[0-2]}}
-; CHECK-NEXT:   jbe .LBB2_3
+; CHECK-NEXT:   jbe .LBB2_4
 ; CHECK-NEXT:   ucomiss %xmm{{[0-2]}}, %xmm{{[0-2]}}
-; CHECK-NEXT:   ja .LBB2_4
-; CHECK-NEXT: .LBB2_2:
+; CHECK-NEXT:   ja .LBB2_5
+; CHECK-NEXT: .LBB2_3:
 ; CHECK-NEXT:   movb $1, %al
 ; CHECK-NEXT:   ret
-; CHECK-NEXT: .LBB2_3:
-; CHECK-NEXT:   ucomiss %xmm{{[0-2]}}, %xmm{{[0-2]}}
-; CHECK-NEXT:   jbe .LBB2_2
 ; CHECK-NEXT: .LBB2_4:
+; CHECK-NEXT:   ucomiss %xmm{{[0-2]}}, %xmm{{[0-2]}}
+; CHECK-NEXT:   jbe .LBB2_3
+; CHECK-NEXT: .LBB2_5:
 ; CHECK-NEXT:   xorl %eax, %eax
 ; CHECK-NEXT:   ret
 
 define i1 @dont_merge_oddly(float* %result) nounwind {
 entry:
   %tmp4 = getelementptr float, float* %result, i32 2
   %tmp5 = load float, float* %tmp4, align 4
   %tmp7 = getelementptr float, float* %result, i32 4
bb12:
   unreachable
 
 return:
   ret void
 }
 
 ; two_nosize - Same as two, but without the optsize attribute.
 ; Now two instructions are enough to be tail-duplicated.
 
 ; CHECK-LABEL: two_nosize:
 ; CHECK: movl $0, XYZ(%rip)
 ; CHECK: jmp tail_call_me
-; CHECK: movl $0, XYZ(%rip)
-; CHECK: jmp tail_call_me
 
 define void @two_nosize() nounwind {
 entry:
   %0 = icmp eq i32 undef, 0
   br i1 %0, label %bbx, label %bby
 
 bby:
   switch i32 undef, label %bb7 [

test/CodeGen/X86/trunc-to-bool.ll

 ; CHECK-NEXT:    fnstcw (%esp)
 ; CHECK-NEXT:    movzwl (%esp), %eax
 ; CHECK-NEXT:    movw $3199, (%esp) # imm = 0xC7F
 ; CHECK-NEXT:    fldcw (%esp)
 ; CHECK-NEXT:    movw %ax, (%esp)
 ; CHECK-NEXT:    fistps {{[0-9]+}}(%esp)
 ; CHECK-NEXT:    fldcw (%esp)
 ; CHECK-NEXT:    testb $1, {{[0-9]+}}(%esp)
-; CHECK-NEXT:    je .LBB4_2
+; CHECK-NEXT:    je .LBB4_3
 ; CHECK-NEXT:  # BB#1: # %cond_true
 ; CHECK-NEXT:    movl $21, %eax
 ; CHECK-NEXT:    popl %ecx
 ; CHECK-NEXT:    retl
-; CHECK-NEXT:  .LBB4_2: # %cond_false
+; CHECK-NEXT:  .LBB4_3: # %cond_false
 ; CHECK-NEXT:    movl $42, %eax
 ; CHECK-NEXT:    popl %ecx
 ; CHECK-NEXT:    retl
     %tmp = fptosi double %d to i1
     br i1 %tmp, label %cond_true, label %cond_false
 cond_true:
     ret i32 21
 cond_false:
     ret i32 42
 }

test/CodeGen/X86/wide-integer-cmp.ll

 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %ecx
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %edx
 ; CHECK-NEXT:    movl {{[0-9]+}}(%esp), %esi
 ; CHECK-NEXT:    cmpl {{[0-9]+}}(%esp), %edx
 ; CHECK-NEXT:    sbbl {{[0-9]+}}(%esp), %esi
 ; CHECK-NEXT:    sbbl {{[0-9]+}}(%esp), %eax
 ; CHECK-NEXT:    sbbl {{[0-9]+}}(%esp), %ecx
-; CHECK-NEXT:    jge .LBB4_2
+; CHECK-NEXT:    jge .LBB4_3
 ; CHECK-NEXT:  # BB#1: # %bb1
 ; CHECK-NEXT:    movl $1, %eax
 ; CHECK-NEXT:    popl %esi
 ; CHECK-NEXT:    retl
-; CHECK-NEXT:  .LBB4_2: # %bb2
+; CHECK-NEXT:  .LBB4_3: # %bb2
 ; CHECK-NEXT:    movl $2, %eax
 ; CHECK-NEXT:    popl %esi
 ; CHECK-NEXT:    retl
 entry:
   %cmp = icmp slt i128 %a, %b
   br i1 %cmp, label %bb1, label %bb2
 bb1:
   ret i32 1