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

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×.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science & Applications

Department dc:contributor.department

Computer Science and#38; Applications

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2025

Author dc:creator

• Ramachandra Sharma, Srinivasan

Chair dc:contributor.committeechair

• Sundararajah, Kirshanthan

Committee members dc:contributor.committeemember

• Gulzar, Muhammad Ali
• Jian, Xun

• Control Flow Merging
• Compiler Optimization

Statement dc:rights

• Creative Commons Attribution 4.0 International

Licence dc:rights.uri

• http://creativecommons.org/licenses/by/4.0/

Language dc:language.iso

en

Dc Identifier Other

vt_gsexam:44400

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/136935