技術

3.4. 関数のコード生成

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第3章 万華鏡: LLVM IRコードの生成
第4節 関数のコード生成

プロトタイプと関数のためのコード生成は、いくつかの細かい点について処理しなければならない。
なので、式に関するコード生成のときより美しくなくなるが、しかしいくつかの重要な点について解説するための良い題材となる。
まず、プロトタイプのためのコード生成について考えてみよう。
プロトタイプは、関数本体と外部関数(extern関数)宣言の両方で使用される。

Function *PrototypeAST::Codegen() {
  // double(double, double)などの関数型を作る。
  std::vector<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が生成される。
万華鏡における関数の引数は全てdoubleなので、最初の行はN個のLLVM double型のベクタを生成する。
そして、N個のdoubleの引数をとり、それらが可変長(vararg)ではなく(falseがそれを示している)、ひとつのdoubleの戻り値を返す関数型がFunctionType::getによって生成される。
LLVMにおける型は、定数と同じように一意となるので、型を”new”するのではなく、”get”しなければならない。
訳注: N個 = Args.size()個。
Argsは引数名を保持するPrototypeASTのメンバ変数で、型はstd::vector<std::string>である。

上のコードの最後の行では、プロトタイプに合致するであろう関数が実際に生成される。
型やリンケージや名前を指定することで、どのモジュールを挿入するかを示す。
外部リンケージ(external linkage)は、関数が現在のモジュールの外部で定義されるかもしれない事、および(または)、外部のモジュールの関数から呼び出し可能であるという事を意味する。
上記の関数呼び出しに渡されてるNameは、ユーザーが指定したものである。
TheModuleが引数に指定されてるので、その名前はTheModuleのシンボルテーブルに登録される。
訳注: NameはPrototypeASTのメンバ変数であり、PrototypeASTインスタンスの生成時に構文解析器によってNameの中身は渡されている。

// Fの名前がNameと一致しない場合, Nameが表す文字列で名付けられた何かがすでに存在しているということになる。
// 関数本体を持つものに関しては、再定義や再extern(reextern)は許可しない。
if (F->getName() != Name) {
  // ひとつだけ存在してる状態を保つために、消去する。
  F->eraseFromParent();
  F = TheModule->getFunction(Name);

モジュールのシンボルテーブルは、名前の不一致があった場合には関数のシンボルテーブルとして動作する。
もし新しい関数が、すでにシンボルテーブルに追加されているものと同じ名前によって生成された場合、その関数がモジュールに追加されるとき暗黙的にリネームされる。
上のコードは、この事実を利用してこの関数がすでに定義されているかどうかを判定している。

万華鏡では、2つの場合において関数の再定義を許可することにした。
ひとつは、プロトタイプが合致する限り(引数はすべて同じ型なので、引数の数が合ってるかどうかだけチェックすればいい)、externの宣言を複数回可能としたい。
もうひとつは、まずextern宣言した後、後でその本体を定義する事を可能としたい。
これは、互いに再帰的な関数の定義で役立つ。

これを実装するにあたって、上のコードではまず関数の名前の不一致が無いかどうかチェックする。
もし不一致があれば、たった今生成したばかりの関数を(eraseFromParentを呼び出すことによって)削除し、それから指定された名前を使って、すでに存在している関数を得るためにgetFunctionを呼ぶ。
LLVMには、消去(erase)系や、除去(remove)系のAPIがたくさんある事に注意。
remove系は、該当のオブジェクトをその親から分離(unlink)(例えば、モジュールから関数を分離、等)して、そのオブジェクトを返す。
erase系は、該当のオブジェクトをその親から分離(unlink)して、そのオブジェクトを削除(delete)する。

  // すでに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;
  }
}

上記のロジックを検証するために、まず、すでに存在してる関数が”空(empty)”かどうかをチェックする。
この場合の”空”とは、その関数が基本ブロックを持たない、つまり本体を持たないという事を意味する。
関数が本体を持たない場合、それは前方宣言である。
関数の完全な定義の後は何も許可されないので、その場合はこのコードは受け入れない。
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;
}

