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

1、2022-5-81第第9 9章章 代码优化与代码优化与目标代码生成（介绍）目标代码生成（介绍）n代码优化代码优化n代码生成代码生成2022-5-82引例引例for i=1 to n step m do si:=4*i+n*ma:=4*m; s1:=4+ n*m;for i=1 to n step m do si:=s1; s1:=s1+aa:=4*m;s1=4+n*m;for i=2 to n step m do si:=si-1+a;2022-5-83代码优化代码优化v代码优化的任务代码优化的任务通过等价的程序变换，获得通过等价的程序变换，获得执行速度快、占执行速度快、占用空间少用空间少的程

2、序的程序2022-5-84for i=2 to 10000 dofor i=2 to 10000 do T=0; T=0; for j=2 to i-1 do for j=2 to i-1 doif i=i/jif i=i/j* *j then T=1;breakj then T=1;break if T=0 then print (i) if T=0 then print (i)for i=2 to 10000 dofor i=2 to 10000 do T=0;T=0; for j=2 to i/2 do for j=2 to i/2 doif i=i/jif i=i/j* *j then

3、 T=1;breakj then T=1;break if T=0 then print (i) if T=0 then print (i)for i=2 to 10000 dofor i=2 to 10000 do T=0; T=0; for j=2 to sqrt(i) do for j=2 to sqrt(i) doif i=i/jif i=i/j* *j then T=1;breakj then T=1;break if T=0 then print (i) if T=0 then print (i)v算法优化算法优化例：顺序查找例：顺序查找与与hashhash算法算法有效的数据结有效

4、的数据结构和算法构和算法领域相关领域相关2022-5-85编译原理编译原理(Principles of Compiling)n主主 讲：蒋宗礼讲：蒋宗礼2022-5-86上次课主要内容上次课主要内容v关键字表关键字表关键字名字关键字名字关键字标识关键字标识beginbegin112112endend113113whilewhile114114名字名字信息信息1 1信息信息2 2信息信息n nsum1sum1real real 所在层所在层定义定义/ /引用引用2022-5-87上次课主要内容上次课主要内容v层次表层次表所在层所在层性质性质起点起点终点终点直接外层直接外层本层计数本层计数2022

5、-5-88上次课主要内容上次课主要内容v过程表过程表v变量表变量表v标号表标号表名字名字 种类种类类型类型 地址地址参数个数参数个数层次层次定义定义/引用引用名字名字种类种类类型类型长度长度地址地址标志标志2022-5-89上次课主要内容上次课主要内容通过等价变换，获得执行速度快、占用空间通过等价变换，获得执行速度快、占用空间少的程序少的程序2022-5-810v编译优化编译优化目标代码优化：机器相关目标代码优化：机器相关v特殊指令的利用特殊指令的利用v特殊结构的高效利用：特殊结构的高效利用：SIMDSIMD、MIDMMIDM、流水、向、流水、向量机量机中间代码优化：机器无关中间代码优化：机器

6、无关v如：常数计算、公共代码段的提取如：常数计算、公共代码段的提取2022-5-811v局部优化局部优化基本块内部（不包括各种转移控制）基本块内部（不包括各种转移控制）v全局优化全局优化循环优化、控制流分析与化简、数据流分循环优化、控制流分析与化简、数据流分析析2022-5-812v基本块基本块控制流从第一语控制流从第一语句进入，从最后句进入，从最后一条语句离开一条语句离开语句序列中间没语句序列中间没有停止或分枝有停止或分枝关键：确定每个关键：确定每个基本块的入口基本块的入口(1) (1) i := m - 1i := m - 1(2) j := n(2) j := n(3) t1 := 4

7、(3) t1 := 4 * * n; n;(4) v := a t1 (4) v := a t1 (5) i := i + 1(5) i := i + 1(6) t2 := 4 (6) t2 := 4 * * i; i;(7) t3 := a t2 ;(7) t3 := a t2 ;(8) if t3 v goto(8) if t3 v goto(12) if t5 v goto (9)(9)转移语句的转移语句的下一条语句下一条语句转移语句转移语句的目标的目标第一条语句第一条语句2022-5-813v1) 1) 定义入口语句定义入口语句代码序列的第一语句代码序列的第一语句转移语句的目标语句转移

