The Bounded Pathwidth of Control-Flow Graphs
summary
Proves control-flow graphs of structured, goto-free programs have pathwidth at most 2·nesting depth, and gives a linear-time path decomposition construction. Builds a spill-free register-allocation DP whose exponent depends on pathwidth rather than treewidth and shows practical gains on SDCC benchmarks (pathwidth ≈ treewidth so the new method is often exponentially cheaper), reporting up to ~800× speedups and 2–3 orders of magnitude runtime improvement in experiments.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 0:21Control flow graphs
- 2:28Bounded pathwidth matters
- 3:52Nesting depth
- 4:34Pathwidth vs treewidth
- 6:42Path decompositions
- 7:25Constructing decompositions
- 8:49Nested statements
- 9:51Pathwidth bounds
- 10:31Register allocation
- 11:12Experimental comparison
- 12:38Key takeaways
- 13:41Path decompositions simplify
- 14:25Q&A
related talks
26mCircuit Width Estimation via Effect Typing and Linear Dependency (Extended Abs...
01h 02mTheory and Control
24mBounded Treewidth, Multiple Context-Free Grammars, and Downward Closures
23mAn Abstract Interpretation for SPMD Divergence on Reducible Control Flow Graphs
13mEffects for Efficiency: Asymptotic Speedup with First-Class Control
19mPanel: Compilation Frameworks
16mBeyond Relooper: Recursive Translation of Unstructured Control Flow to Structu…
18mParameterized Algorithms and Complexity for Function Merging with Branch Reordering