Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Common subexpression elimination
Summary
In compiler theory, common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.
In the following code:
a = b * c + g;
d = b * c * e;
it may be worth transforming the code to:
tmp = b * c;
a = tmp + g;
d = tmp * e;
if the cost of storing and retrieving tmp is less than the cost of calculating b * c an extra time.
The possibility to perform CSE is based on available expression analysis (a data flow analysis). An expression bc is available at a point p in a program if:
every path from the initial node to p evaluates bc before reaching p,
and there are no assignments to b or c after the evaluation but before p.
The cost/benefit analysis performed by an optimizer will calculate whether the cost of the store to tmp is less than the cost of the multiplication; in practice other factors such as which values are held in which registers are also significant.
Compiler writers distinguish two kinds of CSE:
local common subexpression elimination works within a single basic block
global common subexpression elimination works on an entire procedure,
Both kinds rely on data flow analysis of which expressions are available at which points in a program.
The benefits of performing CSE are great enough that it is a commonly used optimization.
In simple cases like in the example above, programmers may manually eliminate the duplicate expressions while writing the code. The greatest source of CSEs are intermediate code sequences generated by the compiler, such as for array indexing calculations, where it is not possible for the developer to manually intervene. In some cases language features may create many duplicate expressions. For instance, C macros, where macro expansions may result in common subexpressions not apparent in the original source code.
Compilers need to be judicious about the number of temporaries created to hold values.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.