1 概述

• 代码优化（code optimization)
  指编译程序为了生成高质量的目标程序而做的各种加工和处理。
  • 目的：提高目标代码运行效率
    • 时间效率（减少运行时间）
    • 空间效率（减少内存容量）
  • 原则：进行优化必须严格遵循“不能改变原有程序语义”原则。
• 优化所花费的代价和优化产生的效果可用下图表示：
  只要做些简单的处理，便能得到明显的优化效果。若要进一步提高优化效果，就要逐步付出更大的代价。
  

为什么要优化？

• 用开发时的开销代替运行时开销
  • 有的大型计算程序一运行就要花上几十分钟，甚至几小时、几天、几十天，这时为优化即使付出些代价是值得的。
  • 对于像学生作业之类的简单小程序（占机器内存，运行速度均可接受），或在程序的调试阶段，花费许多代价去进行一遍又一遍的优化就毫无必要了（尤其机器速度、存储的快速发展）
• 循环：程序中的“2-8原则”
  • 程序中的循环往往要占用大量的计算时间
  • 为减少循环执行时间所进行的优化对减少整个程序的运行时间有很大的意义。 ——尤其有实时要求的程序

优化的分类

• 从优化的层次，与机器是否有关，分为：
  • 独立于机器的优化：即与目标机无关的优化，通常是在中间代码上进行的优化。
    如：数据流分析，常量传播，公共子表达式删除，死代码删除，循环交换，代码内联等等
  • 与机器有关的优化：充分利用系统资源（指令系统，寄存器资源）。
    • 面向超标量超流水线架构、VLIW或者EPIC架构的指令调度方法；面向SMP架构的同步负载优化方法；面向SIMD、MIMD或者SPMD架构的数据级并行优化方法等 。
    • 特点：仅在特定体系结构下有效
• 从优化涉及的范围，又分为：
  • 局部优化：
    • 是指在基本块内进行的优化。
    • 例如，局部公共子表达式删除
  • 循环优化：对循环语句所生成的中间代码序列上所进行的优化。
  • 全局优化：顾名思义，跨越多个基本块的全局范围内的优化。因此它是指在非线性程序段上（包括多个基本块, GOTO, 循环）的优化。需要进行全局控制流和数据流分析，比较复杂。
    • 函数/过程内进行的优化
    • 跨越基本块
    • 例如全局数据流分析
  • 跨函数优化
    • 整个程序
    • 例如跨函数别名分析，逃逸分析等

2 基本块和流图

2.1 基本块

• 基本块中的代码是连续的语句序列。
• 程序的执行（控制流）只能从基本块的第一条语句进入。
• 程序的执行只能从基本块的最后一条语句离开。

2.2 算法：划分基本块

• 输入：四元式序列
• 输出：基本块列表。每个四元式仅出现在一个基本块中
• 方法：
  1. 首先确定入口语句（每个基本块的第一条语句）的集合。
     • 规则1：整个语句序列的第一条语句属于入口语句；（1）
     • 规则2：任何能由条件/无条件跳转语句转移到的第一条语句属于入口语句；（3）
     • 规则3：紧跟在跳转语句之后的第一条语句属于入口语句。（13）
  2. 每个入口语句直到下一个入口语句，或者程序结束，它们之间的所有语句都属于同一个基本块。

2.3 流图

• 流图是一种有向图
• 流图的结点是基本块
• 如果在某个执行序列中，B2的执行紧跟在B1之后，则从B1到B2有一条有向边
• 我们称B1为B2的前驱，B2为B1的后继
  • 从B1的最后一条语句有条件或者无条件转移到B2的第一条语句；
  • 按照程序的执行次序，B2紧跟在B1之后，并且B1没有无条件转移到其他基本块。

3 基本块内优化

3.1 利用代数性质（代数变换）

• 编译时完成常量表达式的计算（常数合并），整数类型与实型的转换。
  
