Machine Code Sinking后汇编代码基本块顺序变更原因探究

我是编译器与LLVM新手，若问题或思路有不当之处请见谅。

初始机器代码 #

bb.0.entry:
  successors: %bb.1(0x50000000), %bb.5(0x30000000); %bb.1(62.50%), %bb.5(37.50%)
  // Omit...

bb.1.for.body.i79.preheader:
; predecessors: %bb.0
  successors: %bb.2(0x80000000); %bb.2(100.00%)
  // Omit...

bb.2.for.body.i79:
; predecessors: %bb.1, %bb.4
  successors: %bb.3(0x40000000), %bb.4(0x40000000); %bb.3(50.00%), %bb.4(50.00%)
  // Omit...

bb.3.switch.lookup:
; predecessors: %bb.2
  successors: %bb.4(0x80000000); %bb.4(100.00%)
  // Omit..

bb.4.for.inc.i96:
; predecessors: %bb.2, %bb.3
  successors: %bb.5(0x04000000), %bb.2(0x7c000000); %bb.5(3.12%), %bb.2(96.88%)
  // Omit...

...

此时生成asm的块顺序为：

bb.0
bb.1
bb.2
bb.3
bb.4

Machine Code Sinking后的变化 #

执行Machine Code Sinking后，bb.2与bb.4之间的临界边被拆分：*** Splitting critical edge: %bb.2 -- %bb.78 -- %bb.4

得到机器代码：

bb.0.entry:
  successors: %bb.1(0x50000000), %bb.5(0x30000000); %bb.1(62.50%), %bb.5(37.50%)
  // Omit...

bb.1.for.body.i79.preheader:
; predecessors: %bb.0
  successors: %bb.2(0x80000000); %bb.2(100.00%)
  // Omit...

bb.2.for.body.i79:
; predecessors: %bb.1, %bb.4
  successors: %bb.3(0x40000000), %bb.78(0x40000000); %bb.3(50.00%), %bb.78(50.00%)
  // Omit...

bb.78:
; predecessors: %bb.2
  successors: %bb.4(0x80000000); %bb.4(100.00%)
  // Omit..

bb.3.switch.lookup:
; predecessors: %bb.2
  successors: %bb.4(0x80000000); %bb.4(100.00%)
  // Omit..

bb.4.for.inc.i96:
; predecessors: %bb.3, %bb.78
  successors: %bb.5(0x04000000), %bb.2(0x7c000000); %bb.5(3.12%), %bb.2(96.88%)
  // Omit...

此时生成asm的块顺序变为：

bb.0
bb.1
bb.3
bb.4
bb.2
bb.78

疑惑与问题 #

bb.1到bb.2的控制流仍为100%，但汇编顺序却改变了。希望了解：

1. 基本块顺序的决定逻辑
2. LLVM中该逻辑的源码文件位置

若我的理解或思路有误，请指出，谢谢！

解答 #

基本块排序的核心逻辑

LLVM的汇编生成阶段，基本块排序主要由MachineBlockPlacement pass负责，核心目标是优化指令缓存（ICache）命中率、减少分支预测错误，提升程序执行效率。排序策略并非只看单一的控制流概率，而是综合以下因素：

• 热路径优先：基于profile数据（或静态预测）将执行频率高的块放在一起
• 分支概率与方向：将最可能的后继块放在当前块的直接后继位置（即“fall-through”，无需跳转）
• 循环结构优化：循环体内部块尽量紧凑排列，减少跨块跳转
• 临界边拆分后的影响：拆分临界边新增的块（如bb.78）会改变控制流图的结构，导致排序算法重新评估块之间的关联度。在你的案例中，bb.2的后继拆分为bb.3和bb.78，而bb.3和bb.4的关联更紧密（bb.3直接跳转到bb.4），同时bb.4又循环回bb.2，排序算法可能优先将bb.3、bb.4放在前面，让高频的循环跳转更高效。

LLVM源码位置

• 核心实现位于llvm/lib/CodeGen/MachineBlockPlacement.cpp
• 相关的辅助逻辑（如概率计算、块权重评估）在llvm/lib/Analysis/BlockFrequencyInfo.cpp和llvm/lib/CodeGen/MachineBlockPlacementStats.cpp中
• 排序策略的具体配置和入口可查看llvm/lib/CodeGen/Passes.cpp中对MachineBlockPlacement pass的注册代码

内容的提问来源于stack exchange，提问作者Jinlock