Page MenuHomePhabricator

lower __builtin_expect() directly to prof metadata instead of LLVM intrinsic
AbandonedPublic

Authored by spatel on Apr 19 2016, 4:41 PM.

Details

Summary

__builtin_expect() is a GCC-derived builtin that's used as a hint for branch prediction:
https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

The Clang/LLVM implementation of this feature introduced an LLVM intrinsic to convey the hint to the optimizer:
https://marc.info/?l=llvm-commits&m=130997676129580&w=4

There are problems with this (and several were noted in the above thread, but it didn't change the outcome):

  1. We created an intrinsic to improve perf, but the intrinsic can harm optimization by interfering with other passes.
  1. To solve that, create a pass to always transform the intrinsic into metadata at a very early stage. But now every program is paying a compile-time tax for a feature that is rarely used.
  1. The IR lowering uses profile weight metadata as the means for conveying the hint. But the hint is meant to be a programmer override for profile data. That is, "I don't care what the profile says; I want my code to use this source-level hint." So it should use a different kind of metadata, not profile weight. We added the inverse programmer hint as metadata - __builtin_unpredictable():

http://llvm.org/docs/LangRef.html#unpredictable-metadata
http://reviews.llvm.org/D12341
so I think we can enhance that to solve this problem.

This patch is an intermediate step. It doesn't try to solve #3 above, but it handles #1 and clears the way to deprecate the llvm.expect intrinsic and delete the LowerExpectIntrinsic pass (problem #2).

This is part of solving:
https://llvm.org/bugs/show_bug.cgi?id=27344
But to complete that, we need to make changes in SimplifyCFG and possibly other places, so that we're propagating and using the expect/unpredictable metadata as intended. Ref: D18133, D18220, rL264527, rL266442

Diff Detail

Event Timeline

spatel updated this revision to Diff 54277.Apr 19 2016, 4:41 PM
spatel retitled this revision from to lower __builtin_expect() directly to prof metadata instead of LLVM intrinsic.
spatel updated this object.
spatel added reviewers: hfinkel, davidxl, bkramer.
spatel added a subscriber: cfe-commits.
davidxl edited edge metadata.Apr 19 2016, 5:20 PM

I like the direction this patch is going. Will look into details soon.

deadalnix added inline comments.
lib/CodeGen/CGStmt.cpp
1565–1593

If I understand properly this is transitional and eventually, you want to remove the intrinsic ? I think I like it, having 2 ways to hint here is only making things more complicated without adding much value.

spatel added inline comments.Apr 20 2016, 7:43 AM
lib/CodeGen/CGStmt.cpp
1565–1593

Yes, I want to merge the handling of builtin_expect and builtin_unpredictable. Currently, the 'unpredictable' metadata has no parameters; it is an empty string like:

br i1 %or.cond, label %bb3, label %bb4, !unpredictable !2
...
!2 = !{}

In D12341, we considered having an integer parameter value that would be a measure of the unpredictability. For example, this could be used with PGO if someone had collected branch mispredict data as part of a profiling run.

So as a first proposal, let's say we add an integer parameter for predictability for this metadata type. We could define '-1' to mean 'perfectly predictable' and so builtin_expect would map to this:

!2 = !{-1 42}   <--- perfectly predictable with expected value of '42'

Rereading your question, I'm now wondering if you are asking if we can get rid of the source level builtin_unpredictable() ? I had not considered that, but I think that is also possible if we add a flag to builtin_expect() to mean 'this branch is unpredictable'.

Please let me know if I answered the correct question. :)

So, yes this patch is transitional - hopefully, no more than a few days. I'm going to audit where we actually use profile data to make transform decisions. Once those places (I'm assuming they actually exist!) are updated to look at the unpredictable metadata, we can fix up this clang code to match the optimizer's algorithms.

[reposting this as a general comment because the inline comment did not seem to make it to the mailing list]

Yes, I want to merge the handling of builtin_expect and builtin_unpredictable. Currently, the 'unpredictable' metadata has no parameters; it is an empty string like:

br i1 %or.cond, label %bb3, label %bb4, !unpredictable !2
...
!2 = !{}

In D12341, we considered having an integer parameter value that would be a measure of the unpredictability. For example, this could be used with PGO if someone had collected branch mispredict data as part of a profiling run.