• 下标变量引用时，其地址计算的一部分工作可在编译时预先做好（运行时只需计算“可变部分”即可）。
• 运算强度削弱：用一种需要较少执行时间的运算代替另一种运算，以减少运行时的运算强度(时、空开销)。
  

3.2 复写（copy）传播

• 如 x := y 这样的赋值语句称为复写语句。由于 x 和 y 值相同，所以当满足一定条件时，在该赋值语句下面出现的 x 可用 y 来代替。
  
• 若上例中不是x := y而是 x := 3。则复写传播变成了常量传播。即
  

3.3 删除冗余代码

• 冗余代码就是毫无实际意义的代码，又称死代码 (dead code)或无用代码(useless code)。
  

3.4 !!!算法：消除公共子表达式

通过 DAG 图消除公共子表达式

• Directed Acyclic Graph 有向无环图
• 用来表示基本块内各中间代码之间的关系
  

DAG 图定义

• 图的叶结点由变量名或常量所标记。（对于那些在基本块内先引用再赋值的变量，可以采用变量名加下标0的方式命名其初值）。
• 图的中间结点由中间代码的操作符所标记，代表着基本块中一条或多条中间代码。
• 基本块中变量的最终计算结果都对应着图中的一个结点；具有初值的变量，其初值和最终值可以分别对应不同的结点。
  

!!!算法：DAG图的生成算法

• 输入：基本块内的中间代码序列
• 输出：完成局部公共子表达式删除后的DAG图
• 方法：
  1. 首先建立结点表，该表记录了变量名和常量值，以及它们当前所对应的DAG图中结点的序号。该表初始状态为空。
  2. 从第一条中间代码开始，按照以下规则建立DAG图。
  3. 对于形如z = x op y的中间代码，其中z为记录计算结果的变量名，x为左操作数，y为右操作数，op为操作符：首先在结点表中寻找x，如果找到，记录下x当前所对应的结点号i；如果未找到，在DAG图中新建一个叶结点，假设其结点号仍为i，标记为x（如x为变量名，该标记更改为x0）；在结点表中增加新的一项(x, i)，表明二者之间的对应关系。右操作数y与x同理，假设其对应结点号为j。
  4. 在DAG图中寻找中间结点，其标记为op，且其左操作数结点号为i，右操作数结点号为j。如果找到，记录下其结点号k；如果未找到，在DAG图中新建一个中间结点，假设其结点号仍为k，并将结点i和j分别与k相连，作为其左子结点和右子结点。
  5. 在结点表中寻找z，如果找到，将 z 所对应的结点号更改为k；如果未找到，在结点表中新建一项(z, k)，表明二者之间的对应关系。
  6. 对输入的中间代码序列依次重复上述步骤3～5。
     
     

数组、指针及函数调用的 DAG 图

• 当中间代码序列中出现了数组成员、指针或函数调用时，算法 14.2 需要作出一定的调整，否则将得出不正确的优化结果。
• 数组：保守处理，把修改 a[i] 看做修改了 a
  
• 指针：保守处理
  
• 函数调用：在缺乏跨函数数据流分析的支持下，需要保守地假设函数调用改变了所有它可能改变的数据。

从 DAG 图重新导出中间代码

生成的中间代码顺序会影响最后代码的运行效率

!!!算法：从DAG导出中间代码的启发式算法

• 输入：DAG图
• 输出：中间代码序列
• 方法：
  1. 初始化一个放置DAG图中间结点的队列。
  2. 如果DAG图中还有中间结点未进入队列，则执行步骤3，否则执行步骤5
  3. 选取一个尚未进入队列，但其所有父结点均已进入队列的中间结点n，将其加入队列；或选取没有父结点的中间结点，将其加入队列
  4. 如果n的最左子结点符合步骤3的条件，将其加入队列；并沿着当前结点的最左边，循环访问其最左子结点，最左子结点的最左子结点等，将符合步骤3条件的中间结点依次加入队列；如果出现不符合步骤3条件的最左子结点，执行步骤2
  5. 将中间结点队列逆序输出，便得到中间结点的计算顺序，将其整理成中间代码序列
     
     

