Re: GCC optimizes integer overflow: bug or feature?

[Ian Lance Taylor]

Paul Eggert <address@hidden> writes:

> What worries me is code like this (taken from GNU expr; the vars are
> long long int):
> 
>             val = l->u.i * r->u.i;
>             if (! (l->u.i == 0 || r->u.i == 0
>                    || ((val < 0) == ((l->u.i < 0) ^ (r->u.i < 0))
>                        && val / l->u.i == r->u.i)))
>               integer_overflow ('*');
> 
> This breaks if signed integer overflow has undefined behavior.

For what it's worth, this code works as you expect with current
mainline: gcc does not remove the overflow test.

(As Joseph mentioned, this can be written fully safely by casting to
an unsigned type.)

We can identify all the places where gcc relies on the undefinedness
of signed overflow by looking for all tests of flag_wrapv (barring
bugs, of course).  Interestingly, a number of tests of flag_wrapv
exist merely to avoid optimizations which may cause signed overflow,
since the resulting code may then be optimized such that it breaks the
original intent.

I think it might be interesting to add -Wundefined-signed-overflow to
warn about every case where gcc assumes that signed overflow is
undefined.  This would not be difficult.  It would be interesting to
see how many warnings it generates for real code.  This warning should
probably not be part of -Wall.

Here is a quick list of optimizations that mainline gcc performs which
rely on the idea that signed overflow is undefined.  All the types
are, of course, signed.  I made have made some mistakes.  I think this
gives a good feel for the sorts of optimizations we can make with this
assumption.

* Fold (- (A / B)) to (A / - B) or (- A / B).

* Fold ((- A) / B) to (A / - B), or (A / - B) to ((- A) / B) (where it
  seems profitable).

* Fold ((A + C1) cmp C2) to (A cmp (C1 + C2)) where C1 and C2 are
  constants, and likewise for -.

* Fold ((A + C1) cmp (B + C2)) to (A cmp (B + C1 + C2)) where C1 and
  C2 are constants, and likewise for -.

* Fold simple comparisons like (X - C > X) to false.

* Assume that abs (X) >= 0 when simplifying comparisons and divisions
  (we can't assume this when -fwrapv is used, because abs (INT_MIN) ==
  INT_MIN).

* Simplify abs (X) < 0 to false, and simplify abs (X) >= 0 to true.

* Assume that if X >= 0 and Y >= 0, then X + Y != 0 exactly when X != 0
  or Y != 0.  This is used primarily when simplifying comparisons
  against NULL.

* Assume that X * Y != 0 exactly when X != 0 and Y != 0.

* In range tests, assume that (low < A + C < high) is equivalent to
  (low - C < A < high - C).

* Transform ((A + C1) * C2), to (A + C1 * C2) even if (C1 * C2)
  overflows.  Likewise for ((A + C1) / C2) if C1 is a multiple of C2.
  Likewise for - instead of +.  (This seems like it might be an
  inappropriate optimization (extract_muldiv_1 in fold-const.c).)

* Try to reduce the magnitude of the constant in comparisons:
  + C <= A ==> C - 1 < A.
  + - CST < A ==> - CST - 1 <= A.
  + C > A ==> C - 1 >= A.
  + - C >= A ==> - C - 1 > A.
  + A - C < B ==> A - C - 1 <= B.
  + A + C > B ==> A + C - 1 >= B.
  + A + C <= B ==> A + C - 1 < B.
  + A - C >= B ==> A - C - 1 > B.

* -fwrapv affects handling of pointer types in some cases; I'm not
  really sure why.  See, e.g., maybe_canonicalize_comparison in
  fold-const.c "In principle pointers also have undefined overflow
  behavior, but that causes problems elsewhere."

* Assume that signed loop induction variables do not overflow.

* Compute the number of iterations in a loop of the form X = INIT; X
  cmp END; X OP= Y by assuming that X will not wrap around.

* VRP optimizations:
  + Assume A < A + C1.
  + Assume A > A - C1 and A - C1 < A.
  + Assume A + C1 > A + C2 <==> C1 > C2, likewise for <.
  + Assume A + C1 > A - C2 and A - C1 < A + C2.
  + Treat signed integer overflow as infinity.
  + Assume that - (range with low value type_MIN) becomes (range with
    high value type_MAX).
  + Assume that abs (type_MIN) != type_MIN.

Ian