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–846

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))
+      if (Successors.count(SuccPred)) {
+        // Make sure that it is actually a triangle.
+        for (MachineBasicBlock *CheckSucc : SuccPred->successors())
+          if (!Successors.count(CheckSucc))
+            return false;
         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)
         continue;

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

ret1:
   br label %ret
 ret2:
   call void @b()
   br label %ret
 ret:
   ret void
 }
 
+; Verify that we did not mis-identify triangle trellises if it is not
+; really a triangle.
+; CHECK-LABEL: trellis_no_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}