diff --git a/llvm/docs/BranchWeightMetadata.rst b/llvm/docs/BranchWeightMetadata.rst --- a/llvm/docs/BranchWeightMetadata.rst +++ b/llvm/docs/BranchWeightMetadata.rst @@ -37,6 +37,9 @@ i32 } +Weight metadata with a zero value on one size will be interpreted as an unlikely +outcome that will be normalized to the same probability as `llvm.expect`. + ``SwitchInst`` ^^^^^^^^^^^^^^ diff --git a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h --- a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h @@ -135,6 +135,14 @@ return *this; } + /// Return the weight for a "likely branch". A 1/LikelyBranchWeight ratio + /// corresponds to the probability of `llvm.expect` matching the expected + /// value. + /// Note: There is also `TargetTransformInfo::getPredictableBranchThreshold` + /// for a value matching the current target. + static uint32_t getLikelyBranchWeight(); + static void normalizeLikelyWeights(SmallVectorImpl& Weights); + bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &); diff --git a/llvm/include/llvm/IR/ProfDataUtils.h b/llvm/include/llvm/IR/ProfDataUtils.h --- a/llvm/include/llvm/IR/ProfDataUtils.h +++ b/llvm/include/llvm/IR/ProfDataUtils.h @@ -99,12 +99,5 @@ /// metadata was found. bool extractProfTotalWeight(const Instruction &I, uint64_t &TotalWeights); -/// Return the weight for a "likely branch". A 1/LikelyBranchWeight ratio -/// corresponds to the probability of `llvm.expect` matching the expected -/// value. -/// Note: There is also `TargetTransformInfo::getPredictableBranchThreshold` -/// for a value matching the current target. -uint32_t getLikelyBranchWeight(); - } // namespace llvm #endif diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -51,6 +51,17 @@ #define DEBUG_TYPE "branch-prob" +// This default value is chosen to represent an extremely skewed outcome for +// a condition, but they leave some room for interpretation by later passes. +// +// If the documentation for __builtin_expect() was made explicit that it should +// only be used in extreme cases, we could make this ratio higher. As it stands, +// programmers may be using __builtin_expect() / llvm.expect to annotate that a +// branch is likely or unlikely to be taken. +static cl::opt LikelyBranchWeight( + "likely-branch-weight", cl::Hidden, cl::init(2000), + cl::desc("Weight of the branch likely to be taken (default = 2000)")); + static cl::opt PrintBranchProb( "print-bpi", cl::init(false), cl::Hidden, cl::desc("Print the branch probability info.")); @@ -372,6 +383,31 @@ } } +uint32_t BranchProbabilityInfo::getLikelyBranchWeight() { + return LikelyBranchWeight; +} + +// Normalize branch_weights like `1:0` or `0:1:0` to use `LikelyBranchWeight`. +void BranchProbabilityInfo::normalizeLikelyWeights(SmallVectorImpl& Weights) { + // Check if all but one entry are zero. + bool HadNonZeroWeight = false; + for (uint32_t W : Weights) { + if (W != 0) { + if (HadNonZeroWeight) + return; + HadNonZeroWeight = true; + } + } + + for (uint32_t &W : Weights) { + if (W != 0) { + W = getLikelyBranchWeight(); + } else { + W = 1; + } + } +} + // Propagate existing explicit probabilities from either profile data or // 'expect' intrinsic processing. Examine metadata against unreachable // heuristic. The probability of the edge coming to unreachable block is @@ -399,6 +435,8 @@ SmallVector ReachableIdxs; extractBranchWeights(WeightsNode, Weights); + normalizeLikelyWeights(Weights); + for (unsigned I = 0, E = Weights.size(); I != E; ++I) { WeightSum += Weights[I]; const LoopBlock SrcLoopBB = getLoopBlock(BB); @@ -1328,3 +1366,4 @@ AM.getResult(F).print(OS); return PreservedAnalyses::all(); } + diff --git a/llvm/lib/IR/ProfDataUtils.cpp b/llvm/lib/IR/ProfDataUtils.cpp --- a/llvm/lib/IR/ProfDataUtils.cpp +++ b/llvm/lib/IR/ProfDataUtils.cpp @@ -23,18 +23,6 @@ using namespace llvm; -// These default values are chosen to represent an extremely skewed outcome for -// a condition, but they leave some room for interpretation by later passes. -// -// If the documentation for __builtin_expect() was made explicit that it should -// only be used in extreme cases, we could make this ratio higher. As it stands, -// programmers may be using __builtin_expect() / llvm.expect to annotate that a -// branch is likely or unlikely to be taken. - -static cl::opt LikelyBranchWeight( - "likely-branch-weight", cl::Hidden, cl::init(2000), - cl::desc("Weight of the branch likely to be taken (default = 2000)")); - namespace { // MD_prof nodes have the following layout @@ -196,6 +184,4 @@ return extractProfTotalWeight(I.getMetadata(LLVMContext::MD_prof), TotalVal); } -uint32_t getLikelyBranchWeight() { return LikelyBranchWeight; } - } // namespace llvm diff --git a/llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp b/llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp --- a/llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp +++ b/llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp @@ -41,7 +41,7 @@ getBranchWeight(Intrinsic::ID IntrinsicID, CallInst *CI, int BranchCount) { if (IntrinsicID == Intrinsic::expect) { // __builtin_expect - return std::make_tuple(getLikelyBranchWeight(), 1); + return std::make_tuple(1, 0); } else { // __builtin_expect_with_probability assert(CI->getNumOperands() >= 3 && diff --git a/llvm/lib/Transforms/Utils/MisExpect.cpp b/llvm/lib/Transforms/Utils/MisExpect.cpp --- a/llvm/lib/Transforms/Utils/MisExpect.cpp +++ b/llvm/lib/Transforms/Utils/MisExpect.cpp @@ -30,6 +30,7 @@ #include "llvm/Transforms/Utils/MisExpect.h" #include "llvm/ADT/Twine.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/Instruction.h" @@ -188,6 +189,7 @@ SmallVector ExpectedWeights; if (!extractBranchWeights(I, ExpectedWeights)) return; + BranchProbabilityInfo::normalizeLikelyWeights(ExpectedWeights); verifyMisExpect(I, RealWeights, ExpectedWeights); } @@ -196,6 +198,7 @@ SmallVector RealWeights; if (!extractBranchWeights(I, RealWeights)) return; + BranchProbabilityInfo::normalizeLikelyWeights(RealWeights); verifyMisExpect(I, RealWeights, ExpectedWeights); } diff --git a/llvm/test/Transforms/CodeExtractor/PartialInlinePGOMultiRegion.ll b/llvm/test/Transforms/CodeExtractor/PartialInlinePGOMultiRegion.ll --- a/llvm/test/Transforms/CodeExtractor/PartialInlinePGOMultiRegion.ll +++ b/llvm/test/Transforms/CodeExtractor/PartialInlinePGOMultiRegion.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=partial-inliner -min-block-execution=1 -skip-partial-inlining-cost-analysis < %s | FileCheck %s +; RUN: opt -S -passes=partial-inliner -min-block-execution=100 -skip-partial-inlining-cost-analysis < %s | FileCheck %s ; Require a dummy block (if.then.b) as successor to if.then due to PI requirement ; of region containing more than one BB. define signext i32 @bar(i32 signext %value, i32 signext %ub) #0 !prof !30 { @@ -169,6 +169,6 @@ !27 = !{i32 999990, i64 1, i32 4} !28 = !{i32 999999, i64 1, i32 4} !29 = !{!"clang version 6.0.0 (123456)"} -!30 = !{!"function_entry_count", i64 2} +!30 = !{!"function_entry_count", i64 100} !31 = !{!"branch_weights", i32 100, i32 1} !32 = !{!"branch_weights", i32 0, i32 100} diff --git a/llvm/test/Transforms/CodeExtractor/PartialInlinePGORegion.ll b/llvm/test/Transforms/CodeExtractor/PartialInlinePGORegion.ll --- a/llvm/test/Transforms/CodeExtractor/PartialInlinePGORegion.ll +++ b/llvm/test/Transforms/CodeExtractor/PartialInlinePGORegion.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes=partial-inliner -min-block-execution=1 -skip-partial-inlining-cost-analysis < %s | FileCheck %s +; RUN: opt -S -passes=partial-inliner -min-block-execution=100 -skip-partial-inlining-cost-analysis < %s | FileCheck %s ; Require a dummy block (if.then.b) as successor to if.then due to PI requirement ; of region containing more than one BB. define signext i32 @bar(i32 signext %value, i32 signext %ub) #0 !prof !30 { @@ -114,6 +114,6 @@ !27 = !{i32 999990, i64 1, i32 4} !28 = !{i32 999999, i64 1, i32 4} !29 = !{!"clang version 6.0.0 (123456)"} -!30 = !{!"function_entry_count", i64 2} +!30 = !{!"function_entry_count", i64 100} !31 = !{!"branch_weights", i32 100, i32 1} !32 = !{!"branch_weights", i32 0, i32 100} diff --git a/llvm/test/Transforms/LowerExpectIntrinsic/basic.ll b/llvm/test/Transforms/LowerExpectIntrinsic/basic.ll --- a/llvm/test/Transforms/LowerExpectIntrinsic/basic.ll +++ b/llvm/test/Transforms/LowerExpectIntrinsic/basic.ll @@ -284,7 +284,7 @@ declare i1 @llvm.expect.i1(i1, i1) nounwind readnone -; CHECK: !0 = !{!"branch_weights", i32 2000, i32 1} -; CHECK: !1 = !{!"branch_weights", i32 1, i32 2000} -; CHECK: !2 = !{!"branch_weights", i32 1, i32 1, i32 2000} -; CHECK: !3 = !{!"branch_weights", i32 2000, i32 1, i32 1} +; CHECK: !0 = !{!"branch_weights", i32 1, i32 0} +; CHECK: !1 = !{!"branch_weights", i32 0, i32 1} +; CHECK: !2 = !{!"branch_weights", i32 0, i32 0, i32 1} +; CHECK: !3 = !{!"branch_weights", i32 1, i32 0, i32 0} diff --git a/llvm/test/Transforms/LowerExpectIntrinsic/expect_nonboolean.ll b/llvm/test/Transforms/LowerExpectIntrinsic/expect_nonboolean.ll --- a/llvm/test/Transforms/LowerExpectIntrinsic/expect_nonboolean.ll +++ b/llvm/test/Transforms/LowerExpectIntrinsic/expect_nonboolean.ll @@ -99,6 +99,6 @@ !0 = !{i32 1, !"wchar_size", i32 4} !1 = !{!"clang version 5.0.0 (trunk 304373)"} -; CHECK: [[LIKELY]] = !{!"branch_weights", i32 2000, i32 1} -; CHECK: [[UNLIKELY]] = !{!"branch_weights", i32 1, i32 2000} +; CHECK: [[LIKELY]] = !{!"branch_weights", i32 1, i32 0} +; CHECK: [[UNLIKELY]] = !{!"branch_weights", i32 0, i32 1} diff --git a/llvm/test/Transforms/LowerExpectIntrinsic/phi_merge.ll b/llvm/test/Transforms/LowerExpectIntrinsic/phi_merge.ll --- a/llvm/test/Transforms/LowerExpectIntrinsic/phi_merge.ll +++ b/llvm/test/Transforms/LowerExpectIntrinsic/phi_merge.ll @@ -352,5 +352,5 @@ !llvm.ident = !{!0} !0 = !{!"clang version 5.0.0 (trunk 302965)"} -; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1} -; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000} +; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 1, i32 0} +; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 0, i32 1} diff --git a/llvm/test/Transforms/LowerExpectIntrinsic/phi_or.ll b/llvm/test/Transforms/LowerExpectIntrinsic/phi_or.ll --- a/llvm/test/Transforms/LowerExpectIntrinsic/phi_or.ll +++ b/llvm/test/Transforms/LowerExpectIntrinsic/phi_or.ll @@ -99,5 +99,5 @@ !0 = !{!"clang version 5.0.0 (trunk 302965)"} -; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 2000, i32 1} -; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 1, i32 2000} +; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 1, i32 0} +; CHECK: [[WEIGHT2]] = !{!"branch_weights", i32 0, i32 1} diff --git a/llvm/test/Transforms/LowerExpectIntrinsic/phi_tern.ll b/llvm/test/Transforms/LowerExpectIntrinsic/phi_tern.ll --- a/llvm/test/Transforms/LowerExpectIntrinsic/phi_tern.ll +++ b/llvm/test/Transforms/LowerExpectIntrinsic/phi_tern.ll @@ -53,4 +53,4 @@ !0 = !{!"clang version 5.0.0 (trunk 302965)"} -; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 1, i32 2000} +; CHECK: [[WEIGHT]] = !{!"branch_weights", i32 0, i32 1} diff --git a/llvm/test/Transforms/LowerExpectIntrinsic/phi_unexpect.ll b/llvm/test/Transforms/LowerExpectIntrinsic/phi_unexpect.ll --- a/llvm/test/Transforms/LowerExpectIntrinsic/phi_unexpect.ll +++ b/llvm/test/Transforms/LowerExpectIntrinsic/phi_unexpect.ll @@ -1,4 +1,4 @@ -; RUN: opt -S -passes='function(lower-expect),strip-dead-prototypes' -likely-branch-weight=2147483647 < %s | FileCheck %s +; RUN: opt -S -passes='function(lower-expect),strip-dead-prototypes' < %s | FileCheck %s ; The C case ; if (__builtin_expect_with_probability(((a0 == 1) || (a1 == 1) || (a2 == 1)), 1, 0)) @@ -21,7 +21,7 @@ ; CHECK: block1: ; CHECK-NOT: prof ; CHECK: block3: -; CHECK: br i1 %tobool, label %block4, label %block5, !prof !0 +; CHECK: br i1 %tobool, label %block4, label %block5, !prof [[PROF_TEST1:![0-9]+]] define void @test1_expect_1(i8 %a0, i8 %a1, i8 %a2) { block0: %c0 = icmp eq i8 %a0, 1 @@ -58,7 +58,7 @@ ; CHECK: block1: ; CHECK-NOT: prof ; CHECK: block3: -; CHECK: br i1 %tobool, label %block4, label %block5, !prof !0 +; CHECK: br i1 %tobool, label %block4, label %block5, !prof [[PROF_MAX:![0-9]+]] define void @test2_expect_with_prob_1_1(i8 %a0, i8 %a1, i8 %a2) { block0: %c0 = icmp eq i8 %a0, 1 @@ -95,7 +95,7 @@ ; CHECK: block1: ; CHECK-NOT: prof ; CHECK: block3: -; CHECK: br i1 %tobool, label %block4, label %block5, !prof !0 +; CHECK: br i1 %tobool, label %block4, label %block5, !prof [[PROF_MAX]] define void @test3_expect_with_prob_0_0(i8 %a0, i8 %a1, i8 %a2) { block0: %c0 = icmp eq i8 %a0, 1 @@ -127,11 +127,11 @@ ; CHECK-LABEL: @test4_expect_0( ; CHECK: block0: -; CHECK: br i1 %c0, label %block3, label %block1, !prof !1 +; CHECK: br i1 %c0, label %block3, label %block1, !prof [[PROF_TEST4:![0-9]+]] ; CHECK: block1: -; CHECK: br i1 %c1, label %block3, label %block2, !prof !1 +; CHECK: br i1 %c1, label %block3, label %block2, !prof [[PROF_TEST4]] ; CHECK: block3: -; CHECK: br i1 %tobool, label %block4, label %block5, !prof !1 +; CHECK: br i1 %tobool, label %block4, label %block5, !prof [[PROF_TEST4]] define void @test4_expect_0(i8 %a0, i8 %a1, i8 %a2) { block0: %c0 = icmp eq i8 %a0, 1 @@ -164,11 +164,11 @@ ; should have exactly the same behavior as test4 ; CHECK-LABEL: @test5_expect_with_prob_1_0( ; CHECK: block0: -; CHECK: br i1 %c0, label %block3, label %block1, !prof !1 +; CHECK: br i1 %c0, label %block3, label %block1, !prof [[PROF_MIN:![0-9]+]] ; CHECK: block1: -; CHECK: br i1 %c1, label %block3, label %block2, !prof !1 +; CHECK: br i1 %c1, label %block3, label %block2, !prof [[PROF_MIN]] ; CHECK: block3: -; CHECK: br i1 %tobool, label %block4, label %block5, !prof !1 +; CHECK: br i1 %tobool, label %block4, label %block5, !prof [[PROF_MIN]] define void @test5_expect_with_prob_1_0(i8 %a0, i8 %a1, i8 %a2) { block0: %c0 = icmp eq i8 %a0, 1 @@ -201,11 +201,11 @@ ; should have exactly the same behavior as test4 ; CHECK-LABEL: @test6_expect_with_prob_0_1( ; CHECK: block0: -; CHECK: br i1 %c0, label %block3, label %block1, !prof !1 +; CHECK: br i1 %c0, label %block3, label %block1, !prof [[PROF_MIN]] ; CHECK: block1: -; CHECK: br i1 %c1, label %block3, label %block2, !prof !1 +; CHECK: br i1 %c1, label %block3, label %block2, !prof [[PROF_MIN]] ; CHECK: block3: -; CHECK: br i1 %tobool, label %block4, label %block5, !prof !1 +; CHECK: br i1 %tobool, label %block4, label %block5, !prof [[PROF_MIN]] define void @test6_expect_with_prob_0_1(i8 %a0, i8 %a1, i8 %a2) { block0: %c0 = icmp eq i8 %a0, 1 @@ -235,5 +235,7 @@ ret void } -; CHECK: !0 = !{!"branch_weights", i32 2147483647, i32 1} -; CHECK: !1 = !{!"branch_weights", i32 1, i32 2147483647} +; CHECK: [[PROF_TEST1]] = !{!"branch_weights", i32 1, i32 0} +; CHECK: [[PROF_MAX]] = !{!"branch_weights", i32 2147483647, i32 1} +; CHECK: [[PROF_TEST4]] = !{!"branch_weights", i32 0, i32 1} +; CHECK: [[PROF_MIN]] = !{!"branch_weights", i32 1, i32 2147483647} diff --git a/llvm/test/Transforms/SampleProfile/profile-inference.ll b/llvm/test/Transforms/SampleProfile/profile-inference.ll --- a/llvm/test/Transforms/SampleProfile/profile-inference.ll +++ b/llvm/test/Transforms/SampleProfile/profile-inference.ll @@ -198,27 +198,27 @@ b4: call void @llvm.pseudoprobe(i64 -907520326213521421, i64 4, i32 0, i64 -1) br i1 %cmp, label %b5, label %b6 -; CHECK: edge b4 -> b5 probability is 0x80000000 / 0x80000000 = 100.00% -; CHECK: edge b4 -> b6 probability is 0x00000000 / 0x80000000 = 0.00% +; CHECK: edge b4 -> b5 probability is 0x7fef9fcb / 0x80000000 = 99.95% +; CHECK: edge b4 -> b6 probability is 0x00106035 / 0x80000000 = 0.05% ; CHECK2: - b4: float = {{.*}}, int = {{.*}}, count = 5992 b5: call void @llvm.pseudoprobe(i64 -907520326213521421, i64 5, i32 0, i64 -1) br label %b7 ; CHECK: edge b5 -> b7 probability is 0x80000000 / 0x80000000 = 100.00% -; CHECK2: - b5: float = {{.*}}, int = {{.*}}, count = 5992 +; CHECK2: - b5: float = {{.*}}, int = {{.*}}, count = 5989 b6: call void @llvm.pseudoprobe(i64 -907520326213521421, i64 6, i32 0, i64 -1) br label %b8 ; CHECK: edge b6 -> b8 probability is 0x80000000 / 0x80000000 = 100.00% -; CHECK2: - b6: float = {{.*}}, int = {{.*}}, count = 0 +; CHECK2: - b6: float = {{.*}}, int = {{.*}}, count = 3 b7: call void @llvm.pseudoprobe(i64 -907520326213521421, i64 7, i32 0, i64 -1) br label %b8 ; CHECK: edge b7 -> b8 probability is 0x80000000 / 0x80000000 = 100.00% -; CHECK2: - b7: float = {{.*}}, int = {{.*}}, count = 5992 +; CHECK2: - b7: float = {{.*}}, int = {{.*}}, count = 5989 b8: call void @llvm.pseudoprobe(i64 -907520326213521421, i64 8, i32 0, i64 -1)