3.5 窥孔优化

• 窥孔优化关注在目标指令的一个较短的序列上，通常称其为“窥孔”
• 通过删除其中的冗余代码，或者用更高效简洁的新代码来替代其中的部分代码，达到提升目标代码质量的目的
• 必须出现在同一个基本块中的情况：
  mov EAX, [ESP+08H]
mov [ESP+08H], EAX
• 但是窥孔优化并不局限在同一个基本块中。以上方法，如利用代数性质等都可以用。
  jmp B2
B2: …

4 全局优化（函数/过程内）

4.1 数据流分析

• 用于获取数据在程序执行路径中如何流动的有关信息。
  例如：
  • 某个变量在某个特定的执行点（语句前后）是否还“存活”
  • 某个变量的值，是在什么地方定义的
  • 某个变量在某一执行点上被定义的值，可能在哪些其他执行点被使用
• 是全局优化的基础
• 数据流分析是为了了解程序的状态

1 程序的状态

• 程序的执行过程：程序状态的变换过程
  • 程序状态由程序中的变量和其它数据结构组成
  • 每一条执行指令都可能改变程序的状态
• 通过数据流分析，可以了解程序的状态。
  • 例如，如果得知在某条中间代码之后，无论程序在实际执行时通过哪条路径，某个变量都不会再被访问，那么该变量此前所保有的全局寄存器或临时寄存器就可以安全地被其他变量重新使用。
  • 例如，如果得知在程序的某个点上，对某个变量进行引用时，无论程序如何运行，该变量都仅具有某个唯一的常量值，那么就可以将该常量引入中间代码，在代码生成时生成更高效的指令。
• 一种常用的数据流分析方法：到达定义

2 数据流分析方程

• 考察在程序的某个执行点的数据流信息。
• out[S] = gen[S] ∪ (in[S] – kill[S])
  含义：当执行控制流通过S时，在S末尾得到的数据流信息等于S本身产生的数据流信息，合并进入S时的数据流信息减去S注销的数据流信息后的数据流信息。
  • S代表某条语句（也可以是基本块，或者语句集合，或者基本块集合等）
  • out[S] 代表在S末尾得到的数据流信息
  • gen[S] 代表S本身产生的数据流信息
  • in[S] 代表进入S时的数据流信息
  • kill[S] 代表S注销的数据流信息
  • 集合运算

数据流方程求解过程中的3个关键因素

• 当前语句产生和注销的信息取决于需要解决的具体问题 ：可以由in[S]定义out[S]，也可以反向定义，由out[S]定义in[S]
• 由于数据是沿着程序的执行路径，也就是控制流路径流动，因此数据流分析的结果受到程序控制结构的影响
• 代码中出现的诸如过程调用、指针访问以及数组成员访问等操作，对定义和求解一个数据流方程都会带来不同程度的困难

3 到达定义分析

• 通过到达定义分析，希望知道：
  在程序的某个静态点p，例如某条中间代码之前或者之后，某个变量可能出现的值都是在哪里被定义的？

• 在p处对该变量的引用，取得的值是否在d处定义？

  • 如果从定义点d出发，存在一条路径达到p，并且在该路径上，不存在对该变量的其他定义语句，则认为“变量的定义点 d 到达静态点p ”
  • 如果路径上存在对该变量的其他赋值语句，那么路径上的前一个定义点就被路径上的后一个定义点“杀死”，或者消除了

• 说明:

  • 变量的定义：赋值语句、过程参数、指针引用等多种形式。
  • 不能判断时：保守处理

单个语句的到达定义数据流方程

• 对于基本块中的某一条中间代码：
  d1: u = v op w，v和w为变量，op为操作符
• 代码对应的到达定义数据流方程是：
  out[d1] = gen[d1] ∪ ( in[d1] – kill[d1] )
• 其中
  • gen[d1] = {d1}，表明该语句产生了一个定义点（定义了变量u）
  • kill[d1] 是程序中所有对变量u定义的其他定义点的集合（包括d1之前或之后的定义点 --why？后面的语句可能跳转到当前语句）
  • 对于该代码在同一基本块中紧邻的后继代码，假设其为d2，in[d2]等价于out[d1]

