Partial redundancy elimination (PRE) makes partially redundant
computation fully redundant, and then replaces all redundant
computation with copies. PRE thus combines global common subexpression
elimination and loop invariant code motion. This optimization is
traditionally accomplished by solving a set of data flow equations.
In Scale, we can solve it using Chow, et al.
PRE combines global common sub-expression elimination and loop invariant code motion.
This is traditionally accomplished by solving a set of data flow equations.
Scale PRE is based on the SSA form of the Scribble CFG
Traditional PRE
- Go out of SSA form, perform data flow equations, go back into SSA form
Scale PRE
- Maintains SSA information on the fly
- Uses Fred Chow's PRE algorithm
- Sparse algorithm, operates on one lexical expression at a time by traversing use-def links
Return to Scale home page.
(Last changed: March 21, 2007.)