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.
Project members:
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
Project goals:
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.
Project description:
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.
Implementation:
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.
Software download:
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
http://www.ida.liu.se/~chrke55/optimist/download.html
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
CENIIT.
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.
Industrial cooperation:
IAR Systems AB, Uppsala
Ericsson AB Softlab, Linköping