{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:36:58Z","timestamp":1775054218456,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["621-2011-6229"],"award-info":[{"award-number":["621-2011-6229"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>In code generation, instruction selection chooses processor instructions to implement a program under compilation where code quality crucially depends on the choice of instructions. Using methods from combinatorial optimization, this paper proposes an expressive model that integrates global instruction selection with global code motion. The model introduces (1) handling of memory computations and function calls, (2) a method for inserting additional jump instructions where necessary, (3) a dependency-based technique to ensure correct combinations of instructions, (4) value reuse to improve code quality, and (5) an objective function that reduces compilation time and increases scalability by exploiting bounding techniques. The approach is demonstrated to be complete and practical, competitive with LLVM, and potentially optimal (w.r.t. the model) for medium-sized functions. The results show that combinatorial optimization for instruction selection is well-suited to exploit the potential of modern processors in embedded systems.<\/jats:p>","DOI":"10.1145\/3126528","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T12:33:53Z","timestamp":1506515633000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Complete and Practical Universal Instruction Selection"],"prefix":"10.1145","volume":"16","author":[{"given":"Gabriel Hjort","family":"Blindell","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology and RISE SICS, Kista, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mats","family":"Carlsson","sequence":"additional","affiliation":[{"name":"RISE SICS, Uppsala, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto Casta\u00f1eda","family":"Lozano","sequence":"additional","affiliation":[{"name":"RISE SICS and KTH Royal Institute of Technology, Kista, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Schulte","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology and RISE SICS, Kista, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"URL: http:\/\/www.cpubenchmark.net\/singleThread.html, updated","author":"Single Thread Performance CPU","year":"2017","unstructured":"CPU Benchmarks -- Single Thread Performance . PassMark Software . URL: http:\/\/www.cpubenchmark.net\/singleThread.html, updated June 2, 2017 . CPU Benchmarks -- Single Thread Performance. PassMark Software. URL: http:\/\/www.cpubenchmark.net\/singleThread.html, updated June 2, 2017."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/69558.75700"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/567067.567085"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSD.2013.91"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168857.1168906"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/309847.310076"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"A. Bednarski and C. W. Kessler. 2006. Optimal Integrated VLIW Code Generation with Integer Linear Programming. 2006.  A. Bednarski and C. W. Kessler. 2006. Optimal Integrated VLIW Code Generation with Integer Linear Programming. 2006.","DOI":"10.1007\/11823285_48"},{"key":"e_1_2_1_9_1","volume-title":"Springer","author":"Boender J.","year":"2014","unstructured":"J. Boender and C. S. Coen . 2014. On the Correctness of a Branch Displacement Algorithm. In TACAS\u201914. 605--619 . Springer , 2014 . J. Boender and C. S. Coen. 2014. On the Correctness of a Branch Displacement Algorithm. In TACAS\u201914. 605--619. Springer, 2014."},{"key":"e_1_2_1_10_1","volume-title":"Optgen: A Generator for Local Optimizations. In CC\u201915. 171--189","author":"Buchwald S.","year":"2015","unstructured":"S. Buchwald . 2015 . Optgen: A Generator for Local Optimizations. In CC\u201915. 171--189 . Springer , 2015. S. Buchwald. 2015. Optgen: A Generator for Local Optimizations. In CC\u201915. 171--189. Springer, 2015."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1878921.1878926"},{"key":"e_1_2_1_12_1","volume-title":"CP\u201912. 750--766","author":"Lozano R. C.","unstructured":"R. C. Lozano , M. Carlsson , F. Drejhammar , and C. Schulte . Constraint-based Register Allocation and Instruction Scheduling . In CP\u201912. 750--766 . Springer . R. C. Lozano, M. Carlsson, F. Drejhammar, and C. Schulte. Constraint-based Register Allocation and Instruction Scheduling. In CP\u201912. 750--766. Springer."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597809.2597815"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207154"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375657.1375663"},{"key":"e_1_2_1_19_1","volume-title":"ACM","author":"Eckstein E.","year":"2003","unstructured":"E. Eckstein , O. K\u00f6nig , and B. Scholz . 2003. Code Instruction Selection Based on SSA-Graphs. In SCOPES\u201903. 49--65 . ACM , 2003 . E. Eckstein, O. K\u00f6nig, and B. Scholz. 2003. Code Instruction Selection Based on SSA-Graphs. In SCOPES\u201903. 49--65. ACM, 2003."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/292540.292562"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1133988"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675827"},{"key":"e_1_2_1_23_1","volume-title":"IEEE","author":"Floch A.","year":"2010","unstructured":"A. Floch , C. Wolinski , and K. Kuchcinski . 2010. Combined Scheduling and Instruction Selection for Processors with Reconfigurable Cell Fabric. In ASAP\u201910. 167--174 . IEEE , 2010 . A. Floch, C. Wolinski, and K. Kuchcinski. 2010. Combined Scheduling and Instruction Selection for Processors with Reconfigurable Cell Fabric. In ASAP\u201910. 167--174. IEEE, 2010."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/131080.131089"},{"key":"e_1_2_1_25_1","volume-title":"Code Size, Estimated Energy. In ISSS\u201997. 41--47","author":"Gebotys C. H.","year":"1997","unstructured":"C. H. Gebotys . 1997. An Efficient Model for DSP Code Generation: Performance , Code Size, Estimated Energy. In ISSS\u201997. 41--47 . IEEE , 1997 . C. H. Gebotys. 1997. An Efficient Model for DSP Code Generation: Performance, Code Size, Estimated Energy. In ISSS\u201997. 41--47. IEEE, 1997."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/200994.201003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/143095.143146"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2967117"},{"key":"e_1_2_1_29_1","volume-title":"Springer","author":"Blindell G. H.","year":"2015","unstructured":"G. H. Blindell , R. C. Lozano , M. Carlsson , and C. Schulte . 2015. Modeling Universal Instruction Selection. In CP\u201915. 609--626 . Springer , 2015 . G. H. Blindell, R. C. Lozano, M. Carlsson, and C. Schulte. 2015. Modeling Universal Instruction Selection. In CP\u201915. 609--626. Springer, 2015."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204007"},{"key":"e_1_2_1_31_1","volume-title":"Springer","author":"Johnson N.","year":"2003","unstructured":"N. Johnson and A. Mycroft . 2003. Combined Code Motion and Register Allocation Using the Value State Dependence Graph. In CC\u201903. 1--16 . Springer , 2003 . N. Johnson and A. Mycroft. 2003. Combined Code Motion and Register Allocation Using the Value State Dependence Graph. In CC\u201903. 1--16. Springer, 2003."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2443608.2443611"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356058.1356065"},{"key":"e_1_2_1_34_1","volume-title":"Econometrica: Journal of the Econometric Society 497--520","author":"Land A. H.","year":"1960","unstructured":"A. H. Land and A. G. Doig . 1960 . An automatic method of solving discrete programming problems. Econometrica: Journal of the Econometric Society 497--520 , 1960. A. H. Land and A. G. Doig. 1960. An automatic method of solving discrete programming problems. Econometrica: Journal of the Econometric Society 497--520, 1960."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/349299.349320"},{"key":"e_1_2_1_36_1","volume-title":"IEEE\/ACM International Symposium on Code Generation and Optimization. 75--86","author":"Lattner C.","year":"2004","unstructured":"C. Lattner and V. Adve . 2004. LLVM: A Compilation Framework for Lifelong Program Analysis 8 Transformation . In IEEE\/ACM International Symposium on Code Generation and Optimization. 75--86 . IEEE, 2004 . C. Lattner and V. Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis 8 Transformation. In IEEE\/ACM International Symposium on Code Generation and Optimization. 75--86. IEEE, 2004."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(78)90029-2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-006-7095-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11889205_22"},{"key":"e_1_2_1_40_1","volume-title":"IEEE","author":"Lee C.","year":"1997","unstructured":"C. Lee , M. Potkonjak , and W. H. Mangione-Smith . 1997. MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems. In MICRO\u201997. 330--335 . IEEE , 1997 . C. Lee, M. Potkonjak, and W. H. Mangione-Smith. 1997. MediaBench: A Tool for Evaluating and Synthesizing Multimedia and Communications Systems. In MICRO\u201997. 330--335. IEEE, 1997."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/343647.343679"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254106"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737965"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASAP.2009.19"},{"key":"e_1_2_1_45_1","volume-title":"Springer","author":"Nethercote N.","year":"2007","unstructured":"N. Nethercote , P. J. Stuckey , R. Becket , S. Brand , G. J. Duck , and G. Tack . 2007. MiniZinc: Towards a Standard CP Modelling Language. In CP\u201907. 529--543 . Springer , 2007 . N. Nethercote, P. J. Stuckey, R. Becket, S. Brand, G. J. Duck, and G. Tack. 2007. MiniZinc: Towards a Standard CP Modelling Language. In CP\u201907. 529--543. Springer, 2007."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73586"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPASS.2005.1430555"},{"key":"e_1_2_1_48_1","unstructured":"Hexagon V5\/V55 Programmer\u2019s Reference Manual. Qualcomm Technologies Inc. 80-N2040-8 Rev. A.  Hexagon V5\/V55 Programmer\u2019s Reference Manual. Qualcomm Technologies Inc. 80-N2040-8 Rev. A."},{"key":"e_1_2_1_49_1","unstructured":"F. Rossi P. van Beek and T. Walsh. 2006. Handbook of Constraint Programming. Elsevier Science Inc. 2006. ISBN 0-444-52726-5.   F. Rossi P. van Beek and T. Walsh. 2006. Handbook of Constraint Programming. Elsevier Science Inc. 2006. ISBN 0-444-52726-5."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/377792.377849"},{"key":"e_1_2_1_51_1","volume-title":"Springer","author":"Tanaka H.","year":"2013","unstructured":"H. Tanaka , S. Kobayashi , Y. Takeuchi , K. Sakanushi , and M. Imai . 2013. A Code Selection Method for SIMD Processors with PACK Instructions. In SCOPES\u201903. 66--80 . Springer , 2013 . H. Tanaka, S. Kobayashi, Y. Takeuchi, K. Sakanushi, and M. Imai. 2013. A Code Selection Method for SIMD Processors with PACK Instructions. In SCOPES\u201903. 66--80. Springer, 2013."},{"key":"e_1_2_1_52_1","volume-title":"Miller Freeman","author":"\u017divojnovi\u0107 V.","year":"1994","unstructured":"V. \u017divojnovi\u0107 , J. M. Velarde , C. Schl\u00e4ger , and H. Meyr . 1994. DSPstone: A DSP-Oriented Benchmarking Methodology. In ICSPAT\u201994. 715--720 . Miller Freeman , 1994 . V. \u017divojnovi\u0107, J. M. Velarde, C. Schl\u00e4ger, and H. Meyr. 1994. DSPstone: A DSP-Oriented Benchmarking Methodology. In ICSPAT\u201994. 715--720. Miller Freeman, 1994."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155118"},{"key":"e_1_2_1_54_1","volume-title":"IEEE","author":"Wilson T.","year":"1994","unstructured":"T. Wilson , G. Grewal , B. Halley , and D. Banerji . 1994. An Integrated Approach to Retargetable Code Generation. In ISSS\u201994. 70--75 . IEEE , 1994 . T. Wilson, G. Grewal, B. Halley, and D. Banerji. 1994. An Integrated Approach to Retargetable Code Generation. In ISSS\u201994. 70--75. IEEE, 1994."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126528","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:02Z","timestamp":1750273502000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":53,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3126528"],"URL":"https:\/\/doi.org\/10.1145\/3126528","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,27]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}