南京大学《软件分析》课程02 Intermediate Representation 笔记
1.Compilers and Static Analyzers
编译器流程：
语法分析：
词法分析的主要任务从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示词法单元(token)形式token:＜种别码，属性值>
词法分析后得到的token序列：
词法分析的实现：
暴力求解或者DFA算法
2.AST & IR
AST | IR |
|---|---|
高级 更接近于语法结构 | 低级 更接近于机器码 |
依赖语言种类 | 不依赖 |
适用于快速检查 | 压缩且简洁 |
缺少控制流信息 | 包含控制流信息 |
通常用作程序分析的基础 |
为什么使用IR作为程序分析的基础：
1、语言无关；
2、包含控制流信息。
3.IR：Three-Address Code（3AC）
中间语言的一种，每个三地址码指令，都可以被分解成一个四元组
运算符、操作数1，操作数2，结果
𝑧=𝑥 𝑜𝑝 𝑦
𝑥=𝑜𝑝 𝑦
𝑥=𝑦
𝑔𝑜𝑡𝑜 𝐿
𝑖𝑓 𝑥 𝑔𝑜𝑡𝑜 𝐿
𝑖𝑓 𝑥 𝑜𝑝 𝑦 𝑔𝑜𝑡𝑜 𝐿
4.3AC in Real Static Analyzer:Soot
基于栈
java语言的字节码表示本来就是栈的，而象Dalvik 是基于寄存器的，在这点上Jimple基于栈
有类型
每一个参数都定义了Type，并且类型精度没有丢失，比如int $i0
基于三地址分析
三地址解析中会出现很多的中间变量
三地址同时会拆解一些高级特性，被分解成多个单位，包含一些低级操作，支持低端指令一般而言，三地址代码将包含大部分低级操作，即目标机所支持的指令。
invokespecial : call constructor, call superclass methos, call private methods
构造函数
Method Signature
<class name : return type <method name> >(params);
invokevirtual: instance methods call(virtual dispath)
java7 : invokedynamic
clinit
5.Static Single Assignment(SSA)
静态单赋值（Static Single Assignment，SSA） 是另一种IR的形式，它和3AC的区别是，在每次赋值的时候都会创建一个新的变量，也就是说，在SSA中，每个变量（包括原始变量和新创建的变量）都只有唯一的一次定义。
当控制流汇合（Merge）的时候，我们会用一个特殊的操作符表示汇和后的定义：
关于SSA，我们只要简单了解一下定义和优缺点就可以了，之后还是用3AC比较多。
优点：
控制流的信息间接地被包含在了独特的变量名之中
当我们做一些对控制流敏感的分析的时候，这些信息可能会有帮助
定义和使用的关系明确
缺点：
可能会引入过多的变量名和ϕ函数
被翻译成机器码的时候效率低，因为有太多对于程序执行来说不必要的赋值
6.Basic Blocks(BB)
INPUT: A sequence of three-address instructions of P
OUTPUT: A list of basic block of P
METHOD: Determine the leader
简单理解，基块就是满足如下性质的最长指令序列：
程序的控制流只能从首指令进入
程序的控制流只能从尾指令流出
于是我们可以直观的感受到，跳转指令会将一个完整的程序块切割为几个基块，如果我们能够把基块的分隔点找出来，那么整个程序P就可以被我们转化成许多的基块了。
7.Control Flow Graphs(CFG)
The nodes of CFG are basic blocks
CFG的节点是基块
There is an edge from block A to block B if and only if ：
There is a conditional or unconditional jump from the end of A to the beginning of B.
B immediately follows A in the original order of instructions and A does not end in an unconditional jump
It is normal to replace the jumps to instruction labels by jumps to basic blocks
从A到B有一条边当且仅当：
从基块A的结束到基块B的开始存在条件跳转和无条件跳转
基块B按照指令的原始顺序紧跟在基块A之后，而基块A不会以无条件跳转结束
通常将跳转到标签替换为跳转到basic block
于是我们可以直观的感受到，跳转指令会将一个完整的程序块切割为几个基块，如果我们能够把基块的分隔点找出来，那么整个程序P就可以被我们转化成许多的基块了。
简单理解，一个基块的领导者就是这个基块的首指令，整个程序中的领导者有如下3种：
整个程序的首指令；
跳转指令（包括条件跳转和无条件跳转）的目标指令；
跳转指令（包括条件跳转和无条件跳转）紧接着的下一条指令。
(1) x = input
(2) y = x -1
(3) z = x * y
(4) if z< x goto (7)
(5) p = x / y
(6) q = p + y
(7) a = q
(8) b = x + a
(9) c = 2a -b
(10) if p == q goto (12)
(11) goto (3)
(12) return
一、The first instruction in P is a leader.
(1)
二、Any target instruction of a conditional or unconditional jump is a leader.
(3)(7)(12)
三、Any instruction that immediately follows a conditional or unconditional jump is a leader.
(5)(11)(12)
Leader : (1)(3)(5)(7)(11)(12)
BB1 :(1)(2)
BB2 :(3)(4)
BB3 : (5)(6)
BB4 :(7)(8)(9)(10)
BB5: (11)
BB6: (12)
所以可以得出CFG：
