Skip to content

Latest commit

 

History

History
302 lines (201 loc) · 12.3 KB

optimizer.md

File metadata and controls

302 lines (201 loc) · 12.3 KB
Raw

代码优化

[toc]

纵观整个项目，实现的优化相关技术如下图

optim_hier

其中流图与基本块的数据结构已经在 midcode 一节中介绍过了。机器相关代码优化技术在 mips 一节中会进行详细介绍。本节主要介绍项目中应用的机器无关代码优化技术。

数据流分析

流图与基本块的架构已经在 midcode 一节中介绍过，因此本文不再说明。作为优化的另一个基本的数据结构，数据流在本节中起到了和流图类似的重要作用。数据流分析方法可以用来获取数据如何在程序执行路径中流动等相关信息，是许多全局优化方法的基础。

活跃变量数据流

相比于到达定义数据流，活跃变量比较容易分析。改写书上列出的分析算法可以得到

  1. 计算每个基本块的 use & def
  2. 将基本块的 in 初始化为 use
  3. 对于每个基本块，根据数据流方程计算 out 并更新 $in = in \cup (out - def)$
  4. 检查第三步中是否有更新。若有则跳回第三步，否则结束

改写后的算法不仅省去了第一次循环，而且不必存储 use 信息，在一定程度上可以提高效率。最终得到的数据流是一个字典

std::map<const BasicBlock*, Vars> _out;

其中 Vars 表示活跃变量的集合

using Vars = std::set<const symtable::Entry*>;

事实上，在一般的活跃变量数据流中可以只存储 out 对应的基本块编号，而不必使用 map 。这样设计主要是因为实际应用中常常需要反推每条中间代码的 out 。而如果不知道某个 Vars 对应的基本块，就难以实现这个功能。因此在存储时记录的是 <basicblock, vars> 这一二元组。

到达定义数据流

到达定义数据流和活跃变量数据流类似，但到达定义数据流的基本单位是中间代码。也就是说对应于 Vars 的 Defs 应该有如下形式

using Defs = std::set<const MidCode*>;

类似地可以改写更新算法得到

  1. 计算每个基本块的 gen 存储到 blockGens
  2. 计算整个函数的 gen 存储到 funcGen
  3. 根据 blockGens 和 funcGen 计算每个基本块的 kill
  4. 将基本块的 out 初始化为 gen
  5. 对于每个基本块，根据数据流方程计算 in 并更新 $out = out \cup (in - kill)$
  6. 检查第三步中是否有更新。若有则跳回第三步，否则结束

与活跃变量的算法不同，到达定义数据流在计算每个基本块的 kill 时需要函数整体的 gen 信息。对于单个基本块来说，可能在基本块间流动的定义点是同一个变量在这个基本块中的最后一个定义点。因此 blockGens 可以用 map 来表示

std::vector<DefMap> blockGens(blocks.size());

其中 DefMap 定义为

using DefMap = std::map<const symtable::Entry*, const MidCode*>;

而对于函数整体，某个变量可能存在多个定义点，因此定义 funcGen

std::map<const symtable::Entry*, Defs> funcGen;

有了局部和整体的 gen 信息，基本块就可以计算出它的 kill 。后续过程和活跃变量数据流类似，这里不再赘述。

常量合并

常量合并是将能在编译时计算出值的表达式用其相应的值替代。例如中间代码

a = 1 + 2;

就可以被替换为

a = 3

这样做看似毫无意义（因为计算指令和赋值语句消耗的时间是相同的），但是一旦辅以复制传播和死代码删除，这个优化的作用将是巨大的。

除了书中提到的计算类指令，跳转指令也可以被替换。例如

if 1 > 2 branch to label1

很显然这样的语句是没有实际效果的，可以直接被删除。而如果将指令中的立即数 1 和 2 互换

if 2 > 1 branch to label1

则这条指令可以等效为一个 GOTO 。和之前一样，尽管 GOTO 和 branch 需要消耗同样的时间，但这样修改可以减少这条中间代码所在基本块的后继块的数量，从而提高其他优化的效率。

