LLVM 區塊頻率術語¶

簡介 ¶

區塊頻率是用於估計不同基本區塊相對頻率的指標。本文檔描述了 BlockFrequencyInfo 和 MachineBlockFrequencyInfo 分析pass所使用的術語。

具有多個後繼區塊的區塊，其每個外向邊都關聯有機率。這些稱為分支機率。對於給定的區塊，其外向分支機率的總和應為 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 分析pass的主要輸出。

區塊頻率計算的實作分析每個迴圈，由下而上，忽略回邊；也就是說，作為 DAG。在處理完每個迴圈後，它會被打包起來，在其父迴圈（或函式）的 DAG 分析中充當偽節點。

對於每個 DAG，進入節點被分配質量 UINT64_MAX，並且質量根據分支權重分佈到後繼節點。區塊質量使用定點表示法，其中 UINT64_MAX 表示 1.0，而 0 表示略高於 0.0 的數字。

在質量完全分佈後，在 DAG 的任何切割中，該切割將出口節點與進入節點分開，被切割邊所繼承的節點的區塊質量總和應等於 UINT64_MAX。換句話說，質量在“落入” DAG 時是守恆的。

如果函式的基本區塊圖是 DAG，則區塊質量是有效的區塊頻率。然而，這在實務中效果不佳，因為下游使用者依賴於將區塊頻率加總在一起而不會達到最大值。

迴圈尺度是一個指標，指示每個進入點迴圈迭代多少次。當質量分佈在迴圈的 DAG 中時，會收集（否則被忽略的）回邊質量。此回邊質量用於計算出口頻率，進而計算迴圈尺度。

在分析完整的一系列 DAG 後，每個區塊都有一個質量（如果有的話，則為其包含迴圈的本地質量），並且每個迴圈偽節點都有一個迴圈尺度及其自身的質量（來自其父 DAG）。

我們可以通過將這些質量和迴圈尺度相乘，獲得初始頻率分配（進入頻率為 1.0）。給定區塊的頻率是其質量、包含迴圈的偽節點的質量以及包含迴圈的迴圈尺度的乘積。

由於下游使用者需要整數（而不是浮點數），因此此初始頻率分配會根據需要移位到 uint64_t 的範圍內。

區塊偏差是一種擬議的絕對指標，用於指示在函式執行期間，相對於給定區塊的偏差程度。其概念是偏差可以單獨使用，以指示區塊是相對熱門還是冷門，或者比較兩個區塊以指示一個區塊比另一個區塊更熱門還是更冷門。

擬議的計算涉及計算參考區塊頻率，其中

此參考頻率表示在無偏差圖形中區塊頻率會是多少。

偏差是區塊頻率與此參考區塊頻率的比率。