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.