Re: non trivial constant folding

anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:


> "Mihai Christodorescu" <mihai@cs.wisc.edu> writes:
>> 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.
>
>If the original program was code with defined behaviour, differences
>in observable behaviour are not optimization, they are an indication
>of a broken compiler.
>
>And even if the original code had undefined behaviour, a particular
>compiler should implement a consistent behaviour for that, if possible
>(for practical reasons, like finding the bug).


          Why? And what behaviour would you suggest? It may not be
possible for the compiler to detect that a given condition can occur.
Consider the possibility of aliasing. Trying to accommodate the
exceptional cases may result in much slower code for the general case.


>> 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.
>
>Well, if your + does exception-on-overflow, or saturating arithmetic,
>then it is not associative, and you cannot apply this transformation.
>
>OTOH, if your + does modulo arithmetic (aka wrap-around), then it is
>associative, and both expressions will give the same result.
>
>So it comes down to: does the operation satisfy the algebraic laws
>required by the transformation? If not, you cannot apply the
>transformation in an optimizer.


          What are the algebraic rules of overflow? Are there any?


Sincerely,


Gene Wirchenko

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