- 1.compiler和static analysis之间的关系
- 2. AST和IR的差异
- 3. IR
- 4. Static Single Assignment(SSA)
- 5. BB（basic block）
- 6. CFG(Control Flow Graph)
1.compiler和static analysis之间的关系
我直接用一张图表示！
这里可以看到，在源代码编译成机器可执行的程序之中，经历了很多的步骤，像Scanner（词法分析）、Parser（语法分析）、Type checker（语义分析），得到一个抽象语法树(AST)，然后经过 Translator转换成汇编代码后，交给Code Generator生成二进制可执行程序
但是其实，如果Translator的任务不是生成汇编代码，而是生成IR，从这里就可以开始做静态分析的应用了。
2. AST和IR的差异
AST就像图中左边的这种形式，IR就是右边下面的形如
1: i=i+1
2: t1 = a[i]
3: if t1 < v goto 1
的类似代码的东西。
其实这么一看差异还是比较明显的，接下来仔细说明AST和IR之间的关系。
AST:
接近语言本身的语法结构
依赖语言
比较适合做快速的类型检测
缺少控制流
IR:
比较低级，接近机器码的执行流程
语言无关
形式统一
保护控制信息
3. IR
IR(intermediate representation)是静态分析中很重要的概念。
先前也稍微提到了IR的形式，它是静态分析的主要载体，大部分静态分析工具，都是在IR的基础上进行分析的。
其实IR就是一种 3-Address Code（3AC) 三地址码
它的特征也比较明显:
a+b+3 转换成 IR后
t1 = a+b
t2 = t1+3
像这种有3个操作数的，就是三地址码了，其实2个操作数也是合理的。
4. Static Single Assignment(SSA)
SSA是不同于3AC的表现形式，具体体现在：
- 对于每个定义，都必须有自己的名字
- 每个变量只有一个定义
给个3AC和SSA的图示。
可以看到，每个步骤所得到的结果，都需要有一个变量标识，每个定义也需要有一个变量标识，且变量随后不能再被使用。这种形式当然是有问题的，比如:
像这种条件分支，因为会产生2个变量x0 和 x1，但是其实到达下一步后，程序无法得知到底是哪个值被用到了，如果就2个还可以通过遍历，但是如果分支多起来就很麻烦了。
于是SSA有了一种叫做special merge operator的操作符，用来merge变量的。
SSA的优势与劣势
优势:
- flow-insensitive, 速度快，精度低
- Define-and-Use pairs are explicit，就是定义使用对很明显很简介
劣势:
- 变量太多了
- 无法应对大型的copy操作
5. BB（basic block）
BB（基本块）是构成控制流图的基本单位
,BB由 若干条IR组成，BB的具体定义就两条:
入口唯一、出口唯一
生成BB的算法
可以看到，其实只需要找， 一段IR中的 第一条指令、jump指令的目标、跳转指令后的那条指令 ，都是一个BB的入口，可以通过找入口来生成BBs
举个例子:
6. CFG(Control Flow Graph)
由一系列BBS构成的图，就叫做控制流图（IDA中的那个，想必大家用过都知道）
生成CFG的算法
三步走:
- BB是CFG的节点，首先需要生成BBS
- 画边
A的末尾和B的开头之间有跳转指令，连边 B直接跟在A后面且A不以无条件跳转指令结束
- 替换标签（比如跳转到第几条指令变为 跳转到块几）