【课程笔记】南大软件分析课程2——IR

roger

【课程笔记】南大软件分析课程2——IR

目录：

1.编译器和静态分析的关系2.AST vs IR3.IR:3-地址代码（3AC）4.实际静态分析器的3AC—Soot（Java）5.SSA-静态单赋值6.基本块（BB）7.控制流图（CFG）

1.编译器和静态分析的关系

源码->（Scanner - 词法Lexical分析-Regular Expression）->（Parser- 语法Syntax分析-Context-Free Grammar）， 生成AST ->（Type Checker - 语义Semantic分析 - Attribute Grammar），生成 Decorated AST -> Translator，生成IR，进行静态分析 -> Code Generator

【课程笔记】南大软件分析课程2——IR

1-1-编译器原理.png2.AST vs IR

AST ：高级，更接近于语法结构，依赖于语言种类，适用于快速类型检查，缺少控制流信息

IR：低级，更接近于机器码，不依赖语言种类，压缩且简洁，包含控制流信息。是静态分析的基础

【课程笔记】南大软件分析课程2——IR

1-2-AST&IR.png3.IR:3-地址代码（3AC）

// 最多1个操作符
　　a+b+3  ->  t1 = a+b
　　t2 = t1+3
　　Address：
　　Name:a、b
　　Constant: 3
　　编译器的临时变量：t1、t2
　　

【课程笔记】南大软件分析课程2——IR

1-3-常用3地址码.png4.实际静态分析器的3AC—Soot（Java）

Soot-常用的Java静态分析框架

// java IR（Jimple）基本知识
　　invokespecial：call constructor, call superclass methods, call private methods
　　invokevirtual: instance methods call (virtual dispatch)
　　invokeinterface: cannot optimization, checking interface implementation
　　invokestation:call static methods
　　Java 7: invokedynamic -> Java static typing, dynamic language runs on JVM
　　method signature: class name, return type, method name(parameter1 type, parameter2 type)
　　

5.SSA-静态单赋值

定义：给每一个定义变量一个新的名字，传递到接下来的使用当中，每个变量有1个定义（赋值的目标变量）。

【课程笔记】南大软件分析课程2——IR

1-4-SSA.png

优点：唯一的变量名可以间接体现程序流信息，简化分析过程；清楚的Define-Use信息。

缺点：引入很多变量和phi-function；转换为机器码时效率变低（引入很多拷贝操作）。

6.基本块（BB）

定义：只有1个开头入口和1个结尾出口的最长3-地址指令序列。

识别基本块的算法：首先确定入口指令，第一条指令是入口；任何跳转指令的目标地址是入口；任何跟在跳转指令之后的指令是入口。然后构造基本块，任何基本块包含1个入口指令和其接下来的指令。

我的想法：对于下1条指令，若该指令不是入口，则可以加入；若该指令有多个出口，则停止加入，否则继续判断下一条指令。

【课程笔记】南大软件分析课程2——IR

1-5-基本块算法.png7.控制流图（CFG）

控制流边：基本块A的结尾有跳转指令跳转到基本块B；原始指令序列中，B紧跟着A，且A的结尾不是无条件跳转。

【课程笔记】南大软件分析课程2——IR

1-6-控制流边.png

添加Entry / Exit：没有块跳转到该块 / 没有跳转到其他块。

参考：

南大课件[1]

南大视频课程[2]

北大课件[3]

References

[1] 南大课件: https://pascal-group.bitbucket.io/teaching.html[2] 南大视频课程: https://zhuanlan.zhihu.com/p/110050716[3] 北大课件: https://xiongyingfei.github.io/SA/2019/main.htm

---