{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T21:44:05Z","timestamp":1786743845255,"version":"3.56.0"},"reference-count":100,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T00:00:00Z","timestamp":1562025600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Ericsson AB and the Swedish Research Council","award":["621-2011-6229"],"award-info":[{"award-number":["621-2011-6229"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            This article introduces a combinatorial optimization approach to register allocation and instruction scheduling, two central compiler problems. Combinatorial optimization has the potential to solve these problems optimally and to exploit processor-specific features readily. Our approach is the first to leverage this potential\n            <jats:italic>in practice<\/jats:italic>\n            : it captures the\n            <jats:italic>complete<\/jats:italic>\n            set of program transformations used in state-of-the-art compilers,\n            <jats:italic>scales<\/jats:italic>\n            to medium-sized functions of up to 1,000\u00a0instructions, and generates\n            <jats:italic>executable<\/jats:italic>\n            code. This level of practicality is reached by using constraint programming, a particularly suitable combinatorial optimization technique. Unison, the implementation of our approach, is open source, used in industry, and integrated with the LLVM toolchain.\n          <\/jats:p>\n          <jats:p>An extensive evaluation confirms that Unison generates better code than LLVM while scaling to medium-sized functions. The evaluation uses systematically selected benchmarks from MediaBench and SPEC CPU2006 and different processor architectures (Hexagon, ARM, MIPS). Mean estimated speedup ranges from\u00a01.1% to\u00a010% and mean code size reduction ranges from\u00a01.3% to\u00a03.8% for the different architectures. A significant part of this improvement is due to the integrated nature of the approach. Executing the generated code on Hexagon confirms that the estimated speedup results in actual speedup. Given a fixed time limit, Unison solves optimally functions of up to 946 instructions, nearly an order of magnitude larger than previous approaches.<\/jats:p>\n          <jats:p>The results show that our combinatorial approach can be applied in practice to trade compilation time for code quality beyond the usual compiler optimization levels, identify improvement opportunities in heuristic algorithms, and fully exploit processor-specific features.<\/jats:p>","DOI":"10.1145\/3332373","type":"journal-article","created":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T12:50:33Z","timestamp":1562071833000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Combinatorial Register Allocation and Instruction Scheduling"],"prefix":"10.1145","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2806-7333","authenticated-orcid":false,"given":"Roberto Casta\u00f1eda","family":"Lozano","sequence":"first","affiliation":[{"name":"RISE SICS, Sweden and KTH Royal Institute of Technology, Kista, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3079-8095","authenticated-orcid":false,"given":"Mats","family":"Carlsson","sequence":"additional","affiliation":[{"name":"RISE SICS, Kista, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6794-6413","authenticated-orcid":false,"given":"Gabriel Hjort","family":"Blindell","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Kista, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6283-7004","authenticated-orcid":false,"given":"Christian","family":"Schulte","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology, Sweden and RISE SICS, Kista, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(93)90068-A"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278283.278285"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378854"},{"key":"e_1_2_1_4_1","unstructured":"ARM. 2007. ARM1156T2F-S Technical Reference Manual. ARM. Rev. r0p4. Retrieved from http:\/\/infocenter.arm.com\/help\/topic\/com.arm.doc.ddi0290g\/DDI0290G_arm1156t2fs_r0p4_trm.pdf."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/647476.727759"},{"key":"e_1_2_1_6_1","volume-title":"Claude Le Pape, and Wim Nuijten","author":"Baptiste Philippe","year":"2006","unstructured":"Philippe Baptiste, Claude Le Pape, and Wim Nuijten. 2006. Constraint-based scheduling and planning. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, 759--797."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1757112.1757140"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008966522714"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(94)90127-9"},{"key":"e_1_2_1_11_1","volume-title":"Handbook of Constraint Programming, Francesca Rossi, Peter van Beek","author":"Bessiere Christian","unstructured":"Christian Bessiere. 2006. Constraint propagation. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, 27--81."},{"key":"e_1_2_1_12_1","unstructured":"Armin Biere Marijn Heule Hans van Maaren and Toby Walsh (Eds.). 2009. Handbook of Satisfiability. IOS Press."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.7.5.621"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143143"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892211"},{"key":"e_1_2_1_16_1","unstructured":"Mats Carlsson and Roberto Casta\u00f1eda Lozano. 2018. Unison\u2019s source code: x86 fork. Retrieved from: https:\/\/github.com\/matsc-at-sics-se\/unison."},{"key":"e_1_2_1_17_1","unstructured":"Roberto Casta\u00f1eda Lozano. 2016. Tool demonstration: Register allocation and instruction scheduling in Unison. Retrieved from: https:\/\/youtu.be\/t4g2AjSfMX8."},{"key":"e_1_2_1_18_1","unstructured":"Roberto Casta\u00f1eda Lozano. 2017. Register allocation and instruction scheduling in Unison. Retrieved from: https:\/\/youtu.be\/kx64V74Mba0."},{"key":"e_1_2_1_19_1","unstructured":"Roberto Casta\u00f1eda Lozano. 2017. The Unison manual. Retrieved from: https:\/\/unison-code.github.io\/doc\/manual.pdf."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33558-7_54"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597809.2597815"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892237"},{"key":"e_1_2_1_23_1","volume-title":"Gabriel Hjort Blindell, and Christian Schulte","author":"Lozano Roberto Casta\u00f1eda","year":"2018","unstructured":"Roberto Casta\u00f1eda Lozano, Mats Carlsson, Gabriel Hjort Blindell, and Christian Schulte. 2018. Unison website. Retrieved from: https:\/\/unison-code.github.io."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2245737.2245881"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(97)00184-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.53999"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/502949.502896"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2014.12"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2685392"},{"key":"e_1_2_1_32_1","volume-title":"Engineering a Compiler","author":"Cooper Keith","unstructured":"Keith Cooper and Linda Torczon. 2012. Engineering a Compiler (2nd ed.). Morgan Kaufmann.","edition":"2"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629395.1629408"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772980"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2180887.2180896"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2011.10"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800046.801649"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the International Workshop on Theory and Practice of Logic Programming","author":"Gange Graeme","unstructured":"Graeme Gange, Jorge A. Navas, Peter Schachte, Harald S\u00f8ndergaard, and Peter J. Stuckey. 2015. Horn clauses as an intermediate representation for program analysis and transformation. In Proceedings of the International Workshop on Theory and Practice of Logic Programming. Cambridge University Press, 526--542."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/261693.261706"},{"key":"e_1_2_1_42_1","volume-title":"Gecode: Generic constraint development environment. Retrieved from: https:\/\/www.gecode.org.","author":"Team Gecode","year":"2018","unstructured":"Gecode Team. 2018. Gecode: Generic constraint development environment. Retrieved from: https:\/\/www.gecode.org."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(00)00081-3"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006314320276"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55407"},{"key":"e_1_2_1_46_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_47_1","volume-title":"The Compiler Design Handbook","author":"Govindarajan R.","unstructured":"R. Govindarajan. 2007. Instruction scheduling. In The Compiler Design Handbook (2nd ed.). CRC.","edition":"2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_20"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1999263"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2967117"},{"key":"e_1_2_1_52_1","unstructured":"Intel. 2017. Intel 64 and IA-32 Architectures Software Developer Manuals. Intel. 325462-065US. Retrieved from https:\/\/software.intel.com\/en-us\/articles\/intel-sdm."},{"key":"e_1_2_1_53_1","volume-title":"Embedded Computing","author":"Fisher Cliff Young","unstructured":"Cliff Young Joseph A. Fisher, Paolo Faraboschi. 2005. Embedded Computing. Elsevier."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/646906.710512"},{"key":"e_1_2_1_55_1","volume-title":"Handbook of Signal Processing Systems","author":"Kessler Christoph W.","unstructured":"Christoph W. Kessler. 2010. Compiling for VLIW DSPs. In Handbook of Signal Processing Systems. Springer-Verlag, 603--638."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/1152682.1152685"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134006"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1543820.1543824"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30201-8_28"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/266800.266832"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/504670"},{"key":"e_1_2_1_63_1","first-page":"2","article-title":"Two-dimensional packing problems: A survey. Euro","volume":"141","author":"Lodi Andrea","year":"2002","unstructured":"Andrea Lodi, Silvano Martello, and Michele Monaci. 2002. Two-dimensional packing problems: A survey. Euro. J. Op. Res. 141, 2 (Sept. 2002), 241--252.","journal-title":"J. Op. Res."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-011-9115-6"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability","author":"MacQueen James B.","year":"1967","unstructured":"James B. MacQueen. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. University of California Press, 281--297."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85958-1_7"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213008003765"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.2.219"},{"key":"e_1_2_1_69_1","unstructured":"MiniZinc Team. 2018. MiniZinc constraint modeling language. Retrieved from: https:\/\/www.minizinc.org."},{"key":"e_1_2_1_70_1","unstructured":"MIPS. 2016. The MIPS32 Instruction Set Manual. MIPS. Rev. 6.06. Retrieved from https:\/\/www.mips.com\/downloads\/the-mips32-instruction-set-v6-05."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759937.1759949"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/513829.513851"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_19"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391451.2391463"},{"key":"e_1_2_1_75_1","volume-title":"Wolsey","author":"Nemhauser George L.","year":"1999","unstructured":"George L. Nemhauser and Laurence A. Wolsey. 1999. Integer and Combinatorial Optimization. Wiley."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.5555\/1771668.1771709"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375609"},{"key":"e_1_2_1_78_1","volume-title":"Evaluating Unison\u2019s Speedup Estimation. Master\u2019s Thesis","author":"Persson Martin","unstructured":"Martin Persson. 2017. Evaluating Unison\u2019s Speedup Estimation. Master\u2019s Thesis. KTH Royal Institute of Technology, Sweden."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2005.1430555"},{"key":"e_1_2_1_80_1","unstructured":"Qualcomm. 2013. Hexagon Application Binary Interface Specification. Qualcomm. 80-N2040-23 Rev. B. Retrieved from https:\/\/developer.qualcomm.com\/software\/hexagon-dsp-sdk\/tools."},{"key":"e_1_2_1_81_1","unstructured":"Qualcomm. 2013. Hexagon Simulator User Guide. Qualcomm. 80-N2040-17 Rev. B. Retrieved from https:\/\/developer.qualcomm.com\/software\/hexagon-dsp-sdk\/tools."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205181"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","unstructured":"Francesca Rossi Peter van Beek and Toby Walsh (Eds.). 2006. Handbook of Constraint Programming. Elsevier.","DOI":"10.5555\/2843512"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.4.445"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/513829.513854"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512432"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85958-1_4"},{"key":"e_1_2_1_88_1","volume-title":"Handbook of Constraint Programming, Francesca Rossi, Peter van Beek","author":"Smith Barbara M.","unstructured":"Barbara M. Smith. 2006. Modelling. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, 375--404."},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.2307\/1412159"},{"key":"e_1_2_1_90_1","volume-title":"CPU 2006 Benchmarks. SPEC. Retrieved from: https:\/\/www.spec.org\/cpu2006","author":"SPEC.","year":"2016","unstructured":"SPEC. 2016. CPU 2006 Benchmarks. SPEC. Retrieved from: https:\/\/www.spec.org\/cpu2006."},{"key":"e_1_2_1_91_1","volume-title":"Building the SPEC CPU2006 Tool Suite. SPEC. Retrieved from: https:\/\/www.spec.org\/cpu2006\/Docs\/tools-build.html.","author":"SPEC.","year":"2018","unstructured":"SPEC. 2018. Building the SPEC CPU2006 Tool Suite. SPEC. Retrieved from: https:\/\/www.spec.org\/cpu2006\/Docs\/tools-build.html."},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.5555\/647168.718132"},{"key":"e_1_2_1_93_1","volume-title":"Handbook of Constraint Programming, Francesca Rossi, Peter van Beek","author":"van Beek Peter","unstructured":"Peter van Beek. 2006. Backtracking search algorithms. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, 83--132."},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.5555\/2887965.2888082"},{"key":"e_1_2_1_95_1","volume-title":"Handbook of Constraint Programming, Francesca Rossi, Peter van Beek","author":"van Hoeve Willem-Jan","unstructured":"Willem-Jan van Hoeve and Irit Katriel. 2006. Global constraints. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, 205--244."},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800060205"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/12276.13338"},{"key":"e_1_2_1_98_1","unstructured":"Fredrik Wickberg and Mattias Eriksson. 2017. Outperforming state-of-the-art compilers in Unison. Retrieved from: https:\/\/www.ericsson.com\/research-blog\/outperforming-state-art-compilers-unison."},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.2307\/3001968"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349318"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.5555\/254208.254233"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-2323-9_6"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331699.1331707"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3332373","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3332373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:37Z","timestamp":1750204477000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3332373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,2]]},"references-count":100,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3332373"],"URL":"https:\/\/doi.org\/10.1145\/3332373","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,2]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}