{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T20:34:23Z","timestamp":1761510863358,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2004,7,1]],"date-time":"2004-07-01T00:00:00Z","timestamp":1088640000000},"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. Program. Lang. Syst."],"published-print":{"date-parts":[[2004,7]]},"abstract":"<jats:p>\n            Graph-coloring register allocators eliminate copies by coalescing the source and target nodes of a copy if they do not interfere in the interference graph. Coalescing, however, can be harmful to the colorability of the graph because it tends to yield a graph with nodes of higher degrees. Unlike\n            <jats:italic>aggressive coalescing<\/jats:italic>\n            , which coalesces any pair of noninterfering copy-related nodes,\n            <jats:italic>conservative coalescing<\/jats:italic>\n            or\n            <jats:italic>iterated coalescing<\/jats:italic>\n            perform safe coalescing that preserves the colorability. Unfortunately, these heuristics give up coalescing too early, losing many opportunities for coalescing that would turn out to be safe. Moreover, they ignore the fact that coalescing may even improve the colorability of the graph by reducing the degree of neighbor nodes that are interfering with both the source and target nodes being coalesced. This article proposes a new heuristic called\n            <jats:italic>optimistic coalescing<\/jats:italic>\n            which optimistically performs aggressive coalescing, thus exploiting the positive impact of coalescing aggressively, but when a coalesced node is to be spilled, it is split back into separate nodes. Since there is a better chance of coloring one of those splits, we can reduce the overall spill amount.\n          <\/jats:p>","DOI":"10.1145\/1011508.1011512","type":"journal-article","created":{"date-parts":[[2004,10,7]],"date-time":"2004-10-07T17:38:56Z","timestamp":1097170736000},"page":"735-765","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Optimistic register coalescing"],"prefix":"10.1145","volume":"26","author":[{"given":"Jinpyo","family":"Park","sequence":"first","affiliation":[{"name":"Seoul National University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soo-Mook","family":"Moon","sequence":"additional","affiliation":[{"name":"Seoul National University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,7]]},"reference":[{"volume-title":"Proceedings of the 3rd International Symposium on Programming Language Implementation and Logic Programming.","year":"1991","author":"Appel A.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of the 2001 ACM SIGPLAN Conference on Programming Languages Design and Implementation. ACM","author":"Appel A. W.","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of the 1997 ACM SIGPLAN Conference on Programming Languages Design and Implementation. ACM","year":"1997","author":"Bergner P.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","unstructured":"Briggs P. 1992. Register allocation via graph coloring. Ph.D. dissertation Rice University.   Briggs P. 1992. Register allocation via graph coloring. Ph.D. dissertation Rice University."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/177492.177575"},{"volume-title":"Proceedings of the ACM SIGPLAN 1982 Symposium on Compiler Construction. ACM","year":"1982","author":"Chaitin G.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/88616.88621"},{"volume-title":"Proceedings of the 1997 ACM SIGPLAN Conference on Programming Languages Design and Implementation. ACM","author":"Cooper K. D.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the 1998 International Compiler Construction Conference.","author":"Cooper K. D.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/229542.229546"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1032620"},{"volume-title":"Proceedings of the 1993 ACM SIGPLAN Conference on Programming Languages Design and Implementation. ACM","author":"Kolte P.","key":"e_1_2_1_13_1"},{"volume-title":"Proceedings of the 1988 ACM SIGPLAN Conference on Programming Languages Design and Implementation. ACM","year":"1988","author":"Lam M.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","unstructured":"Lueh G.-Y. 1997. Fusion-based register allocation. Ph.D dissertation Carnegie Mellon Univ.   Lueh G.-Y. 1997. Fusion-based register allocation. Ph.D dissertation Carnegie Mellon Univ."},{"volume-title":"Proceedings of the 1997 ACM SIGPLAN Conference on Programming Languages Design and Implementation. ACM","author":"Lueh G.-Y.","key":"e_1_2_1_16_1"},{"volume-title":"IEE Proc. Comput. Digital Tech., 215--224","author":"Moon S.-M.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/267959.269966"},{"volume-title":"Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM","year":"1999","author":"Vegdahl S. R.","key":"e_1_2_1_19_1"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1011508.1011512","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1011508.1011512","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:25:42Z","timestamp":1750281942000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1011508.1011512"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["10.1145\/1011508.1011512"],"URL":"https:\/\/doi.org\/10.1145\/1011508.1011512","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2004,7]]},"assertion":[{"value":"2004-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}