[MBP] Avoid placing random blocks between loop preheader and header

[reames]

Summary

If we have a loop with a rarely taken path, we will prune that from the blocks which get added as part of the loop chain. The problem is that we weren't then recognizing the loop chain as schedulable when considering the preheader when forming the function chain. We'd then fall to various non-predecessors before finally scheduling the loop chain (as if the CFG was unnatural.) The net result was that there could be lots of garbage between a loop preheader and the loop, even though we could have directly fallen into the loop. It also meant we separated hot code with regions of colder code.

The particular reason for the rejection of the loop chain was that we were scanning predecessor of the header, seeing the backedge, believing that was a globally more important predecessor (true), but forgetting to account for the fact the backedge precessor was already part of the existing loop chain (oops!.

[reames]

lib/CodeGen/MachineBlockPlacement.cpp

210

As a side note, the name of this variable is highly misleading. When scheduling function chains, this is used to track unscheduled predecessors outside of any loop. Once this change is in, I'd like to rename this to something more meaningful. Any suggestions?

[chandlerc]

Gah, excellent bug fix. That makes perfect sense to me, and thanks!

lib/CodeGen/MachineBlockPlacement.cpp

210

No real idea. =/ I agree, it was bad when it started and it has gotten worse.

[congh]

Great fix! Then we can ignore any predecessors in the same chain and treat the chain as a single node, in which case the chain should always be a loop chain.

lib/CodeGen/MachineBlockPlacement.cpp

210

Maybe ChainPredecessors? But in loops this may also be misleading. If we treat the function as a loop body, maybe ChainPredecessorsInLoop is better?

[davidxl]

LGTM.

test/CodeGen/X86/mbp-false-cfg-break.ll

9

There does not seem to be a guarantee about the order between rare and rare1. How about using CHECK-NOT to make sure cold blocks are intermixed with hot ones?

[reames]

lib/CodeGen/MachineBlockPlacement.cpp

210

How does UnscheduledPredecessors sound? I'm going for something that describes how the value changes over time and what that actually means.

[congh]

lib/CodeGen/MachineBlockPlacement.cpp

210

Sounds good!

[davidxl]

Or perhaps UnscheduledPredInLoop ?

David

[reames]

I'm am specifically trying to avoid any mention of loops because the
variable is used when not in any loop.

Philip

[reames]

Landed in 262571

lib/CodeGen/MachineBlockPlacement.cpp

for (MachineBasicBlock *MBB : *this)
       MBB->dump();
   }
 #endif // NDEBUG
 
   /// \brief Count of predecessors within the loop currently being processed.
   ///
   /// This count is updated at each loop we process to represent the number of
   /// in-loop predecessors of this chain.
   unsigned LoopPredecessors;
 };
 }
 
 namespace {
 class MachineBlockPlacement : public MachineFunctionPass {
   /// \brief A typedef for a block filter set.
   typedef SmallPtrSet<MachineBasicBlock *, 16> BlockFilterSet;
 
if (SuccChain.LoopPredecessors != 0) {
 
       // Make sure that a hot successor doesn't have a globally more
       // important predecessor.
       auto RealSuccProb = MBPI->getEdgeProbability(BB, Succ);
       BlockFrequency CandidateEdgeFreq =
           MBFI->getBlockFreq(BB) * RealSuccProb * HotProb.getCompl();
       bool BadCFGConflict = false;
       for (MachineBasicBlock *Pred : Succ->predecessors()) {
-        if (Pred == Succ || (BlockFilter && !BlockFilter->count(Pred)) ||
+        if (Pred == Succ || BlockToChain[Pred] == &SuccChain ||
+            (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/mbp-false-cfg-break.ll

+; RUN: llc < %s -march=x86-64 | FileCheck %s
+
+define void @test(i1 %cnd) !prof !{!"function_entry_count", i64 1024} {
+; CHECK-LABEL: @test
+; Using the assembly comments to indicate block order..
+; CHECK: # %loop
+; CHECK: # %backedge
+; CHECK: # %exit
+; CHECK: # %rare
+; CHECK: # %rare.1
+
+  br i1 undef, label %rare.1, label %preheader, !prof !{!"branch_weights", i32 0, i32 1000}
+rare.1:
+  call void @foo()
+  br label %preheader
+
+preheader:
+  br label %loop
+
+loop:
+  %iv = phi i32 [0, %preheader], [%iv.next, %backedge]
+  call void @foo()
+  br i1 %cnd, label %backedge, label %rare, !prof !{!"branch_weights", i32 1000000, i32 1}
+rare:
+  call void @foo()
+  br label %backedge
+backedge:
+  call void @foo()
+  %iv.next = add i32 %iv, 1
+  %cmp = icmp eq i32 %iv.next, 200
+  br i1 %cmp, label %loop, label %exit, !prof !{!"branch_weights", i32 1000, i32 1}
+
+exit:
+  ret void
+
+}
+
+
+declare void @foo()