3. 萬花筒：程式碼生成至 LLVM IR¶
3.1. 第 3 章 簡介¶
歡迎來到「使用 LLVM 實作語言」教學的第 3 章。本章將向您展示如何將第 2 章中建構的 抽象語法樹轉換為 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;
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 表示形式是什麼。（換句話說，它是程式碼的符號表）。在這種形式的萬花筒中，唯一可以引用的事物是函數參數。因此，在為函數主體生成程式碼時，函數參數將在此映射表中。
有了這些基礎知識，我們可以開始討論如何為每個表達式生成程式碼。請注意，這假定 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 引用變數也很簡單。在簡化版本的萬花筒中，我們假設變數已在某處發出，並且其值可用。實際上，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");
}
}
二元運算子開始變得更有趣。這裡的基本概念是，我們遞迴地為表達式的左側生成程式碼，然後為右側生成程式碼，然後我們計算二元表達式的結果。在此程式碼中，我們在運算碼上進行簡單的切換以建立正確的 LLVM 指令。
在上面的範例中，LLVM builder 類別開始展現其價值。IRBuilder 知道在哪裡插入新建立的指令，您只需指定要建立的指令（例如，使用 CreateFAdd）、要使用的運算元（此處為 L 和 R），並可選擇為生成的指令提供名稱。
關於 LLVM 的一個好處是，名稱只是一個提示。例如，如果上面的程式碼發出多個 “addtmp” 變數，LLVM 會自動為每個變數提供一個遞增的唯一數字後綴。指令的本機值名稱是完全可選的，但它使讀取 IR 傾印更容易。
LLVM 指令受到嚴格規則的約束：例如，add 指令的 Left 和 Right 運算元必須具有相同的型別，並且 add 的結果型別必須與運算元型別相符。由於萬花筒中的所有值都是雙精度浮點數，因此這使得加法、減法和乘法的程式碼非常簡單。
另一方面，LLVM 規定 fcmp 指令始終回傳一個 ‘i1’ 值（一個位元整數）。問題在於萬花筒希望該值為 0.0 或 1.0 值。為了獲得這些語意，我們將 fcmp 指令與 uitofp 指令結合使用。此指令透過將輸入視為無符號值，將其輸入整數轉換為浮點值。相比之下，如果我們使用 sitofp 指令，則萬花筒 ‘<’ 運算子將根據輸入值回傳 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 Module 的符號表中執行函數名稱查找。回想一下，LLVM Module 是保存我們 JIT 函數的容器。透過為每個函數提供與使用者指定的名稱相同的名稱，我們可以使用 LLVM 符號表為我們解析函數名稱。
一旦我們有了要呼叫的函數，我們就會遞迴地為要傳遞的每個引數生成程式碼，並建立一個 LLVM call 指令。請注意，LLVM 預設使用原生 C 呼叫慣例，允許這些呼叫也呼叫到諸如 “sin” 和 “cos” 之類的標準函式庫函數，而無需額外的努力。
這總結了我們到目前為止在萬花筒中處理的四個基本表達式。隨時進入並新增更多內容。例如，透過瀏覽 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 Function 是有意義的。
呼叫 FunctionType::get 會建立應用於給定 Prototype 的 FunctionType。由於萬花筒中的所有函數引數都是 double 型別，因此第一行會建立一個包含 “N” 個 LLVM double 型別的向量。然後，它使用 Functiontype::get 方法來建立一個函數型別，該型別將 “N” 個 double 作為引數，回傳一個 double 作為結果，並且不是 vararg（false 參數表示這一點）。請注意，LLVM 中的型別與常數一樣是唯一化的，因此您不會 “new” 一個型別，而是 “get” 它。
上面的最後一行實際上建立了與 Prototype 對應的 IR Function。這指示要使用的型別、連結和名稱，以及要插入的模組。“外部連結”表示該函數可以在目前模組之外定義，和/或可以被模組之外的函數呼叫。傳入的 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 表示函數宣告的方式。對於萬花筒中的 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 映射表中（在首先清空它之後），以便它們可以被 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 映射表，我們就為函數的根表達式呼叫 codegen() 方法。如果沒有發生錯誤，這會發出程式碼以將表達式計算到 entry 區塊中，並回傳計算出的值。假設沒有錯誤，然後我們建立一個 LLVM ret 指令，完成函數。建立函數後，我們呼叫 LLVM 提供的 verifyFunction。此函數對生成的程式碼執行各種一致性檢查，以確定我們的編譯器是否一切正常。使用它非常重要：它可以捕獲很多錯誤。函數完成並驗證後，我們回傳它。
// Error reading body, remove function.
TheFunction->eraseFromParent();
return nullptr;
}
這裡剩下的唯一部分是處理錯誤情況。為了簡單起見，我們僅透過使用 eraseFromParent 方法刪除我們產生的函數來處理此問題。這允許使用者重新定義之前錯誤輸入的函數：如果我們不刪除它，它將存在於符號表中，帶有主體，阻止未來的重新定義。
但是，此程式碼確實存在一個錯誤：如果 FunctionAST::codegen() 方法找到現有的 IR Function，它不會根據定義自己的原型驗證其簽名。這表示先前的 ‘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 builder 呼叫的驚人相似性。
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
}
當您退出目前的示範（透過在 Linux 上透過 CTRL+D 或在 Windows 上透過 CTRL+Z 和 ENTER 發送 EOF）時，它會傾印出為整個模組生成的 IR。在這裡，您可以看到引用彼此的所有函數的全貌。
這總結了萬花筒教學的第三章。接下來，我們將描述如何新增 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;
}