チュートリアル「LLVMを使用したプログラミング言語の作成」の第3章にようこそ。 この章では、 第2章で作成したAST（Abstract Syntax Tree）をLLVM IRに変換する方法について説明します。 彼女はLLVMのいくつかの側面について説明し、またそれがいかに簡単かを示します。 LLVM IRコードを直接作成するよりも、字句解析と構文解析に多くの作業が必要であることがわかります。



注 ：この章のコードにはLLVM 2.2以降が必要です。 LLVM 2.1バージョンを含むと、このコードは機能しません。 LLVMリリースに一致するこのチュートリアルのバージョンを使用する必要があることにも注意してください。公式リリースに付属のドキュメントを使用するか、llvm.orgのリリースページにアクセスしてください 。

コード生成のために調整されています

LLVM IRを生成するには、いくつかの簡単なセットアップが必要です。 まず、ASTクラスごとに仮想コード生成メソッド（ Codegen



）を定義します。

 /// ExprAST -      . class ExprAST { public: virtual ~ExprAST() {}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

  virtual Value *Codegen() = 0;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 }; /// NumberExprAST -       "1.0". class NumberExprAST : public ExprAST { double Val; public: NumberExprAST(double val) : Val(val) {}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

  virtual Value *Codegen();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 }; ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Codegen()



メソッドは、指定されたASTノードのIRとそのすべての依存ノードを返し、それらすべてがLLVM Value



オブジェクトを返します。 "Value"



は、LLVMの「 静的単一割り当て （ SSA ） レジスタ 」または「SSA値」を表すために使用されるクラスです。 SSAで最も重要な点は、値が関連する命令の実行として計算され、命令が再実行されるまで（およびその場合）新しい値を受け取ることができないことです。 つまり、SSA値を「変更」する方法はありません。 詳細については、 静的単一割り当てについてお読みください-これらの概念は、注意を払うとすぐに非常に自然に見えます。



ExprAST



クラスの階層に仮想メソッドを追加する代わりに、 Visitorデザインパターンまたは他のメソッドを使用するのが理にかなっていることに注意してください。 繰り返しますが、このチュートリアルでは、優れたソフトウェア開発方法については説明しません。目標はシンプルであり、仮想メソッドを追加することは簡単です。



また、パーサーに使用されたものと同様のエラーを処理する方法も必要です。 コード生成中に見つかったエラーメッセージにこのメソッドを使用します（たとえば、宣言されていないパラメーターを使用します）。

 Value *ErrorV(const char *Str) { Error(Str); return 0; } static Module *TheModule; static IRBuilder<> Builder(getGlobalContext()); static std::map<std::string, Value*> NamedValues;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらの静的変数は、コード生成中に使用されます。 TheModule



は、すべての関数とグローバル変数をコードの一部に含むLLVMコンストラクトです。 ほとんどの場合、これらは、LLVM IRが含まれるコードに使用する最上位の構造です。



Builder



オブジェクトは、LLVM命令を簡単に生成できるようにするヘルパーオブジェクトです。 クラステンプレートインスタンス IRBuilder



IRBuilder



は、命令を挿入するための現在の場所を追跡し、新しい命令を作成するためのメソッドを含んでいます。



NamedValues



マップNamedValues



、現在のスコープで定義されている値とそのLLVM表現NamedValues



追跡します。 （つまり、これはコードの文字テーブルです）。 Kaleidoscopeの現在のフォームでは、参照できるのは関数パラメーターのみです。 したがって、このマップでは、関数本体のコードを生成するときに、この関数のパラメーターが配置されます。



これらすべてを知っていれば、式のコードの生成について話すことができます。 「何でも」のコードを生成するために、 Builder



がすでに作成されていることを前提としています。 とりあえず、これは既に行われていると仮定し、それを使用してコードを保存します。

式コード生成

