第八章 中间代码优化

常量表达式：任何时候都取固定常数值的表达式 优化方法：用常量值替换原来的运算 – i = 30; j = 2*i; k = i*j; 可用 k=1800代替 优化的关键：知道哪些量取常数值 方法：建立常量定义表ConDef (id, value) 优化算法：
1. 在入口处，ConDef为空； 2. 读取一个四元式tuple,对tuple中的分量进行值替换得newtuple; 3. 若newtuple是(,A,B,t)情形：且A,B都是常数值，则计算A B的值v，
8.2 基本块划分
标号性四元式： (LABEL, -, -, L) (ENTRY, Lf, size, Level) (WHILE, -, -, -) (ENDIF,-,-,-)

转移性四元式： (JMP/JMP0/JMP1, -, -, L) (THEN,E,-,-) (ELSE,-,-,-) (DO,E,-,-) (ENDWHILE,-,-,-) (ENDFUNC,-,-,-)
– 若存在di : (,A,B,ti)UsableExpr,使得dj代码是di代码的公共表达
–
否则，把(tj, NewVN)填入ValuNum中，把dj加到UsableExpr中；

如果newtuple是dj: (ASSIG,A’,-,B’)，进行如下操作：
– – –
从UsableExpr中删除含B’的所有可用表达式代码； 若A’是首次出现，则把(A’,NewVN)填入ValuNum； 令 (B’) = (A’);

循环不变式外 提应从最内层 循环开始！
(ASSIG,1,-i) (WHILE,-,-,-) (LE,i,100,t1) (DO,t1,-,-) (MULTI,i,k,t2) (MULTI,t2,5,t3) (ASSIG,t3,-,z) (MULTI,2,k,t4) (MULTI,t4,2,t5) (ADDI,t4,t5,t6)
1. (*,b,c,t1)
2. (*,b,c,t2)
3. (+,t1,t2,t3) t1
4. (:=,t3,-,a)
ValuNum (b,1) (c,2) (t1,3) (t2,3) (t3,4) (a,4) (d,1) (t4,3) (t5,3) (t6,4) (e,4) UsableExpr 1 3 PAIR

等价四元式: 两个运算型四元式(1,A1,B1,t1)和 (2,A2,B2,t2)，若1= 2, A1和A2的值相同，B1和B2的值 相同，则称这两个四元式等价

公共表达式节省：当一个基本块中出现多个等价四元式时， 除第一个四元式以外，其他的均可节省。 关键：判断四元式等价 方法：建立可用表达式表UsableExpr 建立值编码表ValuNum (id, Vno) 建立临时变量等价表PAIR: (ti,tj)
第八章 中间代码优化
8.1 中间代码优化概述 8.2 基本块划分
8.3 常量表达式局部优化
8.4 公共表达式局部优化 8.5 循环不变式外提 8.6 其他各类优化介绍
8.1 中间代码优化概述

为什么在中间代码上进行优化？
– 有些优化只在中间代码一级进行
优化的目标
– 最小的代价，提高目标程序运行速度 – 是否优化，优化到何种程度取决于编译器设计者

在基本块入口处，置ValuNum, UsableExpr,PAIR为空
逐条扫描基本块的中间代码。
对当前四元式tuple中运算分量进行等价替换(用PAIR替换)， 设所得代码为newtuple.

如果newtuple是dj : (,A’,B’,tj)，进行如下操作：
– –
若A’是首次出现，则把(A’,NewVN)填入ValuNum; 若B’是首次出现，则把(B’,NewVN)填入ValuNum; 式，则删除tuple,将(ti,tj)填入PAIR，同时(tj) = (ti);
8.2 基本块划分

基本块是指程序的一组顺序执行的语句序 列，其中只有一个出口和一个入口。
– 入口：基本块的第一条语句； – 出口：基本块的最后一条语句；
语句1 语句2 语句n 语句1 语句2 语句n 语句1 语句2 语句n
8.2 基本块划分



基本块划分方法： 第一条四元式作为第一个基本块的入口； 当遇到标号性四元式时，结束当前基本块，该标 号性四元式作为新基本块的入口； 当遇到转移性四元式时，结束当前基本块，并把 该转移性四元式作为当前基本块的出口； 当遇到赋值四元式(ASSIG,A,_,x)，且x为变参时， 结束当前基本块，并把该四元式作为当前基本块 的出口。


将(,A,B,t)外提到本层循环入口处； 把t从本层LoopDef移到外层LoopDef. 删除原(,A,B,t)。
5. 重复1-4直到本层循环结束。

i =1; while i<=100 do begin z=i*k*5; a = 2*k+2*k*2; i=i+1; end

(ASSIG,1,-i) (WHILE,-,-,-) (LE,i,100,t1) (DO,t1,-,-) (MULTI,i,k,t2) (MULTI,t2,5,t3) (ASSIG,t3,-,z) (MULTI,2,k,t4) (MULTI,t4,2,t5) (ADDI,t4,t5,t6) (ASSIG,t6,-,a) (ADDI,i,1,t7) (ASSIG,t7,-,i) (ENDWHILE,-,-,-)
y= 1; L: if A and B then x=0 else y=0; x=x+1; y=y-1; while x+y>0 do x=x-1; z=0;
(ADDI,x,y,t3)
(GT,t3,0,t4) (DO,t4,-,-) (SUBI,x,1,t5)
(ASSIG,t5,-,x)
(ENDWHILE,-,-,-) (ASSIG,0,-,z)








