Re: non trivial constant folding

"Mihai Christodorescu" <mihai@cs.wisc.edu>6 Jan 2001 22:09:53 -0500

From comp.compilers

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]
| List of all articles for this month |

 From: "Mihai Christodorescu" 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