💬 NLP

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

This paper presents a general linear-time algorithm for solving Partial Constraint Satisfaction Problems over Series-Parallel-Loop decomposed control-flow graphs with a fixed domain, unifying previous approaches for tasks like register allocation and achieving significant performance improvements in optimal bank selection.

Original authors: Xuran Cai, Amir Goharshady

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xuran Cai, Amir Goharshady

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the director of a complex play. You have a script (the program) with many scenes (statements) and actors (variables). The script tells you exactly how the story flows: Scene A leads to Scene B, or sometimes Scene A splits into two paths depending on a character's choice. This flow of scenes is called a Control-Flow Graph.

Your job is to assign specific costumes to your actors as they move through the play. However, you have strict rules:

The Rules (Constraints): If two actors are on stage at the same time, they can't wear the same costume (or they'll get confused).
The Cost (Partial Satisfaction): Sometimes, the rules are impossible to follow perfectly. Maybe you only have three costumes for five actors. In that case, you have to break a rule. But breaking a rule costs you "points" (like extra time or money). Your goal isn't to be perfect; it's to break the fewest rules or pay the lowest cost possible.

This is the Partial Constraint Satisfaction Problem (PCSP). It's a puzzle that computer scientists use to solve tricky optimization problems, like deciding which computer parts go where or how to organize code.

The Problem: A Maze of Rules

Usually, solving these puzzles is incredibly hard. It's like trying to solve a massive maze where every turn depends on the last one. Even with modern computers, finding the best solution can take forever, especially if the script is long and the rules are complex.

Previous methods tried to solve this by looking at the "shape" of the maze. They noticed that most computer programs aren't chaotic messes; they are structured. They have loops (repeating scenes), choices (if-then-else), and straight lines.

The Innovation: The "SPL" Blueprint

The authors of this paper, Xuran Cai and Amir Goharshady, decided to use a special blueprint called SPL Decomposition (Series-Parallel-Loop).

Think of a complex program not as a giant, tangled ball of yarn, but as a set of Lego blocks.

Series: One block stacked on top of another (Scene A happens, then Scene B).
Parallel: Two blocks side-by-side (If you choose Path A, you get this block; if Path B, you get that one).
Loop: A block that connects back to itself (A scene that repeats).

The authors realized that if you break the program down into these simple Lego blocks, you can solve the costume puzzle piece by piece, starting from the smallest blocks and working your way up to the whole play.

The Magic Trick: The Fast Algorithm

Their main contribution is a new, super-fast way to solve this puzzle.

The Old Way: Previous methods were like trying to solve the whole puzzle at once, or using a very complicated map that sometimes got stuck.
The New Way: Their algorithm is like a smart assembly line. It looks at the Lego blocks, solves the tiny problems for each block, and then combines those answers. Because the blocks are so simple, the math is easy.

They claim this method is linear, meaning if you double the size of the play, the time it takes to solve the puzzle only doubles. It doesn't get exponentially harder. It's like walking through a hallway: the longer the hallway, the longer it takes to walk, but you don't have to run faster or take more steps per foot.

Real-World Tests: The "Bank Selection" Race

To prove their method works, they tested it on a specific problem called Optimal Bank Selection.

The Analogy: Imagine a library with different sections (banks). Some books are only available in the "History" section, others in "Science." To get a book, you have to walk to the right section. If you need a History book, then a Science book, then another History book, you have to walk back and forth. This walking is slow and wastes time.
The Goal: Figure out the best order to arrange your trips so you walk the least amount of distance.

They compared their new "Lego block" method against the current best method (which uses a different kind of map called "Treewidth").

The Result: Their method was four times faster.
The Comparison: They also compared it to two other famous puzzle solvers (SAT and ILP). Their method was roughly 10 times faster than the ILP solver and nearly 1,000 times faster than the SAT solver.

The Bottom Line

The authors didn't just invent a new puzzle; they found a faster, simpler way to solve a whole family of puzzles that computer compilers use every day. By treating computer programs as structured Lego sets (Series-Parallel-Loop), they created a tool that is not only theoretically faster but practically much quicker, shaving off significant time when optimizing code for devices like microcontrollers.

In short: They found a shortcut through the maze that everyone else was walking around, and it works for almost any type of maze you throw at it.

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

Problem Definition

This work addresses the Partial Constraint Satisfaction Problem (PCSP) over the Control-Flow Graphs (CFGs) of structured, goto-free programs. While the standard Constraint Satisfaction Problem (CSP) requires finding an assignment of values to variables that satisfies all constraints, PCSPs allow for the violation of certain constraints at a specified cost. The objective is to find an assignment that minimizes the total cost of violated constraints.

In the context of compiler optimization, many tasks can be modeled as PCSPs where:

Variables correspond to vertices (statements or basic blocks) in the CFG.
Constraints correspond to edges between vertices.
Costs are associated with edge violations (e.g., register spills, redundant computations, or bank selection instructions).

The paper notes that PCSPs are generally NP-hard, even with small domain sizes (e.g., size 3 or even size 2 under specific reductions). However, the CFGs of structured programs possess specific structural properties—specifically, they are sparse and decomposable—that can be exploited to design efficient algorithms.

Methodology

