[Loop Peeling] Fix the handling of branch weights of peeled off branches.

Current algorithm to update branch weights of latch block and its copies is
based on the assumption that number of peeling iterations is approximately equal
to trip count.

However it is not correct. According to profitability check in one case we can decide to peel
in case it helps to reduce the number of phi nodes. In this case the number of peeled iteration
can be less then estimated trip count.

This patch introduces another way to set the branch weights to peeled of branches.
Let F is a weight of the edge from latch to header.
Let E is a weight of the edge from latch to exit.
F/(F+E) is a probability to go to loop and E/(F+E) is a probability to go to exit.
Then, Estimated TripCount = F / E.
For I-th (counting from 0) peeled off iteration we set the the weights for
the peeled latch as (TC - I, 1). It gives us reasonable distribution,
The probability to go to exit 1/(TC-I) increases. At the same time
the estimated trip count of remaining loop reduces by I.

As a result after peeling off N iteration the weights will be
(F - N * E, E) and trip count of loop becomes
F / E - N or TC - N.

The idea is taken from the review of the patch D63918 proposed by Philip.

Reviewers: reames, mkuper, iajbar, fhahn
Reviewed By: reames
Subscribers: hiraditya, zzheng, llvm-commits
Differential Revision: https://reviews.llvm.org/D64235

llvm-svn: 366665

2 files changed, 16 insertions, 8 deletions

diff --git a/llvm/test/Transforms/LoopUnroll/peel-loop-pgo-deopt.ll b/llvm/test/Transforms/LoopUnroll/peel-loop-pgo-deopt.ll
index dc023f36dd2..27e54f9ac75 100644
--- a/llvm/test/Transforms/LoopUnroll/peel-loop-pgo-deopt.ll
+++ b/llvm/test/Transforms/LoopUnroll/peel-loop-pgo-deopt.ll
@@ -4,17 +4,22 @@
 
 ; Make sure we use the profile information correctly to peel-off 3 iterations
 ; from the loop, and update the branch weights for the peeled loop properly.
+; All side exits to deopt does not change weigths.
 
 ; CHECK: Loop Unroll: F[basic]
 ; CHECK: PEELING loop %for.body with iteration count 3!
 
 ; CHECK-LABEL: @basic
+; CHECK: br i1 %c, label %{{.*}}, label %side_exit, !prof !15
 ; CHECK: br i1 %{{.*}}, label %[[NEXT0:.*]], label %for.cond.for.end_crit_edge, !prof !16
 ; CHECK: [[NEXT0]]:
+; CHECK: br i1 %c, label %{{.*}}, label %side_exit, !prof !15
 ; CHECK: br i1 %{{.*}}, label %[[NEXT1:.*]], label %for.cond.for.end_crit_edge, !prof !17
 ; CHECK: [[NEXT1]]:
+; CHECK: br i1 %c, label %{{.*}}, label %side_exit, !prof !15
 ; CHECK: br i1 %{{.*}}, label %[[NEXT2:.*]], label %for.cond.for.end_crit_edge, !prof !18
 ; CHECK: [[NEXT2]]:
+; CHECK: br i1 %c, label %{{.*}}, label %side_exit.loopexit, !prof !15
 ; CHECK: br i1 %{{.*}}, label %for.body, label %{{.*}}, !prof !19
 
 define i32 @basic(i32* %p, i32 %k, i1 %c) #0 !prof !15 {
@@ -74,8 +79,11 @@ attributes #1 = { nounwind optsize }
 !16 = !{!"branch_weights", i32 3001, i32 1001}
 !17 = !{!"branch_weights", i32 1, i32 0}
 
-;CHECK: !16 = !{!"branch_weights", i32 900, i32 101}
-;CHECK: !17 = !{!"branch_weights", i32 540, i32 360}
-;CHECK: !18 = !{!"branch_weights", i32 162, i32 378}
-;CHECK: !19 = !{!"branch_weights", i32 1399, i32 162}
+; This is a weights of deopt side-exit.
+;CHECK: !15 = !{!"branch_weights", i32 1, i32 0}
+; This is a weights of latch and its copies.
+;CHECK: !16 = !{!"branch_weights", i32 3001, i32 1001}
+;CHECK: !17 = !{!"branch_weights", i32 2000, i32 1001}
+;CHECK: !18 = !{!"branch_weights", i32 999, i32 1001}
+;CHECK: !19 = !{!"branch_weights", i32 1, i32 1001}
 
diff --git a/llvm/test/Transforms/LoopUnroll/peel-loop-pgo.ll b/llvm/test/Transforms/LoopUnroll/peel-loop-pgo.ll
index 361a2ca71c3..f34d3d46c82 100644
--- a/llvm/test/Transforms/LoopUnroll/peel-loop-pgo.ll
+++ b/llvm/test/Transforms/LoopUnroll/peel-loop-pgo.ll
@@ -103,8 +103,8 @@ attributes #1 = { nounwind optsize }
 !15 = !{!"function_entry_count", i64 1}
 !16 = !{!"branch_weights", i32 3001, i32 1001}
 
-;CHECK: !15 = !{!"branch_weights", i32 900, i32 101}
-;CHECK: !16 = !{!"branch_weights", i32 540, i32 360}
-;CHECK: !17 = !{!"branch_weights", i32 162, i32 378}
-;CHECK: !18 = !{!"branch_weights", i32 1399, i32 162}
+;CHECK: !15 = !{!"branch_weights", i32 3001, i32 1001}
+;CHECK: !16 = !{!"branch_weights", i32 2000, i32 1001}
+;CHECK: !17 = !{!"branch_weights", i32 999, i32 1001}
+;CHECK: !18 = !{!"branch_weights", i32 1, i32 1001}