三下-编译原理

编译原理

(PrinciplesofCompiling)2023/1/41主讲：蒋宗礼办公室：二教205电话：67392690Email：栈式存储管理SPnSPn-1……SP1SP02023/1/42数组存储区本过程……所辖分第临时工作单元程一序层局部数组说明存分储程局部变量区序分程序TOP本过程Display形式单元（m+1个）连主调分程序TOP接全局Display地址数返回地址据主调过程SP本过程TOPSP堆管理上次课主要内容上次课主要内容参数传递传值调用引用调用复制恢复传名调用2023/1/43A实际参数A形参XA的值间址访AAA的地址AA的值A的地址将过程体嵌在调用处执行，参数需文字替换上次课主要内容Procedureid(X1,X2,…,Xn)X1.codeX2.code……Xn.code动态存储分配相关进入过程体2023/1/44id(E1,E2,…,En)

E1.codea1:=E1.place…En.codean:=En.place动态存储分配相关gotopc+n+1parama1……paramancallid.place，n过程调用语句属性文法2023/1/45{Elist.num:=Elist1.num+1;Elist.code:=Elist1.code||E.code||t:=newtemp;gen(t’:=’E.place);将t放入队列q}{Elist.num:=1;Elist.code:=E.code||t:=newtemp;gen(t’:=’E.place)；建立队列q，并将t放入q}{S.code:=Elist.code||gen(‘goto‘pc+Elist.num+1)||for队列q中的每一项

tdogen(’param’t)||gen(‘call’id.place’,’Elist.num)}Elist→E Elist→Elist1,ES→callid(Elist)Ei.codeai:=Ei.placegotopc+n+1parama1……paramancallid.place，n第9章代码优化与

目标代码生成(介绍)2023/1/46代码优化代码生成引例fori=1tonstepmdo

s[i]:=4*i+n*m每次增加4*m，且n*m重复计算：s[i]=s[i-1]+4*m2023/1/47a:=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;初值为4+n*m，每次增加4*m代码优化代码优化的任务通过等价的程序变换，获得执行速度快、占用空间少的程序2023/1/48代码优化fori=2to10000do{T=0; forj=2toi-1do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}fori=2to10000do {T=0;

forj=2to

i/2do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}fori=2to10000do {T=0; forj=2tosqrt(i)do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}算法优化例：顺序查找与hash算法有效的数据结构和算法领域相关代码优化编译优化目标代码优化：机器相关特殊指令的利用特殊结构的高效利用：SIMD、MIMD、流水、向量机中间代码优化：机器无关如：常数计算、公共代码段的提取2023/1/410中间代码优化局部优化基本块内部(除最后一个代码，不含转移控制)全局优化循环优化控制流分析数据流分析2023/1/4119.1基本块和流图基本块控制流从第一语句进入，从最后一条语句离开语句序列中间没有停止或分枝关键：确定每个基本块的入口2023/1/412(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)ift3<vgoto

(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5>vgoto

(9)转移语句的下一条语句转移语句的目标第一条语句基本块的划分1)定义入口语句代码序列的第一语句转移语句的目标语句转移语句的下一条语句2)定义基本块一入口语句到下一入口语句之前一入口语句到转移语句(最后一条语句)或停语句2023/1/413(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)ift3<vgoto

(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5>vgoto(9)程序流图的构造程序流图G={N,E,n0}以基本块为结点，以控制流为有向边N：基本块集n0：含首语句的基本块E：有向边集合(A,B)A的出口是转移语句，转向B的入口A的出口非转移语句，B紧跟A之后2023/1/414例9-1：基本块划分和流图i=m-1; j=n; v=a[n];while(1)do{ whiledo(a[++i]<v); whiledo(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;2023/1/415三地址码序列(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)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5>vgoto(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(1)do{while(a[++i]<v)do;while(a[--j]>v)do;if(i≥j)thenbreak;x=a[i];a[i]=a[j];a[j]=x;}x=a[i];a[i]=a[n];a[n]=x;B1B2B3B4B5B6程序流图2023/1/417B1(1-4)B2(5-8)B3(9-12)B4(13)B5(14-22)B6(23-30)(8)ift3<vgoto(5)(12)ift5>vgoto(9)(13)ifi≥jgoto(23)(22)goto(5)9.2局部优化(1)合并已知量常数表达式计算2023/1/418t3:=110*xt1:=5+6t2:=t1*10t3:=t2*x(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)ift3<vgoto(5)(9)j:=j-1(10)t4:=4*j;(11)t5:=a[t4];(12)ift5>vgoto(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,t15t3代替t5,t8,t13,t14t1t1t1t1t1t1t1t1t1t1t1t1t1t1t1t1t3t3t3t3t3t3t3t3(3)删除基本块内的公共子表达式(14)(16)、(17)(20)、(23)(25)、(26)(29)2023/1/420(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]:=x9.2局部优化(4)删除死代码未出现在程序流中的代码赋值但未引用的指令2023/1/421B1B2B3B4B6B5B8B7t1:=a+xt2:=b*yt:=t1+zp:=t*xPrintpstop9.2局部优化(5)交换语句次序减少临时变量2023/1/422t1:=a+xt2:=b*yt:=t1+zp:=t*xt1:=a+xt:=t1+zt1:=b*yp:=t*x9.3循环优化循环体是优化的重点反复执行循环的定义有唯一入口点的强连接子图强连接子图任意两结点间的通路上各结点属于子图2023/1/423方法1：代码外提将循环不变运算移到循环外例 i=0; while(i<20){ x=4*i; i++; y=z*6+x}(3)x:=4*i(4)i:=i+1(5)t1:=z*6(6)y:=t1+x(7)goto(2)(1)i:=0(2)ifi≥20goto(8)(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)方法2：强度削弱用较快的操作代替较慢的操作+替代*；*替代**循环归纳变量相关的强度削弱X:=K*i+Y 相关计算i:=i+C 归纳变量，步长为C(K、C、Y为循环不变量)改为X:=X+KC

设X的初值=Y-KC，KC为K*C的结果2023/1/426(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)方法3:消除归纳变量利用归纳变量相关的计算代替归纳变量的计算条件表达式的修改无用语句的删除优化效果语句数、乘除法数、变址运算、一般运算2023/1/428(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)if

i

≥20goto(9)(3)if

x≥76

goto(7)9.4目标代码生成代码生成的任务针对目标语言的特殊性，生成高性能的目标代码(机器相关)2023/1/4309.4目标代码生成输入：中间代码序列三地址代码、语法结构树、后缀式输出：目标代码绝对机器代码、可重定位机器指令代码、汇编指令代码目标机多通用寄存器、控制栈、堆2023/1/431性能问题质量要求目标代码效率高目标程序短实现方法充分利用寄存器参考目标机的结构与指令形式2023/1/432分配寄存器节省的执行代价对象：基本块N中的变量AUSE(N,A)：N中对A定值前，A的引用次数LIVE(N,A)：1表示A在N中被定值，且出口之后有引用；0表示其他情况。循环L中为变量A分配寄存器可节省执行代价∑N∈L[use(N,A)+2*LIVE(N,A)]2023/1/433代码生成概要计算各循环中各变量的可节省执行代价，据此分配寄存器对于每条三地址码，参照目标机允许的指令形式，进行翻译例2023/1/434x:=yopzmovRi,yopRi,zmovx,Ri例9-3代码生成一般寄存器R0、R1专用寄存器R2分配给xR3分配给t1指令种类赋值