[LLVMdev] Static Profiling - GSoC 2009

[Chris Lattner]

On Mar 31, 2009, at 8:12 AM, Andrei Alvares wrote:
> Hello all,
>  I would like to participate in this year's Google Summer of Code and
> I am sending you a short description of my proposal. I have written
> the formal proposal already and if someone is interested I can send
> him the pdf.

This is a very interesting proposal, I encourage you to apply!

>  One of the open projects in the LLVM list is to enhance LLVM with
> static profiling capabilities. LLVM already provides a unified
> structure for writing pro file-guided transformations that utilizes
> information harvested by a dynamic profiler. However, this framework
> does not yet contain static pro ling capabilities. I think that static
> profiling would be a valuable tool to many of the optimizations that
> are already part of the LLVM framework, allowing them to focus on the
> heavily executed program parts that are critical to performance.

Yes, the profile system in general hasn't gotten much love lately.

>  The proposal is to implement the static branch predictor described
> by Wu et al. (1994) as a LLVM Function Pass. This pass will associate
> to each path in the control flow graph of a program encoded in LLVM
> intermediate representation a real number between zero and one that
> denotes the probability that the path is taken during the program
> execution.  In order to determine the probability that a branch (br)
> instruction is taken during execution, we will use a collection of
> heuristics. Examples of heuristics include:
>  - Edges that point to the head of a loop are taken with 95% of  
> probability.
>  - A comparison of a pointer with NULL fails with 80% of probability.
>  - A comparison of an integer for less than zero will fail with 75%
> of probability.

Also: EH destination blocks should be predicted as almost never taken  
(1%?)

Another idea is that we could have the front-end lower  
__builtin_expect to drop an intrinsic in the true/false branches of  
"expected" branch that indicates hi/low probabilities, this could also  
use that info.

> A substantial part of the work will be to determine all the
> heuristics that apply to the LLVM intermediate representation, and to
> tune the probabilities associated to each comparison. Once the pass is
> ready and working, ideally I would like to modify one of the analysis
> that already exist in LLVM to use the profiling information. I would
> be happy to hear which of the LLVM analysis you guys think is the
> nicest candidate to be improved with static profiling.

I think that it would be *very* important to have a client for this.   
Without that, it would be very difficult to show the value of any  
tuning you do.

The first step is probably a block layout pass.  We already have a  
very simple one that might "just work".

The second step is probably the register allocator's spill weight  
heuristic.  Right now I think it is something simple like 8^loop-depth  
plus information about # uses/defs.  With profile info, we could do a  
better job at estimating the cost.

I'm not sure of another good client for this information, but this  
isn't something I have thought about deeply.

-Chris