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 的范围内。

块偏差是一个提议的绝对指标，用于指示在函数执行期间对给定块的偏向或偏离。这个想法是，偏差可以单独使用，以指示一个块是相对热还是冷，或者比较两个块以指示一个块比另一个块更热还是更冷。

提议的计算涉及计算参考块频率，其中

此参考频率表示无偏图中块频率将是多少。

偏差是块频率与此参考块频率的比率。