CS143 斯坦福大学编译原理-Optimization
简介
编译流程
L.A. Parsing Semantic A. Opt. Code Gen. 代码优化器是现在编译器中最复杂的，也是耗时最长的。
优化时机
- 对于AST Pro：机器无关 Con：层次太多
- 对于汇编 Pro：暴露优化选项 Con：机器相关 Con：不同目标必须重新实现优化器
- 对于中间码 Pro：机器无关 Pro：暴露优化选项
Basic block基本块
是一个最大指令序列，拥有以下特性： - 没有标签（第一行指令除外） - 没有跳转（最后一行指令除外）
思路
- 不能跳转到基本块内部（第一行指令除外）
- 不能跳出基本块外部（最后一行指令除外）
- 基本块是一个单入口、单出口、单线性代码段
示例说明
一般不能优化。除非能其他地方没有使用t变量。
Control-flow graph控制流图
有以下特点： - 基本块为节点 - 一条边由基本块A指向基本块B，即A的最后一条指令指向B的第一条指令
示例
所有节点都有结束
目的
代码优化主要是提升程序资源利用率，比如： - 执行时间 - 代码大小 - 网络消息 优化不能改变计算结果。 按粒度分有三类优化器： - 局部优化：应用在基本块 - 全局优化：应用在控制流（方法体中） - 函数间优化：应用在跨方法边间 大部分编译器做局部优化，许多会做全局优化，只有少数会做函数间优化。
Local Optimization
最简单的优化器。 主要关注基本块内部。
删除优化
简化优化
常量折叠
在编译时，根据上下文能计算结果的可以优化： 
注意
常量优化有时是比较危险的。比如在嵌入式开发中进行交叉编译，浮点数常量会存在精度问题。
不可达优化
代码块没有被其他jump指令跳转即不可达基本块。移除不可达基本块可以减小生成代码大小，有时运行会更快。
单声明
每个寄存器只进行一次声明，减少重复声明。 
相同表达式
中间过程寄存器值不变，直接结果赋值。
拷贝传播
代码块中有w:=x的申明，使用x替换w。 
一般配合其他优化共同作用，常量折叠、删除优化等。
特点
- 优化器交叉作用
- 编译优化需要不断调用优化器，直到没有提升的可能结束
综合示例
示例1 
示例2 初始化代码： 
最终形式： 
Peephole Optimization
简介
直接应用于汇编代码。 Peephole是一组精简（通常是连续的）的指令序列。 优化器使用等效的代码序列替换它们。
示例说明
示例1 
示例2 
示例3 
特点
与[[#Local Optimization]]相似，要想获得最佳效果必须要不断重复进行优化。
Dataflow Analysis
简介
为使用常量k替换变量x，需要满足条件： - 使用变量x的每条路径均为x:=k
示例说明
X为常量，可以优化： 
左边X值改变，不能优化： 
特点
- 检测条件是否满足不能太琐碎
- 所有路径包括循环路径和条件分支
- 检测条件依赖全局数据流分析 全局优化任务有几个方法：
- 依靠执行程序已知的属性X
- 依靠整个程序的体系在任意点证明X
- 保守没问题 全局数据流分析是解决这类问题的标准技术。 全局常量传播是一种优化手段，它依赖全局数据流分析。
Constant Propagation
约定
假定需要在每个代码点观测X的值，定义如下符号： 
对于每个状态s，可以在s前后迅速得到x的值信息： 
规则
Rule 1
前面有声明，则输入为声明 
Rule 2
前面存在不同常量，则输入为T 
Rule 3
前面所有值为相同常量或未执行，则输入为常量 
Rule 4
前面都为未执行，则输入为未执行 
Rule 5
输入为未执行，输出为未执行 
Rule 6
输入不为未执行，且c为常量，输出为常量 
Rule 7
输入不为未执行，且x:=f(…)，输出为声明 
Rule 8
输出与输入相同，声明y且y不等于x 
通用步骤
- 程序的每个入口s，初始值为C(s,x,in)=T
- 除步骤1的每个地方C(s,x,in)=C(s,x,out)=⊥
- 不断遍历所有状态s，将不满足规则1-8的，进行更新。直到全部s符合规则
示例说明
初始状态 
最终状态 
Orderings
简化分析表达，可以得到：⊥ < c < T 使用图形表达是 
构造函数lub计算最小上边界，例如： lub(⊥,1)=1 lub(T,⊥)=T lub(1,2)=T 任意两点通过图形找到通用的边界 使用lub可以将Rule 1改写为： C(s,x,in)=lub{C(p,x,out)|p是s的前一状态}
特点
- 状态值只能由⊥开始，并持续上升
- ⊥可以变为常数，常数可以变为T
- C(s,x,in/out)最多只能变化两次
Liveness Analysis
简介
如图，第一个X没有被使用，就是dead；第二个X就是live。
基本定义
如何判断变量x在状态s中一直存活： - 存在一个状态s’使用变量x - 有一个路径由s指向s’ - 这个路径中没有重新声明x 若在变量x声明后又遇到x:=…，就说明x存活结束（dead）
规则
Rule 1
Rule 2
Rule 3
Rule 4
通用步骤
- 初始化所有L(…)=false
- 重复选择规则1-4中的s，并按照规则更新，直到所有s满足规则1-4
示例说明
特点
- false可以变为true，但不能反向；（即false<true）
- 每个值只能改变一次，因此循环结束有保障
- 使用存活分析，可以消除多余代码很容易 前面介绍的常量传播是正向分析，即信息由输入到输出推出的； 存活分析是后向分析，即信息由输出反向到输入推出的；
Register Allocation
简介
中间码使用大量的临时变量。需要使用与物理寄存器数量匹配的临时变量。 主要方式有： - 为每个寄存器声明多个临时变量 - 不能改变程序行为 简单示例 
示例说明
获取每个点存活的变量： 
register interference graph
构建一个无向图，这也是寄存器干涉图 - 每个临时变量一个节点 - 边连接的节点不能同时被相同寄存器替代 两个能用相同寄存器存储的节点，不存在边直接连接它们 简单示例 
Graph Coloring
简介
边连接的节点有不同的颜色。若图有k种颜色，则它就是k可着色（k-colorable） 其中有多少颜色就需要等量的寄存器。
问题
如何计算图有多少颜色不是很容易的。 - 可以使用heuristics 若需要的寄存器少于颜色 - 可以使用后面讲解spilling
简单方案
步骤： - 在图中选择邻居少于k的节点t - 从图中将节点t和它的边移除 - 若结果图就是k可着色，那这就是原图
泛化步骤： 1. 构造堆栈 - 在图中选择邻居少于k的节点t - 从图中将节点t和它的边移除，并将节点t放入堆栈 - 重复上述步骤直到图为空
- 为节点涂色
- 从堆栈中获取节点
- 新节点颜色与上色的邻居不一致即可
示例说明
开始的图形： 
所有节点少于4邻居： 
所有节点入栈： 
节点上色： 
最终结果： 
Spilling
若最终寄存器数量不足，则需要将数据“持久化”。 示例： 使用图中三颜色 
可以选择一个节点，比如f将它存入内存。 简化后可以得到满足条件的图 
即 
具体步骤
- 若颜色优化失败，则声明内存存放f
- 在每处读取f前，增加指令从内存中恢复f再操作
- 在每处写入f后，增加指令将结果写入内存 示例
spilling后的图可以化简为 
注意
spilling选定的临时变量有一些要求： - 邻居要尽量多 - 声明少且使用少 - 避免在循环内使用（会增加循环时间复杂度）
缓存管理
简介
编译器擅长管理寄存器，但不擅长管理缓存。编译器可以对缓存进行优化的空间很小。
内存管理
简介
需要对临时对象内存的生命周期进行管理（声明由程序进行）。 如何判断对象是否为不再使用则是内存管理的关键。 示例： 
管理方法
标记mark阶段： 
清理sweep阶段： 遍历堆中所有对象标记为0的，将其加入到释放列表中 
完整过程示例 