LLVM の処理

これは LLVM のドキュメントを置き換えるものではなく、Julia で LLVM を使うときに気を付けるべき事項をまとめたものです。

Julia から LLVM へのインターフェースの概要

デフォルトで Julia は LLVM を動的リンクします。静的リンクするには USE_LLVM_SHLIB=0 としてください。

低水準形式の Julia AST を LLVM IR に変換する、あるいは直接実行するためのコードは src/ ディレクトリにあります:

ファイル 説明
builtins.c 組み込み関数
ccall.cpp ccall の変換
cgutils.cpp 変換ユーティリティ (特に配列とタプルへのアクセス)
codegen.cpp コード生成のトップレベル・パスのリスト・組み込み関数の変換
debuginfo.cpp JIT コードに対するデバッグ情報の追跡
disasm.cpp JIT コードのディスアセンブリとネイティブオブジェクトファイルの処理
gf.c 総称関数
intrinsics.cpp 組み込み命令の変換
llvm-simdloop.cpp @simd 用の独自 LLVM パス
sys.c IO とオペレーティングシステムユーティリティ関数

いくつかの .cpp はまとめて単一のオブジェクトにコンパイルされます。

組み込み命令 (intrinsic) と組み込み関数 (builtin) の違いは、組み込み関数はファーストクラスの関数なので他の Julia 関数と同様に使える点にあります。これに対して組み込み命令が操作できるのはボックス化されていないデータだけであり、そのため引数は静的に型が付いていなければなりません。

別名解析

Julia は現在 LLVM が提供する型ベースの別名解析を利用します。包含関係に関するコメントは src/codegen.cpp を static MDNode* で検索すると見つかります。

-O オプションを付けると LLVM が提供する基本的な別名解析が有効になります。

異なる LLVM のバージョンを使って Julia をビルドする

デフォルトの LLVM バージョンは deps/Versions.make で指定されます。この値を上書きするには、トップレベルディレクトリに Make.user というファイルを作って次の行を追加してください:

LLVM_VER = 6.0.1

LLVM リリースを表す数値以外にも、LLVM_VER = svn と指定すれば LLVM の最新開発バージョンを使ったビルドが可能です。

Make.user ファイルに LLVM_DEBUG = 1 または LLVM_DEBUG = Release を追加すれば、デバッグバージョンの LLVM ビルドを指定できます。LLVM_DEBUG = 1 では全く最適化されない LLVM ビルドが使われ、LLVM_DEBUG = Release では最適化された LLVM ビルドが使われます。用途によっては後者で十分であり、後者は前者に比べて非常に高速です。LLVM_DEBUG = Release を設定するときは LLVM_ASSERTIONS = 1 も設定して様々なパスに対する診断を有効にした方がよいでしょう。デフォルトでは LLVM_DEBUG = 1 だけがこのオプションを自動的に有効にします。

LLVM にオプションを渡す

LLVM にオプションを渡すには環境変数 JULIA_LLVM_ARGS を使います。bash の構文を使った例を示します:

LLVM の変形を個別にデバッグする

LLVM が行う IR の変形を他の Julia システムと切り離してデバッグできると便利な場合があります。例えば julia 内部で問題を再現するのに時間がかかる場合や、bugpoint などの LLVM のツールを活用したい場合です。システムイメージ全体に対する最適化されていない IR を取得するには、システムイメージのビルドで --output-unopt-bc unopt.bc オプションを使ってください。こうすると unopt.bc ファイルに最適化されていない IR が出力され、このファイルは通常のファイルと同じように LLVM ツールへ渡すことができます。libjulia は LLVM パスプラグインとして動作するので、LLVM ツールから libjulia を読み込めば現在の環境における Julia 特有のパスが利用可能になります。加えて -julia というメタパスが公開され、このパスは Julia が持つパスパイプラインを全て IR に対して実行します。例えば次のコマンドでシステムイメージを生成できます:

opt -load libjulia.so -julia -o opt.bc unopt.bc
llc -o sys.o opt.bc
cc -shared -o sys.so sys.o

このシステムイメージは julia から通常と同じ方法でロードできます。

--output-unopt-bc unopt.bc の代わりに --output-jit-bc jit.bc を使うと、JIT に渡された全ての IR のトレースを取得できます。これはシリアライズ不可能な状態を生成するなどの理由でシステムイメージの生成処理中に実行できないコードで有用です。ただし、このコマンドで生成される jit.bc にはシステムイメージのデータが含まれないので、そのままではシステムイメージとして使うことができません。

単一の Julia 関数に対する LLVM IR モジュールをダンプすることもできます。次のようにしてください:

fun, T = +, Tuple{Int,Int} # ダンプする関数で置き換える。
optimize = false
open("plus.ll", "w") do file
    println(file, InteractiveUtils._dump_function(fun, T, false, false, false, true,
                                                  :att, optimize, :default))
end

こうして作成される plus.ll は上述した最適化されていないシステムイメージ IR と同様に処理できます。

Julia に対する LLVM 最適化の改善

