[MBP] do not reorder and move up loop latch block

[SjoerdMeijer]

Summary

Do not reorder and move up a loop latch block when optimising for size because this will generate an extra unconditional branch. Also some more cleaning up of comments.

[mgrang]

lib/CodeGen/MachineBlockPlacement.cpp

1130

Can we change the two ifs into an if-else clause and move the "return nullptr" outside the if-else? (and also get rid of the braces after the ifs). This will make the code more compact and reduce duplication.

[SjoerdMeijer]

lib/CodeGen/MachineBlockPlacement.cpp

1130

I don't see how I can do this with an if-else and keep the different debug messages. I created these 2 different ifs because I wanted to see the exact reason for not selecting a new header.

[davidxl]

Please split the comment changes into a different patch

lib/CodeGen/MachineBlockPlacement.cpp

88

Just one line comment defining "Outlining" should be put here. The rest do not fit.

574

Remove redundunat "and Pred needs to be ....". Actually I don't see the need of modification of this paragraph.

675

add "is less than probability threshold "

[SjoerdMeijer]

Hi David, thanks for reviewing.
I will separate the functional changes from the tidy up. This patch implements the functional change.
Cheers.

[davidxl]

lib/CodeGen/MachineBlockPlacement.cpp

972

There is one case where the existing header is not the cfg successor of its layout predecessor. In this case, rotating loop does not actually add additional size cost.

[SjoerdMeijer]

I have added checks to see if the header's layout predecessor is a fallthrough or unconditional branch to the loop header. In that case we do not move up the latch block, but we still do otherwise.

[SjoerdMeijer]

Ping. :-)

[davidxl]

Can you add a test case to cover that rotation happens when there is no fall through predecessor for the header?

lib/CodeGen/MachineBlockPlacement.cpp

956

This should be renamed to findFallthroughPredecessor and add a brief documentation.

LayoutPredecessor by definition does not need to be its cfg predecessor.

982

if (...->canFallthrough()) {
..
}

[SjoerdMeijer]

It's funny but I haven't been able to create an extra test case that still does the reordering. The issue in creating that test case is, i) when I manually reorder blocks in the .ll files to create a layout predecessos that cannot fallthrough, then somehow the blocks still end up in the original order again and there is a fallthrough, and ii) even for conditional branches to the loop the canFallThrough function returns true, which again prevents me from creating a case that does not fallthrough.

[davidxl]

Re the new test case -- you can just modify the test case by branch directly to block %bb instead of %loop from entry.

[SjoerdMeijer]

Thanks for the suggestion!
I have been looking at it again and with the change to jump to bb from entry the cfg looks likes this:

      entry-------
                  |
      loop        |
      /     \     |
blocka    bb  - -
           |      
          exit

the problem however is that blocks are placed like this (before pass MBP):

entry
block_a
loop
bb
exit

and when it is looking for a best loop top for "loop", it finds that "block_a" is placed before "loop", and it can fallthrough to "loop". So this does not result in "block_a" being placed before "loop". Actually, while writing tests, there will always be some preheader that fallsthrough to the loop.

The fact that it is difficult to come up with a test is a bit worrying, in the sense that we add code in form of hasFallthroughLayoutPredecessor() that is always going to return true, so we will never end rotating the latch block to the top (when optimising for size). That in itself is fine, I think, because it shows that it in theory there is this case, but in practise it never happens. If we agree on this (I may have missed something), then we can make the implementation much simpler. We get rid of hasFallthroughLayoutPredecessor(), and simply don't do findBestLoopTop() when we optimize for size. By the way, while looking at this again I found that hasFallthroughLayoutPredecessor() is a bit dodgy because there is much simpler implementation possible, but it is not really important for now.

[SjoerdMeijer]

I got rid of the helper function, and added the fixme/todo to the comments.

[SjoerdMeijer]

Okay to commit?

[davidxl]

lgtm with the nit.

lib/CodeGen/MachineBlockPlacement.cpp

976

if (F->getFunction()->optForSize())

..

[SjoerdMeijer]

Thanks a lot for the review! Will fix and commit.

lib/CodeGen/MachineBlockPlacement.cpp

 
 // Definition:
 // - Outlining: placement of a basic block outside the chain or hot path.
 
 static cl::opt<bool> OutlineOptionalBranches(
     "outline-optional-branches",
     cl::desc("Outlining optional branches will place blocks that are optional "
               "branches, i.e. branches with a common post dominator, outside "
               "the hot path or chain"),
     cl::init(false), cl::Hidden);
 
 static cl::opt<unsigned> OutlineOptionalThreshold(
     "outline-optional-threshold",
     cl::desc("Don't outline optional branches that are a single block with an "
              "instruction count below this threshold"),
     cl::init(4), cl::Hidden);
 
