Inside compilers - overview

about posts categories aya
8/18/2020 compiler

本文章是在朋友的强烈要求下作为科普性质而写成的，尽可能做到用最通俗的语言和例子把事情讲清楚。我一直也想把自己学到的知识输出出来，帮助到后来的人。

本文将对编译器的设计和相关概念作出直观的理解，以帮助对编译器和编程语言技术感兴趣的同学对该领域有一个基础的认识。

# 背景

编译器本身也是一个程序，这个程序负责将程序员编写的高级语言代码转换成机器可以理解的低级代码，通常情况下这些低级代码就是我们常说的机器码。

# 前端和后端

我们把编译器人工地分为前端和后端两个部分，每个部分负责不同的功能。

简单来说，编译器的前端主要负责以下逻辑：

  • 将源代码经过 Parse 转换成抽象语法树（英文缩写为 AST）
  • 在 AST 的基础上做去语法糖（desugar），将语法糖转换成其本质上的语法结构
  • 在 AST 的基础上做类型重建（type-reconstruction），这包括类型推导，类型检查
  • 在 AST 的基础上做语义分析，这包括借用检查，重载决议等
  • 在 AST 的基础上做简单的优化，比如死代码消除，常量折叠等
  • 将 AST 转换成 IR 以便编译器的后端对代码执行进一步的逻辑

而编译器的后端主要负责：

  • 接收前端提供的 IR 和相关数据
  • 对 IR 进行类型分析等正确性分析，对不合法的 IR 报错
  • 在 IR 基础上做进一步分析和优化，如数据流分析，指针分析，逃逸分析等等
  • 将 IR 转换成最终目标平台所能理解的机器码，其中包括寄存器分配，目标平台选择等
  • 生成可执行文件或字节码文件（对虚拟机平台而言，比如 JVM）

需要注意的是，上面所描述的步骤并不是严格顺序要求的，这意味着编译器的开发者们可以自行决定哪一步在前，哪一步在后，也可以决定将哪写步骤合并为一个步骤。这里将他们分开列出来，是为了在后文可以进一步对每一个步骤做更详细的描述。

值得一提的是，接收前端提供的 IR 和相关数据 被列在后端负责事项的第一条并不是脱裤子放屁。相反，这是必须的。因为许多现代编译器被设计为前后端分离（如 clang 和 llvm，clang 为前端，而 llvm 为后端），这意味着前端和后端可以是两个不同的程序，那么在程序之间传递数据就成为了刚需。同样地，在后端重新检查前端生成的 IR 是否正确可以保证后端实现的健壮，同时可以让一些巨佬能手写后端 IR（我就见过能手写 llvm-ir 的大佬）。

# 广义上的编译器

广义上来说，编译器可以被抽象为一个函数 compile :: String -> IR，这个函数的输入是 String，并且产生一个 IR 作为输出结果，这里使用 IR 作为输出是因为我们的编译器是前后端分离的。

我们的后端通常使用这样的函数来表示 codegen :: IR -> NativeCode，这里的 NativeCode 代码目标平台的二进制代码。

当然，也有时候我们直接这样定义编译 compile :: String -> NativeCode，因为这种情况下，我们并不关心前后端是否分离，我们只关心编译的结果（比如在用户眼中就是这样）。

还有一种特殊情况，我们这样定义编译 fn compile(); 那是因为博客的空间太小了，写不下那么多的东西（逃

# 前端

# 构建语法树

编译器拿到源代码后第一件事是 Parse，即将源代码转换成抽象语法树，而 Parse 过程又有两个小过程，一个是词法分析，一个是构建语法树。

执行词法分析的程序我们叫做 Lexer，Lexer 会将源代码分割成一个有一个的 Token，这个过程类似于正则表达式的匹配。Token 通常被翻译为词法元素，比如我们有下面的程序（不要在意是什么语言，因为我们是编译器，你可以实现任何你喜欢的语法的 Lexer 和 Parser）:

pub fn main() {
    println("hello world");
}

这个程序在经过 Lexer 处理后，会生成下面的一堆 Token:

Token { type: Keyword, text: "pub" }
Token { type: Space }
Token { type: Keyword, text: "fn" }
Token { type: Space }
Token { type: Identifier, text: "main" }
Token { type: LeftParentheses }
Token { type: RightParentheses }
Token { type: Space }
Token { type: LeftBrace }
Token { type: NewLine }
Token { type: Identifier, text: "println" }
Token { type: LeftParentheses }
Token { type: Literal, text: "\"hello world\"" }
Token { type: RightParentheses }
Token { type: SemiColon }
Token { type: NewLine }
Token { type: RightBrace }

其中，type 为 Keyword 的 Token 代表关键字，type 为 Identifier 的 Token 代表标志符，type 为 Literal 的 Token 代表字面量

