静态分析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的最后一条指令