代码优化与目标代码生成(介绍)-编译原理-09-(一).

2019/12/21第9章代码优化与目标代码生成（介绍）代码优化代码生成2019/12/22引例fori=1tonstepmdos[i]:=4*i+n*ma:=4*m;s1:=4+n*m;fori=1tonstepmdo{s[i]:=s1;s1:=s1+a}a:=4*m;s[1]=4+n*m;fori=2tonstepmdos[i]:=s[i-1]+a;2019/12/23代码优化代码优化的任务通过等价的程序变换，获得执行速度快、占用空间少的程序2019/12/24代码优化fori=2to10000do{T=0;forj=2toi-1doifi=i/j*jthen{T=1;break}ifT=0thenprint(i)}fori=2to10000do{T=0;forj=2toi/2doifi=i/j*jthen{T=1;break}ifT=0thenprint(i)}fori=2to10000do{T=0;forj=2tosqrt(i)doifi=i/j*jthen{T=1;break}ifT=0thenprint(i)}算法优化例：顺序查找与hash算法有效的数据结构和算法领域相关2019/12/25《编译原理》(PrinciplesofCompiling)主讲：蒋宗礼2019/12/26上次课主要内容——符号表管理关键字表关键字名字关键字标识begin112end113while114名字信息1信息2……信息nsum1real所在层定义/引用……2019/12/27上次课主要内容——符号表管理层次表所在层性质起点终点直接外层本层计数2019/12/28上次课主要内容——符号表管理过程表变量表标号表名字种类类型地址参数个数层次……定义/引用名字种类类型长度地址……标志2019/12/29上次课主要内容代码优化通过等价变换，获得执行速度快、占用空间少的程序算法优化2019/12/210代码优化编译优化目标代码优化：机器相关特殊指令的利用特殊结构的高效利用：SIMD、MIDM、流水、向量机中间代码优化：机器无关如：常数计算、公共代码段的提取2019/12/211中间代码优化局部优化基本块内部（不包括各种转移控制）全局优化循环优化、控制流分析与化简、数据流分析2019/12/2129.1基本块和流图基本块控制流从第一语句进入，从最后一条语句离开语句序列中间没有停止或分枝关键：确定每个基本块的入口(1)i:=m-1(2)j:=n(3)t1:=4*n;(4)v:=a[t1](5)i:=i+1(6)t2:=4*i;(7)t3:=a[t2];(8)ift3vgoto(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5vgoto(9)转移语句的下一条语句转移语句的目标第一条语句2019/12/213基本块的划分1)定义入口语句代码序列的第一语句转移语句的目标语句转移语句的下一条语句2)定义基本块一入口语句到下一入口语句之前一入口语句到转移语句或停语句(1)i:=m-1(2)j:=n(3)t1:=4*n;(4)v:=a[t1](5)i:=i+1(6)t2:=4*i;(7)t3:=a[t2];(8)ift3vgoto(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5vgoto(9)2019/12/214程序流图的构造程序流图Ｇ＝｛Ｎ，Ｅ，n0｝以基本块为结点，以控制流为有向边Ｎ：基本块集n0：含首语句的基本块Ｅ：有向边集合(A,B)A的出口是转移语句，转向B的入口A的出口不是转移语句，B紧跟A之后2019/12/215例9-1：基本块划分和流图i=m-1;j=n;v=a[n];while(1){while(a[++i]v);while(a[--j]v);if(i≥j)thenbreak;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;2019/12/216三地址码序列(1)i:=m-1(2)j:=n(3)t1:=4*n;(4)v:=a[t1](5)i:=i+1(6)t2:=4*i;(7)t3:=a[t2];(8)ift3vgoto(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5vgoto(9)(13)ifi≥jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x入口：代码序列的第一语句转移语句的目标语句转移语句下一条语句i=m-1;j=n;v=a[n];while(a[++i]v);while(a[--j]v);if(i≥j)thenbreak;x=a[i];a[i]=a[j];a[j]=x;x=a[i];a[i]=a[n];a[n]=x;2019/12/217程序流图B1(1-4)B2(5-8)B3(9-12)B4(13)B5(14-22)B6(23-30)(8)ift3vgoto(5)(12)ift5vgoto(9)(13)ifi≥jgoto(23)(22)goto(5)2019/12/2189.2局部优化(1)合并已知量常数表达式计算t3:=110*xt1:=5+6t2:=t1*10t3:=t2*x2019/12/219(1)i:=m-1(2)j:=n(3)t1:=4*n;(4)v:=a[t1](5)i:=i+1(6)t2:=4*i;(7)t3:=a[t2];(8)ift3vgoto(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5vgoto(9)(13)ifi≥jgoto(23)(14)t6:=4*i(15)x:=a[t6](16)t7:=4*i(17)t8:=4*j(18)t9:=a[t8](19)a[t7]:=t9(20)t10:=4*j(21)a[t10]:=x(22)goto(5)(23)t11:=4*i(24)x:=a[t11](25)t12:=4*i(26)t13:=4*n(27)t14:=a[t13](28)a[t12]:=t14(29)t15:=4*n(30)a[t15]:=x(2)重新命名临时变量t1代替t2,t4,t6,t7,t10,t11,t12,t15t3代替t5,t8,t13,t142019/12/220(3)删除基本块内的公共子表达式(14)(16)、(17)(20)、(23)(25)、(26)(29)(14)t1:=4*i(15)x:=a[t1](16)t1:=4*i(17)t3:=4*j(18)t9:=a[t3](19)a[t1]:=t9(20)t1:=4*j(21)a[t1]:=x(22)goto(5)(23)t1:=4*i(24)x:=a[t1](25)t1:=4*i(26)t3:=4*n(27)t3:=a[t3](28)a[t1]:=t3(29)t1:=4*n(30)a[t1]:=x(14)t1:=4*i(15)x:=a[t1](17)t3:=4*j(18)t9:=a[t3](19)a[t1]:=t9(21)a[t3]:=x(22)goto(5)(23)t1:=4*i(24)x:=a[t1](26)t3:=4*n(27)t3:=a[t3](28)a[t1]:=t3(30)a[t3]:=x2019/12/221(4)删除死代码未出现在程序流图中的代码赋值但未引用的指令(5)交换语句次序减少临时变量t1:=a+xt2:=b*yt:=t1+zp:=t*xt1:=a+xt:=t1+zt1:=b*yp:=t*x2019/12/2229.3循环优化循环体是优化的重点反复执行循环的定义有唯一入口点的强连接子图强连接子图任意两结点间的通路上各结点属于子图2019/12/223方法1：代码外提将循环不变运算移到循环外例：程序优化i=0;while(i20){x=4*i;i++;y=z*6+x}2019/12/224(3)x:=4*i(4)i:=i+1(5)t1:=z*6(6)y:=t1+x(7)goto(2)(4)x:=4*i(5)i:=i+1(6)y:=t1+x(7)goto(3)(1)i:=0(1)i:=0(2)t1:=z*6(2)ifi≥20goto(8)(3)ifi≥20goto(8)2019/12/225方法2：强度削弱用较快的操作代替较慢的操作+替代*；*替代**循环归纳变量相关的强度削弱X:=K*i+Y相关计算i:=i+C归纳变量（K、C、Y为循环不变量）改为X:=X+KC设X的初值=Y-KC，KC为K*C的结果2019/12/226(4)x:=4*i(5)i:=i+1(6)y:=t1+x(7)goto(3)(5)x:=x+4(4*1)(6)i:=i+1(7)y:=t1+x(8)goto(4)(1)i:=0(2)t1:=z*6(1)i:=0(2)t1:=z*6(3)x:=-4(3)ifi=20goto(8)(4)ifi=20goto(9)2019/12/227方法3:消除归纳变量利用归纳变量相关的计算代替归纳变量的计算条件表达式的修改无用语句的删除优化效果语句数、乘除法数、变址运算、一般运算2019/12/228(5)x:=x+4(6)i:=i+1(7)y:=t1+x(8)goto(4)(4)x:=x+4(5)y:=t1+x(6)goto(3)(1)i:=0(2)t1:=z*6(3)x:=-4(1)t1:=z*6(2)x:=-4(4)ifi≥20goto(9)(3)ifx≥76goto(7)2019/12/2299.4目标代码生成代码生成的任务针对目标语言的特殊性，生成高性能的目标代码（机器相关）2019/12/2309.4目标代码生成输入：中间代码序列三地址代码、语法结构树、后缀式输出：目标代码绝对机器代码、可重定位机器指令代码、汇编指令代码目标机多通用寄存器、控制栈、堆2019/12/231性能问题质量要求目标代码效率高目标程序短实现方法充分利用寄存器参考目标机的结构与指令形式2019/12/232分配寄存器节省的执行代价对象：基本块N中的变量AUSE(N,A)：N中对A定值前，A的引用次数LIVE(N,A)：1表示A在N中被定值，且出口之后有引用；0表示其他情况。循环L中为变量A分配寄存器节省的执行代价LN)]A,N(LIVE*)A,N(USE[22019/12/233代码生成概要计算各循环中各变量的可节省执行代价，据此分配寄存器对于每条三地址码，参照目标机允许的指令形式，进行翻译例x:=yopzmovRi,yopRi,zmovx,Ri2019/12/234例9-3：代码生成一般寄存器R0R1专用寄存器R2分配给xR3分配给t1指令种类赋值MOV比较CMP条件转移JGE转移JMP累加ADD乘MUL2019/12/235生成目标代码(1)MOVR0,Z(2)MULR0,6(3)MOVR3,R0(4)MOVR2,-4(5)CMPR2,76(6)JGE(12)(7)ADDR2,4(8)MOVR0,R3(9)ADDR0,R2(10)MOVY,R0(11)JMP(5)三地址码(1)t1:=z*6R3(2)x:=-4R2(3)ifx≥76goto(7)(4)x:=x+4(5)y:=t1+x(6)goto(3)2019/12/236上次课主要内