【MIT 6.172笔记】Lecture 5: LLVM 入门——从C到汇编指令 ...

龙犁

Lecture 4 主要讲解了x86_64指令集，绝大多数都是本科计算机体系结构和组成原理课上的内容，因此本系列就不再总结。
Lecture 5讲解了C语言是如何一步步变成汇编指令的过程，并且讲解了LLVM IR，以及C代码与LLVM IR的关系、LLVM IR与汇编指令的关系。

为什么需要LLVM IR

将C语言转变为汇编语言的过程中编译器做了很多工作：

• 选择汇编指令来实现C的操作
  
• 使用跳转和分支指令来实现C语言中的分支和循环
  
• 选择寄存器和内存位置来存储数据
  
• 在满足依赖的条件下在寄存器和内存中移动数据
  
• 协调函数依赖
  
• 将生成的汇编指令优化地足够快
  

下面是代码编译的大体流程，预处理（Preprocess）是对C进行文本预处理，比如宏替换，然后再编译（Compile）为汇编指令。


在这种情况下将C转换为汇编的过程过于复杂，而且从C到汇编的映射也不是那么明显：


我们需要的是一个比C语言更底层，但是比汇编语言更抽象的中间表示（IR：Intermediate Representation），这也就是LLVM IR。我们将C指令转化为LLVM IR，然后再在LLVM IR的基础上进行各种各样的编译优化，最后再转变为汇编指令，这样可以编译过程中的复杂性给分条缕析地搞清楚。
这是加上了LLVM这一中间层级以后的编译流程：


预处理后的 .i 文件经过Clang（编译器前端）转化为LLVM IR，然后LLVM optimizer在LLVM IR上做多次优化，最后LLVM code generator讲LLVM IR转化为汇编指令。
下面我们对照看一下C代码和LLVM IR。


看LLVM IR就好像看一个从来不给变量起名字也不写注释的同事写的代码。它也有函数名（ @fib ）、类型（ i64 ）、变量（ % +数字，其实是寄存器），具体LLVM IR的每行会在下面详述。但是在分支语句上，LLVM IR更像汇编，例如上图中 br 指令根据变量 %2 的值跳转到 ; <label>:3 或是 ; <label>:9 。
下面再看LLVM IR和汇编指令的对比：


可以清晰地看到，在汇编指令中，寄存器（ %+数字 就是寄存器好，只不过在LLVM IR中的寄存器抽象为无穷多个 ，和C语言的变量更类似）不再以”变量赋值“的形式出现，而代之以 <instruction> <destination resigter> <source register> 代形式。但是在分支上展现出了一致性。
下面我们正式进入LLVM IR的学习。
LLVM IR Primer

LLVM IR 基本结构

下面是LLVM IR的基本组成部分：

• 函数声明：LLVM IR中的函数声明以 define 开头，它的函数名与C语言的函数名有对应关系（ @fib ），但是返回值与参数不标具体的名称，而是只标记类型（ i64 ，64位整数）。
  
• 寄存器：LLVM IR中的寄存器标以 %+数字 ，在LLVM IR中假定寄存器的数量是无限的，这一点和C语言中的变量是无限的一样。将LLVM IR中无限多的寄存器如何在编译时分配到有限的寄存器上，这是后续要考虑的问题。
  
• 指令：LLVM IR中的指令类似于C语言中的指令，指令采取 %<寄存器名> = <操作符> <多个操作数> 的形式。比如 %6 = add nsw i64 %0, -2 表示”将寄存器 %0 中的值减去2，结果存储在寄存器 %6 中“。nsw是一个符号扩展标记，表示应该进行有符号数的溢出检查，这类标记的作用时指导后续的优化。LLVM IR的指令集有load、store、add、sub、mul、div等算术指令,也有比较指令如icmp,还有分支跳转指令br等。
  
• 数据类型：比如 i1 表示1位int，也就是bool型； i64 表示64位有符号整数。
  
• 基本块（Basic Block）：LLVM IR中将代码组织成基本块——一个基本块内的指令必须顺序执行，而且必须每条都执行，基本块之间可以相互调用。这么组织是为了实现递归和分支，一个if分支就是一个基本块（ ; <label>:3 ），else又是另一个基本块（ ; <label>:9 ）。
  

LLVM IR比汇编代码更简单在：

• 指令集更简单（相比之下x64_64的指令集过于复杂）。
  
• LLVM IR中的寄存器有无限多个。
  
• LLVM IR中没有隐式的FLAG寄存器（比如汇编代码中判断分支要先做减法、再检查CF寄存器），这在LLVM IR中时没有的。
  
• 没有显式的stack指针，因此不需要手动管理栈。
  
• 与C类似的类型系统和函数调用。
  

LLVM IR 指令类型

可以看到，LLVM的指令系统不仅比x86_64这样的CISC指令集要简单，而且还比RISC指令集更简单。LLVM IR不涉及具体架构，是对程序的高度抽象，可以理解为 *****伪汇编。*******


LLVM IR 数据类型

下面是LLVM IR的数据类型，他们大体上类似于C，但是还是有一些区别。

• 基于整数的类型（int，bool）都是用 i64 i1 这样的“整型”来表示
  
• LLVM IR中的数组使用 [元素个数 ✖️ 类型] 来“标注”。比如 [5 ✖️ i32] %0 可以理解为 vector<int> %0(5) 。Vectors类型和Arrays类型类似
  
• Label 类型用来表示基本块。C语言中“函数“是最小课调用的单元，通过函数名调用；LLVM IR中最小课调用单元是基本块，所以需要一个类型来表明基本块，也需要一个名称来调用基本块，这种类型就是Label。
  
• 其他类型，比如浮点数、结构体、指针，都和C语言类似。
  

C语言映射到LLVM IR

普通的语句

不包含条件分支和循环的C语句会被映射成顺序（Sequence）的LLVM IR指令，中间结果会被保存在“寄存器”中。
比如这个语句的映射关系如下：


分别将变量 n （ %0 ）减去-1和-2、调用 @foo 函数和 @bar 函数，并且最后将结果加起来。 nsw 是为了优化而给的LLVM属性。
聚合类型（Aggregate Type）

聚合类型，比如有 Struct 和 Array ，一般都存储在内存中而非寄存器中。
因此访问聚合类型需要有两步：

• 计算地址
  
• 通过地址读取数据
  

两个过程如下所示：

• %5 = ... 这一句使用 getelementptr 指令来计算地址。
  
  
  
  • getelementptr [7 x i32] 表示需要取得一个类型为 [7 x i32] 的Array， inbounds 表示数组没有越界。
    
  
  

• [7 x i32]* %2, i64 0, i64 %4 表示数组首地址存储在 %2 中，要读取从第0个元素开始的第 %4 个元素。
  
• %6 = ... 这一句表示从 %5 指向的位置读取一个4字节对齐的 i32 变量。
  

函数

LLVM IR的函数和C语言的函数类似：

• 都有函数声明
  
• 都通过ret（return）语句返回
  

图中 local_unnamed_attr 也是一个用于优化的标识
表示一个全局符号在当前模块中具有未命名的本地链接，不需要在模块外部进行链接。它通常用于定义某个模块内部使用的常量或函数等，这些常量或函数不需要在模块外部被使用或链接。使用 local_unnamed_addr属性可以使编译器在优化时更容易地识别出这些不需要在模块外部链接的符号，并进行相应的优化。

如图所示，LLVM IR和C语言中的函数参数是一一对应的，但是LLVM IR中不标变量名。

• restrict 对应到 noalias ，表示这个变量没有别的引用（别名）。
  
• nocapture 表示该参数所指向的内存区域确实不会被传递到其他函数中。
  
• readonly 表示只读
  

这三个都说为了编译优化而打上的标签。
分支（If-then-else）

分支的if块和else块

LLVM的分支会被映射到基本块


基本块只要从第一句进入，就必须不跳过的全部执行完。
LLVM会把基本块给抽象为这样的控制流图，来分别进行块内和块间的优化。


分支条件的判定

分支条件的判定在LLVM中分为两步：

• 比较—— icmp (int compare)
  
• 跳转—— br (*br*anch)
  

• slt 表示‘set on less than’，意为如果 %0 的值小于2那么 %2 为True。
  
• br 语句可以理解为C语句 %2==True ? 进入 label %9 : 进入 label %3
  

无条件分支



无条件分支的存在是为了解决“菱形”控制流图的问题，也就是无论执行if还是else，最终都要喝到一处，因此if和else的最后都需要使用无条件分支和到一处。


循环（Loop）

一个循环有四个部分：

• 初始化
  
• 循环体
  
• 是否进入循环的条件断言
  
• 循环后操作（++i）
  

他们会被分别映射到LLVM IR：

• i 存储在 %9 中， phi 指令我们在后面会讲。他的目的是给 i 赋值——如果循环体是从循环外的基本块（ label %6 ）进入的，就赋值0，如果是从循环中再次进入的循环（ label %8 ）就赋值给他 i++ 之后的值（ %14 ）
  
• 循环体结束后先进行 i++ （ %14 = ... ），后进行分支判断（ %15 = ... 和 br ... ）。
  

具体而言映射关系如下：


因为LLVM IR采用静态单复制（Static Single Assignment），也就是一个寄存器在一个块中只能被赋值一次。但是在这个循环块中 如果从循环外进入 i 应该为0，如果从循环体内进入应该为 i++ ，所以使用phi语句来起到“条件分支”的作用。
总结

• LLVM IR中将所有计算出的值都存在寄存器中。
  
• LLVM使用静态单赋值——每个寄存器在一个基本块中只能被写一次。
  
• LLVM中一个函数被抽象为以基本块为节点的控制流图。
  
• 和C相比，LLVM中的操作都是显式的——没有隐含的size、没有隐含的变换。
  

周建群

同学，麻烦问一下，这个网课哪里能看啊？

牙簽大少

B站上就有视频。官方网站是https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/resources/lecture-videos/

新会陈皮茶业

B站上就有视频。官方网站是https://ocw.mit.edu/courses/6-172-performance-engineering-of-software-systems-fall-2018/resources/lecture-videos/

五千金

十分感谢！[调皮]

火炬哥

垃圾内容，路过为证。