[Bug c/50865] New: Invalid code generation for INT64_MIN % -1 on x86_64

[Bug c/50865] New: Invalid code generation for INT64_MIN % -1 on x86_64

[jaak at ristioja dot ee]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

             Bug #: 50865
           Summary: Invalid code generation for INT64_MIN % -1 on x86_64
    Classification: Unclassified
           Product: gcc
           Version: 4.5.3
            Status: UNCONFIRMED
          Severity: blocker
          Priority: P3
         Component: c
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: jaak@ristioja.ee


/*
 * Compiled under 64-bit enviroments with: -O0 -std=c99 -pedantic
 * Happens with GCC 4.5.3 on Gentoo, 4.4.5 on Debian and Apple's 4.2.1 on Mac.
 * The error does not appear when compiler is passed -m32.
 */

#include <inttypes.h>
#include <stdio.h>

#define PRINT_INT64(n, x) printf("(" #n ") r = %" PRId64 "\n", x)

int main(void) {

    /* (1) No crash: */
    PRINT_INT64(1, INT64_MIN % 1);

    /* (2) No crash: */
    {
      volatile int64_t m1 = 1;
      PRINT_INT64(2, INT64_MIN % m1);
    }

    /* (3) No crash: */
    {
      volatile int64_t m2 = -1;
      if (m2 == -1)
          PRINT_INT64(3, INT64_MIN % 1);
      else
          PRINT_INT64(3, INT64_MIN % -m2);
    }

    /* (4) Crash: */
    {
      volatile int64_t m3 = -1;
      PRINT_INT64(4, INT64_MIN % -m3);
    }

    return 0;
}

