{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:20:47Z","timestamp":1750306847619,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>Register allocation is an essential optimization for all compilers. A number of sophisticated register allocation algorithms have been developed over the years. The two fundamental classes of register allocation algorithms used in modern compilers are based on Graph Coloring (GC) and Linear Scan (LS). However, these two algorithms have fundamental limitations in terms of precision. For example, the key data structure used in GC-based algorithms, the interference graph, lacks information on the program points at which two variables may interfere. The LS-based algorithms make local decisions regarding spilling, and thereby trade off global optimization for reduced compile-time and space overheads. Recently, researchers have proposed Static Single Assignment (SSA)-based decoupled register allocation algorithms that exploit the live-range split points of the SSA representation to optimally solve the spilling problem. However, SSA-based register allocation often requires extra complexity in repairing register assignments during SSA elimination and in addressing architectural constraints such as aliasing and ABI encoding; this extra overhead can be prohibitively expensive in dynamic compilation contexts.<\/jats:p>\n          <jats:p>This article proposes a decoupled non-SSA--based global register allocation algorithm for dynamic compilation. It addresses the limitations in current algorithms by introducing a Bipartite Liveness Graph (BLG)-based register allocation algorithm that models the spilling phase as an optimization problem on the BLG itself and the assignment phase as a separate optimization problem. Advanced register allocation optimizations such as move coalescing, live-range splitting, and register class handling are also performed along with the spilling and assignment phases. In the presence of register classes, we propose a bucket-based greedy heuristic for assignment that strikes a balance between spill-cost and register class constraints. We present experimental evaluation of our BLG-based register allocation algorithm and compare it with production-quality register allocators in Jikes RVM and LLVM.<\/jats:p>","DOI":"10.1145\/2544101","type":"journal-article","created":{"date-parts":[[2014,1,6]],"date-time":"2014-01-06T20:42:39Z","timestamp":1389040959000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A decoupled non-SSA global register allocation using bipartite liveness graphs"],"prefix":"10.1145","volume":"10","author":[{"given":"Rajkishore","family":"Barik","sequence":"first","affiliation":[{"name":"Intel Labs, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jisheng","family":"Zhao","sequence":"additional","affiliation":[{"name":"Rice University, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vivek","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Rice University, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378854"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/258916.258941"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1167473.1167488"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.19"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.26"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_12"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/73141.74843"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143143"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/177492.177575"},{"volume-title":"Proceedings of the 14th International Workshop on Logic and Synthesis.","author":"Brisk P.","key":"e_1_2_1_12_1","unstructured":"Brisk , P. , Dabiri , F. , Macbeth , J. , and Sarrafzadeh , M . 2005. Polynomial time graph coloring register allocation . In Proceedings of the 14th International Workshop on Logic and Synthesis. Brisk, P., Dabiri, F., Macbeth, J., and Sarrafzadeh, M. 2005. Polynomial time graph coloring register allocation. In Proceedings of the 14th International Workshop on Logic and Synthesis."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/512529.512534"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/113445.113462"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(81)90048-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038698.2038708"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2006.35"},{"volume-title":"The meeting graph: A new model for loop cyclic register allocation. In Proceedings of the IFIP WG10","author":"Eisenbeis C.","key":"e_1_2_1_18_1","unstructured":"Eisenbeis , C. , Lelait , S. , and Marmol , B . 1995 . The meeting graph: A new model for loop cyclic register allocation. In Proceedings of the IFIP WG10 .3 Working Conference on Parallel Architectures and Compilation Techniques (PACT\u201995). IFIP Working Group on Algol, Manchester, UK, 264--267. Eisenbeis, C., Lelait, S., and Marmol, B. 1995. The meeting graph: A new model for loop cyclic register allocation. In Proceedings of the IFIP WG10.3 Working Conference on Parallel Architectures and Compilation Techniques (PACT\u201995). IFIP Working Group on Algol, Manchester, UK, 264--267."},{"key":"e_1_2_1_19_1","unstructured":"EPCC. 2001. The Java Grande Forum Benchmark Suite. Retrieved from http:\/\/www.epcc.ed.ac.uk\/javagrande\/javag.html.  EPCC. 2001. The Java Grande Forum Benchmark Suite. Retrieved from http:\/\/www.epcc.ed.ac.uk\/javagrande\/javag.html."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/229542.229546"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297027.1297033"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/177492.177499"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.01.008"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375610"},{"key":"e_1_2_1_26_1","unstructured":"Jikes RVM. 2011. Homepage. Retrieved from http:\/\/jikesrvm.org\/.  Jikes RVM. 2011. Homepage. Retrieved from http:\/\/jikesrvm.org\/."},{"key":"e_1_2_1_27_1","unstructured":"Jonathan Lee K. Palsberg J. and Pereira F. M. 2007. Aliased register allocation for straight-line programs is NP-complete. In Automata Languages and Programming. 680--691.   Jonathan Lee K. Palsberg J. and Pereira F. M. 2007. Aliased register allocation for straight-line programs is NP-complete. In Automata Languages and Programming. 680--691."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1369396.1370017"},{"key":"e_1_2_1_29_1","unstructured":"Lattner C. 2009. The LLVM Compiler Infrastructure. Retrieved from http:\/\/llvm.org\/.  Lattner C. 2009. The LLVM Compiler Infrastructure. Retrieved from http:\/\/llvm.org\/."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/353926.353929"},{"volume-title":"Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques (PACT\u201998)","author":"Park J.","key":"e_1_2_1_31_1","unstructured":"Park , J. and Moon , S . -M. 1998. Optimistic register coalescing . In Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques (PACT\u201998) . J.-L. Gaudiot, Ed., 196--204. Park, J. and Moon, S.-M. 1998. Optimistic register coalescing. In Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques (PACT\u201998). J.-L. Gaudiot, Ed., 196--204."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_21"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375609"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00722-4_12"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11970-5_10"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996875"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1669112.1669123"},{"volume-title":"Proceedings of the 16th International Conference on Compiler Construction (CC\u201907)","author":"Sarkar V.","key":"e_1_2_1_39_1","unstructured":"Sarkar , V. and Barik , R . 2007. Extended linear scan: An alternate foundation for global register allocation . In Proceedings of the 16th International Conference on Compiler Construction (CC\u201907) . Sarkar, V. and Barik, R. 2007. Extended linear scan: An alternate foundation for global register allocation. In Proceedings of the 16th International Conference on Compiler Construction (CC\u201907)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1034774.1034776"},{"key":"e_1_2_1_41_1","volume-title":"SPEC CPU2006 Benchmarks.","author":"The Standard Performance Evaluation Corporation","year":"2006","unstructured":"The Standard Performance Evaluation Corporation . 2006 . SPEC CPU2006 Benchmarks. Retrieved from http:\/\/www.spec.org\/cpu2006\/. The Standard Performance Evaluation Corporation. 2006. SPEC CPU2006 Benchmarks. Retrieved from http:\/\/www.spec.org\/cpu2006\/."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277714"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772979"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064979.1064998"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017753.1017769"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2544101","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2544101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:15Z","timestamp":1750234215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2544101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2544101"],"URL":"https:\/\/doi.org\/10.1145\/2544101","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}