值得注意的是，因为本项目中的中间代码是不可变对象，所以在替换时需要先析构，然后再构造新的中间代码替换过去。这样做会降低编译器的运行效率，但却是保证中间代码有效性的必要措施。

复制传播

如果代码中有形如

a = b

的变量复制语句，则在后续 a 的使用点上，可以用 b 来代替 a 。首先看基本块内的情况。假设我们分析的是一个没有前驱的基本块，也就是说没有其他定义点可以到达这个基本块。那么可以使用一个 matcher 来记录这个基本块内部的变量对应情况

std::map<const symtable::Entry*, const symtable::Entry*> _matches;

完整的算法如下

  1. 初始化 matcher 为空
  2. 对于每一条中间代码，循环执行 3 & 4 两步
  3. 如果中间代码使用的变量 b 在 matcher 中存在映射，则将 b 替换
  4. 如果中间代码是复制语句，则修改 matcher 的映射关系；否则如果中间代码定义了变量 a 则清除 matcher 中和 a 有关的全部关系

算法的前三步很好理解，主要难点在于第四步。如果存在对应关系

c -> a
a -> d

此时中间代码 a = 1 定义了变量 a 则这两个关系都应该删除，同时生成新关系

c -> d

因此删除映射关系的算法如下

  1. 检索 matcher 的全部映射，如果 a 出现在映射的右侧，则将其标记
  2. 如果 a 在 matcher 中映射到 b ，则将所有被标记的映射中的 a 换成 b ，否则删除之
  3. 删除 a 在 matcher 中的映射

修改映射关系建立在删除的基础之上，其算法如下（设修改后的映射是 a -> b）

  1. 删除 matcher 中和 a 有关的全部关系
  2. 建立映射关系 a -> b

上面说明了基本块内的复制传播，对于基本块间的情况需要到达定义数据流的帮助。如果一个基本块的到达定义数据流包含形如 a = 1 且没有其他对于 a 的定义点，则将 a = 1 加入 matcher 。具体算法如下

  1. 初始化 blackList 为空
  2. 对于到达定义数据流中的定义点，如果不形如 a = 1 或被定义变量已经出现过，则执行 3 否则执行 4
  3. 将被定义变量从 matcher 删除，并加入 blackList
  4. 如果被定义变量不在 blackList 则将对应关系加入 matcher

死代码删除

有了活跃变量数据流的支持，死代码删除就比较容易了。只要判断每条中间代码定义的变量是否在当前定义点是活跃的即可。但是有一些特殊情况，即使被定义的变量不活跃，中间代码也不能被删除。这些特殊情况有

  • 被定义变量是全局变量
  • 中间代码是函数跳转
  • 中间代码是输入操作

因为活跃变量数据流中并不包含全局变量，使得第一种情况被误判的可能性大大提高。但是只要仔细推导，这些问题还是比较容易避免的。正常情况下源程序中可能会引入的死代码有

  1. 有控制宏参与的条件判断
  2. 死循环
  3. 未使用变量

其中第三种情况一般会被编译器警告，出现情况不多。而前两种情况虽然被大量使用，在优化效果上也不会很显著。死代码删除最重要的作用是结合常量合并以及复制传播，以达到提前计算的目的。例如下面的代码

a = 1;
b = 2;
c = a + b;
d = 2 * c;

经过复制传播，这段代码可能变成下面的样子

a = 1;
b = 2;
c = 1 + 2;
d = 2 * c;

此时可以用常量合并将 c = 1 + 2 替换

a = 1;
b = 2;
c = 3;
d = 2 * c;

对于这段代码来说，原本活跃的变量 a 和 b 现在已经不活跃了，成为了死代码；而 c 原本无法被复制传播补货，现在也可以进行传播了

c = 3;
d = 2 * 3;

经过类似的过程，这段代码最终只剩下

d = 6

常量合并、复制传播以及死代码删除保证了，在不改变计算方式的情况下，提前计算出全部编译期常量。这里所说不改变计算方式是指对于下面的表达式

a = 1 + b + 2;

