[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[vincent-gcc at vinc17 dot net]

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

--- Comment #12 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
(In reply to Joseph S. Myers from comment #10)
> There is still a bug for the -fwrapv case, where clearly both INT_MIN / -1
> and INT_MIN % -1 should be well defined, but probably the extra checks
> if implemented should only be enabled implicitly for -fwrapv, not for C
> standards conformance modes.

I don't understand why it is still a bug for -fwrapv. Mathematically, INT_MIN %
-1 gives 0; there is no wrapping for the modulo. So, -fwrapv shouldn't
introduce a change.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[joseph at codesourcery dot com]

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

--- Comment #13 from joseph at codesourcery dot com <joseph at codesourcery dot com> ---
For -fwrapv, the mathematical values of INT_MIN / -1 and INT_MIN % -1 
should be reduced using modulo arithmetic, so both operations are 
well-defined, and there is a bug then either operation causes SIGFPE or 
fails to produce the correct modulo result.

Without -fwrapv, INT_MIN / -1 is not representable, so "otherwise, the 
behavior of both a/b and a%b is undefined" (C11 and later, considered as a 
defect fix for older standard revisions) applies to make both operations 
undefined, and there is no bug.

That is, there is a bug in the -fwrapv case (when the operations should 
give well-defined results but GCC fails to implement that), but not in the 
-fno-wrapv case because both operations are undefined if either one is.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[vincent-gcc at vinc17 dot net]

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

--- Comment #14 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
Well, you could change the definition of -fwrapv in the same way that the
standard has changed. I mean that the intent of making INT_MIN / -1 undefined
was *only* for a performance reason (not for a mathematical reason). Normally,
-fwrapv should be as fast as without it (except for some optimizations like
VRP, but I would actually expect a program based on -fwrapv to be faster in
general, because the programmer does not have to care about intermediate
overflows). However, if INT_MIN % -1 is defined with -fwrapv, you get a
performance penalty. And ditto for INT_MIN / -1.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[rguenther at suse dot de]

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

--- Comment #15 from rguenther at suse dot de <rguenther at suse dot de> ---
On Mon, 23 Aug 2021, vincent-gcc at vinc17 dot net wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30484
> 
> --- Comment #14 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
> Well, you could change the definition of -fwrapv in the same way that the
> standard has changed. I mean that the intent of making INT_MIN / -1 undefined
> was *only* for a performance reason (not for a mathematical reason). Normally,
> -fwrapv should be as fast as without it (except for some optimizations like
> VRP, but I would actually expect a program based on -fwrapv to be faster in
> general, because the programmer does not have to care about intermediate
> overflows).

On the contrary - -fwrapv allows the compiler to make less assumptions
and thus usually results in slower code.  Given overflow is undefined
with -fno-wrapv the actual operation code generation can generate the
same code as with -fwrapv so it should never be slower even on the
machine instruction level.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[vincent-gcc at vinc17 dot net]

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

--- Comment #16 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
The issue is that the source code assuming -fno-wrapv may be more complex, thus
giving slower generated code. Here's an example, which consists in adding 3
signed integers, for which the user knows that the sum is representable, so
that the only issue is a potential integer overflow in the first addition. I've
used GCC 11.2.0 on x86_64.

With -fwrapv, the integer overflow is well-defined as wrapping, so that the
user can write:

int f (int a, int b, int c)
{
  return a + b + c;
}

The generated code with -O3 -fwrapv has 2 instructions (the 2 additions):

        addl    %edx, %esi
        leal    (%rsi,%rdi), %eax

But without -fwrapv, one needs to make sure that one doesn't get any integer
overflow. Assume that the user knows that there is a single negative number
among the 3 integers, so that using this negative number in the first addition
will avoid an integer overflow. So the user can write:

int f (int a, int b, int c)
{
  if (b < 0)
    return a + b + c;
  else
    return a + c + b;
}

The generated code with -O3 has 6 instructions:

        leal    (%rdi,%rdx), %eax
        addl    %esi, %edi
        addl    %edx, %edi
        addl    %esi, %eax
        testl   %esi, %esi
        cmovs   %edi, %eax

In theory, the compiler could normally optimize to produce the same code as
with the source that assumes -fwrapv (here, a + b + c and a + c + b are
obviously equivalent on a typical processor), but in practice, this is often
not the case as shown above.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[rguenther at suse dot de]

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

--- Comment #17 from rguenther at suse dot de <rguenther at suse dot de> ---
On Tue, 24 Aug 2021, vincent-gcc at vinc17 dot net wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=30484
> 
> --- Comment #16 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
> The issue is that the source code assuming -fno-wrapv may be more complex, thus
> giving slower generated code. Here's an example, which consists in adding 3
> signed integers, for which the user knows that the sum is representable, so
> that the only issue is a potential integer overflow in the first addition. I've
> used GCC 11.2.0 on x86_64.
> 
> With -fwrapv, the integer overflow is well-defined as wrapping, so that the
> user can write:
> 
> int f (int a, int b, int c)
> {
>   return a + b + c;
> }
> 
> The generated code with -O3 -fwrapv has 2 instructions (the 2 additions):
> 
>         addl    %edx, %esi
>         leal    (%rsi,%rdi), %eax
> 
> But without -fwrapv, one needs to make sure that one doesn't get any integer
> overflow. Assume that the user knows that there is a single negative number
> among the 3 integers, so that using this negative number in the first addition
> will avoid an integer overflow. So the user can write:
> 
> int f (int a, int b, int c)
> {
>   if (b < 0)
>     return a + b + c;
>   else
>     return a + c + b;
> }
> 
> The generated code with -O3 has 6 instructions:
> 
>         leal    (%rdi,%rdx), %eax
>         addl    %esi, %edi
>         addl    %edx, %edi
>         addl    %esi, %eax
>         testl   %esi, %esi
>         cmovs   %edi, %eax

True.  The user could have written the following though:

int f (int a, int b, int c)
{
  return (unsigned)a + b + c;
}

or alternatively

int f (int a, int b, int c)
{ 
  return (long)a + b + c;
} 

both of which produce optimal code.

> In theory, the compiler could normally optimize to produce the same code as
> with the source that assumes -fwrapv (here, a + b + c and a + c + b are
> obviously equivalent on a typical processor), but in practice, this is often
> not the case as shown above.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[vincent-gcc at vinc17 dot net]

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

--- Comment #18 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
(In reply to Vincent Lefèvre from comment #16)
> int f (int a, int b, int c)
> {
>   if (b < 0)
>     return a + b + c;
>   else
>     return a + c + b;
> }
> 
> The generated code with -O3 has 6 instructions:
> 
>         leal    (%rdi,%rdx), %eax
>         addl    %esi, %edi
>         addl    %edx, %edi
>         addl    %esi, %eax
>         testl   %esi, %esi
>         cmovs   %edi, %eax
> 
> In theory, the compiler could normally optimize to produce the same code as
> with the source that assumes -fwrapv (here, a + b + c and a + c + b are
> obviously equivalent on a typical processor), but in practice, this is often
> not the case as shown above.

Surprisingly, GCC can optimize this second test to 2 instructions with -fwrapv.
I've reported PR102032 about the missed optimization without -fwrapv.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv

[vincent-gcc at vinc17 dot net]

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

--- Comment #19 from Vincent Lefèvre <vincent-gcc at vinc17 dot net> ---
(In reply to rguenther@suse.de from comment #17)
> True.  The user could have written the following though:
> 
> int f (int a, int b, int c)
> {
>   return (unsigned)a + b + c;
> }

This code is incorrect, as based on an implementation-defined behavior.

> or alternatively
> 
> int f (int a, int b, int c)
> { 
>   return (long)a + b + c;
> } 

This code is incorrect, and it may yield an integer overflow when long = int,
e.g. on 32-bit processors.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|INT_MIN % -1 is well        |INT_MIN % -1 is well
                   |defined for -fwrapv         |defined for -fwrapv but
                   |                            |traps on x86
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2023-09-18
             Status|UNCONFIRMED                 |NEW
             Target|                            |x86_64-*-*

--- Comment #20 from Richard Biener <rguenth at gcc dot gnu.org> ---
Re-confirmed.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86

[rguenth at gcc dot gnu.org]

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

--- Comment #21 from Richard Biener <rguenth at gcc dot gnu.org> ---
operation_could_trap_helper_p is also wrong in only checking for integer_zerop
on the divisor though a literal x / -1 could be optimized to x * -1 and thus
safely rewritten to unsigned arithmetic.  Likewise RTLs may_trap_p_1 is wrong
in the same way (that can also look at the first operand though).  We might
also want to have a SDIV_TRAPS_ON_OVERFLOW (mode) target hook which is half
of the work to fix this very bug at RTL expansion time (not sure if we want
to diverge earlier).

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |rguenth at gcc dot gnu.org
             Status|NEW                         |ASSIGNED

--- Comment #22 from Richard Biener <rguenth at gcc dot gnu.org> ---
Mine.

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86

[rguenth at gcc dot gnu.org]

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

--- Comment #23 from Richard Biener <rguenth at gcc dot gnu.org> ---
RTL documents no specific behavior for 'div' but says 'ss_div' "ensures that an
out-of-bounds result saturates to the maximum or minimum signed value".

I'm not sure we want target specific semantics for the RTL IL, but since
x86 at least has a valid 'div' for the case overflow is undefined we probably
have to assume div by minus one might trap.  Practically we already assume
that give we simplify division by -1 to negate and have to assume that
division by a non-constant amount traps since it could be a division by zero.

That means practically speaking the -fwrapv issue remains.  Since RTL
doesn't document any specific behavior we have to generally expand signed
division differently.

Using

  b == -1 ? -a : a / b

will for example generate

        cmpl    $-1, %esi
        je      .L5
        cltd
        idivl   %esi
...

.L5:
        negl    %eax
...


We'd expect the following to pass.  I wonder how many targets FAIL it, thus
whether we can require that RTL sdiv has the desired overflow behavior for
-fwrapv (it always appeared to me that RTL behaves as if -fwrapv).  It
works fine with the libgcc implementation for int128.

/* { dg-additional-options "-fwrapv" } */

#define TYPE int
#define UTYPE unsigned

//#define TYPE __int128_t
//#define UTYPE __uint128_t

TYPE __attribute__((noipa))
div (TYPE a, TYPE b)
{
  return a / b;
}

TYPE __attribute__((noipa))
neg (TYPE a)
{
  return -a;
}

int main()
{
  TYPE min = (TYPE)((UTYPE)1 << (sizeof(TYPE)*8-1));
  if (div (min, -1) != min
      || neg (min) != min)
    __builtin_abort ();
  return 0;
}

[Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |uros at gcc dot gnu.org

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> ---
So in case we declare this a bug in the backend and we'd really want to check
flag_wrapv in the machine description we could widen + truncate or
conditionalize the minus one divisor.  There are quite some division patterns
though.