[WIP][BPI] `calcEstimatedHeuristics()`: symmetrically with loop exiting edge, scale loop enter edge weight by trip count

[lebedev.ri]

Summary

I don't really know this area of LLVM, and probably not equipped to drive this the end.
This is motivated by D113342, but implemented in a more general manner.

[lebedev.ri]

Fix one more test.

[bin.cheng]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

850

Please correct me if I understand the idea incorrectly.
The problem at this point is that we don't know if the entering edge is duplicated from loop exit branch from LoopRotate. The edge could be from source code or other transformations, in this case, we don't really know the probability taking or skipping the guarded loop. For example, GCC has a heuristics saying that guarded inner loop in loop nest usually is not likely to be executed.

[lebedev.ri]

Only do so for loops in rotated form.

[ebrevnov]

It seems that the new heuristic is applied not only to loops in rotated form. For example "test_cold_loop" or "test13".
In general we should decrease probability to take particular back edge proportionally to number of added exits. For example if number of exits equal to number of predicted iterations then each particular exit should be 50/50. But this is not supported yet anyway..

[bin.cheng]

llvm/lib/Analysis/BranchProbabilityInfo.cpp

851

IMHO isRotatedForm check is not enough because it only checks "form". For example, a user written do-while loop under some irrelevant guard condition. Is it possible to also check if we are checking on induction variable of SuccLoop? I guess this covers most cases with minimum false positive.

llvm/lib/Analysis/BranchProbabilityInfo.cpp

bool BranchProbabilityInfo::calcEstimatedHeuristics(const BasicBlock *BB) {
   // Go over all successors of BB and put their weights into SuccWeights.
   for (const BasicBlock *SuccBB : successors(BB)) {
     Optional<uint32_t> Weight;
     const LoopBlock SuccLoopBB = getLoopBlock(SuccBB);
     const LoopEdge Edge{LoopBB, SuccLoopBB};
 
     Weight = getEstimatedEdgeWeight(Edge);
 
+    if (isLoopEnteringEdge(Edge) && SuccLoopBB.getLoop() &&
+        SuccLoopBB.getLoop()->isRotatedForm() &&
+        // Avoid adjustment of ZERO weight since it should remain unchanged.
+        Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
+      // Scale up loop entering weight by trip count,
+      // this is symmetrical with loop exiting edge.
+      Weight =
+          Weight.getValueOr(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) *
+          TC;
+    }
     if (isLoopExitingEdge(Edge) &&
         // Avoid adjustment of ZERO weight since it should remain unchanged.
         Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
       // Scale down loop exiting weight by trip count.
       Weight = std::max(
           static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),
           Weight.getValueOr(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) /
               TC);

llvm/test/Analysis/BranchProbabilityInfo/basic.ll

exit:
   %result = phi i32 [ %a, %then ], [ %b, %else ]
   ret i32 %result
 }
 
 define i32 @test_cold_loop(i32 %a, i32 %b) {
 entry:
   %cond1 = icmp eq i32 %a, 42
   br i1 %cond1, label %header, label %exit
-; CHECK: edge entry -> header probability is 0x40000000 / 0x80000000 = 50.00%
-; CHECK: edge entry -> exit probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge entry -> header probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge entry -> exit probability is 0x04000000 / 0x80000000 = 3.12%
 header:
   br label %body
 
 body:
   %cond2 = icmp eq i32 %b, 42
   br i1 %cond2, label %header, label %exit
 ; CHECK: edge body -> header probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge]
 ; CHECK: edge body -> exit probability is 0x0041edfd / 0x80000000 = 0.20%

llvm/test/Analysis/BranchProbabilityInfo/loop.ll

for.body.lr.ph:
   %cmp27 = icmp sgt i32 %b, 0
   br label %for.body
 ; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 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 0x50000000 / 0x80000000 = 62.50%
-; CHECK: edge for.body -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge for.body -> for.body3 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge for.body -> for.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 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 0x04000000 / 0x80000000 = 3.12%

 ; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %if.end ]
   call void @g1()
   %0 = load i32, 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 0x40000000 / 0x80000000 = 50.00%
-; CHECK: edge do.body -> if.end probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge do.body -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.body -> if.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 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 0x7c000000 / 0x80000000 = 96.88% [HOT edge]

 ; CHECK: edge entry -> do.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 do.body:
   %i.0 = phi i32 [ 0, %entry ], [ %inc4, %do.end ]
   call void @g1()
   %0 = load i32, 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 0x04000000 / 0x80000000 = 3.12%
-; CHECK: edge do.body -> do.body1 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge do.body -> return probability is 0x00220ff7 / 0x80000000 = 0.10%
+; CHECK: edge do.body -> do.body1 probability is 0x7fddf009 / 0x80000000 = 99.90% [HOT edge]
 
 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 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
