编译原理及实现技术：第八章 中间代码优化

1、第八章第八章 中间代码优化中间代码优化本章内容本章内容 概述概述 常量表达式优化常量表达式优化 公共表达式优化公共表达式优化 循环不变式外提循环不变式外提概述概述 优化的目标优化的目标 提高程序执行效率提高程序执行效率 优化的要求优化的要求 有效有效 平衡平衡 优化的对象优化的对象 深层循环和下标变量地址的计算深层循环和下标变量地址的计算概述（续）概述（续） 优化的种类优化的种类 常表达式优化（合并常数项）常表达式优化（合并常数项） 公共表达式优化（消除重复操作）公共表达式优化（消除重复操作） 循环不变表达式外提循环不变表达式外提 削减运算强度削减运算强度 优化方法：优化方法： 全局优化全局优

2、化 局部优化：源代码、中间代码、目标代码局部优化：源代码、中间代码、目标代码常表达式优化常表达式优化 基本块与程序流图基本块与程序流图 常表达式局部优化方法常表达式局部优化方法基本块和程序流图基本块和程序流图基本块：基本块：单入口单出口的程序段。单入口单出口的程序段。程序流图：程序流图：以基本块为结点的有向图，有向边表示以基本块为结点的有向图，有向边表示 程序执行的流程。程序执行的流程。中间代码基本块的划分：中间代码基本块的划分： 初始代码为第一个基本块的入口初始代码为第一个基本块的入口 遇转移性中间代码时，结束当前基本块，下一条代码遇转移性中间代码时，结束当前基本块，下一条代码作为新基本块的

3、入口作为新基本块的入口 遇标号性代码结束当前基本块，代码本身作为新基本遇标号性代码结束当前基本块，代码本身作为新基本块的入口。块的入口。 遇（遇（ASSIG,A,n,XASSIG,A,n,X）时，如果时，如果X X为引用型形参时结束当为引用型形参时结束当前块，并作为该块的出口。前块，并作为该块的出口。基本块划分的例子基本块划分的例子y = 1 ;y = 1 ;ifif（A&BA&B）x = 0;x = 0;else y = 0 ;else y = 0 ;x = x + 1 ;x = x + 1 ;y = y 1 ;y = y 1 ;while (x + y 0) x = x -

4、 1 ;while (x + y 0) x = x - 1 ;z = 0 ; z = 0 ; 基本块划分的例子基本块划分的例子B1B1:(ASSIG ,1,_,y):(ASSIG ,1,_,y)B2B2:(LABEL,L):(LABEL,L) (AND, A, B, t) (AND, A, B, t) (THEN,t,_,_)(THEN,t,_,_)B3:(ASSIG,0,_,x)B3:(ASSIG,0,_,x) (ELSE,_,_,_)(ELSE,_,_,_)B4:(ASSIG,0,_,y)B4:(ASSIG,0,_,y) (ENDIF,_,_,_)(ENDIF,_,_,_)B5:(ADDI

5、,x,1,t1)B5:(ADDI,x,1,t1) (ASSIG,t1,_,x) (ASSIG,t1,_,x) (SUBI,y,1,t2) (SUBI,y,1,t2) (ASSIG,t2,_,y) (ASSIG,t2,_,y) B B1 1B B2 2 B B4 4B B3 3B B5 5B B6 6B B8 8B B7 7 程序流图例程序流图例B6B6:(WHILE,_,_,):(WHILE,_,_,) (ADDI,x,y,t3) (ADDI,x,y,t3) (GT,t3,0,t4) (GT,t3,0,t4) (DO,t4,_,_)(DO,t4,_,_)B7:(SUBI,x,1,t5)B7:(

6、SUBI,x,1,t5) (ASSIG,t5,_,x) (ASSIG,t5,_,x) (ENDWHILE,_,_,_)(ENDWHILE,_,_,_)B8:(ASSIG,0,_,z) B8:(ASSIG,0,_,z) 常表达式局部优化常表达式局部优化 常表达式的定义常表达式的定义 任何时候都取固定常数值的表达式任何时候都取固定常数值的表达式 处理思想处理思想：针对每个基本块，如果一个多元式的两针对每个基本块，如果一个多元式的两个分量的值已知，则计算其值，并删掉相应个分量的值已知，则计算其值，并删掉相应的中间代码。的中间代码。 常表达式优化原理常表达式优化原理常量定值表常量定值表ConsDefC

7、onsDef：( (Var,ValVar,Val) )。 基本块入口置基本块入口置ConstDefConstDef为空；为空； 对当前多元式的分量利用对当前多元式的分量利用ConstDefConstDef表进行值代表进行值代换；换； 新多元式新多元式形如（形如（ , ,A,B,tA,B,t）: :如果如果A A和和B B是常数，是常数，则计算则计算A A B B的值的值v v，并将（并将（t,vt,v）填入填入ConsDefConsDef表。表。并并 删除该多元式删除该多元式 形如（形如（ASSIG,A,n,BASSIG,A,n,B）: :如果如果A A是常数，则把是常数，则把（B,AB,A）

