资源描述：
《川师编译原理课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十一章代码优化教学目的：让学生了解几种常见的代码优化技术，掌握局部优化、循环优化、数据流分析方法。教学重点：代码优化技术、基本块的DAG及应用。课时分配：4学时。教学过程：7/27/2021111.1优化技术简介一、代码优化分类编译前端中间代码优化目标代码中间代码目标代码优化1、按阶段分类中间代码优化、目标代码优化。2、按程序范围分类局部（基本块）优化、循环优化、全局优化。二、代码优化原则等价原则、高效原则。三、代码优化技术例：有如下源程序段，求其四元式形式的中间代码，并优化之(设A为实型数组，每个元素占四个字节)。P：=0；fori:=1to20doP:=P+A[i
2、]*B[i];1、数组的存储空间设数组中每个元素占t个存储空间，则A[1]A[2]A[3]A[4].......数组首地址Addr(A)A[i]的地址为：Addr(A)+(i-1)*t=Addr(A)-t+i*t令为T=Addr(A)-t，则A[i]的地址为：T+i*t(1)P：=0(2)i:=1(3)T1:=4*i(4)T2:=addr(A)-4(5)T3:=T2[T1](=[])(6)T4:=4*i(7)T5:=addr(B)-4(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)i:=i+1(12)IFi<=20GOTO(3)2、程序段
3、对应的中间代码为如下四元式序列B2：B1：每个元素占四个字节，故t=41）删除公共子表达式(4*i)和代码外提(4)(7)(3)T1:=4*i(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)i:=i+1(12)IFi<=20GOTO(3)(1)P：=0(2)i:=1(4)T2:=addr(A)-4(7)T5:=addr(A)-4B1：B2：2）强度削弱(T1的乘法变为加法)(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T4](9)T7:=T3*T6(10)P:=P+T7(11)
4、i:=i+1(3')T1:=T1+4(12)IFi<=20GOTO(5)(1)P：=0(2)i:=1(4)T2:=addr(A)-4(7)T5:=addr(A)-4(3)T1:=4*iB1：B2：3）变换循环控制条件(T1<=80)、合并已知量(T1:=4)和复写传播(T6:=T5[T1])(5)T3:=T2[T1](6)T4:=T1(8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(11)i:=i+1(3')T1:=T1+4(12)IFT1<=80GOTO(5)(1)P：=0(2)i:=1(4)T2:=addr(A)-4(7)T5:=addr(A
5、)-4(3)T1:=4B1：B2：4）删除无用赋值(2)、(6)、(11)(5)T3:=T2[T1](8)T6:=T5[T1](9)T7:=T3*T6(10)P:=P+T7(3')T1:=T1+4(12)IFT1<=80GOTO(5)(1)P：=0(4)T2:=addr(A)-4(7)T5:=addr(A)-4(3)T1:=4B1：B2：11.2局部优化一、局部优化的概念1、基本块的定义：一个基本块是指程序中一顺序执行的语句序列，其中只有一个入口和一个出口。入口是程序第一个语句或转移语句的目标语句，或转移语句的后继第一个语句。出口是程序最后一个语句或转移语句。2、对中间
6、代码求基本块后，凡是没被纳入某个基本块的语句，则是控制流程无法到达的、也不会被执行的语句，可删去。3、在基本块范围内的优化称为局部优化。二、基本块的变换1、提高运算效率的代数变换；2、四种保结构变换１）删除公共子表达式；２）删除无用代码；３）重新命名临时变量：引入新的临时变量不影响基本块的运算结果；4）变换语句次序：当两个语句相互没有引用关系时，变换语句次序也不影响基本块的运算结果。例如：1)t1:=a+b;2)t2:=c+d;3)t1:=t2+b;其中，1)和2)可交换次序。三、基本块的DAG表示1、DAG图即有向无环图例：n1n2n2n22、附加信息的DAG图1）以
7、四元式为结点构造中间代码的DAG，其中，ni表示结点编号，结点下符号为结点标记，结点右边符号为附加标识符。2）基本块中各种四元式及对应DAG图的结点形式：(0)A:=B(:=,B,_,A)n1AB(1)A：=opB(op,B,_,A)(2)A：=BopC(:=,B,C,A)n1n2ABopn1n3ABopn2C(3)A：=B[C](=[],B[C],_,A)或(=[],B,C,A)(4)ifBropCgoto(s)(jrop,B,C,(s))n1n3AB=[]n2Cn1n3(s)Bropn2C(5)D[C]:=B([]=,B,_,D[C]
