基于LLVM的编译原理简明教程: 写一个自己的编译器​

LLVM简介

进入21世纪，新的编程语言如雨后春笋一样不停地冒出来。需求当然是重要的驱动力量，但是在其中起了重要作用的就是工具链的改善。

2000年，UIUC的Chris Lattner主持开发了一套称为LLVM(Low Level Virtual Machine)的编译器工具库套件。后来，LLVM的scope越来越大，Low Level Virtual Machine已经不足以表示LLVM的全部，于是，LLVM就变成了正式的名字。LLVM可以用于常规编译器，JIT编译器，汇编器，调试器，静态分析工具等一系列跟编程语言相关的工作。

后来，Chris Lattner又主持开发了Clang，针对C/C++/Objective-C的前端。这个编译器直接挑战了GCC的统治地位。成为Apple系统的主要编译器，在Android中，指名使用Clang的模块也越来越多。2012年，LLVM荣获美国计算机学会ACM的软件系统大奖，跟UNIX，WWW，TCP/IP，TeX，Java等经典系统作伴。

另外再八卦几句LLVM的主要作者和架构师Chris Lattner。这哥们生于1978年。2005年，Chris Lattner加入Apple。因为Apple对于GCC支持Objective-C不力的不满，LLVM和Clang成为Apple替代GCC的杀手级武器。2010年，Chris Lattner又开始主持开发Swift语言。

LLVM简介

LLVM（wiki chs）是开源跨平台的编译器基础设施，包含一系列模块化的编译器组件和工具链，用来开发编译器前端和后端。源代码见：github 也可从官网下载代码 注：LLVM本身并不是编译器

LLVM架构提供了完整编译系统的中间层，与绝大多数编译器一样，LLVM架构也使用经典三段式的结构设计。

① 前端（Frontend）负责分析源代码【词法分析】，可以检查语法级错误【语法分析】，构建针对该语言的抽象语法树（Abstract Syntax Tree，AST）【语义分析】 ，并将代码编译成LLVM IR【IR生成】

② 抽象语法树可以进一步转换为优化，最终转为新的表示方式， 然后再交给优化器

③ 最终由后端生成可执行的机器码 注：如果需要增加一种处理器架构（如：arm64、x86等），只需要增加一种后端

Clang及许多GCC工具链都支持LLVM架构，能输出LLVM IR代码。LLVM已经成为多个编译器和代码生成相关子项目的母项目。 注：Clang是类C语言的编译器前端，是LLVM的一个子项目。

LLVM前端已支持的编程语言：C、C++、ActionScript、Ada、D语言、Fortran、GLSL、Haskell、Java字节码、Objective-C、Swift、Python、Ruby、Crystal、Rust、Scala以及C#等

LLVM后端已支持指令集架构：x86、x86-64、ARM、MIPS、PowerPC以及RISC-V等

相比之下，GCC的前端和后端没分得太开，耦合在一起。这使得GCC支持一门新的语言或新的目标平台，变得特别麻烦

LLVM的核心是IR语言（Intermediate Representation），一种类似汇编的底层语言。

IR是一种强类型的精简指令集（Reduced Instruction Set Computing，RISC），并对目标指令集进行了抽象。

LLVM IR有3种表示形式：

text：便于阅读的文本格式。扩展名为.llbitcode：二进制格式。扩展名为.bcmemory：内存格式

LLVM其他子项目

lld链接器

lld链接器子项目旨在为LLVM开发一个内置的，平台独立的链接器，去除对所有第三方链接器的依赖。

2017.5，lld已经支持ELF、PE/COFF和Mach-O可执行文件格式。

在lld支持不完全的情况下，用户可以使用其他项目，如GNU ld链接器、bfd链接器（ld.bfd）、gold链接器。 注：ld.gold是google在GNU ld上改进的链接器

C++标准库

LLVM项目包含一个叫做libc++的C++标准库的实现 注：GNU的为Libstdc++

lldb调试器

