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*cbefore reaching p, - and there are no assignments to
borcafter 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.
Read more about this topic: Common Subexpression Elimination
Famous quotes containing the word principle:
“The principle of subordination is the great bond of union and harmony through the universe.”
—Catherine E. Beecher (1800–1878)
“Country people do not behave as if they think life is short; they live on the principle that it is long, and savor variations of the kind best appreciated if most days are the same.”
—Edward Hoagland (b. 1932)
“Experimental work provides the strongest evidence for scientific realism. This is not because we test hypotheses about entities. It is because entities that in principle cannot be ‘observed’ are manipulated to produce a new phenomena
[sic] and to investigate other aspects of nature.”
—Ian Hacking (b. 1936)