《编译原理 代码优化.ppt》由会员分享，可在线阅读，更多相关《编译原理 代码优化.ppt（51页珍藏版）》请在三一文库上搜索。
1、代码优化,代码优化的目标,提高最终目标代码的运行效率（性能） 时间：运行的更快 空间：降低内存需求 保持源程序的语义,代码优化的种类,窥孔优化 局部优化基本块内优化 全局优化基本块间优化（过程内） 过程间优化程序全局优化,代码优化的种类窥孔优化,“孔”未优化的目标代码片段（windows） 窥孔优化种类： 删除冗余的存、取操作 e.g. mov r0, a / r0 - a mov a, r0 / a - r0, 可删除 删除不可达代码,代码优化的种类窥孔优化,e.g. goto L1 goto L2 / 语句前无标号，死代码 L1: L2: 控制流优化,代码优化的种类窥孔优化,goto L1
2、 L1: goto L2,goto L2 L1: goto L2,if ab goto L1 L1: goto L2,if ab goto L2 L1: goto L2,goto L1 /唯一跳转L1 /L1前是无条件跳转 L1: if a b goto L2 L3:,if a b goto L2 goto L3 L3:,代码优化的种类窥孔优化, 强度消弱、删除无用指令 e.g. MUL $8, R0 - ShiftLeft $3, R0 ADD $0, R1 / 删除，未改变R1 MUL $1, R2 / 删除 利用目标机指令特点 e.g. inc、enter(建立栈帧）leave（清除栈帧
3、） CISC 系统的“复杂”寻址模式 其它优化措施，如常量合并、复写传播等,代码优化的种类局部优化,基本块和流图 基本块：能顺序执行的程序代码序列。其入口为： 程序的第一代码 条件或无条件转移代码所转到的目标代码 跟在条件或无条件转移代码后的代码 基本块划分 相邻入口中间的代码序列（仅含前一入口） 某入口到程序的停止语句代码之间的代码序列 流图：由基本块按控制流方向形成的有向图 基本块内优化，主要有： 常量传播、合并和公共子表达式删除 复写传播与死代码（无用代码）删除,代码优化的种类全局优化,基本块间优化基本块间控制流与数据流分析技术 优化措施主要有： 循环优化 ：80/20 规则 不变式外提
4、、归纳变量删除、强度消弱等 公共子表达式删除 常量传播、合并常量、复写传播 死代码（无用赋值）删除,典型的优化编译器的组织,中间表示,中间表示,优化举例,快速排序程序片段如下， 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
5、; 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 (
6、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)
7、; 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=
8、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 * i x := at6 t7 := 4 * i t8 := 4 * j t9 := at8 at7 := t9 t10 := 4 * j at10 := x goto B2,B5
9、,B6,t11 := 4 * i x := at11 t12 := 4 * i t13 := 4 * n t14 := at13 at12 := t14 t15 := 4 * n at15 := x,变 换,优化举例,公共子表达式删除 基本块内,t6 := 4 * i x := at6 t8 := 4 * j t9 := at8 at6 := t9 at8 := x goto B2,B5,B6,t11 := 4 * i x := at11 t13 := 4 * n t14 := at13 at11 := t14 at13 := x,优化举例,公共子表达式删除基本块间 t2:=4 * i : B
10、2 - B5 t2:=4 * i : B2 - B6 t4:= 4 * j : B3 - B5 t1:= 4 * n : B1 - B6,t6 := 4 * i x := at6 t8 := 4 * j t9 := at8 at6 := t9 at8 := x goto B2,B5,B6,t11 := 4 * i x := at11 t13 := 4 * n t14 := at13 at11 := t14 at13 := x,变 换,优化举例,公共子表达式删除基本块间 t3:=at2 : B2 - B5 t3:=at2 : B2 - B6 t5:= at4 : B3 - B5,x := at2
11、 t9 := at4 at2 := t9 at4 := x goto B2,B5,B6,x := at2 t14 := at1 at2 := t14 at1 := x,变 换,优化举例,公共子表达式删除基本块间 B1中 v := at1 能否作为公共子表达式？,x := t3 at2 := t5 at4 := x goto B2,B5,B6,x := t3 t14 := at1 at2 := t14 at1 := x,优化举例,复写传播 形成为f := g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换是在复写语句f := g后，尽可能用g代表f（暗示有前提条件） 复写传播变换带来
12、常量合并 死代码删除,x := t3 /可以考虑删除 at2 := t5 at4 := t3 goto B2,x := t3 at2 := t5 at4 := x goto B2,优化举例,复写传播,B5,B5,x := t3 /可以考虑删除 t14 := at1 at2 := t14 at1 := t3,优化举例,复写传播,B6,B6,x := t3 t14 := at1 at2 := t14 at1 := x,B6中，t14 := at1 可以复写传播吗？,优化举例,循环优化 代码外提 归纳变量删除 强度削弱 例：while (i = limit 2 ) 变换成 t = limit 2;
13、/为什么提出循环？ while (i = t ) ,优化举例,强度削弱和归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 在循环中有多个归纳变量时， 也许只需要留下一个 这个操作由归纳变量删除 过程来完成,优化举例,j := j 1 t4 := 4 * j t5 := at4 if t5 v goto B3,B3,除第一次外， t4 = 4 * j在B3的入口 一定保持 在j := j 1后， 关系t4 = 4 * j + 4也 保持,优化举例,2019/9/22,编译原理与技术之代码优化,30,代码优化（续）, 循环优化简介,2019/9/22,编译原理与技术之代码优化,31
14、,流图中的循环,循环定义 程序流图中有唯一入口的强连通子图 必经结点（集合） d DOM n 表示结点d是结点n的必经结点， 如果从流图的开始结点出发到达结点n的每条路径上必须经过结点d。 回边 n-d, 如果d DOM n。,2019/9/22,编译原理与技术之代码优化,32,流图中的循环,自然循环 由回边 n-d 确定的循环Loop(n-d) Loop(n-d) = d U 流图中所有不经过结点 d 而能达到结点 n 的其它结点 可归约流图 去除流图中的回边后的子图是无环有向图 结构化程序流图是可归约的 存在不可归约流图,2019/9/22,编译原理与技术之代码优化,33,流图中的循环,1
15、,2,3,4,5,6,7,8,9,10,e.g. 右边流图的必经结点树,e.g. 一个流图,2019/9/22,编译原理与技术之代码优化,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 1 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,e.g. 一个流图,2019/9/22,编译原理与技术之代码优化,35,循环优化,代码外提 循环不变计算 前置结点,2019/9/22,编译原理与技术之代码优化,36,循环优化代码外提,寻找循环不变计算 （
16、1）标记循环各结点（基本块）中的语句x := y + z为不变计算，如果y和z均为常量或定值点在循环外（ud链）； （2）检查其余语句，如 w := x + u，如果x和u均为常量或定值点在循环外，或其唯一能达到的定值点已标记, 如 （1）中的x，则标记该语句； （3）重复（2）直至没有语句被标记为不变计算为止。,2019/9/22,编译原理与技术之代码优化,37,循环优化代码外提,如何实施代码外提？ 考察已标记的循环不变计算，P: x := y + z ， 如果满足， （1）P点所在基本块是所有循环出口结点的必经结点； （2）x 在循环中没有其它定值点； （3）循环中对 x 的引用均来自 P
17、 点的定值。 问题：如果 P 点定值满足（2）和（3），而不满足（1），能否外提该代码？,2019/9/22,编译原理与技术之代码优化,38,循环优化代码外提,非法代码外提case 1,代码外提,i := 1,B1,if u v goto B3,B2,u := u + 1,B3,v := v -1 if v = 20 goto B5,B4,j := i,B5,i := 2,B6,j：我要1,2019/9/22,编译原理与技术之代码优化,39,循环优化代码外提,非法代码外提case 2,B2,代码外提,j：2呢？,我要外提？,2019/9/22,编译原理与技术之代码优化,40,循环优化代码外提,
18、非法代码外提case 3,i := 1,B1,i := 3 if u v goto B3,i := 2/外提 u := u + 1,B3,k := i v := v -1 if v = 20 goto B5,B4,j := i,B5,i , 你从哪里来？,2019/9/22,编译原理与技术之代码优化,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
19、:= j * b, k := b * j, k := j / b, k := j + b , k := b + j, b 为循环不变量，j 为 i 族归纳变量（i，c，d） ，则 k 亦为i 族归纳变量。,2019/9/22,编译原理与技术之代码优化,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; 在基本
20、归纳变量 i 定值语句，i := i n 后添加语句 s := s + c * n; s 也是i 族归纳变量 s : ( i, c, d ),2019/9/22,编译原理与技术之代码优化,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
21、 + n,2019/9/22,编译原理与技术之代码优化,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;,2019/9/22,编译原理与技术之代码优化,45,循环优化举例代码外提,for ( i 0 ; i100; i+) for ( j = 0; j100; j+) for ( k = 0; k100; k+) A i j k i * j * k;,对于最内层循环k而言，为
22、循环不变计算,2019/9/22,编译原理与技术之代码优化,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中保持“不变”,2019/9/22,编译原理与技术之代码优化,47,循环优化举例代码外提,for ( i 0 ; i100; i+) t3 = addr( A i ); for ( j = 0; j100; j+) t1 = addr( t3 j );
23、 t2 = i * j; for ( k = 0; k100; k+) t1 k t2 * k; / Loop j / Loop i,归纳表达式（变量）,2019/9/22,编译原理与技术之代码优化,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 k
24、 t4 = t4 + i; / Loop j / Loop i,利用复写传播， 删除t2,2019/9/22,编译原理与技术之代码优化,49,循环优化举例强度消弱,上述程序中隐含的有价值的归纳表达式： addr(A i ) 可以表示为： A + i * 40000 , A 为数组开始地址 addr( t3 j ) 可以表示为： t3 + j * 400 t1 k 的地址表示为： t1 + k * 4,2019/9/22,编译原理与技术之代码优化,50,循环优化举例强度消弱,t6 = A; / A + i * 40000的初值 for ( i 0 ; i100; i+) t3 = t6； t4
25、= 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 k t4 = t4 + i; t7 = t7 + 400; / Loop j t6 = t6 + 40000; / Loop i,应用复写传播，再次删除t3和 t1;,2019/9/22,编译原理与技术之代码优化,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 k t4 = t4 + i; t7 = t7 + 400; / Loop j t6 = t6 + 40000; / Loop i,结果最优了？,