LLVM Cookbook中文版

本书特色：简洁明了、容易效仿的风格||选择*重要的任务和问题||仔细组织有效解决问题的指令||清晰解释所完成的工作||将解决方案应用于其他场景

本书包括以下内容：

√ 介绍LLVM的模块化设计及LLVM工具

√ 编写一门语言的前端

√ 增加JIT支持，使用不同语言的前端

√ 学习LLVM Pass基础架构及LLVM Pass管理器

√ 创建分析和转换的优化Pass

√ 从头开始构建LLVM TOY语言后端

√ 在SelectionDAG的层面进行代码优化，并实现寄存器分配

《LLVM Cookbook中文版》以任务驱动的方式，带领读者编写基于LLVM 的编译器前端、优化器、后端。通过丰富的实例，读者能够从中理解LLVM 的架构，以及如何使用LLVM 来编写自己的编译器。

相比于传统的介绍编译技术的书籍，此书更偏向于实战，因此适合熟悉编译但对LLVM 比较陌生的人员，也适合正在学习编译技术并且在寻找实战机会的人员。

Mayur Pandey 是一名专业的软件工程师，同时也是一位开源软件的爱好者。他专注于编译器以及编译器工具的开发，是LLVM 开源社区的活跃贡献者，也是Tizen 编译器项目的一员，他对其他编译器也有着亲身实践经验。

Mayur 在印度阿拉哈巴德的Motilal Nehru 国家技术研究所获得学士学位。目前居住在印度班加罗尔。

Suyog Sarda 是一名专业的软件工程师，同时也是一位开源软件的爱好者。他专注于编译器以及编译器工具的开发，是LLVM 开源社区的活跃贡献者，也是Tizen 编译器项目的一员。除此之外，Suyog 也参与了ARM 和x86 架构的代码改进工作。他对其他的编译器也有着亲身实践经验。他对编译器的主要研究在于代码优化和向量化。除了编译器之外，Suyog 也对Linux 内核的开发很感兴趣。他曾在2012 年于迪拜由Birla技术协会举办的IEEE 国际云计算技术应用大会的议程上发表技术论文，题为“SecureCo-resident Virtualization in Multicore Systems by VM Pinning and Page Coloring”。他在印度普纳工程大学获得计算机学士学位。目前居住于印度班加罗尔。

前言 XI

第1 章 LLVM设计与使用 1

概述 1

模块化设计 2

交叉编译Clang/LLVM 6

将C 源码转换为LLVM 汇编码 8

将LLVM IR 转换为bitcode 9

将LLVM bitcode 转换为目标平台汇编码 12

将LLVM bitcode 转回为LLVM 汇编码 14

转换LLVM IR 15

链接LLVM bitcode 18

执行LLVM bitcode 19

使用C 语言前端——Clang 20

使用GO 语言前端 24

使用DragonEgg 25

第2 章 实现编译器前端 29

概述 29

定义TOY 语言 30

实现词法分析器 32

定义抽象语法树 35

实现语法分析器 38

解析简单的表达式 39

解析二元表达式 42

为解析编写驱动 45

对TOY 语言进行词法分析和语法分析 47

为每个AST 类定义IR 代码生成方法 48

为表达式生成IR 代码 49

为函数生成IR 代码 51

增加IR 优化支持 55

第3 章 扩展前端并增加JIT 支持 57

概述 57

处理条件控制结构——if/then/else 结构 58

生成循环结构 64

处理自定义二元运算符 71

处理自定义一元运算符. 77

增加JIT 支持 83

第4 章 准备优化 87

概述 87

多级优化 88

自定义LLVM Pass 89

使用opt 工具运行自定义Pass 92

在新的Pass 中调用其他Pass 93

使用Pass 管理器注册Pass 96

实现一个分析Pass 99

实现一个别名分析Pass 102

使用其他分析Pass 105

第5 章 实现优化 109

概述 109

编写无用代码消除Pass 110

编写内联转换Pass 115

编写内存优化Pass 119

合并LLVM IR 121

循环的转换与优化 123

表达式重组 126

IR 向量化 127

其他优化Pass 134

第6 章 平台无关代码生成器 139

概述 139

LLVM IR 指令的生命周期 140

使用GraphViz 可视化LLVM IR 控制流图 143

使用TableGen 描述目标平台 150

定义指令集 151

添加机器码描述 152

