代码优化.

Presentation on theme: "代码优化."— Presentation transcript:

1 代码优化

2 代码优化的目标 提高最终目标代码的运行效率（性能） － 时间：运行的更快 － 空间：降低内存需求 保持源程序的语义

3 代码优化的种类 窥孔优化 局部优化－基本块内优化 全局优化－基本块间优化（过程内） 过程间优化－程序全局优化

4 代码优化的种类－窥孔优化 “孔”－未优化的目标代码片段（windows） 窥孔优化种类： － 删除冗余的存、取操作
e.g. mov r0, a // r0 -> a mov a, r0 // a -> r0, 可删除 － 删除不可达代码

5 代码优化的种类－窥孔优化 e.g goto L1 goto L2 // 语句前无标号，死代码 L1: … L2: … － 控制流优化

6 代码优化的种类－窥孔优化 goto L1 … L1: goto L2 goto L2 … L1: goto L2
if a<b goto L1 … L1: goto L2 if a<b goto L2 … L1: goto L2 goto L1 //唯一跳转L1 … //L1前是无条件跳转 L1: if a <b goto L2 L3: if a < b goto L2 goto L3 … L3:

7 代码优化的种类－窥孔优化 － 强度消弱、删除无用指令 e.g. MUL $8, R0 -> ShiftLeft $3, R0
ADD $0, R1 // 删除，未改变R1 MUL $1, R2 // 删除 － 利用目标机指令特点 e.g. inc、enter(建立栈帧）leave（清除栈帧） CISC 系统的“复杂”寻址模式 － 其它优化措施，如常量合并、复写传播等

8 代码优化的种类－局部优化 基本块和流图 － 基本块：能顺序执行的程序代码序列。其入口为： － 程序的第一代码
－ 条件或无条件转移代码所转到的目标代码 － 跟在条件或无条件转移代码后的代码 － 基本块划分 － 相邻入口中间的代码序列（仅含前一入口） － 某入口到程序的停止语句代码之间的代码序列 － 流图：由基本块按控制流方向形成的有向图 基本块内优化，主要有： － 常量传播、合并和公共子表达式删除 － 复写传播与死代码（无用代码）删除

9 代码优化的种类－全局优化 基本块间优化－基本块间控制流与数据流分析技术 优化措施主要有： － 循环优化 ：80/20 规则
－ 不变式外提、归纳变量删除、强度消弱等 － 公共子表达式删除 － 常量传播、合并常量、复写传播 － 死代码（无用赋值）删除

10 典型的优化编译器的组织 前 端 代 码 生成器 优化器 变 换 数据流 分 析 控制流 中间表示 中间表示

11 优化举例 //B1 (1) i := m 1 (2) j := n (3) t1 := 4 * n (4) v := a[t1]
快速排序程序片段如下， i = m  1; j = n; v = a[n]; while (1) { do i = i +1; while(a[i]<v); do j =j 1;while (a[j]>v); if (i >= j) break; x=a[i]; a[i]=a[j]; a[j]=x; } x=a[i]; a[i]=a[n]; a[n]=x;

12 优化举例 //B2 (5) i := i + 1 (6) t2 := 4 * i (7) t3 := a[t2] 快速排序程序片段如下，
(8) if t3 < v goto （5） 快速排序程序片段如下， i = m  1; j = n; v = a[n]; while (1) { do i = i +1; while(a[i]<v); do j =j 1;while (a[j]>v); if (i >= j) break; x=a[i]; a[i]=a[j]; a[j]=x; } x=a[i]; a[i]=a[n]; a[n]=x;

13 优化举例 快速排序程序片段如下， //B3 i = m  1; j = n; v = a[n]; (9) j := j 1
while (1) { do i = i +1; while(a[i]<v); do j =j 1;while (a[j]>v); if (i >= j) break; x=a[i]; a[i]=a[j]; a[j]=x; } x=a[i]; a[i]=a[n]; a[n]=x; //B3 (9) j := j 1 (10) t4 := 4 * j (11) t5 := a[t4] (12) if t5 > v goto (9)

14 优化举例 快速排序程序片段如下， i = m  1; j = n; v = a[n]; while (1) {
do i = i +1; while(a[i]<v); do j =j 1;while (a[j]>v); if (i >= j) break; x=a[i]; a[i]=a[j]; a[j]=x; } x=a[i]; a[i]=a[n]; a[n]=x; //B4 (13) if i >= j goto (23)

