Strength reduction

Strength reduction is a compiler optimization in which expensive operations are replaced with equivalent but cheaper ones. The classic case converts multiplications inside a loop into additions, which often arises in array addressing, because most execution time is spent in small hot spots that sit inside loops. To apply it the compiler finds loop invariants, values that do not change in the loop body, and induction variables, values that change by known amounts each pass, and rewrites expressions that combine the two. Beyond loops, operator strength reduction uses mathematical identities, for example replacing a multiplication or division by a power of two with a shift, a multiplication by a constant with shifts and adds, or an integer division by a constant with a multiplication. A related form, recursive strength reduction on an induction variable, replaces a function of a changing variable with a simpler calculation from previous values. How much it helps depends on the target processor and the surrounding code.