Editing Strength reduction (section)

== Code analysis ==
<!--

::''Say what's going to happen. Explain how strength reduction is recognized. Works with other optimizations.''

:::''Focus on values that are constants within a loop''
:::''Focus on [[induction variable]]s -- variables that are incremented/decremented by a constant -- and linear functions of induction variables.''

::''Somewhere explain that operations that used to be expensive on old architectures are now cheap. A load instruction using an index register, for example, will often be able to scale the index register by a power of two. John Cocke's comment that code optimization gains a little performance, but hardware gains a lot.''
-->

Most of a program's execution time is typically spent in a small section of code (called a [[hot spot (computer programming)|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 <code>c</code> and induction variable <code>i</code>
<syntaxhighlight lang="cpp">
c = 7;
for (i = 0; i < N; i++)
{
    y[i] = c * i;
}
</syntaxhighlight>

can be replaced with successive weaker additions
<syntaxhighlight lang="cpp">
c = 7;
k = 0;
for (i = 0; i < N; i++)
{
    y[i] = k;
    k = k + c;
}
</syntaxhighlight>