Strength Reduction - Code Analysis

Code Analysis

Most of a program's execution time is typically spent in a small section of code, and that code is often inside a loop that is executed over and over.

A compiler uses methods to identify loops and recognize the characteristics of register values within those loops. For strength reduction, the compiler is interested in

• loop invariants. These are values that do not change within the body of a loop.
• induction variables. These are the values that are being iterated each time through the loop.

Loop invariants are essentially constants within a loop, but their value may change outside of the loop. Induction variables are changing by known amounts. The terms are relative to a particular loop. When loops are nested, an induction variable in the outer loop can be a loop invariant in the inner loop.

Strength reduction looks for expressions involving a loop invariant and an induction variable. Some of those expressions can be simplified. For example, the multiplication of loop invariant c and induction variable i

c = 8; for (i = 0; i < N; i++) { y = c * i; }

can be replaced with successive weaker additions

c = 8; k = 0; for (i = 0; i < N; i++) { y = k; k = k + c; }