Change search
Link to record
Permanent link

Direct link
BETA
Castañeda Lozano, RobertoORCID iD iconorcid.org/0000-0002-2806-7333
Alternative names
Publications (10 of 11) Show all publications
Castañeda Lozano, R. (2018). Constraint-Based Register Allocation and Instruction Scheduling. (Doctoral dissertation). Stockholm: KTH Royal Institute of Technology
Open this publication in new window or tab >>Constraint-Based Register Allocation and Instruction Scheduling
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Register allocation (mapping variables to processor registers or memory) and instruction scheduling (reordering instructions to improve latency or throughput) are central compiler problems. This dissertation proposes a combinatorial optimization approach to these problems that delivers optimal solutions according to a model, captures trade-offs between conflicting decisions, accommodates processor-specific features, and handles different optimization criteria.

The use of constraint programming and a novel program representation enables a compact model of register allocation and instruction scheduling. The model captures the complete set of global register allocation subproblems (spilling, assignment, live range splitting, coalescing, load-store optimization, multi-allocation, register packing, and rematerialization) as well as additional subproblems that handle processor-specific features beyond the usual scope of conventional compilers.

The approach is implemented in Unison, an open-source tool used in industry and research that complements the state-of-the-art LLVM compiler. Unison applies general and problem-specific constraint solving methods to scale to medium-sized functions, solving functions of up to 647 instructions optimally and improving functions of up to 874 instructions. The approach is evaluated experimentally using different processors (Hexagon, ARM and MIPS), benchmark suites (MediaBench and SPEC CPU2006), and optimization criteria (speed and code size reduction). The results show that Unison generates code of slightly to significantly better quality than LLVM, depending on the characteristics of the targeted processor (1% to 9.3% mean estimated speedup; 0.8% to 3.9% mean code size reduction). Additional experiments for Hexagon show that its estimated speedup has a strong monotonic relationship to the actual execution speedup, resulting in a mean speedup of 5.4% across MediaBench applications.

The approach contributed by this dissertation is the first of its kind that is practical (it captures the complete set of subproblems, scales to medium-sized functions, and generates executable code) and effective (it generates better code than the LLVM compiler, fulfilling the promise of combinatorial optimization). It can be applied to trade compilation time for code quality beyond the usual optimization levels, explore and exploit processor-specific features, and identify improvement opportunities in conventional compilers.

Abstract [sv]

Registerallokering (tilldelning av programvariabler till processorregister eller minne) och instruktionsschemaläggning (omordning av instruktioner för att förbättra latens eller genomströmning) är centrala kompilatorproblem. Denna avhandling presenterar en kombinatorisk optimeringsmetod för dessa problem. Metoden, som är baserad på en formell modell, är kraftfull nog att ge optimala lösningar och göra avvägningar mellan motstridiga optimeringsval. Den kan till fullo uttnyttja processorspecifika funktioner och uttrycka olika optimeringsmål.

Användningen av villkorsprogrammering och en ny programrepresentation möjliggör en kompakt modell av registerallokering och instruktionsschemaläggning. Modellen omfattar samtliga delproblem som ingår i global registerallokering: spilling, tilldelning, live range splitting, coalescing, load-store-optimering, flertilldelning, registerpackning och rematerialisering. Förutom dessa, kan den också integrera processorspecifika egenskaper som går utanför vad konventionella kompilatorer hanterar.

Metoden implementeras i Unison, ett öppen-källkods-verktyg som används inom industri- och forskningsvärlden och utgör ett komplement till LLVM-kompilatorn. Unison tillämpar allmänna och problemspecifika villkorslösningstekniker för att skala till medelstora funktioner, lösa funktioner med upp till 647 instruktioner optimalt och förbättra funktioner på upp till 874 instruktioner. Metoden utvärderas experimentellt för olika målprocessorer (Hexagon, ARM och MIPS), benchmark-sviter (MediaBench och SPEC CPU2006) och optimeringsmål (hastighet och kodstorlek). Resultaten visar att Unison genererar kod av något till betydligt bättre kvalitet än LLVM. Den uppskattade hastighetsförbättringen varierar mellan 1% till 9.3% och kodstorleksreduktionen mellan 0.8% till~3.9%, beroende på målprocessor. Ytterligare experiment för Hexagon visar att dess uppskattade hastighetsförbättring har ett starkt monotoniskt förhållande till den faktiska exekveringstiden, vilket resulterar i en 5.4% genomsnittlig hastighetsförbättring för MediaBench-applikationer.

