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.

Fri Sep 15 09:15:06 PDT 1995