中间代码优化

中间代码优化第一页，共二十四页，2022年，8月28日8.1中间代码优化概述为什么在中间代码上进行优化？有些优化只在中间代码一级进行优化的目标最小的代价，提高目标程序运行速度是否优化，优化到何种程度取决于编译器设计者中间代码优化的分类按照优化范围：分为局部优化和非局部优化(循环优化和全局优化)按照优化方法：分为常量表达式优化，公共子表达式优化，循环不变量外提优化第二页，共二十四页，2022年，8月28日8.1中间代码优化概述常量表达式优化(合并常数)v=a*b+c,若a=2,b=3,c=5则可用v=11替换u=v+3;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;}第三页，共二十四页，2022年，8月28日8.2基本块划分基本块是指程序的一组顺序执行的语句序列，其中只有一个出口和一个入口。入口：基本块的第一条语句；出口：基本块的最后一条语句；语句1语句2语句n语句1语句2语句n语句1语句2语句n第四页，共二十四页，2022年，8月28日8.2基本块划分基本块划分方法：第一条四元式作为第一个基本块的入口；当遇到标号性四元式时，结束当前基本块，该标号性四元式作为新基本块的入口；当遇到转移性四元式时，结束当前基本块，并把该转移性四元式作为当前基本块的出口；当遇到赋值四元式(ASSIG,A,_,x)，且x为变参时，结束当前基本块，并把该四元式作为当前基本块的出口。第五页，共二十四页，2022年，8月28日8.2基本块划分标号性四元式：(LABEL,-,-,L)(ENTRY,Lf,size,Level)(WHILE,-,-,-)(ENDIF,-,-,-)转移性四元式：(JMP/JMP0/JMP1,-,-,L)(THEN,E,-,-)(ELSE,-,-,-)(DO,E,-,-)(ENDWHILE,-,-,-)(ENDFUNC,-,-,-)第六页，共二十四页，2022年，8月28日设有源程序如下：

y=1;L:ifAandBthenx=0elsey=0;x=x+1;y=y-1;whilex+y>0dox=x-1;z=0;(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,-,-,-)(ASSIG,0,-,z)第七页，共二十四页，2022年，8月28日(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,-,-,-)(ASSIG,0,-,z)B1B2B3B4B5B6B7B8第八页，共二十四页，2022年，8月28日程序流图：以基本块为结点的有向图在一个基本块上进行的优化称为局部优化在多个基本块上进行的优化称为非局部优化循环优化(多个基本块)全局优化(整个程序流图)B2B5B3B4B1B6B7B8第九页，共二十四页，2022年，8月28日8.3常量表达式的局部优化常量表达式：任何时候都取固定常数值的表达式优化方法：用常量值替换原来的运算i=30;j=2*i;k=i*j;可用k=1800代替优化的关键：知道哪些量取常数值方法：建立常量定义表ConDef(id,value)优化算法：在入口处，ConDef为空；读取一个四元式tuple,对tuple中的分量进行值替换得newtuple;若newtuple是(,A,B,t)情形：且A,B都是常数值，则计算AB的值v，并在ConDef中填入(t,v),同时删除四元式(,A,B,t)；若newtuple是(ASSIG,A,-,B)情形：若A是常数，则把(B,A)填入ConDef中(若已有B的表项，则只需修改B的值)；否则，从ConDef中删除B的表项。重复2-4直到基本块结束第十页，共二十四页，2022年，8月28日x=10y=x+1;x=a;z=y+5;(ASSIG,10,-x)(ADDI,x,1,t1)(ASSIG,t1,-,y)(ASSIG,a,-,x)(ADDI,y,5,t2)(ASSIG,t2,-,z)ConDefx10t111y11t216z161116第十一页，共二十四页，2022年，8月28日8.4公共表达式的局部优化等价四元式:两个运算型四元式(1,A1,B1,t1)和(2,A2,B2,t2)，若1=2,A1和A2的值相同，B1和B2的值相同，则称这两个四元式等价公共表达式节省：当一个基本块中出现多个等价四元式时，除第一个四元式以外，其他的均可节省。关键：判断四元式等价方法：建立可用表达式表UsableExpr

