Combinatorial register allocation and instruction scheduling
2019 (English)In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 41, no 3, article id 17Article in journal (Refereed) Published
Abstract [en]
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 in practice: it captures the complete set of program transformations used in state-of-the-art compilers, scales to medium-sized functions of up to 1,000 instructions, and generates executable 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. 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 1.1% to 10% and mean code size reduction ranges from 1.3% to 3.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. 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.
Place, publisher, year, edition, pages
Association for Computing Machinery , 2019. Vol. 41, no 3, article id 17
Keywords [en]
Combinatorial optimization, Instruction scheduling, Register allocation
National Category
Natural Sciences
Identifiers
URN: urn:nbn:se:ri:diva-39654DOI: 10.1145/3332373Scopus ID: 2-s2.0-85068443848OAI: oai:DiVA.org:ri-39654DiVA, id: diva2:1341034
Note
Funding details: Vetenskapsrådet, VR, 621-2011-6229; Funding text 1: This article is partially based on preliminary work presented at the Principles and Practice of Constraint Programming (2012) [20]; Languages, Compilers, and Tools for Embedded Systems (2014) [21]; and Compiler Construction (2016) [22]conferences. Compared to the preliminary work, this article is completely restructured and rewritten, completes the combinatorial model with rematerialization, proposes extensions to capture additional program transformations and processor-specific features, and contributes a more exhaustive evaluation. Additions to the evaluation include more benchmarks and processors, evidence of the fundamental benefit of the integrated approach, an in-depth study of scalability, and actual execution measurements. This work has been partially funded by Ericsson AB and the Swedish Research Council (VR) under grant 621-2011-6229. Authors’ addresses: R. C. Lozano, RISE SICS, Electrum 229, Kista, 164 40, Sweden, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden; email: roberto.castaneda@ri.se; M. Carlsson, RISE SICS, Electrum 229, Kista, 164 40, Sweden; email: mats.carlsson@ri.se; G. H. Blindell, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden; email: ghb@kth.se; C. Schulte, KTH Royal Institute of Technology, School of Electrical Engineering and Computer Science, Electrum 229, Kista, 164 40, Sweden, RISE SICS, Electrum 229, Kista, 164 40, Sweden; email: cschulte@kth.se. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2019 Association for Computing Machinery. 0164-0925/2019/07-ART17 $15.00 https://doi.org/10.1145/3332373
2019-08-072019-08-072023-05-05Bibliographically approved