教程 | 编译器入门:没有siri的那些年,我们如何实现人机对话?

选自nicoleorchard

作者:Nicole Orchard

机器之心编译

参与:朱乾树、路雪

编译器可将源代码转换成计算机理解的可执行的机器代码,或将源代码转换成另一种编程语言。本文从 LLVM 入手介绍了编译器工具。

编译器不过就是一个翻译其它程序的程序。传统的编译器将源代码转换成计算机可理解的可执行的机器代码。(一些编译器将源代码转换为另一种编程语言,这些编译器被称为源到源转换器或转译器)。LLVM 是一个广泛使用的编译器项目,包括多个模块化的编译器工具。

传统的编译器设计包括三个部分:

  • 前端将源代码转换成一种中间表示(IR)。clang (http://clang.llvm.org/) 是 LLVM 项目中 C 类语言的前端工具。
  • 优化器解析 IR 并将其转换成一种更高效的形式。opt是 LLVM 项目的优化器工具。
  • 后端通过将 IR 映射到目标硬件指令集上来生成机器代码。llc 是 LLVM 项目的后端工具。

LLVM IR 是一种类似汇编的低级语言。但是,它不针对特定的硬件信息编程。

你好,编译器

下面是一个简单的打印「Hello,Compiler」字符串的 C 语言程序。虽然程序员可以读懂 C 语言语法,但是计算机却看的一脸懵逼。接下来我要过一遍编译的三个阶段,以便将以下程序转换成机器可执行的程序。

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

#include <stdio.h>

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

前端

前文讲到,clang 是 LLVM C 类语言的前端工具。Clang 由一个 C 预处理器、词法分析器(lexer)、解析器、语义分析器和中间表示生成器组成。

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)将一串字符转换成一串词。每个词或符号,按其属性被分配到对应的句法类别:标点符号、关键词、标识符、常量或注释。

compile_me.c 的词法分析:

解析器判定由词法分析器生成的一串词是否包含源语言中的有效语句。在分析完词的语法以后,解析器输出了一个抽象语法树(AST)。Clang AST 中的节点分别表示声明与类型。

compile_me.c 的 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 -S 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 函数没有在栈上分配内存,因为它没有使用任何内存。优化后的代码调用了 puts 函数而不是 printf 函数,因为它没有使用 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 对加法进行运算,因为所有的变量都是常量。很酷吧?

后端

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 汇编语言程序,是计算机和程序员共通的语言。看似晦涩,但肯定有人懂我。

相关资源

1. Engineering a compiler (https://www.amazon.com/Engineering-Compiler-Second-Keith-Cooper/dp/012088478X)

2. Getting Started with LLVM Core Libraries (https://www.amazon.com/Getting-Started-LLVM-Core-Libraries/dp/1782166920)

原文链接:https://nicoleorchard.com/blog/compilers

本文为机器之心编译,转载请联系本公众号获得授权。

原文发布于微信公众号 - 机器之心(almosthuman2014)

原文发表时间:2017-08-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏zhisheng

面向对象设计原则之依赖倒转原则

前两天的算法排序文章,《Java常用排序算法/程序员必须掌握的8大排序算法(上)》、《Java常用排序算法/程序员必须掌握的8大排序算法(下)》,没看的可以点上...

38580
来自专栏美团技术团队

Android热更新方案Robust开源,新增自动化补丁工具

我们在之前的博客文章中介绍了高兼容性、高稳定性的实时热更新解决方案Robust之后,业内反响强烈,不断有读者咨询我们什么时候开源。今天我们非常高兴地宣布,Rob...

52450
来自专栏tkokof 的技术,小趣及杂念

Coroutine,你究竟干了什么?(小续)

前篇中讲了一些自己关于Coroutine的理解,后来陆陆续续的又想到了一些,在此简单记录一下,内容不多,故作“小”续吧 :)

9620
来自专栏海说

[转]我的编码习惯 - 接口定义

工作中,少不了要定义各种接口,系统集成要定义接口,前后台掉调用也要定义接口。接口定义一定程度上能反应程序员的编程功底。列举一下工作中我发现大家容易出现的问题:

9830
来自专栏恰童鞋骚年

设计模式的征途—3.工厂方法(Factory Method)模式

上一篇的简单工厂模式虽然简单,但是存在一个很严重的问题:当系统中需要引入新产品时,由于静态工厂方法通过所传入参数的不同来创建不同的产品,这必定要修改工厂类的源代...

8320
来自专栏程序猿DD

程序员你为什么这么累[续]:编码习惯之接口定义

前传传送门:程序员你为什么这么累? 工作中,少不了要定义各种接口,系统集成要定义接口,前后台掉调用也要定义接口。接口定义一定程度上能反应程序员的编程功底。列举一...

384100
来自专栏Jimoer

经历的面试题,先做下部分总结。

17530
来自专栏PhpZendo

如何使用 Laravel Collections 类编写神级代码

Laravel 提供了一些超赞的组件,在我看来,它是目前所有 Web 框架中提供组件支持最好的一个。它不仅提供了开箱即用的视图(views)、身份认证(auth...

14120
来自专栏DOTNET

设计原则

一、面向对象应用程序开发原则(SOLID) 1单一职责原则(SRP) 定义: 一个类应该只有一个发生变化的原因。这条原则曾被称为内聚性,即一个模块的组成元素之间...

30270
来自专栏java一日一条

JAVA常见面试题及解答(精华)

这里,如果T类的一个对象写入一个持久的存储区域,a的内容不被保存,但b的将被保存。

13120

扫码关注云+社区

领取腾讯云代金券