基于图排序减少‘边距离’：编译器基本块跳转消除技术问询

可行的实现算法 #

• 深度优先遍历（DFS）排序：这是最易实现的方案。对控制流图做DFS遍历，生成的线性序列会天然让绝大多数前驱-后继块相邻——尤其是循环内部的块，DFS会深入循环体，自然把循环内的基本块紧凑排列，能直接消除大量循环内的跳转指令。
• 贪心权重排序：给不同类型的控制流边设置权重（比如循环内的边权重设为最高，高频执行的普通边次之），每次从当前块出发，选择权重最高的后继块放在序列下一位。这种方法实现简单，还能针对性优先处理你关注的循环边。
• 轮廓引导排序：如果能拿到程序运行时的轮廓数据（比如各边的执行次数），直接把执行次数最多的前驱-后继块排在一起，最大化消除跳转的收益，循环边因为执行次数通常远高于普通边，会被优先处理。

方案合理性 #

这个思路完全合理，属于编译器后端里基本块布局优化的核心方向。消除跳转指令不仅能减少分支指令的数量，还能降低分支预测失败的概率，同时提升指令缓存的命中率，对程序运行效率的提升很明显。对业余编译器来说，这类算法实现成本低（比如DFS排序几行代码就能搞定），收益却很直观，非常值得做。

优先处理循环边的技巧 #

• 先识别控制流图中的循环结构：通过支配树找到回边（即指向支配节点的边），以此标记出循环内的所有基本块。把每个循环作为一个独立的整体来排序，保证循环内的块紧凑排列，内部跳转自然就能被消除。
• 在贪心排序里给循环边设置更高优先级：遍历块的后继时，优先选择属于同一循环的块，再考虑其他后继。这样能确保循环内的前驱-后继对尽可能相邻，优先消除循环里的跳转。

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