What Every C Programmer Should Know About Undefined Behavior #1/3

Friday, May 13, 2011
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
翻译：王鑫

当开始编译器优化的时候，llvm 编译出的代码偶尔会产生 SIGTRAP 信号。随着对此问题的深入研究，人们发现，clang会产生一个“ud2”的指令（假设在X86平台下），这个指令同__builtin_trap()产生的一样。与之相关的问题全都是关于C代码的未定义行为以及LLVM如何处理它的。

本文试图通过解释这些问题，使得你能够更好的理解编译器优化中的权衡和复杂度，也许还能学到一点关于C语言的隐蔽特性。C并不像许多有经验的C程序员（尤其是那些关注底层的人）所想的那样是一个“高级汇编”，而且C++和Objective-C从中直接继承了许多同样的问题。

Introduction to Undefined Behavior
无论是LLVM IR（intermediate representation）和C语言都有“未定义行为”这个概念。未定义行为是一个有着许多微妙之处的广阔话题。我发现的对此的最佳介绍是John Regehr博客里的一篇文章。这篇极其精彩的文章概括了一件事情：许多在C中貌似合理的事情实际上都有着不确定的行为，并且这通常都是程序中BUG的源头。除此之外，C中的任何的未定义行为都有可能（无论是编译期还是运行期）产生一些格式化你的硬盘的、做一些你完全想象不到的事情的代码，或者更糟。我再次强烈推荐读一下John的那篇文章。

基于C的语言中一般都存在着未定义行为，这是因为C的设计者想要把它作为一种极其有效的低级编程语言。相反，像Java（还有其它许多“安全的”语言）就规避了此类未定义行为，因为他们想要的是安全性和一致性，并且为此可以牺牲性能。不管“哪个目标才是正确的”，如果你是一个C程序员的话，你确实应该了解一下什么是未定义行为。

在我们详细深入这个话题之前，我认为有必要简单地说一下为了使C的应用程序获得更好的性能，编译器都干了些什么。概括来看，编译器产生高性能的应用程序一般通过：

1. 基础计算优化（比如寄存器分配、调度）
2. 许许多多的小技巧（比如窥孔优化、循环转换）
3. 擅长消除一些不必要的抽象（比如，由于C中的宏而产生的冗余，内联函数，在C++中消除临时对象等）
4. 不把任何事情搞糟

也许这些优化可能听起来微不足道，但是在一个关键循环中哪怕只是减少一次循环都有可能使代码运行快10%或者少消耗10%。

未定义行为带来的好处
在讲述未定义行为的阴暗面，以及LLVM编译器的策略和行为之前，我打算先介绍一些特定的未定义行为是如何比像Java一类的安全语言获得更好的性能的。要么是因为未定义行为使得优化成为可能，要么是因为被完备定义会带来额外的开销。编译器的优化器有时可以消除这些开销，但为了达到这个目的需要解决很多“有意思的挑战”。

同样需要指出的是，无论Clang还是GCC都将一部分标准C中遗留的未定义行为确定了下来。下面将要讲到的例子无论是根据标准还是被这两个编译器的缺省所对待的，都是未定义的（行为）。

使用未初始化变量：这通常被认为是C程序的问题之源，而且现在也有许多工具可以捕获它：从编译器警告到静态或动态分析。这种方法通过当变量进入自己的有效范围（像Java那样）时而不必要求所有变量初始化为0而达到改进性能的目的。对于大多数的scalar变量，这将基本不会引起系统开销，但是若是对栈数组或malloc分配的内存调用memset，代价则非常昂贵，尤其是当该存储空间经常被完全改写的时候。

有符号的整数溢出：如果一个‘int’类型的变量运算溢出了，结果是不确定的。一个例子就是不能保证“INT_MAX+1”等于“INT_MIN”。这种行为对于某些代码而言，开启特定的优化器是重要的。例如，知道了INT_MAX+1是未定义的，那么允许优化“X+1 > X”的结果为“true”。知道了乘法“不能”溢出（因为如果溢出的话结果将是不确定的），那么开启优化“X*2/2”等于“X”。虽然这些可能看起来都是微不足道的小事，但是这类事情总是由于内联和宏展开而成为不受保护的。一个更重要的优化是针对for循环中的“

在这个循环中，编译器会假设当“i”溢出成为不确定值的时候，这个循环会精确地迭代N+1次，随后有更多的循环优化可能。另一方面，如果变量确定是在溢出周围的话，那么编译器必须假设这个循环可能是无穷的（当N是INT_MAX的情况），循环优化就无法进行了。这点尤其影响64位的平台，因为如此之多的代码都把“int”用作归纳变量。

