[1] The classic example of strength reduction converts strong multiplications inside a loop into weaker additions – something that frequently occurs in array addressing.
(Cooper, Simpson & Vick 1995, p. 1) 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.
Strength reduction looks for expressions involving a loop invariant and an induction variable.
For example, the multiplication of loop invariant c and induction variable i can be replaced with successive weaker additions 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.
Recognition that some variables don't change allows registers to be merged; n is constant, so r2, r4, r7, r12 can be hoisted and collapsed.
That multiplication can be strength reduced by adding 8*r2 each time through the loop.
Induction variable or recursive strength reduction replaces a function of some systematically changing variable with a simpler calculation using previous values of the function.
[5] For example, becomes Here modified recursive function f′ takes a second parameter z = 3 ** x, allowing the expensive computation (3 ** x) to be replaced by the cheaper (3 * z).