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. Example 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. Principle The possibility to perform CSE is based on available expression analysis (a data flow analysis). An expression b*c is available at a point p in a program if:
  • every path from the initial node to p evaluates b*c 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 t
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.
Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading