技術

4.3. LLVM最適化パス

LLVMによるプログラミング言語の実装チュートリアル日本語訳
第4章 万華鏡: JITの追加と最適化のサポート
第3節 LLVM最適化パス

LLVMは、様々な種類の、様々なトレードオフを持つ、多くの最適化パスを提供する。
他のシステムと違って、LLVMは、ある最適化が全ての言語や全ての状況において正しい、という誤った考えは持っていない。
LLVMでは、コンパイラの実装者が、どの場合に、どういう順番で、どの最適化を使うかについて全て好きに選択することが可能となっている。

具体的な例として、LLVMは”モジュール全体(whole module)”のパス -コードの本文の全体に渡って最適化可能にするためのもの- をサポートする。
(しばしばそれはファイル全体である。ただしリンク時の場合は、プログラム全体の実体部分となりうる。)
また、他の関数を見ずに、一度にひとつの関数だけを処理するための”関数単位(per-function)”のパスをサポートする。
パスの詳しい情報や、パスがどうやって動作するかについては、ドキュメントの”LLVMのパス一欄“のページと、”パスの書き方“のページを参照。

万華鏡については、現状では、ユーザが関数を入力したときに、一度にひとつずつ、オンザフライで関数を生成している。
このような状況では、もの凄い最適化体験というものは得られないが、簡単で手っ取り早く似たようなことを行う方法はある。
つまり、ユーザーが関数を入力した際に、”関数単位(per-function)”の最適化をいくつか施そうというのである。
もし、スタティックな万華鏡コンパイラを作りたい場合は、ファイル全体が構文解析されるまで最適化の実行を遅らせなきゃいけないという点を除いて、現在我々が持っているコードがそのまま使える。
訳注: スタティックなコンパイラというのはJITコンパイラに対して普通のコンパイラの事を指してるものと思われる。

関数毎の最適化を実行するには、実行したいLLVM最適化をまとめて保持するためのFunctionPassManagerをセットアップする必要がある。
一度それを行えば、実行したい最適化を追加することが出来る。
以下のような感じである。

FunctionPassManager OurFPM(TheModule);

// オプティマイザのパイプラインを準備する。
// ターゲットがデータ構造をどうやって配置するかについての情報をまず登録する。
OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout()));
// GVN(Global value numbering, 大域値番号付け)のために、基本的なエイリアス解析のサポートを提供する。
OurFPM.add(createBasicAliasAnalysisPass());
// 簡単なピープホール最適化(覗き穴最適化)とビット操作最適化を行わせる。
OurFPM.add(createInstructionCombiningPass());
// 式の再結合。
OurFPM.add(createReassociatePass());
// 共通な部分式の除去。(CSE, 共通部分式除去)
OurFPM.add(createGVNPass());
// 制御フローグラフの簡約化。(到達不能なブロックを削除するなど)
OurFPM.add(createCFGSimplificationPass());

OurFPM.doInitialization();

// コード生成器から利用するためグローバル変数に格納。
TheFPM = &OurFPM;

// ここでメインのインタプリタのループを実行する。
MainLoop();

このコードは、FunctionPassManagerを”OurFPM”として定義している。
FunctionPassManagerは、それ自身の構築のためにModuleへのポインタを必要とする。
準備が終われば、あとは様々なLLVMのパスを一連のaddメソッドの呼び出しで追加出来る。
最初のパスは、いわば決まり文句であり、プログラムの中のデータ構造がどういう配置になってるかについて以降の最適化パスに知らせるためのパスである。
“TheExecutionEngine”変数はJITに関連していて、それについては次の節で述べる。

上の場合では、我々は4つの最適化パスを追加する事を選択した。
ここで選んだパスは、色んな種類のコードに対して役立つ非常に標準的な”クリーンアップ”最適化である。
ここではそれらの最適化が何を行ってるのかについて深く説明することはしないが、これはよい出発点であると思って欲しい。
訳注: ここでいうクリーンアップは野球用語(米国では4番打者のみを指す)で、”かなり効果的”というような意味かと思う。

PassManagerが準備できたら、それを使うようにする必要がある。
これについては、新しく関数が構築された後、呼び出し元に返る直前に行う。(FunctionAST::Codegenの中で)

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

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

  // 関数を最適化する。
  TheFPM->run(*TheFunction);

  return TheFunction;
}

見ての通り、そのまんまである。
FunctoinPassManagerは、インプレースでLLVM Function*を最適化して更新し、(うまくいけば)その関数本体に磨きをかける。
前節で行ったテストを再度やってみる。

ready> def test(x) (1+2+x)*(x+(1+2));
ready> Read function definition:
define double @test(double %x) {
entry:
        %addtmp = fadd double %x, 3.000000e+00
        %multmp = fmul double %addtmp, %addtmp
        ret double %multmp
}

期待してた通り、うまく最適化されたコードを得ることが出来た。
元の関数にあった複数の浮動小数点の加算は削減された。

LLVMは、色んな状況のなかで動作するいろんな種類の最適化を提供する。
様々なパスについてのドキュメントがいくつかあるが、未完全である。
Clangがどのようにパスを使ってるかについて見てみるのは、パスについてのアイデアを得る別の良い方法である。
“opt”ツールによって、コマンドラインからパスに対する実験を行うことができる。
訳注: optは、LLVMに付属するツールであり、LLVMのBitcodeを受け取り、コマンド引数で指定された最適化パスを実行して、Bitcodeを出力するためのもの。
LLVM IRをLLVMのVMに対するアセンブリ言語とすると、BitcodeはLLVMのVMに対するバイナリのようなもの。

これで、我々のコンパイラのフロントエンドはいい感じのコードを得た。
次はその実行に関して考えてみよう。

コメントを残す

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



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