Intermediate Representation - 中间表示 (IR)
Compiler and Static Analysis
下图给出了编译器Compiler将源代码转换为机器码的具体过程，以及静态分析Static Analysis所在位置
(1) 首先利用词法分析器Lexical Analysis Scanner，结合正则表达式，将Source Code转换成Tokens
(2) 然后利用语法分析器Syntax Analysis Parser，结合上下文无关法Context-Free Grammar解析为AST (Abstract Syntax Tree)抽象语法树
(3) 接着利用语意分析器Semantic Analysis Type Checker，结合属性文法Attribute Grammar，将AST解析为Decorated AST，比如图中给出的例子，Apples eat you，符合主谓宾，即符合语法，通过了语法检测，但是存在语义问题，因为苹果apples是不可能发出吃eat这个动作的。
但在编译器的角度，更多的是做简单的语意检查，比如类型检查Type Checker，比如用一个String类型的值除以一个int类型的值，这种类型错误等等
(4) 若这个编译器还要做后续的优化，会通过转换器Translator转换成中间表示形式，即IR(三地址码)，并基于IR进行静态分析
(5) 最后通过Code Generator将IR转换为Machine Code
AST vs IR
为什么IR更适合被用于静态分析
(1) AST更接近语法结构，而IR更底层更接近于机器码Machine Code
(2) AST需要依赖于编程语言，IR不需要，不同的编程语言可以被统一转换为IR
(3) 相比于AST，IR中包含控制流信息，在AST中，我们知道这是一个循环是因为头节点的do-while关键字，而在IR中，通过if t1 < v goto 1可以很容易知道这是一个循环
3-Address Code (3AC)
一些常用的3AC的写法如下图所示
Soot
Soot IR被称为Jimple - typed 3AC
Loop 3AC
do{}while的3AC如下图所示，不多做赘述
Method Call 3AC
Method Call方法调用的3AC如下图所示，对应foo方法的3AC
这里的 specialinvoke 对应java.lang.StringBuilder的构造方法
$r3.<java.lang.StringBuilder: void <init>()>() 中<>包裹的值即为method signiture
method signiture通常构成形式为 <className: returnType MethodName(Parameter1 type, Parameter2 type, .....)>
搞懂了foo方法，main函数的3AC就很好理解了
Class 3AC
Static Single Assignment - SSA
给每一个定义一个新的name
利用phi-function解决不同的流交汇的问题
对比图一3AC和SSA，可以看出SSA更像是一个数据流，通过p1, p2, p3, q1, q2
Control Flow Analysis
IR三地址码 -> 转换为Control Flow Graph -> 在Control Flow Graph (CFG)的基础上进行静态分析
CFG的Node，可以是单独的三地址码指令，也可以把某些指令集中到一起-构成Basic Block(如图中所示B1, B2, .... B6)
Basic Blocks - BB
Basic Block需要满足两个特征
(1) 只能从块的第一条指令进入
(2) 只能从块的最后一条指令输出
从实际例子分析
为什么 (1),(2) 可以作为一个BB，而(1),(2),(3)不行，因为 (11) 中的goto (3)指令，会导致(1),(2),(3)构成的块同时有两个入口，违背了只允许有一个入口的规则
同理可以分析，为什么(3),(4)可以作为一个BB，而(3),(4),(5)不行，因为(3),(4),(5)构成的块同时有两个出口，违背了只允许有一个出口的原则
根据上述规则，可以得出构建BB的方法
根据上述算法确定所有的Leader，一个Leader后续所有的指令直至下一个Leader中的指令可以构成一个BB
Add edges to build CFG
首先进行替换
加边
加完边后，可以称B1是B2的前驱predecessor，B2是B1的后继successor
通常还要加两个Node，Entry和Exit
自此CFG构建完成