MENU

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

June 1, 2020 • Read: 202 • 编程之路,编译原理

编译原理目录
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]);

示例:

语句123456
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])$
  • 同样可给出不动点算法

    • 从初始的空集{}出发
    • 循环到没有集合变化为止

示例:

这里采用逆序

语句654321
use/gen{c}{a, N}{b}{c, b}{a}{}
def/kill{}{}{a}{c}{b}{a}
迭代out/inout/inout/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间连一条无向边。
- - - 结束 - - -
  • 文章标题:【编译原理】6、中间代码与程序分析
  • 文章链接:https://blog.canye365.cn/archives/311.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021