8、语句的目标语句转移语句的下一条语句转移语句的下一条语句v2) 2) 定义基本块定义基本块一入口语句到下一入口一入口语句到下一入口语句之前语句之前一入口语句到一入口语句到转移语句转移语句或或停语句停语句(1) (1) i := m - 1i := m - 1(2) j := n(2) j := n(3) t1 := 4 (3) t1 := 4 * * n; n;(4) v := a t1 (4) v := a t1 (5) i := i + 1(5) i := i + 1(6) t2 := 4 (6) t2 := 4 * * i; i;(7) t3 := a t2 ;(7) t3 := a t2

9、 ;(8) if t3 v goto(8) if t3 v goto(12) if t5 v goto (9)(9)2022-5-814v程序流图程序流图，n n0 0 以基本块为结点，以控制流为有向边以基本块为结点，以控制流为有向边：基本块集：基本块集n n0 0 ：含首语句的基本块含首语句的基本块：有向边集合：有向边集合 ( (A, A, B)B)vA A 的出口是转移语句，转向的出口是转移语句，转向 B B 的入口的入口v A A 的出口不是的出口不是 转移语句，转移语句， B B 紧跟紧跟 A A 之后之后2022-5-815i = m - 1;i = m - 1;j = n;j =

10、n;v = a n ;v = a n ;while( 1 ) while( 1 ) while( a+i v );while( a+i v );while( a-j v );if( i j ) then break;if( i j ) then break;x = a i ;x = a i ; a i = a j ; a j = x; a i = a j ; a j = x; x = a i ; a i = a n ; a n = x;x = a i ; a i = a n ; a n = x;2022-5-816(1) (1) i := m - 1i := m - 1(2) j := n(2

11、) j := n(3) t1 := 4 (3) t1 := 4 * * n; n;(4) v := a t1 (4) v := a t1 (5) i := i + 1(5) i := i + 1(6) t2 := 4 (6) t2 := 4 * * i; i;(7) t3 := a t2 ;(7) t3 := a t2 ;(8) if t3 v (8) if t3 v (12) if t5 v goto (9)goto (9)(13)(13) if ij if ij goto (23)goto (23)(14)(14) t6 := 4 t6 := 4 * * i i(15) x := at6(

12、15) x := at6(16) t7 := 4 (16) t7 := 4 * * i i(17) t8 := 4 (17) t8 := 4 * * j j(18) t9 := a t8 (18) t9 := a t8 (19) a t7 := t9(19) a t7 := t9(20) t10 := 4 (20) t10 := 4 * * j j(21) a t10 := x(21) a t10 := x(22) (22) goto (5)goto (5)(23) t11 := 4 * i(24) x := at11(25) t12 := 4 * i(26) t13 := 4 * n(27)

13、 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 );if( i j ) then break;x = a i ;a i = a j ;a j = x;x = a i ;a i = a n ;a n = x;2022-5-8172022-5-818v(1) (1) 合并已知量合并已知量常数表达式计算常数表达式计算t3:=1

14、10t3:=110* *x xt1:=5+6t1:=5+6t2:=t1t2:=t1* *1010t3:=t2t3:=t2* *x x2022-5-819(1) (1) i := m - 1i := m - 1(2) j := n(2) j := n(3) (3) t1 t1 := 4 := 4 * * n; n;(4) v := a (4) v := a t1 t1 (5) i := i + 1(5) i := i + 1(6) (6) t2 t2 := 4 := 4 * * i; i;(7) (7) t3 t3 := a := a t2t2 ; ;(8) if (8) if t3t3 v v

15、 v goto (9)goto (9)(13)(13) if ij goto (23)if ij goto (23)(14)(14) t6t6 := 4 := 4 * * i i(15) x := a(15) x := at6t6 (16) (16) t7 t7 := 4 := 4 * * i i(17) (17) t8t8 := 4 := 4 * * j j(18) t9 := a (18) t9 := a t8t8 (19) a (19) a t7t7 := t9 := t9(20) t(20) t10 10 := 4 := 4 * * j j(21) a (21) a t10t10 :=

