Common subexpression elimination
|
|
In compiler theory, common subexpression elimination (CSE) is the practice of finding repeated redundant expression evaluations, and replacing them with a single computation assigned to a temporary variable. Although it can be done manually, the term usually refers to a compiler optimization.
Here is a simple example:
a = b * c + g; d = b * c * d; e = b * c;
which does four multiplies and one addition, can be replaced by
tmp = b * c; a = tmp + g; d = tmp * d; e = tmp;
which does only two multiplies and one addition.
Although in simple cases like this, most programmers will habitually create "tmp" while writing the code, the compiler optimization becomes more important in the case of C macros, where macro expansions may result in common subexpressions not apparent in the original source, or in code sequences generated by the compiler, such as for array indexing calculations, or after inline expansion.
CSE is usually advantageous, but the compiler needs to be judicious about the number of subexpressions it saves in temporaries; a excessive number of temporary values creates register pressure possibly resulting in register allocation saving and loading temporaries to/from memory, which may take longer than simply recomputing an arithmetic result when it is needed.
Compiler writers distinguish two kinds of CSE:
- local common subexpression elimination works within a single basic block and is thus a simple optimization to implement.
- global common subexpression elimination works on an entire procedure, and relies on dataflow analysis which expressions are available at which points in a procedure.
Reference
- Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kauffmann, 1997) pp. 378-396