Compiling for VLIW DSPs - Signal Processing Systems - page 1169

4 Instruction Selection and Resource Allocation

The instruction selection problem is often modeled as a pattern matching problem,
where the processor-independent operations of the intermediate representation are
to be covered by patterns that correspond to the semantics of target processor
instructions. The description of the target processor instructions in terms of IR
operations has to be provided by the compiler writer.
Each IR operation has to be covered by exactly one pattern node. Some examples
are shown in Fig. 10 . As intermediate results corresponding to inner edges of a
multi-node pattern are no longer accessible in registers if that instruction is selected,
such a pattern is only applicable as a cover if no other operations (such as SUB in
Fig. 10 b ) access such an intermediate result. In other words, all outgoing edges from
IR nodes covered by non-root pattern nodes must be covered by pattern edges.
Each pattern is associated with a cost , which is typically its occupation time or
its latency as an a-priori estimation of the instruction's impact on overall execution
time in the final code (the exact impact will only be known after the remaining tasks
of code generation, in particular instruction scheduling, have been done). But also
other cost metrics such as register space requirements are possible. The optimization
goal is then to minimize the accumulated total cost of all covering patterns, subject
to the condition that each IR operation is covered by exactly one pattern node.
The optimizing pattern matching problem can be solved in various ways.
A common technique, tree parsing , is applicable if the patterns are tree-shaped and
the data flow graph of the current basic block (for instruction selection, we usually
consider one basic block of the input program at a time) is a tree . The patterns are
modeled as tree rewrite rules in a tree grammar describing admissible derivations of
coverings of the input tree. A heuristic solution could be determined by a LR-parser
that selects, in each step of constructing bottom-up a derivation the input tree, in a
greedy way whenever there are several applicable rules (patterns) to choose from
[ 43 ] . An optimal solution (i.e., a minimum-cost covering of the tree with respect to
the given costs) can be computed in polynomial time by a dynamic programming
algorithm that keeps track of all possibly optimal coverings in a subtree [ 1 , 39 ] .

a b c

SUB ADD

MADD

ADD32

SUB16

ADD32

ADD2
ADD16

ADD16

MUL LDH

MUL16 INDIR16

MUL16

Fig. 10 Examples for covering IR nodes ( solid circles ) and edges ( arrows ) with patterns ( dashed
ovals ) corresponding to instructions