Vendor import of llvm trunk r154661:

http://llvm.org/svn/llvm-project/llvm/trunk@r154661

4 files changed, 535 insertions, 0 deletions

diff --git a/test/Analysis/BranchProbabilityInfo/basic.ll b/test/Analysis/BranchProbabilityInfo/basic.ll
new file mode 100644
index 0000000..74d06a1
--- /dev/null
+++ b/test/Analysis/BranchProbabilityInfo/basic.ll
@@ -0,0 +1,90 @@
+; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+
+define i32 @test1(i32 %i, i32* %a) {
+; CHECK: Printing analysis {{.*}} for function 'test1'
+entry:
+  br label %body
+; CHECK: edge entry -> body probability is 16 / 16 = 100%
+
+body:
+  %iv = phi i32 [ 0, %entry ], [ %next, %body ]
+  %base = phi i32 [ 0, %entry ], [ %sum, %body ]
+  %arrayidx = getelementptr inbounds i32* %a, i32 %iv
+  %0 = load i32* %arrayidx
+  %sum = add nsw i32 %0, %base
+  %next = add i32 %iv, 1
+  %exitcond = icmp eq i32 %next, %i
+  br i1 %exitcond, label %exit, label %body
+; CHECK: edge body -> exit probability is 4 / 128
+; CHECK: edge body -> body probability is 124 / 128
+
+exit:
+  ret i32 %sum
+}
+
+define i32 @test2(i32 %i, i32 %a, i32 %b) {
+; CHECK: Printing analysis {{.*}} for function 'test2'
+entry:
+  %cond = icmp ult i32 %i, 42
+  br i1 %cond, label %then, label %else, !prof !0
+; CHECK: edge entry -> then probability is 64 / 68
+; CHECK: edge entry -> else probability is 4 / 68
+
+then:
+  br label %exit
+; CHECK: edge then -> exit probability is 16 / 16 = 100%
+
+else:
+  br label %exit
+; CHECK: edge else -> exit probability is 16 / 16 = 100%
+
+exit:
+  %result = phi i32 [ %a, %then ], [ %b, %else ]
+  ret i32 %result
+}
+
+!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'
+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: edge entry -> case_a probability is 4 / 80
+; CHECK: edge entry -> case_b probability is 4 / 80
+; CHECK: edge entry -> case_c probability is 64 / 80
+; CHECK: edge entry -> case_d probability is 4 / 80
+; CHECK: edge entry -> case_e probability is 4 / 80
+
+case_a:
+  br label %exit
+; CHECK: edge case_a -> exit probability is 16 / 16 = 100%
+
+case_b:
+  br label %exit
+; CHECK: edge case_b -> exit probability is 16 / 16 = 100%
+
+case_c:
+  br label %exit
+; CHECK: edge case_c -> exit probability is 16 / 16 = 100%
+
+case_d:
+  br label %exit
+; CHECK: edge case_d -> exit probability is 16 / 16 = 100%
+
+case_e:
+  br label %exit
+; CHECK: edge case_e -> exit probability is 16 / 16 = 100%
+
+exit:
+  %result = phi i32 [ %a, %case_a ],
+                    [ %b, %case_b ],
+                    [ %c, %case_c ],
+                    [ %d, %case_d ],
+                    [ %e, %case_e ]
+  ret i32 %result
+}
+
+!1 = metadata !{metadata !"branch_weights", i32 4, i32 4, i32 64, i32 4, i32 4}
diff --git a/test/Analysis/BranchProbabilityInfo/lit.local.cfg b/test/Analysis/BranchProbabilityInfo/lit.local.cfg
new file mode 100644
index 0000000..19eebc0
--- /dev/null
+++ b/test/Analysis/BranchProbabilityInfo/lit.local.cfg
@@ -0,0 +1 @@
+config.suffixes = ['.ll', '.c', '.cpp']
diff --git a/test/Analysis/BranchProbabilityInfo/loop.ll b/test/Analysis/BranchProbabilityInfo/loop.ll
new file mode 100644
index 0000000..b648cbb
--- /dev/null
+++ b/test/Analysis/BranchProbabilityInfo/loop.ll
@@ -0,0 +1,365 @@
+; Test the static branch probability heuristics for no-return functions.
+; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+
+declare void @g1()
+declare void @g2()
+declare void @g3()
+declare void @g4()
+
+define void @test1(i32 %a, i32 %b) {
+entry:
+  br label %do.body
+; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc3, %do.end ]
+  call void @g1()
+  br label %do.body1
+; CHECK: edge do.body -> do.body1 probability is 124 / 124 = 100%
+
+do.body1:
+  %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.body1 ]
+  call void @g2()
+  %inc = add nsw i32 %j.0, 1
+  %cmp = icmp slt i32 %inc, %b
+  br i1 %cmp, label %do.body1, label %do.end
+; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
+; CHECK: edge do.body1 -> do.end probability is 4 / 128
+
+do.end:
+  call void @g3()
+  %inc3 = add nsw i32 %i.0, 1
+  %cmp4 = icmp slt i32 %inc3, %a
+  br i1 %cmp4, label %do.body, label %do.end5
+; CHECK: edge do.end -> do.body probability is 124 / 128
+; CHECK: edge do.end -> do.end5 probability is 4 / 128
+
+do.end5:
+  call void @g4()
+  ret void
+}
+
+define void @test2(i32 %a, i32 %b) {
+entry:
+  %cmp9 = icmp sgt i32 %a, 0
+  br i1 %cmp9, label %for.body.lr.ph, label %for.end6
+; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
+; CHECK: edge entry -> for.end6 probability is 12 / 32
+
+for.body.lr.ph:
+  %cmp27 = icmp sgt i32 %b, 0
+  br label %for.body
+; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
+
+for.body:
+  %i.010 = phi i32 [ 0, %for.body.lr.ph ], [ %inc5, %for.end ]
+  call void @g1()
+  br i1 %cmp27, label %for.body3, label %for.end
+; CHECK: edge for.body -> for.body3 probability is 62 / 124 = 50%
+; CHECK: edge for.body -> for.end probability is 62 / 124 = 50%
+
+for.body3:
+  %j.08 = phi i32 [ %inc, %for.body3 ], [ 0, %for.body ]
+  call void @g2()
+  %inc = add nsw i32 %j.08, 1
+  %exitcond = icmp eq i32 %inc, %b
+  br i1 %exitcond, label %for.end, label %for.body3
+; CHECK: edge for.body3 -> for.end probability is 4 / 128
+; CHECK: edge for.body3 -> for.body3 probability is 124 / 128
+
+for.end:
+  call void @g3()
+  %inc5 = add nsw i32 %i.010, 1
+  %exitcond11 = icmp eq i32 %inc5, %a
+  br i1 %exitcond11, label %for.end6, label %for.body
+; CHECK: edge for.end -> for.end6 probability is 4 / 128
+; CHECK: edge for.end -> for.body probability is 124 / 128
+
+for.end6:
+  call void @g4()
+  ret void
+}
+
+define void @test3(i32 %a, i32 %b, i32* %c) {
+entry:
+  br label %do.body
+; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ]
+  call void @g1()
+  %0 = load i32* %c, align 4
+  %cmp = icmp slt i32 %0, 42
+  br i1 %cmp, label %do.body1, label %if.end
+; CHECK: edge do.body -> do.body1 probability is 62 / 124 = 50%
+; CHECK: edge do.body -> if.end probability is 62 / 124 = 50%
+
+do.body1:
+  %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ]
+  call void @g2()
+  %inc = add nsw i32 %j.0, 1
+  %cmp2 = icmp slt i32 %inc, %b
+  br i1 %cmp2, label %do.body1, label %if.end
+; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
+; CHECK: edge do.body1 -> if.end probability is 4 / 128
+
+if.end:
+  call void @g3()
+  %inc4 = add nsw i32 %i.0, 1
+  %cmp5 = icmp slt i32 %inc4, %a
+  br i1 %cmp5, label %do.body, label %do.end6
+; CHECK: edge if.end -> do.body probability is 124 / 128
+; CHECK: edge if.end -> do.end6 probability is 4 / 128
+
+do.end6:
+  call void @g4()
+  ret void
+}
+
+define void @test4(i32 %a, i32 %b, i32* %c) {
+entry:
+  br label %do.body
+; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
+  call void @g1()
+  %0 = load i32* %c, align 4
+  %cmp = icmp slt i32 %0, 42
+  br i1 %cmp, label %return, label %do.body1
+; CHECK: edge do.body -> return probability is 4 / 128
+; CHECK: edge do.body -> do.body1 probability is 124 / 128
+
+do.body1:
+  %j.0 = phi i32 [ %inc, %do.body1 ], [ 0, %do.body ]
+  call void @g2()
+  %inc = add nsw i32 %j.0, 1
+  %cmp2 = icmp slt i32 %inc, %b
+  br i1 %cmp2, label %do.body1, label %do.end
+; CHECK: edge do.body1 -> do.body1 probability is 124 / 128
+; CHECK: edge do.body1 -> do.end probability is 4 / 128
+
+do.end:
+  call void @g3()
+  %inc4 = add nsw i32 %i.0, 1
+  %cmp5 = icmp slt i32 %inc4, %a
+  br i1 %cmp5, label %do.body, label %do.end6
+; CHECK: edge do.end -> do.body probability is 124 / 128
+; CHECK: edge do.end -> do.end6 probability is 4 / 128
+
+do.end6:
+  call void @g4()
+  br label %return
+; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
+
+return:
+  ret void
+}
+
+define void @test5(i32 %a, i32 %b, i32* %c) {
+entry:
+  br label %do.body
+; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
+  call void @g1()
+  br label %do.body1
+; CHECK: edge do.body -> do.body1 probability is 124 / 124 = 100%
+
+do.body1:
+  %j.0 = phi i32 [ 0, %do.body ], [ %inc, %if.end ]
+  %0 = load i32* %c, align 4
+  %cmp = icmp slt i32 %0, 42
+  br i1 %cmp, label %return, label %if.end
+; CHECK: edge do.body1 -> return probability is 4 / 128
+; CHECK: edge do.body1 -> if.end probability is 124 / 128
+
+if.end:
+  call void @g2()
+  %inc = add nsw i32 %j.0, 1
+  %cmp2 = icmp slt i32 %inc, %b
+  br i1 %cmp2, label %do.body1, label %do.end
+; CHECK: edge if.end -> do.body1 probability is 124 / 128
+; CHECK: edge if.end -> do.end probability is 4 / 128
+
+do.end:
+  call void @g3()
+  %inc4 = add nsw i32 %i.0, 1
+  %cmp5 = icmp slt i32 %inc4, %a
+  br i1 %cmp5, label %do.body, label %do.end6
+; CHECK: edge do.end -> do.body probability is 124 / 128
+; CHECK: edge do.end -> do.end6 probability is 4 / 128
+
+do.end6:
+  call void @g4()
+  br label %return
+; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
+
+return:
+  ret void
+}
+
+define void @test6(i32 %a, i32 %b, i32* %c) {
+entry:
+  br label %do.body
+; CHECK: edge entry -> do.body probability is 16 / 16 = 100%
+
+do.body:
+  %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
+  call void @g1()
+  br label %do.body1
+; CHECK: edge do.body -> do.body1 probability is 124 / 124 = 100%
+
+do.body1:
+  %j.0 = phi i32 [ 0, %do.body ], [ %inc, %do.cond ]
+  call void @g2()
+  %0 = load i32* %c, align 4
+  %cmp = icmp slt i32 %0, 42
+  br i1 %cmp, label %return, label %do.cond
+; CHECK: edge do.body1 -> return probability is 4 / 128
+; CHECK: edge do.body1 -> do.cond probability is 124 / 128
+
+do.cond:
+  %inc = add nsw i32 %j.0, 1
+  %cmp2 = icmp slt i32 %inc, %b
+  br i1 %cmp2, label %do.body1, label %do.end
+; CHECK: edge do.cond -> do.body1 probability is 124 / 128
+; CHECK: edge do.cond -> do.end probability is 4 / 128
+
+do.end:
+  call void @g3()
+  %inc4 = add nsw i32 %i.0, 1
+  %cmp5 = icmp slt i32 %inc4, %a
+  br i1 %cmp5, label %do.body, label %do.end6
+; CHECK: edge do.end -> do.body probability is 124 / 128
+; CHECK: edge do.end -> do.end6 probability is 4 / 128
+
+do.end6:
+  call void @g4()
+  br label %return
+; CHECK: edge do.end6 -> return probability is 16 / 16 = 100%
+
+return:
+  ret void
+}
+
+define void @test7(i32 %a, i32 %b, i32* %c) {
+entry:
+  %cmp10 = icmp sgt i32 %a, 0
+  br i1 %cmp10, label %for.body.lr.ph, label %for.end7
+; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
+; CHECK: edge entry -> for.end7 probability is 12 / 32
+
+for.body.lr.ph:
+  %cmp38 = icmp sgt i32 %b, 0
+  br label %for.body
+; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
+
+for.body:
+  %i.011 = phi i32 [ 0, %for.body.lr.ph ], [ %inc6, %for.inc5 ]
+  %0 = load i32* %c, align 4
+  %cmp1 = icmp eq i32 %0, %i.011
+  br i1 %cmp1, label %for.inc5, label %if.end
+; CHECK: edge for.body -> for.inc5 probability is 62 / 124 = 50%
+; CHECK: edge for.body -> if.end probability is 62 / 124 = 50%
+
+if.end:
+  call void @g1()
+  br i1 %cmp38, label %for.body4, label %for.end
+; CHECK: edge if.end -> for.body4 probability is 62 / 124 = 50%
+; CHECK: edge if.end -> for.end probability is 62 / 124 = 50%
+
+for.body4:
+  %j.09 = phi i32 [ %inc, %for.body4 ], [ 0, %if.end ]
+  call void @g2()
+  %inc = add nsw i32 %j.09, 1
+  %exitcond = icmp eq i32 %inc, %b
+  br i1 %exitcond, label %for.end, label %for.body4
+; CHECK: edge for.body4 -> for.end probability is 4 / 128
+; CHECK: edge for.body4 -> for.body4 probability is 124 / 128
+
+for.end:
+  call void @g3()
+  br label %for.inc5
+; CHECK: edge for.end -> for.inc5 probability is 124 / 124 = 100%
+
+for.inc5:
+  %inc6 = add nsw i32 %i.011, 1
+  %exitcond12 = icmp eq i32 %inc6, %a
+  br i1 %exitcond12, label %for.end7, label %for.body
+; CHECK: edge for.inc5 -> for.end7 probability is 4 / 128
+; CHECK: edge for.inc5 -> for.body probability is 124 / 128
+
+for.end7:
+  call void @g4()
+  ret void
+}
+
+define void @test8(i32 %a, i32 %b, i32* %c) {
+entry:
+  %cmp18 = icmp sgt i32 %a, 0
+  br i1 %cmp18, label %for.body.lr.ph, label %for.end15
+; CHECK: edge entry -> for.body.lr.ph probability is 20 / 32
+; CHECK: edge entry -> for.end15 probability is 12 / 32
+
+for.body.lr.ph:
+  %cmp216 = icmp sgt i32 %b, 0
+  %arrayidx5 = getelementptr inbounds i32* %c, i64 1
+  %arrayidx9 = getelementptr inbounds i32* %c, i64 2
+  br label %for.body
+; CHECK: edge for.body.lr.ph -> for.body probability is 16 / 16 = 100%
+
+for.body:
+  %i.019 = phi i32 [ 0, %for.body.lr.ph ], [ %inc14, %for.end ]
+  call void @g1()
+  br i1 %cmp216, label %for.body3, label %for.end
+; CHECK: edge for.body -> for.body3 probability is 62 / 124 = 50%
+; CHECK: edge for.body -> for.end probability is 62 / 124 = 50%
+
+for.body3:
+  %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
+  %0 = load i32* %c, align 4
+  %cmp4 = icmp eq i32 %0, %j.017
+  br i1 %cmp4, label %for.inc, label %if.end
+; CHECK: edge for.body3 -> for.inc probability is 62 / 124 = 50%
+; CHECK: edge for.body3 -> if.end probability is 62 / 124 = 50%
+
+if.end:
+  %1 = load i32* %arrayidx5, align 4
+  %cmp6 = icmp eq i32 %1, %j.017
+  br i1 %cmp6, label %for.inc, label %if.end8
+; CHECK: edge if.end -> for.inc probability is 62 / 124 = 50%
+; CHECK: edge if.end -> if.end8 probability is 62 / 124 = 50%
+
+if.end8:
+  %2 = load i32* %arrayidx9, align 4
+  %cmp10 = icmp eq i32 %2, %j.017
+  br i1 %cmp10, label %for.inc, label %if.end12
+; CHECK: edge if.end8 -> for.inc probability is 62 / 124 = 50%
+; CHECK: edge if.end8 -> if.end12 probability is 62 / 124 = 50%
+
+if.end12:
+  call void @g2()
+  br label %for.inc
+; CHECK: edge if.end12 -> for.inc probability is 124 / 124 = 100%
+
+for.inc:
+  %inc = add nsw i32 %j.017, 1
+  %exitcond = icmp eq i32 %inc, %b
+  br i1 %exitcond, label %for.end, label %for.body3
+; CHECK: edge for.inc -> for.end probability is 4 / 128
+; CHECK: edge for.inc -> for.body3 probability is 124 / 128
+
+for.end:
+  call void @g3()
+  %inc14 = add nsw i32 %i.019, 1
+  %exitcond20 = icmp eq i32 %inc14, %a
+  br i1 %exitcond20, label %for.end15, label %for.body
+; CHECK: edge for.end -> for.end15 probability is 4 / 128
+; CHECK: edge for.end -> for.body probability is 124 / 128
+
+for.end15:
+  call void @g4()
+  ret void
+}
diff --git a/test/Analysis/BranchProbabilityInfo/noreturn.ll b/test/Analysis/BranchProbabilityInfo/noreturn.ll
new file mode 100644
index 0000000..8b9ae11
--- /dev/null
+++ b/test/Analysis/BranchProbabilityInfo/noreturn.ll
@@ -0,0 +1,79 @@
+; Test the static branch probability heuristics for no-return functions.
+; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+
+declare void @abort() noreturn
+
+define i32 @test1(i32 %a, i32 %b) {
+; CHECK: Printing analysis {{.*}} for function 'test1'
+entry:
+  %cond = icmp eq i32 %a, 42
+  br i1 %cond, label %exit, label %abort
+; CHECK: edge entry -> exit probability is 1048575 / 1048576
+; CHECK: edge entry -> abort probability is 1 / 1048576
+
+abort:
+  call void @abort() noreturn
+  unreachable
+
+exit:
+  ret i32 %b
+}
+
+define i32 @test2(i32 %a, i32 %b) {
+; CHECK: Printing analysis {{.*}} for function 'test2'
+entry:
+  switch i32 %a, label %exit [i32 1, label %case_a
+                              i32 2, label %case_b
+                              i32 3, label %case_c
+                              i32 4, label %case_d]
+; CHECK: edge entry -> exit probability is 1048575 / 1048579
+; CHECK: edge entry -> case_a probability is 1 / 1048579
+; CHECK: edge entry -> case_b probability is 1 / 1048579
+; CHECK: edge entry -> case_c probability is 1 / 1048579
+; CHECK: edge entry -> case_d probability is 1 / 1048579
+
+case_a:
+  br label %case_b
+
+case_b:
+  br label %case_c
+
+case_c:
+  br label %case_d
+
+case_d:
+  call void @abort() noreturn
+  unreachable
+
+exit:
+  ret i32 %b
+}
+
+define i32 @test3(i32 %a, i32 %b) {
+; CHECK: Printing analysis {{.*}} for function 'test3'
+; Make sure we unify across multiple conditional branches.
+entry:
+  %cond1 = icmp eq i32 %a, 42
+  br i1 %cond1, label %exit, label %dom
+; CHECK: edge entry -> exit probability is 1048575 / 1048576
+; CHECK: edge entry -> dom probability is 1 / 1048576
+
+dom:
+  %cond2 = icmp ult i32 %a, 42
+  br i1 %cond2, label %idom1, label %idom2
+; CHECK: edge dom -> idom1 probability is 1 / 2
+; CHECK: edge dom -> idom2 probability is 1 / 2
+
+idom1:
+  br label %abort
+
+idom2:
+  br label %abort
+
+abort:
+  call void @abort() noreturn
+  unreachable
+
+exit:
+  ret i32 %b
+}