[LLVMdev] Profiling in LLVM Patch

[Andreas Neustifter]

Hi all,

as proposed in
http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-February/020396.html
I implemented the algorithm presented in [Ball94]. It only instruments
the minimal number of edges necessary for edge profiling.

The main changes introduced by this patch are:
*) a interface compatible rewrite of ProfileInfo
*) a cleanup of ProfileInfoLoader
    (some functionality in ProfileInfoLoader was duplicated in ProfileInfo or
    ProfileInfoLoaderPass; ProfileInfoLoader now really only performs the
    loading but not the post-processing)
*) a new instrumentation pass that performs the optimal edge profiling
    instrumentation
*) a helper module MaximumSpanningTree that selects the edges with have to
    be instrumented for optimal edge profiling
*) a ProfileEstimatorPass that does an offline estimation of a profile based
    on branching and loop depth (also proposed in [Ball94])
    (it is possible to use this ProfileEstimator stand-alone to have at least
    some profile estimation available in the frontend without doing profiling
    runs)
*) a ProfileVerifierPass that checks the current profiling information
    against the flow preservation rules

I did performance measurements on the C and C++ portions of the SPEC CPU2000
benchmark, the results are:
*) on average 46% of the edges are instrumented with a counter (in
    comparison to 100% with the current edge profiling)
*) the performance overhead (on linux-x68_64, other platforms to follow) was
    14.76% with the current profiling and 8.20% with the optimal profiling
    (there are strange effects with the mcf and equake benchmarks where the
    current edge profiling is as fast as the un-instrumented code whereas the
    optimally instrumented code has a small (~5%) performance overhead)
*) when mcf and equake are excluded the average performance overhead is
    51.31% with optimal profiling (in comparison to 100% with the current
    edge profiling)

Please tell me what you do not like and if this is interesting enough to be
added to the trunk, if so, I will also devise test cases for "make check".

If you do not like the size of this patch it is possible to break it up a
little. I did not use the mkpatch utility since it does not include added
files, I hope the format is readable enough (it should be...)

I ran "make check" and there are not additional errors introduced
by the patch.

Grettings,

Andreas Neustifter

[Ball94] Thomas Ball, James R. Larus:
"Optimally profiling and tracing programs"
ACM TOPLAS, Volume 16, Issue 4, 1994
http://portal.acm.org/citation.cfm?id=183527
-------------- next part --------------
A non-text attachment was scrubbed...
Name: llvm-r74306.optimal_profiling.patch
Type: text/x-patch
Size: 85518 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090629/9d908488/attachment.bin>