Loop-Invariant Computations and Code Motion

Induction Variable Detection and Elimination

Strength Reduction

Loop Unrolling

Loop Jamming (Fusion)

Counting up to Zero

Unswitching

Loop Collapse

Although strength reduction is, strictly speaking, a global optimization, it rarely pays off except in loops.

Consider the multiplication in Example 11. Since d is an induction variable, we can replace the induction expression i * 3 by initializing d to its initial value, 3, outside the loop and then adding 3 on each loop iteration. This is shown in Example 12.

EXAMPLE 12 Strength reduction

        t := b * c                      t := b * c
         FOR i := 1 to 10000 DO          d := 0
          BEGIN                          FOR i := 1 TO 10000 DO
            a := t                       BEGIN
            d := i * 3                           a := t
            ...                                  d := d + 3
          END                                    ...
                                           END

We have shown the example for a strength reduction of a multiplication to an addition, but other strength reductions may be performed also (see Exercise 7).