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 funded by the Swedish Research Council (VR) under grant 621-2011-6229, 2012–2014. Volume: 2400 KSEK, role: principal investigator.
The project is conducted in close collaboration with a project on constraint-based compilation at SICS (Swedish Institute of Computer Science) also lead by Christian Schulte and funded by LM Ericsson AB.