Common subexpression elimination

Common subexpression elimination, usually shortened to CSE, is a compiler optimization that searches a program for instances of identical expressions, ones that all evaluate to the same value, and decides whether it is worthwhile to replace them with a single variable holding the computed value. For instance, if b times c is computed twice, the compiler may store it once in a temporary and reuse it, provided storing and fetching the temporary costs less than another multiplication. The optimization rests on available expression analysis, a data flow analysis: an expression is available at a point if every path from the start evaluates it first and neither of its operands is reassigned in between. Compiler writers distinguish local elimination, within a single basic block, from global elimination across a whole procedure. Most duplicates come from compiler-generated code such as array indexing, and too many temporaries can cause register pressure and spilling, so an optimizer must judge each case.