LLVM によるコード生成の改善は通常 Julia の低水準形式を LLVM のパスが扱いやすい形に変更するか、LLVM パスを改善することで行われます。

パスの改善を計画しているなら、LLVM developer policy を必ず読んでください。LLVM の opt ツールに入力できるコードを作って、対象のパスとコードを個別に調べるのがよいでしょう。つまり次の手順です:

  1. 対象の Julia コードを作成する。
  2. JULIA_LLVM_ARGS = -print-after-all で IR にダンプする。
  3. 対象のパスが実行される直前の IR を保存する。
  4. デバッグメタデータを削除し、TBAA メタデータを手で修正する。

最後のステップはかなりの手間です。何かいい方法があればぜひ教えてください。

jlcall 呼び出し規約

Julia は最適化されていないコードに対する汎用的な呼び出し規約を持ちます。次の形をした呼び出し規約です:

jl_value_t *any_unoptimized_call(jl_value_t *, jl_value_t **, int);

第一引数がボックス化された関数オブジェクト、第二引数がスタックに置かれた引数の配列、第三引数がその配列の長さを表します。この呼び出し規約に対して字面通りの低水準化を行うこともできますが、そうすると呼び出し側が SSA でなくなってしまって最適化 (GC ルートの配置など) が非常に難しくなってしまいます。そのため実際に生成されるのは次のようなコードです:

%bitcast = bitcast @any_unoptimized_call to %jl_value_t *(*)(%jl_value_t *, %jl_value_t *)
call cc 37 %jl_value_t *%bitcast(%jl_value_t *%arg1, %jl_value_t *%arg2)

cc 37 という特別な注釈は、この呼び出しが jlcall 呼び出し規約を本当に使っていることを表しています。こうすることでオプティマイザが活用する SSA 性が保持されます。後で GC ルートの配置処理がこの呼び出しをオリジナルの C ABI に低水準化します。この呼び出し規約の番号はコードでは JLCALL_F_CC という定数で表されます。この他に JLCALL_CC という呼び出し規約もあり、これは第一引数を省略した JLCALL_F_CC と等価です。

GC ルートの配置

GC ルート1の配置 (GC root placement) はパスパイプラインの後ろの方にある LLVM パスで行われます。GC ルートの配置をここまで遅らせることで、LLVM は GC ルートを必要とするコードの周りで踏み込んだ最適化が可能になり、さらに GC ルート/ストア操作の回数が減少します (LLVM は Julia の GC を関知しないために GC フレームに格納される値に対して処理を行うことができず、保守的に非常に限られた操作だけを行うためです)。例として次のエラーパスを考えます:

if some_condition()
    #= 何らかの変数を使う =#
    error("An error occurred")
end

定数畳み込みの結果、この条件が常に偽であることを LLVM が発見したとすれば、エラーブロックの削除が可能です。しかし GC ルートの配置が早い段階で行われていると、エラーブロックで使われる GC ルートのスロット、およびそこに保存される変数であって最後に使われるのがエラーブロックであるものは LLVM によって生きているとみなされてしまいます。GC ルートの低水準化を遅らせれば LLVM は通常の最適化 (定数畳み込みやデッドコードの削除) をそのまま行うことができ、どの値が GC に追跡されるのかを気にする必要は (それほど) ありません。

しかし GC ルートの配置を遅らせるには、

を特定しなければなりません。よって GC ルートの配置の目標はシンプルに表現できます:

制約「全てのセーフポイントにおいて、GC に追跡されていて生存している任意のポインタ (つまり、セーフポイントより後に利用されるパスが存在するポインタ) がいずれかの GC スロットに収まっている」を満たしながら、GC ルート/ストアの回数を最小化する。

表現

というわけで、最初の問題は GC によって追跡されるポインタとその利用を識別できるような IR 表現を選択することです。この表現は最適化を経た後でも効果を持たなくてはいけません。私たちが採用した設計では、これは LLVM が持つ三つの機能を使って実現されます:

独自アドレス空間を使うと、最適化を通じて保存される必要のある点に整数値でタグを付けることができます。コンパイラは元々のプログラムに存在しないアドレス空間が関わるキャストを挿入せず、ロードやストアといった演算でポインタのアドレス空間を変更してはいけないことになっています。そのためポインタが GC によって追跡されているために最適化で触れてはいけないことを表す注釈として独自アドレス空間を利用できます。この用途にメタデータは使えないことに注意してください。メタデータはプログラムの意味論を変更せずにいつでも削除できるとみなされるためです。GC に追跡されるポインタの特定に失敗すれば、プログラムの振る舞いは大きく変化します ──クラッシュするか、間違った答えを返すでしょう。

現在の Julia は四つの異なるアドレス空間を使っており、src/codegen_shared.cpp でアドレス空間の番号が定義されています:

不変条件

GC ルート配置パスはいくつかの不変条件を仮定します。これらの不変条件はフロントエンドが保証し、オプティマイザが保存しなければなりません。

まず、許されるアドレス空間のキャストは次の三つだけです:

次はアドレス空間をどのように使うかを考えます:

