语义分析实战（四）—— 构建 CFG

章节标题

控制流图的核心作用

控制流图（CFG）是一种重要的程序表示形式，它的主要作用是：

表示程序控制流：直观地展示程序的执行路径
支持数据流分析：为数据流分析提供基础结构
支持代码优化：帮助识别优化机会，如循环优化、死代码消除等
支持程序分析：用于程序验证、测试覆盖率分析等

控制流图的基本概念

控制流图由以下元素组成：

基本块：一段顺序执行的代码，只有一个入口和一个出口
边：表示控制流的转移，从一个基本块指向另一个基本块
入口节点：程序的起始基本块
出口节点：程序的终止基本块

基本块的识别

基本块的识别是构建CFG的第一步，它的基本规则是：

入口点：
- 程序的第一个语句
- 跳转指令的目标语句
- 跳转指令之后的语句
出口点：
- 跳转指令
- return语句
- 程序的最后一个语句

从三地址码构建CFG的原理

从三地址码构建CFG的过程包括以下步骤：

识别基本块：根据上述规则识别程序中的基本块
为基本块编号：为每个基本块分配一个唯一的标识符
构建边：根据控制流关系构建基本块之间的边
确定入口和出口：确定CFG的入口节点和出口节点

基本块的识别算法

def identify_basic_blocks(instructions):
    """识别基本块"""
    # 第一步：识别所有入口点
    entry_points = set()
    entry_points.add(0)  # 程序的第一个语句是入口点
    
    for i, instr in enumerate(instructions):
        if instr['op'] == 'goto':
            # 跳转指令的目标是入口点
            target_label = instr['arg1']
            # 找到目标标签对应的指令索引
            for j, instr_j in enumerate(instructions):
                if instr_j['op'] == 'label' and instr_j['label'] == target_label:
                    entry_points.add(j)
                    break
            # 跳转指令之后的语句是入口点
            if i + 1 < len(instructions):
                entry_points.add(i + 1)
        elif instr['op'] == 'if':
            # 条件跳转指令的目标是入口点
            target_label = instr['result']
            # 找到目标标签对应的指令索引
            for j, instr_j in enumerate(instructions):
                if instr_j['op'] == 'label' and instr_j['label'] == target_label:
                    entry_points.add(j)
                    break
            # 条件跳转指令之后的语句是入口点
            if i + 1 < len(instructions):
                entry_points.add(i + 1)
        elif instr['op'] == 'return':
            # return语句之后的语句是入口点
            if i + 1 < len(instructions):
                entry_points.add(i + 1)
    
    # 第二步：构建基本块
    basic_blocks = []
    entry_points = sorted(entry_points)
    
    for i in range(len(entry_points)):
        start = entry_points[i]
        if i == len(entry_points) - 1:
            end = len(instructions)
        else:
            end = entry_points[i + 1]
        
        # 提取基本块的指令
        block_instructions = instructions[start:end]
        if block_instructions:
            basic_blocks.append({
                'id': f'B{i}',
                'start': start,
                'end': end - 1,
                'instructions': block_instructions,
                'successors': [],
                'predecessors': []
            })
    
    return basic_blocks

构建CFG的边

