基本概念
基本块：是语句的一个序列，从第一条执行到最后一条
- 不能从中间进入，不能从中间退出，即跳转指令只能出现在最后
控制流图：控制流图是一个有向图G=(V，E)
- 节点V：是基本块
- 边E：是基本块之间的跳转关系
控制流图的定义
是更精细的三地址码
数据结构定义（以B为例）
struct Block {Label_t label;List_t stms;Jump_t j;
};如何生成控制流图？
（1）可以直接从抽象语法树生成
- 如果高层语言具有特别规整的控制流结构的话较容易
（2）也可以先生成三地址码，然后继续生成控制流图
- 对于像C这样的语言更合适，因为其中包含像goto这样的非结构化的控制流语句
- 更加通用（阶段划分！）
使用控制流图的编译器结构
由三地址码生成控制流图算法（线性扫描算法）
List_t stms; // 三地址码中所有语句
List_t blocks = {}; // 控制流图中的所有基本块
Block_t b = Block_fresh(); // 一个初始的空的基本块
scan_stms()
{foreach(s ∈ stms)if (s is "Label L") // s是标号b.label = L;else (s is some jump) // s是跳转b.j = s;blocks ∪= {b};b = Block_fresh();else // s是普通指令b.stms ∪= {s};
}控制流图的基本操作
● 标准的图论算法都可以用在控制流图的操作上
- 各种遍历算法、生成树、必经节点结构等等。
● 图节点的顺序有重要的应用
- 拓扑序、逆拓扑序、近似拓扑序等等。
这里我们不详细展开这些算法，而是通过研究一个具体的例子来展示基本图算法的应用
- 死基本块删除优化
例子：死基本块删除优化
int f()
{int i = 3;while (i < 10){i = i + 1;printi(i);continue;printi(i);}return 0;
}对上述程序，构建出对应的控制流图如下（L0为入口块，L2为出口块）
通过观察我们可以看出，上图中并没有任何一条边进入L3（即L3的入度为0），L3这个块是从L0出发对这个图做遍历不可达的一个块，这样的块称为死基本块。这个块是不可能被执行到的。
死基本块删除算法
- 输入：控制流图g
- 输出：经过死基本块删除后的控制流图
dead_blocks_elim(g)dfs(g);for (each node in g)if (!visited(n))delete(n);
