2026-07-23T03:46:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26138 2026-06-25T08:55:22Z ddc:004 open_access

Eliminate Branches by Melding IR Instructions (Artifact) Li, Yuze Sharma, Srinivasan Ramachandra Saumya, Charitha Butt, Ali R. Sundararajah, Kirshanthan Branch elimination Compiler transformation LLVM-IR 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 Eliminate Branches by 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 1.51× on 24 branch-heavy microbenchmarks (peak 32× on toUpper), reducing branch mispredictions by 48% on average. On realistic workloads - SPECrate 2017 (16 benchmarks), SQLite TPC-H (22 queries), and CPython pyperformance (40 benchmarks) - MERIT with profile-guided function selection achieves ∼1% geometric mean speedup across all three suites, demonstrating consistent improvement without regressions on diverse production workloads. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuze Li and Srinivasan Ramachandra Sharma and Charitha Saumya and Ali R. Butt and Kirshanthan Sundararajah 2026 Is Part Of DARTS, Volume 12, Issue 1, Special Issue of the 40th European Conference on Object-Oriented Programming (ECOOP 2026) Article Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DARTS.12.1.1 urn:nbn:de:0030-drops-261381 https://drops.dagstuhl.de/entities/document/10.4230/DARTS.12.1.1 eng https://creativecommons.org/licenses/by/4.0/legalcode