过程建立一个受控的执行环境，都具有自身私有的局部变量，是大多数编译器工作处理的基本单位。过程有三个关键的抽象：过程调用抽象、命名空间、外部接口。本章专注于编译器实现这些抽象的机制。
面向对象语言和面向过程语言的过程调用的主要差别在于指定被调用者和运行时定位被调用者的机制。
过程的调用和返回通常可以利用栈来模拟。但对于支持闭包的程序语言，调用闭包时，过程在封装的运行时上下文中执行，使用栈不足以实现这种控制抽象。
词法作用域与动态作用域的区别在于自由变量，即在自身作用域之外声明的变量。词法作用域把自由变量绑定到使用位置最接近的同名声明，编译器会从源代码使用处的作用域开始连续检查外层的作用域，直到找到第一个声明。动态作用域将自由变量绑定到程序运行时最近创建的实例上，可以通过一个运行时名字栈来实现。
注意词法作用域规则检查的是源程序中块之间的静态关系，而动态作用域规则依赖的是程序执行时的函数调用顺序。比如下面的例子，不同作用域规则运行得到的结果时不同的。
int x = 1;
int g() { return x; }
int f() {
int x = 2;
return g();
}
f();
为了实现过程调用和作用域，编译器必须建立一组运行时结构，称为活动记录（Activation Record, AR），这是对特定过程特定调用相关联的私有内存区。
举一个可能的 AR 布局方式为例。AR 中包含返回地址、参数信息、局部变量、寄存器保存区、返回值、自由变量、调用者的活动记录指针 ARP，其通过活动记录指针 ARP 加上偏移量来获取 AR 中各个字段。
由于过程通常会频繁访问其 AR，编译器大多数会专门用一个硬件寄存器保存当前过程调用的 ARP。
在 p 调用 q 时，两者之一必须负责保存寄存器，供调用完成后恢复其值。因为 p 的每次激活都存储了不同的寄存器值，因此将寄存器保存在 AR 是有意义的。对于 p，任意时刻仅有一个调用是活动的。因此在 p 的 AR 分配寄存器保存区就足以完成 p 中的所有调用。
p 调用 q 时，调用的代码必须为 q 分配一个 AR，并初始化相关字段。不过 p 可能不知道 q 的局部数据区长度。如果 AR 的相关字段可以通过寄存器传递，则由 q 来实际分配 AR 也是可行的。
大多数变量的生命周期都小于创建变量的过程激活期间，过程激活期也小于其调用者的激活期。这种情况遵循后进先出，因而可以采用基于栈分配的 AR。这种方式的分配和释放操作比较廉价，只需要对栈顶的值进行算术操作。设置 AR 的工作也可以从调用者开始，调用者分配不包括局部数据在内的空间，由被调用者通过递增栈顶指针来扩展 AR 空间。
如果过程的激活期超出其调用者，或者过程返回的对象引用了已返回过程的局部变量，此时采用基于堆分配的 AR，如 Scheme 和 ML 的实现。
叶过程是不包含过程调用的过程。编译器可以为叶过程静态分配 AR 以消除运行时分配的代价。如果语言不允许闭包，那么执行期间的任意时刻，至多只有一个叶过程是活动的，编译器可以为所有叶过程静态分配单一的 AR。这个静态 AR 必须足够大以容纳任一叶过程。
如果一组过程总是按照固定的序列调用，那么可以合并其活动记录以节省分配操作。不过这种优化受到分离编译和函数值参数的限制。
面向对象语言的命名空间很复杂，一些语言特性，比如虚函数、开放类结构，会导致运行时才能彻底推断命名空间。实现面向对象语言也同样需要运行时结构来支持词法作用域和类层次结构。其中 AR 和过程式语言类似，而为了解决面向对象特定的问题，需要对象记录（object record, OR）来保存每个对象的状态。这部分内容可参考 C++ 类的实现方式。
过程内部声明的局部变量通常存储在 AR 中，因此它们具有动态的地址。为了访问这些值，编译器必须构建一些运行时数据结构，把静态坐标 (level, offset) 转成运行时地址。这里有两种方式：存取链（access link）和 GD （Global Display）。存取链把所有的 AR 串成链表，遍历链表直到找到变量对应的 ARP 及偏移。GD 方案会分配一个全局数组 display，保存各个词法层次上最新激活的过程的 ARP，这样静态坐标可以访问标量的时间代价是固定的，但是需要维护 display。
本章关注实现源语言中各种结构的方法，这些实现的具体细节会影响到编译器在后续各趟处理中分析和改进代码的能力。不同的实现方法使用的内存、寄存器、耗能各异，这些区别源于代码形式的不同。
比如所要实现条件位单字节字符值的 switch 语句，可以用一系列的 if 判断来实现，这将退化为线性查找。也可以用二分查找，这会快不少。如果要利用空间换时间，则可以构建一个哈希表，这样查找的时间是常数级的。对于特定的 switch 语句来说，判断使用哪种方法取决很多因素，最重要的是 case 的数目和相应的执行频度。
考虑另一个例子 x + y + z，源代码可以映射为求值顺序不同的一系列二元加法操作。编译器需要知道表达式的上下文，才能选择最佳的求值顺序。
编译器必须为代码中产生的值分配存储位置，因此必须了解该值的类型、长度、可见性和生命周期。除此之外，还要考虑内存的运行时布局、源语言对数据区和数据结构布局的约束、目标处理器对数据位置或使用的约束。
编译选项也可能影响到值的放置。比如调试需要保留所有调试器可以引用的名字。
编译器会使用两种常见的内存模型来确定将值保持在寄存器还是内存中，分别是内存到内存模型和寄存器到寄存器模型。内存到内存模型假定值都在内存中，按需加载到寄存器，定义后写回内存。IR 通常使用物理寄存器名，编译器确保对寄存器的需求不会超出实际寄存器。？寄存器到寄存器模型假定有足够的寄存器，仅在必要时将虚拟寄存器的值写回内存。
内存模型的选择会影响到编译器的结构，比如内存到内存模型中，寄存器分配器是一种可选优化。而寄存器到寄存器模型中，寄存器分配器是必须的。
程序地址空间布局、操控和管理的许多决策超出编译器的范围，与操作系统和处理器相关。最常见的一种程序地址空间布局，从低地址到高地址分别是：代码、静态或全局数据、堆、空闲内存、栈。
为方便起见，编译器会把同样生命周期和可见性的值都放在一个位置，由此划分不同的数据区。比如过程局部变量放置在过程活动记录内部，过程静态局部变量放在内存中的静态区域。
对于每个数据区，编译器必须计算出一个布局，为其中的变量分配偏移值。目标机的 ISA 可能会限制这些偏移值，要求遵守对齐规则。
对于代码中使用位置接近的两个值，编译器最好能够把两者都加载到高速缓存中。最佳情况下是两者在同一缓存块中。如果不能，则可以通过控制变量地址的距离来让两者映射到不同缓存行。？逻辑地址到物理地址的映射不一定会保持特定变量之间的距离。因此编译器对于不同内存页上两个变量的布局几乎是不起作用，应该专注于让同时被引用的对象放置在同一内存页。
寄存器到寄存器模型中，编译器只保持无歧义的值，直到定义另一个有歧义的赋值。除非能证明两个值指向的地址集合不相交。比如 C 语言中，局部变量只要没有被获取过地址，那它就都是无歧义的。？更复杂的分析需要对每个指针建立潜在名字的集合，如果集合只有一个元素，则无歧义。
语言特性会影响到编译器分析歧义的能力，比如 C 语言的 restrict 关键字可以通知编译器某个指针是无歧义的，volatile 关键字可以通知某个变量可能发生改变。
许多问题都会影响到代码生成的质量。比如数据存储位置不同，生成的加载指令数目也不同，使用的寄存器数目也不同。即使存储位置相同，不同的代码形式也会影响到对寄存器的需求。
比如 a - b * c。假设数据都在内存中，且按照树后序遍历的方式生成代码。从左到右遍历和从右到左遍历生成的代码经过寄存器分配器优化后，所需的寄存器数目不同。
在生成代码的阶段，以上面的例子，我们生成的加载指令是
loadI @a -> r1
loadA0 rarp, r1 -> r2
而非 loadAI rarp, @a -> r2，这有几个原因：
在优化阶段，编译器可能通过发现的知识将两条指令合并为单个指令。但更好的做法是将该问题推迟到指令选择器，将第二个原因中与机器相关的因素隔离到编译器处理机器相关的阶段。
为了选择一种能够减少寄存器使用量的求值顺序，必须不断交换左右子树并计算可能的改进。一般来说，只要对每个节点中使用寄存器数最大的子树先求值，就能最小化寄存器的使用。因此要求对代码进行两趟处理，先计算寄存器使用量，然后输出处理后的代码。
重排表达式可以暴露出一些额外的优化机会。但是由于精度的限制，浮点数表达式不应该重排，除非语言定义允许这么做。
函数调用的存在，可能会限制编译器改变表达式顺序的能力，因为函数可能有副作用，可能修改其他变量的值。这促进过程间分析的大部分工作。
布尔值有两种表达方式：数值编码和位置编码。前者为 true 和 false 分配具体的数值。后者通过代码不同分支控制流来表示求值结果。如果布尔表达式的结果不需要存储，则使用位置编码是有意义的，否则选择数值编码方案。
目标机指令集的具体细节会影响到关系运算的实现方式，其中有几种方案：直接条件码、条件复制、布尔值比较和谓词操作。
直接条件码中比较操作会设置一个条件码寄存器，只有条件分支操作能够读取寄存器的值。优势在于一些处理器能够通过算术运算来设置条件码，这样可以避免比较操作。？
条件复制方案为模型增加一个条件复制的指令，这样可以避免比较操作和分支，但是会对指令中的两个表达式都求值。对于要求短路求值的语言，这可能带来风险。
布尔值比较和直接条件码类似，不过它对关系运算求值可以无需分支操作。缺点在于总是需要显式的比较操作。
谓词执行模型中，目标机可以在指令前加一个谓词表达式来决定指令是否生效。这种方案生成的代码精炼，但在一些场合下，不如其他采用分支的方案，这在后面小节会谈及到。
本节介绍几种在内存中布置数组的方案。
考虑引用一维数组的元素，如果我们使用基地址加偏移量的寻址方式，以及使用零作为索引下界，那么可以简化代码。如果编译器不知道数组的上下界，那么可以在运行时计算数组的虚零点。像 C 语言则采用另一种策略，强制使用 0 作为数组下界。
多维数组有几种实现方式：行主序、列主序和间接向量。间接向量像拉链法的哈希表，优点在于容易实现不规则数组。
数组作为参数传递时，通常采用引用的方式。编译器需要在被调用者中将引用绑定到对应的形参，因此需要数组引用的各维度信息。Fortran 中要求程序员在声明数组时指定维度。其他的一些语言则时会收集必要的信息留给编译器处理。比如编译器会建立一个描述数组信息的消息矢量（dope vector），在被调用过程的 AR 中为该数据结构分配空间，而实参传递的值时指向该数据结构的指针。
访问检查最简单的实现就是在数组引用前都加一个条件判断，则可能需要在信息矢量中加入额外的信息。这种方式开销可能很大，也有一些技术可以降低范围检查的开销。也有一些其他的实现方式，比如让编译器证明给定的引用不会产生越界访问。
必须为字符串选择一种表示，所选方法对字符串操作的性能有巨大影响。考虑两种方式，一种是 C 语言的以 \0 结尾的方式，另一种是长度+数据的方式。当对字符串执行操作，比如查询长度，这两种方式的性能就不同。
编译器必须知道结构体的起始地址和每个结构成员的长度及偏移，可以通过建立一个表来保存这些结构布局的信息。布局必须遵守目标体系结构的对齐规则，如果源语言不允许用户定义结构布局，则编译器可以按任意顺序布局，以缩小结构空间占用。
对于联合这种结构，有几种实现方案。比如源语言强制程序员使用无歧义的引用。另一种方案是，联合中有个字段 tag 用于区别不同变体，由运行时进行标记和判断。
在条件执行语句中，随着 then 和 else 代码的增长，内部代码高效执行的重要性开始超过控制表达式执行的代价。假设 then 和 else 都包含 10 条独立的操作，在双发射机器上，支持谓词执行的方式会使每个 false 的操作都占用一个发射槽，这导致每个分支都需要 10 个周期。而不使用谓词方式，采取分支跳跃则能使每个分支都只需要 5 个周期。
因此实现条件判断语句方案中，选择分支还是谓词需要考虑：
循环结构都有一个相似的结构，也有一些优化的地方。比如可以使用循环体中的指令来填充延迟槽、常量折叠以消除部分分支甚至循环本身。
许多程序语言都有包含 case 语句的变体，比如 Fortran 的 goto，C 语言的 switch。case 语句的复杂点在于，如何高效定位目标 case 子句。有三种策略：线性查找，二分查找和直接计算地址。
编译器前端将源代码转换为某种 IR， 后端将 IR 转换为某种可以直接在目标机上执行的形式。两个过程之间就是编译器的中间部分优化器，负责转换前端产生的 IR，以提高后端生成代码的质量。
代码优化需要在编译时发现程序运行时行为的信息，并利用其来改进生成的代码。改进有多方面，除了执行效率，还有代码长度、能耗、对实时事件的响应、内存的访问量等。
有很多因素能够带来优化的机会。低效性主要来源是对源语言抽象的实现。因为源语言转换 IR 是个局部的过程，不能对上下文进行广泛分析，生成的 IR 是处理源语言结构的最一般情形。另一个重要来源在于目标机影响性能的属性，比如功能单元的数目和能力、内存层次结构中各个层次的延迟和带宽，指令集寻址方式等等，这些都会影响编译器为有特定需求的程序生成代码的方式。
早期，人们将优化看成编译器的可选特性，这带来了调试编译器和优化编译器的区别（-O0、-O3）。现代优化器假定后端会处理资源分配的问题，因此优化器通常是对具有无限寄存器、内存和功能单元的理想机器进行优化。
举个计算数组地址的例子。考虑前端对 Fortran 数组引用 m(i, j) 先列后行生成的 IR。如果不了解 m、i、j 的具体知识或上下文，那编译器必须生成寻址二维数组的完整表达式：@m+(j-low2(m))(high1(m)-low1(m)+1)w+(i-low1(m))*w。@m 是第一个元素的运行地址，lowi(m) 和 highi(m) 是 m 第 i 个维度的下界和上界（即以 0 起始？维度大小？），w 是一个元素的长度。
如果 m 是局部变量，各维度下界为 1 且上界已知，则编译器可将计算数组地址的表达式简化为@m+(j-1)high1(m)w+(i-1)*w。
如果数组引用出现在循环内，且在循环中 j 从 1 变动到 k，则可以利用运算符强度削减（Operator Strength Reduction）进行进一步优化。即 (j-1)high1(m)w 将替换为序列 j1’ j2’ j3’ …，ji’=ji-1’+high1(m)*w。 如果 i 也是个循环的归纳变量，也可同理进行优化。
如果 m 是过程实参，那么编译器可能无法在编译时获取相关知识，因为在过程的不同调用中，m 的上下界可能是变化的，因此无法像上文一样简化地址计算。
接下来举 LINPACK 库中循环嵌套的一个例子，库作者做了对外层循环进行展开，把多个赋值合并为一条语句。理想情况下，编译器会自动将原本循环嵌套的代码变换为循环展开或其他更适合目标机的形式。但很少有编译器包括了完成该目标的所有优化。
对于循环展开的版本，从编译器角度来看，语句中包含很多不同的数组地址的计算，应该简化这些计算。比如对于地址计算中内层循环的不变量，可以保持在寄存器中。 如果目标机有等价于 loadAI （使用寄存器基地址和常数偏移量寻址）的指令，那么可以对地址引用进行重构，使用相同的基地址与不同的常数偏移量进行表示。
如果编译器不能执行上述优化，那么循环展开的版本可能生成更差的代码。比如如果无法重构地址表达式，那么需要维护多个归纳变量，迫使寄存器分配器在循环中插入额外的 load 和 store 指令。
每种优化都需要保证安全性和可获利性，既能保持原有语义，又能提高程序性能。比如刚刚的循环展开例子，减少了循环控制的开销，循环中执行一次内存操作能够执行更多工作，受限于内存的可能性较小。在一个循环中，如果 load/store 指令耗费的周期数多于计算指令的耗费，则认为该循环是受限于内存的。
循环展开也能帮助编译器做其他优化，展开会增加内层循环代码的数量，为指令调度器提供隐藏延迟的机会。如果循环末尾的分支指令延迟很长，则较长的循环体使编译器能够填充分支延迟槽中更多的部分。在一些处理器上，不使用的延迟槽会用 nop 填充，循环展开可以减少处理器取到的 nop 指令数目。
总结一下，可供优化编译器利用的时机有几种不同的来源：
刚刚的例子是对单一数组引用以及循环嵌套的优化，然而优化还可以在更大的范围上，不同的粒度上进行，比如局部的、区域性的、全局的、整个程序。
局部优化作用于单个基本块。基本块保证语句顺序执行、除非运行时异常否则任一语句执行整个基本块也执行。因此编译器能够利用这两个性质来证明更强的事实，做出在更大范围上无法达到的优化。
区域性的作用范围大于单个基本块小于一个完整的过程。与整个过程相比，区域性有时能够进行更好的优化。比如循环嵌套内部，编译器能够证明一个大量使用的指针是常量，尽管该指针在过程中的其他位置会被修改。因此在该区域中的指针引用的值可以保持在寄存器中。
全局方法又称为过程内方法，作用在整个过程上。因为局部最优的优化在更大的上下文中可能不是最优。
过程间方法考虑的范围大于单个过程，也带来新的挑战。过程间优化两个经典例子是内联替换（inline substitution）和过程间常数传递（interprocedural constant propagation）。
随着优化范围加大，优化时机也更多，但分析较大范围代码得到的知识通常不怎么精确，因此优化范围与生成代码质量并不存在一个简单的关系。
本节介绍两种局部优化方法：值编号（value numbering）和树高平衡（tree-height balancing）。值编号用于重用计算过的值来替代冗余表达式，树高平衡用于重新组织表达式以带来指令层次的并行性。
局部值编号 考虑下面的基本块，第四条语句是冗余的。
a = b + c
b = a - d
c = b + c
d = a - d
我们可以把第四条语句替换为 d = b。或者可以把后续代码使用 d 的地方都替换成 b，但这种方法需要确定在每一处 d 的位置上 b 是否被修改。一个简单的解决方法是，在使用前插入复制操作，由后续的一趟 pass 来判断复制操作是否必须，是否可以合并。
将冗余替换为之前计算的值并不总是可获利的。比如上面的例子，替换成 d = b 可能会延长 b 或缩短 a 和 d 的生命周期，导致影响到对寄存器的需求。然而代码到达寄存器分配器前还会有很多变换，因此优化器无法预测寄存器分配器的行为，于是总是假定删除冗余是可获利的。
刚刚的例子中，冗余表达式的文本是相同的。再看下面的例子，冗余表达式的文本是不同的。
a = b * c
d = b
e = d * c
因此依赖于文本相同的技术在这里不可行，必须跟踪值通过名字发生的流动。
现有包含 n 个 T = L Op R 表达式的基本块，基本的局部值编号（Local Value Numbering, LVN）算法会维护一个哈希表，并按顺序处理基本块中每个表达式。对于第 i 个操作，从表中获取 L 和 R 的值编号，然后基于两者的编号和 Op 一起构造 T 的哈希键，接着在表中查找该键。如果找不到则在表中插入哈希键和新的值编号对，并将新的值编号赋予 T。 则说明该表达式是冗余的，可以替换为查找到的值编号，同时也要把该值编号赋予 T。
注意这里不是根据文本计算出哈希值，而是根据编号。因此不同变量具有同个编号（即值相同）就可以得到同个哈希值。
表达式的顺序对于分析冗余的结构有直接的影响。考虑 v = a * b * c 和 v = a * (b * c) ，如果 b * c 在上下文出现过，则右边表达式将产生冗余而左边不会。如何重排表达式以提高优化的效果，通常从采用启发式技术，因为重排表达式的方法太多了。
一些优化的点：
考虑下面的例子，如果尝试运用刚刚的 LVN 算法，会有一些问题。
a = x + y
b = x + y
a = 17
c = x + y
在第四个表达式中，无法将表达式重写为 c=a，因为 a 的值编号已经变了。有两个方法来解决这个问题：
前面的讨论都基于直接的赋值，但是对于间接赋值，如指针、结构体或数组赋值的情况，会导致编译器对值流动的推测出错，是值编号及其他优化变复杂。考虑刚刚下标命名方案的值编号算法，当 *p = 0 时，编译器不知道 p 可能指向的内存位置，不知道应该递增哪个变量的下标，因此只能对所有可能被修改的变量下标。再比如 a(i, j) = 0，如果 i 或 j 时未知的，那只能假定赋值操作改变了 a 中所有元素。
树高平衡 现代处理器有多个功能单元，可以在每个周期执行多个独立的操作。如果编译器可以通过编排指令流使之包含独立的多个操作，那么程序会运行得更快。考虑表达式 a+b+c+d+e+f+g+h，如果处理器每次可以执行多个加法，那么可以按照 ((a+b)+(c+d))+((e+f)+(g+h)) 顺序来编码指令。
树高平衡算法分为两部分：分析和变换。分析用于确定基本块中的候选表达式树有哪些。候选树中，所有的运算符相同且可交换和可结合的，而且内部节点的名字都只使用一次。变换类似于构建哈夫曼树，会从存放子树的优先队列中，依次取出权重最小的两个进行合并再放回，直至生成最终的平衡树。
基本块中的展现值（exposed value）指的是在基本块后被使用，或者在基本块中被使用超过一次的值。如何获得基本块中的展现值，可以通过计算 LiveOut 集合获得。
分析阶段会遍历基本块中的表达式。比如分析到 T = L Op R，会判断 T 是否展现值。如果是展现值，则将 T 及 Op 的运算优先级一起加入到以 Op 运算优先级为权重的队列中，作为候选表达式树的根节点。
比如现有基本块如下，这里的展现值有 t3, t6, t7, t10, t11
t1 = 13 + s
t2 = t1 + t
t3 = t2 + 4
t4 = t3 * u
t5 = 3 * t4
t6 = v * t5
t7 = w + x
t8 = t7 + y
t9 = t8 + z
t10 = t3 * t7
t11 = t3 + t9
分析阶段得到的优先队列包含 (t11,1), (t7,1), (t3,1), (t10,2), (t6,2)。
变换阶段会遍历分析阶段得到的优先队列。对于每个队列元素，即候选表达式树的根节点，会维护另一个以操作数为权重的优先队列。递归候选表达式树，获得每个操作数并为之赋予权重加入队列中。如果该操作数是常数，则权重为 0；操作数是叶子节点，权重为 1；操作数是另一候选表达式树的根节点，则递归获得权重；否则是中间节点，则权重为左右子树权重之和。
如上面的例子中，首先会对优先队列中 t11 进行变换，获得操作数及其权重，(z,1),(y,1),(t7,2),(t3,2)。这里 t7，t3 的权重会通过递归，变换获得。
候选表达式树获得的操作数及其权重，就会按照类似于构建哈夫曼树进行重建。例子中，t11 候选表达式树就会变成：
n1 = z + y
n2 = n1 + t7
t11 = n2 + t3
例子中最终生成的代码如下：
n0 = 17 + t
t3 = n0 + s
t7 = x + w
n1 = z + y
n2 = n1 + t7
t11 = n2 + t3
t10 = t7 * t3
n3 = 3 * v
n4 = n3 * u
t6 = n4 * t3
可以看到，在变换阶段也能实现像 LVN 的常量折叠的效果。
本节介绍两种作用于多个基本块的优化技术。从局部优化到区域优化，主要的复杂之处在于处理控制流的不同路径。
超局部值编号 Superlocal Value Numbering，SVN。思路在于将多个基本块当成一个基本块，当成直线式代码进行局部值编号。这要求除了第一个基本块，其他基本块都不能有多个前趋。
难点在于如何高效地处理，因为处理多条包含同个基本块的路径，都会重复分析该基本块。因此我们需要重用分析过的结果，这里有三种方式：
第三种比较简单和快速，因为能重用编译器前端实现作用域的代码。不过有一些问题，名字的值编号是记录在定义该名字基本块的哈希表中，而后续基本块为该名字计算的新值编号也记录在原本哈希表中，撤销后续基本块的哈希表会导致新值编号仍然存在。
为避免这种情况，可以在只定义名字一次的表示法，比如 SSA，上运行 SVN 算法。
循环展开 减少控制流的分支数，循环体内部产生重用，减少内存访问。但也有一些缺点，比如增大程序的长度，增大编译时间，可能会撑爆指令高速缓存。
循环展开也有一些间接的影响，比如
要预测这些间接影响很困难，一般使用自适应方法，由展开因子来确定。
作用于整个过程上。由于作用域包括有环的控制流，所以通常会先进行一个分析阶段。本节介绍两个例子。
利用活动信息查找未初始化变量 严格来说这不是优化。它使用全局数据流分析技术来揭示过程中值流动的信息。对于其他优化都有帮助。
如果过程 p 在为变量 v 分配值之前就使用了 v 的值，则 v 在被使用时是未初始化的。通过计算活动情况的信息，我们可以找到这些未初始化变量。
CFG 中存在一条从 p 到使用 v 的某个位置之间的路径，且 v 在该路径中没有被重新定义，则 v 在 p 处是活动的。我们把每个基本块的活跃变量记录到集合 LiveOut 中，LiveOut(b) 包含基本块 b 退出时所有的活跃变量。也就是说，集合中变量的值在后续基本块会被用到。
计算 LiveOut 集合的公式如下，其中 UEVar(m) 包含在 m 中重新定义前就被使用的变量，VarKill(m) 包含 m 中定义的变量。
$LiveOut(n) = \cup(UEVar(m) \cup (LiveOut(m)-VarKill(m))),m \in succ(n)$
可以看出，这是一个反向数据流的问题，我们可以通过迭代不动点的方式来为每个基本块计算出 LiveOut。
当计算出 LiveOut 集合，查找可能的未初始化变量就简单了。如果 n 是 CFG 的入口结点，则 LiveOut(n) 中的值都可能会是未初始化。
识别未初始化变量可能会出错：
如果分析的过程又调用另一个过程，而在缺少被调用者信息的情况下，只能假定每个可能被修改的变量会被修改，每个可能被使用的变量会被使用。
活跃变量的信息可以在很多优化中被使用，除了之前说的树高平衡，还有寄存器分配（除非值是活跃的，否则不必保持在寄存器中）、SSA 的构建（基本块中的不活跃的值，不需要插入 phi 节点？）、发现无用的 store 操作（如果值是不活跃的，则不需要存储到内存）
全局代码置放 许多处理器的分支指令代价不对称，比如落空分支（控制流直接往下走）比采纳分支（控制流需要跳跃到该分支）更快。因此需要移动代码，让执行频度更高的分支控制流走落空分支。
代码置放具有独立的分析和变换阶段。分析阶段收集分支执行频度数据，变换阶段利用这些数据来对基本块进行排序。
收集剖析信息有几种方式：
编译器应该统计 CFG 各条边的执行次数，而不是基本块的执行次数。如下图，左边能够判断出 (B1,B3) 作为落空分支会更好。而如果按照右边基本块执行次数的方式统计，则 B3 和 B4 会具有同等重要性。
B0 B0 10
│ │ │ │
7┌──┘ └─┐3 ┌──┘ └─┐
│ │ │ │
▼ ▼ ▼ ▼
B1 B2 7 B1 B2 3
│ │ │ │ │ │
5┌┘ └──┐ ┌─┘ ┌┘ └──┐ ┌─┘
│ 2 │ │3 │ │ │
▼ ▼ ▼ ▼ ▼ ▼
B3 B4 5 B3 B4 5
│ │ │ │
5└─┐ ┌─┘5 └─┐ ┌─┘
▼ ▼ ▼ ▼
B5 B5 10
10 │ │
▼ ▼
得到每条边的执行次数后，就需要构建出执行最频繁的路径，即热路径。这里使用贪婪算法，按照执行频度从高到低的顺序选择边 <x, y>，如果有以 x 为结尾块、以 y 为起始块的两条路径，则会合并为新路径，新路径的优先级取两条路径的最小值。初始情况下，每条路径的优先级可以设置为一个大数 E，当合并两条初始的路径，优先级为已经合并的数目。
刚刚的例子计算的热路径如下：
| 选择的边 | 路径集合 | 已经合并的数目 |
|---|---|---|
| - | (B0)E, (B1)E, (B2)E, (B3)E, (B4)E, (B5)E | 0 |
| (B0,B1) | (B0,B1)0, (B2)E, (B3)E, (B4)E, (B5)E | 1 |
| (B3,B5) | (B0,B1)0, (B2)E, (B3,B5)1, (B4)E | 2 |
| (B4,B5) | (B0,B1)0, (B2)E, (B3,B5)1, (B4)E | 2 |
| (B1,B3) | (B0,B1,B3,B5)0, (B2)E, (B4)E | 3 |
| (B0,B2) | (B0,B1,B3,B5)0, (B2)E, (B4)E | 3 |
| (B2,B4) | (B0,B1,B3,B5)0, (B2,B4)3 | 4 |
| (B1,B4) | (B0,B1,B3,B5)0, (B2,B4)3 | 4 |
计算出热路径后，就进行代码布局。取出第一条热路径放入 WorkList，把路径中的基本块顺序放置。同时与该路径中基本块相关的路径也加入 WorkList。按照优先级从小到大的顺序取出另一条热路径放置代码，直至 WorkList 为空。于是例子中放置的结果为 (B0,B1,B3,B5,B2,B4)
过程调用对于编译器生成高效代码有利有弊。从正面看，限制编译器需要考虑的代码数量。从负面来看，限制了编译器理解调用过程内部行为的能力，引入了调用者调用前返回后的代码、被调用者起始收尾代码的开销。
为支持过程间分析，编译器的结构也需要改变。因为对于传统的编译器来说，编译单元生成的代码只取决于该内容，一旦要支持过程间分析，生成的代码就需要同时取决于多个编译单元。这也带来一些依赖性，对某个编译单元的修改可能导致需要重新编译其他单元。
为让编译器能够访问其需要的所有代码，提出了几种编译器结构：
接下来介绍两种不同的过程间优化技术
内联替换 为实现过程调用会有很多额外的操作：分配活动记录、实参求值、保存调用者状态、创建被调用者环境、控制转移、返回值传递。编译器可以通过内联替换减少这些开销。
内敛替换有两个问题，变换和决策需要变换的过程。
变换相对简单，但仍有一些注意的点。一些源语言结构可能导致内联的代码控制流很复杂，比如多个过早的返回语句，或者 Fortran 的交替返回（alternate return）特性，都会使控制流图变得复杂。
除此之外，也要注意内联后局部变量变多的问题。考虑内联过程的一个简单实现，在被调用点处为过程的局部变量创建对应的局部变量。这时如果内联多个过程，或者在几个调用位置内联同一个过程，会有局部变量太多的问题。这不是一个正确性问题，但会影响其他的优化过程。其实这里我们只要能够做到重用局部变量就可以了。
决策过程比较复杂且对性能有直接影响。内联过程不一定都会提高性能，比如会增加代码长度和命名空间规模，影响到寄存器的需求。因此有多个方面来考虑是否需要内联替换：
一般编译器会采用启发式决策来决定是否内联替换
过程置放 思想很简单，当过程 p 调用 q，我们希望 p 和 q 占用相邻的内存位置，才能更好地利用局部性。同样，这个算法也类似于上面见过的全局代码置放，由分析和变换两个阶段组成。
分析阶段统计出每条调用边的频度。变换阶段按照频度从高到低的顺序依次取出边 <x, y>，把过程 y 的代码放置 x 之后，合并 x 和 y 为一个节点。合并可能需要修改与 x 和 y 相关的其他边的指向及边的频度。当每条调用边都处理完，调用图就已经被合并为一个节点，所有过程的置放顺序也就确定了。
编译器使用数据流分析来确定可进行优化的机会，并证明特定变换的安全性。
如果从入口结点到某结点 B0 的所有路径上，都包含结点 B1，则 B1 支配 B0。记集合 Dom(b) 包含支配 b 的所有结点的名字，则 $Dom(n) = {n} \cup ( \cap Dom(m)), m\in preds(n)$。初始条件是：Dom(n0)={n0}，且对其他结点 n，Dom(n)=N，N 是所有结点的集合。
根据定义，结点支配本身。若 $a \in DOM(b)-{b}$，则 a 严格支配 b。
该算法具有可停止性、正确性、不动点解的唯一性，该解与求解过程中计算的次序无关，因此可通过改变计算次序来提高效率。
| 后序遍历优先访问结点的直接点，而逆后序遍历相反，它的访问次序编号是 | N | +1 减去后序遍历编号。 |
对于正向数据流问题（如 Dom），应该使用在 CFG 上计算得到的逆后序顺序（RPO）。对于反向数据流（如 LiveOut），应该使用在反向 CFG 上计算得到的 RPO 顺序。一个 CFG 上计算出的 RPO 顺序可能有多个，不过对于算法而言，它们是等价的。
反向 CFG 将原 CFG 的各条边反向，可能需要向原 CFG 添加唯一的出口结点，使得反向 CFG 有唯一的入口结点。注意，反向 CFG 的 RPO 不等价与 CFG 的逆先序。
如果程序点 p 处的变量 v 可以在 CFG 图中，以 p 为起始点的某条路径中被使用，则称其在程序点 p 上 live，否则为 dead。用 LiveOut(n) 来表示 n 代码块出口处的活跃变量集合。求解方程为 $LiveOut(n) = \cup(UEVar(m) \cup (LiveOut(m)-VarKill(m))),m \in succ(n)$。初始条件是对于所有结点 n，LiveOut(n)={}。
可用于寄存器分配，dead 变量不会被之后代码使用到，因此可以将 dead 变量移出寄存器。
程序点 p 处的表达式 x op y 是 available（可替换）需满足 2 个条件：
对于每个节点 n，用集合 AvailIn(n) 表示 n 对应程序块入口处所有可用表达式的名字。求解方程为 $AvailIn(n)=\cap(DEExpr(m)\cup(AvailIn(m)-ExprKill(m))),m \in preds(n)$。初始条件 AvailIn(n0)={}，AvailIn(n)={all expressions}
可用于进行全局冗余消除（全局公共子表达式消除）。实现全局冗余消除可计算每个程序块的 AvailIn 集合，然后在局部值编号算法中使用。或者使用缓式代码移动来进行公共子表达式消除。
变量 v 的一个定义 d 能够达到操作 i，当且仅当 i 读取 v 的值，且存在一条从 d 到 i 的路径，该路径没有定义 v。我们用 Reaches(n) 来表示能够到达代码块 n 入口处的定义集合。求解方程为 $Reaches(n)=\cup(DEDef(m)\cup(Reaches(m)-DefKill(m))), m \in preds(n)$。初始条件是对于所有结点 n，Reaches(n)={}。
可达性分析可用于查找未初始化变量。具体操作为每个变量都在第一行之前加一个 dummy 定义。对于每个块，其 Reaches(n) 包含该 dummy 定义，则该块可能会使用到未初始化变量。
表达式 e 在 程序块 b 的出口处被认为是可预测的，当且仅当：
我们用 AntOut(n) 表示代码块 n 出口处的可预测表达式集合，求解公式为 $AntOut(n)=\cap(UEExpr(m)\cup(AntOut(m)-ExprKill(m))),m \in succ(n)$。初始条件 AntOut(nf)={}，AntOut(n)={all expressions}
可预测分析的结果可用到代码移动中。如用于缓式代码移动来减少执行时间、代码提升来减小编译后代码长度。
在缺少关于特定调用具体信息的情况下，编译器必须做出最坏情况假定。为了避免这种情况，编译器可以在每个调用位置上计算综述信息，如计算可能被调用修改的变量、计算可能是调用结果的变量。
过程间可能修改问题是程序调用图上的一组数据量方程，为每个过程标注一个 MayMod 集合，方程为 $MayMod(p) = LocalMod(p) \cup (\cup unbind_e(MayMod(q))), e \in (p,q)$。LocalMod(p) 包含在 p 本地修改且外部可见的名字集合，可以通过将 p 中所有定义过的名字减去 p 局部作用域名字计算得到。e 是调用图中从 p 到 q 的一条边，unbind 将名字空间映射到另一个。初始条件把所有过程的 MayMod(p) 都初始化为 LocalMod(p)。
可能修改问题对其他分析，如全局常量传播，生成信息的质量有重要影响。
为限制编译器编写者必须实现和编译器必须运行的分析的数目，我们希望使用单趟分析来支持多种变换。为了实现这种通用分析，一种方式是将数据流和控制流编码到 IR 中，如静态单赋值形式。静态单赋值要求过程中的每个定义都创建唯一的名字，并且每个使用处都引用了一个确定的定义。
一种构建静态单赋值形式的简单方法是：
这种方法构建出来的被称为最大静态单赋值形式，包含过多的 $\Phi$ 函数，可能会引入不活动或不必要的 $\Phi$ 函数（如同个 SSA 名字从不同路径到达 $\Phi$ 函数 $x_j \leftarrow \Phi(x_1, x_1)$）。
为了减少 $\Phi$ 函数的数目，编译器必须理解在每个汇合点哪个变量需要 $\Phi$ 函数，编译器可以使用支配信息来指导 $\Phi$ 函数的插入。考虑 CFG 的结点 n 中一个定义，该值到达某个结点 m 时，如果 n 支配 m， 则该值不需要 $\Phi$ 函数，因为到达 m 的每条路径都经过 n。？仅仅在 CFG 中 n 支配区域之外的汇合点才需要插入 $\Phi$ 函数。
我们将相对于结点 n 具有如下性质的结点 m 的集合称为 n 的支配边界，记作 DF(n)：
非正式的，DF(n) 包含在离开 n 的每条路径上第一个不支配的结点
严格支配 n 的集合中，最接近 n 的结点 m 称为 n 的直接支配结点，记作 $IDom(n)$。将 CFG 中具有直接支配关系的两个结点连起来（如上面的 $m\rightarrow n$），就构成支配者树。Dom(n) 中的各个结点，就是支配者树根节点到 n 路径上经过的所有结点。如果 p 是 IDom(n)，则 p 支配 n 的所有前趋。
为了高效插入 $\Phi$ 函数，我们需要为每个结点计算支配边界。算法基于三个见解：
因此算法如下
for all nodes, n, in the CFG do
DF(n) = ∅
for all nodes, n, in the CFG do
if n has multiple predecessors then
for each CFG predecessor p of n do
runner = p
while runner != IDOM(n) do
DF(runner) = DF(runner) ∪ {n}
runner = IDOM(runner)
有了支配边界之后，编译器可以更加精确地判断何处需要 $\phi$ 函数：若程序块 b 中对 x 进行定义，那么 DF(b) 集合中每个结点的起始处都要有 $\phi$ 函数。注意 $\phi$ 函数也是一个定义，此处插入 $\phi$ 函数可能导致额外插入 $\phi$ 函数。
编译器可以进一步缩小 $\phi$ 函数集合：只在单个基本块活动的变量，就不必有相应的 $\phi$ 函数。因此需要计算出能够跨多个程序块的活动变量集合，称为全局名字集合。这种方式也称为半剪枝静态单赋值形式。
找到全局名字集合的算法如下，Globals 集合包含所有全局名字，Blocks(x) 包含定义 x 名字的基本块。
Globals = Ø
Initialize all the Blocks sets to empty
for each block b
VarKill = Ø
for each operation i in b, in order
assume that i is "x = y op z"
if y not in VarKill then
Globals = Globals ∪ {y}
if z not in VarKill then
Globals = Globals ∪ {z}
VarKill = VarKill ∪ {x}
Blocks(x) = Blocks(x) ∪ {b}
插入 $\phi$ 函数的算法如下
for each name x in Globals
WorkList = Blocks(x)
for each block b in WorkList
for each block d in DF(b)
if d has no Ø function for x then
insert a Ø function for x in d
WorkList = WorkList ∪ {d}
插入算法仅处理全局名字集合，这可以避免插入不需要的 $\phi$ 函数，但仍不足以避免所有不需要的 $\phi$ 函数。编译器可以构建 LiveOut 集合，用于在插入 $\phi$ 函数判断变量的活动性，这种改进方法称为剪枝静态单赋值形式。
在插入 $\phi$ 函数后，我们需要通过给全局名字加上下标，使其变成静态单赋值基本名。具体算法如下
for each global name i do
counter[i] ← 0
stack[i] ← ∅
Rename(root of the CFG)
Rename(b)
for each φ-function in b, "x ← φ(···)" do
rewrite x as NewName(x)
for each operation "x ← y op z" in b do
if y ∈ Globals then
rewrite y with subscript top(stack[y])
if z ∈ Globals then
rewrite z with subscript top(stack[z])
if x ∈ Globals then
rewrite x as NewName(x)
for each successor of b in the CFG do
fill in φ-function parameters
for each successor s of b in the dominator tree do
Rename(s)
for each operation “x ← y op z” in b and
each φ-function “x ← φ(···)” do
pop(stack[x])
NewName(n)
i ← counter[n]
counter[n] ← counter[n] + 1
push i onto stack[n]
return "n_i"
算法先根次序遍历支配者树。对于每个基本块，首先重命名顶部 $\phi$ 函数定义的值，然后按序修改程序块各个操作中的名字。接着重命名 CFG 中后续节点中 $\phi$ 函数的参数。最后递归处理支配者树的子节点。递归调用返回时，会恢复名字空间。
算法中的栈模拟了当前程序块中最新定义的生命周期。如果基本块重复定义同一个基本名，那么栈可以只维护最新的名字，这使得栈的最大长度可预测，不可能比支配者树的深度更长。
因为现代处理器没有实现 $\phi$ 函数，编译器需要将静态单赋值形式转换回可执行代码。转换过程不是简单地去掉变量名下标以及删除 $\phi$ 函数。因为如果代码被重排或者值被重命名过，这种方法会产生错误的代码。
因此，编译器可以 保持 SSA 名字空间不动，将 $\phi$ 函数替换为给当前块的前趋结点末尾增加复制操作。
如果前趋结点有多个后继，那么末尾处插入的复制操作可能导致在其他路径下冗余或不正确的结果。我们把 CFG 图中，这种源结点具有多个后继、目标结点具有多个前趋的边称为关键边。为了解决这个问题，我们可以拆分关键边，往其插入一个新程序块用于复制操作。
但有时候编译器不应该拆分关键边，比如关键边是一个频繁执行循环的控制分支，那么添加包含多个复制操作和跳转操作的程序块，会给性能带来影响。在编译后期添加的程序块和边，也可能干扰到区域性调度、寄存器分配和优化。因此还是需要在能够避免带来错误的前提下，给前趋结点的末尾插入复制操作。而激进的程序变换就可能使插入的复制操作成为错误的代码，考虑下面的程序块，右边是对左边代码做了代码折叠的优化版本。
│ │
▼ ▼
i0 = 1 i0 = 1
│ ┌─────────────┐ │ ┌─────────────┐
▼ ▼ │ ▼ ▼ │
i1 = phi(i0,i2) │ i1 = phi(i0,i2) │
y0 = i1 │ i2 = i1 + 1 │
i2 = i1 + 1 │ │ │ │
│ │ │ ▼ └─────────────┘
▼ └─────────────┘ z0 = i1
z0 = y0
如果对右边的代码转换回可执行代码，那么给汇合代码块的末尾插入的 i1=i2 会导致代码逻辑发生改变。根本原因是代码折叠延长了变量 i1 的生命周期，导致末尾处插入的复制操作导致不正确的结果。
为了避免这种情况，编译器需要检查插入的每个复制操作目标的活动性，将仍然活动的值保存在临时变量，并将后续的引用重写为临时变量。
│
▼
i0 = 1
i1 = i0
│ ┌─────────────┐
▼ ▼ │
i2 = i1 + 1 │
t = i1 │
i1 = i2 │
│ │ │
▼ └─────────────┘
z0 = t
静态单赋值形式转换其他形式还有一些问题，比如交换问题，其原因是 $\phi$ 函数引用同一程序块中其他 $\phi$ 函数。根据定义，所有的 $\phi$ 函数并发执行，转成其他形式插入的复制操作却是顺序执行的，这将会计算得到不正确的结果。如下面的例子，左边代码是用于交换 x 和 y 的代码，中间是 SSA 形式并且复制折叠之后的版本，右边是使用朴素算法插入复制操作得到的版本。
x = ... x0 = ... x0 = ...
y = ... y0 = ... y0 = ...
│ ┌────┐ │ ┌────────────┐ x1 = x0
▼ ▼ │ ▼ ▼ │ y1 = y0
t = x │ x1 = phi(x0,y1) │ │ ┌─────┐
x = y │ y1 = phi(y0,x1) │ ▼ ▼ │
y = t │ │ │ │ x1 = y1 │
│ │ │ │ └────────────┘ y1 = x1 │
│ └────┘ ▼ │ │ │
▼ │ └─────┘
▼
有一种简单的解决方法是采用二段式的复制，先把 $\phi$ 函数的各个参数复制到临时名字，再把临时名字的值复制到 $\phi$ 函数的目标。
在无环的情形下，也可能出现交换问题，不过可以通过对插入复制操作进行排序，来避免该问题。
以上转换过程中出现的问题源自两个原因：转换改变了 SSA 名字的生命周期、转换没有保留 $\phi$ 函数的并行语义。接下来介绍一种三阶段组成的算法来解决这个问题，同时还能够避免分裂关键边
TODO
使用稀疏简单常量传播（Sparse Simple Constant Propagation, SCCP）算法在静态单赋值形式上进行全局常量传播。不同于经典数据流问题，该算法使用了半格（semilattice）的数学概念。
半格由值集 L 和 meet 运算符 ∧ 组成，该运算符必须满足幂等性、交换律、结合律。半格有一个底元素 ⊥ 和一个顶元素 ⊤ 。meet 运算符的规则如下：
SSCP 算法可分为初始化和传播两个阶段。初始化阶段会对每个 SSA 名字 n 计算出 Value(n)，规则如下。传播阶段是一个经典的不动点方案，相比经典的数据流方法，它比较高效，运行在一个特别浅的格上。
具体算法如下
// Initialization Phase
WorkList ← ∅
for each SSA name n do
initialize Value(n) by rules specified in the text
if Value(n) ≠ ⊤ then
WorkList ← WorkList ∪ {n}
// Propagation Phase - Iterate to a fixed point
while (WorkList ≠ ∅) do
remove some n from WorkList
for each operation op that uses n do
let m be the SSA name that op defines
if Value(m) ≠ ⊥ then
t ← Value(m)
Value(m) ← result of interpreting op over lattice values
if Value(m) ≠ t then
WorkList ← WorkList ∪ {m}
注意编译器在使用 meet 运算时必须注意操作符的特点。比如 Φ 函数就仅仅是执行普通的 meet 运算，而对乘法操作进行 meet 运算需要注意参数是否为 0：⊥∧x=⊥，⊥∧0=0。对于加法操作 a+b，如果存在参数格值为 ⊤，则 Value(a+b)=⊤。
举个例子
x0 = 17
│ ┌───────────┐
▼ ▼ │
x1 = phi(x0,x2) │
x2 = x1+1 │
│ │ │
│ └───────────┘
▼
|n| x0| x1| x2| worklist |-|-|-|-|-| |init|17|⊤|⊤|{x0}| |x0|17|17|T|{x1}| |x1|17|17|18|{x2}| |x2|17|⊥|18|{x1}| |x1|17|⊥|⊥|{x2}| |x2|17|⊥|⊥|{}|
因此可得 x0 是常量，x1 和 x2 不是常量
过程调用的低效性在于分析优化中知识的缺失，和维护过程调用的抽象而引入的开销。我们使用过程间分析是为了解决前一个问题。
进行过程间分析的第一个问题是构建调用图。可以为每个过程创造结点，为有调用关系的两个结点添加一条边。但是源语言的一些特性可能使构建调用图的难度大大增加：
概念上，过程间常量传播由3个子问题组成：发现常量的初始集合、围绕调用图传播已知的常数值、对值穿越过程的传输进行建模。
结构性数据流分析和可归约性 前面讨论的大多是迭代算法，但也存在其他数据流分析方法，其中许多算法首先推导出代码控制流结构的一个简单模型，然后再应用求解方程式。如何对图进行一系列变换来降低复杂度，对图进行归约成为核心所在。
非迭代数据流算法从整个流图收集信息并合并，直到归约为一个结点。最后倒转整个过程，从一个结点返回到原始流图，将合并后的集合等效回传到原始的各个结点。
不是所有图都能归约到一个结点。此时必须通过拆分结点来修改流图，或者在部分归约的图上求解方程式。
本章专注于单个控制线程下代码的优化，将识别编译后代码中低效性的 5 种关键来源，然后阐述一组有助于消除这些低效性的优化。
数据流分析发现变换的时机并证明其安全性，优化器使用分析的结果对代码进行重写。优化器会消除由编译语言的抽象引入的不必要开销，还会将结果程序的需求与目标机上可用的软硬件资源相匹配。
大多数优化器都被构建为一系列处理趟。变换的选择和顺序对优化器的整体有效性具有非常关键的作用。各种变换可能具有重叠效应，如局部值编号和超局部值编号。不同效果的变换可能发生相互作用，为其他变换创造、隐藏或者消除应用时机。
假如 r2>0 且 r5=4，则优化器可以将 mult r2, r5 -> r17 替换为 lshiftI r2, 2 -> r17。这将一个多周期整数乘法替换为单周期移位操作，并减少对寄存器的需求，这么看是有利可图的。但是如果后续代码可以依赖乘法的交换律来重排表达式，那么这个优化就关闭一个优化的时机，可能会影响到代码的整体质量。
删除无用或不可达代码可以缩减代码的 IR，这会导致可执行程序更小、编译更快、通常执行更快，还能增强编译器改进代码的能力。比如不可达代码可能会阻碍某些变换，消除之后可以改变分析结果。
消除无用代码的经典算法类似于标记-清除垃圾回收器，它在代码上处理两趟。第一趟清除所有的标记字段，并将“关键”操作均标记为“有用的”。如果一个操作会设置过程的返回值，是输入输出语句，或者会影响从当前过程外部可访问的某个内存的位置中的值，则我们称该操作为“关键的”。接下来，算法将跟踪“有用”操作的操作数，回溯到其定义位置，将操作数标记为“有用”。直至无法将更多操作标记为有用为止。第二趟将遍历代码并删除任何没有标记为有用的操作。
对控制流操作的处理较为复杂，分支（cbr）和跳转（jump）的指令需要做特殊的处理。
每个跳转指令都认为是有用的。
某个有用操作的执行依赖于分支指令时，则该分支指令是有用的。依赖定义为：在 CFG 中，有多条边离开程序块 i，有一条或多条必定经过程序块 j 到达出口结点，也有一条或多条必定不经过 j 到达出口结点，则结点 j 依赖于结点 i。这个依赖的定义就是反向支配边界（RDF）。
在清除操作时，未标记的分支指令被替换成跳转指令，跳转到第一个包含有用指令的后向支配者。这可以通过向上遍历后向支配者树获得包含有用操作的程序块。根据定义，出口程序块是有用的，所以遍历必定会停止。
运行这个算法后，代码将不包含无用计算，但可能包含空程序块，比如跳跃指令指向的程序块，则可以通过下一个算法消除。
本节介绍一个消除无用控制流的简单算法 Clean。该算法直接运行在 CFG 上，按照顺序应用 4 个变换：
Clean 算法按照后根次序遍历流图，因此 Bi 的后继节点会在 Bi 之前被简化，除非 CFG 是有环图。
具体算法如下：
MakeAPass( )
for each block i, in postorder do
if i ends in a conditional branch then
if both targets are identical then
replace the branch with a jump /* case 1 */
if i ends in a jump to j then
if i is empty then
replace transfers to i with transfers to j /* case 2 */
if j has only one predecessor then
combine i and j /* case 3 */
if j is empty and ends in a conditional branch then
overwrite i’s jump with a copy of j’s branch /* case 4 */
Clean( )
while the CFG keeps changing do
compute postorder
MakeAPass( )
Clean 本身不能消除空循环，但通过上一节的消除无用代码算法的协作可以消除空循环。考虑以下图
graph TD
B1 --> B2
B1 --> B3
B2 --> B3
B2 --> B2
如果 B1 和 B3 包含有用操作，而 B2 没有有用操作，则 B2 ∉ RDF(B3)。所以 B2 结束处的分支指令会被转换为跳转指令，指向第一个包含有用指令的后向支配者 B3，这也消除了循环。
可能因为以下两个原因成为不可达代码
第一种情况容易解决，执行简单的标记-清除的可达性分析就可以。第二种情况会困难一点，它要求编译器推断分支表达式的值。
编译器因两大原因而进行代码移动：通过将操作移动到执行次数较少的位置以减少代码的执行时间、将操作移动到能够用单个操作实例覆盖 CFG 中多条代码路径的位置以缩短代码长度。本节将针对这两种情况介绍两个例子。
缓式代码移动使用数据流分析来发现代码移动的候选操作和放置的位置，此领域大部分工作都专注于将不变的表达式从循环中移出。
算法运行在 IR 形式及其 CFG 上，而非 SSA 形式上，这是为了避免 SSA 引入的复杂性。比如移动定义 xi 的操作，可能会导致重命名，或者插入 phi 结点。
如果在到达位置 p 的每条路径上表达式 e 都进行过求值，且 e 的操作数均未改变，则表达式 e 在位置 p 是冗余的。如果在到达位置 p 的部分路径（非全部）上表达式 e 都进行过求值，且 e 的操作数均未改变，则表达式 e 在位置 p 是部分冗余的。
b = b + 1
b = b + 1 ... b * c
│ │
│ ┌──────┐ │ ┌──────┐
▼ ▼ │ ▼ ▼ │
a = b * c │ a = b * c │
│ │ │ │ │ │
│ └──────┘ │ └──────┘
▼ ▼
通过给左图中的部分冗余表达式插入求值得到右图，使得该表达式在循环内部变成冗余的。通过使循环中不变的计算变冗余并消除之，可将其从循环移出。这种优化也成为循环不变量代码移动（loop-invariant code motion）。
LCM 通过计算可用表达式和可预测表达式来获得 Earliest(i, j) 集合，该集合包含以（i, j) 边为最早合法置放位置的所有表达式。接下来通过求解 Later 集合来发现延迟置放的情况，即将表达式求值延迟到最早置放位置之后仍具有同样效果的情形，因为它可以缩短插入值的生命周期。最终 LCM 计算集合 Insert 和 Delete。
LCM 移动的是表达式求值，而不是赋值，因此 LCM 会创建一个临时名字用于存放表达式的值。我们需要区分程序变量和存放表达式的临时名字（从汇编角度看都是虚拟的寄存器编号），这里采用一种简单的方法，规定变量使用的寄存器下标小于表达式下标。因此对于 ri -> rj，如果 i > j，则是变量赋值；否则是表达式求值。
可用表达式 计算可用表达式的公式是 $AvailOut(n)=DEExpr(n)\cup(AvailIn(n)-ExprKill(n))$，初始状态 $AvailIn(n0)=\varnothing$，$AvailOut(n)=all expressions, ∀n \ne n0$。
因此如果表达式在 AvailOut(b) 中，则可以将该表达式的求值放置在程序块 b 末尾。借助 AvailOut，编译器可以判断能够将表达式的求值向前移动多远。
可预测表达式 计算可预测表达式的公式是 $AntIn(n)=UEExpr(n)\cup(AntOut(n)-ExprKill(n))$, AntOut 公式见之前笔记。
最早置放
延迟置放
例子
for i = 1 to n do
x = a + b * c
B1: loadI 1 -> r10
i2i r10 -> r4
loadAI rarp,@n -> r11
i2i r11 -> r5
cmp_LE r4, r5 -> r12
cbr r12 -> B2, B3
B2: mult r2, r3 -> r15
add r1, r15 -> r16
i2i r16 -> r6
addI r4, 1 -> r13
i2i r13 -> r4
cmp_GT r4, r5 -> r14
cbr r14 -> B3, B2
B3: ...
TODO 第二次看还是看不懂
尾调用优化
叶调用优化 不进行调用的过程称为叶过程
RISC-V 的返回地址不直接保存在栈帧里, 而是被放在一个叫做 ra 的寄存器里——毕竟 RISC-V 有 32 个寄存器, 用掉一个也还有很多富余. 这么做其实有一个好处: 函数可以自由决定自己要不要把返回地址保存到栈帧里. 如果当前函数里没有再调用其他函数, 那 ra 的值就不会被覆盖, 我们就可以放心大胆地使用 ret 来进行函数返回, 同时节省一次内存写入的开销
参数提升 如果编译器能够证明对某形参对应的实参在被调用者中是无歧义的，那么可以将该参数的值提升到一个局部标量值中，使被调用者能够将其保存在寄存器中。
冗余消除 冗余消除的前提式，重用一个值比重算更快。之前阐述的用于冗余消除的有效技术：局部值编号、 超局部值编号、缓式代码移动，主要区别在于确定两个值相等的方法。
LVN为每个值分配唯一的标识号，假定如果两个表达式运算符相同，且具有相同的值编号，那么两个表达式将产生相同的值。不过不能证明a+a和a*2、a和a+0值相同，因而可以用代数恒等式来扩展LVN。
LCM可以消除冗余和部分冗余的表达式求值，但不会消除赋值计算。值编号算法不能识别部分冗余，但可以消除赋值操作。基于支配者的值编号算法在超局部值编号基础上，把支配者块的信息也纳入计算，结合了以上两种方法的优势。
辅助性的处理趟 主要意图是为其他变换创造或暴露时机。某些情况下，会改变代码的形式，使之更容易优化。之前描述了几种，如循环展开和内联替换确实消除一些开销，但更大的效果来自之后应用的其他优化。树高平衡算法并不消除操作，但其产生的代码形式可以使指令调度产生更好的结果。
超级块复制 复制具有多个前趋结点的程序块，并将复制后的程序块分别与前趋结点进行合并。优化器从循环入口开始，复制每条代码路径，直到遇见反向分支
会导致代码变得更大，可能导致一些指令高速缓存失败，导致代码运行得更慢
过程复制 与超级块复制相似。
循环外提 如循环中的条件控制流的判断表达式是循环不变量，那么可以将条件控制流移出循环
重命名
合并优化 同时进行两项优化可以产生以任意组合方式运行两种优化所无法达到的结果。如稀疏简单常量传播算法为每个操作的结果计算格值。如条件分支的操作数是一个已知值，那么可以删除其中的不可达分支。但稀疏简单常量传播算法没有利用这一知识，由此推广出来稀疏条件常量传播算法。
将IR操作映射到目标机操作的过程称为指令选择。本节介绍两种指令选择的方式：树模式匹配、窥孔优化。基于树模式匹配依赖于对IR和目标ISA的一个高层次的树表示法。窥孔优化将IR转换为一种底层线性IR，然后对其进行系统化改进并映射到目标机ISA。
指令选择的复杂性来自ISA操作提供了大量的备选实现方案。最简单的，编译器可以为每个IR都提供一个目标ISA操作，通过模式匹配并展开来生成代码。不过这样对目标机的资源利用比较低。我们需要考虑所有可能的候选操作序列，从中选择代价最低的。
典型的编译器会使用一种通用的IR，根据一组适用于大多数目标机的假定来进行优化，接着使用指令选择器、调度器和寄存器分配器来处理代码生成的相关问题。后端的三个过程，指令选择、指令调度和寄存器分配会互相影响，需要尽可能保持分离。
编译器编写者尽量把目标机相关的细节隔离在后端，如寄存器数目、处理器数目、内存对齐、调用约定等，但有时候一些目标机相关的细节不可避免。比如由于内存对齐的差异，不同目标机可能会将语义相同的值存到活动记录的不同偏移值。因此如果编译器要利用这些机器相关的特性来充分优化代码，就必须在后端之前暴露这些特性。
指令选择器输入是IR，输出是目标机汇编代码。它由一个模式匹配引擎和一组表组成，表中包含了从IR映射到目标ISA所需的知识。编译器编写者对目标机建立描述，通过后端生成器来推导出这些表。
如果每个IR操作在目标机上只有一种实现，那么简单将IR重写为等价的机器操作序列即可。但是大多数目标机都提供多种方法来实现每个IR。比如将寄存器r1的值复制到寄存器r2，就有多种方式：
add r1, 0, r2、div r1, 1, r2、and r1, r1, r2等等。
IR的不同实现方法都有不同的代价，如指令周期，是否读写内存、上下文环境、能耗、长度等等。有些ISA也会对特定操作由约束，如双字的load指令才能提供最佳带宽和延迟、内存操作只能在某个功能单元执行等等。
考虑三个生成代码的目标机：
考虑使用简单的树遍历方案来处理变量和数字，其代码如下所示：
case IDENT:
t1 = base(node);
t2 = offset(node);
result = NextRegister();
emit(loadA0, t1, t2, result);
break;
case NUM:
result = NextRegister();
emit(loadI, val(node), none, result)；
break;
这里的处理变量的方法没有区分变量的信息，所以如果要扩展这个树遍历方案，让它能够支持不同长度的变量、传值还是传引用、整个生命周期都在寄存器的变量，就需要在 case 语句中增加很多判断语句，使得树遍历方案的简单性大打折扣。
这里处理数字的方法比较简单，都是把值存入寄存器中。但是有时候使用这个数字的操作，在目标机上有一种立即形式（如mulI r1, c1 => r2），且这个数字的值能够载入到立即字段，那就不需要把值存入寄存器。
这种方案对每个特定种类的 AST 节点，都会产生同样的代码序列。这样产生的代码是正确的，但往往不是最优的，因为它没有利用上下文的知识来参与指令选择的决策。
比如说如果能够识别出子树求值结果为常量，且有对应的立即数操作指令，那么应该使用立即形式。处理这种情况需要非全局的上下文知识。又比如说出现公共子表达式这种冗余情况，这在 AST 中是隐藏的。
为了能够发现冗余并处理，最好的方法是 IR 能够暴露出暴露目标机的知识，并在指令选择期间参与决策。通常会将IR扩展为更加详细的底层形式，可以是结构性的，也可以是线性的。
当然，如果编译器在指令选择之后还会进行一系列优化，这可能不是问题。但如果没有后续的优化，最终生成的代码就会比较低效。
优化后的指令执行顺序会直接影响到编译后代码的执行速度。指令调度器会对程序块或过程中的操作进行排序以有效利用处理器资源，让每个周期执行尽可能多的操作。指令调度必须考虑到数据流、指令延迟、目标处理器能力等方面的约束，它采用表调度的一种贪婪启发式算法作为主导。
指令调度器有 3 个主要目标：保持输入代码的语义、避免拖延或 nop 指令、避免延长值的生命周期，至少不能导致额外的寄存器溢出。
大多数处理器会重叠执行各个操作，并在有限功能单元的前提下尽快发射连续的各条指令。为了防止处理器在操作数就绪前就执行该操作，处理器有两种方式来解决这个问题：
处理器通常包含不同延迟的各种指令，甚至同一条指令的延迟也是可变的。比如 load 指令的延迟取决于目标值在内存层次结构中的位置，一些乘法除法指令的延迟也会根据操作数而不同。如果这些指令的延迟有一个最大值，则调度器可以根据此值进行安全的调度。但这样会带来不少的空闲周期，因此调度器应该评估可能的延迟，并依赖硬件发现未完成的操作数来拖延后续操作。
衡量调度质量除了时间，还有对寄存器的需求、能耗等。
如果 x 位于 y 之前，且 y 定义了一个 x 中使用的值，则 x 反作用于 y。调换执行顺序会导致 x 计算出不同的值。
表调度不是一种具体的算法，在实现方式上、对待调度指令进行优先级排序方面，都存在大量变化。经典表调度运行在一个基本块上，调度器遵循以下四个步骤：
很多编程语言拥有一些很难在编译期生成高效代码的特性，比如延迟绑定、动态加载、多态、动态类型、开放的类结构。其中一些知识可以在链接时，或者在 JAVA class-load time 时获取，但也有一些只能在运行期才能知道。对于这种情况，编译器生成代码的性能会有很大影响。传统的编译器，也被称为 ahead-of-time (AOT) 编译器，能够为这些特性生成普适性代码，但是却很难拥有足够的知识去优化代码，只能推迟优化时机直到获取到必要的知识。
运行时优化能够让编译器利用那些运行时才能知道的知识。编译器必须权衡优化带来的收益以及为了获得知识而引入的成本。如果这些知识能够促进折叠不变量、避免类型转换、将虚函数调用替换为直接调用、编译频繁执行的代码，那么运行时优化的收益会非常可观。
对于 AOT 编译器来说，优化开销不是大问题，因此可以尽情地做各种优化变换。而对于 JIT 编译器来说， 必须保证优化开销小于优化收益。
运行时系统既可以执行本地机器码，也可以解释抽象机器码，也可以通过 JIT 把抽象机器码编译为本地机器码并执行，选择哪种方式各有优劣。通常来说，通过 JIT 执行转换后的本地机器码更快，解释抽象的启动成本更低。考虑把所有虚拟码编译成本地机器码的方案，这需要采用 AOT 方式或者 JIT 方式。AOT 方式会导致生成的代码优化程度低，JIT 方案导致系统执行更多的运行时编译，并在每次执行时都会产生这些成本。
为了支持能够执行本地机器码和抽象机器码，JIT 编译器还需要一些数据结构来支持。比如说活动记录 AR 既需要能支持虚拟机的格式，也要能支持本机 ISA 格式。这不同表示之间的转换也会带来运行时开销。