8、填入填入ConsDefConsDef表，若已有表，若已有B B项，只需修项，只需修改其值；否则从改其值；否则从ConsDefConsDef中删除中删除B B的登记项。的登记项。 常表达式局部优化的例子常表达式局部优化的例子源程序源程序 中间代码中间代码 ConstDef ConstDef 优化后的代码优化后的代码a=1 (ASSIG,1,-,a) (a,1 ) a=1 (ASSIG,1,-,a) (a,1 ) (ASSIG,1,-,a)(ASSIG,1,-,a)b=a+1 (ADDI,a,1,t1) (a,1)(t1,2) b=a+1 (ADDI,a,1,t1) (a,1)(t1,2) ( )

9、( ) (ASSIG,t1,-,b) (a,1)(t1,2)(b,2) (ASSIG,t1,-,b) (a,1)(t1,2)(b,2)(ASSIG,2,-,b)(ASSIG,2,-,b)a=x (ASSIG,x,-,a) (t1,2)(b,2)a=x (ASSIG,x,-,a) (t1,2)(b,2) (ASSIG,x,-,a)(ASSIG,x,-,a)c=b+5 (ADDI,b,5,t2) (t1,2)(b,2)(t2,7) c=b+5 (ADDI,b,5,t2) (t1,2)(b,2)(t2,7) ( )( ) (ASSIG,t2,-,c) (t1,2)(b,2)(t2,7)(c,7) (

10、ASSIG,7,c) (ASSIG,t2,-,c) (t1,2)(b,2)(t2,7)(c,7) (ASSIG,7,c) 基于值编码的基于值编码的公共表达式局部优化公共表达式局部优化 按值等价原理按值等价原理 优化思想：优化思想： 对一个多元式的分量分别编码，具有相同编码对一个多元式的分量分别编码，具有相同编码的分量等价。的分量等价。 值编码表值编码表ValuNnmValuNnm 可用表达式代码表可用表达式代码表UsableExprUsableExpr 临时变量等价表临时变量等价表TempEquaTempEqua基于值编码的基于值编码的ECCECC优化算法优化算法 入口处初始化：入口处初始化：

11、 ValueNum,UsableExpValueNum,UsableExp和和TempEquaTempEqua为空。为空。 对当前多元式用对当前多元式用TempEquaTempEqua等价替换，生成等价替换，生成NewTuple.NewTuple. 如果如果NewTupleNewTuple的的A A和和B B分量是未编码的，则编新码；分量是未编码的，则编新码； 如果多元式形如如果多元式形如dk:(dk:( ,A,A ,B,B ,tk ),tk ) 若存在若存在didi UsableExprUsableExpr使得使得dkdk是是didi的的ECCECC，则删掉则删掉dkdk，将将( (tk,t

12、tk,ti i) )填入填入TempEquaTempEqua表；表； 否则，为否则，为tktk编码；把编码；把dkdk加入到加入到UsableExprUsableExpr表；表； 如果多元式形如如果多元式形如dk:(ASSIG,Adk:(ASSIG,A ,-,B,-,B ) ) 则令则令B B 的值编码等于的值编码等于A A 的值编码，的值编码，填入填入ValuNumValuNum表中；表中；从从UsableExprUsableExpr删除所有含删除所有含B B的中间代码。的中间代码。基于值编码的优化实例基于值编码的优化实例A=BA=B* *C+BC+B* *C;C;D=B;D=B;E=DE=

13、D* *C+BC+B* *C;C;循环不变式外提优化循环不变式外提优化 循环的识别：循环的识别：识别循环的入口、重复体、出口部识别循环的入口、重复体、出口部分分 识别方法：识别方法：基于程序文本，基于程序图。基于程序文本，基于程序图。 外提对象：外提对象：循环不变式循环不变式 安全性安全性: : 除法表达式不能外提除法表达式不能外提( (除零溢出除零溢出) )赋值表赋值表达式不能外提达式不能外提( (不一定执行该循环）不一定执行该循环） 原理：原理： 定义定义LoopDefLoopDef是在循环体内被定义的变量集合是在循环体内被定义的变量集合; ; 对每层循环记录对每层循环记录LoopDef;

14、LoopDef;若循环体内的多元式若循环体内的多元式( ( , ,A,B,tA,B,t) )中的中的A,BA,B不在本层的不在本层的LoopDefLoopDef中中, ,则把则把( ( , ,A,B,t)A,B,t)外提到循环体的入口处。外提到循环体的入口处。循环优化实例循环优化实例i=1;i=1;while (i=100)while (i=100)z=iz=i* *k k* *5;5;a=2a=2* *k+2k+2* *k k* *2;2;i=i+1;i=i+1; FOR i =0 TO 9 DOFOR i =0 TO 9 DO FOR j =0 TO 9 DO FOR j =0 TO 9 DOFOR k=0 TO 9 DO FOR k=0 TO 9 DO Aijk=(i Aijk=(i j)j) k k ENDFORENDFOR ENDFOR ENDFOR ENDFOR ENDFOR 外提实例外提实例 ( , i ,100, t1 ) ( , A,t1, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , t4, k , t5 ) ( , i , j, t6 ) ( , t6, k, t7 ) ( = =, t7, -, t5 ) ( , i ,100, t1 ) ( , A,t1, t