编译器入门

2018-08-23 17:38:46 浏览数 (1)

编译器（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 语言的语法，但是机器并不认识它。我将通过三个编译步骤，使得机器能够执行这个程序。

代码语言：javascript复制
// 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 函数的声明。

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

代码语言：javascript复制
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:

代码语言：javascript复制
clang -S -emit-llvm -o llvm_ir.ll compile_me.c

在 llvm_ir.ll 中的 main 函数：

代码语言：javascript复制
; llvm_ir.ll

@.str = private unnamed_addr constant [18 x i8] c"Hello, Compiler!A0", 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 代码和优化后的代码：

代码语言：javascript复制
opt -O2 llvm_ir.ll -o optimized.ll

optimized.ll 的 main 函数：

代码语言：javascript复制
; optimized.ll

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

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. 优化器也会对循环进行展开，内联简单计算的结果。考虑下面的代码，它将两个数加起来并打印结果：

代码语言：javascript复制
// add.c
#include <stdio.h>

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

这是未优化的 LLVM IR：

代码语言：javascript复制
@.str = private unnamed_addr constant [14 x i8] c"%i   %i = %iA0", 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
   = 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:

代码语言：javascript复制
@.str = private unnamed_addr constant [14 x i8] c"%i   %i = %iA0", 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） 是对操作的重新安排，它反映了目标机器上的性能限制。

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

代码语言：javascript复制
llc -o compiled-assembly.s optimized.ll
代码语言：javascript复制
_main:
    pushq   %rbp
    movq    %rsp, %rbp
    leaq    L_str(%rip), %rdi
    callq   _puts
    xorl    �x, �x
    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

汇编语言

0 人点赞