中科大2021－2022学年秋季第一学期《编译原理与技术》第十一讲 代码优化（1）

1、代码优化7/25/20221编译原理与技术之代码优化代码优化的目标提高最终目标代码的运行效率（性能） 时间：运行的更快 空间：降低内存需求保持源程序的语义7/25/20222编译原理与技术之代码优化代码优化的种类窥孔优化局部优化基本块内优化全局优化基本块间优化（过程内）过程间优化程序全局优化7/25/20223编译原理与技术之代码优化代码优化的种类窥孔优化“孔”未优化的目标代码片段（windows）窥孔优化种类： 删除冗余的存、取操作e.g.mov r0, a / r0 - amov a, r0 / a - r0, 可删除 删除不可达代码7/25/20224编译原理与技术之代码优化代码优化的种

2、类窥孔优化 e.g. goto L1goto L2 / 语句前无标号，死代码L1: L2: 控制流优化7/25/20225编译原理与技术之代码优化代码优化的种类窥孔优化goto L1L1: goto L2goto L2L1: goto L2if ab goto L1L1: goto L2if ab goto L2L1: goto L2goto L1 /唯一跳转L1 /L1前是无条件跳转L1: if a b goto L2L3:if a ShiftLeft $3, R0ADD $0, R1 / 删除，未改变R1MUL $1, R2 / 删除 利用目标机指令特点e.g. inc、enter(建立栈

3、帧）leave（清除栈帧） CISC 系统的“复杂”寻址模式 其它优化措施，如常量合并、复写传播等7/25/20227编译原理与技术之代码优化代码优化的种类局部优化基本块和流图 基本块：能顺序执行的程序代码序列。其入口为： 程序的第一代码 条件或无条件转移代码所转到的目标代码 跟在条件或无条件转移代码后的代码 基本块划分 相邻入口中间的代码序列（仅含前一入口） 某入口到程序的停止语句代码之间的代码序列 流图：由基本块按控制流方向形成的有向图基本块内优化，主要有： 常量传播、合并和公共子表达式删除 复写传播与死代码（无用代码）删除7/25/20228编译原理与技术之代码优化代码优化的种类全局优化

4、基本块间优化基本块间控制流与数据流分析技术优化措施主要有： 循环优化 ：80/20 规则 不变式外提、归纳变量删除、强度消弱等 公共子表达式删除 常量传播、合并常量、复写传播 死代码（无用赋值）删除7/25/20229编译原理与技术之代码优化典型的优化编译器的组织前 端代 码生成器代 码优化器变 换数据流分 析控制流分 析中间表示中间表示7/25/202210编译原理与技术之代码优化优化举例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(aiv); if (i = j) break; x=ai; ai=aj; aj

5、=x; x=ai; ai=an; an=x;/B1(1) i := m 1(2) j := n(3) t1 := 4 * n(4) v := at17/25/202211编译原理与技术之代码优化优化举例快速排序程序片段如下，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）7/25/2022

6、12编译原理与技术之代码优化优化举例快速排序程序片段如下，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)7/25/202213编译原理与技术之代码优化优化举例快速排序程序片段如下，i = m 1; j = n; v = an; while (1) do i = i +1; while(

7、aiv); if (i = j) break; x=ai; ai=aj; aj=x; x=ai; ai=an; an=x;/B4(13) if i = j goto (23)7/25/202214编译原理与技术之代码优化优化举例快速排序程序片段如下，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

8、 * j(18) t9 := at8(19) at7 := t9(20) t10 := 4 * j(21) at10 := x(22) goto (5)7/25/202215编译原理与技术之代码优化优化举例快速排序程序片段如下，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

9、) t14 := at13(28) at12 := t14(29) t15 := 4 * n(30) at15 := x7/25/202216编译原理与技术之代码优化优化举例流图i := m 1j := nt1 := 4 * nv := at1i := i + 1t2 := 4 * it3 := at2if t3 v goto B2B1B2j := j 1t4 := 4 * jt5 := at4if t5 v goto B3if i = j goto B6B4B3B5B67/25/202217编译原理与技术之代码优化优化举例公共子表达式删除基本块内t6 := 4 * ix := at6t7 :

