Next: A complete exercise Up: Compiler Theory: Code Optimization Previous: Invariant Code Motion

# Induction Variables

A BASIC INDUCTION VARIABLE of a loop is a variable b defined in a statement of the form b := b + n or b := b - n where
• n is a constant, and
• b has no other definitions in the loop.
Knowing the induction variables is very useful. For instance, they may allow us to replace multiplication by addition (often by a constant)

REPLACING MULTIPLICATIONS BY ADDITIONS can be performed by the following algorithms.

• Find every variable c in the loop
• with a single definition
• of the form c := b*m
• where m is a constant and b is a basic induction variable.
• After each occurrence of b:= b + n (or b := b - n) add a statement t := t +p, where p is theconstant n*m
• Replace statement c := b*m by c := t.
• Add a statement t := b*m into the pre-header (initialization) after possible definition of b.

Next: A complete exercise Up: Compiler Theory: Code Optimization Previous: Invariant Code Motion
Marc Moreno Maza
2004-12-02