第13章：静态分析基础

静态分析是程序行为分析的重要支柱，它在不执行程序的情况下推理程序的可能行为。与前面章节介绍的动态profiling技术相比，静态分析提供了一种互补的视角：动态分析告诉我们程序实际做了什么，而静态分析告诉我们程序可能做什么。本章将介绍静态分析的基础概念和核心数据结构，包括控制流图、支配关系、SSA形式等，这些是理解后续高级静态分析技术的基石。

静态分析的本质与挑战

静态分析的核心任务是在编译时推理程序的运行时行为。这种"预测"面临着根本性的理论限制：莱斯定理告诉我们，任何关于程序行为的非平凡性质都是不可判定的。因此，实用的静态分析必须在精确性、可靠性和可扩展性之间寻求平衡。

精确性与可靠性的权衡：

过近似（Over-approximation）：保守分析，确保包含所有可能行为，可能产生误报（false positive）
欠近似（Under-approximation）：乐观分析，只报告确定的行为，可能产生漏报（false negative）
实用策略：大多数编译优化使用过近似确保正确性，而bug查找工具可能使用欠近似减少误报

分析的可扩展性挑战：

状态空间爆炸：程序路径数量随分支呈指数增长
过程间分析：函数调用创造了上下文敏感性需求
内存建模：指针和动态内存使分析复杂化
并发程序：线程交错产生组合爆炸

静态分析的分类维度

理解静态分析技术需要从多个维度进行分类：

流敏感性（Flow Sensitivity）：

流敏感分析：考虑语句执行顺序，为每个程序点维护不同的分析状态
流不敏感分析：忽略语句顺序，整个程序使用单一分析状态
路径敏感分析：区分不同执行路径，最精确但开销最大

上下文敏感性（Context Sensitivity）：

上下文敏感：区分不同调用点的函数调用
上下文不敏感：合并所有调用点的信息
k-CFA：维护k层调用栈信息的有限上下文敏感

堆抽象策略：

基于分配点：相同分配点的对象合并为一个抽象对象
基于类型：相同类型的对象共享抽象
基于形状：使用形状图表示堆结构

分析范围：

过程内分析（Intraprocedural）：单个函数内部
过程间分析（Interprocedural）：跨函数边界
全程序分析（Whole-program）：考虑整个程序

静态分析基础设施

现代编译器中的静态分析建立在一系列基础设施之上：

中间表示（IR）选择：

三地址码：简单，便于分析，常用于优化
控制流图：显式表示控制流，本章重点
SSA形式：简化数据流分析，现代编译器标配
抽象语法树：保留源码结构，适合源码级分析

符号信息管理：

符号表：变量、函数、类型信息的中心存储
类型系统：类型信息指导分析精度
调试信息：源码位置映射，错误报告需要

分析框架组件：

工作列表算法：管理分析的迭代过程
传递函数：描述程序语句的语义效果
汇合操作：合并不同路径的分析信息
加宽操作：确保分析终止的抽象技术

控制流图构建

控制流图（Control Flow Graph, CFG）是静态分析的基础数据结构，它将程序表示为一个有向图，其中节点代表基本块，边代表控制流转移。CFG提供了程序结构的抽象视图，隐藏了不影响控制流的细节，使得分析算法可以高效地推理程序行为。

CFG的形式化定义

控制流图G = (N, E, entry, exit)是一个有向图，其中：

N：基本块节点集合
E ⊆ N × N：控制流边集合
entry ∈ N：唯一入口节点
exit ∈ N：唯一出口节点（可能是虚拟的）

CFG的性质：

可达性：从entry可达所有节点（除了死代码）
终止性：所有节点都可达exit（除了无限循环）
确定性：每个节点的后继由其最后一条指令决定

基本块识别

基本块是最大的顺序执行指令序列，具有以下特性：

只有一个入口点（第一条指令）
只有一个出口点（最后一条指令）
内部没有分支或跳转目标

基本块识别算法通过扫描指令序列，识别以下位置作为基本块边界：

