Sun, 5 Feb 1995 05:50:55 GMT

Related articles |
---|

common sub-expression elimination sastry@GODEL.MIEL.MOT.COM (1995-02-03) |

Re: common sub-expression elimination danhicks@aol.com (1995-02-05) |

Re: common sub-expression elimination preston@tera.com (1995-02-05) |

Newsgroups: | comp.compilers |

From: | danhicks@aol.com (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

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.