基本块和流图

 基本块（１）

 后续使用信息

注意：上述次序不能颠倒，因为x可能是y或z

 流图（1）

流图的表示方式 

本次笔记内容：
8-1 流图
8-2 常用代码优化方法一
8-3 常用代码优化方案二
8-4 基本快的优化

本节课幻灯片，见于我的 GitHub 仓库：第16讲 代码优化_1.pdf

流图

基本块(Basic Block)

基本块是满足下列条件的最大的连续三地址指令序列：

• 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令
• 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机

基本块划分算法

输入：

• 三地址指令序列

输出：

• 输入序列对应的基本块列表，其中每个指令恰好被分配给一个基本块

方法：

• 首先，确定指令序列中哪些指令是首指令(leaders)，即某个基本块的第一个指令

1. 指令序列的第一个三地址指令是一个首指令
2. 任意一个条件或无条件转移指令的目标指令是一个首指令
3. 紧跟在一个条件或无条件转移指令之后的指令是一个首指令

• 然后，每个首指令对应的基本块包括了从它自己开始，直到下一个首指令(不含)或者指令序列结尾之间的所有指令

例

如上是快速排序法的部分源代码。

根据跳转指令找首指令（如跳转指令后的一条指令）。

流图(Flow Graphs)

• 流图的结点是一些基本块
• 从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B的最后一条指令之后执行

此时称B是C的前驱(predecessor) ，C是B的后继(successor)。

有两种方式可以确认这样的边：

• 有一个从B的结尾跳转到C的开头的条件或无条件跳转语句
• 按照原来的三地址语句序列中的顺序，C紧跟在之B后，且B的结尾不存在无条件跳转语句

例

感觉像是描述各个运算部分的关系。

常用的代码优化方法(1)

优化的分类

• 机器无关优化：针对中间代码
• 机器相关优化：针对目标代码
• 局部代码优化：单个基本块范围内的优化
• 全局代码优化：面向多个基本块的优化

常用的优化方法

• 删除公共子表达式
• 删除无用代码
• 常量合并
• 代码移动
• 强度削弱
• 删除归纳变量

①删除公共子表达式

公共子表达式：

• 如果表达式x op y先前已被计算过，并且从先前的计算到现在，x op y中变量的值没有改变，那么x op y的这次出现就称为公共子表达式(common subexpression)

例

将 B3 重构如黄色区域。


由 B3 “逆流而上”，发现 $4\ast i$ 没有被修改过，则其是一个公共子表达式。

进行了再次的画家如上。

发现 $a[t_2]$ 与 $a[t_4]$ 也是公共子表达式。




$a[t_1]$能否作为公共子表达式？

把$a[t_1]$作为公共子表达式是不稳妥的，因为控制离开$B_1$进入$B_6$之前可能进入$B_5$，而$B_5$有对$a$的赋值。

关键问题：如何自动识别公共子表达式？

会在后面的课程详细介绍。

常用的代码优化方法(2)

②删除无用代码

复制传播：常用的公共子表达式消除算法和其它一些优化算法会引入一些复制语句(形如x=y的赋值语句)

复制传播：在复制语句x= y之后尽可能地用y代替x。

无用代码(死代码Dead-Code)：其计算结果永远不会被使用的语句。

例

程序员不大可能有意引入无用代码，无用代码通常是因为前面执行过的某些转换而造成的。

如何自动识别无用代码？

也将在后文详细介绍。

如上，通过删除公共子表达式与删除无用代码，将 B5 与 B6 简化了不少。

③常量合并(Constant Folding)

如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式。该技术被称为常量合并。

④代码移动(Code Motion)

这个转换处理的是那些不管循环执行多少次都得到相同结果的表达式(即循环不变计算，loop-invariant computation) ，在进入循环之前就对它们求值。

例

如何自动识别循环不变计算？

循环不变计算的相对性

对于多重嵌套的循环，循环不变计算是相对于某个循环而言的。可能对于更加外层的循环，它就不是循环不变计算。

⑤强度削弱(Strength Reduction)

用较快的操作代替较慢的操作，如用加代替乘。

循环中的强度削弱

对于一个变量x ，如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c ，那么x就称为归纳变量(Induction Variable)。

例

归纳变量可以通过在每次循环迭代中进行一次简单的增量运算(加法或减法)来计算。

⑥删除归纳变量

在沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，常常可以将这组变量删除为只剩一个。


如上，$i$ 与 $j$ 都无用了。

基本块的优化

很多重要的局部优化技术首先把一个基本块转换成为一个无环有向图(directed acyclic graph，DAG)。

基本块的 DAG 表示

基本块中的每个语句s都对应一个内部结点N：

