LLVM ブロック頻度用語集¶
はじめに¶
ブロック頻度は、異なる基本ブロックの相対的な頻度を推定するための指標です。このドキュメントでは、BlockFrequencyInfo および MachineBlockFrequencyInfo 分析パスが使用している用語について説明します。
分岐確率¶
複数後継者がいるブロックには、各送信エッジに関連付けられた確率があります。これを分岐確率と呼びます。特定のブロックの場合、その送信分岐確率の合計は 1.0 である必要があります。
分岐重み¶
各エッジに小数点を格納するのではなく、整数重み格納します。重みは、特定の前置ブロックの他のエッジと相対的です。特定のエッジに関連付けられた分岐確率は、そのエッジの重みを前置ブロックの送信エッジの重みの合計で割ったものです。
たとえば、この IR を検討してください
define void @foo() {
; ...
A:
br i1 %cond, label %B, label %C, !prof !0
; ...
}
!0 = !{!"branch_weights", i32 7, i32 8}
およびこの単純なグラフ表現
A -> B (edge-weight: 7)
A -> C (edge-weight: 8)
ブロック A からブロック B へ分岐する確率は 7/15 であり、ブロック A からブロック C へ分岐する確率は 8/15 です。
分岐重量 IR 表現の詳細については、LLVM 分岐重量メタデータ を参照してください。
ブロック頻度¶
ブロック頻度は、ブロックの実行回数を表す相対的な指標です。ブロック頻度をエントリブロック頻度で割ったものが、関数へのエントリごとにブロックが実行される期待回数です。
ブロック頻度は、BlockFrequencyInfo および MachineBlockFrequencyInfo 分析パスの主な出力です。
実装: DAG のシリーズ¶
ブロック頻度の計算の実装では、各ループが下から上へ、後方エッジを無視して、つまり DAG として分析されます。各ループが処理されると、親のループ (または関数の) DAG 分析の擬似ノードとして機能するようにパッケージ化されます。
ブロック質量¶
各 DAG に対して、エントリノードに質量 UINT64_MAX が割り当てられ、質量は分岐の重みに応じて後続に分散されます。ブロック質量は、UINT64_MAX が 1.0 を表し、0 が 0.0 より少しだけ大きい数を表す固定小数点表現を使用します。
質量が完全に分散された後、DAG の任意のカットで出口ノードと入口ノードを分離すると、カットエッジによって継承されたノードのブロック質量の和は UINT64_MAX にならなければなりません。言い換えると、質量は DAG を通して「落下」するときに保存されます。
関数の基本ブロックグラフが DAG である場合、ブロック質量は有効なブロック周波数です。これらは、しかし、ダウンストリームユーザーが最大値に達することなくブロック周波数を一緒に追加することに依存するため、実際にはうまく機能しません。
ループスケール¶
ループスケールは、ループがエントリごとに何回反復するかを示すメトリックです。質量がループの DAG に分散されるとき、（それ以外は無視される）バックエッジ質量が収集されます。このバックエッジ質量は出口周波数、つまりループスケールを計算するために使用されます。
実装: 質量とスケールから周波数を得る¶
DAG の完全なシリーズを解析した後、各ブロックには質量（任意の場合、その包含ループに対してローカル）があり、各ループ疑似ノードにはループスケールとそれ自身の質量（親の DAG から)があります。
これらの質量とループスケールを一緒に掛け算することで、最初の周波数割り当て（エントリ周波数は 1.0）を得ることができます。特定のブロックの周波数は、その質量、包含ループの疑似ノードの質量、包含ループのループスケールの積です。
ダウンストリームユーザーは整数（浮動小数点ではない）を必要としているため、この最初の周波数割り当ては必要に応じて uint64_t の範囲にシフトされます。
ブロックバイアス¶
ブロックバイアスは、関数の実行中に特定のブロックに向かうまたは離れるバイアスを示す提案された絶対メトリックです。バイアスは、独立してブロックが比較的ホットまたはコールドであるかどうかを示したり、2 つのブロックを比較してどちらが他方よりホットまたはコールドであるかを示したりするために使用できるという考えです。
提案されている計算には参照ブロック周波数の計算が含まれ、ここで
すべてに分岐の重みが 1 であると想定され（つまり、すべての分岐確率分布が偶数である）
ループスケールは無視されます。
この参照周波数は、バイアスのないグラフにおけるブロック周波数が何になるかを表しています。
バイアスは、ブロック周波数とこの参照ブロック周波数の比率です。