參考

Kaleidoscope: Code generation to LLVM IR

1. 前言

在之前的文章中，已經(jīng)完成了 AST 的生成，本文將講述如何把生成的 AST 轉(zhuǎn)換成 LLVM IR（中間表達(dá)）。

2. 設(shè)置

首先，我們每一個(gè)AST 類(lèi)中定義一個(gè)代碼生成的虛函數(shù)

/// 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) {}
  virtual Value *codegen();
};
...

函數(shù)codegen()表示為節(jié)點(diǎn)極其所有依賴(lài)發(fā)出（emit）IR，并且返回的都是 LLVM Value 對(duì)象。Value 對(duì)象最獨(dú)特的是他的值是在相關(guān)指令執(zhí)行的時(shí)候計(jì)算的，并且在指令重新執(zhí)行前，值都不會(huì)更新。當(dāng)然除了用虛函數(shù)的方式，還可以用 visitor pattern 等其他模式實(shí)現(xiàn)。

首先，和Parser 一樣，定義一個(gè) LogError 的函數(shù)，同時(shí)定義需要試用到的 LLVM 對(duì)象。

static LLVMContext TheContext;
static 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;
}

涉及到的主要數(shù)據(jù)結(jié)構(gòu)如下：

• LLVMContext TheContext：一個(gè)非透明的對(duì)象，包含了很多核心的 LLVM 數(shù)據(jù)結(jié)構(gòu)，比如類(lèi)型和常量值表。我們無(wú)需了解它的細(xì)節(jié)，只需要一個(gè)該對(duì)象的單例，傳入到需要它的 api 中。
• IRBuilder<> Builder(TheContext)：一個(gè)helper 對(duì)象，以便于生成 LLVM 指令。IRBuilder 實(shí)例跟蹤了指令插入的位置，提供了生成新指令的方法。
• std::unique_ptr<Module> TheModule： 一個(gè)包含函數(shù)和全局變量的 LLVM 結(jié)構(gòu)體。在很多方面，他是LLVM IR 用來(lái)包含代碼的頂層結(jié)構(gòu)。他擁有我們生成的所有 IR的內(nèi)存，這也是 codegen()方法為什么返回原始的 Value*而不是 unique_ptr<Value>。Module 是存放 JIT 函數(shù)的容器。
• std::map<std::string, Value *> NamedValues：跟蹤當(dāng)前范圍定義了哪些值，以及他們的 LLVM 表達(dá)式什么（換句話(huà)說(shuō)，他是代碼的符號(hào)表）。在Kaleidoscope中，唯一能引用的就是函數(shù)參數(shù)。因此，函數(shù)參數(shù)在生成函數(shù)體代碼的時(shí)候，會(huì)存放在這個(gè) map 中。

3. 表達(dá)式的代碼生成

四個(gè)表達(dá)節(jié)點(diǎn)的實(shí)現(xiàn)是很簡(jiǎn)單的。

3.1. 數(shù)字表達(dá)式

Value *NumberExprAST::codegen() {
  return ConstantFP::get(TheContext, APFloat(Val));
}

在 LLVM IR 中，數(shù)字常量用 ConstantFP 類(lèi)（內(nèi)部用APFloat來(lái)存放數(shù)值，可以表達(dá)浮點(diǎn)數(shù)據(jù)的任意精度）來(lái)表示。 LLVM IR 中，每個(gè)常量值都是唯一的、共享的。因此API 使用foo::get(…)，而不是new foo(..)或foo::Create(..)。

3.2. 變量表達(dá)式

Value *VariableExprAST::codegen() {
  // Look this variable up in the function.
  Value *V = NamedValues[Name];
  if (!V)
    LogErrorV("Unknown variable name");
  return V;
}

在普通版本的Kaleidoscope中，我們假設(shè)變量已經(jīng)產(chǎn)出（emit）且他的值是可獲得的。實(shí)際中，NamedValues 映射表中唯一可用的值是函數(shù)參數(shù)。上述代碼簡(jiǎn)單的檢查指定的變量名字是否在映射表中，如果不存在，那么引用的是未知變量，如果存在，就返回對(duì)應(yīng)的值。后續(xù)的章節(jié)，會(huì)在符號(hào)表中支持loop induction variables 和 local variables。

3.3. 二元表達(dá)式

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");
  }
}

二元表達(dá)式的基本思想就是遞歸地產(chǎn)出右側(cè)代碼，然后是左側(cè)代碼，然后計(jì)算二元表達(dá)式的結(jié)果。

：

• 在上述的例子中，可以看到 LLVM Builder 類(lèi)知道在哪里插入新創(chuàng)建的指令，你需要做的就是指定要?jiǎng)?chuàng)建的指令（比如 CreateFAdd）、要使用的操作數(shù)，并且可以為生成的指令指定一個(gè)名字（可選的）。
  這個(gè)名字僅僅是一個(gè)示意，比如說(shuō)，如果有多個(gè)指令使用名字addtmp，LLVM 會(huì)自動(dòng)給每一個(gè)名字增加遞增、唯一的后綴。