for.body:
   %cmp1 = icmp eq i32 %0, %i.011
   br i1 %cmp1, label %for.inc5, label %if.end
 ; CHECK: edge for.body -> for.inc5 probability is 0x40000000 / 0x80000000 = 50.00%
 ; CHECK: edge for.body -> if.end probability is 0x40000000 / 0x80000000 = 50.00%
 
 if.end:
   call void @g1()
   br i1 %cmp38, label %for.body4, label %for.end
-; CHECK: edge if.end -> for.body4 probability is 0x50000000 / 0x80000000 = 62.50%
-; CHECK: edge if.end -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge if.end -> for.body4 probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge if.end -> for.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 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 0x04000000 / 0x80000000 = 3.12%
for.body.lr.ph:
   %arrayidx9 = getelementptr inbounds i32, i32* %c, i64 2
   br label %for.body
 ; CHECK: edge for.body.lr.ph -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 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 0x50000000 / 0x80000000 = 62.50%
-; CHECK: edge for.body -> for.end probability is 0x30000000 / 0x80000000 = 37.50%
+; CHECK: edge for.body -> for.body3 probability is 0x7c000000 / 0x80000000 = 96.88%
+; CHECK: edge for.body -> for.end probability is 0x04000000 / 0x80000000 = 3.12%
 
 for.body3:
   %j.017 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ]
   %0 = load i32, 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 0x40000000 / 0x80000000 = 50.00%
 ; CHECK: edge for.body3 -> if.end probability is 0x40000000 / 0x80000000 = 50.00%

 }
 
 declare i32 @InvokeCall()
 declare void @cold() cold
 
 ; If loop has single exit and it leads to 'cold' block then edge leading to loop enter
 ; should be considered 'cold' as well.
 define void @test13() {
-; CHECK: edge entry -> loop probability is 0x078780e3 / 0x80000000 = 5.88%
-; CHECK: edge entry -> exit probability is 0x78787f1d / 0x80000000 = 94.12% [HOT edge]
+; CHECK: edge entry -> loop probability is 0x546cd4b7 / 0x80000000 = 65.96%
+; CHECK: edge entry -> exit probability is 0x2b932b49 / 0x80000000 = 34.04%
 ; CHECK: edge loop -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge]
 ; CHECK: edge loop -> cold probability is 0x0041edfd / 0x80000000 = 0.20%
 ; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 entry:
   br i1 undef, label %loop, label %exit
 
 loop:

 
 exit:
   ret void
 }
 
 ; If loop has multiple low probability exits then edge leading to loop enter
 ; should be considered low probable as well.
 define void @test15() {
-; CHECK: edge entry -> loop probability is 0x078780e3 / 0x80000000 = 5.88%
-; CHECK: edge entry -> exit probability is 0x78787f1d / 0x80000000 = 94.12% [HOT edge]
+; CHECK: edge entry -> loop probability is 0x546cd4b7 / 0x80000000 = 65.96%
+; CHECK: edge entry -> exit probability is 0x2b932b49 / 0x80000000 = 34.04%
 ; CHECK: edge loop -> cont probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 ; CHECK: edge loop -> unreached probability is 0x00000000 / 0x80000000 = 0.00%
 ; CHECK: edge cont -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge]
 ; CHECK: edge cont -> cold probability is 0x0041edfd / 0x80000000 = 0.20%
 ; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 entry:
   br i1 undef, label %loop, label %exit

 
 exit:
   ret void
 }
 
 ; This is the same case as test15 but with additional loop 'preheader' block.
 define void @test16() {
 ; CHECK: edge entry -> preheader probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge preheader -> loop probability is 0x078780e3 / 0x80000000 = 5.88%
-; CHECK: edge preheader -> exit probability is 0x78787f1d / 0x80000000 = 94.12% [HOT edge]
+; CHECK: edge preheader -> loop probability is 0x546cd4b7 / 0x80000000 = 65.96%
+; CHECK: edge preheader -> exit probability is 0x2b932b49 / 0x80000000 = 34.04%
 ; CHECK: edge loop -> cont probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 ; CHECK: edge loop -> unreached probability is 0x00000000 / 0x80000000 = 0.00%
 ; CHECK: edge cont -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge]
 ; CHECK: edge cont -> cold probability is 0x0041edfd / 0x80000000 = 0.20%
 ; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 entry:
   br label %preheader

 }
 
 declare void @abort() noreturn
 
 ; Check that 'preheader' has 50/50 probability since there is one 'normal' exit.
 ; Check that exit to 'cold' and 'noreturn' has lower probability than 'normal' exit.
 define void @test17() {
 ; CHECK: edge entry -> preheader probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge preheader -> loop probability is 0x40000000 / 0x80000000 = 50.00%
-; CHECK: edge preheader -> exit probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge preheader -> loop probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
+; CHECK: edge preheader -> exit probability is 0x04000000 / 0x80000000 = 3.12%
 ; CHECK: edge loop -> cont probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
 ; CHECK: edge loop -> noreturn probability is 0x00000800 / 0x80000000 = 0.00%
 ; CHECK: edge cont -> cont2 probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge]
 ; CHECK: edge cont -> cold probability is 0x0041edfd / 0x80000000 = 0.20%
 ; CHECK: edge cont2 -> loop probability is 0x7c000000 / 0x80000000 = 96.88% [HOT edge]
 ; CHECK: edge cont2 -> exit probability is 0x04000000 / 0x80000000 = 3.12%
 ; CHECK: edge cold -> exit probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 entry:
