This MedLibrary.org supplementary page on Common subexpression elimination is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:
Related Sponsors
In computer science, common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (ie, they all evaluate to the same value), and analyses whether it is worthwhile replacing them with a single variable holding the computed value.
In the following example:
a = b * c + g; d = b * c * d;
it may be worth (ie, program executes faster) transforming the code so that it is translated as if it had been written:
tmp = b * c; a = tmp + g; d = tmp * d;
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.
In simple cases like this, 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.
The benefits of performing CSE are great enough that it is a commonly used optimization.
Compilers need to be judicious about the number of temporaries created to hold values; 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.
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 of which expressions are available at which points in a procedure.
References
- Steven S. Muchnick, Advanced Compiler Design and Implementation (Morgan Kaufmann, 1997) pp. 378-396
- John Cocke. "Global Common Subexpression Elimination." Proceedings of a Symposium on Compiler Construction, ACM SIGPLAN Notices 5(7), July 1970, pages 850-856.
- Briggs, Preston, Cooper, Keith D., and Simpson, L. Taylor. "Value Numbering." Software-Practice and Experience, 27(6), June 1997, pages 701-724.
Wikipedia content modification information:
- This page was last modified on 22 September 2008, at 13:47.
Wikipedia Authorship and Review
Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.
Wikipedia Usage Guidelines
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Common subexpression elimination".
The URL for this specific entry is:
All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.