Making all divisions slower to fix a bug in 0.000000000000000000542% of cases

本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

Making all divisions slower to fix a bug in 0.000000000000000000542% of cases

几乎所有现代机器都使用补码来表示整数。这种表示法是不对称的，因为最小的负数没有对应的正数。例如，对于有符号 8 位整数，最小的负数是 -128，而最大的正数是 127。这种特性在多种情况下都会出现，但就本文而言，我关注的是有符号整数除法。在数学上，x/-1 应该产生 -x，但在 x 是最小负数的情况下，这是不可能实现的。对于我随意认定为最常见的 32 位整数而言，这意味着每 2⁶⁴ 个可能的输入中就有一个无法被正确表示——这便引出了本文略带噱头的标题，以及 Futhark 编译器中最近修复的一些麻烦。在本文中，我将解释这对语言实现来说究竟是什么问题，我们如何修复它，以及性能代价如何。本文的主要受众是其他语言实现者，但我认为所涉及的概念足够简单，任何对底层问题感兴趣的人都可以跟上。

The C issue

The Futhark compiler has multiple backends, but the most important ones work by generating C code. This has many practical advantages: It is easy to debug the generated code because it is easy to read and modify by hand. Most systems have a C compiler (or easy access to one), meaning Futhark has fewer dependencies, is portable, and doesn’t need to bundle native code generators. Many languages can interoperate with C, so by exposing Futhark as a C API, those languages can also call Futhark. That said, there are also disadvantages: Some code patterns are hard to express (or express efficiently) in C. This is mainly the case for advanced language features such as coroutines, tail calls, or garbage collection. Fortunately Futhark is pretty boring from a semantic perspective, so this does not affect us too much.

C 语言问题 Futhark 编译器有多个后端，但最重要的后端是通过生成 C 代码来工作的。这有许多实际优势：生成的代码易于调试，因为它们易于阅读和手动修改。大多数系统都有 C 编译器（或易于获取），这意味着 Futhark 的依赖项更少，具有可移植性，且无需捆绑原生代码生成器。许多语言可以与 C 互操作，因此通过将 Futhark 公开为 C API，这些语言也可以调用 Futhark。话虽如此，也有一些缺点：某些代码模式在 C 中很难表达（或难以高效表达）。这主要针对协程、尾调用或垃圾回收等高级语言特性。幸运的是，从语义角度来看，Futhark 非常简单，因此这不会对我们产生太大影响。

It is very easy to accidentally generate C code that is subtly wrong. This does unfortunately keep pestering us. C is of course renowned as a very safe and easy-to-use language, because C programmers never make coding mistakes. The few times they do make mistakes, it is often due to mishandling of pointers or array sizes, leading to buffer overflows, heap smashing, etc. These are actually not the main problem with generating C from Futhark, as Futhark itself is memory-safe, and systematically inserting in bounds checks in generated code is easy (although a little more interesting in GPU code). No, the main problem we’ve had is actually undefined behaviour.

生成微妙错误的 C 代码非常容易。不幸的是，这确实一直困扰着我们。C 语言当然以非常安全且易于使用而闻名，因为 C 程序员从不犯编码错误。他们偶尔犯错时，通常是由于指针或数组大小处理不当，导致缓冲区溢出、堆破坏等。这些实际上并不是从 Futhark 生成 C 代码的主要问题，因为 Futhark 本身是内存安全的，并且在生成的代码中系统地插入边界检查很容易（尽管在 GPU 代码中稍微复杂一些）。不，我们遇到的主要问题实际上是未定义行为。

As is by now well-known, C specifies various events as explicitly undefined, meaning not only that a C compiler can assume it will never occur, but also that no particular result is guaranteed should a program perform one of the undefined operations. Some causes of undefined behaviour are obvious and easy to avoid: reading arrays out-of-bounds, using freed memory, etc. But C has a long list of more obscure cases. My favourite example is that in C99, it is undefined behaviour if a source code file does not end with a final newline character. Yet we have honestly not spent that much time dealing with that particular issue in Futhark.