LoofDef 1 …… j-1 j
…… …… …… i t1 t2 t3 z t4 t5 t6 a t7 i
(ASSIG,t6,-,a) (ADDI,i,1,t7) (ASSIG,t7,-,i) (ENDWHILE,-,-,-)
(ASSIG,1,-i) (MULTI,2,k,t4) (MULTI,t4,2,t5) (ADDI,t4,t5,t6) (WHILE,-,-,-) (LE,i,100,t1) (DO,t1,-,-) (MULTI,i,k,t2) (MULTI,t2,5,t3) (ASSIG,t3,-,z) (ASSIG,t6,-,a) (ADDI,i,1,t7) (ASSIG,t7,-,i) (ENDWHILE,-,-,-)

中间代码优化的分类
– 按照优化范围：分为局部优化和非局部优化(循
环优化和全局优化) – 按照优化方法：分为常量表达式优化，公共子表 达式优化，循环不变量外提优化
8.1 中间代码优化概述

常量表达式优化(合并常数)
– v = a*b+c, 若a = 2, b=3, c=5 则可用v = 11替换
– u = v +3;

设有源程序如下：
(ASSIG,1,-,y)
(LABEL,-,-,L) (AND,A,B,t) (THEN,t,-,-) (ASSIG,0,-,x) (ELSE,-,-,-) (ASSIG,0,-,y) (ENDIF,-,-,-) (ADDI,x,1,t1) (ASSIG,t1,-,x) (SUBI,y,1,t2) (ASSIG,t2,-,y) (WHILE,-,-,-)
– 凡是循环不变式都外提
– 只外提一定被执行的循环不变式
Biblioteka Baidu
8.5 循环不变式外提优化

1. 2. 3.
4.
生成中间代码过程中构造本层循环的LoopDef; 当结束一层循环的中间代码时，做如下操作： 扫描本层循环的一个中间代码，设(,A,B,t) 若不是可外提操作码，则转1扫描下一代码； 若是外提操作码，则检查A,B是否属于本层 LoopDef，若都不属于，则转4，否则转1； 若A和B都是本层循环不变量，则作：
B1 B2
(ASSIG,1,-,y)
(LABEL,-,-,L) (AND,A,B,t) (THEN,t,-,-) (ASSIG,0,-,x) (ELSE,-,-,-) (ASSIG,0,-,y) (ENDIF,-,-,-) (ADDI,x,1,t1) (ASSIG,t1,-,x)
(SUBI,y,1,t2) (ASSIG,t2,-,y) (WHILE,-,-,-) (ADDI,x,y,t3) (GT,t3,0,t4) (DO,t4,-,-) (SUBI,x,1,t5) (ASSIG,t5,-,x) (ENDWHILE,-,-,-) B6
8.6 其他各类优化介绍
消减运算强度：用强度低的运算代
替强度高的运算 for j=1 to 100 do a[j] = j*3+10 m=13; for j=1 to 100 do begin a[j]=m; m=m+3 end
8.6 其他各类优化介绍
复写传播：把a
= b类型赋值语句去掉 a = b; c=a+1; d=a+c; a=…;
B3 B4
B7
B5
(ASSIG,0,-,z)
B8
程序流图：以基本块为结点的有向图 B1 在一个基本块上进行的优化称为局部优 化 B2 在多个基本块上进行的优化称为非局部 优化 B3 – 循环优化(多个基本块) B4

– 全局优化(整个程序流图)
B5
B6
B7
B8
8.3 常量表达式的局部优化
并在ConDef中填入(t,v),同时删除四元式(,A,B,t)； 4. 若newtuple是(ASSIG,A,-,B)情形：若A是常数，则把(B,A)填入 ConDef中(若已有B的表项，则只需修改B的值)；否则，从ConDef 中删除B的表项。 5. 重复2-4直到基本块结束

x = 10 y = x+1; x=a; z=y+5;
(t2,t1) (t4,t1) (t5,t1) (t6,t3)
5. (:=,b,-,d)
6. (*,d,c,t4) 7. (*,b,c,t5)
t1 t1 8. (+t4,t5,t6)
9. (:=,t6,-,e) t3
8.5 循环不变式外提优化

思想: 将值在循环里不发生改变的表达式运算提 到循环外面进行 i =1; while i<1000 do a[i] = x*y; i =1; t = x*y; while i<1000 do a[i] = t; 关键： 识别循环结构(循环入口，循环体，循环出口) 判断循环不变式 判断循环不变量 方法：

(ASSIG,10,-x) (ADDI,x,1,t1) 11 (ASSIG,t1,-,y) (ASSIG,a,-,x) (ADDI,y,5,t2) 16 (ASSIG,t2,-,z)
ConDef x 10 t1 11 y 11 t2 16 z 16
8.4 公共表达式的局部优化
– 识别循环：(WHILE,-,-,-) –入口 – (DO,e.form,-,-) –循环体开始 – (ENDWHILE,-,-,-) –出口 – 识别循环不变量：建立循环定义表LoopDef
8.5 循环不变式外提优化

外提对象: 除法运算不外提
– while e do
if y=0 then x=y; else x=a/y; 赋值不外提: (赋值操作的左部和右部都是 循环不变式) 外提策略：
u替换成14

公共子表达式节省(消除重复操作)
– t = b*c; e = b*c+b*c; c=b*c+10; d = b*c+d; – t = b*c; e = t+t; c=b*c+10;d = b*c+d;

循环不变量外提
– while (k<10) {a[k] = b*c; k=k+1} – t = b*c; while(k<10){a[k]=t;k=k+1;}