LLVM 学习笔记

为了引入 llvm，这里我们先从编译器慢慢说起

1. 编译器设计简介

传统静态编译器（如大多数 C 编译器）最流行的设计是三阶段设计，其主要组件是前端、优化器和后端。

前端解析源代码，检查错误，并构建特定于语言的抽象语法树 (AST) 来表示输入代码。AST 可选择转换为新的表示以进行优化，然后优化器和后端在代码上运行。

优化器负责进行各种转换，以尝试缩短代码的运行时间，例如消除冗余计算，并且通常或多或少独立于语言和目标。然后，后端（也称为代码生成器）将代码映射到目标指令集。除了生成正确的代码外，它还负责生成利用所支持架构的不寻常功能的良好代码。

编译器后端的常见部分包括指令选择、寄存器分配和指令调度。

这里可以思考一下为什么要将编译器设置为这种三阶段形式？

其实当编译器决定支持多种源语言或目标架构时，这种经典设计的最大优势就体现出来了。如果编译器在其优化器中使用通用代码表示，则可以为任何可以编译成该语言的语言编写前端，也可以为任何可以从该语言编译的目标编写后端，如下图所示。

采用这种设计，移植编译器以支持新的源语言（例如 Algol 或 BASIC）仅需要实现新的前端，但现有的优化器和后端可以重复使用。注意如果不将这些部分分开，实现新的源语言将需要从头开始，因此支持N目标和 M源语言将需要 N*M 个编译器，这显然是非常耗费人力的一件事。

三阶段设计的另一个优势是，实现前端所需的技能与优化器和后端所需的技能不同。将它们分开可以让“前端人员”更轻松地增强和维护他们的编译器部分。

2. 现有的语言实现

虽然前面这种三阶段设计的优点引人注意，但可惜的是在实践中从未充分实现，像 Glasgow Haskell Compiler (GHC) 和 FreeBASIC 这样的项目可以重新定位到多个不同的 CPU，但它们的实现非常特定于它们支持的一种源语言。

这种三阶段设计有三个比较成功的案例：

1. Java 和 .NET 虚拟机
2. 使用自己语言的源代码编译成C代码，然后再在各个平台调用C编译器来生成可执行程序
3. GCC 的实现

尽管上面三个案例是非常成功的，但其实上面三个案例也有很多局限性，因为它们往往是作为一个整体程序存在的，举个例子，将GCC嵌入到其他应用程序中、将GCC用作运行时/JIT编译器，或者在不引入大部分编译器的情况下提取和重用GCC的部分内容，这些都是不现实的。按我的理解就是程序内部耦合较高，难以分离做出一些方便优化的行为。

3. LLVM 介绍

再了解了前面的背景知识之后，我们就开始引入 LLVM，首先是它的概念：LLVM是一个编译器（确切的说是一套框架+基于框架的一些编译器实现，如clang），是当下很先进的一套编译系统。

LLVM之所以优秀，在于以下几点：

• LLVM的中间表达（IR）是可以dump出来成为可阅读的文本形式的（语法有点像汇编），看起来微不足道，但是其他很多编译器却只有内存中的数据结构，使得学习调试难度大增。
• 模块化的设计比较好，这一方面是后发优势，吸收了很多前人经验，也和设计者的架构功力息息相关。
• 虽然始于学术项目，但LLVM一直受到工业界的支持（Apple），所以不仅好用，而且开源可定制。

注意事项：LLVM 不只是用于实现新的编译器及编译优化！

基础架构：

下面这张图显示了 LLVM 架构的主要部件

这里对上图的一些核心组件做出一些解释：

• 前端，获取源代码并将其转换为中间表示或 IR。这种翻译简化了编译器其余部分的工作，它不想处理 C++ 源代码的全部复杂性。比如Clang
• 将 IR 转换为 IR的 Pass。在一般情况下，pass 通常会优化代码：生成一个 IR 程序作为输出，它与作为输入的 IR 执行相同的操作，只是它更快更优，这是需要拓展定制的地方。
• 后端，生成实际的机器码。

尽管这种架构描述了当今大多数编译器，但值得注意的是 LLVM 的一个新颖之处：整个编译过程中使用相同的 IR 。而在其他编译器中，每次传递都可能以独特的形式生成代码。

4. LLVM IR

从上图可以看到 IR 是作为整个架构器的中间表示，在这里即代表的是 LLVM IR，LLVM IR（Intermediate Representation）可以说是 LLVM 的最核心的一环，LLVM IR 旨在承载编译器优化器部分的分析和转换，LLVM IR 可以看做是一种类汇编语言，但是它拥有比汇编更好的易读性，还包括可定制。

LLVM IR 在设计时考虑了很多目标，包括支持轻量级运行时优化、跨函数/过程间优化、整个程序的分析以及重构转换等。然而，它最重要的方面是，它本身被定义为一种具有明确定义语义的一流语言。为了更具体地说明这一点，这里有一个简单的 .ll 文件示例：

define i32 @add1(i32 %a, i32 %b) {
entry:
  %tmp1 = add i32 %a, %b
  ret i32 %tmp1
}

define i32 @add2(i32 %a, i32 %b) {
entry:
  %tmp1 = icmp eq i32 %a, 0
  br i1 %tmp1, label %done, label %recurse

recurse:
  %tmp2 = sub i32 %a, 1
  %tmp3 = add i32 %b, 1
  %tmp4 = call i32 @add2(i32 %tmp2, i32 %tmp3)
  ret i32 %tmp4

done:
  ret i32 %b
}

这里我们先不具体说明 IR 的语法，只是先简单了解一下 LLVM IR 是什么，上面的 LLVM IR 实现了两个不同的加法功能，一个是直接对两个操作数进行相加，另外一个是实现递归相加，其实从直观上来看，LLVM IR 更像是一种 C语言和汇编语言的杂糅，如它支持这种C语言中显式的函数传参调用，又有类似汇编风格的指令。

上面的代码对应下图中的 C 代码：

unsigned add1(unsigned a, unsigned b) {
  return a+b;
}

// Perhaps not the most efficient way to add two numbers.
unsigned add2(unsigned a, unsigned b) {
  if (a == 0) return b;
  return add2(a-1, b+1);
}

LLVM具有严格的类型定义和简单的类型系统（例如，i32是32位整数，i32**是指向32位整数的指针的指针），并且抽象掉了机器的一些细节。例如，调用约定是通过call和ret指令以及显式参数来抽象的。LLVM IR与机器代码的另一个显著区别是，它不使用固定的一组命名寄存器，而是使用无限数量的以%字符命名的临时变量，你可以理解为 LLVM IR 中有无限寄存器，但是这些寄存器都是虚拟的。

4.1 写一个 LLVM IR 优化器

这里通过一些例子来直观感受优化的过程是如何进行的，在实际过程中有很多的优化技巧和方法，所以很难提出一个解决任何问题的方案，但是大多数优化都遵循下面三个部分：

• 寻找一个对应的匹配模式然后去转换
• 验证转换后的匹配实例是否安全
• 完成转换并更新代码

最基本的优化是算术恒等式的模式匹配，比如说对于变量 X，X-X 是 0, X-0 是 X, (X*2)-X 是 X，这几个操作所对应的 LLVM IR 指令如下

⋮    ⋮    ⋮
%example1 = sub i32 %a, %a
⋮    ⋮    ⋮
%example2 = sub i32 %b, 0
⋮    ⋮    ⋮
%tmp = mul i32 %c, 2
%example3 = sub i32 %tmp, %c
⋮    ⋮    ⋮

这些具体的转换处理在 SimplifySubInst 函数中，并具体表现如下：

// X - 0 -> X
if (match(Op1, m_Zero()))
  return Op0;

// X - X -> 0
if (Op0 == Op1)
  return Constant::getNullValue(Op0->getType());

// (X*2) - X -> X
if (match(Op0, m_Mul(m_Specific(Op1), m_ConstantInt<2>())))
  return Op1;
…
return 0;  // Nothing matched, return null to indicate no transformation.

在这段代码中，Op0 和 Op1 分别绑定到一个整数减法指令的左操作数和右操作数，LLVM 由 C++ 实现，但 C++ 并不以这种模式匹配能力而出名，但 C++ 中提供的模版系统可以让我们来实现类似的功能。比如说上面的 match 和 m_函数 都允许我们由 LLVM IR 匹配具体的模式，然后决定是否 return 返回优化后的结果。

一个简单的优化示例如下：

for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
  if (Value *V = SimplifyInstruction(I))
    I->replaceAllUsesWith(V);

SimplifyInstruction 完成指令层面的优化转化，replaceAllUsesWith 完成具体的指令替换过程。

4.2 LLVM 的三阶段优化实现

在基于 LLVM 的编译器中，前端负责解析、验证和诊断输入代码中的错误，然后将解析后的代码转换为 LLVM IR（通常但并非总是通过构建 AST 然后将 AST 转换为 LLVM IR）。此 IR 可选择经过一系列分析和优化过程以改进代码，然后发送到代码生成器以生成本机机器代码。分别对应下图中的三个阶段：

具体来说，LLVM IR 不仅规范明确，而且是优化器的唯一接口。此属性意味着，编写 LLVM 前端时，只需要知道 LLVM IR 是什么、它如何工作等。由于 LLVM IR 具有一流的文本格式，因此构建一个将 LLVM IR 输出为文本的前端，然后使用 Unix 管道将其发送到选择的优化器序列和代码生成器，是可能的也是合理的。

5. LLVM 特性介绍

LLVM的指令集抓住了通用处理器的关键操作，并且避免了与底层硬件的约束关联，它提供了无限数量的虚拟寄存器，可用于处理多种原类型，如布尔型、整型、浮点型、指针等。

虚拟寄存器采用静态单赋值形式（SSA），关于这个概念解释如下：

在编译器设计中，在静态单赋值形式SSA是程序语言中间表示IR的一个属性，它要求每个变量只能被赋值一次并且在使用之前定义，它的好处在于可以通过简化变量的属性来改进编译器优化的结果。

以如下代码为例。

y := 1
y := 2
x := y

转换为SSA形式如下：

y1 := 1
y2 := 2
x1 := y2

LLVM是一种load/store架构：程序仅通过使用类型化指针的加载和存储操作，在寄存器和内存之间传输值。其中，load指令从内存中取值加载到寄存器，store指令将寄存器的值存储到内存中。

完整的LLVM指令集仅包含为数不多的操作码，LLVM采用较少的指令集一方面是避免多个操作码执行同样的操作，另一方面是大多数的操作码实际上是过载的，例如add加法指令可以对任意整型或浮点型的操作数执行计算。

5.1 语言无关类型系统

cast，getelementptr指令

LLVM类型系统包含了预定义大小的原类型，例如void、bool、有符号或无符号的integer、单精度或双精度的float等，且只有4种派生类型：pointer、array、strut和function。

LLVM IR是一种强类型的语言，它要求所有变量都必须明确指定其类型，包括局部变量、全局变量，寄存器地址、内存地址等。cast指令用于将某个值的类型转换成任意类型，且是唯一进行类型转换的方式，这使得所有类型的变化过程都是显式的且能够追踪的。

getelementptr指令将内存指针算术化，既保留了类型信息又具有与机器无关的语义。给定一个指向聚合类型对象的内存指针，该指令能保留计算该对象子元素地址的行为，可有效使用[]来选取数组的指定项以及使用.来选取结构体的指定元素。例如C语言中的X[i].a = 1语句，可转换为如下LLVM指令：

%p = getelement %xty* %X, long %i, ubyte 3;
store int 1, int* %p;

其中，假设a是结构体X[i]的第3个元素，结构体的类型为%xty，所有变量的类型都是显式的。上述的第一条指令获得X[i].a元素的地址分配到虚拟寄存器%p，第二条指令通过store操作将int类型的值1存入到%p指向的内存地址中。

5.2 显式的内存分配和统一的内存模型

在C语言中，malloc函数会在堆上分配一个或多个指定类型的内存空间并返回相应类型的指针，而free函数则搭配进行内存空间的释放。LLVM使用类似的指令alloca完成类似的操作，不同的是该指令是在当前函数的栈上划分内容空间而不是堆，所有栈相关的数据都必须显式地通过该指令进行内存空间分配。另外，全局变量和函数定义都定义在一张符号表中，并且提供对象地址而非对象自身进行使用，从而LLVM实现了一个统一的内存模型

5.3 函数调用和异常捕获

LLVM使用invoke和unwind两个指令共同实现了抽象的异常捕获模型，invoke指令与call指令类似但指定一个特殊的程序基本块，当程序执行到unwind指令时它将堆栈恢复且从invoke指令指定的标签处跳转，可以很清晰地看到异常操作的程序控制流。高级语言使用的try/catch代码块从而可以很直接地用这两个指令来进行实现，任何函数内部遇到try关键字时将被编译为invoke指令，而当程序catch到某个抛出的异常时将调用unwind指令继续执行。在16.0.0版本的LLVM项目中，unwind指令被替换成了resume指令

5.4 纯文本、二进制和内存表示

LLVM IR是一种对文本、二进制、内存进行平等表示的一阶语言，指令集采用可持久且离线的设计，使得其不需要在不同编译环节进行语义转换。中间表示在进行分析和转换时不会发生信息丢失，这使得程序调试变得更加简单，而且也降低了对内存表示的理解和学习门槛。

6. LLVM 实践

安装 LLVM 编译器框架，安装比较简单，直接执行下面几个指令即可

wget https://apt.llvm.org/llvm.sh
chmod +x llvm.sh
sudo ./llvm.sh 16 all

一个 hello world 程序

test.c 文件如下：

