Re: GCC optimizes integer overflow: bug or feature?

[Ian Lance Taylor <iant at google dot com>]

Paul Eggert <eggert@CS.UCLA.EDU> writes:

> That probably sounds vague, so here's the code that beta
> gcc -O2 actually broke (which started this whole thread):
> 
>       int j;
>       for (j = 1; 0 < j; j *= 2)
> 	if (! bigtime_test (j))
> 	  return 1;

It's interesting to note that in gcc 4.1 this turns into, essentially,

  for (j = 1, i = 0; i != 31; j *= 2, ++i)
   ...

That is, gcc 4.1 assumes wrapping semantics and works out that the
loop will iterate (up to) 31 times (I'm testing on a 32-bit system,
obviously).  This is also what mainline gcc does if you use -fwrapv.

> Here it is obvious to a programmer that the comparison is
> intended to do overflow checking, even though the test
> controls the loop.  Can gcc -O2 be made "smart" enough to
> notice this, and not optimize away the test?

Although this is in a loop, the test is actually being removed by VRP.
VRP cunningly sees that j has the range [1, +INF] in all cases.
Therefore, 0 < j is always true, and the test can be removed.  Using
the -fno-tree-vrp option causes the code to work as the programmer
expected.

Basically, VRP sees that j > 0, because the loop condition already
held.  Then it multiplies it by two.  Without -fwrapv, it concludes
that j > 0 is still true.  Then it tests the loop condition again, and
discovers that it is definitely true.  This is more or less the sort
of thing which VRP is supposed to do.

We could disable VRP's assumptions about signed overflow.  I don't
know what else we could do to fix this case.  I don't even know how we
could issue a useful warning.  Perhaps there is a way.

> Another question for the GCC experts: would it fix the bug
> if we replaced "j *= 2" with "j <<= 1" in this sample code?

Well, mainline VRP isn't clever enough to understand that case.  But
it doesn't make the code any more defined.  A left shift of a signed
value to a value which can not be represented in the signed type is
also undefined (C99 6.5.7).


> I ask the latter question partly because nobody has yet
> proposed a portable fix for this bug.  The patch proposed in
> <http://lists.gnu.org/archive/html/bug-gnulib/2006-12/msg00084.html>
> worked for Ralf, but it does not work in general.  It
> attacks the problem by changing "int j" to "unsigned j".
> But because bigtime_test wants an int, this causes the test
> program to compute the equivalent of (int) ((unsigned int)
> INT_MAX + 1), and C99 says that if you cannot assume
> wrapping semantics this expression has undefined behavior in
> the common case where INT_MAX < UINT_MAX.

No, as Joseph says, conversion from a unsigned value to a signed value
is implementation defined (C99 6.3.1.3).

Ian