Paper Info
Title
Constructing HPSSA over SSA
Abstract
The Hot Path SSA (HPSSA) form filled a long-standing void by providing an SSA-like intermediate representation that could weave static program code and run-time profile information in a single data structure, thereby facilitating speculative analyses and optimizations. The original algorithm proposed for the Hot Path SSA construction builds HPSSA over non-SSA programs with interleaved SSA and HPSSA construction passes. In this work, we propose a new algorithm for constructing HPSSA programs from programs in the SSA form. Our new algorithm has the following advantages over the original algorithm: firstly, as all modern compilers have built-in SSA construction passes, it is difficult to incorporate the original algorithm within an existing compiler as it requires the compiler writer to intrude in and retrofit the HPSSA construction stages with the SSA construction pass. Our new algorithm can simply be pipelined next to the SSA construction pass with no modification required to existing passes. Secondly, our new algorithm is more efficient than the original algorithm: the original algorithm needs to process all definitions in the program while our new algorithm processes only the &phis;-functions---a small fraction of all program instructions. Most importantly, our new algorithm is much simpler than the original algorithm. We have implemented our algorithm in the LLVM compiler framework and evaluated its effectiveness by implementing an ILP driven path-profile guided register allocator.
Year
DOI
Venue
2017
10.1145/3078659.3078660
SCOPES
Field
DocType
ISBN
Data structure,Program code,Programming language,Computer science,Parallel computing,Compiler,Dataflow programming,Intermediate language,Allocator,Static single assignment form
Conference
978-1-4503-5039-6
Citations 
PageRank 
References 
0
0.34
14
Authors
3
Name
Order
Citations
PageRank
Smriti Jaiswal100.34
Praveen Hegde200.34
Subhajit Roy34510.84