编译技术：中间代码生成

中间代码生成设计

编码前的设计

需求分析

读取语法分析构建的 AST 以及语义分析构建的符号表，生成中间代码结构并以 LLVM IR 形式给出表示，输出至 llvm_ir.txt。

文件组织

新建目录 src\midend\llvm，该部分存储 LLVM IR 的数据结构，其中包含若干类：

Builder：该模块“主函数”，完成中间代码的构建。

新建目录 src\midend\visit，该部分定义节点遍历方法。

中间代码数据结构

这一部分个人认为是最难以理解的，各大资料对此说法不一且囿于理论，大家都是全局层面的高度抽象，想直接全部把握确实很难。

从全局言之，LLVM IR 数据结构如下图：

Value：是所有数据结构的父类，它拥有valueType、name、useList三个属性：

valueType：这个数据结构的数据类型，类比高级程序语言的 int, void 等。
name：这个数据结构 toString 时输出的名称，类比高级程序语言的 identifier。
useList：Use 的数组，指出这个 Value 有哪些使用关系。

Module：顶层模块，拥有多个 GlobalValue，表示一个 .c 程序文件。因为我们的文法只允许单文件，因此也只有一个 module。

GlobalValue：全局量，有全局变量和函数，它们不在任何一个基本块，而是直接在模块内定义，在所有基本块中都可以被使用。

GlobalVariable：全局变量。
Function：函数定义，包括若干普通函数和一个主函数。

BasicBlock：基本块，基本块的定义可以看编译理论，就是一整个可以顺序执行的语句块，直到跳转指令和返回指令为止。一个基本块包含若干指令。

Instruction：指令，它又分为很多种具体的指令类型。同时继承于 User 类。

User：使用者，使用者可以使用其他 value。举例理解为：%21 = add nsw i32 %15, %20，这个语句的意思是 %21=%15+%20，这里的 use 关系是“%21 使用了 %15 和 %20，而这个 %21 其实是一个 add 指令”。这也是为什么只有指令是 user。

构建中间代码结构

在 Builder 静态类中提供了构建中间代码的所有方法，Builder 类是连接 llvm 数据结构和 ast 结点的桥梁。因此 Builder 有一个具体的 module。

public static GlobalVariable createGlobalVariable(…)：创建一个新的全局变量，在 Visitor 读到新的全局变量定义时触发。

public static Function createFunction(…)：创建一个新的函数，给函数初始化一个基本块，并记录当前属于哪个函数和哪个基本块（这样后续添加指令才不会放错），在 Visitor 读到新的函数定义时触发。

public static BasicBlock createBasicBlock()：创建一个新的基本块，但更新当前基本块，在创建函数和 Visitor 读到跳转相关语句时触发。

public static void setCurBasicBlock(…)：设置当前基本块，在确定了如何跳转时触发，创建函数时也会被使用。

public static void addInst(Instruction instruction)：添加指令，把指令加到当前基本块内。

编码完成后的修改

完整文件组织

midend
├── Midend.java
├── llvm
│   ├── Builder.java
│   ├── Module.java
│   └── value
│       ├── BasicBlock.java
│       ├── Inst
│       │   ├── AllocateInst.java
│       │   ├── AluInst.java
│       │   ├── BranchInst.java
│       │   ├── CallInst.java
│       │   ├── CompareInst.java
│       │   ├── ExtendInst.java
│       │   ├── GepInst.java
│       │   ├── Instruction.java
│       │   ├── JumpInst.java
│       │   ├── LoadInst.java
│       │   ├── PrintIntInst.java
│       │   ├── PrintStrInst.java
│       │   ├── ReturnInst.java
│       │   └── StoreInst.java
│       ├── Loop.java
│       ├── Parameter.java
│       ├── Use.java
│       ├── User.java
│       ├── Value.java
│       ├── ValueType.java
│       ├── constant
│       │   ├── Constant.java
│       │   ├── IntConst.java
│       │   └── StringConst.java
│       └── globalValue
│           ├── Function.java
│           ├── GlobalValue.java
│           ├── GlobalVariable.java
│           ├── LibFunc.java
│           └── StringLiteral.java
├── symbol
└── visit
    ├── BlockVisitor.java
    ├── DeclVisitor.java
    ├── ExpVisitor.java
    ├── FuncDefVisitor.java
    ├── LValVisitor.java
    ├── StmtVisitor.java
    └── Visitor.java

