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

1、第八章 中间代码优化 引言 常量表达式优化 公共表达式优化 循环不变式外提 优化的目标：提高程序运行速度 优化的要求：正确性、效果、适度 优化的对象：深层循环和下标变量地址的计算 优化的种类： 常表达式优化（合并常数项） 公共表达式优化（消除重复操作） 循环不变表达式外提 削减运算强度等等 优化方法： 全局优化：全局信息 局部优化：局部信息基本块和程序流图 基本块：单入口单出口的程序段。 程序流图：以基本块为结点的有向图，有向边表示 程序执行的流程。 中间代码基本块的划分：初始代码为第一个基本块的入口遇转移性中间代码时，结束当前基本块，下一条代码作为新基本块的入口遇标号性代码结束当前基本块，代

2、码本身作为新基本块的入口。遇（ASSIG, A, X）时，如果X为引用型形参时结束当前块，并作为该块的出口。基本块划分的例子y:=1;L:if A and B then x:=0 else y:=0;x:=x+1;y:=y-1;while x+y0 do x:=x-1;z:=0; 基本块划分的例子B1:(ASSIG ,1,_,y)B2:(LABEL,L) (AND, A, B, t) (THEN,t,_,_)B3:(ASSIG,0,_,x) (ELSE,_,_,_)B4:(ASSIG,0,_,y) (ENDIF,_,_,_)B5:(ADDI,x,1,t1) (ASSIG,t1,_,x) (SU

3、BI,y,1,t2) (ASSIG,t2,_,y) B1B2 B4B3B5B6B8B7 程序流图例B6:(WHILE,_,_,) (ADDI,x,y,t3) (GT,t3,0,t4) (DO,t4,_,_)B7:(SUBI,x,1,t5) (ASSIG,t5,_,x) (ENDWHILE,_,_,_)B8:(ASSIG,0,_,z) 常表达式局部优化常表达式：任何时候都取固定常数值的表达式处理思想：针对每个基本块，如果一个多元式的两个分量的值已知，则计算其值，并删掉相应的中间代码。原理：常量定值表ConsDef：(Var,Val)。基本块入口置ConstDef为空；对当前多元式的分量利用Con

4、stDef表进行值代换；新多元式形如（,A,B,t）:如果A和B是常数，则计算AB的值v，并将（t,v）填入ConsDef表。并删除该多元式形如（ASSIG,A,-,B）:若A是常数，则把（B,A）填入ConsDef表（对于表中原有的B对应的项，只需修改其值）；否则从ConsDef中删除B的登记项。 常表达式局部优化的例子源程序 中间代码 ConstDef 优化后的代码a:=1 (ASSIG,1,a) (a,1 ) (ASSIG,1,a)b:=a+1 (ADDI,a,1,t1)(a,1)(t1,2) 空 (ASSIG,t1,b) (a,1)(t1,2)(b,2) (ASSIG,2,b)a:=x

5、 (ASSIG,x,a) (t1,2)(b,2) (ASSIG,x,a)c:=b+5 (ADDI,b,5,t2)(t1,2)(b,2)(t2,7) 空 (ASSIG,t2,c) (t1,2)(b,2)(t2,7)(c,7) (ASSIG,7,c) 基于值编码的公共表达式局部优化按值等价原理优化思想：对一个多元式的分量分别编码，具有相同编码的分量等价。值编码表ValuNum，变量（常量）及其值编码。可用表达式代码表UsableExpr，基本块中间代码地址。临时变量等价表TempEqua（PAIR），等价的临时变量偶对。基于值编码的公共表达式节省优化算法基本块入口处初始化：置空表。对块中多元式用T

6、empEqua等价替换生成新多元式。如果多元式的A和B分量未编码，则编新码；如果多元式形如dk:(,A,B,tk)且存在di:(,A,B,ti) UsableExpr中使得dk是di的公共表达式，则删掉dk，将(tk,ti)填入TempEqua表；否则，为tk编码；把dk加入到UsableExpr表；如果多元式形如dk:(ASSIG,A,-,B)则令B的值编码等于A的值编码，填入ValuNum表中；从UsableExpr删除所有含B的中间代码。基于值编码的优化实例A:=B*C+B*CD:=BE:=D*C+B*C循环不变式外提优化循环的识别：入口、重复体以及出口的识别。识别方法：基于程序文本，基

7、于程序图。外提对象：循环不变式安全性: 除法表达式不能外提(除零溢出)赋值表达式不能外提(不一定执行该循环）外提原理：变量信息表LoopDef是在循环体内被定义的变量集合;对每层循环记录LoopDef;若循环体内的多元式(,A,B,t)中的A,B不在本层的LoopDef中,则把(,A,B,t)外提到循环体的入口处。循环优化实例i=1;while(i=100)z=i*k*5;a=2*k+2*k*2;i=i+1;外提实例FOR i :=0 TO 9 DO FOR j :=0 TO 9 DOFOR k:=0 TO 9 DO Aijk:=(ij)k 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, t2 ) ( , j ,10, t3 ) ( , t2, t3, t4 ) ( , i , j, t6 ) ( , t4, k , t5 ) ( , t6,k, t7 ) ( , t7, t5 ) (