Re: common sub-expression elimination (DanHicks)
Sun, 5 Feb 1995 05:50:55 GMT

          From comp.compilers

Related articles
common sub-expression elimination sastry@GODEL.MIEL.MOT.COM (1995-02-03)
Re: common sub-expression elimination (1995-02-05)
Re: common sub-expression elimination (1995-02-05)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (DanHicks)
Keywords: optimize
Organization: America Online, Inc. (1-800-827-6364)
References: 95-02-048
Date: Sun, 5 Feb 1995 05:50:55 GMT

Consider the following code with common subexpression


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

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

Post a followup to this message

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