Reapply "blockfreq: Rewrite BlockFrequencyInfoImpl"

This reverts commit r206556, effectively reapplying commit r206548 and
its fixups in r206549 and r206550.

In an intervening commit I've added target triples to the tests that
were failing remotely [1] (but passing locally).  I'm hoping the mystery
is solved?  I'll revert this again if the tests are still failing
remotely.

[1]: http://bb.pgr.jp/builders/ninja-x64-msvc-RA-centos6/builds/1816

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206622 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 548 insertions, 28 deletions

diff --git a/test/Analysis/BlockFrequencyInfo/bad_input.ll b/test/Analysis/BlockFrequencyInfo/bad_input.ll
new file mode 100644
index 0000000000..bcdc1e6f0b
--- /dev/null
+++ b/test/Analysis/BlockFrequencyInfo/bad_input.ll
@@ -0,0 +1,50 @@
+; RUN: opt < %s -analyze -block-freq | FileCheck %s
+
+declare void @g(i32 %x)
+
+; CHECK-LABEL: Printing analysis {{.*}} for function 'branch_weight_0':
+; CHECK-NEXT: block-frequency-info: branch_weight_0
+define void @branch_weight_0(i32 %a) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  br label %for.body
+
+; Check that we get 1,4 instead of 0,3.
+; CHECK-NEXT: for.body: float = 4.0,
+for.body:
+  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  call void @g(i32 %i)
+  %inc = add i32 %i, 1
+  %cmp = icmp ugt i32 %inc, %a
+  br i1 %cmp, label %for.end, label %for.body, !prof !0
+
+; CHECK-NEXT: for.end: float = 1.0, int = [[ENTRY]]
+for.end:
+  ret void
+}
+
+!0 = metadata !{metadata !"branch_weights", i32 0, i32 3}
+
+; CHECK-LABEL: Printing analysis {{.*}} for function 'infinite_loop'
+; CHECK-NEXT: block-frequency-info: infinite_loop
+define void @infinite_loop(i1 %x) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  br i1 %x, label %for.body, label %for.end, !prof !1
+
+; Check that the loop scale maxes out at 4096, giving 2048 here.
+; CHECK-NEXT: for.body: float = 2048.0,
+for.body:
+  %i = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  call void @g(i32 %i)
+  %inc = add i32 %i, 1
+  br label %for.body
+
+; Check that the exit weight is half of entry, since half is lost in the
+; infinite loop above.
+; CHECK-NEXT: for.end: float = 0.5,
+for.end:
+  ret void
+}
+
+!1 = metadata !{metadata !"branch_weights", i32 1, i32 1}
diff --git a/test/Analysis/BlockFrequencyInfo/basic.ll b/test/Analysis/BlockFrequencyInfo/basic.ll
index ce29fb5ce1..006e6ab4d7 100644
--- a/test/Analysis/BlockFrequencyInfo/basic.ll
+++ b/test/Analysis/BlockFrequencyInfo/basic.ll
@@ -1,13 +1,14 @@
 ; RUN: opt < %s -analyze -block-freq | FileCheck %s
 
 define i32 @test1(i32 %i, i32* %a) {
-; CHECK: Printing analysis {{.*}} for function 'test1'
-; CHECK: entry = 1.0
+; CHECK-LABEL: Printing analysis {{.*}} for function 'test1':
+; CHECK-NEXT: block-frequency-info: test1
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   br label %body
 
 ; Loop backedges are weighted and thus their bodies have a greater frequency.
-; CHECK: body = 32.0
+; CHECK-NEXT: body: float = 32.0,
 body:
   %iv = phi i32 [ 0, %entry ], [ %next, %body ]
   %base = phi i32 [ 0, %entry ], [ %sum, %body ]
@@ -18,29 +19,29 @@ body:
   %exitcond = icmp eq i32 %next, %i
   br i1 %exitcond, label %exit, label %body
 
-; CHECK: exit = 1.0
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 exit:
   ret i32 %sum
 }
 
 define i32 @test2(i32 %i, i32 %a, i32 %b) {
-; CHECK: Printing analysis {{.*}} for function 'test2'
-; CHECK: entry = 1.0
+; CHECK-LABEL: Printing analysis {{.*}} for function 'test2':
+; CHECK-NEXT: block-frequency-info: test2
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   %cond = icmp ult i32 %i, 42
   br i1 %cond, label %then, label %else, !prof !0
 
 ; The 'then' branch is predicted more likely via branch weight metadata.
-; CHECK: then = 0.94116
+; CHECK-NEXT: then: float = 0.9411{{[0-9]*}},
 then:
   br label %exit
 
-; CHECK: else = 0.05877
+; CHECK-NEXT: else: float = 0.05882{{[0-9]*}},
 else:
   br label %exit
 
-; FIXME: It may be a bug that we don't sum back to 1.0.
-; CHECK: exit = 0.99993
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
   ret i32 %result
@@ -49,37 +50,37 @@ exit:
 !0 = metadata !{metadata !"branch_weights", i32 64, i32 4}
 
 define i32 @test3(i32 %i, i32 %a, i32 %b, i32 %c, i32 %d, i32 %e) {
-; CHECK: Printing analysis {{.*}} for function 'test3'
-; CHECK: entry = 1.0
+; CHECK-LABEL: Printing analysis {{.*}} for function 'test3':
+; CHECK-NEXT: block-frequency-info: test3
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   switch i32 %i, label %case_a [ i32 1, label %case_b
                                  i32 2, label %case_c
                                  i32 3, label %case_d
                                  i32 4, label %case_e ], !prof !1
 
-; CHECK: case_a = 0.04998
+; CHECK-NEXT: case_a: float = 0.05,
 case_a:
   br label %exit
 
-; CHECK: case_b = 0.04998
+; CHECK-NEXT: case_b: float = 0.05,
 case_b:
   br label %exit
 
 ; The 'case_c' branch is predicted more likely via branch weight metadata.
-; CHECK: case_c = 0.79998
+; CHECK-NEXT: case_c: float = 0.8,
 case_c:
   br label %exit
 
-; CHECK: case_d = 0.04998
+; CHECK-NEXT: case_d: float = 0.05,
 case_d:
   br label %exit
 
-; CHECK: case_e = 0.04998
+; CHECK-NEXT: case_e: float = 0.05,
 case_e:
   br label %exit
 
-; FIXME: It may be a bug that we don't sum back to 1.0.
-; CHECK: exit = 0.99993
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
 exit:
   %result = phi i32 [ %a, %case_a ],
                     [ %b, %case_b ],
@@ -91,44 +92,50 @@ exit:
 
 !1 = metadata !{metadata !"branch_weights", i32 4, i32 4, i32 64, i32 4, i32 4}
 
-; CHECK: Printing analysis {{.*}} for function 'nested_loops'
-; CHECK: entry = 1.0
-; This test doesn't seem to be assigning sensible frequencies to nested loops.
 define void @nested_loops(i32 %a) {
+; CHECK-LABEL: Printing analysis {{.*}} for function 'nested_loops':
+; CHECK-NEXT: block-frequency-info: nested_loops
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   br label %for.cond1.preheader
 
+; CHECK-NEXT: for.cond1.preheader: float = 4001.0,
 for.cond1.preheader:
   %x.024 = phi i32 [ 0, %entry ], [ %inc12, %for.inc11 ]
   br label %for.cond4.preheader
 
+; CHECK-NEXT: for.cond4.preheader: float = 16008001.0,
 for.cond4.preheader:
   %y.023 = phi i32 [ 0, %for.cond1.preheader ], [ %inc9, %for.inc8 ]
   %add = add i32 %y.023, %x.024
   br label %for.body6
 
+; CHECK-NEXT: for.body6: float = 64048012001.0,
 for.body6:
   %z.022 = phi i32 [ 0, %for.cond4.preheader ], [ %inc, %for.body6 ]
   %add7 = add i32 %add, %z.022
-  tail call void @g(i32 %add7) #2
+  tail call void @g(i32 %add7)
   %inc = add i32 %z.022, 1
   %cmp5 = icmp ugt i32 %inc, %a
   br i1 %cmp5, label %for.inc8, label %for.body6, !prof !2
 
+; CHECK-NEXT: for.inc8: float = 16008001.0,
 for.inc8:
   %inc9 = add i32 %y.023, 1
   %cmp2 = icmp ugt i32 %inc9, %a
   br i1 %cmp2, label %for.inc11, label %for.cond4.preheader, !prof !2
 
+; CHECK-NEXT: for.inc11: float = 4001.0,
 for.inc11:
   %inc12 = add i32 %x.024, 1
   %cmp = icmp ugt i32 %inc12, %a
   br i1 %cmp, label %for.end13, label %for.cond1.preheader, !prof !2
 
+; CHECK-NEXT: for.end13: float = 1.0, int = [[ENTRY]]
 for.end13:
   ret void
 }
 
-declare void @g(i32) #1
+declare void @g(i32)
 
 !2 = metadata !{metadata !"branch_weights", i32 1, i32 4000}
diff --git a/test/Analysis/BlockFrequencyInfo/double_exit.ll b/test/Analysis/BlockFrequencyInfo/double_exit.ll
new file mode 100644
index 0000000000..2fe617c9f5
--- /dev/null
+++ b/test/Analysis/BlockFrequencyInfo/double_exit.ll
@@ -0,0 +1,165 @@
+; RUN: opt < %s -analyze -block-freq | FileCheck %s
+
+; CHECK-LABEL: Printing analysis {{.*}} for function 'double_exit':
+; CHECK-NEXT: block-frequency-info: double_exit
+define i32 @double_exit(i32 %N) {
+; Mass = 1
+; Frequency = 1
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  br label %outer
+
+; Mass = 1
+; Backedge mass = 1/3, exit mass = 2/3
+; Loop scale = 3/2
+; Psuedo-edges = exit
+; Psuedo-mass = 1
+; Frequency = 1*3/2*1 = 3/2
+; CHECK-NEXT: outer: float = 1.5,
+outer:
+  %I.0 = phi i32 [ 0, %entry ], [ %inc6, %outer.inc ]
+  %Return.0 = phi i32 [ 0, %entry ], [ %Return.1, %outer.inc ]
+  %cmp = icmp slt i32 %I.0, %N
+  br i1 %cmp, label %inner, label %exit, !prof !2 ; 2:1
+
+; Mass = 1
+; Backedge mass = 3/5, exit mass = 2/5
+; Loop scale = 5/2
+; Pseudo-edges = outer.inc @ 1/5, exit @ 1/5
+; Pseudo-mass = 2/3
+; Frequency = 3/2*1*5/2*2/3 = 5/2
+; CHECK-NEXT: inner: float = 2.5,
+inner:
+  %Return.1 = phi i32 [ %Return.0, %outer ], [ %call4, %inner.inc ]
+  %J.0 = phi i32 [ %I.0, %outer ], [ %inc, %inner.inc ]
+  %cmp2 = icmp slt i32 %J.0, %N
+  br i1 %cmp2, label %inner.body, label %outer.inc, !prof !1 ; 4:1
+
+; Mass = 4/5
+; Frequency = 5/2*4/5 = 2
+; CHECK-NEXT: inner.body: float = 2.0,
+inner.body:
+  %call = call i32 @c2(i32 %I.0, i32 %J.0)
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %exit, label %inner.inc, !prof !0 ; 3:1
+
+; Mass = 3/5
+; Frequency = 5/2*3/5 = 3/2
+; CHECK-NEXT: inner.inc: float = 1.5,
+inner.inc:
+  %call4 = call i32 @logic2(i32 %Return.1, i32 %I.0, i32 %J.0)
+  %inc = add nsw i32 %J.0, 1
+  br label %inner
+
+; Mass = 1/3
+; Frequency = 3/2*1/3 = 1/2
+; CHECK-NEXT: outer.inc: float = 0.5,
+outer.inc:
+  %inc6 = add nsw i32 %I.0, 1
+  br label %outer
+
+; Mass = 1
+; Frequency = 1
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
+exit:
+  %Return.2 = phi i32 [ %Return.1, %inner.body ], [ %Return.0, %outer ]
+  ret i32 %Return.2
+}
+
+!0 = metadata !{metadata !"branch_weights", i32 1, i32 3}
+!1 = metadata !{metadata !"branch_weights", i32 4, i32 1}
+!2 = metadata !{metadata !"branch_weights", i32 2, i32 1}
+
+declare i32 @c2(i32, i32)
+declare i32 @logic2(i32, i32, i32)
+
+; CHECK-LABEL: Printing analysis {{.*}} for function 'double_exit_in_loop':
+; CHECK-NEXT: block-frequency-info: double_exit_in_loop
+define i32 @double_exit_in_loop(i32 %N) {
+; Mass = 1
+; Frequency = 1
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  br label %outer
+
+; Mass = 1
+; Backedge mass = 1/2, exit mass = 1/2
+; Loop scale = 2
+; Pseudo-edges = exit
+; Psuedo-mass = 1
+; Frequency = 1*2*1 = 2
+; CHECK-NEXT: outer: float = 2.0,
+outer:
+  %I.0 = phi i32 [ 0, %entry ], [ %inc12, %outer.inc ]
+  %Return.0 = phi i32 [ 0, %entry ], [ %Return.3, %outer.inc ]
+  %cmp = icmp slt i32 %I.0, %N
+  br i1 %cmp, label %middle, label %exit, !prof !3 ; 1:1
+
+; Mass = 1
+; Backedge mass = 1/3, exit mass = 2/3
+; Loop scale = 3/2
+; Psuedo-edges = outer.inc
+; Psuedo-mass = 1/2
+; Frequency = 2*1*3/2*1/2 = 3/2
+; CHECK-NEXT: middle: float = 1.5,
+middle:
+  %J.0 = phi i32 [ %I.0, %outer ], [ %inc9, %middle.inc ]
+  %Return.1 = phi i32 [ %Return.0, %outer ], [ %Return.2, %middle.inc ]
+  %cmp2 = icmp slt i32 %J.0, %N
+  br i1 %cmp2, label %inner, label %outer.inc, !prof !2 ; 2:1
+
+; Mass = 1
+; Backedge mass = 3/5, exit mass = 2/5
+; Loop scale = 5/2
+; Pseudo-edges = middle.inc @ 1/5, outer.inc @ 1/5
+; Pseudo-mass = 2/3
+; Frequency = 3/2*1*5/2*2/3 = 5/2
+; CHECK-NEXT: inner: float = 2.5,
+inner:
+  %Return.2 = phi i32 [ %Return.1, %middle ], [ %call7, %inner.inc ]
+  %K.0 = phi i32 [ %J.0, %middle ], [ %inc, %inner.inc ]
+  %cmp5 = icmp slt i32 %K.0, %N
+  br i1 %cmp5, label %inner.body, label %middle.inc, !prof !1 ; 4:1
+
+; Mass = 4/5
+; Frequency = 5/2*4/5 = 2
+; CHECK-NEXT: inner.body: float = 2.0,
+inner.body:
+  %call = call i32 @c3(i32 %I.0, i32 %J.0, i32 %K.0)
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %outer.inc, label %inner.inc, !prof !0 ; 3:1
+
+; Mass = 3/5
+; Frequency = 5/2*3/5 = 3/2
+; CHECK-NEXT: inner.inc: float = 1.5,
+inner.inc:
+  %call7 = call i32 @logic3(i32 %Return.2, i32 %I.0, i32 %J.0, i32 %K.0)
+  %inc = add nsw i32 %K.0, 1
+  br label %inner
+
+; Mass = 1/3
+; Frequency = 3/2*1/3 = 1/2
+; CHECK-NEXT: middle.inc: float = 0.5,
+middle.inc:
+  %inc9 = add nsw i32 %J.0, 1
+  br label %middle
+
+; Mass = 1/2
+; Frequency = 2*1/2 = 1
+; CHECK-NEXT: outer.inc: float = 1.0,
+outer.inc:
+  %Return.3 = phi i32 [ %Return.2, %inner.body ], [ %Return.1, %middle ]
+  %inc12 = add nsw i32 %I.0, 1
+  br label %outer
+
+; Mass = 1
+; Frequency = 1
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
+exit:
+  ret i32 %Return.0
+}
+
+!3 = metadata !{metadata !"branch_weights", i32 1, i32 1}
+
+declare i32 @c3(i32, i32, i32)
+declare i32 @logic3(i32, i32, i32, i32)
diff --git a/test/Analysis/BlockFrequencyInfo/irreducible.ll b/test/Analysis/BlockFrequencyInfo/irreducible.ll
new file mode 100644
index 0000000000..46a2958700
--- /dev/null
+++ b/test/Analysis/BlockFrequencyInfo/irreducible.ll
@@ -0,0 +1,197 @@
+; RUN: opt < %s -analyze -block-freq | FileCheck %s
+
+; A loop with multiple exits should be handled correctly.
+;
+; CHECK-LABEL: Printing analysis {{.*}} for function 'multiexit':
+; CHECK-NEXT: block-frequency-info: multiexit
+define void @multiexit(i32 %a) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  br label %loop.1
+
+; CHECK-NEXT: loop.1: float = 1.333{{3*}},
+loop.1:
+  %i = phi i32 [ 0, %entry ], [ %inc.2, %loop.2 ]
+  call void @f(i32 %i)
+  %inc.1 = add i32 %i, 1
+  %cmp.1 = icmp ugt i32 %inc.1, %a
+  br i1 %cmp.1, label %exit.1, label %loop.2, !prof !0
+
+; CHECK-NEXT: loop.2: float = 0.666{{6*7}},
+loop.2:
+  call void @g(i32 %inc.1)
+  %inc.2 = add i32 %inc.1, 1
+  %cmp.2 = icmp ugt i32 %inc.2, %a
+  br i1 %cmp.2, label %exit.2, label %loop.1, !prof !1
+
+; CHECK-NEXT: exit.1: float = 0.666{{6*7}},
+exit.1:
+  call void @h(i32 %inc.1)
+  br label %return
+
+; CHECK-NEXT: exit.2: float = 0.333{{3*}},
+exit.2:
+  call void @i(i32 %inc.2)
+  br label %return
+
+; CHECK-NEXT: return: float = 1.0, int = [[ENTRY]]
+return:
+  ret void
+}
+
+declare void @f(i32 %x)
+declare void @g(i32 %x)
+declare void @h(i32 %x)
+declare void @i(i32 %x)
+
+!0 = metadata !{metadata !"branch_weights", i32 3, i32 3}
+!1 = metadata !{metadata !"branch_weights", i32 5, i32 5}
+
+; The current BlockFrequencyInfo algorithm doesn't handle multiple entrances
+; into a loop very well.  The frequencies assigned to blocks in the loop are
+; predictable (and not absurd), but also not correct and therefore not worth
+; testing.
+;
+; There are two testcases below.
+;
+; For each testcase, I use a CHECK-NEXT/NOT combo like an XFAIL with the
+; granularity of a single check.  If/when this behaviour is fixed, we'll know
+; about it, and the test should be updated.
+;
+; Testcase #1
+; ===========
+;
+; In this case c1 and c2 should have frequencies of 15/7 and 13/7,
+; respectively.  To calculate this, consider assigning 1.0 to entry, and
+; distributing frequency iteratively (to infinity).  At the first iteration,
+; entry gives 3/4 to c1 and 1/4 to c2.  At every step after, c1 and c2 give 3/4
+; of what they have to each other.  Somehow, all of it comes out to exit.
+;
+;       c1 = 3/4 + 1/4*3/4 + 3/4*3^2/4^2 + 1/4*3^3/4^3 + 3/4*3^3/4^3 + ...
+;       c2 = 1/4 + 3/4*3/4 + 1/4*3^2/4^2 + 3/4*3^3/4^3 + 1/4*3^3/4^3 + ...
+;
+; Simplify by splitting up the odd and even terms of the series and taking out
+; factors so that the infite series matches:
+;
+;       c1 =  3/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
+;          +  3/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
+;       c2 =  1/4 *(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
+;          +  9/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
+;
+;       c1 = 15/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
+;       c2 = 13/16*(9^0/16^0 + 9^1/16^1 + 9^2/16^2 + ...)
+;
+; Since this geometric series sums to 16/7:
+;
+;       c1 = 15/7
+;       c2 = 13/7
+;
+; If we treat c1 and c2 as members of the same loop, the exit frequency of the
+; loop as a whole is 1/4, so the loop scale should be 4.  Summing c1 and c2
+; gives 28/7, or 4.0, which is nice confirmation of the math above.
+;
+; However, assuming c1 precedes c2 in reverse post-order, the current algorithm
+; returns 3/4 and 13/16, respectively.  LoopInfo ignores edges between loops
+; (and doesn't see any loops here at all), and -block-freq ignores the
+; irreducible edge from c2 to c1.
+;
+; CHECK-LABEL: Printing analysis {{.*}} for function 'multientry':
+; CHECK-NEXT: block-frequency-info: multientry
+define void @multientry(i32 %a) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  %choose = call i32 @choose(i32 %a)
+  %compare = icmp ugt i32 %choose, %a
+  br i1 %compare, label %c1, label %c2, !prof !2
+
+; This is like a single-line XFAIL (see above).
+; CHECK-NEXT: c1:
+; CHECK-NOT: float = 2.142857{{[0-9]*}},
+c1:
+  %i1 = phi i32 [ %a, %entry ], [ %i2.inc, %c2 ]
+  %i1.inc = add i32 %i1, 1
+  %choose1 = call i32 @choose(i32 %i1)
+  %compare1 = icmp ugt i32 %choose1, %a
+  br i1 %compare1, label %c2, label %exit, !prof !2
+
+; This is like a single-line XFAIL (see above).
+; CHECK-NEXT: c2:
+; CHECK-NOT: float = 1.857142{{[0-9]*}},
+c2:
+  %i2 = phi i32 [ %a, %entry ], [ %i1.inc, %c1 ]
+  %i2.inc = add i32 %i2, 1
+  %choose2 = call i32 @choose(i32 %i2)
+  %compare2 = icmp ugt i32 %choose2, %a
+  br i1 %compare2, label %c1, label %exit, !prof !2
+
+; We still shouldn't lose any frequency.
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
+exit:
+  ret void
+}
+
+; Testcase #2
+; ===========
+;
+; In this case c1 and c2 should be treated as equals in a single loop.  The
+; exit frequency is 1/3, so the scaling factor for the loop should be 3.0.  The
+; loop is entered 2/3 of the time, and c1 and c2 split the total loop frequency
+; evenly (1/2), so they should each have frequencies of 1.0 (3.0*2/3*1/2).
+; Another way of computing this result is by assigning 1.0 to entry and showing
+; that c1 and c2 should accumulate frequencies of:
+;
+;       1/3   +   2/9   +   4/27  +   8/81  + ...
+;     2^0/3^1 + 2^1/3^2 + 2^2/3^3 + 2^3/3^4 + ...
+;
+; At the first step, c1 and c2 each get 1/3 of the entry.  At each subsequent
+; step, c1 and c2 each get 1/3 of what's left in c1 and c2 combined.  This
+; infinite series sums to 1.
+;
+; However, assuming c1 precedes c2 in reverse post-order, the current algorithm
+; returns 1/2 and 3/4, respectively.  LoopInfo ignores edges between loops (and
+; treats c1 and c2 as self-loops only), and -block-freq ignores the irreducible
+; edge from c2 to c1.
+;
+; Below I use a CHECK-NEXT/NOT combo like an XFAIL with the granularity of a
+; single check.  If/when this behaviour is fixed, we'll know about it, and the
+; test should be updated.
+;
+; CHECK-LABEL: Printing analysis {{.*}} for function 'crossloops':
+; CHECK-NEXT: block-frequency-info: crossloops
+define void @crossloops(i32 %a) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  %choose = call i32 @choose(i32 %a)
+  switch i32 %choose, label %exit [ i32 1, label %c1
+                                    i32 2, label %c2 ], !prof !3
+
+; This is like a single-line XFAIL (see above).
+; CHECK-NEXT: c1:
+; CHECK-NOT: float = 1.0,
+c1:
+  %i1 = phi i32 [ %a, %entry ], [ %i1.inc, %c1 ], [ %i2.inc, %c2 ]
+  %i1.inc = add i32 %i1, 1
+  %choose1 = call i32 @choose(i32 %i1)
+  switch i32 %choose1, label %exit [ i32 1, label %c1
+                                     i32 2, label %c2 ], !prof !3
+
+; This is like a single-line XFAIL (see above).
+; CHECK-NEXT: c2:
+; CHECK-NOT: float = 1.0,
+c2:
+  %i2 = phi i32 [ %a, %entry ], [ %i1.inc, %c1 ], [ %i2.inc, %c2 ]
+  %i2.inc = add i32 %i2, 1
+  %choose2 = call i32 @choose(i32 %i2)
+  switch i32 %choose2, label %exit [ i32 1, label %c1
+                                     i32 2, label %c2 ], !prof !3
+
+; We still shouldn't lose any frequency.
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
+exit:
+  ret void
+}
+
+declare i32 @choose(i32)
+
+!2 = metadata !{metadata !"branch_weights", i32 3, i32 1}
+!3 = metadata !{metadata !"branch_weights", i32 2, i32 2, i32 2}
diff --git a/test/Analysis/BlockFrequencyInfo/loop_with_branch.ll b/test/Analysis/BlockFrequencyInfo/loop_with_branch.ll
new file mode 100644
index 0000000000..9d27b6bf0f
--- /dev/null
+++ b/test/Analysis/BlockFrequencyInfo/loop_with_branch.ll
@@ -0,0 +1,44 @@
+; RUN: opt < %s -analyze -block-freq | FileCheck %s
+
+; CHECK-LABEL: Printing analysis {{.*}} for function 'loop_with_branch':
+; CHECK-NEXT: block-frequency-info: loop_with_branch
+define void @loop_with_branch(i32 %a) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  %skip_loop = call i1 @foo0(i32 %a)
+  br i1 %skip_loop, label %skip, label %header, !prof !0
+
+; CHECK-NEXT: skip: float = 0.25,
+skip:
+  br label %exit
+
+; CHECK-NEXT: header: float = 4.5,
+header:
+  %i = phi i32 [ 0, %entry ], [ %i.next, %back ]
+  %i.next = add i32 %i, 1
+  %choose = call i2 @foo1(i32 %i)
+  switch i2 %choose, label %exit [ i2 0, label %left
+                                   i2 1, label %right ], !prof !1
+
+; CHECK-NEXT: left: float = 1.5,
+left:
+  br label %back
+
+; CHECK-NEXT: right: float = 2.25,
+right:
+  br label %back
+
+; CHECK-NEXT: back: float = 3.75,
+back:
+  br label %header
+
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
+exit:
+  ret void
+}
+
+declare i1 @foo0(i32)
+declare i2 @foo1(i32)
+
+!0 = metadata !{metadata !"branch_weights", i32 1, i32 3}
+!1 = metadata !{metadata !"branch_weights", i32 1, i32 2, i32 3}
diff --git a/test/Analysis/BlockFrequencyInfo/nested_loop_with_branches.ll b/test/Analysis/BlockFrequencyInfo/nested_loop_with_branches.ll
new file mode 100644
index 0000000000..d93ffceb5f
--- /dev/null
+++ b/test/Analysis/BlockFrequencyInfo/nested_loop_with_branches.ll
@@ -0,0 +1,59 @@
+; RUN: opt < %s -analyze -block-freq | FileCheck %s
+
+; CHECK-LABEL: Printing analysis {{.*}} for function 'nested_loop_with_branches'
+; CHECK-NEXT: block-frequency-info: nested_loop_with_branches
+define void @nested_loop_with_branches(i32 %a) {
+; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
+entry:
+  %v0 = call i1 @foo0(i32 %a)
+  br i1 %v0, label %exit, label %outer, !prof !0
+
+; CHECK-NEXT: outer: float = 12.0,
+outer:
+  %i = phi i32 [ 0, %entry ], [ %i.next, %inner.end ], [ %i.next, %no_inner ]
+  %i.next = add i32 %i, 1
+  %do_inner = call i1 @foo1(i32 %i)
+  br i1 %do_inner, label %no_inner, label %inner, !prof !0
+
+; CHECK-NEXT: inner: float = 36.0,
+inner:
+  %j = phi i32 [ 0, %outer ], [ %j.next, %inner.end ]
+  %side = call i1 @foo3(i32 %j)
+  br i1 %side, label %left, label %right, !prof !0
+
+; CHECK-NEXT: left: float = 9.0,
+left:
+  %v4 = call i1 @foo4(i32 %j)
+  br label %inner.end
+
+; CHECK-NEXT: right: float = 27.0,
+right:
+  %v5 = call i1 @foo5(i32 %j)
+  br label %inner.end
+
+; CHECK-NEXT: inner.end: float = 36.0,
+inner.end:
+  %stay_inner = phi i1 [ %v4, %left ], [ %v5, %right ]
+  %j.next = add i32 %j, 1
+  br i1 %stay_inner, label %inner, label %outer, !prof !1
+
+; CHECK-NEXT: no_inner: float = 3.0,
+no_inner:
+  %continue = call i1 @foo6(i32 %i)
+  br i1 %continue, label %outer, label %exit, !prof !1
+
+; CHECK-NEXT: exit: float = 1.0, int = [[ENTRY]]
+exit:
+  ret void
+}
+
+declare i1 @foo0(i32)
+declare i1 @foo1(i32)
+declare i1 @foo2(i32)
+declare i1 @foo3(i32)
+declare i1 @foo4(i32)
+declare i1 @foo5(i32)
+declare i1 @foo6(i32)
+
+!0 = metadata !{metadata !"branch_weights", i32 1, i32 3}
+!1 = metadata !{metadata !"branch_weights", i32 3, i32 1}
diff --git a/test/CodeGen/XCore/llvm-intrinsics.ll b/test/CodeGen/XCore/llvm-intrinsics.ll
index e0acd66e4a..b436282615 100644
--- a/test/CodeGen/XCore/llvm-intrinsics.ll
+++ b/test/CodeGen/XCore/llvm-intrinsics.ll
@@ -287,9 +287,8 @@ define void @Unwind1() {
 ; CHECKFP: .LBB{{[0-9_]+}}
 ; CHECKFP-NEXT: ldc r2, 40
 ; CHECKFP-NEXT: add r2, r10, r2
-; CHECKFP-NEXT: add r0, r2, r0
+; CHECKFP-NEXT: add r2, r2, r0
 ; CHECKFP-NEXT: mov r3, r1
-; CHECKFP-NEXT: mov r2, r0
 ; CHECKFP-NEXT: ldw r9, r10[4]
 ; CHECKFP-NEXT: ldw r8, r10[5]
 ; CHECKFP-NEXT: ldw r7, r10[6]
@@ -337,9 +336,8 @@ define void @Unwind1() {
 ; CHECK-NEXT: ldc r2, 36
 ; CHECK-NEXT: ldaw r3, sp[0]
 ; CHECK-NEXT: add r2, r3, r2
-; CHECK-NEXT: add r0, r2, r0
+; CHECK-NEXT: add r2, r2, r0
 ; CHECK-NEXT: mov r3, r1
-; CHECK-NEXT: mov r2, r0
 ; CHECK-NEXT: ldw r10, sp[2]
 ; CHECK-NEXT: ldw r9, sp[3]
 ; CHECK-NEXT: ldw r8, sp[4]