Branch transformation with branch-weight metadata

Hello :slight_smile:

I am looking around __builtin_expect() directive for optimization.
( http://llvm.org/docs/BranchWeightMetadata.html )
Since it is not included in v2.9, I am searching about it on svn trunk.

I found that the lowering phase generates branch-weight metadata node for that directive.
However, I can’t find any code related to the metadata even in the branch transformation code.
IMHO, in case the branch direction is, for example, reversed for optimization,
the corresponding branch-weight metadata also has to be changed.

In what code can I find such a metadata management code ?
Can anyone give me a hint ?

Thank you.
Have a nice day. :slight_smile:

Regards,
Hae-woo Park

Hello :slight_smile:

I am looking around __builtin_expect() directive for optimization.
( http://llvm.org/docs/BranchWeightMetadata.html )
Since it is not included in v2.9, I am searching about it on svn trunk.

I found that the lowering phase generates branch-weight metadata node for that directive.
However, I can’t find any code related to the metadata even in the branch transformation code.
IMHO, in case the branch direction is, for example, reversed for optimization,
the corresponding branch-weight metadata also has to be changed.

In what code can I find such a metadata management code ?
Can anyone give me a hint ?

lib/Analysis/BranchProbabilityInfo.cpp (and the accompanying header) provide an LLVM Analysis pass that should model metadata, as well as __builtin_expect() information, and various generally accepted static branch probabilities. It is likely what you’re looking for.

You can also find a MachineBranchProbabilityInfo pass that operates at the machine layer to guide architecture-specific optimization and passes that need the same set of information.

Sorry, the documentation and comments can be misleading. The branch weight metatdata support you’re looking for doesn’t exist yet. I consider the document you’re reading a strawman proposal. The good news is that the interface between branch profile information and optimization is working and supported. See BranchProbabilityInfo and BlockFrequencyInfo. Currently, they fall back to static heuristics for lack of profile data.

If you want to use builtin_expect, you actually have various options:

  1. Use the metadata currently generated by LowerExpectIntrinsic. Implement the “management” code in every pass that inverts branches. Make a small change to BranchProbabilityInfo to read the metadata when available. Unfortunately, this approach is not robust or readily verifiable. But probably the easiest to get working. You could certainly push your changes back to trunk if they’re clean.

  2. Modify LowerExpectIntrinsic to generate your own symbolic metadata format that is robust in the presence of unknown intermediate phases. Make a more involved change to BranchProbabilityInfo to read your metadata format and sort out any CFG changes that may have occurred as best as you can. I’m not sure how cleanly and efficiently this can be done, so not sure if we would integrate it on trunk or not.

  3. Skip the meta-data altogether and run BranchProbabilityInfo before LowerExpectIntrinsic. Modify all passes in your “profile optimization” compilation path to preserve BranchProbabilityInfo. Preserving BPI is not much harder than “managing metadata”. We could probably take back at least some of your changes if the BPI updating is well-factored into APIs. Many passes may even choose to preserve BlockFrequencyInfo.

  4. Same as #3 but avoid preserving BPI in early passes by leaving the expect intrinsics in the IR later. Unfortunately we don’t have general support for a “nop” intrinsic, so this will currently interfere with optimization. I think adding “nop” intrinsic support would be a welcome improvement, and we could take it back. It’s also the most sensible approach for builtin_expect, but it conflicts with the larger goal of supporting profile info from other sources.

-Andy