15 优化举例 //B5 (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) 快速排序程序片段如下， i = m  1; j = n; v = a[n]; while (1) { do i = i +1; while(a[i]<v); do j =j 1;while (a[j]>v); if (i >= j) break; x=a[i]; a[i]=a[j]; a[j]=x; } x=a[i]; a[i]=a[n]; a[n]=x;

16 优化举例 快速排序程序片段如下， i = m  1; j = n; v = a[n]; while (1) {
do i = i +1; while(a[i]<v); do j =j 1;while (a[j]>v); if (i >= j) break; x=a[i]; a[i]=a[j]; a[j]=x; } x=a[i]; a[i]=a[n]; a[n]=x; //B6 (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

17 优化举例－流图 i := m 1 B1 j := n t1 := 4 * n v := a[t1] B2 i := i + 1
t2 := 4 * i t3 := a[t2] if t3 > v goto B2 B1 B2 j := j 1 t4 := 4 * j t5 := a[t4] if t5 > v goto B3 if i >= j goto B6 B4 B3 B5 B6

18 优化举例 公共子表达式删除 －基本块内 t6 := 4 * i x := a[t6] t7 := 4 * i t8 := 4 * j
公共子表达式删除 －基本块内 B5 t6 := 4 * i x := a[t6] t7 := 4 * i t8 := 4 * j t9 := a[t8] a[t7] := t9 t10 := 4 * j a[t10] := x goto B2 t11 := 4 * i x := a[t11] t12 := 4 * i t13 := 4 * n t14 := a[t13] a[t12] := t14 t15 := 4 * n a[t15] := x B6 变 换

19 优化举例 公共子表达式删除 －基本块内 t6 := 4 * i x := a[t6] t8 := 4 * j t9 := a[t8]
公共子表达式删除 －基本块内 B5 t6 := 4 * i x := a[t6] t8 := 4 * j t9 := a[t8] a[t6] := t9 a[t8] := x goto B2 t11 := 4 * i x := a[t11] t13 := 4 * n t14 := a[t13] a[t11] := t14 a[t13] := x B6

20 优化举例 公共子表达式删除－基本块间 t2:=4 * i : B2 -- B5 t2:=4 * i : B2 -- B6
t4:= 4 * j : B3 -- B t1:= 4 * n : B1 -- B6 B5 t6 := 4 * i x := a[t6] t8 := 4 * j t9 := a[t8] a[t6] := t9 a[t8] := x goto B2 B6 t11 := 4 * i x := a[t11] t13 := 4 * n t14 := a[t13] a[t11] := t14 a[t13] := x 变 换

21 优化举例 公共子表达式删除－基本块间 t3:=a[t2] : B2 -- B5 t3:=a[t2] : B2 -- B6
x := a[t2] t9 := a[t4] a[t2] := t9 a[t4] := x goto B2 B6 x := a[t2] t14 := a[t1] a[t2] := t14 a[t1] := x 变 换

22 优化举例 公共子表达式删除－基本块间 B1中 v := a[t1] 能否作为公共子表达式？ x := t3 a[t2] := t5
goto B2 B6 x := t3 t14 := a[t1] a[t2] := t14 a[t1] := x

23 优化举例 复写传播 － 形成为f := g的赋值叫做复写语句 － 优化过程中会大量引入复写
－ 复写传播变换是在复写语句f := g后，尽可能用g代表f（暗示有前提条件） －复写传播变换带来 － 常量合并 － 死代码删除

24 优化举例 复写传播 x := t3 a[t2] := t5 a[t4] := x goto B2 x := t3 //可以考虑删除

25 优化举例 复写传播 x := t3 t14 := a[t1] a[t2] := t14 a[t1] := x
B6 x := t3 t14 := a[t1] a[t2] := t14 a[t1] := x B6 x := t3 //可以考虑删除 t14 := a[t1] a[t2] := t14 a[t1] := t3 B6中，t14 := a[t1] 可以复写传播吗？

26 优化举例 循环优化 － 代码外提 － 归纳变量删除 － 强度削弱 例：while (i <= limit  2 ) … 变换成
t = limit  2; //为什么提出循环？ while (i <= t ) …

27 优化举例 强度削弱和归纳变量删除 j和t4的值步伐一致地变化 这样的变量叫做归纳变量 B3 在循环中有多个归纳变量时， 也许只需要留下一个
这个操作由归纳变量删除 过程来完成 j := j 1 t4 := 4 * j t5 := a[t4] if t5 > v goto B3 B3

