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)
“On principle I dislike an oath which requires a man to swear he has not done wrong. It rejects the Christian principle of forgiveness on terms of repentance. I think it is enough if the man does no wrong hereafter.”
—Abraham Lincoln (1809–1865)
“It were as wise to cast a violet into a crucible that you might discover the formal principle of its colour and odour, as seek to transfuse from one language into another the creations of a poet. The plant must spring again from its seed, or it will bear no flower—and this is the burthen of the curse of Babel.”
—Percy Bysshe Shelley (1792–1822)