程序入口点
分支指令的目标地址
紧跟在分支指令后的地址

领导者（Leader）识别：基本块的第一条指令称为领导者。识别算法的核心是找出所有领导者：

第一条指令是领导者
任何条件或无条件跳转的目标指令是领导者
紧跟在条件跳转后的指令是领导者

基本块构建过程：

扫描所有指令，标记领导者
对每个领导者，其基本块包含从该领导者到下一个领导者之前（或程序结束）的所有指令
建立基本块之间的前驱后继关系

特殊情况处理：

空基本块：某些控制流结构可能产生空基本块，通常可以优化掉
单指令基本块：只包含一条跳转指令的基本块
Fall-through块：没有显式跳转，自然流向下一个基本块

基本块的内部结构

虽然基本块内部是顺序执行的，但仍需要仔细设计其表示：

指令链表示：

双向链表：支持高效的插入、删除和遍历
指令索引：快速定位特定指令
定义-使用信息：每条指令维护其定义和使用的变量集合

基本块属性：

活跃信息：入口和出口的活跃变量集
支配信息：支配者和被支配者集合
循环信息：所属循环和嵌套深度
频率信息：执行频率估计（用于优化）

基本块优化：

死代码消除：删除无用指令
局部CSE：消除块内公共子表达式
指令调度：重排指令提高性能
窥孔优化：局部模式匹配和替换

控制流边类型

CFG中的边表示不同类型的控制流转移，每种边类型都有其特定的语义和分析含义：

顺序流（Fall-through）：基本块按照程序顺序执行到下一个基本块。

特征：隐式控制流，无需显式跳转指令
优化机会：可以合并相邻基本块
布局影响：代码布局时优先保持fall-through减少跳转

条件分支（Conditional Branch）：根据条件选择不同的执行路径，通常产生两条出边。

分支预测：使用profile信息标注分支概率
分支简化：常量条件可以转换为无条件跳转
关键边：从多后继节点到多前驱节点的边需要特殊处理

无条件跳转（Unconditional Jump）：直接跳转到目标基本块。

跳转优化：跳转到跳转可以简化
死代码识别：跳转后的代码可能不可达
尾调用优化：特殊形式的无条件跳转

函数调用（Function Call）：调用其他函数，涉及interprocedural分析时需要特殊处理。

调用图构建：需要解析可能的调用目标
参数传递：建模参数和返回值的数据流
异常传播：被调函数可能抛出异常

异常边（Exception Edge）：表示可能的异常抛出路径。

隐式异常：除零、空指针等运行时异常
显式异常：throw语句产生的异常
精度权衡：精确异常分析代价高昂

间接跳转（Indirect Jump）：跳转目标在运行时确定。

跳转表：switch语句的常见实现
函数指针：需要指针分析确定目标
虚函数调用：需要类型分析确定目标集

返回边（Return Edge）：函数返回到调用点。

多返回点：一个函数可能有多个return语句
异常返回：通过异常机制返回
尾调用：优化后可能没有显式返回

CFG表示方法

CFG可以使用多种数据结构表示：

邻接表：每个基本块维护其后继列表，空间效率高，适合稀疏图。

优点：空间复杂度O(V+E)，添加边操作高效
缺点：判断两节点是否相邻需要O(degree)时间
适用场景：大多数实际程序的CFG是稀疏的

邻接矩阵：使用二维数组表示边关系，访问效率高但空间开销大。

优点：O(1)时间判断连接关系，矩阵运算友好
缺点：空间复杂度O(V²)，不适合大型程序
适用场景：小型函数的密集控制流图

边列表：显式存储所有边，便于遍历所有控制流转移。

优点：遍历所有边最高效，便于边属性存储
缺点：查找特定节点的邻居效率低
适用场景：需要频繁遍历所有边的算法

混合表示：实际编译器often使用混合方案：

基本块对象包含前驱和后继指针列表
边对象存储额外属性（如分支概率）
全局边列表用于特定遍历需求

特殊控制流处理

现代编程语言包含多种复杂控制流结构，每种都需要特殊的CFG建模策略：

