↓Skip to main content
A cup of beer
  1. Posts/

做个编译器——代码优化

·332 words·2 mins
笔记
Table of Contents

General #

优化可以是针对目标代码生成过程的，也可以是针对中间代码的。

对于中间代码的优化，通常处于编译的前端与后端之间。对于目标代码的优化，往往处于后端。

代码优化器通过考虑数据流、控制流，从而对代码进行等价变换。

优化要求等价性、有效性、合算性。有效性是指真的能降低复杂度，合算性是指花费的代价不宜过大。

优化的级别分为局部优化（局限在基本块范围）、循环优化（在循环结构范围）、全局优化（全部代码的范围）。我们只考虑局部优化级别。

基本块和流图 #

定义 #

基本块是一段顺序执行的语句序列，其只有唯一的入口和出口，分别是其范围内的首个语句和最后一个语句。

定值和引用 #

例如三地址代码x := y + z，x被赋值了称为对x进行定值；y和z被用到了称为对y和z进行引用。

活跃的名字 #

”基本块中的某名字在程序中的某个定点是活跃的“的意思是：它在该定点的后续的程序执行过程中会被引用。（可以是在当前基本块中，也可以是在之后被执行的一些基本块中）

换言之，该名字在之后的执行中会被引用，就说这个名字是活跃的

基本块的划分 #

基本思路：先找到所有可能成为基本块入口的语句，再分别从这些可能的入口语句开始，一条接一条遍历代码，找到第一个可能与其匹配的成为出口的语句。

可能成为入口的语句有下面三种：

  • 程序的第一个语句
  • 能由转移语句（可条件，可无条件）转移到的语句（即成为了跳转目标的语句）：这样的语句在跳转后会被接着执行
  • 紧跟在条件转移语句后的语句：这样的语句相当于条件不满足时的跳转目标，在条件不满足时会被接着执行

对于每个入口确定的基本块，其出口语句可能是以下三种：

  • 停机语句
  • 下一入口语句之前的那个语句
  • 下一个转移语句（包括该转移语句）

例如下面的三地址代码

image-20220618170328745

确定入口

  • 1是入口，因为是程序第一条语句；
  • 8是入口，因为是条件转移语句的转移目标；
  • 3是入口，因为是无条件转移语句的转移目标；
  • 5是入口，因为是条件转移语句紧跟着的下一语句。
image-20220618170622269

确定出口

  • 从1开始向下依次遍历，看到2，发现是下一个入口的上一个语句，故作为与其配对的出口。
  • 从3开始向下依次遍历，看到4，发现是转移语句，故作为与其配对的出口。
  • 从5开始向下依次遍历，看到7，发现是转移语句，故作为与其配对的出口。
  • 从8开始向下依次遍历，看到9，发现是停机语句，故作为与其配对的出口。

完成配对后，基本块就都出来了。

删除多余屎山💩 #

如果按照上述算法完成了基本块的划分，存在一些语句没有被基本块包含，那么这些语句就必然无法被执行到，属于程序员写的的屎山💩，可以直接被删除。

程序的流图 #

以基本块为节点，根据执行顺序建立一张图，称为程序的流图。它代表了程序中的各基本块是以什么顺序执行，从而完成整个程序的。

例如上述基本块划分，就可以产生如图的流图。它的结点就是把基本块揪出来了。

image-20220618171023859

构建一个流图 #

流图是以首结点为根，不同结点之间按照”前驱“指向”后继“的原则建立有向边而构成的有向图。

【首结点】基本块包含程序首条语句的结点，称为首结点。

【前驱后继关系的确定】有以下三种方式来确定这种关系，假设现有B1、B2和B3结点。

  • 如果B1的出口不是转移指令，而B2在程序结构上紧跟着B1出现，那么B1就是B2的前驱。
  • 如果B1的出口是无条件转移指令，通过该转移指令能跳转到B3，那么B1是B3的前驱。
  • 如果B1的出口是条件转移指令，那么其同时是其真出口B2和假出口B3的前驱。

基于基本块的DAG优化 #

为什么以基本块为单位 #

  • 因为基本块是顺序执行的一个程序单位。相对来说逻辑上很简单。
  • 而且基本块是相对独立的一个程序单位。因此不同基本块之间的优化应当是互不影响的。

DAG天生自带优化效果 #

image-20220618172256361 image-20220618172228614

如图，对于同一语句的翻译，如果采用DAG进行翻译，会比采用抽象语法树生成更优秀的三地址代码，因为DAG能够合并冗余的公共子树。

这就指导我们利用DAG进行代码优化。现在需要对DAG进行扩充，使之成为一种可以用于描述基本块内部的运算过程的，且可以用于优化的工具。

注意箭头方向 #

DAG是有向图，但是课件为了描述方便，省略了边的箭头。**我们都是默认箭头的方向是自上而下。**因为这和语法树形成对应关系。

对DAG的表示信息进行扩充 #

image-20220618172843161

标识符或常量赋值给node：叶结点下方的标记. 表示该标记的值赋值给DAG结点。 例如图中的3.14和R，表示这个结点的标识符（如果是变量）或值（如果是常量）。

运算结果赋值给node：内部结点下方的标记. 表示标记的该运算的结果赋值给DAG结点。例如这里的+，代表n4结点附带有n2+n3的结果。值得注意的是，该内部结点代表的运算的左、右操作数分别是其左右儿子。这和AST是一脉相承的 。

node赋值给别的标识符：任意节点右侧的标记（附加标记）. 表示该节点的值赋值给该标记的标识符。例如n4上还有等价标记T2、T4，这表示T2、T4也具有该结点的值。

值得注意的是，前面两种标记都是别的东西赋给DAG结点，而最后一种标记是DAG结点的值赋值给别的东西。

常用四元式的DAG表示 #

对于0型四元式的三地址代码例如 A:=B，其四元式是(:=,B,_,A)。其DAG结点表示是：

思想：找到B所在的结点，把A附加上去。

image-20220618173801200
  • B表示： B赋值给n1
  • A表示：n1赋值给A

对于1型四元式的三地址代码例如A:=op B，其四元式是(op,B,_,A)。其DAG结点是：

image-20220618174244136
  • B表示：B赋值给n1
  • op表示：n1做op运算的结果赋值给n2
  • A表示： n2赋值给A

对于2型四元式的三地址代码例如A:=B op C，其四元式是 （op,B,C,A）。其DAG结点是：

image-20220618174605363
  • n1 := B, n2 := C
  • n3 := n1 op n2
  • A := n3

基本块和DAG的关系 #

一个基本块可以用一个DAG来表示。

因为我们可以用上述的常用四元式DAG表示，来对基本块中的每个四元式都进行转化，把每个构造出的这样的DAG进行连接，从而连成了等价于该基本块的较大的DAG。

DAG显示出的活跃性信息 #

DAG的叶节点上的标识符肯定是在该基本块之前就被定值，在该基本块中必然是活跃的，在基本块后也可以仍然活跃的。

DAG的内点上附加的标识符肯定是在该基本块内部被定值，可以是在基本块后仍然活跃的。

优化算法概述 #

在对基本块中的每个四元式构造对应的子DAG时，分成四步骤进行。按照这种步骤来逐步构造各四元式的子DAG，连成的大DAG就是优化后的结果。四步骤如下。

  • 准备操作数结点

    • 遵从”尽量不新建“原则：语句肯定需要操作数。如果当前DAG里面已经有值为该所需操作数的结点，则复用它，否则新建。

  • 合并已知量

    • 对于常量，现在就给予计算
    • 对于非常量，生成相应的运算代码

  • 删除公共子表达式

    • 看有没有和当前的完全相同的表达式的DAG，也就是操作数（左右孩子）完全相同的，且运算（即父结点）相同的，如果有，那么直接复用这个父结点即可。

  • 删除无用赋值