lldb（wiki）是LLVM的调试子项目，目前已支持C、C++及Objective-C。XCode5+、Android Studio缺省使用LLDB进行调试，LLDB也被VS Code、Eclipse等IDE使用。

参考

The Architecture of Open Source Applications: LLVM

LLVM IR语言参考

深入剖析 iOS 编译 Clang / LLVM （github链接）

好了，言归正传。首先我们想说明的是，跟学院派的厚书给大家的印象不同，其实用LLVM写个简单的编译器是件容易的事情，因为大部分事情LLVM都替我们做了。

用LLVM做个简单的编译器

我们先看一个使用LLVM工具之后，实现一门编程语言的简图：

编译器简图

完全需要我们手工，或者依靠其他工具如lex, yacc来做的事情，是从源代码到token的词法分析和从token到AST的语法分析。也就是前端的主要部分需要我们来实现，毕竟我们是这门语言的定义者。在介绍LLVM的书里，讲前端的部分都是只占很小的篇幅的，所以大家可以take it easy.

在LLVM的万花筒语言例子里，带有注释的词法分析和语法分析也不过400行。大家如果觉得还复杂，后面我会带大家做一些更简单的，先完成一小部分功能，然后迭代式开发。区区百余行代码，不需要学习编译原理。

比如Clang就是一个实现了C/C++/Objective-C的前端。

从AST转LLVM开始，LLVM就开始提供一系列的工具帮助我们快速开发。从IR(中间指令代码)到DAG(有向无环图)再到机器指令，针对常用的平台，LLVM有完善的后端。也就是说，我们只要完成了到IR这一步，后面的工作我们就享有和Clang一样的先进生产力了。

口说无凭，有例子为证，这是将二元表达式AST转成IR的函数：

Value *BinaryExprAST::codegen() {

...

switch (Op) {

case '+':

return Builder.CreateFAdd(L, R, "addtmp");

case '-':

return Builder.CreateFSub(L, R, "subtmp");

case '*':

return Builder.CreateFMul(L, R, "multmp");

case '<':

L = Builder.CreateFCmpULT(L, R, "cmptmp");

// Convert bool 0/1 to double 0.0 or 1.0

return Builder.CreateUIToFP(L, Type::getDoubleTy(TheContext), "booltmp");

default:

...

}

}

如何生成加减乘除的IR，在这个阶段完全不用关心，LLVM会帮我们生成相应的代码。下面我们再看一个声明函数原型的：

Function *PrototypeAST::codegen() {

// Make the function type: double(double,double) etc.

std::vector Doubles(Args.size(), Type::getDoubleTy(TheContext));

FunctionType *FT =

FunctionType::get(Type::getDoubleTy(TheContext), Doubles, false);

Function *F =

Function::Create(FT, Function::ExternalLinkage, Name, TheModule.get());

// Set names for all arguments.

unsigned Idx = 0;

for (auto &Arg : F->args())

Arg.setName(Args[Idx++]);

return F;

}

词法分析

在正则表达式已经成为基本技能的今天，词法分析完全无门槛啊。正常情况下，我们只要写一组正则表达式，或者写个简单的状态机就可以了。

词法分析的输出是将源代码解析成一个个的token。这些token就是有类型和值的一些小单元，比如是关键字，还是数字，还是标识符等等。这个阶段不用管它们是如何组合的，都是干嘛的。比如一个token类型是数值，值是3. 这个信息就已经足够了，至于这个3干嘛用，后面整理AST的时候再放到合适的位置上去。至于什么时上下文无关语言，什么是确定有穷自动机，非确定有穷自动机等等这些，暂时都不需要了解。

语法分析

语法分析诚然是比词法分析要复杂一些。但是幸运的是，对于绝大多数语句和表达式来讲，并不需要高深的知识，“移进-归约”是个好方法，但是在我们学习的相当长的一段时期内都用不上。语法分析的输出是抽象语法树AST，既然是棵树，自然构造时需要递归。所以在大部分的语句中，我们只按递归下降的方法就足够了。对于表达式，递归下降还不够用，至少运算符还有优先级啊。所以针对表达式，我们还需要运算符优先分析法。SLR，LALR和LR暂时还用不上。

