Srinivasan Ramachandra Sharma's MS Defense on Monday 06/23 at 11.00 AM in GP 4001
All are invited to the MS Thesis Defense of Srinivasan Ramachandra Sharma on Monday 06/23 at 11.00 AM in 4001 Gilbert Place and in my Zoom room https://virginiatech.zoom.us/my/kirshanthans Feel free to invite others as well. Title: 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 precomputation 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 upto 53x peedup in the best case, and a geometric-mean speedup of 1.57×. Kirshanthan "Krish" Sundararajah, Ph.D. Assistant Professor Virginia Tech | Computer Science 220 Gilbert St, Suite 4103 Blacksburg, VA 24060 (540) 231-1779 | kirshanthans@vt.edumailto:kirshanthans@vt.edu kirshanthans.github.iohttps://kirshanthans.github.io/
participants (1)
-
Sundararajah, Kirshanthan