A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 35

Therefore, we should try to use the sequence on the right when possible.But the issue here turns into one of register allocation, not of instruction speed; so wedefer its solution to the register allocator.5. Several addressing modes: An addressing mode that accomplishes six thingstypically takes six steps to execute.

Thus, these instructions are often no faster than themulti-instruction sequences they replace. They have only two advantages: They"trash" fewer registers (such as the register eax in the previous example), and theyhave a shorter instruction encoding. With some work, treematching instructionselection can be made to select CISC addressing modes, but programs can be just asfast using the simple RISC-like instructions.6.

Variable-length instructions: This is not really a problem for the compiler; once theinstructions are selected, it is a trivial (though tedious) matter for the assembler to emitthe encodings.7. Instructions with side effects: Some machines have an "autoincrement" memoryfetch instruction whose effect isr2 ← M[r1]; r1← r1 + 4This instruction is difficult to model using tree patterns, since it produces two results. Thereare three solutions to this problem:a.

Ignore the autoincrement instructions, and hope they go away. This is an increasinglysuccessful solution, as few modern machines have multiple-side-effect instructions.b. Try to match special idioms in an ad hoc way, within the context of a tree patternmatching code generator.c. Use a different instruction algorithm entirely, one based on DAG patterns instead oftree patterns.Several of these solutions depend critically on the register allocator to eliminate moveinstructions and to be smart about spilling; see Chapter 11.1649.3 INSTRUCTION SELECTION FOR THE MiniJava COMPILERPattern-matching of "tiles" is simple (if tedious) in Java, as shown in Program 9.3. But thisfigure does not show what to do with each pattern match.

It is all very well to print the nameof the instruction, but which registers should these instructions use?In a tree tiled by instruction patterns, the root of each tile will correspond to someintermediate result held in a register. Register allocation is the act of assigning registernumbers to each such node.The instruction selection phase can simultaneously do register allocation.

However, manyaspects of register allocation are independent of the particular target-machine instruction set,and it is a shame to duplicate the registerallocation algorithm for each target machine. Thus,register allocation should come either before or after instruction selection.Before instruction selection, it is not even known which tree nodes will need registers to holdtheir results, since only the roots of tiles (and not other labeled nodes within tiles) requireexplicit registers. Thus, register allocation before instruction selection cannot be veryaccurate. But some compilers do it anyway, to avoid the need to describe machine instructionswithout the real registers filled in.We will do register allocation after instruction selection.

The instruction selection phase willgenerate instructions without quite knowing which registers the instructions use.ABSTRACT ASSEMBLY LANGUAGE INSTRUCTIONSWe will invent a data type for "assembly language instruction without register assignments",called Assem.Instr:package Assem;import Temp.TempList;public abstract class Instr {public String assem;public abstract TempList use();public abstract TempList def();public abstract Targets jumps();public String format(Temp.TempMap m);}public Targets(Temp.LabelList labels);public OPER(String assem, TempList dst, TempList src,Temp.LabelList jump);public OPER(String assem, TempList dst, TempList src);public MOVE(String assem, Temp dst, Temp src);public LABEL(String assem, Temp.Label label);An OPER holds an assembly language instruction assem, a list of operand registers src, and alist of result registers dst. Any of these lists may be empty.

Operations that always fallthrough to the next instruction are constructed with OPER(assem,dst,src) and the jumps()method will return null; other operations have a list of "target" labels to which they mayjump (this list must explicitly include the next instruction if it is possible to fall through to it).The use() method returns the src list, and the def() method returns the dst list, either ofwhich may be null.165A LABEL is a point in a program to which jumps may go. It has an assem componentshowing how the label will look in the assembly language program and a label componentidentifying which label symbol was used.A MOVE is like an OPER, but must perform only data transfer.

Then, if the dst and srctemporaries are assigned to the same register, the MOVE can later be deleted. The use()method returns a singleton list src, and the def() method returns a singleton list dst.Calling i.format(m) formats an assembly instruction as a string; m is an object implementingthe TempMap interface, which contains a method to give the register assignment (or perhapsjust the name) of every temp.package Temp;public interface TempMap {public String tempMap(Temp.Temp t);}Machine independence.

The Assem.Instr class is independent of the chosen target-machineassembly language (though it is tuned for machines with only one class of register). If thetarget machine is a Sparc, then the assem strings will be Sparc assembly language. We willuse Jouette assembly language for illustration.For example, the treecould be translated into Jouette assembly language asnew OPER("LOAD 'd0 <- M['s0+8]",new TempList(new Temp(), null),new TempList(frame.FP(), null));This instruction needs some explanation.

The actual assembly language of Jouette, afterregister allocation, might beLOAD r1 <- M[r27+8]assuming that register r27 is the frame pointer fp and that the register allocator decided toassign the new temp to register r1.Butthe Assem instruction does not know about registerassignments; instead, it just talks of the sources and destination of each instruction. ThisLOAD instruction has one source register, which is referred to as ‘s0, and one destinationregister, referred to as ‘d0.Another example will be useful. The tree166could be translated asassemdst srcADDI ‘d0 <- ‘s0+3t908 t87LOAD ‘d0 <- M[‘s0+0] t909 t92MUL ‘d0 <- ‘s0*‘s1t910 t908,t909where t908, t909, and t910 are temporaries newly chosen by the instruction selector.After register allocation the assembly language might look like:ADDILOADMULr1 <- r12+3r2 <- M[r13+0]r1 <- r1 * r2The string of an instr may refer to source registers ‘s0, ‘s1, … ‘s(k − 1), and destinationregisters ‘d0, ‘d1, etc.

