Strength reduction

From Wikipedia, the free encyclopedia

Strength reduction is a compiler optimization where a costly operation is replaced with an equivalent, but less expensive operation.

Operator strength reduction involves using mathematical identities to replace slow math operations with faster operations. Examples of this include: replacing integer division or multiplication by a power of 2 with a shift operation, replacing integer division by a constant with reciprocal multiplication, and replacing integer multiplication by a constant with a combination of shifts, adds or subtracts. The cost and benefits will depend highly on the target CPU and sometimes on the surrounding code (depending on availability of other functional units within the CPU).

Examples:

original calculation	replacement calculation
y = x / 8	y = x >> 3
y = x * 64	y = x << 6
y = x * 2.0	y = x + x
y = x * 15	y = (x << 4) - x

Induction variable or recursive strength reduction replaces a function of some systematically changing variable with a simpler calculation using previous values of the function. In a procedural programming language this would apply to an expression involving a loop variable and in a declarative language it would apply to the argument of a recursive function. E.g.

f x = ... (2 ** x) ... (f (x + 1)) ...

becomes

f x = f' x (2 ** x)
where
  f' x z = ... z ... (f' (x + 1) (2 * z)) ...

Here the expensive operation (2 ** x) has been replaced by the cheaper (2 * z) in the recursive function f'. This maintains the invariant that z = 2 ** x for any call to f'.

This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.