107

Adding two 32-bit integers can result an integer overflow:

uint64_t u64_z = u32_x + u32_y;

This overflow can be avoided if one of the 32-bit integers is first casted or added to a 64-bit integer.

uint64_t u64_z = u32_x + u64_a + u32_y;

However, if the compiler decides to reorder the addition:

uint64_t u64_z = u32_x + u32_y + u64_a;

the integer overflow might still happen.

Are compilers allowed to do such a reordering or can we trust them to notice the result inconsistency and keep the expression order as is?

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Tal
  • 1,759
  • 1
  • 12
  • 22
  • 1
    As far as I understand, since addition is left-associative the reordering in your example is not allowed. – August Karlstrom Jul 25 '16 at 09:13
  • 15
    You don't actually show integer overflow because you appear to be added `uint32_t` values - which don't overflow, they wrap. These are not different behaviours. – Martin Bonner supports Monica Jul 25 '16 at 09:13
  • 5
    See the section 1.9 of the c++ standards, it directly answers your question (there is even an example that is almost exactly the same as yours). – Holt Jul 25 '16 at 09:18
  • As @MartinBonner says, your examples don't show anything. Addition of unsigned values is done modulo, so such operations don't overflow (they wrap) are even commutative. There will be no difference what so ever if you reorder them, cast to `uint64_t` or things like that. – Jens Gustedt Jul 25 '16 at 09:50
  • 1
    @rustyx, In your example if C is a 64-bit integer, A+(B+C) will not overflow. while (A+B)+C could overflow. – Tal Jul 25 '16 at 10:12
  • @Holt, the standard example is not mixing integers with different type size. I do agree the standard suggest reordering is OK as long as the result is consistent, I just wanted to assure compilers recognize possible integer overflow as an inconsistent result. – Tal Jul 25 '16 at 10:20
  • 3
    @Tal: As others already stated: there is no overflow of integers. Unsigned are defined to wrap, for signed it is undefined behaviour, so any implementation will do, including nasal daemons. – too honest for this site Jul 25 '16 at 10:22
  • @Olaf, If I replace 'overflow' with 'wrap', someone else will tell us it might saturate - not wrap. – Tal Jul 25 '16 at 11:05
  • 5
    @Tal: Nonsense! As I already wrote: the standard is very clear and requires wrapping, not saturating (that would be possible with signed, as that is UB as-of the standard. – too honest for this site Jul 25 '16 at 11:09
  • 1
    @Olaf, I've checked the standard, you are correct, wrapping is the correct wording to my question. Feel free to edit and correct the question. – Tal Jul 25 '16 at 11:30
  • 15
    @rustyx: Whether you *call* it wrapping or overflowing, the point remains that `((uint32_t)-1 + (uint32_t)1) + (uint64_t)0` results in `0`, whereas `(uint32_t)-1 + ((uint32_t)1 + (uint64_t)0)` results in `0x100000000`, and these two values are not equal. So it's significant whether or not the compiler can apply that transformation. But yeah, the standard only uses the word "overflow" for signed integers, not unsigned. – Steve Jessop Jul 25 '16 at 11:30
  • 2
    @Tal: signed integers can overflow. If they do so you have undefined behaviour, and it is the programmers responsibility to avoid it. In practise, chips tend to wrap, or saturate, or raise a signal. Compilers also use the fact that operations may not overflow to deduce something about the values involved. *Unsigned* integers will always wrap (or you are not using a C or C++ compiler). – Martin Bonner supports Monica Jul 25 '16 at 11:32
  • @Martin, Wikipedia suggest there were actual saturation-arithmetic C/C++ implementation, but I guess they do not confront to the standard. – Tal Jul 25 '16 at 11:34
  • 2
    Yes they did. It is open to a compiler to extend the standard by (for example) defining the behaviour when integer arithmetic overflows. – Martin Bonner supports Monica Jul 25 '16 at 11:36
  • 1
    @Tal: if you'd like a remark on the particular passage in WIkipedia that you're looking at then say exactly where it is or quote it. But there's no such thing as a C or C++ implementation in which *unsigned* arithmetic saturates. If it does that then it's not C and neither is it C++. Like there's no such thing as a 4-pointed "non-standard triangle". It's just not a triangle. Saturating *signed* arithmetic, sure. – Steve Jessop Jul 25 '16 at 11:36
  • 2
    Since when is wraparound not a form of overflow? – Joren Jul 25 '16 at 11:48
  • 3
    @Joren: in the context of C and C++, ever since the standard chose to use "overflow" as a jargon term with a more specific application. So, since 1989 not all wraparound is overflow ;-) In the context of signed arithmetic in C or C++, and in the context of the English language, sure, wraparound is one kind of overflow behaviour. – Steve Jessop Jul 25 '16 at 11:49
  • 1
    @SteveJessop: Interesting. What, then, does overflow mean in C++? – Joren Jul 25 '16 at 11:52
  • 3
    @Joren: it means the thing that happens when the mathematically-accurate result of a signed arithmetic (or floating-point IIRC) operation exceeds the limits of the type. It's basically a quirk of the standard, that it uses "overflow" to mean "danger, bad stuff!". It therefore doesn't apply it to unsigned arithmetic since that has a well-defined result within the limit of the type. – Steve Jessop Jul 25 '16 at 11:53
  • Parentheses are your friend... – Bob Jarvis - Слава Україні Jul 25 '16 at 16:38
  • @MartinBonner: Not only is it possible for compilers to define integer behaviors in case of overflow, but if the authors of the C89 rationale are to be believed, the decision to have short unsigned types promote to signed int was predicated at least in part on the fact that the majority of "current" C compilers did so in at least some cases [and the authors of the Standard likely intended that future C compilers for two's-complement hardware would continue to do likewise]. – supercat Jul 25 '16 at 20:58

6 Answers6

84

If the optimiser does such a reordering it is still bound to the C specification, so such a reordering would become:

uint64_t u64_z = (uint64_t)u32_x + (uint64_t)u32_y + u64_a;

Rationale:

We start with

uint64_t u64_z = u32_x + u64_a + u32_y;

Addition is performed left-to-right.

The integer promotion rules state that in the first addition in the original expression, u32_x be promoted to uint64_t. In the second addition, u32_y will also be promoted to uint64_t.

So, in order to be compliant with the C specification, any optimiser must promote u32_x and u32_y to 64 bit unsigned values. This is equivalent to adding a cast. (The actual optimising is not done at the C level, but I use C notation because that is a notation that we understand.)

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Klas Lindbäck
  • 33,105
  • 5
  • 57
  • 82
29

A compiler is only allowed to re-order under the as if rule. That is, if the reordering will always give the same result as the specified ordering, then it is allowed. Otherwise (as in your example), not.

For example, given the following expression

i32big1 - i32big2 + i32small

which has been carefully constructed to subtract the two values which are known to be large but similar, and only then add the other small value (thus avoiding any overflow), the compiler may choose to reorder into:

(i32small - i32big2) + i32big1

and rely on the fact that the target platform is using two-complement arithmetic with wrap-round to prevent problems. (Such a reordering might be sensible if the compiler is pressed for registers, and happens to have i32small in a register already).

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Martin Bonner supports Monica
  • 28,528
  • 3
  • 51
  • 88
  • OP's example uses unsigned types. `i32big1 - i32big2 + i32small` implies signed types. Additional concerns come into play. – chux - Reinstate Monica Jul 25 '16 at 13:10
  • @chux Absolutely. The point I was trying to make is that although I could not write `(i32small-i32big2) + i32big1`, (because it might cause UB), the compiler can rearrange it to effectively that because the compiler can be confident that the behaviour will be correct. – Martin Bonner supports Monica Jul 25 '16 at 13:13
  • 3
    @chux: Additional concerns like UB do not come into play, because we're talking about a compiler reordering under the as-if rule. A particular compiler may take advantage of knowing its own overflow behavior. – MSalters Jul 26 '16 at 07:15
16

There is the "as if" rule in C, C++, and Objective-C: The compiler may do whatever it likes as long as no conforming program can tell the difference.

In these languages, a + b + c is defined to be the same as (a + b) + c. If you can tell the difference between this and for example a + (b + c) then the compiler cannot change the order. If you can't tell the difference, then the compiler is free to change the order, but that's fine, because you can't tell the difference.

In your example, with b = 64 bit, a and c 32 bit, the compiler would be allowed to evaluate (b + a) + c or even (b + c) + a, because you couldn't tell the difference, but not (a + c) + b because you can tell the difference.

In other words, the compiler isn't allowed to do anything that makes your code behave different from what it should. It is not required to produce the code that you think it would produce, or that you think it should produce, but the code will give you exactly the results it should.

gnasher729
  • 51,477
  • 5
  • 75
  • 98
  • But with a big caveat; the compiler is free to assume no undefined behaviour (in this case overflow). This is similar to how an overflow check `if (a + 1 < a)` can be optimized out. – csiz Jul 25 '16 at 12:57
  • 7
    @csiz ...on _signed_ variables. Unsigned variables have well-defined overflow semantics (wrap-around). – Gavin S. Yancey Jul 25 '16 at 14:27
7

Quoting from the standards:

[ Note: Operators can be regrouped according to the usual mathematical rules only where the operators really are associative or commutative.7 For example, in the following fragment int a, b;

/∗ ... ∗/
a = a + 32760 + b + 5;

the expression statement behaves exactly the same as

a = (((a + 32760) + b) + 5);

due to the associativity and precedence of these operators. Thus, the result of the sum (a + 32760) is next added to b, and that result is then added to 5 which results in the value assigned to a. On a machine in which overflows produce an exception and in which the range of values representable by an int is [-32768,+32767], the implementation cannot rewrite this expression as

a = ((a + b) + 32765);

since if the values for a and b were, respectively, -32754 and -15, the sum a + b would produce an exception while the original expression would not; nor can the expression be rewritten either as

a = ((a + 32765) + b);

or

a = (a + (b + 32765));

since the values for a and b might have been, respectively, 4 and -8 or -17 and 12. However on a machine in which overflows do not produce an exception and in which the results of overflows are reversible, the above expression statement can be rewritten by the implementation in any of the above ways because the same result will occur. — end note ]

Rahul Tripathi
  • 168,305
  • 31
  • 280
  • 331
4

Are compilers allowed to do such a reordering or can we trust them to notice the result inconsistency and keep the expression order as is?

The compiler can reorder only if it gives the same result - here, as you observed, it doesn't.

It's possible to write a function template, if you want one, which promotes all arguments to std::common_type before adding - this would be safe, and not rely on either argument order or manual casting, but it's pretty clunky.

Useless
  • 64,155
  • 6
  • 88
  • 132
  • I know explicit casting should be used, but I wish to know the compilers behavior when such casting was mistakenly omitted. – Tal Jul 25 '16 at 09:26
  • 1
    As I said, without explicit casting: the left addition is performed first, without integral promotion, and therefore subject to wrapping. The _result_ of that addition, possibly wrapped, is _then_ promoted to `uint64_t` for addition to the right-most value. – Useless Jul 25 '16 at 10:30
  • Your explanation about the as-if rule is totally wrong. The C language for example specifies what operations should happen on an abstract machine. The "as-if" rule allows it to do absolutely whatever it wants as long as nobody can tell the difference. – gnasher729 Jul 25 '16 at 11:07
  • Which means the compiler can do whatever it wants so long as the result is the same as that determined by the left-associativity and arithmetic conversion rules shown. – Useless Jul 25 '16 at 11:25
1

It depends on bit width of unsigned/int.

The below 2 are not the same (when unsigned <= 32 bits). u32_x + u32_y becomes 0.

u64_a = 0; u32_x = 1; u32_y = 0xFFFFFFFF;
uint64_t u64_z = u32_x + u64_a + u32_y;
uint64_t u64_z = u32_x + u32_y + u64_a;  // u32_x + u32_y carry does not add to sum.

They are the same (when unsigned >= 34 bits). Integer promotions caused u32_x + u32_y addition to occur at 64-bit math. Order is irrelevant.

It is UB (when unsigned == 33 bits). Integer promotions caused addition to occur at signed 33-bit math and signed overflow is UB.

Are compilers allowed to do such a reordering ...?

(32 bit math): Re-order yes, but same results must occur, so not that re-ordering OP proposes. Below are the same 

// Same
u32_x + u64_a + u32_y;
u64_a + u32_x + u32_y;
u32_x + (uint64_t) u32_y + u64_a;
...

// Same as each other below, but not the same as the 3 above.
uint64_t u64_z = u32_x + u32_y + u64_a;
uint64_t u64_z = u64_a + (u32_x + u32_y);

... can we trust them to notice the result inconsistency and keep the expression order as is?

Trust yes, but OP's coding goal is not crystal clear. Should u32_x + u32_y carry contribute? If OP wants that contribution, code should be

uint64_t u64_z = u64_a + u32_x + u32_y;
uint64_t u64_z = u32_x + u64_a + u32_y;
uint64_t u64_z = u32_x + (u32_y + u64_a);

But not 

uint64_t u64_z = u32_x + u32_y + u64_a;
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256