Switch语句：可能产生多个分支，需要创建到每个case标签的边。

密集switch：使用跳转表实现，所有case共享一个间接跳转
跳转表索引计算：table[expr - min_case]
边界检查：确保索引在有效范围内
CFG建模：从switch节点到每个case的直接边
稀疏switch：编译为if-else链，每个比较产生一个分支
二分查找优化：对case值排序减少比较次数
决策树生成：平衡比较次数和代码大小
CFG复杂度：O(log n)层的二叉树结构
分析策略：保守假设所有case都可达，或使用值范围分析优化
常量传播：确定switch表达式值时简化CFG
不可达case消除：基于类型或范围分析
Default处理：确保完整的case覆盖

异常处理：try-catch块需要添加从可能抛出异常的指令到catch块的边。

显式异常：throw语句产生确定的异常边
异常对象创建点
栈展开路径
Catch匹配顺序
隐式异常：数组访问、空指针解引用等可能抛出异常
异常点识别：哪些操作可能失败
精度选择：全部建模vs仅关键异常
路径爆炸控制：合并相似异常路径
异常传播：需要考虑异常在调用链中的传播路径
函数异常规范：noexcept/throws声明
跨函数边界：调用点的异常处理
异常类型层次：catch的多态匹配
Finally块：无论是否异常都执行，需要特殊的CFG建模
多入口：正常路径和异常路径
多出口：继续传播异常或正常返回
嵌套finally：正确的执行顺序

函数指针：间接调用需要进行指针分析确定可能的目标。

类型分析：基于函数签名缩小可能目标集合
函数类型兼容性检查
参数和返回值匹配
调用约定一致性
流敏感分析：追踪函数指针的赋值来源
定义-使用链跟踪
路径敏感的指针值
上下文敏感的分析
保守处理：无法确定时假设可调用任何类型兼容的函数
函数逃逸分析
外部函数处理
动态加载考虑

虚函数调用：需要类层次分析确定可能的调用目标。

CHA（Class Hierarchy Analysis）：基于类继承关系的快速分析
构建完整类层次图
查找所有可能的重写
保守但快速
RTA（Rapid Type Analysis）：只考虑实际创建的类型
收集所有new/malloc点
过滤未实例化的类
更精确的调用目标
流敏感分析：精确追踪对象类型信息
对象创建点追踪
类型测试和转换
虚表指针分析

协程和生成器：

Yield点：既是退出点也是重入点
保存点：局部变量和执行位置
恢复点：从yield后继续
CFG分割：yield将函数分成多段
状态机转换：协程可建模为状态机，每个yield对应一个状态
状态变量：记录当前执行位置
状态转换：switch-case实现跳转
局部变量持久化：跨yield保持值
多入口函数：resume操作需要特殊的CFG入口处理
入口分发：根据状态跳转到正确位置
参数传递：yield值和resume参数
终止处理：生成器耗尽的边

循环结构的特殊形式：

Do-while循环：至少执行一次的语义
循环体在条件检查前
回边从条件检查到循环头
For-each循环：迭代器模式的语法糖
迭代器初始化
hasNext/next调用序列
隐式异常处理
无限循环：显式的无出口循环
可达性分析特例
优化机会：循环不变量外提
终止分析：证明循环终止

支配关系与循环识别

支配关系是理解程序结构的关键概念，对于优化和程序理解都至关重要。支配关系揭示了程序中的必经路径，这些信息对于代码移动、冗余消除和并行化等优化至关重要。

支配关系定义

在CFG中，如果从入口节点到节点n的每条路径都必须经过节点d，则称d支配n（d dominates n）。支配关系具有以下性质：

自反性：每个节点支配自己
传递性：如果a支配b，b支配c，则a支配c
反对称性：如果a支配b且b支配a，则a=b

严格支配（Strict Dominance）：如果d支配n且d≠n，则d严格支配n。这个概念在构建支配树时很重要。

支配者集合：节点n的支配者集合dom(n)包含所有支配n的节点。计算公式：

