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.