exit:
   ret void
 }
 
 
 ; This is case with two loops where one nested into another. Nested loop has
 ; low probable exit what encreases robability to take exit in the top level loop.
 define void @test18() {
 ; CHECK: edge entry -> top.loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge top.loop -> loop probability is 0x546cd4b7 / 0x80000000 = 65.96%
-; CHECK: edge top.loop -> exit probability is 0x2b932b49 / 0x80000000 = 34.04%
+; CHECK: edge top.loop -> loop probability is 0x7de75ca9 / 0x80000000 = 98.36% [HOT edge]
+; CHECK: edge top.loop -> exit probability is 0x0218a357 / 0x80000000 = 1.64%
 ; CHECK: edge loop -> loop probability is 0x7fbe1203 / 0x80000000 = 99.80% [HOT edge]
 ; CHECK: edge loop -> cold probability is 0x0041edfd / 0x80000000 = 0.20%
 ; CHECK: edge cold -> top.loop probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
 
 entry:
- br label %top.loop 
+ br label %top.loop
 
 top.loop:
   %j.0 = phi i32 [ 0, %entry ], [ %j.inc, %cold ]
   br i1 undef, label %loop, label %exit
 
 loop:
   %i.0 = phi i32 [ %j.0, %top.loop ], [ %inc, %loop ]
   %inc = add nsw i32 %i.0, 1

llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll

 }
 
 define i32 @test4(i32 %a, i32 %b) {
 ; CHECK: Printing analysis {{.*}} for function 'test4'
 ; Make sure we handle loops post-dominated by unreachables.
 entry:
   %cond1 = icmp eq i32 %a, 42
   br i1 %cond1, label %header, label %exit
-; CHECK: edge entry -> header probability is 0x00000800 / 0x80000000 = 0.00%
-; CHECK: edge entry -> exit probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge entry -> header probability is 0x0000f7fe / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x7fff0802 / 0x80000000 = 100.00% [HOT edge]
 
 header:
   br label %body
 
 body:
   %cond2 = icmp eq i32 %a, 42
   br i1 %cond2, label %header, label %abort
 ; CHECK: edge body -> header probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]

llvm/test/ThinLTO/X86/function_entry_count.ll

 ; RUN: llvm-lto -thinlto-action=run -disable-thinlto-funcattrs=0 -thinlto-synthesize-entry-counts -exported-symbol=f \
 ; RUN:     -exported-symbol=g -exported-symbol=h -thinlto-save-temps=%t3. %t1.bc %t2.bc
 ; RUN: llvm-dis %t3.0.3.imported.bc -o - | FileCheck %s
 
 ; CHECK: define void @h() [[ATTR:#[0-9]+]] !prof ![[PROF2:[0-9]+]]
 ; CHECK: define void @f(i32{{.*}}) [[ATTR:#[0-9]+]] !prof ![[PROF1:[0-9]+]]
 ; CHECK: define available_externally void @g() !prof ![[PROF2]]
 ; CHECK-DAG: ![[PROF1]] = !{!"synthetic_function_entry_count", i64 10}
-; CHECK-DAG: ![[PROF2]] = !{!"synthetic_function_entry_count", i64 198}
+; CHECK-DAG: ![[PROF2]] = !{!"synthetic_function_entry_count", i64 308}
 ; CHECK-DAG: attributes [[ATTR]] = { norecurse nounwind }
 
 target triple = "x86_64-unknown-linux-gnu"
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 declare void @g();
 
 define void @h() {

llvm/test/Transforms/SyntheticCountsPropagation/prop.ll

 ; CHECK: !prof ![[COUNT3:[0-9]+]]
 define internal void @level3a(i32 %n) {
   ret void
 }
 
 !1 = !{!"branch_weights", i32 1, i32 99}
 !2 = !{!"branch_weights", i32 1, i32 1}
 ; CHECK: ![[COUNT1]] = !{!"synthetic_function_entry_count", i64 10}
-; CHECK: ![[COUNT2]] = !{!"synthetic_function_entry_count", i64 520}
-; CHECK: ![[COUNT3]] = !{!"synthetic_function_entry_count", i64 260}
+; CHECK: ![[COUNT2]] = !{!"synthetic_function_entry_count", i64 988}
+; CHECK: ![[COUNT3]] = !{!"synthetic_function_entry_count", i64 494}