関数のインライン化に対するTruffleのアプローチ

Truffleでは、そのフレームワークで構築されたすべての言語に自動インライン化が提供されます。20.2.0リリース以降、インライン化に対する新しいアプローチが導入されました。このドキュメントでは、新しいアプローチの仕組みについて説明し、従来のインライン化アプローチと比較して、新しいアプローチで設計する意義を示します。

インライン化

インライン化は、関数のコールをその関数の本体に置き換えるプロセスです。これにより、コールのオーバーヘッドが解消されますが、より重要なことは、コンパイラの以降のフェーズで最適化の機会が増えることです。このプロセスの短所は、関数がインライン化されるたびにコンパイルのサイズが増加することです。コンパイル・ユニットが大きすぎると、最適化が困難になり、コードをインストールするためのメモリーが限られます。

このため、インライン化する関数を選択することは、関数をインライン化することで得られる利点と、コンパイル・ユニットのサイズの増加による負荷との間の難しいトレードオフになります。

Truffleの従来のインライン化

Truffleには、かなり前からインライン化するためのアプローチがありました。残念ながら、この初期のアプローチには複数の問題がありました。主な問題の1つは、コール・ターゲットのサイズを概算する際にコール・ターゲット内のTruffle ASTノードの数に依存していたことです。

ASTノードは、1つのASTノードが生成するコードの量が保証されないため、コール・ターゲットの実際のコード・サイズに対して非常に貧弱なプロキシです。たとえば、2つの整数を追加するために特殊化された追加ノードは、同じノードが整数、倍精度浮動小数点数および文字列(異なるノードおよび異なる言語のノードは言うに及ばず)を追加するために特殊化された場合と比較して、生成されるコードがはるかに少なくなります。これにより、すべてのTruffle言語で確実に機能する単一のインライン化アプローチを使用できなくなりました。

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

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

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

これを行うには、すべての候補コール・ターゲットに対して部分評価を実行した後で、インライン化を決定します(部分評価を実行する前に決定した従来のインライン化とは対照的です)。実行される部分評価の量とインライン化される量のどちらも、予算の概念によって制御されます。これらはそれぞれ探索予算とインライン化予算であり、どちらもGraalノード数で表されます。

このアプローチの短所は、最終的にはインライン化しないことにしたコール・ターゲットに対しても部分評価を実行する必要があることです。これにより、従来のインライン化と比較して、平均コンパイル時間が大幅に増加します(約10%)。

インライン化の監視および影響

インライナは、内部コール・ツリーを保持して、ターゲットに対する個々のコールの状態と、行われたインライン化の決定を追跡します。次の各項では、コール・ツリー内のコールの状態、およびコンパイル中に行われた決定を確認する方法について説明します。

コール・ツリーの状態

インライン・コール・ツリーのノードは、特定のターゲットに対するコールを表します。つまり、あるターゲットが別のターゲットを2回コールした場合、同じコール・ターゲットであっても、これは2つのノードとして表示されます。

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

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

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ノードの数を制御します。この予算を増やすと、インライン化される候補が増える可能性があり、その結果、コンパイル・ユニットが大きくなります。これにより、グラフが大きくなるほど最適化に時間がかかるため、特に部分評価後のフェーズでコンパイルの速度が低下する可能性があります。また、パフォーマンスが向上(コールの削除、最適化フェーズの全体像の把握)することも、パフォーマンスが低下(グラフが大きすぎて正しく最適化できない場合や、まったくコンパイルできない場合など)することもあります。