[南京大学]-[软件分析]课程学习笔记(二)-IR

Intermediate Representation

1. compilers and static analyzers

compilers是将source code转化为machine code，中间过程如下：

1. 词法分析(Scanner)，通过词法分析Lexical analysis将source code翻译为tokens，判断单词是否合法（词典、规则，Regular expression）
2. 语法分析（Parser），通过语法分析Syntax analysis将token解析为AST，结合上下文无关文法分析（Context-free grammar），弱表达能力，速度较快，组成句子的要素都存在，但顺序不一定正确
3. 语义分析器（Type Checker），通过语义分析（Semantic analysis），结合属性文法（Attribute grammar）将AST解析为Decorated AST
4. Translator，将decorated AST翻译为IR（三地址码），并基于IR做静态分析西
5. Code generator，将IR转化为machine code

为什么不直接拿source code做静态分析？

因为首先要确保这是一份合格的代码，词法正确，语法正确，语义正确，而后再进行分析non-trivial的一些属性，而不是在可能编译不通过，运行不起来的程序中去分析这些trivial属性。

PS：这里可能还是需要看应用场景，应用场景不同，其需求不同，source code有时确实会比IR或者machine code表达出更丰富的语义。在OSS重用，代码相似性的field中，确实存在若干paper基于source code构建代码相似性

2. AST vs IR

• 抽象语法树是high-level，且比较接近语法结构的，而IR是low-level且接近机器代码的
• AST依赖于语言，而IR通常独立于语言
• AST适合快速类型检查，而IR的结构更加紧凑和统一
• AST缺少控制流信息，而IR包含了控制流信息

因此IR更适合作为静态分析的基础

3. IR: three-address code (3AC)

三地址码：通常没有统一的格式

There is at most one operator on the right side of an instruction.

每条指令右边最多有一个操作符

每当出现多个操作符，可以通过引入临时变量来解决。

为什么叫3地址码呢？因为最多可以包含3个地址，地址可以是以下三种形式：

• Name:a, b
• Constant: 3
• Compiler-generated temporary: t1, t2

一些常用的3AC：

4. 3ac in real static analyzer:Soot

5. Static Single Assignment(SSA)

静态单一赋值：

• 每个变量都有自己的定义
• 不同的控制流汇入一个块中，则会导致多个变量备选，因此merge时引入phi-function

Why SSA:

• 流信息会间接的引入到独特的变量名称中；对流不敏感的分析可能会得到流敏感分析的一些精度；
• Define-and-use 是显示的，在一些按需任务中可以更有效的存储和传播数据事实；一些优化器任务在SSA上表现的更好，例如条件变量传播，全局变量计数等

Why not SSA:

• 会引入太多变量；
• 转换为机器码时会带来性能问题；

6. Basic blocks(BB)

最多的序列，连续的三地址码

• BB入口只能是第一条指令
• BB出口只能是最后一条指令

入口唯一，出口也唯一

在三地址码序列中输出基本块：

1. 决定BB等起始指令：
   1. 程序的第一条指令为一个起始指令；
   2. 任何条件跳转或者非条件跳转的目标指令是一个起始指令；
   3. 任何跳转指令的下一条指令为一个起始指令；
2. 建立程序P的BB：
   1. 一个基本块包含一条起始指令和直到下一条起始指令的所有指令序列

7. Control Flow Graphs(CFG)

• CFG的节点就是BB；
• block A 和 block B之间有边，条件是：
  • 条件跳转和非条件跳转从A的结尾到B的开头
  • 在原始指令顺序中，B紧接着A（无条件goto不可以 ）
• 用跳转到基本块来代替跳转到指令；
• 添加Entry和Exit，Entry连接第一个BB，Exit连接最后一个BB；

A是B的前驱，B是A的后继（均不唯一）