The closure operation can be extended to recognize higher order induction variables, such as a variable incremented inside a triangular loop. Such variables are not uncommon in scientific codes as linearized array subscripts. To handle 2nd-order induction variables, we extend the iteration operator with an auxiliary map, as follows:

Unfortunately, the resulting closed form of a second-order induction
variable which is thus introduced is non-affine and not directly useful
to the affine parallelization tests used in array analysis.
For this reason, the analysis in this case
introduces a new variable **x**, whose scope is
limited to the loop body, and in place of the non-affine expression
, we use the affine expression
.

When the array analysis performs a comparison between two
accesses containing **x**, the additional affine information is
provided that if, for example, and , then for
iteration we have and for iteration we have
such that if then . Similar
useful affine
information can be provided under other conditions on and .
This approach enables one commonly occurring case of non-affine symbolic values
in array subscripts to be handled without an expensive extension to
the array analysis.

Mon Oct 2 11:00:22 PDT 1995