Truffle における関数インライン化のアプローチ

Truffle は、フレームワークで構築されたすべての言語に対して自動インライン化を提供します。20.2.0 リリース以降、新しいインライン化アプローチが導入されました。このドキュメントでは、新しいアプローチがどのように機能するか、従来のアプローチと比較して、新しいアプローチのために行われた設計上の選択について説明します。

インライン化 #

インライン化とは、関数呼び出しをその関数の本体に置き換えるプロセスです。これにより、呼び出しのオーバーヘッドが取り除かれるだけでなく、コンパイラの後の段階でより多くの最適化の機会が開かれます。このプロセスの欠点は、インライン化される関数ごとにコンパイルのサイズが大きくなることです。過度に大きなコンパイル単位は最適化が難しく、コードをインストールするためのメモリには限りがあります。

これらのすべてを考慮すると、どの関数をインライン化するかを選択することは、関数をインライン化することによって期待される利点と、コンパイル単位のサイズ増加のコストとの間の微妙なトレードオフになります。

Truffle の従来型インライン化 #

Truffle には、かなり長い間インライン化のアプローチがありました。残念ながら、この初期のアプローチには複数の問題があり、主な問題は、呼び出しターゲットのサイズを近似するために呼び出しターゲットの Truffle AST ノードの数に依存していたことでした。

AST ノードは、1 つの AST ノードがどのくらいのコードを生成するか保証がないため、呼び出しターゲットの実際のコードサイズの非常に貧弱なプロキシです。たとえば、2 つの整数を加算するために特殊化された加算ノードは、整数、double、および文字列を加算するために特殊化された場合（異なるノードや異なる言語のノードは言うまでもなく）よりも大幅に少ないコードを生成します。これにより、すべての Truffle 言語で確実に機能する単一のインライン化アプローチを持つことが不可能になりました。

従来型インライン化の注目すべき点の 1 つは、AST からの情報のみを使用するため、インライン化の決定は部分評価が開始される前に行われることです。これは、インライン化することに決定した呼び出しターゲットのみを部分的に評価することを意味します。このアプローチの利点は、インライン化されない呼び出しターゲットの部分評価に時間が費やされないことです。一方、これにより、インライナーによる不十分な決定に起因するコンパイルの問題が頻繁に発生します。たとえば、結果として得られるコンパイル単位が大きすぎてコンパイルできないなどです。

言語に依存しないインライン化 #

新しいインライン化アプローチの主な設計目標は、部分評価後の Graal ノード（コンパイラノード）の数を呼び出しターゲットのサイズのプロキシとして使用することです。部分評価により AST のすべての抽象化が削除され、呼び出しターゲットが実際に実行する低レベルの命令にはるかに近いグラフになるため、これははるかに優れたサイズプロキシです。これにより、呼び出しターゲットをインライン化するかどうかを決定する際により正確なコストモデルが得られ、AST が持つ言語固有の情報の多くが削除されます（したがって、言語に依存しないインライン化という名前）。

これは、すべての候補呼び出しターゲットに対して部分評価を実行し、その後（部分評価を行う前に決定を下した従来のインライン化とは対照的に）インライン化の決定を行うことで実現されます。部分評価を行う量と、インライン化する量の両方が、予算という概念によって制御されます。これらは、「探索予算」と「インライン化予算」であり、どちらも Graal ノード数で表されます。

このアプローチの欠点は、最終的にインライン化しないと決定した呼び出しターゲットに対しても部分評価を行う必要があることです。これにより、従来型インライン化と比較して、平均コンパイル時間が大幅に増加します（約 10％）。

インライン化の観察と影響 #

インライナーは、ターゲットへの個々の呼び出しの状態と、行われたインライン化の決定を追跡するために、内部呼び出しツリーを保持します。次のセクションでは、呼び出しツリー内の呼び出しが取りうる状態と、コンパイル中に行われた決定をどのように見つけるかを説明します。

呼び出しツリーの状態 #

