Add a flag to experiment with outlining optional branches.

[djasper]

Summary

In a CFG with the edges A->B->C and A->C, B is an optional branch.

LLVM's default behavior is to lay the blocks out naturally, i.e. A, B, C, in order to improve code locality and fall throughs. However, if a function contains many of those optional branches only a few of which are taken, this leads to a lot of unnecessary icache misses. Moving B out of line can work around this.

[djasper]

Removed left-over attempt to use llvm.assume to modify branch probabilities.

[djasper]

Move if statement into the right scope. I think, I might have messed this up when merging.

[reames]

Codewise, I have some concern about adding the post dominator dependency. Any idea how much running time that adds? Otherwise, LGTM.

Approach wise, I think you may want to invert your reasoning. Your currently inferring coldness of the conditional block from the hotness of the successor. It would be more clear and predictable to consider the probability of the skipped successors directly.

Overall, I'm really excited about the direction of this patch. This might be very material on my workloads. Once this is landed, I'll do a run and see what differences I can report.

[djasper]

As previously discussed on IRC, using the post dominator tree is probably not an option for performance reasons. I'll try to come up with an implementation that doesn't need it. If we had it, the implementation can actually be simplified as in this version of the patch (a single lookup in the dominator tree instead of many). Just adding this for documentation of the progress.

[hfinkel]

In D7719#125705, @djasper wrote:

As previously discussed on IRC, using the post dominator tree is probably not an option for performance reasons.

I highly recommend measuring the performance of the post-dom-tree version before concluding it is too expensive. True, we've traditionally avoided them. But we also added use of a post-dom tree to the MachineSink pass, because it was the right way to solve the problem, and the compile time cost increase turned out to be relatively small.

I'll try to come up with an implementation that doesn't need it. If we had it, the implementation can actually be simplified as in this version of the patch (a single lookup in the dominator tree instead of many). Just adding this for documentation of the progress.

[djasper]

Updated to not use a post-dominator tree.

[djasper]

Don't do needless computations if optional branches aren't outlined.

[djasper]

Re-add the test.

[chandlerc]

I'm not sure this is exactly the right *heuristic*, but the code is fine and I really want to get it into the tree because it highlights fundamental flaws in the existing MBP algorithm that you've found. The flag is off by default and only requires a domtree, so I think it is entirely reasonable to commit. We can and should experiment with this off-by-default heuristic, learn what we can, and either fix and enable it or replace it with a better construct.

[djasper]

Submitted as r231230.

lib/CodeGen/MachineBlockPlacement.cpp

 #include "llvm/CodeGen/Passes.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
+#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Target/TargetInstrInfo.h"

 
 // FIXME: Find a good default for this flag and remove the flag.
 static cl::opt<unsigned>
 ExitBlockBias("block-placement-exit-block-bias",
               cl::desc("Block frequency percentage a loop exit block needs "
                        "over the original exit to be considered the new exit."),
               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);
+
 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 {
   const MachineLoopInfo *MLI;
 
   /// \brief A handle to the target's instruction info.
   const TargetInstrInfo *TII;
 
   /// \brief A handle to the target's lowering info.
   const TargetLoweringBase *TLI;
 
+  /// \brief A handle to the post dominator tree.
+  MachineDominatorTree *MDT;
+
+  /// \brief A set of blocks that are unavoidably execute, i.e. they dominate
+  /// all terminators of the MachineFunction. 
+  SmallPtrSet<MachineBasicBlock *, 4> UnavoidableBlocks;
+
   /// \brief Allocator and owner of BlockChain structures.
   ///
   /// We build BlockChains lazily while processing the loop structure of
   /// a function. To reduce malloc traffic, we allocate them using this
   /// slab-like allocator, and destroy them after the pass completes. An
   /// important guarantee is that this allocator produces stable pointers to
   /// the chains.
   SpecificBumpPtrAllocator<BlockChain> ChainAllocator;
MachineBlockPlacement() : MachineFunctionPass(ID) {
     initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnMachineFunction(MachineFunction &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<MachineBranchProbabilityInfo>();
     AU.addRequired<MachineBlockFrequencyInfo>();
+    AU.addRequired<MachineDominatorTree>();
     AU.addRequired<MachineLoopInfo>();
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 };
 }
 
 char MachineBlockPlacement::ID = 0;
 char &llvm::MachineBlockPlacementID = MachineBlockPlacement::ID;
 INITIALIZE_PASS_BEGIN(MachineBlockPlacement, "block-placement2",
                       "Branch Probability Basic Block Placement", false, false)
 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
 INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 INITIALIZE_PASS_END(MachineBlockPlacement, "block-placement2",
                     "Branch Probability Basic Block Placement", false, false)
 
 #ifndef NDEBUG
 /// \brief Helper to print the name of a MBB.
 ///
 /// Only used by debug logging.
for (MachineBasicBlock *Succ : BB->successors()) {
     if (Succ != *SuccChain.begin()) {
       DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> Mid chain!\n");
       continue;
     }
 
     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)
+      return Succ;
+
     // Only consider successors which are either "hot", or wouldn't violate
     // any CFG constraints.
     if (SuccChain.LoopPredecessors != 0) {
       if (SuccProb < HotProb) {
         DEBUG(dbgs() << "    " << getBlockName(Succ) << " -> " << SuccProb
                      << " (prob) (CFG conflict)\n");
         continue;
       }
if (BlockToChain[I] != &PlacedChain) {
       // and satisfies the requirements of merging chains.
       return *BlockToChain[I]->begin();
     }
   }
   return nullptr;
 }
 
 void MachineBlockPlacement::buildChain(
-    MachineBasicBlock *BB,
-    BlockChain &Chain,
+    MachineBasicBlock *BB, BlockChain &Chain,
     SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
     const BlockFilterSet *BlockFilter) {
   assert(BB);
   assert(BlockToChain[BB] == &Chain);
   MachineFunction &F = *BB->getParent();
   MachineFunction::iterator PrevUnplacedBlockIt = F.begin();
 
   MachineBasicBlock *LoopHeaderBB = BB;
for (;;) {
                    << getBlockName(BB) << " -> " << getBlockName(NextBB)
                    << "\n");
       Chain->merge(NextBB, nullptr);
       FI = NextFI;
       BB = NextBB;
     }
   }
 