• 结点N的标号是s中的运算符；同时还有一个定值变量表被关联到N ，表示s是在此基本块内最晚对表中变量进行定值的语句
• N的子结点是基本块中在s之前、最后一个对s所使用的运算分量进行定值的语句对应的结点。如果s的某个运算分量在基本块内没有在s之前被定值，则这个运算分量对应的子结点就是代表该运算分量初始值的叶结点(为区别起见，叶节点的定值变量表中的变量加上下脚标0)
• 在为语句x=y+z构造结点N的时候，如果x已经在某结点M的定值变量表中，则从M的定值变量表中删除变量x

例，有基本块：

a = b + c
b = a - d
c = b + c
d = a - d

对于形如 x=y+z 的三地址指令，如果已经有一个结点表示 y+z，就不往 DAG 中增加新的结点，而是给已经存在的结点附加定值变量x。

基于基本块的 DAG 删除无用代码

从一个DAG上删除所有没有附加活跃变量（活跃变量是指其值可能会在以后被使用的变量）的根结点(即没有父结点的结点) 。重复应用这样的处理过程就可以从DAG中消除所有对应于无用代码的结点。

数组元素赋值指令的表示

如上，因为有可能出现 $i=j$ ，因此不能轻易把 $a[i]$ 算作公共子表达式。

• 对于形如a[j] = y的三地址指令，创建一个运算符为“[]=”的结点，这个结点有3个子结点，分别表示a、j和y
• 该结点没有定值变量表
• 该结点的创建将杀死所有已经建立的、其值依赖于a的结点
• 一个被杀死的结点不能再获得任何定值变量，也就是说，它不可能成为一个公共子表达式

根据基本块的DAG可以获得一些非常有用的信息

• 确定哪些变量的值在该基本块中赋值前被引用过：在DAG中创建了叶结点的那些变量
• 确定哪些语句计算的值可以在基本块外被引用：在DAG构造过程中为语句s（该语句为变量x定值）创建的节点N，在DAG构造结束时x仍然是N的定值变量

从 DAG 到基本块的重组

对每个具有若干定值变量的节点，构造一个三地址语句来计算其中某个变量的值。

倾向于把计算得到的结果赋给一个在基本块出口处活跃的变量(如果没有全局活跃变量的信息作为依据，就要假设所有变量都在基本块出口处活跃，但是不包含编译器为处理表达式而生成的临时变量)。

如果结点有多个附加的活跃变量，就必须引入复制语句，以便给每一个变量都赋予正确的值。

例

构建 DAG 如右边。常量直接标记出来。

最终，根据 DAG 得到优化后的基本块如下：

D = A + C
E = A * C
F = E + D
L = 15 + F

前言

参考课上PPT内容。 该学习笔记目前仅打算个人使用。
后续会进一步整理，包括添加笔记内容，标明参考资料。

更新中。。。

参考资料

1. 《编译技术》
2. 邵老师PPT

跳过目录

一、基本块

1、基本块定义

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

例：函数foo的C语言源码和三地址中间代码

划分基本块

属于同一个基本块的有
（1）~（6）
（3）~（8）
（7）~（13）

分析

• 不利于优化，因为编译器:
  • 得不到分支、路径等控制信息。
  • 得不到数据流、控制流的信息。

2、基本块划分算法

输入：四元式序列

输出：基本块列表。每个四元式仅属于一个基本块

方法：

1、确定各个入口语句：

• 规则1：整个语句序列的第一条语句
• 规则2：能由条件/无条件跳转语句转移到的第一条语句
• 规则3：紧跟在跳转语句之后的第一条语句

2、每个入口语句直到下一个入口语句，或者程序结束，它们之间的所有语句都属于同一个基本块。

二、流图

1、定义

• 流图是一种有向图
  • 结点：基本块
  • 有向边：如果在某个执行序列中， B2的执行紧随在B1之后，则从B1到B2有一条有向边

紧随：满足下列条件中之一即称为紧随

• B1的最后一条语句条件/无条件转移到B2的第一条语句
• B1的最后一条语句条件转移判断失败后，进入到B2的第一条语句
• 按照程序的执行次序， B2紧跟在B1之后，并且B1没有无条件转移到其他基本块

前驱和后继：

• 设从B1到B2有一条有向边，则：
  • B1为B2的前驱
  • B2为B1的后继

三、基本块的有向无环图（DAG）

1、有向无环图（DAG）

• Directed Acyclic Graph
• 用来表示基本块内各中间代码之间的关系
• 可通过DAG图消除公共子表达式

定义

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

例：基本块的DAG图表示

赋值语句：

a = b * (-c) + b * (-c)

中间代码

t1 := - c
t2 := b * t1
t3 := - c
t4 := b * t3
t5 := t2 + t4
a := t5

语法树

DAG图

注：

• 这里，由于变量 c 被赋值前曾经被引用，因此有 c 和 c₀ 两种不同的表示。

2、构建DAG图的算法

在消除局部公共子表达式处