控制流(Control Flow)：操作的序列
控制流分析(Control Flow Analysis)：通过分析程序去发现每一过程内控制流层次结构。
控制流分析的原因：
- 控制流分析(CFA)能够帮助我们理解控制流图（control-flow graphs,CFG）的结构
- 能够确定控制流图中的循环结构
- 通过CFA获得的必经结点信息，为代码动作形成条件
- SSA形式的构造
- 通过CFA获得区间结构，来实现数据流分析
- 寻找在并行化中所需要的控制依赖
控制流分析的方法
确定构造过程的基本块构造CFG，有如下两种途径：
- 使用必经结点来找出循环，并为优化简单地标识出它所找到的循环
- 区间分析（成熟变体：结构分析（对例程中的每一种控制流结构进行分类））
基本块
1、基本块（basic block）：
一个只能从第一条指令进入，最后一条指令离开的最长指令序列。
2、构建基本块
先确定首领（leader）：基本块的第一条指令
- 例程的入口点，或
- 分支的目标，或
- 直接紧跟在分支指令或返回指令之后的所有指令
3、构建基本块的算法
Input: List of n instructions(instr[i]=ith instruction)
Output: Set of leaders & list of basic blocks(block[x] is block with leader x)//第一条指令是领导
leaders = {1}
for i = 1 to n //找到所有的领导if instr[i] is a branchleaders = leaders U set of potential targets of instr[i]
for each xleadersblock[x] = {x}i = x + 1 //补足第x个基本块while i<=n and ileadersblock[x] = block[x] {i}i = i + 1
控制流图（CFG）
1、定义：有向图
注意：entry,exit基本块不是实质性的，引入是为了算法的描述简单
2、构造过程
- 每一个CFG节点代表一个基本块
- 节点i到j有边，若
- 基本块i的最后一条语句分支跳转到块j的第一条语句，或者
- 块i不是以无条件分支结束且块j直接跟在其后面
3、从基本块构造CFG算法
Input:A list of m basic blocks(block)
Output:A CFG where each node is a basic blockfor i = 1 to nx = last instruction of block[i]if instr x is a branchfor each target(to block j)of instr xcreate an edge from block i to block jif instr x is not an unconditional branchcreate an edge from block i to block i+1例子（鲸书中的）：
扩展基本块
1、扩展基本块（extended basic block）:
从一个首领开始的最长指令序列，在这个指令序列中，除了第一个结点之外不含其他汇合结点
- 只有一个入口且可能有多个出口（可看作以入口基本块为根的一棵树）
- 某些局部优化（如指令调度）在扩展基本块上更加有效
2、算法
对以r为根的扩展基本块，构造其内诸基本快的索引集合
全局变量EbbRoots记录扩展基本块的根基本块
procedure Build_Ebb(r,Succ,Pred)
{Ebb = {}Add_Bbs(r,Ebb,Succ,Pred)return Ebb
}procedure Add_Bbs(r,Ebb,Succ,Pred)
{Ebb = Ebb{r}for each xSucc(r) doif |Pred(x)|=1& xEbb thenAdd_Bbs(x,Ebb,Succ,Pred)else if xEbbRoots thenEbbRoots = EbbRoots{x}
}
