[MBP] do not rotate loop if it creates extra branch

[skatkov]

Summary

This is a last fix for the corner case of PR32214. Actually this is not really corner case in general.

We should not do a loop rotation if we create an additional branch due to it.
Consider the case where we have a loop chain H, M, B, C , where
H is header with viable fallthrough from pre-header and exit from the loop
M - some middle block
B - backedge to Header but with exit from the loop also.
C - some cold block of the loop.

Let's H is determined as a best exit. If we do a loop rotation M, B, C, H we can introduce the extra branch.
Let's compute the change in number of branches:
+1 branch from pre-header to header
-1 branch from header to exit
+1 branch from header to middle block if there is such
-1 branch from cold bock to header if there is one

So if C is not a predecessor of H then we introduce extra branch.

This change actually prohibits rotation of the loop if both true

1. Best Exit has next element in chain as successor.
2. Last element in chain is not a predecessor of first element of chain.

[iteratee]

lib/CodeGen/MachineBlockPlacement.cpp

1941

How is your test different from the test above?

[skatkov]

lib/CodeGen/MachineBlockPlacement.cpp

1941

The test above checks whether Bottom block has a fallthrough out of the loop. If it has than there is no reason to make a loop rotation due to it will introduce a branch to that out of loop basic block.

My check is described in the summary. It checks the creation of extra branch inside a loop in case of loop rotation. Simply if Exit Candidate has a fallthrough BB and Bottom does not fallthrough (potentially) to Top then rotation will not create a fallthrough from Bottom to Top but will create a branch from Exit Candidate to next block in a chain (which will become the first block in a chain).

[skatkov]

Dear Reviewers, Can I do anything to make a progress on this?

[iteratee]

lib/CodeGen/MachineBlockPlacement.cpp

1952

Can you re-write this comment, I can't make heads or tails of what you're trying to do.

Something like:
Rotating a loop exit to the bottom when there is a fallthrough to top trades the entry fallthrough for an exit fallthrough.
If there is no bottom->top edge, but the chosen exit block does have a fallthrough, We break that fallthrough for nothing in return.

You don't have to use that language, but embedding your example may help as well. Include the Pre and Post blocks in the sequences, it makes it more obvious what's going on, and don't assume that the the header is the chosen exit block.

[skatkov]

Hi Kyle, please take a look, whether it is better wording?

[iteratee]

Approved with the changes I've marked.

lib/CodeGen/MachineBlockPlacement.cpp

1957

*broken now*

1963

This is really good. Thank you.
Could you add one more sentence, that we know there is no exit fallthrough from Bn because of the check above?

1972

"Rotating loop to put exit " ... " at bottom.\n"

[skatkov]

The commit has been reverted as it causes sanitizer build bot crash. Will investigate.

lib/CodeGen/MachineBlockPlacement.cpp

void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
   if (ViableTopFallthrough) {
     MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
     for (MachineBasicBlock *Succ : Bottom->successors()) {
       BlockChain *SuccChain = BlockToChain[Succ];
       if (!LoopBlockSet.count(Succ) &&
           (!SuccChain || Succ == *SuccChain->begin()))
         return;
     }
   }
 
   BlockChain::iterator ExitIt = find(LoopChain, ExitingBB);
   if (ExitIt == LoopChain.end())
     return;
 
+  // Rotating a loop exit to the bottom when there is a fallthrough to top
+  // trades the entry fallthrough for an exit fallthrough.
+  // If there is no bottom->top edge, but the chosen exit block does have
+  // a fallthrough, we break that fallthrough for nothing in return.
+
+  // Let's consider an example. We have a built chain of basic blocks
+  // B1, B2, ..., Bn, where Bk is a ExitingBB - chosen exit block.
+  // By doing a rotation we get
+  // Bk+1, ..., Bn, B1, ..., Bk
+  // Break of fallthrough to B1 is compensated by a fallthrough from Bk.
+  // If we had a fallthrough Bk -> Bk+1 it is borken now.
+  // It might be compensated by fallthrough Bn -> B1.
+  // So we have a condition to avoid creation of extra branch by loop rotation.
+  // All below must be true to avoid loop rotation:
+  //   If there is a fallthrough to top (B1)
+  //   There was fallthrough from chosen exit block (Bk) to next one (Bk+1)
+  //   There is no fallthrough from bottom (Bn) to top (B1).
+  if (ViableTopFallthrough) {
+    MachineBasicBlock *NextBlockInChain = *std::next(ExitIt);
+    MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
+    if (NextBlockInChain->isPredecessor(ExitingBB))
+      if (!Top->isPredecessor(Bottom))
+        return;
+  }
+
+  DEBUG(dbgs() << "Do loop rotation with new exit block "
+               << getBlockName(ExitingBB) << "\n");
   std::rotate(LoopChain.begin(), std::next(ExitIt), LoopChain.end());
 }
 
 /// \brief Attempt to rotate a loop based on profile data to reduce branch cost.
 ///
 /// With profile data, we can determine the cost in terms of missed fall through
 /// opportunities when rotating a loop chain and select the best rotation.
 /// Basically, there are three kinds of cost to consider for each rotation:

test/CodeGen/X86/block-placement.ll

 }
 
 define void @unnatural_cfg2() {
 ; Test that we can handle a loop with a nested natural loop *and* an unnatural
 ; loop. This was reduced from a crash on block placement when run over
 ; single-source GCC.
 ; CHECK-LABEL: unnatural_cfg2
 ; CHECK: %entry
+; CHECK: %loop.header
 ; CHECK: %loop.body1
 ; CHECK: %loop.body2
 ; CHECK: %loop.body4
 ; CHECK: %loop.inner2.begin
 ; CHECK: %loop.inner2.begin
 ; CHECK: %loop.body3
 ; CHECK: %loop.inner1.begin
-; CHECK: %loop.header
 ; CHECK: %bail
 
 entry:
   br label %loop.header
 
 loop.header:
   %comp0 = icmp eq i32* undef, null
   br i1 %comp0, label %bail, label %loop.body1

 then:                                             ; preds = %endif
   call void @effect(i32 3)
   br label %ret
 
 ret:                                              ; preds = %endif, %then
   ret void
 }
 
+define i32 @not_rotate_if_extra_branch(i32 %count) {
+; Test checks that there is no loop rotation
+; if it introduces extra branch.
+; Specifically in this case because best exit is .header
+; but it has fallthrough to .middle block and last block in
+; loop chain .slow does not have afallthrough to .header.
+; CHECK-LABEL: not_rotate_if_extra_branch
+; CHECK: %.entry
+; CHECK: %.header
+; CHECK: %.middle
+; CHECK: %.backedge
+; CHECK: %.slow
+; CHECK: %.bailout
+; CHECK: %.stop
+.entry:
+  %sum.0 = shl nsw i32 %count, 1
+  br label %.header
+
+.header:
+  %i = phi i32 [ %i.1, %.backedge ], [ 0, %.entry ]
+  %sum = phi i32 [ %sum.1, %.backedge ], [ %sum.0, %.entry ]
+  %is_exc = icmp sgt i32 %i, 9000000
+  br i1 %is_exc, label %.bailout, label %.middle, !prof !13
+
+.bailout:
+  %sum.2 = add nsw i32 %count, 1
+  br label %.stop
+
+.middle:
+  %pr.1 = and i32 %i, 1023
+  %pr.2 = icmp eq i32 %pr.1, 0
+  br i1 %pr.2, label %.slow, label %.backedge, !prof !14
+
+.slow:
+  tail call void @effect(i32 %sum)
+  br label %.backedge
+
+.backedge:
+  %sum.1 = add nsw i32 %i, %sum
+  %i.1 = add nsw i32 %i, 1
+  %end = icmp slt i32 %i.1, %count
+  br i1 %end, label %.header, label %.stop, !prof !15
+
+.stop:
+  %sum.phi = phi i32 [ %sum.1, %.backedge ], [ %sum.2, %.bailout ]
+  ret i32 %sum.phi
+}
+
 declare void @effect(i32)
 
 !5 = !{!"branch_weights", i32 84, i32 16}
 !6 = !{!"function_entry_count", i32 10}
 !7 = !{!"branch_weights", i32 60, i32 40}
 !8 = !{!"branch_weights", i32 5001, i32 4999}
 !9 = !{!"branch_weights", i32 85, i32 15}
 !10 = !{!"branch_weights", i32 90, i32 10}
 !11 = !{!"branch_weights", i32 1, i32 1}
 !12 = !{!"branch_weights", i32 5, i32 3}
+!13 = !{!"branch_weights", i32 1, i32 1}
+!14 = !{!"branch_weights", i32 1, i32 1023}
+!15 = !{!"branch_weights", i32 4095, i32 1}

test/CodeGen/X86/code_placement_cold_loop_blocks.ll

if.end:
   %call2 = call zeroext i1 @a()
   br i1 %call2, label %header, label %end, !prof !5
 
 end:
   call void @f()
   ret void
 }
 
-define void @nested_loop_0() !prof !1 {
+define void @nested_loop_0(i1 %flag) !prof !1 {
 ; Test if a block that is cold in the inner loop but not cold in the outer loop
 ; will merged to the outer loop chain.
 ;
 ; CHECK-LABEL: nested_loop_0:
 ; CHECK: callq c
 ; CHECK: callq d
 ; CHECK: callq e
 ; CHECK: callq b

 
 if.then:
   call void @d()
   %call3 = call zeroext i1 @a()
   br i1 %call3, label %header2, label %header, !prof !3
 
 if.else:
   call void @e()
-  %call2 = call zeroext i1 @a()
-  br i1 %call2, label %header2, label %header, !prof !3
+  br i1 %flag, label %header2, label %header, !prof !3
 
 end:
   call void @f()
   ret void
 }
 
 define void @nested_loop_1() !prof !1 {
 ; Test if a cold block in an inner loop will be placed at the end of the