基本块的到达定义数据流方程

out[B] = gen[B]∪( in[B] – kill[B] )

• in[B]为进入基本块B时的数据流信息
• kill[B] = kill[d1] ∪ kill[d2] … ∪ kill[dn]， d1~dn依次为基本块中的语句
• gen[B] = gen[dn]∪
(gen[d(n-1)] – kill[dn])∪
(gen[d(n-2)] – kill[d(n-1)] – kill[dn])…∪
(gen[d1] – kill[d2] – kill[d3]… – kill[dn])

4 !!!算法：基本块的到达定义数据流分析

• 输入：程序流图，且基本块的kill集合和gen集合已经计算完毕
• 输出：每个基本块入口和出口处的in和out集合，即in[B]和out[B]
• 方法：
  1. 将包括代表流图出口基本块 的所有基本块的out集合，初始化为空集。
  2. 根据方程 的前驱基本块，out[B] = gen[B]∪( in[B] –kill[B] )，为每个基本块B依次计算集合in[B]和out[B]。如果某个基本块计算得到的out[B]与该基本块此前计算得出的out[B]不同，则循环执行步骤2，直到所有基本块的out[B]集合不再产生变化为止。

5 到达定义分析的代码实现

• 集合“∪”和“–”运算：可以采用位向量（Bit Vector）的方式完成。
• 将集合中的每个定义点，根据其下标映射为一个无限位二进制数的某一位，例如，可以将d1映射为第1位，d3映射为第3位，以此类推。
  • 例如，out[B3] = { d2, d3, d4, d5, d7, d8}，其对应的二进制位向量为11011110，该位向量从低位到高位依次对应d1~d8。
  • 基于这样的设定，集合之间的“∪”运算等价于位向量之间的或运算，集合之间的“–”运算等价于将后者取反后，和前者进行按位与运算。
• 在数据流分析方法的实现中，位向量是常用的手段之一。

4.2 活跃变量分析

• 到达定义分析是沿着流图路径的，活跃变量分析是反方向计算的

• 活跃变量分析：

  • 了解变量x在某个执行点p是活跃的
    变量x的值在p点或沿着从p出发的某条路经中会被使用，则称x在p点是活跃的。
  • 通过活跃变量分析，可以了解到某个变量x在程序的某个点上是否活跃，或者从该点出发的某条路径上是否会被使用。如果存在被使用的可能，x在该程序点上便是活跃的，否则就是非活跃，或者死的。

• 活跃变量信息对于寄存器分配，不论是全局寄存器分配还是临时寄存器分配都有重要意义。

  • 如果拥有寄存器的变量x在p点开始的任何路径上不再活跃，可以释放寄存器
  • 如果两个变量的活跃范围不重合，则可以共享同一个寄存器

1 活跃变量分析

• 数据流方程如下：
  • in[B] = use[B] ∪ (out[B] – def[B])
  • 的后继基本块
  • def[B]：变量在B中被定义（赋值）先于任何对它们的使用 【先定义后使用】
  • use[B]：变量在B中被使用先于任何对它们的定义 【先使用后定义】
• 直观理解：如果在路径后方的某个基本块中，变量x被使用，则沿着执行路径的逆向直到x被定义的基本块，x都是活跃的。
• 到达定义数据流分析，其数据流信息是沿着流图中路径的方向进行计算的
• 活跃变量分析的数据流信息，需要沿着流图路径的反方向计算得出

2 活跃变量分析与到达定义分析的区别

活跃变量分析：in[B] = use[B]∪(out[B] – def[B])
到达定义分析：out[B] = gen[B]∪(in[B] – kill[B])

• 采用use[B]代表当前基本块新生成的数据流信息（用了）
• 采用def[B]代表当前基本块消除的数据流信息 （定义的）
• 采用in[B]而不是out[B]来计算当前基本块中的数据流信息
• 采用out[B]而不是in[B]来计算其它基本块汇集到当前基本块的数据流信息
• 在汇集数据流信息时，考虑的是后继基本块而不是前驱基本块

