0.    简介

静态代码分析是指在不实际执行程序的情况下，对代码语义和行为进行分析，由此找出程序中由于错误的编码导致异常的程序语义或未定义的行为。它能在软件开发流程早期就发现代码中的各种问题，从而提高开发效率和软件质量。

静态代码分析，从工具实现的角度，就是开发一款分析器，对程序源代码进行分析，识别程序中的各种类型的问题。为了识别这些问题，开发分析器就需要不同的实现方式（算法），这时候，为了让分析器在实现时更加简洁、高效，就需要对源代码进行处理，转换为一种针对特定的分析器算法和源码在语义上等价的，但是更加简洁、高效、实用的表示形式，也就是中间表示。

就像源码，里面包含各种注释等内容，很不方便分析，一般也不会基于源码来直接分析，都会转换为某种格式来分析。当然，我们介绍的都是当前静态代码分析（编译原理）里面最经典的一些中间表示。首先，会介绍一下AST，然后会介绍一下三地址码，随后介绍一下SSA形式的三地址码，最后介绍一下什么是CFG（包括BB块）和CG。

1.    AST和三地址码

在介绍AST和三地址码时，我们用一个简单的例子：x = 3 + 4 * y 这个表达式作为例子来进行介绍。

1.1 AST

抽象语法树（Abstract Syntax Tree，AST）是源代码的抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，之所以说是抽象的，是因为抽象语法树并不会表示出真实语法出现的每一个细节。

实际上，抽象语法树，其实就是用树状结构表示语法结构，也没有说必须是什么形式，只要能忠实地反映出源码的格式即可。在https://xie.infoq.cn/article/6f8ff63d6b88480c05f805d96中，第1.2节中，就介绍了Yaml、XML和Graphiz dot等几种格式，也有工具可以输出json格式的语法树结构，例如Coverity的CodeXM规则开发中，就支持先输出json格式的语法树给规则开发提供支持。

当然，一般资料中在进行介绍时，都是以操作符作为根节点，画个树状的结构来表示，这里咱们也简单画一个意思一下，如下图：

图1.1 AST示例

1.2    三地址码

三地址码是一种有意思的中间表示，当前也是编译原理中用得最火的。这里我给大家梳理一种我的理解上的概念，那就是，刨掉赋值操作，最多只有一个操作符，先看下面的几个例子：

• x = y bop z
• x = uop y
• x = y
• goto L

如上，第一个，除了赋值之外，只有 bop 一个操作符，第二个，只有 uop 一个操作符，第三个没有操作符，同时，操作符的概念可以进一步扩展到函数调用等，例如 call fun(a, b, c, d)，虽然有四个操作数，但是我们认为 call fun只是一个操作符。

如上面 x = 3 + 4 * y 转换为三地址码如下：

t1 = 4
t2 = y
t3 = t1 * t2
t4 = 3
t5 = t4 + t3
x = t5

当然，有些形式下会减少临时变量的使用，尽量复用原来的变量或者常量，形成的三地址码如下：

t1 = 4 * y
x = 3 + t1

三地址码最初只是处理类似于 x = y bop z 这种形式的语句，而提出来的“三个操作数”的意思，随着语法的扩充，也并不是完全就是“三地址”。

1.3 AST和三地址码对比

下面介绍几点AST和三地址码的对比特点：

• 源码相关性

AST中的节点与输入源代码中的各个语法元素一一对应，忠实地体现了源码的内容和语法特性，因此AST与源码强相关；三地址码就是从AST进一步抽象的一种中间表示，更接近机器语言，可以认为和语言无关，是连接前后端的一种中间表示。

• 变化频繁程度

因为AST需要忠实地体现出源代码的语法元素，因此在对应的编程语言升级时，对应的AST必然会跟着发生变化，比如Java，从Java7变成Java8，增加了大量的Lambda表达式、函数引用等特性，所以AST节点也需要增加这些语法节点，所以AST的版本需要随着语言发布而不断变化。

但是三地址码是一种经过处理的语言无关的中间表示，即使源代码结构变化，AST结构变化，但是转换后的三地址码是稳定的，不会经常发生变化，构造在三地址码上面的分析算法就相对比较稳定。

