南大软分课程笔记｜02 中间语言

前言

第二堂课的主题是Intermediate Representation，简称IR，翻译过来就是“中间语言”。又要说回之前读过的论文了——IR在其中发挥了关键作用。很多论文的模式都是将研究对象（如Linux内核）的源码过LLVM生成IR，在IR基础上构建控制流图，最后在控制流图上做相关研究的。

这节课，李樾老师深入浅出地讲解了一系列的概念，下面笔记中的每一个二级标题都对应着课件的一个小节。

Compilers and Static Analyzers

从下图可以看到，编译通常包括词法分析、语法分析、语义分析等过程，最终生成机器码。静态分析使用的是Translator生成的IR。另外，此处也可以去延伸了解一下乔姆斯基体系，包含了0型文法（对应递归可枚举语言，图灵机）、1型文法（对应上下文敏感语言）、2型文法（对应上下文无关语言）和3型文法（正则文法，有限状态机）。

AST vs. IR

从上图中我们可以发现有两类常用的中间结果：抽象语法树（AST）和IR。一个自然而然的问题是，为什么是基于IR做静态分析，而不是AST呢？我们来看一个简单的例子：

do i = i + 1; while(a[i] < v);

上面这个示例的AST如下：

它的IR则是这样的：

1: i = i + 1
2: t1 = a [ i ]
3: if t1 < v goto 1

总结一下，AST与IR各有以下特点：

IR: Three-Address Code (3AC)

IR常用的表示形式是三地址码（3-Address Code，简称3AC）。它的一个要求是，在一个指令的右边至多只有一个操作符。例如，对于c = a + b + 3这样的语句，3AC需要引入一个中间变量来将其变成两个指令：t1 = a + b和c = t1 + 3。

所谓三地址码，指的是每个3AC指令可以至多包含三种地址：变量名（如a、b、c），常量（如数字3），编译器生成的临时变量（如t1）。下面是一些常见的3AC形式：

3AC in Real Static Analyzer: Soot

本课程使用Java作为研究对象，因此后面会用到Java的静态分析框架Soot（官方教程：tutorials）和它的IR Jimple。Jimple是一种有类型的三地址码（typed 3AC）。

接下来是三个Jimple的示例，分别对应do-while循环、方法调用和类定义。我们将给出Java示例源码，然后使用Soot在本地环境生成Jimple文件。我的Java环境是JDK8，因此需要预先生成class文件，然后再执行Soot。具体命令如下所示：

javac DoWhileLoop3AC.java
java -cp sootclasses-trunk-jar-with-dependencies.jar soot.Main -cp . -pp -f jimple DoWhileLoop3AC

Do-While Loop

示例代码：

package nju.sa.examples;

public class DoWhileLoop3AC {
    public static void main(String[] args) {
        int[] arr = new int[10];
        int i = 0;
        do {
            i = i + 1;
        } while (arr[i] < 10);
    }
}

Soot生成的Jimple文件（摘录了main函数部分）：

public static void main(java.lang.String[])
{
    int[] r0;
    int $i0, i1;
    java.lang.String[] r1;
    r1 := @parameter0: java.lang.String[];
    r0 = newarray (int)[10];
    i1 = 0;
 label1:
    i1 = i1 + 1;
    $i0 = r0[i1];
    if $i0 < 10 goto label1;
    return;
}

Method Call

示例代码：

package nju.sa.examples;

public class MethodCall3AC {
    String foo(String para1, String para2) {
        return para1 + " " + para2;
    }
    public static void main (String[] args) {
        MethodCall3AC mc = new MethodCall3AC();
        String result = mc.foo("hello", "world");
    }
}

Soot生成的Jimple文件：

foo函数：

java.lang.String foo(java.lang.String, java.lang.String)
{
    java.lang.StringBuilder $r0, $r2, $r3, $r5;
    java.lang.String r1, r4, $r6;
    MethodCall3AC r7;
    r7 := @this: MethodCall3AC;
    r1 := @parameter0: java.lang.String;
    r4 := @parameter1: java.lang.String;
    $r0 = new java.lang.StringBuilder;
    specialinvoke $r0.<java.lang.StringBuilder: void <init>()>();
    $r2 = virtualinvoke $r0.<java.lang.StringBuilder: java.lang.StringBuilder append(java.lang.String)>(r1);
    $r3 = virtualinvoke $r2.<java.lang.StringBuilder: java.lang.StringBuilder append(java.lang.String)>(" ");
    $r5 = virtualinvoke $r3.<java.lang.StringBuilder: java.lang.StringBuilder append(java.lang.String)>(r4);
    $r6 = virtualinvoke $r5.<java.lang.StringBuilder: java.lang.String toString()>();
    return $r6;
}

