Phase-decoupled methods for code generation are the state of the art in com
pilers for standard processors but generally produce code of poor quality f
or irregular target architectures such as many DSPs. In that case, the gene
ration of efficient code requires the simultaneous solution of the main sub
problems instruction selection, instruction scheduling, and register alloca
tion, as an integrated optimization problem.
In contrast to compilers for standard processors, code generation for DSPs
can afford to spend much higher resources in time and space on optimization
s. Today, most approaches to optimal code generation are based on integer l
inear programming, but these are either not integrated or not able to produ
ce optimal solutions except for very small problem instances.
We report on research in progress on a novel method for fully integrated co
de generation that is based on dynamic programming. In particular, we intro
duce the concept of a time profile. We focus on the basic block level where
the data dependences among the instructions form a DAG. Our algorithm aims
at combining time-optimal scheduling with optimal instruction selection, g
iven a limited number of general-purpose registers. An extension for irregu
lar register sets, spilling of register contents, and intricate structural
constraints on code compaction based on register usage is currently under d
evelopment, as well as a generalization for global code generation.
A prototype implementation is operational, and we present first experimenta
l results that show that our algorithm is practical also for medium-size pr
oblem instances. Our implementation is intended to become the core of a fut
ure, retargetable code generation system.