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

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

first let me emphasize one thing that you probably missed (as some
of your comments suggest):  The ivcanon patch does not have problems
with semantics of overflow of signed arithmetics, since all induction
variables it creates are unsigned.

Now some comments to what you said below:

> On Sat, 21 Aug 2004, Zdenek Dvorak wrote:
> > If I understand you correctly, what you say here is that all this
> > -fwrapv discussion is completely irrelevant to the original problem,
> > i.e. if there are optimizations in gcc that assume that signed
> > arithmetics does not overflow?
> 
> It is relevant to your patch, and the reason why RTH refused to approve
> it.  Yes, GCC contains optimizations that assume that signed arithmetic
> does not overflow, and this is allowed by the C language specification.

hmm... but what lead me to this question was that you said:

"The flag "-fwrapv" doesn't control whether overflow can or can't
happen", which you again contradict below.

Could you please make the issue clear by telling me whether the
following statements are true:

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.

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.

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

Consequently:

-- unless -ftrapv, it is correct to assume for example that:
     INT_MAX+1 is INT_MIN
     unsigned arithmetic works like signed arithmetic
     arithmetic overflow does wrap around
   (either due to -fwrapv, or the fact that the result is undefined).

-- however unless -fwrapv, it is incorrect to produce expressions in
   signed arithmetics that may overflow, since they would either
     cause error (with -ftrapv), or
     have undefined behavior, which could cause misscompilations in
       other passes (with -fno-trapv -fno-wrapv).

Zdenek

(*) Or we may postulate any other semantics we like for the overflow.
    But I don't know of a case where it would be useful.

> As a result, code transformations have to be extremely careful when
> they change the trapping behaviour of program as many of the assumptions
> that are made may be unsafe or counter-intuitive.
> 
> For example,
> 
>   for (unsigned int u=0; u != N; u++)
> 
> can't be canonicalized to the seemingly equivalent
> 
>   for (int i=0; i != (int)N; i++)
> 
> without falsely assuming and relying on -fwrapv.  This transformation is
> valid for Java, but not for C or C++.  For example, later GCC passes may
> constant propagate N, and then a subsequent loop pass may decide that the
> loop never terminates and entirely eliminate the biv.
> 
> You're assuming and relying on the fact that GCC doesn't already contain
> the allowable optimization of "for (int i=0; i!=-1; i++)" into "for(;;)".
> 
> 
> Its a mistake to assume or rely on arithmetic overflow does wrap around,
> that INT_MAX+1 is INT_MIN, that unsigned arithmetic works like signed
> arithmetic, that the tree optimizers make the same assumptions as the
> RTL optimizers.  The problem is that a low-level programmer's sense of
> intuition of what is reasonable, and what can be taken for granted
> doesn't perfectly fit with what the C standard allows.
> 
> We're in a mystical world where "abs(x) >= 0" is always true even if
> x == INT_MIN!?  And arithmetic expressions can have different results
> depending upon whether they're evaluated at run-time vs. compile-time.