Re: non trivial constant folding

        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

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