|
Funded by the Vicerreitoría de Investigación of the University of A Coruña and the Ministry of Education and Science of Spain 
|
Integer Linear Programming versus Dynamic Programming for Optimal Integrated VLIW Code Generation
Andrzej Bednarski and Christoph Kessler
PELAB, Departement of Computer and Information Science, Linköpings Universitet, Sweden
To our knowledge there is only one Integer Linear Programming (ILP)
formulation in the literature that fully integrates all steps of
code generation, i.e. instruction selection, register
allocation and instruction scheduling, on the basic block level.
We give in this paper an improved version of this ILP formulation
that also covers VLIW processors.
Moreover, our ILP formulation does no longer require preprocessing
the basic block's data flow graph to support instruction selection.
In earlier work, we proposed and implemented a dynamic programming
(DP) based method for optimal integrated code generation, called
OPTIMIST. In this paper we give first results to evaluate and compare
our ILP formulation with our DP method on a VLIW processor.
We identify different code situations and shapes of
data dependence graphs for which either ILP or DP is most
suitable.
