Add support of __builtin_expect_with_probability

[LukeZhuang]

Summary

Add a new builtin-function __builtin_expect_with_probability and intrinsic llvm.expect.with.probability.
The interface is __builtin_expect_with_probability(long expr, long expected, double probability).
It is mainly the same as __builtin_expect besides one more argument indicating the probability of expression equal to expected value. The probability should be a constant floating-point expression and be in range [0.0, 1.0] inclusive.
It is similar to builtin-expect-with-probability function in GCC built-in functions.

[lebedev.ri]

Thanks for working on this.
Please upload patch with full context.

[erichkeane]

Type checking/value checking for this should happen during Sema, not codegen.

clang/lib/CodeGen/CGBuiltin.cpp

2049

This check should be able to be done during Sema.

2056

Same as above, we shouldn't do this during Codegen.

[RKSimon]

Add a description in our documentation?

[davidxl]

Is it possible to overload __builtin_expect(..)?

[erichkeane]

In D79830#2034400, @davidxl wrote:

Is it possible to overload __builtin_expect(..)?

No OP, but...
First, Overloading builtins is a bit of a pain. You end up having to do custom type checking.
Second, GCC already made the decision to do a separate name. I'd want us to match them unless we have a really good reason not to.

[xbolva00]

In D79830#2034380, @RKSimon wrote:

Add a description in our documentation?

And Ideally add a note to release notes too..

[LukeZhuang]

In D79830#2033367, @lebedev.ri wrote:

Thanks for working on this.
Please upload patch with full context.

Hi, sorry but I'm not sure what does full context means, is that means I need to show more lines(for example 10 lines) when generating patch or show the whole function? Thank you!

[lebedev.ri]

In D79830#2034779, @LukeZhuang wrote:

In D79830#2033367, @lebedev.ri wrote:

Thanks for working on this.
Please upload patch with full context.

Hi, sorry but I'm not sure what does full context means, is that means I need to show more lines(for example 10 lines) when generating patch or show the whole function? Thank you!

git diff -p -U99999

[erichkeane]

In D79830#2034779, @LukeZhuang wrote:

In D79830#2033367, @lebedev.ri wrote:

Thanks for working on this.
Please upload patch with full context.

Hi, sorry but I'm not sure what does full context means, is that means I need to show more lines(for example 10 lines) when generating patch or show the whole function? Thank you!

See https://llvm.org/docs/Phabricator.html particularly https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

[LukeZhuang]

1. fix code format
2. move probability type and value check from codegen to semacheck
3. update patch with full context

[LukeZhuang]

In D79830#2034796, @lebedev.ri wrote:

In D79830#2034779, @LukeZhuang wrote:

In D79830#2033367, @lebedev.ri wrote:

Thanks for working on this.
Please upload patch with full context.

Hi, sorry but I'm not sure what does full context means, is that means I need to show more lines(for example 10 lines) when generating patch or show the whole function? Thank you!

git diff -p -U99999

Thanks! It is updated in lastest revision

[LukeZhuang]

clang/lib/CodeGen/CGBuiltin.cpp

2049

fixed in the lastest change

2056

fixed in the lastest change

[rsmith]

clang/include/clang/Basic/Builtins.def

567

I assume we don't have any equivalent of the I flag to require a floating-point constant expression? If not, it's probably not worth adding that if this builtin would be the only user of it.

clang/lib/CodeGen/CGBuiltin.cpp

2195

If the intrinsic expects a ConstantFP value, this isn't enough to guarantee that you get one (the set of cases that we fold to constants during expression emission is much smaller than the set of cases we can constant-evaluate). You should run the constant evaluator first, to produce an APFloat, then emit that value as a constant. (Optionally you can form a ConstantExpr as part of the check in Sema and store the value in that object rather than recomputing it here.)

clang/lib/Sema/SemaChecking.cpp

1806

