编译原理复习-6

纯纯傻逼课

从数学上讲, 为给定源程序生成一个最优的目标程序是不可判定问题. 但还好我们有一系列较为可靠的启发式算法.

代码生成器主要有三个任务: 指令选择, 寄存器分配, 指令排序.

Chapter-8: 代码生成和优化

构造方法:

确定首指令:
- 中间代码的第一个三地址指令是一个首指令
- 任意一个条件或无条件转移指令的目标指令是一个首指令
- 紧跟在一个条件或无条件转移指令之后的指令是一个首指令
每个首指令对应的基本块包括了从它自己开始，直到下一个首指令（不含）或者中间程序的结尾指令之间的所有指令

过程调用语句作为一个新的基本块的开始，甚至独立成为一个基本块

确定算法:

输入：一个三地址语句的基本块B，假设在基本块B开始时，所有的非临时变量都是活跃的
输出：对于每一个语句i：x = y op z，将x、y及z的活跃性信息及后续使用信息关联到i
方法：从基本块B的最后一个语句开始，反向扫描到B的开始处。对每一个三地址语句 i：x := y op z，依次执行下述步骤：
1. 把当前符号表中x、y和z的后续使用信息和活跃信息附加到语句i上；（若x不活跃，则这个语句可以删掉）
2. 在符号表中设置x为“无后续使用”和“不活跃”；
3. 把符号表中y和z的后续使用信息均置为i，活跃信息均置为“活跃”。

目前还不知道有什么用???????

采用DAG表示

方法：检测公共子表达式的“值编码”方法
当一个新的结点M将被加入到DAG中时
- 检查是否存在一个结点N，它和M具有同样的运算符和子结点，且子结点顺序相同
- 若存在，则N计算的值和M计算的值是一样的，可以用N替换M

如果有不活跃的公共表达式, 则可以删除一个. 如果都活跃, 则必须要有赋值语句去复制.

这种对不活跃的考察, 就是删除死代码

对数组而言, 情况较为不同, 比如下列式子:

x = a[ i ];
a[ j ] = y;
z = a[ i ];

其中a[i]并不是CSE, 因为i=j有可能成立.

在DAG中, 表示数组访问如下:

取数组元素的右值（如x = a[ i ]），用新创建的运算符为=[ ]的结点表示，其左右子结点分别代表数组初始值（本例中为a0）和下标i，变量x是该结点标号之一
取数组元素的左值（如a[ j ] = y），用新创建的运算符为[ ]=的结点表示，这个结点的三个子结点分别表示a0 、j和y，没有变量用这个结点标号
- 左值结点的创建杀死了所有当前已建立的，其值依赖于a0的结点
- 被杀死的结点都不再有标号，且不能作为CSE

控制结点（必经结点）描述了流图上如下关系

控制节点
- n是m的控制节点(n dominates m)
- 当且仅当, 从root到m的所有路径都经过n(想到m必须先到n)
- 控制关系构成偏序集
后控制节点
- n是m的后控制节点(n post-dominates m)
- 当且仅当, 从m到exit的所有路径都经过n(m想离开必须经过n)
- 控制关系构成偏序集

变量x的定值：是一个语句，它（可能）赋值给x

无二义的定值：语句真正对x定一个值
二义的定值：
- x作为形式参数，或由于别名的关系
- 通过引用x的指针对x赋值变量a的定值d到达一点p：如果有路径从紧跟d的点到达p，并且在这条路径上d没有被注销定值的注销：如果在这条路径上有对变量a的其它定值，则称前面的定值被注销
只有控制结点的无二义的定值才能注销其它的定值
到达-定值可能是不精确的

几个集合：

例子如下:

Flow InOut

对每个基本块有:

活跃变量：反向计算流信息