基于LLVM的编译原理简明教程 (1) - 写编译器越来越容易了-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

基于LLVM的编译原理简明教程 (1) - 写编译器越来越容易了

简介: 跟学院派的厚书给大家的印象不同,其实用LLVM写个简单的编译器是件容易的事情,因为大部分事情LLVM都替我们做了。

基于LLVM的编译原理简明教程 (1) - 写编译器越来越容易了

进入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等经典系统作伴。
ACM系统奖完全名单

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

好了,言归正传。首先我们想说明的是,跟学院派的厚书给大家的印象不同,其实用LLVM写个简单的编译器是件容易的事情,因为大部分事情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<Type *> 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_identifier
static 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<std::string> Args;

public:
  PrototypeAST(const std::string &Name, std::vector<std::string> Args)
      : Name(Name), Args(std::move(Args)) {}
  Function *codegen();
  const std::string &getName() const { return Name; }
};

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

/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
  auto Result = llvm::make_unique<NumberExprAST>(NumVal);
  getNextToken(); // consume the number
  return std::move(Result);
}

再看看函数声明的:

/// prototype
///   ::= id '(' id* ')'
static std::unique_ptr<PrototypeAST> 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<std::string> ArgNames;
  while (getNextToken() == tok_identifier)
    ArgNames.push_back(IdentifierStr);
  if (CurTok != ')')
    return LogErrorP("Expected ')' in prototype");

  // success.
  getNextToken(); // eat ')'.

  return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}

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

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

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

Hello,LLVM

LLVM的下载

  1. 先下载LLVM
svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm
  1. 在LLVM的tools目录下,下载Clang(可选,但是建议):
cd llvm/tools
svn co http://llvm.org/svn/llvm-project/cfe/trunk clang
  1. 在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我还没试过,后面更新一下吧。

  1. 在LLVM目录下创建build目录
  2. cd build
  3. cmake -G Ninja
  4. Ninja

写个LLVM上的Hello,World程序吧

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

#include "llvm/IR/Module.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <vector>

static llvm::LLVMContext TheContext;
static llvm::IRBuilder<> Builder(TheContext);
static std::unique_ptr<llvm::Module> TheModule;
static std::map<std::string, llvm::Value *> NameValues;

int main(){
 TheModule = llvm::make_unique<llvm::Module>("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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: