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" <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.