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

代码块偏差是一种建议的绝对度量，用于指示在函数执行期间对给定代码块的偏向或偏离。其思想是，偏差可以单独使用来指示代码块是相对热还是冷，或者比较两个代码块以指示一个比另一个更热或更冷。

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

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

偏差是代码块频率与该参考代码块频率的比率。