编译原理 第七章代码优化 上海交通大学 张冬茉 Email:Zhang-dm@cssjtu.edu.cn 2004年6月
1 编译原理 第七章 代码优化 上海交通大学 张冬茉 Email:zhang-dm@cs.sjtu.edu.cn 2004年6月
本章目的 代码优化是从生成的目标代码中识 别出那些可以经过变换而提高效率的部 分,并实施这种变换。这种优化并不是 极值理论中的那种求极值点的优化,它 只追求变换后的代码要比变换前的效率 要高些
2 本章目的 代码优化是从生成的目标代码中识 别出那些可以经过变换而提高效率的部 分，并实施这种变换。这种优化并不是 极值理论中的那种求极值点的优化，它 只追求变换后的代码要比变换前的效率 要高些
第七章代码优化 §7.1优化概述 、优化定义 优化是一种等价、有效的程序变换。等价是指不改变 程序运行结果,即对变换前后的程序给以相同的输入, 应有相同的输出,即变换是安全的。 而有效是指经变换后的程序与变换前的程序相比运行 速度更快,所占空间更少,也即所谓时空效益要高。 时间短空间省,这两个要求可以是相容的,并行不悖 的。数据不相关的两个循环,经循环合并构成一个循 环,循环控制的开销节省了,代码长度也因此缩短了。 但有时,时间短空间省的要求可能会不可兼得,这时 就有牺牲时间换取空间或牺牲空间换取时间两种策略, 需要有个综合分析和实事求是的取舍
3 第七章 代码优化 §7.1 优化概述 一、优化定义 优化是一种等价、有效的程序变换。等价是指不改变 程序运行结果，即对变换前后的程序给以相同的输入， 应有相同的输出，即变换是安全的。 而有效是指经变换后的程序与变换前的程序相比运行 速度更快，所占空间更少，也即所谓时空效益要高。 时间短空间省，这两个要求可以是相容的，并行不悖 的。数据不相关的两个循环，经循环合并构成一个循 环，循环控制的开销节省了，代码长度也因此缩短了。 但有时，时间短空间省的要求可能会不可兼得，这时 就有牺牲时间换取空间或牺牲空间换取时间两种策略， 需要有个综合分析和实事求是的取舍。
二、不同阶段的优化 (1)优化可以在源程序阶段也可以在编译阶段进行 (2)编译优化又可分成两个阶段,即中间代码优化与目 标代码优化:编译优化工作中有一部分与目标机 有关,有效而合理地使用机器资源便是目标代码优 化阶段要实现的 (3)中间代码的优化有局部化与非局部优化之分。局 部优化是指基本块内的优化,非局部优化是指超越 基本块的优化,因此对中间代码划分基本块,是优 化所必需的 (4)非局部优化也有循环优化与全书局优化之分,将 中间代码以基本块为结点,构造出程序流图,从中 识别出循环结构
4 二、不同阶段的优化 (1)优化可以在源程序阶段也可以在编译阶段进行 (2)编译优化又可分成两个阶段，即中间代码优化与目 标代码优化 ：编译优化工作中有一部分与目标机 有关，有效而合理地使用机器资源便是目标代码优 化阶段要实现的 (3) 中间代码的优化有局部化与非局部优化之分。局 部优化是指基本块内的优化，非局部优化是指超越 基本块的优化，因此对中间代码划分基本块，是优 化所必需的。 (4) 非局部优化也有循环优化与全书局优化之分，将 中间代码以基本块为结点，构造出程序流图，从中 识别出循环结构
优化 源程序优编译优化 中间代码目标代码 优化 局部优化非局部优 循环优化全局优化 图71在各个阶段的优化
5 优化 源程序优 化 编译优化 中间代码 优化 目标代码 优化 非局部优 化 局部优化 循环优化 全局优化 图7.1 在各个阶段的优化
、程序流图的构造 程序流图是程序的图形表示。我们把有唯一首结点 n0的有向图G称为控制流程图。首结点n0是到图 中任何结点n都有道路n0→n的一个特殊的结点。 因此控制流程图是一个三元组G=(N、E、m0), 其中N为结点集(包括n0),E为有向边集。通常将 控制流程图简称为流图,或程序流图。对一个程 序流图来说,结点代表计算,有向边代表控制流, 而首结点是程序起始位置所在的结点(基本块) 基本块 基本块是程序语句序列中满足下列条件的长度最长 的子序列:这个语句子序列是顺序执行的;它只 有一个入口即子序列的第一语句;只有一个出口 即子序列的最后一个语句。停止语句和转向(分 支)语句只可能是基本块的最末一个语句
6 三、程序流图的构造 程序流图是程序的图形表示。我们把有唯一首结点 n0的有向图G称为控制流程图。首结点n0是到图 中任何结点n都有道路n0→n的一个特殊的结点。 因此控制流程图是一个三元组G=(N、E、n0)， 其中N为结点集(包括n0)，E为有向边集。通常将 控制流程图简称为流图，或程序流图。对一个程 序流图来说，结点代表计算，有向边代表控制流， 而首结点是程序起始位置所在的结点(基本块)。 1. 基本块 基本块是程序语句序列中满足下列条件的长度最长 的子序列：这个语句子序列是顺序执行的；它只 有一个入口即子序列的第一语句；只有一个出口 即子序列的最后一个语句。停止语句和转向(分 支)语句只可能是基本块的最末一个语句。
2.划分基本块的算法 输入:三地址语句序列 输出:基本块表。每个三地址语句,仅在一个基本块 中。方法: (1)首先确定各个基本块的第一个语句即入口语句 规则是:程序的第一个语句。 能由条件或无条件转移语句转移到的语句 紧跟在条件转移语句后的那个语句。 (2)由每个入口语句构造所在的基本块:①由一入口 语句到转移或停止语句(含转移或停止语句)之间的 语句序列。②由一入口语句到下一入口语句(不含 下一入口语句)之间的语句序列。 (3)凡未被归入基本块的语句,为程序控制流图不能 到达的语句,因此为不可能执行的语句,故可从程 序中删除。 7
7 2. 划分基本块的算法 输入：三地址语句序列。 输出：基本块表。每个三地址语句，仅在一个基本块 中。方法： (1) 首先确定各个基本块的第一个语句即入口语句。 规则是：程序的第一个语句。 能由条件或无条件转移语句转移到的语句。 紧跟在条件转移语句后的那个语句。 (2) 由每个入口语句构造所在的基本块：①由一入口 语句到转移或停止语句(含转移或停止语句)之间的 语句序列。②由一入口语句到下一入口语句(不含 下一入口语句)之间的语句序列。 (3) 凡未被归入基本块的语句，为程序控制流图不能 到达的语句，因此为不可能执行的语句，故可从程 序中删除。
3.构造流图的算法 输入:划分基本块算法输出的基本块表 输出:程序流图G=(N,E,m0 方法: (1)输入的基本块集即为N (2)含有程序第一个语句的基本块为首结点n0。 (3)对N中任两个结点(基本块)B和B如果B紧跟在Bi 之后,且Bi的出口语句不是无条件转移或停止语句; 或B的出口语句是转移语句,其转向点为B的第一个 语句。则结点B和B之间有一有向边Bi→B。这些有 向边的集合为E。 8
8 3. 构造流图的算法 输入：划分基本块算法输出的基本块表 输出：程序流图G=(N, E, n0) 方法： (1) 输入的基本块集即为N。 (2) 含有程序第一个语句的基本块为首结点n0。 (3) 对N中任两个结点(基本块)Bi和Bj如果Bj紧跟在Bi 之后，且Bi的出口语句不是无条件转移或停止语句； 或Bi的出口语句是转移语句，其转向点为Bj的第一个 语句。则结点Bi和Bj之间有一有向边Bi→Bj。这些有 向边的集合为E。
§7.2局部优化 、基本块内的优化 局部优化是基本块内的优化,通常有: 1.合并已知量 对于A:=0pB或A:=BopC,其中B及C均为常数,则 编译时即可计算出opB或BopC的值,作为A的值, 而不必生成相应的代码。 2.删除公共子表达式 也称为删除多余运算。如图73的基本块B5中,语句 (14),(16)计算相同的4*称为公共子表达式,在 (14)6:=4*计算后(16)处只需将t6的值复写给7即 t7:=t6就可以了。语句(17)、(20)也有公共子表达式4*j, 故语句(20)可变换成10:=t8,这样就避免了多余运算
9 §7.2 局部优化 一、基本块内的优化 局部优化是基本块内的优化，通常有： 1. 合并已知量 对于A:=op B或 A:=B op C，其中B及C均为常数，则 编译时即可计算出op B或B op C的值，作为A的值， 而不必生成相应的代码。 2. 删除公共子表达式 也称为删除多余运算。如图7.3的基本块B5中，语句 (14)，(16)计算相同的4*I称为公共子表达式，在 (14)t6:=4*i计算后(16)处只需将t6的值复写给t7即 t7:=t6就可以了。语句(17)、(20)也有公共子表达式4*j， 故语句(20)可变换成t10:=t8，这样就避免了多余运算。
3.删除死代码 死代码有两种情况: (1)在分支程序中,测试语句取固定值,如取ture,则 false分支的代码是死代码。这种情况下删除死代码不 可能局限在基本块内 (2)变量A被定值后不再被引用,或者仅有的定值与引 用为A:=A+C的递归赋值形式,则该定值语句是死代 码,称为无用赋值。例如基本块B5中删除公共子表达 式后t7、t6有相同的值,故对7的引用可由t6来代替, 同样对t10的引用也可由t8来代替。故语句(19)可转换 成a6:=9,语句(21)可转换成a|t8:=x。如果t7,t10 出了基本块B5后也不活跃(即不再被引用),则(16)的 t7:=t6和(20)的t10:=t8便成为无用赋值。在基本块范围 内,变量A在定值后未经引用又发生了对A的第二次 定值,则前一定值为无用赋值 10
10 3. 删除死代码 死代码有两种情况： (1) 在分支程序中，测试语句取固定值，如取ture，则 false分支的代码是死代码。这种情况下删除死代码不 可能局限在基本块内。 (2) 变量A被定值后不再被引用，或者仅有的定值与引 用为A:=A+C的递归赋值形式，则该定值语句是死代 码，称为无用赋值。例如基本块B5中删除公共子表达 式后t7、t6有相同的值，故对t7的引用可由t6来代替， 同样对t10的引用也可由t8来代替。故语句(19)可转换 成a[t6]:=t9，语句(21)可转换成a[t8]:=x。如果t7, t10 出了基本块B5后也不活跃(即不再被引用)，则(16)的 t7:=t6和(20)的t10:=t8便成为无用赋值。在基本块范围 内，变量A在定值后未经引用又发生了对A的第二次 定值，则前一定值为无用赋值。