blog/content/post/llvm-blog-ub-3.md

+++ date = "2018-09-04T22:00:00+08:00" draft = false tags = ['undefined-behavior'] title = "What Every C Programmer Should Know About Undefined Behavior #3/3" summary = """ This is a Chinese translation of the original article on LLVM blog. """ authors = ["sabre"] +++

原作者 Chris Lattner 发表于 2011 年 5 月 21 日（星期六），原文链接

在本系列的 第一篇 中，我们简要介绍了未定义行为，以及通过具体实例， 展示了它们是如何使得 C 语言比 “安全” 语言效率更高的。 第二篇 中，我们关注了未定义行为导致的令人惊讶的 bug， 以及许多程序员对 C 语言固有的、流毒甚广的误解。在本文中， 我们将讨论 LLVM 和 Clang 提供的若干特性和工具如何在保证性能的同时， 消除未定义行为导致的一部分惊人结果。

为什么你们在根据未定义行为进行优化时没有警告？

人们经常质问，为什么编译器在优化过程中利用未定义行为时不给出警告， 因为这些未定义行为的实例可能其实是用户代码中的 bug 。这种想法的主要问题是， 1) 容易产生一大堆没用的警告 —— 因为这些优化在没有 bug 的时候也会随时发生。 2) 很难仅仅在人们需要的时候才产生警告。 3) 没有好的办法（向用户）解释，如何在一系列优化组合起来后， 发现这一步优化的可能性。

下面依次解释这些问题。

“真的很难” 使得警告变得真正有用

让我们看一个例子：即使无效的类型转换 bug 往往被基于类型的别名分析（TBAA） 暴露出来，在优化下面的 zero_array 函数（从 我们的第一篇文章 中复制过来）时，很难真正产生一条有用，类似 “优化器假设 P 和 P[i] 不会互为别名” 的警告。

float *P;
void zero_array() {
  int i;
  for (i = 0; i < 10000; i++)
    P[i] = 0.0f;
}

就算不考虑对该程序的警告其实是虚警，仅仅从逻辑上说， 优化器手中的信息根本不足以生成一条合理的警告。首先， 优化器在代码的一种抽象化表达（LLVM IR）上工作，它和 C 语言完全不同。 其次，编译器是高度分层的，负责“将对 P 的加载操作从循环中提取出来” 的优化器根本不知道是 TBAA 负责处理指针别名问题。对，这是本文中 “编译器作者的抱怨”部分 :) ，但这真的是一个难题。

很难仅在人们需要时才产生警告

Clang 对于未定义行为中那些简单和显然的情况实现了一些警告，例如像 x << 421 这种超过位数的移位。你可能会觉得这很简单很显然， 但最后我们却发现这很复杂，因为 人们不想看到对于死码的警告 （这一问题还有 重复报告）。

死码可能是由于在传递常数时，宏定义以一种神奇的方式展开后形成的。 甚至有人抱怨说我们应该在 switch 语句中使用 控制流分析 证明一些分支是无法到达的，以避免一些警告。这其实根本没卵用， 因为 C 语言中的 switch 语句 未必是良好的结构化程序。

为了解决这些问题，Clang 中负责处理 “运行时行为” 警告的内部结构越来越大， 还加入了很多剪枝代码，以便在我们后续发现代码块不会执行时不输出警告。 这就像是和程序员的军备竞赛，因为总是会出现我们未曾预料的编程惯例， 而且在语言前端中处理这些问题，意味着不可能发现人们希望我们发现的所有问题。

如何解释一系列优化展示出的新优化机会

如果在前端中很难产生好的警告，或许我们可以让优化器产生它们！ 妨碍实现这一想法的最大问题是数据跟踪。编译器的优化器有几十轮优化过程， 每轮都会改变代码，使它更正规化，或者（希望能）使它跑得更快。 例如，如果内联器决定内联一个函数，则它可能会暴露出一项 可以优化掉的 X*2/2。

虽然我在文章中会给出 简单的、自包含的例子 来展示优化过程， 但在现实中它们往往都是宏实例化、内联以及其他编译器的抽象层消除活动的结果。 现实生活中人不会直接写出这样愚蠢的代码。对于警告来说， 这意味着它不能直接反映用户代码中的问题， 而是必须重构编译器处理中间代码的准确过程。 我们需要让编译器能说出像这样的东西：

警告：在 3 次内联（可能在链接时优化中跨过文件边界）， 若干次公共子表达式消除，将该表达式提出循环， 并证明这 13 个指针不会互为别名后，我们发现你的代码存在未定义行为。 这可能是因为你的代码有 bug ，也可能是因为你使用了宏和内联函数， 结果产生了一些实际不会运行的错误代码，但我们却不能证明它是死码。