我们还可以发现，其中有一些 type 为 Space，NewLine 的 Token 并没有任何用处，因为直觉告诉我们，源代码中的空行，空格并不会对源代码的意思产生任何影响，所以我们可以剔除这些没有用的 Token，只留下我们认为需要的:

Token { type: Keyword, text: "pub" }
Token { type: Keyword, text: "fn" }
Token { type: Identifier, text: "main" }
Token { type: LeftParentheses }
Token { type: RightParentheses }
Token { type: LeftBrace }
Token { type: Identifier, text: "println" }
Token { type: LeftParentheses }
Token { type: Literal, text: "\"hello world\"" }
Token { type: RightParentheses }
Token { type: SemiColon }
Token { type: RightBrace }

那么至此，Lexer 就完成了它的使命。接下来就轮到 Parser 来根据 Token 构建语法树了。

在正式构建语法树之前，我们先来定义一下我们的语法，因为没有规范的语法定义，我们的 Parser 不知道应该按照怎样的规矩来构建语法树。在这里，我们使用 BNF 规则 (opens new window) 来定义我们的语法。

fn_decl ::= qualifier? 'fn' id '(' params? ')' '{' body '}' ;

qualifier ::= 'pub';

id ::= [a-zA-Z][0-9a-zA-Z]*;

params ::= id ':' id;

body ::= stmt*;

stmt ::= id '(' args? ')' ';';

args ::= expr (',' expr)*;

expr ::= ...;

别急，别慌着去搜索 BNF 的语法，这里我们只需要知道非常简单的东西就行了：

  • BNF 规则使用 a ::= b 这样的语法来定义，其中 a 叫做规则的名字，b 叫做规则的生成式
  • 生成式中可以出现小括号，被小括号包起来的被视为匿名规则
  • 生成式中可以出现中括号，被中括号包括起来的元素中只能出现一个，可以用短横线(-)表示一个范围，如上文的 [a-zA-Z] 说明这里可以出现 a ～ z 和 A ～ Z 中的任何一个字符
  • 生成式中可以出现其他规则的名字，如上文中的 stmt ::= id '(' args? ')';，id 和 args 都是其他规则的名字
    • 如果其他规则的名字后面带着 ?，则说明这个规则是可选的，即这个规则可以被匹配，也可以不被匹配
    • 如果其他规则的名字后面带着 *，则说明这个规则可以出现多次，如上文中的 args ::= expr (',' expr)*;，第二个规则 (',' expr) 可以出现多次
    • 如果其他规则的名字后面带着 +，则说明这个规则至少出现一次

不难发现，这其实很类似正则表达式，恭喜你，你已经学会了 BNF（

这里我并没有给出 expr 规则的具体模式，因为 expr 是一个很复杂的结构，这里我们为了方便，只要记得这个 expr 可以表示 "hello world" 这个字面量就够了。

这里我们让 Parser 从 fn_decl 这个规则开始解析 Token，那么这个过程如下:

  1. qualifier?: 我们先解析 qualifier
    1. 'pub': 匹配到了 Token { type: Keyword, text: "pub" }
  2. 'fn': 匹配到了 Token { type: Keyword, text: "fn" }
  3. id: 匹配到了 Token { type: Identifier, text: "main" }
  4. '(': 匹配到了 Token { type: LeftParentheses }
  5. params?: 这是一个可选的匹配
    1. 先看 params 的产生式中的第一个规则 id: 并没有出现 id，所以结束
    2. 该规则匹配结果为空
  6. ')': 匹配到了 Token { type: RightParentheses }
  7. '{': 匹配到了 Token { type: LeftBrace }
  8. stmt*: 这是一个多项匹配
    1. 先看产生式中第一个规则 id: 匹配到了 Token { type: Identifier, text: "println" }
    2. '(': 匹配到了 Token { type: LeftParentheses }
    3. args?: 这是一个可选匹配
      1. args 的第一个规则 expr: 匹配到了 Token { type: Literal, text: "\"hello world\"" }
      2. 接下来看 (',' expr)*: 没有出现 ,, 于是结束
    4. ')': 匹配到了 Token { type: RightParentheses }
    5. ';': 匹配到了 Token { type: SemiColon }
  9. '}': 匹配到了 Token { type: RightBrace }
  10. 接下来根据匹配到的 Token 建立 AST

我们最终得到了这样的 AST:

FnDecl {
    qualifier: "pub",
    id: "main",
    params: [],
    body: [
        Stmt {
            id: "println",
            args: [
                Expr("\"hello world\"")
            ]
        }
    ],
}

# 去语法糖

要去语法糖，我们得首先知道语法糖是什么。语法糖就是一类能让编程语言写起来更舒服的语法，但他们和其他语法元素不一样的地方在于：语法糖会在真正进入复杂的解析（如类型重建，语义分析等等）之前被转换成更一般的语法结构，这个转换的过程就叫做去语法糖。

