Remove return heuristics from the static branch probabilities, and

introduce no-return or unreachable heuristics.

The return heuristics from the Ball and Larus paper don't work well in
practice as they pessimize early return paths. The only good hitrate
return heuristics are those for:
 - NULL return
 - Constant return
 - negative integer return

Only the last of these three can possibly require significant code for
the returning block, and even the last is fairly rare and usually also
a constant. As a consequence, even for the cold return paths, there is
little code on that return path, and so little code density to be gained
by sinking it. The places where sinking these blocks is valuable (inner
loops) will already be weighted appropriately as the edge is a loop-exit
branch.

All of this aside, early returns are nearly as common as all three of
these return categories, and should actually be predicted as taken!
Rather than muddy the waters of the static predictions, just remain
silent on returns and let the CFG itself dictate any layout or other
issues.

However, the return heuristic was flagging one very important case:
unreachable. Unfortunately it still gave a 1/4 chance of the
branch-to-unreachable occuring. It also didn't do a rigorous job of
finding those blocks which post-dominate an unreachable block.

This patch builds a more powerful analysis that should flag all branches
to blocks known to then reach unreachable. It also has better worst-case
runtime complexity by not looping through successors for each block. The
previous code would perform an N^2 walk in the event of a single entry
block branching to N successors with a switch where each successor falls
through to the next and they finally fall through to a return.

Test case added for noreturn heuristics. Also doxygen comments improved
along the way.

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

1 files changed, 79 insertions, 0 deletions

diff --git a/test/Analysis/BranchProbabilityInfo/noreturn.ll b/test/Analysis/BranchProbabilityInfo/noreturn.ll
new file mode 100644
index 0000000000..c53c1ed113
--- /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 1023 / 1024
+; CHECK: edge entry -> abort probability is 1 / 1024
+
+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 1023 / 1027
+; CHECK: edge entry -> case_a probability is 1 / 1027
+; CHECK: edge entry -> case_b probability is 1 / 1027
+; CHECK: edge entry -> case_c probability is 1 / 1027
+; CHECK: edge entry -> case_d probability is 1 / 1027
+
+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 1023 / 1024
+; CHECK: edge entry -> dom probability is 1 / 1024
+
+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
+}