众所周知，C 语言将各种事件明确指定为未定义，这意味着 C 编译器不仅可以假设它们永远不会发生，而且如果程序执行了其中一种未定义操作，也不保证会有任何特定的结果。某些未定义行为的原因显而易见且易于避免：数组越界读取、使用已释放的内存等。但 C 语言有一长串更晦涩的情况。我最喜欢的例子是，在 C99 中，如果源文件没有以换行符结尾，则属于未定义行为。然而，老实说，我们在 Futhark 中并没有花太多时间处理那个特定的问题。

No, the main problem, and now we are finally returning to the premise in the post, is that signed integer overflow is undefined behaviour in C. This is particularly insidious since most programmers have a mental model of fixed-size integer arithmetic where overflow is a natural event, and so does the actual machines we use, but a C compiler may assume it never happens. The reason behind this specification is so the C compiler can optimise based on useful properties such as x+1>x, which are not true in the presence of overflow, but the motivation does not actually matter to us.

不，主要问题——现在我们终于回到了本文的前提——是有符号整数溢出在 C 语言中是未定义行为。这一点尤其阴险，因为大多数程序员对固定大小整数算术的心理模型是溢出是一种自然事件，我们使用的实际机器也是如此，但 C 编译器可能会假设它永远不会发生。这一规范背后的原因是让 C 编译器能够基于诸如 x+1>x 之类的有用属性进行优化，而这些属性在溢出时并不成立，但其动机对我们来说并不重要。

In a language like Futhark, where integer overflow is defined behaviour (it wraps around), this creates a very unfortunate mismatch between what we want to do, and what we can express in our target language. Fortunately, C is merciful enough to specify that for unsigned numbers, overflow is well-defined, and behaves just as you would expect (on a two’s-complement machine, anyway). For this reason, Futhark’s C code generation actually represents all integer types using unsigned C types, (so i64 becomes uint64_t), and then performs the arithmetic on unsigned types. This works due to the nice property of two’s complement representation that most arithmetic operations are done exactly the same, at the bit level, as for unsigned integers.

在像 Futhark 这样整数溢出是定义行为（即回绕）的语言中，这在我们想要做的事情和我们在目标语言中能表达的事情之间造成了非常不幸的不匹配。幸运的是，C 语言足够仁慈，规定对于无符号数，溢出是定义明确的，并且表现正如你所预期的那样（至少在补码机器上是这样）。因此，Futhark 的 C 代码生成实际上使用无符号 C 类型来表示所有整数类型（所以 i64 变成了 uint64_t），然后在无符号类型上执行算术运算。这之所以有效，是因为补码表示法的一个良好特性：大多数算术运算在位级别上与无符号整数的执行方式完全相同。

One exception is comparison operators, in which we cast to the signed type (e.g. int64_t) before performing the comparison. Such conversions are free, since they do not need to change the bit representation of the number, but only affect what instructions the C compiler emits for e.g. a <= operation. Another operator where sign matters is division. If we do x/-1, then it is quite important whether we are dividing with a small negative number, or with the number that arises if we interpret the two’s complement bit pattern for -1 as an unsigned integer. This means that for signed integer division, Futhark generates a signed C division. This means that if we do x/-1 where x is the most negative number, we are stuck with the issue described in the post opener - the correct result (-x) cannot be represented as a signed integer, so this is a signed integer overflow, and that is undefined behaviour in C. Futhark is a principled language, and therefore producing undefined behaviour is unacceptable. (I realise the hypocrisy of this puritan declaration whilst leaving in the bug for ten years.) Further, on x86 th

一个例外是比较运算符，我们在执行比较之前将其转换为有符号类型（例如 int64_t）。这种转换是免费的，因为它们不需要改变数字的位表示，只会影响 C 编译器为例如 <= 操作发出的指令。另一个符号很重要的运算符是除法。如果我们执行 x/-1，那么我们是除以一个小的负数，还是除以将 -1 的补码位模式解释为无符号整数时产生的数字，这非常重要。这意味着对于有符号整数除法，Futhark 会生成有符号的 C 除法。这意味着如果我们执行 x/-1，其中 x 是最小的负数，我们就会陷入文章开头描述的问题——正确的结果 (-x) 无法表示为有符号整数，因此这是有符号整数溢出，而在 C 语言中这是未定义行为。Futhark 是一门有原则的语言，因此产生未定义行为是不可接受的。（我意识到在保留这个 bug 十年之后再发表这种清教徒式的声明是多么虚伪。）此外，在 x86 上……