High-Performance Embedded Computing

166 Chapter 3 Programs

r1 and r2 using the l instruction; all the cycles between r1 and r2 include the

memory node. This condition ensures that values can be spilled to main memory

when needed. Based on this property, Araujo and Malik showed that expression

trees can always be scheduled without a memory spill.

They use a tree-grammar parser to select instructions and allocate registers;

the patterns that define the instructions include the registers used by the instruc-

tions. They then use an O(n) algorithm, shown in Figure 3-11, to schedule the

instructions.

Figure 3-11 The Araujo and Malik instruction-scheduling algorithm. From Araujo and

Malik [A ...