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:
“Now, what I want is, Facts. Teach these boys and girls nothing but Facts. Facts alone are wanted in life. Plant nothing else, and root out everything else. You can only form the minds of reasoning animals upon Facts: nothing else will ever be of any service to them. This is the principle on which I bring up my own children, and this is the principle on which I bring up these children. Stick to Facts, sir!”
—Charles Dickens (1812–1870)
“I sincerely believe ... that banking establishments are more dangerous than standing armies, and that the principle of spending money to be paid by posterity, under the name of funding, is but swindling futurity on a large scale.”
—Thomas Jefferson (1743–1826)
“Whether our feet are compressed in iron shoes, our faces hidden with veils and masks; whether yoked with cows to draw the plow through its furrows, or classed with idiots, lunatics and criminals in the laws and constitutions of the State, the principle is the same; for the humiliations of the spirit are as real as the visible badges of servitude.”
—Elizabeth Cady Stanton (1815–1902)