int main() {
    return 1;
}

将其编译为LLVM IR，执行命令如下：

$ clang-16 -S -emit-llvm test.c

会生成一个test.ll文件，内容如下：

clang-16 main.ll -o main
./main
echo $?

我们可以对上面的流程进行分解

前端的语法分析

首先，Clang的前端编译器会将这个C语言的代码进行预处理、语法分析、语义分析，把前面的 test.c 执行下面的指令

clang-16 -Xclang -ast-dump -fsyntax-only test.c

test.c经过编译器前端的预处理、语法分析、语义分析之后，生成的抽象语法树（AST）：

|-FunctionDecl 0x64f45bb19b58 </usr/include/stdio.h:885:1, col:27> col:12 __uflow 'int (FILE *)' extern
| `-ParmVarDecl 0x64f45bb19ac0 <col:21, col:26> col:27 'FILE *'
|-FunctionDecl 0x64f45bb19dc0 <line:886:1, col:35> col:12 __overflow 'int (FILE *, int)' extern
| |-ParmVarDecl 0x64f45bb19c20 <col:24, col:29> col:30 'FILE *'
| `-ParmVarDecl 0x64f45bb19ca0 <col:32> col:35 'int'
`-FunctionDecl 0x64f45bb19ed0 <test.c:3:1, line:5:1> line:3:5 main 'int ()'
  `-CompoundStmt 0x64f45bb19fa8 <col:11, line:5:1>
    `-ReturnStmt 0x64f45bb19f98 <line:4:2, col:9>
      `-IntegerLiteral 0x64f45bb19f78 <col:9> 'int' 4

核心内容只需要关注后面四个部分，经过 clang 前端的处理，源代码被分析成一个函数 FunctionDecl，其中包含一个复合语句，复合语句中又包含一个返回语句，返回语句中又使用了一个整型字面量 0。

前端生成中间代码

第二个步骤，就是根据内存中的抽象语法树AST生成LLVM IR中间代码

clang -S -emit-llvm test.c

会生成一个 test.ll 文件，这一部分实际上在前面有介绍，内容如下，由 LLVM IR 构成

; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  ret i32 4
}

attributes #0 = { noinline nounwind optnone uwtable "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3, !4}
!llvm.ident = !{!5}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{i32 7, !"frame-pointer", i32 2}
!5 = !{!"Ubuntu clang version 16.0.6 (++20231112100510+7cbf1a259152-1~exp1~20231112100554.106)"}

上面的代码乍一看有点多，但是我们看它的核心内容即可

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  ret i32 4
}

这是AST转化为LLVM IR中最核心的部分

LLVM 后端优化 IR

LLVM后端优化 IR 是由opt这个组件完成的，该工具会根据输入的LLVM IR和相应的优化等级，进行优化，并输出对应的LLVM IR。

opt test.ll -S --O3

上面的指令我在尝试的时候报错了，但是也可以从源代码直接进行优化

clang-16 -S -emit-llvm -O3 test.c

这时候我们再来看生成后的优化代码相较于前面发生了哪些变化

; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local i32 @main() local_unnamed_addr #0 {
  ret i32 4
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3}
!llvm.ident = !{!4}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{!"Ubuntu clang version 16.0.6 (++20231112100510+7cbf1a259152-1~exp1~20231112100554.106)"}

可以看到核心部分仅仅变为了 1 行。

define dso_local i32 @main() local_unnamed_addr #0 {
  ret i32 4
}

LLVM 后端生成汇编代码

llc test.ll

这里不知道啥原因产生了报错，但是我对另外一个直接由 LLVM IR 写的 main.ll 文件可以成功生成汇编代码

LLVM IR

LLVM IR同时表示了三种东西：

• 内存中的LLVM IR
• 比特码形式的LLVM IR
• 可读形式的LLVM IR

内存中的LLVM IR是编译器处理最本质的形式，其中比特码形式和可读形式则是将内存中的LLVM IR持久化的方法。

生成可读形式的LLVM IR文件test.ll，如下

clang -S -emit-llvm test.c

生成比特码形式的LLVM IR文件test.bc，如下

clang -c -emit-llvm test.c

将比特码test.bc转化为可读形式的test.ll

llvm-dis test.bc

7. 总结

这篇文章主要是想把 LLVM 介绍的清楚一点，并没有过多的纠缠于一些细节，如 LLVM IR 的具体指令语法，编写 LLVM PASS 等等，后面可以尝试来进行下一步分析

Reference

• https://aosabook.org/en/v1/llvm.html
• https://zhuanlan.zhihu.com/p/472813616
• https://zhuanlan.zhihu.com/p/689798611