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. A diagram of the operation of an ideal compiler. ... An expression combines numbers, operators, and/or free variables and bound variables: bound variables are defined in the expression (they are for internal use), free variables are taken from the context. ... Compiler optimization techniques are optimization techniques that have been programmed into a compiler. ...

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. The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized imperative computer programming language developed in the early 1970s by Ken Thompson and Dennis Ritchie for use on the... A macro in computer science is an abstraction, whereby a certain textual pattern is replaced according to a defined set of rules. ... In computer programming, an array, also known as a vector or list, is one of the simplest data structures. ... In-line expansion or inlining for short is a compiler optimization which expands a function call site into the actual implementation of the function which is called, rather than each call transferring control to a common piece of code. ...

CSE is usually advantageous, but the compiler needs to be judicious about the number of subexpressions it saves in temporaries; an excessive number of temporary values creates register pressure possibly resulting in spilling registers to memory, which may take longer than simply recomputing an arithmetic result when it is needed. (By analogy with spilling the contents of an overfull container. ...

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.

In computing, a basic block is a straight-line piece of code without any jumps or jump targets in the middle; jump targets, if any, start a block, and jumps end a block. ... A simple way to perform dataflow analysis (DFA) of programs is to set up dataflow equations for each node of the control flow graph (CFG) and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i. ...

Reference

• Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kauffmann, 1997) pp. 378-396