{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,30]],"date-time":"2026-10-30T21:48:28Z","timestamp":1793396908578,"version":"4.5.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,9,16]],"date-time":"2013-09-16T00:00:00Z","timestamp":1379289600000},"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. Archit. Code Optim."],"published-print":{"date-parts":[[2013,9,16]]},"abstract":"<jats:p>Balancing Instruction-Level Parallelism (ILP) and register pressure during preallocation instruction scheduling is a fundamentally important problem in code generation and optimization. The problem is known to be NP-complete. Many heuristic techniques have been proposed to solve this problem. However, due to the inherently conflicting requirements of maximizing ILP and minimizing register pressure, heuristic techniques may produce poor schedules in many cases. If such cases occur in hot code, significant performance degradation may result. A few combinatorial optimization approaches have also been proposed, but none of them has been shown to solve large real-world instances within reasonable time. This article presents the first combinatorial algorithm that is efficient enough to optimally solve large instances of this problem (basic blocks with hundreds of instructions) within a few seconds per instance. The proposed algorithm uses branch-and-bound enumeration with a number of powerful pruning techniques to efficiently search the solution space. The search is based on a cost function that incorporates schedule length and register pressure. An implementation of the proposed scheduling algorithm has been integrated into the LLVM Compiler and evaluated using SPEC CPU 2006. On x86-64, with a time limit of 10ms per instruction, it optimally schedules 79% of the hot basic blocks in FP2006. Another 19% of the blocks are not optimally scheduled but are improved in cost relative to LLVM's heuristic. This improves the execution time of some benchmarks by up to 21%, with a geometric-mean improvement of 2.4% across the entire benchmark suite. With the use of precise latency information, the geometric-mean improvement is increased to 2.8%.<\/jats:p>","DOI":"10.1145\/2512432","type":"journal-article","created":{"date-parts":[[2013,9,23]],"date-time":"2013-09-23T13:47:05Z","timestamp":1379944025000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Preallocation instruction scheduling with register pressure minimization using a combinatorial optimization approach"],"prefix":"10.1145","volume":"10","author":[{"given":"Ghassan","family":"Shobaki","sequence":"first","affiliation":[{"name":"Princess Sumaya University for Technology, Jordan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maxim","family":"Shawabkeh","sequence":"additional","affiliation":[{"name":"Google"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Najm Eldeen Abu","family":"Rmaileh","sequence":"additional","affiliation":[{"name":"Princess Sumaya University for Technology, Jordan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,9,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 9th Workshop on Optimizations for DSP and Embedded Systems (ODES'11)","author":"Barany G.","year":"2011"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_2"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the IFIP Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism. 243--254","author":"Berson D."},{"key":"e_1_2_1_4_1","unstructured":"Cooper K. and Torczon L. 2004. Engineering a Compiler. Morgan Kaufmann San Fransisco CA.   Cooper K. and Torczon L. 2004. Engineering a Compiler. Morgan Kaufmann San Fransisco CA."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.964443"},{"key":"e_1_2_1_6_1","unstructured":"Fog A. 2012. The micro-architecture of INTEL AMD and VIA cpus. An optimization guide for assembly programmers and compiler makers. http:\/\/www.agner.org\/optimize\/microarchitecture.pdf.  Fog A. 2012. The micro-architecture of INTEL AMD and VIA cpus. An optimization guide for assembly programmers and compiler makers. http:\/\/www.agner.org\/optimize\/microarchitecture.pdf."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55407"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1159750"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 4th International Symposium on High-Performance Computer Architecture (HPCA'98)","author":"Havanki W."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(98)00002-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/238997.239002"},{"key":"e_1_2_1_12_1","unstructured":"Malik A. 2008. Constraint programming techniques for optimal instruction scheduling. Ph.D. thesis University of Waterloo. https:\/\/cs.uwaterloo.ca\/&sim;vanbeek\/Publications\/malik.pdf.   Malik A. 2008. Constraint programming techniques for optimal instruction scheduling. Ph.D. thesis University of Waterloo. https:\/\/cs.uwaterloo.ca\/&sim;vanbeek\/Publications\/malik.pdf."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.275355"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2004.27"},{"key":"e_1_2_1_15_1","unstructured":"Shobaki G. 2006. Optimal global instruction scheduling using enumeration. Ph.D. dissertation Department of Computer Science UC Davis. http:\/\/www.cs.ucdavis.edu\/research\/tech-reports\/2006\/CSE-2006-19.pdf.   Shobaki G. 2006. Optimal global instruction scheduling using enumeration. Ph.D. dissertation Department of Computer Science UC Davis. http:\/\/www.cs.ucdavis.edu\/research\/tech-reports\/2006\/CSE-2006-19.pdf."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498690.1498694"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-005-6466-x"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1241601.1241621"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331699.1331707"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2512432","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2512432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:59Z","timestamp":1750231739000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2512432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,16]]},"references-count":19,"aliases":["10.1145\/2509420.2512432"],"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9,16]]}},"alternative-id":["10.1145\/2512432"],"URL":"https:\/\/doi.org\/10.1145\/2512432","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,16]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}