实现MachineInstrBuilder 类 156

实现MachineBasicBlock 类 157

实现MachineFunction 类 159

编写指令选择器 160

合法化SelectionDAG 166

优化SelectionDAG 173

基于DAG 的指令选择 179

基于SelectionDAG 的指令调度 186

第7 章 机器码优化 191

概述 191

消除机器码公共子表达式 192

活动周期分析 203

寄存器分配 209

插入头尾代码 215

代码发射 219

尾调用优化 221

兄弟调用优化 225

第8 章 实现LLVM 后端 227

概述 227

定义寄存器和寄存器集合 228

定义调用约定 230

定义指令集 231

实现栈帧lowering 232

打印指令 236

选择指令 240

增加指令编码 244

子平台支持 246

多指令lowering 249

平台注册 251

第9 章 LLVM项目最佳实践 265

概述265

LLVM 中的异常处理 265

使用sanitizer 271

使用LLVM 编写垃圾回收器 273

将LLVM IR 转换为JavaScript 279

使用Clang 静态分析器 281

使用bugpoint 282

使用LLDB 286

使用LLVM 通用Pass 291

译者序

LLVM 这个名字源于Lower Level Virtual Machine，但这个项目并不局限于创建一个虚拟机，它已经发展成为当今炙手可热的编译器基础框架。LLVM 最初以C/C++为编译目标，近年来经过众多机构和开源社区的努力，LLVM 已经能够为ActionScript、D、Fortran、Haskell、Java、Objective-C、Swift、Python、Ruby、Rust、Scala 等众多语言提供编译支持，而一些新兴语言则直接采用了LLVM 作为后端。可以说，LLVM 对编译器领域的发展起到了举足轻重的作用。

本书是目前为数不多的介绍LLVM 的书籍。本书从LLVM 的构建与安装开始说起，介绍了LLVM 的设计思想、LLVM 工具链、前端、优化器、后端，涵盖了LLVM 的绝大部分内容。本书以任务驱动的方式对内容进行介绍，围绕着实现TOY 语言的编译器，每一章节都会带领读者编写代码。在第2 章实现了编译器的前端，第4、5 章逐步实现优化器，后面的章节则实现了编译器后端。书中以实践的方式进行讲述，既阐述了原理，又让读者参与到编译器的开发当中，这一方面降低了学习LLVM 的门槛，另一方面也让读者在实践中理解LLVM 的细节。

作为译者，我觉得能够翻译此书也是一种缘分。最初是因为一次偶然的机会，我接触了一些自然语言处理的内容，在此过程中我领悟了词法分析和语法分析是怎么一回事；之后凭借着自己先前了解的零零碎碎的知识，在没有系统学习过编译原理的情况下写出了自己的第一个解释器（当然它很不完备）；接着便去系统学习编译原理，由于有了一定的实践基础，理解那些概念也轻松了许多；而关于这本书的翻译，则是因为在豆瓣上看到了一位豆友转发的消息，遂联系出版社的张春雨老师；最后在翻译此书的过程中，也收获了很多。

所以在这里要感谢带我走近自然语言处理的那位朋友，要感谢转发此消息的那位豆友，还要感谢博文视点的张春雨老师。人生充满了机缘巧合，我很幸运能够遇见你们。

与此同时，我也希望此书能够揭开编译器的面纱，能够让国内更多的人了解编译技术。

王欢明

2015 年8 月

程序员在编程时没有一刻可以离开编译器。简单来说，所谓编译器就是把人类可读的高级语言映射到机器执行码。但你知道这里面发生了什么吗？编译器在生成优化过的机器码之前还做了很多处理工作，一个好的编译器包含了很多复杂的算法。

这本书介绍了编译的几个阶段：前端处理、代码优化、代码生成等。为了将这个复杂的过程简化，LLVM 使用了模块化的思想，使得每一个编译阶段都被独立出来；LLVM 使用面向对象的C++语言完成，为编译器开发人员提供了易用而丰富的编程接口和API。所以，LLVM 可能是最容易学习的编译器框架了。

作为作者，我们认为简单的解决方案往往会比复杂的解决方案更加奏效；通过这本书，我们将会了解许多编译技术，它能提升你的能力，让你了解编译选项，理解编译过程。

我们也相信，那些从事编译器开发的程序员会从本书收益良多，因为对编译器技术的了解会帮助他们写出更好的代码。

