2026-09-08T11:38:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26114 2026-09-05T19:37:23Z ddc:004 open_access

Eliminate Branches by Melding IR Instructions Li, Yuze Sharma, Srinivasan Ramachandra Saumya, Charitha Butt, Ali R. Sundararajah, Kirshanthan Control-flow Transformation Branch Elimination 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 access 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 MERIT (MElding IR InsTructions), 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 1.52× geometric mean speedup on 24 branch-heavy microbenchmarks (peak 32× on toUpper) and reduces branch mispredictions by 48.9% on average. On more realistic workloads - SPECrate 2017 (16 benchmarks), SQLite TPC-H (22 queries), and CPython pyperformance (40 benchmarks) - MERIT with profile-guided function selection achieves a positive geomean (∼1.01×) across all three suites, demonstrating consistent improvement without regressions. 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 LIPIcs, Volume 372, 40th European Conference on Object-Oriented Programming (ECOOP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECOOP.2026.18 urn:nbn:de:0030-drops-261148 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode