[BPI] Reduce the probability of unreachable edge to minimal value greater than 0

The probability of edge coming to unreachable block should be as low as possible.
The change reduces the probability to minimal value greater than zero.

The bug https://bugs.llvm.org/show_bug.cgi?id=32214 show the example when
the probability of edge coming to unreachable block is greater than for edge
coming to out of the loop and it causes incorrect loop rotation.

Please note that with this change the behavior of unreachable heuristic is a bit different
than others. Specifically, before this change the sum of probabilities
coming to unreachable blocks have the same weight for all branches
(it was just split over all edges of this block coming to unreachable blocks).
With this change it might be slightly different but not to much due to probability of
taken branch to unreachable block is really small.

Reviewers: chandlerc, sanjoy, vsk, congh, junbuml, davidxl, dexonsmith
Reviewed By: chandlerc, dexonsmith
Subscribers: reames, llvm-commits
Differential Revision: https://reviews.llvm.org/D30633

llvm-svn: 303327

3 files changed, 34 insertions, 34 deletions

diff --git a/llvm/test/Analysis/BranchProbabilityInfo/basic.ll b/llvm/test/Analysis/BranchProbabilityInfo/basic.ll
index 7bee1bd5737..64e0a82456f 100644
--- a/llvm/test/Analysis/BranchProbabilityInfo/basic.ll
+++ b/llvm/test/Analysis/BranchProbabilityInfo/basic.ll
@@ -378,8 +378,8 @@ entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %unr, !prof !4
 
-; CHECK:  edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK:  edge entry -> unr probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK:  edge entry -> exit probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
+; CHECK:  edge entry -> unr probability is 0x00000001 / 0x80000000 = 0.00%
 
 unr:
   unreachable
@@ -396,8 +396,8 @@ entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %unr, !prof !5
 
-; CHECK:  edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK:  edge entry -> unr probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK:  edge entry -> exit probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
+; CHECK:  edge entry -> unr probability is 0x00000001 / 0x80000000 = 0.00%
 
 unr:
   unreachable
@@ -406,7 +406,7 @@ exit:
   ret i32 %b
 }
 
-!5 = !{!"branch_weights", i32 1048575, i32 1}
+!5 = !{!"branch_weights", i32 2147483647, i32 1}
 
 define i32 @test_unreachable_with_prof_zero(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test_unreachable_with_prof_zero'
@@ -414,8 +414,8 @@ entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %unr, !prof !6
 
-; CHECK:  edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK:  edge entry -> unr probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK:  edge entry -> exit probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
+; CHECK:  edge entry -> unr probability is 0x00000001 / 0x80000000 = 0.00%
 
 unr:
   unreachable
@@ -451,11 +451,11 @@ entry:
                                  i32 2, label %case_c
                                  i32 3, label %case_d
                                  i32 4, label %case_e ], !prof !8
-; CHECK: edge entry -> case_a probability is 0x00000800 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_b probability is 0x07fffdff / 0x80000000 = 6.25%
-; CHECK: edge entry -> case_c probability is 0x67fffdff / 0x80000000 = 81.25% [HOT edge]
-; CHECK: edge entry -> case_d probability is 0x07fffdff / 0x80000000 = 6.25%
-; CHECK: edge entry -> case_e probability is 0x07fffdff / 0x80000000 = 6.25%
+; CHECK: edge entry -> case_a probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_b probability is 0x07ffffff / 0x80000000 = 6.25%
+; CHECK: edge entry -> case_c probability is 0x67ffffff / 0x80000000 = 81.25% [HOT edge]
+; CHECK: edge entry -> case_d probability is 0x07ffffff / 0x80000000 = 6.25%
+; CHECK: edge entry -> case_e probability is 0x07ffffff / 0x80000000 = 6.25%
 
 case_a:
   unreachable
@@ -493,11 +493,11 @@ entry:
                                  i32 2, label %case_c
                                  i32 3, label %case_d
                                  i32 4, label %case_e ], !prof !9
-; CHECK: edge entry -> case_a probability is 0x00000400 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_b probability is 0x00000400 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_c probability is 0x6aaaa7ff / 0x80000000 = 83.33% [HOT edge]
-; CHECK: edge entry -> case_d probability is 0x0aaaa7ff / 0x80000000 = 8.33%
-; CHECK: edge entry -> case_e probability is 0x0aaaa7ff / 0x80000000 = 8.33%
+; CHECK: edge entry -> case_a probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_b probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_c probability is 0x6aaaaaa9 / 0x80000000 = 83.33% [HOT edge]
+; CHECK: edge entry -> case_d probability is 0x0aaaaaa9 / 0x80000000 = 8.33%
+; CHECK: edge entry -> case_e probability is 0x0aaaaaa9 / 0x80000000 = 8.33%
 
 case_a:
   unreachable
@@ -534,10 +534,10 @@ entry:
                                  i32 3, label %case_d
                                  i32 4, label %case_e ], !prof !10
 ; CHECK: edge entry -> case_a probability is 0x00000000 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_b probability is 0x00000400 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_c probability is 0x6e08fa2d / 0x80000000 = 85.96% [HOT edge]
-; CHECK: edge entry -> case_d probability is 0x08fb80e9 / 0x80000000 = 7.02%
-; CHECK: edge entry -> case_e probability is 0x08fb80e9 / 0x80000000 = 7.02%
+; CHECK: edge entry -> case_b probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_c probability is 0x6e08fb82 / 0x80000000 = 85.96% [HOT edge]
+; CHECK: edge entry -> case_d probability is 0x08fb823e / 0x80000000 = 7.02%
+; CHECK: edge entry -> case_e probability is 0x08fb823e / 0x80000000 = 7.02%
 
 case_a:
   unreachable
diff --git a/llvm/test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll b/llvm/test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll
index faa09f9e8a0..c2681e5e7c8 100644
--- a/llvm/test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll
+++ b/llvm/test/Analysis/BranchProbabilityInfo/deopt-intrinsic.ll
@@ -9,8 +9,8 @@ entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %deopt
 
-; CHECK:  edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK:  edge entry -> deopt probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK:  edge entry -> exit probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
+; CHECK:  edge entry -> deopt probability is 0x00000001 / 0x80000000 = 0.00%
 
 deopt:
   %rval = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"() ]
diff --git a/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll b/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll
index 0c2fe863d03..0566ca16c2f 100644
--- a/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll
+++ b/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll
@@ -9,8 +9,8 @@ define i32 @test1(i32 %a, i32 %b) {
 entry:
   %cond = icmp eq i32 %a, 42
   br i1 %cond, label %exit, label %abort
-; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge entry -> abort probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> abort probability is 0x00000001 / 0x80000000 = 0.00%
 
 abort:
   call void @abort() noreturn
@@ -27,11 +27,11 @@ entry:
                               i32 2, label %case_b
                               i32 3, label %case_c
                               i32 4, label %case_d]
-; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge entry -> case_a probability is 0x00000200 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_b probability is 0x00000200 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_c probability is 0x00000200 / 0x80000000 = 0.00%
-; CHECK: edge entry -> case_d probability is 0x00000200 / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x7ffffffc / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> case_a probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_b probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_c probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> case_d probability is 0x00000001 / 0x80000000 = 0.00%
 
 case_a:
   br label %case_b
@@ -56,8 +56,8 @@ define i32 @test3(i32 %a, i32 %b) {
 entry:
   %cond1 = icmp eq i32 %a, 42
   br i1 %cond1, label %exit, label %dom
-; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge entry -> dom probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> dom probability is 0x00000001 / 0x80000000 = 0.00%
 
 dom:
   %cond2 = icmp ult i32 %a, 42
@@ -87,8 +87,8 @@ define i32 @throwSmallException(i32 %idx, i32 %limit) #0 personality i8* bitcast
 entry:
   %cmp = icmp sge i32 %idx, %limit
   br i1 %cmp, label %if.then, label %if.end
-; CHECK: edge entry -> if.then probability is 0x00000800 / 0x80000000 = 0.00%
-; CHECK: edge entry -> if.end probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> if.then probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> if.end probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
 
 if.then:                                          ; preds = %entry
   %exception = call i8* @__cxa_allocate_exception(i64 1) #0