[MBP] Prevent rotating a chain contains entry block

[Carrot]

Summary

The entry block should always be the first BB in a function. So we should not rotate a chain contains the entry block.

[xur]

Look reasonable to me.

[snehasish]

Can we add a test for this?

llvm/lib/CodeGen/MachineBlockPlacement.cpp

2390

Consider using the helper MachineBasicBlock::isEntryBlock here and above.

[davidxl]

yes, a test case please :) Any performance numbers?

[Carrot]

In D92882#2441182, @snehasish wrote:

Can we add a test for this?

Sorry, no small test case for it.
It was triggered by https://reviews.llvm.org/D89088, when build firefox and chrome with LTO+PGO. This patch has been verified for them.

[Carrot]

In D92882#2441215, @davidxl wrote:

yes, a test case please :) Any performance numbers?

It doesn't have any performance impact.
If user doesn't notice anything, there is no such case for them.
If someone encountered such case, he should get a compiler crash in LiveDebugVariable pass.

[davidxl]

It is possible to synthesize a test case that rotates the entry without the fix, no? The expected output is that the entry is not rotated (no need to reproduce crash).

[Carrot]

In D92882#2444285, @davidxl wrote:

It is possible to synthesize a test case that rotates the entry without the fix, no? The expected output is that the entry is not rotated (no need to reproduce crash).

The key is to generate an entry block and make the following condition in buildCFGChains() evaluated as false:

if (!TII->analyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough())
  break;

It means the entry block must end with an unanalyzable branch and it must also fall through to following block, so the entry block will be pre-merged with the following block, the following block is a loop header, so later it can be rotated by rotateLoop.

I failed to construct such a test case after a whole day's experiments :(

[davidxl]

thanks for working on the test -- good to add later if possible. LGTM after addressing snehasish's comment.

[Carrot]

Will commit this version.

llvm/lib/CodeGen/MachineBlockPlacement.cpp

void MachineBlockPlacement::rotateLoop(BlockChain &LoopChain,
 
   MachineBasicBlock *Top = *LoopChain.begin();
   MachineBasicBlock *Bottom = *std::prev(LoopChain.end());
 
   // If ExitingBB is already the last one in a chain then nothing to do.
   if (Bottom == ExitingBB)
     return;
 
+  // The entry block should always be the first BB in a function.
+  if (Top->isEntryBlock())
+    return;
+
   bool ViableTopFallthrough = hasViableTopFallthrough(Top, LoopBlockSet);
 
   // If the header has viable fallthrough, check whether the current loop
   // bottom is a viable exiting block. If so, bail out as rotating will
   // introduce an unnecessary branch.
   if (ViableTopFallthrough) {
     for (MachineBasicBlock *Succ : Bottom->successors()) {
       BlockChain *SuccChain = BlockToChain[Succ];

 ///    3. The missed fall through edge (if it exists) from the last BB to the
 ///    first BB in the loop chain.
 ///  Therefore, the cost for a given rotation is the sum of costs listed above.
 ///  We select the best rotation with the smallest cost.
 void MachineBlockPlacement::rotateLoopWithProfile(
     BlockChain &LoopChain, const MachineLoop &L,
     const BlockFilterSet &LoopBlockSet) {
   auto RotationPos = LoopChain.end();
+  MachineBasicBlock *ChainHeaderBB = *LoopChain.begin();
+
+  // The entry block should always be the first BB in a function.
+  if (ChainHeaderBB->isEntryBlock())
+    return;
 
   BlockFrequency SmallestRotationCost = BlockFrequency::getMaxFrequency();
 
   // A utility lambda that scales up a block frequency by dividing it by a
   // branch probability which is the reciprocal of the scale.
   auto ScaleBlockFrequency = [](BlockFrequency Freq,
                                 unsigned Scale) -> BlockFrequency {
     if (Scale == 0)
       return 0;
     // Use operator / between BlockFrequency and BranchProbability to implement
     // saturating multiplication.
     return Freq / BranchProbability(1, Scale);
   };
 
   // Compute the cost of the missed fall-through edge to the loop header if the
   // chain head is not the loop header. As we only consider natural loops with
   // single header, this computation can be done only once.
   BlockFrequency HeaderFallThroughCost(0);
-  MachineBasicBlock *ChainHeaderBB = *LoopChain.begin();
   for (auto *Pred : ChainHeaderBB->predecessors()) {
     BlockChain *PredChain = BlockToChain[Pred];
     if (!LoopBlockSet.count(Pred) &&
         (!PredChain || Pred == *std::prev(PredChain->end()))) {
       auto EdgeFreq = MBFI->getBlockFreq(Pred) *
           MBPI->getEdgeProbability(Pred, ChainHeaderBB);
       auto FallThruCost = ScaleBlockFrequency(EdgeFreq, MisfetchCost);
       // If the predecessor has only an unconditional jump to the header, we