Parameterized Algorithms and Complexity for Function Merging with Branch Reordering DOI: 10.1145/3808282 Journal: PACMPL Volume: 10 PLDI 204 6 pldi26main-p183-p CCS: Software and its engineering Compilers CCS: Theory of computation Fixed parameter tractability CCS: Theory of computation Parameterized complexity and exact algorithms
Amir K. Goharshady, Kerim Kochekov, Tian Shu, Ahmed Khaled Zaher · 2026
Read Parameterized Algorithms and Complexity for Function Merging with Branch Reordering DOI: 10.1145/3808282 Journal: PACMPL Volume: 10 PLDI 204 6 pldi26main-p183-p CCS: Software and its engineering Compilers CCS: Theory of computation Fixed parameter tractability CCS: Theory of computation Parameterized complexity and exact algorithms by Amir K. Goharshady, Kerim Kochekov, Tian Shu, Ahmed Khaled Zaher (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-11027.txt.
Description
Goharshady and three colleagues study function merging with branch reordering, a compiler technique for binary size reduction. Function merging combines similar functions into one, eliminating redundancy. The leading approach views functions as linear instruction sequences matched by sequence alignment. The authors allow branch swaps within each function, enabling more flexible matching and better merging. They show this makes the problem NP-hard, then study it through parameterized algorithms, identifying governing input parameters. They examine two natural factors: input functions' branching factor and nesting depth.
Catalog record
| CREATOR | Amir K. Goharshady, Kerim Kochekov, Tian Shu, Ahmed Khaled Zaher |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99190 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.11027