dom(entry) = {entry}
dom(n) = {n} ∪ (∩{dom(p) | p是n的前驱})

支配关系的应用：

不变代码外提：循环不变量必须在循环的支配节点定义
SSA构建：φ函数放置位置由支配边界决定
死代码消除：如果定义点不支配任何使用点，则可能是死代码

支配关系的高效计算

计算支配关系的朴素算法是迭代求解数据流方程，但这可能需要O(n³)时间。现代编译器使用更高效的算法：

Cooper-Harvey-Kennedy算法：

简单直观的实现
实践中接近线性时间
适合教学和小规模程序

支配关系的增量维护：当CFG发生变化时，增量更新支配关系比完全重算更高效：

边添加：可能减少某些节点的支配者
边删除：可能增加某些节点的支配者
节点添加/删除：局部重算受影响区域

立即支配者

节点n的立即支配者（immediate dominator）是除n外支配n的所有节点中最接近n的节点。立即支配关系构成一棵树，称为支配树。

支配树性质：

每个节点（除入口外）有唯一的立即支配者
支配树的祖先-后代关系对应CFG中的支配关系
支配树的深度影响许多算法的效率

支配树的构建通常使用Lengauer-Tarjan算法，其时间复杂度接近线性。算法核心思想是：

对CFG进行深度优先遍历，建立DFS树
使用半支配者（semi-dominator）概念简化计算
通过路径压缩优化查找效率

Lengauer-Tarjan算法详解：

半支配者定义：sdom(w) = min{v | 存在路径v=v0→v1→...→vk=w，其中对于1≤i≤k-1，DFS序号(vi)>DFS序号(w)}
计算过程： 1. DFS编号：对CFG进行DFS，为每个节点分配序号 2. 半支配者计算：按DFS逆序处理节点 3. 隐式评估：使用路径压缩加速祖先查询 4. 显式计算：从半支配者推导立即支配者

支配边界（Dominance Frontier）：节点n的支配边界DF(n)是所有这样的节点y：n支配y的某个前驱但不严格支配y。形式化定义： DF(n) = {y | ∃p∈pred(y), n支配p且n不严格支配y}

支配边界的计算对SSA构建至关重要，φ函数需要放置在变量定义点的支配边界上。

自然循环识别

循环是程序中的重要结构，识别循环对于优化至关重要。自然循环的定义基于支配关系：

回边（Back Edge）：从节点n到节点h的边，其中h支配n。

自然循环：由回边n→h定义的循环包含h（循环头）以及所有能够到达n而不经过h的节点。

循环识别算法：

计算支配关系
识别所有回边
对每个回边，计算其对应的自然循环

循环嵌套分析

程序中的循环经常嵌套出现，理解嵌套关系对于循环优化很重要：

循环嵌套深度：节点所属的最内层循环的嵌套层次。

深度0：不在任何循环中
深度k：在k层嵌套循环中
用于指导寄存器分配和指令调度优先级

循环森林：将所有循环组织成森林结构，父子关系表示嵌套关系。

根节点：最外层循环
叶节点：最内层循环
兄弟关系：同层次的独立循环

循环属性分析：

循环不变量：在循环执行过程中值不变的表达式
归纳变量：每次迭代以固定步长变化的变量
循环界限：循环执行次数的上下界估计

不可归约循环：某些由goto语句产生的循环结构不满足自然循环定义，需要特殊处理。

特征：多个入口节点，没有唯一的循环头
检测：强连通分量中没有节点支配所有其他节点
处理方法：
节点分裂：复制多入口节点
T1-T2变换：系统化的图变换方法
直接分析：某些算法可以处理不可归约图

循环优化机会识别：

完美嵌套：内层循环体只包含循环语句
循环融合候选：相邻且迭代空间相同的循环
循环分裂点：具有不同数据访问模式的语句组

SSA形式与use-def链

静态单赋值（Static Single Assignment, SSA）形式是现代编译器广泛使用的中间表示，它简化了许多分析和优化。

SSA的核心特性

在SSA形式中，每个变量只被赋值一次。这带来以下优势：

use-def关系变得显式且唯一
简化了数据流分析
便于实现各种优化

SSA对优化的影响：

常量传播：直接替换使用点，无需考虑中间重定义
死代码消除：没有使用者的定义可直接删除
值编号：相同计算的识别变得简单
代码移动：依赖关系明确，便于安全地移动指令

SSA的变体：

剪枝的SSA：只在真正需要的地方插入φ函数
静态单信息（SSI）：每个使用点也只有一个版本
门控SSA：添加路径条件信息

φ函数的作用

当控制流汇合时，需要φ函数来选择正确的变量版本。φ函数是一个虚拟操作，根据控制流的来源选择相应的值。

例如，在if-then-else结构后：

x3 = φ(x1, x2)

表示如果从then分支来，x3取x1的值；如果从else分支来，x3取x2的值。

φ函数的语义：

参数顺序：φ函数参数与CFG前驱一一对应
执行时机：概念上在基本块开始处同时执行
活跃性：只有实际执行的路径对应的参数才被选择

φ函数的优化：

冗余φ消除：所有参数相同的φ可以删除
死φ消除：结果未被使用的φ可以删除
φ合并：连续的φ操作可能被合并

φ函数的实现：

在代码生成阶段需要消除φ函数
通常通过插入拷贝指令实现
需要处理φ函数之间的依赖关系

SSA构建算法

SSA构建分为两个主要步骤：

φ函数插入：使用支配边界（dominance frontier）确定需要插入φ函数的位置。

迭代支配边界算法：

对每个定义变量v的节点n： - 将n加入工作列表W - 记录n为v的定义节点
当W非空时： - 取出节点n - 对DF(n)中的每个节点y：
- 如果y未为v插入过φ函数：
- 在y插入v的φ函数
- 如果y不是v的原始定义点，将y加入W

变量重命名：对每个变量的定义和使用进行重命名，确保每个定义都有唯一的名字。

重命名算法：

初始化： - 为每个变量维护一个版本栈 - 为每个变量维护一个计数器
DFS遍历支配树： - 进入节点时：
- 处理φ函数：创建新版本并压栈
- 处理普通赋值：创建新版本并压栈
- 处理变量使用：使用栈顶版本
- 离开节点时：
- 弹出该节点压入的所有版本

剪枝优化：

活跃变量分析：只为汇合点活跃的变量插入φ
半剪枝：结合活跃信息和支配边界
最小φ插入：只在真正需要的位置插入

use-def链构建

在SSA形式下，use-def链的构建变得简单：

每个使用点直接指向唯一的定义
def-use链通过遍历所有使用点构建
支持高效的死代码消除和常量传播

数据结构设计：

Use节点：记录使用位置和指向定义的指针
Def节点：记录定义位置和使用者列表
双向链接：便于快速查询和更新

SSA下的传统分析：

可达定义：在SSA中退化为use-def链
活跃变量：直接遍历def-use链
可用表达式：基于值编号的高效实现

SSA的退出：

关键边分裂：在前驱块末尾插入拷贝
并行拷贝序列化：处理φ函数间的循环依赖
合并干扰：减少额外的拷贝操作

基本块与程序点

程序点是静态分析中的基本概念，表示程序执行过程中的特定位置。

程序点粒度

程序点可以有不同的粒度级别：

指令级：每条指令前后都是程序点，提供最精确的分析。

优点：精度最高，可以捕捉细微的状态变化
缺点：分析复杂度高，状态空间巨大
适用：安全关键代码、精确错误定位

基本块级：只在基本块边界设置程序点，降低分析复杂度。

优点：平衡精度和效率，广泛使用
缺点：无法捕捉块内中间状态
适用：大多数数据流分析问题

过程级：在函数调用边界设置程序点，用于过程间分析。

优点：可扩展性好，适合大型程序
缺点：精度损失严重
适用：模块化分析、接口检查

混合粒度：

热点代码使用细粒度
冷代码使用粗粒度
动态调整分析精度

基本块内分析

基本块内部的分析相对简单，因为执行是顺序的：

