CPC 2006 CPC 2006

Call for Participation
Current List of
Program (List of Talks)
Registration Form
Travel Information

Funded by the Vicerreitoría de Investigación of the University of A Coruña and the Ministry of Education and Science of Spain

Universidade de A Coruña Ministerio de
		      Educación y Ciencia

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.

Back to the Workshop Program 

Please contact our webadmin with any comments or changes.