基本块与轨迹

发表于

基本块和轨迹

在tree语言中含有一些与机器语言不一致的情况，但我们又必须将tree语言转换成汇编语言或者机器语言，例如

  • CJUMP指令能够跳转到两个标号中的任意一个，但真正的机器指令在条件为false时是跳转到下一个指令；
  • 在表达式中使用ESEQ会很不方便，因为它会使得子树的不同计算顺序产生不同的结果；
  • CALL指令也可能会有问题；

因此我们必须要对任意一棵树进行转换，以避免上述情况：

  • 将一棵树重写成不含SEQ和ESEQ的规范树；
  • 将这一列树组合成其内不含标号和转移的基本块组合；
  • 对基本快并形成一组trace；

规范树

什么是规范树：

  1. 无SEQ或者ESEQ
  2. 每一个CALL的父亲不是EXP，就是MOVE

ESEQ的转换

消除ESEQ的方法是，在树中一级一级地将它们提升，直至它们可以变成SEQ节点。

下面，介绍四种情况，其中三四两种情况的不同在于s1与e能否交换：

img

一般，常数和空语句可以与任何语句交换，其它假定不能交换。

一般重写规则

一般而言，对于每一种tree语言或者表达式，都会有等价的子表达式。

例如对于[e1, e2, ESEQ(s, e3)]，需要将s抽取出来放到e2和e1的左边。如果可以交换，则得到(s; [e1,e2,e3])，如果不能交换，则是上图中第三种情况。

利用函数reorder接收一个表达式，并返回由(语句，表达式表)组成的一个偶对。其中语句必须包含所有在表达式表之前执行的操作。传入reorder的是一个链表，它会抽出所有的ESEQ。reorder对参数的链表中的每一个表达式都调用de_exp，而do_exp的实现又只是对除了ESEQ之外的任何类型的表达式建立其子表达式的地址表并调用reorder。

将call移到顶层

由于在tree语言允许call节点作为子表达式，但实际中call的实现是，每一个函数将它的结果返回到同一个规定的返回值寄存器中，那么后面的调用就可能把前面的调用给覆盖掉了。

因此，我们可以重写：

CALL(func, args)--->ESEQ(MOVE(TEMP t, CALL(func, args)), TEMP t)

在这种情况中，do_stm不会调用reorder去处理CALL节点，而是把f和args看做MOVE节点的儿子

线性语句表

一旦整个函数体都已经用do_stm处理完毕之后，所有的SEQ节点都集中在树的顶部。函数linearize重复施加规则，使得SEQ(SEQ(a,b),c) ==> SEQ(a, SEQ(b,c))

但SEQ节点不提供任何结构性信息，只是简单列表。

处理条件分支

tree语言与多数机器指令集不一样的是，它具有两路分支CJUMP指令。为了便于将tree转换为机器指令，我们需要重新安排CJUMP，使得CJUMP(cond, lt, lf)后面跟随的LABEL(lf)。

我们分两步实现这一目的：取一颗规范树，并由它们形成基本块；对这些基本块进行排序，形成trace轨迹。

基本块

在分析程序的控制流时，任何非分支指令的程序语句对分析都没有意义，因此可以将非分支指令的序列集中到基本块中。

基本块是语句组成的一个序列，只能从序列的开始进入并从结尾处退出：

  • 第一个语句是一个LABEL；
  • 最后一个语句是JUMP或者CJUMP；
  • 没有其他的LABEL, JUMP或者CJUMP；

划分基本块的算法：

从头到尾扫描语句序列，遇到一个LABEL就开始一个新的基本块并结束前一个基本块，遇到一个JUMP或者CJUMP就结束一个基本块；若过程遗留的基本块中，有任何基本块不是以LABEL开始的，则新生成一个标号插入到开始；若有不是以JUMP结束的，则在这个基本块的末尾假如一个转移到下一个基本块标号的指令。

轨迹

由于我们以任意顺序安排基本块，程序结果都是一致的，因此我们可以合理地安排基本块，以满足每个CJUMP之后都跟随它的false标号的基本块。

另外，也可以安排基本块使得JUMP之后跟随的是它们的目标标号，然后删除这些转移。

还有，需要安排轨迹使得重叠的轨迹越来越少。

完善

主要针对的是CJUMP指令：

  • 所有后面直接跟随的false标号的CJUMP维持不变；
  • 对任何直接跟随true标号的CJUMP，交换true标号和false标号，并将条件改为相反；
  • 如果既不是true也不是false标号直接跟随着，则新生成一个标号lf'，重写CJUMP；
1
2
3
CJUMP(cond, a, b, lt, lf')
LABEL(lf')
JUMP(NAME lf)