+  if (OutlineOptionalBranches) {
+    // Find the nearest common dominator of all of F's terminators.
+    MachineBasicBlock *Terminator = nullptr;
+    for (MachineBasicBlock &MBB : F) {
+      if (MBB.succ_size() == 0) {
+        if (Terminator == nullptr)
+          Terminator = &MBB;
+        else
+          Terminator = MDT->findNearestCommonDominator(Terminator, &MBB);
+      }
+    }
+
+    // MBBs dominating this common dominator are unavoidable.
+    UnavoidableBlocks.clear();
+    for (MachineBasicBlock &MBB : F) {
+      if (MDT->dominates(&MBB, Terminator)) {
+        UnavoidableBlocks.insert(&MBB);
+      }
+    }
+  }
+
   // Build any loop-based chains.
   for (MachineLoopInfo::iterator LI = MLI->begin(), LE = MLI->end(); LI != LE;
        ++LI)
     buildLoopChains(F, **LI);
 
   SmallVector<MachineBasicBlock *, 16> BlockWorkList;
 
   SmallPtrSet<BlockChain *, 4> UpdatedPreds;
bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) {
   if (skipOptnoneFunction(*F.getFunction()))
     return false;
 
   MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
   MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
   MLI = &getAnalysis<MachineLoopInfo>();
   TII = F.getSubtarget().getInstrInfo();
   TLI = F.getSubtarget().getTargetLowering();
+  MDT = &getAnalysis<MachineDominatorTree>();
   assert(BlockToChain.empty());
 
   buildCFGChains(F);
 
   BlockToChain.clear();
   ChainAllocator.DestroyAll();
 
   if (AlignAllBlock)

test/CodeGen/X86/code_placement_outline_optional_branches.ll

+; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux < %s | FileCheck %s -check-prefix=CHECK
+; RUN: llc -mcpu=corei7 -mtriple=x86_64-linux -outline-optional-branches < %s | FileCheck %s -check-prefix=CHECK-OUTLINE
+
+define void @foo(i32 %t1, i32 %t2) {
+; Test that we lift the call to 'c' up to immediately follow the call to 'b'
+; when we disable the cfg conflict check.
+;
+; CHECK-LABEL: foo:
+; CHECK: callq a
+; CHECK: callq b
+; CHECK: callq c
+; CHECK: callq d
+;
+; CHECK-OUTLINE-LABEL: foo:
+; CHECK-OUTLINE: callq b
+; CHECK-OUTLINE: callq c
+; CHECK-OUTLINE: callq d
+; CHECK-OUTLINE: callq a
+
+entry:
+  %cmp = icmp eq i32 %t1, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  call void @a()
+  br label %if.end
+
+if.end:
+  call void @b()
+  br label %hotbranch
+
+hotbranch:
+  %cmp2 = icmp eq i32 %t2, 0
+  br i1 %cmp2, label %if.then2, label %if.end2, !prof !1
+
+if.then2:
+  call void @c()
+  br label %if.end2
+
+if.end2:
+  call void @d()
+  ret void
+}
+
+declare void @a()
+declare void @b()
+declare void @c()
+declare void @d()
+
+!1 = !{!"branch_weights", i32 64, i32 4}