• LLVM 指令是嚴(yán)格限制的，比如說(shuō)，add 指令的左右操作數(shù)必須是相同的類(lèi)型，add 的結(jié)果類(lèi)型必須和操作數(shù)的類(lèi)型一樣。在Kaleidoscope中，因?yàn)樗械闹刀际?double 的，所以代碼實(shí)現(xiàn)就很簡(jiǎn)單。

• LLVM定義 fcmp 指定總是范圍一個(gè) i1 （一個(gè) bit 位的整型）。問(wèn)題是根據(jù)Kaleidoscope的語(yǔ)義，希望值是0.0或者1.0。為了達(dá)到這個(gè)語(yǔ)義，使用了 uitofp 指令和 fcmp 指令的結(jié)合。uitofp 指令將輸入的整型轉(zhuǎn)為浮點(diǎn)型，轉(zhuǎn)換時(shí)將輸入視作無(wú)符號(hào)值。相反，如果使用sitofp指令，Kaleidoscope中的<就會(huì)根據(jù)輸入返回0.0或者是-1.0。

3.4. 函數(shù)調(diào)用表達(dá)式

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");
}

函數(shù)調(diào)用的代碼生成很直接了當(dāng)。首先，在 LLVM Module 中去查找函數(shù)名的符號(hào)表，之前提到過(guò)，LLVM Module 是存放 JIT 函數(shù)的容器。通過(guò)為每個(gè)函數(shù)指定與用戶(hù)指定的名稱(chēng)相同的名稱(chēng)，我們可以使用LLVM符號(hào)表為我們解析函數(shù)名稱(chēng)。

一旦我們有了要調(diào)用的函數(shù)，我們遞歸的生成傳入?yún)?shù)的代碼，并創(chuàng)建 LLVM call instruction。注意，LLVM 默認(rèn)使用的是本地 C 調(diào)用約定，從而允許這些調(diào)用標(biāo)準(zhǔn)庫(kù)函數(shù)（如 sin、cos）而無(wú)需其他代價(jià)。

如有需要，在 LLVM language reference 可以查閱其他的LLVM指令。

3.5. 函數(shù)代碼生成

函數(shù)體和 prototype 需要處理更多細(xì)節(jié)，所以比之前的表達(dá)式代碼生成更麻煩。

3.5.1. prototype

prototype 用于函數(shù)體和函數(shù)的外部聲明。首先看最開(kāi)始的幾行代碼如下：

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());
......
}

首先注意這個(gè)函數(shù)的返回結(jié)果是Function*而不是Value*。這是因?yàn)閜rototype 實(shí)際上是在討論函數(shù)的外部接口，而不是一個(gè)表達(dá)式計(jì)算的值。

FunctionType::get的調(diào)用創(chuàng)建了prototype 需要用到的FunctionType。Kaleidoscope 的數(shù)據(jù)都是 double 類(lèi)型的，第一行創(chuàng)建了一個(gè)長(zhǎng)度為 N（等于函數(shù)參數(shù)個(gè)數(shù)） 的 LLVM double類(lèi)型 vector。然后使用Functiontype::get方法創(chuàng)建一個(gè) FunctionType 對(duì)象，這個(gè)函數(shù)對(duì)象使用 N 個(gè)對(duì)象作為傳入?yún)?shù)，返回結(jié)果是一個(gè) double 而不是vararg（由第三個(gè)參數(shù)false指明）。注意，LLVM 的 Types和 Constants 一樣都是唯一的，所以不會(huì)去 new 一個(gè) type，而是 get。

上述代碼的最后一行，創(chuàng)建了 prototype 對(duì)應(yīng)的 IR Function。它指明了類(lèi)型、鏈接、名字以及要插入到哪個(gè) module。external linkage意味著這個(gè)函數(shù)可以在當(dāng)前 module 之外被定義或者被當(dāng)前 module 之外的函數(shù)調(diào)用。Name 是用戶(hù)定義的名字，將會(huì)注冊(cè)到TheModule的符號(hào)表中。

Function *PrototypeAST::codegen() {
......
// Set names for all arguments.
unsigned Idx = 0;
for (auto &Arg : F->args())
  Arg.setName(Args[Idx++]);

return F;
}

最后，根據(jù) prototype 里面給出的名字，設(shè)置每一個(gè)參數(shù)的名字。這個(gè)步驟不是嚴(yán)格必要的，但是保持名字一直可以讓 IR 更易讀，也可以讓隨后的代碼可以通過(guò)名字直接引用到這些參數(shù)，而不用去 prototype 的 ast 中查找。

