From b197d5b0a00747c0b6d8f82a275f871f3c9240c2 Mon Sep 17 00:00:00 2001
From: Dehao Chen <dehao@google.com>
Date: Thu, 23 Mar 2017 23:28:09 +0000
Subject: [PATCH] Fix trellis layout to avoid mis-identify triangle.

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.

Reviewers: davidxl, iteratee

Reviewed By: iteratee

Subscribers: nemanjai, llvm-commits

Differential Revision: https://reviews.llvm.org/D31310

llvm-svn: 298661
---
 llvm/lib/CodeGen/MachineBlockPlacement.cpp   |  7 +++-
 llvm/test/CodeGen/PowerPC/tail-dup-layout.ll | 48 ++++++++++++++++++++++++++++
 2 files changed, 54 insertions(+), 1 deletion(-)

diff --git a/llvm/lib/CodeGen/MachineBlockPlacement.cpp b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
index d3bf95b..de0b572 100644
--- a/llvm/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/llvm/lib/CodeGen/MachineBlockPlacement.cpp
@@ -839,8 +839,13 @@ bool MachineBlockPlacement::isTrellis(
     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])
diff --git a/llvm/test/CodeGen/PowerPC/tail-dup-layout.ll b/llvm/test/CodeGen/PowerPC/tail-dup-layout.ll
index 12fce24..c9b5bf8 100644
--- a/llvm/test/CodeGen/PowerPC/tail-dup-layout.ll
+++ b/llvm/test/CodeGen/PowerPC/tail-dup-layout.ll
@@ -474,6 +474,51 @@ 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()
@@ -492,3 +537,6 @@ declare void @j()
 !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}
-- 
2.7.4