next up previous
Next: Array Analysis Up: Parallelization Analysis Algorithms Previous: Parallelization Analysis Algorithms

Scalar Analysis

  Our system has interprocedural scalar analysis that encompasses both scalar parallelization analysis and scalar symbolic analysis. For the scalar parallelization analysis, simple flow-insensitive analysis --- interprocedural analysis that does not consider control flow within a procedure --- provides the information to locate scalar dependences and scalar reductions. Recognizing privatizable scalars is more complex, requiring a bottom-up flow-sensitive region-based analysis to find upwards-exposed reads at loop boundaries.

An interprocedural symbolic analysis combines constant propagation, value numbering, and induction variable recognition. The analysis is performed, through a region-based analysis, in two passes over the call graph. Procedures and regions are summarized by scalar value maps, which describe variable values on exit as an arbitrary expression of variable values on entry. The top-down pass determines symbolic values for integer variables in terms of loop indices and loop invariants, and selectively clones based on symbolic values used in the procedure. This analysis also provides support for analyzing some non-linear array subscripts. The analysis recognizes higher-order induction variables (such as MRSIJ in the MI loop of Figure 1(a)) and provides an approximation of the information to the array analysis as a set of additional linear inequality constraints. This simple approach captures what is required to analyze many non-linear subscript expressions without the need to adopt sophisticated non-linear dependence tests [4,19].

A separate top-down interprocedural context analysis propagates contextual relations (in the loop-relative terms obtained from the symbolic analysis) from enclosing IF predicates and loop bounds; a context of relations is represented as a set of systems of linear equalities similar to the array summary descriptors described below.

Saman Amarasinghe
Fri Sep 15 09:15:06 PDT 1995