Previous    Next

TREE PATTERNS

We can express a machine instruction as a fragment of an IR tree, called a tree pattern. Then instruction selection becomes the task of tiling the tree with a minimal set of tree patterns. For purposes of illustration, we invent an instruction set: the Jouette architecture. The arithmetic and memory instructions of Jouette are shown in Image 9.1. On this machine, register r0 always contains zero.

Java Click To expand
Image 9.1: Arithmetic and memory instructions. The notation M[x] denotes the memory word at address x.

Each instruction above the double line in Image 9.1 produces a result in a register. The very first entry is not really an instruction, but expresses the idea that a TEMP node is implemented as a register, so it can "produce a result in a register" without executing any instructions at all. The instructions below the double line do not produce results in registers, but are executed only for side effects on memory. For each instruction, the tree patterns it implements are shown. Some instructions correspond to more than one tree pattern; the alternate patterns are obtained for commutative operators (+ and *), and in some cases where a register or constant can be zero (LOAD and STORE). In this chapter we abbreviate the tree diagrams slightly: BINOP(PLUS, x, y) nodes will be written as +(x, y), and the actual values of CONST and TEMP nodes will not always be shown. The fundamental idea of instruction selection using a tree-based intermediate representation is tiling the IR tree. The tiles are the set of tree patterns corresponding to legal machine instructions, and the goal is to cover the tree with nonoverlapping tiles. For example, the MiniJava-language expression such as a[i] := x, where i is a register variable and a and x are frame-resident, results in a tree that can be tiled in many different ways. Two tilings, and the corresponding instruction sequences, are shown in Image 9.2 (remember that a is really the frame offset of the pointer to an array). In each case, tiles 1, 3, and 7 do not correspond to any machine instructions, because they are just registers (TEMPs) already containing the right values.

Java Click To expand
Image 9.2: A tree tiled in two ways.

Finally - assuming a "reasonable" set of tile patterns - it is always possible to tile the tree with tiny tiles, each covering only one node. In our example, such a tiling looks like this:

ADDI

r1r0 + a

ADD

r1fp + r1

LOAD

r1M[r1 + 0]

ADDI

r2r0 + 4

MUL

r2ri × r2

ADD

r1r1 = r2

ADDI

r2r0 + x

ADD

r2fp + r2

LOAD

r2M[r2 + 0]

STORE

M[r1 + 0] ← r2

For a reasonable set of patterns, it is sufficient that each individual Tree node correspond to some tile. It is usually possible to arrange for this; for example, the LOAD instruction can be made to cover just a single MEM node by using a constant of 0, and so on.


JaVaScreenshot Previous    Next
Comments