消除分支：通过融合IR指令实现 (Eliminate Branches by Melding IR Instructions)

Branch mispredictions cause catastrophic performance penalties in modern processors, leading to performance loss. While hardware predictors and profile-guided techniques exist, data-dependent branches with irregular patterns remain challenging. Traditional if-conversion eliminates branches via software predication but faces limitations on architectures like x86. It often fails on paths containing memory instructions or incurs excessive instruction overhead by fully speculating large branch bodies. This paper presents Melding IR Instructions (MERIT), a compiler transformation that eliminates branches by aligning and melding similar operations from divergent paths at the IR instruction level. By observing that divergent paths often perform structurally similar operations with different operands, MERIT adapts sequence alignment to discover merging opportunities and employs safe operand-level guarding to ensure semantic correctness without hardware predication. Implemented as an LLVM pass and evaluated on 102 programs from four benchmark suites, MERIT achieves a geometric mean speedup of 10.9% with peak improvements of 32x compared to hardware branch predictor, demonstrating the effectiveness with reduced static instruction overhead.

翻译：分支预测失误在现代处理器中会造成灾难性的性能损失，导致性能下降。尽管存在硬件预测器和基于性能剖析的技术，但具有不规则模式的数据依赖型分支仍然具有挑战性。传统的if转换通过软件谓词化消除分支，但在x86等架构上存在局限性。它通常在包含内存指令的路径上失败，或者因完全推测大型分支体而产生过多的指令开销。本文提出IR指令融合（MERIT），这是一种编译器转换技术，通过在IR指令级别对齐和融合来自不同路径的相似操作来消除分支。通过观察到不同路径通常使用不同操作数执行结构相似的操作，MERIT采用序列对齐技术来发现融合机会，并采用安全的操作数级防护来确保语义正确性，而无需硬件谓词化。作为LLVM通道实现，并在来自四个基准测试套件的102个程序上进行评估，MERIT实现了10.9%的几何平均加速比，与硬件分支预测器相比峰值改进达到32倍，证明了其在降低静态指令开销方面的有效性。