インラインノード呼び出しツリーは、特定のターゲットへの呼び出しを表します。これは、あるターゲットが別のターゲットを 2 回呼び出す場合、同じ呼び出しターゲットであっても、2 つのノードとして表示されることを意味します。

各ノードは、ここで説明する 6 つの状態のいずれかになります。

インライン化済み - この状態は、呼び出しがインライン化されたことを意味します。当初、コンパイルのルートのみがこの状態になります。これは、暗黙的に「インライン化」（つまり、コンパイル単位の一部）されるためです。
カットオフ - この状態は、呼び出しターゲットが部分評価されなかったため、インライン化の対象にすらならなかったことを意味します。これは通常、インライナーが探索予算の制限に達したことが原因です。
展開済み - この状態は、呼び出しターゲットが部分的に評価された（したがって、インライン化の対象と見なされた）が、インライン化しないという決定が下されたことを意味します。これは、インライン化予算の制限、またはターゲットがインライン化するにはコストが高すぎると見なされたことが原因である可能性があります（たとえば、「カットオフ」呼び出しが複数ある小さなターゲットをインライン化すると、コンパイル単位への呼び出しが増えるだけです）。
削除済み - この状態は、この呼び出しが AST に存在するが、部分評価によって呼び出しが削除されたことを意味します。これは、事前に決定を下し、このような状況に気付く方法がなかった従来型インライン化に対する利点です。
間接 - この状態は間接呼び出しを示します。間接呼び出しはインライン化できません。
中止 - この状態は非常にまれであり、パフォーマンスの問題と見なされます。これは、ターゲットの部分評価が BailoutException になったこと、つまり、正常に完了できなかったことを意味します。これは、特定のターゲットに何らかの問題があることを意味しますが、コンパイル全体を終了するのではなく、その呼び出しをインライン化できないものとして扱います。

インライン化の決定のトレース #

Truffle は、コンパイル中に、多くの付随データを含む、呼び出しツリーの最終状態をトレースするためのエンジンオプションを提供します。このオプションは TraceInlining であり、言語ランチャーに --engine.TraceInlining=true を追加したり、ゲスト言語（Truffle で実装された言語）を実行する通常の Java プログラムを実行している場合はコマンドラインに -Dpolyglot.engine.TraceInlining=true を追加したり、エンジンに対してオプションを明示的に設定するなど、通常の方法で設定できます。

JavaScript 関数の TraceInlining の出力例を次に示します。

[engine] inline start     M.CollidePolygons                                           |call diff        0.00 |Recursion Depth      0 |Explore/inline ratio     1.07 |IR Nodes        27149 |Frequency        1.00 |Truffle Callees     14 |Forced          false |Depth               0
[engine] Inlined            M.FindMaxSeparation <opt>                                 |call diff       -8.99 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes         4617 |Frequency        1.00 |Truffle Callees      7 |Forced          false |Depth               1
[engine] Inlined              parseInt <opt>                                          |call diff       -1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          111 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               2
[engine] Inlined              M.EdgeSeparation                                        |call diff       -3.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes         4097 |Frequency        1.00 |Truffle Callees      2 |Forced          false |Depth               2
[engine] Inlined                parseInt <opt>                                        |call diff       -1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          111 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               3
[engine] Inlined                parseInt <opt>                                        |call diff       -1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          111 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               3
[engine] Inlined              parseInt <opt>                                          |call diff       -1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          111 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               2
[engine] Expanded             M.EdgeSeparation                                        |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes         4097 |Frequency        1.00 |Truffle Callees      2 |Forced          false |Depth               2
[engine] Inlined              parseInt <opt>                                          |call diff       -1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          111 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               2
[engine] Inlined              M.EdgeSeparation                                        |call diff       -3.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes         4097 |Frequency        1.00 |Truffle Callees      2 |Forced          false |Depth               2
[engine] Inlined                parseInt <opt>                                        |call diff       -1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          111 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               3
[engine] Inlined                parseInt <opt>                                        |call diff       -1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          111 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               3
[engine] Cutoff               M.EdgeSeparation                                        |call diff        0.01 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        0.01 |Truffle Callees      2 |Forced          false |Depth               2
[engine] Cutoff             M.FindMaxSeparation <opt>                                 |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      7 |Forced          false |Depth               1
[engine] Cutoff             M.FindIncidentEdge <opt>                                  |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees     19 |Forced          false |Depth               1
[engine] Cutoff             parseInt <opt>                                            |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      0 |Forced           true |Depth               1
[engine] Cutoff             parseInt <opt>                                            |call diff        0.98 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        0.98 |Truffle Callees      0 |Forced           true |Depth               1
[engine] Cutoff             A.Set <split-16abdeb5>                                    |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      0 |Forced          false |Depth               1
[engine] Cutoff             A.Normalize <split-866f516>                               |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      1 |Forced          false |Depth               1
[engine] Cutoff             A.Set <split-1f7fe4ae>                                    |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      0 |Forced          false |Depth               1
[engine] Cutoff             M.ClipSegmentToLine                                       |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      2 |Forced          false |Depth               1
[engine] Cutoff             M.ClipSegmentToLine                                       |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      2 |Forced          false |Depth               1
[engine] Cutoff             A.SetV <split-7c14e725>                                   |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      0 |Forced          false |Depth               1
[engine] Cutoff             A.SetV <split-6029dec7>                                   |call diff        1.00 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes            0 |Frequency        1.00 |Truffle Callees      0 |Forced          false |Depth               1
[engine] Inlined            L.Set <split-2ef5921d>                                    |call diff       -3.97 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          205 |Frequency        1.98 |Truffle Callees      1 |Forced          false |Depth               1
[engine] Inlined              set <split-969378b>                                     |call diff       -1.98 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          716 |Frequency        1.98 |Truffle Callees      0 |Forced          false |Depth               2
[engine] Inlined            set                                                       |call diff       -1.98 |Recursion Depth      0 |Explore/inline ratio      NaN |IR Nodes          381 |Frequency        1.98 |Truffle Callees      0 |Forced          false |Depth               1
[engine] inline done      M.CollidePolygons                                           |call diff        0.00 |Recursion Depth      0 |Explore/inline ratio     1.07 |IR Nodes        27149 |Frequency        1.00 |Truffle Callees     14 |Forced          false |Depth               0

インライン化の決定のダンプ #

トレースを介してテキスト形式で提供されるのと同じ情報は、IGV ダンプでも利用できます。グラフは、Call Tree サブグループの Graal Graphs グループの一部です。グラフは、インライン化の前後の呼び出しツリーの状態を示しています。

インライン化予算の制御 #

注: インライン化関連の予算のデフォルト値は、コンパイル時間、パフォーマンス、およびコンパイラの安定性を考慮して慎重に選択されています。これらのパラメータを変更すると、これらすべてに影響を与える可能性があります。

言語に依存しないインライン化には、コンパイラが実行できる探索量とインライン化量を制御するための 2 つのオプションが用意されています。これらはそれぞれ、InliningExpansionBudget と InliningInliningBudget です。どちらも Graal ノード数で表されます。これらは、他のエンジンオプションと同様に制御できます（つまり、「インライン化の決定のトレース」セクションで説明した方法と同じ方法）。

InliningExpansionBudget は、インライナーが候補の部分評価を停止する時点を制御します。したがって、この予算を増やすと、平均コンパイル時間（特に部分評価に費やされる時間）に非常に悪影響を与える可能性がありますが、インライン化の候補が増える可能性があります。

InliningInliningBudget は、インライン化の結果として、コンパイルユニットが持つことを許容される Graal ノードの数を制御します。この予算を増やすと、より多くの候補がインライン化される可能性が高くなり、結果としてコンパイルユニットが大きくなります。これは、特に部分評価後のフェーズでコンパイルを遅くする可能性があります。これは、グラフが大きいほど最適化に時間がかかるためです。パフォーマンスを向上させる可能性（呼び出しの削除、最適化フェーズがより大きな全体像を把握できる）もあれば、パフォーマンスを低下させる可能性（グラフが大きすぎて正しく最適化できない、またはまったくコンパイルできないなど）もあります。