llvm dev - Aug 2011 - [LLVMdev] Branch transformation with branch-weight metadata

Hello :)

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



Regards,
Hae-woo Park
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110831/be50c14d/attachment.html>

On Tue, Aug 30, 2011 at 10:25 PM, Hae-woo Park <starlet at
iris.snu.ac.kr>wrote:
>
> Hello :)
>
> 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.

>
> Thank you.
> Have a nice day. :)
>
>
>
> Regards,
> Hae-woo Park
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110830/5fa35647/attachment.html>

On Aug 30, 2011, at 10:25 PM, Hae-woo Park wrote:
> 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 ?
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110831/8acdd129/attachment.html>