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") Index: clang/include/clang/Basic/DiagnosticSemaKinds.td =================================================================== --- clang/include/clang/Basic/DiagnosticSemaKinds.td +++ clang/include/clang/Basic/DiagnosticSemaKinds.td @@ -10773,4 +10773,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/lib/CodeGen/CGBuiltin.cpp =================================================================== --- clang/lib/CodeGen/CGBuiltin.cpp +++ clang/lib/CodeGen/CGBuiltin.cpp @@ -2187,6 +2187,24 @@ 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)); + Value *Confidence = EmitScalarExpr(E->getArg(2)); + // Don't generate llvm.expect.with.probability on -O0 as the backend + // won't use it for anything. + // Note, we still IRGen ExpectedValue 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/lib/Sema/SemaChecking.cpp =================================================================== --- clang/lib/Sema/SemaChecking.cpp +++ clang/lib/Sema/SemaChecking.cpp @@ -1795,6 +1795,27 @@ 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] + llvm::APFloat Confidence(0.0); + const Expr *ProbArg = TheCall->getArg(2); + if (ProbArg->EvaluateAsFloat(Confidence, Context)) { + double P = Confidence.convertToDouble(); + if (P < 0.0 || P > 1.0) { + Diag(ProbArg->getLocStart(), diag::err_probability_out_of_range) + << ProbArg->getSourceRange(); + return ExprError(); + } + } else { + Diag(ProbArg->getLocStart(), diag::err_probability_not_constant_float) + << ProbArg->getSourceRange(); + return ExprError(); + } + break; + } case Builtin::BI__builtin_preserve_access_index: if (SemaBuiltinPreserveAI(*this, TheCall)) return ExprError(); 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/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: llvm/include/llvm/IR/Intrinsics.td =================================================================== --- llvm/include/llvm/IR/Intrinsics.td +++ llvm/include/llvm/IR/Intrinsics.td @@ -797,6 +797,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/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 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(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(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 Weights(n + 1, UnlikelyBranchWeight); + std::pair WeightNums = + setBranchWeight(Fn->getIntrinsicID(), CI, n + 1); + uint32_t LikelyBranchWeightVal = WeightNums.first; + uint32_t UnlikelyBranchWeightVal = WeightNums.second; + + SmallVector 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 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 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: