02 - Intermediate Representation(IR)
# 02 - Intermediate Representation(IR)
本系列笔记的课程地址：南京大学《软件分析》课程2020 (opens new window)
# Compilers and Static Analyzers
# Compiler
流程：
源码 -> (Scanner；进行词法分析；用到 正则表达式) ->
Tokens -> (Parser；进行语法分析；用到 Context-Free Grammar) ->
Context-Free 上下文无关文法，更适合且足够用于代码
Context-Sensitive 上下文敏感文法，更适合人类语言
AST -> (Type Checker；进行语义分析；用到 Attribute Grammar) ->
Decorated AST -> (Translator) ->
IR -> (Code Generator) ->
Machine Code
IR 之间是编译器前端，IR 之后是编译器后端
静态分析需要在编译器前端生成的 IR 上进行，例如：代码编译优化
# Abstract Syntax Tree(AST) vs. IR
# AST
更接近语法结构；语言相关
适合用来做快速的类型检查
缺少了控制流信息（看不出来控制流）
# IR（三地址码形式）
更接近汇编、机器语言；语言无关
紧凑且统一
包含了控制流信息
通常被用来作为静态分析的基础
# IR: Three-Address Code(3AC)
3-Address Code(3AC)：一条指令右边最多只有一个运算符
每个三地址码指令包含最多 3 个 addresses
Address 可以是
Name：a, b
Constant：3
Compiler-generated temporary：t1，t2
eg.
a + b + 3->t1 = a + b; t2 = t1 + 3;
每一种指令都有自己的 3AC Form，下面是一个常见的三地址码：
# 3AC in real Static Analyzer: Soot
Soot 是 Java 领域非常常用的静态分析框架
Soot 的 IR 是 Jimple（三地址码形式的）
下面是一些 Jimple 的例子
# Do-While Loop
- 「$」 标注了临时变量
# Method Call
JVM 中的四种 invoke 调用
invoke speciall：call constructor、call superclass(父类) methods、call private methods
invoke virtual：call instance methods(virtual dispatch，虚函数查表，即会先从调用该方法的对象的类实现中找，找不到再去父类找)
invoke interface：类似 invoke virtual，但不做优化，且会进行 checking interface implementation(实现接口时方法时候都实现了)
invoke static：call static methods
Java 7 还引入了 invoke dynamic
<...>尖括号里的是 method signature：- [class name]: [return type] [method name](parameter type...)
# Class
- clinit 是对静态变量的初始化方法
# Static Single Assignment(SSA) 「optional material」
# 什么是 SSA ？
- 需要记住的两点特征：1. 每个变量都有个准确的定义、名字；2. 当变量名有多种可能性时，会引入
来进行合并
# SSA 的好处（核心点在于变量名的 distinct）
程序流可以被间接的融入在 unique variable names 中
- 携带了更多信息，可以帮助提供一些更简单的分析，例如：flow-insensitive analysis 可以无需提高 cost 就能获取部分 flow-sensitive analysis 的精度
定义与使用更为清楚、明确
# SSA 的坏处
引入更多变量和
函数 导致一些性能问题
# Control Flow Analysis
一般指建立控制流图 Control Flow Graph（CFG)
CFG 是静态分析的基础结构
CFG 中的 node 可以是一个三地址码指令，或者通常是一个 Basic Block
# Basic Blocks(BB)
BB 是连续三地址码指令的最大序列，且满足 1. 入口唯一(第一条指令)；2. 出口唯一(最后一条指令)
这里的入口和出口指的是一条语句
# 如何构建 Basic Blocks？
输入：P 的三地址码序列
输出：P 的 BB 列表
算法：
决定 P 的入口
P 的第一条语句一定是入口
跳转命令的 target 指令一定是入口
跳转命令后紧跟的一条语句也一定是入口（因为跳转命令一定是唯一的出口）
构建 P 的 BBs
- 一个 BB 包含了一个入口和直到下一个入口前的所有子序列指令
eg：
# 构建 Control Flow Graph（CFG)
CFG 的每个 node 是一个 BB
连接一条 from A to B 的边，需要且仅需要满足下面的条件
A 的出口有一个条件跳转或无条件跳转到 B 的入口
B 按指令初始顺序紧跟在 A 的后面，且 A 的出口不是一条无条件跳转（如下图右一为例，
(j) goto (i)是无跳转指令，A 不能连边到 B）
- 替换指令 label 的跳转为 BB 的跳转
A 到 B 有一条边，则我们称 A 是 B 的前驱 predecessor，B 是 A 的后继 successor
我们还要添加两个特殊节点，Entry 和 Exit
他们与可执行 IR 无关，引入只是为了方便后续静态分析算法设计的初始化
Entry 节点连了一条边到包含了 IR 的第一条指令的 BB（本课程中 Entry 只有一条，例如多线程下可能有多个 Entry）
Exit 节点作为后继，与任何包含了 IR 的最后一条指令的 BB 相连，可能有多条边
- 【Input：3AC of P】 -> 【Output：CFG of P】
# 需要掌握的重点
理解编译器和静态分析的关系
理解 3AC 和他的常见形式（in IR Jimple）
如何在 IR 上构建 Basic Blocks
在 Basic Blocks 上构建控制流图