Jumps are OPER instructions that refer to labels ‘j0, ‘j1, etc.Conditional jumps, which may branch away or fall through, typically have two labels in thejump list but refer to only one of them in the assem string.Two-address instructions Some machines have arithmetic instructions with two operands,where one of the operands is both a source and a destination. The instruction add t1,t2,which has the effect of t1 ← t1 + t2, can be described asassemadd ‘d0,‘s1dstt1srct1, t2where ‘s0 is implicitly, but not explicitly, mentioned in the assem string.PRODUCING ASSEMBLY INSTRUCTIONSNow it is a simple matter to write the right-hand sides of the pattern-matching clauses that"munch" Tree expressions into Assem instructions.

We will show some examples from theJouette code generator, but the same ideas apply to code generators for real machines.The functions munchStm and munchExp will produce Assem instructions, bottom-up, as sideeffects. MunchExp returns the temporary in which the result is held.Temp.Temp munchExp(Tree.Exp e);voidmunchStm(Tree.Stm s);The "actions" of the munchExp clauses of Program 9.3 can be written as shown in Programs9.5 and 9.6.PROGRAM 9.5: Assem-instructions for munchStm.TempList L(Temp h, TempList t) {return new TempList(h,t);}munchStm(SEQ(a,b)){munchStm(a); munchStm(b);}munchStm(MOVE(MEM(BINOP(PLUS,e1,CONST(i))),e2))emit(new OPER("STORE M['s0+" + i + "] <- 's1\n",null, L(munchExp(e1), L(munchExp(e2), null))));167munchStm(MOVE(MEM(BINOP(PLUS,CONST(i),e1)),e2))emit(new OPER("STORE M['s0+" + i + "] <- 's1\n",null, L(munchExp(e1), L(munchExp(e2), null))));munchStm(MOVE(MEM(e1),MEM(e2)))emit(new OPER("MOVE M['s0] <- M['s1]\n",null, L(munchExp(e1), L(munchExp(e2), null))));munchStm(MOVE(MEM(CONST(i)),e2))emit(new OPER("STORE M[r0+" + i + "] <- 's0\n",null, L(munchExp(e2), null)));munchStm(MOVE(MEM(e1),e2))emit(new OPER("STORE M['s0] <- 's1\n",null, L(munchExp(e1), L(munchExp(e2), null))));munchStm(MOVE(TEMP(i), e2))emit(new OPER("ADD 'd0 <- 's0 + r0\n",L(i,null), L(munchExp(e2), null)));munchStm(LABEL(lab))emit(new Assem.LABEL(lab.toString() + ":\n", lab));PROGRAM 9.6: Assem-instructions for munchExp.munchExp(MEM(BINOP(PLUS,e1,CONST(i))))Temp r = new Temp();emit(new OPER("LOAD 'd0 <- M['s0+" + i + "]\n",L(r,null), L(munchExp(e1),null)));return r;munchExp(MEM(BINOP(PLUS,CONST(i),e1)))Temp r = new Temp();emit(new OPER("LOAD 'd0 <- M['s0+" + i + "]\n",L(r,null), L(munchExp(e1),null)));return r;munchExp(MEM(CONST(i)))Temp r = new Temp();emit(new OPER("LOAD 'd0 <- M[r0+" + i + "]\n",L(r,null), null));return r;munchExp(MEM(e1))Temp r = new Temp();emit(new OPER("LOAD 'd0 <- M['s0+0]\n",L(r,null), L(munchExp(e1),null)));return r;munchExp(BINOP(PLUS,e1,CONST(i)))Temp r = new Temp();emit(new OPER("ADDI 'd0 <- 's0+" + i + "\n",L(r,null), L(munchExp(e1),null)));return r;munchExp(BINOP(PLUS,CONST(i),e1))Temp r = new Temp();emit(new OPER("ADDI 'd0 <- 's0+" + i + "\n",L(r,null), L(munchExp(e1),null)));return r;munchExp(CONST(i))Temp r = new Temp();emit(new OPER("ADDI 'd0 <- r0+" + i + "\n",null, L(munchExp(e1),null)));return r;munchExp(BINOP(PLUS,e1,e2))Temp r = new Temp();emit(new OPER("ADD 'd0 <- 's0+'s1\n",L(r,null), L(munchExp(e1),L(munchExp(e2),null))));return r;munchExp(TEMP(t))return t;168The emit function just accumulates a list of instructions to be returned later, as shown inProgram 9.7.PROGRAM 9.7: The Codegen class.package Jouette;public class Codegen {Frame frame;public Codegen(Frame f) {frame=f;}private Assem.InstrList ilist=null, last=null;private void emit(Assem.Instr inst) {if (last!=null)last = last.tail = new Assem.InstrList(inst,null);else last = ilist = new Assem.InstrList(inst,null);}voidmunchStm(Tree.Stm s) { ...