对于删除公共子表达式和删除无用代码这两种优化技术， 我们在11.1中已经讨论过，这里简单介绍重新命名临时变量 和交换语句次序是什么含义。 重新命名临时变量：假如有语句t∶=b+c，其中t是临时 变量。如果把这个语句改为u∶=b+c，其中u是新的临时变量， 并且把这个t的所有引用改成u，那么基本块的运算结果不变。 交换语句次序： 如果基本块有两个相邻的语句： t1∶=b+c t2∶=x+y 当且仅当x和y都不是t1，b和c都不是t2时，我们可以交换这 两个语句的次序。
B
1
B
2
图 11.5变换循环控制条件， 合并已知量，复写传播
图11.4中，四元式（3） 可变为T1＝4，这种变换称为 合并已知量。 图11.4中，四元式(6)把T1 的值复写到T4中，四元式（8） 要引用T4的值，而从四元式 （6）到四元式（8）之间未改 变T4和T1的值，则将四元式 （8）改为T6∶=T5[T1]，这种 变换称为复写传播.复写传播之 后运算结果保持不变。 图11.4经过变换循环控制 条件，合并已知量和复写传播 等变换后，变为图11.5。
另外依据优化所涉及的程序范围，又可分为局部优化、 循环优化和全局优化三个不同的级别。局部优化指的是在 只有一个入口、一个出口的基本程序块上进行的优化。循 环优化是对循环中的代码进行的优化。全局优化是在整个 程序范围内进行的优化。
编译程序的优化工作旨在生成较好性能的目标代码， 为此，编译程序需要对代码（中间代码或目标代码）进行 各种方式的变换。变换的宗旨是： 等价－经优化工作变换后的代码运行结果应与原来程序运行 结果一样。 有效－经优化工作变换后的代码应运行时间较短，占用的存 储空间较小。 合算－获得较好性能的目标代码是优化工作的意图，而优化 本身包括大量的代码分析和变换工作，这里有个权衡： 应尽可能以较低的代价取得较好的优化效果。
11.2.1 基本块的划分
我们先定义基本块的入口语句。 所谓入口语句有三种，就是： ① 程序的第一个语句； ② 条件转移语句或无条件转移语句的转移目标语句； ③ 紧跟在条件转移语句后面的语句。
有了入口语句的概念之后，我们就可以给出划分中间 代码（四元式程序）为基本块的算法。
划分中间代码（四元式程序）为基本块的算法：
图11.2 中间代码段
B2
1）删除多余运算（删除公共子表达式） 优化的目的在于使生 成的目标代码较少而执行 速度较快。
(1)P:＝0 (2)I:＝1
B1
四元式（6）变换成： T4∶=T1。这种优化称为 删除多余运算或称为删除 公共子表达式。
(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)T4:＝T3*T6 (10)P:＝P+T7 (11)I:＝I+1 (12)if I≤20 goto (3)
(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)T4:＝T3*T6 (10)P:＝P+T7 (11)I:＝I+1 (3 )T1:＝T1+4 (12)if T1≤80 goto (5)B1B Nhomakorabea2
图 11.6 删除无用赋值
11.2 局部优化
我们所说的局部优化是指基本块内的优化。
所谓基本块，是指程序中一个单入口、单出口的线性 程序块（顺序执行的语句序列）。
控制流只能从其入口语句进入，从其出口语句退出, 没有中途停止或分支。 局部优化工作包括对于一个给定的程序，把它划分为 一系列的基本块,在各个基本块范围内分别进行优化。 局限于基本块范围内的优化称为基本块内的优化，也 称为局部优化。
(5)T3:＝T2[T1] (6)T4:＝T1 (8)T6:＝T5[T4] (9)T4:＝T3*T6 (10)P:＝P+T7 (11)I:＝I+1 (3 )T1:＝T1+4 (12)if I≤20 goto (5)
图11.4强度削弱
B2
4）变换循环控制条件
图11.4的代码中，四元式 （12）的循环控制条件I≤20 变换成T1≤80，这样整个程序 的运行结果不变。这种变换 称为变换循环控制条件。 经过这一变换后，循环 中I的值在循环后不会被引用， 四元式（11）成为多余运算， 可以从循环中删除。变换循 环控制条件可以达到代码优 化的目的。
(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)T4:＝T3*T6 (10)P:＝P+T7 (11)I:＝I+1 (3 )T1:＝T1+4 (12)if T1≤80 goto (5)
先求出四元式程序中各个基本块的 入口语句： 1. 语句（1）是程序的第一个语句， 因此它是入口语句。 2. 语句（4）和语句（8）是条件转移 语句或无条件转移语句的转移目标 语句，因此是入口语句。 3. 语句（6）是紧跟在条件转移语句 后面的语句，因此是入口语句。
(1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B>= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt
我们以下述四元式程序为例来说明如何划分基本块的。 例11.1:有四元式程序如下，构造其基本块。 (1) read (C) (2) A:= 0 (3) B:= 1 (4) L1: A:=A + B (5) if B>= C goto L2 (6) B:=B+1 (7) goto L1 (8) L2: write (A) (9) halt
① 求出四元式程序中各个基本块的入口语句。 ② 对每一入口语句，构造其所属的基本块。它是由该入 口语句到下一入口语句（不包括下一入口语句），或 到一转移语句（包括该转移语句），或到一停语句 （包括该停语句）之间的语句序列组成的。 ③ 凡未被纳入某一基本块的语句、都是程序中控制流程 无法到达的语句，因而也是不会被执行到的语句，可 以把它们删除。
第11章 代码优化
11.1 代码优化技术 11.2 局部优化 11.3 控制流程分析和循环
【学习目标】 通过本章学习： ◇ 理解所谓代码优化是指什麽？ ◇ 知道最常用的代码优化技术有哪些？ ◇ 知道实现代码优化要进行哪些工作？ 【学习指南】 所谓代码优化是指对程序代码进行等价变换。程序 代码可以是中间代码(如四元式代码)，也可以是目标代 码。优化的含义是最终生成的目标代码短(而运行速度 快)，时空效率优化。最常用的代码优化技术有删除多余 运算，循环不变代码外提，强度削弱，变换循环控制条 件，合并已知量与复写传播，以及删除无用赋值等等。 【难重点】 从概念上理解什么是代码优化，编译过程中可进行 哪些优化，以及进行优化所需要的基础都没有难点，但 在实现上是有相当复杂的工作。
优化可在编译的不同阶段进行，对同一阶段，涉及 的程序范围也有所不同，在同一范围内，可进行多种优 化。目前编译程序的优化工作一般是在中间代码生成之 后和（或）目标代码生成之后进行。如图11.1所示。
源程序 编译前端
中间代码
代码生成
目标代码
目标程序
中间代码优化
目标代码优化
中间代码的优化是对中间代码进行等价变换。目标代 码的优化是在目标代码生成之后进行的，因为生成的目标 代码对应于具体的计算机，因此，这一类优化在很大程度 上依赖于具体的机器，我们不做详细讨论。
图11.3 删除公共子表达式和代码外提
3）强度削弱
强度削弱的思想是 把强度大的运算换算 成强度小的运算。
(1)P:＝0 (2)I:＝1 (4)T2:＝addr(A)-4 (7)T5:＝addr(B)-4 (3)T1:＝4*I
B1
循环中计算T1值的 乘法运算变换成在循 环前进行一次乘法运 算，而在循环中将其 变换成加法运算。变 换后如图11.4所示。
B1
B2
图 11.5变换循环控制条件， 合并已知量，复写传播
6）删除无用赋值
在图11.5中，（6）对T4 赋值，但T4未被引用；另外， （2）和（11）对I赋值，但只 有（11）引用I。所以，只要 程序中其它地方不需要引用T4 和I，则（6），（2）和（11） 对程序的运行结果无任何作用。 我们称之为无用赋值，无用赋 值可以从程序中删除，如图 11.6所示。 比较图11.2和图11.6可看 出，经过优化后的代码的执行 效率提高了很多。当然，实现 这些优化的一系列工作是非常 复杂的，代价也是很大的。
B2
图11.2 中间代码段
2）代码外提
减少循环中代码总数的一 个重要办法是循环不变代码外 提。这种变换把循环不变运算， 即其结果独立于循环执行次数 的表达式，提到循环的前面,使 之只在循环外计算一次。
(1)P:＝0 (2)I:＝1
B
1
(4)T2:＝addr(A)-4 (7)T5:＝addr(B)-4
11.0 概述
源语言程序经过词法分析、语法分析、语义分析和中 间代码生成等编译前期工作（编译前端），得到了与源程 序等价的中间代码程序。中间代码程序的质量将直接影响 目标程序执行的效率。程序执行的效率体现在两个方面： 目标程序运行时刻所占用的存储空间和目标程序运行时刻 所耗费的时间。 所谓优化，是为了提高程序的执行效率而对程序代码 进行的等价变换。使得变换后的代码运行结果与变换前代 码运行结果相同，而运行速度加大或占用存储空间少，或 两者都有。 编译过程中可进行的优化可按阶段划分：优化可在编 译的不同阶段进行，分为中间代码一级和目标代码一级的 优化。可按优化涉及的程序范围划分：对同一阶段，分为 局部优化,循环优化和全局优化。可按优化是否涉及具体计 算机来划分：分为与计算机有关的优化和与计算机无关的 优化。