LLVM IR 生成

一、内存 SSA

llvm 是 SSA 形式的，但是在没有经过 mem2reg 的时候，SSA 是内存形式的，也就是说，对于每个变量，只要在定义他的时候，为他在内存中划分空间存入，在使用他的时候在取出来，这样就可以达到 SSA 的效果。这是因为 SSA 只要求我们不能改变一个已经定义的值，改变内存的内容显然并不违法 SSA。

这会导致当我们提到（也就是查询）一个局部变量的时候，其实是从符号表中取出来的是它的指针，这个过程一般发生在 LVal。一般我们会对变量干两件事情，读变量和写变量和做实参。对于读变量，一般发生在 LVal 作为 PrimaryExp 的时候发生，此时需要在 PrimaryExp 中对其进行 Load，而写变量一般发生在 LVal 在 AssignStmt 和 InStmt 中，只需要用 Store 将其写入即可。做实参要单独挑出来讲，是因为它的逻辑是与 C 需要保持一致的，他是有指针类型的，这就要求我们对他进行单独的处理。这就是内存式 SSA 的基本逻辑。

二、符号表

正如前面所述，因为 LLVM IR 是 SSA 形式的，所以符号表中存的内容也和 C 中理解并不相同，比如说对于

f()
{
    int a = 2;
}

在 C 中，我们会认为 a 在符号表中是一个 int，但是在 llvm 中，为了满足 SSA ，所以在符号表中，a 中对应的是一个指向 int 的指针，如果想要获得 a 中的内容，那么就需要使用一个 load 指令。这就造成了某种逻辑的不一致性。更可悲的是，C 中还有 const 的概念。

f()
{
    const a = 3;
    int b[a] = {1, 2, 3};
}

是不是可以直接也用一个指针去存他，然后用一个 load 访存呢？大概是不行的，因为下面那个语句会用到 alloca，虽然我不确定 alloca 是否可以动态分配，但是如果是下面这种，就肯定不行了

const a = 3;
int b[a] = {1, 2, 3};
f()
{
    
}

在全局部分是没有办法使用 load 指令的，尤其是我们一般面对上面的情况，会要求求出 b 的维度信息，如果维度信息不是 3 ，而是一个 load，显然就无法求出了，这就导致面对这种情况，我们必须存一个常量到符号表中，这就更要求我们在解析的时候，知道我么你啥时候存的是常量，啥时候存的是指针，这需要额外的继承属性（也是最重要的继承属性）canCalValueDown ，其实这个属性意味着一种“常量读”。

三、符号的定义

符号的定义本质是填写符号表和定义，我本来打算总结起来再写，但是感觉太冗杂了，很难理出一个头绪，所以就变成了罗列。

3.1 全局单常量

如果是一个单常量，那么只需要把 ConstInitVal 求解出来，会得到一个 int ，然后在符号表中，只需要存储一个 ConstInt 就可以了。

3.2 局部单常量

与全局单常量相同，依然是将 ConstInt 存入到符号表中，并没有任何问题。

3.3 全局常量数组

对于常量数组的初始值，我们要求是可以在编译器求值的，所以它的每个元素的初始值一定是可以被求值的，当我们求出来它的值以后，没有办法直接在符号表中存入它的值，这是因为我们会进行类似于变量的访问：

const int a[2] = {1, 2};

int main()
{
    int i = 2;
    a[i];
    return 0;
}

这样我们是没有办法在编译时就求出 a[i] 的，所以 a 必须提供变量访问形式，这就要求他必须被当成一个全局变量，所以他确实是一个全局变量，我们在符号表中存入的其实是一个全局变量，因为在 llvm 中，全局变量本质是一个指向其内容的指针，所以其实符号表中存入的是一个指针。但是也需要注意的是，其实符号表中 a 这个东西对应了两个 Value ，一个是 GlobalVariable ，另一个是 GlobalVariable.getInitValue() 获得的 ConstArray ，这样是极其有必要的，因为对于这种情况

const int a[2] = {1, 2};
const int b = a[1];
int main()
{
    int i = 2;
    a[i];
    return 0;
}

b 的初始值没法使用 load 访问，所以只能用常量形式获得，所以依然是需要 ConstArray 的。

3.4 局部常量数组

局部常量数组与全局常量数组类似，因为它也具有“变量”的访问形式，所以也不能仅仅在符号表中存入一个 ConstArray，而是需要利用 Alloca 分配一块内存，然后利用 gep, store （这么看比全局常量数组还有麻烦一些）将这片内存填写成正确的值。同时依然需要注意，就是我们还是需要在 Alloca 里面存入一个 ConstArray 的，这是因为我们依然需要像一个“常量”一样读取这个局部常量数组，比如说在一些常量初始化或者维度信息方面，所以还是需要存入 ConstArray 的。

