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

To be able to create arbitrarily many temps and moves, and rely on the register allocatorto clean them up, greatly simplifies procedure-calling sequences and code generation.PROGRAM PROCEDURE ENTRY/EXITImplement the rest of the Frame module, which contains all the machine-dependent parts ofthe compiler: register sets, calling sequences, and activation record (frame) layout.Program 12.1 shows the Frame class. Most of this interface has been described elsewhere.What remains isPROGRAM 12.1: Package Frame.package Frame;import Temp.Temp;public abstractabstract publicabstract publicabstract publicabstract publicabstract publicabstract public153)abstract publicclass Frame implements Temp.TempMap {Temp RV();(see p.

157)Temp FP();(p. 143)Temp.TempList registers();String tempMap(Temp temp);int wordSize(); (p. 143)Tree.Exp externalCall(String func,Tree.ExpList args);Frame newFrame(Temp.Label name,Util.BoolList formals);(p. 127)public AccessList formals;(p. 128)public Temp.Label name;(p. 127)abstract public Access allocLocal(boolean escape);(p. 129)abstract public Tree.Stm procEntryExit1(Tree.Stm body);(p. 251)abstract public Assem.InstrList procEntryExit2(Assem.InstrList body);199)abstract public Proc procEntryExit3(Assem.InstrList body);abstract public Assem.InstrList codegen(Tree.Stm stm);(p. 196)}•••(p.(p.registers A list of all the register names on the machine, which can be used as "colors"for register allocation.tempMap For each machine register, the Frame module maintains a particular Tempthat serves as the "precolored temporary" that stands for the register.

These tempsappear in the Assem instructions generated from CALL nodes, in procedure entrysequences generated by procEntryExit1, and so on. The tempMap tells the "color" ofeach of these precolored temps.procEntryExit1 For each incoming register parameter, move it to the place fromwhich it is seen from within the function. This could be a fresh temporary.

One goodway to handle this is for newFrame to create a sequence of Tree.MOVE statements as it212creates all the formal parameter "accesses." newFrame can put this into the frame datastructure, and procEntryExit1 can just concatenate it onto the procedure body.Also concat enated to the body are statements for saving and restoring of callee-saveregisters (including the return-address register). If your register allocator does notimplement spilling, all the callee-save (and return-address) registers should be writtento the frame at the beginning of the procedure body and fetched back afterward.Therefore, procEntryExit1 should call allocLocal for each register to be saved, andgenerate Tree.MOVE instructions to save and restore the registers.

With luck, savingand restoring the callee-save registers will give the register allocator enough headroomto work with, so that some nontrivial programs can be compiled. Of course, someprograms just cannot be compiled without spilling.If your register allocator implements spilling, then the callee-save registers should notalways be written to the frame.

Instead, if the register allocator needs the space, it maychoose to spill only some of the callee-save registers. But "precolored" temporaries arenever spilled; so procEntryExit1 should make up new temporaries for each calleesave (and return-address) register. On entry, it should move all these registers to theirnew temporary locations, and on exit, it should move them back. Of course, thesemoves (for nonspilled registers) will be eliminated by register coalescing, so they costnothing.•procEntryExit3 Creates the procedure prologue and epilogue assembly language.First (for some machines) it calculates the size of the outgoing parameter space in theframe. This is equal to the maximum number of outgoing parameters of any CALLinstruction in the procedure body. Unfortunately, after conversion to Assem trees theprocedure calls have been separated from their arguments, so the outgoing parametersare not obvious.

Either procEntryExit2 should scan the body and record thisinformation in some new component of the frame type, or procEntryExit3 shoulduse the maximum legal value.Once this is known, the assembly language for procedure entry, stackpointeradjustment, and procedure exit can be put together; these are the prologue andepilogue.PROGRAM MAKING IT WORKMake your compiler generate working code that runs.The file $MINIJAVA/chap12/runtime.c is a C-language file containing several externalfunctions useful to your MiniJava program. These are generally reached by externalCallfrom code generated by your compiler. You may modify this as necessary.Write a module Main that calls on all the other modules to produce an assembly language fileprog.s for each input program prog.java. This assembly language program should beassembled (producing prog.o) and linked with runtime.o to produce an executable file.Programming projectsAfter your MiniJava compiler is done, here are some ideas for further work:213•••••••••••12.1 Write a garbage collector (in C) for your MiniJava compiler.

You will need tomake some modifications to the compiler itself to add descriptors to records and stackframes (see Chapter 13).12.2 Implement inner classes is MiniJava.12.3 Implement dataflow analyses such as reaching definitions and availableexpressions and use them to implement some of the optimizations discussed inChapter 17.12.4 Figure out other approaches to improving the assembly language generated byyour compiler.

Discuss; perhaps implement.12.5 Implement instruction scheduling to fill branch-delay and load-delay slots in theassembly language (for a machine such as the Sparc). Or discuss how such a modulecould be integrated into the existing compiler; what interfaces would have to change,and in what ways?12.6 Implement "software pipelining" (instruction scheduling around loop iterations)in your compiler (see Chapter 20).12.7 Analyze how adequate the MiniJava language itself would be for writing acompiler. What are the smallest possible additions/changes that would make it a muchmore useful language?12.8 In the MiniJava language, some object types are recursive and must beimplemented as pointers; that is, a value of that type might contain a pointer to anothervalue of the same type (directly or indirectly). But some object types are not recursive,so they could be implemented without pointers.

Modify your compiler to takeadvantage of this by keeping nonrecursive records in the stack frame instead of on theheap.12.9 Similarly, some arrays have bounds that are known at compile time, are notrecursive, and are not assigned to other array variables. Modify your compiler so thatthese arrays are implemented right in the stack frame.12.10 Implement inline expansion of functions (see Section 15.4).12.11 Suppose an ordinary MiniJava program were to run on a parallel machine (amultiprocessor)? How could the compiler automatically make a parallel program outof the original sequential one? Research the approaches.214Part Two: Advanced TopicsChapter ListChapter 13: Garbage CollectionChapter 14: Object-Oriented LanguagesChapter 15: Functional Programming LanguagesChapter 16: Polymorphic TypesChapter 17: Dataflow AnalysisChapter 18: Loop OptimizationsChapter 19: Static Single-Assignment FormChapter 20: Pipelining and SchedulingChapter 21: The Memory HierarchyAppendix A: MiniJava Language Reference Manual215Chapter 13: Garbage Collectiongar-bage: unwanted or useless materialWebster's DictionaryOVERVIEWHeap-allocated records that are not reachable by any chain of pointers from program variablesare garbage.

The memory occupied by garbage should be reclaimed for use in allocating newrecords. This process is called garbage collection, and is performed not by the compiler butby the runtime system (the support programs linked with the compiled code).Ideally, we would say that any record that is not dynamically live (will not be used in thefuture of the computation) is garbage. But, as Section 10.1 explains, it is not always possibleto know whether a variable is live. So we will use a conservative approximation: We willrequire the compiler to guarantee that any live record is reachable; we will ask the compiler tominimize the number of reachable records that are not live; and we will preserve all reachablerecords, even if some of them might not be live.Figure 13.1 shows a Java program ready to undergo garbage collection (at the point markedgarbage-collect here).

There are only three program variables in scope: p, q, and r.Figure 13.1: A heap to be garbage collected. Class descriptors are not shown in the diagram.21613.1 MARK-AND-SWEEP COLLECTIONProgram variables and heap-allocated records form a directed graph. The variables are rootsof this graph. A node n is reachable if there is a path of directed edges r → … → n starting atsome root r. A graph-search algorithm such as depth-first search (Algorithm 13.2) can markall the reachable nodes.ALGORITHM 13.2: Depth-first search.function DFS(x)if x is a pointer into the heapif record x is not markedmark xfor each field fi of record xDFS(x. fi)Any node not marked must be garbage, and should be reclaimed.

This can be done by a sweepof the entire heap, from its first address to its last, looking for nodes that are not marked(Algorithm 13.3). These are garbage and can be linked together in a linked list (the freelist).The sweep phase should also unmark all the marked nodes, in preparation for the nextgarbage collection.ALGORITHM 13.3: Mark-and-sweep garbage collection.Mark phase:for each root vDFS(v)Sweep phase:p ← first address in heapwhile p < last address in heapif record p is markedunmark pelse let f1 be the first field in pp.

f1 ← freelistfreelist ← pp ← p+(size of record p)After the garbage collection, the compiled program resumes execution. Whenever it wants toheap-allocate a new record, it gets a record from the freelist. When the freelist becomesempty, that is a good time to do another garbage collection to replenish the freelist.Cost of garbage collection Depth-first search takes time proportional to the number of nodesit marks, that is, time proportional to the amount of reachable data. The sweep phase takestime proportional to the size of the heap. Suppose there are R words of reachable data in aheap of size H. Then the cost of one garbage collection is c1R + c2H for some constants c1 andc2; for example, c1 might be 10 instructions and c2 might be 3 instructions.The "good" that collection does is to replenish the freelist with H − R words of usablememory.