Integer Linear Programming versus Dynamic Programming for Optimal Integrated VLIW Code Generation

Andrzej Bednarski, Christoph W. Keßler

Proc. CPC-2006 Workshop on Compilers for Parallel Computers, Jan. 2006, A Coruna, Spain.


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.


An improved version of this paper was published at EuroPar-2006.


@inproceedings{ BednarskiKessler-CPC06-ILP,
 author = {Andrzej Bednarski and Christoph Kessler},
 title = {Integer Linear Programming versus Dynamic Programming for
          Optimal Integrated {VLIW} Code Generation},
 booktitle = {Proc. 12th Int.\ Workshop on Compilers for Parallel Computers (CPC-2006)},
 location = {A Coruna (Spain)},
 year = 2006, month = jan



Christoph Kessler