[MBP] Don't move bottom block before header if it can't reduce taken branches

[Carrot]

Summary

If bottom of block BB has only one successor OldTop, in most cases it is profitable to move it before OldTop, except the following case:

-->OldTop<-
|    .    |
|    .    |
|    .    |
---Pred   |
     |    |
    BB-----

Move BB before OldTop can't reduce the number of taken branches, this patch detects this case and prevent the moving.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1775

Is there any benefit of keeping the original layout?

[Carrot]

lib/CodeGen/MachineBlockPlacement.cpp

1775

1 If there is no benefit, the original layout is much better for readability.

2 In theory on modern processor the consecutive two branches should be slower than two branches with other instructions between them.

case 1

...
jne 
jmp

case 2

jne
alu_1
...
alu_n
jmp

When prediction for jne is correct, there is no difference.
When prediction for jne is false and branch is not taken, following instructions is fetched and executed, in case 1 only one instruction is fetched and executed, in case 2 multiple instruction is fetched and executed at the same time. Usually branch instructions cause bubble in pipeline. In case 1 when jmp is executed, the pipeline is completely empty. In case 2 when jmp is executed, the pipeline can still execute previous instructions.

[Carrot]

lib/CodeGen/MachineBlockPlacement.cpp

1775

I also noticed findBestLoopExit is only called when it can't find a better new Header. So if we move bottom BB as new Header, it will prevent finding a better loop exit edge.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

1775

Right. Suppose oldTop has another predecessor from outside the loop, when bottom BB is rotated before the oldTop, there will be a missing fall through from that predecessor to oldTop.

[davidxl]

lgtm.

Do you have any benchmarking numbers?

[Carrot]

In D57067#1369587, @davidxl wrote:

lgtm.

Do you have any benchmarking numbers?

No. I just observed it many multi times in unit tests, found it not optimal, and think it should be improved.

lib/CodeGen/MachineBlockPlacement.cpp

#endif
   /// present in the set will be added to the worklist. If nullptr
   /// is provided, no filtering occurs.
   void fillWorkLists(const MachineBasicBlock *MBB,
                      SmallPtrSetImpl<BlockChain *> &UpdatedPreds,
                      const BlockFilterSet *BlockFilter);
 
   void buildChain(const MachineBasicBlock *BB, BlockChain &Chain,
                   BlockFilterSet *BlockFilter = nullptr);
