编译器笔记45-代码优化-流图

基本块 (Basic Block)

基本块是满足下列条件的最大的连续三地址指令序列

• 控制流只能从基本块的第一个指令进入该块。也就是说，没有跳转到基本块中间或末尾指令的转移指令。
• 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或者停机。

基本块划分算法

• 输入
  三地址指令序列

• 输出
  输入序列对应的基本块列表，其中每个指令恰好被分配给一个基本块。

• 方法
  首先，确定指令序列中哪些指令是首指令 (leaders) ，即某个基本块的第一个指令。

  1. 指令序列的第一个三地址指令是一个首指令
  2. 任意一个条件或无条件转移指令的目标指令是一个首指令
  3. 紧跟在一个条件或无条件转移指令之后的指令是一个首指令

  然后，每个首指令对应的基本块包括了从它自己开始，直到下一个首指令(不含)或者指令序列结尾之间的所有指令。

例.png

流图(Flow Graphs)

• 流图的结点是一些基本块
• 从基本块B到基本块C之间有一条边当且仅当基本块C的第一个指令可能紧跟在B。此时称B是C的前驱(predecessor)，C是B的后继(successor)。

有两种方法可以确认这样的边：

1. 有一个从B的结尾跳转到C的开头的条件或无条件跳转语句
2. 按照原来的三地址语句序列中的顺序，C紧跟在之B后，且B的结尾不存在无条件跳转语句。

例.png 例.png