Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs

AI summary

Overview

Research area: Algorithm design for compiler optimization, specifically constraint satisfaction over control-flow graphs (CFGs) of programs.

Technical level: Advanced. The paper assumes familiarity with constraint satisfaction, graph decompositions, dynamic programming, and NP-hardness arguments.

Scope: The paper presents a single general dynamic-programming algorithm that solves Partial Constraint Satisfaction Problems (PCSPs) over the control-flow graphs of structured goto-free programs in linear time for any fixed variable domain, and validates it experimentally on the Optimal Bank Selection problem.

What This Paper Is About

Many compiler optimization tasks — register allocation, redundancy elimination, memory bank selection — can be expressed as Partial Constraint Satisfaction Problems, where each vertex of the program's control-flow graph gets a value and each edge charges a cost if the two endpoint values conflict. Solving these problems in general is NP-hard, so the authors ask whether the special structure of real-world program control-flow graphs can be exploited to get a fast, general-purpose solver. Their answer is to use Series-Parallel-Loop (SPL) decompositions of CFGs and run dynamic programming over the resulting decomposition tree.

Key Contributions

1. A general PCSP algorithm over SPL graphs with a runtime of O(|G| · |D|^6), where |G| is the size of the control-flow graph and |D| is the domain of variables. For any fixed domain D, this is linear time.

2. A unification of previous SPL-based work. The authors show that their algorithm generalizes and subsumes the earlier SPL-based algorithms for register allocation [6] and Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE) [7], which then become special cases rather than separate bespoke algorithms.

3. A new application: Optimal Placement of Bank Selection Instructions, which the authors say had not previously been addressed with SPL decompositions.

4. An experimental evaluation showing roughly four times better runtime than the previous state of the art for bank selection, plus comparisons against SAT and ILP solvers.

Main Findings

• Linear-time PCSP for fixed domains: The DP at each node of the SPL decomposition runs in O(|D|^6), and the decomposition has the same asymptotic size as the CFG, giving an overall O(|G| · |D|^6) algorithm.

• Per-node costs are modest: Atomic nodes cost O(|D|^2) after ignoring disconnected vertices (down from O(|D|^4)), series nodes O(|D|^5), parallel nodes O(|D|^4), and loop nodes O(|D|^6) after temporarily ignoring the disconnected break and continue vertices (down from O(|D|^8)).

• Register allocation as a PCSP instance: With r registers and V live variables, the domain size is O(r · V^r), yielding a runtime of O(|G| · r^6 · V^6 · r).

• LOSPRE as a PCSP instance: The domain size is 2^3 = 8, so the algorithm runs in O(|G| · 8^6) = O(|G|) — linear time with no extra parameter.

• Bank selection runtimes (HC08): The new algorithm averaged 1,998.3 nanoseconds versus 8,558.8 nanoseconds for the treewidth-based approach of [30].

• Bank selection runtimes (Z80): 2,402.1 nanoseconds versus 8,209.3 nanoseconds for [30].

• Bank selection runtimes (MCS51): 1,834.3 nanoseconds versus 6,268.3 nanoseconds for [30].

• Comparison against generic solvers: The method is nearly 10 times faster than the ILP approach (Gurobi), which is itself roughly 100 times faster than the SAT solver (Kissat).

• No quality difference: The authors did not compare outputs, because both their approach and [30] find optimal bank selection solutions and the outputs coincide.

• Benchmark scale: The SDCC regression test suite used comprised 13,463 instances for HC08, 179,611 for Z80, and 84,700 for MCS51.

Methodology in Plain English

The authors start from a known structural fact: the control-flow graphs of structured, goto-free programs can be built up from three simple pieces using three operations — putting two code fragments in sequence (series), choosing between two fragments with an if-else (parallel), and wrapping a fragment in a while loop (loop). This construction is called an SPL decomposition and is captured as a parse tree.

The algorithm walks that parse tree bottom-up. For every subtree, it stores a table indexed by every possible assignment of values to that subgraph's four special vertices (start, terminate, break, continue), recording the minimum total cost achievable inside the subgraph consistent with that assignment. Leaves are computed directly. At each internal node, the algorithm combines the children's tables, checking that the shared special vertices are assigned the same values on both sides — "compatibility" — and adding the children's costs. For parallel nodes, duplicate edges that represent the same edge in the parent are subtracted so they are only counted once. For loop nodes, the cost of the three new edges is added. The final answer is the minimum over all assignments at the root.