不幸的是，我们根本没有内部跟踪微结构可以生成这样的警告。就算我们实现了它， 编译器也没有很好的用户接口向程序员表达这类问题。

总而言之，未定义行为对编译器是很有价值的，因为它等于说“这个操作是错误的 —— 你可以假设它永远不会发生”。例如，*P 告诉优化器 P 绝对不是 NULL。 而像 *NULL 这样的东西（在若干次常量传递和内联后生成的） 则会告诉优化器这段代码绝不会执行。这里的问题是，由于无法解决停机问题， 编译器不可能准确确定这个未定义行为是死码（而 C 标准说它一定是）， 还是在一系列（可能很冗长）的优化后暴露出来的 bug 。通常来说没办法区分它们， 所以几乎所有这样的警告都会是虚警（噪声）。

Clang 处理未定义行为的方法

鉴于现在我们处理未定义行为的糟糕状态，你可能希望知道 Clang 和 LLVM 改进现状的尝试。我之前已经提到了一些：Clang 静态分析器， Klee 项目，以及 -fcatch-undefined-behavior 选项都是跟踪特定类型 bug 的有用工具。问题是它们并不像编译器一样被广泛使用， 所以在编译器中直接进行的改进比其他工具中的改进高到不知哪里去了。 请注意编译器永远受到缺乏动态信息和不能消耗太多编译时间的限制。

Clang 提高代码质量的第一步努力是，和其他编译器相比，它默认打开更多的警告。 一些开发者受过训练，总是使用 -Wall -Wextra （等）警告选项构建项目， 很多人根本不知道这些选项，或者懒得传递它们。 默认打开更多警告可以在多数情况下捕获更多的 bug 。第二步是，Clang 对于许多种明显的未定义行为（如解引用空指针、超过位数的移位等） 给出警告，以捕获一些常见的错误。这种警告的局限性已经在前文讨论， 但它们在实践中仍然工作良好。

第三步是，LLVM 优化器通常在利用未定义行为进行优化时，只使用很少的自由度。 尽管标准规定任何未定义行为实例都可能对程序有任意的影响， 但完全利用这种任意性并不是很有用，也不用户友好。相反，LLVM 优化器采用一些不同的方式处理这些优化（下面链接到的文档讨论 LLVM IR 的规则，而不是 C ，抱歉！）：

1. 某些未定义行为被自动、无提示地转化为隐式的陷阱陷入， 如果存在好的转化方法的话。例如，在使用 Clang 编译时，以下 C++ 函数

int *foo(long x) {
  return new int[x];
}

编译为以下 X86-64 机器码：

__Z3fool:
        movl $4, %ecx
        movq %rdi, %rax
        mulq %rcx
        movq $-1, %rdi        # Set the size to -1 on overflow
        cmovnoq %rax, %rdi    # Which causes 'new' to throw std::bad_alloc
        jmp __Znam

而 GCC 却编译出

__Z3fool:
        salq $2, %rdi
        jmp __Znam             # Security bug on overflow!

这里的区别是，我们决定消耗几个时钟周期， 来防止一种可能 非常严重的整数溢出 bug （译者：链接已失效） ， 这种 bug 可能导致缓冲区溢出和安全漏洞 （new 运算符本身就很昂贵，所以额外消耗的时间几乎不会引起注意）。 GCC 的工作人员 至少从 2005 年 就知道这件事， 但迄今为止仍然没有进行修复。 （译者：这个情况是否属于未定义行为本来就有争议， 因为毕竟这里用户没有写乘法表达式，整数溢出不是用户代码的直接结果。 后来委员会修正了标准，规定这不属于未定义行为，然后 GCC 进行了修复。）

2. 对 未定义值 的算术运算只会产生未定义值，而不会产生其他未定义行为。 这样做的目的是，一个未定义值不会直接格式化掉你的硬盘，或者搞出其他麻烦。 此外，如果未定义值上的运算在某些二进制位总是得到确定结果，这些位会被净化掉。 例如，优化器假设 undef & 1 的高位都是零，所以在 LLVM 中 ((undef & 1) >> 1) 永远是零，而不是未定义值。 （译者：另一方面，在 LLVM 的新版本或者其他编译器中，它可能是未定义值。）

3. 动态执行未定义操作的运算（如带符号整数溢出）产生一个逻辑 陷阱值 （译者：链接指向最新版 LLVM 文档 ，但其中已经没有这个名词了， 见 3.0 版文档） 。它可能使基于它进行的后续计算陷入， 但不会导致整个程序跑飞。这意味着，在这次未定义计算之后的逻辑可能受影响， 但不会彻底摧毁整个程序 （彻底摧毁整个程序就允许优化器删掉所有基于未初始化值的代码）。

