基于LLVM的編譯原理簡明教程 (1) - 寫編譯器越來越容易了
進(jìn)入21世紀(jì)光督，新的編程語言如雨后春筍一樣不停地冒出來。需求當(dāng)然是重要的驅(qū)動(dòng)力量毡琉，但是在其中起了重要作用的就是工具鏈的改善婉宰。
2000年，UIUC的Chris Lattner主持開發(fā)了一套稱為LLVM(Low Level Virtual Machine)的編譯器工具庫套件拌夏。后來僧著，LLVM的scope越來越大叫编，Low Level Virtual Machine已經(jīng)不足以表示LLVM的全部，于是霹抛，LLVM就變成了正式的名字搓逾。LLVM可以用于常規(guī)編譯器，JIT編譯器杯拐，匯編器霞篡，調(diào)試器，靜態(tài)分析工具等一系列跟編程語言相關(guān)的工作端逼。
后來朗兵，Chris Lattner又主持開發(fā)了Clang，針對C/C++/Objective-C的前端顶滩。這個(gè)編譯器直接挑戰(zhàn)了GCC的統(tǒng)治地位余掖。成為Apple系統(tǒng)的主要編譯器，在Android中礁鲁，指名使用Clang的模塊也越來越多盐欺。
2012年，LLVM榮獲美國計(jì)算機(jī)學(xué)會(huì)ACM的軟件系統(tǒng)大獎(jiǎng)仅醇，跟UNIX冗美，WWW，TCP/IP析二，TeX粉洼，Java等經(jīng)典系統(tǒng)作伴。
ACM系統(tǒng)獎(jiǎng)完全名單
另外再八卦幾句LLVM的主要作者和架構(gòu)師Chris Lattner叶摄。這哥們生于1978年属韧。
2005年，Chris Lattner加入Apple蛤吓。因?yàn)锳pple對于GCC支持Objective-C不力的不滿宵喂，LLVM和Clang成為Apple替代GCC的殺手級武器。
2010年柱衔，Chris Lattner又開始主持開發(fā)Swift語言樊破。
好了，言歸正傳唆铐。首先我們想說明的是哲戚，跟學(xué)院派的厚書給大家的印象不同，其實(shí)用LLVM寫個(gè)簡單的編譯器是件容易的事情艾岂，因?yàn)榇蟛糠质虑長LVM都替我們做了顺少。
用LLVM做個(gè)簡單的編譯器很容易
我們先看一個(gè)使用LLVM工具之后，實(shí)現(xiàn)一門編程語言的簡圖：
完全需要我們手工，或者依靠其他工具如lex, yacc來做的事情脆炎，是從源代碼到token的詞法分析和從token到AST的語法分析梅猿。也就是前端的主要部分需要我們來實(shí)現(xiàn)，畢竟我們是這門語言的定義者秒裕。在介紹LLVM的書里袱蚓，講前端的部分都是只占很小的篇幅的，所以大家可以take it easy.
在LLVM的萬花筒語言例子里几蜻，帶有注釋的詞法分析和語法分析也不過400行喇潘。大家如果覺得還復(fù)雜，后面我會(huì)帶大家做一些更簡單的梭稚，先完成一小部分功能颖低，然后迭代式開發(fā)。區(qū)區(qū)百余行代碼弧烤，不需要學(xué)習(xí)編譯原理忱屑。
比如Clang就是一個(gè)實(shí)現(xiàn)了C/C++/Objective-C的前端。
從AST轉(zhuǎn)LLVM開始暇昂，LLVM就開始提供一系列的工具幫助我們快速開發(fā)莺戒。從IR(中間指令代碼)到DAG(有向無環(huán)圖)再到機(jī)器指令，針對常用的平臺(tái)话浇，LLVM有完善的后端脏毯。也就是說，我們只要完成了到IR這一步幔崖，后面的工作我們就享有和Clang一樣的先進(jìn)生產(chǎn)力了。
口說無憑渣淤，有例子為證赏寇，這是將二元表達(dá)式AST轉(zhuǎn)成IR的函數(shù)：
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，在這個(gè)階段完全不用關(guān)心价认，LLVM會(huì)幫我們生成相應(yīng)的代碼嗅定。
下面我們再看一個(gè)聲明函數(shù)原型的：
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;
}
詞法分析
在正則表達(dá)式已經(jīng)成為基本技能的今天，詞法分析完全無門檻啊用踩。正常情況下渠退，我們只要寫一組正則表達(dá)式，或者寫個(gè)簡單的狀態(tài)機(jī)就可以了脐彩。
詞法分析的輸出是將源代碼解析成一個(gè)個(gè)的token碎乃。這些token就是有類型和值的一些小單元，比如是關(guān)鍵字惠奸，還是數(shù)字梅誓，還是標(biāo)識(shí)符等等。這個(gè)階段不用管它們是如何組合的，都是干嘛的梗掰。
比如一個(gè)token類型是數(shù)值嵌言，值是3. 這個(gè)信息就已經(jīng)足夠了，至于這個(gè)3干嘛用及穗，后面整理AST的時(shí)候再放到合適的位置上去摧茴。
至于什么時(shí)上下文無關(guān)語言，什么是確定有窮自動(dòng)機(jī)埂陆，非確定有窮自動(dòng)機(jī)等等這些蓬蝶，暫時(shí)都不需要了解。
語法分析
語法分析誠然是比詞法分析要復(fù)雜一些猜惋。但是幸運(yùn)的是丸氛，對于絕大多數(shù)語句和表達(dá)式來講，并不需要高深的知識(shí)著摔，“移進(jìn)-歸約”是個(gè)好方法缓窜，但是在我們學(xué)習(xí)的相當(dāng)長的一段時(shí)期內(nèi)都用不上。
語法分析的輸出是抽象語法樹AST谍咆，既然是棵樹禾锤，自然構(gòu)造時(shí)需要遞歸。所以在大部分的語句中摹察，我們只按遞歸下降的方法就足夠了恩掷。
對于表達(dá)式，遞歸下降還不夠用供嚎，至少運(yùn)算符還有優(yōu)先級啊黄娘。所以針對表達(dá)式，我們還需要運(yùn)算符優(yōu)先分析法克滴。SLR逼争，LALR和LR暫時(shí)還用不上。
語法制導(dǎo)翻譯和中間代碼生成
從前面的簡單例子中我們已經(jīng)看到了劝赔，這部分大部分調(diào)用LLVM為我們提供的IR構(gòu)造工具就可以了誓焦。入門階段我們能想到的，如代碼塊着帽，函數(shù)調(diào)用杂伟，控制結(jié)構(gòu)等，LLVM都為我們準(zhǔn)備好了仍翰。
優(yōu)化
LLVM主我們提供了大量的優(yōu)化Pass供我們選擇和組合赫粥。在IR階段和機(jī)器碼階段，我們都將花大量的篇幅來討論優(yōu)化歉备。這可能也是我們真正感興趣的部分傅是。
詞法分析很簡單
我們看一個(gè)官方的例子，首先定義token的類型，有一種算一種吧喧笔。將來擴(kuò)展都是體力活帽驯。
enum Token {
tok_eof = -1,
...
// primary
tok_identifier = -4,
tok_number = -5
};
然后就是解析正則表達(dá)式，一點(diǎn)技術(shù)含量也沒有书闸，哈哈~
我對官方的版本做了一點(diǎn)刪節(jié)尼变，看起來可以更清楚一些：
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之類的工具很多浆劲，就是根據(jù)正則表達(dá)式來決定token類型嫌术，根據(jù)類型存一下對應(yīng)的值。
如果token的類型多牌借，就是搭積木度气，寫正則。都是體力活~
夠用的語法分析其實(shí)也很簡單
上面介紹了膨报，我們自頂向下磷籍，構(gòu)造抽象語法樹。
先定義個(gè)根類型吧：
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() {}
virtual Value *codegen() = 0;
};
我們先來個(gè)簡單的现柠，就表示一個(gè)數(shù)字院领。這個(gè)好辦，就一個(gè)節(jié)點(diǎn)够吩，存?zhèn)€數(shù)值比然。
/// NumberExprAST - Expression class for numeric literals like "1.0".
class NumberExprAST : public ExprAST {
double Val;
public:
NumberExprAST(double Val) : Val(Val) {}
Value *codegen() override;
};
再來一個(gè)例子，變量周循，就是一個(gè)變量名么强法。賦值是下一步的事情了。
/// 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;
};
函數(shù)原型：
/// 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去構(gòu)造一個(gè)數(shù)值的AST:
詞法分析時(shí)鱼鼓，已經(jīng)把這個(gè)數(shù)值暫存了拟烫，我們把它拿來用就是了。
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = llvm::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
再看看函數(shù)聲明的：
/// 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));
}
先讀函數(shù)名迄本，再找左括號(hào)，然后是參數(shù)列表课竣，最后是處理右括號(hào)嘉赎。什么嘛，一點(diǎn)技術(shù)含量也沒有于樟。公条。。
上面例子這些迂曲，都是沒有嵌套的靶橱，也不需要遞歸下降和算符優(yōu)先。這些是處理比如二元表達(dá)式的時(shí)候才會(huì)遇到的。我們可以先學(xué)習(xí)容易的关霸，先能把這些容易的組件組成一門雖然語言功能不全传黄，但是真正實(shí)現(xiàn)了從源碼到機(jī)器指令的編譯器。
上面的例子都來自官方的例子萬花筒(Keleidoscope)語言的片段队寇。官方教程當(dāng)然寫得已經(jīng)足夠好膘掰，但是還是稍嫌復(fù)雜了點(diǎn)，能生成一個(gè)可玩的編譯器的速度還是有點(diǎn)慢佳遣。我打算把學(xué)習(xí)曲線再降低一下识埋，通過不斷地迭代，一點(diǎn)一點(diǎn)搭起可玩的編譯器零渐，然后慢慢擴(kuò)充功能窒舟。
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的開發(fā)者都使用Ninja杀糯，我們也就follow他們吧扫俺。
我在Mac下，所以使用Homebrew來安裝CMake和Ninja固翰。Linux與些類似狼纬，GCC版本太舊之類的請自助。Windows我還沒試過骂际，后面更新一下吧疗琉。
- 在LLVM目錄下創(chuàng)建build目錄
- cd build
- cmake -G Ninja
- Ninja
寫個(gè)LLVM上的Hello,World程序吧
從AST轉(zhuǎn)IR開始，我們都要用到LLVM的工具啦歉铝。先寫個(gè)小程序?qū)W習(xí)一下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;
}
輸出結(jié)果如下：
; ModuleID = 'hello,llvm'
source_filename = "hello,llvm"
如何鏈接LLVM的庫
使用LLVM庫的話盈简，需要一大堆參數(shù).
下面是在我的電腦上的參數(shù)：
-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
每次都這么寫嚇?biāo)廊肆税 Ｓ谑荓LVM為我們提供了llvm-config工具太示。剛才我那一大串柠贤，是用下面的命令行生成的：
llvm-config --cxxflags --ldflags --system-libs --libs core
完整的編譯命令可以這么寫：
clang++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy
