The OPTIMIST project (2001-2012) at Linköping University, partly funded by the LiU Ceniit programme and by Vetenskapsrådet project Integrated Software Pipelining, investigated and contributed combinatorial optimization algorithms, techniques and an open-source prototype framework for integrated code generation in compiler back ends.
This web page archives key project information, project results, software and documentation of OPTIMIST. For further information please contact Prof. Christoph Kessler.
Christoph Kessler, prof., project leader
Andrzej Bednarski, PhD 2006
Mattias Eriksson, PhD 2011
Master thesis students: Anders Edqvist, David Landén, Yuan Yongyi, Andreas Rehnströmer, Lukas Kemmer, Oskar Skoog
We develop optimization algorithms for integrated code generation, where optimal can be in terms of execution time, register/stack space, energy, or program length, and we allow additional constraints on time (deadlines), space (available registers), energy (energy budget), or length (program memory size). Integrated code generation means that we simultaneously solve instruction scheduling, instruction selection, partitioning, and register allocation as a combined optimization problem. While our methods work for standard processors as well, an integrated approach is crucial especially for irregular VLIW and DSP architectures to achieve high code quality as required in time-critical regions of embedded applications. A method that is capable of computing optimal solutions for non-trivial problem sizes will be useful to assess the quality of fast heuristics and to evaluate the potential of a given processor architecture for a fixed application. As a byproduct, an optimal method can often be relaxed to faster heuristics, too. We develop and implement our optimization algorithms in our retargetable optimizing code generator framework called OPTIMIST.
Previous work focused on a generic dynamic programming approach for optimal integrated code generation at the basic-block level. The method allows to optimize for execution time, register/temporary space, energy consumption, and constrained and mixed optimization goals. Domain-specific properties are exploited to prune the solution space and terminate construction as early as possible. The method allows to derive optimal code for basic blocks of small and (in the case of a single register set) medium size. For larger problem instances, the method can be seamlessly relaxed to a heuristic.
Another optimization engine is based on integer linear programming. This method has been successfully applied for fully integrated code generation at both basic block level and loop level (integrated software pipelining).
We also have developed heuristics to tackle really large problem instances. A recently developed one is based on genetic programming for the basic block level.
All these methods support also clustered VLIW architectures. Note that clustering makes the code optimization problem much more complex compared to the homogeneous single-cluster VLIW case.
Our integrated code generator framework OPTIMIST is retargetable: We use our XML-based architecture description language xADML to specify the target processor architecture for the code generator. Our method can handle code selection with tree, DAG and forest patterns on a low-level intermediate representation of the program. Case studies done so far involve the processors TI C62x, ARM9E and Motorola MC56K.
We use LCC as C front end and the LCC-IR (node DAGs) as intermediate representation. A recently finished interface from the Open Research Compiler (ORC) allows to use ORC's high-level transformations and additional frontends for C++ and Fortran77. xADML is parsed with Xerces. The rest of the system is written in C++, using the Boost library. DAGs and solution spaces are visualized with VCG.
The OPTIMIST framework with complete source code and example xADML specifications for ARM9E, ARM9E Thumb, MC 56K DSP and TI C62x, installation guide and documentation, is available on the page
Comments and suggestions are welcome!
The integrated software pipelining branch of this project was funded 2006-2008 and 2010-2012 by a project grant from the Swedish national science foundation (Vetenskapsrådet).
The OPTIMIST main project was supported 2001-2007 as a long-term
research effort by
During July 2004-June 2005 and July 2006-Dec. 2007 it was also supported by SSF project RISE, subproject RISE-OPTIMIST resp. subproject RISE-CODECOMP.
The case study for ARM9E was supported by
IAR Systems AB.
The case study for MC56K is a cooperation with Softube AB.
IAR Systems AB, Uppsala
Ericsson AB Softlab, Linköping