Java Reference
In-Depth Information
lw $t1,i
mul $t1,$t1,4
lw $t2,a($fp)
addi $t2,$t2,1
sw
$t2,b($t1)
Figure 13.29: MIPS code for b[i]=a+1
13.5.1
Instruction Selection Using BURS
It is often the case that more than one instruction sequence can implement
the same construct. In terms of IR trees, di
ff
erent reductions of the same tree,
yielding di
erent instruction sequences, may be possible. How can we choose
the instruction sequence to be generated?
A very elegant approach involves assigning costs to instruction patterns.
The
cost
of an instruction is set when a code generator is built. This cost
may be the size of an instruction, its execution speed, the number of memory
references the instruction makes, or any criterion that measures how “good”
an instruction is. When given a choice, we will prefer a cheaper instruction
over a more expensive one.
Now matching of instruction patterns to an IR tree is generalized so that
a
least-cost cover
is obtained. That is, the pattern matcher guarantees that
the matches it selects have the lowest possible cost. Thus, using the mea-
sure of quality selected when the code generator was built, the best possible
instruction sequence is generated.
To guarantee that a least-cost cover of an IR tree is found, we use
dynamic
programming
. Starting at the leaves of the tree, we mark each leaf with
the lowest cost possible to reduce the leaf to each of the nonterminals. (A
nonterminal
, as in context-free productions, is the symbol that appears on
the left-hand side of an instruction pattern). Next, we consider the interior
nodes just above the leaves. Each instruction pattern that correctly matches
the interior node and has the correct number of children is considered. The cost
of the pattern plus the costs of the node's children are considered. The node
is marked with the cheapest cost possible to reduce the tree to each possible
nonterminal. We continue traversing the IR tree, until the root node is reached.
The lowest cost found to reduce the tree to any nonterminal is selected as the
best cover.
IR trees for a large program or subroutine can easily comprise tens or
hundreds of thousands of nodes. The extensive processing needed for each
node would appear to make least-cost instruction selection using patterns a
very slow process. Happily this is not the case.
ff
