编译器简介

—— 在 Siri 出现以前如何与计算机对话

译者：penghuster
作者：Nicole Orchard
原文：An Intro to Compilers

---

简单来说，编译器是一个翻译其他程序的程序。传统的编译器把源码翻译为电脑可识别的机器码。（一些编译器也可将源码翻译为另外一种编程语言。这类编译器被称为源码到源码的翻译器或转译器。）LLVM 是一个使用非常广泛的编译器项目， 由许多模块化的编译工具组成。

传统的编译器设计包括以下三部分：

• 前端（Frontend）翻译源码 为一种中间表示(IR)*。clang 是 LLVM 提供的 c 系列语言的前端工具。
• 优化器（Optimizer）分析 IR，并翻译为一种更有效率的形式。opt 是 LLVM 提供的优化工具。
• 后后端通过 IR 与目标硬件的指令集映射关系生成机器码。 llc 是 LLVM 提供的后端工具。
  *LLVM IR 是一种与汇编语言类似的低级语言。然而，它总是与特定的硬件相关。

你好，编译器👋

下面是一个简单的 c 程序，打印 “Hello， Compiler！”到标准输出。C 语法是容易阅读的，但是电脑却不知道如何处理它。我将通过编译的 3 个阶段，将该程序翻译为可执行的机器码。

// compile_me.c
// Wave to the compiler. The world can wait.

#include <stdio.h>

int main() {
  printf("Hello, Compiler!\n");
  return 0;
}

The Frontend

如上文所述，clang 是 LLVM 提供的 C 系列语言的前端工具。clang 由 c 前处理程序、词法分析程序、语法分析程序、语义分析程序和 IR 生成程序。

• C 前处理程序 在开始翻译为 IR 之前修改源码。该前处理程序会处理包含的外部文件，如上述代码中的 #include <stdio.h>。前处理程序将该代码行替换为所指文件(stdio.h)的整个内容，该 C 标准库文件包含了 printf 的函数声明。
  查看前处理程序的输出，需执行如下命令：
  clang -E compile_me.c -o preprocessed.i
• 词法分析程序也叫扫描程序或分词程序，它将一行字符转化为一行单词。每个单词或者记号将被归列于如下 5 种词法范畴：标点符号、关键字、标识符、字面量或注释。
  Tokenization of compile_me.c
• 语法分析程序决定这一串单词流在源语言中是否能够组成有效的句子。然后通过分析语法标记流，输出一个抽象语法书（abstract syntax tree，AST）。在 clang 语法树中的节点代表声明、语句和类型。
  compile_me.c 的语法树：
  
• 词法分析程序 借助语法树判断代码语句是否有有效的意义。该阶段检查类型错误。如果用 “zero” 代替 compile_me.c 文件中的 0，那么词法分析程序将由于 “zero” 不是 int 类型而抛出异常。
• IR 生成程序 翻译语法树为 IR。
  运行 clang 前端工具利用 compile_me.c 文件生成 LLVM IR：
  clang -S -emit-llvm -o llvm_ir.ll compile_me.c
  在 llvm_ir.ll 中的主函数为：

; llvm_ir.ll

@.str = private unnamed_addr constant [18 x i8] c"Hello, Compiler!\0A\00", align 1

define i32 @main() {
  %1 = alloca i32, align 4 ; <- memory allocated on the stack
  store i32 0, i32* %1, align 4
  %2 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([18 x i8], [18 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

declare i32 @printf(i8*, ...)

优化器

优化器的工作是根据它对于程序运行时行为的理解，提高代码执行效率。优化器输入 IR 输出优化后的 IR。LLVM 的优化工具—opt—的选项 -O2 将优化处理器执行该程序速度，选项 -Os 将优化改程序的大小。

比较 LLVM 前端工具生成的 LLVM IR 与执行如下指令生成的结果：
opt -O2 -S llvm_ir.ll -o optimized.ll
optimized.ll 中的主函数：

; optimized.ll

@str = private unnamed_addr constant [17 x i8] c"Hello, Compiler!\00"

define i32 @main() {
  %puts = tail call i32 @puts(i8* getelementptr inbounds ([17 x i8], [17 x i8]* @str, i64 0, i64 0))
  ret i32 0
}

declare i32 @puts(i8* nocapture readonly) 

在这个优化版本中，main 函数没有在栈上分配内存空间，因此
main 函数不占用任何内存。由于 printf 中没有用到格式化字符串，故优化代码中调用 puts 代替 printf。

当然，优化器不仅仅知道何时用 printf 替换 puts，也知道适时展开循环和内联化简单计算的结果。分析如下程序，该程序两个数相加并打印结果。

// add.c
#include <stdio.h>

int main() {
  int a = 5, b = 10, c = a + b;
  printf("%i + %i = %i\n", a, b, c);
}

这是未经优化的 LLVM IR：

@.str = private unnamed_addr constant [14 x i8] c"%i + %i = %i\0A\00", align 1

define i32 @main() {
  %1 = alloca i32, align 4 ; <- allocate stack space for var a
  %2 = alloca i32, align 4 ; <- allocate stack space for var b
  %3 = alloca i32, align 4 ; <- allocate stack space for var c
  store i32 5, i32* %1, align 4  ; <- store 5 at memory location %1
  store i32 10, i32* %2, align 4 ; <- store 10 at memory location %2
  %4 = load i32, i32* %1, align 4 ; <- load the value at memory address %1 into register %4
  %5 = load i32, i32* %2, align 4 ; <- load the value at memory address %2 into register %5
  %6 = add nsw i32 %4, %5 ; <- add the values in registers %4 and %5. put the result in register %6
  store i32 %6, i32* %3, align 4 ; <- put the value of register %6 into memory address %3
  %7 = load i32, i32* %1, align 4 ; <- load the value at memory address %1 into register %7
  %8 = load i32, i32* %2, align 4 ; <- load the value at memory address %2 into register %8
  %9 = load i32, i32* %3, align 4 ; <- load the value at memory address %3 into register %9
  %10 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i32 0, i32 0), i32 %7, i32 %8, i32 %9)
  ret i32 0
}

declare i32 @printf(i8*, ...)

这是优化后的 LLVM IR：

@.str = private unnamed_addr constant [14 x i8] c"%i + %i = %i\0A\00", align 1

define i32 @main() {
  %1 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i64 0, i64 0), i32 5, i32 10, i32 15)
  ret i32 0
}

declare i32 @printf(i8* nocapture readonly, ...)

随着变量值的内联化，优化后的 main 函数本质上减少了 17 到 18 行代码。由于变量为常量，opt直接计算了该和。 是否很酷？

后端

LLVM 的后端工具是 llc。它输入 LLVM IR 输出机器码的过程分为三个阶段：

• 指令选择是映射 IR 指令到目标机器的指令集。该步骤使用虚拟寄存器的无限命名空间。
• 寄存器分配是在目标机器架构上虚拟寄存器映射到真实寄存器的过程。我的 CPU 是 x86 架构，该架构只有 16 个寄存器。然而，编译器将会尽可能少的使用寄存器。
• 指令安排阶段是根据目标计算机的性能限制重排指令操作顺序。

运行如下命令将产生机器码。
llc -o compiled-assembly.s optimized.ll

_main:
    pushq   %rbp
    movq    %rsp, %rbp
    leaq    L_str(%rip), %rdi
    callq   _puts
    xorl    %eax, %eax
    popq    %rbp
    retq
L_str:
    .asciz  "Hello, Compiler!"

该程序是 x86 汇编语言，它是计算机说出的人可阅读的语言。某些人最终也许理解了我。 🙌

---

版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）