Editing Common subexpression elimination

{{Short description|Compiler optimization}}
In [[compiler theory]], '''common subexpression elimination''' ('''CSE''') is a [[compiler optimization]] that searches for instances of identical [[Expression (computer science)|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.<ref name="MuchnickAssociates1997">{{cite book|author1=Steven Muchnick|author2=Muchnick and Associates|title=Advanced Compiler Design Implementation|url=https://archive.org/details/advancedcompiler00much|url-access=registration|quote=Common subexpression elimination.|date=15 August 1997|publisher=Morgan Kaufmann|isbn=978-1-55860-320-2}}</ref>

== 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 <code>tmp</code> is less than the cost of calculating <code>b * c</code> an extra time.

== Principle ==
The possibility to perform CSE is based on [[available expression]] analysis (a [[data flow analysis]]). An expression <code>b*c</code> is available at a point ''p'' in a program if: 
* every path from the initial node to p evaluates <code>b*c</code> before reaching ''p'',
* and there are no assignments to <code>b</code> or <code>c</code> after the evaluation but before ''p''.

The cost/benefit analysis performed by an optimizer will calculate whether the cost of the store to <code>tmp</code> 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.

== Benefits ==
{{original research|section|date=September 2017}}

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 code|duplicate expressions]] while writing the code. The greatest source of CSEs are intermediate code sequences generated by the compiler, such as for [[Array data structure|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 (programming language)|C]] [[Macro (computer science)|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. An excessive number of temporary values creates [[register pressure]] possibly resulting in [[register spilling|spilling registers]] to memory, which may take longer than simply recomputing an arithmetic result when it is needed.

==See also==
* [[Global value numbering]]
* [[Loop-invariant code motion]]

==References==
{{Reflist}}
* [[Steven S. Muchnick]], ''[https://books.google.com/books?id=Pq7pHwG1_OkC&dq=%22Common+subexpression+elimination%22&pg=PA378 Advanced Compiler Design and Implementation]'' ([[Morgan Kaufmann]], 1997) pp.&nbsp;378–396
* [[John Cocke (computer scientist)|John Cocke]]. [http://dl.acm.org/citation.cfm?id=390013.808480 "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. "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.7975&rep=rep1&type=pdf Value Numbering]." ''Software-Practice and Experience'', 27(6), June 1997, pages 701-724.

{{Compiler optimizations}}

[[Category:Compiler optimizations]]