main函数：

public static void main(java.lang.String[])
{
    nju.sa.examples.MethodCall3AC $r0;
    java.lang.String[] r3;
    r3 := @parameter0: java.lang.String[];
    $r0 = new nju.sa.examples.MethodCall3AC;
    specialinvoke $r0.<nju.sa.examples.MethodCall3AC: void <init>()>();
    virtualinvoke $r0.<nju.sa.examples.MethodCall3AC: java.lang.String foo(java.lang.String,java.lang.String)>("hello", "world");
    return;
}

Class

示例代码：

package nju.sa.examples;

public class Class3AC {
    public static final double pi = 3.14;
    public static void main(String[] args) {
    }
}

完整的Jimple文件：

public class Class3AC extends java.lang.Object
{
    public static final double pi;
    public void <init>()
    {
        Class3AC r0;
        r0 := @this: Class3AC;
        specialinvoke r0.<java.lang.Object: void <init>()>();
        return;
    }
    public static void main(java.lang.String[])
    {
        java.lang.String[] r0;
        r0 := @parameter0: java.lang.String[];
        return;
    }
    public static void <clinit>()
    {
        <Class3AC: double pi> = 3.14;
        return;
    }
}

Static Single Assignment (SSA)

OK，接下来是静态单一赋值（SSA）这个概念。在3AC的基础上，SSA指的是，所有赋值操作的被赋值变量都需要有一个独特的名字。每个定义都会有一个新名字，这个新名字可以应用在后续的分析中，每个变量都有一个定义。下面是一个SSA的示例：

3AC:                    SSA:
p = a + b               p1 = a + b
q = p - c               q1 = p1 - c
p = q * d               p2 = q1 * d
p = e - p               p3 = e - p2
q = p + q               q2 = p3 + q1

有时，某个变量可能受到条件分支影响，处于控制流汇聚的位置（control flow merges），此时就需要使用$\varphi$函数来处理，如下图所示：

$\varphi(x_{0}, x_{1})$的值由控制流经过的条件分支决定。

关于SSA的讨论：

Control Flow Analysis

控制流分析通常指的是建立控制流图（Control Flow Graph，简称CFG）。CFG是静态分析的基础结构，CFG的每个节点可以是一个3AC，也可以是一个基本块（Basic Block，简称BB），后者更为常见。

下图就是这样的一个示例，输入是目标程序P的3AC，输出是目标程序P的CFG：

Basic Blocks (BB)

BB指的是一个连续、最长的3AC序列，该序列具有以下特性：

• 控制流只能从该序列的起始指令进入。
• 控制流只能从该序列的最后一条指令退出。

上一节中示例图右侧的B1到B6就是六个具有以上特性的BB。现在的问题是，给定一段3AC，如何将其划分为不同的BB？

经过尝试，我们找到了这样一个算法来划分BB：

1. 确定3AC序列中的leaders。leaders包括具有以下特性的指令：
   1. 3AC序列中的第一条指令。
   2. 所有有条件跳转或无条件跳转的所有目标指令。
   3. 所有有条件跳转或无条件跳转后面的一条指令。
2. 划分BB。BB包含leader指令及其后面紧邻的所有非leader指令。

Control Flow Graphs (CFG)

在划分好BB的基础上，我们就可以构建CFG了。CFG具有如下特性：

• CFG的节点均为BB。
• 从块A到块B之间有一个有向边，当且仅当“从A到B一个有条件或无条件跳转”，或“B是A后面的紧邻块且A最后一条指令不是无条件跳转”。
• 将原来3AC序列中的所有“跳转到某指令标签处”改为“跳转到某基本块处”。

通常我们还会在CFG的开头和结尾加两个虚拟节点“Entry”和“Exit”。

总结与思考

这一课上，李樾老师主要依次讲解了IR、3AC、基本块和CFG。这些概念很有意思，理解起来也不费劲。就这样，我们能一点点地将一个程序变成IR，进一步抽象为CFG，逐渐就可以进行静态分析了。