最後のちょっとしたプロトタイプのためのコードは、現在の関数におけるすべての引数についてループを回し、LLVM引数オブジェクト(LLVM Argument objects)の名前をセットし、この後VariableExprASTノードで使えるようにするために、NamedValuesにその引数を登録する。
これが終われば、このメンバ関数は呼び出し元に関数オブジェクトを返す。
ここでは、引数名の重複についてはチェックしていない点に注意。(例えば、”extern foo(a b a)”)
これを行うには、これまで使ってきた方法を使えば簡単に実装できるだろう。
訳注: 引数名はArgs配列(vector<std::string>)に入ってるので、効率はさて置いて重複を調べるのは簡単だろう。
後は、重複があった場合に関数オブジェクトを消して、return 0 するだけで良い。んじゃないかな。

Function *FunctionAST::Codegen() {
  NamedValues.clear();

  Function *TheFunction = Proto->Codegen();
  if (TheFunction == 0)
    return 0;

関数定義のためのコード生成処理の始まりは、これで十分である。
その関数のプロトタイプ(Proto)のコード生成を行い、戻り値をチェックするだけである。
NamedValues(std::map<std::string, Value*>、グローバル変数)をクリアしているのは、直前の関数のコンパイルによるデータを消して、確実に空にするためである。
プロトタイプのコード生成によって、この後の処理に用いるLLVM関数オブジェクトの存在が確実なものとなる。

// 挿入するための、新しい基本ブロックを作成する。
BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction);
Builder.SetInsertPoint(BB);

if (Value *RetVal = Body->Codegen()) {

これはBuilderをセットアップしてる部分である。
最初の行で、新しい基本ブロック(名前は”entry”)が作成され、TheFunctionの中に挿入される。
次の行で、今後の命令を新しい基本ブロックの末尾に挿入すべきであるという事Builderに伝える。
LLVMにおける基本ブロックは、制御フローグラフ(Control Flow Graph)を定義するための、関数の重要な部分である。
現時点では何の制御フローも持たないので、関数はひとつのブロックのみを含むだろう。
これについては第5章で改良する。
訳注: 制御フローグラフについて知らない場合はググるべし。

if (Value *RetVal = Body->Codegen()) {
  // 関数を仕上げる。
  Builder.CreateRet(RetVal);

  // 矛盾が無いか、生成されたコードを検証する。
  verifyFunction(*TheFunction);

  return TheFunction;
}

挿入点(insertion point)がセットされたら、関数のルート式(root expression)のためにCodeGen()メソッドを呼ぶ。
何もエラーが起きなければ、entryブロックの中に、式を計算しその結果を返すためのコードが生成さる。
エラーが起きなければ、関数を完成させるため、LLVMのret命令が生成される。
関数が出来上がったら、LLVMが提供するverifyFunction関数を呼ぶ。
この関数は、生成されたコードに対して種々の整合性チェックを行うことによって、我々のコンパイラの動きに間違いがないかを調べる。
多くのバグを捕まえることが出来るので、この関数は重要である。
関数が完成し検証されれば、それを返す。
訳注: ret命令は以下の形をとる。

ret <type> <value>       ; 非void関数から値を返す。
ret void                 ; void関数から返る。

  // 本体のコード生成でエラーがあれば、関数を消去する。
  TheFunction->eraseFromParent();
  return 0;
}

残りは、エラーの場合の処理だけである。
簡単のため、eraseFromParentメソッドで単に関数を消去することによって、この場合を処理する。
これによって、ユーザーが以前に間違って入力した関数を再定義することが可能となる。
もし、エラー時に消去しない場合、その関数本体と共にシンボルテーブルに残り続け、再定義を妨げてしまうだろう。

まぁ正直いうと、このコードにはバグがある。
PrototypeAST::Codegenは、以前に定義された前方宣言を返す可能性があるので、このコードでは実は前方宣言を削除してしまう可能性がある。
このバグを修正する方法はたくさんあるが、どうやったらそれが可能か考えてみて欲しい。
以下はそのためのテストケースである。

extern foo(a b);     # ok, defines foo.
def foo(a b) c;      # error, 'c' is invalid.
def bar() foo(1, 2); # error, unknown function "foo"

訳注: 1行目でプロトタイプが生成される。
2行目で、不明な変数cを使っているのでエラーとなる。
が、このとき関数本体の定義だけでなく1行目で宣言したプロトタイプも消去される。
よって、3行目でfooという関数が不明というエラーが発生してしまっている。
関数本体の定義にエラーがあっても、事前に宣言されたプロトタイプを消去しないようにすれば、3行目ではエラーは出なくなるはずである。

コメントを残す

メールアドレスが公開されることはありません。



※画像をクリックして別の画像を表示