可以使用简单的符号执行
传递函数通常是多个指令效果的组合
不需要考虑控制流合并

传递函数组合：对于基本块B = [s1, s2, ..., sn]，其传递函数： F_B = F_sn ∘ F_{sn-1} ∘ ... ∘ F_s2 ∘ F_s1

块内优化机会：

窗口优化：局部观察相邻指令
代数简化：利用代数恒等式
强度削减：替换昂贵操作
指令选择：选择最优指令序列

特殊指令处理：

内存操作：考虑别名关系
函数调用：处理副作用
浮点运算：考虑精度和舍入

程序点标记

为了高效索引和引用，程序点需要系统的标记方案：

使用基本块ID和块内偏移的组合
为特殊位置（如函数入口/出口）预留特殊ID
支持快速的前驱/后继查询

标记方案设计：

分层标记： - 高位：基本块ID - 低位：块内偏移 - 特殊位：ENTRY=0, EXIT=MAX
索引结构： - 基本块到程序点范围的映射 - 程序点到指令的映射 - 前驱/后继关系缓存
压缩表示： - 对于稀疏程序点使用压缩表示 - 区间编码优化存储 - 位向量表示程序点集合

块间信息传递

分析信息在基本块间的传递遵循数据流方程：

OUT[B] = gen[B] ∪ (IN[B] - kill[B])
IN[B] = ∪(OUT[P]) for all predecessors P

传递函数需要正确处理：

φ函数的语义
异常边的特殊情况
函数调用的影响

数据流方程分类：

前向分析： - 信息沿控制流方向传播 - 例子：可达定义、可用表达式 - 方程：IN[B] = ∪{OUT[P] | P ∈ pred(B)}
后向分析： - 信息逆控制流方向传播 - 例子：活跃变量、很忙表达式 - 方程：OUT[B] = ∪{IN[S] | S ∈ succ(B)}
双向分析： - 结合前向和后向信息 - 例子：部分冗余消除

汇合操作的选择：

并集(∪)：Must分析，保守假设
交集(∩)：May分析，乐观假设
自定义：基于格理论的一般化

特殊情况处理：

异常边： - 可能不执行完整基本块 - 需要特殊的kill/gen集合
函数调用： - 保守假设：杀死所有可能修改的值 - 过程间分析：使用摘要信息
循环入口： - 迭代求解不动点 - 加速收敛技术

本章小结

本章介绍了静态分析的基础概念和核心数据结构：

控制流图（CFG）：程序的图表示，包含基本块识别、边类型分类、特殊控制流处理等关键技术。CFG是几乎所有静态分析的基础。
支配关系：描述了CFG中节点间的必经关系，支配树的构建使用Lengauer-Tarjan算法实现近线性时间复杂度。支配边界概念是SSA构建的关键。
循环识别：基于回边和支配关系识别自然循环，循环嵌套分析帮助理解程序结构，为循环优化提供基础。
SSA形式：每个变量只赋值一次的程序表示，通过φ函数处理控制流汇合，简化了use-def链的构建和许多优化算法。
程序点：分析的基本单位，可以有不同粒度。基本块内分析相对简单，块间传递需要处理数据流方程。

这些概念相互关联：CFG提供程序结构，支配关系帮助理解控制依赖，SSA简化数据依赖分析，程序点定义分析精度。掌握这些基础对于理解后续的数据流分析、abstract interpretation等高级技术至关重要。

练习题

基础题

练习 13.1：基本块识别 给定以下伪代码，识别所有基本块并画出CFG：

1:  x = 10
2:  if x > 5:
3:    y = x * 2
4:    if y > 15:
5:      z = y - 10
6:    else:
7:      z = y + 10
8:  else:
9:    z = x
10: print(z)

Hint：先找出所有分支指令和跳转目标，然后确定基本块边界。

参考答案

基本块划分：

B1: 行1-2（到if判断）
B2: 行3-4（then分支开始到内层if）
B3: 行5（内层then分支）
B4: 行7（内层else分支）
B5: 行9（外层else分支）
B6: 行10（最终汇合点）

