public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
@ 2021-08-22 23:54 ` vincent-gcc at vinc17 dot net
2021-08-23 19:44 ` joseph at codesourcery dot com
` (11 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: vincent-gcc at vinc17 dot net @ 2021-08-22 23:54 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
2021-08-22 23:54 ` [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv vincent-gcc at vinc17 dot net
@ 2021-08-23 19:44 ` joseph at codesourcery dot com
2021-08-23 21:06 ` vincent-gcc at vinc17 dot net
` (10 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: joseph at codesourcery dot com @ 2021-08-23 19:44 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
2021-08-22 23:54 ` [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv vincent-gcc at vinc17 dot net
2021-08-23 19:44 ` joseph at codesourcery dot com
@ 2021-08-23 21:06 ` vincent-gcc at vinc17 dot net
2021-08-24 6:50 ` rguenther at suse dot de
` (9 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: vincent-gcc at vinc17 dot net @ 2021-08-23 21:06 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (2 preceding siblings ...)
2021-08-23 21:06 ` vincent-gcc at vinc17 dot net
@ 2021-08-24 6:50 ` rguenther at suse dot de
2021-08-24 8:33 ` vincent-gcc at vinc17 dot net
` (8 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: rguenther at suse dot de @ 2021-08-24 6:50 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (3 preceding siblings ...)
2021-08-24 6:50 ` rguenther at suse dot de
@ 2021-08-24 8:33 ` vincent-gcc at vinc17 dot net
2021-08-24 8:38 ` rguenther at suse dot de
` (7 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: vincent-gcc at vinc17 dot net @ 2021-08-24 8:33 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (4 preceding siblings ...)
2021-08-24 8:33 ` vincent-gcc at vinc17 dot net
@ 2021-08-24 8:38 ` rguenther at suse dot de
2021-08-24 8:47 ` vincent-gcc at vinc17 dot net
` (6 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: rguenther at suse dot de @ 2021-08-24 8:38 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (5 preceding siblings ...)
2021-08-24 8:38 ` rguenther at suse dot de
@ 2021-08-24 8:47 ` vincent-gcc at vinc17 dot net
2021-08-24 8:49 ` vincent-gcc at vinc17 dot net
` (5 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: vincent-gcc at vinc17 dot net @ 2021-08-24 8:47 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (6 preceding siblings ...)
2021-08-24 8:47 ` vincent-gcc at vinc17 dot net
@ 2021-08-24 8:49 ` vincent-gcc at vinc17 dot net
2023-09-18 7:36 ` [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86 rguenth at gcc dot gnu.org
` (4 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: vincent-gcc at vinc17 dot net @ 2021-08-24 8:49 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (7 preceding siblings ...)
2021-08-24 8:49 ` vincent-gcc at vinc17 dot net
@ 2023-09-18 7:36 ` rguenth at gcc dot gnu.org
2023-09-18 8:47 ` rguenth at gcc dot gnu.org
` (3 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-09-18 7:36 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (8 preceding siblings ...)
2023-09-18 7:36 ` [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86 rguenth at gcc dot gnu.org
@ 2023-09-18 8:47 ` rguenth at gcc dot gnu.org
2023-09-18 8:47 ` rguenth at gcc dot gnu.org
` (2 subsequent siblings)
12 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-09-18 8:47 UTC (permalink / raw)
To: gcc-bugs
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).
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (9 preceding siblings ...)
2023-09-18 8:47 ` rguenth at gcc dot gnu.org
@ 2023-09-18 8:47 ` rguenth at gcc dot gnu.org
2023-09-19 12:21 ` rguenth at gcc dot gnu.org
2023-09-19 12:28 ` rguenth at gcc dot gnu.org
12 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-09-18 8:47 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (10 preceding siblings ...)
2023-09-18 8:47 ` rguenth at gcc dot gnu.org
@ 2023-09-19 12:21 ` rguenth at gcc dot gnu.org
2023-09-19 12:28 ` rguenth at gcc dot gnu.org
12 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-09-19 12:21 UTC (permalink / raw)
To: gcc-bugs
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;
}
^ permalink raw reply [flat|nested] 13+ messages in thread
* [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
` (11 preceding siblings ...)
2023-09-19 12:21 ` rguenth at gcc dot gnu.org
@ 2023-09-19 12:28 ` rguenth at gcc dot gnu.org
12 siblings, 0 replies; 13+ messages in thread
From: rguenth at gcc dot gnu.org @ 2023-09-19 12:28 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2023-09-19 12:28 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <bug-30484-4@http.gcc.gnu.org/bugzilla/>
2021-08-22 23:54 ` [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv vincent-gcc at vinc17 dot net
2021-08-23 19:44 ` joseph at codesourcery dot com
2021-08-23 21:06 ` vincent-gcc at vinc17 dot net
2021-08-24 6:50 ` rguenther at suse dot de
2021-08-24 8:33 ` vincent-gcc at vinc17 dot net
2021-08-24 8:38 ` rguenther at suse dot de
2021-08-24 8:47 ` vincent-gcc at vinc17 dot net
2021-08-24 8:49 ` vincent-gcc at vinc17 dot net
2023-09-18 7:36 ` [Bug target/30484] INT_MIN % -1 is well defined for -fwrapv but traps on x86 rguenth at gcc dot gnu.org
2023-09-18 8:47 ` rguenth at gcc dot gnu.org
2023-09-18 8:47 ` rguenth at gcc dot gnu.org
2023-09-19 12:21 ` rguenth at gcc dot gnu.org
2023-09-19 12:28 ` rguenth at gcc dot gnu.org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).