Code generation for fixed-point DSPs.
This paper examines the problem of code-generation for Digital Signal Processors (DSPs). We make two major contributions. First, for an important class of DSP architectures, we propose an optimal O(n) algorithm for the tasks of register allocation and instruction scheduling for expression trees. Optimality is guaranteed by sufficient conditions derived from a structural representation of the processor Instruction Set Architecture (ISA). Second, we develop heuristics for the case when basic blocks are Directed Acyclic Graphs (DAGs).
INTRODUCTION
Digital Signal Processors (DSPs) are receiving increased attention recently due to
their role in the design of modern embedded systems like video cards, cellular telephones
and other multimedia and communication devices. DSPs are largely used
in systems where general-purpose architectures are not capable of meeting domain
specific constraints. In the case of portable devices, for example, the power consumption
and cost may make the usage of general-purpose processors prohibitive.
The same is true when high-performance arithmetic processing is required to implement
dedicated functionality at low cost, as in the case of specific communications
Preliminary version of parts of this paper was presented in [Araujo and Malik 1995] at the 1995
ACM/IEEE International Symposiumon System Synthesis, France, September 13-15, 1995, and in
[Araujo et al. 1996] at the 1996 ACM/IEEE Design Automation Conference, June 3-7. Author's
address: G. Araujo, Institute of Computing, University of Campinas (UNICAMP), Cx.Postal
6176, Campinas, SP, 13081-970, Brazil and S. Malik, Department of Electrical Engineering, Princeton
University, Olden St., Princeton, NJ, 08544, USA.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is
granted without fee provided that copies are not made or distributed for profit or direct commercial
advantage and that copies show this notice on the first page or initial screen of a display along
with the full citation. Copyrights for components of this work owned by others than ACM must
be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on
servers, to redistribute to lists, or to use any component of this work in other works, requires prior
specific permission and/or a fee. Permissions may be requested from Publications Dept, ACM
Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or permissions@acm.org.
and computer graphics applications. The increasing usage of these processors has
revealed a new set of code generation problems, which are not efficiently handled
by traditional compiling techniques. These techniques make implicit assumptions
about the regular nature of the target architecture and microarchitecture. This is
rarely the case with DSPs, where irregularities in the microarchitecture are the very
basis for the efficient computation of specialized functions. Due to hard on-chip
memory constraints and hard real-time performance requirements, the code generated
for these processors has to meet very high quality standards. Since existing
compilation techniques are not up to this task, the vast majority of the code is
written directly in assembly language. This research is part of a project directed
towards developing compilation techniques that are capable of generating quality
code for such processors (http://ee.princeton.edu/spam). The implementation of
these techniques forms the compiling infrastructure used in this work, which is
called the SPAM compiler.
There is a large body of work done in code generation for general purpose pro-
cessors. Code generation is, in general, a hard problem. Instruction selection for
expressions subsumes Directed Acyclic Graph (DAG) covering, which is an NP-complete
problem [Garey and Johnson 1979]. Bruno and Sethi [1976] and Sethi
[1975] showed that the problem of optimal code generation for DAGs is NP-complete
even for a single register machine. It remains NP-complete for expressions in which
no shared term is a subexpression of any other shared term [Aho et al. 1977a]. An
efficient solution for a restricted class of DAGs has been proposed in [Prabhala and
1980]. Code generation for expression trees has a number of O(n) solutions,
where n is the number of nodes in the tree. These algorithms offer solutions for the
case of stack machines [Bruno and Sethi 1975], register machines [Sethi and Ullman
1970] [Aho and Johnson 1976] [Appel and Supowit 1987] and machines with
specialized instructions [Aho et al. 1977b]. They form the basis of code generation
for single issue, in order execution, general-purpose architectures.
The problem of generating code for DSPs and embedded processors has not received
much attention though. This was probably due to the small size of the
programs running on these architectures, which enabled assembly programming.
With the increasing complexity of embedded systems, programming such systems
without the support of high-level languages has become impractical. Many of the
problems associated to code generation for DSP processors were first brought to
light by Lee in [Lee 1988] [Lee 1989], a comprehensive analysis of the architecture
features of these processors. Code generation for DSP processors has been studied
in the past, but only more recently a number of interesting work has tackled
some of its important problems. Marwedel [1993] proposed a tree-based mapping
technique for compiling algorithms into microcode architectures. [Liem et al. 1994]
uses a tree-based approach for algorithm matching and instruction selection, where
registers are organized in classes and register allocation is based on a left-first algo-
rithm. Datapath routing techniques have also been proposed [Lanner et al. 1994]
to perform efficient register allocation. Wess [1990] proposed the usage of Normal
Form Schedule for DSP architectures, and offered a combined approach for register
allocation and instruction selection using the concept of trellis diagrams [Wess
1992]. [Kolson et al. 1996] recently proposed an interesting exact approach for
register allocation in loops for embedded processors. An overview of the current
Code Generation for Fixed-Point DSPs \Delta 3
research work on code generation for DSP processors, and embedded processors in
general, can be found in [Marwedel and Goosens 1995].
In this paper, we propose an optimal two phase algorithm which performs instruction
selection, register allocation and instruction scheduling for an expression tree
in polynomial time, for a class of DSPs. The architecture model here (described in
Section 2) is of a programmable highly-encoded Instruction Set Architecture (ISA),
fixed-point DSP processor. Formally speaking, this class is an extension of the machine
models discussed in Coffman and Sethi [1983]. In the first pass (Section 3),
we perform instruction selection and register allocation simultaneously, using the
Aho-Johnson algorithm [Aho and Johnson 1976]. The second pass, described in
Section 4, is an O(n) algorithm that takes an optimally covered expression tree
with n nodes, and schedules instructions such that no memory spills are required.
A memory spill is an operation where the contents of a particular register is saved
in memory due to a lack of available registers for some operation, and reloaded
from memory after that operation is finished. Observe that a memory store operation
required by the architecture topology is not considered a memory spill. The
proposed algorithm uses the concept of the Register Transfer Graph (RTG) that is
a structural representation of the datapath, annotated with ISA information. We
show that if the RTG of a machine is acyclic, then optimal code is guaranteed for
any program expression tree written for that machine. In this case the DSP is
said to have an acyclic datapath. Since DAG code generation is NP-complete, we
develop heuristics for the case of acyclic datapaths (Section 5) which again uses the
RTG concept. In Section 6 we show the results of applying these ideas to benchmark
programs. Section 7 summarizes our major contributions and suggests some
open problems.
2. ARCHITECTURAL MODEL
DSP processors are irregular architectures, when compared with their general purpose
counterparts. This section analyzes the main architecture features which distinguish
DSPs from general purpose processors with respect to basic block code
generation. It is not the purpose of this section to give a detailed and extensive
analysis of these features. A comprehensive analysis of DSP architectures can be
found in [Lee 1988][Lee 1989] [Lapsley et al. 1996].
DSPs can be classified according to the type of data they use as fixed-point DSPs
and floating-point DSPs. In applications running on a fixed-point DSP, users are
responsible for scaling the result of the integer operations. This is automatically
done in floating-point DSPs. Floating point units are extremely costly in terms of
silicon area and clock cycles. For this reason, a large number of the systems based
on DSPs uses fixed-point DSPs. In this case, the acronym DSP will be assumed
from now on to mean fixed-point DSP.
DSPs have on-chip data memory, based on fast static RAMs and on-chip non-volatile
program ROM. Unlike general purpose architectures, DSPs are not designed
with cache or virtual memory systems, since data and program streams usually fit
into the available on-chip memories. Because on-chip memories are fast and cache
misses are not an issue, some DSPs are designed as memory-register architectures
[Texas Instruments 1990]. In order to achieve the bandwidth required by its appli-
cations, other DSPs architectures provide multiple memory banks [Motorola 1990].
Since performance is an important factor for DSP applications, DSP instructions
are usually designed to be fetched in a single machine cycle. In order to achieve
that instructions are encoded such as to minimize the number of bits they require.
In some architectures [Texas Instruments 1990] this is done by means of data memory
pages, where instructions need only to carry the offset of the data within the
current page in order to access it.
The goal of the design of a DSP datapath is to implement those functional units
which can speed up costly operations that frequently occur in the processor application
domain. A common example of such units is Multiply and Accumulate
(MAC). Due to design requirements, DSP designers frequently constrain the inter-connectivity
between registers and functional units. There are two main reasons for
this. First, the desired functionality usually requires a particular datapath topol-
ogy. Second, broad interconnectivity translates into datapath buses and/or muxes,
which results in increased cost and instruction performance degradation.
A large number of DSPs are heterogeneous register architectures. These are architectures
which contain multiple register files, and instructions that require operands
and store the resulting computation in different register files (hence the name het-
erogeneous). In general-purpose architectures, instructions usually do not restrict
the registers they use, provided they come from the same register file (hence operand
registers are homogeneous). This considerably simplifies the code generation prob-
lem, since it decouples the tasks of instruction selection from register allocation.
Due to this property, we say that general-purpose architectures are homogeneous
register architectures.
Example 1. An example of a DSP architecture is the TI TMS320C25 Digital
Signal Processor (DSP) [Texas Instruments 1990], which will be considered the
target architecture for the rest of this paper. This processor is part of the TI
TMS320 family of processors, which makes a large number of all commercial DSP
processors in use today. The TMS320 family is composed of fixed-point processors
(TMS320C1x/C2x/C5x/C54x) which are heterogeneous architectures, and also by
a number of floating-point homogeneous architecture DSPs (TMS320C3x/C4x).
The TMS320C25 processor contains an ISA with specialized memory-register and
register-register instructions. It has three separate register-files (a, p and t) containing
a single register each.
3. OPTIMAL INSTRUCTION SELECTION AND REGISTER ALLOCATION
In homogeneous register architectures the selection of an instruction has no connection
whatsoever with the types of registers that the instruction uses. Selecting
instructions for heterogeneous register architectures usually requires allocating register
from specific register-files as operands for particular instructions. The strong
binding between instruction selection and register allocation indicates that these
tasks must be performed together [Araujo and Malik 1995].
Consider, for example, the Intermediate Representation (IR) patterns in Figure 1
corresponding to a subset of the instructions in the TMS320C25 ISA. In Figure 1
each instruction is associated to a tree-pattern whose node is composed of operations
(PLUS,MINUS,MUL), registers (a,p,t), constants (CONST) and memory
references (m).
Code Generation for Fixed-Point DSPs \Delta 5
a m
a
a
a
add: apac:
mpy: mpyk: p
a
pac:
sacl:
a
a
CONST
a
a
spac:
a
lac: m
lack: CONST
Fig. 1. IR patterns for the TMS320C25 processor
Instruction Operands Destination Cost Three Address Form
add m a,m a 1 a / a +m
apac a,p a 1 a / a
spac a,p a 1 a / a \Gamma p
lack k k a 1 a / k
pac p a 1 a / p

Table

1. Partial ISA of the TMS320C25 processor
These tree-patterns, are represented using three-address form in Table 1. Three-address
is a standard compiler representation for instructions, where the destination
of the instruction, its two operands (hence the name three address) and the operation
it performs are present. Any reference in square brackets is associated to a
memory position. Table 1 also lists the cost associated to each instruction.
Notice that the instructions implicitly define the registers they use. For example,
the instruction apac can only take its operands from registers a and p, and always
computes the result back into a. Observe also that operations which transfer data
through the datapath like lac m (load register a from memory position m), and
pac (move register p into register a) can be represented each as a single node,
corresponding to the source register of the transfer operation. The associated cost
in this case is only the cost of moving the data from the source register into the
destination register. Since registers in DSP architectures are a scarce resource, the
final code quality is very sensitive to the cost of routing data through the datapath.
3.1 Problem Definition
Optimal instruction selection combined with register allocation is the problem of
determining the best cover of an expression tree such that the cost of each pattern
match depends not only on the number of cycles of the associated instruction, but
also on the number of cycles required to move its operands from the location they
6 \Delta Guido Araujo and Sharad Malik
currently are to the location where the instruction requires them to be.
3.2 Problem Solution
A solution for this problem is to use a variation of the Aho-Johnson algorithm [Aho
and Johnson 1976] such that at each node we keep not only all possible costs for
matches at that node, but also all possible costs resulting from matching the node
and moving the result from where it is originally computed into any other reachable
location in the datapath.
Tree-grammar parsers have been used as a way to implement code-generators [Aho
et al. 1989] [Fraser et al. 1993] [Tjiang 1993]. They combine dynamic programming
and efficient tree-pattern matching algorithms [Hoffman and O'Donnell 1992] for
optimal instruction selection. We have implemented combined instruction selection
and register allocation using the olive [Tjiang 1993] code-generator generator.
olive is based on the techniques proposed in iburg [Fraser et al. 1993]. It takes
as input a set of grammar rules where tree-patterns are described in a prefixed
linearized format. The IR patterns from Table 1 were converted into the olive
description of Figure 2, by rewriting each instruction three-address representation
into that format. Notice that the instruction destination registers are now associated
to grammar non-terminals, and that these are represented by lower case letters
in

Figure

2.
Fig. 2. Partial olive specification for the TMS320C25 processor (instruction numbers and names
on the right are not part of the specification)
Rules 1 to 3 and 4 to 5 correspond to instructions that take two operands and
store the final result in a particular register (a and p respectively). Rule 6 describes
an immediate load into register a. Rules 7 to 10 are associated to data transference
instructions and bring the cost of moving data through the datapath into the total
cost of a match. We should point out that, for sake of simplicity, we do not
represent in Figure 2 all patterns corresponding to commutative operations. For
example, instruction add m can be specified in two different ways: PLUS(a,m) and
PLUS(m,a). Nevertheless, we will consider for the remainder of this paper that all
commutative forms of any operation pattern are available whenever required.
If we do not consider instruction scheduling and the associated spills at this
point, then the algorithm proposed above is optimal. This follows from the fact
that this algorithm is a variation of the provably optimal Aho-Johnson dynamic
programming algorithm [Aho and Johnson 1976].
Code Generation for Fixed-Point DSPs \Delta 7
4. SCHEDULING
Optimal instruction selection and register allocation for an expression tree is not
enough to produce optimal code. For optimal code the instructions must be scheduled
in such a way that no memory spills are introduced. Notice that memory
positions allocated in the previous phase are not considered spills. They result
from the optimal selection of memory-register instructions in the ISA and not from
the presence of resource conflicts.
Aho and Johnson [1976] showed that, by using dynamic programming, optimal
code can be generated in linear time for a wide class of architectures. The schedule
they propose is based on their Strong Normal Form Theorem. This theorem guarantees
that any optimal code schedule for an expression tree, for a homogeneous
register architectural model, can always be transformed into Strong Normal Form
(SNF). A code sequence is in SNF if it is formed by a set of code sub-sequences
separated by memory storages, where each code sub-sequence is determined by a
Strongly Contiguous (SC) schedule. A code sequence is a SC schedule if it is formed
as follows: at every selected match m, with child subtrees T 1 and T 2 , continuously
schedule the instructions corresponding to subtree T 1 followed by the instructions
corresponding to T 2
, and finally the instruction corresponding to pattern m. Wess
[1990] used SNF as a heuristic to schedule instructions for the TMS320C25 DSP.
4.1 Problem Definition
SC schedules are not an efficient way to schedule instructions for heterogeneous
register set architectures. They produce code sequences whose quality is extremely
dependent on the order the subtrees are evaluated. Consider for example the IR
tree of Figure 3(a). The expression tree was optimally matched using the approach
proposed in Section 3 and the target ISA. It takes variables at memory positions m 0
to m 4 and stores the resulting computation into one variable at memory position
using m 5 as temporary storage.
The code sequences generated for three different schedules and its corresponding
three-address representation are showed in Figure 3(b-d). Memory position m 7
was used whenever a spill location was required by the scheduler. For the code of

Figure

3(b) the left subtree of each node was scheduled first followed by its right
subtree and then the instruction corresponding to the node operation. The opposite
approach was used to obtain the code of Figure 3(c). Neither the SC schedules in

Figure

3(b) and (c), nor any SC schedule will ever produce optimal code. This is
obtained using a non-SC schedule that first schedules the addition
then the rest of the tree, as in Figure 3(d). Notice that this schedule is indeed
an SNF schedule, since first the subtree corresponding to m 2
is contiguously
scheduled followed by a storage operation into memory position m 5
, and by another
code sequence resulting from a SC schedule of the rest of the tree.
From

Figure

3 we can verify how the appropriate SNF schedule minimizes spilling.
For example, if the tree of Figure 3(a) is scheduled using left-first, the result of
operation
\Theta m 1 is first stored in p and then moved into a. Just after that,
register a has to be used to route the result of position
m 5 . But a still contains a live result (the result of m 0
In this case, the
code-generator has to emit code to spill the value of a into memory and recover it
(a)
a
a
a
a
mpy m0 p / t * [m0] lac m3 a / [m3] add m2 a / a
pac a / p add m2 a / a
sacl m7 [m7] / a sacl m5 [m5] / a lt m1 t / [m1]
lac m3 a / [m3] mpy m5 p / t * [m5] mpy m0 p / t * [m0]
add m2 a / a
sacl m5 [m5] / a pac a / p lt m4 t / [m4]
mpy m5 p / t * [m5] mpy m0 p / t * [m0] spac a / a - p
lac m7 a / [m7] pac a / p sacl m6 [m6] / a
spac a / a - p lt m7 t / [m7]
spac a / a - p
sacl m6 [m6] / a
(b) (c) (d)
Fig. 3. (a) Matched IR tree for the TMS320C25; (b) SNF Left-first schedule; (c) SNF Right-first
schedule; (d) Optimal schedule
later. This would not be required if the scheduler had first stored m 2
into
, before loading a with the result of m 0
Problems like the one illustrated above are very common in DSP architectures.
The obvious question it raises is - Does there exist a guaranteed SNF schedule such
that no spilling is required ? We will prove that this schedule exist, under certain
conditions that depend exclusively on the ISA of the target processor. But before
doing so, let us define the problem formally: Given an optimally covered expression
tree for an heterogeneous register architecture, determine an instruction schedule
that does not introduce any spill code.
4.2 Problem Solution
This section is divided as follows. In Section 4.2.1 we state and prove a sufficient
condition that an heterogeneous register architecture has to satisfy in order to
enable spill free schedules. In Section 4.2.2 we introduce the concept of Register
Transfer Graph (RTG) and show how it impacts the code generation task. Finally,
Code Generation for Fixed-Point DSPs \Delta 9
we prove the existence of an optimal linear time scheduling algorithm for a class
DSP architectures which have acyclic RTGs.
Let T be an expression tree with unary and binary operations. Let
be a function which maps nodes in T to the set R[M , where
is a set of N registers, and M the set of memory locations. Let u be the root of
an expression tree, with v 1
children of u. Consider that after allocation is
performed, registers L(v 1
are assigned to v 1
respectively.
and T 2
be the subtrees rooted at v 1
, as in

Figure

4. From now on the
terms expression tree and allocated expression tree will be used interchangeably,
with the context distinguishing if the tree is allocated or not.
4.2.1 Allocation Deadlock
Definition 1. An expression tree contains an allocation deadlock iff the following
conditions are true: (a) L(v 1
and (c) there
exist nodes w 1
and w 2
and w 2
such that L(w 1
The above definition can be visualized in Figure 4. This is the situation when two
sibling subtrees T 1
and T 2
contain each at least one node allocated to the same
register as the register assigned to the root of the other sibling tree. Using this
definition it is possible to propose the following result.
Fig. 4. Allocation deadlock in an expression tree
Theorem 1. Let T be an expression tree. If T does not have a spill free schedule
then it contains at least one subtree which has an allocation deadlock.
Proof. Assume that all nodes u in T are such that T u is free of allocation
deadlocks and that no valid schedule exist for T . According to Definition 1 T u does
not have an allocation deadlock when:
(a) In this case, a SNF schedule exists if subtree T 1
is scheduled first followed by subtree
This case cannot happen since no non-unary operator of an
expression tree takes its two operands simultaneously from the same location.
(a) (b) (c)
Fig. 5. Trees without allocation deadlock
(c) exist for which L(w 2
In this case, it is possible to schedule T 1
first, followed by T 2
and the instruction
corresponding to node u. This is a valid schedule because just after the schedule
of T 1
is finished only register r 1
is live, and therefore, since no register r 1
exists in
, no resource conflict will occur when this subtree is scheduled (Figure 5(a)).
exist for which L(w 1
This is symmetric to the previous case. Schedule T 2 first, followed by T 1 and the
instruction corresponding to u (Figure 5(b)).
exist. This case is trivial, any SC
schedule results in a spill free schedule (Figure 5(c)).
Since the above conditions can be applied to any node u, T will have a valid
schedule that is free of memory spilling code. This contradicts the initial assumption

Corollary 1. Let T be an expression tree. If T has no subtree containing an
allocation deadlock then it must have a spill free schedule. Moreover this schedule
can be computed using the proof of Theorem 1.
Proof. Directly from the theorem above.
4.2.2 The RTG Model and Theorem
Definition 2. The RTG is a directed labeled graph where each node represents a
location in the datapath architecture where data can be stored. Each edge in the
RTG from node r i to node r j is labeled after those instructions in the ISA that
take operands from location r i and store the result into location r j .
The nodes in the RTG represent two types of storage: register files and single
registers. Register file nodes represent a set of locations of the same type which can
store multiple operands. A datapath single register (or simply single register) is a
register file of unitary capacity. Register file nodes are distinguished from single
register nodes by means of a double circle. Because of its uniqueness, memory is
not described in the RTG. Arrows are used instead to represent memory operations.
An incoming (outgoing) arrow pointing to (from) an RTG node r is associated to
Code Generation for Fixed-Point DSPs \Delta 11
a load (store) operation from (into) memory. Notice that the RTG is a labeled
graph where each edge has labels corresponding to the instructions that require
that operation. In other words, if both instructions p and q take one operand in r i
and store its result into r j , then the edge from r i to r j will have at least two labels,
p and q. We say that an architecture RTG is acyclic if it contains no cycles. As a
consequence of that any register transfer cycle in an acyclic RTG has to go through
memory 1 .
Example 2. Consider, for example, the partial olive description in Figure 2. The
RTG of

Figure

6 was formed from that description. The numbers in parenthesis
on the right side of Figure 2 are used to label each edge of the graph. Not all ISA
instructions of the target processor are represented in the description of Figure 2,
and therefore not all edges in the RTG of Figure 6 are labeled. Notice that the
RTG of the TMS320C25 architecture is acyclic. Other DSP processors also have
acyclic RTGs, like the processors TMS320C1X/C2X/C5X and the Fujitsu FDSP-4.
This paper proposes a solution for code generation for acyclic RTG architectures.
Unfortunately, other known DSPs like the ADSP-2100 and the Motorola 56000
have cyclic RTGs. Nevertheless, as it will be shown later, code generation for these
processors can also benefit from the results of this work.
a t
p1,2,3
Fig. 6. TMS320C25 architecture has an acyclic RTG
Theorem 2. If an architecture RTG is acyclic, then for any expression tree
there exists a schedule that is free of memory spills.
Proof. Let T be an expression tree rooted at u, and v 1
its children, such
that
and L(v 2
. Let T 1
and T 2
be the subtrees rooted at
nodes
. Let P k , be subtrees of T with root p k for which the
result of operation p k is stored into memory (i.e. L(p k
(dark areas in Figure 7) as the subtrees formed in T i after removing all nodes from
subtrees P k . We will show that if the RTG is acyclic, an optimal schedule can
always be determined by properly ordering the schedules for P k (e.g. P 1
. Here we have to address two cases: (a) Assume that T has no
allocation deadlock. Therefore, from Corollary 1 T has an optimal schedule. (b)
Now consider that an allocation deadlock is present in T , and that it is caused by
registers r 1 and r 2 , as shown in Figure 7. Assume also that there exist paths from
r 2 to r 1 in the processor RTG. Observe now that for each node in T 2 (Figure 7)
allocated to r 1 , e.g. w 2 , the path that goes from w 2 to its ancestor v 2 (allocated to
1 Observe that a self-loop is not considered an RTG cycle.
wp
Fig. 7. The RTG Theorem
necessarily pass by a node allocated to memory, e.g. p 2
. This comes from
the fact that any path from r 1
to r 2
has to traverse memory, given that the RTG
is acyclic and that it contains paths from r 2
to r 1
. Notice that one can recursively
schedule subtrees P 2
and P 4
in T 2
for which the root was allocated to memory, and
that this corresponds to emitting in advance all instructions that store results in
. Once this is done, only memory locations are live and the remaining subtree Q 2
contains no instruction that uses r 1
. The nodes that remain to be scheduled are
those in subtrees T 1
and
. Therefore, the tree T 1
[fug can now be scheduled
using Corollary 1 and no spill will be required. Notice that the same result will be
obtained if one first recursively schedules all subtrees P 1
(white areas in

Figure

followed by applying Corollary 1 to schedule subtree Q 1
fug.
Based on the proof of Theorem 2 above, an algorithm can be designed which
computes the best schedule for an expression tree in any acyclic RTG architecture.
We have designed such algorithm and named it OptSchedule.
Theorem 3. Algorithm OptSchedule is optimal and has running time O(n),
where n is the number of nodes in the subject tree T .
Proof. The first part is trivial since OptSchedule implements the proof of Theorem
2. Also from Theorem 2, the algorithm divides T into a set of disjoint subtrees
recursively schedules each of them. Therefore, every node
in T is visited only once. Hence, the algorithm running time is O(n).
Remark 1. If the RTG is acyclic for a particular architecture, then optimal sequential
code is guaranteed for any expression tree compiled from programs running
on that architecture. Unfortunately, this is not true for those architectures which
Code Generation for Fixed-Point DSPs \Delta 13
do not have acyclic RTGs. Nevertheless, expression trees in those architectures can
also benefit from this work. Observe from Corollary 1 that if an expression tree is
free of allocation deadlocks then it can be optimally scheduled. This is valid for
any expression tree generated from any architecture, no matter if this architecture
has an acyclic RTG or not. Consider for example that a path is added from p to t
in the RTG of Figure 6. This creates a cycle in the architecture RTG, which does
not go through memory. On the other hand, any expression tree which do not use
this new path is free of allocation deadlocks, and therefore can still be optimally
scheduled. Such expression trees could be identified by a simple modification of the
instruction selection algorithm. The question of how many of these trees exist in a
typical program is still open though.
5. HEURISTIC FOR DAGS
Instruction selection for an expression DAG requires DAG covering, which is known
to be NP-complete [Garey and Johnson 1979]. In practical solutions to this problem
heuristics have been proposed which divide the DAG into its component trees by
selecting an appropriate set of trees. However, this dismanteling of the DAG into
component trees is not unique and there are several ways in which this can be
done. Traditionally, the heuristic employed in the case of homogeneous register
architectures is to disconnect multiple fanout nodes of the DAG [Aho et al. 1988].
Dividing a DAG into its component trees requires disconnecting (or breaking)
edges in the DAG. For the code generation task, breaking a DAG edge between
nodes u and v implies the allocation of temporary storage to save the result of
operation u while this is not consumed by operation v. This storage location is
traditionally the memory but it can, in general, be any location in the datapath.
The key idea proposed here is a heuristic which uses architectural information from
the RTG in the selection of component trees of a DAG, such that the resulting
code has minimal spills. Consider for example the DAG of Figure 8. Notice that
two different approaches can be used to decompose this DAG into its component
trees, depending on which edge (e 1
or e 2
is selected to break. From now on, we
will represent a broken edge by a line segment traversal to the subject edge. As one
can see in Figure 8(b), one extra instruction is generated when the dismanteling
heuristic is based on breaking edge e 2
instead of e 1
. Incidentally, the code in

Figure

8(a) is also the best sequential code one can generate from the subject
DAG. Observe from the architectural description in Table 1, that the multiplication
operation requests its operands from memory (m) and t, and that the result of the
addition operation always produce its result in the accumulator a.
Notice also in Figure 6 that to bring any data from a to register t one has to go
through m. From Figure 8 one can see that the result of the addition operation
has to be stored into a and must be moved to m or t in order to be
used as an operand of the multiplication operation. But to move data from a to
t one has to go through memory (m). Suppose the memory position selected to
store this temporary result is m 5 . Hence, by breaking DAG edge e 1 one is just
assigning in advance a memory operation which will appear on that edge, during
the instruction selection phase of the code generation. Notice that the existence of a
register-transfer path which always goes through memory whenever data is moved
from a to t is a property of the target datapath. Similarly, the register-transfer
14 \Delta Guido Araujo and Sharad Malik
lac m2 a / [m2] lac m2 a / [m2]
add m3 a / a
sacl m5 [m5] / a sacl m5 [m5] / a
mpy m5 p / t * [m5] add m4 a / a
add m4 a / a
mpy m5 p / t * [m5]
(a) (b)
Fig. 8. (a) Breaking edge e 1
Breaking edge e 2
path from a to p must also pass through memory.
Notice also that when edge e 2
is broken, pattern PLUS(a,m) (instruction add m 4
cannot be used to match the addition of m 4
with the result of m 2
in the
accumulator a. In this case, instruction lac m 5
in

Figure

8(b) has to be issued in
order to bring the data from m 5
back to the accumulator adding a new instruction
to the final code.
a a a
a
a
(1) (1)
(1)
(2)
Fig. 9. Expression DAG after partial register allocation was performed and natural and pseudo-natural
edges identified by its corresponding lemma.
Code Generation for Fixed-Point DSPs \Delta 15
5.1 Problem Solution
The heuristic we propose to address the problem just described is divided into four
phases. In the first phase (Section 5.1.1) partial register allocation is done for those
datapath operations which can be clearly allocated before any code generation task
is performed in the DAG. During the second phase (Section 5.1.2), architectural
information is employed to identify special edges in the DAG which can be broken
without introducing any loss of optimality for the subsequent tree mapping
stages. In the third phase (Section 5.2) edges are marked and disconnected from
the DAG. Finally component trees are scheduled and optimal code generated for
each component tree (Section 5.2).
5.1.1 Partial Register Allocation. A general property of heterogeneous register
architectures is that the results of specific operations are always stored in well defined
datapath locations. This does not imply total register allocation because data
has to be routed through the datapath to locations required by other instructions.
Take for example operations add and mul in the target processor. Notice that
they implicitly define the primary storage resources that are used for the operation
result. In this case (observe Table 1), no register allocation task is required
to determine that registers a and p are respectively used to store the immediate
result of operations add and mul. Thus, partial allocation can be performed well
in advance, even before the task of breaking the edges of the expression DAG takes
place. Again, observe that this is only possible if an operation always uses the same
register file to store its immediate result. Consider for example the expression DAG
of

Figure

9. Notice that partial register allocation can be immediately performed
for registers a and p.
5.1.2 Natural Edges. We saw before in Figure 8 that some edges have specific
properties originating from the target architecture, which allow us to disconnect
them from the DAG without compromising optimality. These edges, termed natural
edges, are defined as follows.
Definition 3. If the instruction selection matching of edge (u; v) always produces
a sequence of data transfer operations in the datapath which pass through memory,
edge (u; v) is referred to as a natural edge.
(a) (b)
r
Fig. 10. Natural edges are identified by a single line segment: (a) (u; v) is natural; (b) (u; v) is
natural if r i has no self-loop in the RTG
Now given an expression DAG D, and a target architecture which has an acyclic
RTG. It can be shown that a number of edges in D are natural edges. In order to
do that let us state a set of lemmas.
Let r 1 and r 2 be a pair of registers in the datapath of an acyclic RTG architecture.
Also let , be a function which maps nodes in D into the set of
datapath locations R [ M , where R is the set of registers in the datapath and M
the set of memory positions.
Lemma 1. Let r 1 and r 2 be registers in the architecture RTG, such that there
exist no path from r 1 to r 2 . Therefore, any edge (u; v) in D for which
and is a natural edge.
Proof. Given that a path from registers r 1
to r 2
will be traversed whenever
instruction selection is performed on edge (u; v), then a memory operation will
always be selected during instruction selection on (u; v), and therefore (u; v) is a
natural edge (Figure 10(a)).
Lemma 2. Edges (u; v) for which are natural
edges only if no self-loop exists on register node r i in the RTG representation of the
target architecture (Figure 10(b)).
Proof. If an architecture has an acyclic RTG, then any loop in the RTG (which
is not a self-loop) will traverse memory. Thus, if register r i has no self-loop in the
RTG, then any loop starting at r i will go through memory. Therefore, a memory
operation will be selected whenever instruction selection is performed on edge (u; v).
Hence (u; v) is a natural edge.
Notice that the task of breaking natural edges does not introduce any new operations
into the DAG because, as the name implies, during the instruction selection
phase a memory operation is naturally selected due to constraints in the architecture
datapath topology. As a result, no potential optimality is lost by breaking
natural edges.
Example 3. Consider each one of the lemmas above and the RTG of Figure 6.
Observe the expression DAG of Figure 9 after natural edges have been identified.
(1) From Lemma 1 we can see that when r 1
a and r 2
every edge (u; v)
such that is a natural edge.
(2) Consider now Lemma 2. First take the situation when r From the
RTG of

Figure

6 observe that register p has no self-loop. Since the RTG is
acyclic, then any DAG edge (u; v) such that is a natural edge.
Now consider the case when r Register a in Figure 6 contains a self-loop
and thus nothing can be said regarding these edges.
5.1.3 Pseudo-Natural Edges. In the following two lemmas we show that DAG
edges can sometimes interact such that one edge out of a set of two edges must
result in storage in memory. The edges in this set are called pseudo-natural edges.
Lemma 3. Consider operation v and its operand nodes u and w in Figure 11(a).
If partial register allocation of these operations is such that
are (w; v) pseudo-natural edges.
Proof. Notice that no binary operation v can take both its operands simultaneously
from the same register. We have to consider here two situations:
Code Generation for Fixed-Point DSPs \Delta 17
w
(a) (b)
r
r
Fig. 11. The selected pseudo-natural edges are identified by a double line segment: (a) One of
the edges uses a loop in the RTG; (b) One of the edges goes through memory;
(a) If node r i has a self-loop in the architecture RTG, one of the edges, e.g.
could be matched by an instruction which takes one operand from r i .
On the other hand, when this same instruction matches the other edge, i.e.
(w; v), it will make use of a register which is contained in an RTG loop (not
a self-loop) that goes from r i back to r i . Similarly as in Lemma 2, matching
(w; v) will introduce a sequence of transfer operations which necessarily goes
through memory, making (w; v) and (u; v) pseudo-natural edges.
(b) If no self-loop node r i exists in the architecture RTG, then both edges are
natural edges according to Lemma 2.
Lemma 4. Consider operation v and its operand nodes u and w of Figure 11(b).
Let the partial register allocation of these nodes be such that
. If all RTG paths between each pair of nodes are such that only one path
does not go through memory, then (u; v) and (w; v) are pseudo-natural edges.
Proof. The proof is trivial and follows from the fact that since operation v
cannot take both of its operands from the same register r j at the same time, it has
to use two paths in the RTG to bring data from register r j . Since only one path
from r j to r i does not go through memory, then the other path has to pass through
memory.
Based on the lemmas above, we need to decide which edge between (u; v) and
(w; v) is to be disconnected from the DAG. Loss of optimality might occur depending
on which edge is selected. The selected pseudo-natural edge is identified using
a double line segment to distinguish it from natural edges. Unlike natural edges,
breaking pseudo-natural edges might result in compromising the optimality of code
generation for the component trees. However, there is a good chance that this
might not happen in actual practice.
Example 4. Consider Lemmas 3 and 4 above and the RTG of Figure 6: Observe
the expression DAG of Figure 9 after pseudo-natural edges have been identified.
Lemma 3 is satisfied for the case when r
(4) In this case, if r only one path exists in the RTG from p to
a which does not go through memory.
After rules 1-4 of Examples 3 and 4 are applied, the expression DAG of Figure 9
results. Each marked edge in Figure 9 has on its side the number corresponding to
a rule used from Examples 3 and 4.
5.2 Dismanteling Algorithm
The task of dismanteling an expression DAG may potentially introduce cyclic Read
After Write RAW dependencies between the resulting tree components leading to
an impossible schedule. A similar problem was also encountered in [Aho et al. 1977a]
and [Liao et al. 1995] when the authors studied the problem of scheduling worm-
graphs derived from DAGs in single-register architectures. Consider, for example,
(b)
(a)
Fig. 12. (a) Cyclic RAW dependency; (b) Constraining the tree scheduler
the reconvergent paths from nodes u to v and the component trees T 1
and T 2
of

Figure

12(a). Dismanteling the DAG of Figure 12(a) requires that at least one of
the edges of the multiple fanout nodes u and T 2
be disconnected. Assume that edges
have been selected as the edges to break. In this case, nodes u, v
and tree T 1
can be collapsed into a single component tree T 3
, dismanteling the DAG
into trees T 3
and T 4
. When an edge between two nodes is broken, a RAW edge is
introduced (dashed lines in Figure 12), in order to guarantee that the original data-dependencies
are preserved by the scheduler. In this case, the resulting RAW edges
form a cycle between component trees T 3
and T 4
, which results in an infeasible
schedule for the component trees.
Notice that dismanteling is also possible if edge (T 2 ; w) is broken instead of

Figure

12(b)). When this occurs, RAW edge (u; T 2 ) is brought into the
resulting component tree (T 3 ). As a consequence, the potential optimality of the
tree scheduler algorithm OptSchedule can not be guaranteed anymore, since now
it has to satisfy the constraint imposed by the new RAW edge inside T 3 . A possible
solution to this problem is to modify the tree scheduler algorithm such that it can
satisfy any RAW constraint inserted into the tree. Unfortunately, this is a very
difficult task for which an efficient solution seems not to exist. Hence, we have to
dismantle the DAG such as to avoid inserting RAW edges into the component trees.
From the two situations analyzed above, we can conclude that edges on both
reconvergent paths have to be disconnected in order to guarantee proper scheduling
Code Generation for Fixed-Point DSPs \Delta 19
of operations inside component trees and between component trees. An algorithm
which dismantles the DAG should disconnect edges by using as many natural and
pseudo-natural edges as possible. We have designed such an algorithm, which we
call Dismantle.
The Dismantle algorithm starts by first breaking all natural edges, since breaking
these edges adds no cost to the total cost of the final code. After that Dismantle
proceeds identifying reconvergent paths. It traverses paths in the DAG looking for
edges marked as pseudo-natural edges. If a pseudo-natural edge can be used to
break an existing reconvergent path the edge is broken. Otherwise the outgoing
edge which starts the reconvergent path at the corresponding multiple fanout node
is broken. These edges are marked with a black dot in Figure 13. At this point
all reconvergent paths in the expression DAG have been disconnected. Additional
edges are then broken such that no node ends up with more than one outgoing edge
(these edges are also marked with black dots). The resulting DAG after applying
algorithm Dismantle is shown in Figure 13. It decomposes the original DAG into
five expression trees Finally, these expression trees are scheduled and
code is generated for each expression tree.
a a a
a
a
Fig. 13. Resulting component trees after dismanteling
6. EXPERIMENTAL RESULTS
DSPstone [Zivojnovic et al. 1994] is a benchmark designed to evaluate the code
quality generated by compilers for different DSP processors. DSPstone is divided
into three benchmark suites: Application, DSP-kernel and C-kernel. The Application
benchmark consists of the program adpcm, a well-known speech encoding
algorithm. The DSP-kernel benchmark consists of a number of code fragments,
which cover the most often used DSP algorithms. The C-kernel suite aims to test
typical C program statements. The DSPstone project was supported by a number
of major DSP manufacturers (Analog Devices, AT&T, Motorola, NEC and Texas
Instruments). We used this benchmark for experimental evaluations.
Scheduling Algorithms
Tree Origin Left-first Right-first OptSchedule
real update 5 5 5
3 dot product 8 8 8
6 iir one biquad

Table

2. Number of cycles to compute expression trees using: Right-Left, Left-Right and
OptSchedule
6.1 Expression Trees
We have applied algorithm OptSchedule to expression trees extracted from programs
in the DSP-kernel benchmark. The metric used to compare the code was the number
of cycles that takes to compute the expression tree.
Observe from Table 2 that algorithm OptSchedule produces the best code when
compared with two SC schedules, what is expected since we have proved its opti-
mality. Notice that although SC schedules can sometimes produce optimal code,
it can also generate bad quality code, as it is the case for expression tree 6. We
can also verify that the same expression tree generates different code quality when
different SC schedules are used. The structure of the expression tree dictates the
best SC schedule, and this structure is a function of the way the programmer writes
the code.
6.2 DAG Types Distribution
Expression DAGs were classified in trees, leaf DAGs and full DAGs. Leaf DAGs
are DAGs for which only leaf nodes have outdegree greater than one. We classify
a DAG as a full DAG if it is neither a tree nor a leaf DAG. As one can see from

Table

3, the classification revealed that of all basic blocks analyzed 56% were trees,
DSP kernel Basic Blocks Trees Leaf DAGs DAGs
real update
dot product
iir one biquad 1
convolution
lms

Table

3. Types of DAGs found in typical digital signal processing algorithms
Code Generation for Fixed-Point DSPs \Delta 21
DAG DAG Hand-written Standard Dismantle
Origin Type Code Heuristic Heuristic
complex update F
matrix 1x3 L 5 5 0% 5 0%
iir one biquad F 15 17 13%
convolution
lms F 7 9 28% 8 14%

Table

4. Experiments with DAGs - Leaf DAG (L); Full DAG
38% leaf DAGs and 6% full DAGs. From the set of benchmarks in Table 3 we have
noticed that the majority of the basic blocks found in these programs are trees
and leaf DAGs. Another experiment was performed, this time using the DSPstone
application benchmark adpcm. As before, basic blocks were analyzed to determine
the frequency of trees, leaf DAGs and DAGs. In this case, 94% of the basic blocks
in this program were found to be trees, 3% leaf DAGs and 3% full DAGs. Although
dynamic counting of basic blocks is required in order to provide information on the
impact on execution time, one can reasonably argue that a large portion of this
program execution time is spent in processing expression trees. Thus, tree-based
code generation is very suitable for this application domain.
6.3 Expression DAGs
In

Table

4 we list a series of expression DAGs extracted from programs in the
DSP-kernel benchmark. We have selected the largest DAG found in each kernel for
the purpose of comparison with hand-written code. Hand-written assembly code
(or assembly reference code) for each DSP-kernel program is available from the
DSPstone benchmark suite [Zivojnovic et al. 1994].
Compiled code was generated for each DAG and the resulting number of cycles
for a single loop execution reported in Table 4. Compiled code was also generated
using a standard heuristic, which dismantles the DAG by breaking all edges at
multiple fanout nodes (column Standard Heuristic). Table 4 shows the number
of processor cycles and the overhead with respect to hand-written code. Notice
that the overhead is due only to the DAG dismanteling technique. The average
overhead when comparing the compiled (Dismantle Heuristic) and the assembly
reference code was 7%. Leaf nodes are treated the same way in both heuristics.
They are simply duplicated into different nodes - one for each outgoing edge. As a
consequence, both heuristics have the same performance for the case of leaf DAGs.
The average overhead (Dismantle Heuristic) for the case of full DAGs was higher
(11%) than for the case of leaf DAGs (4%). The discrepancy is due to the existence
of memory-register and immediate instructions in the processor ISA, which can have
zero cost multiple fanout operands when these are memory references or constant
values. Although the heuristic gains may seem very small, every byte matters,
since DSPs have restricted on-chip memory size, what makes the generation of high
22 \Delta Guido Araujo and Sharad Malik
quality code the most important goal for the compiler.
7. CONCLUSION
With the increasing demand for wireless and multimedia systems, it is expected
that the usage of DSPs will continue to grow. Inspite of this, research on compiling
techniques for DSPs has not received the adequate attention. These devices
continue to offer new research challenges which originate from the need for high
quality code at low cost and power consumption.
We have proposed an optimal O(n) instruction selection, register allocation, and
instruction scheduling algorithm for expression trees, for a class of heterogeneous
register DSP architectures which have acyclic RTGs. We then extend this by
proposing heuristics for the case when basic blocks are DAGs. This approach is
based on the concept of natural and pseudo-natural edges and seeks to use architectural
information to help in the task of dismanteling the expression DAG into a
forest of trees.
The question on how to generate good code for architectures which have cyclic
RTGs remains open though. As it was mentioned before, expression trees generated
in these architectures can also benefit from this optimality provided they are free
of any allocation deadlock. An interesting question which follows from that is how
many of expression trees with this property are generated in programs running on
these architectures. More work is under way in order to answer this and other
questions.

ACKNOWLEDGMENTS

This research was supported in part by the Brazilian Council for Research and Development
(CNPq) under contract 204033/87-0, and by the Institute of Computing
(unicamp), Brazil.



--R

Code generation using tree matching and dynamic programming.
Optimal code generation for expression trees.
Code generation for expressions with common subexpressions.
Code generation for machineswith multireg- ister operations

Generalizations of the Sethi-Ullman algorithm for register allocation
Optimal code generation for embedded memory non-homogeneous register architectures
Using register-transfer paths in code generation for heterogeneous memory-register architectures

Code generation for one-register machine
Instructions sets for evaluating arithmetic expressions.
Journal of the ACM
Engineering a simple
Computers and Intractability.
Pattern matching in trees.

Data routing: a paradigm for efficient data-path synthesis and code generation
DSP Processor Fundamentals: Architectures and Features.
Programmable DSP architectures: Part I.
Programmable DSP architectures: Part II.
Instruction selection using binate covering.

Marwedel and Goosens


Efficient computation of expressions with common subexpressions.
Complete register allocation problems.
The generation of optimal code for arithmetic expressions.
Journal of the ACM 17
Digital Signal Processing Applications with the TMS320 Family.
An olive twig.
On the optimal code generation for signal flow computation.

Automatic instruction code generation based on trellis diagrams.
Circuits and Systems

--TR
Compilers: principles, techniques, and tools
Generalization of the Sethi-Ullman algorithm for register allocation
Code generation using tree matching and dynamic programming
Digital signal processing applications with the TMS320 family (vol. 2)
Optimal code generation for embedded memory non-homogeneous register architectures
Instruction selection using binate covering for code size optimization
Optimal register assignment to loops for embedded code generation
Using register-transfer paths in code generation for heterogeneous memory-register architectures
Data routing
Tree-based mapping of algorithms to predefined structures
The Generation of Optimal Code for Arithmetic Expressions
The Generation of Optimal Code for Stack Machines
Optimal Code Generation for Expression Trees
Code Generation for a One-Register Machine
Code Generation for Expressions with Common Subexpressions
Efficient Computation of Expressions with Common Subexpressions
Pattern Matching in Trees
Instruction Sets for Evaluating Arithmetic Expressions
Code-generation for machines with multiregister operations
Code Generation for Embedded Processors
Computers and Intractability

--CTR
Jeonghun Cho , Yunheung Paek , David Whalley, Fast memory bank assignment for fixed-point digital signal processors, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.9 n.1, p.52-74, January 2004
Jeonghun Cho , Yunheung Paek , David Whalley, Efficient register and memory assignment for non-orthogonal architectures via graph coloring and MST algorithms, ACM SIGPLAN Notices, v.37 n.7, July 2002
Alain Pegatoquet , Emmanuel Gresset , Michel Auguin , Luc Bianco, Rapid development of optimized DSP code from a high level description through software estimations, Proceedings of the 36th ACM/IEEE conference on Design automation, p.823-826, June 21-25, 1999, New Orleans, Louisiana, United States
Shuvra S. Bhattacharyya , Praveen K. Murthy, The CBP Parameter: A Module Characterization Approach for DSP Software Optimization, Journal of VLSI Signal Processing Systems, v.38 n.2, p.131-146, September 2004
Minwook Ahn , Jooyeon Lee , Yunheung Paek, Optimistic coalescing for heterogeneous register architectures, ACM SIGPLAN Notices, v.42 n.7, July 2007
register allocation;scheduling;code generation