Because the domain is finite and the tables are small, each combination step is polynomial in |D| but independent of the graph size, so the whole computation is linear in the number of program lines once |D| is fixed. The authors then express three classic compiler problems as instances of this framework and plug them in.

Why This Matters

Impact on research: Prior work solved PCSP-like compiler problems one at a time with task-specific algorithms, typically via tree decompositions parameterized by treewidth. This paper shows a single SPL-based dynamic program covers a whole family of tasks, and that no treewidth parameter is needed for structured programs — a conceptually simpler and asymptotically cleaner route.

Real-world applications:

• Register allocation in compiled code, where variables must be mapped to a limited register set and spill costs minimized.
• Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE), a redundancy elimination technique that computes repeated expressions once and caches them in a temporary variable.
• Memory bank selection for 8-bit and 16-bit microcontrollers with partitioned address spaces, where inserting bank-switching instructions costs code size.
• Embedded and resource-constrained compilation generally, since the benchmarks are embedded programs where code size is a primary concern.

Industry relevance: The implementation was integrated with the Small Device C Compiler (SDCC), a widely used, already highly optimized compiler for embedded targets, and the baseline it beats is itself shipped in SDCC. The authors report an approximately four-fold speed-up and attribute it to the absence of a treewidth parameter plus a small constant factor in practice.

Future Directions

1. Extending beyond structured, goto-free programs. The SPL guarantee applies only to graphs generated by the structured-program grammar, so handling arbitrary control flow with unrestricted goto statements remains open.

2. Richer or multi-domain cost models. The paper notes the algorithm can be trivially extended to support different domains for different variables, but this extension is not evaluated.

3. Applying the general framework to further compiler tasks. Since register allocation, LOSPRE, and bank selection all reduced to PCSP, other optimization problems over CFGs that fit the edge-cost formulation could presumably be plugged in as well.

4. A more thorough empirical campaign across domains. The reported experiments focus on bank selection on three architectures, while the register allocation and LOSPRE results are inherited from prior work rather than re-measured; independent benchmarking of the unified algorithm across all three tasks is a natural next step.

Target Audience

Compiler engineers and researchers in programming languages who implement optimizations over control-flow graphs will get the most direct value, especially those working on embedded systems and register allocation. Algorithm researchers interested in constraint satisfaction, tree decompositions, and parameterized complexity will find the SPL formulation and the O(|G| · |D|^6) bound of theoretical interest. Graduate students with a background in algorithms and compiler design would need to be comfortable with graph decompositions and dynamic programming to follow the details.

Authors’ abstract

In this work, we focus on the Partial Constraint Satisfaction Problem (PCSP) over control-flow graphs (CFGs) of programs. PCSP serves as a generalization of the well-known Constraint Satisfaction Problem (CSP). In the CSP framework, we define a set of variables, a set of constraints, and a finite domain $D$ that encompasses all possible values for each variable. The objective is to assign a value to each variable in such a way that all constraints are satisfied. In the graph variant of CSP, an underlying graph is considered and we have one variable corresponding to each vertex of the graph and one or several constraints corresponding to each edge. In PCSPs, we allow for certain constraints to be violated at a specified cost, aiming to find a solution that minimizes the total cost. Numerous classical compiler optimization tasks can be framed as PCSPs over control-flow graphs. Examples include Register Allocation, Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE), and Optimal Placement of Bank Selection Instructions. On the other hand, it is well-known that control-flow graphs of structured programs are sparse and decomposable in a variety of ways. In this work, we rely on the Series-Parallel-Loop (SPL) decompositions as introduced by~\cite{RegisterAllocation}. Our main contribution is a general algorithm for PCSPs over SPL graphs with a time complexity of \(O(|G| \cdot |D|^6)\), where \(|G|\) represents the size of the control-flow graph. Note that for any fixed domain $D,$ this yields a linear-time solution. Our algorithm can be seen as a generalization and unification of previous SPL-based approaches for register allocation and LOSPRE. In addition, we provide experimental results over another classical PCSP task, i.e. Optimal Bank Selection, achieving runtimes four times better than the previous state of the art.