Compiling for VLIW DSPs - Signal Processing Systems - page 1168

For simple target architectures, the main tasks in code generation include
instruction selection, instruction scheduling and register allocation:

￿ Instruction selection maps the abstract operations of the IR to equivalent

instructions of the target processor. If we associate fixed resources (functional
units, buses etc.) to be used with each instruction, this also includes the resource
allocation problem. Details will be given in Sect. 4 .

￿ Instruction scheduling arranges instructions in time, usually in order to minimize

the overall execution time, subject to data dependence, control dependence and
resource constraints. In particular, this includes the subproblems of instruction
sequencing , i.e., determining a linear (usually, topological) order of instructions
for scheduling, and code compaction , i.e. determining which independent in-
structions to execute in parallel and mapping these to slots in instruction issue
packets and fetch packets. Local, loop-level and global instruction scheduling
methods will be discussed in Sect. 7 .

￿ Register allocation selects which values should, at what time during execution,

reside in some target processor register. If there may not be enough registers
available at a time, some values must be temporarily spilled to memory, which
requires the generation and scheduling of additional spill code in the form of load
and store instructions. The simpler problem of register assignment maps the run-
time values that were allocated a register to a concrete register number. Details
will be given in Sect. 6 .

Advanced architectures such as clustered architectures may require additional
tasks such as cluster assignment and data transfer generation (see Sect. 5 ) , which
may be considered separately or be combined with some of the above tasks. For
instance, cluster assignment for instructions could be considered part of instruction
selection, and cluster assignment for data may be modeled as an extension of register
allocation.
Another task that is typical for DSP processors is that of address code generation
for address generation units (AGUs). AGUs provide auto-increment and auto-
decrement functionality as a parallel side effect to ordinary instructions that use
special address registers for accessing data in memory. The AGUs may provide fixed
offset values or offset registers to be used for in-/decrementing. A compiler could
thus assign address registers and select offsets in an attempt to minimize the amount
of residual addressing code that would still be computed with ordinary processor
instructions on the main functional unit. See Sect. 3.1 in the chapter on C Compilers
and Code Optimizations for DSPs [ 38 ] of this topic for further details.
Further code generation problems frequently occuring with VLIW DSPs include
exploiting available SIMD instructions, which can be regarded a subproblem of
instruction selection, and optimizing memory data layout to avoid stalls caused
by memory bank access conflicts. Also here we refer to the above-mentioned
chapter [ 38 ] , Sects. 3.3 and 3.4, for a discussion of SIMD code generation and
optimization of memory bank assignment, respectively.