有没有一些有意义的统计数据可以证明保持有符号整数算术溢出未定义是合理的？

Question

C标准明确规定有符号整型溢出具有未定义的行为。然而，大多数CPU使用有定义的语义来实现有符号算术溢出（除了除法溢出： x / 0和INT_MIN / -1）。

编译器作者一直利用这种溢出的未定义性来添加更激进的优化，往往会以非常微妙的方式破坏传统代码。例如，这段代码可能在旧版的gcc和clang上运行正常，但在当前版本中却不再工作：

/* Increment a by a value in 0..255, clamp a to positive integers.
   The code relies on 32-bit wrap-around, but the C Standard makes
   signed integer overflow undefined behavior, so sum_max can now 
   return values less than a. There are Standard compliant ways to
   implement this, but legacy code is what it is... */
int sum_max(int a, unsigned char b) {
    int res = a + b;
    return (res >= a) ? res : INT_MAX;
}

这些优化是否值得采用有可靠的证据吗？是否有比较研究记录了实际示例或经典基准测试中的改进情况？

我提出了这个问题，因为我正在观看：C++Now 2018: John Regehr “Closing Keynote: Undefined Behavior and Compiler Optimizations”

我标记了c和c++，因为两种语言的问题相似，但答案可能不同。

- chqrlie

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Samuel Liew

C之所以说有符号整数的溢出是未定义的，是因为一些CPU使用“二进制补码”，一些使用“一进制补码”，一些使用“符号位加减法”；而对于所有情况下的溢出都可能引起任何问题（例如像MIPS这样的CPU会“在溢出时进行陷阱处理”）。换句话说，这涉及到可移植性而不是优化。 - Brendan

没错。任何人都需要知道的唯一“有意义的统计数据”是：存在反码和补码计算机。 - user207421

@user207421：是的，那是一个好问题，答案似乎是“不再支持”。因此目前的提议是移除对非二补数表示的支持：http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2330.pdf。 - chqrlie

@Brendan：一补数架构已经过时了。MIPS的溢出陷阱是可选择的。 - chqrlie

@chqrlie：C语言也是过去的事情了（现在已经47岁了）。有很多设计决策当时是有道理的，但现在已经不再合理，但仍然存在，因为改变会破坏太多现有的软件。 - Brendan

Answer 1

虽然我不了解研究和统计方面的知识，但编译器确实考虑了这一点进行了优化。这些优化非常重要（例如，循环向量化）。

除了编译器优化之外，还有另一个需要考虑的方面。在存在未定义行为（UB）时，C/C++带符号整数的算术行为与你所期望的数学行为相同。例如，现在x + 10>x成立（当然是对于有效的代码），但在回绕行为下则不成立。

我找到了Krister Walfridsson博客上的一篇优秀文章《如何利用有符号溢出的未定义行为使GCC进行优化》，其中列出了一些考虑带符号溢出UB的优化。以下示例来自该文章。我将给它们添加C++和汇编示例。

如果这些优化看起来过于简单、无趣或没有影响力，请记住，这些优化只是更大的优化链中的步骤。蝴蝶效应确实会发生，因为较早步骤的看似不重要的优化可能会触发更具影响力的优化。

如果这些示例看起来毫无意义（谁会写x * 10>0），请记住，你可以通过常量、宏、模板很容易地得到这种示例。此外，编译器在应用IR的转换和优化时也可以得到这种示例。

带符号整数表达式简化

• 消除与0比较中的乘法

  (x * c) cmp 0   ->   x cmp 0 
  

  bool foo(int x) { return x * 10 > 0 }
  

  foo(int):
          test    edi, edi
          setg    al
          ret
  

• 优化除法运算

  当c1是c2的倍数时，(x * c1) / c2 可以简化为 x * (c1 / c2)

int foo(int x) { return (x * 20) / 10; }

foo(int):
        lea     eax, [rdi+rdi]
        ret

• 消除否定

  (-x) / (-y) -> x / y

int foo(int x, int y) { return (-x) / (-y); }

foo(int, int):
        mov     eax, edi
        cdq
        idiv    esi
        ret

• 简化永远为真或为假的比较

x + c < x       ->   false
x + c <= x      ->   false
x + c > x       ->   true
x + c >= x      ->   true

bool foo(int x) { return x + 10 >= x; }

foo(int):
        mov     eax, 1
        ret

消除比较中的否定

(-x) cmp (-y)   ->   y cmp x

