ProjectUnison - Robust, Scalable, and Open Code Generation by Combinatorial Problem Solving

Unison - Robust, Scalable, and Open Code Generation by Combinatorial Problem Solving

Today's compilers typically generate code in stages: instruction selection (choose appropriate instructions for the program being compiled) is followed by register allocation (assign variables to registers or memory) and instruction scheduling (order instructions to improve throughput). Each stage commonly executes an approximation algorithm as taking optimal decisions is computationally infeasible in general. Both staging and approximation compromise the quality of the generated code and preclude optimal code generation.

This project proposes a radical departure in that the various tasks for code generation are translated into models of combinatorial problems and the resulting models are solved in unison by constraint programming as a modern method for combinatorial optimization. The models are generated with respect to the program to be translated and a high-level description of the target architecture.

The challenge in this project is to devise an approach and techniques such that code generation is correct and simple, robust and scalable, potentially optimal, retargetable and open, and widely applicable.

The project's research is significant as it is the first integrated approach to compilation using combinatorial optimization that combines robustness with scalability while using the very same combinatorial models. Previous approaches do not scale and resort to several models to achieve robustness which is error prone and sacrifices simplicity.

The project is a collaboration between SICS, Ericsson, and KTH, funded by Ericsson from 2010 to 2013. From 2012 onwards, additional funding will be provided by the Swedish Research Council (Vetenskapsrådet) under grant 621-2011-6229.

Publications
Number of items: 3.

Castañeda Lozano, Roberto and Carlsson, Mats and Hjort Blindell, Gabriel and Schulte, Christian (2014) Combinatorial Spill Code Optimization and Ultimate Coalescing. In: Fourteenth ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, 12-13 Jun 2014. (In Press)

Castañeda Lozano, Roberto and Hjort Blindell, Gabriel and Carlsson, Mats and Drejhammar, Frej and Schulte, Christian (2013) Constraint-based Code Generation. In: Sixteenth International Workshop on Software and Compilers for Embedded Systems, 19-21 June 2013, St. Goar, Germany.

Castañeda Lozano, Roberto and Carlsson, Mats and Drejhammar, Frej and Schulte, Christian (2012) Constraint-based Register Allocation and Instruction Scheduling. In: Eighteenth International Conference on Principles and Practice of Constraint Programming, 8-12 Oct 2012, Québec City, Canada.

This list was generated on Fri Apr 18 11:03:28 2014 CEST.