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

第9章代码优化与

目标代码生成（介绍）代码优化代码生成2023/2/51引例fori=1tonstepmdo

s[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=2tonstepmdo

s[i]:=s[i-1]+a;2023/2/52代码优化代码优化的任务通过等价的程序变换，获得执行速度快、占用空间少的程序2023/2/53代码优化fori=2to10000do{T=0; forj=2toi-1do ifi=i/j*jthen{T=1;break} ifT=0thenprint(i)}fori=2to10000do {T=0; forj=2toi/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算法有效的数据结构和算法领域相关2023/2/54《编译原理》

(PrinciplesofCompiling)主讲：蒋宗礼2023/2/55上次课主要内容

——符号表管理关键字表关键字名字关键字标识begin112end113while114名字信息1信息2……信息nsum1real所在层定义/引用……2023/2/56上次课主要内容

——符号表管理层次表所在层性质起点终点直接外层本层计数2023/2/57上次课主要内容

——符号表管理过程表变量表标号表名字种类类型地址参数个数层次……定义/引用名字种类类型长度地址……标志2023/2/58上次课主要内容代码优化通过等价变换，获得执行速度快、占用空间少的程序算法优化2023/2/59代码优化编译优化目标代码优化：机器相关特殊指令的利用特殊结构的高效利用：SIMD、MIDM、流水、向量机中间代码优化：机器无关如：常数计算、公共代码段的提取2023/2/510中间代码优化局部优化基本块内部（不包括各种转移控制）全局优化循环优化、控制流分析与化简、数据流分析2023/2/5119.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)ift3<vgoto

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

(9)转移语句的下一条语句转移语句的目标第一条语句2023/2/512基本块的划分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)ift3<vgoto

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

(9)2023/2/513程序流图的构造程序流图Ｇ＝｛Ｎ，Ｅ，n0

｝以基本块为结点，以控制流为有向边Ｎ：基本块集n0：含首语句的基本块Ｅ：有向边集合(A,B)A的出口是转移语句，转向

B的入口

A的出口不是转移语句，B紧跟

A之后2023/2/514例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;2023/2/515三地址码序列(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≥j

goto(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;2023/2/516程序流图B1(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)2023/2/5179.2局部优化(1)合并已知量常数表达式计算t3:=110*xt1:=5+6t2:=t1*10t3:=t2*x2023/2/518(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≥j

goto(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,t142023/2/519(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]:=x2023/2/520(4)删除死代码未出现在程序流图中的代码赋值但未引用的指令(5)交换语句次序减少临时变量t1:=a+xt2:=b*yt:=t1+zp:=t*xt1:=a+xt:=t1+zt1:=b*yp:=t*x2023/2/5219.3循环优化循环体是优化的重点反复执行循环的定义有唯一入口点的强连接子图强连接子图任意两结点间的通路上各结点属于子图2023/2/522方法1：代码外提将循环不变运算移到循环外例：程序优化i=0;while(i<20){x=4*i;i++;y=z*6+x}2023/2/523(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)2023/2/524方法2：强度削弱用较快的操作代替较慢的操作+替代*；*替代**循环归纳变量相关的强度削弱X:=K*i+Y 相关计算i:=i+C 归纳变量（K、C、Y为循环不变量）改为X:=X+KC

设X的初值=Y-KC，KC为K*C的结果2023/2/525(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)2023/2/526方法3:消除归纳变量利用归纳变量相关的计算代替归纳变量的计算条件表达式的修改无用语句的删除优化效果语句数、乘除法数、变址运算、一般运算2023/2/527(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)2023/2/5289.4目标代码生成代码生成的任务针对目标语言的特殊性，生成高性能的目标代码（机器相关）2023/2/5299.4目标代码生成输入：中间代码序列三地址代码、语法结构树、后缀式输出：目标代码绝对机器代码、可重定位机器指令代码、汇编指令代码目标机多通用寄存器、控制栈、堆2023/2/530性能问题质量要求目标代码效率高目标程序短实现方法充分利用寄存器参考目标机的结构与指令形式2023/2/531分配寄存器节省的执行代价对象：基本块N中的变量AUSE(N,A)：N中对A定值前，A的引用次数LIVE(N,A)：1表示A在N中被定值，且出口之后有引用；0表示其他情况。循环L中为变量A分配寄存器节省的执行代价2023/2/532代码生成