Denna avhandling beskriver den första praktiskt användbara kombinatoriska optimeringsmetoden för integrerad registerallokering och instruktionsschemaläggning. Metoden är praktiskt användbar då den hanterar samtliga ingående delproblem, genererar exekverbar maskinkod och skalar till medelstora funktioner. Den är också effektiv då den genererar bättre maskinkod än LLVM-kompilatorn. Metoden kan tillämpas för att byta kompileringstid mot kodkvalitet utöver de vanliga optimeringsnivåerna, utforska och utnyttja processorspecifika egenskaper samt identifiera förbättringsmöjligheter i konventionella kompilatorer.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2018. p. 60
Series
TRITA-EECS-AVL ; 2018:48
Series
SICS Dissertation Series, ISSN 1101-1335 ; 78
Keywords
constraint programming, combinatorial optimization, register allocation, instruction scheduling, compiler construction
National Category
Computer Systems Computer Sciences
Research subject
Information and Communication Technology
Identifiers
urn:nbn:se:kth:diva-232192 (URN)978-91-7729-853-3 (ISBN)
Public defence
2018-09-03, Sal Ka-208, Electrum, Kistagången 16, Kista, Stockholm, 13:15 (English)
Opponent
Supervisors
Note

QC 20180716

Available from: 2018-07-16 Created: 2018-07-13 Last updated: 2018-07-26Bibliographically approved
Castañeda Lozano, R. & Schulte, C. (2018). Survey on Combinatorial Register Allocation and Instruction Scheduling. ACM Computing Surveys
Open this publication in new window or tab >>Survey on Combinatorial Register Allocation and Instruction Scheduling
2018 (English)In: ACM Computing Surveys, ISSN 0360-0300, E-ISSN 1557-7341Article in journal (Refereed) In press
Abstract [en]

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 last 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.

This paper 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.

Place, publisher, year, edition, pages
ACM Press, 2018
National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-232189 (URN)
Funder
Swedish Research Council, 621-2011-6229
Note

QC 20180823

Available from: 2018-07-13 Created: 2018-07-13 Last updated: 2018-12-11Bibliographically approved
Hjort Blindell, G., Carlsson, M., Castañeda Lozano, R. & Schulte, C. (2017). Complete and Practical Universal Instruction Selection. Paper presented at International Conferences on Compilers, Architectures and Synthesis for Embedded Systems. ACM Transactions on Embedded Computing Systems
Open this publication in new window or tab >>Complete and Practical Universal Instruction Selection
2017 (English)In: ACM Transactions on Embedded Computing Systems, ISSN 1539-9087, E-ISSN 1558-3465Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
ACM Press, 2017
Keywords
instruction selection, code generation, constraint programming, combinatorial optimization
National Category
Computer Systems Embedded Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-213968 (URN)10.1145/3126528 (DOI)000414353800002 ()2-s2.0-85030692980 (Scopus ID)
Conference
International Conferences on Compilers, Architectures and Synthesis for Embedded Systems
Funder
Swedish Research Council, 621-2011-6229
Note

QC 20170908

Available from: 2017-09-07 Created: 2017-09-07 Last updated: 2018-01-03Bibliographically approved
Castañeda Lozano, R., Carlsson, M., Hjort Blindell, G. & Schulte, C. (2016). Register allocation and instruction scheduling in Unison. In: Proceedings of CC 2016: The 25th International Conference on Compiler Construction. Paper presented at 25th International Conference on Compiler Construction, CC 2016, Barcelona, Spain, 17 March 2016 through 18 March 2016 (pp. 263-264). Association for Computing Machinery (ACM)
Open this publication in new window or tab >>Register allocation and instruction scheduling in Unison
2016 (English)In: Proceedings of CC 2016: The 25th International Conference on Compiler Construction, Association for Computing Machinery (ACM), 2016, p. 263-264Conference paper, Published paper (Refereed)
Abstract [en]

