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. For future work, we are
exploring the use of Array SSA form for efficient pointer-induced alias analysis, which will be essential for
efficient execution of Java programs on EPIC-style processors.




Static single assignment (SSA) form for scalars has been a significant
advance. It has simplified the way we think about scalar variables. It
has simplified the design of some optimizations and has made other
optimizations more effective. Unfortunately none of this can be said for
SSA form for arrays. Traditional SSA form views an array as a single
object and does not provide element-level data flow information.

In this talk, we introduce an Array SSA form that captures precise
element-level data flow information for array variables. It is general
and simple, and coincides with scalar SSA form when applied to scalar
variables. Array SSA form provides for renaming of array variables and
uses a phi function that identifies the defining assignment for each
array element. The combination of array renaming and the ability to
specify element-level merges of distinct definitions in Array SSA form
significantly increases the potential for program analysis and
transformation. 

As an example of program analysis using Array SSA form, we present a
conditional constant propagation algorithm that can be applied to both
scalar and array variables. The element-level phi functions in Array
SSA form enable constant propagation through array elements and can lead
to discovery of a larger set of constants than previous algorithms. As
an example of program transformation, we discuss the application of
Array SSA form to automatic parallelization. The parallelization
techniques based on Array SSA form exploit the possibility of computing
phi functions at runtime in addition to analyzing array indices at
compile time, and can thus uncover more general forms of loop-level and
region-level parallelism than past techniques.