控制流边：

B1 → B2（条件true）
B1 → B5（条件false）
B2 → B3（内层条件true）
B2 → B4（内层条件false）
B3 → B6
B4 → B6
B5 → B6

练习 13.2：支配关系计算 对于练习13.1中的CFG，计算： a) 每个节点的支配者集合 b) 每个节点的立即支配者 c) 画出支配树

Hint：从入口节点开始，考虑到达每个节点的所有路径。

参考答案

a) 支配者集合：

dom(B1) = {B1}
dom(B2) = {B1, B2}
dom(B3) = {B1, B2, B3}
dom(B4) = {B1, B2, B4}
dom(B5) = {B1, B5}
dom(B6) = {B1, B6}

b) 立即支配者：

idom(B2) = B1
idom(B3) = B2
idom(B4) = B2
idom(B5) = B1
idom(B6) = B1

c) 支配树：

    B1
   /|\\
  B2 B5 B6
 / \
B3  B4

练习 13.3：SSA形式转换 将以下代码片段转换为SSA形式：

x = 5
y = x + 1
if condition:
    x = y * 2
    y = 10
else:
    y = x - 1
z = x + y

Hint：首先识别需要φ函数的位置，然后进行变量重命名。

参考答案

SSA形式：

x1 = 5
y1 = x1 + 1
if condition:
    x2 = y1 * 2
    y2 = 10
else:
    y3 = x1 - 1
x3 = φ(x2, x1)  // 从if分支来取x2，从else分支来取x1
y4 = φ(y2, y3)  // 从if分支来取y2，从else分支来取y3
z1 = x3 + y4

注意x在else分支中没有被重新定义，所以φ函数选择x1。

挑战题

练习 13.4：循环识别算法 设计一个算法，给定CFG和支配关系，识别所有自然循环。你的算法应该： a) 找出所有回边 b) 对每个回边计算对应的循环体 c) 处理嵌套循环

Hint：回边是从被支配者到支配者的边。循环体包含所有能到达回边源而不经过循环头的节点。

参考答案

算法步骤：

识别回边：对每条边(n→h)，如果h支配n，则是回边
对每个回边(n→h)计算循环： - 初始化循环体L = {h, n} - 工作列表W = {n} - while W不空:
- 取出节点m
- 对m的每个前驱p:
- 如果p不在L中，加入L和W
循环嵌套：如果循环L1的头支配循环L2的头，且L2⊆L1，则L2嵌套在L1中

时间复杂度：O(E×N)，其中E是边数，N是节点数。

练习 13.5：SSA破坏性更新处理 考虑数组和对象字段的SSA表示。如何处理以下情况：

a[i] = 10
x = a[j]
a[k] = 20
y = a[j]

其中i, j, k的关系在编译时未知。

Hint：考虑使用特殊的函数来建模数组更新和访问。

参考答案

使用以下方案处理数组SSA：

引入两个特殊函数： - update(array, index, value)：返回更新后的数组 - access(array, index)：返回数组元素
转换后的SSA形式：

a1 = update(a0, i, 10)
x1 = access(a1, j)
a2 = update(a1, k, 20)
y1 = access(a2, j)

别名分析： - 如果能证明i≠j且k≠j，则x1=10，y1=10 - 如果能证明k=j，则y1=20 - 否则需要保守假设y1可能是10或20
优化机会： - 冗余数组访问消除 - 数组拷贝传播 - 基于别名分析的常量传播

练习 13.6：不可归约CFG处理 某些CFG包含不可归约的控制流（例如由goto产生）。设计一种方法将不可归约CFG转换为可归约形式。

Hint：考虑节点分裂或添加预处理节点。

参考答案

处理不可归约CFG的方法：