3.5 全局单变量

需要当成一个 GlobalVariable 处理，这是因为必须给这个单变量开辟空间，这是因为我们有可能修改这个值。

3.6 全局变量数组

也需要当成一个 GlobalVariable 处理，似乎这里保证了初始值一定是常量。

全局变量声明中指定的初值表达式必须是常量表达式。

3.7 局部单变量

用 Alloca 处理，最后在符号表中存入的是一个指针。

3.8 局部变量数组

用 Alloca 处理，但是此时的 Alloca 是不需要像局部常量数组一样在里面存储一个 ConstArray 的，这是因为第一没有意义，第二不一定能办到。

四、符号的使用

4.1 写变量

写一个变量一般都是对于 LVal 进行操作，并不是可以写内存中的所有东西，这是因为常量是不允许写操作的，所以对于 LVal 获得的东西一定是一个指针（LVal 的本质就是在符号表中按照符号查询出对应的 Value ），然后利用 Store 指令就可以将内容写入，“写变量”这个过程本身十分简单。

比较复杂的是如何处理 LVal ，首先需要明白，对于 LVal.builIr 可以将其分为两类，一类是 canCalValue ，也就是常量形式的读（显然没有常量写），另外就是没有办法常量读的 build，对于第二种情况，除了在符号表中找到找到指针，对于数组指针，还涉及一些 gep 操作以找到正确的数组元素。

4.2 读变量

4.2.1 读变量用于表达式

当一个 LVal 用于表达式的时候（也就是参与运算的时候），可以分成两个情况讨论，如果是一个常量，那么就直接用就行了；如果是一个指针，那么就需要将其 Load 出来使用。

4.2.2 读变量用于实参

实参和表达式计算不同在于，他可能是一个指针。而因为 C 的指针与 llvm 是不同的，比如说同样一个一维数组 a[2] ，在 C 中为 int* ，而在 llvm 中，却是 [2 x i32]* 。而当参数位 int a[] 的时候，又要求 llvm 划为 int*，这就说需要控制 gep 的数量进行降维，同时对于为指针的变量，也不能一味的 load，这样有可能将原本的指针实参给 Load 出一个整型来。

五、短路求值

对于短路求值，并不是一件可有可无的事情，因为对于

if (1 == 2 && f())

如果没有短路求值，那么 f() 就会被指令，如果 f() 是一个有副作用的函数（也就是对内存写了），那么就会导致 bug 的出现，所以短路求值是必要的。

实现短路求值就是将

if (cond1 && cond2)

变成

if (cond1)
	if (cond2)

这样的结构，将

if (cond1 || cond2)

变成

if (cond1) {
    // then-block
} else {
    if (cond2) {
        // then-block
    } else {
        // else-block
    }
}

对于多个条件，只要确定好优先级，递归处理即可。

六、控制结构

控制结构就是通过制造 BasicBlock 来对数据流进行控制。

6.1 分支

ConditionNode 有两种可能，有无 else 决定了到底是 2 个 BasicBlock 或者是 3 个 BasicBlock。对于没有 else 的分支结构，只用一个三参数的 Br 就可以解决，对于有 else 的结构，只需要将 Br 的 falseBlock 调整为 else 对应的块即可。

6.2 循环

需要制作出 3 个块，分别为 condBlock, bodyBlock, nextBlock ，其中 condBlock 选择跳转到 bodyBlock 或者是 nextBlock （这个部分由 LOrExp, LAndExp 自动完成），bodyBlock 会无条件跳转到 condBlock。

6.3 Break & Continue & Return

这些指令面对的最大问题是为了满足基本块的定义，与这些指令所处同一基本块并位于这些指令之后的指令不应该得到翻译。我们可以直接做一个新的块，让其后的指令都依附与这个块，而入口块并没有到达这个块的方式，这样就完成了对其后指令的忽略。

此外，break, continue 都需要确定跳转的目标，break 会跳转到 nextBlock ，而 continue 会跳转到 condBlock ，但是因为循环存在嵌套结构，所以不同层的 break, continue 需要跳转到不同的层。所以在全局用一个栈维护该结构，如下所示

protected static final Stack<BasicBlock> loopCondBlockDown = new Stack<>();
protected static final Stack<BasicBlock> loopNextBlockDown = new Stack<>();

在循环的时候，进行出入栈操作

loopCondBlockDown.push(condBlock);
loopNextBlockDown.push(nextBlock);

// ...

loopNextBlockDown.pop();
loopCondBlockDown.pop();

在 break 中：

irBuilder.buildBr(curBlock, loopNextBlockDown.peek());

在 continue 中

irBuilder.buildBr(curBlock, loopCondBlockDown.peek());

钟鼓楼

编译技术-llvm生成