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.

Algebraic Program Analysis (APA) is a ubiquitous framework that has been employed as a unifying model for various problems in data-flow analysis, termination analysis, invariant generation, predicate abstraction and a wide variety of other standard static analysis tasks. APA models program summaries as elements of a regular algebra . Suppose that a summary inAis assigned to every transition of the program and that we aim to compute the effect of running the program starting at linesand ending at linet. APA first computes a regular expression capturing all program paths of interest. In case of intraprocedural analysis, models all paths fromstot, whereas in the interprocedural case it models all interprocedurally-valid paths, i.e. ‍paths that go back to the right caller function when a callee returns. This regular expression is then interpreted over the algebra to obtain the desired result. Suppose the program hasnlines of code and each evaluation of an operation in the regular algebra takesO(k) time. It is well-known that a single APA query, or a set of queries with the same starting points, can be answered inO(n· α(n) ·k), where α is the inverse Ackermann function. In this work, we consider an on-demand setting for APA: the program is given in the input and can be preprocessed. The analysis has to then answer a large number of on-line queries, each providing a pair (s,t) of program lines which are the start and end point of the query, respectively. The goal is to avoid the significant cost of running a fresh APA instance for each query. Our main contribution is a series of algorithms that, after a lightweight preprocessing ofO(n· lgn·k), answer each query inO(k) time. In other words, our preprocessing has almost the same asymptotic complexity as a single APA query, except for a sub-logarithmic factor, and then every future query is answered instantly, i.e. ‍by a constant number of operations in the algebra. We achieve this remarkable speedup by relying on certain structural sparsity properties of control-flow and call graphs (CFGs and CGs). Specifically, we exploit the fact that control-flow graphs of real-world programs have a tree-like structure and bounded treewidth and nesting depth and that their call graphs have small treedepth in comparison to the size of the program. Finally, we provide experimental results demonstrating the effectiveness and efficiency of our approach and showing that it beats the runtime of classical APA by several orders of magnitude.