语法制导翻译和中间代码生成

从前面的简单例子中我们已经看到了，这部分大部分调用LLVM为我们提供的IR构造工具就可以了。入门阶段我们能想到的，如代码块，函数调用，控制结构等，LLVM都为我们准备好了。

优化

LLVM主我们提供了大量的优化Pass供我们选择和组合。在IR阶段和机器码阶段，我们都将花大量的篇幅来讨论优化。这可能也是我们真正感兴趣的部分。

词法分析很简单

我们看一个官方的例子，首先定义token的类型，有一种算一种吧。将来扩展都是体力活。

enum Token { tok_eof = -1,

...

// primary

tok_identifier = -4,

tok_number = -5

};

然后就是解析正则表达式，一点技术含量也没有，哈哈~我对官方的版本做了一点删节，看起来可以更清楚一些：

static std::string IdentifierStr; // Filled in if tok_identifierstatic double NumVal; // Filled in if tok_number

/// gettok - Return the next token from standard input.

static int gettok() {

static int LastChar = ' ';

// Skip any whitespace.

while (isspace(LastChar))

LastChar = getchar();

if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*

IdentifierStr = LastChar;

while (isalnum((LastChar = getchar())))

IdentifierStr += LastChar;

...

return tok_identifier;

}

if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+

std::string NumStr;

do {

NumStr += LastChar;

LastChar = getchar();

} while (isdigit(LastChar) || LastChar == '.');

NumVal = strtod(NumStr.c_str(), nullptr);

return tok_number;

}

...

// Check for end of file. Don't eat the EOF.

if (LastChar == EOF)

return tok_eof;

...

}

如果不想手写的话，lex, flex之类的工具很多，就是根据正则表达式来决定token类型，根据类型存一下对应的值。如果token的类型多，就是搭积木，写正则。都是体力活~

够用的语法分析其实也很简单

上面介绍了，我们自顶向下，构造抽象语法树。先定义个根类型吧：

/// ExprAST - Base class for all expression nodes.class ExprAST {

public:

virtual ~ExprAST() {}

virtual Value *codegen() = 0;

};

我们先来个简单的，就表示一个数字。这个好办，就一个节点，存个数值。

/// NumberExprAST - Expression class for numeric literals like "1.0".class NumberExprAST : public ExprAST {

double Val;

public:

NumberExprAST(double Val) : Val(Val) {}

Value *codegen() override;

};

再来一个例子，变量，就是一个变量名么。赋值是下一步的事情了。

/// VariableExprAST - Expression class for referencing a variable, like "a".

class VariableExprAST : public ExprAST {

std::string Name;

public:

VariableExprAST(const std::string &Name) : Name(Name) {}

Value *codegen() override;

};

函数原型：

/// PrototypeAST - This class represents the "prototype" for a function,

/// which captures its name, and its argument names (thus implicitly the number

/// of arguments the function takes).

class PrototypeAST {

std::string Name;

std::vector Args;

public:

PrototypeAST(const std::string &Name, std::vector Args)

: Name(Name), Args(std::move(Args)) {}

Function *codegen();

const std::string &getName() const { return Name; }

};

然后我们再看看如何通过token去构造一个数值的AST:词法分析时，已经把这个数值暂存了，我们把它拿来用就是了。

/// numberexpr ::= number

static std::unique_ptr ParseNumberExpr() {

auto Result = llvm::make_unique(NumVal);

getNextToken(); // consume the number

return std::move(Result);

}

再看看函数声明的：

/// prototype

/// ::= id '(' id* ')'

