一句话：首次从算法与复杂度角度研究允许分支重排序的函数合并，证明其 NP 难，并基于分支因子与嵌套深度给出 FPT 算法及硬度结果。
二进制大小缩减对移动与嵌入式编译优化日益重要，函数合并通过合并相似函数消除冗余。现有最优方法将函数视为指令线性序列并用序列对齐最大化匹配。本文推广该问题，允许在每个函数内部重排分支，以获得更灵活匹配。作者证明该推广问题 NP 难，并从参数化算法与复杂度角度研究：输入为两个函数 F1、F2，参数包括大小 n_i、分支因子 b_i 和嵌套深度 d_i。主要结果：关于 b1、d1、b2、d2 的 FPT 算法（2^{O(bd)} n^2）；即使一个函数嵌套深度无界仍属 FPT 的算法（2^{O(bd^2)} n^7）；以及即使 d1、b2、d2 为常数问题仍 NP 难的硬度结果。这是首个从算法与复杂度角度系统研究带分支重排序函数合并的工作。
Binary size reduction is an increasingly important optimization objective for compilers, especially in the context of mobile applications and resource-constrained embedded devices. In such domains, binary size often takes precedence over compilation time. One emerging technique that has been shown effective is function merging , where multiple similar functions are merged into one, thereby eliminating redundancy. The state-of-the-art approach to perform the merging, due to Rocha et al. [CGO 2019, PLDI 2020], is based on sequence alignment , where functions are viewed as linear sequences of instructions that are then matched in a way maximizing their alignment. In this paper, we consider a significantly generalized formulation of the problem by allowing reordering of branches within each function, subsequently allowing for more flexible matching and better merging. We show that this makes the problem NP -hard, and thus we study it through the lens of parameterized algorithms and complexity , where we identify certain parameters of the input that govern its complexity. We look at two natural parameters: the branching factor and nesting depth of input functions. Concretely, our input consists of two functions F 1 , F 2 , where each F i has size n i , branching factor b i , and nesting depth d i . Our task is to reorder the branches of F 1 and F 2 in a way that yields linearizations achieving the maximum sequence alignment. Let n = max ( n 1 , n 2 ), and define b , d similarly. Our results are as follows: • A simple algorithm running in time 2 O ( bd ) n 2 , establishing that the problem is fixed-parameter tractable ( FPT ) with respect to all four parameters b 1 , d 1 , b 2 , d 2 . • An algorithm running in time 2 O ( bd 2 ) n 7 , showing that even when one of the functions has an unbounded nesting depth, the problem remains in FPT . • A hardness result showing that the problem is NP -hard even when constrained to constant d 1 , b 2 , d 2 . To the best of our knowledge, this is the first systematic study of function merging with branch reordering from an algorithmic or complexity-theoretic perspective.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2604-11027,
title = {Parameterized Algorithms and Complexity for Function Merging with Branch Reordering},
author = {Amir K. Goharshady and Kerim Kochekov and Tian Shu and Ahmed Khaled Zaher},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {PLDI},
year = {2026},
doi = {10.1145/3808282}
}