6 Jan 2001 22:09:53 -0500

Related articles |
---|

non trivial constant folding mpointie@eden-studios.fr (Mickaël Pointier) (2001-01-05) |

Re: non trivial constant folding broeker@physik.rwth-aachen.de (Hans-Bernhard Broeker) (2001-01-05) |

Re: non trivial constant folding mihai@cs.wisc.edu (Mihai Christodorescu) (2001-01-06) |

Re: non trivial constant folding pat@jantar.org (Patryk Zadarnowski) (2001-01-06) |

Re: non trivial constant folding bonzini@gnu.org (2001-01-06) |

Re: non trivial constant folding idbaxter@semdesigns.com (Ira D. Baxter) (2001-01-06) |

Re: non trivial constant folding cfc@world.std.com (Chris F Clark) (2001-01-06) |

Re: non trivial constant folding anton@mips.complang.tuwien.ac.at (2001-01-09) |

Re: non trivial constant folding anton@mips.complang.tuwien.ac.at (2001-01-09) |

[14 later articles] |

From: | "Mihai Christodorescu" <mihai@cs.wisc.edu> |

Newsgroups: | comp.compilers |

Date: | 6 Jan 2001 22:09:53 -0500 |

Organization: | UWisc CS Dept - http://www.cs.wisc.edu/~mihai |

References: | 01-01-015 |

Keywords: | optimize |

Posted-Date: | 06 Jan 2001 22:09:53 EST |

As far as I know, expression rewriting for optimization purposes is

NP-complete. There are some compilers that perform some expression

optimizations, but not really extensive, as you have noticed yourself.

There is also another problem: the optimized expression can behave

differently than the original expression, due to operations being executed

in different order/with different operands. Consider:

"MAXINT + x - 1"

If x is 1, then evaluating MAXINT + x will overflow.

If you optimize the expression to be:

"the_value_of_MAXINT_minus_1 + x"

(i.e. you evaluate MAXINT - 1 at compile time), then if x is 1, the

expression will not overflow. Of course, these are contrived examples, but a

compiler has to work for all cases, not most of the time (OK, at least in

theory).

Mihai

Mihai Christodorescu -=- mihai@cs.wisc.edu - http://www.cs.wisc.edu/~mihai

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.