(A + B + C) ≠ (A + C + B)且编译器重新排序

Question

将两个32位整数相加可能导致整数溢出：

uint64_t u64_z = u32_x + u32_y;

如果将32位整数之一先转换或加到64位整数中，则可以避免此溢出。

uint64_t u64_z = u32_x + u64_a + u32_y;

然而，如果编译器决定重新排列加法：

uint64_t u64_z = u32_x + u32_y + u64_a;

整数溢出仍可能发生。

编译器是否允许进行这样的重新排序，或者我们可以相信它们会注意到结果的不一致并保持表达式顺序不变？

- Tal

---

你实际上并没有展示整数溢出，因为你似乎是在相加 uint32_t 的值 - 它们不会发生溢出，而是会进行包裹。这些不是不同的行为。 - Martin Bonner supports Monica

请见C++标准的第1.9节，它直接回答了你的问题（甚至有一个与你的问题几乎完全相同的示例）。 - Holt

如其他人已经指出的那样：不存在整数溢出。无符号整数被定义为环绕，对于带符号的整数，则是未定义行为，因此任何实现均可，包括鼻妖精。 - too honest for this site

@Tal：胡说八道！正如我之前写的那样：标准非常清楚并要求进行包装，而不是饱和（使用有符号数可以实现饱和，但这是标准上的未定义行为）。 - too honest for this site

不论您称其为包装还是溢出，重点在于 ((uint32_t)-1 + (uint32_t)1) + (uint64_t)0 的结果为 0，而 (uint32_t)-1 + ((uint32_t)1 + (uint64_t)0) 的结果为 0x100000000，这两个值不相等。因此，编译器能否进行这种转换非常重要。但是，标准只针对有符号整数使用了“溢出”一词，而未使用该术语来描述无符号整数。 - Steve Jessop

Answer 1

如果优化器进行这样的重新排序，它仍然受制于C规范，因此这样的重新排序将变为：

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

理由：

我们从这里开始

uint64_t u64_z = u32_x + u64_a + u32_y;

加法是从左到右进行的。

整数提升规则指出，在原始表达式中的第一次加法中，u32_x 将被提升为 uint64_t。在第二次加法中，u32_y 也将被提升为 uint64_t。

因此，为了符合 C 规范，任何优化器都必须将 u32_x 和 u32_y 提升为 64 位无符号值。这相当于添加强制类型转换。（实际的优化不是在 C 级别上完成的，但我使用 C 表示法是因为那是我们理解的表示法。）

- Klas Lindbäck

---

它不是左结合的吗，所以应该是 (u32_x + u32_t) + u64_a 吧？ - Useless

@Useless：Klas将所有内容都转换为了64位。现在顺序完全不重要了。编译器不需要遵循结合律，它只需要生成与遵循结合律相同的结果即可。 - gnasher729

它似乎暗示 OP 的代码会被评估为那样，但事实并非如此。 - Useless

@Klas - 你能解释一下为什么会这样，并且详细说明你的代码示例是如何得出的吗？ - rustyx

@rustyx 这确实需要解释。谢谢你推动我加上解释。 - Klas Lindbäck

Answer 2

编译器只允许根据“仿佛”规则重新排序。也就是说，如果重新排序总是得到与指定顺序相同的结果，则是被允许的。否则（就像您的示例一样），不行。

例如，给定以下表达式：

i32big1 - i32big2 + i32small

这个语句被精心构建，可以对已知相似但较大的两个值进行减法计算，然后再加上另一个小的值（从而避免任何溢出），编译器可能会重新排序为：

(i32small - i32big2) + i32big1

而且依靠目标平台使用二补数算术并进行包装以防止问题。(如果编译器已经把i32small放在寄存器中，那么这样的重新排序可能是明智的。)

- Martin Bonner supports Monica

---

OP的示例使用了无符号类型。i32big1 - i32big2 + i32small 暗示着有符号类型。还有其他相关问题需要考虑。 - chux - Reinstate Monica

@chux 当然。我想表达的是，尽管我无法编写(i32small-i32big2) + i32big1（因为它可能会导致UB），但编译器可以重新排列它以实现有效性，因为编译器可以确信行为将是正确的。 - Martin Bonner supports Monica

@chux：额外的关注点，如未定义行为不会涉及到，因为我们正在讨论编译器在“ as-if规则”下进行重新排序。特定的编译器可能会利用了解自己的溢出行为的优势。 - MSalters

Answer 3

在 C、C++ 和 Objective-C 中有一个“好像”规则：只要没有符合规范的程序能够区分，编译器可以随意更改代码。在这些语言中，a + b + c 被定义为与 (a + b) + c 相同。如果您能够区分这个和 a + (b + c)，那么编译器无法更改顺序。如果您不能区分，则编译器可以自由更改顺序，但这是可以的，因为您不能区分。在您的例子中，当 b = 64 位，a 和 c = 32 位时，编译器将被允许评估 (b + a) + c 或甚至是 (b + c) + a，因为您无法区分，但不会评估 (a + c) + b，因为您可以区分。

换句话说，编译器不能做出任何使您的代码行为与它应该表现的不同的事情。它不需要产生您认为它会产生的代码或者您认为应该产生的代码，但代码将会给您完全符合期望的结果。

- gnasher729

---

但有一个重要的条件；编译器可以假设没有未定义的行为（在这种情况下是溢出）。这类似于如何将溢出检查 if (a + 1 < a) 进行优化。 - csiz

“@csiz...关于_signed_变量的问题。 无符号变量具有明确定义的溢出语义（环绕）。 ” - Gavin S. Yancey

Answer 4

引用自标准:

[ 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

Answer 5

编译器是否允许进行这种重排序，或者我们可以相信它们会注意到结果不一致并保持表达式顺序不变？编译器只有在给出相同结果的情况下才能重新排序 - 正如您所观察到的那样，这里并没有。如果需要，可以编写一个函数模板，将所有参数提升为std::common_type，然后再进行加法运算 - 这样是安全的，不依赖于任何参数顺序或手动转换，但是它看起来很笨重。

- Useless

---

我知道应该使用显式转换，但我想知道当这种转换被错误地省略时编译器的行为。 - Tal

正如我所说，没有显式转换：左侧加法首先执行，没有整数提升，因此可能会出现包装。该加法的结果（可能被包装）随后被提升为 uint64_t，以便与最右边的值相加。 - Useless

你关于“似乎”规则的解释完全错误。例如，C语言规定了在抽象机器上应该发生什么操作。“似乎”规则允许它做任何它想做的事情，只要没有人能察觉到区别。 - gnasher729

这意味着编译器可以随意进行操作，只要结果与左结合和算术转换规则所确定的结果相同。 - Useless

Answer 6

这取决于无符号/整型数的位宽。当无符号数<=32位时，下面两个不相同。u32_x + u32_y将变为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.

它们是相同的（当unsigned >= 34位）。整数提升导致u32_x + u32_y加法在64位数学中发生。顺序无关紧要。

这是UB（当unsigned == 33位）。整数提升导致加法在有符号33位数学中发生，有符号溢出是UB。

编译器是否允许进行这种重新排序...？

（32位数学）：是可以重新排序的，但必须产生相同的结果，因此不是OP提出的那种重新排序。下面是相同的

// 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);

...我们能相信他们会注意到结果的不一致性并保持表达式顺序吗？

可以信任，但是OP的编程目标并不十分清晰。是否应该包含u32_x + u32_y的进位贡献？如果OP想要这种贡献，代码应该是这样的。

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);

但不包括

uint64_t u64_z = u32_x + u32_y + u64_a;

- chux - Reinstate Monica