<div dir="ltr"><div><br></div><div>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. </div><div>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.</div><div><br></div><div>About Me : </div><div>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.</div><div><br></div><div>Prior Work :</div><div>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. </div><div><br></div><div>Current Implementation :</div><div>+ HashTable based</div><div>+ Static overflow checks (64 bit counters) at instrumentation time with fallback to APInt counters</div><div>+ Implements efficient event counting [Ball94] to reduce instrumentation overheads</div><div>+ Context sensitive counters if no 64-bitoverflow (i.e. supports path profiling across recursion)</div><div>+ Optimizations for use cases with very large number of executed paths</div><div>+ Used to analyse C/C++ benchmarks from SPECCPU2006</div><div><br></div><div>Proposed Integration :</div><div>+ Support library code added to compiler-rt</div><div>+ llvm/Analysis gets PathEncoding, PathDecoding and PathProfileInfo module passes</div><div>+ llvm/Transforms/Instrumentation gets PathProfileInstrumentation module pass</div><div>+ PathProfileInfo offers const only public methods to query info</div><div><br></div><div>Open Issues :</div><div>+ Update PathProfileInfo on CFG transformations ?</div><div>+ Verify with PGOEdge info ?</div><div>+ Handle setjmp, longjmp, early program termination, noreturn calls</div><div><br></div><div> </div><div>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. </div><div><br></div><div>Thanks,</div><div>Snehasish Kumar</div><div>School of Computing Science</div><div>Simon Fraser University</div><div><br></div><div><br></div><div>References : </div><div>[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.</div><div>[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.</div><div>[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.</div><div>[Preuss10] <a href="http://lists.llvm.org/pipermail/llvm-dev/2010-December/036790.html">http://lists.llvm.org/pipermail/llvm-dev/2010-December/036790.html</a></div><div><br></div></div>