在我们常见的语言中，有很多这样的语法糖。我们以 Java 为例，Java 的字符串拼接运算符实际上是一种语法糖，如下面的程序:

String s = "hello" + "world";

在去语法糖后就会变成这样:

String s = new StringBuilder().append("hello").append("hello").toString();

又比如我们熟悉的 C 语言中，对指针/数组用下标访问也是一种语法糖:

int a = array[pos];

在经过去语法糖以后就变成了这样:

int a = *(array + pos);

在现代语言中，往往还有更复杂的语法糖，如 async/await (opens new window)，一个这样的 async 函数:

async fn get() -> i32 {
    0
}

在经过去语法糖后，就可能变成了这样:

fn get() -> Future<i32> {
    future::ready(0)
}

这里并不介绍解糖的具体算法，因为本文仅仅只在概念上作出解释，而不会涉及到具体的算法细节。

# 类型重建

在上面的过程中，我们得到的 AST 都是没有类型信息的，但是在类型重建过程中，我们会通过一定的算法将原始 AST 转换成带类型的 AST (typed AST)。

在这个过程中，我们会检查用户编写的代码中是否有类型错误，如:

  • while 循环的条件表达式的类型是否为 Bool
  • 三目运算符 (a ? b : c) 中 b 和 c 的类型是否相同
  • match 表达式的每个分支是否都有相同的类型
  • 函数签名中的返回值类型是否和函数体中真正的返回值类型相同
  • 调用函数时所提供的参数的类型是否都和目标函数签名相同
  • ...

总之，许多跟类型有关的检查都发生在这一步，而这一步的关键就是类型推导。我们这里介绍一种运用的很广泛的类型推导算法 (Hindley-Milner)，这是一个被用于很多现代语言（如 Haskell 和 Rust）的类型推导算法。这个算法具有良好的可拓展性，可以在修改后适应不同的需求（如生命周期检测，借用检查等等）。我们这里只描述该算法的最基本原理。

由于篇幅关系，该算法的具体解释暂时省略（后续有专栏）。

# 语义分析

经过类型重建以后，我们的 AST 成功带上了类型信息，那么接下来就需要我们在 typed AST 上做更多更细致的检查了。这个过程叫做语义分析，我们会检查用户编写的代码中是否存在不合理的地方，如：

  • 是否存在不可达的代码
  • 函数是否真的能返回
  • 是否存在未使用的变量或者函数
  • 变量在使用前是否正确初始化
  • ...

在这一步之后，我们会在 AST 中带上更多的信息，这样的 AST 往往被称为 Decorated AST。之后，优化器可以利用这些信息作出进一步优化。

# 前端优化

我们的优化器主要工作在这一步。优化器会根据 Decorated AST 中提供的信息，执行一些优化步骤。常见的优化步骤有:

  • 死代码消除
  • 循环不变量优化
  • 循环展开
  • 尾递归优化
  • ...

需要注意的是，在这里发生的优化步骤多半也可以发生在后端，只是他们的实现难度不太一样。著名的 LLVM 后端会执行大量的提升代码效率的优化，所以有很多编译到 LLVM 的语言的编译器前端并不会自己实现上面这些优化，而是留给 LLVM 去进行。这是很明智的，因为代码优化是十分困难的，将工作留给后端可以减少前端开发人员的工作难度～

# 死代码消除

死代码是指永远不会被执行到的代码，比如这样的代码:

if (false) {
    println("this would never be printed")
}
println("hello world")

显然，这个 if (false) 中的代码永远也不会被执行，那么编译器就可以将这部分代码直接删除，最终得到的代码就可以像下面这样:

println("hello world")

# 循环不变量优化

循环不变量是指在每一次循环过程中都不会发生改变的变量，那么我们就可以将这个变量的计算过程提取到循环之外，以减少每次循环执行的重复代码数量，比如:

int sum = 0;
while (sum < get_max()) {
    sum += 1;
}

每次循环，我们都会调用一次 get_max() 并将其结果与 sum 比较，但如果我们的编译器可以确定 get_max() 是一个纯函数（即没有副作用的函数，即每次用相同的参数调用都会产生相同的结果，并且对其他变量没有影响），那么我们就可以将 get_max() 的调用提取到循环外面，用临时变量储存起来，然后循环时就不需要再次调用这个函数了。 所以我们会产生这样的代码:

int sum = 0;
int max = get_max();
while (sum < max) {
    sum += 1;
}

可以看到，这样的代码里每次循环不会再调用 get_max()，而是使用其之前存储过的值，这样就提升了代码的执行速度。

# 循环展开

