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:
“In some things, we Americans leave to other countries the carrying out of the principle that stands at the head of our Declaration of Independence.”
—Herman Melville (1819–1891)
“The principle of all sovereignty resides essentially in the nation.”
—French National Assembly. Declaration of the Rights of Man (Sept. 1791)
“All Protestantism, even the most cold and passive, is a sort of dissent. But the religion most prevalent in our northern colonies is a refinement on the principle of resistance; it is the dissidence of dissent, and the Protestantism of the Protestant religion.”
—Edmund Burke (1729–1797)