Strength reduction

In compiler construction, strength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts strong multiplications inside a loop into weaker additions – something that frequently occurs in array addressing. Examples of strength reduction include replacing a multiplication within a loop with an addition and replacing exponentiation within a loop with a multiplication. Most of a program's execution time is typically spent in a small section of code (called a hot spot), 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: the values which do not change within the body of a loop. Induction variables: the values which 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 = 7; for (i = 0; i < N; i++) { y[i] = c * i; } can be replaced with successive weaker additions c = 7; k = 0; for (i = 0; i < N; i++) { y[i] = k; k = k + c; } Below is an example that will strength-reduce all the loop multiplications that arose from array indexing address calculations. Imagine a simple loop that sets an array to the identity matrix. for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { A[i,j] = 0.0; } A[i,i] = 1.