Embedding Dataflow Information on Arrays into SSA and Extended Optimization Schema for Parallelization

H. Sato (Japan)


SSA, Parallelizing compiler, Compiler optimization,Dataflow analysis


This paper presents an improvement of SSA (static single assignment) to embed dataflow information of arrays. Be cause dataflow representation in SSA is based on names, an extension of SSA to include array analysis needs essential improvement. We regard an array as a collection of individual scalars. By using symbolic analysis, we solve equations between indices, and extend SSA to include arrays. φ functions are extended to δ in order to represent dependence on previous iterations. Furthermore, γ is introduced to represent confluence of indexed variables. Optimizations using our extended SSA are also discussed. Scalar optimizations using SSA are naturally extended to arrays. In our model, δ corresponds to synchronization between iterations, and its elimination increases the opportunity of parallelization.

Important Links:

Go Back