在循环不变量优化中，我们减少了每次循环需要执行的代码数量从而提高了代码的运行效率。但还有一种情况，我们可以直接将整个循环展开，即直接在编译期计算出该循环的值，或者将该循环的循环体手动复制多次来减少比较的次数（循环需要对条件表达式进行比较，循环展开的主要目的就是减少比较次数，因为比较往往十分耗时）。

以上一例的代码为例，我们经过循环不变量优化后，得到了这样的代码:

int sum = 0;
int max = get_max();
while (sum < max) {
    sum += 1;
}

但我们的编译器如果足够强大，那么可以直接将上面的代码优化成下面的样子:

int sum = 0;
int max = get_max();
sum = max;

如果更强大一点，如果编译器能发现这个 max 只在 sum = max 处被使用，那么这段代码还可以被优化成这样:

int sum = get_max();

是不是很神奇呢～

# 生成 IR

编译器前端的最后一步就是生成 IR。IR 的全称是 Intermediate Representation (中间表示)，其作用在于将多种多样的前端 AST 抽象成一种更低级的中间代码。IR 往往和用户编写的源程序没有太多相似之处，以 llvm-ir 为例，我们可以使用 clang -S -emit-llvm 将 C 的源代码转换成 llvm-ir。

比如下面这样的 C 程序:

#include <stdio.h>
int main() {
    printf("hello world");
}

将其保存为 main.c 后我们在终端中执行如下命令:

clang -S -emit-llvm main.c

命令成功后，我们会在当前目录下得到 main.ll:

; ModuleID = 'main.c'
source_filename = "main.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.15.0"

@.str = private unnamed_addr constant [12 x i8] c"hello world\00", align 1

; Function Attrs: noinline nounwind optnone ssp uwtable
define i32 @main() #0 {
  %1 = call i32 (i8*, ...) 
    @printf(
        i8* getelementptr inbounds (
            [12 x i8], [12 x i8]* @.str, i32 0, i32 0
        )
    )
  ret i32 0
}

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

attributes #0 = { noinline nounwind optnone ssp uwtable 
    "correctly-rounded-divide-sqrt-fp-math"="false" "darwin-stkchk-strong-link" 
    "disable-tail-calls"="false" 
    "less-precise-fpmad"="false" 
    "min-legal-vector-width"="0" 
    "no-frame-pointer-elim"="true" 
    "no-frame-pointer-elim-non-leaf" 
    "no-infs-fp-math"="false" 
    "no-jump-tables"="false" 
    "no-nans-fp-math"="false" 
    "no-signed-zeros-fp-math"="false" 
    "no-trapping-math"="false" 
    "probe-stack"="___chkstk_darwin" 
    "stack-protector-buffer-size"="8" 
    "target-cpu"="penryn" 
    "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" 
    "unsafe-fp-math"="false" "use-soft-float"="false"
}

attributes #1 = { 
    "correctly-rounded-divide-sqrt-fp-math"="false" "darwin-stkchk-strong-link" 
    "disable-tail-calls"="false" 
    "less-precise-fpmad"="false" 
    "no-frame-pointer-elim"="true" 
    "no-frame-pointer-elim-non-leaf" 
    "no-infs-fp-math"="false" 
    "no-nans-fp-math"="false" 
    "no-signed-zeros-fp-math"="false" 
    "no-trapping-math"="false" 
    "probe-stack"="___chkstk_darwin" 
    "stack-protector-buffer-size"="8" 
    "target-cpu"="penryn" 
    "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" 
    "unsafe-fp-math"="false" "use-soft-float"="false" 
}

!llvm.module.flags = !{!0, !1, !2}
!llvm.ident = !{!3}

!0 = !{i32 2, !"SDK Version", [2 x i32] [i32 10, i32 15]}
!1 = !{i32 1, !"wchar_size", i32 4}
!2 = !{i32 7, !"PIC Level", i32 2}
!3 = !{!"Apple clang version 11.0.0 (clang-1100.0.33.8)"}

可以看到，经过前端的处理后，后端拿到的 IR 中包含的信息量十分巨大，我们可以从这里面看到我们的 main 函数被转换成了这样的形式:

@.str = private unnamed_addr constant [12 x i8] c"hello world\00", align 1

; Function Attrs: noinline nounwind optnone ssp uwtable
define i32 @main() #0 {
  %1 = call i32 (i8*, ...) 
    @printf(
        i8* getelementptr inbounds (
            [12 x i8], [12 x i8]* @.str, i32 0, i32 0
        )
    )
  ret i32 0
}


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

看不懂吗？看不懂就对了～

比如许多翻译软件都将英语作为 IR，那么他们只要实现其他语言和英语之间的互相翻译，那么就自然而然的实现了各种语言之间的互相翻译，这就是 IR 的作用的最简单理解方式。

# 后端

© Kiva 2019 – 2024