目录：

1. 编译器和静态分析的关系

2. AST vs IR

3. IR:3-地址代码（3AC）

4. 实际静态分析器的3AC—Soot（Java）

5. SSA-静态单赋值

6. 基本块（BB）

7. 控制流图（CFG）

1.编译器和静态分析的关系

源码->（Scanner - 词法Lexical分析-Regular Expression）->（Parser- 语法Syntax分析-Context-Free Grammar）， 生成AST ->（Type Checker - 语义Semantic分析 - Attribute Grammar），生成 Decorated AST -> Translator，生成IR，进行静态分析 -> Code Generator

1-1-编译器原理.png

2.AST vs IR

AST ：高级，更接近于语法结构，依赖于语言种类，适用于快速类型检查，缺少控制流信息

IR：低级，更接近于机器码，不依赖语言种类，压缩且简洁，包含控制流信息。是静态分析的基础

1-2-AST&IR.png

3.IR:3-地址代码（3AC）

// 最多1个操作符
a+b+3  ->  t1 = a+b
                 t2 = t1+3
Address：
    Name:a、b
    Constant: 3
    编译器的临时变量：t1、t2

1-3-常用3地址码.png

4.实际静态分析器的3AC—Soot（Java）

Soot-常用的Java静态分析框架

// java IR（Jimple）基本知识
invokespecial：call constructor, call superclass methods, call private methods
invokevirtual: instance methods call (virtual dispatch)
invokeinterface: cannot optimization, checking interface implementation
invokestation:call static methods

Java 7: invokedynamic -> Java static typing, dynamic language runs on JVM

method signature: class name, return type, method name(parameter1 type, parameter2 type)

5.SSA-静态单赋值

定义：给每一个定义变量一个新的名字，传递到接下来的使用当中，每个变量有1个定义（赋值的目标变量）。

1-4-SSA.png

优点：唯一的变量名可以间接体现程序流信息，简化分析过程；清楚的Define-Use信息。

缺点：引入很多变量和phi-function；转换为机器码时效率变低（引入很多拷贝操作）。

6.基本块（BB）

定义：只有1个开头入口和1个结尾出口的最长3-地址指令序列。

识别基本块的算法：首先确定入口指令，第一条指令是入口；任何跳转指令的目标地址是入口；任何跟在跳转指令之后的指令是入口。然后构造基本块，任何基本块包含1个入口指令和其接下来的指令。

我的想法：对于下1条指令，若该指令不是入口，则可以加入；若该指令有多个出口，则停止加入，否则继续判断下一条指令。

1-5-基本块算法.png

7.控制流图（CFG）

控制流边：基本块A的结尾有跳转指令跳转到基本块B；原始指令序列中，B紧跟着A，且A的结尾不是无条件跳转。

1-6-控制流边.png

添加Entry / Exit：没有块跳转到该块 / 没有跳转到其他块。

参考：

南大课件

南大视频课程

北大课件