上面的做法无法进行优化，因为优化需要用到加法的交换律和结合律。为了保证程序正确性，这种语义信息暂时没有加入考虑。

不可达代码删除

严格来说不可达代码的删除并不属于本次优化的范畴，因为不可达代码不会占用指令数量。但是从编译器设计角度来看，不可达代码的删除对于提高编译速度和压缩代码空间有极为显著的作用。本节中讨论的不可达代码主要有以下几种

  1. 已经被内联的函数
  2. return 语句之后代码
  3. 流图中的不可达基本块
  4. 没有跳转指令跳到的标签

事实上条件 2 是条件 3 的一个特例，但是条件 2 是在前端判断的，而条件 3 在优化器中判断，因此此处将其拆分成两种情况。对于不再上述 4 种情况中的代码，本项目都保守的认为其可达。

函数内联

函数内联是编译器优化的普遍做法之一。一般的编译器会考虑函数的指令数量是不是足够少，以至于内联的效果比较显著而且不会给代码存储造成负担。但是在本项目中主要追求运行速度，因此对于所有可以内联的函数都进行了默认内联。这里所说的可内联函数是指非递归函数。尽管正常的编译器并不会这样判断，但在我们的文法中，非递归这一条件等价于可内联。

代码内联的核心思想是将函数体复制到函数的被调用处，从而节省函数跳转时保存现场的开支。具体算法如下

  1. 对于每个函数调用基本块，检查被调用函数是否可以被内联，不可内联直接返回
  2. 将所有 PUSH 语句转换为 ASSIGN 语句，初始化被调用函数的参数
  3. 检查调用者是否需要保存函数返回值，如果是则记录保存返回值的变量
  4. 生成新标签作为函数结束标志
  5. 遍历每条被调用函数的中间代码，执行第 6 ～ 8 步
  6. 如果中间代码是 RET ，替换为 GOTO 跳转到函数结束标签。如果函数返回值需要保存，则在 GOTO 之前生成 ASSIGN 语句对返回值赋值
  7. 对于 branch 语句、 GOTO 语句、 LABEL 语句，用相应新标签替换原有标签
  8. 对于其他语句，直接进行深拷贝
  9. 将被调用函数的局部变量引入调用者局部变量

相比其他优化，函数内联对源代码结构的更改较大，因此风险也更大。而且在保证函数内变量不冲突这一点上，需要符号表的支持（参考 symtable 中关于变量 rename 的描述）。不过相应地，函数内联的收效也比其他优化更加显著。这主要是因为一下两点

  1. 函数跳转时的开支占据了程序总访存量的很大一部分，将其省去可以大幅降低访存
  2. 原本被划分到不同基本块的语句（函数调用作为划分基本块的规则之一）现在可以同处于一个更大的基本块，为其他优化提供便利

窥孔优化

本项目采用从中间代码到目标代码逐条生成的方法，目标代码中通常会含有大量的冗余指令。窥孔优化可以有效减少这些冗余指令。本节实现的窥孔优化主要针对

  1. GOTO 语句：跳转标签在当前语句的下一条语句
  2. ASSIGN 语句：翻译过程引入的冗余中间变量

第一种情况有可能在函数内联时产生，例如

void func() { return; }
void main() { func(); return; }

内联后将得到如下中间代码

main:
	goto func_end
func_end:
	return;

只要被调用函数的 return 语句出现在最后一句，就有可能出现上述第一种窥孔情况。对于第二种情况，考虑下面的赋值语句

a = b + c;

为了方便翻译，通常会引入中间变量

t = b + c;
a = t;

但是由于中间变量仅由编译器生成，因此可以确定中间变量的活跃范围。理论上，上述中间代码可以直接简化成为 a = b + c 。但是为了尽量减少程序中的约束，此处将中间代码改写为

t = b + c;
a = b + c;

这样在进行死代码删除时即可完成优化。可以看到，这样的窥孔优化不仅适用于中间变量，也适用于一般的局部或全局变量，只要

  1. 序列中第一条中间代码的 use 和 def 没有交集
  2. 第一条中间代码的 def 是第二条中间代码（ASSIGN）的右端变量