def build_cfg(basic_blocks, instructions):
    """构建CFG的边"""
    # 为每个基本块创建标签到基本块的映射
    label_to_block = {}
    for block in basic_blocks:
        # 检查基本块的第一条指令是否是标签
        if block['instructions'][0]['op'] == 'label':
            label_to_block[block['instructions'][0]['label']] = block
    
    # 为每个基本块创建索引到基本块的映射
    index_to_block = {}
    for block in basic_blocks:
        for i in range(block['start'], block['end'] + 1):
            index_to_block[i] = block
    
    # 构建边
    for block in basic_blocks:
        # 获取基本块的最后一条指令
        last_instr = block['instructions'][-1]
        
        if last_instr['op'] == 'goto':
            # 无条件跳转
            target_label = last_instr['arg1']
            if target_label in label_to_block:
                target_block = label_to_block[target_label]
                block['successors'].append(target_block['id'])
                target_block['predecessors'].append(block['id'])
        elif last_instr['op'] == 'if':
            # 条件跳转
            target_label = last_instr['result']
            if target_label in label_to_block:
                target_block = label_to_block[target_label]
                block['successors'].append(target_block['id'])
                target_block['predecessors'].append(block['id'])
            # 同时跳转到下一个基本块（如果有）
            block_index = basic_blocks.index(block)
            if block_index + 1 < len(basic_blocks):
                next_block = basic_blocks[block_index + 1]
                block['successors'].append(next_block['id'])
                next_block['predecessors'].append(block['id'])
        elif last_instr['op'] == 'return':
            # return语句，没有后继
            pass
        else:
            # 顺序执行，跳转到下一个基本块（如果有）
            block_index = basic_blocks.index(block)
            if block_index + 1 < len(basic_blocks):
                next_block = basic_blocks[block_index + 1]
                block['successors'].append(next_block['id'])
                next_block['predecessors'].append(block['id'])
    
    return basic_blocks

实用案例分析

案例：构建简单程序的CFG

假设我们有以下简单的三地址码：

t0 = 5
x = t0
t1 = 3
y = t1
t2 = x > y
if t2 != 0 goto L3
goto L4
L3:
t3 = x + y
z = t3
goto L5
L4:
t4 = x - y
z = t4
L5:
return z

对应的基本块识别结果如下：

基本块 B0：
- 指令：t0 = 5, x = t0, t1 = 3, y = t1, t2 = x > y, if t2 != 0 goto L3, goto L4
- 入口点：0
- 出口点：6
基本块 B1：
- 指令：L3:, t3 = x + y, z = t3, goto L5
- 入口点：7
- 出口点：10
基本块 B2：
- 指令：L4:, t4 = x - y, z = t4
- 入口点：11
- 出口点：13
基本块 B3：
- 指令：L5:, return z
- 入口点：14
- 出口点：15

构建的CFG如下：

B0 → B1
B0 → B2
B1 → B3
B2 → B3

CFG的可视化

为了更好地理解CFG，我们可以将其可视化。以下是一个简单的CFG可视化函数：

def visualize_cfg(basic_blocks):
    """可视化CFG"""
    print("=== Control Flow Graph ===")
    for block in basic_blocks:
        print(f"{block['id']}:")
        print(f"  Instructions: {block['start']}-{block['end']}")
        print(f"  Successors: {block['successors']}")
        print(f"  Predecessors: {block['predecessors']}")
    print("=======================")
    
    # 打印ASCII图
    print("\n=== CFG ASCII Diagram ===")
    for block in basic_blocks:
        for succ_id in block['successors']:
            print(f"{block['id']} → {succ_id}")
    print("=======================")

CFG的应用

CFG在编译器中有广泛的应用，包括：

数据流分析：
- 活跃变量分析
- 到达定值分析
- 可用表达式分析
代码优化：
- 循环优化
- 死代码消除
- 公共子表达式消除
程序分析：
- 测试覆盖率分析
- 程序验证
- 故障定位

构建CFG的完整实现

下面是一个完整的从三地址码构建CFG的实现示例：

class BasicBlock:
    """基本块类"""
    def __init__(self, id, start, end, instructions):
        self.id = id
        self.start = start
        self.end = end
        self.instructions = instructions
        self.successors = []
        self.predecessors = []
    
    def __str__(self):
        return f"{self.id}: {self.start}-{self.end}"

class CFG:
    """控制流图类"""
    def __init__(self, instructions):
        self.instructions = instructions
        self.basic_blocks = []
        self.entry_block = None
        self.exit_blocks = []
        self._build()
    
    def _identify_basic_blocks(self):
        """识别基本块"""
        # 第一步：识别所有入口点
        entry_points = set()
        entry_points.add(0)  # 程序的第一个语句是入口点
        
        for i, instr in enumerate(self.instructions):
            if instr['op'] == 'goto':
                # 跳转指令的目标是入口点
                target_label = instr['arg1']
                # 找到目标标签对应的指令索引
                for j, instr_j in enumerate(self.instructions):
                    if instr_j['op'] == 'label' and instr_j['label'] == target_label:
                        entry_points.add(j)
                        break
                # 跳转指令之后的语句是入口点
                if i + 1 < len(self.instructions):
                    entry_points.add(i + 1)
            elif instr['op'] == 'if':
                # 条件跳转指令的目标是入口点
                target_label = instr['result']
                # 找到目标标签对应的指令索引
                for j, instr_j in enumerate(self.instructions):
                    if instr_j['op'] == 'label' and instr_j['label'] == target_label:
                        entry_points.add(j)
                        break
                # 条件跳转指令之后的语句是入口点
                if i + 1 < len(self.instructions):
                    entry_points.add(i + 1)
            elif instr['op'] == 'return':
                # return语句之后的语句是入口点
                if i + 1 < len(self.instructions):
                    entry_points.add(i + 1)
        
        # 第二步：构建基本块
        entry_points = sorted(entry_points)
        
        for i in range(len(entry_points)):
            start = entry_points[i]
            if i == len(entry_points) - 1:
                end = len(self.instructions) - 1
            else:
                end = entry_points[i + 1] - 1
            
            # 提取基本块的指令
            block_instructions = self.instructions[start:end + 1]
            if block_instructions:
                block = BasicBlock(f'B{i}', start, end, block_instructions)
                self.basic_blocks.append(block)
        
        # 设置入口块
        if self.basic_blocks:
            self.entry_block = self.basic_blocks[0]
        
        # 设置出口块
        for block in self.basic_blocks:
            last_instr = block.instructions[-1]
            if last_instr['op'] == 'return':
                self.exit_blocks.append(block)
    
    def _build_edges(self):
        """构建边"""
        # 为每个基本块创建标签到基本块的映射
        label_to_block = {}
        for block in self.basic_blocks:
            # 检查基本块的第一条指令是否是标签
            if block.instructions[0]['op'] == 'label':
                label_to_block[block.instructions[0]['label']] = block
        
        # 构建边
        for block in self.basic_blocks:
            # 获取基本块的最后一条指令
            last_instr = block.instructions[-1]
            
            if last_instr['op'] == 'goto':
                # 无条件跳转
                target_label = last_instr['arg1']
                if target_label in label_to_block:
                    target_block = label_to_block[target_label]
                    block.successors.append(target_block.id)
                    target_block.predecessors.append(block.id)
            elif last_instr['op'] == 'if':
                # 条件跳转
                target_label = last_instr['result']
                if target_label in label_to_block:
                    target_block = label_to_block[target_label]
                    block.successors.append(target_block.id)
                    target_block.predecessors.append(block.id)
                # 同时跳转到下一个基本块（如果有）
                block_index = self.basic_blocks.index(block)
                if block_index + 1 < len(self.basic_blocks):
                    next_block = self.basic_blocks[block_index + 1]
                    block.successors.append(next_block.id)
                    next_block.predecessors.append(block.id)
            elif last_instr['op'] == 'return':
                # return语句，没有后继
                pass
            else:
                # 顺序执行，跳转到下一个基本块（如果有）
                block_index = self.basic_blocks.index(block)
                if block_index + 1 < len(self.basic_blocks):
                    next_block = self.basic_blocks[block_index + 1]
                    block.successors.append(next_block.id)
                    next_block.predecessors.append(block.id)
    
    def _build(self):
        """构建CFG"""
        self._identify_basic_blocks()
        self._build_edges()
    
    def visualize(self):
        """可视化CFG"""
        print("=== Control Flow Graph ===")
        for block in self.basic_blocks:
            print(f"{block.id}:")
            print(f"  Instructions: {block.start}-{block.end}")
            print(f"  Successors: {block.successors}")
            print(f"  Predecessors: {block.predecessors}")
        print("=======================")
        
        # 打印ASCII图
        print("\n=== CFG ASCII Diagram ===")
        for block in self.basic_blocks:
            for succ_id in block.successors:
                print(f"{block.id} → {succ_id}")
        print("=======================")
    
    def get_block(self, block_id):
        """根据ID获取基本块"""
        for block in self.basic_blocks:
            if block.id == block_id:
                return block
        return None
    
    def get_blocks(self):
        """获取所有基本块"""
        return self.basic_blocks
    
    def get_entry_block(self):
        """获取入口块"""
        return self.entry_block
    
    def get_exit_blocks(self):
        """获取出口块"""
        return self.exit_blocks

CFG的测试

下面是一个简单的测试代码，用于测试CFG的构建功能：

# 测试CFG构建
if __name__ == "__main__":
    # 三地址码指令示例
    instructions = [
        {'op': '=', 'arg1': '5', 'arg2': None, 'result': 't0'},
        {'op': '=', 'arg1': 't0', 'arg2': None, 'result': 'x'},
        {'op': '=', 'arg1': '3', 'arg2': None, 'result': 't1'},
        {'op': '=', 'arg1': 't1', 'arg2': None, 'result': 'y'},
        {'op': '>', 'arg1': 'x', 'arg2': 'y', 'result': 't2'},
        {'op': 'if', 'arg1': 't2', 'arg2': '!=', 'arg3': '0', 'result': 'L3'},
        {'op': 'goto', 'arg1': 'L4', 'arg2': None, 'result': None},
        {'op': 'label', 'label': 'L3'},
        {'op': '+', 'arg1': 'x', 'arg2': 'y', 'result': 't3'},
        {'op': '=', 'arg1': 't3', 'arg2': None, 'result': 'z'},
        {'op': 'goto', 'arg1': 'L5', 'arg2': None, 'result': None},
        {'op': 'label', 'label': 'L4'},
        {'op': '-', 'arg1': 'x', 'arg2': 'y', 'result': 't4'},
        {'op': '=', 'arg1': 't4', 'arg2': None, 'result': 'z'},
        {'op': 'label', 'label': 'L5'},
        {'op': 'return', 'arg1': 'z', 'arg2': None, 'result': None}
    ]
    
    # 构建CFG
    cfg = CFG(instructions)
    
    # 可视化CFG
    cfg.visualize()
    
    # 打印基本块信息
    print("\n=== Basic Blocks Information ===")
    for block in cfg.get_blocks():
        print(f"Block {block.id}:")
        print(f"  Start: {block.start}")
        print(f"  End: {block.end}")
        print(f"  Instructions:")
        for instr in block.instructions:
            if instr['op'] == 'label':
                print(f"    {instr['label']}:")
            else:
                if instr['arg2'] is None:
                    print(f"    {instr['result']} = {instr['op']} {instr['arg1']}")
                else:
                    print(f"    {instr['result']} = {instr['arg1']} {instr['op']} {instr['arg2']}")
        print()

CFG的优化

基本块合并：合并相邻的基本块，减少CFG的大小
无用基本块消除：消除不可达的基本块
CFG简化：移除冗余的边和节点
循环识别：识别程序中的循环结构

常见问题及解决方案

基本块识别错误：
- 解决方案：仔细检查入口点识别规则，确保所有入口点都被正确识别
边构建错误：
- 解决方案：确保正确处理所有类型的跳转指令，包括无条件跳转和条件跳转
CFG过于复杂：
- 解决方案：使用CFG优化技术，如基本块合并、无用基本块消除等
循环识别困难：
- 解决方案：使用专门的循环识别算法，如Dominator Tree-based方法
可视化效果差：
- 解决方案：使用更高级的可视化工具，如Graphviz

总结

控制流图（CFG）是编译器中一种重要的程序表示形式，它为数据流分析、代码优化和程序分析提供了基础结构。通过本集的学习，我们了解了如何从三地址码构建CFG，包括基本块识别、边的构建、CFG可视化等核心功能。

在本集的实战中，我们实现了一个基本的CFG构建器，它可以从三地址码识别基本块并构建控制流图。这个构建器可以处理简单的程序结构，但在实际编译器中，CFG构建器会更加复杂，需要处理更多的语言特性和优化策略。

通过本集的学习，我们为后续的数据流分析和代码优化奠定了基础。在后续的实战中，我们将继续深入学习编译器的中间代码生成和优化技术。