我们希望你能喜欢这本书，享受这本书提供的技术盛宴，也能开发自己的编译器。迫不及待了吗？让我们开始吧。

本书概述

第1 章：LLVM 设计与使用。本章介绍了模块化的LLVM 基础架构设计，让你学会如何下载安装LLVM 和Clang，通过一些例子来了解如何使用LLVM 工作，也会介绍一些其他的编译器前端。

第2 章：实现编译器前端。本章介绍了如何为一门编程语言编写一个编译器前端，我们通过为一门玩具语言写一个玩具编译器，来了解如何把前端语言映射到LLVM IR。

第3 章：扩展前端并增加JIT 支持。本章为这门玩具语言增加了一些现代语言的高级特性，以及对前端的JIT 支持。

第4 章：准备优化。本章介绍LLVM IR 的Pass 结构，以及不同的优化级别和每一级别上的优化技术。我们也将看到如何一步一步编写自己的LLVM Pass。

第5 章：实现优化。本章介绍如何在LLVM IR 上实施诸多优化Pass，以及在LLVM开源代码上实现一些向量化技术。

第6 章：平台无关代码生成器。本章介绍了一个平台无关代码生成器的抽象结构，如何把LLVM IR 转换到有向无环图（DAG），以及如何进一步生成目标平台机器码。

第7 章：机器码优化。本章介绍了DAG 的优化过程，目标寄存器分配算法，还介绍了Selection DAG 上的各种优化技术及不同寄存器的分配技术。

第8 章：实现LLVM 后端。本章介绍了目标架构，包括寄存器、指令集、调用约定、编码、子平台特性等。

第9 章：LLVM项目最佳实践。本章介绍了一些使用LLVM IR 做代码分析的其他项目。需要记住的是，LLVM 不仅仅是一个编译器，而且是一个编译器框架。本章介绍了一段可应用到各种项目的代码，可从中获取有用信息。

阅读背景

你只需要一台Linux 计算机，最好是Ubuntu 系统，就能完成本书的大部分例子。你也需要一个简单的文本或代码编辑器、网络连接，以及一个浏览器。我们建议安装两个文件的合并包，它在大部分Linux 平台都能运行。

读者对象

本书适合那些熟悉编译器概念并且想理解学习LLVM 的程序员。

本书也适合不直接参与编译器开发但参与大量代码开发的程序员。具备一定的编译器知识将会使你写出更加优秀的代码。

内容组织

在此书中你会频繁地看到一些标题，例如准备工作、详细步骤、工作原理、更多内容、另请参阅。

为了更好地呈现本书内容，我们采用了如下的组织方式。

准备工作

这部分对章节做了概述，并且描述了如何配置软件及其他工具。

详细步骤

这部分涵盖了具体的实践步骤。

工作原理

这部分涵盖了前一部分的详细解释。

更多内容

这部分涵盖了关于章节的更多信息。

另请参阅

这部分涵盖了参考资料的链接。

约定

在本书中你会发现大量用不同格式展示的文字，这里举例说明它们的涵义。

嵌入代码、数据库表名、目录名、文件名、文件扩展名、路径名、URL、用户输入、Twitter 用如下方式展示：“我们可以用include 指令引入其他的上下文。”

代码块用如下格式：

primary := identifier_expr :

LLVM Cookbook 中文版

【XIV】

=numeric_expr

:=paran_expr

当我们想强调部分代码块时，相关行会使用粗体：

primary := identifier_expr

:=numeric_expr

:=paran_expr

命令行输入和输出用如下格式：

$ cat testfile.ll

新的术语和重要单词也会用黑体显示。你在屏幕上看到的内容，包括对话框或菜单，会这样显示：“单击下一步将进入下一屏”。

下载示例代码

你可以从https://www.broadview.com.cn 下载所有已购买的博文视点书籍的示例代码文件。

勘误表

虽然我们已经尽力谨慎地确保内容的准确性，但错误仍然存在。如果你发现了书中的错误，包括正文和代码中的错误，请告诉我们，我们会非常感激。这样，你不仅帮助了其他读者，也帮助我们改进后续的出版。如发现任何勘误，可以在博文视点网站相应图书的页面提交勘误信息。一旦你找到的错误被证实，你提交的信息就会被接受，我们的网站也会发布这些勘误信息。你可以随时浏览图书页面，查看已发布的勘误信息。