10、= 4 * i t8 := 4 * jt9 := at8at7 := t9t10 := 4 * jat10 := xgoto B2B5B6t11 := 4 * ix := at11t12 := 4 * i t13 := 4 * nt14 := at13at12 := t14t15 := 4 * n at15 := x 变换7/25/202218编译原理与技术之代码优化优化举例公共子表达式删除基本块内t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2B5B6t11 := 4 * ix := at11t13 := 4 *

11、nt14 := at13at11 := t14at13 := x 7/25/202219编译原理与技术之代码优化优化举例公共子表达式删除基本块间 t2:=4 * i : B2 - B5 t2:=4 * i : B2 - B6 t4:= 4 * j : B3 - B5 t1:= 4 * n : B1 - B6t6 := 4 * ix := at6t8 := 4 * jt9 := at8at6 := t9at8 := xgoto B2B5B6t11 := 4 * ix := at11t13 := 4 * nt14 := at13at11 := t14at13 := x 变换7/25/202220编

12、译原理与技术之代码优化优化举例公共子表达式删除基本块间 t3:=at2 : B2 - B5 t3:=at2 : B2 - B6 t5:= at4 : B3 - B5x := at2t9 := at4at2 := t9at4 := xgoto B2B5B6x := at2t14 := at1at2 := t14at1 := x 变换7/25/202221编译原理与技术之代码优化优化举例公共子表达式删除基本块间B1中 v := at1 能否作为公共子表达式？x := t3at2 := t5at4 := xgoto B2B5B6x := t3t14 := at1at2 := t14at1 := x

13、7/25/202222编译原理与技术之代码优化优化举例复写传播 形成为f := g的赋值叫做复写语句 优化过程中会大量引入复写 复写传播变换是在复写语句f := g后，尽可能用g代表f（暗示有前提条件）复写传播变换带来 常量合并 死代码删除7/25/202223编译原理与技术之代码优化x := t3 /可以考虑删除at2 := t5at4 := t3goto B2x := t3at2 := t5at4 := xgoto B2优化举例复写传播B5B57/25/202224编译原理与技术之代码优化x := t3 /可以考虑删除t14 := at1at2 := t14at1 := t3 优化举例复写

