基本块 (Basic Block)
基本块是满足下列条件的最大的连续三地址指令序列
- 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令。
- 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机。
基本块划分算法
-
输入
三地址指令序列 -
输出
输入序列对应的基本块列表，其中每个指令恰好被分配给一个基本块。 -
方法
首先，确定指令序列中哪些指令是首指令 (leaders) ，即某个基本块的第一个指令。- 指令序列的第一个三地址指令是一个首指令
- 任意一个条件或无条件转移指令的目标指令是一个首指令
- 紧跟在一个条件或无条件转移指令之后的指令是一个首指令
然后，每个首指令对应的基本块包括了从它自己开始，直到下一个首指令(不含)或者指令序列结尾之间的所有指令。
例.png
流图(Flow Graphs)
- 流图的结点是一些基本块
- 从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B。此时称B是C的前驱(predecessor)，C是B的后继(successor)。
有两种方法可以确认这样的边：
- 有一个从B的结尾跳转到C的开头的条件或无条件跳转语句
- 按照原来的三地址语句序列中的顺序，C紧跟在之B后，且B的结尾不存在无条件跳转语句。
例.png
例.png
网友评论