ロード/ストアと単純な関数呼び出しは Tracked と Derived のアドレス空間で明示的に許されます。jlcall 引数配列の要素はどんなときでも必ず Tracked アドレス空間にある値である必要があります (ABI により引数は jl_value_t* 型のポインタであることが要求されます)。リターン命令でも同様ですが、もしリターンの引数が構造体なら、それはどのアドレス空間にあっても構いません。アドレス空間 CalleeRooted のポインタは呼び出しに渡すときにだけ使用できます (このときオペランドには適切な型が付いているはずです)。

さらに、Tracked アドレス空間では getelementptr が無効化されます。引数のアドレスがそのまま返らない限り、この命令が返すポインタは GC スロットに格納できないので、Tracked アドレス空間に存在してはいけないポインタとなるためです。そういったポインタが必要なら、まず Derived アドレス空間に落としてください。

最後に、独自アドレス空間では inttoptr/ptrtoint 命令が無効化されます。この二つの命令が利用可能だと、ただの i64 値を GC が追跡できることになりますが、このとき GC に関連するポインタを特定できるという前述の要件が満たされなくなるので問題です。この不変条件は LLVM の「非整数ポインタ (non-integral pointer)」を使って実現されます。この機能は LLVM 5.0 で導入されたものであり、オプティマイザが inttoptr/ptrtoint 命令を生成する最適化を行わなくなります。なお JIT 時に inttoptr を使ってアドレス空間 0 の静的定数を挿入し、それを独自アドレス空間に "落とす" ことはできます。

ccall のサポート

ここまでの議論で触れてこなかった重要な話題の一つが ccall の取り扱いです。ccall には呼び出しの位置とスコープが一致しないという厄介な特徴があります。例えば次のコードを考えます:

A = randn(1024)
ccall(:foo, Cvoid, (Ptr{Float64},), A)

低水準化においてコンパイラは配列からポインタへの変換を挿入しますが、これによって配列値 A への参照はなくなります。しかし当然、ccall をしている間は配列 A への参照を生かしておく必要があります。この処理を理解するために、まず上のコードの低水準形式を示します:

return $(Expr(:foreigncall, :(:foo), Cvoid, svec(Ptr{Float64}), 0, :(:ccall),
              Expr(:foreigncall, :(:jl_array_ptr),
                   Ptr{Float64}, svec(Any), 0, :(:ccall), :(A)),
              :(A)))

最後の :(A) は低水準化で挿入される追加引数であり、この ccall の間に生かしておくべき Julia レベルの値をコードジェネレータに伝えます。この情報は IR のレベルで「オペランドバンドル (operand bundle)」として表現されます。オペランドバンドルは呼び出し側に関連付けられる (事実上) 偽の使用であり、IR のレベルで次のような形をしています:

call void inttoptr (i64 ... to void (double*)*)(double* %5) [ "jl_roots"(%jl_value_t addrspace(10)* %A) ]

GC ルート配置パスは jl_roots というオペランドバンドルを通常のオペランドと同じように扱います。ただし最後のステップとして、命令選択の邪魔にならないよう GC ルートを挿入した後にオペランドバンドルを削除します。

pointer_from_objref のサポート

pointer_from_objref を使うと GC ルートをユーザーから明示的に操作できるので、この関数は特別です。そのときアドレス空間 10 から 0 へのキャストを行うので、上述の不変条件を考えると、この関数は正当ではありません。しかしこの関数が便利になる状況があるので、特別な組み込み命令として提供されます:

declared %jl_value_t *julia.pointer_from_objref(%jl_value_t addrspace(10)*)

この命令は GC ルートの低水準化の後に対応するアドレス空間のキャストに低水準化されます。ただし組み込み命令 pointer_from_objref でポインタを取得する値がルートされていることを保証するのは呼び出し側の責任です。さらに pointer_from_objref は値の使用とみなされないので、GC ルート配置パスはこの関数に対してルートを提供しません。そのため、この関数を使った外部からのルート化は対象の値がシステムから追跡されている間に行われなければなりません。言い換えると、pointer_from_objref の返り値を使ってグローバルなルートを構築するのは間違っています ──オプティマイザがその値を削除する可能性があるためです。

使われていない値を生存させる

使われていることがコンパイラから見えないオブジェクトを生存させておく必要がある状況が存在します。例えばオブジェクトのメモリ表現を直接操作する低水準コードや C コードとやり取りを行うコードです。これが行えるように、Julia は次の組み込み命令を LLVM のレベルで提供します (名前の llvm. は token 型を使うために必要です):

token @llvm.julia.gc_preserve_begin(...)
void @llvm.julia.gc_preserve_end(token)

この命令の意味論は「ある gc_preserve_begin に支配され、対応する gc_preserve_end (gc_preserve_begin が返すトークンに対する gc_preserve_end) に支配されない任意のセーフポイントにおいて、gc_preserve_begin の引数に渡された値は生存したままとなる」です。gc_preserve_begin は渡される値は通常の使用としてカウントされるので、値の寿命を決める通常の意味論がそこまでの生存を保証することに注意してください。

  1. 訳注: 「GC ルート」の意味は Julia の組み込みの章を参照。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。