A long-standing goal for optimizing compilers and program analysis
tools is to find efficient algorithms that can reveal the flow of data
in a program as precisely as possible. Static single assignment (SSA)
form has been a significant advance in this regard for scalar
variables. In this talk, we introduce an Array SSA form that captures
precise element-level data flow information for array variables and
aggregate data types. As an example of program analysis using Array
SSA form, we present a conditional constant propagation algorithm that
can lead to discovery of a larger set of constants than previous
algorithms that analyze only scalar variables. As an example of
program transformation using Array SSA form, we show that its
element-level "phi" functions enable a larger set of loops to be
parallelized than in past work. Finally, we show how Array SSA form
can encompass a limited form of pointer-induced alias analysis in support
of load elimination of object fields and array elements in Java programs.
This work was done jointly with Kathleen Knobe and Stephen Fink.
* Unified Analysis of Array and Object References in Strongly Typed Languages. S.Fink, K.Knobe, V.Sarkar. Proceedings of the 2000 Static Analysis Symposium (SAS ’00), October 2000. http://www.cs.rice.edu/~vsarkar/PDF/sas2000.pdf
* Enhanced Parallelization via Analyses and Transformations on Array SSA Form. K.Knobe, V.Sarkar. Workshop on Compilers for Parallel Computers (CPC), Jan 2000. http://www.cs.rice.edu/~vsarkar/PDF/cpc2000.pdf
* Enabling Sparse Constant Propagation of Array Elements via Array SSA Form. V.Sarkar and K.Knobe. Proceedings of the 1998 Static Analysis Symposium (SAS ’98), October 1998. http://www.cs.rice.edu/~vsarkar/PDF/sas1998.pdf
* Array SSA form and its use in Parallelization. Kathleen Knobe and Vivek Sarkar. Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Diego, California, January 1998. http://doi.acm.org/10.1145/268946.268956