So as a first proposal, let's say we add an integer parameter for predictability for this metadata type. We could define '-1' to mean 'perfectly predictable' and so builtin_expect would map to this:

!2 = !{-1 42}   <--- perfectly predictable with expected value of '42'

Rereading your question, I'm now wondering if you are asking if we can get rid of the source level builtin_unpredictable() ? I had not considered that, but I think that is also possible if we add a flag to builtin_expect() to mean 'this branch is unpredictable'.

Please let me know if I answered the correct question. :)

So, yes this patch is transitional - hopefully, no more than a few days. I'm going to audit where we actually use profile data to make transform decisions. Once those places (I'm assuming they actually exist!) are updated to look at the unpredictable metadata, we can fix up this clang code to match the optimizer's algorithms.

davidxl added inline comments.Apr 20 2016, 9:34 AM
lib/CodeGen/CGBuiltin.cpp
636–637

Can this be reordered with unpredicatle case so that it can handle arg 1 and fall through?

lib/CodeGen/CGStmt.cpp
1550

update the comment here.

1567

I am not sure about this. builtin_expect can be used to do general value profiling annotation (single value). For instance,

if (builtin_expect(a, 20) > 10) {
}

should have same effect as

if (builtin_expect(a > 10), true) {

}

The above can be handled by gcc, but not LLVM.

It can be useful for switch case annotation:

switch (__builtin_expect(v, 20) ) {
case 10: ...
case 20: ...
...
}
where compiler can do switch peeling.

Longer term, I am thinking extending builtin_expect to take list of values with probabilities and predicatibiity hint.

1571

Unpredicable meta data is probably not suitable for switch annotation. builtin_expect can be used to specify one case that is more likely to be taken thus helping switch lowering decision (not used in the cases such as if conversion).

lib/CodeGen/CodeGenFunction.cpp
1311–1312

Update comment here.

1331

I suggest removing these comments.

spatel added inline comments.Apr 20 2016, 11:00 AM
lib/CodeGen/CGStmt.cpp
1567

Ah, I hadn't considered extending builtin_expect in that way. In that case, it does make sense to leave it as-is here and use prof metadata because it's already set up for a list of values.

I'll clean up and re-post the patch. Thanks everyone for the reviews!

Rereading your question, I'm now wondering if you are asking if we can get rid of the source level builtin_unpredictable() ? I had not considered that, but I think that is also possible if we add a flag to builtin_expect() to mean 'this branch is unpredictable'.

Please let me know if I answered the correct question. :)

You did answer my question. I don't really mind source level intrinsic, I'm more concerned about the IR and how they are lowered. Overall I like where this is going. It looks like @davidxl is on it for the review, and he seems to have a good idea of where this should go, so I'll defer to him for acceptance/change requests.

spatel marked 4 inline comments as done.Apr 20 2016, 2:39 PM
spatel added inline comments.
lib/CodeGen/CGBuiltin.cpp
636–637

I had coded it that way initially, but I think we must emit the expression for arg0 *before* the expression for arg1.

The ordering is checked by the 'main()' test in the regression test file. If you see a way to code around that, please let me know.

spatel updated this revision to Diff 54423.Apr 20 2016, 2:44 PM
spatel edited edge metadata.

Patch updated:

  1. Fixed/removed comments
  2. Changed likely/unlikely profile weights to be min/max values. I'm not sure why 4 and 64 were used in LowerExpectIntrinsics, but that may not trigger the programmer's intent with builtin_expect().
davidxl accepted this revision.Apr 21 2016, 10:24 AM
davidxl edited edge metadata.

lgtm

This revision is now accepted and ready to land.Apr 21 2016, 10:24 AM
spatel abandoned this revision.Apr 26 2016, 11:14 AM

Abandoning.

The feedback on the dev list was that handling the builtin_expect() in clang is ugly, so it's better to pay a small cost in LLVM to do it.

Note that the current llvm.expect lowering pass doesn't actually work for anything but the simplest cases. The pass needs to be enhanced to handle patterns like:

int foo(int x, int y) {
  if (__builtin_expect(x, 20) > 10) return 234;  // expected value is not 1
  return 2;
}

or:

int foo(int n) {
  int b = __builtin_expect(n, 1);  // expect is not directly used in comparison
  if (b) return 24;
  return 234;
}

Currently, the llvm.expect is discarded in these cases without generating any metadata.