编译原理之基本块和流图
基本块和流图
•采用图的方式表示中间代码，有助于生成更好的代码
ä构造方法
1.把中间代码划分成基本块（basic block，BB），每个基本块满足如下条件：
①控制流只能从基本块的第一个指令进入
②除了基本块的最后一条指令，控制流在离开基本块前不会停机或者跳转
2.基本块形成了流图（flow graph）的结点，流图的边指明了哪些基本块可能紧随一个基本块之后执行
ä中断等程序行为可能打破基本块的上述约定1
•构造基本块和流图的目的是对代码进行优化
ä如果中断正常返回，则中断本身的保护机制可以使程序正常执行下去，不影响正确性，但可能形象优化效果
ä如果中断导致异常退出，优化的结果也不会有错，程序本身非正常终止
基本块（１）
•基本块：
ä定义：基本块是程序中最大限度顺序执行的语句序列，其中只有一个入口和出口，入口是其第一个语句，出口是其最后一个语句
ä基本块的入口语句可能是
•程序的第一个语句
•跳转的目标语句
•条件跳转的下一条语句
ä基本块的结束语句可能是
•停机语句
•跳转语句
•跳转目标语句的前一个语句（词法序）
•基本块（续）
ä构造方法
•输入：一个三地址指令序列
•输出：与之对应的基本块列表，每个指令恰好被分到一个基本块中
•方法：
ä首先，取定中间代码序列中哪些指令是首指令（leader，入口指令，基本块的第一条指令）
1.中间代码的第一个三地址指令是一个首指令
2.任意一个条件或无条件转移指令的目标指令是一个首指令
3.紧跟在一个条件或无条件转移指令之后的指令是一个首指令
ä然后，每个首指令对应的基本块包括了从它自己开始，直到下一个首指令（不含）或者中间程序的结尾指令之间的所有指令
ä一个特殊情况：过程调用语句作为一个新的基本块的开始，甚至独立成为一个基本块
后续使用信息
•下次不再引用意味着优化的机会
ä寄存器优化
ä临时名字存储单元的指派
•计算后续使用信息
ä三地址语句中名字的使用（use）定义：
•假定三地址语句i把a的值赋给x，如果语句j用x作为运算对象，并且控制从i流到j，这条路径中没有x的其它赋值，则称j引用x在i定的值
•此时，称x在语句i处活跃（live）
ä在基本块内：后续使用信息
•对每个基本块反向扫描
•为每个名字x在符号表中登记它是否在本块中有后续使用
•如果在本块中没有后续使用，则登记它是否在本块的出口活跃。缺省认为所有的非临时变量在出口都是活跃的
ä算法8.7：对一个基本块中的每一个语句确定活跃性与后续使用信息
•输入：一个三地址语句的基本块B，假设在基本块B开始时，所有的非临时变量都是活跃的
•输出：对于每一个语句i：x = y op z，将x、y及z的活跃性信息及后续使用信息关联到i
•方法：从基本块B的最后一个语句开始，反向扫描到B的开始处。对每一个三地址语句 i：x := y op z，依次执行下述步骤：
ä把当前符号表中x、y和z的后续使用信息和活跃信息附加到语句i上；（若x不活跃，则这个语句可以删掉）
ä在符号表中设置x为“无后续使用”和“不活跃”；
ä把符号表中y和z的后续使用信息均置为i，活跃信息均置为“活跃”。
注意：上述次序不能颠倒，因为x可能是y或z
流图（1）
•定义：控制流图或流图
ä结点是基本块的有向图G = ( N, E, root)
•N是结点的集合，每个结点表示一个基本块
•E是边的集合，如果结点ni和nj间存在前驱和后继的关系，则在存在一条从ni到nj的有向边（此时意味着，在ni执行后，可能会执行nj）
äni的出口语句是goto(s)或if … goto(s)，且(s)是的nj入口语句
änj在程序中的位置紧跟在ni后，且ni的出口语句不是无条件转移语句和停语句
•root是流图的首结点（或称为根结点），是包含程序第一个语句的基本块
ä每个流图都可以等价变换为单入口，且每个结点最多有两个后继的图
流图的表示方式
•可以用任意的表示图的数据结构表示流图
•结点（基本块）
ä基本块是一个指令序列
ä可能要频繁改变这个指令序列
•数量或组成的指令
•目的之一是优化
ä采用指令链表的形式较为高效