编译原理--中间代码优化算法总结

一.常量表达式节省

在每一个基本块中创建常量表，对于当前基本块，每次读入一条语句，就执行以下步骤：

1. 使用常量表中的数据对当前四元式进行替换
2. 如果当前四元式为非赋值型四元式：形如$(w,A,B,t)$，如果A和B都在常量表里面，在执行完$1$步骤之后，就将该表达式删去，并且把t填入到常量表里
3. 如果当前四元式为赋值型四元式，形如$(=,A,-,t)$,如果A是常量，此时分为两种情况，如果$t$就在常量表中，则把$t$的值改成$A$的值，如果$t$不在常量表中，就把$t$填入常量表。如果$A$是变量（不在常量表里）同时$t$是常量（在常量表里），就把$t$从常量表中删去。注意：赋值表达式在这里不能被删去

注意：含有地址相加的不能作为常数写进常数表里

二.基于值编码方式的公共表达式节省

该方法涉及到的数据结构：
$ValuNum$(变量编码），可用表达式代码表$UsableExpr$，等价表 $PAIR$
运行时，区分基本块，对于每一条读入的四元式遵循如下原则
$if$(当前运算符不是赋值运算符)

1. 使用$PAIR$表中的对四元式$(w,A,B,t)$中的可能临时变量$A,B$($A,B$未必是临时变量）进行替换(因为此时有一些临时变量可能已经通过$UsableExpr$删去了,如果该四元式需要被保留不能使用一个不存在的临时变量)

2. 在$ValuNum$表中寻找变量编码，在四元式中替换，不能被替换的变量新建编码。

3. 将替换编码之后的四元式变换成映射编码四元式，形如$(w,i,j,k)$，其中$w$为操作码且$w$不为赋值运算符,其中$i,j,k$为值编码$(>=1)$，如果发现在$UsableExpr$中存在相同的映射编码四元式为$(w,i,j,l)$注意映射编码四元式相同应该定义为w,i,j分别相同而k和l可以相同可以不同则将$k$和$l$所对应变量填入$PAIR$表中，将$k$编码为$l$的编码，删去$(w,i,j,l)$四元式(此时已经没有临时变量$k$了)

$else$

1. $(:=,A,-,B)$，将$B$的编码赋值为$A$，不做其他操作。

三.循环不变外提优化

首先要注意一些不能外提的：

5. 除法表达式不能外提，防止除$0$溢出
6. 含引用型表达式$(a[3]+1)$不外提，注意$a[3]$可以外提
7. 赋值表达式不外提

算法流程

1. 扫描一遍循环内四元式，将全部的右值变量都加入$LoopDef$表中
2. 再扫描一遍，读入四元式$(w,A,B,C)$，如果发现$A$和$B$都不在$LoopDef$表中，就把该四元式外提，同时把$C$从$LoopDef$表中删掉

这里有个问题：如果现在给删了，之后如果再出现这个变量怎么算？
喵喵喵，刚才问完老师了，不能用重复的中间变量
能秒回的老师我太爱了
注意：含有地址相加的可以往外提

练习：