This is an archive of the discontinued LLVM Phabricator instance.

Add support of __builtin_expect_with_probability
ClosedPublic

Authored by LukeZhuang on May 12 2020, 5:23 PM.

Details

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.

Diff Detail

Event Timeline

LukeZhuang created this revision.May 12 2020, 5:23 PM
lebedev.ri added a subscriber: lebedev.ri.

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

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.

Add a description in our documentation?

Is it possible to overload __builtin_expect(..)?

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.

Add a description in our documentation?

And Ideally add a note to release notes too..

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!

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 added a comment.EditedMay 13 2020, 12:02 PM

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

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

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 marked 4 inline comments as done.May 13 2020, 3:58 PM
LukeZhuang added inline comments.
clang/lib/CodeGen/CGBuiltin.cpp
2049

fixed in the lastest change

2056

fixed in the lastest change

LukeZhuang marked 2 inline comments as done.May 13 2020, 3:59 PM
rsmith added inline comments.May 13 2020, 4:41 PM
clang/include/clang/Basic/Builtins.def
569

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
2197

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 added inline comments.May 13 2020, 9:54 PM
clang/lib/CodeGen/CGBuiltin.cpp
2197

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 added inline comments.May 14 2020, 12:17 PM
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 added inline comments.May 14 2020, 2:29 PM
clang/lib/CodeGen/CGBuiltin.cpp
2197

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.

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 marked 15 inline comments as done.May 15 2020, 2:54 PM
LukeZhuang added inline comments.
clang/include/clang/Basic/Builtins.def
569

Seems there is currently no tag for constant floating-point

clang/lib/CodeGen/CGBuiltin.cpp
2197

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

LukeZhuang marked 5 inline comments as done.May 15 2020, 2:57 PM
erichkeane added inline comments.May 21 2020, 8:38 AM
clang/lib/CodeGen/CGBuiltin.cpp
2199

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

2204

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

2206

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 added inline comments.May 21 2020, 10:05 AM
clang/lib/CodeGen/CGBuiltin.cpp
2206

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 added inline comments.May 21 2020, 10:22 AM
clang/lib/CodeGen/CGBuiltin.cpp
2204

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

2206

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 marked 6 inline comments as done.May 21 2020, 11:13 AM
LukeZhuang added inline comments.
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.

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.

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 marked 8 inline comments as done.May 21 2020, 2:10 PM

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.

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
569

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
2199

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.

2201

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

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

LukeZhuang marked 3 inline comments as done.May 26 2020, 11:47 AM

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

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.

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 marked an inline comment as done.May 28 2020, 9:04 AM
lebedev.ri added inline comments.Jun 3 2020, 7:53 AM
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
20–21

Do these tests actually pass?

LukeZhuang updated this revision to Diff 268226.Jun 3 2020, 9:09 AM

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

LukeZhuang marked 4 inline comments as done.Jun 3 2020, 9:15 AM
LukeZhuang added inline comments.
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
20–21

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 added inline comments.Jun 4 2020, 2:50 PM
clang/include/clang/Basic/DiagnosticSemaKinds.td
10814–10817

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

clang/lib/CodeGen/CGBuiltin.cpp
2204

(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
19

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.

149–156

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.

Can you add some tests at the LLVM side?

LukeZhuang added inline comments.Jun 4 2020, 7:55 PM
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
149–156

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 this revision to Diff 269002.Jun 6 2020, 1:39 AM

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 marked 12 inline comments as done.Jun 6 2020, 1:45 AM

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
19

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 this revision to Diff 269028.Jun 6 2020, 2:05 PM
LukeZhuang added a reviewer: dexonsmith.

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

LukeZhuang updated this revision to Diff 269408.EditedJun 8 2020, 8:34 PM

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

davidxl added inline comments.Jun 9 2020, 9:49 AM
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 this revision to Diff 269642.Jun 9 2020, 1:07 PM

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

LukeZhuang marked 4 inline comments as done.Jun 9 2020, 1:08 PM
davidxl accepted this revision.Jun 9 2020, 2:18 PM

LLVM side of change LGTM.

This revision is now accepted and ready to land.Jun 9 2020, 2:18 PM

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

erichkeane accepted this revision.Jun 15 2020, 11:05 AM

Please fix the 'nit' when committing.

clang/lib/CodeGen/CGBuiltin.cpp
2204

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

LukeZhuang marked an inline comment as done.

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

Please fix the 'nit' when committing.

Fixed. Thank you!

xbolva00 added inline comments.Jun 15 2020, 8:35 PM
clang/lib/CodeGen/CGBuiltin.cpp
2211

Fix comment and remove Probability?

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

LukeZhuang marked an inline comment as done.

Added: fix comment

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

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

This revision was automatically updated to reflect the committed changes.
antiagainst added inline comments.
llvm/lib/Transforms/Scalar/LowerExpectIntrinsic.cpp
62

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};
                            ^

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

Thank you very much!

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 added a comment.EditedJun 23 2020, 8:38 AM

@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 : 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.