代码优化-经解.doc

代码优化概述

李 文 军
（中山大学计算机科学系·软件工程实验室）


Last Update：2007-05-30

l 代码优化部分的内容主要参考：吕映芝、张素琴等《编译原理》 (1998, 清华大学出版社)。

一、代码优化概述

l 注意概念：优化并非最优，只是相对较好。

l 注意一种现象：据统计，程序执行的 90%时间花在 10%的代码。

1、优化前提：等价变换，即要求程序变换前后的运行结果相同（但通常缺乏严格的定义，即以形式语
义学证明一种优化是正确的）。

2、优化目标：时间优化 vs. 空间优化。通常是一对矛盾的目标，需要折衷（trade-off）。

3、优化层次：
(1) 源代码优化，虽需人工完成，但是最有效的优化途径；
(2) 中间代码优化，具有普遍意义；
(3) 目标代码优化，依赖于具体机器特点。

4、优化范围：
(1) 局部优化，以单入口、单出口的基本程序块为单位；
(2) 循环优化，以循环语句为单位；
(3) 全局优化，在整个程序范围内做优化。

5、一个例子：通过一个简单的实例了解优化的基本方法。

源程序：

中间代码：

p := 0;
for i := 1 to 20 do p := p + A[i] * B[i];

(1) p := 0
(2) i := 1

(3) t1 := 4 * i
(4) t2 := addr(A) - 4
(5) t3 := t2[t1]
(6) t4 := 4 * i
(7) t5 := addr(B) - 4
(8) t6 := t5[t4]
(9) t7 := t3 * t6
(10) p := p + t7
(11) i := i + 1
(12) if i ≤ 20 goto (3)

李文军：《编译原理》补充材料
B1

B2


下标从 1 开始；(3)和(4)的次序与教
材中的翻译模式刚好相反；整数数
组，每个整数占 4 个字节。


第 1 页

对中间代码的优化：
(1) 删除多余运算（合并公共子表达式）：
(6)的运算多余，可改为 (6) t4 := t1 。

(2) 代码外提：
(4)、{7}在每次循环时都保持不变，将(4)和(7)外提并合并(6)的公共运算后，中间代码变为：

(1) p := 0
(2) i := 1
(4) t2 := addr(A) - 4
(7) t5 := addr(B) - 4

(3) t1 := 4 * i
(5) t3 := t2[t1]
(6) t4 := t1
(8) t6 := t5[t4]
(9) t7 := t3 * t6
(10) p := p + t7
(11) i := i + 1
(12) if i ≤ 20 goto (3)

(3) 强度削弱（将强度大的运算替换为强度小的运算）：


B1

B2

由于 t1与 i 线性增长，可将循环中的乘法运算*改为加法运算+，强度削弱后中间代码变为：

(1) p := 0
(2) i := 1
(4) t2 := addr(A) - 4
(7) t5 := addr(B) - 4
(3) t1 := 4 * i

(5) t3 := t2[t1]
(6) t4 := t1
(8) t6 := t5[t4]
(9) t7 := t3 * t6
(10) p := p + t7
(11) i := i + 1
(3') t1 := t1 + 4
(12) if i ≤ 20 goto (3)

*** 某些强度削弱优化可在语法制导地生成中间代码的同时完成。


B1

B2

*** 类似的优化譬如：将 x * 8 转换为 x << 3，将 2 * x 转换为 x + x，将 B and true 转换为 B。

(4) 变换循环控制条件：
将 i ≤ 20 改为 t1≤ 80，使 i 不再被引用，从而在下一步优化时可被删除。

李文军：《编译原理》补充材料


第 2 页

(5) 合并已知量/复写传播：
(3)中的 i 已知为 1，故将(3)改为 t1 := 4；
(8)引用 t4，(6)～(8)未改变 t4，故将(8)改为 t6 := t5[t1]。
优化结果为：

(1) p := 0
(2) i := 1
(4) t2 := addr(A) - 4
(7) t5 := addr(B) - 4
(3) t1 := 4

(5) t3 := t2[t1]
(6) t4 := t1
(8) t6 := t5[t1]
(9) t7 := t3 * t6
(10) p := p + t7
(11) i := i + 1
(3') t1 := t1 + 4
(12) if t1≤ 80 goto (3)

(6) 删除无用赋值：
(6)对 t4赋值，后无引用，可删除；
(11)对 i 赋值，后无引用，可删除；
(2)对 i 赋值，只有(11)引用，此时亦可删除。
优化结果为：

(1) p := 0
(2) i := 1
(4) t2 := addr(A) - 4
(7) t5 := addr(B) - 4
(3) t1 := 4

(5) t3 := t2[t1]
(6) t4 := t1
(8) t6 := t5[t1]
(9) t7 := t3 * t6
(10) p := p + t7
(11) i := i + 1
(3') t1 := t1 + 4
(12) if t1≤ 80 goto (3)

李文军：《编译原理》补充材料


B1

B2

B1

B2


第 3 页