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，入口節點會被賦予 UINT64_MAX 的質量，並且質量會根據分支權重分配給後繼節點。區塊質量使用定點表示法，其中 UINT64_MAX 表示 1.0，而 0 表示一個略大於 0.0 的數字。

在質量完全分配後，在任何將出口節點與入口節點分開的 DAG 切割中，由切割邊緣繼承的節點的區塊質量總和應等於 UINT64_MAX。換句話說，質量在「落下」DAG 時是守恆的。

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

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

在分析完完整的 DAG 序列後，每個區塊都有一個質量（如果有的話，則在其包含的迴圈中是局部的），並且每個迴圈偽節點都有一個迴圈規模及其自身的質量（來自其父 DAG）。

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

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

區塊偏差是一個建議的*絕對*指標，用於指示函數執行期間對給定區塊的偏向或偏離。這個想法是，偏差可以單獨使用來指示區塊是相對熱還是冷，或者比較兩個區塊以指示一個比另一個更熱或更冷。

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

此參考頻率表示無偏差圖中的區塊頻率。

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