next up previous
Next: Inequality Constraints Up: Support for Array Previous: Cloning.

Higher-order Induction Variable Support

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.

Saman Amarasinghe
Mon Oct 2 11:00:22 PDT 1995