• 结构

AST体现源码的结构，需要匹配源码的语法，因此一般结构比较复杂，而三地址经过处理，一般比较紧凑，简单。例如，Java中，对 for，while，do while 有多种不同的循环方式，但是，其实内容大同小异，但是在AST层面，就是不一样的，但是转换为三地址码后，所表达的控制语义是完全一样的。

• 表达信息

AST表达了源码的信息，因此可以在AST上做程序结构的检查，但是三地址码中，可以更好地包含了程序控制流和数据流信息，能进行更深层次的流敏感分析，过程间分析，上下文敏感分析和对象敏感分析等等，从而实现各种更高难度的程序漏洞检查。

同时，三地址码因为是语言无关的， 所以在部分静态代码分析工具实现时，会对不同的三地址码，实现一个分析引擎，只是通过开发不同语言的规则，实现对不同语言的能力的覆盖，而AST是无法做到这一点的。因此，三地址码也被认为是静态代码分析的基础。

2.    SSA形式

2.1 SSA概念及分类

2.1.1 SSA概念

SSA（Static Single Assignment，静态单赋值），顾名思义，就是每个变量只有唯一的赋值。以下面的代码举例：

public void test(int x) {
    int y = 0;
    if (x > 3) {
        y = x + 4;
    } else {
        y = 10;
    }
    int z = y + 3;
    System.out.println(z);
}

以下图为例，左图是原始代码，里面有分支， y 变量在不同路径中有不同赋值，最后打印 z的值。右图是等价的 SSA 形式，y 变量在两个分支中被改写为 y2, y3，在控制流交汇处插入φ函数，合并了来自不同边的 y2, y3值, 赋给 y4 最后z由y4生成。

图2-1 原始代码与 SSA 形式及相应 CFG 控制流图

其实要讲SSA形式，就不能离开对DU Chain（Define-Use Chain）和UD Chain（Use-Define Chain）的介绍，因为很多地方对SSA的概念的介绍，都是从DU Chain和UD Chain引起的。Use-Define Chain 是一个数据结构，包含一个Define变量，以及它的全部Use的集合。相对的，Define-Use Chain 包含一个Use变量，以及它的全部 Define的集合。

另外一种SSA的描述，就是在 Define-Use Chain中，每一个Use变量，只会有一个Define，例如，在前面例子中，z = y + 3 中，因为此时 y可能在两个分支中赋值，因此，对于变量 z = y + 3 中，y 的Use来说，有两个 Define，但是，通过更改为 SSA形式，z = y + 3 中，y只有一个 Define，那就是 y4。因此，通过将三地址码转为SSA形式，可以很大程度上，简化Use-Define Chain和Define-Use Chain。

2.1.2 SSA分类

SSA 有几种不同分类（主要是最小SSA、剪枝SSA、半剪枝SSA，另外两种严格SSA和最大SSA，大部分资料上都没有看到，只是在少部分资料中有见到，所以简单提一下）：

• 最小 SSA

最小SSA有以下特点：同一原始名字的两个不同定义的路径汇合处都插入一个φ函数。这样得到符合两大特征的且拥有最少φ函数数量的 SSA 形式。但是这里的最小不包含优化效果，比如死代码消除。如上面图2.1节，就是一个最小SSA形式。

• 剪枝 SSA

如果变量在基本块的入口处不是活跃 (live) 的，就不必插入φ函数。一种方法是在插入 φ函数的时候计算活跃变量分析。另一种剪枝方式是在最小SSA上做死代码消除，删掉多余的φ函数。如下面的例子，y在分支执行完后，在最后的BB块中不再使用，y已经不再活跃，此时没必要在这个节点添加φ函数，如下面右图红色标出来的位置（说明：虽然不是剪枝SSA，但是仍然是最小SSA）。

图2.2 剪枝SSA和最小SSA说明

• 半剪枝 SSA

