{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,14]],"date-time":"2026-08-14T21:44:04Z","timestamp":1786743844890,"version":"3.56.0"},"reference-count":154,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T00:00:00Z","timestamp":1560816000000},"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 Comput. Surv."],"published-print":{"date-parts":[[2020,5,31]]},"abstract":"<jats:p>Register allocation (mapping variables to processor registers or memory) and instruction scheduling (reordering instructions to increase instruction-level parallelism) are essential tasks for generating efficient assembly code in a compiler. In the past three decades, combinatorial optimization has emerged as an alternative to traditional, heuristic algorithms for these two tasks. Combinatorial optimization approaches can deliver optimal solutions according to a model, can precisely capture trade-offs between conflicting decisions, and are more flexible at the expense of increased compilation time.<\/jats:p>\n          <jats:p>This article provides an exhaustive literature review and a classification of combinatorial optimization approaches to register allocation and instruction scheduling, with a focus on the techniques that are most applied in this context: integer programming, constraint programming, partitioned Boolean quadratic programming, and enumeration. Researchers in compilers and combinatorial optimization can benefit from identifying developments, trends, and challenges in the area; compiler practitioners may discern opportunities and grasp the potential benefit of applying combinatorial optimization.<\/jats:p>","DOI":"10.1145\/3200920","type":"journal-article","created":{"date-parts":[[2019,6,19]],"date-time":"2019-06-19T12:05:38Z","timestamp":1560945938000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Survey on Combinatorial Register Allocation and Instruction Scheduling"],"prefix":"10.1145","volume":"52","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-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,6,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Orlin","author":"Ahuja Ravindra K.","year":"1993","unstructured":"Ravindra K. Ahuja , Thomas L. Magnanti , and James B . Orlin . 1993 . Network Flows : Theory, Algorithms, and Applications. Prentice-Hall . Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/212094.212131"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.56325"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201995)","author":"Altman Erik R.","unstructured":"Erik R. Altman , R. Govindarajan , and Guang R. Gao . 1995. Scheduling and mapping: Software pipelining in the presence of structural hazards . In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201995) . ACM, 139--150. Erik R. Altman, R. Govindarajan, and Guang R. Gao. 1995. Scheduling and mapping: Software pipelining in the presence of structural hazards. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201995). ACM, 139--150."},{"key":"e_1_2_1_5_1","unstructured":"Analog Devices. 2017. ADSP-2106x SHARC Processor User\u2019s Manual. Retrieved from: http:\/\/www.analog.com\/en\/products\/landing-pages\/001\/sharc-manuals.html.  Analog Devices. 2017. ADSP-2106x SHARC Processor User\u2019s Manual. Retrieved from: http:\/\/www.analog.com\/en\/products\/landing-pages\/001\/sharc-manuals.html."},{"key":"e_1_2_1_6_1","volume-title":"Appel and Lal George","author":"Andrew","year":"2000","unstructured":"Andrew W. Appel and Lal George . 2000 . Optimal Coalescing Challenge. Retrieved from: http:\/\/www.cs.princeton.edu\/ appel\/coalesce. Andrew W. Appel and Lal George. 2000. Optimal Coalescing Challenge. Retrieved from: http:\/\/www.cs.princeton.edu\/ appel\/coalesce."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201901)","author":"Andrew","unstructured":"Andrew W. Appel and Lal George. 2001. Optimal spilling for CISC machines with few registers . In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201901) . ACM, 243--253. Andrew W. Appel and Lal George. 2001. Optimal spilling for CISC machines with few registers. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI\u201901). ACM, 243--253."},{"key":"e_1_2_1_8_1","unstructured":"ARM. 2017. ARM Architecture Reference Manuals. Retrieved from: http:\/\/infocenter.arm.com\/help\/topic\/com.arm.doc.set.architecture\/index.html.  ARM. 2017. ARM Architecture Reference Manuals. Retrieved from: http:\/\/infocenter.arm.com\/help\/topic\/com.arm.doc.set.architecture\/index.html."},{"key":"e_1_2_1_9_1","volume-title":"Algorithms, Extensions and Applications","author":"Artigues Christian","unstructured":"Christian Artigues , Sophie Demassey , and Emmanuel Neron . 2008. Resource-constrained Project Scheduling: Models , Algorithms, Extensions and Applications . Wiley . Christian Artigues, Sophie Demassey, and Emmanuel Neron. 2008. Resource-constrained Project Scheduling: Models, Algorithms, Extensions and Applications. Wiley."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676531"},{"key":"e_1_2_1_11_1","volume-title":"Barton","author":"Bailey David H.","year":"1985","unstructured":"David H. Bailey and John T . Barton . 1985 . The NAS Kernel Benchmark Program. Technical Report. NASA Ames Research Center , Mountain View, CA. David H. Bailey and John T. Barton. 1985. The NAS Kernel Benchmark Program. Technical Report. NASA Ames Research Center, Mountain View, CA."},{"key":"e_1_2_1_12_1","volume-title":"Claude Le Pape, and Wim Nuijten","author":"Baptiste Philippe","year":"2006","unstructured":"Philippe Baptiste , Philippe Laborie , 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 , chapter 22, 671--800. Philippe Baptiste, Philippe Laborie, 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, chapter 22, 671--800."},{"key":"e_1_2_1_13_1","volume-title":"Claude Le Pape, and Wim Nuijten","author":"Baptiste Philippe","year":"2001","unstructured":"Philippe Baptiste , Claude Le Pape, and Wim Nuijten . 2001 . Constraint-based Scheduling. Kluwer . Philippe Baptiste, Claude Le Pape, and Wim Nuijten. 2001. Constraint-based Scheduling. Kluwer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_2"},{"key":"e_1_2_1_15_1","volume-title":"Languages and Compilers for Parallel Computing (Lecture Notes in Computer Science)","author":"Barik Rajkishore","unstructured":"Rajkishore Barik , Christian Grothoff , Rahul Gupta , Vinayaka Pandit , and Raghavendra Udupa . 2007. Optimal bitwise register allocation using integer linear programming . In Languages and Compilers for Parallel Computing (Lecture Notes in Computer Science) , Vol. 4382 . Springer , 267--282. Rajkishore Barik, Christian Grothoff, Rahul Gupta, Vinayaka Pandit, and Raghavendra Udupa. 2007. Optimal bitwise register allocation using integer linear programming. In Languages and Compilers for Parallel Computing (Lecture Notes in Computer Science), Vol. 4382. Springer, 267--282."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008966522714"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205183"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512470"},{"key":"e_1_2_1_19_1","volume-title":"Principles and Practice of Constraint Programming (Lecture Notes in Computer Science)","author":"Beldiceanu Nicolas","unstructured":"Nicolas Beldiceanu and Mats Carlsson . 2001. Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint . In Principles and Practice of Constraint Programming (Lecture Notes in Computer Science) , Vol. 2239 . Springer , 377--391. Nicolas Beldiceanu and Mats Carlsson. 2001. Sweep as a generic pruning technique applied to the non-overlapping rectangles constraint. In Principles and Practice of Constraint Programming (Lecture Notes in Computer Science), Vol. 2239. Springer, 377--391."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1177\/109434208900300302"},{"key":"e_1_2_1_22_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 , chapter 3, 29--84. Christian Bessiere. 2006. Constraint propagation. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, chapter 3, 29--84."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823285_30"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.7.5.621"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/106972.106986"},{"key":"e_1_2_1_26_1","volume-title":"Principles and Practice of Constraint Programming (Lecture Notes in Computer Science)","author":"Lozano Roberto Casta\u00f1eda","unstructured":"Roberto Casta\u00f1eda Lozano , Mats Carlsson , Frej Drejhammar , and Christian Schulte . 2012. Constraint-based register allocation and instruction scheduling . In Principles and Practice of Constraint Programming (Lecture Notes in Computer Science) , Vol. 7514 . Springer , 750--766. Roberto Casta\u00f1eda Lozano, Mats Carlsson, Frej Drejhammar, and Christian Schulte. 2012. Constraint-based register allocation and instruction scheduling. In Principles and Practice of Constraint Programming (Lecture Notes in Computer Science), Vol. 7514. Springer, 750--766."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597809.2597815"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2245737.2245881"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(97)00184-3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.335014"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.372778"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2014.12"},{"key":"e_1_2_1_34_1","first-page":"4","article-title":"Studying optimal spilling in the light of SSA","volume":"11","author":"Colombet Quentin","year":"2015","unstructured":"Quentin Colombet , Florian Brandner , and Alain Darte . 2015 . Studying optimal spilling in the light of SSA . ACM Trans. Archit. Code Optimiz. 11 , 4 (Jan. 2015), 1--26. Quentin Colombet, Florian Brandner, and Alain Darte. 2015. Studying optimal spilling in the light of SSA. ACM Trans. Archit. Code Optimiz. 11, 4 (Jan. 2015), 1--26.","journal-title":"ACM Trans. Archit. Code Optimiz."},{"key":"e_1_2_1_35_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/19.1.43"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.94.0281"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.1994.363069"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892219"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.728"},{"key":"e_1_2_1_42_1","first-page":"2","article-title":"From machine scheduling to VLIW instruction scheduling","volume":"1","author":"de Dinechin Beno\u00eet Dupont","year":"2004","unstructured":"Beno\u00eet Dupont de Dinechin . 2004 . From machine scheduling to VLIW instruction scheduling . ST J. Res. 1 , 2 (Sep. 2004). Beno\u00eet Dupont de Dinechin. 2004. From machine scheduling to VLIW instruction scheduling. ST J. Res. 1, 2 (Sep. 2004).","journal-title":"ST J. Res."},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications. MISTA, 144--151","author":"de Dinechin Beno\u00eet Dupont","year":"2007","unstructured":"Beno\u00eet Dupont de Dinechin . 2007 . Time-indexed formulations and a large neighborhood search for the resource-constrained modulo scheduling problem . In Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications. MISTA, 144--151 . Beno\u00eet Dupont de Dinechin. 2007. Time-indexed formulations and a large neighborhood search for the resource-constrained modulo scheduling problem. In Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications. MISTA, 144--151."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/354880.354894"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629395.1629408"},{"key":"e_1_2_1_47_1","volume-title":"Software and Compilers for Embedded Systems (Lecture Notes in Computer Science)","author":"Eckstein Erik","unstructured":"Erik Eckstein , Oliver K\u00f6nig , and Bernhard Scholz . 2003. Code instruction selection based on SSA-graphs . In Software and Compilers for Embedded Systems (Lecture Notes in Computer Science) , Vol. 2826 . Springer , 49--65. Erik Eckstein, Oliver K\u00f6nig, and Bernhard Scholz. 2003. Code instruction selection based on SSA-graphs. In Software and Compilers for Embedded Systems (Lecture Notes in Computer Science), Vol. 2826. Springer, 49--65."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/776261.776298"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/258915.258933"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/224538.224542"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92990-1_7"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2180887.2180896"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361096.1361099"},{"key":"e_1_2_1_55_1","volume-title":"Programming Language Implementation and Logic Programming (Lecture Notes in Computer Science)","author":"Ertl Anton","unstructured":"Anton Ertl and Andreas Krall . 1991. Optimal instruction scheduling using constraint logic programming . In Programming Language Implementation and Logic Programming (Lecture Notes in Computer Science) , Vol. 528 . Springer , 75--86. Anton Ertl and Andreas Krall. 1991. Optimal instruction scheduling using constraint logic programming. In Programming Language Implementation and Logic Programming (Lecture Notes in Computer Science), Vol. 528. Springer, 75--86."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2011.10"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/339647.339682"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675827"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/800046.801649"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the International Symposium on Microarchitecture. IEEE, 245--256","author":"Fu Changqing","year":"2002","unstructured":"Changqing Fu and Kent Wilken . 2002 . A faster optimal register allocator . In Proceedings of the International Symposium on Microarchitecture. IEEE, 245--256 . Changqing Fu and Kent Wilken. 2002. A faster optimal register allocator. In Proceedings of the International Symposium on Microarchitecture. IEEE, 245--256."},{"key":"e_1_2_1_62_1","unstructured":"GCC2017. GCC the GNU Compiler Collection. Retrieved from: https:\/\/gcc.gnu.org\/.  GCC2017. GCC the GNU Compiler Collection. Retrieved from: https:\/\/gcc.gnu.org\/."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/261693.261706"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/127601.127609"},{"key":"e_1_2_1_65_1","volume-title":"Handbook of Constraint Programming, Francesca Rossi, Peter van Beek","author":"Gomes Carla","unstructured":"Carla Gomes and Toby Walsh . 2006. Randomness and structure . In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek , and Toby Walsh (Eds.). Elsevier , chapter 18, 639--664. Carla Gomes and Toby Walsh. 2006. Randomness and structure. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, chapter 18, 639--664."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55407"},{"key":"e_1_2_1_67_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_68_1","volume-title":"The Compiler Design Handbook","author":"Govindarajan R.","unstructured":"R. Govindarajan . 2007. Instruction scheduling . In The Compiler Design Handbook ( 2 nd ed.). CRC. R. Govindarajan. 2007. Instruction scheduling. In The Compiler Design Handbook (2nd ed.). CRC.","edition":"2"},{"key":"e_1_2_1_69_1","volume-title":"Gao","author":"Govindarajan R.","year":"1994","unstructured":"R. Govindarajan , Erik R. Altman , and Guang R . Gao . 1994 . A framework for resource-constrained rate-optimal software pipelining. In Vector and Parallel Processing (Lecture Notes in Computer Science), Vol. 854 . Springer , 640--651. R. Govindarajan, Erik R. Altman, and Guang R. Gao. 1994. A framework for resource-constrained rate-optimal software pipelining. In Vector and Parallel Processing (Lecture Notes in Computer Science), Vol. 854. Springer, 640--651."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/192724.192733"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1159750"},{"key":"e_1_2_1_72_1","volume-title":"Grewal et al","author":"Greenley D.","year":"1995","unstructured":"D. Greenley , J. Bauman , D. Chang , D. Chen , R. Eltejaein , P. Ferolito , P. Fu , R. Garner , D. Greenhill , H. Grewal et al . 1995 . UltraSPARC: The next generation superscalar 64-bit SPARC. In Digest of Papers. COMPCON\u201995. Technologies for the Information Superhighway. IEEE , 442--451. D. Greenley, J. Bauman, D. Chang, D. Chen, R. Eltejaein, P. Ferolito, P. Fu, R. Garner, D. Greenhill, H. Grewal et al. 1995. UltraSPARC: The next generation superscalar 64-bit SPARC. In Digest of Papers. COMPCON\u201995. Technologies for the Information Superhighway. IEEE, 442--451."},{"key":"e_1_2_1_73_1","volume-title":"Compiler Construction (Lecture Notes in Computer Science)","author":"Grund Daniel","unstructured":"Daniel Grund and Sebastian Hack . 2007. A fast cutting-plane algorithm for optimal coalescing . In Compiler Construction (Lecture Notes in Computer Science) , Vol. 4420 . Springer , 111--125. Daniel Grund and Sebastian Hack. 2007. A fast cutting-plane algorithm for optimal coalescing. In Compiler Construction (Lecture Notes in Computer Science), Vol. 4420. Springer, 111--125."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_20"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/11860990_21"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-005-2862-8"},{"key":"e_1_2_1_78_1","volume-title":"Patterson","author":"Hennessy John L.","year":"2011","unstructured":"John L. Hennessy and David A . Patterson . 2011 . Computer Architecture : A Quantitative Approach (5th ed.). Morgan Kaufmann . John L. Hennessy and David A. Patterson. 2011. Computer Architecture: A Quantitative Approach (5th ed.). Morgan Kaufmann."},{"key":"e_1_2_1_79_1","volume-title":"Modular Programming Languages (Lecture Notes in Computer Science)","author":"Hirnschrott Ulrich","unstructured":"Ulrich Hirnschrott , Andreas Krall , and Bernhard Scholz . 2003. Graph coloring vs. optimal register allocation for optimizing compilers . In Modular Programming Languages (Lecture Notes in Computer Science) , Vol. 2789 . Springer , 202--213. Ulrich Hirnschrott, Andreas Krall, and Bernhard Scholz. 2003. Graph coloring vs. optimal register allocation for optimizing compilers. In Modular Programming Languages (Lecture Notes in Computer Science), Vol. 2789. Springer, 202--213."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.5555\/2967117"},{"key":"e_1_2_1_81_1","volume-title":"Handbook of Constraint Programming, Francesca Rossi, Peter van Beek","author":"Hooker John N.","unstructured":"John N. Hooker . 2006. Operations research methods in constraint programming . In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek , and Toby Walsh (Eds.). Elsevier , chapter 15, 527--570. John N. Hooker. 2006. Operations research methods in constraint programming. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, chapter 15, 527--570."},{"key":"e_1_2_1_82_1","volume-title":"Integrated Methods for Optimization","author":"Hooker John N.","unstructured":"John N. Hooker . 2012. Integrated Methods for Optimization ( 2 nd ed.). Springer . John N. Hooker. 2012. Integrated Methods for Optimization (2nd ed.). Springer.","edition":"2"},{"key":"e_1_2_1_83_1","volume-title":"Hoos and Edward Tsang","author":"Holger","year":"2006","unstructured":"Holger H. Hoos and Edward Tsang . 2006 . Local search methods. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier , chapter 5, 135--168. Holger H. Hoos and Edward Tsang. 2006. Local search methods. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, chapter 5, 135--168."},{"key":"e_1_2_1_84_1","volume-title":"On sentences which are true of direct unions of algebras. Symbol. Logic 16, 1 (03","author":"Horn Alfred","year":"1951","unstructured":"Alfred Horn . 1951. On sentences which are true of direct unions of algebras. Symbol. Logic 16, 1 (03 1951 ), 14--21. Alfred Horn. 1951. On sentences which are true of direct unions of algebras. Symbol. Logic 16, 1 (03 1951), 14--21."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.75629"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205185"},{"key":"e_1_2_1_87_1","unstructured":"Infineon Technologies. 2017. Carmel. Retrieved from: https:\/\/www.infineon.com.  Infineon Technologies. 2017. Carmel. Retrieved from: https:\/\/www.infineon.com."},{"key":"e_1_2_1_88_1","unstructured":"Infineon Technologies. 2017. TriCore 1 Architecture Overview Handbook. Retrieved from: http:\/\/www.infineon.com\/dgdl\/TC1_3_ArchOverview_1.pdf?fileId&equals;db3a304312bae05f0112be86204c0111.  Infineon Technologies. 2017. TriCore 1 Architecture Overview Handbook. Retrieved from: http:\/\/www.infineon.com\/dgdl\/TC1_3_ArchOverview_1.pdf?fileId&equals;db3a304312bae05f0112be86204c0111."},{"key":"e_1_2_1_89_1","unstructured":"Intel Corporation. 2017. Intel 64 and IA-32 Architectures Software Developer Manuals. Retrieved from: https:\/\/software.intel.com\/en-us\/articles\/intel-sdm.  Intel Corporation. 2017. Intel 64 and IA-32 Architectures Software Developer Manuals. Retrieved from: https:\/\/software.intel.com\/en-us\/articles\/intel-sdm."},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/41625.41635"},{"key":"e_1_2_1_92_1","unstructured":"Gerry Kane. 1996. PA-RISC 2.0 Architecture. Prentice Hall.   Gerry Kane. 1996. PA-RISC 2.0 Architecture. Prentice Hall."},{"key":"e_1_2_1_94_1","volume-title":"PROPAN: A retargetable system for postpass optimisations and analyses. In Languages, Compilers, Tools and Theory for Embedded Systems (Lecture Notes in Computer Science)","author":"K\u00e4stner Daniel","year":"2001","unstructured":"Daniel K\u00e4stner . 2001 . PROPAN: A retargetable system for postpass optimisations and analyses. In Languages, Compilers, Tools and Theory for Embedded Systems (Lecture Notes in Computer Science) , Vol. 1985 . Springer , 63--80. Daniel K\u00e4stner. 2001. PROPAN: A retargetable system for postpass optimisations and analyses. In Languages, Compilers, Tools and Theory for Embedded Systems (Lecture Notes in Computer Science), Vol. 1985. Springer, 63--80."},{"key":"e_1_2_1_95_1","volume-title":"Compiler Construction (Lecture Notes in Computer Science)","author":"K\u00e4stner Daniel","unstructured":"Daniel K\u00e4stner and Marc Langenbach . 1999. Code optimization by integer linear programming . In Compiler Construction (Lecture Notes in Computer Science) , Vol. 1575 . Springer , 122--136. Daniel K\u00e4stner and Marc Langenbach. 1999. Code optimization by integer linear programming. In Compiler Construction (Lecture Notes in Computer Science), Vol. 1575. Springer, 122--136."},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(98)00002-2"},{"key":"e_1_2_1_97_1","volume-title":"Handbook of Signal Processing Systems","author":"Kessler Christoph","unstructured":"Christoph Kessler . 2010. Compiling for VLIW DSPs . In Handbook of Signal Processing Systems . Springer , 603--638. Christoph Kessler. 2010. Compiling for VLIW DSPs. In Handbook of Signal Processing Systems. Springer, 603--638."},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/384197.384219"},{"key":"e_1_2_1_99_1","doi-asserted-by":"publisher","DOI":"10.5555\/1152682.1152685"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.1987.1169716"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2005.4"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134006"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1145\/1543820.1543824"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.5555\/290940.291002"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907742"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626497000371"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.54022"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1145\/238997.239002"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_2_1_110_1","volume-title":"Proceedings of the International Symposium on Microarchitecture. IEEE, 330--335","author":"Lee Chunho","unstructured":"Chunho Lee , Miodrag Potkonjak , and William H . Mangione-Smith. 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems . In Proceedings of the International Symposium on Microarchitecture. IEEE, 330--335 . Chunho Lee, Miodrag Potkonjak, and William H. Mangione-Smith. 1997. MediaBench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the International Symposium on Microarchitecture. IEEE, 330--335."},{"key":"e_1_2_1_111_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.555991"},{"key":"e_1_2_1_112_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90102-9"},{"key":"e_1_2_1_114_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85958-1_7"},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213008003765"},{"key":"e_1_2_1_116_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.8.2.219"},{"key":"e_1_2_1_117_1","volume-title":"Livermore Fortran Kernels: A Computer Test of Numerical Performance Range","author":"McMahon Francis H.","unstructured":"Francis H. McMahon . 1986. Livermore Fortran Kernels: A Computer Test of Numerical Performance Range . Technical Report. Lawrence Livermore National Laboratory, Livermore, CA. Francis H. McMahon. 1986. Livermore Fortran Kernels: A Computer Test of Numerical Performance Range. Technical Report. Lawrence Livermore National Laboratory, Livermore, CA."},{"key":"e_1_2_1_118_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2003.1196114"},{"key":"e_1_2_1_120_1","volume-title":"Compiler Construction (Lecture Notes in Computer Science)","volume":"4420","author":"Nagarakatte Santosh G.","unstructured":"Santosh G. Nagarakatte and R. Govindarajan . 2007. Register allocation and optimal spill code scheduling in software pipelined loops using 0-1 integer linear programming formulation . In Compiler Construction (Lecture Notes in Computer Science) , Vol. 4420 . Springer, 126--140. Santosh G. Nagarakatte and R. Govindarajan. 2007. Register allocation and optimal spill code scheduling in software pipelined loops using 0-1 integer linear programming formulation. In Compiler Construction (Lecture Notes in Computer Science), Vol. 4420. Springer, 126--140."},{"key":"e_1_2_1_121_1","doi-asserted-by":"publisher","DOI":"10.1145\/513829.513851"},{"key":"e_1_2_1_122_1","volume-title":"The Compiler Design Handbook","author":"Nandivada V. Krishna","unstructured":"V. Krishna Nandivada . 2007. Advances in register allocation techniques . In The Compiler Design Handbook ( 2 nd ed.). CRC. V. Krishna Nandivada. 2007. Advances in register allocation techniques. In The Compiler Design Handbook (2nd ed.). CRC.","edition":"2"},{"key":"e_1_2_1_123_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509420.2509427"},{"key":"e_1_2_1_124_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_19"},{"key":"e_1_2_1_125_1","volume-title":"Fernando Magno Quint\u00e3o Pereira, and Jens Palsberg","author":"Nandivada V. Krishna","year":"2007","unstructured":"V. Krishna Nandivada , Fernando Magno Quint\u00e3o Pereira, and Jens Palsberg . 2007 . A framework for end-to-end verification and evaluation of register allocators. In Static Analysis (Lecture Notes in Computer Science), Vol. 4634 . Springer , 153--169. V. Krishna Nandivada, Fernando Magno Quint\u00e3o Pereira, and Jens Palsberg. 2007. A framework for end-to-end verification and evaluation of register allocators. In Static Analysis (Lecture Notes in Computer Science), Vol. 4634. Springer, 153--169."},{"key":"e_1_2_1_126_1","volume-title":"Wolsey","author":"Nemhauser George L.","year":"1999","unstructured":"George L. Nemhauser and Laurence A . Wolsey . 1999 . Integer and Combinatorial Optimization. Wiley . George L. Nemhauser and Laurence A. Wolsey. 1999. Integer and Combinatorial Optimization. Wiley."},{"key":"e_1_2_1_127_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-008-9064-x"},{"key":"e_1_2_1_129_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375609"},{"key":"e_1_2_1_130_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155114"},{"key":"e_1_2_1_131_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2009.74"},{"key":"e_1_2_1_132_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.16.1.93"},{"key":"e_1_2_1_135_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1972.5008918"},{"key":"e_1_2_1_136_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205181"},{"key":"e_1_2_1_137_1","first-page":"4","article-title":"Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing","volume":"12","author":"Ramakrishna Rau B.","year":"1981","unstructured":"B. Ramakrishna Rau and Christopher D. Glaeser . 1981 . Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing . ACM SIGMICRO Newslett. 12 , 4 (Dec. 1981), 183--198. B. Ramakrishna Rau and Christopher D. Glaeser. 1981. Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing. ACM SIGMICRO Newslett. 12, 4 (Dec. 1981), 183--198.","journal-title":"ACM SIGMICRO Newslett."},{"key":"e_1_2_1_138_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.275355"},{"key":"e_1_2_1_139_1","doi-asserted-by":"crossref","unstructured":"Hongbo Rong and R. Govindarajan. 2007. Advances in software pipelining. In The Compiler Design Handbook (2nd ed.). CRC.  Hongbo Rong and R. Govindarajan. 2007. Advances in software pipelining. In The Compiler Design Handbook (2nd ed.). CRC.","DOI":"10.1201\/9781420043839.ch20"},{"key":"e_1_2_1_140_1","unstructured":"Francesca Rossi Peter van Beek and Toby Walsh (Eds.). 2006. Handbook of Constraint Programming. Elsevier.   Francesca Rossi Peter van Beek and Toby Walsh (Eds.). 2006. Handbook of Constraint Programming. Elsevier."},{"key":"e_1_2_1_141_1","doi-asserted-by":"publisher","DOI":"10.1145\/359327.359336"},{"key":"e_1_2_1_142_1","doi-asserted-by":"publisher","DOI":"10.1145\/513829.513854"},{"key":"e_1_2_1_143_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512432"},{"key":"e_1_2_1_144_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2004.27"},{"key":"e_1_2_1_145_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498690.1498694"},{"key":"e_1_2_1_146_1","doi-asserted-by":"publisher","DOI":"10.1145\/996841.996875"},{"key":"e_1_2_1_147_1","unstructured":"Standard Performance Evaluation Corporation. 2017. SPEC CPU Benchmarks. Retrieved from: https:\/\/www.spec.org\/benchmarks.html.  Standard Performance Evaluation Corporation. 2017. SPEC CPU Benchmarks. Retrieved from: https:\/\/www.spec.org\/benchmarks.html."},{"key":"e_1_2_1_148_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349317"},{"key":"e_1_2_1_149_1","volume-title":"See MIPS Run","author":"Sweetman Dominic","unstructured":"Dominic Sweetman . 2006. See MIPS Run , Second Edition. Morgan Kaufmann . Dominic Sweetman. 2006. See MIPS Run, Second Edition. Morgan Kaufmann."},{"key":"e_1_2_1_150_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604139"},{"key":"e_1_2_1_151_1","unstructured":"Texas Instruments. 2017. TMS320C20x User\u2019s Guide. Retrieved from: http:\/\/www.ti.com\/lit\/ug\/spru127c\/spru127c.pdf.  Texas Instruments. 2017. TMS320C20x User\u2019s Guide. Retrieved from: http:\/\/www.ti.com\/lit\/ug\/spru127c\/spru127c.pdf."},{"key":"e_1_2_1_152_1","unstructured":"Texas Instruments. 2017. TMS320C62x DSP CPU and Instruction Set Reference Guide. Retrieved from: www.ti.com\/lit\/pdf\/spru731.  Texas Instruments. 2017. TMS320C62x DSP CPU and Instruction Set Reference Guide. Retrieved from: www.ti.com\/lit\/pdf\/spru731."},{"key":"e_1_2_1_154_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 , chapter 4, 85--134. Peter van Beek. 2006. Backtracking search algorithms. In Handbook of Constraint Programming, Francesca Rossi, Peter van Beek, and Toby Walsh (Eds.). Elsevier, chapter 4, 85--134."},{"key":"e_1_2_1_155_1","volume-title":"Principles and Practice of Constraint Programming (Lecture Notes in Computer Science)","author":"van Beek Peter","unstructured":"Peter van Beek and Kent Wilken . 2001. Fast optimal instruction scheduling for single-issue processors with arbitrary latencies . In Principles and Practice of Constraint Programming (Lecture Notes in Computer Science) , Vol. 2239 . Springer , 625--639. Peter van Beek and Kent Wilken. 2001. Fast optimal instruction scheduling for single-issue processors with arbitrary latencies. In Principles and Practice of Constraint Programming (Lecture Notes in Computer Science), Vol. 2239. Springer, 625--639."},{"key":"e_1_2_1_156_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 , chapter 6, 169--208. 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, chapter 6, 169--208."},{"key":"e_1_2_1_157_1","volume-title":"Linear Programming: Foundations and Extensions","author":"Vanderbei Robert J.","year":"2013","unstructured":"Robert J. Vanderbei . 2013 . Linear Programming: Foundations and Extensions . Springer . Robert J. Vanderbei. 2013. Linear Programming: Foundations and Extensions. Springer."},{"key":"e_1_2_1_158_1","volume-title":"Proceedings of the Conference on Signal Processing Applications and Technology. DSP Associates, 715--720","author":"\u017divojnovi\u0107 Vojin","year":"1994","unstructured":"Vojin \u017divojnovi\u0107 , Juan M. Velarde , Christian Schl\u00e4ger , and Heinrich Meyr . 1994 . DSPSTONE: A DSP-oriented benchmarking methodology . In Proceedings of the Conference on Signal Processing Applications and Technology. DSP Associates, 715--720 . Vojin \u017divojnovi\u0107, Juan M. Velarde, Christian Schl\u00e4ger, and Heinrich Meyr. 1994. DSPSTONE: A DSP-oriented benchmarking methodology. In Proceedings of the Conference on Signal Processing Applications and Technology. DSP Associates, 715--720."},{"key":"e_1_2_1_159_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800060205"},{"key":"e_1_2_1_160_1","unstructured":"Fredrik Wickberg and Mattias Eriksson. 2017. Outperforming state-of-the-art compilers in Unison. Ericsson research blog entry. Retrieved from: https:\/\/www.ericsson.com\/research-blog\/outperforming-state-art-compilers-unison\/.  Fredrik Wickberg and Mattias Eriksson. 2017. Outperforming state-of-the-art compilers in Unison. Ericsson research blog entry. Retrieved from: https:\/\/www.ericsson.com\/research-blog\/outperforming-state-art-compilers-unison\/."},{"key":"e_1_2_1_161_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349318"},{"key":"e_1_2_1_162_1","doi-asserted-by":"publisher","DOI":"10.5555\/254208.254233"},{"key":"e_1_2_1_163_1","volume-title":"Code Generation for Embedded Processors (Engineering and Computer Science)","author":"Wilson Tom","unstructured":"Tom Wilson , Gary Grewal , Shawn Henshall , and Dilip Banerji . 2002. An ILP-based approach to code generation . In Code Generation for Embedded Processors (Engineering and Computer Science) , Vol. 317 . Springer , 103--118. Tom Wilson, Gary Grewal, Shawn Henshall, and Dilip Banerji. 2002. An ILP-based approach to code generation. In Code Generation for Embedded Processors (Engineering and Computer Science), Vol. 317. Springer, 103--118."},{"key":"e_1_2_1_164_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977669"},{"key":"e_1_2_1_166_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331699.1331707"},{"key":"e_1_2_1_167_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.491460"},{"key":"e_1_2_1_168_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349319"},{"key":"e_1_2_1_170_1","unstructured":"Zilog Inc. 2017. Z8 CPU User Manual. Retrieved from: http:\/\/www.zilog.com\/docs\/um0016.pdf.  Zilog Inc. 2017. Z8 CPU User Manual. Retrieved from: http:\/\/www.zilog.com\/docs\/um0016.pdf."}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3200920","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3200920","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:30Z","timestamp":1750213590000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3200920"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,18]]},"references-count":154,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5,31]]}},"alternative-id":["10.1145\/3200920"],"URL":"https:\/\/doi.org\/10.1145\/3200920","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,18]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}