A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition) (798439), страница 33
Текст из файла (страница 33)
Some instructions correspondto 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). Inthis chapter we abbreviate the tree diagrams slightly: BINOP(PLUS, x, y) nodes will bewritten as +(x, y), and the actual values of CONST and TEMP nodes will not always beshown.The fundamental idea of instruction selection using a tree-based intermediate representation istiling the IR tree.
The tiles are the set of tree patterns corresponding to legal machineinstructions, 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 variableand a and x are frame-resident, results in a tree that can be tiled in many different ways. Twotilings, and the corresponding instruction sequences, are shown in Figure 9.2 (remember thata is really the frame offset of the pointer to an array).
In each case, tiles 1, 3, and 7 do not154correspond to any machine instructions, because they are just registers (TEMPs) alreadycontaining the right values.Figure 9.2: A tree tiled in two ways.Finally - assuming a "reasonable" set of tile patterns - it is always possible to tile the tree withtiny tiles, each covering only one node. In our example, such a tiling looks like this:ADDI r ← r + a10ADD r ← fp + r11LOAD r ← M[r + 0]11ADDI r ← r + 420MULr2 ← ri × r2ADDr1 ← r1 = r2ADDI r ← r + x20ADD r ← fp + r22LOAD r ← M[r + 0]22STORE M[r + 0] ← r12For a reasonable set of patterns, it is sufficient that each individual Tree node correspond tosome tile. It is usually possible to arrange for this; for example, the LOAD instruction can bemade to cover just a single MEM node by using a constant of 0, and so on.155OPTIMAL AND OPTIMUM TILINGSThe best tiling of a tree corresponds to an instruction sequence of least cost: the shortestsequence of instructions.
Or if the instructions take different amounts of time to execute, theleast-cost sequence has the lowest total time.Suppose we could give each kind of instruction a cost. Then we could define an optimumtiling as the one whose tiles sum to the lowest possible value. An optimal tiling is one whereno two adjacent tiles can be combined into a single tile of lower cost. If there is some treepattern that can be split into several tiles of lower combined cost, then we should remove thatpattern from our catalog of tiles before we begin.Every optimum tiling is also optimal, but not vice versa. For example, suppose everyinstruction costs one unit, except for MOVEM, which costs m units.
Then either Figure 9.2a isoptimum (if m > 1) or Figure 9.2b is optimum (if m < 1) or both (if m = 1); but both trees areoptimal.Optimum tiling is based on an idealized cost model. In reality, instructions are not selfcontained with individually attributable costs; nearby instructions interact in many ways, asdiscussed in Chapter 20.9.1 ALGORITHMS FOR INSTRUCTION SELECTIONThere are good algorithms for finding optimum and optimal tilings, but the algorithms foroptimal tilings are simpler, as you might expect.Complex instruction set computers (CISC) have instructions that accomplish severaloperations each.
The tiles for these instructions are quite large, and the difference betweenoptimum and optimal tilings - while never very large - is at least sometimes noticeable.Most architectures of modern design are reduced instruction set computers (RISC). EachRISC instruction accomplishes just a small number of operations (all the Jouette instructionsexcept MOVEM are typical RISC instructions). Since the tiles are small and of uniform cost,there is usually no difference at all between optimum and optimal tilings.
Thus, the simplertiling algorithms suffice.MAXIMAL MUNCHThe algorithm for optimal tiling is called maximal munch. It is quite simple. Starting at theroot of the tree, find the largest tile that fits. Cover the root node - and perhaps several othernodes near the root - with this tile, leaving several subtrees. Now repeat the same algorithmfor each subtree.As each tile is placed, the instruction corresponding to that tile is generated. The maximalmunch algorithm generates the instructions in reverse order - after all, the instruction at theroot is the first to be generated, but it can only execute after the other instructions haveproduced operand values in registers.The "largest tile" is the one with the most nodes.
For example, the tile for ADD has one node,the tile for SUBI has two nodes, and the tiles for STORE and MOVEM have three nodeseach.156If two tiles of equal size match at the root, then the choice between them is arbitrary. Thus, inthe tree of Figure 9.2, STORE and MOVEM both match, and either can be chosen.Maximal munch is quite straightforward to implement in Java. Simply write two recursivefunctions, munchStm for statements and munchExp for expressions. Each clause of munchExpwill match one tile.
The clauses are ordered in order of tile preference (biggest tiles first).Program 9.3 is a partial example of a Jouette code generator based on the maximal munchalgorithm. Executing this program on the tree of Figure 9.2 will match the first clause ofmunchStm; this will call munchExp to emit all the instructions for the operands of the STORE,followed by the STORE itself. Program 9.3 does not show how the registers are chosen andoperand syntax is specified for the instructions; we are concerned here only with the patternmatching of tiles.PROGRAM 9.3: Maximal Munch in Java.void munchMove(MEM dst, Exp src) {// MOVE(MEM(BINOP(PLUS, e1, CONST(i))), e2)if (dst.exp instanceof BINOP && ((BINOP)dst.exp).oper==BINOP.PLUS&& ((BINOP)dst.exp).right instanceof CONST){munchExp(((BINOP)dst.exp).left); munchExp(src); emit("STORE");}// MOVE(MEM(BINOP(PLUS, CONST(i), e1)), e2)else if (dst.exp instanceof BINOP && ((BINOP)dst.exp).oper==BINOP.PLUS&& ((BINOP)dst.exp).left instanceof CONST){munchExp(((BINOP)dst.exp).right); munchExp(src); emit("STORE");}// MOVE(MEM(e1), MEM(e2))else if (src instanceof MEM){munchExp(dst.exp); munchExp(((MEM)src).exp); emit("MOVEM");}// MOVE(MEM(e1, e2)else{munchExp(dst.exp); munchExp(src); emit("STORE");}}void munchMove(TEMP dst, Exp src) {// MOVE(TEMP(t1), e)munchExp(src); emit("ADD");}void munchMove(Exp dst, Exp src) {// MOVE(d, e)if (dst instanceof MEM) munchMove((MEM)dst,src);else if (dst instanceof TEMP) munchMove((TEMP)dst,src);}void munchStm(Stm s) {if (s instanceof MOVE) munchMove(((MOVE)s).dst, ((MOVE)s).src);⋮ // CALL, JUMP, CJUMP unimplemented here}void munchExp(Exp)MEM(BINOP(PLUS, e1, CONST(i))) ⇒ munchExp(e1); emit("LOAD");MEM(BINOP(PLUS, CONST(i), e1)) ⇒ munchExp(e1); emit("LOAD");MEM(CONST(i)) ⇒ emit("LOAD");MEM(e1)⇒ munchExp(e1); emit("LOAD");BINOP(PLUS, e1, CONST(i)) ⇒ munchExp(e1); emit("ADDI");BINOP(PLUS, CONST(i, e1) ⇒ munchExp(e1); emit("ADDI");CONST(i) ⇒ munchExp(e1); emit("ADDI");BINOP(PLUS, e1, CONST(i)) ⇒ munchExp(e1); emit("ADD");TEMP(t) ⇒ {}157If, for each node-type in the Tree language, there exists a single-node tile pattern, thenmaximal munch cannot get "stuck" with no tile to match some subtree.DYNAMIC PROGRAMMINGMaximal munch always finds an optimal tiling, but not necessarily an optimum.
A dynamicprogramming algorithm can find the optimum. In general, dynamic programming is atechnique for finding optimum solutions for a whole problem based on the optimum solutionof each subproblem; here the subproblems are the tilings of the subtrees.The dynamic-programming algorithm assigns a cost to every node in the tree. The cost is thesum of the instruction costs of the best instruction sequence that can tile the subtree rooted atthat node.This algorithm works bottom-up, in contrast to maximal munch, which works top-down.
First,the costs of all the children (and grandchildren, etc.) of node n are found recursively. Then,each tree pattern (tile kind) is matched against node n.Each tile has zero or more leaves. In Figure 9.1 the leaves are represented as edges whosebottom ends exit the tile.
The leaves of a tile are places where subtrees can be attached.For each tile t of cost c that matches at node n, there will be zero or more subtrees sicorresponding to the leaves of the tile. The cost ci of each subtree has already been computed(because the algorithm works bottom-up). So the cost of matching tile t is just c + ∑ci.Of all the tiles tj that match at node n, the one with the minimum-cost match is chosen, andthe (minimum) cost of node n is thus computed. For example, consider this tree:The only tile that matches CONST 1 is an ADDI instruction with cost 1. Similarly, CONST 2has cost 1.
Several tiles match the + node:The ADD tile has two leaves, but the ADDI tile has only one leaf. In matching the first ADDIpattern, we are saying "though we computed the cost of tiling CONST 2, we are not going touse that information." If we choose to use the first ADDI pattern, then CONST 2 will not bethe root of any tile, and its cost will be ignored. In this case, either of the two ADDI tiles leadsto the minimum cost for the + node, and the choice is arbitrary.
The + node gets a cost of 2.Now, several tiles match the MEM node:158Either of the last two matches will be optimum.Once the cost of the root node (and thus the entire tree) is found, the instruction emissionphase begins. The algorithm is as follows:Emission(node n): for each leaf li of the tile selected at node n, perform Emission(li).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
