、程序流图的构造 程序流图是程序的图形表示。我们把有唯一首结点 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的第二次 定值，则前一定值为无用赋值。