Faster Chaitin-like Register Allocation via Grammatical Decompositions of Control-Flow Graphs
It is well-known that control-flow graphs (CFGs) of structured programs are sparse. This sparsity has been previously formalized in terms of graph parameters such as treewidth and pathwidth and used to design faster parameterized algorithms for numerous compiler optimization, model checking and program analysis tasks.
Authors
- Amir Kafshdar Goharshady (ORCID: https://orcid.org/0000-0003-1702-6584)
- S. Hitarth
- Chun Kit Lam (ORCID: https://orcid.org/0000-0002-8856-9095)
- Xuran Cai (ORCID: https://orcid.org/0009-0005-2626-5503)
Institutions
- Hong Kong University of Science and Technology (HK)
- University of Oxford (GB)
Publication Details
- Published
- 2025-02-06
- DOI
- https://doi.org/10.1145/3669940.3707286
- Citations
- 1
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 1.50