bool foo(int x, int y) { return -x < -y; }

foo(int, int):
        cmp     edi, esi
        setg    al
        ret

缩小常量的大小

x + c > y       ->   x + (c - 1) >= y
x + c <= y      ->   x + (c - 1) < y

bool foo(int x, int y) { return x + 10 <= y; }

foo(int, int):
        add     edi, 9
        cmp     edi, esi
        setl    al
        ret

• 比较中消除常量

  (x + c1) cmp c2         ->   x cmp (c2 - c1)
  (x + c1) cmp (y + c2)   ->   x cmp (y + (c2 - c1)) if c1 <= c2
  

  第二次变换仅在 c1 <= c2 时有效，否则当 y 的值为 INT_MIN 时会导致溢出。

  bool foo(int x) { return x + 42 <= 11; }
  

  foo(int):
          cmp     edi, -30
          setl    al
          ret
  

指针算术和类型提升

如果一个操作不会溢出，那么在更宽的类型上执行相同的操作会得到相同的结果。这在进行 64 位体系结构上的数组索引等操作时非常有用。通常使用 32 位 int 进行索引计算，但指针是 64 位的，当有符号溢出未定义时，编译器可能通过将 32 位整数提升为 64 位操作而生成更有效的代码。

另一个方面是未定义的溢出确保 a[i] 和 a[i+1] 相邻。这改善了内存访问的分析，以便进行矢量化等操作。

这是一种非常重要的优化，因为循环矢量化是最有效和有效的优化算法之一。

以下是将无符号索引更改为有符号索引可以改进生成的汇编代码的示例：

无符号版本

#include <cstddef>

