[MBP] Don't outline short optional branches

[djasper]

Summary

With the option -outline-optional-branches, LLVM will place optional branches out of line (more details on r231230).

With this patch, this is not done for short optional branches. A short optional branch is a branch containing a single block with an instruction count below a certain threshold (defaulting to 3). Still everything is guarded under -outline-optional-branches).

Outlining a short branch can't significantly improve code locality. It can however decrease performance because of the additional jmp and in cases where the optional branch is hot. This fixes a compile time regression I have observed in a benchmark.

[chandlerc]

lib/CodeGen/MachineBlockPlacement.cpp

394

Shouldn't this be disabling the return of Succ here rather than arbitrarily returning Pred?

And in general, it seems very strange to look at all of the predecessors' predecessors here. That seems really expensive and it isn't clear why. This at least needs some serious commenting to clarify the algorithm used.

[djasper]

lib/CodeGen/MachineBlockPlacement.cpp

394

Addressed both concerns.

[djasper]

Ping?

[chandlerc]

I'm fine for this to go in behind the flag. It makes the code strictly better.

However, looking at this and thinking about it is really confirming for me that this isn't quite the correct approach. Here are my thoughts, mostly for reference going forward:

Currently, the code is working to select a definite successor to lay out next in the chain. But some of the time, we don't want to do that because there is a non-definite successor that doesn't have a CFG conflict and is small. I feel like it would be better to phrase this whole thing from the perspective of actually *outlining*. Rather than returning a successor early, I wonder if it would work better to *skip* successors which are non-small and optional.

I've tried to think through how this would be implemented, and sadly it doesn't seem straight forward. I really feel like we're struggling with a much more deeply flawed design here and that is why nothing seems to work elegantly.

lib/CodeGen/MachineBlockPlacement.cpp

399–414

I feel like this code would be much easier to read as a lambda predicate.

[djasper]

Turned into lambda and committed as r232802.

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<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);
+
 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.
for (MachineBasicBlock *Succ : BB->successors()) {
 
     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)
+        UnavoidableBlocks.count(Succ) > 0) {
+      for (MachineBasicBlock *Pred : Succ->predecessors()) {
+        if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) ||
+            BlockToChain[Pred] == &Chain)
+          continue;
+        for (MachineBasicBlock *PredPred : Pred->predecessors()) {
+          if (BlockToChain[PredPred] == &Chain &&
+              Pred->size() < OutlineOptionalThreshold)
+            return Pred;
+        }
+      }
       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;
       }
 
       // Make sure that a hot successor doesn't have a globally more
       // important predecessor.
       BlockFrequency CandidateEdgeFreq =
           MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl();
       bool BadCFGConflict = false;
       for (MachineBasicBlock *Pred : Succ->predecessors()) {
         if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) ||
             BlockToChain[Pred] == &Chain)
           continue;
         BlockFrequency PredEdgeFreq =
             MBFI->getBlockFreq(Pred) * MBPI->getEdgeProbability(Pred, Succ);
         if (PredEdgeFreq >= CandidateEdgeFreq) {
           BadCFGConflict = true;
           break;

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) {
+define void @foo(i32 %t1, i32 %t2, i32 %t3) {
 ; 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 a
+; CHECK: callq a
+; CHECK: callq a
 ; CHECK: callq b
 ; CHECK: callq c
 ; CHECK: callq d
+; CHECK: callq e
+; CHECK: callq f
 ;
 ; CHECK-OUTLINE-LABEL: foo:
 ; CHECK-OUTLINE: callq b
 ; CHECK-OUTLINE: callq c
 ; CHECK-OUTLINE: callq d
+; CHECK-OUTLINE: callq e
+; CHECK-OUTLINE: callq f
+; CHECK-OUTLINE: callq a
+; CHECK-OUTLINE: callq a
+; CHECK-OUTLINE: callq a
 ; 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()
+  call void @a()
+  call void @a()
+  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()
+  br label %shortbranch
+
+shortbranch:
+  %cmp3 = icmp eq i32 %t3, 0
+  br i1 %cmp3, label %if.then3, label %if.end3
+
+if.then3:
+  call void @e()
+  br label %if.end3
+
+if.end3:
+  call void @f()
   ret void
 }
 
 declare void @a()
 declare void @b()
 declare void @c()
 declare void @d()
+declare void @e()
+declare void @f()
 
 !1 = !{!"branch_weights", i32 64, i32 4}