Bug 30475 - assert(int+100 > int) optimized away
Summary: assert(int+100 > int) optimized away
Status: RESOLVED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: c (show other bugs)
Version: 4.1.1
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2007-01-15 19:43 UTC by felix-gcc
Modified: 2023-10-27 17:50 UTC (History)
11 users (show)

See Also:
Host: x86_64-unknown-linux-gnu
Target: x86_64-unknown-linux-gnu
Build: x86_64-unknown-linux-gnu
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description felix-gcc 2007-01-15 19:43:02 UTC
The small test program at http://ptrace.fefe.de/int.c illustrated the problem.

The assert is there to prevent integer overflow, which would not happen in my test program, but you get the idea.

There appears to be something wrong with integer promotion here.  The same code with int changed to unsigned int (http://ptrace.fefe.de/unsignedint.c) correctly fails the assertion at that point.  My understanding of C integer promotion is that the 100 is an int unless anything else is said, so int+100 should still be an int, and so both sides should still be an int.  Is that not correct?
Comment 1 felix-gcc 2007-01-15 19:46:03 UTC
Mhh, if I change "int+100" to "(int)(int+100)", the assert still gets optimized away.

So it's not an integer promotion issue.  Both sides are definitely int.
Comment 2 Andrew Pinski 2007-01-15 19:47:43 UTC
signed type overflow is undefined by the C standard, use unsigned int for the addition or use -fwrapv.
Comment 3 felix-gcc 2007-01-15 19:50:37 UTC
even stranger, if I assert ((int)(a+100) > 0) then it STILL gets optimized away.
WTF!?
Comment 4 felix-gcc 2007-01-15 19:57:08 UTC
(In reply to comment #2)
> signed type overflow is undefined by the C standard, use unsigned int for the
> addition or use -fwrapv.

You have GOT to be kidding?

All kinds of security issues are caused by integer wraps, and you are just telling me that with gcc 4.1 and up I cannot test for them for signed data types any more?!

You are missing the point here.  There HAS to be a way to get around this.  Existing software uses signed int and I can't just change it to unsigned int, but I still must be able to check for a wrap!  There does not appear to be a work around I could do in the source code either!  Do you expect me to cast it to unsigned, shift right by one, and then add or what?!

PLEASE REVERT THIS CHANGE.  This will create MAJOR SECURITY ISSUES in ALL MANNER OF CODE.  I don't care if your language lawyers tell you gcc is right.  THIS WILL CAUSE PEOPLE TO GET HACKED.

I found this because one check to prevent people from getting hacked failed.

THIS IS NOT A JOKE.  FIX THIS!  NOW!
Comment 5 Andrew Pinski 2007-01-15 20:04:37 UTC
> THIS IS NOT A JOKE.  FIX THIS!  NOW!

I am not joking, the C standard explictly says signed integer overflow is undefined behavior.

See PR 27257 and others.

*** This bug has been marked as a duplicate of 27257 ***
Comment 6 Andrew Pinski 2007-01-16 04:47:29 UTC
I forgot to mention GCC already has an option to trap on every signed overflow, -ftrapv, which might be faster than doing it by hand.
Comment 7 Pawel Sikora 2007-01-16 07:00:14 UTC
(In reply to comment #6)
> I forgot to mention GCC already has an option to trap on every signed overflow,
> -ftrapv, which might be faster than doing it by hand.

and it doesn't work -> PR19020
Comment 8 John Simon 2007-01-16 07:24:13 UTC
The original poster might want to read http://c-faq.com/misc/intovf.html and http://c-faq.com/misc/sd26.html to see how he might "prevent people from getting hacked" correctly.
Comment 9 felix-gcc 2007-01-17 13:55:29 UTC
Hey Andrew, do you really think this issue goes away if you keep closing the bugs fast enough?

Let me tell you something: that INT_MAX way to do it is bogus.  These checks are there so that it is obvious the int overflow is caught and handled.  If you use INT_MAX, then the auditor still has to check if it was an int and not an unsigned int, for example.

If that doesn't convince you, let's say it's not int, but it's "ptrdiff_t".  Or "off_t".  Or "beancount_t", which the application defined somewhere.  Then limits.h won't have a _MAX definition for it.  What if the size of the type depends on the context as well?  There are multiple definitions of it depending on some -Dwhatever on the command line?

All these cases were covered just fine by the "if (a+100 < a)" check.  There is no context needed about the type of a, it works for pointers, unsigned integers, and signed integers.  Well, you broke the pointer bit once, too, but that was reverted.  The guy who reverted it back then should come back, we need someone with his vision and good judgement here now.

No, let's face it.  You fucked this up royally, and now you are trying to close all the bugs as fast as you can, so nobody sees just how much damage you have done.  You, sir, are unprofessional and a disgrace to the gcc development team.
And this bug stays open until you revert the change or make it opt-in instead of opt-out.  As long as you just destroy programs where the author foolishly opted in, I don't care.  But I will not let you make my work environment less secure because you don't have the professionalism to let your pet optimization go, after it was shown to do more damage than good.  How much more proof do you need?  For god's sake, autoconf considers turning your "optimization" off globally!  Do you even notice all the explosions around you?

PS: Mr Simon, that link to a how-to that says "btw this doesn't work for this special input", is that supposed to impress anyone?  It certainly does not impress me very much, really.

It's better to keep your mouth shut and appear stupid than to
open it and remove all doubt.
        --Mark Twain (1835 - 1910)
Comment 10 Richard Biener 2007-01-17 14:26:20 UTC
You need to improve your communication skills - pissing people off doesn't help your agenda.  Btw, pointer overflow is undefined and we use that fact.
Comment 11 Richard Biener 2007-01-17 14:31:18 UTC
Btw. your testcase "fails" with gcc 2.95.3 for me as well, so no news here.
Comment 12 felix-gcc 2007-01-17 15:21:10 UTC
(In reply to comment #11)
> Btw. your testcase "fails" with gcc 2.95.3 for me as well, so no news here.
> 

Bullshit.

  $ ./gcc2 -v
  Reading specs from /usr/lib/gcc-lib/i686-pc-linux-gnu/2.95.3/specs
  gcc version 2.95.3 20010315 (release)
  $ ./gcc2 -o int int.c
  200 100
  int: int.c:4: foo: Assertion `a+100 > a' failed.
  $

Why don't you get your facts straight.  My gcc is the stock gcc 2.95.3, your's is apparently some butchered distro version.

You know, the more apologists for the current behavior come forward, the less credible your position looks.
Comment 13 Richard Biener 2007-01-17 16:32:33 UTC
rguenther@murzim:/tmp> /space/rguenther/install/gcc-2.95/bin/gcc -o int int.c -O
rguenther@murzim:/tmp> ./int 
200 100
-2147483549 2147483647

stock 2.95.3 sources.  Don't tell people words, it makes you look like an asshole
Comment 14 felix-gcc 2007-01-17 16:37:21 UTC
1. "apologist", in contrast to "asshole", is not a cuss word.  Apparently you are as ignorant about English as you are about the issue at hand.

2. I showed my gcc -v, why don't you?  Maybe it's platform dependent?  For all we know you could be running this on an old Alpha where sizeof(int)==8.
Comment 15 Dirk Engling 2007-01-17 16:54:23 UTC
(In reply to comment #11)
> Btw. your testcase "fails" with gcc 2.95.3 for me as well, so no news here.

Putting your struggles here aside, I'd like to see a type-agnostic assert from you C-cracks to use for my source code now where the way I handled this is gone. Could you please deliver that or revert the change that led to this unsatisfying situation? Thank you.
Comment 16 Andrew Pinski 2007-01-17 16:56:53 UTC
http://c-faq.com/misc/sd26.html is all I am going to say from now on.  It tell you explictly how to dectect an overflow before an overflow is going to happen.
Comment 17 felix-gcc 2007-01-17 17:02:56 UTC
You misunderstand.

We don't want you to say anything.

We want to you make your "optimization" off by default, or remove it altogether.

You could also try to convince us that there is any actual tangible performance gain, then you would at least have a leg to stand on.  We would still laugh in your face because you broke security code in real world apps and refuse to fix it, though, but it would be a start.
Comment 18 Richard Biener 2007-01-17 17:05:58 UTC
There is no single change that led to this situation and "reverting" it from
current development sources will not satisfy you anyway because old versions
are then still "affected".

The correct way to test for this overflow with compilers that implement
C90 6.2.1.2 / C99 6.3.1.3 as using modulo 2^N reduction is to simply
use unsigned arithmetic:

int foo(int a) {
  assert((signed)((unsigned)a+100) > a);
  printf("%d %d\n",a+100,a);
  return a;
}

if that is not the case you need to avoid the overflow (as a conforming
implementation may also trap here) in the first place, so for example

int foo(int a)
{
  if (a > INT_MAX - 100)
    abort ();
  printf("%d %d\n", a, a + 100);
  return a;
}
Comment 19 Andrew Pinski 2007-01-17 17:12:00 UTC
Again your code is broken to the standard and the comp.lang.c faq mentions a way to not dependent on the undefined code so this again is not really a bug.

The question about security is what do you trust, the inputs or the outputs?  Really what you are saying with your current code, you trust the inputs but not the outputs.  What the code given in the comp.lang.c faq does is not trust the inputs.  I am sorry that you wrote broken code to begin with but given you are writting C+signedintegeroverflowaswrapping code and not C (and GCC is a C compiler), GCC breaks your code.  
Comment 20 Andrew Macleod 2007-01-17 17:14:11 UTC
Perhaps comment #12 and comment #13 would have the same results if they both used the same options?  One has -O and the other does not.
Comment 21 felix-gcc 2007-01-17 17:20:28 UTC
I DID NOT WRITE THE BROKEN CODE.

Trying to trivialize the issue or insult me will not make it go away.

So, please tell me, which part of the argument in comment #9 were you unable to follow?  I could try using less complicated words so you actually understand it this time around.

Guys, your obligation is not just to implement the C standard.  Your obligation is also not to break apps that depend on you.  And A LOT of apps are depending on you.  When you broke the floating point accuracy, you made it opt-in (-ffast-math).  When you added the aliasing breakage, you made it opt-in (-fstrict-aliasing).  IIRC for that you also quoted some legalese from the standard at first, until people with more grounding in reality overruled you.  And I'm going to keep this bug open until the same thing happens again for this issue.

You can't just potentially break of the free software in the world because you changed your mind about what liberty the C standard gives you.  Grow up or move out of the way and let more responsible people handle our infrastructure.

You know that the Ariane 5 rocket crashed (and could have killed people!) because of an int overflow?  What if people die because you decided the C standard allows you to optimize away other people's security checks?

Again: IT DOES NOT MATTER WHAT THE C STANDARD SAYS.  You broke code, people are suffering damage.  Now revert it.  The least you can do is make -fwrapv on by default.  You would still have to make it actually work (I hear it's broken in some corner cases?), but that's another story.
Comment 22 Andrew Pinski 2007-01-17 17:42:20 UTC
(In reply to comment #21)
> I DID NOT WRITE THE BROKEN CODE.

But you wrote the bug so I assumed you wrote it.

> Trying to trivialize the issue or insult me will not make it go away.

How about this has not changed since at least "January 24, 1994" (when 2.5.8 was released) so the decission about this code was made 13 years ago.  What does that say about new code since then? 

 
> So, please tell me, which part of the argument in comment #9 were you unable to
> follow?  I could try using less complicated words so you actually understand it
> this time around.

None.  Just this decission was done a long long time ago before I even started working on GCC.
 
> Guys, your obligation is not just to implement the C standard.  Your obligation
> is also not to break apps that depend on you.  And A LOT of apps are depending
> on you.  When you broke the floating point accuracy, you made it opt-in
> (-ffast-math). 
Actually -ffast-math breaks the C standard too so your argument here fails.

>  When you added the aliasing breakage, you made it opt-in
> (-fstrict-aliasing). 
I think we should not have made that optional but I was not around when that decission was made.  Also remember we had a release (2.95) where it was on and then it had to be turned off by default (2.95.2) while people fixed there code  but while this optimization was on during that time.
And we do make this optimization optional with -fwrapv already so I don't see where you argument is going to now.

>  IIRC for that you also quoted some legalese from the
> standard at first, until people with more grounding in reality overruled you. 
> And I'm going to keep this bug open until the same thing happens again for this
> issue.

Why this really should not be discussed in the bug but on the gcc@ mailing list where all over discussions happen?

> 
> You can't just potentially break of the free software in the world because you
> changed your mind about what liberty the C standard gives you.  Grow up or move
> out of the way and let more responsible people handle our infrastructure.

Wait a minute, this optimization has been there since 1994, if new code in the free software world has abused signed overflow like this, they were asking for it.

> 
> You know that the Ariane 5 rocket crashed (and could have killed people!)
> because of an int overflow?  
And I showed you how to find an overflow before it happens and not after so that argument is dead in the water.

> What if people die because you decided the C standard allows you to
> optimize away other people's security checks?

Again I showed you how to check for integer overflows before they happen instead of after.  You can teach other security people how to write that code.

> Again: IT DOES NOT MATTER WHAT THE C STANDARD SAYS.  You broke code, people are
> suffering damage.  Now revert it. 

Revert what was done 13 years ago.  Do you have a time machine, because I sure had hoped so because I wantted to change what happened last year a little bit.

>  The least you can do is make -fwrapv on by
> default.  
It is default on languages which actually define the language that way.

> You would still have to make it actually work (I hear it's broken in
> some corner cases?), but that's another story.

It __WAS__ broken in a corner case but that already was fixed in 4.0.0.


Again there is no reason why this decussion should not be on gcc@ and not here.  I gave the correct way of writting overflow dection and if you don't like what the C standard says, that is not my fault at all.

Remember GCC is also an optimizing compiler, if you want optimizations, you need to follow the language which you are writting in closer instead of playing it loose which is what is happening with both C and C++ in general.
Comment 23 felix-gcc 2007-01-17 18:23:42 UTC
In earlier gcc versions this only happened if the optimizer was on.  So your argument might hold some water there, if I squint my eyes enough.

But gcc 4.1 removes that code even with the optimizer turned off.

There goes your argument.

Please make -fwrapv default again and I'll shut up.
Comment 24 Andrew Pinski 2007-01-17 18:43:10 UTC
Try doing some timings with and without -fwrapv and see what happens for normal code.
You will see that without -fwrapv code runs faster.
Comment 25 felix-gcc 2007-01-17 19:04:06 UTC
Well, duh.  You removed the security checks.

Hey, I have one for you, too.  Optimize away all calls to pthread_mutex_lock, and lo and behold, multithreaded code will be much faster!  It will also be broken, but apparently, that's not much of a concern around here.

The most time critical code I have, I just benchmarked.

  $ gcc -O3 -fomit-frame-pointer -funroll-loops -march=athlon64 -o t t.c misc.c add.c mul.c write.c read.c comba.c
  $ ./t
  adding two bignums: 84 cycles
  multiply two bignums: 1414 cycles
  writing a bignum as radix 10: 207488 cycles
  comba: 1467 cycles
  $ gcc -O3 -fomit-frame-pointer -funroll-loops -march=athlon64 -o t t.c misc.c add.c mul.c write.c read.c comba.c -fwrapv
  adding two bignums: 82 cycles
  multiply two bignums: 1414 cycles
  writing a bignum as radix 10: 202761 cycles
  comba: 1465 cycles
  $

So, uh, where does the optimization part about your "optimization" come in?  This is code that has no integer overflow checks.  So my conjecture is: your "optimization" makes code faster in exactly those cases where it removes security checks from it, endangering people on the way.

So, again, please make -fwrapv the default, and I'll leave you alone.
Comment 26 Andrew Pinski 2007-01-17 19:17:51 UTC
(In reply to comment #25)
> Well, duh.  You removed the security checks.
Which were wrong to begin with,  See the comp.lang.c faq.

> 
> Hey, I have one for you, too.  Optimize away all calls to pthread_mutex_lock,
> and lo and behold, multithreaded code will be much faster!  It will also be
> broken, but apparently, that's not much of a concern around here.

No, because it is not undefined for pthread_mutex_lock unlike this case.
 
> The most time critical code I have, I just benchmarked.
> 
>   $ gcc -O3 -fomit-frame-pointer -funroll-loops -march=athlon64 -o t t.c misc.c
> add.c mul.c write.c read.c comba.c
>   $ ./t
>   adding two bignums: 84 cycles
>   multiply two bignums: 1414 cycles
>   writing a bignum as radix 10: 207488 cycles
>   comba: 1467 cycles
>   $ gcc -O3 -fomit-frame-pointer -funroll-loops -march=athlon64 -o t t.c misc.c
> add.c mul.c write.c read.c comba.c -fwrapv
>   adding two bignums: 82 cycles
>   multiply two bignums: 1414 cycles
>   writing a bignum as radix 10: 202761 cycles
>   comba: 1465 cycles
>   $
> 
> So, uh, where does the optimization part about your "optimization" come in? 

Most of the time it is loops.  Try adding bounds checking to the code and try again.  You will then see the difference,  This is an important optimization for C++ code that has bound checked array accesses, Java code and Fortran code.

> This is code that has no integer overflow checks.

Your specific code has no code which benifits that much.  Try again with some C++ code which uses vector and get.  You will see a huge difference in the code there.

>  So my conjecture is: your
> "optimization" makes code faster in exactly those cases where it removes
> security checks from it, endangering people on the way.

You are missunderstanding, your one piece of code does not benifit so you can just alway turn on -fwrapv if you really depend on signed integer overflow wrapping.  You need to look at the bigger picture:
1) security is important
2) code generation is important

which one is better for the users, all of the above.  Just because the person who wrote the security checks in the code you are looking at got it wrong is no reason to penality the people who actually got it right by using the way decribed in the comp.lang.c faq.  This is my point, you are trying to penality the people who wrote their security checks so it is defined C.
Comment 27 felix-gcc 2007-01-18 15:20:38 UTC
Oh, so C++ code using vector gets faster, you say?  Let's see...

This is vector.C from http://ptrace.fefe.de/vector.C

It does some assignments to a vector.  It runs the loop 10 times and takes the minimum cycle counter.

  $ g++ -O2 -o vector vector.C
  $ ./vector
  20724 cycles
  $ g++ -O2 -o vector vector.C -fwrapv
  $ ./vector
  20724 cycles
  $

And AGAIN you are proven wrong by the facts.  Do you have some more "proof" where this came from?

Man, this is ridiculous.  Just back out that optimization and I'll shut up.
Comment 28 felix-gcc 2007-01-18 15:23:57 UTC
Mhh, so I wondered, how can it be that the code is exactly as fast.  So I disassembled the binary.  You know what?  IT'S THE EXACT SAME CODE.

So, my conjecture is, again: your "optimization" does exactly NO good whatsoever, it just breaks code that tries to defend against integer overflows.

Please remove it.  Now.
Comment 29 Andrew Pinski 2007-01-18 17:36:26 UTC
Oh and I meant "at", not get or [].  at does bounds checking.
Comment 30 Andrew Pinski 2007-01-21 08:58:31 UTC
GCC is not going to change.  There is no reason why you can't either use -fwrapv or change the security checks to be before the overflow happens.  There are now good reasons why -fwrapv is not on by default, if you look at:
int f(int max, int *t)
{
  int i;
  for(i = 0;i<=max;i++)
    {
      if (i<0)  return 1;
      t[i]++;
    }
  return 0;
}

The "if (i<0)" should always be removed as i can never be negative.
Comment 31 andreas 2007-01-21 12:23:12 UTC
And who will go over the existing millions lines of code, and verify the overflow checks everywhere? Or add -fwrapv to all the Makefiles for unaidited code? Obviously not you.  It seems to be easier to pretend you're not responsible for the next security bug in Linux.

I'm still amazed that for the gcc maintainers, performance seems to be more important than security of the existing code base. I'm even more amazed that they seem to be unable to do some benchmarks to show that they have a point, apart from some made-up examples.

Why is Microsoft willing and able to do such changes to Visual Studio, and you are not?
Comment 32 andreas 2007-01-21 12:49:42 UTC
Oh, and besides, proper range analysis could optimize the above code, even in the presence of correct (and I mean LIA-1) overflow behaviour of signed ints.

It seems you still didn't even manage to come up with an example where is optimization matters which is not "eliminate bounds checks during array access".  And the single reason bounds checks are done is to prevent buffer overflow exploits.  So if you optimize that away in a situation where a LIA-1 compliant compiler would not, you're creating a security problem.

I don't see why making make_range in fold-const.c behave in compliance with LIA-1 should be a problem, especially not performance-wise.  It would really make a lot of people sleep better in the night.
Comment 33 felix-gcc 2007-01-21 13:53:35 UTC
so now you give us... a straw man?
The range analysis has nothing to do with just assuming integers can't wrap.

But more to the point: the Intel compiler does not assume signed integers can't wrap, and IT STILL PRODUCES MUCH FASTER CODE THAN GCC.

So all your hand waiving about how this optimization is good for performance is utterly destroyed by the Intel compiler.

And please let me express my shock how you tell me to my face that the only example where this optimization has measurable impact (I didn't actually try it, but I will) is when it optimizes away range checks in C++ vectors.  Which, you know, exist solely because THERE ARE NO RANGE CHECKS IN C ARRAYS and, uh, C++ is much better and people are told to use C++ vectors instead BECAUSE THEY HAVE RANGE CHECKS and now you tell me that your optimization removes those.  Whoa, what an improvement, man.  Now you convinced me.  Not that the optimization is useful, mind you, but that you are a marauding saboteur sent by the evil minions at Microsoft on a mission to make open source software look bad.
Comment 34 Andrew Pinski 2007-01-21 16:31:00 UTC
> The range analysis has nothing to do with just assuming integers can't wrap.

Partly wrong, range analysis is helped by the fact assuming integers can't wrap.  If range analysis dependent on pointer overflow being undefined, would you complain then, I bet you would.

Intel's compiler assumes integer overflow is undefined but if you think it does not, then fine, most if not all commerial compilers assume that.  Unlike them, we give you an option to assume otherwise.

>I don't see why making make_range in fold-const.c 

It is already if you use -fwrapv.

The problem here is that the people who added these security checks in the first place did not know C.  So either GCC can be changed or these programs can be fixed by the way comp.lang.c faq recommends or by using -fwrapv.  If we change GCC, you punish the people who actually write defined C so that is out of the question.  

I think the real issue that some of the security folks want to check after the fact that something happened instead of before it happend which is the correct way to do anything.
Comment 35 andreas 2007-01-21 17:29:50 UTC
(In reply to comment #34)
> > The range analysis has nothing to do with just assuming integers can't wrap.
> Partly wrong, range analysis is helped by the fact assuming integers can't
> wrap.

And in those cases then leads to code that does unexpected things, such as breaking existing security checks.

> >I don't see why making make_range in fold-const.c 
> It is already if you use -fwrapv.

No, it is not.  What happens is that make_range will generate invalid ranges in any case, and then optimizations depending on those ranges will be skipped when -fwrapv is specified.  (Please correct me if I'm reading the code wrong, even though I'm maintaining an open source compiler myself, I don't have much experience reading gcc code.)

What this means is that in the example you posted above, even though the compiler *could* compute a correct range and properly fold the if statement even given LIA-1 compliant overflow behaviour, gcc will skip the optimization when passed -fwrapv.

After reading the code, I can certainly see why making -fwrapv is something you'd rather avoid: it makes a lot of optimizations go down the drain. But: this wouldn't have to happen if you fixed make_range to do something sensible instead.  I wonder why this didn't jump right into the face of the person who implemented -fwrapv, it must have been a real pain to track down all the usages.

> The problem here is that the people who added these security checks in the
> first place did not know C.  So either GCC can be changed or these programs can
> be fixed by the way comp.lang.c faq recommends or by using -fwrapv.  If we
> change GCC, you punish the people who actually write defined C so that is out
> of the question.  

Well, maybe they didn't.  I did a non-representative survey with the C programmers I know: everybody assumed overflow of signed ints would behave as it does for the underlying machine representation.  Not a single one was aware of the danger.  And we're talking of people with 20+ years of professional experience in the field here.

And I think people who do know can be expected to read the gcc manual to figure out that there were a -fnowrapv option to make their code go a wee bit faster.

Did I mention that I have yet to see a convincing example of a case where undefinedness of signed overflow actually makes code go faster that isn't per definition a security problem?  Especially after having learned from reading the gcc code that -fwrapv turns off a whole lot more optimizations than it has to?

> I think the real issue that some of the security folks want to check after the
> fact that something happened instead of before it happend which is the correct
> way to do anything.

No, I would call any security expert who refuses to learn that there is a problem with signed overflow and how to check for that correctly an idiot.  The issue here is really how to deal with the existing body of code out there that was written in the implicit assumption of LIA-1 compliant behaviour.

This is about risk management for all the Linux systems out there.  It is not about "whose fault is it".  It's about "Houston, we have a problem, and need it fixed".
Comment 36 felix-gcc 2007-01-21 17:47:35 UTC
I think the actual root issue here is that the gcc argumentation is fundamentally wrong.  I am complaining that gcc removes my checks, not that signed integer overflow is undefined.

Also, note that it is everything BUT undefined.  Adding 5 to INT_MAX will create a negative number.  It behaves EXACTLY as expected by basically everyone.  And if gcc decided that it is undefined and it creates INT_MAX again, then I would be happy, too.  No problem with that whatsoever.

All I want is gcc to be consistent.  gcc DOES create a negative number.  And then it removes an if statement asking whether the number is negative.  That can not be explained away with signed int overflow being undefined.  Let's write it in separate statements, so even the biggest idiot in the world can understand the issue.

  int a,b,c;
  a=INT_MAX;     /* statement ONE */
  b=a+2;         /* statement TWO */
  c=(b>a);       /* statement THREE */

My issue with gcc is that it removes statement THREE.  Your argument about undefinedness is about statement TWO.  Following your argumentation, gcc is allowed to return 23 in statement TWO.  But it still not allowed to generate no code for statement THREE.

In my opinion, people who don't understand this most basic of logic should not be let NEAR the code of a compiler, let alone a compiler millions of people are depending on.

Now, to summarize.  We destroyed your complete argument, including wild assertions you happened to make during its course.  We gave evidence that the current behavior is bad for a lot of people.  What more do you need to see reason?  Do you want a bribe?  Some more crack?  Hookers, maybe?  I don't see what else could be discussed about the matter.  I will refrain from wasting time on trying to find new way to explain the obvious to you.  From now on, I'll just auto-reopen the bug and say "see previous arguments".
Comment 37 Pawel Sikora 2007-01-21 18:16:42 UTC
(In reply to comment #36)

> Now, to summarize.

you're leading to undefined behaviour - do you understand this simple fact?
in such cases compiler can do *anything* with your code.

> current behavior is bad for a lot of people.

it's the highest time to read the standard
and use unsigned types or -fwrapv.

> I'll just auto-reopen the bug and say "see previous arguments".

you're violating standard, so stop screaming.
Comment 38 Richard Biener 2007-01-21 19:46:22 UTC
(in reply to comment #35)

It is true that in the face of -fwrapv gcc does not optimize as good as it does
for unsigned numbers (that wrap, too).  I am in the progress of fixing that
for the value range propagation pass.  You are of course welcome to fix it
for make_range ;)  (or maybe file an enhancement bug report for that, so we
don't lose track of that issue)
Comment 39 Andrew Pinski 2007-01-21 20:14:13 UTC
No reason to keep this open as you are violating the C standard.
Comment 40 Tom Tromey 2007-01-21 21:52:34 UTC
I've read through the comments in this PR.

I thought it would be useful to point out that a decision on how
GCC will optimize in the absence of -fwrapv will not be decided
by this PR.  This change has been extensively discussed on the GCC
list, and, really, that is the appropriate forum for this.  So, even
if this PR is constantly reopened, it won't be resolved via this route.

If you do intend to bring this up again on the GCC list, please read
the previous discussion before posting.  Thanks.
Comment 41 felix-gcc 2007-01-22 02:18:01 UTC
So I tested some C++ vector code using at, in a desperate attempt to find ANY case where this so called "optimization" actually produces faster code.

http://ptrace.fefe.de/vector2.C

  $ gcc -O3 -o vector2 vector2.C
  $ ./vector2
  69859 cycles
  $ gcc -O3 -o vector2 vector2.C -fwrapv
  $ ./vector2
  69606 cycles
  $

so, not only is the different negligible, it also turns out that the optimization made the code SLOWER.  Now, let's see what the Intel compiler does (I'm using 9.1.042):

  $ icc64 -O3 -o vector2 vector2.C
  $ ./vector2
  50063 cycles
  $

So, all this fuss you are making is about an optimization that actually makes code slower, and the competition does not need foul language lawyer games like this to still beat you by 28%.  28%!

You should be ashamed of yourself.

Why don't you get over the fact that this was a really bad decision, undo it, and we will all live happily ever after.

Oh, and: If it really does not matter whether I keep reopening this bug, why do you keep closing it?  I will keep this bug open, so the world can see how you broke gcc and are unable to let even facts as clear as these convince you to see the error of your ways.
Comment 42 Andrew Pinski 2007-01-22 02:27:23 UTC
(In reply to comment #41)
> So I tested some C++ vector code using at, in a desperate attempt to find ANY
> case where this so called "optimization" actually produces faster code.

Try looking at real code instead of benchmarks :).  I bet the reason why ICC beats GCC is not because GCC cannot do a good job but ICC's standard template library is implemented slightly different.


>  $ gcc -O3 -o vector2 vector2.C
>  $ ./vector2
>  69859 cycles
>  $ gcc -O3 -o vector2 vector2.C -fwrapv
>  $ ./vector2
>  69606 cycles

I bet this is all to do with cache and not really anything do with the optimization.

>Why don't you get over the fact that this was a really bad decision,
> undo it, and we will all live happily ever after.

Only a few people think it is a bad decision.  Anyways nothing said in this bug will change anything, you should do what Tom Tromey  said in comment #40 and what I mentioned in comment #22, and write to the gcc@gcc.gnu.org mailing list after reading all previous decussion on this matter.  Since it sounds like you only care about the security code which was incorrectly written.
Comment 43 felix-gcc 2007-01-22 13:02:30 UTC
No, it WAS about the security.  Now that you made me check and I saw that the optimization also doesn't give any actual speed increase, I want it removed on that grounds, too.  And I want it removed for reasons of sanity.  The compiler must never give me a negative value but then not take the "if (a<0)" branch.  That is utterly unacceptable.
Comment 44 Andrew Pinski 2007-01-22 17:14:49 UTC
Again this really has nothing to do with security except for the fact some developers wrote security checking code that depends on overflow being defined as wrapping which is not what the C standard says and what GCC decided a while back (1992 or so) to be undefined.  So in reality you have not proved why people can't audit their code like they did in the first place to place the undefined code in there.
Comment 45 Steven Bosscher 2007-01-22 18:26:35 UTC
Marking this as WONTFIX leaves the impression that here is a bug here at all.  This should have been closed as INVALID.

First commandment of using C: "Thou shall not rely on undefined behavior."
Comment 46 Andrew Pinski 2007-01-22 18:33:24 UTC
> PS: Mr Simon, that link to a how-to that says "btw this doesn't work for this
> special input", is that supposed to impress anyone?  It certainly does not
> impress me very much, really.

yes and the special input is one value which is easy to add a check for
input == INT_MIN.
The reason why INT_MIN is "special" is because signed integer in C does not have to be symetric.  Now if you take Fortran on the other hand, integers are always symetric.
Comment 47 andreas 2007-01-22 18:36:41 UTC
It was suggested to me that this issue should be discussed on the mailing list. If you have an opinion, come there.
Comment 48 felix-gcc 2007-01-22 19:50:23 UTC
Oh wow, another wise cracking newbie who comments without actually understanding the issue.  I AM NOT RELYING ON UNDEFINED BEHAVIOR.  On the contrary.  gcc is fine to assign 23 instead of a negative number.  But if it does assign a negative number (as it does), I want "if (a<0)" to trigger.  That part is not undefined.

But never mind the security issue here, which is apparently too complicated for you guys to understand.  This optimization actually makes code SLOWER.  AND it makes people mad when they find out about it.

So, uh, which part of that don't you understand?

There is an optimization that makes the code slower, not faster.  Turn it off already.
Comment 49 Ian Lance Taylor 2007-01-22 20:16:29 UTC
In the C language standard "undefined behaviour" meants that the compiler can do anything at all.  It means that the program is specifically undefined.

When you say that the compiler should not eliminate the test because the value does turn out to be negative, you appear to be assuming that signed overflow is actually "implementation defined behaviour."  That would have the property that you are after.

When you say that -fwrapv makes the code faster, I don't know which benchmarks you are relying on.  Other people have demonstrated that -fwrapv slows down the well-known SPEC benchmark.

I've written some comments in the appropriate place: the gcc mailing list:
http://gcc.gnu.org/ml/gcc/2007-01/msg00885.html
Comment 50 Andrew Pinski 2007-01-22 22:27:47 UTC
There is no nothing special about signed integer overflow in C, it is just undefined behavior at runtime.  I had forgot to mention the SPEC results because I don't feel SPEC CPU or any benchmark is a good way to measure your own code.  And with -fwrapv being default, you punish people who write valid and well defined C programs which causes those people to get up set and we already get more of those complaints than getting complaints about signed integer being undefined in C.  If you really want to make a difference, raise an issue with the C standards committee (just a word of cation, they might laugh at you and tell you to go away) with a very very good reason to make signed integer overflow as implementation defined; plain out security checks is not a good reason as you can check for the issues before they can happen as already mentioned.

I would agree with your idea of turning on -fwrapv if there was no way to check for overflow before they happened but there are ways.  Yes we are going to break  code which was written using the assumtion that signed integer overflow is defined as wrapping but that is a cost which we can take, I think.  
Comment 51 andreas 2007-01-22 23:10:25 UTC
Sure, new security checks can be written in a compliant manner.

But what plan do you suggest to find instances of non-compliant overflow checking in the existing body?  Think something like a whole Linux distribution. Something in the order of 15000 packages. Dozens of millions of lines of code. Any suggestion?
Comment 52 kargl 2007-01-23 00:45:51 UTC
(In reply to comment #51)
> Sure, new security checks can be written in a compliant manner.
> 
> But what plan do you suggest to find instances of non-compliant overflow
> checking in the existing body?  Think something like a whole Linux
> distribution. Something in the order of 15000 packages. Dozens of millions of
> lines of code. Any suggestion?
> 

How about http://scan.coverity.com/
Comment 53 Johannes Stezenbach 2007-03-08 01:03:23 UTC
I read all this and the mailing list thread with great interest,
however I think there is a fundamental flaw in the reasoning:

C90 6.2.1.2 / C99 6.3.1.3 defines signed integer overflow
as "implementation-defined behaviour", which is something completely
different than "undefined behaviour".
See C90 3.11 vs. 3.18 / C99 3.4.1 vs. 3.4.3.
(3.4.1 implementation-defined behavior: "unspecified behavior where each
implementation documents how the choice is made").

And lo and behold:
http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Integers-implementation.html
http://gcc.gnu.org/onlinedocs/gcc-4.0.4/gcc/Integers-implementation.html

"For conversion to a type of width N, the value is reduced modulo 2^N to be within range of the type; no signal is raised."

(Older versions of gcc left this undocumented.)

Of course, software which relies on that is non-portable, but that's
different from being "invalid C". If it turns out that many major
C compilers use a similar implementation (which is what I expect
but have no proof of), then it would be wise if gcc would do the
same.

E.g. Sun C uses this definitions:
http://docs.sun.com/source/819-3688/c90.implementation.app.html#pgfId-998756
"When an integer is converted to a shorter signed integer, the low order bits are copied from the longer integer to the shorter signed integer. The result may be negative."

Anyway, gcc should behave as documented, which isn't the case at least
for gcc (GCC) 4.1.2 20061115 (prerelease) (Debian 4.1.1-21).
Comment 54 Andrew Pinski 2007-03-08 01:14:37 UTC
(In reply to comment #53)
> I read all this and the mailing list thread with great interest,
> however I think there is a fundamental flaw in the reasoning:
> 
> C90 6.2.1.2 / C99 6.3.1.3 defines signed integer overflow
> as "implementation-defined behaviour", which is something completely
> different than "undefined behaviour".

Those sections are not about singed integer overflow but conversion between the types which is implementation defined as you shown.

If you look at what is being descibed here is conversion between types but overflow.
Comment 55 Johannes Stezenbach 2007-03-08 16:22:43 UTC
Point taken. I was misled by the mentioning of C99 6.3.1.3
in comment #18, that this would apply to integer conversion.

Funnily enough, C99 3.4.3 even says "An example of undefined
behavior is the behavior on integer overflow."
I should've read that one more thoroughly.

C99 Annex H (Informative) says:
"C’s unsigned integer types are ‘‘modulo’’ in the LIA&#8722;1 sense
in that overflows or out-of-bounds results silently wrap. An
implementation that defines signed integer types as also being
modulo need not detect integer overflow, in which case, only
integer divide-by-zero need be detected."

Which suggests that implmentations define signed integer
overflow semantics, but maybe it's just bad wording, and
anyway it's not part of the standard proper.

Sorry for the noise and thanks for the C lesson.
Comment 56 Jackie Rosen 2014-02-16 10:00:25 UTC Comment hidden (spam)
Comment 57 Marian 2019-01-10 13:58:25 UTC
Sorry for posting to this ancient bugreport.

Is there a way to get a warning when code get optimized out based on undefined behavior?

I bet that at least 90% of the C developers out there would be completely surprised that signed integer overflow is actually undefined behavior. And at least 99% of the C developers out there would not spot the bug in http://ptrace.fefe.de/int.c spending significant time and energy. So being able to get a warning for that would be highly appreciated tool to help finding and fixing those bugs.

Kind regards,
Marian

PS: Please also consider to enable this warning with `-Wall -Wextra -pedantic`. I bet that 99% of the cases the compiler can optimize code out because of this undefined behavior the code has a bug in some bound checks.
Comment 58 Andreas Schwab 2019-01-10 14:11:49 UTC
-Wstrict-overflow=1 is enabled by -Wall.
Comment 59 Marian 2019-01-10 15:46:32 UTC
Thanks for the fast replay

    wget http://ptrace.fefe.de/int.c
    gcc -Wstrict-overflow=1 -Wall -Wextra -pedantic -o int int.c

does not produce a warning (except for the missing `#include <stdio.h>`) on gcc 8.2.0 on Alpine Linux for me, nor on GCC 8.2.1 20181127 an Arch Linux.
Comment 60 Harald van Dijk 2019-01-10 23:36:13 UTC
(In reply to Marian from comment #59)
> Thanks for the fast replay
> 
>     wget http://ptrace.fefe.de/int.c
>     gcc -Wstrict-overflow=1 -Wall -Wextra -pedantic -o int int.c
> 
> does not produce a warning (except for the missing `#include <stdio.h>`) on
> gcc 8.2.0 on Alpine Linux for me, nor on GCC 8.2.1 20181127 an Arch Linux.

It warned at -O2 -Wall with GCC 4.2 to 7 (-O2 enabling -fstrict-overflow), but stopped warning in GCC 8. Warnings no longer being emitted in cases where they are desired is part of bug 80511.

The GCC 8 Changes page[*] says -Wstrict-overflow is deprecated (even if it is supposed to still work) and recommends to use -fsanitize=signed-integer-overflow to get a run-time warning, which does catch this.

[*] https://gcc.gnu.org/gcc-8/changes.html
Comment 61 Marian 2019-01-14 12:07:26 UTC
Thanks for your reply

> The GCC 8 Changes page[*] says -Wstrict-overflow is deprecated (even if it is supposed to still work) and recommends to use -fsanitize=signed-integer-overflow to get a run-time warning, which does catch this.

I think using run-time warnings will miss a lot of bugs, compared to compile time warnings. I assume that in production builds that the run-time warnings will be disabled for performance reasons. I also assume that singed integer overflows will not "normally" happen, e.g. only when an adversary is abusing the bug in the integer overflow detection. So unless unit tests are explicitly checking if the signed integer overflow detection code does work properly, the run-time checks will never trigger.

Even when production builds would have run time warnings enabled, those warnings would not stop an adversary in exploiting the integer overflow detection.

I would greatly appreciate if the GCC developer could reconsider depreciating -Wstrict-overflow.

Kind regards,
Marian
Comment 62 Daniel Marjamäki 2021-01-05 12:26:18 UTC
> I think using run-time warnings will miss a lot of bugs, compared to compile time warnings.

I fully agree. This current situation is just dangerous.

In my humble opinion, the optimisations should be disabled until proper warnings are written.

It is no silver bullet but to give a little confidence in your code you can currently use Cppcheck. Cppcheck writes a warning with id invalidTestForOverflow for `int + 100 > int`.
Comment 63 Daniel Marjamäki 2021-01-05 12:56:52 UTC
Sorry. I should have mentioned I am a Cppcheck developer in my comment.
Comment 64 Jakub Jelinek 2021-01-05 13:30:33 UTC
The X + 100 > X case is optimized with:
/* X + Y < Y is the same as X < 0 when there is no overflow.  */
(for op (lt le gt ge)
 (simplify
  (op:c (plus:c@2 @0 @1) @1)
  (if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (@0))
       && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))
       && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0))
       && (CONSTANT_CLASS_P (@0) || single_use (@2)))
   (op @0 { build_zero_cst (TREE_TYPE (@0)); }))))
So, if we wanted to maintain -Wstrict-overflow=*, we'd need to add it to this spot and to other 40+ or so other spots that check for TYPE_OVERFLOW_UNDEFINED.
In this particular case, it would need to differentiate between whether @0 is a constant (then it should warn at WARN_STRICT_OVERFLOW_ALL level), or not,
then it should warn at WARN_STRICT_OVERFLOW_COMPARISON level).
Though, -fsanitize=undefined really is the preferred way how to check code,
warnings will necessarily have lots of false positives, while the X + 100 > X
case when written that way is easy to avoid, if it is e.g. after inlining it might not be that easy and there can be much more complex cases.
Comment 65 Jakub Jelinek 2021-01-05 13:37:36 UTC
And the warning went away in r8-3771-g6358a676c3eb4c6df013ce8319bcf429cd14232b
Comment 66 Daniel Marjamäki 2021-01-06 10:37:59 UTC
Thanks! I can appreciate that it's not very simple. Well using a flag is totally acceptable. I don't trust the sanitizer completely but those that do can use the optimisation.