Seminar by Subhajit Roy
The Hot Path SSA Form: Extending the Static Single Assignment Form for Speculative Optimizations
Subhajit Roy
Indian Institute of Science, Bangalore
Date: Monday, February 22, 2010
Time: 5:00 PM
Venue: CS101.Abstract:
The Single Static Assignment (SSA) form has been a eminent contribution towards analyzing and transforming programs for compiler optimizations. The factoring of the du-chains by renaming every distinct definition of a variable has been affable to the design of some extremely simple algorithms for existing optimizations and has facilitated the development of new ones. However, speculative optimizations - optimizations targeted towards speeding-up the common cases of a given program - have not been fortunate enough to savor an SSA-like intermediate form. We extend the SSA form for speculative analysis and optimizations by allowing only hot reaching definitions - definitions along frequent acyclic paths in the program profile - to reach its respective uses; we call this representation the Hot Path SSA (HPSSA) form. We propose an algorithm for constructing such a form, and demonstrate its effectiveness by designing a novel optimization - Speculative Sparse Conditional Constant Propagation: an almost obvious extension of Wegman and Zadeck's Sparse Conditional Constant Propagation algorithm. Our experiments on some SPEC 2000 programs proves the potency of such an optimization. We believe that our HPSSA form would be as rewarding to speculative analysis and transformations as the SSA form has been to safe optimizations. This is a joint work with Prof. Y. N. Srikant.
To appear in the International Conference on Compiler Construction 2010.