BlogPapers

SummerSec

View on GitHub

Intermediate Representation 中间代表(IR)

Compilers and Static Analyzers 编译器与静态分析

编译器将源代码(Source code) 转换为机器代码(Machine Code)。其中的流程框架是:

有人要问了,为什么不直接拿 source code 做静态分析?这是因为我们得先确保这是一份合格的代码,然后再进行分析。分析代码合不合格,这是 trivial (琐碎)的事情,由前面的各种分析器去做就行了,我们要做的是 non-trivial 的事情。


AST vs. IR

为什么在静态分析的时候,使用 IR 而非 AST 呢?

image-20220105105502801

这是因为:

AST 相对来说比较**高级**,可读性比较高对象开发者,而相反IR更倾向于机器。AST规范不统一,每一种语言大致相同但不完全一样,而IR是统一的规范的。

IR: Three-Address Code

三地址码(3-Address Code)通常没有统一的格式。在每个指令的右边至多有一个操作符。

image-20220105105745115

三地址码为什么叫做三地址码呢?因为每条 3AC 至多有三个地址。而一个「地址」可以是:

常见的 3AC 包括:


Static Single Assignment 静态单赋值(SSA)

所谓静态单赋值(SSA),就是让每次对变量x赋值都重新使用一个新的变量xi,并在后续使用中选择最新的变量。

3AC        | SSA
p = a + b    p1 = a + b
q = p - c    q1 = p1 - c
p = q * d    p2 = q1 * d
q = p + q    q2 = p2 + q1

但是这样一来,肯定会因为不同控制流汇入到一个块,导致多个变量备选的问题:

这里解决的办法就是使用一个合并操作符$\phi$(phi-function),根据控制流的信息确定使用哪个变量。

为什么要用 SSA 呢?

为什么不用 SSA 呢?

某些具体场景还是会用到SSA,比例说llvm是ssa,一些领域特定的编程语言也是ssa。

Basic Blocks & Control Flow Graphs 基本块 & 控制流图

控制流分析(Control Flow Analysis)通常指的是构建控制流图(Control Flow Graph, CFG),并以 CFG 作为基础结构进行静态分析的过程。

image-20220105111922258

CFG 的一个结点可以是一条单独的 3AC,但是更常见的是一个基本块(Basic Block)。所谓基本块,就是满足以下性质的连续 3AC:

image-20220105112133363

如何构建一个基本块呢?

除了基本块,CFG 中还会有块到块的边。块 A 和块 B 之间有一条边,当且仅当:

image-20220105152735721

注意到每个基本块和开头指令的标号唯一对应,因此很自然地,我们可以将跳转指令的目标改为基本块的标号而非指令标号:

image-20220105152758818

有了这些定义,我们就可以了解一些概念:

这样,我们就完成了一个控制流图的构建:

image-20220105174001342