编译原理 代码优化.ppt

代码优化,代码优化的目标,提高最终目标代码的运行效率（性能）时间：运行的更快 空间：降低内存需求保持源程序的语义,代码优化的种类,窥孔优化局部优化基本块内优化全局优化基本块间优化（过程内）过程间优化程序全局优化,代码优化的种类窥孔优化,“孔”未优化的目标代码片段（windows）窥孔优化种类：删除冗余的存、取操作e.g.mov r0,a/r0-amov a,r0/a-r0,可删除 删除不可达代码,代码优化的种类窥孔优化,e.g.goto L1goto L2/语句前无标号，死代码L1:L2:控制流优化,代码优化的种类窥孔优化,goto L1L1:goto L2,goto L2L1:goto L2,if ab goto L1L1:goto L2,if ab goto L2L1:goto L2,goto L1/唯一跳转L1/L1前是无条件跳转L1:if a b goto L2L3:,if a b goto L2goto L3L3:,代码优化的种类窥孔优化,强度消弱、删除无用指令e.g.MUL$8,R0-ShiftLeft$3,R0ADD$0,R1/删除，未改变R1MUL$1,R2/删除 利用目标机指令特点e.g.inc、enter(建立栈帧）leave（清除栈帧）CISC 系统的“复杂”寻址模式 其它优化措施，如常量合并、复写传播等,代码优化的种类局部优化,基本块和流图 基本块：能顺序执行的程序代码序列。其入口为：程序的第一代码 条件或无条件转移代码所转到的目标代码 跟在条件或无条件转移代码后的代码 基本块划分 相邻入口中间的代码序列（仅含前一入口）某入口到程序的停止语句代码之间的代码序列 流图：由基本块按控制流方向形成的有向图基本块内优化，主要有：常量传播、合并和公共子表达式删除 复写传播与死代码（无用代码）删除,代码优化的种类全局优化,基本块间优化基本块间控制流与数据流分析技术优化措施主要有：循环优化：80/20 规则 不变式外提、归纳变量删除、强度消弱等 公共子表达式删除 常量传播、合并常量、复写传播 死代码（无用赋值）删除,典型的优化编译器的组织,中间表示,中间表示,优化举例,快速排序程序片段如下，i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B1(1)i:=m 1(2)j:=n(3)t1:=4*n(4)v:=at1,优化举例,快速排序程序片段如下，i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B2(5)i:=i+1(6)t2:=4*i(7)t3:=at2(8)if t3 v goto（5）,优化举例,快速排序程序片段如下，i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B3(9)j:=j 1(10)t4:=4*j(11)t5:=at4(12)if t5 v goto(9),优化举例,快速排序程序片段如下，i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B4(13)if i=j goto(23),优化举例,快速排序程序片段如下，i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B5(14)t6:=4*i(15)x:=at6(16)t7:=4*i(17)t8:=4*j(18)t9:=at8(19)at7:=t9(20)t10:=4*j(21)at10:=x(22)goto(5),优化举例,快速排序程序片段如下，i=m 1;j=n;v=an;while(1)do i=i+1;while(aiv);if(i=j)break;x=ai;ai=aj;aj=x;x=ai;ai=an;an=x;,/B6(23)t11:=4*i(24)x:=at11(25)t12:=4*i(26)t13:=4*n(27)t14:=at13(28)at12:=t14(29)t15:=4*n(30)at15:=x,优化举例流图,优化举例,公共子表达式删除基本块内,t6:=4*ix:=at6t7:=4*i t8:=4*jt9:=at8at7:=t9t10:=4*jat10:=xgoto B2,B5,B6,t11:=4*ix:=at11t12:=4*i t13:=4*nt14:=at13at12:=t14t15:=4*n at15:=x,变换,优化举例,公共子表达式删除基本块内,t6:=4*ix:=at6t8:=4*jt9:=at8at6:=t9at8:=xgoto B2,B5,B6,t11:=4*ix:=at11t13:=4*nt14:=at13at11:=t14at13:=x,优化举例,公共子表达式删除基本块间 t2:=4*i:B2-B5 t2:=4*i:B2-B6 t4:=4*j:B3-B5 t1:=4*n:B1-B6,t6:=4*ix:=at6t8:=4*jt9:=at8at6:=t9at8:=xgoto B2,B5,B6,t11:=4*ix:=at11t13:=4*nt14:=at13at11:=t14at13:=x,变换,优化举例,公共子表达式删除基本块间 t3:=at2:B2-B5 t3:=at2:B2-B6 t5:=at4:B3-B5,x:=at2t9:=at4at2:=t9at4:=xgoto B2,B5,B6,x:=at2t14:=at1at2:=t14at1:=x,变换,优化举例,公共子表达式删除基本块间B1中 v:=at1 能否作为公共子表达式？,x:=t3at2:=t5at4:=xgoto B2,B5,B6,x:=t3t14:=at1at2:=t14at1:=x,优化举例,复写传播 形成为f:=g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换是在复写语句f:=g后，尽可能用g代表f（暗示有前提条件）复写传播变换带来 常量合并 死代码删除,x:=t3/可以考虑删除at2:=t5at4:=t3goto B2,x:=t3at2:=t5at4:=xgoto B2,优化举例,复写传播,B5,B5,x:=t3/可以考虑删除t14:=at1at2:=t14at1:=t3,优化举例,复写传播,B6,B6,x:=t3t14:=at1at2:=t14at1:=x,B6中，t14:=at1 可以复写传播吗？,优化举例,循环优化 代码外提 归纳变量删除 强度削弱例：while(i=limit 2)变换成t=limit 2;/为什么提出循环？while(i=t),优化举例,强度削弱和归纳变量删除j和t4的值步伐一致地变化这样的变量叫做归纳变量在循环中有多个归纳变量时，也许只需要留下一个这个操作由归纳变量删除 过程来完成,优化举例,j:=j 1t4:=4*jt5:=at4if t5 v goto B3,B3,除第一次外，t4=4*j在B3的入口一定保持在j:=j 1后，关系t4=4*j+4也保持,优化举例,2023/4/26,编译原理与技术之代码优化,30,代码优化（续）,循环优化简介,2023/4/26,编译原理与技术之代码优化,31,流图中的循环,循环定义 程序流图中有唯一入口的强连通子图必经结点（集合）d DOM n 表示结点d是结点n的必经结点，如果从流图的开始结点出发到达结点n的每条路径上必须经过结点d。回边 n-d,如果d DOM n。,2023/4/26,编译原理与技术之代码优化,32,流图中的循环,自然循环 由回边 n-d 确定的循环Loop(n-d)Loop(n-d)=d U 流图中所有不经过结点 d 而能达到结点 n 的其它结点可归约流图 去除流图中的回边后的子图是无环有向图 结构化程序流图是可归约的 存在不可归约流图,2023/4/26,编译原理与技术之代码优化,33,流图中的循环,1,2,3,4,5,6,7,8,9,10,e.g.右边流图的必经结点树,e.g.一个流图,2023/4/26,编译原理与技术之代码优化,34,流图中的循环,自然循环回边10 7 循环7,8,10回边7 4 循环4,5,6,7,8,10回边4 3和8 3 循环3,4,5,6,7,8,10回边9 11,2,3,4,5,6,7,8,9,10,e.g.一个流图,2023/4/26,编译原理与技术之代码优化,35,循环优化,代码外提 循环不变计算 前置结点,2023/4/26,编译原理与技术之代码优化,36,循环优化代码外提,寻找循环不变计算（1）标记循环各结点（基本块）中的语句x:=y+z为不变计算，如果y和z均为常量或定值点在循环外（ud链）；（2）检查其余语句，如 w:=x+u，如果x和u均为常量或定值点在循环外，或其唯一能达到的定值点已标记,如（1）中的x，则标记该语句；（3）重复（2）直至没有语句被标记为不变计算为止。,2023/4/26,编译原理与技术之代码优化,37,循环优化代码外提,如何实施代码外提？考察已标记的循环不变计算，P:x:=y+z，如果满足，（1）P点所在基本块是所有循环出口结点的必经结点；（2）x 在循环中没有其它定值点；（3）循环中对 x 的引用均来自 P 点的定值。问题：如果 P 点定值满足（2）和（3），而不满足（1），能否外提该代码？,2023/4/26,编译原理与技术之代码优化,38,循环优化代码外提,非法代码外提case 1,代码外提,i:=1,B1,if u v goto B3,B2,u:=u+1,B3,v:=v-1if v=20 goto B5,B4,j:=i,B5,i:=2,B6,j：我要1,2023/4/26,编译原理与技术之代码优化,39,循环优化代码外提,非法代码外提case 2,B2,代码外提,j：2呢？,我要外提？,2023/4/26,编译原理与技术之代码优化,40,循环优化代码外提,非法代码外提case 3,i:=1,B1,i:=3if u v goto B3,i:=2/外提u:=u+1,B3,k:=iv:=v-1if v=20 goto B5,B4,j:=i,B5,i,你从哪里来？,2023/4/26,编译原理与技术之代码优化,41,循环优化,归纳变量 基本归纳变量 i:（i，1，0），循环中有唯一定值，形如 i:=i+n，n 为常量。i 族归纳变量 j:（i，c，d），如果循环中变量 j 的唯一定值满足 j:=i*c d，c和d为循环不变量。更多的i 族归纳变量 k,k 的定值形式为：k:=j*b,k:=b*j,k:=j/b,k:=j+b,k:=b+j,b 为循环不变量，j 为 i 族归纳变量（i，c，d），则 k 亦为i 族归纳变量。,2023/4/26,编译原理与技术之代码优化,42,循环优化,强度消弱 i 族归纳变量 j:(i,c,d),j:=i*c+d;引入新变量 s，在循环前置块末尾添加如下语句：s:=c*i0/if c=1 then s:=i0 s:=s+d/if d=0 then no code 变量 j 的定值语句变为 j:=s;在基本归纳变量 i 定值语句，i:=i n 后添加语句s:=s+c*n;s 也是i 族归纳变量 s:(i,c,d),2023/4/26,编译原理与技术之代码优化,43,循环优化,删除归纳变量 如果基本归纳变量 i,循环出口后不活跃，在循环中除了递归赋值外，仅出现在若干条件测试语句中，如 if i op x goto L 等，则可以考虑删除此基本归纳变量。选择 i 族归纳变量 j:(i,c,d),用以下语句序列，s:=c*x;s:=s+d;if j op s goto L 替代 if i op x goto L 删除语句 i:=i+n,2023/4/26,编译原理与技术之代码优化,44,循环优化举例,e.g.对以下伪C程序片段进行有关循环优化int A100100100;for(i 0;i100;i+)for(j=0;j100;j+)for(k=0;k100;k+)A i j k i*j*k;,2023/4/26,编译原理与技术之代码优化,45,循环优化举例代码外提,for(i 0;i100;i+)for(j=0;j100;j+)for(k=0;k100;k+)A i j k i*j*k;,对于最内层循环k而言，为循环不变计算,2023/4/26,编译原理与技术之代码优化,46,循环优化举例代码外提,for(i 0;i100;i+)for(j=0;j100;j+)t1=addr(A i j);t2=i*j;for(k=0;k100;k+)t1 k t2*k;/Loop j,A i 在循环j中保持“不变”,2023/4/26,编译原理与技术之代码优化,47,循环优化举例代码外提,for(i 0;i100;i+)t3=addr(A i);for(j=0;j100;j+)t1=addr(t3 j);t2=i*j;for(k=0;k100;k+)t1 k t2*k;/Loop j/Loop i,归纳表达式（变量）,2023/4/26,编译原理与技术之代码优化,48,循环优化举例强度消弱,for(i 0;i100;i+)t3=addr(A i);t4=0;/i*j 的初值for(j=0;j100;j+)t1=addr(t3 j);t2=t4;t5=0;/t2*k 的初值for(k=0;k100;k+)t1 k t5;t5=t5+t2;/Loop kt4=t4+i;/Loop j/Loop i,利用复写传播，删除t2,2023/4/26,编译原理与技术之代码优化,49,循环优化举例强度消弱,上述程序中隐含的有价值的归纳表达式：addr(A i)可以表示为：A+i*40000,A 为数组开始地址addr(t3 j)可以表示为：t3+j*400t1 k 的地址表示为：t1+k*4,2023/4/26,编译原理与技术之代码优化,50,循环优化举例强度消弱,t6=A;/A+i*40000的初值for(i 0;i100;i+)t3=t6；t4=0;t7=t3;/t3+j*400 的初值for(j=0;j100;j+)t1=t7;t5=0;t8=t1;/t1+k*4 的初值;for(k=0;k100;k+)*t8=t5;t5=t5+t4;t8=t8+4;/Loop kt4=t4+i;t7=t7+400;/Loop jt6=t6+40000;/Loop i,应用复写传播，再次删除t3和 t1;,2023/4/26,编译原理与技术之代码优化,51,循环优化举例强度消弱,t6=A;/A+i*40000的初值for(i 0;i100;i+)t4=0;t7=t6;for(j=0;j100;j+)t5=0;t8=t7;for(k=0;k100;k+)*t8=t5;t5=t5+t4;t8=t8+4;/Loop kt4=t4+i;t7=t7+400;/Loop jt6=t6+40000;/Loop i,结果最优了？,