NJU Static Analysis - Intermediate Representation

重点：

• 编译过程中的IR

• 3AC –> BB –> CFG的构建过程

Complier

大致过程如下：

词法分析（Scanner）=> 生成token

语法分析（Parser）=> 由token解析成AST（非上下文检查，比如只把token组成一个语句而已）

语义分析（Type Checker） => 上下文基础上进行检查

然后通过Translator（这个依语言而定）来转成IR（中间表示）

静态分析的对象就是IR

IR

IR的表示方法：

组织结构 特点	类型	举例
Linear IR	基于线性代码、堆栈机代码	三地址代码
Graphical IR	基于图 抽象语	抽象语法树、法树、有向无环图、控制流图
Hybrid IR	基于图与线性代码混合 LLVM IR

3AC

3地址码

• Some Common 3AC Forms

不同静态分析框架中的3AC表示形式不同

SSA

SSA（Static Single Assignment）

给每个符号都添加下标以区别不同时刻下的符号信息

• Give each definition a fresh name
• Propagate fresh name to subsequent uses
• Every variable has exactly one definition

需要在控制流图上添加一些新的语句

Control Flow Analysis

3AC => BB => CFG

Basic Blocks（BB）

Basic blocks (BB) are maximal sequences of consecutive three-address instructions

（连续的三地址码序列）

BB中的入口只能是BB中的第一句

结束语句只能是BB中的最后一句

build Basic Blocks

每个Basic Blocks中的第一条指令是leader

我们确定每个Basic Block的本质方法是确定Basic Block中的leader和跳转语句即可

Control Flow Graph（CFG）

控制流图的构建过程，注重“静态”思维，对于一些永真的判断是不关注的

• CFG的节点是BB
• 一个Basic Block到另一个Basic Block之间有且仅有一个edge
  • 有条件跳转，相邻块之间需要加edge
  • 无条件跳转，相邻块之间不需要加edge

• goto label-value ==> goto BasicBlock Name