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.
Abstract:
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.
Comments:
An improved version of this paper was published at EuroPar-2006.
BibTeX:
@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
}
Download:
PDF
Christoph Kessler