编译原理目录
1、词法分析
2、语法分析(重点)
3、语法制导翻译与抽象语法树
4、语义分析
5、代码生成
6、中间代码与程序分析
7、代码优化
六、中间代码与程序分析
语义分析器 => 中间表示层 => 汇编
6.1 中间代码的地位和作用
6.1.1 中间代码
- 树和有向无环图(DAG):高层表示,适用于程序源代码
- 三地址码(3-address code): 低层表示,靠近目标机器
- 控制流图(CFG):更精细的三地址码,程序的图状表示。适合做程序分析、程序优化等。
- 静态单赋值形式(SSA):更精细的控制流图、同时编码控制流信息和数据流信息
- 连续传递风格(CPS):更一般的SSA
- ...
6.1.2 为什么要划分成不同的中间表示?
编译器工程上的考虑:
- 阶段划分:把整个编译过程划分成不同的阶段
- 任务分解:每个阶段只处理翻译过程的一个步骤
- 代码工程:代码更容易实现、除错、维护和演进
程序分析和代码优化的需要
- 两者都和程序的中间表示密切相关:许多优化在特定的中间表示上才可以或才容易进行
- ...
6.2 几种常用的重要中间表示
6.2.1 三地址码
翻译1 => 三地址码 => 翻译2 => 汇编
三地址码的基本思想
- 给每个中间变量和计算结果命名,没有复合表达式。
- 只有最基本的控制流,没有各种控制结构,只有goto, call等。
- 所以三地址码可以看成是抽象的指令集,通用的RISC。
示例:
三地址码的定义
s -> x = n // 常数赋值
| x = y ⊕ z // 二元运算
| x = Ө y // 一元运算
| x = y // 数据移动
| x[y] = z // 内存写
| x = y[v] // 内存读
| x = f (x1, …, xn) // 函数调用
| Cjmp (x1, L1, L2) // 条件跳转
| Jmp L // 无条件跳转
| Label L // 标号
| Return x // 函数返回
定义三地址码数据结构:
enum instr_kind {
INSTR_CONST,
INSTR_MOVE,
…
};
struct Instr_t {
enum instr_kind kind;
};
struct Instr_Add {
enum instr_kind kind;
char *x;
char *y;
char *z;
};
struct Instr_Move {
…;
};
生成三地址码 —— 从C--生成三地址码
// 扩展了C--的语法
P -> F*
F -> x ((T id,)*) { (T id;)* S*}
T -> int
| bool
S -> x = E
| printi (E)
| printb (E)
| x (E1, …, En)
| return E
| if (E, S*, S*)
| while (E, S*)
E -> n
| x
| true
| false
| E + E
| E && E
// 要写如下几个递归函数:
Gen_P(P); Gen_F(F); Gen_T(T); Gen_S(S); Gen_E(E);
语句的代码生成
Gen_S(S s)
switch (s)
case x=e:
x1 = Gen_E(e);
emit(“x = x1”);
break;
case printi(e):
x = Gen_E(e);
emit (“printi(x)”);
break;
case printb(e):
x = Gen_E(e);
emit (“printb(x)”);
break;
case x(e1, …, en):
x1 = Gen_E(e1);
…;
xn = Gen_E(en);
emit(“x(x1, …, xn)”);
break;
case return e;
x = Gen_E(e);
emit (“return x”);
break;
case if(e, s1, s2):
x = Gen_E(e);
emit (“Cjmp(x, L1, L2)”);
emit (“Label L1:”);
Gen_SList(s1);
emit (“jmp L3”);
emit (“Label L2:”);
Gen_SList (s2);
emit (“jmp L3”);
emit (“Label L3:”);
break;
case while(e, s):
emit (“Label L1:”);
x = Gen_E(e);
emit (“Cjmp(x, L2, L3)”);
emit (“Label L2:”);
Gen_SList(s);
emit (“jmp L1”);
emit (“Label L3:”);
break;
三地址码的优缺点:
优点:
- 所有的操作是原子的:变量,没有复合结构
- 控制流结构被简化了:只有跳转
- 是抽象的机器代码:向后做代码生成更容易
缺点:
- 程序的控制流信息是隐式的
- 可以做进一步的控制流分析
6.2.2 控制流图
抽象语法树 => 翻译1 => 三地址码 => 翻译2 => 控制流图 => 翻译3 => 汇编
抽象语法树 => 翻译1 => 控制流图 => 翻译2 => 汇编
示例(还是上面的例子):
基本概念:
基本块:是语句的一个序列,从第一条执行到最后一条
- 不能从中间进入
- 不能从中间退出
- 即跳转指令只能出现在最后
控制流图:控制流图是一个有向图$G=(V, E)$
- 节点V:是基本块
- 边E:是基本块之间的跳转关系
示例:
优点:
控制流分析:对很多程序分析来说,程序的内部结构很重要
- 典型的问题:“程序中是否存在循环?”
可以进一步进行其他分析:例如数据流分析。
- 典型的问题:“程序第5行的变量x可能的值是什么?”
现代编译器的早期阶段就会倾向做控制流分析
- 方便后续阶段的分析
控制流图的定义
// 是更精细的三地址码
S -> x = n
| x = y + z
| x = y
| x = f (x1, x2, …, xn)
J -> jmp L
| cjmp (x, L1, L2)
| return x
B -> Label L;
S1; S2; …; Sn
J
F -> x() { B1, …, Bn }
P -> F1, …, Fn
数据结构的定义: 以$B$为例
struct Block{
Label_t label;
List_t stms;
Jump_t j;
};
如何生成控制流图:
可以直接从抽象语法树生成:
- 如果高层语言具有特别规整控制流结构的话较容易
也可以先生成三地址码,然后继续生成控制流图:
- 对于像C这样的语言更合适(包含像goto这样的非结构化的控制流语句)
- 更加通用(阶段划分)
由三地址码生成控制流图算法:
List_t stms; // 三地址码中所有语句
List_t blocks = {}; // 控制流图中的所有基本块
Block_t b = Block_fresh(); // 一个初始的空的基本块
scan_stms ()
foreach(s ∈ stms)
if (s is “Label L”) // s是标号
b.label = L;
else (s is some jump) // s是跳转
b.j = s;
blocks ∪ = {b};
b = Block_fresh ();
else // s是普通指令
b.stms ∪ = {s};
控制流图的基本操作
- 标准的图论算法都可以用在控制流图的操作上:各种遍历算法、生成树、必经节点结构、等等
- 图节点的顺序有重要的应用:拓扑序、逆拓扑序、近似拓扑序、等等。
示例:死基本块删除优化
删除算法:
// 输入: 控制流图g
// 输出: 经过死基本块删除
// 后的控制流图
dead_blocks_elim (g)
dfs (g);
for(each node n in g)
if(!visited(n))
delete(n);
6.3 优化
抽象语法树 => 翻译1 => 中间表示1 => 翻译2 => 中间表示2 => 更多的中间表示及翻译 => 汇编
优化的一般模式
程序分析
- 控制流分析,数据流分析,依赖分析, …
- 得到被优化程序的静态保守信息 (是对动态运行行为的近似)
程序重写
- 以上一步得到的信息制导对程序的重写
静态保守
如果x是某一个正数,运行时x为真,编译器就可以保守估计:"只执行L_1"。
如果x是程序输入的话,运行时才能知道值。所以编译器只能采用静态能够获得的信息对程序做保守估计:“L_1和L_2都可能会执行”。
数据流分析
通过对程序代码进行静态分析,得到关于程序数据相关的保守信息
- 必须保证程序分析的结果是安全的
根据优化的目标不同,需要进行的数据流分析也不同
接下来我们将研究两种具体的数据流分析
- 到达定义分析
- 活性分析
6.4 数据流分析
6.4.1 到达定义分析
定义:
数据流方程:
对任何一条定义:
- $[d: x = ...]$
给出两个集合:
- $gen[d: x= ...] = \{d\}$,代表一个式子的标识号
- $kill[d: x= ...] = defs[x] - \{d\}$,所有包含x定义的,除了d的式子的集合
数据流方程:
- $in[s_i] = out[s_{i-1}]$
- $out[s_i] = gen[s_i] ∪ (in[s_i]-kill[s_i])$
从数据流方程到算法:
// 算法:对一个基本块的到达定义算法
// 输入:基本块中所有的语句
// 输出:对每个语句计算in和out两个集合
List_t stms; // 一个基本块中的所有语句
set = {}; // 临时变量,记录当前语句s的in集合
reaching_definition ()
foreach (s ∈ stms)
in[s] = set;
out[s] = gen[s] ∪ (in[s]-kill[s])
set = out[s]
示例:
对于一般的控制流图
前向数据流方程:
- $in[s] =∪ p∈ pred(s) out[p]$
- $out[s] = gen[s] ∪ (in[s]-kill[s])$
从数据流方程到不动点算法
// 算法:对所有基本块的到达定义算法
// 输入:基本块中所有的语句
// 输出:对每个语句计算in和out两个集合
List_t stms; // 所有基本块中的所有语句
set = {}; // 临时变量,记录当前语句s的in集合
reaching_definition ()
while (some set in[] or out[] is still changing)
foreach (s ∈ stms)
foreach (predecessor p of s)
set ∪ = out[p];
in[s] = set;
out[s] = gen[s] ∪ (in[s]-kill[s]);
示例:
语句 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
gen | {1} | {2} | {3} | {4} | {} | {} |
kill | {4} | {} | {} | {1} | {} | {} |
当集合不再发生变化时,终止循环。
6.4.2 活性分析
为什么要进行活性分析?+ 在代码生成的讨论中,我们曾假设目标机器有无限多个(虚拟)寄存器可用。优点:简化了代码生成的算法。+ 缺点是对物理机器是个坏消息,机器只有有限多个寄存器,必须把无限多个虚拟寄存器分配到有限个寄存器中。+ 这是寄存器分配优化的任务,需要进行活性分析。
示例:
考虑这段三地址码:
a = 1
b = a + 2
c = b + 3
return c
假设目标机器上只有一个物理寄存器: r,是否可能把三个变量a, b, c同时放到寄存器r中?
如图,计算在给定的程序点,哪些变量是“活跃”的。活跃信息给出了活跃区间的概念。活跃区间互不相交,所以三个变量可交替使用同一个寄存器。
代码重写:
r = 1
r = r + 2
r = r + 3
return r
数据流方程:
对任何一条语句:
- $[d: s]$
给出两个集合:
- $gen[d: s] = \{x | 变量x在语句s中被使用\}$
- $kill[d: s] = \{x | 变量x在语句s中被定义\}$
基本块内的后向数据流方程:(先计算
out[]
再计算in[]
)- $out[si] = in[si+1]$
- $in[s] = gen[s] ∪ (out[s] - kill[s])$
示例
一般的数据流方程
方程:
- $out[s] =∪ in[p], p是s的后继$
- $in[s] = gen[s] ∪ (out[s]-kill[s])$
同样可给出不动点算法
- 从初始的空集
{}
出发 - 循环到没有集合变化为止
- 从初始的空集
示例:
这里采用逆序
语句 | 6 | 5 | 4 | 3 | 2 | 1 |
---|---|---|---|---|---|---|
use/gen | {c} | {a, N} | {b} | {c, b} | {a} | {} |
def/kill | {} | {} | {a} | {c} | {b} | {a} |
迭代 | out/in | out/in | out/in |
---|---|---|---|
6 | {} {} | {} {c} | {} {c} |
5 | {} {} | {c} {a, c} | {c} {a, c} |
4 | {} {} | {a, c} {b, c} | {a, c} {b, c} |
3 | {} {} | {b, c} {b, c} | {b, c} {b, c} |
2 | {} {} | {b, c} {a, c} | {b, c} {a, c} |
1 | {} {} | {a, c} {c} | {a, c} {c} |
到入口处in的值是
{c}
而非空集,这时候说明变量c没有初始化。
活跃周期
干扰图
干扰图是一个无向图G=(V, E):
- 对每个变量构造无向图G中一个节点;
- 若变量x, y同时活跃,在x、y间连一条无向边。