関数のインライン化に対する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つの状態のいずれかになります:
- Inlined - この状態は、コールがインライン化されたことを意味します。最初は、コンパイルのルートのみが暗黙的にインライン化されているため(つまり、コンパイル・ユニットの一部であるため)、この状態になっています。
- Cutoff - この状態は、コール・ターゲットが部分的に評価されなかったため、インライン化の対象にもならなかったことを意味します。これは通常、インライナが探索予算の制限に達したことが原因です。
- Expanded - この状態は、コール・ターゲットが部分的に評価された(したがって、インライン化の対象になった)が、インライン化しないことにしたことを意味します。これは、インライン化の予算制限、またはターゲットをインライン化するコストが高すぎるとみなされたことが原因である可能性があります(たとえば、複数の送信Cutoffコールで小さいターゲットをインライン化すると、単に、コンパイル・ユニットに導入されるコールが増加します)。
- Removed - この状態は、このコールがASTに存在するが、部分評価によってコールが削除されたことを意味します。これは、事前に決定し、そのような状況に気付く方法がなかった従来のインライン化よりも優れています。
- Indirect - この状態は間接コールを示します。間接コールはインライン化できません。
- BailedOut - この状態は非常にまれであり、パフォーマンスの問題とみなされます。これは、ターゲットの部分評価が
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ノードの数を制御します。この予算を増やすと、インライン化される候補が増える可能性があり、その結果、コンパイル・ユニットが大きくなります。これにより、グラフが大きくなるほど最適化に時間がかかるため、特に部分評価後のフェーズでコンパイルの速度が低下する可能性があります。また、パフォーマンスが向上(コールの削除、最適化フェーズの全体像の把握)することも、パフォーマンスが低下(グラフが大きすぎて正しく最適化できない場合や、まったくコンパイルできない場合など)することもあります。