+  bool canMoveBottomBlockToTop(const MachineBasicBlock *BottomBlock,
+                               const MachineBasicBlock *OldTop);
   MachineBasicBlock *findBestLoopTop(
       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
   MachineBasicBlock *findBestLoopExit(
       const MachineLoop &L, const BlockFilterSet &LoopBlockSet);
   BlockFilterSet collectLoopBlockSet(const MachineLoop &L);
   void buildLoopChains(const MachineLoop &L);
   void rotateLoop(
       BlockChain &LoopChain, const MachineBasicBlock *ExitingBB,
while (true) {
     Chain.merge(BestSucc, &SuccChain);
     BB = *std::prev(Chain.end());
   }
 
   LLVM_DEBUG(dbgs() << "Finished forming chain for header block "
                     << getBlockName(*Chain.begin()) << "\n");
 }
 
+// If bottom of block BB has only one successor OldTop, in most cases it is
+// profitable to move it before OldTop, except the following case:
+//
+//     -->OldTop<-
+//     |    .    |
+//     |    .    |
+//     |    .    |
+//     ---Pred   |
+//          |    |
+//         BB-----
+//
+// If BB is moved before OldTop, Pred needs a taken branch to BB, and it can't
+// layout the other successor below it, so it can't reduce taken branch.
+// In this case we keep its original layout.
+bool
+MachineBlockPlacement::canMoveBottomBlockToTop(
+    const MachineBasicBlock *BottomBlock,
+    const MachineBasicBlock *OldTop) {
+  if (BottomBlock->pred_size() != 1)
+    return true;
+  MachineBasicBlock *Pred = *BottomBlock->pred_begin();
+  if (Pred->succ_size() != 2)
+    return true;
+
+  MachineBasicBlock *OtherBB = *Pred->succ_begin();
+  if (OtherBB == BottomBlock)
+    OtherBB = *Pred->succ_rbegin();
+  if (OtherBB == OldTop)
+    return false;
+
+  return true;
+}
+
 /// Find the best loop top block for layout.
 ///
 /// Look for a block which is strictly better than the loop header for laying
 /// out at the top of the loop. This looks for one and only one pattern:
 /// a latch block with no conditional exit. This block will cause a conditional
 /// jump around it or will be the bottom of the loop if we lay it out in place,
 /// but if it it doesn't end up at the bottom of the loop for any reason,
 /// rotation alone won't fix it. Because such a block will always result in an
for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) {
     if (!LoopBlockSet.count(Pred))
       continue;
     LLVM_DEBUG(dbgs() << "    header pred: " << getBlockName(Pred) << ", has "
                       << Pred->succ_size() << " successors, ";
                MBFI->printBlockFreq(dbgs(), Pred) << " freq\n");
     if (Pred->succ_size() > 1)
       continue;
 
+    if (!canMoveBottomBlockToTop(Pred, L.getHeader()))
+      continue;
+
     BlockFrequency PredFreq = MBFI->getBlockFreq(Pred);
     if (!BestPred || PredFreq > BestPredFreq ||
         (!(PredFreq < BestPredFreq) &&
          Pred->isLayoutSuccessor(L.getHeader()))) {
       BestPred = Pred;
       BestPredFreq = PredFreq;
     }
   }

test/CodeGen/AMDGPU/si-annotate-cf.ll

 }
 
 declare float @llvm.fabs.f32(float) nounwind readnone
 
 ; This broke the old AMDIL cfg structurizer
 ; FUNC-LABEL: {{^}}loop_land_info_assert:
 ; SI:      v_cmp_lt_i32_e64 [[CMP4:s\[[0-9:]+\]]], s{{[0-9]+}}, 4{{$}}
 ; SI:      s_and_b64        [[CMP4M:s\[[0-9]+:[0-9]+\]]], exec, [[CMP4]]
-; SI:      s_mov_b64        vcc, [[CMP4M]]
-; SI-NEXT: s_cbranch_vccnz  [[CONVEX_EXIT:BB[0-9_]+]]
-; SI-NEXT: s_branch         [[FOR_COND_PREHDR:BB[0-9_]+]]
+; SI:      s_branch         [[INFLOOP:BB[0-9]+_[0-9]+]]
+
+; SI:      [[CONVEX_EXIT:BB[0-9_]+]]
+; SI:      s_mov_b64        vcc,
+; SI-NEXT: s_cbranch_vccnz  [[ENDPGM:BB[0-9]+_[0-9]+]]
+; SI:      s_cbranch_vccnz  [[INFLOOP]]
 
 ; SI: ; %if.else
 ; SI:      buffer_store_dword
 
-; SI:      [[INFLOOP:BB[0-9]+_[0-9]+]]:
+; SI:      [[INFLOOP]]:
+; SI:      s_cbranch_vccnz [[CONVEX_EXIT]]
 
