南京大学《软件分析》- 02 - IR

02 - IR

1. Compilers and Static Analyzers
2. AST vs. IR （AST：抽象语法树，在语法分析、词法分析之后的中间表示。）
3. IR: Three-Address Code (3AC)
4. 3AC in Real Static Analyzer: Soot
5. Static Single Assignment (SSA)
6. Basic Block (BB)
7. Control Flow Graphs (CFG)

Compilers

输入为 SourceCode

• Scanner - 词法分析-Lexical Analysis - 检查每一个单词（不一定是英文单词）- 里面用到了正则表达式（Regular Expression）- 最后生成Tokens作为语法分析的输入。
• Parser - 语法分析 - Syntax Analysis - 检查单词之间的语法规则 - Context-Free Grammar（上下无关语法）- 最后生成AST（抽象语法树）。
• Type Checker - 语义分析 - Sementic Analysis - 检查类型处理合理 - Attribute Grammar - 最后生成Decorated AST（装饰的抽象语法树）。
• Translator - 翻译 - 最后生成IR（一般是指3D码）。
• Code Generator - 代码生成器 - 最后生成机器码。

AST vs. IR

• AST

  • 表达层次比较高，与语法树非常贴合
  • 依赖于不同的语言
  • 适合快速的类型检查
  • 在控制流信息流分析

• IR - (“3-address” form)

  • 表达层次比较低，与机器码相近，与汇编相近
  • 与语言相关性不强
  • 压缩且简洁
  • 包含控制流信息
  • 经常被考虑作为静态分析的基础
    

Intermediate Representation (IR)

3-Address Code 三地址码。引入临时变量，一般包含三个信息：

• 名称
• 常量
• 编译临时变量

每种指令都有他们自己的三地址码。

3AC in Real Static Analyzer: Soot

真实的三地址码，Java的IR，Jimple in Soot。

https://github.com/Sable/soot

Loop循环

在这里面x和i在soot中，x被优化掉了。所以在三地址码中看到只有i。【又或者说是，i被优化掉了，仅存在一个x，是不是更加合理？】

Do-while 循环

Method Call

前面的前几个变量（r0,r1,r2,r3）是Jimple翻译器用来临时使用的声明的变量，和一些需要用的变量的类型。

r0声明的是MathodCall3AC这个类型，this指向当前这个对象。

Class

在PL中，在引用一个变量的时候，它会将变量给加载进来。例如上图的

public static void <clinit>()
{<nju.sa.examples.Class3AC: double pi> = 3.14;return;
}

Static Single Assignment (SSA)-可选

SSA是IR里面一种经典的转化模式。

• 给每一个定义一个新的命名。
• 传递新的变量名到后续的式子使用。
• 一个变量只有一个精确的定义。
  
  
  以上PPT，针对x0和x1会引入φ（phi-function）这个函数进行统合。
  SSA有典型的特征：
• 每一个变量（variable）都有自己的一个定义。
• 如果要用多重的x，会引入一个φ函数。

为什么不SSA？

• 可能太多φ函数。

Basic Block (BB)

• 一个BB的入口一定是第一条指令。
• 一个BB的出口一定是最后一条指令。
• 满足以上两个条件之后的最大的指令集合。

如何设计一个算法去生成BB块呢？

• 确定每个BB的入口（Leader）
  • 程序当中的第一个指令是入口（Leader）
  • 任何跳转指令（jump/goto）的目标指令（target）
  • 紧跟在所有跳转指令的后面一条指令
• 建立BB
  • 一个BB包括一个入口（leader）和Leader后面所有跟随的指令，知道遇到下一个Leader。

如何在BB基础上建立CFG？

添边。

Control Flow Graphs (CFG)

三地址码最终还是要转化为控制流图CFG。

添边的规则：

• CFG的结点是BB。
• 满足跳转指令：从A的结尾到B的开始，添边。
• 不满足跳转指令的（紧接在跳转指令后的一条指令）需要添加一条边。
• B紧接着A之后，添边。
  • 除非A的最后一条指令是一条无条件跳转指令（jmp/goto)
• 将跳转到块替换跳转到指令是合理的。
• 一个BB可以有多个前驱，也可以有多个后继。
• 最后需要添加两个结点：Entry和Exit。
  • 入边（Entry）只有一个
  • 出边（Exit）可以有多个

小结