bool MachineBlockPlacement::hasBetterLayoutPredecessor(
   //     |   Pred
   //     |   /
   //     Succ
   // In this case, we are evaluating whether to select edge -> Succ, e.g.
   // set Succ as the layout successor of BB. Picking Succ as BB's
   // successor breaks the CFG constraints (FIXME: define these constraints).
   // With this layout, Pred BB
   // is forced to be outlined, so the overall cost will be cost of the
   // branch taken from BB to Pred, plus the cost of back taken branch
   // from Pred to Succ, as well as the additional cost associated
   // with the needed unconditional jump instruction from Pred To Succ.
 
   // The cost of the topological order layout is the taken branch cost
   // from BB to Succ, so to make BB->Succ a viable candidate, the following
   // must hold:
   //     2 * freq(BB->Pred) * taken_branch_cost + unconditional_jump_cost
   //      < freq(BB->Succ) *  taken_branch_cost.
bool MachineBlockPlacement::hasBetterLayoutPredecessor(
   // is 0. Then the non topo layout is better when
   // freq(S->Pred) < freq(BB->S1).
   // This is exactly what is checked below.
   // Note there are other shapes that apply (Pred may not be a single block,
   // but they all fit this general pattern.)
   BranchProbability HotProb = getLayoutSuccessorProbThreshold(BB);
 
   // Make sure that a hot successor doesn't have a globally more
   // important predecessor.
   BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb;
   bool BadCFGConflict = false;
 
   for (MachineBasicBlock *Pred : Succ->predecessors()) {
     if (Pred == Succ || BlockToChain[Pred] == &SuccChain ||
         (BlockFilter && !BlockFilter->count(Pred)) ||
         BlockToChain[Pred] == &Chain)
       continue;
for (;;) {
     Chain.merge(BestSucc, &SuccChain);
     BB = *std::prev(Chain.end());
   }
 
   DEBUG(dbgs() << "Finished forming chain for header block "
                << getBlockName(*Chain.begin()) << "\n");
 }
 
 /// \brief 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
 /// unconditional jump (for the backedge) rotating it in front of the loop
 /// header is always profitable.
 MachineBasicBlock *
 MachineBlockPlacement::findBestLoopTop(MachineLoop &L,
                                        const BlockFilterSet &LoopBlockSet) {
+  // Placing the latch block before the header may introduce an extra branch
+  // that skips this block the first time the loop is executed, which we want
+  // to avoid when optimising for size.
+  // FIXME: in theory there is a case that does not introduce a new branch,
+  // i.e. when the layout predecessor does not fallthrough to the loop header.
+  // In practice this never happens though: there always seems to be a preheader
+  // that can fallthrough and that is also placed before the header.
+  if (L.getHeader()->getParent()->getFunction()->optForSize())
+    return L.getHeader();
+
   // Check that the header hasn't been fused with a preheader block due to
   // crazy branches. If it has, we need to start with the header at the top to
   // prevent pulling the preheader into the loop body.
   BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
   if (!LoopBlockSet.count(*HeaderChain.begin()))
     return L.getHeader();
 
   DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader())
                << "\n");
 
   BlockFrequency BestPredFreq;
   MachineBasicBlock *BestPred = nullptr;
MachineBlockPlacement::findBestLoopExit(MachineLoop &L,
   // loop, just use the loop header to layout the loop.
   if (!ExitingBB) {
     DEBUG(dbgs() << "    No other candidate exit blocks, using loop header\n");
     return nullptr;
   }
   if (L.getNumBlocks() == 1) {
     DEBUG(dbgs() << "    Loop has 1 block, using loop header as exit\n");
     return nullptr;
   }
 
   // Also, if we have exit blocks which lead to outer loops but didn't select
   // one of them as the exiting block we are rotating toward, disable loop
   // rotation altogether.
   if (!BlocksExitingToOuterLoop.empty() &&
       !BlocksExitingToOuterLoop.count(ExitingBB))
     return nullptr;
 

test/CodeGen/X86/loop-blocks.ll

bb:
   call void @loop_latch()
   br label %loop
 
 done:
   call void @exit()
   ret void
 }
 
+; This is exactly the same function as slightly_more_involved.
+; The difference is that when optimising for size, we do not want
+; to see this reordering.
+
+; CHECK-LABEL: slightly_more_involved_2:
+; CHECK-NOT:      jmp .LBB5_1
+; CHECK:          .LBB5_1:
+; CHECK-NEXT:     callq body
+
+define void @slightly_more_involved_2() #0 {
+entry:
+  br label %loop
+
+loop:
+  call void @body()
+  %t0 = call i32 @get()
+  %t1 = icmp slt i32 %t0, 2
+  br i1 %t1, label %block_a, label %bb
+
+bb:
+  %t2 = call i32 @get()
+  %t3 = icmp slt i32 %t2, 99
+  br i1 %t3, label %exit, label %loop
+
+block_a:
+  call void @bar99()
+  br label %loop
+
+exit:
+  call void @exit()
+  ret void
+}
+
+attributes #0 = { minsize norecurse nounwind optsize readnone uwtable }
+
 declare void @bar99() nounwind
 declare void @bar100() nounwind
 declare void @bar101() nounwind
 declare void @bar102() nounwind
 declare void @body() nounwind
 declare void @exit() nounwind
 declare void @loop_header() nounwind
 declare void @loop_latch() nounwind
 declare i32 @get() nounwind
 declare void @block_a_true_func() nounwind
 declare void @block_a_false_func() nounwind
 declare void @block_a_merge_func() nounwind