Series-Parallel-Loop Decompositions of Control-flow Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912887794040832 |
|---|---|
| author | Cai, Xuran Goharshady, Amir Hitarth, S Lam, Chun Kit |
| author_facet | Cai, Xuran Goharshady, Amir Hitarth, S Lam, Chun Kit |
| contents | Control-flow graphs (CFGs) of structured programs are well known to exhibit strong sparsity properties. Traditionally, this sparsity has been modeled using graph parameters such as treewidth and pathwidth, enabling the development of faster parameterized algorithms for tasks in compiler optimization, model checking, and program analysis. However, these parameters only approximate the structural constraints of CFGs: although every structured CFG has treewidth at most~7, many graphs with treewidth at most~7 cannot arise as CFGs. As a result, existing parameterized techniques are optimized for a substantially broader class of graphs than those encountered in practice.
In this work, we introduce a new grammar-based decomposition framework that characterizes \emph{exactly} the class of control-flow graphs generated by structured programs. Our decomposition is intuitive, mirrors the syntactic structure of programs, and remains fully compatible with the dynamic-programming paradigm of treewidth-based methods. Using this framework, we design improved algorithms for two classical compiler optimization problems: \emph{Register Allocation} and \emph{Lifetime-Optimal Speculative Partial Redundancy Elimination (LOSPRE)}. Extensive experimental evaluation demonstrates significant performance improvements over previous state-of-the-art approaches, highlighting the benefits of using decompositions tailored specifically to CFGs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07627 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Series-Parallel-Loop Decompositions of Control-flow Graphs Cai, Xuran Goharshady, Amir Hitarth, S Lam, Chun Kit Programming Languages Control-flow graphs (CFGs) of structured programs are well known to exhibit strong sparsity properties. Traditionally, this sparsity has been modeled using graph parameters such as treewidth and pathwidth, enabling the development of faster parameterized algorithms for tasks in compiler optimization, model checking, and program analysis. However, these parameters only approximate the structural constraints of CFGs: although every structured CFG has treewidth at most~7, many graphs with treewidth at most~7 cannot arise as CFGs. As a result, existing parameterized techniques are optimized for a substantially broader class of graphs than those encountered in practice. In this work, we introduce a new grammar-based decomposition framework that characterizes \emph{exactly} the class of control-flow graphs generated by structured programs. Our decomposition is intuitive, mirrors the syntactic structure of programs, and remains fully compatible with the dynamic-programming paradigm of treewidth-based methods. Using this framework, we design improved algorithms for two classical compiler optimization problems: \emph{Register Allocation} and \emph{Lifetime-Optimal Speculative Partial Redundancy Elimination (LOSPRE)}. Extensive experimental evaluation demonstrates significant performance improvements over previous state-of-the-art approaches, highlighting the benefits of using decompositions tailored specifically to CFGs. |
| title | Series-Parallel-Loop Decompositions of Control-flow Graphs |
| topic | Programming Languages |
| url | https://arxiv.org/abs/2602.07627 |