3 !!!算法：基本块的活跃变量数据流分析

• 输入：程序流图，且基本块的use集合和def集合已经计算完毕
• 输出：每个基本块入口和出口处的in和out集合，即in[B]和out[B]
• 方法：
  1. 将包括代表流图出口基本块 在内的所有基本块的in集合，初始化为空集。
  2. 根据方程 的后继基本块，in[B] = use[B] ∪ (out[B] – def[B])，
     为每个基本块B依次计算集合out[B]和in[B]。如果计算得到某个基本块的in[B]与此前计算得出的该基本块in[B]不同，则循环执行步骤2，直到所有基本块的in[B]集合不再产生变化为止。

4 冲突图

假设只有跨越基本块活跃的变量才能分配到全局寄存器，并且活跃范围重合的变量之间无法共享全局寄存器

4.3 定义-使用链、网和冲突图

• 冲突图：其结点是待分配全局寄存器的变量，当两个变量中的一个变量在另一个变量定义（赋值）处是活跃的，它们之间便有一条边连接
  

• 活跃变量冲突的不同定义：冲突图中两个结点（变量）间存在边的条件约束为：其中一个变量在另一个变量的定义点处活跃
  

关于变量冲突的判断

两个变量中的一个变量在另一个变量定义（赋值）处是活跃的，它们就是冲突的。

• 算法一：在每一个变量的定义点计算活跃变量。
• 算法二：计算基本块入口处的活跃变量（in的集合），这些变量在该基本块中的定义点活跃，因而冲突。之后，在基本块内部，进一步计算每个定义点的活跃变量（基本块范围内计算），降低了计算的复杂度，因为基本块内部是线性的。

第一个循环的 i 和第二个循环的 i 其实没有关系，可以看做两个 i，这样画成冲突图后就只有两个颜色了

5 循环优化

减少循环部分的目标代码对提高整个程序的时间效率有很大作用。

5.1 循环不变式的代码外提

不变表达式：不随循环控制变量改变而改变的表达式或子表达式。

5.2 循环展开

循环展开是一种优化技术。它将构成循环体的代码(不包括控制循环的测试和转移部分)，重新产生许多次(这可在编译时确定)，而不仅仅是一次。以空间换时间

说明：

• 循环一次执行5条语句才给一个变量赋初值。展开后，一条语句就能赋一个值，运行效率高。
• 优化在生成代码时进行，并不是修改源程序。
• 必须知道循环的初值、终值及步长。
• 但非所有展开都是合适的。如上例中循环展开后节省了测试和转移语句：2*30=60语句。但若循环体中不是一条而是40条，则展开将有40*30=1200条，但省的仍是60条，就不算优化了。
  判断准则：
  1. 主存资源丰富处理机时间昂贵
  2. 循环体语句越少越好

实现步骤

1. 识别循环结构，确定循环的初值、终值和步长。
2. 判断。以空间换时间是否合算来决定是否展开。
3. 展开。重复产生循环体所需的代码个数。

折中方法

在对空间与时间进行权衡时，还可以考虑一种折衷的办法，即部分展开循环。如上例展为：

5.3 归纳变量的优化和条件判断的替换

归纳变量(induction variable): 在每一次执行循环迭代的过程中，若某变量的值固定增加（或减少）一个常量值，则称该变量为归纳变量(induction variable)。即若当前执行循环的第 j 次迭代，归纳变量的值应为c * j + c’ , 这里 c 和 c ’都是循环不变式

5.4 其它循环优化方法

• 把多重嵌套的循环变成单层循环。
• 把 n 个相同形式的循环合成一个循环等。

in_line 展开

• 把过程（或函数）调用改为in_line展开可节省许多处理过程（函数）调用所花费的开销。
• 省去了函数调用时参数压栈，保存返回地址等指令。
• 这也仅仅限于简单的函数。