Java Reference
In-Depth Information
(c)
(a)
(b)
=
=
=
+
+
+
+
+
+
*
fetch
*
fetch
b
1
b
1
reg
b
fetch
1
fetch
+
+
4
reg
4
+
i
$fp
a
$fp
a
$fp a
(d)
(e)
(f)
=
=
void
+
+
+
reg
b
reg
reg 1
b
reg
Figure 13.28: Instruction Selection Using Patterns
(parsed) with adjacent patterns. That is, we find a subtree in the IR translation
that matches exactly the pattern for some instruction. That subtree is then
replaced with the pattern's left-hand side. The process is repeated until the
entire IR tree is reduced to a single node. This is very similar to ordinary
bottom-up parsing (Chapter 6).
As instructionpatterns arematched, their correspondingmachine-language
instructions are generated. Registers can be allocated “on the fly” using the
techniques of Section 13.3.1. Alternatively, pseudo-registers can be allocated
as code is generated, and then later mapped to real registers using the graph
coloring techniques of Section 13.3.2.
As an example, reconsider the IR tree corresponding to b[i]=a+1 shown
in Figure 13.28 (tree a). We first match a load of i (tree b). Next, a multiply
by 4 is matched (tree c). Then, an indexed load is generated for the local
variable a (tree d). Finally, an add-immediate (tree e) and a store instruction
(tree f) reduce the IR tree to void. The instructions generated (assuming calls
to
get
R
eg
and
free
R
eg
as code is generated) are shown in Figure 13.29.