This paper describes Unison, a simple, flexible, and potentially optimal software tool that performs register allocation and instruction scheduling in integration using combinatorial optimization. The tool can be used as an alternative or as a complement to traditional approaches, which are fast but complex and suboptimal. Unison is most suitable whenever high-quality code is required and longer compilation times can be tolerated (such as in embedded systems or library releases), or the targeted processors are so irregular that traditional compilers fail to generate satisfactory code.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2016
Keywords
Combinatorial optimization, Instruction scheduling, Register allocation
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-183393 (URN)10.1145/2892208.2892237 (DOI)000389808800026 ()2-s2.0-84966560429 (Scopus ID)9781450342414 (ISBN)
Conference
25th International Conference on Compiler Construction, CC 2016, Barcelona, Spain, 17 March 2016 through 18 March 2016
Note

QC 20161122

Available from: 2016-03-09 Created: 2016-03-09 Last updated: 2018-07-13Bibliographically approved
Lozano, R. C., Carlsson, M., Hjort Blindell, G. & Schulte, C. (2014). Combinatorial Spill Code Optimization and Ultimate Coalescing. SIGPLAN notices, 49(5), 23-32
Open this publication in new window or tab >>Combinatorial Spill Code Optimization and Ultimate Coalescing
2014 (English)In: SIGPLAN notices, ISSN 0362-1340, E-ISSN 1558-1160, Vol. 49, no 5, p. 23-32Article in journal (Refereed) Published
Abstract [en]

This paper presents a novel combinatorial model that integrates global register allocation based on ultimate coalescing, spill code optimization, register packing, and multiple register banks with instruction scheduling (including VLIW). The model exploits alternative temporaries that hold the same value as a new concept for ultimate coalescing and spill code optimization. The paper presents Unison as a code generator based on the model and advanced solving techniques using constraint programming. Thorough experiments using MediaBench and a processor (Hexagon) that are typical for embedded systems demonstrate that Unison: is robust and scalable; generates faster code than LLVM (up to 4 1 % with a mean improvement of 7 %); possibly generates optimal code (for 2 9 % of the experiments); effortlessly supports different optimization criteria (code size on par with LLVM). Unison is significant as it addresses the same aspects as traditional code generation algorithms, yet is based on a simple integrated model and robustly can generate optimal code.

Keywords
spill code optimization, ultimate coalescing, combinatorial optimization, register allocation, instruction scheduling
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-154398 (URN)10.1145/2597809.2597815 (DOI)000341937800004 ()2-s2.0-84905660668 (Scopus ID)
Funder
Swedish Research Council, VR 621-2011-6229
Note

QC 20141021

Available from: 2014-10-21 Created: 2014-10-20 Last updated: 2018-07-13Bibliographically approved
Castañeda Lozano, R. (2014). Integrated Register Allocation and Instruction Scheduling with Constraint Programming. (Licentiate dissertation). Stockholm, Sweden: KTH Royal Institute of Technology
Open this publication in new window or tab >>Integrated Register Allocation and Instruction Scheduling with Constraint Programming
2014 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This dissertation proposes a combinatorial model, program representations, and constraint solving techniques for integrated register allocation and instruction scheduling in compiler back-ends. In contrast to traditional compilers based on heuristics, the proposed approach generates potentially optimal code by considering all trade-offs between interdependent decisions as a single optimization problem.

The combinatorial model is the first to handle a wide array of global register allocation subtasks, including spill code optimization, ultimate coalescing, register packing, and register bank assignment, as well as instruction scheduling for Very Long Instruction Word (VLIW) processors. The model is based on three novel, complementary program representations: Linear Static Single Assignment for global register allocation; copy extension for spilling, basic coalescing, and register bank assignment; and alternative temporaries for spill code optimization and ultimate coalescing. Solving techniques are proposed that exploit the program representation properties for scalability.