建立值编码表ValuNum(id,Vno)

建立临时变量等价表PAIR:(ti,tj)第十二页，共二十四页，2022年，8月28日在基本块入口处，置ValuNum,UsableExpr,PAIR为空逐条扫描基本块的中间代码。对当前四元式tuple中运算分量进行等价替换(用PAIR替换)，设所得代码为newtuple.如果newtuple是dj:(,A’,B’,tj)，进行如下操作：若A’是首次出现，则把(A’,NewVN)填入ValuNum;若B’是首次出现，则把(B’,NewVN)填入ValuNum;若存在di:(,A,B,ti)UsableExpr,使得dj代码是di代码的公共表达式，则删除tuple,将(ti,tj)填入PAIR，同时(tj)=(ti);否则，把(tj,NewVN)填入ValuNum中，把dj加到UsableExpr中；如果newtuple是dj:(ASSIG,A’,-,B’)，进行如下操作：从UsableExpr中删除含B’的所有可用表达式代码；若A’是首次出现，则把(A’,NewVN)填入ValuNum； 令(B’)=(A’);第十三页，共二十四页，2022年，8月28日1.(*,b,c,t1)2.(*,b,c,t2)3.(+,t1,t2,t3)4.(:=,t3,-,a)5.(:=,b,-,d)6.(*,d,c,t4)7.(*,b,c,t5)8.(+t4,t5,t6)9.(:=,t6,-,e)ValuNumUsableExprPAIR(b,1)(c,2)(t1,3)1(t2,t1)(t2,3)(t3,4)3(a,4)(d,1)(t4,3)(t4,t1)(t5,3)(t5,t1)(t6,4)(t6,t3)(e,4)t1t1t1t3第十四页，共二十四页，2022年，8月28日8.5循环不变式外提优化思想:将值在循环里不发生改变的表达式运算提到循环外面进行i=1;whilei<1000doa[i]=x*y;i=1;t=x*y;whilei<1000doa[i]=t;关键：识别循环结构(循环入口，循环体，循环出口)判断循环不变式判断循环不变量方法：识别循环：(WHILE,-,-,-)–入口

(DO,e.form,-,-)–循环体开始

(ENDWHILE,-,-,-)–出口识别循环不变量：建立循环定义表LoopDef第十五页，共二十四页，2022年，8月28日8.5循环不变式外提优化外提对象:除法运算不外提whileedo ify=0thenx=y; elsex=a/y;赋值不外提:(赋值操作的左部和右部都是循环不变式)外提策略：凡是循环不变式都外提只外提一定被执行的循环不变式第十六页，共二十四页，2022年，8月28日8.5循环不变式外提优化生成中间代码过程中构造本层循环的LoopDef;当结束一层循环的中间代码时，做如下操作：扫描本层循环的一个中间代码，设(,A,B,t)若不是可外提操作码，则转1扫描下一代码；若是外提操作码，则检查A,B是否属于本层LoopDef，若都不属于，则转4，否则转1；若A和B都是本层循环不变量，则作：将(,A,B,t)外提到本层循环入口处；把t从本层LoopDef移到外层LoopDef.删除原(,A,B,t)。重复1-4直到本层循环结束。第十七页，共二十四页，2022年，8月28日i=1;whilei<=100dobeginz=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,-,-,-)第十八页，共二十四页，2022年，8月28日(ASSIG,1,-i)(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,-,-,-)1……j-1jt1t2t3zt4t5t6at7i………………LoofDefi(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,-,-,-)循环不变式外提应从最内层循环开始！(MULTI,2,k,t4)(MULTI,t4,2,t5)(ADDI,t4,t5,t6)第十九页，共二十四页，2022年，8月28日8.6其他各类优化介绍消减运算强度：用强度低的运算代替强度高的运算forj=1to100doa[j]=j*3+10m=