Enabling Sparse Constant Propagation of Array Elements via Array SSA Form

Abstract

We present a new static analysis technique based on Array SSA form [6]. Compared to traditional SSA form, the key enhancement in Array SSA form is that it deals with arrays at the element level instead of as monolithic objects. In addition, Array SSA form improves the φ function used for merging scalar or array variables in traditional SSA form. The computation of a φ function in traditional SSA form depends on the program’s control flow in addition to the arguments of the φ function. Our improved φ function (referred to as a φ function) includes the relevant control flow information explicitly as arguments through auxiliary variables that are called @ variables.

The @ variables and φ functions were originally introduced as run-time computations in Array SSA form. In this paper, we use the element-level φ functions in Array SSA form for enhanced static analysis. We use Array SSA form to extend past algorithms for Sparse Constant propagation (SC) and Sparse Conditional Constant propagation (SCC) by enabling constant propagation through array elements. In addition, our formulation of array constant propagation as a set of data flow equations enables integration with other analysis algorithms that are based on data flow equations.