【编译原理】6、中间代码与程序分析

编译原理目录
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间连一条无向边。