llvm-blog-ub-1.md 10 KB
+++ date = "2018-09-03T12:00:00+08:00" draft = false tags = ['undefined-behavior'] title = "What Every C Programmer Should Know About Undefined Behavior #1/3" summary = """ This is a Chinese translation of the original article on LLVM blog. """ authors = ["sabre"] +++
原作者 Chris Lattner 发表于 2011 年 5 月 13 日（星期五），原文链接
人们经常会问，为什么在启用优化时，LLVM 编译出的代码有时会产生
SIGTRAP 信号。在探索这个问题时，他们会发现 Clang 生成了一条
ud2 指令（假设生成的是 X86 代码） —— 和 __builtin_trap()
生成的一样。关于这个话题可以引申出很多问题，
它们都与 C 语言中的未定义行为和 LLVM 处理未定义行为的方式密切相关。
本文（三篇系列文章中的第一篇）试图解释这些问题中的一部分， 以便你更好地理解它们的复杂性，以及对于它们不得不进行的权衡。 你可能会了解关于 C 语言的更多底层知识。最后会发现， C 语言 不是 许多有经验的 C 程序员（特别是那些注重底层的人） 一般理解的“高级汇编语言”，而且 C++ 和 Objective-C 直接从 C 语言中继承了这许多问题。
什么是未定义行为
LLVM 中间语言（IR) 和 C 语言都有 未定义行为 的概念。 未定义行为是一个很大的主题，其中有很多微妙的细节。 我见过的最好的对未定义行为的介绍是 John Regehr 的博客。 这篇绝妙文章主要介绍了许多看上去合理但实际有未定义行为的 C 语言构造， 这些未定义行为是程序 bug 的常见原因。除此之外， C 语言中任何未定义行为都允许实现（编译器和运行时环境） 生成格式化你的硬盘、进行完全无法预料的操作，甚至更糟 的代码。 再强调一遍，我 （原作者，下同） 强烈建议阅读 John 的文章。
C 语言存在未定义行为，是因为它的设计者希望它成为极为高效的底层编程语言。 相反，Java （和许多其他所谓的 “安全” 语言） 追求在所有实现环境中都有安全和可重复的行为，因此排除了未定义行为， 不惜为此牺牲性能。这两种决策选择都不能称为 “应该追求的正确目标”， 但如果你是 C 程序员，你应该理解什么是未定义行为。
在讨论细节之前，有必要简要介绍编译器在提高各种 C 程序的性能时作出的努力。 总地来说，编译器通过以下方式产生高性能的程序：a) 优化寄存器分配、 调度等关键算法，b) 了解五花八门的优化“技巧”（如窥视优化、循环转化等）， 并在任何值得使用它们的时候使用它们，c) 善于移除不必要的抽象 （如 C 中的宏定义、C++ 中的内联函数和临时变量导致的冗余等），以及 d) 不把事情搞砸。这些优化听上去很平凡， 但只要在一个关键循环中节约一个时钟周期，就可能让某些解码器的速度提升 10% ，或功耗降低 10%。
C 语言中未定义行为的好处及实例
在深入理解未定义行为，以及 LLVM 在作为 C 编译器时针对它们的策略和行为之前， 我认为应该先考虑未定义行为的若干特例，并逐个讨论它们为何允许比 Java 等安全语言更高的性能。你可以将这些未定义行为看作“启用了优化”，或者 “避免了严格定义这些行为的额外代价”。编译器中的代码优化器可能会利用它们， 消除一些额外代价，但一般来说，（对于所有情况） 消除额外代价需要求解停机问题和许多其他“有趣的挑战性问题”。
另外值得指出，Clang 和 GCC 都限制了一些 C 标准未定义的行为， 下面我们只讨论那些不仅语言标准未有定义， 而且这两个编译器在默认状态下都当作未定义行为处理的情况。
使用未初始化的变量： 这是 C 程序中广为人知的问题来源，
有许多工具可以捕获它们，包括编译器警告、静态和动态分析器等。
这样，C 语言就不需要将所有变量都在作用域开始时初始化为零（就像 Java 那样）。
对于多数标量值，初始化只会导致很小的额外代价。但对于栈上的数组，
或 malloc 分配的内存，初始化就需要使用 memset 清零存储空间，
这是代价很高的，因为必须完全重写这段存储空间。
带符号整数溢出： 如果在 int （等）类型数据上的算术运算发生溢出，
则结果是未定义的。例如，INT_MAX+1 未必得到 INT_MIN。
这使得对于某些代码非常重要的一类优化成为可能，例如，如果知道
INT_MAX+1 是未定义的，则总是可以将 X+1 > X 优化成 true。
如果知道乘法“不会”溢出（因为溢出是未定义行为），就能将 X*2/2
优化成 X。这看上去平淡无奇，
但在函数内联或宏定义展开后往往会发现可以进行这类优化。
另外还有一种更为重要的优化，即针对下面这类 <= 循环：
for (i = 0; i <= N; i++) { ... }
此时，如果 i 的溢出是未定义行为，编译器可以假设循环的迭代次数一定为
N+1 次，这就允许许多类型的循环优化。反之，如果 i 在溢出时一定绕回
INT_MIN，则编译器不得不考虑循环可能是无限的（如果 N 是 INT_MAX），
结果就不能使用这些重要的循环优化。这在 64 位平台上特别要命，
因为许多代码使用 int 作为循环变量。
请注意，无符号整数溢出被准确定义为 2 的补码（绕回）溢出，
所以你可以随便使用无符号整数。然而，如果将带符号整数溢出定义为绕回，
许多优化将不可用。特别是，在 64 位机器上，
需要在循环中对循环变量进行无数次符号扩展。Clang 和 GCC 都允许使用 -fwrapv
来强制编译器明确定义带符号整数溢出（除非是用 INT_MIN 除以 -1）。
移位超过整数位数： 将 uint32_t 移位 32 位或更多位是未定义的。
我猜测这是因为不同 CPU 的底层移位操作有不同行为：
例如 X86 将 32 位移位量截断到 5 位（所以移 32 位等价于移 0 位），
而 PowerPC 却将其截断到 6 位 （所以移 32 位得到 0）。
因此，编译器必须生成额外的指令（如 and）以计算移位量，
才能消除这一未定义行为，在一般的 CPU 上这会导致移位操作的代价提高到 2 倍。
解引用野指针，以及数组访问越界： 解引用随机指针（比如 NULL，
指向已经 free 的内存区域的指针，等等）以及它的特例，即数组访问越界，
是 C 语言中常见的 bug ，这不需要多解释。为了消除这一未定义行为，
必须对每次数组访问进行范围检查，
还需要修改 ABI 以保证数组范围信息绑定在可能由地址运算产生的指针上。
这会为数值计算和其他一些应用程序引入超高代价，
也会破坏与现有 C 库的二进制兼容性。
解引用空指针： 和一般人以为的那样不同，在 C 中，解引用空指针是未定义的。
它 没有定义为陷阱 ，如果你在地址 0 处 mmap 一个页面，
访问该页面未有定义 。
这是禁止解引用野指针和使用 NULL 作为哨兵的直接结果。
规定解引用空指针是未定义的，可以允许许多优化。例如，在 Java 中，
编译器移动有副作用的操作时，不能跨越任何指针解引用操作，
除非优化器能证明解引用的指针非空。这严重干扰了调度和其他优化的工作。
而在基于 C 的语言中，
这项未定义行为允许许多在宏定义展开和函数内联的基础上的简单标量优化。
如果你使用基于 LLVM 的编译器，在希望产生一次崩溃时
可以解引用一个 volatile 的空指针，从而产生崩溃，
这是由于编译器不会改动 volatile 变量的存储和加载过程。
目前没有编译选项可以使得编译器将空指针上的加载操作视为有效的，
或者使得编译器将随机加载视为“允许加载空指针”的。
违反类型规则： 将 int* 转换为 float* 再解引用是未定义的
（即不能将 int 当作 float 访问）。C 语言要求这类转换通过 memcpy
完成，使用指针转换是错误的，会导致未定义行为。这里的规则比较琐碎，
我不会详细讨论（比如对于 char * 有例外情况，向量类型有特殊属性，
联合体可以突破规则，等等）。这项未定义行为允许一种称为“基于类型的别名分析”
（TBAA）的分析，它被编译器广泛用于内存访问优化，可以显著提升代码的效率。
例如，它允许 clang 将下列函数：
float *P;
void zero_array() {
int i;
for (i = 0; i < 10000; ++i)
p[i] = 0.0f;
}
优化成 memset(P, 0, 40000)。TBAA 也可以进行将加载操作移出循环、
消除公共子表达式等优化。可以通过 -fno-strict-aliasing 选项禁用
TBAA，从而消除这类未定义行为。但是，这时 Clang 就不得不将这个循环编译成
10000 次 4 字节存储操作（比 memset 慢几倍），
因为它必须假设任何存储操作都能修改 P 的值，比如：
int main() {
P = (float*)&P;
zero_array();
}
这种滥用指针转换的情况很少见，因此标准委员会决定，为了显著的性能提升， 值得将这些似乎“合理”的类型转换规定为未定义的。另外必须指出，Java 也可以从这些基于类型的优化中获益，因为它根本不允许不安全的指针转换。
无论如何，我希望本文能够给你一个初步的印象，
即 C 语言中的未定义行为能够允许特定的优化。当然还有很多这样的未定义行为，
例如违反 sequence point 规则的 foo(i, ++i)、多线程程序中的竞争条件、
违反 restrict 关键字、除以零，等等。
在 下一篇文章 中，我们会讨论当性能不是我们的唯一目标时， 未定义行为为何会成为非常恐怖的问题。在最后一篇文章中，我们会讨论 LLVM 和 Clang 处理它们的方式。
Chris Lattner 发表于 11:25 AM