IR分析

目录：

  1. 编译器和静态分析的关系
  2. AST vs IR
  3. 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

img

1-1-编译器原理.png

2.AST vs IR

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

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

img

1-2-AST&IR.png

3.IR:3-地址代码（3AC）

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

img

1-3-常用3地址码.png

4.实际静态分析器的3AC—Soot（Java）

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

1
2
3
4
5
6
7
8
9
// 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个定义（赋值的目标变量）。

img

1-4-SSA.png

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

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

6.基本块（BB）

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

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

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

img

1-5-基本块算法.png

image-20210507093627625

image-20210507094011702

image-20210507093932573

7.控制流图（CFG）

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

img

1-6-控制流边.png

image-20210507094447334

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

作者：bsauce
链接：https://www.jianshu.com/p/acb73f72cf46
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。