DROPS

Document

DOI: 10.4230/LIPIcs.ECOOP.2026.18

Eliminate Branches by Melding IR Instructions

Authors: Yuze Li, Srinivasan Ramachandra Sharma, Charitha Saumya, Ali R. Butt, and Kirshanthan Sundararajah

Published in: LIPIcs, Volume 372, 40th European Conference on Object-Oriented Programming (ECOOP 2026)

Abstract

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.

Cite as

Yuze Li, Srinivasan Ramachandra Sharma, Charitha Saumya, Ali R. Butt, and Kirshanthan Sundararajah. Eliminate Branches by Melding IR Instructions. In 40th European Conference on Object-Oriented Programming (ECOOP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 372, pp. 18:1-18:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ECOOP.2026.18,
  author =	{Li, Yuze and Sharma, Srinivasan Ramachandra and Saumya, Charitha and Butt, Ali R. and Sundararajah, Kirshanthan},
  title =	{{Eliminate Branches by Melding IR Instructions}},
  booktitle =	{40th European Conference on Object-Oriented Programming (ECOOP 2026)},
  pages =	{18:1--18:30},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-423-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{372},
  editor =	{Krebbers, Robbert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2026.18},
  URN =		{urn:nbn:de:0030-drops-261148},
  doi =		{10.4230/LIPIcs.ECOOP.2026.18},
  annote =	{Keywords: Control-flow Transformation, Branch Elimination}
}

Document

Artifact

DOI: 10.4230/DARTS.12.1.1

Eliminate Branches by Melding IR Instructions (Artifact)

Authors: Yuze Li, Srinivasan Ramachandra Sharma, Charitha Saumya, Ali R. Butt, and Kirshanthan Sundararajah

Published in: DARTS, Volume 12, Issue 1, Special Issue of the 40th European Conference on Object-Oriented Programming (ECOOP 2026)

Abstract

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.

Cite as

Yuze Li, Srinivasan Ramachandra Sharma, Charitha Saumya, Ali R. Butt, and Kirshanthan Sundararajah. Eliminate Branches by Melding IR Instructions (Artifact). In Special Issue of the 40th European Conference on Object-Oriented Programming (ECOOP 2026). Dagstuhl Artifacts Series (DARTS), Volume 12, Issue 1, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{li_et_al:DARTS.12.1.1,
  author =	{Li, Yuze and Sharma, Srinivasan Ramachandra and Saumya, Charitha and Butt, Ali R. and Sundararajah, Kirshanthan},
  title =	{{Eliminate Branches by Melding IR Instructions (Artifact)}},
  pages =	{1:1--1:9},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2026},
  volume =	{12},
  number =	{1},
  editor =	{Li, Yuze and Sharma, Srinivasan Ramachandra and Saumya, Charitha and Butt, Ali R. and Sundararajah, Kirshanthan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.12.1.1},
  URN =		{urn:nbn:de:0030-drops-261381},
  doi =		{10.4230/DARTS.12.1.1},
  annote =	{Keywords: Branch elimination, Compiler transformation, LLVM-IR}
}

Search Results

Documents authored by Li, Yuze

Eliminate Branches by Melding IR Instructions

Abstract

Cite as

Eliminate Branches by Melding IR Instructions (Artifact)

Abstract

Cite as

Thanks for your feedback!

Could not send message