16、 x := x(22) (22) goto (5)goto (5)(23) t11 := 4 * i(24) x := at11(25) t12 := 4 * i(26) t13 := 4 * n(27) t14 := a t13 (28) a t12 := t14(29) t15 := 4 * n(30) a t15 := xv(2) (2) 重新命名临时变量重新命名临时变量t1 t1 代替代替 t2,t4,t6,t7,t10,t11,t12,t15t2,t4,t6,t7,t10,t11,t12,t15t3 t3 代代替替 t5,t8,t13,t14t5,t8,t13,t142022-5-8

17、20v(3) (3) 删除基本块内的公共子表达式删除基本块内的公共子表达式(14)(16)(14)(16)、(17)(20)(17)(20)、(23)(25)(23)(25)、(26)(29)(26)(29)(23) t1 := 4 * i(24) x := at1(25) t1 := 4 * i(26) t3 := 4 * n(27) t3 := a t3 (28) a t1 := t3(29) t1 := 4 * n(30) a t1 := x(23) t1 := 4 * i(24) x := at1(26) t3 := 4 * n(27) t3 := a t3 (28) a t1 :=

18、t3(30) a t3 := x2022-5-821v(4) (4) 删除死代码删除死代码未出现在程序流图中的代码未出现在程序流图中的代码赋值但未引用的指令赋值但未引用的指令v(5) (5) 交换语句次序交换语句次序减少临时变量减少临时变量t1:=a+xt1:=a+xt2:=bt2:=b* *y yt:=t1+zt:=t1+zp:=tp:=t* *x xt1:=a+xt1:=a+xt:=t1+zt:=t1+zt1:=bt1:=b* *y yp:=tp:=t* *x x2022-5-822v循环体是优化的重点循环体是优化的重点反复执行反复执行v循环的定义循环的定义有唯一入口点的强连接子图有唯一入

19、口点的强连接子图强连接子图强连接子图v任意两结点间的通路上各结点属于子图任意两结点间的通路上各结点属于子图2022-5-823v将循环不变运算移到循环外将循环不变运算移到循环外v例例 ：程序优化：程序优化i = 0;i = 0;while( i 20 ) while( i = 20 goto (8)(4) if i = 20 goto (9)2022-5-827v利用归纳变量相关的计算代替归纳变量的利用归纳变量相关的计算代替归纳变量的计算计算条件表达式的修改条件表达式的修改无用语句的删除无用语句的删除v优化效果优化效果语句数、乘除法数、变址运算、一般运算语句数、乘除法数、变址运算、一般运算20

20、22-5-828(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 20 goto (9)(3) if x 76 goto (7)2022-5-829生成生成v代码生成的任务代码生成的任务针对目标语言的特殊性，生成高性能的目标代针对目标语言的特殊性，生成高性能的目标代码（机器相关）码（机器相关）2022-5-830

21、v输入：中间代码序列输入：中间代码序列三地址代码、语法结构树、后缀式三地址代码、语法结构树、后缀式v输出：目标代码输出：目标代码绝对机器代码、可重定位机器指令代码、绝对机器代码、可重定位机器指令代码、汇编指令代码汇编指令代码v目标机目标机多通用寄存器、控制栈、堆多通用寄存器、控制栈、堆2022-5-831v质量要求质量要求目标代码效率高目标代码效率高目标程序短目标程序短v实现方法实现方法充分利用寄存器充分利用寄存器参考目标机的结构与指令形式参考目标机的结构与指令形式2022-5-832v对象：基本块对象：基本块 NN中的变量中的变量A AUSE(N, A)USE(N, A)：NN中对中对 A A定值前，定值前，A A的引用次数的引用次数LIVE(N, A)LIVE(N, A)：1 1 表示表示 A A在在 NN中被定值，且中被定值，且出口出口之后之后有引用；有引用；0 0 表示其他情况。表示其他情况。v循环循环 L L 中为变量中为变量 A A 分配寄存器节省的执行代价分配寄存器节省的执行代价LN)A,N(LIVE*)A,N(USE22022-5-833v计算各循环中各变量的可节省执行代价，据计算各循环中各变量的可节省执行代价，据此分配寄