[译]Clang如何编译函数

作者： John Regehr

原文地址： https://blog.regehr.org/archives/1605

我计划编写一篇关于 LLVM 如何优化函数的博客，但看起来首先要写清楚 Clang 如何将 C 或 C++ 翻译为 LLVM 。

这将是相当高层面的：

• 不是关注 Clang 的内部，我将关注 Clang 的输出如何与其输入相关
• 我们不准备看任何非平凡的 C++ 特性

我们将使用这个小函数，它是我从 这些关于循环优化的优秀课堂讲义 中借来的：

因为 Clang 不进行任何优化，且因为 LLVM IR 最初设计为以 C 与 C++ 为目标，这个翻译进行得相对容易。我将使用 x86-64 上的 Clang 6.0.1 （或附近的版本，因为它还没有完全发布）。

命令行是：

clang++ is_sorted.cpp -O0 -S -emit-llvm

换而言之：将这个文件 is_sort.cpp 作为 C++ 编译，然后告诉剩下的 LLVM 工具链：没有优化，发出汇编，但不是实际发出 LLVM 文本 IR 。文本 IR 是笨重的，对打印或解析不是特别快；在没有涉及人时，二进制“字节码”格式总是首选。 完整的IR文件 在这里，我们会分几个部分来看。

从文件的开头开始，我们有：

; ModuleID = 'is_sorted.cpp'

source_filename = "is_sorted.cpp"

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

target triple = "x86_64-unknown-linux-gnu"

分号与行末的文本都是注释，因此第一行什么都不做，但如果你在意，一个 LLVM“ 模块 ” 基本上是一个编译单元：一个代码与数据的容器。第二行与我们无关。第三行描述了编译器的某些选择与假设；它们与本文不太相关，但你可以在 这里读到更多 。 目标三元组 是一个 gcc 制度，这里也与我们无关。

LLVM 函数带有可选的属性：

; Function Attrs: noinline nounwind optnone uwtable

它们中的一些由前端提供，其他由优化遍在后面添加。这只是一个注释，实际属性在文件末尾指定。这些属性与代码的含义没有任何关系，因此我不准备讨论它们，但如果你感兴趣，可以在 这里 读到更多。

好了，最后回到函数本身：

define zeroext i1 @_Z9is_sortedPii(i32* %a, i32 %n) #0 {

zeroext 表示函数的返回值（ i1 ，一比特整数）应该由后端零扩展到 ABI 要求的宽度。跟着是函数的重整名，然后是参数列表，与 C++ 代码中的基本相同，除了“ int ”类型被完善为 32 比特。 #0 把这个函数与文件底部的 属性组 联系起来。

现在来看第一个基本块：

entry:

%retval = alloca i1, align 1

%a.addr = alloca i32*, align 8

%n.addr = alloca i32, align 4

%i = alloca i32, align 4

store i32* %a, i32** %a.addr, align 8

store i32 %n, i32* %n.addr, align 4

store i32 0, i32* %i, align 4

br label %for.cond

每条 LLVM 指令必须存活在一个基本块内：一组仅在顶部进入在底部退出的指令。基本块的最后指令必须是一条终结符指令：直落是不允许的。每个函数必须有一个除了函数入口本身，没有前驱（来自的地方）的进入块。在解析一个 IR 文件时，检查 这些及其他属性 ，并可能在编译期间由“模块验证器”多次检查。在调试一个遍发出非法 IR 的情形里，验证器是有用的。

入口基本块的前 4 条指令是“ alloca ”：栈内存分配。前 3 个用于编译期间创建的隐含变量，第 4 个用于循环归纳变量。像这样的储存分配仅可以使用 load 及 store 指令访问。后 3 条指令初始化 3 个栈槽：使用作为参数传入函数的值初始化 a.addr 与 n.addr ，将 i 初始化为零。返回值不需要初始化：这将由任何在 C 或 C++ 层面没有未定义的代码处理。最后一条指令是到后续基本块的无条件分支（这里我们不准备操心它，但大多数这些不必要的跳转可以被 LLVM 后端消除）。

你可能问：为什么 Clang 为 a 与 n 分配栈槽？为什么不直接使用这些变量？在这个函数中，因为 a 与 n 从不改变，这个策略可以工作，但注意这个事实被视为一个优化，因而在 Clang 的设计考量之外。在一般情形里，其中 a 与 n 可能被修改，它们必须存活在内存中，而不是作为 SSA 值， SSA ——根据定义——在程序中每处上仅有一个给定值。内存单元在 SSA 世界之外，可以被自由修改。这看起来令人困惑和武断，但人们发现，这些设计决策允许编译器的许多部分以自然和高效的方式表达。

我认为 Clang 发布退化的 SSA 代码：它满足 SSA 的所有要求，但仅因为基本块通过内存通信。发布非退化 SSA 要求一定程度的谨慎与分析， Clang 拒绝做这些导致令人愉悦的关注分离。我没有看过测量结果，但我的理解是，生成大量的内存操作，然后几乎马上优化掉其中的许多，不是编译时开销的主要来源。

接下来让我们看一下如何翻译 for 循环。一般形式是：

这大致翻译为：

initializer

goto COND

COND:

if (condition)

goto BODY

else

goto EXIT

BODY:

body

modifier

goto COND

EXIT:

当然这个翻译不是特定于 Clang 的：任何 C 或 C++ 编译器做的都一样。

在我们的例子里，循环初始化被折叠进了入口基本块。下一个基本块是循环条件测试：

for.cond:                                         ; preds = %for.inc, %entry

%0 = load i32, i32* %i, align 4

%1 = load i32, i32* %n.addr, align 4

%sub = sub nsw i32 %1, 1

%cmp = icmp slt i32 %0, %sub

br i1 %cmp, label %for.body, label %for.end

作为一个有用的注释， Clang 告诉我们可以从 for.inc 或入口基本块到达这个基本块。这个块从内存载入 i 与 n ，递减 n （“ nsw ”标记保留了 C++ 层面的，有符号溢出是未定义的事实；没有这个标记 LLVM 减法将具有 2 进制补码的语义），使用“有符号小于”比较递减后的值与 i ，最后分支到 for.body 基本块或 for.end 基本块。

这个 for 循环的主体仅可以从 for.cond 基本块进入：

for.body:

%2 = load i32*, i32** %a.addr, align 8

%3 = load i32, i32* %i, align 4

%idxprom = sext i32 %3 to i64

%arrayidx = getelementptr inbounds i32, i32* %2, i64 %idxprom

%4 = load i32, i32* %arrayidx, align 4

%5 = load i32*, i32** %a.addr, align 8

%6 = load i32, i32* %i, align 4

%add = add nsw i32 %6, 1

%idxprom1 = sext i32 %add to i64

%arrayidx2 = getelementptr inbounds i32, i32* %5, i64 %idxprom1

%7 = load i32, i32* %arrayidx2, align 4

%cmp3 = icmp sgt i32 %4, %7

br i1 %cmp3, label %if.then, label %if.end

前两行将 a 与 i 载入 SSA 寄存器；然后将 i 加宽到 64 位，使它可以参予地址计算。 getelementptr （简称为 gep ）是 LLVM 著名的巴洛克式的指针计算指令，它甚至有 自己的faq 。不像机器语言， LLVM 不以相同的方式处理指针与整数。这有助于别名分析和其他内存优化。然后代码继续载入 a[i] 与 a[i+1] ，比较它们，基于结果分支。

If.then 块把 0 保存到栈槽，作为函数返回值，并无条件分支到函数的退出块：

if.then:

store i1 false, i1* %retval, align 1

br label %return

else 块是无关紧要的：

if.end:

br label %for.inc

向循环归纳变量加 1 的块也是容易的：

for.inc:

%8 = load i32, i32* %i, align 4

%inc = add nsw i32 %8, 1

store i32 %inc, i32* %i, align 4

br label %for.cond

这个代码分支回循环条件测试。

如果循环正常终止，我们希望返回 true ：

for.end:

store i1 true, i1* %retval, align 1

br label %return

最后，任何保存在返回值栈槽的内容被载入并返回：

return:

%9 = load i1, i1* %retval, align 1

ret i1 %9

函数底部有更多内容，但不重要。好了，本文比我预想的要长，下一篇将看一下 IR 层面的优化对这个函数做了什么。

（感谢 Xi Wang 与 Alex Rosenberg 的纠错）。