新的 Value 类型

之前仅有 GlobalVariable，Function，BasicBlock，Instruction 几个主要类型，编码过程中发现为了方便需要定义新的类型。

LibFunc：库函数声明，是一个全局量，调用 IO 相关库函数时需要这些声明。

declare i32 @getint()  
declare void @putint(i32)  
declare void @putch(i32)  
declare void @putstr(i8*)

StringLiteral：字符串字面量，也是一个全局量，处理字符串。

1	@.str = private unnamed_addr constant [10 x i8] c"23373179\0A\00"

Loop：存储循环信息，用于处理嵌套循环的跳转问题。

Parameter：函数参数信息。

Constant：常量信息。

IntConst：整数常量。
StringConst：字符串常量。

指令生成

具体的生成步骤在实验教程的相关部分已经介绍得非常详细，这里不再赘述。

ReturnInst

返回指令，ValueType 是 void，名称是 null。使用返回值。

返回整数常量的情况：

ret i32 0

返回寄存器的情况：

1	ret i32 %21

无返回值的情况：

ret void

AllocateInst

寄存器分配指令，ValueType 是待分配数据的指针类型，名称按编号规则赋予。不使用其他值。
分配一个 i32 类型的寄存器，命名为 %5，类型为 i32*：

1	%5 = alloca i32

AluInst

算数指令，ValueType 是 i32，名称按编号规则赋予。使用两个值，分别是两个操作数。

加法：

1	%21 = add nsw i32 %15, %20

乘法：

1	%18 = mul nsw i32 %16, %17

另外还有除法和取模，不再赘述。

StoreInst

存数指令，ValueType 是 void，没有名称。使用两个值，一个是待存数据，一个是寄存器地址。

1 2	%4 = alloca i32 store i32 %16, i32* %4

该指令前必有寄存器分配指令，这也解释了为什么寄存器分配指令的类型是指针。

LoadInst

取数指令，ValueType 是待取寄存器的基础类型，名称按编号规则赋予。使用一个值，即待取寄存器的指针。

1 2	%4 = alloca i32 %28 = load i32, i32* %4

该指令前必有寄存器分配指令。

CallInst

函数调用指令，ValueType 是函数的返回类型，名称若有返回值则按编号规则赋予，否则没有名称。使用若干值，即函数形参。

有返回值的函数调用：

1	%32 = call i32 @coordinate_calculater(i32 %28, i32 %29, i32 %30, i32 %31)

没有返回值的函数调用：

1	call void @putstr(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.str.1, i64 0, i64 0))

CompareInst

比较指令，ValueType 是 i1，名称按编号规则赋予。使用两个值，分别是两个比较数。

判断相等：

1	%72 = icmp eq i32 %71, 0

ExtendInst

零扩展指令，ValueType 是要扩展到的数据类型（i32），名称按编号规则赋予。使用一个值，即待扩展的数据。

引入该指令是为了处理 compare 指令返回值 i1 判断是 0 还是 1 的情况，因为 compare 指令使用的两个值都是 i32，因此需要扩展。

BranchInst

有条件跳转指令，ValueType 是 void，没有名称。使用三个值，第一个是条件，第二个是条件为真跳转到的基本块，第三个是条件为假跳转到的基本块。

1	br i1 %4, label %5, label %9

基本块的数据类型是 label，命名规则与寄存器、数据共用一套。

JumpInst