4. 对空指针写入和通过空指针调用函数被转化为 __builtin_trap() 调用 （生成一条像 x86 的 ud2 这样的陷入指令）。在优化代码时总是会发现这种情况 （因为其他优化，如内联和常量传递作用的结果）， 我们以前会直接删掉包含它们的代码块，因为该代码块 “显然不会执行”。 从严谨的语言律师的视角看一定是这样， 但我们很快发现一些人不小心解引用了空指针，然后发现代码直接跳回了上一级函数， 这很难以理解。从性能角度看， 利用这类未定义行为的最大好处是可以压缩生成的代码。 因此，Clang 把这些未定义行为都转换成运行时陷阱： 如果不小心执行到了它们，程序就会立刻停止，这样就能调试它。 这种办法的主要缺点是，由于这些陷阱和判断它们的条件指令的存在， 生成的代码会略微大一些。

5. 优化器在程序员的意图很显然（如 P 是浮点数指针，却使用 *(int *)P） 时试图“做正确的事”。这在某些情况下有帮助，但你真的不应该依赖这一行为。 此外，在很多情况下，你自己觉得“显然”的事情， 在对代码应用很长的一系列优化后就不再显然。

6. 不属于以上几类的优化，如第一篇中 zero_array 和 set/call 的例子， 会直接进行，对用户没有任何提示。这是因为我们根本说不出什么有用的东西， 而且现实中很少有代码因为这些优化出问题。

在插入陷阱这方面，我们还可以做很多改进。我认为，增加一项（默认关闭的） 警告选项，使得优化器一旦生成陷阱指令就警告，肯定很有趣。 这些警告对于某些代码库来说会很聒噪，但对其他代码来说却很有用。 这里的限制因素首先是，优化器没有有用的代码位置信息，除非打开了调试信息输出 （当然这问题可以解决）。

另一项更重要的限制因素是，警告可没有任何“跟踪”信息， 来解释这项操作是展开三层循环并内联四层函数调用后得到的。 最好的情况是，我们能够指出原始操作在文件中的位置， 这对于多数简单的例子很有用，但在其他情况下可能非常令人困惑。 无论如何，这不是我们实现的重点，因为 a) 不太可能给出较好的用户体验， b) 我们不会默认打开它， c) 工作量太大。

使用 C 的较安全的变体（或其他语言）

最后，如果你不在乎“以性能为纲”，可以使用一些编译选项， 从而启用消除一些未定义行为的 C 语言变体。例如，使用 -fwrapv 选项， 会消除带符号整数溢出导致的未定义行为（然而，这可 没有 彻底消除整数溢出导致的安全漏洞）。-fno-strict-alias 关闭 TBAA，这样你就可以完全不管类型规则。如果有需求，我们还可以增加一个 Clang 选项，将所有局部变量隐式初始化为 0 ，或者在使用变量作为移位位数时， 总是为它增加一个与操作。然而，没有什么好的方法可以从 C 中 完全 消除未定义行为，除非破坏 ABI ，并且完全摧毁 C 的性能。另外的问题是， 此时你已经不是在写 C 程序了，你在写一个和 C 很像，但不可移植的变体。

如果你对使用不可移植的 C 变体不感兴趣，尝试 -ftrapv 和 -fcatch-undefined-behavior 选项（以及我们之前提到的其他工具）， 它们会成为你追踪这类 bug 的有力武器。在调试模式构建中启用它们， 可能是提前发现 bug 的一个好方法。如果你在构建对安全性非常关键的程序， 也可以在生产代码中启用这些选项。它们会发现一部分在实践中很重要的 bug 。 最后，这里的真正问题是， C 本来就不是 “安全” 语言， 而且很多人根本就不理解这个语言如何工作（尽管它很成功也很流行）。 在 1989 年标准化 C 之前，它已经演化了数十年，从 “作为 PDP 汇编语言的一个小封装层的底层系统程序语言” 演化为 “为尽量提供性能甚至不惜打破许多人的预期的底层系统程序语言”。 一方面，C 语言的这些 “开挂行为” 几乎总是能正常工作， 而且确实使得生成的代码更高效（某些情况下可以说高到不知哪里去了）。 另一方面，它开的挂往往是最令人吃惊的，而且往往在最坏的时候导致问题。 C 早就不是一个可移植 “汇编器” 了，有时它和汇编器的区别相当惊人。 我希望我们的讨论能够解释与 C 的未定义行为相关的那些问题， 至少是从编译器开发者的视角进行了解释。

Chris Lattner 发表于 12:48 AM