Static Analysis 02-Intermediate Representation

Static Analysis 02-Intermediate Representation

HC_Plantern 164 2022-09-23

本文参考:

重点

• The relation between compilers and static analyzers
• Understand 3AC and its common forms
• How to build basic blocks on top of IR
• How to construct control flow graphs on top of BBs?

Compiler and Static Analysis

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

  1. 词法分析器 Scanner 结合正则表达式, 通过词法分析 Lexical Analysis 将 source code 翻译为 token.
  2. 语法分析器 Parser , 结合上下文无关文法 Context-Free Grammar , 通过语法分析 Syntax Analysis , 将 token 解析为抽象语法树 Abstract Syntax Tree, AST
  3. 语义分析器 Type Checker , 结合属性文法 Attribute Grammar , 通过语义分析 Semantic Analysis , 将 AST 解析为 decorated AST
  4. Translator, 将 decorated AST 翻译为生成三地址码这样的中间表示形式 Intermediate Representation, IR , 并基于 IR 做静态分析 例如代码优化这样的工作 , IR之前的部分我们称为前端, IR之后的部分称为后端。
  5. Code Generator, 将 IR 转换为机器代码。

几个问题:

  1. 语法分析为什么是Context-Free Grammar

    现在的编程语言完全足够, Context-Sensitive Grammar 更适合分析人讲的语言

  2. 为什么不直接拿Source code做静态分析, 而是要经过到IR的这一系列步骤?

    分析代码漏洞, 这是 non-trivial 的事情, 做 non-trivial 之前应该把 trivial 的部分交给各种分析器去做

AST vs. IR

为什么 IR 更适用于静态分析?

3AC ( 三地址码 )

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

  • 名称 Name: a, b
  • 常量 Constant: 3
  • 编译器生成的临时变量 Compiler-generated Temporary: t1, t2

常见的 3AC 包括:

  • z=x bop yz=x bop y:双目运算符并赋值,bop = binary operator
  • x=uop yx=uop y :单目运算符并,unary operator
  • x=yx=y:直接赋值
  • goto Lgoto L:无条件跳转,L = label
  • if x goto Lif x goto L:条件跳转
  • if x rop y goto Lif x rop y goto L:包含运算关系的跳转,rop = relational operator

Soot: Real Static Analyzer

Do-While Loop

Method Call

Java IR (Jimple) basic knowledge:

- invokespecal : call constructor, call superclass methods, call private methods
- invokevirtual: instance methods call (virtual dispatch)
- invokeinterface: cannot optimization, checking interface implementation
- invokestatic: call static methods
- Java 7: invokedynamic -> Java static typing, dynamic language runs on JVM

method signature: class name: return type, method name(para1 type, para2 type)

SSA (Static Single Assignment)



Why SSA?

  • flow-insensitive analysis 精度更好
  • 容易做优化算法

Why not SSA?

  • too many variables and phi-functions
  • inefficiency problem due to copy operations

Control Flow Analysis

CFG

Basic Block (BB)

定义: 只有唯一一个入口和唯一一个出口的最长 3AC 连续序列

  • It can be entered only at the beginning
  • It can be exited only at the end, i.e. the last instruction in the block

识别 BB 入口 (leader) 的方法:

  1. 第一条指令是 leader
  2. goto 目标是 leader
  3. goto 的下一条指令是 leader

由此可以划分出所有的 Basic Block

Build CFG on top of BBs

  1. Nodes of CFG are BBs
  2. Block A -> Block B has an edge if and only if
    1. There is a conditional or unconditional jump from the end of A to the beginning of B
    2. B immediately follows A in the original order of instructions and A doesn’t end in a jump
  3. Add two nodes: Entry and Exit

Example: