{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:16:18Z","timestamp":1750306578789,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,1,9]],"date-time":"2015-01-09T00:00:00Z","timestamp":1420761600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004347","name":"STMicroelectronics","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004347","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2015,1,9]]},"abstract":"<jats:p>\n            Recent developments in register allocation, mostly linked to static single assignment (SSA) form, have shown the benefits of decoupling the problem in two phases: a first\n            <jats:italic>spilling<\/jats:italic>\n            phase places load and store instructions so that the register pressure at all program points is small enough, and a second\n            <jats:italic>assignment<\/jats:italic>\n            and\n            <jats:italic>coalescing<\/jats:italic>\n            phase maps the variables to physical registers and reduces the number of move instructions among registers. This article focuses on the first phase, for which many open questions remain: in particular, we study the notion of optimal spilling (what can be expressed?) and the impact of SSA form (does it help?).\n          <\/jats:p>\n          <jats:p>To identify the important features for optimal spilling on load-store architectures, we develop a new integer linear programming formulation, more accurate and expressive than previous approaches. Among other features, we can express SSA \u03d5-functions, memory-to-memory copies, and the fact that a value can be stored simultaneously in a register and in memory. Based on this formulation, we present a thorough analysis of the results obtained for the SPECINT 2000 and EEMBC 1.1 benchmarks, from which we draw, among others, the following conclusions: (1) rematerialization is extremely important; (2) SSA complicates the formulation of optimal spilling, especially because of memory coalescing when the code is not in conventional SSA (CSSA); (3) microarchitectural features are significant and thus have to be accounted for; and (4) significant savings can be obtained in terms of static spill costs, cache miss rates, and dynamic instruction counts.<\/jats:p>","DOI":"10.1145\/2685392","type":"journal-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:02:10Z","timestamp":1421092930000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Studying Optimal Spilling in the Light of SSA"],"prefix":"10.1145","volume":"11","author":[{"given":"Quentin","family":"Colombet","sequence":"first","affiliation":[{"name":"LIP, CNRS, INRIA, ENS-Lyon, UCB-Lyon"}]},{"given":"Florian","family":"Brandner","sequence":"additional","affiliation":[{"name":"ENSTA ParisTech"}]},{"given":"Alain","family":"Darte","sequence":"additional","affiliation":[{"name":"LIP, CNRS, INRIA, ENS-Lyon, UCB-Lyon"}]}],"member":"320","published-online":{"date-parts":[[2015,1,9]]},"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\/155090.155119"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/301618.301643"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"F. Bouchez A. Darte C. Guillon and F. Rastello. 2006. Register allocation: What does the NP-completeness proof of Chaitin et al. really prove&quest; or revisiting register allocation: Why and how&quest; In Languages and Compilers for Parallel Computing (LCPC'06) (LNCS) Vol. 4382. Springer 283--298.   F. Bouchez A. Darte C. Guillon and F. Rastello. 2006. Register allocation: What does the NP-completeness proof of Chaitin et al. really prove&quest; or revisiting register allocation: Why and how&quest; In Languages and Compilers for Parallel Computing (LCPC'06) (LNCS) Vol. 4382. Springer 283--298.","DOI":"10.1007\/978-3-540-72521-3_21"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.26"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254766.1254782"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00722-4_13"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143143"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800230.806984"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/2245737.2245881"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629395.1629408"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2011.10"},{"volume-title":"Symposium on Microarchitecture (MICRO\u201935)","author":"Fu C.","key":"e_1_2_1_13_1","unstructured":"C. Fu and K. Wilken . 2002. A faster optimal register allocator . In Symposium on Microarchitecture (MICRO\u201935) . IEEE Computer, 245--256. C. Fu and K. Wilken. 2002. A faster optimal register allocator. In Symposium on Microarchitecture (MICRO\u201935). IEEE Computer, 245--256."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/229542.229546"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199608)26:8%3C929::AID-SPE40%3E3.3.CO;2-K"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.01.008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134006"},{"volume-title":"Workshop on Software & Compilers for Embedded Systems (SCOPES&rsquo;\u201909)","author":"Koes D. R.","key":"e_1_2_1_19_1","unstructured":"D. R. Koes and S. C. Goldstein . 2009. Register allocation deconstructed . In Workshop on Software & Compilers for Embedded Systems (SCOPES&rsquo;\u201909) . ACM, 21--30. D. R. Koes and S. C. Goldstein. 2009. Register allocation deconstructed. In Workshop on Software & Compilers for Embedded Systems (SCOPES&rsquo;\u201909). ACM, 21--30."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375609"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_22_1","volume-title":"Symposium on Static Analysis (SAS\u201999)","volume":"1694","author":"Sreedhar V. C.","unstructured":"V. C. Sreedhar , R. D.-C. Ju , D. M. Gillies , and V. Santhanam . 1999. Translating out of static single assignment form . In Symposium on Static Analysis (SAS\u201999) (LNCS), Vol. 1694 . Springer, 194--210. V. C. Sreedhar, R. D.-C. Ju, D. M. Gillies, and V. Santhanam. 1999. Translating out of static single assignment form. In Symposium on Static Analysis (SAS\u201999) (LNCS), Vol. 1694. Springer, 194--210."},{"key":"e_1_2_1_23_1","unstructured":"L. Torczon and K. Cooper. 2011. Engineering A Compiler (2nd ed.). Morgan Kaufmann San Francisco CA.   L. Torczon and K. Cooper. 2011. Engineering A Compiler (2nd ed.). Morgan Kaufmann San Francisco CA."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90107-4"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2685392","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2685392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:44Z","timestamp":1750227224000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2685392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,9]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1,9]]}},"alternative-id":["10.1145\/2685392"],"URL":"https:\/\/doi.org\/10.1145\/2685392","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2015,1,9]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}