透过 LLVM IR 窥探编译优化——编译器会帮你做些什么？
This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International License.
本文使用 知识共享 署名—相同方式共享 4.0 协议国际版 进行授权。
阅读 PDF 原文以获得更好的阅读体验。
前言
在使用各种编程语言编写程序的时候，我们往往需要与各种编译器打交道。对于 C/C++、Rust 等编程语言，它们的编译器（从用户角度上）直接将源代码翻译为目标平台的机器代码，使目标平台可以直接运行编译好的程序；对于 Python、C#、Java 等编程语言，它们的编译器将源代码翻译为它们各自的中间代码，并通过各自的虚拟机或运行时环境运行。总之，编译器所做的，就是将人类读起来写起来很舒服的高级语言代码，翻译为更低级的代码，使得计算机能够理解这些代码并运行。
编译器在编译源代码的时候，往往可以做一些行为上的“恒等替换”，使得程序的执行效率更高、占用空间更低，我们把这个过程叫编译优化。编译优化是编译原理中非常重要而庞大的一个分支，其所应用到的算法与数据结构、数学建模等都非常复杂。一般来讲，对于大多数程序员来说，只需要知道编译器会对你的代码进行哪些优化即可。具体的优化方法和实现，就交给那些在编译原理领域发光发热的“语言黑客”们吧。
本文将给你介绍几种常见的编译优化，包括但不限于常量折叠、函数内联、参数提升、死代码消除等。我们将使用 C 和 LLVM IR 进行讲述。
本文假定你有一定的 C 语言（或 C++ 语言）基础，但不要求你有 LLVM IR 的知识。LLVM IR 是一种中间语言，由 LLVM 后端（backend）编译为目标平台的机器代码。它有些类似于 RISC（精简指令集计算机）指令集，比较接近底层汇编指令，但又保留了一定的高级功能。LLVM IR 有很高的可读性，通常情况下可以在两天内掌握绝大多数指令，并能够阅读或手写一些代码。
本文不要求你有 LLVM IR 的知识基础，使用 LLVM IR 只是为了让编译优化的结果更加明显、透明。本文中出现的未优化的 LLVM IR 代码将附上 C 语言代码描述。LLVM IR 代码中也会附上大量注释标明每条指令的行为。因此，你完全可以不学习 LLVM IR 阅读本文。当然，如果你学习过，这是更好的。
本文使用的 LLVM 版本是 LLVM 22。如果你想自己尝试，建议使用 20 及以上的版本。
不过，在开始之前，需要补充一个内容：控制流的底层表示。LLVM IR 没有明显的控制流，仅保留了跳转指令，用于在一个基本块（basic block）末尾跳转至另一个基本块开头。为了更好地阅读和理解本文中的 LLVM IR 代码（的注释），你需要大概了解控制流是如何使用在只使用跳转指令的情况下实现的。这其实很好理解，将各种控制流的流程图画出来即可。你也可以搜索一些资料，看看在 C 语言中，如何使用 goto 语句来实现其他的控制流语句。当然，在实际应用中，不建议使用 goto 语句。
常见编译优化
我们马上来看看常见的编译优化，以及这些优化在 LLVM IR 中的体现。
我们将手写一些 LLVM IR 代码（以及说明用的对应的 C 代码），并通过以下命令将我们手写的 LLVM IR 代码（假如名为 main.ll）进行优化：
opt -O2 -S main.ll -o main-opt.ll其中 -O2 表示我们使用最常用的 O2 优化等级；-S 表示输出 LLVM IR 源代码（不然会输出二进制字节码）；-o 用于指定输出文件。
没有特殊说明的情况下，我们的优化命令就是上面那一条。大多数情况下，给出的优化后的代码会剔除掉一些我们不需要的、不影响理解优化效果的代码和注释。
常量折叠
常量折叠指的是在编译时计算一些常量表达式，减少运行时的指令数量。下面的 C 语言代码是一个最简单的例子：
int test() {
return (1 + 1) * 2 * 8 / 4 - 5;
}我们可以将其翻译成 LLVM IR 代码（这里是手动翻译，不是 Clang 编译器生成的结果）：
define i32 @test() {
%a = add i32 1, 1 ; a = 1 + 1
%b = mul i32 %a, 2 ; b = a * 2
%c = mul i32 %b, 8 ; c = b * 8
%d = sdiv i32 %c, 4 ; d = c / 4
%e = sub i32 %d, 5 ; e = d - 5
ret i32 %e ; return e
}:::info[提示：LLVM IR 注释]
LLVM IR 的注释使用分号（;）来标注。这是从汇编语言中遗传下来的习惯。
:::
运行之前我们提到的优化命令，可以得到优化后的代码（剔除了部分无关代码）：
define noundef i32 @test() local_unnamed_addr #0 {
ret i32 3
}这里我们只需要关心 test 函数内部的变化：编译器将仅含有常量的表达式在编译时计算好了，并直接返回结果。
常量折叠还有更强大的形式。下面是另一个例子：
int max(int a, int b) {
return (a > b) ? a : b;
}
int test() {
return max(10, 20);
}define i32 @max(i32 %a, i32 %b) {
%cmp = icmp sgt i32 %a, %b ; cmp = a > b
%res = select i1 %cmp, i32 %a, i32 %b ; res = cmp ? a : b
ret i32 %res ; return res
}
define i32 @test() {
%res = call i32 @max(i32 10, i32 20) ; res = max(10, 20)
ret i32 %res ; return res
}这里我们手写了一个 max 函数，用于求最大值。优化后的结果是：
define i32 @max(i32 %a, i32 %b) local_unnamed_addr #0 {
%res = tail call i32 @llvm.smax.i32(i32 %a, i32 %b)
ret i32 %res
}
define noundef i32 @test() local_unnamed_addr #0 {
ret i32 20
}
declare i32 @llvm.smax.i32(i32, i32) #1重点看 test 函数内部的变化：它直接返回了 20！
另外，可以观察到，我们手写的 max 函数被替换为了 LLVM 自己提供的最大值函数。LLVM 提供的内置函数很少，但都是非常高效的。
再看另一个：
int get_sign(int num) {
if (num > 0) {
return 1;
} else if (num < 0) {
return -1;
} else {
return 0;
}
}
int test() {
return get_sign(-10);
}define i32 @get_sign(i32 %num) {
%cmp_gt = icmp sgt i32 %num, 0 ; cmp_gt = num > 0
%cmp_lt = icmp slt i32 %num, 0 ; cmp_lt = num < 0
br i1 %cmp_gt, label %gt_body, label %lt_cond ; cmp_gt: true -> gt_body, false -> lt_cond
gt_body:
ret i32 1 ; return 1
lt_cond:
br i1 %cmp_lt, label %lt_body, label %ret_0 ; cmp_lt: true -> lt_body, false -> ret_0
lt_body:
ret i32 -1 ; return -1
ret_0:
ret i32 0 ; return 0
}
define i32 @test() {
%res = call i32 @get_sign(i32 -10) ; res = get_sign(-10)
ret i32 %res
}优化后的代码：
define noundef range(i32 -1, 2) i32 @test() local_unnamed_addr #0 {
ret i32 -1
}我们可以观察到：test 函数直接返回了 -1！
还有更多的常量折叠：
int fib(int n) {
if (n == 1 || n == 2) {
return 1;
}
int first = 1;
int second = 1;
for (int i = 3; i <= n; i++) {
int temp = first;
first = second;
second += temp;
}
return second;
}
int test() {
return fib(10);
}define i32 @fib(i32 %n) {
%cond.1 = icmp eq i32 %n, 1 ; cond_1 = n == 1
%cond.2 = icmp eq i32 %n, 2 ; cond_2 = n == 2
%cond = or i1 %cond.1, %cond.2 ; cond = cond_1 || cond_2
br i1 %cond, label %ret_1, label %ret_loop ; cond: true -> ret_1, false -> ret_loop
ret_1:
ret i32 1 ; return 1
ret_loop:
%first = alloca i32 ; int first
%second = alloca i32 ; int second
store i32 1, i32* %first ; 1 -> first
store i32 1, i32* %second ; 1 -> second
br label %for_init
for_init:
%i = alloca i32 ; int i
store i32 3, i32* %i ; 3 -> i
br label %for_cond
for_cond:
%i.value = load i32, i32* %i ; i.value <- i
%cond.for = icmp sle i32 %i.value, %n ; cond.for = i.value <= n
br i1 %cond.for, label %for_body, label %for_end
for_body:
%temp = load i32, i32* %first ; temp <- first
%second.value = load i32, i32* %second ; second.value <- second
store i32 %second.value, i32* %first ; second.value -> first
%sum = add i32 %temp, %second.value ; sum = temp + second.value
store i32 %sum, i32* %second ; sum -> second
br label %for_incr
for_incr:
%i.old = load i32, i32* %i ; i.old <- i
%i.new = add i32 %i.old, 1 ; i.new = i.old + 1
store i32 %i.new, i32* %i ; i.new -> i
br label %for_cond
for_end:
%result = load i32, i32* %second ; result <- second
ret i32 %result ; return result
}
define i32 @test() {
%res = call i32 @fib(i32 10) ; res = fib(10)
ret i32 %res ; return res
}优化后的代码为：
define noundef i32 @test() local_unnamed_addr #1 {
fib.exit:
ret i32 55
}可以看到，编译器直接返回结果 55。
内联函数
对于简短的函数，LLVM 为了减少函数调用开销，可能直接将函数内联到调用处。你可以将内联理解为将被调用函数的代码移植到调用处。
下面是一个最简单的例子：
int add(int a, int b) {
return a + b;
}
int test(int n) {
return add(add(n, 1), 3);
}define i32 @add(i32 %a, i32 %b) {
%res = add i32 %a, %b ; res = a + b
ret i32 %res ; return res
}
define i32 @test(i32 %n) {
%a = call i32 @add(i32 %n, i32 1) ; a = add(n, 1)
%b = call i32 @add(i32 %a, i32 3) ; b = add(a, 3)
ret i32 %b ; return b
}优化后代码将变成：
define i32 @add(i32 %a, i32 %b) local_unnamed_addr #0 {
%res = add i32 %b, %a
ret i32 %res
}
define i32 @test(i32 %n) local_unnamed_addr #0 {
%res.i1 = add i32 %n, 4
ret i32 %res.i1
}我们可以看到：add 函数的功能被内联到 test 函数中，且编译器还顺便进行了常量折叠。
更复杂的例子也同理。总之，如果 LLVM 认为函数调用开销相较于代码体积来说前者的损失更大，则 LLVM 就会内联函数。
消除内部无用函数
我们将上面那一节的例子稍微改一下，将 add 的链接性改为内部的：
static int add(int a, int b) {
return a + b;
}
int test(int n) {
return add(add(n, 1), 3);
}define internal i32 @add(i32 %a, i32 %b) {
%res = add i32 %a, %b ; res = a + b
ret i32 %res ; return res
}
define i32 @test(i32 %n) {
%a = call i32 @add(i32 %n, i32 1) ; a = add(n, 1)
%b = call i32 @add(i32 %a, i32 3) ; b = add(a, 3)
ret i32 %b ; return b
}优化后会变成这样：
define i32 @test(i32 %n) local_unnamed_addr #0 {
%res.i1 = add i32 %n, 4
ret i32 %res.i1
}是的，add 函数消失了！
内部链接性的函数只在该文件（LLVM 中的模块）内使用，不会暴露给外界，因此不必担心删除函数导致外部无法使用和链接的情况。在这个例子中，LLVM 将 add 函数内联，然后发现整个模块中再也没有用到过这个内部链接性的函数 add，于是就将其删除。
在上一节的例子中，add 是默认的外部链接性。即使 LLVM 发现该函数在该模块内部没有使用，也不能删除，否则可能导致外部的其他模块无法找到并链接该函数。
栈变量提升到寄存器
我们知道，局部变量存储在函数的栈帧上，也就是该函数调用的栈内存上。但是，我们知道，对于一些经常操作的简单数据，放在寄存器中可以明显加快运行速度。
LLVM IR 中使用 % 符号标记一个虚拟寄存器。LLVM IR 中的虚拟寄存器是不限数量的，在 LLVM 后端编译器编译的时候会视情况（目标平台、空闲寄存器、数据大小等）选择将虚拟寄存器放在真实的寄存器中，或者放在栈上。此外，LLVM IR 使用 alloca 指令在栈上分配内存，以供局部变量使用。
按照上面的说法，我们应该尽量将 alloca 指令分配的栈变量提升到 LLVM IR 虚拟寄存器中，以让编译器为其提供一个放在真实寄存器上的机会。哪怕提升后，后端编译器发现条件不合适，还是把它放在栈上，我们也能够尽可能地多提供一些放在寄存器上的机会。
所以目标很明显：优化代码，将能从 alloca 指令提升到虚拟寄存器的所有值都进行提升优化。
来看一个例子：
:::info[提示：LLVM IR 指针类型与 alloca 指令]
在 LLVM IR 中，在一个类型名称（如 i32、i64 等）后面添加一个星号（*），就可以将其变为指向该类型的指针类型。
alloca 指令返回一个指针，指向分配的栈内存位置。随后可以通过这个指针和 load（加载）、store（存储）指令来读写这块内存。 |
|---|
int get_value();
void use_value(int);
void test() {
int var = get_value();
var *= 2;
use_value(var);
}declare i32 @get_value()
declare void @use_value(i32)
define void @test() {
%var = alloca i32 ; 分配栈内存
; %var 是 i32*（指向 i32 的指针）
%ret_get = call i32 @get_value() ; ret_get = get_value()
store i32 %ret_get, i32* %var ; ret_get -> var
%var.old = load i32, i32* %var ; var.old <- var
%var.new = mul i32 %var.old, 2 ; var.new = var.old * 2
store i32 %var.new, i32* %var ; var.new -> var
%var.value = load i32, i32* %var ; var.value <- var
call void @use_value(i32 %var.value) ; use_value(var.value)
ret void
}很明显，我们自己都能看到这段代码中性能不高的地方：存储值之后又马上取出值。但是这段代码是对 C 代码最直接的翻译，很多前段编译器都是这么做的。
另外，我们声明了两个函数：get_value 和 use_value。这两个函数用于做获取初始值和使用值的占位符，避免编译器进行过度常量折叠和无用代码消除。
我们来看看优化结果：
define void @test() local_unnamed_addr {
%ret_get = tail call i32 @get_value()
%var.new = shl i32 %ret_get, 1
tail call void @use_value(i32 %var.new)
ret void
}可以看到优化效果：所有与栈内存相关的指令被删除，并直接使用虚拟寄存器进行存储。
如果你想看看这份代码编译后是不是真的使用了真实的寄存器，可以将其编译为汇编代码。使用下面这条命令将优化后的代码 main-opt.ll 编译到汇编代码：
llc main-opt.ll -o main.s下面是它在我的计算机上的输出（Intel x86-64 AT&T 格式）：
.file "main.ll"
.text
.globl test # -- Begin function test
.p2align 4
.type test,@function
test: # @test
.cfi_startproc
# %bb.0:
pushq %rax
.cfi_def_cfa_offset 16
callq get_value@PLT
# kill: def $eax killed $eax def $rax
leal (%rax,%rax), %edi
popq %rax
.cfi_def_cfa_offset 8
jmp use_value@PLT # TAILCALL
.Lfunc_end0:
.size test, .Lfunc_end0-test
.cfi_endproc
# -- End function
.section ".note.GNU-stack","",@progbits可以看到，除了根据调用协议需要将 %rax 寄存器备份在栈上以外，没有使用栈内存的地方。
需要注意的是，这种优化要求该变量没有被取指针。如果有取指针操作，那么变量必须有一个内存地址，它就必须被放在栈上。
下面是对上面的例子的修改：
int get_value();
void use_value(int*);
void test() {
int var = get_value();
var *= 2;
use_value(&var);
}declare i32 @get_value()
declare void @use_value(i32*)
define void @test() {
%var = alloca i32 ; 分配栈内存
; %var 是 i32*（指向 i32 的指针）
%ret_get = call i32 @get_value() ; ret_get = get_value()
store i32 %ret_get, i32* %var ; ret_get -> var
%var.old = load i32, i32* %var ; var.old <- var
%var.new = mul i32 %var.old, 2 ; var.new = var.old * 2
store i32 %var.new, i32* %var ; var.new -> var
call void @use_value(i32* %var) ; use_value(var)
ret void
}那么优化后的代码是：
declare i32 @get_value() local_unnamed_addr
declare void @use_value(ptr) local_unnamed_addr
define void @test() local_unnamed_addr {
%var = alloca i32, align 4
%ret_get = tail call i32 @get_value()
%var.new = shl i32 %ret_get, 1
store i32 %var.new, ptr %var, align 4
call void @use_value(ptr nonnull %var)
ret void
}可以看到，编译器依然保留了 alloca 指令，但是简化了存取指令。
控制流优化
一个程序通常拥有很复杂的控制流。如果编译器能够优化控制流（合并分支、优化跳转等），必然能够带来很大的性能提升。
下面是一个非常简单的例子：
void func_a(int num);
void func_b(int num);
void func_c(int num);
void func_d(int num);
void test(int num) {
if (num > 0) {
func_a(num);
} else {
func_b(num);
}
if (num <= 0) {
func_c(num);
} else {
func_d(num);
}
}declare void @func_a(i32)
declare void @func_b(i32)
declare void @func_c(i32)
declare void @func_d(i32)
define void @test(i32 %num) {
if_cond_gt:
%cond_gt = icmp sgt i32 %num, 0 ; cond_gt = num > 0
br i1 %cond_gt, label %body_a, label %body_b ; cond_gt: true -> body_a, false -> body_b
body_a:
call void @func_a(i32 %num) ; func_a(num)
br label %if_end ; -> if_end
body_b:
call void @func_b(i32 %num) ; func_b(num)
br label %if_end ; -> if_end
if_end:
br label %if_cond_le ; -> if_cond_le
if_cond_le:
%cond_le = icmp sle i32 %num, 0 ; cond_ge = num >= 0
br i1 %cond_le, label %body_c, label %body_d ; cond_le: true -> body_c, false -> body_d
body_c:
call void @func_c(i32 %num) ; func_c(num)
br label %ret ; -> ret
body_d:
call void @func_d(i32 %num) ; func_d(num)
br label %ret ; -> ret
ret:
ret void
}优化后的代码是：
define void @test(i32 %num) local_unnamed_addr {
if_cond_gt:
%cond_gt = icmp sgt i32 %num, 0
br i1 %cond_gt, label %body_d, label %body_c
body_c: ; preds = %if_cond_gt
tail call void @func_b(i32 %num)
tail call void @func_c(i32 %num)
br label %ret
body_d: ; preds = %if_cond_gt
tail call void @func_a(i32 %num)
tail call void @func_d(i32 %num)
br label %ret
ret: ; preds = %body_d, %body_c
ret void
}可以看到，LLVM 编译器推断出了：在这个函数中，事实上只有两条分支。而 LLVM 也通过优化将这两条分支进行了合并。
我们再把前面“常量折叠”那一节的斐波那契数列函数搬过来：
int fib(int n) {
if (n == 1 || n == 2) {
return 1;
}
int first = 1;
int second = 1;
for (int i = 3; i <= n; i++) {
int temp = first;
first = second;
second += temp;
}
return second;
}define i32 @fib(i32 %n) {
%cond.1 = icmp eq i32 %n, 1 ; cond_1 = n == 1
%cond.2 = icmp eq i32 %n, 2 ; cond_2 = n == 2
%cond = or i1 %cond.1, %cond.2 ; cond = cond_1 || cond_2
br i1 %cond, label %ret_1, label %ret_loop ; cond: true -> ret_1, false -> ret_loop
ret_1:
ret i32 1 ; return 1
ret_loop:
%first = alloca i32 ; int first
%second = alloca i32 ; int second
store i32 1, i32* %first ; 1 -> first
store i32 1, i32* %second ; 1 -> second
br label %for_init
for_init:
%i = alloca i32 ; int i
store i32 3, i32* %i ; 3 -> i
br label %for_cond
for_cond:
%i.value = load i32, i32* %i ; i.value <- i
%cond.for = icmp sle i32 %i.value, %n ; cond.for = i.value <= n
br i1 %cond.for, label %for_body, label %for_end
for_body:
%temp = load i32, i32* %first ; temp <- first
%second.value = load i32, i32* %second ; second.value <- second
store i32 %second.value, i32* %first ; second.value -> first
%sum = add i32 %temp, %second.value ; sum = temp + second.value
store i32 %sum, i32* %second ; sum -> second
br label %for_incr
for_incr:
%i.old = load i32, i32* %i ; i.old <- i
%i.new = add i32 %i.old, 1 ; i.new = i.old + 1
store i32 %i.new, i32* %i ; i.new -> i
br label %for_cond
for_end:
%result = load i32, i32* %second ; result <- second
ret i32 %result ; return result
}非常庞大的代码，还用到了很多栈内存分配。交给编译器优化，我们会得到：
define i32 @fib(i32 %n) local_unnamed_addr #0 {
%or.cond = icmp slt i32 %n, 3
br i1 %or.cond, label %common.ret, label %for_body
common.ret: ; preds = %for_body, %0
%common.ret.op = phi i32 [ 1, %0 ], [ %sum, %for_body ]
ret i32 %common.ret.op
for_body: ; preds = %0, %for_body
%storemerge6 = phi i32 [ %i.new, %for_body ], [ 3, %0 ]
%second.value15 = phi i32 [ %sum24, %for_body ], [ 1, %0 ]
%sum24 = phi i32 [ %sum, %for_body ], [ 1, %0 ]
%sum = add i32 %sum24, %second.value15
%i.new = add i32 %storemerge6, 1
%cond.for.not = icmp sgt i32 %i.new, %n
br i1 %cond.for.not, label %common.ret, label %for_body
}可以看到，指令数量大幅减少，基本块也减少了一些，跳转指令只剩下两条（ret 不算跳转指令，但是算终止指令），还把栈变量都提升到了虚拟寄存器中。
:::info[拓展：关于 Phi 节点]
Phi 节点（phi 指令）是用于解决 SSA（静态单赋值）系统中对某个变量进行反复赋值的问题的核心解决方案。
上面的代码中，有很多变量需要变化：i、first、second 等。然而，LLVM IR 的虚拟寄存器是 SSA 的，我们无法改变它们的值，因此只能存储在栈上，通过 load 和 store 指令取出和存储值。LLVM 后端编译器为了将这些栈变量提升到虚拟寄存器中（以及简化控制流），就使用 phi 指令解决了多次赋值的问题。
phi 的作用，就是根据跳转到当前基本块的上一个基本块，来选择它产生的值。phi 指令必须在一个基本块的开头使用，因为它是连接多个基本块、在基本块中传递数据的核心指令。 |
|---|
死代码消除
无论在什么情况下程序都不会执行的代码叫做死代码。死代码可以被删除，以减少代码体积。
我们来看一个简单的例子：
void fn_a();
void fn_b();
void fn_c(int);
void test(int num) {
int res;
if (num <= 0) {
fn_a();
res = 1;
} else {
fn_b();
res = 2;
}
if (res < 0) {
fn_c(res);
}
}declare void @fn_a()
declare void @fn_b()
declare void @fn_c(i32)
define void @test(i32 %num) {
%res = alloca i32 ; int res
%cond = icmp sle i32 %num, 0 ; cond = num <= 0
br i1 %cond, label %then_branch, label %else_branch ; cond: true -> then_branch, false -> else_branch
then_branch:
call void @fn_a() ; fn_a()
store i32 1, i32* %res ; 1 -> res
br label %if_end ; -> if_end
else_branch:
call void @fn_b() ; fn_b()
store i32 2, i32* %res ; 2 -> res
br label %if_end ; -> if_end
if_end:
%res.value = load i32, i32* %res ; res.value <- res
%cond.c = icmp slt i32 %res.value, 0 ; cond.c = res.value < 0
br i1 %cond.c, label %call_c, label %ret ; cond.c: true -> call_c, false -> ret
call_c:
call void @fn_c(i32 %res.value) ; fn_c(res.value)
br label %ret ; -> ret
ret:
ret void
}优化后的代码是：
declare void @fn_a() local_unnamed_addr
declare void @fn_b() local_unnamed_addr
define void @test(i32 %num) local_unnamed_addr {
%cond = icmp slt i32 %num, 1
br i1 %cond, label %then_branch, label %else_branch
then_branch: ; preds = %0
tail call void @fn_a()
br label %ret
else_branch: ; preds = %0
tail call void @fn_b()
br label %ret
ret: ; preds = %then_branch, %else_branch
ret void
}我们可以看到，在原程序中，变量 res 的值只可能是 1 或 2，无论如何都不可能是负数，因此最后一个 if 分支永远都不会执行。LLVM 检测到了这一点，直接将最后一个分支的代码删除。死代码消除后，LLVM 还顺带发现了无用的 res，从而将其删除。
乘除法的优化
我们知道，在现代计算机架构中，乘法和除法通常需要很多个 CPU 周期来执行，远不如加减法和位运算。因此，如果我们能使用位运算和加减法达到和原来的乘除法一样的效果，能带来一定的性能提升。LLVM 同样会做这样的优化。
但是需要注意的是，在现代 CPU 架构中，乘法大约只需要 3 个周期。因此，如果 LLVM 发现优化后的代码反而不如直接算乘法，就会不优化。更激进的优化会在编译为真正的汇编代码的时候进行，那时 LLVM 可以根据目标架构的特性选择优化。
来看一个非常简单的例子：
unsigned test1(unsigned num) {
return num * 2;
}
unsigned test2(unsigned num) {
return num / 2;
}
unsigned test3(unsigned num) {
return num * 7;
}
unsigned test4(unsigned num) {
return num * 10;
}
unsigned test5(unsigned num) {
return num % 2;
}
unsigned test6(unsigned num) {
return num % 10;
}define i32 @test1(i32 %num) {
%res = mul i32 %num, 2 ; res = num * 2
ret i32 %res ; return res
}
define i32 @test2(i32 %num) {
%res = udiv i32 %num, 2 ; res = num / 2
ret i32 %res ; return res
}
define i32 @test3(i32 %num) {
%res = mul i32 %num, 7 ; res = num * 7
ret i32 %res ; return res
}
define i32 @test4(i32 %num) {
%res = mul i32 %num, 10 ; res = num * 10
ret i32 %res ; return res
}
define i32 @test5(i32 %num) {
%res = urem i32 %num, 2 ; res = num % 2
ret i32 %res ; return res
}
define i32 @test6(i32 %num) {
%res = urem i32 %num, 10 ; res = num % 10
ret i32 %res ; return res
}由于有符号数在进行乘除运算的时候，与直接位运算和加减法相比，存在一定差异。为方便演示，这里使用无符号数。
优化后的代码是：
define range(i32 0, -1) i32 @test1(i32 %num) local_unnamed_addr #0 {
%res = shl i32 %num, 1 ; res = num << 1
ret i32 %res
}
define range(i32 0, -2147483648) i32 @test2(i32 %num) local_unnamed_addr #0 {
%res1 = lshr i32 %num, 1 ; res = num >> 1
ret i32 %res1
}
define i32 @test3(i32 %num) local_unnamed_addr #0 {
%res = mul i32 %num, 7
ret i32 %res
}
define i32 @test4(i32 %num) local_unnamed_addr #0 {
%res = mul i32 %num, 10
ret i32 %res
}
define range(i32 0, 2) i32 @test5(i32 %num) local_unnamed_addr #0 {
%res = and i32 %num, 1 ; res = num & 1
ret i32 %res
}
define range(i32 0, 10) i32 @test6(i32 %num) local_unnamed_addr #0 {
%res = urem i32 %num, 10
ret i32 %res
}可以看到，LLVM 对部分运算进行了优化：将简单的乘除 2 优化为位移运算，将模 2 的运算优化为按位与运算。
而其他运算，LLVM 则交给更后端的编译器，因为 LLVM 中端（opt 命令所在的端，仅处理 IR，不负责具体机器指令的生成）无法确定在目标架构上，转换成位运算和加减法到底值不值得。
那我们就来看看，LLVM 在确定目标架构的情况下，会不会进行相应的优化。以 Intel x86-64（AT&T 格式）为例，用下面的命令生成目标机器代码：
llc main-opt.ll -o main.s在我的计算机上，可以得到：
.file "main.ll"
.text
.globl test1 # -- Begin function test1
.p2align 4
.type test1,@function
test1: # @test1
# %bb.0:
# kill: def $edi killed $edi def $rdi
leal (%rdi,%rdi), %eax
retq
.Lfunc_end0:
.size test1, .Lfunc_end0-test1
# -- End function
.globl test2 # -- Begin function test2
.p2align 4
.type test2,@function
test2: # @test2
# %bb.0:
movl %edi, %eax
shrl %eax
retq
.Lfunc_end1:
.size test2, .Lfunc_end1-test2
# -- End function
.globl test3 # -- Begin function test3
.p2align 4
.type test3,@function
test3: # @test3
# %bb.0:
# kill: def $edi killed $edi def $rdi
leal (,%rdi,8), %eax
subl %edi, %eax
retq
.Lfunc_end2:
.size test3, .Lfunc_end2-test3
# -- End function
.globl test4 # -- Begin function test4
.p2align 4
.type test4,@function
test4: # @test4
# %bb.0:
# kill: def $edi killed $edi def $rdi
addl %edi, %edi
leal (%rdi,%rdi,4), %eax
retq
.Lfunc_end3:
.size test4, .Lfunc_end3-test4
# -- End function
.globl test5 # -- Begin function test5
.p2align 4
.type test5,@function
test5: # @test5
# %bb.0:
movl %edi, %eax
andl $1, %eax
retq
.Lfunc_end4:
.size test5, .Lfunc_end4-test5
# -- End function
.globl test6 # -- Begin function test6
.p2align 4
.type test6,@function
test6: # @test6
# %bb.0:
movl %edi, %eax
movl %edi, %ecx
movl $3435973837, %edx # imm = 0xCCCCCCCD
imulq %rcx, %rdx
shrq $35, %rdx
addl %edx, %edx
leal (%rdx,%rdx,4), %ecx
subl %ecx, %eax
retq
.Lfunc_end5:
.size test6, .Lfunc_end5-test6
# -- End function
.section ".note.GNU-stack","",@progbits注意观察 test3、test4 和 test6 函数中的汇编指令（已在上面的代码块中高亮），我们发现，最终生成的汇编代码确实使用了位运算和加减法来优化乘除法。这说明，LLVM 认为，在 Intel x86-64 架构上，这样优化是值得的，可以减少 CPU 周期数量。
数学等价变换
如果你的代码中涉及到某些运算或操作，而通过数学上的分析，这些运算或操作可以被更高效的运算方法替代，那么编译器就可以对你的进行等价替换。
最经典的例子，应该就是高斯算法（等差数列求和公式）。用数学的语言表示，就是：
我们来看看编译器会不会进行这样的优化。先编写一个非常简单的 C 语言代码：
int sum(int n) {
int res = 0;
for (int i = 1; i <= n; i++) {
res += i;
}
return res;
}然后，我们将其手动翻译为 LLVM IR：
define i32 @sum(i32 %n) {
%res = alloca i32 ; int res
store i32 0, i32* %res ; 0 -> res
br label %for_init ; -> for_init
for_init:
%i = alloca i32 ; int i
store i32 1, i32* %i ; 1 -> i
br label %for_cond ; -> for_cond
for_cond:
%i.value = load i32, i32* %i ; i.value <- i
%cond = icmp sle i32 %i.value, %n ; cond = i.value <= n
br i1 %cond, label %for_body, label %for_end ; cond: true -> for_body, false -> for_end
for_body:
%i.val = load i32, i32* %i ; i.val <- i
%res.val = load i32, i32* %res ; res.val <- res
%res.new = add i32 %res.val, %i.val ; res.new <- res.val + i.val
store i32 %res.new, i32* %res ; res.new -> res
br label %for_incr ; -> for_incr
for_incr:
%i.old = load i32, i32* %i ; i.old <- i
%i.new = add i32 %i.old, 1 ; i.new = i.old + 1
store i32 %i.new, i32* %i ; i.new -> i
br label %for_cond ; -> for_cond
for_end:
%result = load i32, i32* %res ; result <- res
ret i32 %result ; return result
}好，让我们来运行一下优化命令，看看优化后的代码：
define i32 @sum(i32 %n) local_unnamed_addr #0 {
for_init:
%cond.not4 = icmp slt i32 %n, 1
br i1 %cond.not4, label %for_end, label %for_body
for_body: ; preds = %for_init, %for_body
%i.06 = phi i32 [ %i.new, %for_body ], [ 1, %for_init ]
%res.05 = phi i32 [ %res.new, %for_body ], [ 0, %for_init ]
%res.new = add i32 %i.06, %res.05
%i.new = add i32 %i.06, 1
%cond.not = icmp sgt i32 %i.new, %n
br i1 %cond.not, label %for_end, label %for_body
for_end: ; preds = %for_body, %for_init
%res.0.lcssa = phi i32 [ 0, %for_init ], [ %res.new, %for_body ]
ret i32 %res.0.lcssa
}咦，奇怪了，为什么没有使用高斯公式？我们可以看到，LLVM 编译器确实优化了控制流，并且将栈变量提升到了虚拟寄存器，但是似乎并没有做数学上的等价变换。为什么呢？难道是因为 LLVM 编译器不够智能？
需要注意的是，我们的上下文是计算机科学，而不是数学。在计算机科学中，做任何有关整数的数学变换之前，都要考虑是否可能溢出。在这个语境下，a < b 与 a - b < 0 甚至都不是等价的，因为后者可能会发生溢出。一旦有溢出产生，数学的等价性就会被破坏。在这里，LLVM 无法确认这个函数中的运算（在这里是加法）是否可能产生溢出，而 LLVM 对整数溢出的默认处理方式又是回环溢出（环绕，Wrapping）。为了保证程序的执行结果与原来的代码所表达的一致，LLVM 只能放弃进行数学上的分析和优化。
但如果我们确认我们的运算不可能产生溢出，那么数学的等价分析就成立了，高斯公式就可以使用了。我们只需要在我们的程序做一点小小的修改，就能让 LLVM 编译器毫无顾虑地进行优化。
define i32 @sum(i32 %n) {
%res = alloca i32 ; int res
store i32 0, i32* %res ; 0 -> res
br label %for_init ; -> for_init
for_init:
%i = alloca i32 ; int i
store i32 1, i32* %i ; 1 -> i
br label %for_cond ; -> for_cond
for_cond:
%i.value = load i32, i32* %i ; i.value <- i
%cond = icmp sle i32 %i.value, %n ; cond = i.value <= n
br i1 %cond, label %for_body, label %for_end ; cond: true -> for_body, false -> for_end
for_body:
%i.val = load i32, i32* %i ; i.val <- i
%res.val = load i32, i32* %res ; res.val <- res
%res.new = add nsw i32 %res.val, %i.val ; res.new <- res.val + i.val
store i32 %res.new, i32* %res ; res.new -> res
br label %for_incr ; -> for_incr
for_incr:
%i.old = load i32, i32* %i ; i.old <- i
%i.new = add nsw i32 %i.old, 1 ; i.new = i.old + 1
store i32 %i.new, i32* %i ; i.new -> i
br label %for_cond ; -> for_cond
for_end:
%result = load i32, i32* %res ; result <- res
ret i32 %result ; return result
}上面的代码块中已经高亮标出了修改的部分。我们发现，主要改动在于我们添加了 nsw 标志。这个标志的意思是 No Signed Wrap（不存在有符号环绕）。这个标志直接告诉了 LLVM 编译器：这个函数中的加法运算不存在溢出的可能性。那么 LLVM 就可以放开手脚进行优化了。
我们来看见现在的优化结果：
define i32 @sum(i32 %n) local_unnamed_addr #0 {
for_init:
%cond.not4 = icmp slt i32 %n, 1
br i1 %cond.not4, label %for_end, label %for_body.preheader
for_body.preheader: ; preds = %for_init
%0 = shl nuw i32 %n, 1
%1 = add nsw i32 %n, -1
%2 = zext nneg i32 %1 to i33
%3 = add nsw i32 %n, -2
%4 = zext i32 %3 to i33
%5 = mul i33 %2, %4
%6 = lshr i33 %5, 1
%7 = trunc nuw i33 %6 to i32
%8 = add i32 %0, %7
%9 = add i32 %8, -1
br label %for_end
for_end: ; preds = %for_body.preheader, %for_init
%res.0.lcssa = phi i32 [ 0, %for_init ], [ %9, %for_body.preheader ]
ret i32 %res.0.lcssa
}可以看到，循环结构直接被删除，整个运算流程被替换为了一系列的基本运算。暂时先不用管这里的各种指令和奇怪的 i33（33 位整数）类型，这些是 LLVM 为了保证正确性和高效性的手段。总之，你只需要知道，LLVM 识别出了程序意图，找到了数学等价变换的方式，并用它认为最高效最准确的指令完成了这个任务。
你可能想知道，既然我们的 nsw 标志是人为在 LLVM IR 源代码中添加进去的，那对于我们最常使用的高级编程语言来说，我们有手段通知编译器某个运算不会溢出吗？很遗憾，很多编程语言没有给你这个自由的权限。在 Java、Go 等语言中，溢出的行为被固定为回环溢出，语言本身就认为你的运算中包含溢出的可能。当然，还是有些编程语言以直接或间接的方式提供了这个选项的。在 C/C++ 中，有符号整型溢出事实上是未定义行为，编译器默认认为你的有符号整数运算不会溢出，因此有权利做这个优化；Rust 语言中，整型溢出被规定为无效操作（Debug 模式下程序产生溢出会导致 panic），因此编译器也会认为你的程序中不存在溢出。
:::info[拓展：那些不认为你的程序会溢出的语言] 对于 C/C++，标准没有规定有符号溢出的具体行为，但大多数架构都使用回环溢出（因为是补码表示），所以看起来好像在不同得架构与平台上具有相同的行为。
Rust 默认不允许程序中存在溢出。在 Debug 模式下编译时，Rust 会加入检查代码，一旦发现溢出，就会导致 panic；而在 Release 模式下编译时，编译器不会加入检查代码，并会无脑地认为你的代码不存在溢出。如果确实想要溢出的行为，可以使用 wrapping_add 等方法明确表示运算中产生的溢出是回环溢出。 |
|---|
当然，尽管很多语言不认为你的程序不会溢出，但是如果 LLVM 能分析出你的函数参数、变量等的范围，并确认你的运算不会溢出，也可以做这样的优化。
我们再来看一个例子：我们改一下公差和上限，变成这样：
int sum(int n) {
int res = 0;
for (int i = 1; i <= n * 2; i += 2) {
res += i;
}
return res;
}将其手动翻译为 LLVM IR：
define i32 @sum(i32 %n) {
%res = alloca i32 ; int res
store i32 0, i32* %res ; 0 -> res
br label %for_init ; -> for_init
for_init:
%i = alloca i32 ; int i
store i32 1, i32* %i ; 1 -> i
br label %for_cond ; -> for_cond
for_cond:
%i.value = load i32, i32* %i ; i.value <- i
%upper = mul nsw i32 %n, 2 ; upper = n * 2
%cond = icmp sle i32 %i.value, %upper ; cond = i.value <= upper
br i1 %cond, label %for_body, label %for_end ; cond: true -> for_body, false -> for_end
for_body:
%i.val = load i32, i32* %i ; i.val <- i
%res.val = load i32, i32* %res ; res.val <- res
%res.new = add nsw i32 %res.val, %i.val ; res.new <- res.val + i.val
store i32 %res.new, i32* %res ; res.new -> res
br label %for_incr ; -> for_incr
for_incr:
%i.old = load i32, i32* %i ; i.old <- i
%i.new = add nsw i32 %i.old, 2 ; i.new = i.old + 2
store i32 %i.new, i32* %i ; i.new -> i
br label %for_cond ; -> for_cond
for_end:
%result = load i32, i32* %res ; result <- res
ret i32 %result ; return result
}记得加上 nsw 标志。
然后看看优化结果：
define i32 @sum(i32 %n) local_unnamed_addr #0 {
for_init:
%cond.not4 = icmp slt i32 %n, 1
br i1 %cond.not4, label %for_end, label %for_body.preheader
for_body.preheader: ; preds = %for_init
%upper = shl nuw i32 %n, 1
%0 = or disjoint i32 %upper, 1
%smax = tail call i32 @llvm.smax.i32(i32 %0, i32 3)
%1 = add nsw i32 %smax, -2
%2 = lshr i32 %1, 1
%3 = mul nuw i32 %2, 3
%4 = lshr i32 %1, 1
%5 = add nsw i32 %2, -1
%6 = mul i32 %4, %5
%7 = and i32 %6, -2
%8 = add i32 %3, %7
%9 = add i32 %8, 1
br label %for_end
for_end: ; preds = %for_body.preheader, %for_init
%res.0.lcssa = phi i32 [ 0, %for_init ], [ %9, %for_body.preheader ]
ret i32 %res.0.lcssa
}
declare i32 @llvm.smax.i32(i32, i32) #1可以看到，LLVM 也进行了数学上的分析并进行优化。
参数提升
思考一个问题：如果有一个函数，传入一个结构体指针（或值）作为参数，但是整个函数体中只使用了这个结构体的某个或某些字段，那么我们完全可以把这个函数修改一下，让它直接接受这个或这些字段作为参数，以减少函数调用开销，并方便 LLVM 进行更激进的优化。
需要注意的是，这个函数有一个硬性要求：必须是内部链接性的。如果一个函数是内部链接性的，也就是它只能在当前文件（模块）被使用，那么 LLVM 编译器可以完全确定所有调用这个函数的地方，从而修改调用处以及这个函数的签名。但是，如果这个函数是外部链接性的，那么 LLVM 编译器就不能修改这个函数，因为外部文件也可能使用这个函数，甚至被编译为静态链接库给别的程序使用，LLVM 无法确定所有调用处，因此无法进行参数提升的优化。
:::info[启示：内部链接性函数]
上面的论述也启示我们：对于你根本就没打算让外部文件使用的函数，你大可将其用 static 标记为内部链接性，让编译器能够做更好的优化。对于单文件程序，你甚至可以把除主函数外的所有函数和全局变量设置为内部链接性的，编译器就可以大展身手了。
:::
我们来看一个简单的例子。
struct Data {
int a;
int b;
};
struct Data get_data();
int get_int();
void use_the_value(int);
static void use_data(struct Data* data, int number) {
int value = data->b;
if (value >= 0) {
use_the_value(value + number);
} else {
use_the_value(value - number);
}
}
void test() {
struct Data data = get_data();
int number = get_int();
use_data(&data, number);
}在这个 C 程序中，我们定义了一个结构体 Data，存放两个 int 数据。随后，我们声明一些函数，来假装从别处获取数据和将数据传给别处，以避免编译器做无用代码删除和常量折叠。随后，我们定义了一个函数 use_data，它是内部链接性的，且只使用了 Data 结构体的第二个字段。然后我们在 test 函数中调用这个函数，以进行参数提升优化的测试。
接下来我们来手动将这份 C 代码翻译为 LLVM IR。这里出现了几个新指令，在注释中已经详细解释了。
; 定义一个聚合类型，保存两个 i32 类型的值，命名为 %Data。
%Data = type { i32, i32 }
; 声明一些函数。
declare %Data @get_data()
declare i32 @get_int()
declare void @use_the_value(i32)
; internal 表示内部链接性。
define internal void @use_data(%Data* %data, i32 %number) {
; 下面是 LLVM IR 中除了 phi 之外另一个非常重要的指令：GEP (Get Element Ptr)
; 这条指令用于计算内存偏移量，得到我们想要的值的内存地址（指针）。
; 在下面这条指令中，我们传入一个 %Data 指针类型（%Data*）的值 %data，
; 并获取它的第二个字段的内存地址。
; 第一个索引是 i64 类型的 0，表示对 %data 指针偏移 0 个单位，然后解引用，
; 这样就可以得到 %Data 类型的值（即 %data 指向的值）。
; 第二个索引是 i32 类型的 1，表示取出 %Data 类型的第二个字段的内存地址。
; 随后我们得到一个 i32 类型的指针（i32*），
; 这个指针指向的就是 %data 所指向的结构体值的第二个字段。
; 随后我们可以使用这个指针配合 store 和 load 指令来进行存取操作。
%value.ptr = getelementptr %Data, %Data* %data, i64 0, i32 1
%value = load i32, i32* %value.ptr ; value <- value.ptr
%cond = icmp sge i32 %value, 0 ; cond = value >= 0
br i1 %cond, label %branch_add, label %branch_sub ; cond: true -> branch_add, false -> branch_sub
branch_add:
%value.add = add i32 %value, %number ; value.add = value + number
call void @use_the_value(i32 %value.add) ; use_the_value(value.add)
br label %end ; -> end
branch_sub:
%value.sub = sub i32 %value, %number ; value.sub = value - number
call void @use_the_value(i32 %value.sub) ; use_the_value(value.sub)
br label %end ; -> end
end:
ret void ; return
}
define void @test() {
; 在栈上分配存储 %Data 类型的内存，用以存储变量。
%data = alloca %Data
%result = call %Data @get_data() ; result = get_data()
store %Data %result, %Data* %data ; result -> data
%number = call i32 @get_int() ; number = get_int()
call void @use_data(%Data* %data, i32 %number) ; use_data(data, number)
; 注意，这里 data 是指针。
ret void ; return
}然后我们对这份 IR 代码进行优化。不过这次我们不能直接使用 O2 等级优化，因为 LLVM 编译器会将我们的 use_data 函数内联并删除（因为它发现这个函数只被调用了一次）。我们需要指定 LLVM 编译器需要进行的优化。使用下面的命令进行优化：
opt -passes="function(sroa),cgscc(argpromotion),function(sroa)" -S main.ll -o main-opt.ll这个命令的大概意思是：对数据流进行一次优化（比如简化运算、栈变量提升到虚拟寄存器），然后进行参数提升优化，然后再进行一次数据流优化。
我们最终得到的优化后的 LLVM IR 代码是：
%Data = type { i32, i32 }
declare %Data @get_data()
declare i32 @get_int()
declare void @use_the_value(i32)
define internal void @use_data(i32 %data.4.val, i32 %number) {
%cond = icmp sge i32 %data.4.val, 0
br i1 %cond, label %branch_add, label %branch_sub
branch_add: ; preds = %0
%value.add = add i32 %data.4.val, %number
call void @use_the_value(i32 %value.add)
br label %end
branch_sub: ; preds = %0
%value.sub = sub i32 %data.4.val, %number
call void @use_the_value(i32 %value.sub)
br label %end
end: ; preds = %branch_sub, %branch_add
ret void
}
define void @test() {
%result = call %Data @get_data()
%result.fca.0.extract = extractvalue %Data %result, 0
%result.fca.1.extract = extractvalue %Data %result, 1
%number = call i32 @get_int()
call void @use_data(i32 %result.fca.1.extract, i32 %number)
ret void
}我们可以看到，编译器确实修改了 use_data 函数的签名，将第一个参数修改为只接受一个整数，表示结构体的第二个字段。然后，在 test 函数中，原来的 data 被提升到虚拟寄存器中，变成 result，并使用 extractvalue 指令直接从一个聚合类型（这里是 %Data 类型）中提取出一个字段（这里是第二个字段）的值。随后，调用 use_data 时，直接传入第二个字段的值。
在这个例子中，我们规定了 LLVM 的优化流程，从而避免编译器过度优化。那么这个参数提升优化到底有没有用呢？事实上是有的。在这个例子中，只是因为程序比较小，LLVM 编译器很容易做过度优化，从而将参数提升后的效果也覆盖了。在真正的程序中，情况会更复杂、调用位置也会更多，这时 LLVM 如果选择不是每个地方都内联该函数的话，是真的可能进行参数提升的。
还有几种参数提升，就不限于结构体了。比如，如果一个内部链接性的函数接受一个 int* 指针类型作为参数，但是整个函数中只对这个指针进行了解引用读取操作，没有写入，也没有将其传入给其他函数。那么，这时 LLVM 编译器就会将此指针标记为只读，并且可能在之后几轮的优化中将其变为传值。
尾递归优化
尾递归，就是在尾部的递归。它指的是某个函数在函数的末尾调用自身。那这又有什么好优化的呢？
我们知道，每一个函数调用都会创建一个栈帧。同一个函数所创建的栈帧应该是一致的（存在栈上动态数组除外）。所以，尾递归的函数事实上是在函数末尾又通过函数调用在栈上创建了一个和原来一模一样的栈帧。而“在函数末尾”又意味着原来的栈帧已经不再需要使用。原来的栈帧不再使用，新的栈帧与原来一模一样，那么我们为什么不直接重用原来的栈帧呢？
尾递归优化就是基于这个思想，将尾递归的函数体改写为循环，从而直接避免了调用栈过深导致栈溢出。
我们来看一个简单的例子：
unsigned gcd(unsigned a, unsigned b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}define i32 @gcd(i32 %a, i32 %b) {
%cond = icmp eq i32 %b, 0 ; cond = b == 0
br i1 %cond, label %ret_a, label %ret_gcd ; cond: true -> ret_a, false -> ret_gcd
ret_a:
ret i32 %a ; return a
ret_gcd:
%rem = urem i32 %a, %b ; rem = a % b
%result = call i32 @gcd(i32 %b, i32 %rem) ; result = gcd(b, rem)
ret i32 %result ; return result
}这是一个很简单的 gcd 函数，用于求两个正整数的最大公约数，采用辗转相除法进行计算。LLVM IR 代码是直接根据 C 代码的语义翻译的。在这里，我们可以观察到，gcd 函数是一个尾递归函数：其递归调用在函数末尾。那么 LLVM IR 会怎么优化呢？我们来看看优化后的结果：
define i32 @gcd(i32 %a, i32 %b) local_unnamed_addr #0 {
%cond1 = icmp eq i32 %b, 0
br i1 %cond1, label %common.ret, label %ret_gcd
common.ret: ; preds = %ret_gcd, %0
%a.tr.lcssa = phi i32 [ %a, %0 ], [ %b.tr3, %ret_gcd ]
ret i32 %a.tr.lcssa
ret_gcd: ; preds = %0, %ret_gcd
%b.tr3 = phi i32 [ %rem, %ret_gcd ], [ %b, %0 ]
%a.tr2 = phi i32 [ %b.tr3, %ret_gcd ], [ %a, %0 ]
%rem = urem i32 %a.tr2, %b.tr3
%cond = icmp eq i32 %rem, 0
br i1 %cond, label %common.ret, label %ret_gcd
}仔细观察可以发现：这个优化后的函数体内没有 call 指令了。再分析一下它的跳转指令（br 指令），观察跳转方向，我们可以发现：高亮的那一行会在 %cond 为 false 时跳回 ret_gcd 块的开头，并通过 phi 指令更新数据——这就是一个循环！
不过，需要注意的是，尾递归优化的条件非常严苛，优化难度也很高。一般来说，AOT 编译型语言（如 C/C++、Rust 等）只有在开启较高等级优化（如 C/C++ 的 O2 等级或 Rust 的 Release 模式）的情况下，才可能会进行尾递归优化。对于 LLVM 编译器来说，它如果发现某个函数过于复杂、优化难度过高，可能会出现优化失败的情况，这时它就会放弃尾递归优化。
当然，某些编译器提供了让程序员指定必须使用尾递归优化的方法。Clang 编译器提供了 [[clang::musttail]] 标签，标记一个返回语句，表示该递归函数必须进行尾递归优化。如果编译器优化失败，将直接编译错误，而不是放弃优化继续编译。但是这通常是特定编译器和特定编程语言给你开的“后门”，不是特别通用。我们更应该做的，是将代码写清楚，让编译器能够更好地理解我们的代码，从而更好地选择优化。
结语
我们使用 C 语言和 LLVM IR 看到了很多编译器会为我们的程序做的优化。C 语言负责明确程序结构和行为，而 LLVM IR 则让我们看到了更底层的代码，从而使优化的效果更加明显。
在我们未来无限次与计算机打交道的过程中，可能永远也没有机会真的去接触这些精妙而复杂的优化。你可能永远不会阅读这些优化的实现代码，也可能永远不会尝试自己手写一个。但了解这些编译器能为我们做的优化，不是为了能够自己编写、自己创造，而是知道编译器能为我们做什么、不能为我们做什么，从而改进我们的代码编写方式，知道在哪里可以放开手脚大胆写、在哪里需要细心设计让编译器能够更好地优化。
这趟编译优化探索的旅途已经基本结束，但关于编译优化的理论远不止这些。如果你有兴趣了解更多，可以尝试搜索更多的资料。这里推荐编译原理经典教材“龙书”，其中关于优化的部分就值得读一读。
（洛谷没有 LLVM IR 的代码高亮就非常难受啊！！！）