28 优化举例 除第一次外， t4 = 4 * j在B3的入口 一定保持 在j := j 1后， 关系t4 = 4 * j + 4也 保持 B3
i := m 1 j := n t1 := 4 * n v := a[t1] B1 B2 j := j 1 t4 := t4  4 t5 := a[t4] if t5 > v goto B3 B4 B3 B5 B6 t4 := 4 * j if i >= j goto B6 j := j 1 t4 := 4 * j t5 := a[t4] if t5 > v goto B3 B3 除第一次外， t4 = 4 * j在B3的入口 一定保持 在j := j 1后， 关系t4 = 4 * j + 4也 保持

29 优化举例 i := m 1 j := n t1 := 4 * n v := a[t1] t2 := 4 * i t4 := 4 * j
t3 := a[t2] if t3 > v goto B2 B1 B2 t4 := t4  4 t5 := a[t4] if t5 > v goto B3 if t2 >= t4 goto B6 a[t2] := t5 a[t4] := t3 goto B2 B4 B3 B5 t14 := a[t1] a[t2] := t14 a[t1] := t3 B6

30 代码优化（续） － 循环优化简介 2019/4/25 《编译原理与技术》之代码优化

31 流图中的循环 循环定义 必经结点（集合） 回边 － 程序流图中有唯一入口的强连通子图 － d DOM n 表示结点d是结点n的必经结点，
－ n->d, 如果d DOM n。 2019/4/25 《编译原理与技术》之代码优化

32 流图中的循环 自然循环 可归约流图 － 由回边 n->d 确定的循环Loop(n->d)
－ Loop(n->d) = { d } U {流图中所有不经过结点 d 而能达到结点 n 的其它结点} 可归约流图 － 去除流图中的回边后的子图是无环有向图 － 结构化程序流图是可归约的 － 存在不可归约流图 2019/4/25 《编译原理与技术》之代码优化

33 流图中的循环 1 2 3 4 5 6 7 8 9 10 e.g. 右边流图的必经结点树 e.g. 一个流图 1 2 3 4 5 6 7 8
2019/4/25 《编译原理与技术》之代码优化

34 流图中的循环 自然循环 回边10  7 循环{7, 8, 10} 回边7 4 循环{4, 5, 6, 7, 8, 10}
2 3 4 5 6 7 8 9 10 自然循环 回边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/4/25 《编译原理与技术》之代码优化

35 循环优化 代码外提 － 循环不变计算 － 前置结点 B0 B0 B0 循环L 循环L (b) 外提代码放在前置结点B0
(a) 代码外提前，B0是首结点 2019/4/25 《编译原理与技术》之代码优化

36 循环优化－代码外提 寻找循环不变计算 （1）标记循环各结点（基本块）中的语句x := y + z为不变计算，如果y和z均为常量或定值点在循环外（ud链）； （2）检查其余语句，如 w := x + u，如果x和u均为常量或定值点在循环外，或其唯一能达到的定值点已标记, 如 （1）中的x，则标记该语句； （3）重复（2）直至没有语句被标记为不变计算为止。 2019/4/25 《编译原理与技术》之代码优化

37 循环优化－代码外提 如何实施代码外提？ 考察已标记的循环不变计算，P: x := y + z ， 如果满足，
（3）循环中对 x 的引用均来自 P 点的定值。 问题：如果 P 点定值满足（2）和（3），而不满足（1），能否外提该代码？ 2019/4/25 《编译原理与技术》之代码优化

38 循环优化－代码外提 非法代码外提－case 1 j：我要1 i := 1 B1 i := 1 B1 if u < v goto B3
u := u + 1 B3 v := v -1 if v <= 20 goto B5 B4 j := i B5 i := 2 B6 if u < v goto B3 B2 代码外提 u := u + 1 B3 B4 v := v -1 if v <= 20 goto B5 j：我要1 j := i B5 2019/4/25 《编译原理与技术》之代码优化

39 循环优化－代码外提 非法代码外提－case 2 j：2呢？ i := 1 B1 i := 3 if u < v goto B3
u := u + 1 B3 v := v -1 if v <= 20 goto B5 B4 j := i B5 i := 2 B6 非法代码外提－case 2 我要外提？？ i := 1 B1 i := 3 if u < v goto B3 i := 2 u := u + 1 B3 v := v -1 if v <= 20 goto B5 B4 j := i B5 B2 代码外提 j：2呢？ 2019/4/25 《编译原理与技术》之代码优化

