Re: GCC optimizes integer overflow: bug or feature?
On Tue, 19 Dec 2006, Ian Lance Taylor wrote: 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. Thanks for compiling this exhaustive list, Ian! Currently our documentation on -fwrapv is rather short and does not provide examples or anything to provide such a feel: This option instructs the compiler to assume that signed arithmetic overflow of addition, subtraction and multiplication wraps around using twos-complement representation. This flag enables some optimizations and disables others. This option is enabled by default for the Java front-end, as required by the Java language specification. This flag enables some optimizations and disables others is all we have. I wonder whether you could perhaps add (part of) your list to this documentation? Or would that be too specific? Gerald
Re: GCC optimizes integer overflow: bug or feature?
Currently our documentation on -fwrapv is rather short and does not provide examples or anything to provide such a feel: This option instructs the compiler to assume that signed arithmetic overflow of addition, subtraction and multiplication wraps around using twos-complement representation. This flag enables some optimizations and disables others. This option is enabled by default for the Java front-end, as required by the Java language specification. This flag enables some optimizations and disables others is all we have. I wonder whether you could perhaps add (part of) your list to this documentation? Or would that be too specific? Might it be better to describe this option in terms of the effect on the language, namely to say that it *defines* signed overflow in terms of wrapping, rather than making what would necessarily be vague comments about optimizations?
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-29 00:55:18 -0800, Paul Eggert wrote:
[...]
Obviously this code is buggy, at least in theory, due to the signed
integer overflows. But rewriting it is not so easy, since we have no
INT_MAX to rescue us as we did in the bigtime_test loop. Here's what
I eventually came up with:
for (;;)
{
time_t t = (time_t_max 1) + 1;
if (t = time_t_max)
break;
time_t_max = t;
}
time_t_min = - ((time_t) ~ (time_t) 0 == (time_t) -1) - time_t_max;
This isn't guaranteed to be portable by C99 either, of course; among
other things, left-shift has undefined behavior on signed integer
overflow. I am relying on your heuristic advice to use left shift
rather than multiplication by 2, so that GCC won't mess up here. But
it's a weak heuristic and I'm afraid it doesn't inspire a whole lot of
confidence.
I don't understand why GCC won't mess up.
You should probably use the upper bound obtained from sizeof(time_t)
and CHAR_BIT. As this bound is the actual maximum value when there
are no padding bits, this means that the code will be portable on all
C99 implementations where time_t has no padding bits.
Shouldn't GCC provide an extension to obtain the maximum and minimum
values of integer types?
--
Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/
100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: GCC optimizes integer overflow: bug or feature?
Vincent Lefevre [EMAIL PROTECTED] writes: [...] | Shouldn't GCC provide an extension to obtain the maximum and minimum | values of integer types? GCC already does. I suspect you meant a _generic_ way a la numeric_limits? That is doable. -- Gaby
Re: GCC optimizes integer overflow: bug or feature?
Roberto Bagnara [EMAIL PROTECTED] writes: My reading, instead, is that C99 requires unsigned long long int to have exactly the same number of bits as long long int. Yes, that's correct. Sorry, I got confused between C89 (which is what that Tandem NSK version supports) and C99.
Re: GCC optimizes integer overflow: bug or feature?
Paolo Bonzini [EMAIL PROTECTED] writes:
Or you can do, since elsewhere in the code you compute time_t_max:
for (j = 1; j = time_t_max / 2 + 1; j *= 2)
No, this does not work. It would work to have:
for (j = 1;;)
{
if (j time_t_max / 2)
break;
j *= 2;
}
Oops.
Oops is my thought as well. Even the second version of your code is
incorrect in general, since it assumes that 'int' and 'time_t' are the
same width.
It's surprisingly tricky to get right. This underscores why -O2's
changes in this area are so worrisome.
What I eventually ended up doing -- and this was before reading the
above-quoted email -- was this:
for (j = 1; ; j = 1)
if (! bigtime_test (j))
return 1;
else if (INT_MAX / 2 j)
break;
This is portable and should work on all real platforms.
But that was the easy code! Here's the harder stuff, the
code that computes time_t_max:
static time_t time_t_max;
static time_t time_t_min;
for (time_t_max = 1; 0 time_t_max; time_t_max *= 2)
continue;
time_t_max--;
if ((time_t) -1 0)
for (time_t_min = -1; (time_t) (time_t_min * 2) 0; time_t_min *= 2)
continue;
Obviously this code is buggy, at least in theory, due to the signed
integer overflows. But rewriting it is not so easy, since we have no
INT_MAX to rescue us as we did in the bigtime_test loop. Here's what
I eventually came up with:
for (;;)
{
time_t t = (time_t_max 1) + 1;
if (t = time_t_max)
break;
time_t_max = t;
}
time_t_min = - ((time_t) ~ (time_t) 0 == (time_t) -1) - time_t_max;
This isn't guaranteed to be portable by C99 either, of course; among
other things, left-shift has undefined behavior on signed integer
overflow. I am relying on your heuristic advice to use left shift
rather than multiplication by 2, so that GCC won't mess up here. But
it's a weak heuristic and I'm afraid it doesn't inspire a whole lot of
confidence.
Re: GCC optimizes integer overflow: bug or feature?
Robert Dewar wrote: Valid programs is too narrow a set, you really do have to pay attention to normal usage. I very well remember the Burroughs 5500 compiler, which took advantage of the stack semantics allowed by the standard, but in fact virtually all Fortran programs of the era assumed static allocation since that's what every other compiler did. As a consequence the 5500 Fortran was completely useless, one factor that certainly caused universities I was aassociated with to avoid this machine. [ Sorry for the late reply ] As we say on the committee: Quality of Implementation Issue. -- Toon Moene - e-mail: [EMAIL PROTECTED] - phone: +31 346 214290 Saturnushof 14, 3738 XG Maartensdijk, The Netherlands A maintainer of GNU Fortran: http://gcc.gnu.org/fortran/ Who's working on GNU Fortran: http://gcc.gnu.org/ml/gcc/2006-01/msg0.html
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-20 23:40:45 +0100, Marcin Dalecki wrote: However it's a quite common mistake to forget how bad floats model real numbers. It depends on what you are doing. For instance, thanks to the IEEE-754 standard, it is possible to perform exact computations with floats. By doing unsafe optimizations on floats, gcc may break things. I need to use -ffloat-store on some of my programs (which are not even based on the IEEE-754 standard), otherwise they don't work at all. -- Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/ 100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/ Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-21 17:42:15 -0500, Robert Dewar wrote: Marcin Dalecki wrote: Of course I didn't think about a substitute for ==. Not! However I think that checks for |x-y| epsilion, could be really given a significant speed edge if done in a single go in hardware. One thing to ponder here is that thinks like this are what lead to CISC instruction messes. It just seems obvious to people that it will help efficiency to have highly specialized instructions, but in practice they gum up the architecture with junk, and a careful analysis shows that the actual gain is small at best. How many applications spend a significant amount of time doing such an epsilon test -- best guess: none. Indeed, no-one has requested for one in the revision of IEEE 754, AFAIK. -- Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/ 100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/ Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-19 10:44:25 -0800, Paul Eggert wrote:
Sure, but that is trickier. In many cases code operates on
types like time_t that are signed on some platforms and
unsigned on others. It's easy for such code to test for
overflow if you assume wraparound arithmetic, as code like
{ sum = a + b; if ((sum a) != (b 0)) overflow (); } is
valid regardless of signedness. It's not so easy if you
cannot assume wraparound arithmetic, particularly if
performance is an issue (not the case in GNU expr, but it is
true elsewhere).
If a has the value -2, b has the value 1 and the user expects to
get -1 regardless of signedness of b, then this is not valid.
So, does anyone assume that the compiler should behave as if a + b
in C were a + b on the integer ring just because many programmers
think so, even though this would be non conforming?
--
Vincent Lefèvre [EMAIL PROTECTED] - Web: http://www.vinc17.org/
100% accessible validated (X)HTML - Blog: http://www.vinc17.org/blog/
Work: CR INRIA - computer arithmetic / Arenaire project (LIP, ENS-Lyon)
Re: GCC optimizes integer overflow: bug or feature?
On Fri, Dec 22, 2006 at 01:58:39AM +0100, Denis Vlasenko wrote:
Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):
# cat tt.c
int f(char *p)
{
if (p[0] == 1 p[1] == 2) return 1;
return 0;
}
No, because you'd read past the end of the array:
#include stdlib.h
int main (int argc, char *argv[])
{
char *a;
if ((a == malloc (sizeof (char
{
int r;
a[0] = 1;
r = f (a);
free (a);
return (r);
}
return (0);
}
--
Rask Ingemann Lambertsen
Re: GCC optimizes integer overflow: bug or feature?
On Saturday 23 December 2006 10:06, Rask Ingemann Lambertsen wrote:
No, because you'd read past the end of the array:
#include stdlib.h
int main (int argc, char *argv[])
{
char *a;
if ((a == malloc (sizeof (char
{
int r;
a[0] = 1;
r = f (a);
free (a);
return (r);
}
return (0);
}
Good spotting.
We can use instead of . C standard doesn't
aloow lazy execution of (a b) IIRC...
int f(char *p)
{
if ((p[0] == 1) (p[1] == 2)) return 1;
return 0;
}
Currently it does this:
.file t.c
.text
.p2align 2,,3
.globl f
.type f, @function
f:
movl4(%esp), %edx
cmpb$1, (%edx)
sete%al
cmpb$2, 1(%edx)
sete%dl
andl%edx, %eax
movzbl %al, %eax
ret
.size f, .-f
.ident GCC: (GNU) 4.2.0 20061128 (prerelease)
.section.note.GNU-stack,,@progbits
--
vda
Re: GCC optimizes integer overflow: bug or feature?
On Sat, Dec 23, 2006 at 10:06:54AM +0100, Rask Ingemann Lambertsen wrote: a[0] = 1; Oops, that should be a[0] = 0 or any other value than 1. -- Rask Ingemann Lambertsen
Re: [bug-gnulib] GCC optimizes integer overflow: bug or feature?
On Tue, 19 Dec 2006, Bruno Haible wrote: Paul Eggert wrote: Compiling everything with -fwrapv is simple. It has optimization drawbacks, but if that's the best we can do now, then we'll probably do it. And once we do it, human nature suggests that we will generally not bother with the painstaking analysis needed to omit -fwrapv. Certainly noone will try to analyze megabytes of source code in order to someday be able to omit -fwrapv from the CFLAGS. But if GCC would give a warning every time it does these optimizations which are OK according to C99 but break LIA-1 assumptions, it would be manageable. This way, programmers would have a chance to use 'unsigned int' instead of 'int' in those few places where it matters. Such a warning should be simple to implement: Everywhere you use the value of 'flag_wrapv' in a way that matters, give a warning. No? Bruno Sounds like the -Wstrict-aliasing flag, which was a reasonable aid for the analogous problem with -fstrict-aliasing. There's only 39 places in gcc where flag_wrapv is used. Perhaps not even all of them require the warning. Or at least not all of them necessarily have to be in the first go around. Care to submit a patch? --Kaveh -- Kaveh R. Ghazi [EMAIL PROTECTED]
Re: GCC optimizes integer overflow: bug or feature?
int j; for (j = 1; 0 j; j *= 2) if (! bigtime_test (j)) return 1; Here it is obvious to a programmer that the comparison is intended to do overflow checking, even though the test controls the loop. Well, it's not to me. :-) Another question for the GCC experts: would it fix the bug if we replaced j *= 2 with j = 1 in this sample code? Yes, it will actually compile the code as this: int i, j; for (i = 0, j = 1; i 31; i++) j = 1; Or you can do, since elsewhere in the code you compute time_t_max: for (j = 1; j = time_t_max / 2 + 1; j *= 2) Which is IMO more intention revealing. Paolo
Re: GCC optimizes integer overflow: bug or feature?
Paul Eggert wrote: Roberto Bagnara [EMAIL PROTECTED] writes: (The platform I'm thinking of is Tandem NSK/OSS.) Is this correct? Doesn't C99's 6.2.5#6 mandate that... This is straying from the subject of GCC and into the problems of writing portable C code, but since you asked The Tandem NSK/OSS environment does not claim full conformance to C99. The NSK/OSS community is conservative (fault-tolerance does that do you :-) and has introduced only some C99 features, more as time progresses. The NSK/OSS developers did not introduce 64-bit unsigned int until last year. I'm no expert in the area, but I'd guess that most NSK/OSS production shops are still running older releases, which have 64-bit signed int but only 32-bit unsigned int. I now understand that Tandem NSK/OSS is not conformant, thanks. But he reason I asked is that I interpreted what you wrote, i.e., Also, such an approach assumes that unsigned long long int has at least as many bits as long long int. But this is an unportable assumption; C99 does not require this. as C99 does not require that unsigned long long int has at least as many bits as long long int. My reading, instead, is that C99 requires unsigned long long int to have exactly the same number of bits as long long int. All the best, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: GCC optimizes integer overflow: bug or feature?
Or you can do, since elsewhere in the code you compute time_t_max:
for (j = 1; j = time_t_max / 2 + 1; j *= 2)
No, this does not work. It would work to have:
for (j = 1;;)
{
if (j time_t_max / 2)
break;
j *= 2;
}
Oops.
Paolo
RE: GCC optimizes integer overflow: bug or feature?
On 22 December 2006 00:59, Denis Vlasenko wrote: Or this, absolutely typical C code. i386 arch can compare 16 bits at a time here (luckily, no alighment worries on this arch): Whaddaya mean, no alignment worries? Misaligned accesses *kill* your performance! I know this doesn't affect correctness, but the coder might well have known that the pointer is unaligned and written two separate byte-sized accesses on purpose; volatile isn't the answer because it's too extreme, there's nothing wrong with caching these values in registers and they don't spontaneously change on us. cheers, DaveK -- Can't think of a witty .sigline today
RE: GCC optimizes integer overflow: bug or feature?
On Fri, 2006-12-22 at 17:08 +, Dave Korn wrote: Misaligned accesses *kill* your performance! Maybe on x86, but on PPC, at least for the (current) Cell's PPU misaligned accesses for most cases unaligned are optimal. Thanks, Andrew Pinski
Re: GCC optimizes integer overflow: bug or feature?
Dave Korn wrote: On 22 December 2006 00:59, Denis Vlasenko wrote: Or this, absolutely typical C code. i386 arch can compare 16 bits at a time here (luckily, no alighment worries on this arch): Whaddaya mean, no alignment worries? Misaligned accesses *kill* your performance! is it really worse to do one unaligned 16-bit read, than two separate 8-bit reads? I am surprised ... and of course you have the gain from shorter code, reducing i-cache pressure. I know this doesn't affect correctness, but the coder might well have known that the pointer is unaligned and written two separate byte-sized accesses on purpose; volatile isn't the answer because it's too extreme, there's nothing wrong with caching these values in registers and they don't spontaneously change on us.
Re: GCC optimizes integer overflow: bug or feature?
Andrew Pinski wrote: On Fri, 2006-12-22 at 17:08 +, Dave Korn wrote: Misaligned accesses *kill* your performance! Maybe on x86, but on PPC, at least for the (current) Cell's PPU misaligned accesses for most cases unaligned are optimal. is that true across cache boundaries? Thanks, Andrew Pinski
Re: GCC optimizes integer overflow: bug or feature?
On Fri, 2006-12-22 at 12:30 -0500, Robert Dewar wrote: Maybe on x86, but on PPC, at least for the (current) Cell's PPU misaligned accesses for most cases unaligned are optimal. is that true across cache boundaries? For Cell, crossing the 32byte boundary causes the microcode to happen. But the question is how often does that happen compare to non crossing, I am willing to bet hardly at all, yes I need to test this and I am going to have anyways for my job :). -- Pinski
Re: GCC optimizes integer overflow: bug or feature?
On Friday 22 December 2006 03:03, Paul Brook wrote:
On Friday 22 December 2006 00:58, Denis Vlasenko wrote:
On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
There are a lot of 100.00% safe optimizations which gcc
can do. Value range propagation for bitwise operations, for one
Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):
int f(char *p)
{
if (p[0] == 1 p[1] == 2) return 1;
return 0;
}
Definitely not 100% safe. p may point to memory that is sensitive to the
access width and/or number of accesses. (ie. memory mapped IO).
Take a look what Linux does when you need to touch a MMIO
or PIO areas. In short: it wraps it in macros/inlines
which do all required magic (which may be rather different
on different architectures. For i386, they amount to
*(volatile char*)p).
Simple access to such areas with *p will never work
safely across all spectrum of hardware.
Ok, next example of real-world code I recently saw.
i = N comparisons are completely superfluous -
programmer probably overlooked that fact.
But gcc didn't notice that either and generated 16 bytes extra
for first function:
# cat t3.c
int i64c(int i) {
if (i = 0) return '.';
if (i == 1) return '/';
if (i = 2 i 12) return ('0' - 2 + i);
if (i = 12 i 38) return ('A' - 12 + i);
if (i = 38 i 63) return ('a' - 38 + i);
return 'z';
}
int i64c_2(int i) {
if (i = 0) return '.';
if (i == 1) return '/';
if (i 12) return ('0' - 2 + i);
if (i 38) return ('A' - 12 + i);
if (i 63) return ('a' - 38 + i);
return 'z';
}
# gcc -O2 -c -fomit-frame-pointer t3.c
# nm --size-sort t3.o
0038 T i64c_2
0048 T i64c
# gcc -O2 -S -fomit-frame-pointer t3.c
# cat t3.s
.file t3.c
.text
.p2align 2,,3
.globl i64c
.type i64c, @function
i64c:
movl4(%esp), %edx
testl %edx, %edx
jle .L15
cmpl$1, %edx
je .L16
leal-2(%edx), %eax
cmpl$9, %eax
jbe .L17
leal-12(%edx), %eax
cmpl$25, %eax
jbe .L18
leal-38(%edx), %eax
cmpl$24, %eax
ja .L19
leal59(%edx), %eax
ret
.p2align 2,,3
.L17:
leal46(%edx), %eax
ret
.p2align 2,,3
.L16:
movl$47, %eax
ret
.p2align 2,,3
.L19:
movl$122, %eax
ret
.L18:
leal53(%edx), %eax
ret
.L15:
movl$46, %eax
ret
.size i64c, .-i64c
.p2align 2,,3
.globl i64c_2
.type i64c_2, @function
i64c_2:
movl4(%esp), %eax
testl %eax, %eax
jle .L33
cmpl$1, %eax
je .L34
cmpl$11, %eax
jle .L35
cmpl$37, %eax
jle .L36
cmpl$62, %eax
jg .L37
addl$59, %eax
ret
.p2align 2,,3
.L35:
addl$46, %eax
ret
.p2align 2,,3
.L34:
movb$47, %al
ret
.p2align 2,,3
.L37:
movl$122, %eax
ret
.L36:
addl$53, %eax
ret
.L33:
movl$46, %eax
ret
.size i64c_2, .-i64c_2
.ident GCC: (GNU) 4.2.0 20061128 (prerelease)
.section.note.GNU-stack,,@progbits
--
vda
Re: GCC optimizes integer overflow: bug or feature?
This overflow attitude has some resemblance to the attitude that
resulted in the Y2K issues. I don't try to troll, I have a detailed
explanation below.
Some time ago (a year?) I was told on this mailing-list that code
breakage due to undefinedness of signed overflow is not too common (I at
least claimed with no evidence that it was more than one bug per 1,000
lines). My claim was counterclaimed by something like most of the time
people work with small enough values, so overflows don't happen too many
times in practice. At first, this sounds reasonable. Then, I realized
that it sounds awfully similar to two digits are enough to represent a
year.
You may think that the analogy is far fetched? In that case, I'll pick
some gcc source file, at random and look for signed operations in it:
categorize_ctor_elements_1(..) in gcc/expr.c:
_elts += mult * nz;
elt_count += mult * ic;
Both assume that neither the multiplication, nor the addition overflow.
Can GCC be really sure that this case will be caught outside this
function, before it is called? Will it be always so in the future? You
can't even add an assert to make sure that no overflow had occurred. You
can't write:
temp=mult*nz;
a_gcc_assert(mult !=0 temp/mult==nz);
a_gcc_assert(_elts+temp = _elts);
_elts += temp;
You'd have to add a very weird looking assert like:
some_gcc_assert(
nz !=0 || (unsigned HOST_WIDE_INT)mult*nz/nz == (unsigned
HOST_WIDE_INT)mult
(HOST_WIDE_INT)((unsigned HOST_WIDE_INT)mult*nz) = 0
);
This is very ugly. You see, it was quite easy to find code that works
today but may be easily break due to unrelated code shuffling that
happen in other source files, without any warning!
rant on C standard
I don't understand why the standard committee did not add a new keyword
(say nowrap) instead of going from implementation defined overflows to
undefined. If one wants fast induction variables, it would have been
possible to write:
int f(int k)
{
nowrap int i;
int ret=k;
for (i=0; i = k ; ++i)
++ret;
return ret;
}
and get the code transformed to the simple return k*2+1; which will be
implementation defined for k = MAX_INT/2 and undefined only for k==MAX_INT.
I know, adding a keyword may break existing code, but so does adding
rules for undefined behavior. Having a predictable breakage at compile
time is better than having code break at random at runtime.
/rant
Gabriel Dos Reis wrote:
The problem is that what constitutes a valid program tends to differ
from what constitutes a useful program found in the wild. The
question for GCC is how to accomodate for the useful uses without
getting far away from both conformance and non-conformance.
I don't believe this particular issue of optimization based on
undefined behaviour can be resolved by just telling people hey
look, the C standard says it is undefined, therefore we can optimize.
Exactly. For example take a look at the strict-aliasing issue. First
optimizations were introduced such that if you did not conform to strict
aliasing rules your code would silently break. In later gcc versions,
warnings have been introduced in order to tell the user hey, this code
might break strict aliasing, are you sure you know what you are doing?.
The current state of the strict-aliasing warnings is still imperfect,
but much better and improving.
On the other hand, the state of signed overflow is quite grim. Even
though the signed overflow issue has been here for over a decade, there
is almost no warning on high risk code. Unfortunately, it is much more
difficult to have good warning on potential overflow bugs than for
strict-aliasing (with negligible false positive, and reasonable false
negative). This is true, at least for predictable warnings (that don't
depend on irrelevant architecture/code-gen/optimization flags).
And if you're not happy, just tell the compiler not to optimize.
For not all undefined behaviour are equal, and undefined behaviour is
also a latitude given to implementors to better serve their base
users.
Undefined behavior is bad. I think that any language spec should keep
the amount of undefined behavior at a bare minimum. The whole issue of
C's (or C++'s) undefined behavior is very unintuitive for most code writers:
* Students that learn C/C++ have too much at their hands as it is.
They won't be able to internalize these issues on top of other new
concepts they have to learn: recursion, free store, algorithms, etc.
* Many lecturers (I have a gut feeling that most) that teach C/C++
don't understand these issues well enough to teach them in a basic
C/C++ course.
* Books barely cover (if at all) these issues. Certainly, these
issues are not stressed every time the terms signed or type
casting are mentioned.
* At verification conferences (and in other cases) I had the
opportunity to talk to people that work on formal verification of
C/C++ from the industry and academia. Surprisingly they
Re: GCC optimizes integer overflow: bug or feature?
Some time ago (a year?) I was told on this mailing-list that code breakage due to undefinedness of signed overflow is not too common (I at least claimed with no evidence that it was more than one bug per 1,000 lines). My claim was counterclaimed by something like most of the time people work with small enough values, so overflows don't happen too many times in practice. This claim is a non sequitur. What I would say is, people *don't understand why a compiler needs to assume undefined overflow semantics*, because people work with small values and don't care about the boundary conditions. For example, most programmers that know assembly language will appreciate if the compiler can use the processor's support for loop with a known number of iterations (mtctr on PPC, for example). However, I'm pretty sure that, if you present these two pieces of code to some good programmers, unsigned int i; for (i = 0; i = n; i++) ... unsigned int i; for (i = 0; i n; i++) ... where the compiler uses mtctr only in the second case, most of them will think that the compiler has bug. Almost nobody will realize that the first can loop infinitely, and the second cannot (which is the reason why the compiler cannot optimize them in the same way). Well, these programmers *are* assuming undefined overflow semantics even on unsigned types. Maybe they would like overflow semantics should be defined in some cases and undefined in others? Fine by me, that would be -fwrapv -funsafe-loop-optimizations in GCC; but a language standard cannot go to such detail! On the autoconf mailing list, Paul Eggert mentioned as a good compromise that GCC could treat signed overflow as undefined only for loops and not in general. Except that the original gnulib bug report was in a loop, so this compromise would leave that case undefined. You may think that the analogy is far fetched? In that case, I'll pick some gcc source file, at random and look for signed operations in it: categorize_ctor_elements_1(..) in gcc/expr.c: _elts += mult * nz; elt_count += mult * ic; Both assume that neither the multiplication, nor the addition overflow. I see this as a *counterexample*: it shows that programmers don't care about having wrapping overflow, in fact they don't care about overflow at all. This code is incorrect not only if overflow is undefined, but also if overflow wraps (-fwrapv); it is correct if overflow aborts (-ftrapv). Paolo
Re: GCC optimizes integer overflow: bug or feature?
foo-bar = make_a_bar(); foo-bar-none = value; being rendered as: call make_a_bar foo-bar-none = value foo-bar = result of make_a_bar() You are not describing a C compiler. Um, I'm describing what gcc did? I think he meant x = make_a_bar (); x-none = value; foo-bar = x; I don't know if this is a valid optimization, but I wouldn't be surprised if it is. Palo
Re: GCC optimizes integer overflow: bug or feature?
Paolo Bonzini wrote: foo-bar = make_a_bar(); foo-bar-none = value; being rendered as: call make_a_bar foo-bar-none = value foo-bar = result of make_a_bar() You are not describing a C compiler. Um, I'm describing what gcc did? I think he meant x = make_a_bar (); x-none = value; foo-bar = x; I don't know if this is a valid optimization, but I wouldn't be surprised if it is. Maybe he forgot the delicate details? The issue may happen if this example was incomplete (my completion may need some tweaking to make it more realistic): #define make_a_bar(ppInstance) *(unsigned**)(ppInstance)=make_a_uint(sizeof(struct bar)) make_a_bar(foo-bar); foo-bar-none = value; In this case strict-aliasing starts its act. The store to foo-bar is done through a different type (pointer to unsigned), which tells gcc that foo-bar-none accesses one object (type bar), while the construction of foo-bar accesses a different object type (unsigned int). In this case this code is undefined and the compiler can reorder these two lines. I am not sure if the following would break as well: #define make_a_bar() (struct bar*)make_a_uint(sizeof(struct bar)) foo-bar=make_a_bar(); foo-bar-none = value; Since gcc should know that foo-bar of type struct bar has been updated before value gets written to none which is a field on object of type struct bar. Michael
Re: GCC optimizes integer overflow: bug or feature?
Maybe he forgot the delicate details? The issue may happen if this example was incomplete (my completion may need some tweaking to make it more realistic): #define make_a_bar(ppInstance) *(unsigned**)(ppInstance)=make_a_uint(sizeof(struct bar)) make_a_bar(foo-bar); foo-bar-none = value; Then, the author of make_a_bar() is getting what he deserved. I am not sure if the following would break as well: #define make_a_bar() (struct bar*)make_a_uint(sizeof(struct bar)) foo-bar=make_a_bar(); foo-bar-none = value; Since gcc should know that foo-bar of type struct bar has been updated before value gets written to none which is a field on object of type struct bar. Of course it wouldn't break. But the reason I say that this is what you deserved, is that the cast is completely unnecessary. You should write this: #define make_a_bar (ppInstance) \ ((ppInstance)=(void *)make_a_uint(sizeof(struct bar))) that is, you put the cast on the other side and don't play with the types of the lvalues. This is what happens all the time with malloc. Paolo
Re: GCC optimizes integer overflow: bug or feature?
Paolo Bonzini wrote: Some time ago (a year?) I was told on this mailing-list that code breakage due to undefinedness of signed overflow is not too common (I at least claimed with no evidence that it was more than one bug per 1,000 lines). My claim was counterclaimed by something like most of the time people work with small enough values, so overflows don't happen too many times in practice. This claim is a non sequitur. What I would say is, people *don't understand why a compiler needs to assume undefined overflow semantics*, because people work with small values and don't care about the boundary conditions. But that is generally true for stuff like gets/sprintf/strcpy/unsafe operation de-jour . People don't care for overflow cases of sprintf because they work with small data. Yet when, suddenly, the size of the data grows and funny stuff start to happen *due* to their sprintf et. al. For example, most programmers that know assembly language will appreciate if the compiler can use the processor's support for loop with a known number of iterations (mtctr on PPC, for example). However, I'm pretty sure that, if you present these two pieces of code to some good programmers, unsigned int i; for (i = 0; i = n; i++) ... unsigned int i; for (i = 0; i n; i++) ... where the compiler uses mtctr only in the second case, most of them will think that the compiler has bug. Almost nobody will realize that the first can loop infinitely, and the second cannot (which is the reason why the compiler cannot optimize them in the same way). Unfortunately, some compilers (not gcc) would optimize both cases the same way. Well, these programmers *are* assuming undefined overflow semantics even on unsigned types. Maybe they would like overflow semantics should be defined in some cases and undefined in others? Fine by me, that would be -fwrapv -funsafe-loop-optimizations in GCC; but a language standard cannot go to such detail! It could add the type modifier nowrap, such that loop indexes can be marked this way explicitly, signed or unsigned. On the autoconf mailing list, Paul Eggert mentioned as a good compromise that GCC could treat signed overflow as undefined only for loops and not in general. Except that the original gnulib bug report was in a loop, so this compromise would leave that case undefined. I'd vote for Paul's suggestion. It would have the least-surprise effect. You may think that the analogy is far fetched? In that case, I'll pick some gcc source file, at random and look for signed operations in it: categorize_ctor_elements_1(..) in gcc/expr.c: _elts += mult * nz; elt_count += mult * ic; Both assume that neither the multiplication, nor the addition overflow. I see this as a *counterexample*: it shows that programmers don't care about having wrapping overflow, in fact they don't care about overflow at all. This code is incorrect not only if overflow is undefined, but also if overflow wraps (-fwrapv); it is correct if overflow aborts (-ftrapv). No, it is an example for a bug which is difficult to protect against with an assertion. Even more seriously, instead of a simple mere bug with bad behavior we get escalated to undefined behavior. Undefined is the worst kind since in theory it is allowed to clean-up your disk, and explode your computer and start WW-III. Can this happen in this case? it depends what the caller does and if gcc can see the caller and the callee at the same time (e.g. if gcc knows that a caller causes mult=MAX_INT/2, it might assume that nz =2 for that caller, and perform some nasty transformations down the line). I am not saying that GCC should abandon all optimizations that assume that no execution path gets to undefined cases. I am saying that these things should not be taken lightly. Saying programmers don't care about having [something leading to undefined behavior] is simply ignoring the graveness of the bad effects. By taking seriously I include the VRP that due to its lacking data structure (at least it used to be so) would be much less effective if gcc would to assume wrapping int. Instead of having to choose between the bad alternatives of VRP that gives weird results for undefined cases or does barely anything, its data structure should be improved, and each variable should have a set of ranges instead of a single range (like what I have seen in some Constraints/CP papers). The second point in this example is: Checking for buffer overflows (undefined code) before they occur is trivial in most cases. Checking for a wrapping signed int before it actually wraps is relatively complex and unintuitive (e.g. it is unintuitive why should a/b ever overflow, hint: MIN_INT/-1 -- MIN_INT). I would prefer plain bugs, in which -g and -O3 act just the same, over undefined behavior when I have no choice but to debug a -O3 code !!! I can't forget the day (several years ago)
Re: GCC optimizes integer overflow: bug or feature?
Paolo Bonzini [EMAIL PROTECTED] writes: On the autoconf mailing list, Paul Eggert mentioned as a good compromise that GCC could treat signed overflow as undefined only for loops and not in general. What I meant to propose (and perhaps did not propose clearly enough) is that if the C application is checking for integer overflow, GCC should not optimize that code away; but it is OK for GCC to do other loop optimizations. That is, some overflow checking is done in loops, and GCC should not optimize that away, but the other loop optimizations are OK. 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; 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? Another question for the GCC experts: would it fix the bug if we replaced j *= 2 with j = 1 in this sample code? 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. Obviously this latter can be worked around too, but what a mess, huh?
Re: GCC optimizes integer overflow: bug or feature?
On Thu, 21 Dec 2006, Paul Eggert wrote: 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. Conversion of out-of-range integers to signed types is implementation-defined not undefined, and GCC duly documents the modulo semantics for that conversion. I don't know if you have to deal with compilers applying different semantics there, but shared overflow checking functions in gnulib could deal with the differences between compilers. (Conversion of out-of-range floating-point numbers to integer types *is* undefined, but Annex F changes this to returning an unspecified value so bounding the possible behavior, and I believe GCC follows Annex F for this: it's useful not to have to guarantee any particular result, since different machines have conversion instructions that may do different things for out-of-range values, and to be able to return different results for compile-time and run-time conversions, but floating-point conversions don't have the same scope as integer arithmetic for useful optimization based on undefined behavior.) -- Joseph S. Myers [EMAIL PROTECTED]
Re: GCC optimizes integer overflow: bug or feature?
Marcin Dalecki wrote: But the same applies to floating point numbers. There, the situation is even better, because nowadays I can rely on a float or double being the representation defined in IEEE 754 because there is such overwhelming hardware support. You better don't. Really! Please just realize for example the impact of the (in)famous 80 bit internal (over)precision of a very common IEEE 754 implementation... Well, I know. Which is why I used the term storage representation down the rest of the paragraph that you decided not to quote. :) However it's a quite common mistake to forget how bad floats model real numbers. And it's quite a common mistake to forget how bad finite ints model integer numbers. No it isn't. Most people don't think in terms of infinite arithmetics when programming. And I hold up that the difference between finite and infinite is actually quite a fundamental concept. Let us agree to disagree. However quite a lot of people expect the floating arithmetics rouding to give them well behaved results. I don't know what you mean by well behaved in this context, but I am beginning to suspect something: what you were trying to express with that algebra argument was a mere gut feeling of yours that there is a fundamental need to distinguish between discreet and continous domains. Let me just say that algebra has not much to do with that distinction and is off-topic. Anyway, you are entitled to feel that way or the other, but I cannot agree. Leaving such gut feelings aside, I maintain: GCC has been careful not to violate a standard (IEEE 754) that was not binding, but assumed by many of its users, unless told otherwise (using -ffast-math). Now it is violating another standard (LIA-1) that is not binding, but assumed by many of its users, unless explicitly told to follow that standard (with -fwrapv). That is A Bad Idea. Cheers -richy. -- Richard B. Kreckel http://www.ginac.de/~kreckel/
Re: GCC optimizes integer overflow: bug or feature?
On 12/20/06, Marcin Dalecki [EMAIL PROTECTED] wrote:
You better don't. Really! Please just realize for example the impact
of the (in)famous 80 bit internal (over)precision of a
very common IEEE 754 implementation...
volatile float b = 1.;
if (1. / 3. == b / 3.) {
printf(HALLO!\n)
} else {
printf(SURPRISE SURPRISE!\n);
}
It has always seemed to me that floating point comparison could
be standardized to regularize the exponent and ignore the least significant
few bits and doing so would save a lot of headaches. Would it really save
the headaches or would it just make the cases where absolute comparisons
of fp results break less often, making the error more intermittent and
thereby worse? Could a compiler switch be added that would alter
fp equality?
I have argued for precision to be included in numeric types in other forae
and have been stunned that all except people with a background in Chemistry
find the suggestion bizarre and unnecessary; I realize that GCC is not really
a good place to try to shift norms; but on the other hand if a patch was to
be prepared that would add a command-line switch (perhaps -sloppy-fpe and
-no-sloppy-fpe) that would govern wrapping ((fptype) == (fptype)) with something
that threw away the least sig. GCC_SLOPPY_FPE_SLOP_SIZE bits in
the mantissa, would it get accepted or considered silly?
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-21, at 22:19, David Nicol wrote: It has always seemed to me that floating point comparison could be standardized to regularize the exponent and ignore the least significant few bits and doing so would save a lot of headaches. Well actually it wouldn't save the world. However adding an op-code implementing: x eqeps y = |x - y| epsilion, would be indeed helpful. Maybe some m-f has already patented it, and that's the reason we don't see it already done. But that's of course only me speculating. Would it really save the headaches or would it just make the cases where absolute comparisons of fp results break less often, making the error more intermittent and thereby worse? Could a compiler switch be added that would alter fp equality? However in numerical computation there isn't really a silver bullet to be found. If you are serious about it you simply do the hard work - which is the numerical analysis of your algorithms with respect to computational stability. That's the real effort and perhaps the reason, why the peculiarities of the FP implementations are not perceived as problematic. I have argued for precision to be included in numeric types in other forae and have been stunned that all except people with a background in Chemistry find the suggestion bizarre and unnecessary; I realize that GCC is not really a good place to try to shift norms; but on the other hand if a patch was to be prepared that would add a command-line switch (perhaps -sloppy- fpe and -no-sloppy-fpe) that would govern wrapping ((fptype) == (fptype)) with something that threw away the least sig. GCC_SLOPPY_FPE_SLOP_SIZE bits in the mantissa, would it get accepted or considered silly? No that's not sufficient. And a few bit's of precision are really not the center-point of numerical stability of the overall calculation. Please look up as an example a numerical phenomenon which is usually called cancelation to see immediately why. Marcin Dalecki
Re: GCC optimizes integer overflow: bug or feature?
Joseph S. Myers [EMAIL PROTECTED] writes: Conversion of out-of-range integers to signed types is implementation-defined not undefined, Thanks for the correction; I keep forgetting that. However, a conforming implementation is allowed to raise a signal for those conversions, which could break the code in question, i.e., it could cause the test to report the wrong result. So the distinction between undefined and implementation-defined behavior doesn't much matter here. (Presumably the code could work around the problem by trapping the signal, but that is another can of porting worms.) I daresay many conversions of out-of-range values to signed integers are in a similar boat.
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-21, at 22:19, David Nicol wrote: It has always seemed to me that floating point comparison could be standardized to regularize the exponent and ignore the least significant few bits and doing so would save a lot of headaches. This would be a real nuisance. This myth that you should never compare fpt numbers for absolute equality is nonsense. There are lots of algorithms where it is legitimate to compare for absolute equality (various kinds of iterations that converge reliably to a single bit pattern for example). It *is* a problem to have the 80-bit stuff intefering (in fact Kahan pronounced this a bug in a Fortran compiler. Ada gets around this by providing the 'Machine attribute that forces a fpt number to a canonical machine representation in its type, but it's a bit cumbersome. Note that the use of SSE on the x86 eliminates this problem. Marcin Dalecki: Well actually it wouldn't save the world. However adding an op-code implementing: x eqeps y = |x - y| epsilion, would be indeed helpful. Maybe some m-f has already patented it, and that's the reason we don't see it already done. But that's of course only me speculating. There would be nothing wrong in having such an operation, but it is not equality! David Nicol wrote: I have argued for precision to be included in numeric types in other forae and have been stunned that all except people with a background in Chemistry find the suggestion bizarre and unnecessary; if you are stunned by this, you need to study more about computer arithmetic (btw I have a PhD in chemistry :-)) I realize that GCC is not really a good place to try to shift norms; especially if the attempt is misguided. Floating-point semantics in languages have been studied by a lot of experts, they are not accidental! Marcin Dalecki: No that's not sufficient. And a few bit's of precision are really not the center-point of numerical stability of the overall calculation. Please look up as an example a numerical phenomenon which is usually called cancelation to see immediately why. indeed!
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-21, at 23:17, Robert Dewar wrote: Marcin Dalecki: Well actually it wouldn't save the world. However adding an op-code implementing: x eqeps y = |x - y| epsilion, would be indeed helpful. Maybe some m-f has already patented it, and that's the reason we don't see it already done. But that's of course only me speculating. There would be nothing wrong in having such an operation, but it is not equality! Of course I didn't think about a substitute for ==. Not! However I think that checks for |x-y| epsilion, could be really given a significant speed edge if done in a single go in hardware.
Re: GCC optimizes integer overflow: bug or feature?
Marcin Dalecki wrote: On 2006-12-21, at 23:17, Robert Dewar wrote: Marcin Dalecki: Well actually it wouldn't save the world. However adding an op-code implementing: x eqeps y = |x - y| epsilion, would be indeed helpful. Maybe some m-f has already patented it, and that's the reason we don't see it already done. But that's of course only me speculating. There would be nothing wrong in having such an operation, but it is not equality! Of course I didn't think about a substitute for ==. Not! However I think that checks for |x-y| epsilion, could be really given a significant speed edge if done in a single go in hardware. I don't see this as viable, the choice of epsilon is too application dependent.
Re: GCC optimizes integer overflow: bug or feature?
Marcin Dalecki wrote: Of course I didn't think about a substitute for ==. Not! However I think that checks for |x-y| epsilion, could be really given a significant speed edge if done in a single go in hardware. One thing to ponder here is that thinks like this are what lead to CISC instruction messes. It just seems obvious to people that it will help efficiency to have highly specialized instructions, but in practice they gum up the architecture with junk, and a careful analysis shows that the actual gain is small at best. How many applications spend a significant amount of time doing such an epsilon test -- best guess: none.
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-21, at 23:42, Robert Dewar wrote: Marcin Dalecki wrote: Of course I didn't think about a substitute for ==. Not! However I think that checks for |x-y| epsilion, could be really given a significant speed edge if done in a single go in hardware. One thing to ponder here is that thinks like this are what lead to CISC instruction messes. It just seems obvious to people that it will help efficiency to have highly specialized instructions, but in practice they gum up the architecture with junk, and a careful analysis shows that the actual gain is small at best. How many applications spend a significant amount of time doing such an epsilon test -- best guess: none. Well actually you are interpreting too much wight in to my speculations. I was just curious whatever similar analysis has been already seriously done? And after all, well the most commonly used instruction set architectures for numerical calculations, are not exactly what one would call lean and mean... People simply use what's already there and what is cheap. Or could you imagine something uglier then the stacked/MMX/XMM/SSE4 mess? After all even the supposedly competent instructions set designers admitted their previous fallacy by the introduction of SSE2. Marcin Dalecki
Re: GCC optimizes integer overflow: bug or feature?
Paul Eggert [EMAIL PROTECTED] 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
Re: GCC optimizes integer overflow: bug or feature?
On Thu, 21 Dec 2006, Ian Lance Taylor wrote: 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). As noted, it's only undefined in C99 not C90 and we document that this undefinedness isn't used at present; and non-front-end code can't use flag_isoc99 since it isn't available in non-C-family front ends. -- Joseph S. Myers [EMAIL PROTECTED]
Re: GCC optimizes integer overflow: bug or feature?
Ian Lance Taylor [EMAIL PROTECTED] writes: 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. It is a knotty problem. Thanks for thinking about it. I'm Handwaving with a capital H here, but one possibility is for plain -O2 to keep VRP, but disable its assumption about signed overflow when attempting to optimize away a comparison that comes directly from the user's code (as opposed to a comparison coming from subscript checking and the like). Here's another wild idea. Perhaps GCC could add an option -fundefinedv to request for aggressive optimizations assuming that the program will never have an signed integer overflow. I.e., if you want the optimization that is causing trouble here, you would specify -O2 -fundefinedv; but the default would be to disable this particular troublesome optimization.
Re: GCC optimizes integer overflow: bug or feature?
On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
There are a lot of 100.00% safe optimizations which gcc
can do. Value range propagation for bitwise operations, for one
Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):
# cat tt.c
int f(char *p)
{
if (p[0] == 1 p[1] == 2) return 1;
return 0;
}
# gcc -O2 -S -fomit-frame-pointer tt.c
# cat tt.s
.file tt.c
.text
.p2align 2,,3
.globl f
.type f, @function
f:
movl4(%esp), %eax
cmpb$1, (%eax)
je .L2
xorl%eax, %eax
ret
.p2align 2,,3
.L2:
cmpb$2, 1(%eax)
sete%al
movzbl %al, %eax
ret
.size f, .-f
.ident GCC: (GNU) 4.2.0 20061128 (prerelease)
.section.note.GNU-stack,,@progbits
Re: GCC optimizes integer overflow: bug or feature?
On Friday 22 December 2006 00:58, Denis Vlasenko wrote:
On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
There are a lot of 100.00% safe optimizations which gcc
can do. Value range propagation for bitwise operations, for one
Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):
int f(char *p)
{
if (p[0] == 1 p[1] == 2) return 1;
return 0;
}
Definitely not 100% safe. p may point to memory that is sensitive to the
access width and/or number of accesses. (ie. memory mapped IO).
Paul
Re: GCC optimizes integer overflow: bug or feature?
Paul Brook wrote:
On Friday 22 December 2006 00:58, Denis Vlasenko wrote:
On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
There are a lot of 100.00% safe optimizations which gcc
can do. Value range propagation for bitwise operations, for one
Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):
int f(char *p)
{
if (p[0] == 1 p[1] == 2) return 1;
return 0;
}
Definitely not 100% safe. p may point to memory that is sensitive to the
access width and/or number of accesses. (ie. memory mapped IO).
A program that depends on this is plain wrong. There is no guarantee
that memory references are as they appear in the program. For a
non-volatile variable, any such optimization is valid. For instance
if the flow can be used to prove that p[0] is already 1, then there
is no need to repeat the read.
Paul
Re: GCC optimizes integer overflow: bug or feature?
Paul Eggert [EMAIL PROTECTED] writes: | Ian Lance Taylor [EMAIL PROTECTED] writes: | | 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. | | It is a knotty problem. Thanks for thinking about it. | | I'm Handwaving with a capital H here, but one possibility is | for plain -O2 to keep VRP, but disable its assumption about | signed overflow when attempting to optimize away a | comparison that comes directly from the user's code (as | opposed to a comparison coming from subscript checking and | the like). If that is workable, it would be a good compromise. -- Gaby
Re: GCC optimizes integer overflow: bug or feature?
On Friday 22 December 2006 02:06, Robert Dewar wrote:
Paul Brook wrote:
On Friday 22 December 2006 00:58, Denis Vlasenko wrote:
On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
There are a lot of 100.00% safe optimizations which gcc
can do. Value range propagation for bitwise operations, for one
Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):
int f(char *p)
{
if (p[0] == 1 p[1] == 2) return 1;
return 0;
}
Definitely not 100% safe. p may point to memory that is sensitive to the
access width and/or number of accesses. (ie. memory mapped IO).
A program that depends on this is plain wrong. There is no guarantee
that memory references are as they appear in the program. For a
non-volatile variable, any such optimization is valid. For instance
if the flow can be used to prove that p[0] is already 1, then there
is no need to repeat the read.
Who says the optimisation is valid? The language standard?
The example was given as something that's 100% safe to optimize. I'm
disagreeing with that assertion. The use I describe isn't that unlikely if
the code was written by someone with poor knowledge of C.
My point is that it's not that hard to invent plausible code that breaks
when pretty much any transformation is applied. We have to decide how close
to the standard we want to fly.
Optimization should never change the behavior of any program accepted by the
compiler is not a useful constraint for an optimizing compiler. If program
behavior includes the ability to debug the program, then I'd go as far as
saying this should be the definition of -O0.
Optimization should never change the behavior of a valid program is useful
definition because it forces you to define what constitutes a valid program.
There's actually a much better reason why the transformation is not safe.
Consider a data structure where a byte of 1 indicates the end of the object.
Under normal circumstances short-circuiting of the operator prevents
anything bad happening. If you merge the two accesses you've just read past
the end of the object and all kinds of bad things may happen (eg. a
segfault).
Paul
P.S. I think I'm repeating myself now, so this is the last time I intend to
comment on this thread.
Re: GCC optimizes integer overflow: bug or feature?
Paul Brook wrote: Who says the optimisation is valid? The language standard? The example was given as something that's 100% safe to optimize. I'm disagreeing with that assertion. The use I describe isn't that unlikely if the code was written by someone with poor knowledge of C. My point is that it's not that hard to invent plausible code that breaks when pretty much any transformation is applied. We have to decide how close to the standard we want to fly. I did not find that plausible at all, for someone to depend on memory mapped references without using volatile is indeed such junk code that we don't need to care about it. Optimization should never change the behavior of a valid program is useful definition because it forces you to define what constitutes a valid program. No, no, let's not start calling these programs that violate the standard valid. That's going much too far. Also, sometimes code is inherently non-deterministic, so you have to be careful talking about change of behavior. Optimization should never result in violating the required semantics of a valid (standard) C program is of course criterion 1 Criterion 2 is something like Optimization should not cause non-valid non-standard programs to fail as a result of using a common idiom, which though non-standard is generally expected to work, unless the optimization can be demonstrated to be valuable enough to be worth generating the effective incompatibility with expected practice is a half baked statement of criterion 2 (and it is not so easy to bake this one!) There's actually a much better reason why the transformation is not safe. Consider a data structure where a byte of 1 indicates the end of the object. Under normal circumstances short-circuiting of the operator prevents anything bad happening. If you merge the two accesses you've just read past the end of the object and all kinds of bad things may happen (eg. a segfault). You may well know that it is safe to go one past the last object (generally this will be the case, because of the strange semantics of being allowed to address past the last byte). You do indeed have to be careful of this P.S. I think I'm repeating myself now, so this is the last time I intend to comment on this thread. OK!
Re: GCC optimizes integer overflow: bug or feature?
Paul Eggert wrote: Also, such an approach assumes that unsigned long long int has at least as many bits as long long int. But this is an unportable assumption; C99 does not require this. We have run into hosts where the widest signed integer type has much greater range than the widest unsigned type. I hope these hosts go away in the long run, but they're in production use today. (The platform I'm thinking of is Tandem NSK/OSS.) Is this correct? Doesn't C99's 6.2.5#6 mandate that unsigned long long int has exactly the same number of bits as long long int? Perhaps you mean that in Tandem NSK/OSS unsigned long long ints do not use several bits of the representation? Am I missing something else? All the best, Roberto ISO/IEC 9899:1999 6.2.5 [...] 4 There are five standard signed integer types, designated as signed char, short int, int, long int, and long long int. [...] [...] 6 For each of the signed integer types, there is a corresponding (but different) unsigned integer type (designated with the keyword unsigned) that uses the same amount of storage (including sign information) and has the same alignment requirements. [...] [...] -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:[EMAIL PROTECTED]
Re: GCC optimizes integer overflow: bug or feature?
Roberto Bagnara [EMAIL PROTECTED] writes: (The platform I'm thinking of is Tandem NSK/OSS.) Is this correct? Doesn't C99's 6.2.5#6 mandate that... This is straying from the subject of GCC and into the problems of writing portable C code, but since you asked The Tandem NSK/OSS environment does not claim full conformance to C99. The NSK/OSS community is conservative (fault-tolerance does that do you :-) and has introduced only some C99 features, more as time progresses. The NSK/OSS developers did not introduce 64-bit unsigned int until last year. I'm no expert in the area, but I'd guess that most NSK/OSS production shops are still running older releases, which have 64-bit signed int but only 32-bit unsigned int.
Re: GCC optimizes integer overflow: bug or feature?
Paul Schlie wrote: As a compromise, I'd vote that no optimizations may alter program behavior in any way not explicitly diagnosed in each instance of their application. Sounds reasonable, but it is impossible and impractical! And I think anyone familiar with compiler technology and optimization technology understands why this is the case.
Re: GCC optimizes integer overflow: bug or feature?
Robert Dewar writes: Paul Brook wrote: As opposed to a buggy program with wilful disregard for signed overflow semantics? ;-) I know there is a smiley there, but in fact I think it is useful to distinguish these two cases. This is, I think, a very interesting comment. I've thought about it for a little while, and I don't understand why you think it is useful to distinguish these two cases. Is it simply that one error is likely to be more common than another? Or is there some more fundamental reason? Andrew.
Re: GCC optimizes integer overflow: bug or feature?
Andrew Haley wrote: Is it simply that one error is likely to be more common than another? Or is there some more fundamental reason? I think it is more fundamental. Yes, of course any optimization will change resource utilization (space, time). An optimization may well make a program larger, which means it no longer fits in memory, or it may in some unfortunate case slow down the execution of some program, e.g. due to cache effects from too much inlining, and the program misses deadlines. But these effects are very different from optimizations which change the results in a way permitted by the standard as a direct result of using the optimization. For example if we write a = b * c + d; an optimizer may choose to use a fused multiply-add with subtly different rounding effects or on the x86, keeping intermediate floats in 80 bits, certainly permissible from the standard without LIA, can subtly change results. I do think this is a useful distinction. We can't say don't do any optimization that changes resource utilization, that would be absurd. We can't even say, warn when this optimization might change resource utilization, that would be equally absurd. But when we have an optimization that changes the operational semantics of the particular operation being optimized, we can say: This change in behavior may be unexpected, or undesirable, even if allowed by the standard. Let's be sure the optimization is worth it before enabling it by default.
Re: GCC optimizes integer overflow: bug or feature? (was: avoid integer overflow in mktime.m4)
On 2006-12-20, at 00:10, Richard B. Kreckel wrote: C89 did not refer to IEEE 754 / IEC 60559. Yet, as far as I am aware, -ffast-math or the implied optimizations have never been turned on by GCC unless explicitly requested. That was a wise decision. By the same token it would be wise to refrain from turning on any optimization that breaks programs which depend on wrapping signed integers. Numerical stability of incomplete floating point representations are an entirely different problem category then some simple integer tricks. In the first case the difficulties are inherent to the incomplete representation of the calculation domain. In the second case it's just some peculiarities of the underlying machine as well as the fact that the unsigned qualifier is not used nearly enough frequently in common code. Or in other words: Z/32 resp. 64 IS AN ALGEBRA but float isn't! Thus this argument by analogy simply isn't valid. Marcin Dalecki
Re: GCC optimizes integer overflow: bug or feature?
Hello, Paul Brook wrote: Compiler can optimize it any way it wants, as long as result is the same as unoptimized one. We have an option for that. It's called -O0. Pretty much all optimization will change the behavior of your program. Now that's a bit TOO strong a statement, critical optimizations like register allocation and instruction scheduling will generally not change the behavior of the program (though the basic decision to put something in a register will, and *surely* no one suggests avoiding this critical optimization). Actually they will with multi threaded program, since you can have a case where it works and now it is broken because one thread has speed up so much it writes to a variable which had a copy on another thread's stack. So the argument about it being too strong is wrong because timming matters now a days. Instruction scheduling can cause the same issue as it forces a write too early for another thread to act on. actually, you do not even need (invalid) multithreaded programs to realize that register allocation may change behavior of a program. If the size of the stack is bounded, register allocation may cause or prevent program from running out of stack, thus turning a crashing program to non-crashing one or vice versa. Zdenek
Re: GCC optimizes integer overflow: bug or feature?
Denis Vlasenko writes:
On Tuesday 19 December 2006 20:05, Andrew Haley wrote:
Denis Vlasenko writes:
I wrote this just a few days ago:
do {
int32_t v1 = v 1;
if (v 0) v1 ^= mask;
v = v1;
printf(%10u: %08x\n, c++, v);
} while (v != 1);
I would become rather sad if this will stop compiling correctly.
I can understand the objections to do with dusty deck code that
hasn't been looked at for aeons, but in the case of code that you
wrote so recently, given that you understand the issue, why not simply
use the standard idiom?
I want sane compiler.
One in which N-bit integer variables stay exactly N-bit.
Without magic N+1 bit which is there somethimes. a*2/2:
If I say multiply by 2 and _after that_ divide by 2,
I meant that. Compiler can optimize it any way it wants,
as long as result is the same as unoptimized one.
This kind of thinking was appropriate before standardization.
But C changed. C is no longer a kind of high-level assembly laguage:
it's defined by a standard, in terms of an abstract machine, and some
operations are not well-defined. If you want your programs to do what
you expect, you'd better find out what that abstract machine does.
Above: v is a signed entity. I expect (v 0) to be equal to
most significant bit is set. It's not about standards.
It's about sanity.
You'd better find some other programming langauge that is defined the
way you want.
Andrew.
Re: GCC optimizes integer overflow: bug or feature?
Zdenek Dvorak wrote: actually, you do not even need (invalid) multithreaded programs to realize that register allocation may change behavior of a program. If the size of the stack is bounded, register allocation may cause or prevent program from running out of stack, thus turning a crashing program to non-crashing one or vice versa. Again, I think it is useful to distinguish functional behavior changes from changes that come from resource utilization. Yes, optimization will always change resource utilization. That's the whole point, so if you include resource utilization as a change in behavior, then you lose the useful distinction between optimizations like a*2 = a+a which could change the size of an executable but which of itself is functionally neutral from optimizations which are not functionally neutral for programs with undefined or implementation defined semantics (e.g. fast math). Note that another possible effect of *any* optimization, is to change the address of data and code throughout the program, and of course this could wake up some implementation or buggy behavior that depended on specific addresses of data or code. Again, it is useful to exclude these indirect effects.
Re: GCC optimizes integer overflow: bug or feature?
Dave Korn wrote: On 20 December 2006 02:28, Andrew Pinski wrote: Paul Brook wrote: Pretty much all optimization will change the behavior of your program. Now that's a bit TOO strong a statement, critical optimizations like register allocation and instruction scheduling will generally not change the behavior of the program (though the basic decision to put something in a register will, and *surely* no one suggests avoiding this critical optimization). Actually they will with multi threaded program, since you can have a case where it works and now it is broken because one thread has speed up so much it writes to a variable which had a copy on another thread's stack. So the argument about it being too strong is wrong because timing matters now a days. Instruction scheduling can cause the same issue as it forces a write too early for another thread to act on. Why isn't that just a buggy program with wilful disregard for the use of correct synchronisation techniques? Excuse me while I beat you on the head with a number of real-life examples of *lock-free* algorithms. :-) Particularly lock-free queues (google should help you find one that applies here), whose correct operation is critically dependent on the order in which the loads and stores are performed. This is a very real, entirely legitimate example where the compiler thinking it knows how to do my job better than I do is wrong. We (in a major, commercial application) ran into exactly this issue. 'asm volatile(lock orl $0,(%%esp)::)' is your friend when this happens (it is a barrier across which neither the compiler nor CPU will reorder things). Failing that, no-op cross-library calls (that can't be inlined) seem to do the trick. -- Matthew Hi! I'm a .signature virus! Copy me into your ~/.signature, please!
RE: GCC optimizes integer overflow: bug or feature?
On 20 December 2006 16:25, Matthew Woehlke wrote: Dave Korn wrote: On 20 December 2006 02:28, Andrew Pinski wrote: Paul Brook wrote: Pretty much all optimization will change the behavior of your program. Now that's a bit TOO strong a statement, critical optimizations like register allocation and instruction scheduling will generally not change the behavior of the program (though the basic decision to put something in a register will, and *surely* no one suggests avoiding this critical optimization). Actually they will with multi threaded program, since you can have a case where it works and now it is broken because one thread has speed up so much it writes to a variable which had a copy on another thread's stack. So the argument about it being too strong is wrong because timing matters now a days. Instruction scheduling can cause the same issue as it forces a write too early for another thread to act on. Why isn't that just a buggy program with wilful disregard for the use of correct synchronisation techniques? Excuse me while I beat you on the head with a number of real-life examples of *lock-free* algorithms. :-) Thanks, I've heard of them, in fact I've implemented many, debugged many, and currently work with several every single day of the week. Particularly lock-free queues (google should help you find one that applies here), whose correct operation is critically dependent on the order in which the loads and stores are performed. No, absolutely not. Lock-free queues work by (for example) having a single producer and a single consumer, storing the queue in a circular buffer, and assigning ownership of the queue's head pointer to the producer and the (chasing) tail pointer to the consumer. The whole point about lock-free algorithms is that they are guaranteed to work *regardless* of the order of operations between the two asynchronous processes that interact with the queue, given only the ability to perform an atomic read or write. The ordering is critical within a single thread of execution; e.g. you must fill in all the details of the new entry you are adding to the queue /before/ you increment the head pointer, whereas in a locking algorithm it wouldn't matter if you incremented the head pointer first, then filled in the blank entry you had just moved it past, because you'd do both within the lock. If you design a lock-free algorithm that relies on two threads being precisely synchronised, it's not really lock-free, it just has 'implicit' locking; and if your precise synchronisation depends on the precise cycle-timing of low-level instruction sequences, you have made a very very fragile design that works, if it does, by good fortune. This is a very real, entirely legitimate example where the compiler thinking it knows how to do my job better than I do is wrong. Nope, this is a very real example of a bug in your algorithmic design, or of you misleading the compiler, or relying on undefined or implementation-defined behaviour. We (in a major, commercial application) ran into exactly this issue. 'asm volatile(lock orl $0,(%%esp)::)' is your friend when this happens (it is a barrier across which neither the compiler nor CPU will reorder things). Failing that, no-op cross-library calls (that can't be inlined) seem to do the trick. This simply means you have failed to correctly declare a variable volatile that in fact /is/ likely to be spontaneously changed by a separate thread of execution. And relying on a library call to act as a memory barrier is risky. The only way in which it works is because it takes long enough that there's enough time for the CPU's load-store unit to have completed any posted writes, but if (for a contrived example) you're using a cut-down embedded library and the particular routine that you call happens to be a stub and just returns immmediately, you've got a two-instruction call-return sequence that very seriously is not a guarantee of externally-visible memory access ordering. Now, the compiler *does* know not to optimise moves across library calls, but you're investing too much trust in them if you think the CPU's internal units know or care whether you're in a libcall or your mainline code. cheers, DaveK -- Can't think of a witty .sigline today
Re: GCC optimizes integer overflow: bug or feature?
On 12/20/06, Dave Korn [EMAIL PROTECTED] wrote: ... We (in a major, commercial application) ran into exactly this issue. 'asm volatile(lock orl $0,(%%esp)::)' is your friend when this happens (it is a barrier across which neither the compiler nor CPU will reorder things). Failing that, no-op cross-library calls (that can't be inlined) seem to do the trick. This simply means you have failed to correctly declare a variable volatile that in fact /is/ likely to be spontaneously changed by a separate thread of execution. The C or C++ standard doesn't define ANYTHING related to threads, and thus anything related to threads is beyond the standard. If you think volatile means something in an MT environment, think again. You can deduce certain aspect (e.g. guaranteed appearance of store or load), but nothing beyond that. Add memory model to the mix, and you're way beyond what the language says, and you need to rely on the non-standard non-portable facilities, if provided at all. Even in a single threaded environment, what exactly volatile means is not quite clear in the standard (except for setjmp/longjmp related aspect). I liked the following paper (for general users, not for the compiler developers, mind you): http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf -- #pragma ident Seongbae Park, compiler, http://seongbae.blogspot.com;
Re: GCC optimizes integer overflow: bug or feature?
Dave Korn wrote: Particularly lock-free queues whose correct operation is critically dependent on the order in which the loads and stores are performed. No, absolutely not. Lock-free queues work by (for example) having a single producer and a single consumer, storing the queue in a circular buffer, and assigning ownership of the queue's head pointer to the producer and the (chasing) tail pointer to the consumer. [snip] The ordering is critical within a single thread of execution; e.g. you must fill in all the details of the new entry you are adding to the queue /before/ you increment the head pointer, Exactly. Guess what the compiler did to us? :-) Oh, no, I'm /sure/ it's OK if I re-order your code so that those assignments happen /after/ I handle this dinky little increment for you. Now our code may have been wrong in this instance (see below), but... Let's be clear. Order matters. /You/ said so yourself. :-) And even if the programmer correctly tells the compiler what to do, what (unless the compiler inserts memory barriers) keeps the CPU from circumventing both? That said, I've seen even stranger things, too. For example: foo-bar = make_a_bar(); foo-bar-none = value; being rendered as: call make_a_bar foo-bar-none = value foo-bar = result of make_a_bar() So what was wrong with my C code in that instance? :-) This is a very real, entirely legitimate example where the compiler thinking it knows how to do my job better than I do is wrong. Nope, this is a very real example of a bug in your algorithmic design, or of you misleading the compiler, or relying on undefined or implementation-defined behaviour. [snip] This simply means you have failed to correctly declare a variable volatile that in fact /is/ likely to be spontaneously changed by a separate thread of execution. /That/ is very possible. I'm talking about /OLD/ code here, i.e. code that was written back in KR days, back before there /was/ a volatile keyword. (Although I had understood that 'volatile' was a no-op in most modern compilers? Does it have the semantics that loads/stores of volatile variables are not re-ordered with respect to each other?) At any rate, I don't recall now if making the variable in question 'volatile' helped or not. Maybe this is an exercise in why changing long-standing semantics has an insidious and hard to correct effect. (Does that conversation sound familiar?) And relying on a library call to act as a memory barrier is risky. [snip] Now, the compiler *does* know not to optimise moves across library calls, but you're investing too much trust in them if you think the CPU's internal units know or care whether you're in a libcall or your mainline code. You're preaching to the choir. Unfortunately adding proper assembly modules to our build system didn't go over so well, and I am /not/ going to try to write inline assembler that works on six-or-more different compilers. :-) So I know this is just a 'cross your fingers and hope it works' approach on non-x86 platforms. On x86 I use the correct, previously-quoted inline assembly, which as mentioned acts as a barrier for both the compiler /and/ the CPU. As you say, all it's really ensuring in other cases is that the compiler remains honest, but that was the intent, and I know it isn't perfect. -- Matthew Hi! I'm a .signature virus! Copy me into your ~/.signature, please!
Re: GCC optimizes integer overflow: bug or feature?
Marcin Dalecki wrote: Numerical stability of incomplete floating point representations are an entirely different problem category then some simple integer tricks. In the first case the difficulties are inherent to the incomplete representation of the calculation domain. In the second case it's just some peculiarities of the underlying machine as well as the fact that the unsigned qualifier is not used nearly enough frequently in common code. Or in other words: Z/32 resp. 64 IS AN ALGEBRA but float isn't! Thus this argument by analogy simply isn't valid. Sheesh! This argument is totally confused... 1) Z/Zn and, by isomorphism, unsigned types may be an algebra. But this entire discussion is about signed types, not unsigned types. 2) Signed types are not an algebra, they are not even a ring, at least when their elements are interpreted in the canonical way as integer numbers. (Heck, what are they?) 3) Making behavior partially undefined certainly does not help making it an algebra or any other well-defined mathematical structure. Integral types are an incomplete representation of the calculation domain, which is the natural numbers. This corroborates the validity of the analogy with IEEE real arithmetic. -richy. -- Richard B. Kreckel http://www.ginac.de/~kreckel/
Re: GCC optimizes integer overflow: bug or feature?
Matthew Woehlke [EMAIL PROTECTED] writes: That said, I've seen even stranger things, too. For example: foo-bar = make_a_bar(); foo-bar-none = value; being rendered as: call make_a_bar foo-bar-none = value foo-bar = result of make_a_bar() You are not describing a C compiler. Andreas. -- Andreas Schwab, SuSE Labs, [EMAIL PROTECTED] SuSE Linux Products GmbH, Maxfeldstraße 5, 90409 Nürnberg, Germany PGP key fingerprint = 58CA 54C7 6D53 942B 1756 01D3 44D5 214B 8276 4ED5 And now for something completely different.
Re: GCC optimizes integer overflow: bug or feature?
On 2006-12-20, at 22:48, Richard B. Kreckel wrote: 2) Signed types are not an algebra, they are not even a ring, at least when their elements are interpreted in the canonical way as integer numbers. (Heck, what are they?) You are apparently using a different definition of an algebra or ring than the common one. Integral types are an incomplete representation of the calculation domain, which is the natural numbers. This is an arbitrary assumption. In fact most people simply are well aware of the fact that computer don't to infinite arithmetics. You are apparently confusing natural numbers, which don't include negatives, with integers. However it's a quite common mistake to forget how bad floats model real numbers. This corroborates the validity of the analogy with IEEE real arithmetic. And wrong assumptions lead to wrong conclusions. Marcin Dalecki
Re: GCC optimizes integer overflow: bug or feature?
On 12/20/06, Marcin Dalecki [EMAIL PROTECTED] wrote: You are apparently using a different definition of an algebra or ring than the common one. Fascinating discussion. Pointers to canonical on-line definitions of the terms algebra and ring as used in compiler design please?
Re: GCC optimizes integer overflow: bug or feature?
Marcin Dalecki wrote: On 2006-12-20, at 22:48, Richard B. Kreckel wrote: 2) Signed types are not an algebra, they are not even a ring, at least when their elements are interpreted in the canonical way as integer numbers. (Heck, what are they?) You are apparently using a different definition of an algebra or ring than the common one. What I was talking about was this: http://en.wikipedia.org/wiki/Algebra_over_a_field. In the absence of a modulus (i.e. wrapping) all the operations (the vector space's addition and the algebra's multiplication) run into problems as long as one maintains the canonical homomorphism (i.e. identification with integer numbers 0, 1, 5...) Integral types are an incomplete representation of the calculation domain, which is the natural numbers. This is an arbitrary assumption. In fact most people simply are well aware of the fact that computer don't to infinite arithmetics. But the same applies to floating point numbers. There, the situation is even better, because nowadays I can rely on a float or double being the representation defined in IEEE 754 because there is such overwhelming hardware support. The variety of int sizes encountered nowadays is greater. Case in point: During the last couple of years, I've not seen any nonstandard floating point storage representation. On the other hand, last year 16 bit ints were inflicted upon me (an embedded target), and on UNICOS-MAX I found the 64 bit ints were slightly irritating, too. You are apparently confusing natural numbers, which don't include negatives, with integers. Right, I used the wrong term. However it's a quite common mistake to forget how bad floats model real numbers. And it's quite a common mistake to forget how bad finite ints model integer numbers. This corroborates the validity of the analogy with IEEE real arithmetic. And wrong assumptions lead to wrong conclusions. Which assumption was wrong? -richy. -- Richard B. Kreckel http://www.ginac.de/~kreckel/
Re: GCC optimizes integer overflow: bug or feature?
But the same applies to floating point numbers. There, the
situation is even better, because nowadays I can rely on a float or
double being the representation defined in IEEE 754 because there
is such overwhelming hardware support.
You better don't. Really! Please just realize for example the impact
of the (in)famous 80 bit internal (over)precision of a
very common IEEE 754 implementation...
volatile float b = 1.;
if (1. / 3. == b / 3.) {
printf(HALLO!\n)
} else {
printf(SURPRISE SURPRISE!\n);
}
or just skim through http://gcc.gnu.org/bugzilla/show_bug.cgi?id=323
However it's a quite common mistake to forget how bad floats
model real numbers.
And it's quite a common mistake to forget how bad finite ints
model integer numbers.
No it isn't. Most people don't think in terms of infinite arithmetics
when programming.
And I hold up that the difference between finite and infinite is
actually quite a fundamental
concept. However quite a lot of people expect the floating
arithmetics rouding to give them
well behaved results.
Marcin Dalecki
Re: GCC optimizes integer overflow: bug or feature?
Paul Brook [EMAIL PROTECTED] writes: | Compiler can optimize it any way it wants, | as long as result is the same as unoptimized one. | | We have an option for that. It's called -O0. | | Pretty much all optimization will change the behavior of your program. The | important distinction is whether that difference is observable in valid | programs. The whole point of langage standards is that they define what | constitutes a valid program. The problem is that what constitutes a valid program tends to differ from what constitutes a useful program found in the wild. The question for GCC is how to accomodate for the useful uses without getting far away from both conformance and non-conformance. I don't believe this particular issue of optimization based on undefined behaviour can be resolved by just telling people hey look, the C standard says it is undefined, therefore we can optimize. And if you're not happy, just tell the compiler not to optimize. For not all undefined behaviour are equal, and undefined behaviour is also a latitude given to implementors to better serve their base users. -- Gaby
Re: GCC optimizes integer overflow: bug or feature?
Dave Korn [EMAIL PROTECTED] writes: [...] | We (in a major, commercial application) ran into exactly this issue. | 'asm volatile(lock orl $0,(%%esp)::)' is your friend when this happens | (it is a barrier across which neither the compiler nor CPU will reorder | things). Failing that, no-op cross-library calls (that can't be inlined) | seem to do the trick. | | This simply means you have failed to correctly declare a variable volatile | that in fact /is/ likely to be spontaneously changed by a separate thread of | execution. Note however, that declaring the variable volatile is no guarantee that things will actually work as expected. We have had that discussion before :-) -- Gaby
Re: GCC optimizes integer overflow: bug or feature?
Andrew Haley [EMAIL PROTECTED] writes: [...] | C is no longer a kind of high-level assembly laguage: | it's defined by a standard, in terms of an abstract machine, and some | operations are not well-defined. that does not mean C is not a kind of high-level assembly language. :-/ -- Gaby
Re: GCC optimizes integer overflow: bug or feature?
Matthew Woehlke [EMAIL PROTECTED] writes: That said, I've seen even stranger things, too. For example: foo-bar = make_a_bar(); foo-bar-none = value; being rendered as: call make_a_bar foo-bar-none = value foo-bar = result of make_a_bar() That would obviously be a bug in the compiler. /That/ is very possible. I'm talking about /OLD/ code here, i.e. code that was written back in KR days, back before there /was/ a volatile keyword. (Although I had understood that 'volatile' was a no-op in most modern compilers? Does it have the semantics that loads/stores of volatile variables are not re-ordered with respect to each other?) volatile should not be a no-op in any C compiler. volatile variables must be accessed strictly according to the rules of the virtual machine. For example, if the code reads the variable twie, the program must read the variable twice; it can't cache the value after the first read. volatile variables are reasonably useful for accessing memory mapped devices, in which the memory may change in ways which the compiler does not see. They are not particularly useful, by themselves, for multi-processor systems, because they provide no guarantees about synchronization between processors. And relying on a library call to act as a memory barrier is risky. [snip] Now, the compiler *does* know not to optimise moves across library calls, but you're investing too much trust in them if you think the CPU's internal units know or care whether you're in a libcall or your mainline code. You're preaching to the choir. Unfortunately adding proper assembly modules to our build system didn't go over so well, and I am /not/ going to try to write inline assembler that works on six-or-more different compilers. :-) So I know this is just a 'cross your fingers and hope it works' approach on non-x86 platforms. On x86 I use the correct, previously-quoted inline assembly, which as mentioned acts as a barrier for both the compiler /and/ the CPU. As you say, all it's really ensuring in other cases is that the compiler remains honest, but that was the intent, and I know it isn't perfect. Current versions of gcc provide a set of synchronization primitives which may help write code which works correctly on multi-processor systems. Ian
RE: GCC optimizes integer overflow: bug or feature?
On 20 December 2006 20:16, Seongbae Park wrote: On 12/20/06, Dave Korn [EMAIL PROTECTED] wrote: ... We (in a major, commercial application) ran into exactly this issue. 'asm volatile(lock orl $0,(%%esp)::)' is your friend when this happens (it is a barrier across which neither the compiler nor CPU will reorder things). Failing that, no-op cross-library calls (that can't be inlined) seem to do the trick. This simply means you have failed to correctly declare a variable volatile that in fact /is/ likely to be spontaneously changed by a separate thread of execution. The C or C++ standard doesn't define ANYTHING related to threads, and thus anything related to threads is beyond the standard. If you think volatile means something in an MT environment, think again. No no, I fully appreciate that; what volatile means is simply that the object may change outside the control or knowledge of the compiler, the particular mechanism does not matter at all, and that is all that is relevant for the purpose of my argument. cheers, DaveK -- Can't think of a witty .sigline today
Re: GCC optimizes integer overflow: bug or feature?
On Thursday 21 December 2006 02:38, Gabriel Dos Reis wrote: Paul Brook [EMAIL PROTECTED] writes: | Compiler can optimize it any way it wants, | as long as result is the same as unoptimized one. | | We have an option for that. It's called -O0. | | Pretty much all optimization will change the behavior of your program. | The important distinction is whether that difference is observable in | valid programs. The whole point of langage standards is that they define | what constitutes a valid program. The problem is that what constitutes a valid program tends to differ from what constitutes a useful program found in the wild. The question for GCC is how to accomodate for the useful uses without getting far away from both conformance and non-conformance. I never said any different. If fact you'll notice that later in the same email (which you have cut) I said pretty much the same thing. The post I was replying to wasn't suggesting that we should support specific cases of nonconforming code, it was saying that we shouldn't change the behavior of *any* code. Paul
RE: GCC optimizes integer overflow: bug or feature?
On 20 December 2006 21:42, Matthew Woehlke wrote: Dave Korn wrote: Particularly lock-free queues whose correct operation is critically dependent on the order in which the loads and stores are performed. No, absolutely not. Lock-free queues work by (for example) having a single producer and a single consumer, storing the queue in a circular buffer, and assigning ownership of the queue's head pointer to the producer and the (chasing) tail pointer to the consumer. [snip] The ordering is critical within a single thread of execution; e.g. you must fill in all the details of the new entry you are adding to the queue /before/ you increment the head pointer, Exactly. Guess what the compiler did to us? :-) Oh, no, I'm /sure/ it's OK if I re-order your code so that those assignments happen /after/ I handle this dinky little increment for you. Now our code may have been wrong in this instance Exactly and unquestionably so. You wrote wrong code, it worked not how you expected it, but the compiler *did* do exactly as you told it to and there's an end of it. You left out 'volatile', you completely lied to and misled the compiler! Let's be clear. Order matters. /You/ said so yourself. :-) And even if the programmer correctly tells the compiler what to do, what (unless the compiler inserts memory barriers) keeps the CPU from circumventing both? You wrote wrong code, it worked not how you expected it, but the compiler *did* do exactly as you told it to and there's an end of it. You left out 'volatile', you completely lied to and misled the compiler about what /it/ could assume about the behaviour of entities in the compiled universe. That said, I've seen even stranger things, too. For example: foo-bar = make_a_bar(); foo-bar-none = value; being rendered as: call make_a_bar foo-bar-none = value foo-bar = result of make_a_bar() So what was wrong with my C code in that instance? :-) You'd have to show me the actual real code before I could tell you whether there was a bug in your code or you hit a real bug in the compiler. Either is possible; the virtual machine definition in the standard AKA the 'as-if' rule is what decides which is correct and which is wrong. C is no longer a glorified shorthand for assembly code. It did /used to be/, but every development since K'n'R days has taken it further from that. At -O0, it still /almost/ is a glorified assembler. This is a very real, entirely legitimate example where the compiler thinking it knows how to do my job better than I do is wrong. Nope, this is a very real example of a bug in your algorithmic design, or of you misleading the compiler, or relying on undefined or implementation-defined behaviour. [snip] This simply means you have failed to correctly declare a variable volatile that in fact /is/ likely to be spontaneously changed by a separate thread of execution. /That/ is very possible. I'm talking about /OLD/ code here, i.e. code that was written back in KR days, back before there /was/ a volatile keyword. (Although I had understood that 'volatile' was a no-op in most modern compilers? Does it have the semantics that loads/stores of volatile variables are not re-ordered with respect to each other?) Exactly so, that's why 'volatile' was chosen as the keyword to extend 'asm' in order to mean don't reorder past here because it's unpredictable. As I said, C is no longer a glorified assembler language, and one of the main motivations behind that progression is the non-portability of code such as you describe above, the fact that making assumptions about the precise details behind a compiled version of any particular code sequence is a mistake because they'll only turn out to be right on some platforms and with some compiler versions and not with others. The compiler is *not* a glorified assembler; if you really want guarantees about what codegen you get, use a .S file and write assembler. Or use a 20-year-old version of the compiler if what you *really* want is the exact codegen it used to do 20 years ago. It's open source, it's free, you can get it and use it and keep on using it for ever and it will *always* produce exactly what you expect by the way of codegen. These days, however, you have to accept that your code is not valid; that it contains implicit assumptions that were only ever going to be true for the particular compiler version and on the particular platform where it was first written. And that code needs maintenance, as a matter of routine. If you want to change one part of a system, you must change all the interacting parts to match. If you want your source code to work exactly how it did twenty years ago, the rest of your toolchain better behave exactly the same as it did twenty years ago. Of course, this leaves us a big problem. How can anything ever change, advance, or improve, if either everything has to change at once, or everything will break
RE: GCC optimizes integer overflow: bug or feature?
On 21 December 2006 02:50, Gabriel Dos Reis wrote: Andrew Haley [EMAIL PROTECTED] writes: [...] C is no longer a kind of high-level assembly laguage: it's defined by a standard, in terms of an abstract machine, and some operations are not well-defined. that does not mean C is not a kind of high-level assembly language. :-/ -- Gaby I swear, I wrote my previous two mails before I read this exchange! cheers, DaveK -- Can't think of a witty .sigline today
Re: GCC optimizes integer overflow: bug or feature?
Gabriel Dos Reis wrote: I don't believe this particular issue of optimization based on undefined behaviour can be resolved by just telling people hey look, the C standard says it is undefined, therefore we can optimize. And if you're not happy, just tell the compiler not to optimize. For not all undefined behaviour are equal, and undefined behaviour is also a latitude given to implementors to better serve their base users. Right, and better service is a combination of doing what is expected and generating fast code, and sometimes the two do conflict, and then we have to do the best we can to balance the conlicting goals. My concern is that in achieving this balance, we really need to have data to show that we are indeed generating significantly faster code. Compiler writers tend to want to optimize the last instruction out in any situation, without necessarily showing it is significant to do so.
Re: GCC optimizes integer overflow: bug or feature?
Brooks Moses wrote: Now, if your argument is that following the LIA-1 standard will prevent optimizations that could otherwise be made if one followed only the C standard, that's a reasonable argument, but it should not be couched as if it implies that preventing the optimizations would not be following the C standard. I continue to suspect that the gains from this optimization are minimal to non-existent in practice. Given the requirements in LIA-1, I would think that taking advantage of overflow being undefined is only acceptable if there is very clear quantitative data showing that this indeed is a significant optimization.
Re: GCC optimizes integer overflow: bug or feature?
Robert Dewar writes: Brooks Moses wrote: Now, if your argument is that following the LIA-1 standard will prevent optimizations that could otherwise be made if one followed only the C standard, that's a reasonable argument, but it should not be couched as if it implies that preventing the optimizations would not be following the C standard. I continue to suspect that the gains from this optimization are minimal to non-existent in practice. Given the requirements in LIA-1, I would think that taking advantage of overflow being undefined is only acceptable That's an interesting use of the passive voice. Acceptable to whom? if there is very clear quantitative data showing that this indeed is a significant optimization. We've already defined `-fwrapv' for people who need nonstandard arithmetic. I don't see that this is any different from the interminable strict-aliasing discussion. Andrew.
Re: GCC optimizes integer overflow: bug or feature?
Andrew Haley wrote: Robert Dewar writes: Brooks Moses wrote: Now, if your argument is that following the LIA-1 standard will prevent optimizations that could otherwise be made if one followed only the C standard, that's a reasonable argument, but it should not be couched as if it implies that preventing the optimizations would not be following the C standard. I continue to suspect that the gains from this optimization are minimal to non-existent in practice. Given the requirements in LIA-1, I would think that taking advantage of overflow being undefined is only acceptable That's an interesting use of the passive voice. Acceptable to whom? acceptable from a technical perspective. Damaging useability on the basis of providing better optimization without good data showing that the optimization is worthwhile seems unjustifiable to me. Compiler writers overestimate the value of optimizations all the time. To me it is essential to have data to back up arguments that optimizations that change behavior are worth while. For example, putting variables in registers instead of memory most definitely changes behavior (by making uninitialized variables have a much more deleterious effect in practice), but is easily justified since we can easily show that many programs are really substantially helped by this optimization. We've already defined `-fwrapv' for people who need nonstandard arithmetic. Nonstandard implies that the result does not conform with the standard, which is not correct. -fwrapv provides semantics that exactly conform with the C standard. But how do we know that there is any point to this option? It would not seem hard to run a set of benchmarks. I don't have access to helpful examples, but for what I ran, -fwrapv had no detectable effect on performance. It sure would be nice to get at least ONE example that is at least semi-realistic where it makes a difference. When I worked on SPITBOL, people all the time were suggesting optimizations in letters to the SPITBOL newsletter. I imposed a rule saying that no one could propose an optimization unless they could show ONE example program where the optimization could plausibly save 5% execution time. I never got another suggestion. I don't see that this is any different from the interminable strict-aliasing discussion. Yes, and sadly missing from that discussion is sufficient concrete data, though indeed there are some examples that we know of there, so certainly my 5% rule would apply. Even there I would make strict-aliasing the default (I have argued stronly for that in the GNAT context, but the back end folks are sure (without data) that no-strict-aliasing has a noticeable effect, so it is still the default. In practice we advise many of our large customers to routinely use -fno-strict-aliasing, and we have introduced a pragma to marke individual types to suppress strict aliasing.
Re: GCC optimizes integer overflow: bug or feature?
On Tue, 2006-12-19 at 03:42 -0500, Robert Dewar wrote:
When I worked on SPITBOL, people all the time were suggesting
optimizations in letters to the SPITBOL newsletter. I imposed
a rule saying that no one could propose an optimization unless
they could show ONE example program where the optimization could
plausibly save 5% execution time. I never got another suggestion.
http://gcc.gnu.org/bugzilla//show_bug.cgi?id=18527
A simple loop like:
int foo ()
{
int a[N];
int i;
int n;
for (i = 0; i = n; i++)
ca[i] = 2;
}
we cannot find how many iterations it runs without knowing that signed
types overflow.
And yes people write code like that, it shows up in GCC itself IIRC (as
the original testcase comes from GCC in SPEC).
I don't have the number of times this shows up or how much it helps but
it does help out on being able to vectorize this loop.
Another example (this time for for (i=i0; i=i1+1; ++i) )
http://gcc.gnu.org/bugzilla//show_bug.cgi?id=26900
via:
http://gcc.gnu.org/bugzilla//show_bug.cgi?id=26899
which can only be done when signed overflow is undefined.
All of these do show up in real code, and since loops are now more
important to optimize than anything else, well knowing the number of
iterations is very important.
Thanks,
Andrew Pinski
Re: GCC optimizes integer overflow: bug or feature?
Andrew Pinski wrote: I don't have the number of times this shows up or how much it helps but it does help out on being able to vectorize this loop. Just to be clear, when I ask for quantitative data, it is precisely data about how much it helps. It is always easy enough to show cases where the optimization does help the code. All of these do show up in real code, and since loops are now more important to optimize than anything else, well knowing the number of iterations is very important. Using very is usually a substitute for actual data, and that appears to be the case here. What would make me confident that this optimization is worth while is a message that says This test (hopefully one from a realistic example, or at least from a real benchmark suite, and not just cooked up for demonstration) runs in X seconds with the optimization and X+Y seconds without on bla architecture. That does not seem too much to ask :-) Thanks, Andrew Pinski
Re: GCC optimizes integer overflow: bug or feature?
Ralf Wildenhues [EMAIL PROTECTED] writes: Maybe it's also just an unintended bug I happened to observe (and take for given behavior)? I read up a bit more and it looks like it is intended behavior. However, this disruptive change isn't documented in http://gcc.gnu.org/gcc-4.2/changes.html, which is where I assume stuff like this should be mentioned. (In Capital Letters. :-) The irony of this is that I ran into this problem in 1992 or so, and had the problem fixed in GCC back then. The problem was that the DEC SRC Modula-3 runtime had code that looked something like this: int i, n; ... if (0 i n + i n) report_integer_overflow (); GCC 2.2.2 came out with a new optimization (on the SPARC, with -O) that decided to optimize away the entire `if' statement, on the grounds that the only way that the 'if' could succeed was for integer overflow to occur, and the resulting behavior was undefined. Obviously C89 allows this optimization, as does C99 without LIA-1. But a reasonable amount of C code will break if you do it, and some of this code is in glibc and has been in glibc for quite some time. As well as in other programs like the Modula-3 implementation. This is why the optimization was removed from GCC soon after GCC 2.2.2 came out.
Re: GCC optimizes integer overflow: bug or feature?
Robert Dewar writes: Andrew Haley wrote: We've already defined `-fwrapv' for people who need nonstandard arithmetic. Nonstandard implies that the result does not conform with the standard, I don't think it does; it merely implies that any program which requires -fwrapv for correct execution is not a strictly conforming program. Andrew.
Re: GCC optimizes integer overflow: bug or feature?
Does the test hang forever?
No, the timeout works.
So the app builds. But it has latent bugs. Wonderful.
Is the performance gain by this change to gcc -O2 really worth all
this software engineering hassle and breakage for typical
applications? I'm talking about apps like 'date', 'touch', and
'expr'. Also glibc. Also Python. (They're all affected. Silently.
Ouch.)
I'm not much worried about bugs stemming from loop induction issues; I
think they're unlikely in mainline GNU apps, and at any rate we can
program around them by using unsigned indexes.
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.
There's a lot of overflow-checking code like this in the GNU world.
I'll bet GCC itself has some. Yes, we know this code doesn't conform
to the C Standard sans LIA-1 because signed integer overflow has
undefined behavior if you don't also conform to LIA-1. But there is
no standard way to detect overflow. So we assume wraparound signed
integer arithmetic a la Java and LIA-1. What else can we do,
realistically?
I'm afraid I don't have time to do a code sweep looking for all
instances of where this change to gcc -O2 silently breaks GNU apps.
So unless someone can come up with a better suggestion, I'm inclined
to suggest that we modify coreutils and similar GNU applications so
that their 'configure' scripts and makefiles use -fwrapv when
compiling with gcc. As I understand it, -fwrapv is supposed to fix
the problem. We can also add whatever options non-GNU suppliers want
us to use.
This can be done in Autoconf and/or gnulib, so that the fixes are easy
for GNU apps to pick up by default. This will work around the
problem, at least for the GNU programs I help maintain.
Re: GCC optimizes integer overflow: bug or feature?
Andrew Haley [EMAIL PROTECTED] writes: | Robert Dewar writes: | Andrew Haley wrote: | |We've already defined `-fwrapv' for people who need nonstandard |arithmetic. | | Nonstandard implies that the result does not conform with the standard, | | I don't think it does; it merely implies that any program which | requires -fwrapv for correct execution is not a strictly conforming | program. How many useful C programs do you know that are strictly conforming? Certainly, GCC isn't stritcly conforming. I suspect the actual argument must be somewhere else. -- Gaby
Re: GCC optimizes integer overflow: bug or feature?
Gabriel Dos Reis writes: Andrew Haley [EMAIL PROTECTED] writes: | Robert Dewar writes: | Andrew Haley wrote: | |We've already defined `-fwrapv' for people who need nonstandard |arithmetic. | | Nonstandard implies that the result does not conform with the standard, | | I don't think it does; it merely implies that any program which | requires -fwrapv for correct execution is not a strictly conforming | program. How many useful C programs do you know that are strictly conforming? Certainly, GCC isn't stritcly conforming. I suspect the actual argument must be somewhere else. I'm sure it is. The only purpose of my mail was to clarify what I meant by nonstandard, which in this case was not strictly conforming. I didn't intend to imply anything else. In this case, there are two ways to view the program: either it has a bug, or it has an environmental depencency on wrapping integer arithmetic. Andrew.
Re: GCC optimizes integer overflow: bug or feature?
* Andrew Pinski:
A simple loop like:
int foo ()
{
int a[N];
int i;
int n;
for (i = 0; i = n; i++)
ca[i] = 2;
}
we cannot find how many iterations it runs without knowing that signed
types overflow.
In this case, the assumption is not needed because the lack of
overflow can be inferred from the validity of the expression ca[i] for
all relevant i. However, in the general case, such information might
not be available. I wonder if it is feasible to duplicate the loop
code, once for positive n, and once for negative, or if this would
lead to too much code bloat in real-world applications.
By the way, as I've tried to describe here:
http://cert.uni-stuttgart.de/advisories/c-integer-overflow.php
variable range tracking can result in reintroduction of
supposedly-fixed security vulnerabilities. 8-(
Re: GCC optimizes integer overflow: bug or feature?
By the way, as I've tried to describe here: http://cert.uni-stuttgart.de/advisories/c-integer-overflow.php variable range tracking can result in reintroduction of supposedly-fixed security vulnerabilities. 8-( Interesting read. I agree with the proposed fix; however, note that GCC does not make the result of overflowing signed left-shifts undefined, exactly because in this case the overflow is relied upon by too many existing programs (and also because left shifts are inherently a bitwise operation, with well defined overflowing behavior on the most significant bits). Paolo
Re: GCC optimizes integer overflow: bug or feature?
Andrew Haley [EMAIL PROTECTED] writes: | Gabriel Dos Reis writes: | Andrew Haley [EMAIL PROTECTED] writes: | | | Robert Dewar writes: | | Andrew Haley wrote: | | | |We've already defined `-fwrapv' for people who need nonstandard | |arithmetic. | | | | Nonstandard implies that the result does not conform with the standard, | | | | I don't think it does; it merely implies that any program which | | requires -fwrapv for correct execution is not a strictly conforming | | program. | | How many useful C programs do you know that are strictly conforming? | Certainly, GCC isn't stritcly conforming. | | I suspect the actual argument must be somewhere else. | | I'm sure it is. No doubt GCC is useful. But I very much doubt it is a strictly conforming program. [#5] A strictly conforming program shall use only those features of the language and library specified in this International Standard.2) It shall not produce output dependent on any unspecified, undefined, or implementation- defined behavior, and shall not exceed any minimum implementation limit. | The only purpose of my mail was to clarify what I | meant by nonstandard, which in this case was not strictly | conforming. I didn't intend to imply anything else. OK. The way I saw the exchange of arguments was * Give data that justify this breakage + But we have -fwrapv for nonstandard arithmetic * -fwrap implements standard conforming semantics + But a program that needs -fwrap is not stricly conforming which reads to me as an abstract (bogus) argument is being made in place of providing actual data. What worries me the most -- and prompted my message -- is the implication that it is OK to break a non strictly conforming program. If GCC systematically goes there, it will quickly become useless (except for academic exercises). And I'm sure you did not intend that. Consequently, I suspect the breakage must be non-systematic, but guided by some principles or rules. I also believe that the breakage is not done just because something is labelled an optimization. In end, we need actual data to back up the claim that the transformation is indeed an optimization worthwhile, and it is a good thing for most actual software to have it enabled by default. | In this case, there are two ways to view the program: either it has a | bug, or it has an environmental depencency on wrapping integer | arithmetic. environmental dependency is not necessrily indication of bug. For sure, integer overflow is undefined according to the C standard. However, the C standard is not the only thing in the world that C programs care about. Theere are other useful standards (some of them make contradictory requirements with respect to ISO C). The quandry is to find a ground where GCC implements the C standard, remains useful, yet does a good job. I don't think we can systematically apply the abstract argument that if a program contains an undefined behaviour it is OK to break it. And indeed, GCC already have acknowledged some undefined behaviour and promise not to break programs that contain them. -- Gaby | | Andrew. -- Gabriel Dos Reis [EMAIL PROTECTED] Texas AM University -- Department of Computer Science 301, Bright Building -- College Station, TX 77843-3112
Re: GCC optimizes integer overflow: bug or feature?
Andrew Haley wrote: Robert Dewar writes: Andrew Haley wrote: We've already defined `-fwrapv' for people who need nonstandard arithmetic. Nonstandard implies that the result does not conform with the standard, I don't think it does; it merely implies that any program which requires -fwrapv for correct execution is not a strictly conforming program. OK, well if you say to people gcc is a nonstandard implementation of C99, most people will read that to indicate that it is non-conforming, so I suggest avoiding this term. Andrew.
Re: GCC optimizes integer overflow: bug or feature?
Gabriel Dos Reis wrote: Andrew Haley [EMAIL PROTECTED] writes: | Robert Dewar writes: | Andrew Haley wrote: | |We've already defined `-fwrapv' for people who need nonstandard |arithmetic. | | Nonstandard implies that the result does not conform with the standard, | | I don't think it does; it merely implies that any program which | requires -fwrapv for correct execution is not a strictly conforming | program. How many useful C programs do you know that are strictly conforming? Certainly, GCC isn't stritcly conforming. The other danger in using nonstandard in this peculiar way is that it is too easy to use or at least think in terms of the argument. This feature is nonstandard We want gcc to be standard Therefore we don't want this feature which is faulty reasoning in this particular case. The ONLY reason for doing the optimization is to improve performance, it does not somehow make gcc more standard to take implement undefined in an unpredictable manner :-)
Re: GCC optimizes integer overflow: bug or feature?
Andrew Haley wrote: I suspect the actual argument must be somewhere else. I'm sure it is. The only purpose of my mail was to clarify what I meant by nonstandard, which in this case was not strictly conforming. I didn't intend to imply anything else. But a compiler that implements wrap around IS strictly conforming. A program that takes advantage of it is depending on non-standard semantics, but then so is any program that uses floating-point and expects it to have IEEE semantics to any extent.
Re: GCC optimizes integer overflow: bug or feature?
* Paolo Bonzini: Interesting read. I agree with the proposed fix; however, note that GCC does not make the result of overflowing signed left-shifts undefined, exactly because in this case the overflow is relied upon by too many existing programs Is this documented somewhere? Without documentation, it could also be an oversight (lack of optimization) from a programmer perspective.
Re: GCC optimizes integer overflow: bug or feature?
Florian Weimer wrote: * Paolo Bonzini: Interesting read. I agree with the proposed fix; however, note that GCC does not make the result of overflowing signed left-shifts undefined, exactly because in this case the overflow is relied upon by too many existing programs Is this documented somewhere? Without documentation, it could also be an oversight (lack of optimization) from a programmer perspective. It generally seems desirable for me to have a documentation section which takes every undefined in the standard and says what is done with it (sort of like Annex M in the documentation for an Ada compiler).
Re: GCC optimizes integer overflow: bug or feature?
Hello, Now, if your argument is that following the LIA-1 standard will prevent optimizations that could otherwise be made if one followed only the C standard, that's a reasonable argument, but it should not be couched as if it implies that preventing the optimizations would not be following the C standard. I continue to suspect that the gains from this optimization are minimal to non-existent in practice. the majority of loop optimizations work only assuming that induction variables do not overflow. This assumption can sometimes be verified using quite expensive analyses of the loop code, or in majority of cases easily derived if the induction variables are either signed or pointers (where the standard allows us to assume that the arithmetics does not overflow). Note that there was even a serious discussion about enabling -funsafe-loop-optimizations by default at some optimization level, thus making us assert that *no* induction variables (regardless of signedness) overflow; which IIRC is what some other compilers do. IMHO, using loops relying on the behavior of overflow of an induction variable (*) is an ugly hack and whoever writes such a code does not deserve for his program to work. Zdenek (*) especially without bothering to verify what the language standard says about that
Re: GCC optimizes integer overflow: bug or feature?
Zdenek Dvorak wrote: IMHO, using loops relying on the behavior of overflow of an induction variable (*) is an ugly hack and whoever writes such a code does not deserve for his program to work. I suspect everyone would agree on this, and in practice I would guess that a) there are no programs that rely on this b) the value of the optimization if any, is probably almost all from this treatment of induction variables in loops. Perhaps the proper resolution here is to implement and document that gcc will wrap except in the case of loop variables (needs some more careful documentation of course).
Re: GCC optimizes integer overflow: bug or feature?
On Tue, 19 Dec 2006, Florian Weimer wrote:
* Paolo Bonzini:
Interesting read. I agree with the proposed fix; however, note that
GCC does not make the result of overflowing signed left-shifts
undefined, exactly because in this case the overflow is relied upon by
too many existing programs
Is this documented somewhere? Without documentation, it could also be
an oversight (lack of optimization) from a programmer perspective.
Certainly, in implement-c.texi:
GCC does not use the latitude given in C99 only to treat certain
aspects of signed @samp{} as undefined, but this is subject to
change.
This particular case has the special property that signed was
implementation-defined in C90 (DR#081) and became undefined in some cases
in C99.
We've optimized expressions such as (a*2)/2 on the basis of overflow being
undefined for a very long time, not just loops.
--
Joseph S. Myers
[EMAIL PROTECTED]
Re: GCC optimizes integer overflow: bug or feature?
Joseph S. Myers wrote:
On Tue, 19 Dec 2006, Florian Weimer wrote:
* Paolo Bonzini:
Interesting read. I agree with the proposed fix; however, note that
GCC does not make the result of overflowing signed left-shifts
undefined, exactly because in this case the overflow is relied upon by
too many existing programs
Is this documented somewhere? Without documentation, it could also be
an oversight (lack of optimization) from a programmer perspective.
Certainly, in implement-c.texi:
GCC does not use the latitude given in C99 only to treat certain
aspects of signed @samp{} as undefined, but this is subject to
change.
That hardly seems sufficient documentation, when documenting undefined,
you had better say what the semantics is. Saying it is not treated as
undefined, and then failing to define it is a bit of a contradiction
in terms :-)
This particular case has the special property that signed was
implementation-defined in C90 (DR#081) and became undefined in some cases
in C99.
We've optimized expressions such as (a*2)/2 on the basis of overflow being
undefined for a very long time, not just loops.
What is (a*2)/2 optimized to? certainly it has the value a if you wrap,
so you are not necessarily depending on undefined here.
Re: GCC optimizes integer overflow: bug or feature?
* Joseph S. Myers:
On Tue, 19 Dec 2006, Florian Weimer wrote:
* Paolo Bonzini:
Interesting read. I agree with the proposed fix; however, note that
GCC does not make the result of overflowing signed left-shifts
undefined, exactly because in this case the overflow is relied upon by
too many existing programs
Is this documented somewhere? Without documentation, it could also be
an oversight (lack of optimization) from a programmer perspective.
Certainly, in implement-c.texi:
GCC does not use the latitude given in C99 only to treat certain
aspects of signed @samp{} as undefined, but this is subject to
change.
Thanks, I missed that paragraph. But I fail to see how this is
helpful in any way to a programmer. To me, it reads like we've got
some predictable semantics in some cases, but we don't tell you what
they are, and if you rely on them by chance, your code may break with
the next compiler release, without notice.
Something like:
GCC does not use the latitude given in C99 only to treat
certain aspects of signed @samp{} as undefined: If the right
operand @var{n} is non-negative and less than the width of the
left operand @var{val}, the resulting value @[EMAIL PROTECTED]
@var{n}} is guaranteed to be equal to @var{val} times 2 to the
@var{n}th power under 2-complement arithmetic.
would probably settle the issue, but it's unwieldy.
