静态分析2：控制流分析（构建CFG）
参考：南京大学《软件分析》课程2
1、控制流分析
- 控制流分析实际上指的是构建控制流图（Control Flow Graph，CFG）
- CFG是静态分析的基础数据结构
- CFG的节点可以是单个指令、基本块（Basic Block，BB）
2、构建基本块（Basic Block，BB）
（1）基本块的概念
Basic blocks (BB) are maximal sequences of consecutive three-address instructions with the properties that
- It can be entered only at the beginning, i.e., the first instruction in the block
- It can be exited only at the end, i.e., the last instruction in the block
解释：
基本块是具有以下属性的连续3AC指令的最大序列：
- 只有一个入口，仅在开头进入，即块的第一条指令。
- 只有一个出口，仅在结尾退出，即块的最后一条指令。
（2）构建基本块
INPUT: A sequence of three-address instructions of P
OUTPUT: A list of basic blocks of P
METHOD:
(1) Determine the leaders in P
• The first instruction in P is a leader
• Any target instruction of a conditional or
unconditional jump is a leader
• Any instruction that immediately follows a
conditional or unconditional jump is a leader
(2) Build BBs for P
• A BB consists of a leader and all its subsequent
instructions until the next leader
解释：
输入：程序的3AC指令序列
输出：程序的基本块序列
方法：
（1）确定每个基本块的第一条指令leader
• 程序的第一条指令作为leader；
• 有条件或无条件跳转的目标指令作为leader；
• 紧接着有条件或无条件跳转指令的下一条指令作为leader
（2）构建基本块
• BB由一个leader及其所有后续指令组成，直到下一个leader
例子：
3、构建控制流图（Control Flow Graph ，CFG）
• The nodes of CFG are basic blocks goto (i) Control Flow Graph (CFG)
• There is an edge from block A to block B if and only if
- There is a conditional or unconditional jump from the end of A to the beginning of B
- B immediately follows A in the original order of instructions and A does not end in an unconditional jump
• It is normal to replace the jumps to instruction labels by jumps to basic blocks
• Usually we add two nodes, Entry and Exit.
- They do not correspond to executable IR
- An edge from Entry to the BB containing the first instruction of IR
- An edge to Exit from any BB containing an instruction that could be the last instruction of IR
解释：
• 控制流图的节点是基本块
• 基本块之间的边
- 有条件或无条件跳转的基本块之间存在一条跳转边
- 按照指令的原始顺序，基本块之间存在一条顺序边，但无条件跳转的基本块不存在顺序边
• 将跳转到指令替换成跳转到基本块
• 添加entry和exit
- CFG和IR通常不对应
- Entry到BB的边，包括IR的第一条指令
- BB到Exit的边（可能是多条），包括IR的最后一条指令
