LukeZhuang updated this revision to Diff 265598.
LukeZhuang added a comment.
**Updated: 05/21/2020**
1. add assertion after evaluate probability
2. remove value dependent check in SemaChecking
3. add test case handling value-dependent template
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D79830/new/
https://reviews.llvm.org/D79830
Files:
clang/include/clang/Basic/Builtins.def
clang/include/clang/Basic/DiagnosticSemaKinds.td
clang/lib/CodeGen/CGBuiltin.cpp
clang/lib/Sema/SemaChecking.cpp
clang/test/CodeGen/builtin-expect-with-probability-switch.c
clang/test/CodeGen/builtin-expect-with-probability-template.cpp
clang/test/CodeGen/builtin-expect-with-probability.c
llvm/docs/BranchWeightMetadata.rst
llvm/include/llvm/IR/Intrinsics.td
llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
Index: llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
+++ llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
@@ -55,13 +55,32 @@
"unlikely-branch-weight", cl::Hidden, cl::init(1),
cl::desc("Weight of the branch unlikely to be taken (default = 1)"));
+std::pair<uint32_t, uint32_t> setBranchWeight(Intrinsic::ID IntrinsicID,
+ CallInst *CI, int BranchCount) {
+ if (IntrinsicID == Intrinsic::expect) {
+ // __builtin_expect
+ return {LikelyBranchWeight, UnlikelyBranchWeight};
+ } else {
+ // __builtin_expect_with_probability
+ assert(CI->getNumOperands() >= 3 &&
+ "expect with probability must have 3 arguments");
+ ConstantFP *Confidence = dyn_cast<ConstantFP>(CI->getArgOperand(2));
+ double TrueProb = Confidence->getValueAPF().convertToDouble();
+ double FalseProb = (1.0 - TrueProb) / (BranchCount - 1);
+ uint32_t LikelyBW = ceil((TrueProb * (double)(INT32_MAX - 1)) + 1.0);
+ uint32_t UnlikelyBW = ceil((FalseProb * (double)(INT32_MAX - 1)) + 1.0);
+ return {LikelyBW, UnlikelyBW};
+ }
+}
+
static bool handleSwitchExpect(SwitchInst &SI) {
CallInst *CI = dyn_cast<CallInst>(SI.getCondition());
if (!CI)
return false;
Function *Fn = CI->getCalledFunction();
- if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect)
+ if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&
+ Fn->getIntrinsicID() != Intrinsic::expect_with_probability))
return false;
Value *ArgValue = CI->getArgOperand(0);
@@ -71,15 +90,20 @@
SwitchInst::CaseHandle Case = *SI.findCaseValue(ExpectedValue);
unsigned n = SI.getNumCases(); // +1 for default case.
- SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeight);
+ std::pair<uint32_t, uint32_t> WeightNums =
+ setBranchWeight(Fn->getIntrinsicID(), CI, n + 1);
+ uint32_t LikelyBranchWeightVal = WeightNums.first;
+ uint32_t UnlikelyBranchWeightVal = WeightNums.second;
+
+ SmallVector<uint32_t, 16> Weights(n + 1, UnlikelyBranchWeightVal);
uint64_t Index = (Case == *SI.case_default()) ? 0 : Case.getCaseIndex() + 1;
- Weights[Index] = LikelyBranchWeight;
+ Weights[Index] = LikelyBranchWeightVal;
- SI.setMetadata(
- LLVMContext::MD_misexpect,
- MDBuilder(CI->getContext())
- .createMisExpect(Index, LikelyBranchWeight, UnlikelyBranchWeight));
+ SI.setMetadata(LLVMContext::MD_misexpect,
+ MDBuilder(CI->getContext())
+ .createMisExpect(Index, LikelyBranchWeightVal,
+ UnlikelyBranchWeightVal));
SI.setCondition(ArgValue);
misexpect::checkFrontendInstrumentation(SI);
@@ -223,15 +247,19 @@
return true;
return false;
};
+ std::pair<uint32_t, uint32_t> WeightNums = setBranchWeight(
+ Expect->getCalledFunction()->getIntrinsicID(), Expect, 2);
+ uint32_t LikelyBranchWeightVal = WeightNums.first;
+ uint32_t UnlikelyBranchWeightVal = WeightNums.second;
if (IsOpndComingFromSuccessor(BI->getSuccessor(1)))
- BI->setMetadata(
- LLVMContext::MD_prof,
- MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight));
+ BI->setMetadata(LLVMContext::MD_prof,
+ MDB.createBranchWeights(LikelyBranchWeightVal,
+ UnlikelyBranchWeightVal));
else if (IsOpndComingFromSuccessor(BI->getSuccessor(0)))
- BI->setMetadata(
- LLVMContext::MD_prof,
- MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight));
+ BI->setMetadata(LLVMContext::MD_prof,
+ MDB.createBranchWeights(UnlikelyBranchWeightVal,
+ LikelyBranchWeightVal));
}
}
@@ -277,7 +305,8 @@
}
Function *Fn = CI->getCalledFunction();
- if (!Fn || Fn->getIntrinsicID() != Intrinsic::expect)
+ if (!Fn || (Fn->getIntrinsicID() != Intrinsic::expect &&
+ Fn->getIntrinsicID() != Intrinsic::expect_with_probability))
return false;
Value *ArgValue = CI->getArgOperand(0);
@@ -289,13 +318,22 @@
MDNode *Node;
MDNode *ExpNode;
+ std::pair<uint32_t, uint32_t> WeightNums =
+ setBranchWeight(Fn->getIntrinsicID(), CI, 2);
+ uint32_t LikelyBranchWeightVal = WeightNums.first;
+ uint32_t UnlikelyBranchWeightVal = WeightNums.second;
+
if ((ExpectedValue->getZExtValue() == ValueComparedTo) ==
(Predicate == CmpInst::ICMP_EQ)) {
- Node = MDB.createBranchWeights(LikelyBranchWeight, UnlikelyBranchWeight);
- ExpNode = MDB.createMisExpect(0, LikelyBranchWeight, UnlikelyBranchWeight);
+ Node =
+ MDB.createBranchWeights(LikelyBranchWeightVal, UnlikelyBranchWeightVal);
+ ExpNode =
+ MDB.createMisExpect(0, LikelyBranchWeightVal, UnlikelyBranchWeightVal);
} else {
- Node = MDB.createBranchWeights(UnlikelyBranchWeight, LikelyBranchWeight);
- ExpNode = MDB.createMisExpect(1, LikelyBranchWeight, UnlikelyBranchWeight);
+ Node =
+ MDB.createBranchWeights(UnlikelyBranchWeightVal, LikelyBranchWeightVal);
+ ExpNode =
+ MDB.createMisExpect(1, LikelyBranchWeightVal, UnlikelyBranchWeightVal);
}
BSI.setMetadata(LLVMContext::MD_misexpect, ExpNode);
@@ -347,7 +385,8 @@
}
Function *Fn = CI->getCalledFunction();
- if (Fn && Fn->getIntrinsicID() == Intrinsic::expect) {
+ if (Fn && (Fn->getIntrinsicID() == Intrinsic::expect ||
+ Fn->getIntrinsicID() == Intrinsic::expect_with_probability)) {
// Before erasing the llvm.expect, walk backward to find
// phi that define llvm.expect's first arg, and
// infer branch probability:
Index: llvm/include/llvm/IR/Intrinsics.td
===================================================================
--- llvm/include/llvm/IR/Intrinsics.td
+++ llvm/include/llvm/IR/Intrinsics.td
@@ -798,6 +798,10 @@
def int_expect : Intrinsic<[llvm_anyint_ty],
[LLVMMatchType<0>, LLVMMatchType<0>], [IntrNoMem, IntrWillReturn]>;
+def int_expect_with_probability : Intrinsic<[llvm_anyint_ty],
+ [LLVMMatchType<0>, LLVMMatchType<0>, llvm_double_ty],
+ [IntrNoMem, IntrWillReturn]>;
+
//===-------------------- Bit Manipulation Intrinsics ---------------------===//
//
Index: llvm/docs/BranchWeightMetadata.rst
===================================================================
--- llvm/docs/BranchWeightMetadata.rst
+++ llvm/docs/BranchWeightMetadata.rst
@@ -15,7 +15,7 @@
"branch_weights". Number of operators depends on the terminator type.
Branch weights might be fetch from the profiling file, or generated based on
-`__builtin_expect`_ instruction.
+`__builtin_expect`_ and `__builtin_expect_with_probability`_ instruction.
All weights are represented as an unsigned 32-bit values, where higher value
indicates greater chance to be taken.
@@ -123,6 +123,47 @@
case 5: // This case is likely to be taken.
}
+.. _\__builtin_expect_with_probability:
+
+Built-in ``expect.with.probability`` Instructions
+=================================================
+
+``__builtin_expect_with_probability(long exp, long c, double probability)`` has
+the same semantics as ``__builtin_expect``, but the caller provides the
+probability that ``exp == c``. The last argument ``probability`` must be
+constant floating-point expression and be in the range [0.0, 1.0] inclusive.
+The usage is also similar as ``__builtin_expect``, for example:
+
+``if`` statement
+^^^^^^^^^^^^^^^^
+
+If the expect comparison value ``c`` is equal to 1(true), and probability
+value ``probability`` is set to 0.8, that means the probability of condition
+to be true is 80% while that of false is 20%.
+
+.. code-block:: c++
+
+ if (__builtin_expect_with_probability(x > 0, 1, 0.8)) {
+ // This block is likely to be taken with probability 80%.
+ }
+
+``switch`` statement
+^^^^^^^^^^^^^^^^^^^^
+
+This is basically the same as ``switch`` statement in ``__builtin_expect``.
+The probability that ``exp`` is equal to the expect value is given in
+the third argument ``probability``, while the probability of other value is
+the average of remaining probability(``1.0 - probability``). For example:
+
+.. code-block:: c++
+
+ switch (__builtin_expect_with_probability(x, 5, 0.7)) {
+ default: break; // Take this case with probability 10%
+ case 0: // Take this case with probability 10%
+ case 3: // Take this case with probability 10%
+ case 5: // This case is likely to be taken with probability 70%
+ }
+
CFG Modifications
=================
Index: clang/test/CodeGen/builtin-expect-with-probability.c
===================================================================
--- /dev/null
+++ clang/test/CodeGen/builtin-expect-with-probability.c
@@ -0,0 +1,10 @@
+// RUN: %clang_cc1 -emit-llvm -o - %s -O1 | FileCheck %s
+
+int expect_taken(int x) {
+ // CHECK: !{{[0-9]+}} = !{!"branch_weights", i32 1932735283, i32 214748366}
+
+ if (__builtin_expect_with_probability(x == 100, 1, 0.9)) {
+ return 0;
+ }
+ return x;
+}
Index: clang/test/CodeGen/builtin-expect-with-probability-template.cpp
===================================================================
--- /dev/null
+++ clang/test/CodeGen/builtin-expect-with-probability-template.cpp
@@ -0,0 +1,20 @@
+// RUN: %clang_cc1 -emit-llvm -o - %s -O1 | FileCheck %s
+extern int global;
+
+struct S {
+ static constexpr int prob = 1;
+};
+
+template<typename T>
+int expect_taken(int x) {
+// CHECK: !{{[0-9]+}} = !{!"branch_weights", i32 2147483647, i32 1}
+
+ if (__builtin_expect_with_probability (x == 100, 1, T::prob)) {
+ return 0;
+ }
+ return x;
+}
+
+void f() {
+ expect_taken<S>(global);
+}
Index: clang/test/CodeGen/builtin-expect-with-probability-switch.c
===================================================================
--- /dev/null
+++ clang/test/CodeGen/builtin-expect-with-probability-switch.c
@@ -0,0 +1,18 @@
+// RUN: %clang_cc1 -emit-llvm -o - %s -O1 | FileCheck %s
+
+int expect_taken(int x) {
+ // CHECK: !{{[0-9]+}} = !{!"branch_weights", i32 107374184, i32 107374184, i32 1717986918, i32 107374184, i32 107374184}
+ switch (__builtin_expect_with_probability(x, 1, 0.8)) {
+ case 0:
+ x = x + 0;
+ case 1:
+ x = x + 1;
+ case 2:
+ x = x + 2;
+ case 5:
+ x = x + 5;
+ default:
+ x = x + 6;
+ }
+ return x;
+}
Index: clang/lib/Sema/SemaChecking.cpp
===================================================================
--- clang/lib/Sema/SemaChecking.cpp
+++ clang/lib/Sema/SemaChecking.cpp
@@ -1796,6 +1796,34 @@
TheCall->setType(Context.IntTy);
break;
}
+ case Builtin::BI__builtin_expect_with_probability: {
+ // We first want to ensure we are called with 3 arguments
+ if (checkArgCount(*this, TheCall, 3))
+ return ExprError();
+ // then check probability is constant float in range [0.0, 1.0]
+ const Expr *ProbArg = TheCall->getArg(2);
+ SmallVector<PartialDiagnosticAt, 8> Notes;
+ Expr::EvalResult Eval;
+ Eval.Diag = &Notes;
+ if ((!ProbArg->EvaluateAsConstantExpr(Eval, Expr::EvaluateForCodeGen,
+ Context)) ||
+ !Eval.Val.isFloat()) {
+ Diag(ProbArg->getLocStart(), diag::err_probability_not_constant_float)
+ << ProbArg->getSourceRange();
+ for (const PartialDiagnosticAt &PDiag : Notes)
+ Diag(PDiag.first, PDiag.second);
+ return ExprError();
+ } else {
+ llvm::APFloat Probability = Eval.Val.getFloat();
+ if (!(Probability >= llvm::APFloat(0.0) ||
+ Probability <= llvm::APFloat(1.0))) {
+ Diag(ProbArg->getLocStart(), diag::err_probability_out_of_range)
+ << ProbArg->getSourceRange();
+ return ExprError();
+ }
+ }
+ break;
+ }
case Builtin::BI__builtin_preserve_access_index:
if (SemaBuiltinPreserveAI(*this, TheCall))
return ExprError();
Index: clang/lib/CodeGen/CGBuiltin.cpp
===================================================================
--- clang/lib/CodeGen/CGBuiltin.cpp
+++ clang/lib/CodeGen/CGBuiltin.cpp
@@ -2187,6 +2187,31 @@
Builder.CreateCall(FnExpect, {ArgValue, ExpectedValue}, "expval");
return RValue::get(Result);
}
+ case Builtin::BI__builtin_expect_with_probability: {
+ Value *ArgValue = EmitScalarExpr(E->getArg(0));
+ llvm::Type *ArgType = ArgValue->getType();
+
+ Value *ExpectedValue = EmitScalarExpr(E->getArg(1));
+ llvm::APFloat Probability(0.0);
+ const Expr *ProbArg = E->getArg(2);
+ bool EvalSucceed = ProbArg->EvaluateAsFloat(Probability,
+ CGM.getContext(), Expr::SideEffectsKind::SE_AllowSideEffects);
+ assert(EvalSucceed == true);
+ llvm::Type *Ty = ConvertType(ProbArg->getType());
+ Constant *Confidence = ConstantFP::get(Ty, Probability);
+ // Don't generate llvm.expect.with.probability on -O0 as the backend
+ // won't use it for anything.
+ // Note, we still IRGen ExpectedValue and Probability because
+ // it could have side-effects.
+ if (CGM.getCodeGenOpts().OptimizationLevel == 0)
+ return RValue::get(ArgValue);
+
+ Value *FnExpect =
+ CGM.getIntrinsic(Intrinsic::expect_with_probability, ArgType);
+ Value *Result = Builder.CreateCall(
+ FnExpect, {ArgValue, ExpectedValue, Confidence}, "expval");
+ return RValue::get(Result);
+ }
case Builtin::BI__builtin_assume_aligned: {
const Expr *Ptr = E->getArg(0);
Value *PtrValue = EmitScalarExpr(Ptr);
Index: clang/include/clang/Basic/DiagnosticSemaKinds.td
===================================================================
--- clang/include/clang/Basic/DiagnosticSemaKinds.td
+++ clang/include/clang/Basic/DiagnosticSemaKinds.td
@@ -10778,4 +10778,12 @@
"have a bit size of at least %select{2|1}0">;
def err_ext_int_max_size : Error<"%select{signed|unsigned}0 _ExtInt of bit "
"sizes greater than %1 not supported">;
+
+// errors of expect.with.probability
+def err_probability_not_constant_float : Error<
+ "probability of __builtin_expect_with_probability must be constant "
+ "floating-point expression">;
+def err_probability_out_of_range : Error<
+ "probability of __builtin_expect_with_probability is outside the "
+ "range [0.0, 1.0]">;
} // end of sema component.
Index: clang/include/clang/Basic/Builtins.def
===================================================================
--- clang/include/clang/Basic/Builtins.def
+++ clang/include/clang/Basic/Builtins.def
@@ -564,6 +564,7 @@
BUILTIN(__builtin_unpredictable, "LiLi" , "nc")
BUILTIN(__builtin_expect, "LiLiLi" , "nc")
+BUILTIN(__builtin_expect_with_probability, "LiLiLid" , "nc")
BUILTIN(__builtin_prefetch, "vvC*.", "nc")
BUILTIN(__builtin_readcyclecounter, "ULLi", "n")
BUILTIN(__builtin_trap, "v", "nr")
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