-; SI:      [[CONVEX_EXIT]]:
-; SI:      s_mov_b64        vcc,
-; SI-NEXT: s_cbranch_vccnz  [[ENDPGM:BB[0-9]+_[0-9]+]]
-; SI:      s_branch [[INFLOOP]]
-; SI-NEXT: [[FOR_COND_PREHDR]]:
+; SI: ; %for.cond.preheader
 ; SI:      s_cbranch_vccz [[ENDPGM]]
 
 ; SI:      [[ENDPGM]]:
 ; SI-NEXT: s_endpgm
 define amdgpu_kernel void @loop_land_info_assert(i32 %c0, i32 %c1, i32 %c2, i32 %c3, i32 %x, i32 %y, i1 %arg) nounwind {
 entry:
   %cmp = icmp sgt i32 %c0, 0
   br label %while.cond.outer

test/CodeGen/PowerPC/licm-remat.ll

 
 define linkonce_odr void @ZN6snappyDecompressor_(%"class.snappy::SnappyDecompressor"* %this, %"class.snappy::SnappyIOVecWriter"* %writer) {
 ; CHECK-LABEL: ZN6snappyDecompressor_:
 ; CHECK:       # %bb.0: # %entry
 ; CHECK:       addis 3, 2, _ZN6snappy8internalL8wordmaskE@toc@ha
 ; CHECK-DAG:   addi 25, 3, _ZN6snappy8internalL8wordmaskE@toc@l
 ; CHECK-DAG:   addis 5, 2, _ZN6snappy8internalL10char_tableE@toc@ha
 ; CHECK-DAG:   addi 24, 5, _ZN6snappy8internalL10char_tableE@toc@l
-; CHECK:       b .LBB0_2
-; CHECK:       .LBB0_2: # %for.cond
+; CHECK:       b .[[LABEL1:[A-Z0-9_]+]]
+; CHECK:       .[[LABEL1]]: # %for.cond
 ; CHECK-NOT:   addis {{[0-9]+}}, 2, _ZN6snappy8internalL8wordmaskE@toc@ha
 ; CHECK-NOT:   addis {{[0-9]+}}, 2, _ZN6snappy8internalL10char_tableE@toc@ha
 ; CHECK:       bctrl
 entry:
   %ip_limit_ = getelementptr inbounds %"class.snappy::SnappyDecompressor", %"class.snappy::SnappyDecompressor"* %this, i64 0, i32 2
   %0 = bitcast i8** %ip_limit_ to i64*
   %curr_iov_index_.i = getelementptr inbounds %"class.snappy::SnappyIOVecWriter", %"class.snappy::SnappyIOVecWriter"* %writer, i64 0, i32 2
   %curr_iov_written_.i = getelementptr inbounds %"class.snappy::SnappyIOVecWriter", %"class.snappy::SnappyIOVecWriter"* %writer, i64 0, i32 3

test/CodeGen/X86/2009-02-26-MachineLICMBug.ll

 ; CHECK:       ## %bb.0: ## %entry
 ; CHECK-NEXT:    pushq %r14
 ; CHECK-NEXT:    pushq %rbx
 ; CHECK-NEXT:    pushq %rax
 ; CHECK-NEXT:    movq %rsi, %r14
 ; CHECK-NEXT:    movq %rdi, %rbx
 ; CHECK-NEXT:    orq $2097152, %r14 ## imm = 0x200000
 ; CHECK-NEXT:    andl $15728640, %r14d ## imm = 0xF00000
-; CHECK-NEXT:    jmp LBB0_1
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  LBB0_3: ## %bb.i
-; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
-; CHECK-NEXT:    movl 0, %eax
-; CHECK-NEXT:    xorps %xmm0, %xmm0
-; CHECK-NEXT:    cvtsi2ssq %rax, %xmm0
-; CHECK-NEXT:    movl 4, %eax
-; CHECK-NEXT:    xorps %xmm1, %xmm1
-; CHECK-NEXT:    cvtsi2ssq %rax, %xmm1
-; CHECK-NEXT:    movl 8, %eax
-; CHECK-NEXT:    xorps %xmm2, %xmm2
-; CHECK-NEXT:    cvtsi2ssq %rax, %xmm2
-; CHECK-NEXT:    insertps {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[2,3]
-; CHECK-NEXT:    insertps {{.*#+}} xmm0 = xmm0[0,1],xmm2[0],xmm0[3]
-; CHECK-NEXT:    movaps %xmm0, 0
 ; CHECK-NEXT:  LBB0_1: ## %bb4
 ; CHECK-NEXT:    ## =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    callq _xxGetOffsetForCode
 ; CHECK-NEXT:    movq %rbx, %rdi
 ; CHECK-NEXT:    xorl %esi, %esi
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    callq _xxCalculateMidType
 ; CHECK-NEXT:    cmpl $1, %eax
 ; CHECK-NEXT:    jne LBB0_1
 ; CHECK-NEXT:  ## %bb.2: ## %bb26
 ; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
 ; CHECK-NEXT:    cmpq $1048576, %r14 ## imm = 0x100000
 ; CHECK-NEXT:    jne LBB0_1
-; CHECK-NEXT:    jmp LBB0_3
+; CHECK-NEXT:  ## %bb.3: ## %bb.i
+; CHECK-NEXT:    ## in Loop: Header=BB0_1 Depth=1
+; CHECK-NEXT:    movl 0, %eax
+; CHECK-NEXT:    xorps %xmm0, %xmm0
+; CHECK-NEXT:    cvtsi2ssq %rax, %xmm0
+; CHECK-NEXT:    movl 4, %eax
+; CHECK-NEXT:    xorps %xmm1, %xmm1
+; CHECK-NEXT:    cvtsi2ssq %rax, %xmm1
+; CHECK-NEXT:    movl 8, %eax
+; CHECK-NEXT:    xorps %xmm2, %xmm2
+; CHECK-NEXT:    cvtsi2ssq %rax, %xmm2
+; CHECK-NEXT:    insertps {{.*#+}} xmm0 = xmm0[0],xmm1[0],xmm0[2,3]
+; CHECK-NEXT:    insertps {{.*#+}} xmm0 = xmm0[0,1],xmm2[0],xmm0[3]
+; CHECK-NEXT:    movaps %xmm0, 0
+; CHECK-NEXT:    jmp LBB0_1
 entry:
   br label %bb4
 
 bb4:    ; preds = %bb.i, %bb26, %bb4, %entry
 
   %0 = call i32 (...) @xxGetOffsetForCode(i32 undef) nounwind    ; <i32> [#uses=0]
   %ins = or i64 %p, 2097152   ; <i64> [#uses=1]
   %1 = call i32 (...) @xxCalculateMidType(%struct.Key* %desc, i32 0) nounwind    ; <i32> [#uses=1]

test/CodeGen/X86/avx-cmp.ll

 ; CHECK-NEXT:    pushq %rbx
 ; CHECK-NEXT:    pushq %rax
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB2_6
 ; CHECK-NEXT:  # %bb.1: # %for.cond5.preheader
 ; CHECK-NEXT:    xorl %ebx, %ebx
 ; CHECK-NEXT:    movb $1, %bpl
-; CHECK-NEXT:    jmp .LBB2_2
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB2_5: # %if.then
-; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
-; CHECK-NEXT:    callq scale
 ; CHECK-NEXT:  .LBB2_2: # %for.cond5
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    testb %bl, %bl
 ; CHECK-NEXT:    jne .LBB2_2
 ; CHECK-NEXT:  # %bb.3: # %for.cond5
 ; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
 ; CHECK-NEXT:    testb %bpl, %bpl
 ; CHECK-NEXT:    jne .LBB2_2
 ; CHECK-NEXT:  # %bb.4: # %for.body33
 ; CHECK-NEXT:    # in Loop: Header=BB2_2 Depth=1
 ; CHECK-NEXT:    vucomisd {{\.LCPI.*}}, %xmm0
 ; CHECK-NEXT:    jne .LBB2_5
-; CHECK-NEXT:    jp .LBB2_5
+; CHECK-NEXT:    jnp .LBB2_2
+; CHECK-NEXT:  .LBB2_5: # %if.then
+; CHECK-NEXT:   # in Loop: Header=BB2_2 Depth=1
+; CHECK-NEXT:    callq   scale
 ; CHECK-NEXT:    jmp .LBB2_2
 ; CHECK-NEXT:  .LBB2_6: # %for.end52
 ; CHECK-NEXT:    addq $8, %rsp
 ; CHECK-NEXT:    popq %rbx
 ; CHECK-NEXT:    popq %rbp
 ; CHECK-NEXT:    retq
 entry:
   br i1 undef, label %for.cond5, label %for.end52

test/CodeGen/X86/avx512-i1test.ll

 ; CHECK:       # %bb.0: # %bb1
 ; CHECK-NEXT:    xorl %eax, %eax
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    je .LBB0_1
 ; CHECK-NEXT:  # %bb.4: # %L_30
 ; CHECK-NEXT:    retq
 ; CHECK-NEXT:  .LBB0_1: # %bb56
 ; CHECK-NEXT:    xorl %eax, %eax
-; CHECK-NEXT:    jmp .LBB0_2
 ; CHECK-NEXT:    .p2align 4, 0x90
-; CHECK-NEXT:  .LBB0_3: # %bb35
-; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
-; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:  .LBB0_2: # %bb33
 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    testb %al, %al
 ; CHECK-NEXT:    jne .LBB0_2
-; CHECK-NEXT:    jmp .LBB0_3
+; CHECK-NEXT:  # %bb.3: # %bb35
+; CHECK-NEXT:    # in Loop: Header=BB0_2 Depth=1
+; CHECK-NEXT:    testb %al, %al
+; CHECK-NEXT:    jmp .LBB0_2
 bb1:
   br i1 undef, label %L_10, label %L_10
 
 L_10:                                             ; preds = %bb1, %bb1
   br i1 undef, label %L_30, label %bb56
 
 bb56:                                             ; preds = %L_10
   br label %bb33

test/CodeGen/X86/code_placement_no_header_change.ll

+; RUN: llc -mtriple=i686-linux < %s | FileCheck %s
+
+
+define i32 @bar(i32 %count) {
+; Test checks that basic block backedge2 is not moved before header,
+; because it can't reduce taken branches.
+; Later backedge1 and backedge2 is rotated before loop header.
+; CHECK-LABEL: bar
+; CHECK: %.entry
+; CHECK: %.backedge1
+; CHECK: %.backedge2
+; CHECK: %.header
+; CHECK: %.exit
+.entry:
+  %c = shl nsw i32 %count, 2
+  br label %.header
+
+.header:
+  %val1 = call i32 @foo()
+  %cond1 = icmp sgt i32 %val1, 1
+  br i1 %cond1, label %.exit, label %.backedge1
+
+.backedge1:
+  %val2 = call i32 @foo()
+  %cond2 = icmp sgt i32 %val2, 1
+  br i1 %cond2, label %.header, label %.backedge2
+
+.backedge2:
+  %val3 = call i32 @foo()
+  br label %.header
+
+.exit:
+  ret i32 %c
+}
+
+declare i32 @foo()

test/DebugInfo/X86/PR37234.ll

 ;            return aa;
 ;    }
 
 
 ; CHECK-LABEL: # %bb.{{.*}}:
 ; CHECK:        #DEBUG_VALUE: main:aa <- 0
 ; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG:[0-9a-z]+]]
 ; CHECK:  jmp .LBB0_1
-; CHECK: .LBB0_3:
-; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
-; CHECK:  incl  %[[REG]]
-; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK: .LBB0_2:
+; CHECK:        #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK:        jne     .LBB0_1
+; CHECK: # %bb.{{.*}}:
+; CHECK:        #DEBUG_VALUE: main:aa <- $[[REG]]
+; CHECK:        incl    %[[REG]]
+; CHECK:        #DEBUG_VALUE: main:aa <- $[[REG]]
 ; CHECK: .LBB0_1:
 ; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
-; CHECK:  je  .LBB0_4
+; CHECK:        jne     .LBB0_2
 ; CHECK: # %bb.{{.*}}:
 ; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
-; CHECK:  jne .LBB0_1
-; CHECK:  jmp .LBB0_3
-; CHECK: .LBB0_4:
-; CHECK:  #DEBUG_VALUE: main:aa <- $[[REG]]
 ; CHECK:  retq
 
 source_filename = "PR37234.cpp"
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @.str = private unnamed_addr constant [4 x i8] c"aaa\00", align 1