而无符号数的溢出被保证为2进制数的补码溢出，因此你可以总是使用它们。把有符号整数溢出的行为确定下来的代价是这类优化器失效。（例如，通常表现为64位目标机循环中符号位的扩展）。Clang和GCC全部接受“-fwrapv”标志来强迫编译器把有符号整数的溢出的行为确定下来

超过范围的移位：将一个uint32_t移32或更多的位是未定义的。我猜这最初是因为在不同CPU上的移位操作是不同的：比如，X86平台会将移位值截断为5位（因此移动32位是同移动0位一样的）【译者注：可参考 https://blog.delphij.net/2011/06/post-603.html】，但是PowerPC将移动值截断为6位（因此移动32位的结果为0）。由于硬件的差异性，这个行为在C中也是完全无法确定的（因此在PowerPC上移动32位可能会格式化掉你的硬盘，它并不保证一定产生0）。消除这个未定义行为的代价就是编译器在变量移位时不得不加入一些额外的操作（比如“与”操作），相对于普通的CPU，这将产生两倍的代价。

野指针的解引用以及数组越界访问：解引用随机指针（比如NULL，或者已被free掉的指针等）和越界数组访问在C程序中毫无疑问地都是一个bug。为了从根本上消除此种未定义行为，数组访问将不得不进行边界检查，并且将不得不改变ABI来保证任何指针的范围信息都能够被映射为指针的运算。这对于许多数值和其他应用来说，将花费极高的代价，就好像破坏掉现存的每一个C库的二进制兼容性一样。

解引用一个NULL指针：不同于普遍的看法，在C中解引用一个空指针是未定义的。它并未被定义为自陷（trap），如果你mmap一个页面在0，它并不一定会去访问那个页面。这放弃了原来拒绝解引用野指针和把NULL当作哨兵用的习惯。NULL指针的解引用成为未定义的，这将开启大范围的优化：相反，对于任何一个不能被优化器证明为非空的对象指针的解引用，Java会带来一个副作用，即都会把它当作对于编译器是无效的。这极度地影响了调度策略和其它优化。在基于C的语言中，把NULL当作未定义将开启许多简单的标量优化处理，那是由于宏展开和内联而被展现出来。

如果你在使用一个基于LLVM的编译器，如果你愿意，你能够解引用一个“volatile”null指针来得到一个崩溃，因为volatile的加载和存储通常是不通过优化器的。当前还没有任何标志可以把随机的NULL指针的加载当作有效的访问来对待，或者使随机加载知道它们的指针是“被允许为null”的。

违背类型规则：把一个int*转换成一个float*并且解引用它（把这个“int”当作“float”来访问）是一个未定义行为。C要求这类的类型转换是通过memcpy来完成的：使用指针转换是不正确的并且结果是不确定的。这个规则是有十分细微差别的，而且我不想在这里详细说它（char*是一个特例，向量有着特殊的性质，所有元素一起改变。这个行为引起一个被称之为“基于类型的别名分析”（TBAA）的分析，它在编译器中被用作大范围的内存访问优化，并且能够显著地改进生成代码的性能。比如，这条规则将允许clang把下面这个函数优化为"memset(P, 0, 40000)"。

这个优化也使得许多加载都不用进入循环，消除掉一般的子表达式等。这类的未定义行为可以通过传递-fno-strict-aliasing标志来禁止掉，这将禁止这个分析。当传递此标志时，Clang将会把这个循环编译成10000个4字节存储（将会慢好多倍），因为它不得不假设任何存储都有可能改变其值，就好像下面这样：

这种滥用类型是十分不常见的，这也是为什么标准委员会决定为了显著的性能允许“合理的”类型转换的难以预料的结果。值得说明的是，Java从基于类型的优化中受益但并没有这些缺点，因为在这门语言中完全不存在不安全的指针转换。

不管怎么说，我希望你能了解一些通过C中的未定义行为开启的这些优化。也有许多其他类型的例子，包括以下这些，比如“foo(i, ++i)”，多线程程序中的竞争条件，违反“restrict”，除0等。

在我们的下一篇文章中，我们将讨论为什么当性能不再是你唯一的目标的时候，C中的未定义行为是一件十分可怕的事情。在本系列的最后一篇文章中，我们将讨论LLVM和Clang怎样处理它的。