例子：构造DAG #

对于以下四元式序列，求其DAG。

T0 := 3.14
T1 := 2*T0
T2 := R + r
A := T1 * T2
B := A
T3 := 2* T0
T4 := R + r
T5 := T3 * T4
T6 := R - r
B :=  T5 * T6
image-20220618203014085

对于第一句T0 := 3.14

  • 准备操作数结点：构造新结点n1，赋值为3.14，然后赋值给T0.
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618203312077

对于第二句T1 := 2*T0

  • 准备操作数结点：发现T0已存在，不再生成结点；但是2不存在，所以生成新结点n，赋值2.
  • 合并已知量
    • 不需要生成值为2的结点再进行计算，因为俩操作数都是常量。而是直接计算结果为6.28，创建新结点n2并赋值给T1.
    • 现在发现在本轮中新生成的结点n没用了，可以删除。（注意，每轮只有权限删除本轮新增的node。因此没有权限删除n1.）
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618203655229

对于第三句T2 := R + r

  • 准备操作数结点：发现R和r都不存在，分别创建之。然后创建父节点，父节点赋值给T2.
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618203741628

对于第四句A := T1 * T2

  • 准备操作数结点：发现T1和T2现在都有了，故无需创建。
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618203834563

对于第五句B := A

  • 准备操作数结点：发现A已经存在，B不存在，但是可以直接附加，故无需创建新结点。
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618204053231

对于第六句T3 := 2* T0

  • 准备操作数结点：发现值为2的结点不存在，创建为n。发现T0已经存在，无需创建。
  • 合并已知量
    • 因为T0所在的n1是常量，n是常量，故可以直接创建结果结点6.28
    • 因为值为6.28的结点n2已经存在，故无需创建
    • 本轮生成的值为2的结点n已经没用了，故删除之
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618204214685

对于第七句T4 := R + r

  • 准备操作数结点：R和r已经存在，无需创建
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：已经存在左右操作数为R、r的运算为+的内结点了，无需创建，而只需要附加T4上去即可。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618204339379

对于第八句T5 := T3 * T4

  • 准备操作数结点：T3和T4已经存在，ok。
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：已经存在左右操作数为T3、T4的运算为*的内结点了，无需创建，而只需要附加T5上去即可。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618204550339

对于第九句T6 := R - r

  • 准备操作数结点：R和r已经存在，ok。
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：不存在上一次的赋值还没被引用，就又一次被赋值了的情况。
image-20220618204611733

对于第十句B := T5 * T6

  • 准备操作数结点：T5和T6已存在，ok。
  • 合并已知量：没有需要合并的常量。
  • 删除公共子表达式：不存在这样的表达式的内结点，可以生成新的。
  • 删除无用赋值：B在第五句中已经有一次赋值，且之后B没有被引用过，所以那一次的赋值无效，可以删除。

例子：通过DAG写优化后的中间代码 #

image-20220618205056009

可以遵循“从左到右，从下到上”的顺序来写出优化后的代码。值得注意的是，一定要等本层处理完毕，再去处理更高层，否则运算顺序是错误的。

T0 := 3.14
T1 := 6.28
T3 := T1

注意这里的T3，因为已经有T1是同样的值了，所以其用T1进行赋值即可

T2 := R + r
T4 := T2 //已经有同样的值了
T6 := R - r
A := 6.28 * T2
T5 := A

注意这里的6.28，而不应该写成T1。这是因为能用常量直接给出的就用常量。

B := A * T6

做完之后，还可以再做一步“删除无用赋值”。如果我们假设临时变量T1到T6都只局限在基本块内是活跃的，那么没有必要保留他们的赋值。凡是在基本块内没有被引用的对于临时变量的赋值语句都可以直接删除，如果被非临时变量A、B引用了，就无需删除。为保险起见，我们对已经生成的中间代码从上到下逐条遍历来看是否要删除，也就是：

T2 := R + r
T6 := R - r
A := 6.28 * T2
B := A * T6
↑