[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

1128

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

1128

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.

572

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

652

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

965

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

937

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

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

975

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

969

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
   //
   // Here, we are evaluating to select Succ or Pred as a successor of BB.
   // If we choose Succ, then we break the topological ordering and Pred needs
   // to be outlined which is shown here:
   //
   //                ---<----
   //                |      |
   //          BB-->Succ   Pred
   //           |           |
   //           ------>------
   //
   // The cost = taken_branch(BB->Pred) + taken_back_branch(Pred->Succ) +
bool MachineBlockPlacement::hasBetterLayoutPredecessor(
   // profile data).
 
   BranchProbability HotProb = getLayoutSuccessorProbThreshold(BB);
 
   // Forward checking. For case 2, SuccProb will be 1.
   if (SuccProb < HotProb) {
     DEBUG(dbgs() << "    Not a candidate: " << getBlockName(Succ) << " "
                  << "Respecting topological ordering because "
                  << "probability is less than prob treshold: " 
                  << SuccProb << "\n");
     return true;
   }
 
   // Make sure that a hot successor doesn't have a globally more
   // important predecessor.
   BlockFrequency CandidateEdgeFreq = MBFI->getBlockFreq(BB) * RealSuccProb;
   bool BadCFGConflict = false;
for (;;) {
     Chain.merge(BestSucc, &SuccChain);
     BB = *std::prev(Chain.end());
   }
 
   DEBUG(dbgs() << "Finished forming chain for header block "
                << getBlockName(*Chain.begin()) << "\n");
 }
 
+static MachineBasicBlock * findLayoutPredecessor(MachineBasicBlock &MB)
+{
+  for (MachineBasicBlock *Pred : MB.predecessors()) {
+    if (Pred->isLayoutSuccessor(&MB)) {
+      DEBUG(dbgs() << "   Found layout pred: " << Pred->getName() << "\n");
+      return Pred;
+    }
+  }
+  DEBUG(dbgs() << "    Cannot find layout pred.\n");
+  return nullptr;
+}
+
 /// \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) {
+  DEBUG(dbgs() << "Finding best loop top for: " << getBlockName(L.getHeader())
+               << "\n");
+  // 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. So we keep the header, i.e. don't move the
+  // latch block, when the header layout predecessor is a fallthrough or
+  // unconditional branch to the header, because that would introduce this new
+  // branch. But if there is already a branch, then we can still move up the
+  // latch block.
+  MachineBasicBlock * LayoutPredBB = findLayoutPredecessor(*L.getHeader());
+  if (L.getHeader()->getParent()->getFunction()->optForSize() && LayoutPredBB) {
+    SmallVector<MachineOperand, 4> Cond;
+    MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+    if (!TII->analyzeBranch(*LayoutPredBB, TBB, FBB, Cond) ||    // fallthrough
+        (TBB == L.getHeader() && !FBB)) {              // branch to loop header
+      DEBUG(dbgs() << "    Using loop header: layout predecessor is a "
+                   << "fallthrough or unconditional branch and we optimize "
+                   << "for size\n");
+      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;
   for (MachineBasicBlock *Pred : L.getHeader()->predecessors()) {
     if (!LoopBlockSet.count(Pred))
       continue;
     DEBUG(dbgs() << "    header pred: " << getBlockName(Pred) << ", has "
                  << Pred->succ_size() << " successors, ";
           MBFI->printBlockFreq(dbgs(), Pred) << " freq\n");
if (!HasLoopingSucc) {
       BestExitEdgeFreq = OldBestExitEdgeFreq;
     }
   }
   // Without a candidate exiting block or with only a single block in the
   // 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.

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
+; HECK-NOT-NEXT: callq bar99
+
+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