Re: [patch] Lno branch merge part 8 -- canonical induction variablecreation

[Roger Sayle <roger at eyesopen dot com>]

On Sun, 22 Aug 2004, Zdenek Dvorak wrote:
> Anyway -- could you please respond to the rest of my mail?  I would
> really like to have all the confusion around -f[wt]rapv we have created
> cleared up.

Sure.


> With -ftrapv, we ensure that signed operations that overflow cause
> error.  In particular we may assume that signed operations do
> not overflow if they are executed correctly.

True.  Not only this, but GCC's optimizers shouldn't introduce an
overflow that wasn't in the original source code, and probably also
shouldn't eliminate an overflow that was in the original source
code.

i.e. Transforming "(x + 6) - 5" into "x + 1" may inadvertantly
remove an overflow, and hence work fine with optimizing compilation
but trigger an abort at -O0.


> With -fwrapv, signed operations have a defined behavior -- the
> modulo one.

True.


> With -fno-trapv -fno-wrapv, we assume that signed operations that
> overflow cause undefined behavior.  In particular the optimizers
> may assume that signed operations do not overflow, or that the
> overflow has the modulo semantics (*), if they need to.

The first part is correct, the second part needs to be refined a
little bit.

The assumptions that a transformation makes my be classified into
two types, preconditions and postconditions.  The preconditions
are assumptions that the transformation makes about the behaviour
of the original code, and the postconditions are assumptions that
a transformation makes about the transformed code.

As you state above, with "-fno-trapv -fno-wrapv", the optimizers
may assume any convenient semantics that they want to for overflow
in the original code, either than signed overflow never occurs,
or that it has modulo semantics or saturates or whatever.

The issue is that the transformation can't make any assumptions
about the behaviour of overflow in the transformed code, i.e.
the postconditions.  A transformation that relies on all later passes
agreeing on the same overflow semantics may be very subtly broken.
Perhaps rarely an RTL optimizer may assume different undefined
semantics leading to incorrect code.


Does this make the issue a bit clearer?  Obviously, any optimization
or transformation that either strictly reduces or perfectly preserves
the overflows of a program is safe with the default "-fno-trapv
-fno-wrapv".  i.e. "(x + 5) - 5  ->  x" is safe, and "(x + 2) + 3
->  x+5" is safe.

However, transformations that increase or change the input values
for which overflow occurs can be potentially hazardous.

For example, "(-x) - y  ->  (-y) - x" has to be guarded by flag_wrapv
as we're assuming something about signed overflow if y is INT_MIN.
Similarly the hypothetical loop transformation
"for(unsigned int u=0; u!=N; u++)" -> "for(int i=0; i!=(int)N; i++)"
relies on the "expected" modulo behaviour of the transformed code.
These are allowable as an RTL transformation or with -fwrapv, but not
be default.  Interestingly the reverse loop transformation, performed by
your patch, is always safe, it makes assumption about overflow in the
original code (which its allowed to do), but generates a canonicalized
loop without any overflow assumptions.



Please don't get me wrong.  I'm not a fan of the current default for
flag_wrapv which I believe can often have counter interuitive consequences
and leads to many subtle and difficult to trace logic errors.  Its also
suprising to GCC's users, c.f. PR 4371.  I'd much prefer a world where
signed and unsigned arithmetic may be relied on to behave equivalently.
If nothing else it would reduce the middle-end maintenance burden.



My apologies again if my explanations of these concepts isn't as clear
as it could be.  You can imagine the world before flag_wrapv where
reviewers would argue over why transformations were safe for C but
not for Java, and vice versa.  The complex semantics of flag_wrapv
allows us to reason about and classify transformations, but as I'd
admitted in an earlier e-mail there are probably numerous latent bugs
still lurking in the compiler because they're not guarded by either
the flag_wrapv or !flag_wrapv that they depend upon.

Roger
--