此時(shí)我們就獲得了沒(méi)有函數(shù)體的 prototype 。這就是 LLVM IR如何表示函數(shù)聲明的過(guò)程。但是對(duì)于函數(shù)的定義，我們還需要函數(shù)體。

3.5.2. 函數(shù)體

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.");
......

對(duì)于函數(shù)定義，首先在Module中去查找這個(gè)函數(shù)，以防有人已經(jīng)用extern創(chuàng)建過(guò)了。如果不存在，則調(diào)用 ProtoType 的 codegen 生成。在任一情況下，我們想在開(kāi)始前斷言函數(shù)是空的（沒(méi)有函數(shù)體）。

// 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[Arg.getName()] = &Arg;

上述代碼講的是Builder如何設(shè)置。第一行創(chuàng)建了一個(gè)空的 basic block（被稱(chēng)作entry），插入到Function。第二行高速 Builder新指令應(yīng)該插入到新創(chuàng)建的basic block末尾。在 LLVM 中，basic block 是函數(shù)重要的一個(gè)部分，定義了控制流程圖(Control Flow Graph)。因?yàn)槲覀儧](méi)有任何控制流程圖，我們的函數(shù)只包含了一個(gè) block。在第五章我們將修正這個(gè)情況。

然后我們把函數(shù)參數(shù)添加到 NamedValues 映射表中，使其對(duì)VariableExprAST 節(jié)點(diǎn)可見(jiàn)。

if (Value *RetVal = Body->codegen()) {
  // Finish off the function.
  Builder.CreateRet(RetVal);

  // Validate the generated code, checking for consistency.
  verifyFunction(*TheFunction);

  return TheFunction;
}

一旦插入點(diǎn)設(shè)置完成且 NamedValues 映射也構(gòu)建完成，我就調(diào)用根表達(dá)式的 codegen() 方法。如果沒(méi)有錯(cuò)誤，將產(chǎn)出用于表達(dá)式計(jì)算的代碼到 entry block 中，并且返回計(jì)算的結(jié)果。假設(shè)沒(méi)有錯(cuò)誤，然后創(chuàng)建一個(gè)ret instruction，用于完成函數(shù)。函數(shù)創(chuàng)建完畢之后，我們調(diào)用LLVM 提供的verifyFunction函數(shù)。這個(gè)函數(shù)會(huì)對(duì)生成的代碼做各種一致性的檢查，確定我們的編譯器是否每件事都做得正確。檢查是很有必要的，檢查完成后就直接返回函數(shù)。

  // Error reading body, remove function.
  TheFunction->eraseFromParent();
  return nullptr;
}

剩下的內(nèi)容是錯(cuò)誤處理得情況了。為了簡(jiǎn)化，我們只是通過(guò)eraseFromParent方法將函數(shù)刪除。

目前的實(shí)現(xiàn)有個(gè) bug，如果FunctionAST::codegen()發(fā)現(xiàn)一個(gè)存在的 IR Function，就不會(huì)根據(jù)定義的原型驗(yàn)證簽名。也就是說(shuō)使用 extern 的函數(shù)提前聲明比函數(shù)定義的簽名有更高的優(yōu)先級(jí)，當(dāng)聲明和定義的變量不一樣的時(shí)候就會(huì)出錯(cuò)。例如：

extern foo(a);     # ok, defines foo.
def foo(b) b;      # Error: Unknown variable name. (decl using 'a' takes precedence).

4. 結(jié)語(yǔ)

目前，LLVM codegen并沒(méi)有給我們帶來(lái)很多好處，除了讓我們看到漂亮的 IR 調(diào)用。

樣例代碼把codegen的調(diào)用插入到HandleDefinition、 HandleExtern 等函數(shù)，然后 dump 出對(duì)應(yīng)的 LLVM IR。比如：

ready> 4+5;
Read top-level expression:
define double @0() {
entry:
  ret double 9.000000e+00
}

上面的代碼可以看到LLVM 隱式地對(duì) Top-Level 的表達(dá)式做了簡(jiǎn)單的優(yōu)化，下一章將會(huì)介紹如何顯示的進(jìn)行優(yōu)化。

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
}

上述結(jié)果是一些簡(jiǎn)單的算術(shù)表達(dá)式，注意這和用于創(chuàng)建指令的 LLVM 構(gòu)建器非常相似。

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
}

上述結(jié)果展示了函數(shù)調(diào)用。注意這個(gè)函數(shù)將花較長(zhǎng)的時(shí)間執(zhí)行。未來(lái)會(huì)增加條件控制流，讓遞歸更真正有用。

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
}

以上是 cos的聲明和調(diào)用

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
}

退出命令行的時(shí)候，會(huì)把Module 的所有 IR dump 出來(lái)。

完整代碼清單參見(jiàn)Full Code Listing