检测不可归约性： - 构建支配树 - 检查是否存在交叉边（既不是树边也不是回边的边）
节点分裂法： - 识别多入口强连通分量 - 对多入口节点进行分裂，为每个入口创建副本 - 更新边关系，使每个副本只有一个入口
DJ图方法： - 构建DJ图（Dominator-Join图） - 使用DJ图指导节点分裂，最小化分裂次数
实际考虑： - 节点分裂会增加代码大小 - 可能影响某些优化的效果 - 某些分析可以直接处理不可归约CFG
示例转换：原始不可归约循环可能因为有多个入口，分裂后每个入口对应一个循环副本，形成可归约结构。

练习 13.7：增量式SSA维护 当CFG发生局部修改（如添加/删除基本块）时，如何高效地更新SSA形式而不完全重建？

Hint：考虑受影响的支配边界和φ函数位置。

参考答案

增量SSA更新策略：

CFG修改类型： - 边添加/删除 - 基本块添加/删除 - 基本块内指令修改
支配关系更新： - 使用增量支配树算法 - 只重新计算受影响的节点 - 维护支配边界的增量更新
φ函数调整： - 边添加：可能需要添加新的φ函数操作数 - 边删除：移除对应的φ函数操作数 - 新汇合点：插入必要的φ函数
变量重命名： - 维护定义栈的快照 - 从修改点开始局部重命名 - 使用时间戳避免全局遍历
优化机会： - 缓存支配边界计算 - 延迟φ函数清理 - 批量处理多个修改
正确性保证： - 验证use-def链完整性 - 确保φ函数参数与前驱匹配 - 检查支配性质保持

常见陷阱与错误

CFG构建陷阱

异常边遗漏：忘记为可能抛出异常的指令添加到异常处理器的边，导致CFG不完整。

间接跳转处理：函数指针、虚函数调用、switch语句的跳转表可能有多个目标，需要保守处理或进行额外分析。

库函数假设：错误假设标准库函数不会抛出异常或修改全局状态。

支配关系错误

入口节点遗漏：某些分析可能有多个入口（如异常处理器），需要添加虚拟入口节点。

不可达代码：不可达代码没有支配者，需要特殊处理或预先删除。

增量更新错误：CFG修改后没有正确更新支配关系，导致后续分析错误。

SSA构建问题

φ函数过度插入：在不必要的位置插入φ函数，增加程序复杂度。可以使用剪枝算法优化。

临界边处理：从有多个后继的节点到有多个前驱的节点的边（临界边）需要分裂以正确放置φ函数。

内存SSA错误：对内存操作的SSA建模不当，忽略了别名关系。

循环分析陷阱

不可归约循环：假设所有循环都是自然循环，遇到goto形成的复杂控制流时分析失败。

循环出口识别：多出口循环的处理，需要正确识别所有离开循环的边。

无限循环处理：某些循环可能没有出口，需要特殊标记。

最佳实践检查清单

CFG设计审查

[ ] CFG是否完整包含所有可能的控制流路径？
[ ] 异常边是否正确建模？
[ ] 函数调用和返回是否正确处理？
[ ] 是否有效处理了间接控制流？
[ ] 基本块划分是否最大化了块大小？

支配分析质量

[ ] 支配树构建算法是否使用了高效实现（如Lengauer-Tarjan）？
[ ] 支配边界计算是否正确且高效？
[ ] 是否缓存了支配信息以避免重复计算？
[ ] 增量更新策略是否正确维护了支配性质？

SSA形式规范

[ ] 每个变量是否确实只被赋值一次？
[ ] φ函数参数是否与CFG前驱一一对应？
[ ] 是否正确处理了未初始化变量？
[ ] SSA形式是否是最简的（剪枝的）？
[ ] 是否有从SSA形式退出的策略？

循环优化准备

[ ] 所有循环是否被正确识别和分类？
[ ] 循环嵌套关系是否正确？
[ ] 循环不变量是否被识别？
[ ] 循环边界和步长是否可分析？
[ ] 是否识别了循环携带依赖？

性能考虑

[ ] 数据结构选择是否适合程序规模？
[ ] 是否实现了必要的缓存机制？
[ ] 大型程序的可扩展性如何？
[ ] 是否有内存使用的上限控制？
[ ] 增量分析是否真正比完全重分析更高效？