diff options
4 files changed, 43 insertions, 74 deletions
diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp index db87b17c156..267e19adfe4 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -58,45 +58,12 @@ char BranchProbabilityInfoWrapperPass::ID = 0; static const uint32_t LBH_TAKEN_WEIGHT = 124; static const uint32_t LBH_NONTAKEN_WEIGHT = 4; -/// \brief Unreachable-terminating branch taken weight. +/// \brief Unreachable-terminating branch taken probability. /// -/// This is the weight for a branch being taken to a block that terminates +/// This is the probability for a branch being taken to a block that terminates /// (eventually) in unreachable. These are predicted as unlikely as possible. -static const uint32_t UR_TAKEN_WEIGHT = 1; - -/// \brief Unreachable-terminating branch not-taken weight. -/// -/// This is the weight for a branch not being taken toward a block that -/// terminates (eventually) in unreachable. Such a branch is essentially never -/// taken. Set the weight to an absurdly high value so that nested loops don't -/// easily subsume it. -static const uint32_t UR_NONTAKEN_WEIGHT = 1024*1024 - 1; - -/// \brief Returns the branch probability for unreachable edge according to -/// heuristic. -/// -/// This is the branch probability being taken to a block that terminates -/// (eventually) in unreachable. These are predicted as unlikely as possible. -static BranchProbability getUnreachableProbability(uint64_t UnreachableCount) { - assert(UnreachableCount > 0 && "UnreachableCount must be > 0"); - return BranchProbability::getBranchProbability( - UR_TAKEN_WEIGHT, - (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * UnreachableCount); -} - -/// \brief Returns the branch probability for reachable edge according to -/// heuristic. -/// -/// This is the branch probability not being taken toward a block that -/// terminates (eventually) in unreachable. Such a branch is essentially never -/// taken. Set the weight to an absurdly high value so that nested loops don't -/// easily subsume it. -static BranchProbability getReachableProbability(uint64_t ReachableCount) { - assert(ReachableCount > 0 && "ReachableCount must be > 0"); - return BranchProbability::getBranchProbability( - UR_NONTAKEN_WEIGHT, - (UR_TAKEN_WEIGHT + UR_NONTAKEN_WEIGHT) * ReachableCount); -} +/// All reachable probability will equally share the remaining part. +static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1); /// \brief Weight for a branch taken going into a cold block. /// @@ -232,8 +199,10 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { return true; } - auto UnreachableProb = getUnreachableProbability(UnreachableEdges.size()); - auto ReachableProb = getReachableProbability(ReachableEdges.size()); + auto UnreachableProb = UR_TAKEN_PROB; + auto ReachableProb = + (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) / + ReachableEdges.size(); for (unsigned SuccIdx : UnreachableEdges) setEdgeProbability(BB, SuccIdx, UnreachableProb); @@ -319,7 +288,7 @@ bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { // If the unreachable heuristic is more strong then we use it for this edge. if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) { auto ToDistribute = BranchProbability::getZero(); - auto UnreachableProb = getUnreachableProbability(UnreachableIdxs.size()); + auto UnreachableProb = UR_TAKEN_PROB; for (auto i : UnreachableIdxs) if (UnreachableProb < BP[i]) { ToDistribute += BP[i] - UnreachableProb; 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 |