The model, program representations, and solving techniques are implemented in Unison, a code generator that delivers potentially optimal code while scaling to medium-size functions. Thorough experiments show that Unison: generates faster code (up to 41% with a mean improvement of 7%) than LLVM (a state-of-the-art compiler) for Hexagon (a challenging VLIW processor), generates code that is competitive with LLVM for MIPS32 (a simpler RISC processor), is robust across different benchmarks such as MediaBench and SPECint 2006, scales up to medium-size functions of up to 1000 instructions, and adapts easily to different optimization criteria.

The contributions of this dissertation are significant. They lead to a combinatorial approach for integrated register allocation and instruction scheduling that is, for the first time, practical (it robustly scales to medium-size functions) and effective (it yields better code than traditional heuristic approaches).

Place, publisher, year, edition, pages
Stockholm, Sweden: KTH Royal Institute of Technology, 2014. p. 48
Series
TRITA-ICT-ECS AVH, ISSN 1653-6363 ; 14:13
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-154599 (URN)978-91-7595-311-3 (ISBN)
Presentation
2014-11-27, Sal A, Electrum, Kistagången 16, Kista, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20141117

Available from: 2014-11-17 Created: 2014-10-24 Last updated: 2018-01-11Bibliographically approved
Mallach, S. & Castañeda Lozano, R. (2014). Optimal General Offset Assignment. In: Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014: . Paper presented at 17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014; Schloss RheinfelsSt. Goar; Germany; 10 June 2014 - 11 June 2014.
Open this publication in new window or tab >>Optimal General Offset Assignment
2014 (English)In: Proceedings of the 17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014, 2014Conference paper, Published paper (Refereed)
Abstract [en]

We present an exact approach to the General Offset Assignment problem arising in the domain of address code generation for application specific and digital signal processors. General Offset Assignment is composed of two subproblems, namely to find a permutation of variables in memory and to select a responsible address register for each access to one of these variables. Our method is a combination of established techniques to solve both subproblems using integer linear programming. To the best of our knowledge, it is the first approach capable of solving almost all instances of the established OffsetStone benchmark set to global optimality within reasonable time. We provide a first comprehensive evaluation of the quality of several state-of-the-art heuristics relative to the optimal solutions.

National Category
Computer Systems Embedded Systems
Identifiers
urn:nbn:se:kth:diva-144903 (URN)10.1145/2609248.2609251 (DOI)2-s2.0-84908895295 (Scopus ID)978-145032941-5 (ISBN)
Conference
17th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2014; Schloss RheinfelsSt. Goar; Germany; 10 June 2014 - 11 June 2014
Note

QC 20150410

Available from: 2014-05-02 Created: 2014-05-02 Last updated: 2015-04-10Bibliographically approved
Castañeda Lozano, R. & Schulte, C. (2014). Survey on Combinatorial Register Allocation and Instruction Scheduling.
Open this publication in new window or tab >>Survey on Combinatorial Register Allocation and Instruction Scheduling
2014 (English)Report (Other academic)
Abstract [en]

Register allocation and instruction scheduling are two central compiler back-end problems that are critical for quality. In the last two decades, combinatorial optimization has emerged as an alternative approach to traditional, heuristic algorithms for these problems. Combinatorial approaches are generally slower but more flexible than their heuristic counterparts and have the potential to generate optimal code. This paper surveys existing literature on combinatorial register allocation and instruction scheduling. The survey covers approaches that solve each problem in isolation as well as approaches that integrate both problems. The latter have the potential to generate code that is globally optimal by capturing the trade-off between conflicting register allocation and instruction scheduling decisions.

National Category
Computer Systems
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-154598 (URN)
Funder
Vinnova, VR 621-2011-6229
Note

QC 20141117.

Archived at: arXiv:1409.7628 [cs.PL]

