程序源码直接拿来给静态分析器做静态分析是不合适的，像编译一样也需要在程序的中间表示(IR)上进行分析，这样能让静态分析算法比较简洁、高效。IR也没有绝对的标准，这节课学习的是绝大多数静态分析器采取的IR。
1 编译的基本流程
1.1 词法分析
词法分析(Lexical Analysis)会去检查是否输入的源代码是若干合法单词的组合。词法分析器统称Scanner，运行时需要关键字的词典，以及用正则表达式描述的词法规则。
词法分析会为每个合法的单词生成Token。
1.2 语法分析
语法分析(Syntax Analysis)会去检查这些Token的组合形式是否符合语法规则。语法分析器统称Parser，相应的描述语法规则的方式是上下文无关文法(Context-Free Grammer)。Context-Free Grammer的表达能力比Context-Sensitive Grammer弱，但是对几乎所有的编程语言而言，这样的表达能力就足够了，如果去使用后者反倒会更慢。
语法分析会生成抽象语法树(AST)。
1.3 语义分析
语义分析(Semantic Analysis)会去检查语义是否合理。和自然语言的语义不同，对编译器而言，只具备检查简单的语义的功能，如类型检查器(Type Checker)，相应的进行类型检查时描述规则的方法是Attribute Grammer。
语义分析会生成Decorate AST。
1.4 转换
如果编译器有编译优化的功能，那么就要通过转换器(Translator) 转换成中间表示(IR) 的形式，这里的中间表示IR通常指的都是三地址码形式(3-Address Form)。
生成IR之前的部分是编译器前端，生成IR之后的部分是编译器后端。编译优化就是静态分析的一种应用，静态分析是在IR的基础上做的，所以是属于编译器后端。这也说明了，要做静态分析，就不得不走完编译器前端的部分才能拿到IR，接着再在IR的基础上做分析。
1.5 生成
为了能执行，要将上一步的中间表示，通过代码生成器(Code Generator) 生成机器码(Machine Code)。
2 AST和三地址码的比较
如对于一段简单do-while循环的程序：
do {
i = i + 1;
} while(a[i] < v);
2.1 AST
表示成AST是这样的：
- 比较高层，很贴合编程语言的文法结构
- 通常依赖于具体的编程语言（因为和文法结构贴合）
- 很适合快速进行类型检查
- 控制流信息很隐晦
2.2 三地址码形式的IR
表示成三地址码形式的IR是这样的：
1: i = i + 1
2: t1 = a[i]
3: if t1 < v goto 1
- 比较低层，更贴合汇编语言和机器码
- 通常和具体的编程语言是无关的
- 紧凑、简洁、格式统一
- 能自然地看到控制流信息（如上面的
goto 1） - 通常作为静态分析器IR的正统格式
3 三地址码介绍
3.1 简述
三地址码(3-Address Code)也可简称3AC，其指令右侧至多有一个运算符，如：
t2 = a + b + 3
可以转换成：
t1 = a + b
t2 = t1 + 3
向三地址码的转换通常会引入临时变量，这里t1就是临时变量。
之所以叫三地址码，是因为它的每一条指令最多包含三个地址(Address)，这里的地址不是通常意义上的地址，而是下面中的一种：
- 变量，如
a、b - 常量，如
3 - 编译器或静态分析器自动生成的临时变量，如
t1、t2
3.2 三地址码的理论形式
以下x、y、z都是地址，即变量、常量或临时变量。
x = y bop z，这里bop是二元运算符或逻辑操作符x = uop y，这里uop是一元操作符，如符、取反、类型转换x = ygoto L，即无条件跳转if x goto L，即条件跳转if x rop y goto L，其中rop是关系运算符
这些是理论上的3AC的形式，具体到实现时要更复杂。
4 Soot的三地址码IR——Jimple
Soot是为Java服务的最有名的静态分析器，Jimple是它所使用的中间表示，也是一种特殊的三地址码的形式，下面是几个Java源程序到Jimple三地址码的例子。
4.1 for循环
注意，下面源程序中的x因为最后也没用到，被Soot在得到AST时候就优化去掉了，得到的Jimple里不再有这个变量。
在形参表里面给出了方法参数的完整类型名，抹去了形参的名字。
第一行指令声明字符串类型的r0，接着声明整形的i1（以代替程序for循环中的i）。
后面r0 := @parameter0: java.lang.String[];表示变量r0定义为该方法的第一个参数，其类型是java.lang.String[]。接下来为i1赋值为0。
然后在label1中把这个for循环的行为用三地址码描述了（注意i1 = i1 + 1对应的是程序里的i++而不是x = x + 1），如果i1达到10了就跳到label2然后直接返回。
4.2 do-while循环
在这个例子里args对应r0，数组arr对应r1，变量i对应i1（因为在while条件中被使用所以不能将其消除），而arr[i]对应临时变量$i0也即r1[i1]。
注意在这个do-while例子的三地址码中可以看到label1下总是先执行i1 = i1 + 1，这和do-while的语义是一致的。
4.3 方法调用(方法内部)
例子中这个方法是一个成员方法，这里三地址码中的r0被定义为this的指向，即例子中承载这个函数的MethodCall3AC这个类的对象。
函数的两个参数para1和para2分别对应r1和r2。为了完成函数中三个字符串拼接的操作，创建了一个临时的StringBuilder$r3，然后调用append操作将变量r1拼进来得到$r4，再调用append操作将常量" "拼进来得到$r5，再调用append操作将变量r2拼进来得到$r6，最后用toString()将其转换成String对象$r7，并将其返回。
在上面的Jimple代码中还出现了specialinvoke和virtualinvoke，这是JVM里四种主要方法调用中的两种，这四种命令是：
- invokespecial：用于调用构造方法、父类方法、私有方法
- invokevirtual：用于调用普通的成员方法，进行virtual dispatch
- invokeinterface：用于调用继承的接口的方法，不能做优化，需要检查是否实现了接口中的方法
- invokestatic：用于调用静态方法
在Java7之后还引入了invokedynamic，用来更方便的实现动态类型的语言在JVM上运行。
在上面的Jimple代码中方法调用(invoke)的地方，尖括号<和>之间的内容是方法签名(Method Signature)，它一般会包含方法所在的类名、方法的返回值类型、形参列表中各个参数的类型，有些还会包含方法名（比如上面的例子里append就是方法名）。
4.4 方法调用(调用方)
这里还是4.3例子的程序，但是是方法的调用方（即主函数部分）的Jimple。
可以看到同样是r0声明为主函数形参args，然后$r3是对象mc，先用specialinvoke调用构造方法把这个对象构造出来，然后用virtualinvoke调用了方法foo，把两个字符串参数传了进去。
注意，因为源程序中调用foo的返回变量result没有用到所以被Soot优化消除了，对应的Jimple里也就没有将调用的返回值保存到变量里了。
4.5 类
这里类代码的Jimple不仅要将类名写完整，还要将继承的类显式写出来，以保全语义信息。
源程序中没有显式给出构造函数，Jimple中的<init>是默认生成的构造函数，然后$r0指向this，再用specialinvoke调用其父类（这里是Object，见方法签名）的构造函数。
接下来静态的main方法源程序中是空的，但也要将形参定义以下，这里r0对应args。
接下来静态的<clinit>方法是类的静态的初始化方法，当类被初次加载到内存里时，就是通过调用这个<clinit>方法来将所有的静态属性初始化。例子中就是将pi初始化为3.14这个值，至于pi的声明在最上方。
5 静态单赋值(Static Single Assignment)
5.1 简述
这是一种经典的IR格式，SSA和普通3AC的区别在于它给每一个定义都使用了新的名称：
左侧3SA中第1/3/4行的p在右侧SSA中使用了不同的名称p1/p2/p3，而第2/5行的两个q也被改成了不同的名称q1/q2，在赋值右侧则用前面出现的名称进行对应，不会改变整个程序的语义。
5.2 phi-function
这样使用了不同名称之后，为了保证每个变量还是有唯一的定义而不会产生歧义，在控制流汇合的地方使用 函数进行聚合，例如：
图中 当程序走左边时就取 ，走右边时就取 ，它有专门的分析算法。
5.3 优缺点
- 它可以将flow-sensitive的一条条指令变成flow-insensitive的，也就是对指令的顺序不再敏感，这样flow-insensitive的分析可以提高分析的速度，同时较好保持flow-sensitive的精度，因为它本身就带有了一些flow的信息
- 能更精确地找到其定义的地方，因为每条都是新的定义
- 引入了太多的变量，如果有太多分叉还会引入很多phi-function
- 转换到机器码的过程会有很多低效的地方
6 控制流图的构建
三地址码最终是在控制流图(Control Flow Graph) 上进行分析，这里学习如何从3AC转换到CFG。
在CFG中若干条指令一起组成Basic Block，作为图上结点存在。
6.1 基本块(Basic Block)
基本块是满足下列性质的，最大的连续指令的有序集合。
- 只能有一个入口，为其第一条指令，不存在从另一个位置进入BB的控制流
- 只能由一个出口，为其最后一条指令，不存在从BB中间跳出去的情况
特别注意，满足这两条性质的Block，只要不是最大的连续指令集，就不能成为BB，所以实际程序中每条指令最终所在的BB总是情况唯一的。
6.2 BB的构建思路
-
如果一条指令是程序中某个跳转的目标，那么它一定是一个BB的入口，否则会违反规则1。
-
如果一条指令包含跳转操作，那么它一定是一个BB的出口，否则会违反规则2。
这里老师讲的是，如果一条指令紧跟着一条含有跳转操作的指令，那么它一定是一个BB的入口，和这个的意思是一样的，因为一条指令是BB出口，它的下一条指令一定是下一个BB的入口。
6.3 BB的构建算法
先找整个程序中BB开始的指令，标记为Leader：
- 程序第一条指令
- 跳转的目标指令
- 带跳转的指令的下一条指令
接着从每个Leader开始往下，直到下一个Leader或者程序结尾之前，合起来是一个BB。
例如：
图中标红的就是找出的Leader。
6.4 完整CFG的构建
接下来就是在前面构造好的BB之间添加边，很直观：
- 两个BB顺次相连，加边
- 从A无条件跳转B，加边
- 从A条件跳转到B，加边
注意，这里规则1有例外，如果前一个BB的最后一条指令是无条件的goto，那么不要按照规则1加边。
在构建边的同时，将指令中，goto的目标从指令标号变换成BB的名字：
最终添加Entry和Exit两个特殊结点，即得到这小节最开始图上的CFG。
转载：https://blog.csdn.net/SHU15121856/article/details/104711426