What rules should be applied here? Do we just want to allow anything that we can evaluate (which might change over time), or do we want to use the underlying language's notion of floating-point constant expressions, if it has them?

1807

Converting to a host double here seems suspicious and unnecessary: can you form a suitable APFloat representation of 1.0 and 0.0 instead, and compare to those?

1808

This does not disallow NaN values. I think you want if (!(P >= 0.0 && P <= 1.0)) or equivalent instead.

[LukeZhuang]

clang/lib/CodeGen/CGBuiltin.cpp

2195

Thank you for commenting! I have a question about this. If I check this argument can be fold as constant float in Sema, why I need to check it here? Or do you mean I had better create a ConstantFP value here after constant emitting?

clang/lib/Sema/SemaChecking.cpp

1806

Thank you for commenting. I just read the llvm::Expr document and found that it just have isIntegerConstantExpr without a float-point version. Under EvaluateAsFloat it says "Return true if this is a constant which we can fold and convert to a floating point value", thus I use this function. Is there any better function to achieve this goal?

[LukeZhuang]

clang/lib/Sema/SemaChecking.cpp

1806

Hi, and I didn't find other builtin functions ever handle case like this, is there any example I could refer to?

[rsmith]

clang/lib/CodeGen/CGBuiltin.cpp

2195

EmitScalarExpr will emit arbitrary IR that evaluates the argument. If the argument isn't a simple floating-point literal, then you won't necessarily get an IR-level constant back from that. For example:

struct die {
  constexpr int sides() { return 6; }
  int roll();
} d6;
bool rolled_a_one = __builtin_expect_with_probability(d6.roll(), 1, 1.0 / d6.sides());

Here, we can evaluate 1.0 / d6.sides(), but EmitScalarExpr will emit a function call and a division, not a constant.

Instead, you could use EvaluateAsFloat here (you can assert it succeeds because you already checked that in Sema) and then directly form a ConstantFP from the APFloat result.

clang/lib/Sema/SemaChecking.cpp

1806

I think this is the first builtin (and maybe the first part of Clang) that wants to enforce that it sees a floating-point constant expression.

The right thing to do is generally to call EvaluateAsConstantExpr and check that it produces the right kind of value and doesn't generate any notes. See the code at the end of CheckConvertedConstantExpr for how to do this.

You also need to check that ProbArg is not value-dependent before you try to evaluate it; it's not meaningful to ask for the value of a value-dependent expression.

1814–1815

EvaluateAsConstantExpr will give you some notes to attach to this diagnostic to explain why the expression is non-constant.

[LukeZhuang]

updated 05/15/2020:
(1) add documents about __builtin_expect_with_probability
(2) modify SemaChecking to handle evaluate constant floating-point expression
(3) modify CGBuiltin to evaluate constant floating-point argument before passing it

[LukeZhuang]

clang/include/clang/Basic/Builtins.def

567

Seems there is currently no tag for constant floating-point

clang/lib/CodeGen/CGBuiltin.cpp

2195

Fixed in lastest patch

clang/lib/Sema/SemaChecking.cpp

1806

fixed in lastest patch

1807

fixed in lastest patch

1808

fixed in lastest patch

1814–1815

fixed in lastest patch

[erichkeane]

clang/lib/CodeGen/CGBuiltin.cpp

2197

You likely need to assert on the return value (as Richard suggested).

2202

I believe in EvaluateAsFloat you need to pass 'allow side effects', because by default it does not.

2204

Do you still need to evaluate this for side-effects even when called with O1? I think this code only evaluates side-effects in O0 mode at the moment.

clang/lib/Sema/SemaChecking.cpp

1805

Why is value-dependent an error? The expression should be able to be a template parameter. For example:

struct S {

static constexpr float value = 1.1;

};

template<typename T>
void f(bool b) {

__builtin_expect_with_probability(b, 1, T::value);

}

should work.

Additionally, in C++20(though not yet implemented in clang it seems):

