[llvm-dev] GSoC Proposal : Path Profiling Support

[Snehasish Kumar via llvm-dev]

This proposal adds support  for path profiling [Ball96] to LLVM. Path
profiling compactly represents acyclic paths in a directed acyclic graph
representation of the control flow graph of a routine. Instrumentation can
be added to uniquely identify paths executed at runtime.
Path profiles enable precise enumeration of the sequence of basic blocks
executed in order for a particular path. Using path profiles has been
demonstrated by [Young98] to perform better global scheduling than edge
profiles. Superblocks constructed from path profiles offer more
opportunities for speculative code motion thereby improving program
performance.

About Me :
I am a PhD candidate at Simon Fraser University, Canada. My research
primarily deals with computer architecture and workload analysis. Over the
last year, I have built a toolchain which uses path profiling as its basis.
With support from GSoC, I would like to integrate our path profiling pass
into trunk. Our passes are currently built against LLVM 3.6.2. I am willing
to maintain said passes as they form the core of our research
infrastructure.

Prior Work :
Path profiling was implemented by Adam Preuss for LLVM [Preuss10]. However,
this was before the unified profiling infrastructure was in place. It seems
that the code was removed from trunk post LLVM 3.3.

Current Implementation :
+ HashTable based
+ Static overflow checks (64 bit counters) at instrumentation time with
fallback to APInt counters
+ Implements efficient event counting [Ball94] to reduce instrumentation
overheads
+ Context sensitive counters if no 64-bitoverflow (i.e. supports path
profiling across recursion)
+ Optimizations for use cases with very large number of executed paths
+ Used to analyse C/C++ benchmarks from SPECCPU2006

Proposed Integration :
+ Support library code added to compiler-rt
+ llvm/Analysis gets PathEncoding, PathDecoding and PathProfileInfo module
passes
+ llvm/Transforms/Instrumentation gets PathProfileInstrumentation module
pass
+ PathProfileInfo offers const only public methods to query info

Open Issues :
+ Update PathProfileInfo on CFG transformations ?
+ Verify with PGOEdge info ?
+ Handle setjmp, longjmp, early program termination, noreturn calls


Please let me know your comments on this proposal as a GSoC project. Any
comments on how to refine this proposal are welcome. I can also elaborate
on specific details of our implementation if there is interest on the
mailing list.

Thanks,
Snehasish Kumar
School of Computing Science
Simon Fraser University


References :
[Ball94] Ball, Thomas. "Efficiently counting program events with support
for on-line queries." ACM Transactions on Programming Languages and Systems
(TOPLAS) 16.5 (1994): 1399-1410.
[Ball96] Ball, Thomas, and James R. Larus. "Efficient path profiling."
Proceedings of the 29th annual ACM/IEEE international symposium on
Microarchitecture. IEEE Computer Society, 1996.
[Young98] Young, Cliff, and Michael D. Smith. "Better global scheduling
using path profiles." Proceedings of the 31st annual ACM/IEEE international
symposium on Microarchitecture. IEEE Computer Society Press, 1998.
[Preuss10]
http://lists.llvm.org/pipermail/llvm-dev/2010-December/036790.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160315/d4b866c9/attachment.html>