Software Optimization Techniques #11: Strength Reductions

Continuing our series of blog posts on optimizing embedded software with the aim of improving (i.e. reducing) worst-case execution times, this week’s focus is on strength reductions.

Software optimization techniques which improve worst-case execution times #11: Strength Reductions

Strength reduction is the term used to describe the replacement of an expression with another that computes the same value but requires less execution time to do so.

Examples of strength reductions include:

• Using shift operations on unsigned values to achieve multiplication and division by numbers that are powers of 2. For example: x >> 3 is equivalent to x / 8 and y << 2 is equivalent to y * 4.
• Using the bit-wise AND operator to obtain the remainder when an unsigned value is divided by a number that is a power of 2. For example x & 0x7 is equivalent to x % 8. (This can be particularly useful when dealing with indices into circular buffers).
• Taking advantage of loop variables. For example, multiplying by a loop variable can often be replaced by an addition which is usually a faster operation than multiplication.

Strength reductions are a common compiler optimisation strategy and are done as one of the –O2 set of compiler optimisations for the MPC555.

Next week: Leaf functions