5.7 5.7.2 コード生成クラスの実装方針 コード生成 コード生成では構文解析 / 意味解析で生成した AST を頂点からたどり、必要に応じて関数や命令の生 成を行います。これまでと同じようにコード生成用に C 。 deGen クラスを作成していきます。次に CodeGen クラスの実装方針を示します。 ・基本的に AST クラス 1 つにつき 1 つのコード生成メソッドを作成し、 translation unit から深さ優先で AST をたどってコード生成を行う ・各コード生成メソッド名は「 generate 」から始まり、 AST クラス名との対応がわかるものにする ・コード生成開始のトリガとなる doCodeGen メソッドを実装する ・コード生成は外部から doCodeGen メソッドを呼び出すことで開始し、解析結果の成否を真偽値で返す ・生成した LLVM 旧を外部から取得するために、生成した ModuIe のポインタを返す getModuIe を実装する 以上をまとめた CodeGen クラスの宣言例をリスト 5.32 に示します。 ■リスト 5.32 CodeGen クラスの宣言 2 3 5 6 7 8 9 10 17 20 22 23 24 * コード生成クラス 4 class CodeGen { private : Function *CurFunc ー Modu1e *Mod ー 工 RBui1der く > *Bui1der; public : C0deGen ( ) : -C0deGen ( 房 / / 現在コード生成中の Funct 土 on / / 生成した Modu1e を格納 / / L もⅧーエ R を生成する工 RBu 土 lder クラス b001 doCodeGen ( Trans1ationUnitAST &tunit ′ M0du1e &getM0du1e( ) : private : std: : string name); b001 generateTranslationUnit(TranslationUnitAST &tunit' std: : string name) : Function *generateFunctionDefinition( FunctionAST *func ー Module *mod 房 Function *generateprototype ( PrototypeAST *proto ′ Module * 爪 Od Va1ue Va1ue Va1ue Va1ue Va1ue *generateFunctionStatement ( FunctionStmtAST *func—stmt *generateVariab1eDeclaration (VariableDeclAST *vdecl *generateStatement(BaseAST *stmt); *generateBinaryExpression ( BinaryExprAST *bin—expr *generateCa11Expression(Ca11ExprAST *call—expr); 109

第 5 章フロントエンドの作成 その BasicBIock の前に挿入されます。 generateFunctionDefinition では、 BasicBIock を生成した後、 IRBuilder クラスの SetInsertPoint メソッドで命令の挿入位置を指定しておきます。 SetInsertPoint は IRBuiIder のスーパークラスである IRBuiIderBase クラスで定義されているメソッドで、引数の異なる複数の SetInsertPoint が存在します。 今回使用する SetInsertPoint メソッドのインターフェイスは次のとおりです。 IIvm::IRBuiIderBase::SetInsertPoint VOid Set 工 nsertPoint(BasicBIock *TheBB) SetInsertPoint は、引数で指定した BasicBl 。 ck の末尾に命令の挿入位置を設定します。以降、 IRBuiIder で命令を生成した場合はここで指定した BasicBlock の最後に命令が追加されていくことになり ます * 7 以上をまとめた generateFunctionDefinition をリスト 5.38 に示します。 ・リスト 5.38 generateFunctionDefinition 2 3 4 5 6 7 8 9 12 17 18 ☆関数定義生成メソッド ☆ @param FunctionAST Modu1e * @return 生成した Function のポインタ Function *CodeGen: :generateFunctionDefinition(FunctionAST *func_ast, Modu1e ☆爪 od ) { Function *func=generatePrototype ( func—ast->getPrototype ( ) ′ mod 房 if い func){ return NULL ー func ー CurFunc BasicB10ck *bb10ck=BasicBlock: :Create(getG10ba1Context( ) ′ Bui1der->SetInsertP0int(bb10ck); / / Function のボディを生成 generateFunctionStatement ( func—ast->getBody ( ) ); return func ー generateFunctionStatement generateFunctionStatement では Function のボディを生成します。 "entry" ′ func とは言え、実際に LLVM IR を生 成するのは内部で呼び出す generateVariableDeclaration と generateStatement です。 generateFunction * 7 ほかにも lnstruction 単位で命令の挿入位置を設定する SetlnsertPoint もあります。 116

第 5 章フロントエンドの作成 第 1 引数には戻り値の型を Type で指定します。第 2 引数には引数の型を示す Type を格納したべクタ を与えます。第 3 引数には可変長引数かどうかを b 。 ol 型で指定します。なお、 Type の生成には複数の方 法があるのですが、本書では次に示す Type クラスのメソッドを使用します。 IIvm::Type::getInt32Ty static 工 ntegerType * get 工 nt32Ty(LLVMContext &C) Type クラスの宣言は「 llvm/Type. h 」にあります。なお、 DummyC はすべて int 型という制約を設 けているので Type の生成はどれも getInt32Ty ( ) メソッドを用いればよいのですが、 void 型の場合は getVoidTy 、 float 型の場合は getFloatPtrTy などのほかのメソッドを使用しなければなりません。以上をま ・リスト 5.37 generatePrototype とめた generatePrototype をリスト 5.37 に示します。 2 3 4 5 6 7 8 9 14 17 20 22 23 24 26 27 28 29 30 114 ☆関数宣言生成メソッド * @param PrototypeAST ′ Module ま @return 生成した Function のポインタ Function *CodeGen : : generatePrototype ( PrototypeAST *proto ′ / / already declared? Function *func=mod—>getFunction (proto—>getName ( ) if(func){ ModuIe *mod ) { if( func->arg—size ( )==prot0->getParamNum( ) & & func->empty( ) ) { return func ー }else{ fprintf ( stderr, return NULL ー "error: : function is redefined",proto—>getName( ) . c—str( ) 房 / / create arg—types std : : vector く Type*> int—types ( proto—>getParamNum( ) ′ Type: :getInt32Ty(getG10ba1Context( ) ) ); / / create func type FunctionType *func—type = FunctionType : : get ( Type: :getInt32Ty( getG10ba1Context( ) )' int—types ′ false / / create function func=Function : : Create ( func—type ー Function : : ExternalLinkage ′ prot0->getName ( )'

5.5 構文解析 Variab1eTab1e ・ push—back(vdecI->getName( ) ) : }else if (var—decI=visitVariabIeDec1aration( ) ) { while (var—decl ) { var—dec1->setDec1Type(VariableDec1AST: : local); ・・・本来ならここで変数がニ重宣言されていないことを確認・・ func—stmt—>addVariableDec1aration (var—decl 房 Variab1eTab1e ・ push—back ( var—decI->getName ( ) ); var—decl=visitvariablel)eclaration ( ); if ( stmt=visitStatement( ) ) { while(stmt){ last—stmt=stmt; func—stmt—>addStatement ( stmt ) : stmt=visitStatement ( 房 //other }else{ SAFE—DELETE ( func—stmt ); Tokens->app1yTokenIndex ( bkup return NULL ー 第 5 章 ・・・本来ならここで戻り値の確認・・ if (Tokens->getCurString( ) = Tokens—>getNextToken ( 房 return func—stmt : }else{ SAFE—DELETE ( func_stmt ); Tokens->app1yT0ken 工 ndex ( bkup ) : return NULL; visitVariabIeDecIaration で変数宣言を解析した後、本来は変数が二重宣言がされていないことを確認 する部分ですが、構文解析では行いません。また、 Statement が return 文で終了し、関数が値を返すこ とも確認すべきですが、これも構文解析では未実装とします。 次は、 visitAssignmentExpression です。 visitAssignmentExpression で解析する非終端記号、 assign 89

5.6 意味解析 ■リスト 5.28 意味解析を実装した visitFunctionStatement * FunctionStatement 用構文解析メソッド 2 * @param 関数名、引数を格納した p て ototype クラスのインスタンス 3 * @return 解析成功 : FunctionStmtAST 解析失敗 : NULL 4 5 FunctionStmtAST *Parser : : visitFunctionStatement ( PrototypeAST * p て 0t0 ) { 6 int bkup=Tokens->getCur 工 ndex ( ); 7 8 9 new FunctionStmtAST ( 15 FunctionStmtAST *func—stmt }else if (var—dec1=visitVariab1eDec1aration( ) ) { while (var—decl) { 20 var—dec1->setDec1Type(Variab1eDec1AST: : local); / / 変数名に重複がないか確認 22 if( std: : find(VariableTab1e ・ begin( ) ′ Variab1eTab1e. end( ) ′ var—dec1->getName( ) ) 23 Variab1eTab1e. end( ) ) { 24 SAFE—DELETE ( var—decl 房 25 SAFE—DELETE ( func—stmt 房 26 return NULL; 27 28 / / 変数名テーブルに新しく読み取った変数名を追加 29 Variab1eTab1e. push—back(var—dec1->getName( ) ); 30 func—stmt->addVariab1eDec1aration ( var—decl ); var—dec1=visitVariab1eDec1aration( ) : 32 33 34 36 37 38 39 40 42 43 44 45 46 47 if(Tokens->getCurString( ) = Tokens->getNextToken ( }else{ return NULL; 第 5 章 if(stmt=visitStatement( ) ) { while( stmt) { last—stmt=stmt ー func—stmt->addStatement ( stmt ); stmt=visitStatement ( ) : / / other }else{ SAFE—DELETE ( func—stmt ) : Tokens->app1yToken 工 ndex ( bkup ); return NULL; 103

5.7 コード生成 Statement で行うことは、引数で与えられた FunctionStmtAST が保持する VariabIeDecIAST と各種 Statement の AST を探索し、前述のコード生成メソッドを呼び出すだけです。ただし、 NuIIExprAST についてはコード生成をする必要がないので、何もしないことにします。以上の内容を実装した generateFunctionStatement をリスト 5.39 に示します。 ■リスト 5.39 generateFunctionStatement 33 } v=generateStatement ( stmt else if ( ! isa く Nu11ExprAST>( stmt) ) break; if い stmt) stmt=func—stmt—>getStatement ( 土 / / 最後まで見たら終了 for(int 土 = の BaseAST *stmt; //insert expr statement v=generateVariab1eDeclaration ( vdecl ) : vdecl=dyn—cast く VariableDec1AST>( func—stmt->getVariab1eDec1 は ) / / create alloca return v•, break; if ( ! func—stmt->getVariab1eDec1 は ) ) / / 最後まで見たら終了 for(int 土 = Va1ue *v=NULL; Variab1eDec1AST *vdecl; //insert variable decls 7 Va1ue *CodeGen : : generateFunctionStatement ( FunctionStmtAST *func—stmt ) { ☆ @return 最後に生成した value のポインタ * @param FunctionStmtAST ☆変数宣言、ステートメントの順に生成 * 関数生成メソッド 32 30 29 28 27 26 25 24 23 22 20 10 9 8 6 5 4 3 2 117 す。 CreateA Ⅱ oca のインターフェイスは次のとおりです。 変数宣言の生成とはつまり AIIoca 命令の生成であり、 IRBuilder クラスの CreateAlloca を用いて行いま generateVariableDeclaration では BasicBlock に変数宣言を追加します。 generateVariableDeclaration

第 5 章フロントエンドの作成 function statement variable_declaration 」 ist variable declaration va 「 iable_declaration va 「 iable decla 「 ation list ■図 5.4 function_statement の構文図 ・一一一 statement statement list statement_list function ー statement は変数宣言のリストと式のリストを含む関数のプロックを表す非終端記号です。 function—statement を受け入れるための visitFunctionStatement メソッドの構文解析時点でのコード例を リスト 5.17 に示します。 ■リスト 5.17 visitFunctionStatement 2 3 4 5 * FunctionStatement 用構文解析メソッド * @param 関数名や引数を格納した prototype クラスのインスタンス * @return 解析成功 : FunctionStmtAST 解析失敗 : NULL 6 FunctionStmtAST *Parser : : visitFunctionStatement ( PrototypeAST *proto ) { 7 8 9 15 20 88 int bkup=T0kens->getCurIndex ( ); new FunctionStmtAST( ); FunctionStmtAST *func—stmt / / 引数を func ー st Ⅲ t の変数宣言リストに追加 for (int 土 = 土く proto->getparamNum( i 十 + ) { Variab1eDeclAST *vdecl=new Variab1eDeclAST(proto—>getParamName( i) 房 vdec1->setDec1Type ( Variab1eDec1AST : : param); func—stmt->addVariab1eDec1aration ( vdecl if(Tokens->getCurString( ) = Tokens—>getNextToken ( }else{ return NULL ー

第 5 章フロントエンドの作成 29 30 32 33 34 35 36 37 38 39 40 42 43 / /FunctionDec1aration PrototypeAST *proto=visitFunctionDeclaration ( if(proto) { tunit->addprototype ( proto ) : return true ー //FunctionDefinition FunctionAST *func—def=visitFunctionDefinition ( if( func—def ) { tunit->addFunction ( func—def ); return true ー return false; 44 } visitTranslationUnit の内部では、 EOF がくるまで visitExternalDeclaration による external_declara tion の解析を繰り返します。 visitTransIationUnit メソッドは解析成功の場合はメンバ変数 TU に解析結 果として AST の頂点である TranslationUnitAST のインスタンスを代入し、 true を返します。失敗時には 解析中の AST を破棄して TU に NULL 値を設定した後、 false を返します。 なお、 visitExternaIDecIaration は引数として TransIationUnitAST のポインタをとり、解析した FunctionDeclarationAST と FunctionDefinitionAST を TranslationUnitAST に追加するようにしまし た。ほかのメソッドと整合性をとるためには TranslationUnit への AST の追加は visitTranslationUnit 内 で行ったほうがよいかもしれませんが、簡単に実装したかったのでこのようになっています。以降、同様に構 文規則に基づいて解析メソッドを実装しますが、以降では実装上注意すべき箇所に絞って説明を進めます。 関数の再定義の確認はしない ます、関数宣言と関数定義の解析、つまり visitFunctionDecIaration と visitFunctionDefinition での 処理について説明します。先に構文図を図 5.2 に掲載しておきましよう ( 図中に登場する prototype の解析 は、後述の visitPrototype の説明で言及します ) 。 function declaration ・一 - ー - 十 - prototype function definition ーーー - 十 p 「 ototy pe function_statement ・図 5.2 function_declaration と function definition の構文図 84

5.7 コード生成 for(int i=0; FunctionAST *func=tunit. getFunction(i); if( !func) break; else if( !generateFunctionDefinition(func, MOd) ) { SAFE—DELETE od return false; return true ー generatePrototype FunctionType クラスの get メソッドを使用します。 FunctionType の宣言は「 llvm/DerivedTypes. h 」にあ さて、先ほど後回しにしていた FunctionType の説明に移りましよう。 FunctionType の生成には します。 メソッドで関数名を取得して与えます。第 4 引数には生成した Function を追加する Module クラスを指定 こでは ExternalLinkage を指定します。第 3 引数は関数名の指定なので、 Prot0typeAST の getName() ます。 LinkageTypes は GlobalValue クラスに定義されている列挙型で、さまざまな要素を含みますが、 成については後述するので、 Function::Create の説明を続けます。第 2 引数には LinkageTypes を指定し 第 1 引数の FunctionType は、 Function の戻り値や引数リストを表すクラスです。 FunctionType の生 ModuIe *M=O) static Function ☆ Create(FunctionType *TY' LinkageTypes Linkage' const Twine lIvm::Function::Create す。 Function::Create のインターフェイスは次のとおりです。 Function の生成には「 llvm/Function. h 」に宣言された Function クラスの create メソッドを使用しま 生成を行います。 generateprototype は Function のボディは生成しないので、空の Function 、つまりプロトタイプ宣言の generateprototype では、 Prot0typeAST の情報から Function を生成し、 M0dule に追加します。 り、 FunctionType::get のインターフェイスは次のとおりです。 IIvm::FunctionType::get static FunctionType ☆ get(Type *Resu1t' isVarArg) ArrayRef く Type ☆ > Params, b001 113

第 5 章フロントエンドの作成 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 / / 最後の Statement が jump—statement であるか確認 if( ! last—stmt Ⅱ ! isa く JumpStmtAST>( last—stmt) ) { SAFE—DELETE ( func—stmt 房 Tokens->app1yT0kenIndex ( bkup return NULL; if(Tokens->getCurString( ) = Tokens—>getNextToken ( return func_stmt ー }else{ SAFE—DELETE ( func—stmt ) : Tokens->app1yT0ken 工 ndex ( bkup ) : return NULL; 23 行目での find 関数で、 VariabIeTabIe に新しく読み取った変数宣言の変数名が登録されているか確認 しています。 VariabIeTabIe は解析中の関数の変数名を登録しておくべクタなので、この処理で変数が二重 宣言されないようにしています。変数名に重複があった場合は NULL を返し、そうでなければ 30 行目で VariableTable に読み取った変数名を追加します。 次に、意味解析を実装した visitAssignmentExpression はリスト 5.29 のようになります。 ■リスト 5.29 意味解析を実装した visitAssignmentExpression ☆ AssignmentExpression 用構文解析メソッド 2 ☆ @return 解析成功 : AST 解析失敗 : NULL 3 4 BaseAST *Parser: :visitAssignmentExpression( ) { 5 int bkup=Tokens->getCurIndex ( 6 7 8 9 20 BaseAST * lh if (Tokens->getCurType( )==TOK—IDENT 工 FIER) { / / 変数が宣言されているか確認 if( std: :find(Variab1eTabIe. begin( ) ′ Variab1eTab1e. end( ) ′ T0kens->getCurString( ) ) Variab1eTab1e. end( ) ) { lhs=new Variab1eAST ( Tokens->getCurString ( ) ); Tokens—>getNextToken ( ); BaseAST *rhs; if ( Tokens->getCurType ( ) ==TOK—SYMBOL & & Tokens->getCurString ( ) = Tokens—>getNextToken ( if (rhs=visitAdditiveExpression(NULL) ) { return new BinaryExprAST ( " lhs, rhs ) : }else{ 104