[LLVMdev] Static Profiling - GSoC 2009

[Andrei Alvares]

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.

  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.

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

  As for my background, I was recently accepted in the mastership
program of the Federal University of Minas Gerais (UFMG), Brazil. My
major research topic will be on code optimizations, mainly using LLVM
as an auxiliary framework for testing and debugging. I am part of a
team of four students currently working with code optimizations with
LLVM. I have been programming in C and C++ for more than five years
and I have strong compiler background, as this is my current field of
research. This project will be useful to my master's research and I
believe it will be also useful to the LLVM community.

Reference:
Youfeng Wu and James R. Larus. Static branch frequency and program
profile analysis. In MICRO 27: Proceedings of the 27th annual
international symposium on Microarchitecture. IEEE, 1994.