[MBP] Fix a really horrible bug in MachineBlockPlacement, but behind a flag for now.

[djasper]

Summary

This is similar to Chandler's r231238 (most details on that commit log).

The difference is that Chandler's version led to putting outlined blocks in reverse order, which does seem to have a quite dramatic performance overhead.

In contrast, this version only picks the back of the worklist, if the previously placed machine block had a successor that wasn't placed for other reasons, especially:

• It was cold.
• It had a globally more important predecessor.

Using the back of the worklist in those circumstances keeps outlined branches together. Once an outlined branch was placed completely, there simply won't be any more successors and it is more useful to start with the hottest block from the entire worklist (and the first one for equal probabilities).

[djasper]

Re-added test. Nicely, none of the existing tests needs to be updated now.

lib/CodeGen/MachineBlockPlacement.cpp

static cl::opt<unsigned> ExitBlockBias(
     cl::init(0), cl::Hidden);
 
 static cl::opt<bool> OutlineOptionalBranches(
     "outline-optional-branches",
     cl::desc("Put completely optional branches, i.e. branches with a common "
              "post dominator, out of line."),
     cl::init(false), cl::Hidden);
 
+static cl::opt<bool> PlaceLastSuccessor(
+    "place-last-successor",
+    cl::desc("When selecting a non-successor block, choose the last block to "
+             "have been a successor. This represents the block whose "
+             "predecessor was most recently placed."),
+    cl::init(false), cl::Hidden);
+
 namespace {
 class BlockChain;
 /// \brief Type for our function-wide basic block -> block chain mapping.
 typedef DenseMap<MachineBasicBlock *, BlockChain *> BlockToChainMapType;
 }
 
 namespace {
 /// \brief A chain of blocks which will be laid out contiguously.
class MachineBlockPlacement : public MachineFunctionPass {
   /// between basic blocks.
   DenseMap<MachineBasicBlock *, BlockChain *> BlockToChain;
 
   void markChainSuccessors(BlockChain &Chain, MachineBasicBlock *LoopHeaderBB,
                            SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
                            const BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
                                          BlockChain &Chain,
-                                         const BlockFilterSet *BlockFilter);
-  MachineBasicBlock *
-  selectBestCandidateBlock(BlockChain &Chain,
-                           SmallVectorImpl<MachineBasicBlock *> &WorkList,
-                           const BlockFilterSet *BlockFilter);
+                                         const BlockFilterSet *BlockFilter,
+                                         bool &HasUnmergedSuccessors);
+  MachineBasicBlock *selectBestCandidateBlock(
+      BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
+      const BlockFilterSet *BlockFilter, bool HasUnmergedSuccessors);
   MachineBasicBlock *
   getFirstUnplacedBlock(MachineFunction &F, const BlockChain &PlacedChain,
                         MachineFunction::iterator &PrevUnplacedBlockIt,
                         const BlockFilterSet *BlockFilter);
   void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
                   SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
                   const BlockFilterSet *BlockFilter = nullptr);
   MachineBasicBlock *findBestLoopTop(MachineLoop &L,

 /// successors which also pass the block filter. It will attempt to avoid
 /// breaking CFG structure, but cave and break such structures in the case of
 /// very hot successor edges.
 ///
 /// \returns The best successor block found, or null if none are viable.
 MachineBasicBlock *
 MachineBlockPlacement::selectBestSuccessor(MachineBasicBlock *BB,
                                            BlockChain &Chain,
-                                           const BlockFilterSet *BlockFilter) {
+                                           const BlockFilterSet *BlockFilter,
+                                           bool &HasUnmergedSuccessors) {
   const BranchProbability HotProb(4, 5); // 80%
 
   MachineBasicBlock *BestSucc = nullptr;
   // FIXME: Due to the performance of the probability and weight routines in
   // the MBPI analysis, we manually compute probabilities using the edge
   // weights. This is suboptimal as it means that the somewhat subtle
   // definition of edge weight semantics is encoded here as well. We should
   // improve the MBPI interface to efficiently support query patterns such as
if (&SuccChain == &Chain) {
       DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> Already merged!\n");
       continue;
     }
     if (Succ != *SuccChain.begin()) {
       DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> Mid chain!\n");
       continue;
     }
 
+    HasUnmergedSuccessors = true;
+
     uint32_t SuccWeight = MBPI->getEdgeWeight(BB, Succ);
     BranchProbability SuccProb(SuccWeight / WeightScale, SumWeight);
 
     // If we outline optional branches, look whether Succ is unavoidable, i.e.
     // dominates all terminators of the MachineFunction. If it does, other
     // successors must be optional. Don't do this for cold branches.
     if (OutlineOptionalBranches && SuccProb > HotProb.getCompl() &&
         UnavoidableBlocks.count(Succ) > 0)

 /// profitable only really makes sense in the context of a loop. This returns
 /// the most frequently visited block in the worklist, which in the case of
 /// a loop, is the one most desirable to be physically close to the rest of the
 /// loop body in order to improve icache behavior.
 ///
 /// \returns The best block found, or null if none are viable.
 MachineBasicBlock *MachineBlockPlacement::selectBestCandidateBlock(
     BlockChain &Chain, SmallVectorImpl<MachineBasicBlock *> &WorkList,
-    const BlockFilterSet *BlockFilter) {
+    const BlockFilterSet *BlockFilter, bool HasUnmergedSuccessors) {
+  if (PlaceLastSuccessor && HasUnmergedSuccessors) {
+    // If we're just placing the last successor as the best candidate, the
+    // logic is super simple. We skip the already placed entries on the
+    // worklist and return the most recently added entry that isn't placed.
+    while (!WorkList.empty()) {
+      MachineBasicBlock *SuccBB = WorkList.pop_back_val();
+      BlockChain &SuccChain = *BlockToChain.lookup(SuccBB);
+      if (&SuccChain == &Chain) {
+        DEBUG(dbgs() << "    " << getBlockName(SuccBB)
+                     << " -> Already merged!\n");
+        continue;
+      }
+      assert(SuccChain.LoopPredecessors == 0 && "Found CFG-violating block");
+      return SuccBB;
+    }
+
+    return nullptr;
+  }
   // Once we need to walk the worklist looking for a candidate, cleanup the
   // worklist of already placed entries.
   // FIXME: If this shows up on profiles, it could be folded (at the cost of
   // some code complexity) into the loop below.
   WorkList.erase(std::remove_if(WorkList.begin(), WorkList.end(),
                                 [&](MachineBasicBlock *BB) {
                                   return BlockToChain.lookup(BB) == &Chain;
                                 }),
void MachineBlockPlacement::buildChain(
   BB = *std::prev(Chain.end());
   for (;;) {
     assert(BB);
     assert(BlockToChain[BB] == &Chain);
     assert(*std::prev(Chain.end()) == BB);
 
     // Look for the best viable successor if there is one to place immediately
     // after this block.
-    MachineBasicBlock *BestSucc = selectBestSuccessor(BB, Chain, BlockFilter);
+    bool HasUnmergedSuccessors = false;
+    MachineBasicBlock *BestSucc =
+        selectBestSuccessor(BB, Chain, BlockFilter, HasUnmergedSuccessors);
 
     // If an immediate successor isn't available, look for the best viable
     // block among those we've identified as not violating the loop's CFG at
     // this point. This won't be a fallthrough, but it will increase locality.
     if (!BestSucc)
-      BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter);
+      BestSucc = selectBestCandidateBlock(Chain, BlockWorkList, BlockFilter,
+                                          HasUnmergedSuccessors);
 
     if (!BestSucc) {
       BestSucc =
           getFirstUnplacedBlock(F, Chain, PrevUnplacedBlockIt, BlockFilter);
       if (!BestSucc)
         break;
 
       DEBUG(dbgs() << "Unnatural loop CFG detected, forcibly merging the "

test/CodeGen/X86/block-placement.ll

-; RUN: llc -mtriple=i686-linux -pre-RA-sched=source < %s | FileCheck %s
+; RUN: llc -mtriple=i686-linux -place-last-successor -pre-RA-sched=source < %s | FileCheck %s
 
 declare void @error(i32 %i, i32 %a, i32 %b)
 
 define i32 @test_ifchains(i32 %i, i32* %a, i32 %b) {
 ; Test a chain of ifs, where the block guarded by the if is error handling code
 ; that is not expected to run.
 ; CHECK-LABEL: test_ifchains:
 ; CHECK: %entry
else:
   %gep2 = getelementptr i32, i32* %a, i32 2
   %val2 = load i32, i32* %gep2
   br label %exit
 
 exit:
   %ret = phi i32 [ %val1, %then ], [ %val2, %else ]
   ret i32 %ret
 }
+
+define void @test_outlined() {
+; This test ends up with diamond control flow in outlined optional regions.
+; These diamonds should still be locally cohensive even when out-of-line due to
+; being cold.
+; CHECK-LABEL: test_outlined:
+; CHECK: %a1
+; CHECK: %a2
+; CHECK: %done
+; CHECK: %b1
+; CHECK: %c1
+; CHECK: %d1
+; CHECK: %f1
+; CHECK: %b2
+; CHECK: %c2
+; CHECK: %d2
+; CHECK: %f2
+
+a1:
+  %call.a1 = call i1 @a1()
+  br i1 %call.a1, label %b1, label %a2, !prof !0
+
+b1:
+  %call.b1 = call i1 @b1()
+  br i1 %call.b1, label %c1, label %d1
+
+c1:
+  call void @c1()
+  br label %f1
+
+d1:
+  call void @d1()
+  br label %f1
+
+f1:
+  call void @f1()
+  br label %a2
+
+a2:
+  %call.a2 = call i1 @a2()
+  br i1 %call.a2, label %b2, label %done, !prof !0
+
+b2:
+  %call.b2 = call i1 @b2()
+  br i1 %call.b2, label %c2, label %d2
+
+c2:
+  call void @c2()
+  br label %f2
+
+d2:
+  call void @d2()
+  br label %f2
+
+f2:
+  call void @f2()
+  br label %done
+
+done:
+  call void @done()
+  ret void
+}
+
+declare i1 @a1()
+
+declare i1 @b1()
+
+declare void @c1()
+
+declare void @d1()
+
+declare void @f1()
+
+declare i1 @a2()
+
+declare i1 @b2()
+
+declare void @c2()
+
+declare void @d2()
+
+declare void @f2()
+
+declare void @done()