编译器入门

Myth丶恋晨 2022-06-10 08:42 229阅读 0赞

编译器（compiler）就是一个翻译其他程序的程序而已。传统的编译器将源代码翻译为计算机能够理解的可执行机器代码（有一些编译器将源代码翻译为另一种编程语言。这些编译器叫做从源码到源码的翻译器，source-to-source translators or transpilers）。[LLVM][] 是一个广泛使用的编译器项目，它包含了许多模块化的编译器工具。传统编译器涉及包含了三个部分：

![traditional compiler design][]

*  **前端（frontend）**将源代码翻译为一个中间表示（intermediate representation, **IR**）。`clang` 是 LLVM 中 C 系语言的前端。
 *  **优化器（optimizer）**会对 IR 进行分析，并将其翻译成一个更高效的形式。`opt` 是 LLVM 的优化器工具。
 *  **后端（backend）**通过将 IR 映射为目标硬件的指令集生成机器码。`llc` 是 LLVM 的后端工具。

**LLVM IR** 是一个类似汇编语言的低级语言。但是，它将针对特定硬件的信息抽象了出去。

## Hello, Compiler ##

下面是一个简单的 C 程序，它只是向标准输出打印出 “Hello, Compiler!”。虽然人类可以读懂 C 语言的语法，但是机器并不认识它。我将通过三个编译步骤，使得机器能够执行这个程序。

// 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 预处理器（preprocessor），词法分析器（lexer）,语法分析器（parser）,semantic analyzer（语义分析器）和中间表示生成器（IR generator）。

*  **C 预处理器** 在翻译成 IR 之前对源代码进行修改。预处理器会将外部文件包含进来，比如上面的`#include <stdio.h>`。它会用 C 标准库文件 `stdio.h` 的所有内容替换 `#include <stdio.h>` 这一行，`stdio.h` 包含了 `printf` 函数的声明。

*通过执行下列命令来查看预处理器步骤的输出：*

clang -E compile_me.c -o preprocessed.i

*  **词法分析器（lexer, 或者叫 scanner 或 tokenizer）** 将一串字符转换成一串词。每个词，或者叫 token （记号），被分配到 5 个句法的类别：punctuation（标点符号），keyword（关键词），identifier（标识符），literal（常量） 或 comment（注释）。

compile\_me.c 的 tokenization:

![tokennizaiton][]

*  **语法分析器**决定了由词法分析器生成的一串词是否包含了源语言中的有效句。在分析完词的语法以后，它输出了一个抽象语法树（abstract syntax tree, AST）。一个 Clang AST 中的节点表示 declaration，statement, type.

compile\_me.c 的 AST：

![AST][]

*  **语义分析器**遍历 AST，判定代码句的涵义是否有效。这个阶段会检查类型错误。如果 compile\_me.c 中的 main 函数返回了 `"zero"` 而不是 `0`, 语义分析器就会抛出一个错误，因为 `"zero"` 不是 `int` 类型。
 *  **IR 生成器** 将 AST 翻译为 IR。

*在 compile\_me.c 上运行 clang 前端来生成 LLVM IR:*

clang -S -emit-llvm -o llvm_ir.ll compile_me.c

在 llvm\_ir.ll 中的 main 函数：

; 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` （大写字母 o，2）标志优化处理器速度，`-Os` （大写字母 o，s）优化生成目标的大小。

来看一下优化器优化之前的 LLVM IR 代码和优化后的代码：

opt -O2 llvm_ir.ll -o optimized.ll

optimized.ll 的 main 函数：

; 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 没有在栈（stack）上分配内存，因为它没有使用任何内存。优化后的代码也没有调用 `printf`, 而是调用了 `puts`，因为它没有用到 `printf` 的任何格式化功能。

当然了，优化器知道的不仅仅是什么时候该用 `puts` 代替 `printf`. 优化器也会对循环进行展开，内联简单计算的结果。考虑下面的代码，它将两个数加起来并打印结果：

// 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` 对加法进行了计算，因为所有的变量都是常量。很酷，是吧？

## The Backend ##

LLVM 的后端工具是 `llc`.从 LLVM IR 输入生成机器码，它经历了三个阶段：

*  **指令选取（instruction selection）** 是从 IR 指令到目标机器指令集的映射。这一步使用了虚拟寄存器一个无限的命令空间。
 *  **寄存器分配（register allocation）** 是从虚拟寄存器到目标架构上真实寄存器的映射。我的 CPU 是 x86 架构，也就是说只能使用 16 个寄存器。但是，编译器会选择尽可能少地使用寄存器。
 *  **指令调度（instruction scheduling）** 是对操作的重新安排，它反映了目标机器上的性能限制。

*执行下面的命令将会产生一些机器码！*

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 汇编语言，它是目标机器能够读懂的语言的一个“人类表示”。目标机器只能读懂 0 和 1，汇编语言是将 0 1 代码用人类能够读懂的方式表达了出来。相信肯定会有人懂的:).

资源：  
1. [Engineering a compiler][]  
2. [Getting Started with LLVM Core Libraries][]

本文译自：[An Intro to Compilers][]

[LLVM]: http://llvm.org/
[traditional compiler design]: /images/20220610/f9d8f19ffca94fd6b88e1ab2165ed936.png
[tokennizaiton]: /images/20220610/369388d45e7c45bcab005e94c4f0eab6.png
[AST]: /images/20220610/a485e7edf9b34fc3af2e931ddfe0993d.png
[Engineering a compiler]: https://www.amazon.com/Engineering-Compiler-Second-Keith-Cooper/dp/012088478X
[Getting Started with LLVM Core Libraries]: https://www.amazon.com/Getting-Started-LLVM-Core-Libraries/dp/1782166920
[An Intro to Compilers]: https://nicoleorchard.com/blog/compilers