Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913034703732736 |
|---|---|
| author | Morse, Gregory Kozsik, Tamás |
| author_facet | Morse, Gregory Kozsik, Tamás |
| contents | Loop nesting forests (LNFs) are a fundamental abstraction for reasoning about control-flow structure, enabling applications such as compiler optimizations, program analysis, and dominator computation. While efficient static algorithms for constructing LNFs are well understood, maintaining them under dynamic graph updates has remained largely unexplored due to the lack of efficient dynamic depth-first search (DFS) maintenance.
In this paper, we present the first fully dynamic algorithm for maintaining loop nesting forests in reducible control-flow graphs. Our approach leverages recent advances in dynamic DFS maintenance to incrementally update loop structure under edge insertions and deletions. We show that updates can be confined to local regions of the depth-first spanning tree, avoiding global recomputation.
We provide formal invariants, correctness arguments, and complexity analysis, and demonstrate how the maintained LNF enables efficient derivation of dominance information. Our results establish LNFs as a practical dynamic abstraction for modern compiler and analysis pipelines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_13664 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs Morse, Gregory Kozsik, Tamás Data Structures and Algorithms 68Q25 (Primary) 68N20, 05C85 (Secondary) F.2.2; D.3.4; F.3.2 Loop nesting forests (LNFs) are a fundamental abstraction for reasoning about control-flow structure, enabling applications such as compiler optimizations, program analysis, and dominator computation. While efficient static algorithms for constructing LNFs are well understood, maintaining them under dynamic graph updates has remained largely unexplored due to the lack of efficient dynamic depth-first search (DFS) maintenance. In this paper, we present the first fully dynamic algorithm for maintaining loop nesting forests in reducible control-flow graphs. Our approach leverages recent advances in dynamic DFS maintenance to incrementally update loop structure under edge insertions and deletions. We show that updates can be confined to local regions of the depth-first spanning tree, avoiding global recomputation. We provide formal invariants, correctness arguments, and complexity analysis, and demonstrate how the maintained LNF enables efficient derivation of dominance information. Our results establish LNFs as a practical dynamic abstraction for modern compiler and analysis pipelines. |
| title | Fully Dynamic Maintenance of Loop Nesting Forests in Reducible Flow Graphs |
| topic | Data Structures and Algorithms 68Q25 (Primary) 68N20, 05C85 (Secondary) F.2.2; D.3.4; F.3.2 |
| url | https://arxiv.org/abs/2604.13664 |