Control Flow Merging: A Compiler Transformation to Mitigate Branch Misprediction by Branch Elimination

Abstract

Modern superscalar processors have a high theoretical throughput, being capable of executing multiple instructions per clock cycle. In practice, however, this peak is rarely reached because data, structural, and control flow hazards can stall the pipeline and interrupt execution. Branch prediction is widely adopted in modern architectures to mitigate control flow hazards, yet even sophisticated predictors struggle to handle branches driven by random data. Each misprediction flushes speculative instructions and restarts execution on the correct path, making branch mispredictions a major performance bottleneck. Existing compiler solutions, such as outcome pre-computation and simple predication, are effective only for loop-invariant conditions or small side-effect-free branches. This work introduces Control Flow Merging (CFM), a compiler transformation that eliminates branches by converting control dependencies into data dependencies. CFM systematically replaces if and if-then-else regions with semantically equivalent, predicated instruction sequences, even when handling operations with side effects. Our work targets branch elimination at the compiler level by converting control flow dependencies into dataflow. We introduce the Control Flow Merging (CFM) pass for branch removal which replaces if and if-then-else regions with predicated instructions, while maintaining semantics and safety, even in the presence of instructions with side effects and implement it in LLVM 14. We also evaluate its impact on real-world benchmarks. Our experiments show that CFM can reduce branch mispredictions by up to 99 % and improve performance. Across the entire benchmark set, the pass delivers up to 53x speedup in the best case, and a geometric-mean speedup of 1.57×.