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.
School of Computing Science
Simon Fraser University
[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.