static std::unique_ptr ParsePrototype() {

if (CurTok != tok_identifier)

return LogErrorP("Expected function name in prototype");

std::string FnName = IdentifierStr;

getNextToken();

if (CurTok != '(')

return LogErrorP("Expected '(' in prototype");

std::vector ArgNames;

while (getNextToken() == tok_identifier)

ArgNames.push_back(IdentifierStr);

if (CurTok != ')')

return LogErrorP("Expected ')' in prototype");

// success.

getNextToken(); // eat ')'.

return llvm::make_unique(FnName, std::move(ArgNames));

}

先读函数名，再找左括号，然后是参数列表，最后是处理右括号。什么嘛，一点技术含量也没有。。。

上面例子这些，都是没有嵌套的，也不需要递归下降和算符优先。这些是处理比如二元表达式的时候才会遇到的。我们可以先学习容易的，先能把这些容易的组件组成一门虽然语言功能不全，但是真正实现了从源码到机器指令的编译器。

上面的例子都来自官方的例子万花筒(Keleidoscope)语言的片段。官方教程当然写得已经足够好，但是还是稍嫌复杂了点，能生成一个可玩的编译器的速度还是有点慢。我打算把学习曲线再降低一下，通过不断地迭代，一点一点搭起可玩的编译器，然后慢慢扩充功能。

Hello,LLVM

LLVM的下载

先下载LLVM

svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm

在LLVM的tools目录下，下载Clang(可选，但是建议):

cd llvm/tools

svn co http://llvm.org/svn/llvm-project/cfe/trunk clang

在LLVM的projects目录下，可选下载compiler-rt，Libomp，libcxx，libcxxabi。

svn co http://llvm.org/svn/llvm-project/compiler-rt/trunk compiler-rt

svn co http://llvm.org/svn/llvm-project/openmp/trunk openmp

svn co http://llvm.org/svn/llvm-project/libcxx/trunk libcxx

svn co http://llvm.org/svn/llvm-project/libcxxabi/trunk libcxxabi

LLVM的编译

既然官方说大部分LLVM的开发者都使用Ninja，我们也就follow他们吧。我在Mac下，所以使用Homebrew来安装CMake和Ninja。Linux与些类似，GCC版本太旧之类的请自助。Windows我还没试过，后面更新一下吧。

在LLVM目录下创建build目录

cd build

cmake -G Ninja

Ninja

写个LLVM上的Hello,World程序吧

从AST转IR开始，我们都要用到LLVM的工具啦。先写个小程序学习一下LLVM的程序是如何编译的吧：

#include "llvm/IR/Module.h"

#include "llvm/IR/IRBuilder.h"

#include "llvm/IR/LLVMContext.h"

#include

#include

#include

#include

#include

static llvm::LLVMContext TheContext;

static llvm::IRBuilder<> Builder(TheContext);

static std::unique_ptr TheModule;

static std::map NameValues;

int main(){

TheModule = llvm::make_unique("hello,llvm",TheContext);

TheModule -> dump();

return 0;

}

输出结果如下：

; ModuleID = 'hello,llvm'

source_filename = "hello,llvm"

如何链接LLVM的库

使用LLVM库的话，需要一大堆参数.下面是在我的电脑上的参数：

-I/Users/ziyingliuziying/lusing/llvm/llvm/include -I/Users/ziyingliuziying/lusing/llvm/llvm/build/include -fPIC -fvisibility-inlines-hidden -Wall -W -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wcovered-switch-default -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Werror=date-time -std=c++11 -fcolor-diagnostics -fno-exceptions -fno-rtti -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS

-L/Users/ziyingliuziying/lusing/llvm/llvm/build/lib -Wl,-search_paths_first -Wl,-headerpad_max_install_names

-lLLVMCore -lLLVMSupport

-lcurses -lz -lm

每次都这么写吓死人了啊。于是LLVM为我们提供了llvm-config工具。刚才我那一大串，是用下面的命令行生成的：

llvm-config --cxxflags --ldflags --system-libs --libs core

完整的编译命令可以这么写：

clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy