技術

5.2.4. if/then/elseのためのLLVM IR

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

これで、構文解析してASTを構築できるようになった。
最後のパーツは、LLVMコードの生成機能の追加である。
これはif/then/elseの実例における一番興味深い部分である。
なぜならこれが、新しいコンセプトを紹介するスタート地点だからである。
前節までのコードは以前の章で十分に解説されている。

我々がやりたい事をコードに行わせるために、以下の簡単な例を見て、考えてみよう。

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

もし最適化無しなら、上のコードは万華鏡により以下のようになるはずである。

declare double @foo()

declare double @bar()

define double @baz(double %x) {
entry:
  %ifcond = fcmp one double %x, 0.000000e+00
  br i1 %ifcond, label %then, label %else

then:       ; preds = %entry
  %calltmp = call double @foo()
  br label %ifcont

else:       ; preds = %entry
  %calltmp1 = call double @bar()
  br label %ifcont

ifcont:     ; preds = %else, %then
  %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
  ret double %iftmp
}

制御フローグラフを視覚化するために、LLVMの”opt”ツールのイカシた機能を使用することが出来る。
上記をt.llに保存したとして、”llvm-as < t.ll | opt -analyze -view-cfg"を実行すると、ウインドウが立ち上がり、次のようなグラフが見れるはずである。 訳注: LLVMをソースからコンパイルしてインストールしただけで他は何も設定してないMacでは、上記のコマンドだけでは何のウインドウも開かなかったが、/tmpディレクトリに.dotファイルが出力され、それをGraphvizで開くと同じものが見れた。

cfgbaz-cfac13

このグラフを得る方法は他にもある。
実際のコードの中に、“F->viewCFG()” か “F->viewCFGOnly()”の呼び出し(FはFunction*)を追加して再コンパイルするか、デバッガで“F->viewCFG()” か “F->viewCFGOnly()”を呼び出すと同じグラフが得られる。
LLVMは、いろんなグラフを視覚化するための素晴らしい機能をたくさん持っている。

生成されるべきコードに話を戻すと、それは極めてシンプルである。
entryブロックは条件式を評価し(上記の例ではxが条件式である)、その結果を”fcmp one”命令(”one”は”Ordered and Not Equal”)を用いて0.0と比較する。
この式の結果を元に、コードは”then”か”else”ブロックへジャンプする。
それぞれのブロックはtrueもしくはfalseの場合の式を含んでいる。
訳注: Ordered and Not EqualのOrderedについて。
Ordered は2つのオペランドのうちどちらもQNANではないという事を意味する。
(QNANというのは多分浮動小数点数におけるQuiet NaNのことかと思われる。)
OrderedがあるということはUnorderedもあり、そちらは片方のオペランドがQNANかもしれないということを意味する。
fcmp one <ty> <op1> <op2> の場合(Ordered and Not Equalの場合)、両方のオペランドがQNANではなく、なおかつop1とop2が等しくないときにtrueを返す。
fcmp une <ty> <op1> <op2> の場合(Unordered and Not Equalの場合)、片方のオペランドがQNAN、もしくはop1とop2が等しくないときにtrueを返す。

then/elseブロックの実行が終われば、それら2つの枝分かれは、if/then/elseの後にあるコードを実行するために、ifcontブロックに合流する。
この例の場合だと、残ってるのは関数の呼び出し元に戻るということだけである。
ここで疑問が思い浮かぶ。
どっちの式の結果を返すかについてそのコードはどうやって知るのか?

この疑問への答えは、重要なSSA命令であるphi命令に関係する。
もし、SSAに関してよく知らなければ、Wikipediaの記事(http://en.wikipedia.org/wiki/Static_single_assignment_form)が良い導入になるし、SSAに対する他の様々な説明について好きな検索エンジンで探すことも出来る。
訳注: 日本語だと静的単一代入で検索すべし。

簡単に説明すると、phi命令の実行には、制御がどのブロックから来たのか覚えておく事が必要となる。
phi命令は、入ってきた制御ブロックに合致する値を受け取る。
この場合、制御が”then”ブロックから来た場合、phi命令はcalltmpの値を受け取る。
もし制御が”else”ブロックから来た場合、phi命令はcalltmp1の値を受け取る。

この時点で、あなたは多分こう考え始めるだろう。
「なんてこった!LLVMを使用するために、オレのシンプルでエレガントなフロントエンドを、SSA形式を生成するようにしなきゃいけないってことか!」
幸運にもそうではない。
もの凄く重要な理由が無い限り、SSA構築のアルゴリズムをフロントエンドに実装すべきではないと、我々は強くアドバイスする。
実際問題として、平均的なプログラミング言語のために書かれたコードのまわりで浮かんでいる、phiノードを必要とするかもしれない2種類の値がある。
(In practice, there are two sorts of values that float around in code written for your average imperative programming language that might need Phi nodes:)

1. ユーザ変数をまきこむコード。x = 1; x = x + 1;
2. この場合のphiノードのような、ASTの構造上暗黙的に存在する値。

このチュートリアルの第7章(変更可能な変数)では、1について深く説明する。
このような場合を制御するためにSSAを構築する必要がない、ということを今は単に信じて欲しい。
2については、1と同じく第7章で説明する技法かを使うか、簡単にphiノードを直接挿入する方法が選べる。
この場合、phiノードを生成するのは実に簡単なので、我々は直接挿入する方法を選択する。

よし、十分な動機と概観を得たところで、コードを生成しよう!

コメントを残す

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



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

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください