3. Kaleidoscope：產生 LLVM IR 程式碼¶
3.1. 第三章 簡介¶
歡迎來到「使用 LLVM 實作語言」教學的第三章。本章將向您展示如何將第二章中建構的抽象語法樹轉換為 LLVM IR。這將讓您稍微了解 LLVM 的運作方式，並示範使用它的容易程度。建構詞法分析器和語法分析器比產生 LLVM IR 程式碼的工作量要大得多。 :)
請注意：本章及後續章節中的程式碼需要 LLVM 3.7 或更高版本。LLVM 3.6 及更早版本無法使用。另請注意，您需要使用與您的 LLVM 版本相符的教學版本：如果您使用的是官方 LLVM 版本，請使用您的版本中包含的文件版本或llvm.org 版本頁面上的文件版本。
3.2. 程式碼產生設定¶
為了產生 LLVM IR，我們需要一些簡單的設定來開始。首先，我們在每個 AST 類別中定義虛擬程式碼產生 (codegen) 方法
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
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;
};
...
codegen() 方法表示要為該 AST 節點及其所有依賴項發出 IR，並且它們都返回一個 LLVM Value 物件。「Value」是用於表示 LLVM 中「靜態單一賦值 (SSA) 暫存器」或「SSA 值」的類別。SSA 值最顯著的特點是它們的值是在相關指令執行時計算的，並且在指令重新執行之前（以及如果）不會獲得新值。換句話說，沒有辦法「更改」SSA 值。如需更多資訊，請閱讀靜態單一賦值 - 一旦您理解了這些概念，就會覺得它們非常自然。
請注意，除了向 ExprAST 類別階層添加虛擬方法之外，也可以使用訪客模式或其他方法來建模。同樣，本教學不會詳述良好的軟體工程實務：就我們的目的而言，添加虛擬方法是最簡單的。
我們想要的第二件事是一個類似於我們用於解析器的「LogError」方法，它將用於報告程式碼產生期間發現的錯誤（例如，使用未聲明的參數）
static std::unique_ptr<LLVMContext> TheContext;
static std::unique_ptr<IRBuilder<>> Builder(TheContext);
static std::unique_ptr<Module> TheModule;
static std::map<std::string, Value *> NamedValues;
Value *LogErrorV(const char *Str) {
LogError(Str);
return nullptr;
}
靜態變數將在程式碼生成期間使用。 TheContext 是一個不透明的物件，它擁有許多核心 LLVM 資料結構，例如型別和常數值表。我們不需要詳細了解它，我們只需要一個實例傳遞給需要它的 API。
Builder 物件是一個輔助物件，可以輕鬆生成 LLVM 指令。 IRBuilder 類別範本的實例會持續追蹤要插入指令的當前位置，並具有建立新指令的方法。
TheModule 是一個 LLVM 建構，其中包含函式和全域變數。在許多方面，它是 LLVM IR 用於包含程式碼的頂層結構。它將擁有我們生成的所有 IR 的記憶體，這就是 codegen() 方法傳回原始 Value* 而不是 unique_ptr<Value> 的原因。
NamedValues 對應會持續追蹤在當前作用域中定義了哪些值，以及它們的 LLVM 表示形式為何。（換句話說，它是程式碼的符號表）。在這種形式的 Kaleidoscope 中，唯一可以參考的是函式參數。因此，在為其函式主體生成程式碼時，函式參數將位於此對應中。
有了這些基礎知識後，我們就可以開始討論如何為每個表達式生成程式碼。請注意，這假設已設定 Builder 以將程式碼生成到*某個位置*。目前，我們假設這已經完成，我們將只使用它來發出程式碼。
3.3. 表達式程式碼生成¶
為表達式節點生成 LLVM 程式碼非常簡單：所有四個表達式節點的註釋程式碼不到 45 行。首先，我們將處理數值常數
Value *NumberExprAST::codegen() {
return ConstantFP::get(*TheContext, APFloat(Val));
}
在 LLVM IR 中，數值常數以 ConstantFP 類別表示，該類別在內部以 APFloat 儲存數值（APFloat 具有儲存任意精度浮點常數的功能）。此程式碼基本上只建立並傳回一個 ConstantFP。請注意，在 LLVM IR 中，常數都被唯一化並共用。因此，API 使用“foo::get(…)”習慣用法，而不是“new foo(..)”或“foo::Create(..)”。
Value *VariableExprAST::codegen() {
// Look this variable up in the function.
Value *V = NamedValues[Name];
if (!V)
LogErrorV("Unknown variable name");
return V;
}
使用 LLVM，對變數的參考也很簡單。在 Kaleidoscope 的簡單版本中，我們假設變數已經在某個地方發出，並且它的值是可用的。實際上，NamedValues 對應中唯一可以存在的值是函式參數。此程式碼只是檢查指定的變數是否在對應中（如果不在，則表示正在參考一個未知變數），並傳回其值。在後面的章節中，我們將在符號表中新增對 迴圈歸納變數 的支援，以及對 局部變數 的支援。
Value *BinaryExprAST::codegen() {
Value *L = LHS->codegen();
Value *R = RHS->codegen();
if (!L || !R)
return nullptr;
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:
return LogErrorV("invalid binary operator");
}
}
二元運算子開始變得更加有趣。這裡的基本思想是，我們遞迴地為表達式的左側發出程式碼，然後是右側，然後我們計算二元表達式的結果。在此程式碼中，我們對運算碼執行一個簡單的 switch 語句，以建立正確的 LLVM 指令。
在上面的例子中，LLVM builder 類別開始展現它的價值。IRBuilder 知道在哪裡插入新創建的指令，您只需要指定要創建的指令（例如，使用 CreateFAdd）、要使用的運算元（這裡是 L 和 R），以及選擇性地為生成的指令提供一個名稱。
LLVM 的一個好處是名稱只是一個提示。例如，如果上面的程式碼發出了多個「addtmp」變數，LLVM 會自動為每個變數提供一個遞增的、唯一的數字後綴。指令的局部變數名稱是純粹可選的，但它可以讓您更容易閱讀 IR 轉儲。
LLVM 指令 受限於嚴格的規則：例如，加法指令 的左運算元和右運算元必須具有相同的類型，並且加法的結果類型必須與運算元類型相符。因為 Kaleidoscope 中的所有值都是雙精度浮點數，所以加法、減法和乘法的程式碼非常簡單。
另一方面，LLVM 規定 fcmp 指令 一律返回一個「i1」值（一個一位元整數）。問題是 Kaleidoscope 希望值是 0.0 或 1.0。為了獲得這些語義，我們將 fcmp 指令與 uitofp 指令 結合使用。此指令通過將輸入視為無符號值，將其輸入整數轉換為浮點值。相反，如果我們使用 sitofp 指令，則 Kaleidoscope 的「<」運算符將根據輸入值返回 0.0 或 -1.0。
Value *CallExprAST::codegen() {
// Look up the name in the global module table.
Function *CalleeF = TheModule->getFunction(Callee);
if (!CalleeF)
return LogErrorV("Unknown function referenced");
// If argument mismatch error.
if (CalleeF->arg_size() != Args.size())
return LogErrorV("Incorrect # arguments passed");
std::vector<Value *> ArgsV;
for (unsigned i = 0, e = Args.size(); i != e; ++i) {
ArgsV.push_back(Args[i]->codegen());
if (!ArgsV.back())
return nullptr;
}
return Builder->CreateCall(CalleeF, ArgsV, "calltmp");
}
使用 LLVM 生成函數呼叫的程式碼非常簡單。上面的程式碼首先在 LLVM 模組的符號表中進行函數名稱查找。回想一下，LLVM 模組是存放我們正在 JIT 編譯的函數的容器。通過為每個函數指定與使用者指定的相同的名稱，我們可以使用 LLVM 符號表為我們解析函數名稱。
找到要呼叫的函數後，我們遞迴地對要傳入的每個參數進行程式碼生成，並創建一個 LLVM 呼叫指令。請注意，LLVM 預設使用原生 C 呼叫約定，允許這些呼叫也呼叫標準函數庫中的函數，例如「sin」和「cos」，而無需額外的努力。
至此，我們已經完成了對 Kaleidoscope 中目前擁有的四種基本表達式的處理。您可以隨意添加更多表達式。例如，通過瀏覽 LLVM 語言參考，您會發現其他一些有趣的指令，這些指令很容易插入到我們的基本框架中。
3.4. 函數程式碼生成¶
原型和函數的程式碼生成必須處理許多細節，這使得它們的程式碼不如表達式程式碼生成那麼漂亮，但可以讓我們說明一些要點。首先，讓我們談談原型的程式碼生成：它們既可以用於函數體，也可以用於外部函數聲明。程式碼以
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());
這段程式碼在幾行程式碼中包含了強大的功能。首先要注意，此函數返回一個「Function*」而不是「Value*」。因為「原型」實際上是關於函數的外部介面（而不是表達式計算的值），所以它在程式碼生成時返回對應的 LLVM 函數是有意義的。
呼叫 FunctionType::get 會建立一個用於給定 Prototype 的 FunctionType。由於 Kaleidoscope 中的所有函式引數都是 double 類型，因此第一行會建立一個包含「N」個 LLVM double 類型的向量。然後，它使用 Functiontype::get 方法建立一個函式類型，該類型接受「N」個 double 作為引數，返回一個 double 作為結果，並且不是可變引數（false 參數表示這一點）。請注意，LLVM 中的類型與常數一樣是唯一的，因此您不會「new」一個類型，而是「get」它。
上面的最後一行實際上建立了與 Prototype 對應的 IR 函式。這指示要使用的類型、連結和名稱，以及要插入的模組。「外部連結」表示該函式可以在當前模組之外定義和/或可以由模組之外的函式呼叫。傳入的 Name 是使用者指定的名稱：由於指定了「TheModule」，因此該名稱會註冊在「TheModule」的符號表中。
// Set names for all arguments.
unsigned Idx = 0;
for (auto &Arg : F->args())
Arg.setName(Args[Idx++]);
return F;
最後，我們根據 Prototype 中給出的名稱設定每個函式引數的名稱。這一步並非嚴格必要，但保持名稱一致可以提高 IR 的可讀性，並允許後續程式碼直接透過名稱引用引數，而不必在 Prototype AST 中查找它們。
至此，我們有了一個沒有主體的函式原型。這就是 LLVM IR 表示函式宣告的方式。對於 Kaleidoscope 中的 extern 語句，我們只需要做到這一步。但是，對於函式定義，我們需要產生程式碼並附加函式主體。
Function *FunctionAST::codegen() {
// First, check for an existing function from a previous 'extern' declaration.
Function *TheFunction = TheModule->getFunction(Proto->getName());
if (!TheFunction)
TheFunction = Proto->codegen();
if (!TheFunction)
return nullptr;
if (!TheFunction->empty())
return (Function*)LogErrorV("Function cannot be redefined.");
對於函式定義，我們首先在 TheModule 的符號表中搜尋此函式的現有版本，以防使用「extern」語句已經建立了一個版本。如果 Module::getFunction 返回 null，則表示不存在先前的版本，因此我們將從 Prototype 產生一個版本。無論哪種情況，我們都希望在開始之前斷言該函式是空的（即還沒有主體）。
// Create a new basic block to start insertion into.
BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
Builder->SetInsertPoint(BB);
// Record the function arguments in the NamedValues map.
NamedValues.clear();
for (auto &Arg : TheFunction->args())
NamedValues[std::string(Arg.getName())] = &Arg;
現在我們來到了設定 Builder 的地方。第一行程式碼建立了一個新的 基本區塊（名為「entry」），並將其插入到 TheFunction 中。第二行程式碼告訴 builder 新的指令應該插入到新基本區塊的末尾。LLVM 中的基本區塊是定義 控制流程圖 的函式的重要組成部分。由於我們没有任何控制流程，因此我們的函式目前只包含一個區塊。我們將在 第 5 章 中解決這個問題:)。
接下來，我們將函式引數添加到 NamedValues map 中（在先清除它之後），以便 VariableExprAST 節點可以存取它們。
if (Value *RetVal = Body->codegen()) {
// Finish off the function.
Builder->CreateRet(RetVal);
// Validate the generated code, checking for consistency.
verifyFunction(*TheFunction);
return TheFunction;
}
一旦設定好插入點並填入 NamedValues map，我們就會為函數的根表達式呼叫 codegen() 方法。如果沒有發生錯誤，這會將程式碼發出到 entry block 中以計算表達式，並返回計算出來的值。假設沒有錯誤，我們接著建立一個 LLVM ret 指令，它會完成函數。一旦函數建立完成，我們就會呼叫 LLVM 提供的 verifyFunction。這個函數會對生成的程式碼執行各種一致性檢查，以確定我們的編譯器是否一切正常。使用這個功能很重要：它可以捕捉到很多錯誤。一旦函數完成並通過驗證，我們就會將其返回。
// Error reading body, remove function.
TheFunction->eraseFromParent();
return nullptr;
}
這裡剩下的唯一一部分是錯誤情況的處理。為了簡單起見，我們僅透過使用 eraseFromParent 方法刪除我們生成的函數來處理這個問題。這允許使用者重新定義他們之前輸入錯誤的函數：如果我們沒有刪除它，它將會保留在符號表中，並帶有一個主體，阻止未來重新定義。
不過，這段程式碼確實有一個錯誤：如果 FunctionAST::codegen() 方法找到現有的 IR 函數，它不會根據定義本身的原型來驗證其簽章。這表示較早的「extern」聲明將優先於函數定義的簽章，這可能會導致程式碼生成失敗，例如，如果函數參數的名稱不同。有很多方法可以解決這個錯誤，請看看你能想出什麼辦法！這裡有一個測試案例
extern foo(a); # ok, defines foo.
def foo(b) b; # Error: Unknown variable name. (decl using 'a' takes precedence).
3.5. 驅動程式變更和總結¶
目前，生成到 LLVM 的程式碼並沒有真正給我們帶來太多好處，除了我們可以查看漂亮的 IR 呼叫之外。範例程式碼將對 codegen 的呼叫插入到「HandleDefinition」、「HandleExtern」等函數中，然後輸出 LLVM IR。這提供了一種查看簡單函數的 LLVM IR 的好方法。例如
ready> 4+5;
Read top-level expression:
define double @0() {
entry:
ret double 9.000000e+00
}
請注意解析器如何為我們將頂層表達式轉換為匿名函數。這在我們於下一章中加入JIT 支援時會很方便。另請注意，程式碼是被逐字轉錄的，除了 IRBuilder 執行的簡單常數摺疊之外，沒有執行任何最佳化。我們將在下一章中明確地加入最佳化。
ready> def foo(a b) a*a + 2*a*b + b*b;
Read function definition:
define double @foo(double %a, double %b) {
entry:
%multmp = fmul double %a, %a
%multmp1 = fmul double 2.000000e+00, %a
%multmp2 = fmul double %multmp1, %b
%addtmp = fadd double %multmp, %multmp2
%multmp3 = fmul double %b, %b
%addtmp4 = fadd double %addtmp, %multmp3
ret double %addtmp4
}
這顯示了一些簡單的算術運算。請注意與我們用來建立指令的 LLVM 建構器呼叫的驚人相似之處。
ready> def bar(a) foo(a, 4.0) + bar(31337);
Read function definition:
define double @bar(double %a) {
entry:
%calltmp = call double @foo(double %a, double 4.000000e+00)
%calltmp1 = call double @bar(double 3.133700e+04)
%addtmp = fadd double %calltmp, %calltmp1
ret double %addtmp
}
這顯示了一些函數呼叫。請注意，如果您呼叫此函數，則需要很長時間才能執行完成。未來我們將加入條件控制流程，以實際使遞迴變得有用:)。
ready> extern cos(x);
Read extern:
declare double @cos(double)
ready> cos(1.234);
Read top-level expression:
define double @1() {
entry:
%calltmp = call double @cos(double 1.234000e+00)
ret double %calltmp
}
這顯示了 libm「cos」函數的 extern 聲明及其呼叫。
ready> ^D
; ModuleID = 'my cool jit'
define double @0() {
entry:
%addtmp = fadd double 4.000000e+00, 5.000000e+00
ret double %addtmp
}
define double @foo(double %a, double %b) {
entry:
%multmp = fmul double %a, %a
%multmp1 = fmul double 2.000000e+00, %a
%multmp2 = fmul double %multmp1, %b
%addtmp = fadd double %multmp, %multmp2
%multmp3 = fmul double %b, %b
%addtmp4 = fadd double %addtmp, %multmp3
ret double %addtmp4
}
define double @bar(double %a) {
entry:
%calltmp = call double @foo(double %a, double 4.000000e+00)
%calltmp1 = call double @bar(double 3.133700e+04)
%addtmp = fadd double %calltmp, %calltmp1
ret double %addtmp
}
declare double @cos(double)
define double @1() {
entry:
%calltmp = call double @cos(double 1.234000e+00)
ret double %calltmp
}
當您退出目前的 demo（在 Linux 上透過 CTRL+D 或在 Windows 上透過 CTRL+Z 和 ENTER 發送 EOF）時，它會輸出生成的整個模組的 IR。在這裡，您可以看到所有函數相互參照的概況。
這總結了 Kaleidoscope 教學的第三章。接下來，我們將介紹如何為此添加 JIT 程式碼生成和最佳化器支援，以便我們可以真正開始執行程式碼！
3.6. 完整程式碼清單¶
以下是用 LLVM 代码生成器增强的完整运行示例代码清单。 由于这使用了 LLVM 库，我们需要将其链接进来。 为此，我们使用 llvm-config 工具将要使用的选项告知我们的 makefile/命令行
# Compile
clang++ -g -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core` -o toy
# Run
./toy
代码如下
#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <memory>
#include <string>
#include <vector>
using namespace llvm;
//===----------------------------------------------------------------------===//
// Lexer
//===----------------------------------------------------------------------===//
// The lexer returns tokens [0-255] if it is an unknown character, otherwise one
// of these for known things.
enum Token {
tok_eof = -1,
// commands
tok_def = -2,
tok_extern = -3,
// 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;
if (IdentifierStr == "def")
return tok_def;
if (IdentifierStr == "extern")
return tok_extern;
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;
}
if (LastChar == '#') {
// Comment until end of line.
do
LastChar = getchar();
while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
if (LastChar != EOF)
return gettok();
}
// Check for end of file. Don't eat the EOF.
if (LastChar == EOF)
return tok_eof;
// Otherwise, just return the character as its ascii value.
int ThisChar = LastChar;
LastChar = getchar();
return ThisChar;
}
//===----------------------------------------------------------------------===//
// Abstract Syntax Tree (aka Parse Tree)
//===----------------------------------------------------------------------===//
namespace {
/// ExprAST - Base class for all expression nodes.
class ExprAST {
public:
virtual ~ExprAST() = default;
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;
};
/// BinaryExprAST - Expression class for a binary operator.
class BinaryExprAST : public ExprAST {
char Op;
std::unique_ptr<ExprAST> LHS, RHS;
public:
BinaryExprAST(char Op, std::unique_ptr<ExprAST> LHS,
std::unique_ptr<ExprAST> RHS)
: Op(Op), LHS(std::move(LHS)), RHS(std::move(RHS)) {}
Value *codegen() override;
};
/// CallExprAST - Expression class for function calls.
class CallExprAST : public ExprAST {
std::string Callee;
std::vector<std::unique_ptr<ExprAST>> Args;
public:
CallExprAST(const std::string &Callee,
std::vector<std::unique_ptr<ExprAST>> Args)
: Callee(Callee), Args(std::move(Args)) {}
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; }
};
/// FunctionAST - This class represents a function definition itself.
class FunctionAST {
std::unique_ptr<PrototypeAST> Proto;
std::unique_ptr<ExprAST> Body;
public:
FunctionAST(std::unique_ptr<PrototypeAST> Proto,
std::unique_ptr<ExprAST> Body)
: Proto(std::move(Proto)), Body(std::move(Body)) {}
Function *codegen();
};
} // end anonymous namespace
//===----------------------------------------------------------------------===//
// Parser
//===----------------------------------------------------------------------===//
/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current
/// token the parser is looking at. getNextToken reads another token from the
/// lexer and updates CurTok with its results.
static int CurTok;
static int getNextToken() { return CurTok = gettok(); }
/// BinopPrecedence - This holds the precedence for each binary operator that is
/// defined.
static std::map<char, int> BinopPrecedence;
/// GetTokPrecedence - Get the precedence of the pending binary operator token.
static int GetTokPrecedence() {
if (!isascii(CurTok))
return -1;
// Make sure it's a declared binop.
int TokPrec = BinopPrecedence[CurTok];
if (TokPrec <= 0)
return -1;
return TokPrec;
}
/// LogError* - These are little helper functions for error handling.
std::unique_ptr<ExprAST> LogError(const char *Str) {
fprintf(stderr, "Error: %s\n", Str);
return nullptr;
}
std::unique_ptr<PrototypeAST> LogErrorP(const char *Str) {
LogError(Str);
return nullptr;
}
static std::unique_ptr<ExprAST> ParseExpression();
/// numberexpr ::= number
static std::unique_ptr<ExprAST> ParseNumberExpr() {
auto Result = std::make_unique<NumberExprAST>(NumVal);
getNextToken(); // consume the number
return std::move(Result);
}
/// parenexpr ::= '(' expression ')'
static std::unique_ptr<ExprAST> ParseParenExpr() {
getNextToken(); // eat (.
auto V = ParseExpression();
if (!V)
return nullptr;
if (CurTok != ')')
return LogError("expected ')'");
getNextToken(); // eat ).
return V;
}
/// identifierexpr
/// ::= identifier
/// ::= identifier '(' expression* ')'
static std::unique_ptr<ExprAST> ParseIdentifierExpr() {
std::string IdName = IdentifierStr;
getNextToken(); // eat identifier.
if (CurTok != '(') // Simple variable ref.
return std::make_unique<VariableExprAST>(IdName);
// Call.
getNextToken(); // eat (
std::vector<std::unique_ptr<ExprAST>> Args;
if (CurTok != ')') {
while (true) {
if (auto Arg = ParseExpression())
Args.push_back(std::move(Arg));
else
return nullptr;
if (CurTok == ')')
break;
if (CurTok != ',')
return LogError("Expected ')' or ',' in argument list");
getNextToken();
}
}
// Eat the ')'.
getNextToken();
return std::make_unique<CallExprAST>(IdName, std::move(Args));
}
/// primary
/// ::= identifierexpr
/// ::= numberexpr
/// ::= parenexpr
static std::unique_ptr<ExprAST> ParsePrimary() {
switch (CurTok) {
default:
return LogError("unknown token when expecting an expression");
case tok_identifier:
return ParseIdentifierExpr();
case tok_number:
return ParseNumberExpr();
case '(':
return ParseParenExpr();
}
}
/// binoprhs
/// ::= ('+' primary)*
static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec,
std::unique_ptr<ExprAST> LHS) {
// If this is a binop, find its precedence.
while (true) {
int TokPrec = GetTokPrecedence();
// If this is a binop that binds at least as tightly as the current binop,
// consume it, otherwise we are done.
if (TokPrec < ExprPrec)
return LHS;
// Okay, we know this is a binop.
int BinOp = CurTok;
getNextToken(); // eat binop
// Parse the primary expression after the binary operator.
auto RHS = ParsePrimary();
if (!RHS)
return nullptr;
// If BinOp binds less tightly with RHS than the operator after RHS, let
// the pending operator take RHS as its LHS.
int NextPrec = GetTokPrecedence();
if (TokPrec < NextPrec) {
RHS = ParseBinOpRHS(TokPrec + 1, std::move(RHS));
if (!RHS)
return nullptr;
}
// Merge LHS/RHS.
LHS =
std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
}
}
/// expression
/// ::= primary binoprhs
///
static std::unique_ptr<ExprAST> ParseExpression() {
auto LHS = ParsePrimary();
if (!LHS)
return nullptr;
return ParseBinOpRHS(0, std::move(LHS));
}
/// 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 std::make_unique<PrototypeAST>(FnName, std::move(ArgNames));
}
/// definition ::= 'def' prototype expression
static std::unique_ptr<FunctionAST> ParseDefinition() {
getNextToken(); // eat def.
auto Proto = ParsePrototype();
if (!Proto)
return nullptr;
if (auto E = ParseExpression())
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
return nullptr;
}
/// toplevelexpr ::= expression
static std::unique_ptr<FunctionAST> ParseTopLevelExpr() {
if (auto E = ParseExpression()) {
// Make an anonymous proto.
auto Proto = std::make_unique<PrototypeAST>("__anon_expr",
std::vector<std::string>());
return std::make_unique<FunctionAST>(std::move(Proto), std::move(E));
}
return nullptr;
}
/// external ::= 'extern' prototype
static std::unique_ptr<PrototypeAST> ParseExtern() {
getNextToken(); // eat extern.
return ParsePrototype();
}
//===----------------------------------------------------------------------===//
// Code Generation
//===----------------------------------------------------------------------===//
static std::unique_ptr<LLVMContext> TheContext;
static std::unique_ptr<Module> TheModule;
static std::unique_ptr<IRBuilder<>> Builder;
static std::map<std::string, Value *> NamedValues;
Value *LogErrorV(const char *Str) {
LogError(Str);
return nullptr;
}
Value *NumberExprAST::codegen() {
return ConstantFP::get(*TheContext, APFloat(Val));
}
Value *VariableExprAST::codegen() {
// Look this variable up in the function.
Value *V = NamedValues[Name];
if (!V)
return LogErrorV("Unknown variable name");
return V;
}
Value *BinaryExprAST::codegen() {
Value *L = LHS->codegen();
Value *R = RHS->codegen();
if (!L || !R)
return nullptr;
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:
return LogErrorV("invalid binary operator");
}
}
Value *CallExprAST::codegen() {
// Look up the name in the global module table.
Function *CalleeF = TheModule->getFunction(Callee);
if (!CalleeF)
return LogErrorV("Unknown function referenced");
// If argument mismatch error.
if (CalleeF->arg_size() != Args.size())
return LogErrorV("Incorrect # arguments passed");
std::vector<Value *> ArgsV;
for (unsigned i = 0, e = Args.size(); i != e; ++i) {
ArgsV.push_back(Args[i]->codegen());
if (!ArgsV.back())
return nullptr;
}
return Builder->CreateCall(CalleeF, ArgsV, "calltmp");
}
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;
}
Function *FunctionAST::codegen() {
// First, check for an existing function from a previous 'extern' declaration.
Function *TheFunction = TheModule->getFunction(Proto->getName());
if (!TheFunction)
TheFunction = Proto->codegen();
if (!TheFunction)
return nullptr;
// Create a new basic block to start insertion into.
BasicBlock *BB = BasicBlock::Create(*TheContext, "entry", TheFunction);
Builder->SetInsertPoint(BB);
// Record the function arguments in the NamedValues map.
NamedValues.clear();
for (auto &Arg : TheFunction->args())
NamedValues[std::string(Arg.getName())] = &Arg;
if (Value *RetVal = Body->codegen()) {
// Finish off the function.
Builder->CreateRet(RetVal);
// Validate the generated code, checking for consistency.
verifyFunction(*TheFunction);
return TheFunction;
}
// Error reading body, remove function.
TheFunction->eraseFromParent();
return nullptr;
}
//===----------------------------------------------------------------------===//
// Top-Level parsing and JIT Driver
//===----------------------------------------------------------------------===//
static void InitializeModule() {
// Open a new context and module.
TheContext = std::make_unique<LLVMContext>();
TheModule = std::make_unique<Module>("my cool jit", *TheContext);
// Create a new builder for the module.
Builder = std::make_unique<IRBuilder<>>(*TheContext);
}
static void HandleDefinition() {
if (auto FnAST = ParseDefinition()) {
if (auto *FnIR = FnAST->codegen()) {
fprintf(stderr, "Read function definition:");
FnIR->print(errs());
fprintf(stderr, "\n");
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleExtern() {
if (auto ProtoAST = ParseExtern()) {
if (auto *FnIR = ProtoAST->codegen()) {
fprintf(stderr, "Read extern: ");
FnIR->print(errs());
fprintf(stderr, "\n");
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
static void HandleTopLevelExpression() {
// Evaluate a top-level expression into an anonymous function.
if (auto FnAST = ParseTopLevelExpr()) {
if (auto *FnIR = FnAST->codegen()) {
fprintf(stderr, "Read top-level expression:");
FnIR->print(errs());
fprintf(stderr, "\n");
// Remove the anonymous expression.
FnIR->eraseFromParent();
}
} else {
// Skip token for error recovery.
getNextToken();
}
}
/// top ::= definition | external | expression | ';'
static void MainLoop() {
while (true) {
fprintf(stderr, "ready> ");
switch (CurTok) {
case tok_eof:
return;
case ';': // ignore top-level semicolons.
getNextToken();
break;
case tok_def:
HandleDefinition();
break;
case tok_extern:
HandleExtern();
break;
default:
HandleTopLevelExpression();
break;
}
}
}
//===----------------------------------------------------------------------===//
// Main driver code.
//===----------------------------------------------------------------------===//
int main() {
// Install standard binary operators.
// 1 is lowest precedence.
BinopPrecedence['<'] = 10;
BinopPrecedence['+'] = 20;
BinopPrecedence['-'] = 20;
BinopPrecedence['*'] = 40; // highest.
// Prime the first token.
fprintf(stderr, "ready> ");
getNextToken();
// Make the module, which holds all the code.
InitializeModule();
// Run the main "interpreter loop" now.
MainLoop();
// Print out all of the generated code.
TheModule->print(errs(), nullptr);
return 0;
}