Induction variable (IV) substitution pass recognizes and
substitutes induction variables in loops that take the form of
iv = iv + expr
. This form of assignment prevents the
automatic parallelizer from performing analysis and code generation, due
to the data dependence on the assignment operation. Our IV pass detects
such induction variables and replaces them with equivalent expressions
in terms of relevant loop index variables. The scope of the IV pass is
up to detection and substitution of Generalized Inudction
Variables (GIV) with additive induction operations; it allows
multiple induction operations on a variable in a multiply nested loop,
and the increment expression should not contain any loop-variant
variables other than other induction variables. The following example
shows an input program and a transformed code with our IV pass.
iv = 1; for (i=0; i<10; i++) { iv = 1; iv = iv+1; for (i=0; i<10; i++) { ... = iv; ... = 2+41*i; for (j=0; j<20; j++) { --> for (j=0; j<20; j++) { iv += 2; ... = 4+41*i+2*j; ... = iv; } } } }