1

I'm trying to check if signed addition would overflow. Generally, to check if

int a + int b

would overflow (a and b both positive), I check if

if (a > INT_MAX - b)

But now I want to check if 

int a + int b - int c

would overflow. I know that a, b, and c are positive and that b >= c, so I do the following check:

if (a > INT_MAX - b + c)

Now my question is, can compiler rewrite 

INT_MAX - b + c     to     INT_MAX + c - b   ?

My concern is, then it will first do INT_MAX + c, which may overflow and can result into undefined behavior.

Zhani Baramidze
  • 1,407
  • 1
  • 13
  • 32

3 Answers3

8

It is a fallacy to think about what "the compiler" does when reasoning about undefined behaviour. The compiler is transparent. The behaviour is in your code, not in the compiler. You should ask "what does my code INT_MAX - b + c mean? Can it overflow? The answer is never in "the compiler", but in the standard.

The standard only requires that individual operations that appear in your program do not overflow. It never says anything about any rewritten expressions that do not explicitly appear in your program. INT_MAX - b + c is in your program, and is equivalent to (INT_MAX - b) + c. So the requirement is that (INT_MAX - b) doesn't overflow, and then the result added to c doesn't overflow. INT_MAX + c - b does not appear in your program, so you should not be concerned about it.

If the compiler rewrites your expression in any way, it must make sure that the rewritten expression has the same visible behaviour as yours, per the as-if rule. So if it does replace INT_MAX - b + c with INT_MAX + c - b, it must make sure the overflow either doesn't happen or is dealt with transparently (e.g. ignored by the hardware).

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
  • 4
    @Ivan 1) this is a C question, so C++ is irrelevant 2) when C++ specifies two's complement, signed overflow will still be undefined. The same code will still be produced for this function. https://godbolt.org/z/CAE_XU – Pascal Cuoq Sep 09 '18 at 10:39
  • @PascalCuoq C++ _is_ relevant. Because when C and C++ differ in their requirements, compilers usually choose C++ behavior over C one and apply it to C code as well. –  Sep 09 '18 at 10:41
  • 1
    @Ivan where are you getting this? One particular software house might be less interested in producing a compliant C compiler that others. Don't use their C compiler then. – n. m. could be an AI Sep 09 '18 at 10:45
  • @Ivan This is not the place for debates, but I work closely with compiler implementers and predicting with certainty what the code compilers produce will do is the literal definition of my job, and I think you misunderstand what “specifying two's complement” implies. – Pascal Cuoq Sep 09 '18 at 10:45
  • @n.m. Major compilers like Clang, ICC and MSVC. None of those uses C loop termination conditions, all apply C++ rules to C code instead. –  Sep 09 '18 at 10:46
  • 1
    @Ivan An excellent selection of compilers! All these compilers apply optimizations that rely on signed overflow being undefined, and they are not going to stop when C++20 is published. – Pascal Cuoq Sep 09 '18 at 10:48
  • @PascalCuoq I never said they would. My point was that standard is irrelevent - there are simply to many places when compilers behavior extends or violates the standard. So I consider "standard" answers not very helpful. Standard is not useful enough to be helpful. –  Sep 09 '18 at 10:49
  • @Ivan can you show non-compliant behaviour in any of the C compilers you mentioned? – n. m. could be an AI Sep 09 '18 at 10:51
  • 4
    @Ivan One compiler that don't apply C standard to compile C code is not a C compiler, end. – Stargateur Sep 09 '18 at 10:52
  • @n.m. I already mentioned it in my previous comments. Compilers apply loop termination rules from C++ to C code. C's 6.5.2.3 rule is not used by any compiler known to me. –  Sep 09 '18 at 10:52
  • @Stargateur I don't know of any compiler that follows the standard, end. When papers and reality meet, reality wins. Always. –  Sep 09 '18 at 10:52
  • 1
    I know you *mentioned* it. I'm asking you to *show* it. – n. m. could be an AI Sep 09 '18 at 11:14
4

The expression a - b + c is equivalent to (a - b) + c. This is encoded in the grammar for the language, the most relevant clause here being 6.5.6:1 (but of course you have to look at the whole grammar to make sense of this clause).

      additive-expression:
             multiplicative-expression
             additive-expression + multiplicative-expression
             additive-expression - multiplicative-expression

When faced with a - b + c, the compiler can only parse it as the sum of the additive-expression a - b and of the multiplicative-expression c. There is no other rule that can apply. So a - b + c is the sum of a - b, whatever that is, and of c.

The compiler is free to generate the assembly code it deems most appropriate for the source code you provided, but it has to preserve the meaning of the program. If you wrote source code that was defined for a = INT_MAX, b = 2 and c = 1, then the assembly code has to provide the correct answer for these values. If the compiler chooses to reorder operations, it will only do so in a way that preserves the meaning, for instance because it knows that assembly instructions for the target architecture produce two's complement results and can be re-ordered to arrive to the same result.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
-4

Well, we can assume not.

But "The C language standard doesn't specify operator precedence."

But I would add in brackets because even if there is a slight chance priority will mess up.

A quote from https://stackoverflow.com/a/2722316/3268169:

"compilers are built by smart people and do smart things" and thus, can never go wrong.

is making a foolish argument.

Readability should be enchanced as well if that is a issue.

YukiNyaa
  • 136
  • 1
  • 13
  • `-` and `+` have the same preceedence. – too honest for this site Sep 09 '18 at 10:17
  • @toohonestforthissite Yes, I was making a vague point, sorry for that, I should have done more research to support this point. – YukiNyaa Sep 09 '18 at 10:19
  • This answer seems to advocate adding extra safeguards in case there's a bug in the compiler. That is, frankly, ridiculous – if the compiler messes up something as basic as operator precedence it'll produce something completely broken anyway. And if it's possible to have a bug in operator precedence then it's just as likely that there might be a bug in handling brackets so you don't really accomplish anything by adding them. – JJJ Sep 09 '18 at 15:13