40 循环优化－代码外提 非法代码外提－case 3 i := 1 B1 i := 3 if u < v goto B3
u := u + 1 B3 B4 k := i v := v -1 if v <= 20 goto B5 i , 你从哪里来？ j := i B5 2019/4/25 《编译原理与技术》之代码优化

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 族归纳变量。 2019/4/25 《编译原理与技术》之代码优化

42 循环优化 强度消弱 － i 族归纳变量 j : ( i, c, d ), j := i * c + d;
－ 引入新变量 s ，在循环前置块末尾添加如下语句： s := c * i // 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 ) 2019/4/25 《编译原理与技术》之代码优化

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 2019/4/25 《编译原理与技术》之代码优化

44 循环优化举例 e.g. 对以下伪C程序片段进行有关循环优化 int A[100][100][100];
for ( i ＝ 0 ; i<100; i++) for ( j = 0; j<100; j++) for ( k = 0; k<100; k++) A[ i ][ j ][ k ] ＝ i * j * k; 2019/4/25 《编译原理与技术》之代码优化

45 循环优化举例－代码外提 for ( i ＝ 0 ; i<100; i++) for ( j = 0; j<100; j++)
for ( k = 0; k<100; k++) A[ i ][ j ][ k ] ＝ i * j * k; 对于最内层循环k而言，为循环不变计算 2019/4/25 《编译原理与技术》之代码优化

46 循环优化举例－代码外提 for ( i ＝ 0 ; i<100; i++) for ( j = 0; j<100; j++) {
A[ i ] 在循环j中保持“不变” for ( i ＝ 0 ; i<100; i++) for ( j = 0; j<100; j++) { t1 = addr( A [ i ][ j ] ); t2 = i * j; for ( k = 0; k<100; k++) t1[ k ] ＝ t2 * k; } // Loop j 2019/4/25 《编译原理与技术》之代码优化

47 循环优化举例－代码外提 for ( i ＝ 0 ; i<100; i++) { t3 = addr( A[ i ] );
for ( j = 0; j<100; j++) { t1 = addr( t3[ j ] ); t2 = i * j; for ( k = 0; k<100; k++) t1[ k ] ＝ t2 * k; } // Loop j } // Loop i 归纳表达式（变量） 2019/4/25 《编译原理与技术》之代码优化

48 循环优化举例－强度消弱 for ( i ＝ 0 ; i<100; i++) { t3 = addr( A[ i ] );
t4 = 0; // i * j 的初值 for ( j = 0; j<100; j++) { t1 = addr( t3[ j ] ); t2 = t4; t5 = 0; // t2 * k 的初值 for ( k = 0; k<100; k++) { t1[ k ] ＝ t5; t5 = t5 + t2; } // Loop k t4 = t4 + i; } // Loop j } // Loop i 利用复写传播， 删除t2 2019/4/25 《编译原理与技术》之代码优化

49 循环优化举例－强度消弱 上述程序中隐含的有价值的归纳表达式： addr(A[ i ]) 可以表示为：
A + i * , A 为数组开始地址 addr( t3[ j ] ) 可以表示为： t3 + j * 400 t1[ k ] 的地址表示为： t1 + k * 4 2019/4/25 《编译原理与技术》之代码优化

50 循环优化举例－强度消弱 应用复写传播，再次删除t3和 t1; t6 = A; // A + i * 40000的初值
for ( i ＝ 0 ; i<100; i++) { t3 = t6； t4 = 0; t7 = t3; // t3 + j * 400 的初值 for ( j = 0; j<100; j++) { t1 = t7; t5 = 0; t8 = t1; // t1 + k * 4 的初值; for ( k = 0; k<100; k++) { * t8 = t5; t5 = t5 + t4; t8 = t8 + 4 ; } // Loop k t4 = t4 + i; t7 = t ; } // Loop j t6 = t ; } // Loop i 应用复写传播，再次删除t3和 t1; 2019/4/25 《编译原理与技术》之代码优化

51 循环优化举例－强度消弱 结果最优了？ t6 = A; // A + i * 40000的初值
for ( i ＝ 0 ; i<100; i++) { t4 = 0; t7 = t6; for ( j = 0; j<100; j++) { t5 = 0; t8 = t7; for ( k = 0; k<100; k++) { * t8 = t5; t5 = t5 + t4; t8 = t8 + 4 ; } // Loop k t4 = t4 + i; t7 = t ; } // Loop j t6 = t ; } // Loop i 结果最优了？ 2019/4/25 《编译原理与技术》之代码优化