14、传播B6B6x := t3t14 := at1at2 := t14at1 := x B6中，t14 := at1 可以复写传播吗？7/25/202225编译原理与技术之代码优化优化举例循环优化 代码外提 归纳变量删除 强度削弱例：while (i = limit 2 ) 变换成t = limit 2; /为什么提出循环？while (i v goto B3B37/25/202227编译原理与技术之代码优化优化举例i := m 1j := nt1 := 4 * nv := at1B1B2j := j 1t4 := t4 4t5 := at4if t5 v goto B3B4B3B5B6t4 :=

15、 4 * jif i = j goto B6j := j 1t4 := 4 * jt5 := at4if t5 v goto B3B3除第一次外，t4 = 4 * j在B3的入口一定保持在j := j 1后，关系t4 = 4 * j + 4也保持7/25/202228编译原理与技术之代码优化i := m 1j := nt1 := 4 * nv := at1t2 := 4 * it4 := 4 * jt2 := t2 + 4t3 := at2if t3 v goto B2B1B2t4 := t4 4t5 := at4if t5 v goto B3if t2 = t4 goto B6at2 :=

16、t5at4 := t3goto B2B4B3B5t14 := at1at2 := t14at1 := t3B6优化举例7/25/202229编译原理与技术之代码优化代码优化（续） 循环优化简介7/25/202230编译原理与技术之代码优化流图中的循环循环定义 程序流图中有唯一入口的强连通子图必经结点（集合） d DOM n 表示结点d是结点n的必经结点，如果从流图的开始结点出发到达结点n的每条路径上必须经过结点d。回边 n-d, 如果d DOM n。7/25/202231编译原理与技术之代码优化流图中的循环自然循环 由回边 n-d 确定的循环Loop(n-d) Loop(n-d) = d U

17、流图中所有不经过结点 d 而能达到结点 n 的其它结点可归约流图 去除流图中的回边后的子图是无环有向图 结构化程序流图是可归约的 存在不可归约流图7/25/202232编译原理与技术之代码优化流图中的循环1234567891012345678910e.g. 右边流图的必经结点树e.g. 一个流图7/25/202233编译原理与技术之代码优化流图中的循环自然循环回边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, 1012345678910

18、e.g. 一个流图7/25/202234编译原理与技术之代码优化循环优化代码外提 循环不变计算 前置结点B0B0循环L(b) 外提代码放在前置结点B0B0循环L(a) 代码外提前，B0是首结点7/25/202235编译原理与技术之代码优化循环优化代码外提寻找循环不变计算（1）标记循环各结点（基本块）中的语句x := y + z为不变计算，如果y和z均为常量或定值点在循环外（ud链）；（2）检查其余语句，如 w := x + u，如果x和u均为常量或定值点在循环外，或其唯一能达到的定值点已标记, 如（1）中的x，则标记该语句；（3）重复（2）直至没有语句被标记为不变计算为止。 7/25/2022

19、36编译原理与技术之代码优化循环优化代码外提如何实施代码外提？考察已标记的循环不变计算，P: x := y + z ， 如果满足，（1）P点所在基本块是所有循环出口结点的必经结点；（2）x 在循环中没有其它定值点；（3）循环中对 x 的引用均来自 P 点的定值。问题：如果 P 点定值满足（2）和（3），而不满足（1），能否外提该代码？7/25/202237编译原理与技术之代码优化循环优化代码外提非法代码外提case 1i := 1B1if u v goto B3B2i := 2u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5代码外提i := 1B

20、1if u v goto B3B2u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5i := 2B6j：我要17/25/202238编译原理与技术之代码优化循环优化代码外提非法代码外提case 2B2代码外提i := 1B1i := 3if u v goto B3i := 2u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5i := 1B1i := 3if u v goto B3u := u + 1B3v := v -1if v = 20 goto B5B4j := iB5i := 2B6j：2呢？我要

21、外提？7/25/202239编译原理与技术之代码优化循环优化代码外提非法代码外提case 3i := 1B1i := 3if u v goto B3i := 2/外提u := u + 1B3k := iv := v -1if v = 20 goto B5B4j := iB5i , 你从哪里来？7/25/202240编译原理与技术之代码优化循环优化归纳变量 基本归纳变量 i :（i，1，0），循环中有唯一定值，形如 i := i + n，n 为常量。 i 族归纳变量 j :（i，c，d），如果循环中变量 j 的唯一定值满足 j := i * c d，c和d为循环不变量。 更多的i 族归纳变量 k

22、 , k 的定值形式为：k := j * b, k := b * j, k := j / b, k := j + b , k := b + j,b 为循环不变量，j 为 i 族归纳变量（i，c，d） ，则 k 亦为i 族归纳变量。7/25/202241编译原理与技术之代码优化循环优化强度消弱 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 :=

23、 s; 在基本归纳变量 i 定值语句，i := i n 后添加语句s := s + c * n; s 也是i 族归纳变量 s : ( i, c, d )7/25/202242编译原理与技术之代码优化循环优化删除归纳变量 如果基本归纳变量 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 +

24、 n 7/25/202243编译原理与技术之代码优化循环优化举例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;7/25/202244编译原理与技术之代码优化循环优化举例代码外提for ( i 0 ; i100; i+)for ( j = 0; j100; j+)for ( k = 0; k100; k+)A i j k i * j * k;对于最内层循环k而言，为循环不变计算7/25/202245编译原

25、理与技术之代码优化循环优化举例代码外提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 jA i 在循环j中保持“不变”7/25/202246编译原理与技术之代码优化循环优化举例代码外提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归纳表达式（变量）7/25/202247编译原理与技术之代码优化循环优化举例强度消弱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;