鉴于剪枝 SSA 的成本，可以稍微折衷一点。插入φ函数前先去掉非跨越基本块的变量名。这样既减少了名字空间也没有计算活跃变量集的开销。如下图所示，y变量除了Define，并没有Use，所以，变量y其实可以去掉，如下右图：

图2.3 半剪枝SSA形式

• 严格 SSA

如果一个 SSA中，每个Use被其Define支配（如果从程序入口到一个结点 A 的所有路径，都先经过结点B，则称A被B支配），那么称为严格 SSA（实际上，在强类型语言中，这种情况比较少，因为没有定义，就不允许使用，在少数动态类型语言中，允许没有定义就可以使用的才有这类问题）。

• 最大SSA

最大SSA是相对最小SSA而言的，就是在每个汇合点处为每个变量放置一个φ函数。很显然，这种方法会导致SSA的使用效率最差，用户体验也很差，我估计谁生成的SSA是这样的形式，会被使用的人打死的。

2.2 SSA形式和普通三地址码对比

其实对比SSA形式和普通的三地址码形式，只有一个区别，那就是，SSA形式，对于每个Use，只会有一个Define。两者在一定程度上，还是非常类似的。那么主要对比在于两种形式的各自的优缺点：

• SSA形式相对于三地址码，会引入大量的额外的临时变量，同时需要插入φ函数，还需要维护这些临时变量到原始变量的映射关系（当然，仁者见仁，智者见智，也有资料觉得这些额外的临时变量可以忽略，驳斥这个观点为谬论，不过的确还是有其不舒服的地方的）；
• SSA形式的优势在于，SSA形式简化了DU Chain和UD chain，构建了一种稀疏结构，可以简化数据流分析（一般基于三地址码，需要基于传统的数据流分析来进行分析，称为dense分析，基于SSA形式，可以构造值依赖关系，基于值流分析，也称为sparse分析，同时，SSA形式也隐含了一定的程序流信息）。
• SSA形式相比于普通三地址码，可以优化常量传播、值依赖分析、死代码、重复代码删除等；

3.    CFG、基本块

这里简单介绍基本块和CFG的概念，对于如何构造基本块和CFG，会在后面进行介绍（这里强调一点：我个人倾向于将CFG和基本块等概念，当做中间表示的一部分，因为在很多开发实践中，将CFG、基本块的构造，和三地址码的生成，放在相同阶段，并且都是分析的输入，当然也有资料将CFG和基本块不当做中间表示的一部分，而当做中间表示在分析前的预处理，不过怎么理解都行，没有太大关系）。

3.1 基本块（Basic Block）

基本块由一系列的语句组成，这些语句具有如下特点：

• 只能从第一条语句进入该基本块，不能够以某种方式跳入该基本块的中间;
• 基本块内的语句在执行时必须从最后一条语句离开，不能够执行到一半跳转到其它的基本块;
• 基本块内的语句序列，必须按照顺序依次执行。

即对于一个基本块来说：只能有唯一一个进入点（基本块第一条语句）和唯一的一个出口（基本块最后一条语句），并且内部必须顺序执行，不能有分支和跳转。

3.2 CFG

CFG是一个由基本块组成的有向图，每个节点都是一个基本块。如果程序的执行路径可能从一个基本块B1进入另一个基本块B2，B1有一条指向B2的边。

CFG可以用一个三元式描述：G=(N, E, n0)

其中：

N：表示所有基本块节点的集合；

E：表示所有边的集合；

n0：表示首节点。

CFG具有如下的两条性质：

• CFG 必然有唯一的一个入口点；
• 首节点必然支配CFG中其他的所有节点（即从首节点到CFG上其他任何一个节点都有一条路可以连通）。

4.    总结

本文介绍了一些静态代码分析中，中间表示的一些基本概念。

首先介绍了AST，AST忠实体现源码的结构，可以应用于程序结构检测、程序风格检查等检查；

其次，介绍了三地址码、SSA形式的三地址码，随后介绍了基本块和CFG，基本块就是一系列符合条件的三地址码指令的集合，CFG是一系列基本块按照一定依赖关系组合起来的。

基于CFG的中间表示，可以应用于程序的数据流分析、控制流分析等，是程序静态代码分析的基础。