auto foo(int* v, std::size_t start)
{
    int sum = 0;

    for (std::size_t i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

在使用无符号数时，必须考虑到 start + 4 回绕的情况，并生成分支来处理此情况（分支对性能不利）:

; gcc on x64 with -march=skylake

foo1(int*, unsigned long):
        cmp     rsi, -5
        ja      .L3
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret
.L3:
        xor     eax, eax
        ret

; clang on x64 with -march=skylake

foo1(int*, unsigned long):                             # @foo1(int*, unsigned long)
        xor     eax, eax
        cmp     rsi, -4
        jae     .LBB0_2
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rsi + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rsi]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
.LBB0_2:
        ret

顺便提一下，使用更窄的类型会导致汇编代码更糟糕，从而限制使用SSE向量化指令：

#include <cstddef>

auto foo(int* v, unsigned start)
{
    int sum = 0;

    for (unsigned i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, unsigned int):
        cmp     esi, -5
        ja      .L3
        mov     eax, esi
        mov     eax, DWORD PTR [rdi+rax*4]
        lea     edx, [rsi+1]
        add     eax, DWORD PTR [rdi+rdx*4]
        lea     edx, [rsi+2]
        add     eax, DWORD PTR [rdi+rdx*4]
        lea     edx, [rsi+3]
        add     eax, DWORD PTR [rdi+rdx*4]
        ret
.L3:
        xor     eax, eax
        ret

; clang on x64 with -march=skylake

foo(int*, unsigned int):                              # @foo(int*, unsigned int)
        xor     eax, eax
        cmp     esi, -5
        ja      .LBB0_3
        mov     ecx, esi
        add     esi, 4
        mov     eax, dword ptr [rdi + 4*rcx]
        lea     rdx, [rcx + 1]
        cmp     rdx, rsi
        jae     .LBB0_3
        add     eax, dword ptr [rdi + 4*rcx + 4]
        add     eax, dword ptr [rdi + 4*rcx + 8]
        add     eax, dword ptr [rdi + 4*rcx + 12]
.LBB0_3:
        ret

签名版本

然而，使用签名索引会产生漂亮的向量化无分支代码：

#include <cstddef>

auto foo(int* v, std::ptrdiff_t start)
{
    int sum = 0;

    for (std::ptrdiff_t i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, long):
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

; clang on x64 with -march=skylake

foo(int*, long):                              # @foo(int*, long)
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rsi + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rsi]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

当使用较窄的带符号类型时，仍然会使用向量化指令：

#include <cstddef>

auto foo(int* v, int start)
{
    int sum = 0;

    for (int i = start; i < start + 4; ++i)
        sum += v[i];

    return sum;
}

; gcc on x64 with -march=skylake

foo(int*, int):
        movsx   rsi, esi
        vmovdqu xmm0, XMMWORD PTR [rdi+rsi*4]
        vpsrldq xmm1, xmm0, 8
        vpaddd  xmm0, xmm0, xmm1
        vpsrldq xmm1, xmm0, 4
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

; clang on x64 with -march=skylake

foo(int*, int):                              # @foo(int*, int)
        movsxd  rax, esi
        vpbroadcastq    xmm0, qword ptr [rdi + 4*rax + 8]
        vpaddd  xmm0, xmm0, xmmword ptr [rdi + 4*rax]
        vpshufd xmm1, xmm0, 85                  # xmm1 = xmm0[1,1,1,1]
        vpaddd  xmm0, xmm0, xmm1
        vmovd   eax, xmm0
        ret

值域计算

编译器在程序的每个点上跟踪变量可能值的范围，例如以下代码：

int x = foo();
if (x > 0) {
  int y = x + 5;
  int z = y / 4;

if语句后程序确定了变量x的范围为[1, INT_MAX]，因此可以确定y的范围为[6, INT_MAX]，因为不允许出现溢出。同时，由于编译器知道y是非负数，下一行代码可优化为int z = y >> 2;。

auto foo(int x)
{
    if (x <= 0)
        __builtin_unreachable();
    
    return (x + 5) / 4;
}

foo(int):
        lea     eax, [rdi+5]
        sar     eax, 2
        ret

未定义的上溢有助于对比两个值（因为包装情况会给出形式为[INT_MIN，（INT_MIN + 4)]或[6，INT_MAX] 的可能值，从而防止所有有用的与<或> 的比较），例如：

• 如果x和y的范围不重叠，则将比较x<y更改为true或false
• 如果范围不重叠，则将min（x，y）或max（x，y）更改为x或y
• 如果范围未穿越0，则将abs（x）更改为x或-x
• 如果x> 0并且常数c是2的幂，则将x / c更改为x>> log2（c）
• 如果x> 0并且常数c是2的幂，则将x％c更改为x&（c-1）

循环分析和优化的典型例子是像以下示例的循环：

for (int i = 0; i <= m; i++)

保证在未定义溢出时终止。这有助于具有特定循环指令的体系结构，因为它们通常不能处理无限循环。

但是，未定义的带符号溢出可以帮助许多循环优化。所有分析，例如确定迭代次数、转换归纳变量和跟踪内存访问都使用前面部分中的所有内容来完成其工作。特别地，允许带符号溢出会严重减少可以进行向量化的循环集合。

- bolov

---

@immibis 我的意思是它适用于所有有效的代码，但未定义行为并不是有效的代码。 - bolov

@chqrlie 我听说在cppcon上，标准委员会的重要成员承认，在 hindsight 中无符号大小是一个错误。无符号整数的环绕行为也是如此（对于普通类型来说，在溢出时应该有 UB，并且对于需要显式使用 wraparound 行为的情况，应该有单独的类型会更好）。 - bolov

@immibis 不，这是标准要求的。就像标准要求假定被解引用的指针不为 null 一样。 - bolov

@immibis 你看到编译器如何将 x + 10 >= x; 转换为 mov eax, 1 吗？这正是因为它可以假设 x + 10 >= x 总是成立的（我再强调一遍：对于有效的代码）。 - bolov

@immibis，你现在是故意这样做的。你正在把讨论从原始问题上移开。我的陈述是：“编译器会假定对于有效的代码，x + 10 >= x 总是为真 - 这是标准规定的 - 因此编译器可以将表达式优化为 true”。这一直是我的陈述。这就是我正在辩论的内容（也是你最初反对的内容）。你现在想谈论程序员必须确保自己不编写具有 UB 的代码，因此是无效的，那是另一个讨论。 - bolov

Answer 2

这里有一个实际的小基准测试，冒泡排序。我比较了没有使用-fwrapv 和使用-fwrapv (这意味着溢出是未定义行为/定义行为)的时间。以下是结果（秒）:

                   -O3     -O3 -fwrapv    -O1     -O1 -fwrapv
Machine1, clang    5.2     6.3            6.8     7.7
Machine2, clang-8  4.2     7.8            6.4     6.7
Machine2, gcc-8    6.6     7.4            6.5     6.5

可以看到，不符合未定义行为的版本 (-fwrapv) 几乎总是更慢，最大差异相当大，为1.85倍。

这里是代码。请注意，我故意选择了一种实现方式，以便对这个测试产生更大的差异。

#include <stdio.h>
#include <stdlib.h>

void bubbleSort(int *a, long n) {
        bool swapped;
        for (int i = 0; i < n-1; i++) {
                swapped = false;
                for (int j = 0; j < n-i-1; j++) {
                        if (a[j] > a[j+1]) {
                                int t = a[j];
                                a[j] = a[j+1];
                                a[j+1] = t;
                                swapped = true;
                        }
                }

                if (!swapped) break;
        }
}

int main() {
        int a[8192];

        for (int j=0; j<100; j++) {
                for (int i=0; i<8192; i++) {
                        a[i] = rand();
                }

                bubbleSort(a, 8192);
        }
}

- geza

Answer 3

虽然不是一个优化的例子，但未定义行为的一个有用后果是GCC/clang的-ftrapv命令行开关。它插入代码，在整数溢出时使您的程序崩溃。

对于无符号整数，它不起作用，这符合无符号溢出是有意的想法。

标准对有符号整数溢出的措辞确保人们不会故意编写溢出代码，因此ftrapv是发现无意间溢出的有用工具。

- anatolyg

---

是的。产生错误值是一个严重的问题，而看起来正确的值更加棘手。在许多情况下，对结果没有期望，因此任何打印出来的值都可能被认真对待。这甚至可能导致安全漏洞。 - curiousguy

标准对于调用UB的结构是否应被视为错误或不可移植持中立态度。如果程序从未有意访问例如内部下标大于九的char[10][10]，则在这样做时引发实现陷阱可能是有用的。另一方面，某些任务可以在允许内部下标访问多行数据的实现上更有效地完成，而不是要求程序员用双重循环替换迭代多行项目的循环的实现。 - supercat

处理每一行的数据。虽然标准允许实现假设它永远不会接收到除了严格符合规范的程序之外的任何内容，但这并不意味着这种假设对于大多数实现来说是合理的。 - supercat

Answer 4

最初的回答实际上就在你的问题里：

大多数CPU都使用有定义语义的带符号算术运算，我想不出今天可以购买到的不使用二进制补码算术运算来处理有符号整数的CPU，但这并非一直如此。

C语言是在1972年发明的。当时，IBM 7090大型计算机仍然存在。并非所有计算机都是二进制补码。

如果围绕二进制补码定义语言（和溢出行为）将对不支持该功能的机器上的代码生成产生偏见。

此外，正如已经说过的那样，指定有符号溢出是UB可以使编译器生成更好的代码，因为它可以排除由于有符号溢出而产生的代码路径，假设这永远不会发生。

如果我正确理解了它的意图是将a和b的和夹紧到0….INT_MAX而不是环绕，则可以想到两种以合规方式编写此函数的方法。

首先是通用但效率低下的情况，适用于所有CPU：

int sum_max(int a, unsigned char b) {
    if (a > std::numeric_limits<int>::max() - b)
        return std::numeric_limits<int>::max();
    else
        return a + b;
}

第二种方法是令人惊讶的高效2s补码特殊方式：

int sum_max2(int a, unsigned char b) {
    unsigned int buffer;
    std::memcpy(&buffer, &a, sizeof(a));
    buffer += b;
    if (buffer > std::numeric_limits<int>::max())
        buffer = std::numeric_limits<int>::max();
    std::memcpy(&a, &buffer, sizeof(a));
    return a;
}

生成的汇编代码可以在此处查看：https://godbolt.org/z/F42IXV。原始答案翻译成“最初的回答”。

- Richard Hodges

---

你的二进制补码特定方式具有不同的语义：对于小于 -b 的负值 a，它将返回 INT_MAX。 - chqrlie

@chqrlie 我一定误解了函数的要求。我假设由于我们将输入限制为正数，因此输入保证为正数。 - Richard Hodges

这个愚蠢的例子函数只检测正溢出，因为b是本质上是正数，但是a可以有一个负值。它只是一个例子，你的 sum_max 版本是以可移植的方式实现目标的正确方法，但我曾看到遗留代码使用我发表的测试，虽然这从来不正确但在大约10年前之前仍能“正常工作”。 - chqrlie

顺便提一下，C++ 最近删除了有符号整数的替代表示方式。现在只支持二进制补码。 - chqrlie

这是真的，截至c++20版本，但我没有提到它，因为对于所有之前提到过的与优化相关的原因，有符号整数溢出仍然是未定义行为。我不想给人留下错误的印象，认为遗留代码将变得可行。它不会。 - Richard Hodges