template<float F>
void f(bool b) {

__builtin_expect_with_probability(b, 1, F);

}

Additionally, how about an integer type? It would seem that I should be able ot do:
template<int I>
void f(bool b) {

__builtin_expect_with_probability(b, 1, I); // probability is obviously 0 or 1

}

1812

BTW, this check should be valid (ensuring its a float), since normal conversions should happen as a part of the function call.

[LukeZhuang]

clang/lib/CodeGen/CGBuiltin.cpp

2204

Hi, sorry I am not sure about it. Since this part of code is after evaluating all three arguments(including evaluate ProbArg with allowing side effect), I think it will evaluate ProbArg with side effect whatever the optimization level is. This part of code is just early return the value of first argument ArgValue and do not generate code to backend. Do I correctly understand this? Thank you!

clang/lib/Sema/SemaChecking.cpp

1805

Hi, this code is based on Richard's suggestion that checking ProbArg is not value-dependent before evaluate. I also saw EvaluateAsFloat source code used in CGBuiltin.cpp that it firstly assert the expression is not value-dependent as following:

bool Expr::EvaluateAsFloat(APFloat &Result, const ASTContext &Ctx,
                            SideEffectsKind AllowSideEffects,
                            bool InConstantContext) const {
   assert(!isValueDependent() &&
          "Expression evaluator can't be called on a dependent expression.");

In fact I am not sure is there anything special should be done when is value-dependent. Do you have suggestions about this? Thank you!

[erichkeane]

clang/lib/CodeGen/CGBuiltin.cpp

2202

Thinking further, Since it is with constant-expressions, we might consider disallowing side effects.

2204

You're right here, I'd read the comment and skipped that ArgValue was evaluated above.

clang/lib/Sema/SemaChecking.cpp

1805

Typically in dependent cases (though this file doesn't deal with the much), we just presume the arguments are valid. The values then get checked when instantiated. Tests to show this would also be necessary.

[LukeZhuang]

clang/lib/Sema/SemaChecking.cpp

1805

Hi, is that mean I just not not need this check, and then add test case as you suggest to check it does not yield error, is that correct? Thank you!

1812

Do you mean that when customer pass an integer here and make sure this can handle? I just test this and find isFloat() returns true when this argument is constexpr int. Seems it is automatically converted here.

[erichkeane]

FYI: I'm more of a clang contributor, so I'm unable to review the LLVM code, hopefully someone will come along who can check on that.

clang/lib/Sema/SemaChecking.cpp

1805

Right, exactly. This code path should end up being evaluated 2x in the case of an instantiation, the first time it is with the dependent placeholder types. The second time it will be instantiated. SO if you cannot validate the rules against dependent values, you just assume it would work and let the 2nd pass catch it.

Include some tests to make sure you catch this right and that this is usable in templates.

1812

Ok, thanks for checking. I was unsure, but I presumed that the implicit type-conversion based on the builtin definition would have caused that to happen.

[LukeZhuang]

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

[LukeZhuang]

In D79830#2049582, @erichkeane wrote:

FYI: I'm more of a clang contributor, so I'm unable to review the LLVM code, hopefully someone will come along who can check on that.

Thank you so much for the help. I just submitted a new patch.

[erichkeane]

Additionally, it seems you're missing SEMA tests. Please add those. Those tests should also make sure that the diagnostics still work with dependent values.

clang/include/clang/Basic/Builtins.def

567

The spaces after the first parameter are odd/unnecessary. I suspect it is in the line above because it was used to do alignment in the past. Please don't bother putting them in this new line.

clang/lib/CodeGen/CGBuiltin.cpp

2197

This is going to give an unused variable warning in release mode, since assert is a macro. You'll have to cast EvalSucceeded to void after the assert.

2199

First, don't do ==true here. Second, add a string to the assert (see other assert uses).

[LukeZhuang]

updated: 05/26/2020
(1) add Sema test
(2) improve assert
(3) format change

[LukeZhuang]

Fixed in latest update as well as adding test. Thank you!

[erichkeane]

1 more nit that I saw (don't use an 'else' after an 'if' branch that returns), but otherwise I think this is good from the CFE perspective. Someone better understanding of LLVM needs to look at the rest though.

clang/lib/Sema/SemaChecking.cpp

1816

You don't need the else, since the above branch returns.

[LukeZhuang]

updated: 05/28/2020
(1) remove redundant "else" according to coding standard
(2) change a few document words

Thank you Erich! I think removing this "else" here makes sense.

[LukeZhuang]

ping :)

[lebedev.ri]

clang/lib/Sema/SemaChecking.cpp

1818–1819

This doesn't look right to me, but maybe i'm misreading something?
Assuming the ! is intentional to avoid some fp weirdness (if not, simplify this)
shouldn't this be an &&, not ||?

Consider:
Probability = -1

if (!(-1 >= llvm::APFloat(0.0) ||
      -1 <= llvm::APFloat(1.0))) {

if (!(false ||
      true) {

if (false) {

so i'd think Probability = -1 would not get diagnosed?

clang/test/Sema/builtin-expect-with-probability.cpp

19–20 ↗

(On Diff #266901)

Do these tests actually pass?

[LukeZhuang]

updated 06/03/2020:
(1) fix bug of range checking in SemaChecking

[LukeZhuang]

clang/lib/Sema/SemaChecking.cpp

1818–1819

Yes, you're right.. Because of version problem, I still use converting to double in my local build, and miscopy this when upstreaming. Thank you for point it out.

clang/test/Sema/builtin-expect-with-probability.cpp

19–20 ↗

(On Diff #266901)

It pass it for now. Again my local build still use converting to double to compare and passed the test, but I miscopied it when upstream the change. Thank you!

[rsmith]

clang/include/clang/Basic/DiagnosticSemaKinds.td

10784–10787

I think "probability argument to" rather than "probability of" would be clearer.

clang/lib/CodeGen/CGBuiltin.cpp

2202

(This is marked as done, but SE_AllowSideEffects is still passed above.)

clang/lib/Sema/SemaChecking.cpp

1818–1819

I think this will probably only work if the target double type is IEEEdouble. (Otherwise you'll be comparing an IEEEdouble APFloat to a different kind of APFloat.)

We do not guarantee that double is IEEEdouble for all our supported targets. In particular, for TCE and for AVR (at least under -mdouble=32), double is IEEEsingle instead.

It looks like your LLVM intrinsic expects an LLVM IR double (that is, an IEEEdouble) as its third argument, so perhaps the right thing to do would be to convert the APFloat to IEEEdouble here and in CodeGen. Please add a test for a target where double is not IEEEdouble.

clang/test/Sema/builtin-expect-with-probability.cpp

18 ↗

(On Diff #268226)

Please also test some more edge cases. such as: if the probability argument is not convertible to float, or is inf or nan, negative zero, -denorm_min, or 1+epsilon.

llvm/docs/BranchWeightMetadata.rst

18

There are no instructions with these names. There are Clang builtin functions with these names and LLVM intrinsics with similar but different names. This document should be documenting the llvm.expect and llvm.expect.with.probability intrinsics.

128–135

This whole section of documentation (line 86 to 166) seems inappropriate to me as LLVM documentation, because it's talking about the behavior of one particular source language with one particular frontend, not LLVM semantics. Here's what I'd suggest:

• Move all of that documentation into the Clang user's manual, as a description of the __builtin_expect* builtin functions.
• Here in the LLVM documentation, add documentation for the llvm.expect and llvm.expect.with.probability intrinsic functions, and include a note pointing to the Clang documentation and suggesting that __builtin_expect and __builtin_expect_with_probability can be used to generate these intrinsics in C and C++ source files.

[davidxl]

Can you add some tests at the LLVM side?

[LukeZhuang]

clang/lib/Sema/SemaChecking.cpp

1818–1819

Hi, thank you for comments! I have several questions here:
(1) I do not understand why "APFloat Probability >= APFloat(0.0)" is affected by target here. Is this just a double come from C front-end and I check it here?
(2) And also not sure in CGBuiltin, is there I convert it to llvm intrinsic? How does target double type affect it?
(3) If I convert APFloat to IEEEDouble, should I use APF.convertToDouble or create a DoubleAPFloat. My original code did APFloat.convertToDouble and compare, and I do not sure about the difference.

llvm/docs/BranchWeightMetadata.rst

128–135

Yeah, thank you! I think your suggestion makes much sense, it should be in clang. However, the original __builtin_expect part is not written by me and and I am not sure its affect. So I added the author of this part as reviewer and I think it had better to ask his idea about this.

[LukeZhuang]

updated: 06/06/2020
(1) convert argument to IEEEdouble for different target
(2) update tests, add edge cases and llvm test
(3) minor change

[LukeZhuang]

In D79830#2075038, @davidxl wrote:

Can you add some tests at the LLVM side?

added ll test case

clang/lib/Sema/SemaChecking.cpp

1818–1819

Sorry, after I test with different targets I understood your suggestion. It shows weird behavior in comparing for AVR target. Now I have converted to IEEEdouble. I also added test for AVR target and passed it.

clang/test/Sema/builtin-expect-with-probability.cpp

18 ↗

(On Diff #268226)

added more edge cases here and example for AVR target

llvm/docs/BranchWeightMetadata.rst

18

I also think I might had better add intrinsic documents in llvm/docs/LangRef.rst instead of here, and keep __builtin_exepct_with_probability here or discuss with the original author about this.

[LukeZhuang]

updated: 06/06/2020
(1) updated llvm.expect.with.probability intrinsic document in LangRef.rst

[LukeZhuang]

updated: 06/08/2020
(1) update llvm side test for intrinsic llvm.expect.with.probability, which mimics test for llvm.expect

[davidxl]

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

58

nit: change name to getBranchWeight or computeBranchWeight

69

assert TrueProb is in [0,1]

96

simpler to use tuple and tie here.

[LukeZhuang]

updated: 06/09/2020
(1) improve code in LowerExpectIntrinsic
(2) update and simplify test

[davidxl]

LLVM side of change LGTM.

[LukeZhuang]

ping :)
For clang side is there any suggestions? Thank you!

[erichkeane]

Please fix the 'nit' when committing.

clang/lib/CodeGen/CGBuiltin.cpp

2202

Nit, move this cast next to the assert, its a common pattern in LLVM, so moving it away makes its purpose pretty unknown.

[LukeZhuang]

updated: 06/15/2020
(1) minor change of assertion and cast

[LukeZhuang]

In D79830#2093338, @erichkeane wrote:

Please fix the 'nit' when committing.

Fixed. Thank you!

[xbolva00]

clang/lib/CodeGen/CGBuiltin.cpp

2209

Fix comment and remove Probability?

[LukeZhuang]

updated: 06/15/2020
(1) fix minor variable name and doc word

[LukeZhuang]

Added: fix comment

[LukeZhuang]

@rsmith Hi, could you please take a look at my revision since last comment? Thank you!

[LukeZhuang]

Hi, I do not have access to commit, could anybody help me to commit it? Thank you!

[antiagainst]

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

62

FYI: this breaks GCC5: https://buildkite.com/mlir/mlir-core/builds/5841#4a7c245b-9841-44aa-a82a-97686b04b672

[ashi1]

Hi, I am getting a compiler error due to this patch. I am using cmake command: cmake ../llvm -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_PROJECTS="clang;lld;clang-tools-extra" -DLLVM_TARGETS_TO_BUILD="AMDGPU;X86" -DLLVM_ENABLE_ASSERTIONS=1 . Could you please take a look?

Error:
/root/llvm-project/llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp: In function 'std::tuple<unsigned int, unsigned int> getBranchWeight(llvm::Intrinsic::ID, llvm::CallInst*, int)':
/root/llvm-project/llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp:62:53: error: converting to 'std::tuple<unsigned int, unsigned int>' from initializer list would use explicit constructor 'constexpr std::tuple<_T1, _T2>::tuple(_U1&&, _U2&&) [with _U1 = llvm:🆑:opt<unsigned int>&; _U2 = llvm:🆑:opt<unsigned int>&; <template-parameter-2-3> = void; _T1 = unsigned int; _T2 = unsigned int]'

return {LikelyBranchWeight, UnlikelyBranchWeight};
                                                ^

/root/llvm-project/llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp:74:33: error: converting to 'std::tuple<unsigned int, unsigned int>' from initializer list would use explicit constructor 'constexpr std::tuple<_T1, _T2>::tuple(_U1&&, _U2&&) [with _U1 = unsigned int&; _U2 = unsigned int&; <template-parameter-2-3> = void; _T1 = unsigned int; _T2 = unsigned int]'

return {LikelyBW, UnlikelyBW};
                            ^

[erichkeane]

I'll get this fixed, thanks both of you for letting me know.

[LukeZhuang]

Thank you very much!

[erichkeane]

In D79830#2107404, @LukeZhuang wrote:

Thank you very much!

Turns out when I was validating my patch, someone had beaten me to it, it should be fixed, it just wasn't me :)

[erichkeane]

@LukeZhuang : This patch causes the buildbots to fail, as O1 means something slightly different with the new pass manager :
http://lab.llvm.org:8011/builders/clang-x86_64-debian-new-pass-manager-fast/builds/10542/steps/test-check-all/logs/FAIL%3A%20Clang%3A%3Abuiltin-expect-with-probability.cpp

I'm sorry I didn't notice it during review, but the test that is failing is a poorly written test. The CFE tests shouldn't be written in a way that depends on the actions of the optimizer, so testing the branch_weights is incorrect.

Please submit a new patch with a way to validate the clang codegen actions without depending on the optimization (that is, would work with -disable-llvm-passes), and if necessary, add a test to llvm to ensure the proper result is validated.

EDIT: To clarify, I've unblocked the buildbots by doing a temporary fix. But this test needs to be rewritten.

[LukeZhuang]

In D79830#2109324, @erichkeane wrote:

@LukeZhuang : This patch causes the buildbots to fail, as O1 means something slightly different with the new pass manager :
http://lab.llvm.org:8011/builders/clang-x86_64-debian-new-pass-manager-fast/builds/10542/steps/test-check-all/logs/FAIL%3A%20Clang%3A%3Abuiltin-expect-with-probability.cpp

I'm sorry I didn't notice it during review, but the test that is failing is a poorly written test. The CFE tests shouldn't be written in a way that depends on the actions of the optimizer, so testing the branch_weights is incorrect.

Please submit a new patch with a way to validate the clang codegen actions without depending on the optimization (that is, would work with -disable-llvm-passes), and if necessary, add a test to llvm to ensure the proper result is validated.

EDIT: To clarify, I've unblocked the buildbots by doing a temporary fix. But this test needs to be rewritten.

Thank you for pointing out! I have fixed by mimic the test case builtin-expect.c does. It makes sense to test generated llvm intrinsic instead of branch weight here. The lowering to branch weight is already tested in llvm side.

clang/include/clang/Basic/Builtins.def

 BUILTIN(__builtin___vsprintf_chk, "ic*izcC*a", "FP:3:")
 BUILTIN(__builtin___fprintf_chk, "iP*icC*.", "Fp:2:")
 BUILTIN(__builtin___printf_chk, "iicC*.", "Fp:1:")
 BUILTIN(__builtin___vfprintf_chk, "iP*icC*a", "FP:2:")
 BUILTIN(__builtin___vprintf_chk, "iicC*a", "FP:1:")
 
 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")
 BUILTIN(__builtin_debugtrap, "v", "n")
 BUILTIN(__builtin_unreachable, "v", "nr")
 BUILTIN(__builtin_shufflevector, "v."   , "nct")
 BUILTIN(__builtin_convertvector, "v."   , "nct")
 BUILTIN(__builtin_alloca, "v*z"   , "Fn")

clang/include/clang/Basic/DiagnosticSemaKinds.td

 def warn_sycl_kernel_return_type : Warning<
   "function template with 'sycl_kernel' attribute must have a 'void' return type">,
   InGroup<IgnoredAttributes>;
 
 def err_ext_int_bad_size : Error<"%select{signed|unsigned}0 _ExtInt must "
                                  "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.

clang/lib/CodeGen/CGBuiltin.cpp

RValue CodeGenFunction::EmitBuiltinExpr(const GlobalDecl GD, unsigned BuiltinID,
   }
 
   case Builtin::BI__builtin_clrsb:
   case Builtin::BI__builtin_clrsbl:
   case Builtin::BI__builtin_clrsbll: {
     // clrsb(x) -> clz(x < 0 ? ~x : x) - 1 or
     Value *ArgValue = EmitScalarExpr(E->getArg(0));
 
     llvm::Type *ArgType = ArgValue->getType();
     Function *F = CGM.getIntrinsic(Intrinsic::ctlz, ArgType);
 
     llvm::Type *ResultType = ConvertType(E->getType());
     Value *Zero = llvm::Constant::getNullValue(ArgType);
     Value *IsNeg = Builder.CreateICmpSLT(ArgValue, Zero, "isneg");
     Value *Inverse = Builder.CreateNot(ArgValue, "not");
     Value *Tmp = Builder.CreateSelect(IsNeg, Inverse, ArgValue);
     Value *Ctlz = Builder.CreateCall(F, {Tmp, Builder.getFalse()});
     Value *Result = Builder.CreateSub(Ctlz, llvm::ConstantInt::get(ArgType, 1));
     Result = Builder.CreateIntCast(Result, ResultType, /*isSigned*/true,
                                    "cast");
     return RValue::get(Result);
   }
   case Builtin::BI__builtin_ctzs:
   case Builtin::BI__builtin_ctz:
case Builtin::BI__builtin_expect: {
     if (CGM.getCodeGenOpts().OptimizationLevel == 0)
       return RValue::get(ArgValue);
 
     Function *FnExpect = CGM.getIntrinsic(Intrinsic::expect, ArgType);
     Value *Result =
         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);
     Value *OffsetValue =
       (E->getNumArgs() > 2) ? EmitScalarExpr(E->getArg(2)) : nullptr;
 
     Value *AlignmentValue = EmitScalarExpr(E->getArg(1));
     ConstantInt *AlignmentCI = cast<ConstantInt>(AlignmentValue);

clang/lib/Sema/SemaChecking.cpp

if (const auto *FT = dyn_cast<FunctionProtoType>(FuncType)) {
             << 2 << FnPtrArgType << "'int (*)(const char *, ...)'";
         return ExprError();
       }
     }
 
     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();
     break;
   case Builtin::BI__builtin_call_with_static_chain:
     if (SemaBuiltinCallWithStaticChain(*this, TheCall))
       return ExprError();
     break;

clang/test/CodeGen/builtin-expect-with-probability-switch.c

+// 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;
+}

clang/test/CodeGen/builtin-expect-with-probability-template.cpp

+// 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);
+}

clang/test/CodeGen/builtin-expect-with-probability.c

+// 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;
+}

llvm/docs/BranchWeightMetadata.rst

 
 Branch Weight Metadata represents branch weights as its likeliness to be taken
 (see :doc:`BlockFrequencyTerminology`). Metadata is assigned to an
 ``Instruction`` that is a terminator as a ``MDNode`` of the ``MD_prof`` kind.
 The first operator is always a ``MDString`` node with the string
 "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.
 
 Supported Instructions
 ======================
 
 ``BranchInst``
.. code-block:: c++
 
   switch (__builtin_expect(x, 5)) {
   default: break;
   case 0:  // ...
   case 3:  // ...
   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
 =================
 
 Branch Weight Metatada is not proof against CFG changes. If terminator operands'
 are changed some action should be taken. In other case some misoptimizations may
 occur due to incorrect branch prediction information.
 
 Function Entry Counts

llvm/include/llvm/IR/Intrinsics.td

 }
 // FIXME: Consider maybe adding intrinsics for sitofp, uitofp.
 
 //===------------------------- Expect Intrinsics --------------------------===//
 //
 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 ---------------------===//
 //
 
 // None of these intrinsics accesses memory at all.
 let IntrProperties = [IntrNoMem, IntrSpeculatable, IntrWillReturn] in {
   def int_bswap: Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>]>;
   def int_ctpop: Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>]>;
   def int_bitreverse : Intrinsic<[llvm_anyint_ty], [LLVMMatchType<0>]>;

llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

 
 static cl::opt<uint32_t> LikelyBranchWeight(
     "likely-branch-weight", cl::Hidden, cl::init(2000),
     cl::desc("Weight of the branch likely to be taken (default = 2000)"));
 static cl::opt<uint32_t> UnlikelyBranchWeight(
     "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);
   ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
   if (!ExpectedValue)
     return false;
 
   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,
+  SI.setMetadata(LLVMContext::MD_misexpect,
                  MDBuilder(CI->getContext())
-          .createMisExpect(Index, LikelyBranchWeight, UnlikelyBranchWeight));
+                     .createMisExpect(Index, LikelyBranchWeightVal,
+                                      UnlikelyBranchWeightVal));
 
   SI.setCondition(ArgValue);
   misexpect::checkFrontendInstrumentation(SI);
 
   SI.setMetadata(LLVMContext::MD_prof,
                  MDBuilder(CI->getContext()).createBranchWeights(Weights));
 
   return true;
auto IsOpndComingFromSuccessor = [&](BasicBlock *Succ) {
         return true;
       if (OpndIncomingBB == BI->getParent() && Succ == PhiDef->getParent())
         // Otherwise, if the edge is directly from the branch
         // to the Phi, this successor is the one feeding this
         // Phi operand.
         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));
   }
 }
 
 // Handle both BranchInst and SelectInst.
 template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
 
   // Handle non-optimized IR code like:
   //   %expval = call i64 @llvm.expect.i64(i64 %conv1, i64 1)
template <class BrSelInst> static bool handleBrSelExpect(BrSelInst &BSI) {
   uint64_t ValueComparedTo = 0;
   if (CmpConstOperand) {
     if (CmpConstOperand->getBitWidth() > 64)
       return false;
     ValueComparedTo = CmpConstOperand->getZExtValue();
   }
 
   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);
   ConstantInt *ExpectedValue = dyn_cast<ConstantInt>(CI->getArgOperand(1));
   if (!ExpectedValue)
     return false;
 
   MDBuilder MDB(CI->getContext());
   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);
 
   if (CmpI)
     CmpI->setOperand(0, ArgValue);
   else
     BSI.setCondition(ArgValue);
for (auto BI = BB.rbegin(), BE = BB.rend(); BI != BE;) {
         if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
           if (handleBrSelExpect(*SI))
             ExpectIntrinsicsHandled++;
         }
         continue;
       }
 
       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:
         handlePhiDef(CI);
         Value *Exp = CI->getArgOperand(0);
         CI->replaceAllUsesWith(Exp);
         CI->eraseFromParent();
         Changed = true;