技術

5.2.5. if/then/elseのためのコード生成

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第5章 万華鏡: 言語の拡張: 制御フロー
第2.5節 if/then/elseのためのコード生成

if/then/elseのためのコードを生成するために、IfExprASTのCodegenメソッドを実装する。

Value *IfExprAST::Codegen() {
  Value *CondV = Cond->Codegen();
  if (CondV == 0) return 0;

  // 条件を0.0と比較することによって真偽値に変換する。
  CondV = Builder.CreateFCmpONE(CondV,
                              ConstantFP::get(getGlobalContext(), APFloat(0.0)),
                                "ifcond");

このコードは実に素直で、そして以前見たものと似ている。
条件のための式を生成し、そしてその値をゼロと比較し、1bitの値として真偽値を得る。

Function *TheFunction = Builder.GetInsertBlock()->getParent();

// thenとelseの場合のためのブロックを生成する。
// thenブロックを関数の最後に挿入する。
BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction);
BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else");
BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont");

Builder.CreateCondBr(CondV, ThenBB, ElseBB);

このコードは、前節の例におけるブロックと直接対応していて、if/then/elseに関連した基本ブロックを生成するものである。
最初の行で、現在構築中の関数オブジェクトを取得する。
現在の基本ブロックについてBuilderに尋ね、そしてその親のブロックについて尋ねることによってそれを得る。(その関数はすでに埋めこまれているのでこうして取得する。)

それが終われば、上記のコードは3つのブロックを生成する。
thenブロックのコンストラクタにTheFunctionが渡されているという点に注意。
これによって、新しいブロックが指定された関数の末尾に自動的に挿入される。
他の2つのブロックも作成されるが、まだ関数の中へは挿入しない。

ブロックが生成されたら、どちらのブロックを選ぶかを決めるための条件分岐を生成することが出来る。
新しいブロックの生成は、IRBuilderに対して暗黙的にも影響を与えないことに注意。
なので、それはまだ、条件が入ってるブロックに挿入している。(so it is still inserting into the block that the condition went into.)
thenブロックやelseブロックへの枝分かれの生成はしているが、”else”ブロックはまだ関数に挿入されていないことにも注意。
これでいいのである。
これはLLVMが前方参照をサポートする標準的な方法である。

// then値を発行する。
Builder.SetInsertPoint(ThenBB);

Value *ThenV = Then->Codegen();
if (ThenV == 0) return 0;

Builder.CreateBr(MergeBB);
// thenのCodegenは、現在のブロックを変更し、phiのためにThenBBを更新しうる。
ThenBB = Builder.GetInsertBlock();

条件分岐が挿入されたあと、Builderにthenブロックへ挿入させるようにする。
厳密に言えば、この呼出は指定されたブロックの最後に挿入点を移動する。
しかしながら、thenブロックは空なので、そのブロックの最初から挿入されるようになる。

挿入点がセットされたら、ASTからthenのCodegenを再帰的に実行する。
thenブロックを仕上げるために、無条件の分岐(br命令)をmergeブロックに生成する。
LLVM IRの面白い(そしてとても重要な)性質として、返り(return)や枝分かれ(branch)のような制御フロー命令で、基本ブロックを必ず終端しなければならないという点がある。
これは、フォールスルーを含む全ての制御フローは、LLVM IRにおいては明確でなければならないということを意味する。
このルールに違反した場合、ベリファイアはエラーを発行する。
訳注: ここでいうフォールスルーとは、LLVM IRにおいて、ある関数内のあるブロックから単にすぐ後のブロックに移る、といいう意味だと思う。
この場合も、明確にbr命令をおいて次のブロックを指定しなければならない。

最後の行はかなり分かりづらいが、とても重要である。
mergeブロックにおいてphiノードを生成するとき、phiをどう働かせるかを示すためのブロックと値のペアをセットアップする必要があるということが基本的な問題である。
重要なのは、phiノードは、CFG(Control flow graph)におけるブロックの各先行命令のためのエントリを持つということを予期しているということである。
ところで、5行前で挿入点をThenBBへセットしたときに、現在のブロック得たか?
then式は実際に、Builderがその中に発行した自身のブロックを変更しうるということが問題である。
例えば、入れ子になったif/then/else式を含むかもしれない。
Codegenを再帰的に呼ぶことで、現在のブロックの意向を任意に変えることができるので、phiノードをセットアップするコードの最新の値が必要である。
訳注: 正直ここの文章の訳は全くしっくり来てないので、原文をまとめて載せておく。
The final line here is quite subtle, but is very important. The basic issue is that when we create the Phi node in the merge block, we need to set up the block/value pairs that indicate how the Phi will work. Importantly, the Phi node expects to have an entry for each predecessor of the block in the CFG. Why then, are we getting the current block when we just set it to ThenBB 5 lines above? The problem is that the “Then” expression may actually itself change the block that the Builder is emitting into if, for example, it contains a nested “if/then/else” expression. Because calling Codegen recursively could arbitrarily change the notion of the current block, we are required to get an up-to-date value for code that will set up the Phi node.

// elseブロックを発行する。
TheFunction->getBasicBlockList().push_back(ElseBB);
Builder.SetInsertPoint(ElseBB);

Value *ElseV = Else->Codegen();
if (ElseV == 0) return 0;

Builder.CreateBr(MergeBB);
// elseのCodegenは、現在のブロックを変更し、phiのためにElseBBを更新しうる。.
ElseBB = Builder.GetInsertBlock();

elseブロックのためのコード生成は、基本的にthenの場合と同じである。
唯一の重要な違いは、最初の行で、elseブロックを関数へ追加している。
少し前に、elseブロックは作成されたが、関数へ追加されていなかったことを思い出そう。
これでthenブロックとelseブロックは発行された。
分岐を合流させるコード(merge code)によってこれを仕上げよう。

  // mergeブロックの発行。
  TheFunction->getBasicBlockList().push_back(MergeBB);
  Builder.SetInsertPoint(MergeBB);
  PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
                                  "iftmp");

  PN->addIncoming(ThenV, ThenBB);
  PN->addIncoming(ElseV, ElseBB);
  return PN;
}

最初の2行は、今となっては見慣れただろう。
最初の行は、関数オブジェクトへmergeブロック(上のelseブロックと同じように宙ぶらりんになっていた)を追加している。
次の行で、新しく生成されたコードがmergeブロックに挿入されるよう挿入点を変更している。
これが完了したら、phiノードを生成し、phiノードのためのブロックと値のペアを準備する。

最後に、このCodegen関数は、phiノードをif/then/else式によって計算された値として返す。
前節の例では、この戻り値はトップレベルの関数のコードの中に送り込まれ、その関数はreturn命令を生成するだろう。
訳注: 前節の例というのは多分コレ。

extern foo();
extern bar();
def baz(x) if x then foo() else bar();

これで、万華鏡において条件付きのコードを実行する能力を得た。
この拡張によって、万華鏡は、いろんな種類の数学的計算をおこなえる極めて完全な言語となった。
次は、非関数型言語でおなじみの便利な式を追加する。

コメントを残す

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



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