Re: common sub-expression elimination

>>>
Consider the following code with common subexpression


x=a+b+c
y=b+c+a


With triple or DAG as IR and algorithms discribed in dragon book it is not
possible to identify the RHS of the above two expressions as a common
subexpression.
<<<


The usual solution ot this is to make use of the commutative and
associative properties of addition to place the expression in some
canonical form. For instance, the expression might be reordered into
alphabetical order (or, more realistically, into order of appearance in
the symbol table number). This permits the common subexpression to then
be recognized. Of course to do this you must have "permission" to use the
commutative, and, more importantly, the associative property, even though
computer addition is not really associative (due to the possibility of
overflow, rounding error, etc).


Even if associativity can't be used (due to the problems with computer
arithmetic), you can usually still commute "B+A" into "A+B" (cannonical
form based on alphabetical order again), thereby increasing the chance of
recognizing a CSE. (Ie, computer arithmetic usually IS commutative, even
if it isn't truly associative.)


There are a number of other transformations that can be used with varying
success, but they're all based on the above concepts.


Dan Hicks
--

Return to the comp.compilers page.
Search the comp.compilers archives again.