Fix trellis layout to avoid mis-identify triangle.

[danielcdh]

Summary

For the following CFG:

A->B
B->C
A->C

If there is another edge B->D, then ABC should not be considered as triangle.

[iteratee]

Thanks for catching this. The test case can stay, but I think the fix needs to go in a different spot. Good work.

lib/CodeGen/MachineBlockPlacement.cpp

842

I appreciate the test case, but I think the logic needs to go here.

if (Successors.count(SuccPred)) {
  // Make sure that it is actually a triangle.
  for (MachineBasicBlock *CheckSucc : SuccPred.successors())
    if (!Successors.contains(CheckSucc))
      return false;
  continue;
}

test/CodeGen/PowerPC/tail-dup-layout.ll

477

Change the comment to reflect the fact that we shouldn't mis-identify triangle trellises if it's not really a triangle.

[danielcdh]

update

[iteratee]

Please re-write description before submitting.

lib/CodeGen/MachineBlockPlacement.cpp

SmallPtrSet<const MachineBasicBlock *, 2> Successors(BB->succ_begin(),
                                                        BB->succ_end());
   // To avoid reviewing the same predecessors twice.
   SmallPtrSet<const MachineBasicBlock *, 8> SeenPreds;
 
   for (MachineBasicBlock *Succ : ViableSuccs) {
     int PredCount = 0;
     for (auto SuccPred : Succ->predecessors()) {
       // Allow triangle successors, but don't count them.
       if (Successors.count(SuccPred))
         continue;
       const BlockChain *PredChain = BlockToChain[SuccPred];
       if (SuccPred == BB || (BlockFilter && !BlockFilter->count(SuccPred)) ||
           PredChain == &Chain || PredChain == BlockToChain[Succ])
         continue;
       ++PredCount;
       // Perform the successor check only once.
       if (!SeenPreds.insert(SuccPred).second)
MachineBlockPlacement::getBestTrellisSuccessor(
   if (BestA.Src != BB) {
     // If we have a trellis, and BB doesn't have the best fallthrough edges,
     // we shouldn't choose any successor. We've already looked and there's a
     // better fallthrough edge for all the successors.
     DEBUG(dbgs() << "Trellis, but not one of the chosen edges.\n");
     return Result;
   }
 
+  bool ComputeBestB = true;
   // Did we pick the triangle edge? If tail-duplication is profitable, do
   // that instead. Otherwise merge the triangle edge now while we know it is
   // optimal.
   if (BestA.Dest == BestB.Src) {
     // The edges are BB->Succ1->Succ2, and we're looking to see if BB->Succ2
     // would be better.
     MachineBasicBlock *Succ1 = BestA.Dest;
     MachineBasicBlock *Succ2 = BestB.Dest;
     // Check to see if tail-duplication would be profitable.
     if (TailDupPlacement && shouldTailDuplicate(Succ2) &&
         canTailDuplicateUnplacedPreds(BB, Succ2, Chain, BlockFilter) &&
         isProfitableToTailDup(BB, Succ2, MBPI->getEdgeProbability(BB, Succ1),
                               Chain, BlockFilter)) {
       DEBUG(BranchProbability Succ2Prob = getAdjustedProbability(
                 MBPI->getEdgeProbability(BB, Succ2), AdjustedSumProb);
             dbgs() << "    Selected: " << getBlockName(Succ2)
                    << ", probability: " << Succ2Prob << " (Tail Duplicate)\n");
       Result.BB = Succ2;
       Result.ShouldTailDup = true;
       return Result;
     }
+    // If any of the BestA.Dest's successor is outside of the Trellis, we should
+    // not use BestB as it may not be optimal.
+    for (MachineBasicBlock *Succ : BestA.Dest->successors())
+      if (!Successors.count(Succ)) {
+        ComputeBestB = false;
+        break;
+      }
   }
+  if (ComputeBestB)
     // We have already computed the optimal edge for the other side of the
     // trellis.
     ComputedEdges[BestB.Src] = { BestB.Dest, false };
 
   auto TrellisSucc = BestA.Dest;
   DEBUG(BranchProbability SuccProb = getAdjustedProbability(
             MBPI->getEdgeProbability(BB, TrellisSucc), AdjustedSumProb);
         dbgs() << "    Selected: " << getBlockName(TrellisSucc)
                << ", probability: " << SuccProb << " (Trellis)\n");
   Result.BB = TrellisSucc;
   return Result;

test/CodeGen/PowerPC/tail-dup-layout.ll

ret1:
   br label %ret
 ret2:
   call void @b()
   br label %ret
 ret:
   ret void
 }
 
+; Verify that in the triangular trellis case, if there is hot successor
+; outside of trellis, we should be able to connect them by not connecting
+; the triagular edges.
+; CHECK-LABEL: trellis_triangle
+; CHECK: # %entry
+; CHECK: # %b
+; CHECK: # %d
+; CHECK: # %ret
+; CHECK: # %c
+; CHECK: # %e
+define void @trellis_no_triangle(i32 %tag) {
+entry:
+  br label %a
+a:
+  call void @a()
+  call void @a()
+  %tagbits.a = and i32 %tag, 3
+  %tagbits.a.eq0 = icmp eq i32 %tagbits.a, 0
+  br i1 %tagbits.a.eq0, label %b, label %c, !prof !8 ; 98 to 2
+b:
+  call void @b()
+  call void @b()
+  %tagbits.b = and i32 %tag, 12
+  %tagbits.b.eq1 = icmp eq i32 %tagbits.b, 8
+  br i1 %tagbits.b.eq1, label %d, label %e, !prof !9 ; 97 to 1
+d:
+  call void @d()
+  call void @d()
+  %tagbits.d = and i32 %tag, 48
+  %tagbits.d.eq1 = icmp eq i32 %tagbits.d, 32
+  br i1 %tagbits.d.eq1, label %ret, label %e, !prof !10 ; 96 to 2
+c:
+  call void @c()
+  call void @c()
+  %tagbits.c = and i32 %tag, 12
+  %tagbits.c.eq0 = icmp eq i32 %tagbits.c, 0
+  br i1 %tagbits.c.eq0, label %d, label %e, !prof !2 ; 1 to 1
+e:
+  call void @e()
+  call void @e()
+  br label %ret
+ret:
+  call void @f()
+  ret void
+}
+
 declare void @a()
 declare void @b()
 declare void @c()
 declare void @d()
 declare void @e()
 declare void @f()
 declare void @g()
 declare void @h()
 declare void @i()
 declare void @j()
 
 !1 = !{!"branch_weights", i32 5, i32 3}
 !2 = !{!"branch_weights", i32 50, i32 50}
 !3 = !{!"branch_weights", i32 6, i32 4}
 !4 = !{!"branch_weights", i32 7, i32 2}
 !5 = !{!"branch_weights", i32 2, i32 8}
 !6 = !{!"branch_weights", i32 3, i32 4}
 !7 = !{!"branch_weights", i32 4, i32 2}
+!8 = !{!"branch_weights", i32 98, i32 2}
+!9 = !{!"branch_weights", i32 97, i32 1}
+!10 = !{!"branch_weights", i32 96, i32 2}