课程环境：https://tai-e.pascal-lab.net/lectures.html

课程视频：https://www.bilibili.com/video/BV1b7411K7P4

南大《软件分析》2.0 IR

IR 即 Intermediate Representation，是一种中间语言表示，通常代码在经过编译器前端之后会转化成 IR 的形式来帮助后端进行优化。

这一部分展示了，从源码到最后机器码的过程，涉及到了一些编译原理的知识，不过没有相关编译知识也不用太过担心，只需要熟悉这张图的流程，并且明白通常我们在静态分析的过程是在 IR 这一步就可以了，如果对 IR 理解有困难可以参考我之前关于 llvm IR 的介绍 ，理解它是个什么东西就行了。

这一部分给出了为什么我们静态分析要从 IR 开始，而不是从 AST（抽象语法树）来进行分析，对上面的内容简单翻译之后就是：

AST

• 更接近目标语言的语法结构
• 依赖目标语言
• 适合快速类型检查
• 缺少控制流信息

IR

• 更接近机器码的低级表达
• 不依赖原始语言
• 紧凑和统一的
• 包含控制流信息
• 被认为是静态分析的基础

可以这样想，因为静态分析的目的就是找出那些程序执行时可能出现的一些行为，显然像上图那样的 AST 对于理解程序执行情况是帮助不大的，反而 IR 这种简单的指令形式可以极大的来帮助我们理解程序，并检测其行为。

3-Address Code (3AC)

3AC 是一个概念，即三地址码，实际上是用来更加简化每条指令提出的一种形式，它要求在每条指令的右侧最多只有一个操作符。

//不属于三地址码
c = a+b+3 
//经过优化后的三地址码
t1=a+b		//满足
c =t1+3   //满足

上图归纳了三地址码中的地址具体指：变量名，常量，编译器生成的临时变量。

老师还讲了一些从源码到对应到3AC的一些实际的案例，能看懂理解即可。

SSA

SSA（static single assignment） 即静态单一赋值，即SSA中每个变量只能被定义一次，通俗来讲一个变量只能出现在等号左边一次，不能出现两次及以上。

SSA 优缺点总结如下：

优点：

• 执行流信息被间接传递到变量名
• 定义和使用是明确的

缺点：

• 会引入大量变量和φ函数
• 转化为机器码的效率降低

能理解它是个啥玩意就行，不是课程重点。

Control Flow Analysis

Control Flow Analysis 通常指建立控制流图（CFG），比如说下图就是一个将3AC程序转化为CFG的一个过程。

从控制流图中我们需要关注的一个东西就是基本块（basic block），即上边右图中各个小的代码块。

满足以下两个性质的连续指令称为一个基本块：

• 只能由第一条指令作为基本块入口
• 只能由最后一条指令作为基本块出口

根据程序划分基本块的算法也很简单，用文字描述就是（这里把每个基本块的入口指令称为 leader）：

• 只需要找到各个基本块入口的 leader（对应前面的图下面的例子并不唯一）
  • 程序的第一条指令是一个 leader：x = input
  • 无条件（goto）或条件 goto 的目标指令是一个 leader：z=x*y
  • 无条件（goto）或条件 goto 指令的下一条指令是一个 leader：p = x/y
• 以前面找到的各个 leader 对源程序进行切分，每个块就是一个基本块

可以结合下面的图来理解上面的算法思想。

那有了基本块之后还要思考怎么构造连接基本块之间的边，当然这个算法就更简单了：

• 基本块A到基本块B之间存在无条件（goto）或条件 goto 时添加边
• 基本块B 紧接在基本块A之后（按指令顺序，A执行完的下一条指令属于B）且基本块A不以无条件goto结束

理解起来实际上就对应上图中的内容，通过在实际过程中可能还会加入一个 entry 和 exit 两个块，因为程序毕竟总有开始和结束嘛。

思考题

相信有了前面的内容了解之后，理解这些问题并不难