From 846a14340c4c699d55b42e73e2336490c9255f11 Mon Sep 17 00:00:00 2001
From: "Duncan P. N. Exon Smith" <dexonsmith@apple.com>
Date: Tue, 22 Apr 2014 03:31:53 +0000
Subject: [PATCH] blockfreq: Skip irreducible backedges inside functions

The branch that skips irreducible backedges was only active when
propagating mass at the top-level.  In particular, when propagating mass
through a loop recognized by `LoopInfo` with irreducible control flow
inside, irreducible backedges would not be skipped.

Not sure where that idea came from, but the result was that mass was
lost until after loop exit.  Added a testcase that covers this case.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206860 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/BlockFrequencyInfoImpl.cpp       |  2 +-
 .../BlockFrequencyInfo/irreducible.ll         | 31 +++++++++++++++++++
 2 files changed, 32 insertions(+), 1 deletion(-)

diff --git a/lib/Analysis/BlockFrequencyInfoImpl.cpp b/lib/Analysis/BlockFrequencyInfoImpl.cpp
index b5532fcea1d..29a4117c130 100644
--- a/lib/Analysis/BlockFrequencyInfoImpl.cpp
+++ b/lib/Analysis/BlockFrequencyInfoImpl.cpp
@@ -687,7 +687,7 @@ void BlockFrequencyInfoImplBase::addToDist(Distribution &Dist,
     return;
   }
 
-  if (!LoopHead.isValid() && Resolved < Pred) {
+  if (Resolved < Pred) {
     // Irreducible backedge.  Skip this edge in the distribution.
     DEBUG(debugSuccessor("skipped ", Resolved));
     return;
diff --git a/test/Analysis/BlockFrequencyInfo/irreducible.ll b/test/Analysis/BlockFrequencyInfo/irreducible.ll
index 46a2958700e..f0737fb48d5 100644
--- a/test/Analysis/BlockFrequencyInfo/irreducible.ll
+++ b/test/Analysis/BlockFrequencyInfo/irreducible.ll
@@ -195,3 +195,34 @@ declare i32 @choose(i32)
 
 !2 = metadata !{metadata !"branch_weights", i32 3, i32 1}
 !3 = metadata !{metadata !"branch_weights", i32 2, i32 2, i32 2}
+
+; A reducible loop with irreducible control flow inside should still have
+; correct exit frequency.
+;
+; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_around_irreducible':
+; CHECK-NEXT: block-frequency-info: loop_around_irreducible
+define void @loop_around_irreducible(i1 %x) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  br label %loop
+
+; CHECK-NEXT: loop: float = [[HEAD:[0-9.]+]], int = [[HEADINT:[0-9]+]]
+loop:
+  br i1 %x, label %left, label %right
+
+; CHECK-NEXT: left:
+left:
+  br i1 %x, label %right, label %loop.end
+
+; CHECK-NEXT: right:
+right:
+  br i1 %x, label %left, label %loop.end
+
+; CHECK-NEXT: loop.end: float = [[HEAD]], int = [[HEADINT]]
+loop.end:
+  br i1 %x, label %loop, label %exit
+
+; CHECK-NEXT: float = 1.0, int = [[ENTRY]]
+exit:
+  ret void
+}
-- 
2.34.1