自己收集整理的
错误在所难免
仅供参考交流
如有错误
请指正！谢谢
中间代码优化
实验目的
1 掌握基于中间代码的基本块划分方法
2 掌握常量表达式优化的基本原理
3 掌握公共表达式优化的基本原理
4 掌握循环不变式外提的基本原理
实验学时
4学时
实验要求
1 能够对中间代码正确划分基本块
2 理解常量表达式局部优化算法
3 理解公共表达式局部优化算法
4 理解循环不变式外提优化算法
实验原理
1. 基本块划分方法
所谓基本块是指程序的一组顺序执行的语句序列
其中只有一个出口和一个入口
入口就是其中的第一个语句
出口就是其中的最后一个语句
中间代码一级的基本块划分方法如下：
⑴ 第一个中间代码作为第一个基本块的入口；
⑵ 当遇标号性中间代码时
结束当前基本块
并作为新基本块的入口中间代码；
⑶ 当遇转移性中间代码时
结束当前基本块
并把该转移性中间代码作为当前基本块的出口中间代码
其后的中间代码作为新基本块的入口中间代码；
⑷ 当遇形如（ASSIG , A , - , X）的赋值中间代码
且 X 为引用形参时
结束当前基本块
并把该中间代码作为当前基本块的出口中间代码
2. 常量表达式优化
常表达式节省的基本思想是：如果一个四元式的两个运算分量都是取常数值
则由编译器将其值计算出来
以所求得的值替换原来的运算
并删除当前四元式
为了实现常表达式节省
我们需要定义一个常数定值表
其元素是二元组(var,val),其中var是变量名
val是变量名所对应的常数
如果在常量定值表中有(Y,5)
表示当前的Y一定取值5
并且在Y未被重新赋值以前
后面出现的Y都可替换成5(称为值替换或值传播)；如果一个四元式的两个分量都在常量定值表中
即为常数值
则计算当前四元式的结果值
将表示结果的临时变量和结果值填入常量定值表
并删除当前四元式；如果变量Y被赋值为非常数值
则从所构造的常量定值表中删除变量Y的登记项
以表示变量Y不取常数值
3. 公共表达式优化
我们对SNL源程序采用基于值编码的公共表达式局部优化
值编码方法的主要思想是： 对中间代码中出现的每个分量
确定一个编码(值编码)
使得具有相同编码的分量等价(反之不然)
4. 循环不变式外提优化
因为循环体中可能包含很多基本块
所以循环不变式外提优化不能以基本块为单位
是在整个循环范围内进行的优化
我们规定要将循环不变式外提到循环的前置节点中
循环的前置节点是在循环的入口节点前建立的一个新的节点(基本块)
循环的入口节点是它唯
一的后继
并且原中间代码中从循环外转向循环入口节点的代码修改为转向循环的前置节点
因为循环的入口节点是唯一的
所以前置节点也是唯一的
要实现循环不变式外提
首先要识别出循环的入口部分、循环体部分和出口部分
SNL只有一种循环
就是while循环
故只要考虑while循环的不变式外提就可以了
while的循环体部分紧接着while的入口部分
故只需识别出循环入口和循环出口部分
四元式中间代码中
入口标号和出口标号
分别用WHILESTART和ENDWHILE标志
实验步骤
1．常量表达式优化
（1）输入输出：因此常量表达式节省方法输入的是四元式中间代码
输出的是经过常量表达式优化后的中间代码
（2）数据结构：
对源程序进行常量表达式节省的优化需要用到常量定值表ConstDefT
常量定值表用于记录当前可用的常量定值
我们将常量定值表定义成一个双向链表
其结构图示如下：
former variable
constValue next （3）基本算法
1) 在基本块入口处置ConsDef表为空；
2) 读当前中间代码tuple；
3) 对tuple中的分量进行值替换；
a．对于运算代码和关系比较代码
替换两个运算分量；
b．对于赋值语句、条件跳转语句、输出语句
替换第一个ARG结构；
c．对于地址加运算AADD
替换第二个ARG结构；
d．其他代码
不做任何替换；
4) tuple是运算代码和关系比较代码(w, A ,B , t )情形：若A和B都是常数
则计算A w B的值v
并在ConsDef表中填入(t ,v )
同时删除本tuple
其中判断运算分量是否是常数的方法为：若分量是常数ARG结构
则当前是常数；若分量是变量
且在常量定值表中有定值
则当前也为常数；
5) 若tuple是赋值代码(ASSIG ,A ,B)情形：若A是常数
则把(B,A)填入ConsDef表中(具体做法：若已有B项
则只需改值
否则
增加一项)；否则
从ConsDef删除B的登记项(具体做法：若没有B项
则什么也不做
否则
删掉一项)；
6) 转2)
直到基本块结束；
7) 基本块结束
释放占用的常量定值表空间
2．公共表达式优化
（1）输入输出：公共表达式节省优化作为独立的一遍
其输入是经过常量表达式优化或者没有经过常量表达式优化的中间代码
输出是经过公共表达式优化后的中间代码
（2）数据结构：
* 编码表ValuNum：记录常量和变量的编码；
Arg
access
CodeInfo
next valueCode
twoCode Valuecode
addrcode
* 可用表达式代码表UsableExpr：用来表示哪些中间代码是当前可用的；
Code
mirrorC
Next
* 临时变量的等价表TempEqua：用来记录哪些临时变量是等价的
arg1
arg2
Next （3）基本算法
1）在基本块入口处
置ValuNum、UsableExpr
、PAIR为空；
2）逐条扫描基本块的中间代码；
3）对当前四元式tuple中运算分量进行等价替换
设所得代码为 newtuple ；
4）如果 newtuple 是 dj : ( ω , A' , B' , tj ) 型
做如下操作：
若A' 是首次出现
则把（A', NewVN）填入ValuNum；
若B' 是首次出现
则把（B', NewVN）填入ValuNum；
若存在di : ( ω , A , B , ti ) ∈UsableExpr
使得dj 代码是di 代码的公共表达式
则 删除tuple
并将 ( ti , tj ) 填入 PAIR
同时μ(tj ):=μ(ti ) ；否则
把（tj , NewVN）填入ValuNum中
把 dj 加到 UsableExpr 中；
如果 newtuple 是 dj : ( ASSIG , A' , - , B' ) 型
做如下操作：
从UsableExpr 中删除含 B' 的所有可用表达式代码；
若A' 是首次出现
则把（A', NewVN）填入ValuNum ；
令μ( B' )＝μ( A' )
3. 循环不变式外提
（1）输入输出：循环不变式优化作为独立的一遍
其输入可以是经过或没经过常量表达式优化和公共表达式优化的中间代码
其输出是经过循环不变式优化后的中间代码
而且为了清晰地体现代码对变量定值表的改变情况
我们还输出了经过每条代码改变后的变量定值表
（2）数据结构
1）变量定值表VarDefSet：因为外层循环的变量定义集一定包含内层循环的变量定义集
因此多层循环可以只用一个变量定义表
而每层循环信息中的变量定义集只需记录本层循环中的变量定值在变量定值表中的开始位置
变量定值表用一个指向变量ARG结构的指针数组表示
而开始位置即为数组的下标
2）循环信息表LoopInfo：每层循环一个
state
whileEntry
varDef
whileEnd
3) 循环信息栈：因为循环可以嵌套
需要用到一个栈
以保存未结束循环的信息
栈的元素就是循环的信息表的内容
每当进入新一层循环时
将新循环的信息压入栈；而每当退出循环时
将删除栈顶元素
以使外层循环成为当前循环