The authors propose a general algorithm that leverages the Series-Parallel-Loop (SPL) decomposition of CFGs, a concept introduced by Cai and Goharshady [7]. Unlike previous approaches that rely on tree decompositions and treewidth parameters, this method utilizes the specific grammar of structured programs to decompose the graph into atomic components and operations.

SPL Decomposition

The algorithm operates on an SPL graph $G = (V, E, S, T, B, C)$ , which includes four special nodes: Start ( $S$ ), Terminate ( $T$ ), Break ( $B$ ), and Continue ( $C$ ). The decomposition is defined recursively via three operations:

Series ( $G_1 \otimes G_2$ ): Represents sequential execution ( $P_1; P_2$ ). Vertices $T_1$ and $S_2$ are merged, as are $B$ and $C$ nodes.
Parallel ( $G_1 \oplus G_2$ ): Represents conditional branching ( $if \dots then \dots else \dots$ ). Start, Terminate, Break, and Continue nodes are merged between the two subgraphs.
Loop ( $G_1^\circledast$ ): Represents a loop ( $while \dots do \dots$ ). New $S, T, B, C$ nodes are added, connecting to the subgraph's internal nodes to model loop entry, exit, break, and continue paths.

Dynamic Programming Algorithm

The core contribution is a bottom-up dynamic programming (DP) algorithm that computes the minimum cost for an SPL decomposition tree.

State Definition: For each node $u$ in the decomposition tree, representing a subgraph $G_u$ , the algorithm computes a DP table $dp[u, X]$. Here, $X$ is an assignment of values from the domain $D$ to the four special vertices of $G_u$ ( $S_u, T_u, B_u, C_u$ ).
Transition Logic:
- Atomic Nodes: The cost is calculated directly based on the single edge and the assigned values.
- Series Nodes: The algorithm minimizes the sum of costs from child subgraphs ( $v$ and $w$ ) subject to compatibility constraints (e.g., $X_v(T_v) = X_w(S_w)$ ).
- Parallel Nodes: Similar to series nodes but with stricter equality constraints on merged vertices. The algorithm accounts for potential duplicate edges introduced by the merge.
- Loop Nodes: The algorithm calculates the cost of new edges introduced by the loop operation and adds them to the cost of the subgraph body.
Complexity: The time complexity for processing each node in the decomposition is $O(|D|^6)$ , where $|D|$ is the domain size. Since the size of the SPL decomposition is linear in the size of the CFG ( $|G|$ ), the total runtime is $O(|G| \cdot |D|^6)$ . For any fixed domain size, this yields a linear-time solution.

Key Contributions

Generalization of PCSP: The paper presents a unified framework for solving PCSPs over CFGs, generalizing previous specialized algorithms for Register Allocation [7] and Lifetime-optimal Speculative Partial Redundancy Elimination (LOSPRE) [6].
SPL-Based Efficiency: By utilizing SPL decompositions rather than tree decompositions, the authors avoid the dependency on treewidth parameters. This results in a simpler algorithm that directly exploits the structure of structured programs.
Optimal Bank Selection: The authors apply this general framework to the Optimal Placement of Bank Selection Instructions, a problem previously solved using treewidth-based methods [32].
Experimental Validation: The implementation demonstrates that the SPL-based approach significantly outperforms the state-of-the-art treewidth-based approach for bank selection, achieving runtimes approximately four times faster.

Experimental Results

The authors implemented the algorithm in C++ and integrated it with the Small Device C Compiler (SDCC). Experiments were conducted on the SDCC regression test suite covering three architectures: HC08, Z80, and MCS51.

Performance vs. State-of-the-Art: Compared to the treewidth-based approach of [32] (which has a runtime of $O(|G| \cdot tw(G) \cdot |D|^{tw(G)+1})$ $O (∣ G ∣ \cdot tw (G) \cdot ∣ D ∣^{tw (G) + 1})$ ), the proposed algorithm achieved average runtimes roughly 4 times faster across all tested architectures.
- Example (HC08): 1,998.3 ns (proposed) vs. 8,558.8 ns (baseline).
Comparison with SAT/ILP: The method was also compared against SAT (Kissat) and Integer Linear Programming (Gurobi) solvers. The proposed algorithm was found to be nearly 10 times faster than the ILP approach and approximately 1,000 times faster than the SAT solver.
Optimality: Both the proposed method and the baseline [32] produce identical optimal solutions for bank selection; the improvement is strictly in computational efficiency.

Significance and Claims

The paper claims that the proposed algorithm provides a linear-time solution for a broad class of compiler optimization problems modeled as PCSPs over structured program CFGs, provided the domain size is fixed.

The significance lies in:

Unification: It consolidates distinct optimization tasks (Register Allocation, LOSPRE, Bank Selection) under a single, general algorithmic framework.
Practical Speedup: The removal of the treewidth parameter dependency and the use of SPL decompositions result in a significantly lower constant factor in practice, leading to substantial speedups in real-world compiler scenarios.
Scalability: The linear dependence on the graph size ( $|G|$ ) makes the approach highly scalable for large codebases, outperforming both parameterized tree-decomposition methods and general NP-hard solvers (SAT/ILP).

The authors emphasize that while the theoretical complexity depends on $|D|^6$ , in practical compiler applications (like bank selection where $|D|$ is small and constant), the algorithm behaves as a true linear-time solver, offering a superior alternative to existing heuristics and parameterized algorithms.