CSE Elimination

An expression is a Common Subexpression (CSE) if the expression was previously computed and the values of the operands have not changed since the previous computation. Recomputing the expression can be eliminated by using the value of the previous computation.


In the code fragment below, the second computation of the expression (x + y) can be eliminated.

	i = x + y + 1;
	j = x + y;

After CSE Elimination, the code fragment is rewritten as follows.

	t1 = x + y;
	i = t1 + 1;
	j = t1;


Some compilers perform CSE Elimination within an expression and within a basic block, while more sophisticated compilers can perform CSE Elimination across basic blocks.

In theory, CSE Elimination can be performed on a wide range of operators, data types, and storage classes. In practice, few compilers perform CSE Elimination on all operators, data types, and storage classes. For example, some commercially popular compilers limit CSE Elimination to a few operators (e.g. addition, subtraction, and multiplication) for the data types int and unsigned int and the storage classes register and auto.