[LLVMdev] Static Profiling - GSoC 2009
clattner at apple.com
Wed Apr 1 22:15:22 PDT 2009
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
> - 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
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.
More information about the llvm-dev