无条件跳转指令，ValueType 是 void，没有名称。使用一个值，即跳转到的基本块。

1	br label %9

GepInst

指针获取指令，ValueType 是 i32*，名称按编号规则赋予。使用两个值，指针起始地址和偏移量。

1	%17 = getelementptr inbounds [10 x i32], [10 x i32]* %16, i32 0, i32 5

上面这个指令起始指针是 %16，偏移量是 5。

IO 相关指令

其实是一种特殊的 CallInst，调用相关 IO 函数。

重难点

该部分汇总一些仅看教程容易遗漏的 bug 处理。

static 变量

static 变量应该视为全局变量（llvm 需要把它提到外面去并命名加上对应的函数前缀），在同一种作用域内 static 变量不能重名，但不同作用域内可以。

static int x = 0;  
int func() {  
    static int x = 1;  
    {  
        static int x = 2;  
    }  
}

这样的代码生成的 llvm 如下：

@x = internal global i32 0  
@func.x = internal global i32 1  
@func.x.1 = internal global i32 2  
  
define dso_local i32 @func(){  
  
}

同一函数内重名的 static 变量在后面加上数字用以区分。同时需要 internal 标志内部链接。

函数传参

普通 i32 参数：

int func2(int a)  
{  
    printf("%d", a);  
    return a;  
}

传递的是 i32 数值，一般会无脑分配一个寄存器 i32*，但该部分可以优化掉。

define dso_local i32 @func2(i32 %0){  
1:  
    %2 = alloca i32  
    store i32 %0, i32* %2  
    %3 = load i32, i32* %2  
    call void @putint(i32 %3)  
    %4 = load i32, i32* %2  
    ret i32 %4  
  
}

数组 i32* 参数：

void func3(int a[])  
{  
    printf("%d", a[0]);  
    return;  
}

依然无脑给数组指针分配了一个寄存器，但没有必要。

define dso_local void @func3(i32* %0){  
1:  
    %2 = alloca i32*  
    store i32* %0, i32** %2  
    %3 = load i32*, i32** %2  
    %4 = getelementptr inbounds i32, i32* %3, i32 0  
    %5 = load i32, i32* %4  
    call void @putint(i32 %5)  
    ret void  
  
}

无 return 语句的函数

需要自动加一个 ret void。

空基本块

空基本块如果输出，是不符合 llvm 语法的，因此要么不输出，要么给他加一个跳转到下一个基本块的指令。空基本块的产生原因是 for 语句的空语句。

常量的求值

这里的求值指的是 evaluate，因为数组初始化列表中必须是已经能够确定的值，所以是可以出现常量的。

1
2
3

const int G_CON1 = 10 * 20 + 1 * 3 / 1;  
const int G_CON2 = 1, G_CON3 = 2, G_CON4 = 3;  
const int G_CON_ARR[5-1] = {4 , 3, 2, 0 + G_CON3 - 1};

常量在定义的那一刻就应该直接 evaluate 了。

@G_CON1 = dso_local constant i32 203  
@G_CON2 = dso_local constant i32 1  
@G_CON3 = dso_local constant i32 2  
@G_CON4 = dso_local constant i32 3  
@G_CON_ARR = dso_local constant [4 x i32] [i32 4, i32 3, i32 2, i32 1]

数组初始化列表

1
2
3

void func() {  
    int c[3] = {1, getint()};  
}

数组初始化列表很有多样性，居然是可以放 getint 的？

define dso_local void @func(){  
    %1 = alloca [3 x i32]  
    %2 = getelementptr inbounds [3 x i32], [3 x i32]* %1, i32 0, i32 0  
    store i32 1, i32* %2  
    %3 = getelementptr inbounds i32, i32* %2, i32 1  
    %4 = call i32 @getint()  
    store i32 %4, i32* %3  
    %5 = getelementptr inbounds i32, i32* %3, i32 1  
    store i32 0, i32* %5  
    ret void  
  
}

BaconToast's Shop