Available from: 2014-10-24 Created: 2014-10-24 Last updated: 2014-11-17Bibliographically approved
Castañeda Lozano, R., Hjort Blindell, G., Carlsson, M., Drejhammar, F. & Schulte, C. (2013). Constraint-based Code Generation. In: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems, M-SCOPES 2013: . Paper presented at 16th International Workshop on Software and Compilers for Embedded Systems, M-SCOPES 2013; St. Goar; Germany; 19 June 2013 through 21 June 2013 (pp. 93-95). Association for Computing Machinery (ACM)
Open this publication in new window or tab >>Constraint-based Code Generation
Show others...
2013 (English)In: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems, M-SCOPES 2013, Association for Computing Machinery (ACM), 2013, p. 93-95Conference paper, Published paper (Refereed)
Abstract [en]

Compiler back-ends generate assembly code by solving three main tasks: instruction selection, register allocation and instruction scheduling. We introduce constraint models and solving techniques for these code generation tasks and describe how the models can be composed to generate code in unison. The use of constraint programming, a technique to model and solve combinatorial problems, makes code generation simple, flexible, robust and potentially optimal.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2013
Keywords
Constraint programming, Instruction scheduling, Instruction selection, Register allocation
National Category
Computer Systems
Identifiers
urn:nbn:se:kth:diva-125069 (URN)10.1145/2463596.2486155 (DOI)2-s2.0-84893342426 (Scopus ID)978-1-4503-2142-6 (ISBN)
Conference
16th International Workshop on Software and Compilers for Embedded Systems, M-SCOPES 2013; St. Goar; Germany; 19 June 2013 through 21 June 2013
Note

QC 20140317

Available from: 2013-08-07 Created: 2013-08-07 Last updated: 2014-03-17Bibliographically approved
Castañeda Lozano, R., Carlsson, M., Drejhammar, F. & Schulte, C. (2012). Constraint-Based Register Allocation and Instruction Scheduling. In: Michela Milano (Ed.), Principles and Practice of Constraint Programming: 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings. Paper presented at 18th International Conference on Principles and Practice of Constraint Programming, CP 2012; Quebec City, QC; 8 October 2012 through 12 October 2012 (pp. 750-766). Springer
Open this publication in new window or tab >>Constraint-Based Register Allocation and Instruction Scheduling
2012 (English)In: Principles and Practice of Constraint Programming: 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings / [ed] Michela Milano, Springer, 2012, p. 750-766Conference paper, Published paper (Refereed)
Abstract [en]

This paper introduces a constraint model and solving techniques for code generation in a compiler back-end. It contributes a new model for global register allocation that combines several advanced aspects: multiple register banks (subsuming spilling to memory), coalescing, and packing. The model is extended to include instruction scheduling and bundling. The paper introduces a decomposition scheme exploiting the underlying program structure and exhibiting robust behavior for functions with thousands of instructions. Evaluation shows that code quality is on par with LLVM, a state-of-the-art compiler infrastructure.

The paper makes important contributions to the applicability of constraint programming as well as compiler construction: essential concepts are unified in a high-level model that can be solved by readily available modern solvers. This is a significant step towards basing code generation entirely on a high-level model and by this facilitates the construction of correct, simple, flexible, robust, and high-quality code generators.

Place, publisher, year, edition, pages
Springer, 2012
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7514
Keywords
Computer programming, Constraint theory, Flocculation, Network components
National Category
Computer Sciences Computer Systems
Identifiers
urn:nbn:se:kth:diva-104554 (URN)10.1007/978-3-642-33558-7_54 (DOI)2-s2.0-84868266938 (Scopus ID)978-3-642-33557-0 (ISBN)978-3-642-33558-7 (ISBN)
Conference
18th International Conference on Principles and Practice of Constraint Programming, CP 2012; Quebec City, QC; 8 October 2012 through 12 October 2012
Note

QC 20121212

Available from: 2012-11-05 Created: 2012-11-05 Last updated: 2018-07-13Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-2806-7333

Search in DiVA

Show all publications