[Bug c/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[jaak at ristioja dot ee]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #1 from Jaak Ristioja <jaak at ristioja dot ee> 2011-10-25 14:30:41 UTC ---
Compiled with clang 2.9, the code runs correctly.

[Bug c/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[joseph at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #2 from joseph at codesourcery dot com <joseph at codesourcery dot com> 2011-10-25 14:56:55 UTC ---
What do you think is wrong?  C1X makes explicit what was intended before 
then: that both a/b and a%b have undefined behavior if the quotient is not 
representable.  (See bug 30484 for more discussion; the only bug is that 
with -fwrapv this should reliably give 0.)

[Bug c/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[jaak.randmets at cyber dot ee]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Jaak <jaak.randmets at cyber dot ee> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jaak.randmets at cyber dot
                   |                            |ee

--- Comment #3 from Jaak <jaak.randmets at cyber dot ee> 2011-10-25 15:14:00 UTC ---
(In reply to comment #2)
> What do you think is wrong?  C1X makes explicit what was intended before 
> then: that both a/b and a%b have undefined behavior if the quotient is not 
> representable.  (See bug 30484 for more discussion; the only bug is that 
> with -fwrapv this should reliably give 0.)

In all 4 cases the quotient is representable and should evaluate to the result
of "INT64_MIN % 1".

[Bug c/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[joseph at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #4 from joseph at codesourcery dot com <joseph at codesourcery dot com> 2011-10-25 15:52:38 UTC ---
On Tue, 25 Oct 2011, jaak.randmets at cyber dot ee wrote:

> > What do you think is wrong?  C1X makes explicit what was intended before 
> > then: that both a/b and a%b have undefined behavior if the quotient is not 
> > representable.  (See bug 30484 for more discussion; the only bug is that 
> > with -fwrapv this should reliably give 0.)
> 
> In all 4 cases the quotient is representable and should evaluate to the result
> of "INT64_MIN % 1".

The quotient is INT64_MIN / 1, which is one greater than INT64_MAX and is 
not representable.

[Bug c/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[joseph at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #5 from joseph at codesourcery dot com <joseph at codesourcery dot com> 2011-10-25 15:55:28 UTC ---
Ah, I see your point - this is % 1 not % -1, so there does indeed seem to 
be a bug here.

[Bug tree-optimization/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[jsm28 at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Joseph S. Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011-10-25
          Component|c                           |tree-optimization
     Ever Confirmed|0                           |1

--- Comment #6 from Joseph S. Myers <jsm28 at gcc dot gnu.org> 2011-10-25 16:00:13 UTC ---
      /* X % -Y is the same as X % Y.  */
(fold-const.c:fold_binary_loc) would probably be what's wrong here.

[Bug tree-optimization/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[jaak at ristioja dot ee]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #7 from Jaak Ristioja <jaak at ristioja dot ee> 2011-10-25 16:08:19 UTC ---
(In reply to comment #6)
>       /* X % -Y is the same as X % Y.  */
> (fold-const.c:fold_binary_loc) would probably be what's wrong here.

On the other hand
https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow#INT32-C.Ensurethatoperationsonsignedintegersdonotresultinoverflow-Modulo
also refers to C99, saying that X % Y and X % -Y are equivalent.

[Bug tree-optimization/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[joseph at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #8 from joseph at codesourcery dot com <joseph at codesourcery dot com> 2011-10-25 16:18:12 UTC ---
On Tue, 25 Oct 2011, jaak at ristioja dot ee wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865
> 
> --- Comment #7 from Jaak Ristioja <jaak at ristioja dot ee> 2011-10-25 16:08:19 UTC ---
> (In reply to comment #6)
> >       /* X % -Y is the same as X % Y.  */
> > (fold-const.c:fold_binary_loc) would probably be what's wrong here.
> 
> On the other hand
> https://www.securecoding.cert.org/confluence/display/seccode/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow#INT32-C.Ensurethatoperationsonsignedintegersdonotresultinoverflow-Modulo
> also refers to C99, saying that X % Y and X % -Y are equivalent.

Well, they are equivalent where they are both defined, or if you apply C99 
rules to infinite-precision integers.  The problem here is that INT_MIN % 
-1 is undefined (explicitly in C1X) and so a transformation of INT_MIN % 1 
into INT_MIN % -1 is unsafe (the other way round, transforming undefined 
behavior to defined, is fine at least in the absence of -ftrapv).

[Bug tree-optimization/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[jaak at ristioja dot ee]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #9 from Jaak Ristioja <jaak at ristioja dot ee> 2011-10-25 16:37:48 UTC ---
(In reply to comment #8)
> Well, they are equivalent where they are both defined, or if you apply C99 
> rules to infinite-precision integers.  The problem here is that INT_MIN % 
> -1 is undefined (explicitly in C1X) and so a transformation of INT_MIN % 1 
> into INT_MIN % -1 is unsafe (the other way round, transforming undefined 
> behavior to defined, is fine at least in the absence of -ftrapv).

But INT_MIN % 1 is still defined to be zero?

[Bug tree-optimization/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[joseph at codesourcery dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

--- Comment #10 from joseph at codesourcery dot com <joseph at codesourcery dot com> 2011-10-25 17:13:51 UTC ---
On Tue, 25 Oct 2011, jaak at ristioja dot ee wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865
> 
> --- Comment #9 from Jaak Ristioja <jaak at ristioja dot ee> 2011-10-25 16:37:48 UTC ---
> (In reply to comment #8)
> > Well, they are equivalent where they are both defined, or if you apply C99 
> > rules to infinite-precision integers.  The problem here is that INT_MIN % 
> > -1 is undefined (explicitly in C1X) and so a transformation of INT_MIN % 1 
> > into INT_MIN % -1 is unsafe (the other way round, transforming undefined 
> > behavior to defined, is fine at least in the absence of -ftrapv).
> 
> But INT_MIN % 1 is still defined to be zero?

Yes.  INT_MIN % 1 is defined to be zero, since the infinite-precision 
values of both INT_MIN / 1 and INT_MIN % 1 are representable.  INT_MIN % 
-1 is undefined because the infinite-precision value of INT_MIN / -1 is 
not representable in int.

[Bug middle-end/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[mpolacek at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Marek Polacek <mpolacek at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mpolacek at gcc dot gnu.org
          Component|tree-optimization           |middle-end
   Target Milestone|---                         |4.8.4
           Severity|blocker                     |normal

[Bug middle-end/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.4                       |4.8.5

--- Comment #11 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.8.4 has been released.

[Bug middle-end/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[mikpelinux at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Mikael Pettersson <mikpelinux at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mikpelinux at gmail dot com

--- Comment #12 from Mikael Pettersson <mikpelinux at gmail dot com> ---
Created attachment 34323
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34323&action=edit
patch restricting the X % -Y -> X % Y transformation to when it's safe

This proposed patch restricts the X % -Y -> X % Y transformation to cases when
we can be certain that it doesn't result in undefined behaviour, i.e. when Y !=
1 or X != INT_MIN.  Passes bootstrap and testsuite on x86_64-linux so far.

[Bug middle-end/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[Joost.VandeVondele at mat dot ethz.ch]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |Joost.VandeVondele at mat dot ethz
                   |                            |.ch

--- Comment #13 from Joost VandeVondele <Joost.VandeVondele at mat dot ethz.ch> ---
(In reply to Mikael Pettersson from comment #12)
> Created attachment 34323 [details]
> patch restricting the X % -Y -> X % Y transformation to when it's safe
> 
> This proposed patch restricts the X % -Y -> X % Y transformation to cases
> when we can be certain that it doesn't result in undefined behaviour, i.e.
> when Y != 1 or X != INT_MIN.  Passes bootstrap and testsuite on x86_64-linux
> so far.

Shouldn't disabling this be language dependent ? I.e. in Fortran this
transformation is always valid (as integers in conforming programs are always
in the symmetric range).

[Bug middle-end/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[mikpelinux at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Mikael Pettersson <mikpelinux at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #34323|0                           |1
        is obsolete|                            |

--- Comment #14 from Mikael Pettersson <mikpelinux at gmail dot com> ---
Created attachment 34328
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34328&action=edit
patch revised to always allow the transformation for Fortran

Patch revised to not restrict the transformation for Fortran, since the X !=
INT_MIN condition apparently is an invariant there.

[Bug middle-end/50865] Invalid code generation for INT64_MIN % 1 on x86_64

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50865

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.5                       |---