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; }
} }
}