编译器 - 什么是优化编译器

说明：本文参考Wikipedia的文章形成。感兴趣可以参见英文链接。

Optimizing Compiler (后文以“优化编译器”代之) 就是试图最小化或最大化某些可执行文件属性的编译器。^[1]

• 执行时间
• 内存开销
• 执行文件大小
• 低功耗

后两者经常会出现在嵌入式程序开发中。笔者曾经参与过相关的开发，品尝过抢code size的滋味（在项目刚开始写一些相对占size更大的code, 但功能没问题的，先把size占了，等后面不够了，把这段代码优化一下，size又挤出来了）

它通常被实现为一个优化转换的序列，该序列将会把程序转换成语义上等价的一个输出程序。该程序执行会更快或消耗更少的资源。（以LLVM为例，IR级别的优化就是一个或多个PassManager中代表的所有Pass集合）

根据优化所作用的域来分类，可以有如下类型

通过检查一些相邻的指令（像通过一个小孔一样窥视整体代码）来看，它们是否可以由另外一个或一组更短的指令代替。

常见的有，Strength reduction, 代数简化，等等。

局限于某个Basic Block的优化。

利弊：分析少，时间少，内存需求少，信息不会在Basic Block块之间共享。

又称“intraprocedural methods”, 它会在整个函数上进行优化。

全局优化会遇到的问题：1) 出现函数调用，2)出现全局变量的访问

让编译器可以调整指令来保持同步程序的语义。

BOLT, 通过对机器码二进制级别的分析来优化binary.

某些特点的语言特性会让某些优化变得很困难。比如说C/C++中的指针，会让别名分析遇到困难。但是对于函数式编程语言，由于它没有副作用，所以对于某些优化又很简单。

很多最有效的优化是探索了目标平台的特定特性的优化。

比如，对于寄存器赋值0这个操作，机器码可以有两种方法。1）使用立即数往register中填值 2）使用Xor 指令。对于RISC, 这两种方法是一样的。但是对于x86, xor会产生更短的指令，且可能更快（不需要decode立即数或使用立即数寄存器）

寄存器数量

数量越多，越容易把局部变量，中间值存到寄存器中。

RISC vs CISC

CISC的特征：指令长度可变，指令种类多样，指令执行时间不定

RISC的特征：指令长度恒定，较少的内存和寄存器操作组合，以及当没有内存访问时，指令的每秒执行数是常量（通常是时钟周期的整数倍）

对于CISC, Compiler必须要知道不同指令的开销，以选择正确的组合。

流水线

将指令的执行划分为不同阶段，例如，decode指令，decode地址, 内存访问，寄存器访问，计算，寄存器存储，等等。那么，可以同时出现一条指令在寄存器存储，另一条指令在进行寄存器访问。

编译器在流水线中的角色，是重新排序指令，以尽可能减少流水线的停滞。

功能单元的数量

不同的CPU所拥有的ALU和FPU数量是不同的，那么某些处理器就拥有同时执行两个以上计算指令的可能。和流水线类似的，编译器需要利用这一特点，尽可能把各个功能单元给填满指令。

Cache大小

Cached的引入是为了解决程序的locality问题而产生的。inline和loop unroll都会破坏这一点。

Cache/Memory速度比率

让Compiler可以更好的知道Cache miss所产生的代价。

调试

为什么调试不需要大多数优化？

1. 程序员经常需要编译和测试
2. 程序经常需要单步执行
3. Reorder code的优化会破坏原有程序的执行流，难于调试

通用目的的优化

为什么需要通用目的的优化？

预先编译的软件通常会运行在相同指令架构的CPU上，但是它们的时钟，Cache大小，内存大小，都不可能完全一样，那么优化就需要针对通用目的。

专有目的优化

只会编译成为某些极为相似的系统，且这些特性都是已知的。比如说支持并行和向量的处理器，编译器要为这些专有的机器生成专有的优化。

嵌入式系统

嵌入式系统对于Flash大小，内存大小有非常高的要求。代码的执行并不是越快越好，只需要满足规定条件，且稳定即可。编译器指针这些特殊的系统需要额外的进行优化。（C++不带有虚函数，继承等约定）

Optimizing编译器一般都会试图从以下的这些方向来进行优化。

它独有的一点是，它允许牺牲一条较慢的路径，来提升一条较快的执行路径。当较快的执行路径，执行的次数更多的话，整体的性能就可以得到提升。（likely, unlikely）

复用计算所得的结果。GVN

移除不必要的计算和中间值

跳转会影响指令流水线。inline和loop unroll都可以减少跳转。

在时间上紧密相邻的代码和数据，在内存上要放的尽可能近以增强locality.

各级存储器拥有不同的访问速度，尽可能利用好寄存器，缓存，内存和磁盘。

Reorder操作以允许计算并行执行，不管是在指令，内存，还是线程级别。

PGO

用开销更小的操作来替换

Common CSE

Constant folding and propagation

Induction variable recognition and elimination

Alias classification and pointer analysis

Dead store elimination

Global Value Numbering

Sparse conditional constant propagation

Register allocation

Instruction Selection

Instruction Scheduling

Rematerialization

Code factoring

机器码的合并

Trampolines

Reordering computations

Tail call optimization

Deforestation (data structure fusion)

Partial evaluation

Bounds checking elimination

Branch offset optimization

Code-block reordering

Dead Code elimination

Factoring out of invariants

Inline expansion

Jump threading

Macro compression

Reduction of cache collisions

Stack height reduction

Test reordering

跨过程优化作用在整个程序表示上，它能够跨过函数和文件的边界。它和函数内的优化是紧密合作的。典型的优化有：

Procedure inlining, interprocedural dead code elimination, interprocedural constant propagation, and procedure reordering

同样的，这些优化必须要在分析之后运行。