{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T04:27:30Z","timestamp":1765254450615,"version":"3.44.0"},"publisher-location":"New York, NY, USA","reference-count":61,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T00:00:00Z","timestamp":1743292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Hong Kong Research Grants Council","award":["26208122"],"award-info":[{"award-number":["26208122"]}]},{"name":"Hong Kong PhD Fellowship Scheme"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,3,30]]},"DOI":"10.1145\/3669940.3707286","type":"proceedings-article","created":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T12:28:01Z","timestamp":1738844881000},"page":"463-477","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Faster Chaitin-like Register Allocation via Grammatical Decompositions of Control-Flow Graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-2626-5503","authenticated-orcid":false,"given":"Xuran","family":"Cai","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Clear Water Bay, New Territories, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1702-6584","authenticated-orcid":false,"given":"Amir Kafshdar","family":"Goharshady","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7419-3560","authenticated-orcid":false,"given":"S.","family":"Hitarth","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Clear Water Bay, New Territories, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8856-9095","authenticated-orcid":false,"given":"Chun Kit","family":"Lam","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Clear Water Bay, New Territories, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2025,3,30]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Amir Kafshdar Goharshady, and Andreas Pavlogiannis","author":"Ahmadi Ali","year":"2022","unstructured":"Ali Ahmadi, Majid Daliri, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. 2022. Efficient approximations for cache-conscious data placement. In PLDI. 857--871."},{"key":"e_1_3_2_1_2_1","volume-title":"Kiarash Mohammadi, and Andreas Pavlogiannis.","author":"Asadi Ali","year":"2020","unstructured":"Ali Asadi, Krishnendu Chatterjee, Amir Kafshdar Goharshady, Kiarash Mohammadi, and Andreas Pavlogiannis. 2020. Faster Algorithms for Quantitative Analysis of MCs and MDPs with Small Treewidth. In ATVA. 253--270."},{"key":"e_1_3_2_1_3_1","volume-title":"Markus Gufler, and Sergei Novozhilov.","author":"Barakbayeva Togzhan","year":"2024","unstructured":"Togzhan Barakbayeva, Soroush Farokhnia, Amir Kafshdar Goharshady, Markus Gufler, and Sergei Novozhilov. 2024. Pixiu: Optimal Block Production Revenues on Cardano. In Blockchain. 491--496."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Mirza Omer Beg and Peter van Beek. 2010. A graph theoretic approach to cache-conscious placement of data for direct mapped caches. In ISMM. 113--120.","DOI":"10.1145\/1806651.1806670"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Hans L. Bodlaender. 1988. Dynamic Programming on Graphs with Bounded Treewidth. In ICALP. 105--118.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Hans L. Bodlaender. 2005. Discovering Treewidth. In SOFSEM. 1--16.","DOI":"10.1007\/978-3-540-30577-4_1"},{"key":"e_1_3_2_1_7_1","unstructured":"Hans L. Bodlaender Jens Gustedt and Jan Arne Telle. 1998. Linear-Time Register Allocation for a Fixed Number of Registers. In SODA. 574--583."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"e_1_3_2_1_9_1","volume-title":"Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How. In LCPC. 283--298.","author":"Bouchez Florent","year":"2006","unstructured":"Florent Bouchez, Alain Darte, Christophe Guillon, and Fabrice Rastello. 2006. Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove? Or Revisiting Register Allocation: Why and How. In LCPC. 283--298."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Bernd Burgstaller Johann Blieberger and Bernhard Scholz. 2004. On the Tree Width of Ada Programs. In Ada-Europe. 78--90.","DOI":"10.1007\/978-3-540-24841-5_6"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Xuran Cai and Amir Kafshdar Goharshady. 2024. Faster Lifetime-optimal Speculative Partial Redundancy Elimination for Goto-free Programs. In SETTA.","DOI":"10.1007\/978-981-96-0602-3_21"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Brad Calder Chandra Krintz Simmi John and Todd M. Austin. 1998. Cache-Conscious Data Placement. In ASPLOS. 139--149.","DOI":"10.1145\/291069.291036"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/872726.806984"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Gregory J. Chaitin. 1982 b. Register allocation and spilling via graph coloring (with retrospective). In Best of PLDI. 66--74.","DOI":"10.1145\/989393.989403"},{"key":"e_1_3_2_1_15_1","volume-title":"Amir Kafshdar Goharshady, and Ehsan Kafshdar Goharshady","author":"Chatterjee Krishnendu","year":"2019","unstructured":"Krishnendu Chatterjee, Amir Kafshdar Goharshady, and Ehsan Kafshdar Goharshady. 2019a. The treewidth of smart contracts. In SAC. 400--408."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3363525"},{"key":"e_1_3_2_1_17_1","volume-title":"Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.","author":"Chatterjee Krishnendu","year":"2016","unstructured":"Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. 2016. Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In POPL. 733--747."},{"key":"e_1_3_2_1_18_1","volume-title":"Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.","author":"Chatterjee Krishnendu","year":"2020","unstructured":"Krishnendu Chatterjee, Amir Kafshdar Goharshady, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. 2020. Optimal and Perfectly Parallel Algorithms for On-demand Data-Flow Analysis. In ESOP. 112--140."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290366"},{"key":"e_1_3_2_1_20_1","volume-title":"Amir Kafshdar Goharshady, and Andreas Pavlogiannis","author":"Chatterjee Krishnendu","year":"2017","unstructured":"Krishnendu Chatterjee, Amir Kafshdar Goharshady, and Andreas Pavlogiannis. 2017. JTDec: A Tool for Tree Decompositions in Soot. In ATVA. 59--66."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Krishnendu Chatterjee and Jakub Lacki. 2013. Faster Algorithms for Markov Decision Processes with Low Treewidth. In CAV. 543--558.","DOI":"10.1007\/978-3-642-39799-8_36"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Mark Chimes Radu Iosif and Florian Zuleger. 2024. Tree-Verifiable Graph Grammars. In LPAR. 165--180.","DOI":"10.29007\/8l13"},{"key":"e_1_3_2_1_23_1","first-page":"1","article-title":"Faster Treewidth-Based Approximations for Wiener Index","volume":"6","author":"Conrado Giovanna Kobus","year":"2024","unstructured":"Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit J. Motwani. 2024. Faster Treewidth-Based Approximations for Wiener Index. In SEA. 6:1--6:19.","journal-title":"SEA."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622868"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622807"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"volume-title":"Parameterized algorithms","author":"Cygan Marek","key":"e_1_3_2_1_27_1","unstructured":"Marek Cygan, Fedor V Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized algorithms. Springer."},{"key":"e_1_3_2_1_28_1","volume-title":"Yin Tat Lee, and Guanghao Ye","author":"Dong Sally","year":"2021","unstructured":"Sally Dong, Yin Tat Lee, and Guanghao Ye. 2021. A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. In STOC. 1784--1797."},{"volume-title":"Parameterized complexity","author":"Downey Rodney G","key":"e_1_3_2_1_29_1","unstructured":"Rodney G Downey and Michael Ralph Fellows. 2012. Parameterized complexity. Springer."},{"key":"e_1_3_2_1_30_1","volume-title":"Circuit Cellar","volume":"121","author":"Dutta Sandeep","year":"2000","unstructured":"Sandeep Dutta. 2000. Anatomy of a Compiler: A Retargetable ANSI-C Compiler. Circuit Cellar, Vol. 121, 5 (2000)."},{"key":"e_1_3_2_1_31_1","unstructured":"Sandeep Dutta Daniel Drotos Kevin Vigor et al. 2003. Small Device C Compiler. http:\/\/sdcc.sourceforge.net\/"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/24039.24041"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186898"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382092"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689801"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ress.2019.106665"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Amir Kafshdar Goharshady and Ahmed Khaled Zaher. 2023. Efficient Interprocedural Data-Flow Analysis Using Treedepth and Treewidth. In VMCAI. 177--202.","DOI":"10.1007\/978-3-031-24950-1_9"},{"key":"e_1_3_2_1_38_1","unstructured":"H. C. Grossman. 2013. Register Allocation Example. https:\/\/www.cs.clemson.edu\/course\/cpsc827\/material\/Optimization\/Register%20Allocation%20Example.pdf"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Jens Gustedt Ole A. M\u00e6hle and Jan Arne Telle. 2002. The Treewidth of Java Programs. In ALENEX. 86--97.","DOI":"10.1007\/3-540-45643-0_7"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Susan Horwitz Thomas W. Reps and Shmuel Sagiv. 1995. Demand Interprocedural Dataflow Analysis. In FSE. 104--115.","DOI":"10.1145\/222124.222146"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Ken Kennedy and Linda Zucconi. 1977. Applications of a graph grammar for program control flow analysis. In POPL. 72--85.","DOI":"10.1145\/512950.512958"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Zachary Kincaid Thomas W. Reps and John Cyphert. 2021. Algebraic Program Analysis. In CAV. 46--83.","DOI":"10.1007\/978-3-030-81685-8_3"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Philipp Klaus Krause. 2013. Optimal Register Allocation in Polynomial Time. In CC. 1--20.","DOI":"10.1007\/978-3-642-37051-9_1"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Philipp Klaus Krause. 2021. LOSPRE in linear time. In SCOPES. 35--41.","DOI":"10.1145\/3493229.3493304"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.027"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Rahman Lavaee. 2016. The hardness of data packing. In POPL. 232--242.","DOI":"10.1145\/2837614.2837669"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332373"},{"key":"e_1_3_2_1_48_1","volume-title":"Mohammad Reza Hooshmandasl, and Ali Shakiba.","author":"Meybodi Mohsen Alambardar","year":"2022","unstructured":"Mohsen Alambardar Meybodi, Amir Kafshdar Goharshady, Mohammad Reza Hooshmandasl, and Ali Shakiba. 2022. Optimal Mining: Maximizing Bitcoin Miners' Revenues from Transaction Fees. In Blockchain. 266--273."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Jan Obdrz\u00e1lek. 2003. Fast Mu-Calculus Model Checking when Tree-Width Is Bounded. In CAV. 80--92.","DOI":"10.1007\/978-3-540-45069-6_7"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Erez Petrank and Dror Rawitz. 2002. The hardness of cache conscious data placement. In POPL. 101--112.","DOI":"10.1145\/503272.503283"},{"key":"e_1_3_2_1_51_1","first-page":"275","article-title":"The Hardness of Cache Conscious Data Placement","volume":"12","author":"Petrank Erez","year":"2005","unstructured":"Erez Petrank and Dror Rawitz. 2005. The Hardness of Cache Conscious Data Placement. Nord. J. Comput., Vol. 12, 3 (2005), 275--307.","journal-title":"Nord. J. Comput."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Thomas W. Reps Susan Horwitz and Shmuel Sagiv. 1995. Precise Interprocedural Dataflow Analysis via Graph Reachability. In POPL. 49--61.","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_3_2_1_56_1","volume-title":"Proceedings of the International Conference on Machine Translation and Applied Language Analysis.","author":"Sakai Itiroo","year":"1961","unstructured":"Itiroo Sakai. 1961. Syntax in universal translation. In Proceedings of the International Conference on Machine Translation and Applied Language Analysis."},{"volume-title":"Linear-time computability of combinatorial problems on series-parallel graphs. Journal of the ACM (JACM)","author":"Takamizawa Kazuhiko","key":"e_1_3_2_1_57_1","unstructured":"Kazuhiko Takamizawa, Takao Nishizeki, and Nobuji Saito. [n.,d.]. Linear-time computability of combinatorial problems on series-parallel graphs. Journal of the ACM (JACM), Vol. 29, 3 ( [n.,d.]), 623--641."},{"volume-title":"Cache management by the compiler","author":"Thabit Khalid Omar","key":"e_1_3_2_1_58_1","unstructured":"Khalid Omar Thabit. 1982. Cache management by the compiler. Rice University."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"e_1_3_2_1_60_1","volume-title":"Robert Endre Tarjan, and Eugene L. Lawler","author":"Valdes Jacobo","year":"1979","unstructured":"Jacobo Valdes, Robert Endre Tarjan, and Eugene L. Lawler. 1979. The recognition of Series Parallel digraphs. In STOC. 1--12."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/356635.356639"}],"event":{"name":"ASPLOS '25: 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages","SIGOPS ACM Special Interest Group on Operating Systems","SIGARCH ACM Special Interest Group on Computer Architecture"],"location":"Rotterdam Netherlands","acronym":"ASPLOS '25"},"container-title":["Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 1"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3669940.3707286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3669940.3707286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:50:16Z","timestamp":1755787816000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3669940.3707286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,30]]},"references-count":61,"alternative-id":["10.1145\/3669940.3707286","10.1145\/3669940"],"URL":"https:\/\/doi.org\/10.1145\/3669940.3707286","relation":{},"subject":[],"published":{"date-parts":[[2025,3,30]]},"assertion":[{"value":"2025-03-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}