式ノードのLLVMコードの生成は非常に簡単です。4つの式ノードタイプすべてについて、コメント行が45行未満です。 始めるために、数値リテラルを見てみましょう。

 Value *NumberExprAST::Codegen() { return ConstantFP::get(getGlobalContext(), APFloat(Val)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

LLVM IRでは、数値定数はConstantFP



クラスで表されます。このクラスには、 APFloat



の形式の数値が含まれます（ APFloat



は、実定数を任意の精度の数値にキャストする機能があります）。 このコードは、 ConstantFP



作成して返します。 LLVM IRでは、すべての定数は一意（一意）および共有（共有）であることに注意してください。 このため、APIは"new foo(..)"



や"foo::Create(..)"



ではなく、イディオム"foo::get(...)"



使用し"foo::Create(..)"



。

 Value *VariableExprAST::Codegen() { //      . Value *V = NamedValues[Name]; return V ? V : ErrorV("Unknown variable name"); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

LLVMを使用する場合、変数参照も非常に簡単です。 Kaleidoscopeの単純なバージョンでは、変数が既にどこかに設定されており、その値が利用可能であると想定しています。 実際には、NamedValuesマップの値は関数の引数のみになります。 このコードは、指定された名前がマップ上で定義されていることを確認し（定義されていない場合、これは不明な変数へのリンクです）、その値を返します。 後続の章では、ローカル変数とループカウンター変数のサポートを追加します。

 Value *BinaryExprAST::Codegen() { Value *L = LHS->Codegen(); Value *R = RHS->Codegen(); if (L == 0 || R == 0) return 0; 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"); //   0  1   0.0  1.0 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp"); default: return ErrorV("invalid binary operator"); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

二項演算子で、楽しみが始まります。 ここでの主な考え方は、式の左側のコードを再帰的に生成し、次に右側のコードを生成して、バイナリ式の結果を計算することです。 このコードでは、LLVMステートメントを作成するための2項演算子に関する簡単なスイッチを作成しました。



上記の例では、LLVM Builder



クラスが最終的にその値を示しています。 IRBuilder



は、新しく作成された命令を挿入する場所を認識しており、作成する命令（ "CreateFAdd"



）、使用するオペランド（この場合はLとR）、および必要に応じて使用する命令を指定するだけです。生成された命令の名前。



LLVMのもう1つの優れた機能は、名前の割り当てです。 たとえば、上記で"addtmp"



変数を数回使用すると、LLVMは毎回自動的に一意の数値サフィックスを割り当てます。 指示のローカル値名はオプションですが、IRダンプを読みやすくします。



LLVM命令は厳密なルールによって制限されます。たとえば、 加算命令の左右のオペランドは同じ型である必要があり、加算結果の型はオペランドの型に対応します。 Kaleidoscopeのすべての値は実数であるため、加算、減算、乗算の非常に単純なコードを取得します。



一方、LLVMの仕様では、 fcmp



命令は常に値「i1」（単一ビット整数）を返します。 問題は、Kaleidoscopeでは0.0または1.0の値が必要なことです。 これを行うには、 fcmp



をfcmp



と組み合わせます。 この命令は、符号なし整数を実浮動小数点に変換します。 対照的に、 sitofp



を使用した場合、「<」演算子は入力値に応じて0.0と-1.0を返します。

 Value *CallExprAST::Codegen() { //      . Function *CalleeF = TheModule->getFunction(Callee); if (CalleeF == 0) return ErrorV("Unknown function referenced"); //    . if (CalleeF->arg_size() != Args.size()) return ErrorV("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() == 0) return 0; } return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

LLVMコードを生成して関数を呼び出すのは非常に簡単です。 上記のコードは、最初にLLVMモジュールのシンボルテーブルで関数名を検索します。 LLVMモジュールは、JITコンパイルに使用できるすべての機能を含むコンテナーであることを思い出してください。 各関数に名前を付けると、LLVMシンボルテーブルを使用して関数名を検索できます。



呼び出す関数を受け取った後、渡される各引数のコードを再帰的に生成し、LLVM呼び出し命令を作成します。 LLVMはデフォルトでCのような関数呼び出し規則を使用することに注意してください。これにより、 "sin"



や"cos"



などの標準ライブラリ関数にこれらの呼び出しを追加の労力なしで使用できます。



これで、4つの主要なタイプのKaleidoscope言語式ノードの処理が完了しました。 さらに進んで、さらにいくつかのビューを追加できます。 たとえば、LLVM言語を参照すると、既存の開発への接続が非常に簡単な他の興味深い指示がいくつか見つかります。

機能コード生成

プロトタイプと関数のコード生成では、コード式を生成するよりもコードを美しくしない多くの詳細を処理する必要がありますが、いくつかの重要なポイントを説明できます。 まず、プロトタイプのコード生成について説明しましょう。これは、関数の本体と外部関数の宣言の両方に使用されます。 コードは次で始まります：

 Function *PrototypeAST::Codegen() { //   : double(double,double)  ... std::vector<const Type*> Doubles(Args.size(), Type::getDoubleTy(getGlobalContext())); FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false); Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

数行のこのコードは実際に実力を示しています。 まず、この関数は"Value*"



ではなく"Function*"



返すことに注意してください。 「プロトタイプ」は実際には（計算式ではなく）関数の外部インターフェイスを指すため、関数に対して生成されたコードに対応するLLVM関数を返すことは理にかなっています。



"FunctionType::get"



を呼び出すと、このプロトタイプに使用されるFunctionTypeが作成されます。 Kaleidoscopeのすべての関数引数は実数であるため、最初の行は「N」個の実数からLLVMベクトルを作成します。 次に、 FunctionType::get



メソッドを使用して、「N」個の有効な引数を取り、結果として1つの有効な引数を返す関数型を作成します。 LLVMの型は定数として一意であるため、 "new"



ではなく"get"



が必要であることに注意してください（元の言葉では、「...だから"



作成"



ではなく、 "



get "



」）。 。



最後の行は、実際にプロトタイプに一致する関数を作成します。 使用するタイプ、関係、名前、および挿入するモジュールを示します。 「 外部リンケージ 」は、現在のモジュールの外部で関数を定義できること、および/またはモジュールの外部で呼び出すことができることを意味します。 "Name"



はユーザーが指定する名前を定義し、 "TheModule"



はこの名前が"TheModule"



文字テーブルに登録されていることを示します。

  //   (F)     ,     'Name'. //     ,      . if (F->getName() != Name) { //   ,      . F->eraseFromParent(); F = TheModule->getFunction(Name);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

名前の競合に関しては、モジュールのシンボルテーブルはシンボルテーブルの機能と同じように機能します。以前にシンボルテーブルに追加された名前で新しい関数が作成された場合、モジュールに追加されると暗黙的に名前が変更されます。 上記のコードはこの事実を使用して、同じ関数が以前に宣言されたかどうかを判断します。



Kaleidoscopeでは、関数の再定義は2つの場合があります。 まず、プロトタイプが一致する限り、関数のextern



定義を複数回使用する場合（すべての引数が同じ型であるため、引数の数が一致するかどうかを確認するだけです）。 第二に、関数のextern



定義を使用したい場合は、 extern



定義を使用します。 これは、相互に再帰的な関数を定義するときに必要です。



これを実装するために、上記のコードは最初に関数名の競合があるかどうかを確認します。 存在する場合は、作成した関数を削除し（ "getFunction"



を呼び出して）、次に"getFunction"



を呼び出して、指定した名前の既存の関数を取得します。 LLVMの多くのAPIには"erase"



形式と"remove"



形式の両方があることに注意してください。 "remove"



メソッドは、親オブジェクト（たとえば、モジュールの関数）からオブジェクトを切り離し（リンク解除し）、それを返します。 "erase"



メソッドは、オブジェクトをデタッチ（リンク解除）してから削除します。

  //   (F)   , . if (!F->empty()) { ErrorF("redefinition of function"); return 0; } //   (F)    , . if (F->arg_size() != Args.size()) { ErrorF("redefinition of function with different # args"); return 0; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記の推論を確認するために、まず「既存の」機能が「空」であることを確認します。 この場合、voidはベースブロック、つまり関数の本体が含まれていないことを意味します。 関数にボディがある場合、これは繰り返し宣言であるため、この場合、コードを拒否します。 前の関数が"extern"



関数である場合、引数の数を現在の定義の引数の数と単純に比較します。 それらが一致しない場合、エラーが表示されます。

  //     . unsigned Idx = 0; for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); ++AI, ++Idx) { AI->setName(Args[Idx]); //      . NamedValues[Args[Idx]] = AI; } return F; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数プロトタイプを処理するためのコードの最後の部分は、関数への引数のループですNamedValues



オブジェクト名、対応する引数を指定し、 NamedValues



マップに引数を登録して、その後VariableExprAST



ASTノードで使用します。 次に、関数オブジェクトを返します。 競合する引数名（たとえば、 "extern Foo (aba)"



）をチェックしないことに注意してください。 しかし、これは上記で使用した方法を使用して、非常に簡単かつ簡単に行うことができます。

 Function *FunctionAST::Codegen() { NamedValues.clear(); Function *TheFunction = Proto->Codegen(); if (TheFunction == 0) return 0;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

関数を定義するためのコード生成は非常に簡単に開始されます。プロトタイプコード生成（ Proto



）を呼び出し、すべてが正常であることを確認します。 また、NamedValuesカードをクリアして、処理中の最後の関数が残っていないことを確認します。 プロトタイプコードを生成すると、先に進むことができる既製のLLVM機能オブジェクトが確保されます。

  //      . BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); Builder.SetInsertPoint(BB); if (Value *RetVal = Body->Codegen()) {
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、Builderでの作業に進みます。 最初の行は、新しい基本ブロック [ en ]（ "entry"



と呼ばれる）を作成し、それがTheFunctionに挿入されます。 2行目は、新しいベースユニットの最後に新しい命令が挿入されることをビルダーに伝えます。 LLVMの基本ブロックは、制御フローグラフを定義する機能の重要な部分です。 制御フローがまだないため、関数には1つのブロックのみが含まれます。 しかし、第5章で修正します:)。

  if (Value *RetVal = Body->Codegen()) { //  . Builder.CreateRet(RetVal); //   ,    (). verifyFunction(*TheFunction); return TheFunction; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

挿入ポイントが設定されると、ルート関数式にCodeGen()



を使用してコード生成をCodeGen()



ます。 エラーが発生しない場合、入力ブロックに式計算コードを追加し、計算される値を返します。 次に、エラーがない場合、 LLVM命令"ret"



を作成し、関数を完成させます。 関数が作成された後、LLVMに組み込まれた"verifyFunction"



プロシージャを呼び出します。 生成されたコードに対してさまざまな一貫性チェックを実行し、コンパイラがすべてを正しく行っていることを判断します。 この手順を使用することは非常に重要です。多くのバグを検出できます。 関数が終了して検証されたら、それを返します。

  //  ,   . TheFunction->eraseFromParent(); return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この小さな部分はエラー処理用です。 簡単にするために、 eraseFromParent



メソッドを使用して、作成された関数のこの単純な削除を処理します。 これにより、ユーザーは以前に誤って入力された関数をオーバーライドできます。削除しなかった場合、シンボルテーブルに本体が含まれ、将来のオーバーライドが禁止されます。



実際、このコードにはバグがあります。 "PrototypeAST:: Codegen"



は、事前に定義された事前宣言を返すことができます。コードは実際にそれらを削除できます。 このバグを修正するにはいくつかの方法がありますが、何を思い付くことができるかを考えてください！ ここに小さなテストケースがあります：

 extern foo(ab); # o,  "foo". def foo(ab) c; # ,   'c'. def bar() foo(1, 2); # ,   "foo"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

メインプログラムの変更と最終的な考え

実際、これまでのところ、LLVMコード生成は少し興味深いものでしたが、興味深いIR呼び出しを見ることができます。 コードは、関数「HandleDefinition」、「HandleExtern」などでCodegenを使用してコード生成を呼び出し、LLVM IRをダンプします。 これにより、LLVM IRで簡単な機能を確認できます。 例：

  ready> 4 + 5;
トップレベルの式を読む：
ダブル@ ""（）を定義する{
エントリー：
         ret double 9.000000e + 00
 }

パーサーがトップレベルの式を匿名関数として返す方法に注目してください。 これは、次の章でJITサポートを追加するときに便利です。 また、コードは「非常に文字通り」、「まっすぐ」に翻訳することに注意してくださいIRBuilder



によって行われた定数の単純な折りたたみを除いて、最適化は行われIRBuilder



。 次の章で明示的に最適化を追加します。

  ready> def foo（ab）a * a + 2 * a * b + b * b;
関数定義の読み取り：
ダブル@fooを定義（double％a、double％b）{
エントリー：
         ％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）;
関数定義の読み取り：
ダブル@bar（double％a）{
エントリー：
         ％calltmp = call double @foo（double％a、double 4.000000e + 00）
         ％calltmp1 =ダブル@barを呼び出す（ダブル3.133700e + 04）
         ％addtmp = fadd double％calltmp、％calltmp1
         ret double％addtmp
 }

以下にいくつかの関数呼び出しを示します。 この関数を呼び出すと、長時間実行されることに注意してください。 将来的には、条件付きフロー制御を追加して、再帰を本当に便利にします:)。

  ready> extern cos（x）;
 externを読む： 
 double @cos（double）を宣言します

ready> cos（1.234）;

トップレベルの式を読む：
ダブル@ ""（）を定義する{
エントリー：
         ％calltmp = call double @cos（double 1.234000e + 00）
         ret double％calltmp
 }

ここにextern



いるのは、ライブラリ関数"cos"



とその呼び出しの外部です。

 準備完了> ^ D
 ;  ModuleID = '私のクールなjit'

ダブル@ ""（）を定義する{
エントリー：
         ％addtmp = fadd double 4.000000e + 00、5.000000e + 00
         ret double％addtmp
 }

ダブル@fooを定義（double％a、double％b）{
エントリー：
         ％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
 }

ダブル@bar（double％a）{
エントリー：
         ％calltmp = call double @foo（double％a、double 4.000000e + 00）
         ％calltmp1 =ダブル@barを呼び出す（ダブル3.133700e + 04）
         ％addtmp = fadd double％calltmp、％calltmp1
         ret double％addtmp
 }

 double @cos（double）を宣言します

ダブル@ ""（）を定義する{
エントリー：
         ％calltmp = call double @cos（double 1.234000e + 00）
         ret double％calltmp
 }

現在のデモを終了すると、生成されたモジュール全体のIRダンプが返されます。ここでは、すべての機能が相互に参照し合った全体像を見ることができます。



これで、万華鏡チュートリアルの第3章は終わりです。次の章では、JITサポートとオプティマイザーを追加して、実際にコードの実行を開始できるようにします！

完全なコードリスト

ここに、拡張LLVMコードジェネレーターなど、作業例の完全なコードリストを示します。LLVMライブラリを使用しているため、それらをコードにリンクする必要があります。これを行うには、llvm-configツールを次のように使用します。

#

g++ -g -O3 toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy

#

./toy



そして最後に、コード自体：

 #include "llvm/DerivedTypes.h" #include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Analysis/Verifier.h" #include "llvm/Support/IRBuilder.h" #include <cstdio> #include <string> #include <map> #include <vector> using namespace llvm; //===----------------------------------------------------------------------===// // Lexer ( ) //===----------------------------------------------------------------------===// //     [0-255],   , //       enum Token { tok_eof = -1, //  ( ) tok_def = -2, tok_extern = -3, //  ( : , ) tok_identifier = -4, tok_number = -5 }; static std::string IdentifierStr; // ,  tok_identifier static double NumVal; // ,  tok_number /// gettok -       . static int gettok() { static int LastChar = ' '; //  . while (isspace(LastChar)) LastChar = getchar(); if (isalpha(LastChar)) { // : [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 == '.') { // : [0-9.]+ std::string NumStr; do { NumStr += LastChar; LastChar = getchar(); } while (isdigit(LastChar) || LastChar == '.'); NumVal = strtod(NumStr.c_str(), 0); return tok_number; } if (LastChar == '#') { //     do LastChar = getchar(); while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if (LastChar != EOF) return gettok(); } //   . if (LastChar == EOF) return tok_eof; //         ASCII int ThisChar = LastChar; LastChar = getchar(); return ThisChar; } //===----------------------------------------------------------------------===// // Abstract Syntax Tree (     ) //===----------------------------------------------------------------------===// /// ExprAST -      . class ExprAST { public: virtual ~ExprAST() {} virtual Value *Codegen() = 0; }; /// NumberExprAST -       (, "1.0"). class NumberExprAST : public ExprAST { double Val; public: NumberExprAST(double val) : Val(val) {} virtual Value *Codegen(); }; /// VariableExprAST -      (, "a"). class VariableExprAST : public ExprAST { std::string Name; public: VariableExprAST(const std::string &name) : Name(name) {} virtual Value *Codegen(); }; /// BinaryExprAST -      . class BinaryExprAST : public ExprAST { char Op; ExprAST *LHS, *RHS; public: BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) : Op(op), LHS(lhs), RHS(rhs) {} virtual Value *Codegen(); }; /// CallExprAST -      . class CallExprAST : public ExprAST { std::string Callee; std::vector<ExprAST*> Args; public: CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) : Callee(callee), Args(args) {} virtual Value *Codegen(); }; /// PrototypeAST -    ""  , ///        (,  , ///    ). class PrototypeAST { std::string Name; std::vector<std::string> Args; public: PrototypeAST(const std::string &name, const std::vector<std::string> &args) : Name(name), Args(args) {} Function *Codegen(); }; /// FunctionAST -     class FunctionAST { PrototypeAST *Proto; ExprAST *Body; public: FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {} Function *Codegen(); }; //===----------------------------------------------------------------------===// // Parser (   ) //===----------------------------------------------------------------------===// /// CurTok/getNextToken -    . CurTok -   /// ,  . getNextToken     ///     CurTok. static int CurTok; static int getNextToken() { return CurTok = gettok(); } /// BinopPrecedence -      static std::map<char, int> BinopPrecedence; /// GetTokPrecedence -     . static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; // ,     . int TokPrec = BinopPrecedence[CurTok]; if (TokPrec <= 0) return -1; return TokPrec; } /// Error* -       . ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } static ExprAST *ParseExpression(); /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' static ExprAST *ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); //  . if (CurTok != '(') //  . return new VariableExprAST(IdName); //  . getNextToken(); //  ( std::vector<ExprAST*> Args; if (CurTok != ')') { while (1) { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); if (CurTok == ')') break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); } } //  ')'. getNextToken(); return new CallExprAST(IdName, Args); } /// numberexpr ::= number static ExprAST *ParseNumberExpr() { ExprAST *Result = new NumberExprAST(NumVal); getNextToken(); //   return Result; } /// parenexpr ::= '(' expression ')' static ExprAST *ParseParenExpr() { getNextToken(); //  (. ExprAST *V = ParseExpression(); if (!V) return 0; if (CurTok != ')') return Error("expected ')'"); getNextToken(); //  ). return V; } /// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr static ExprAST *ParsePrimary() { switch (CurTok) { default: return Error("unknown token when expecting an expression"); case tok_identifier: return ParseIdentifierExpr(); case tok_number: return ParseNumberExpr(); case '(': return ParseParenExpr(); } } /// binoprhs /// ::= ('+' primary)* static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { //    ,    while (1) { int TokPrec = GetTokPrecedence(); //           , //  ,    if (TokPrec < ExprPrec) return LHS; // ,  ,    . int BinOp = CurTok; getNextToken(); //    //       ExprAST *RHS = ParsePrimary(); if (!RHS) return 0; //  BinOp   RHS  ,    RHS, //      RHS  LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) { RHS = ParseBinOpRHS(TokPrec+1, RHS); if (RHS == 0) return 0; } //  LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } } /// expression /// ::= primary binoprhs /// static ExprAST *ParseExpression() { ExprAST *LHS = ParsePrimary(); if (!LHS) return 0; return ParseBinOpRHS(0, LHS); } /// prototype /// ::= id '(' id* ')' static PrototypeAST *ParsePrototype() { if (CurTok != tok_identifier) return ErrorP("Expected function name in prototype"); std::string FnName = IdentifierStr; getNextToken(); if (CurTok != '(') return ErrorP("Expected '(' in prototype"); //    . std::vector<std::string> ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); if (CurTok != ')') return ErrorP("Expected ')' in prototype"); //  . getNextToken(); //  ')'. return new PrototypeAST(FnName, ArgNames); } /// definition ::= 'def' prototype expression static FunctionAST *ParseDefinition() { getNextToken(); //  def. PrototypeAST *Proto = ParsePrototype(); if (Proto == 0) return 0; if (ExprAST *E = ParseExpression()) return new FunctionAST(Proto, E); return 0; } /// toplevelexpr ::= expression static FunctionAST *ParseTopLevelExpr() { if (ExprAST *E = ParseExpression()) { //   . PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); return new FunctionAST(Proto, E); } return 0; } /// external ::= 'extern' prototype static PrototypeAST *ParseExtern() { getNextToken(); //  extern. return ParsePrototype(); } //===----------------------------------------------------------------------===// // Code Generation () //===----------------------------------------------------------------------===// static Module *TheModule; static IRBuilder<> Builder(getGlobalContext()); static std::map<std::string, Value*> NamedValues; Value *ErrorV(const char *Str) { Error(Str); return 0; } Value *NumberExprAST::Codegen() { return ConstantFP::get(getGlobalContext(), APFloat(Val)); } Value *VariableExprAST::Codegen() { //      . Value *V = NamedValues[Name]; return V ? V : ErrorV("Unknown variable name"); } Value *BinaryExprAST::Codegen() { Value *L = LHS->Codegen(); Value *R = RHS->Codegen(); if (L == 0 || R == 0) return 0; 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"); //   0  1   0.0  1.0 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp"); default: return ErrorV("invalid binary operator"); } } Value *CallExprAST::Codegen() { //      . Function *CalleeF = TheModule->getFunction(Callee); if (CalleeF == 0) return ErrorV("Unknown function referenced"); //    . if (CalleeF->arg_size() != Args.size()) return ErrorV("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() == 0) return 0; } return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); } Function *PrototypeAST::Codegen() { //   : double(double,double)  .. std::vector<const Type*> Doubles(Args.size(), Type::getDoubleTy(getGlobalContext())); FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false); Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); //   (F)     ,     'Name'. //     ,      . if (F->getName() != Name) { //   ,      . F->eraseFromParent(); F = TheModule->getFunction(Name); //   (F)   , . if (!F->empty()) { ErrorF("redefinition of function"); return 0; } //   (F)    , . if (F->arg_size() != Args.size()) { ErrorF("redefinition of function with different # args"); return 0; } } //     . unsigned Idx = 0; for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); ++AI, ++Idx) { AI->setName(Args[Idx]); //      . NamedValues[Args[Idx]] = AI; } return F; } Function *FunctionAST::Codegen() { NamedValues.clear(); Function *TheFunction = Proto->Codegen(); if (TheFunction == 0) return 0; //      . BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); Builder.SetInsertPoint(BB); if (Value *RetVal = Body->Codegen()) { //  . Builder.CreateRet(RetVal); //   ,    (). verifyFunction(*TheFunction); return TheFunction; } //  ,   . TheFunction->eraseFromParent(); return 0; } //===----------------------------------------------------------------------===// // Top-Level parsing (  )   JIT //===----------------------------------------------------------------------===// static void HandleDefinition() { if (FunctionAST *F = ParseDefinition()) { if (Function *LF = F->Codegen()) { fprintf(stderr, "Read function definition:"); LF->dump(); } } else { //      . getNextToken(); } } static void HandleExtern() { if (PrototypeAST *P = ParseExtern()) { if (Function *F = P->Codegen()) { fprintf(stderr, "Read extern: "); F->dump(); } } else { //      . getNextToken(); } } static void HandleTopLevelExpression() { // Evaluate a top-level expression into an anonymous function. if (FunctionAST *F = ParseTopLevelExpr()) { if (Function *LF = F->Codegen()) { fprintf(stderr, "Read top-level expression:"); LF->dump(); } } else { //      . getNextToken(); } } /// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; case ';': getNextToken(); break; //     . case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; } } } //===----------------------------------------------------------------------===// // "" ,     //   ("extern")   . //===----------------------------------------------------------------------===// /// putchard -        0. extern "C" double putchard(double X) { putchar((char)X); return 0; } //===----------------------------------------------------------------------===// // Main driver code (  ) //===----------------------------------------------------------------------===// int main() { LLVMContext &Context = getGlobalContext(); //    . // 1 -  . BinopPrecedence['<'] = 10; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; BinopPrecedence['*'] = 40; //  . fprintf(stderr, "ready> "); getNextToken(); //  ,     . TheModule = new Module("my cool jit", Context); //    " ". MainLoop(); //   . TheModule->dump(); return 0; }