A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 25
Описание файла
PDF-файл из архива "A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition)", который расположен в категории "". Всё это находится в предмете "конструирование компиляторов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 25 страницы из PDF
If thereis no interference of the type shown in function m, then (on the MIPS) the allocator will takecare to choose register r4 to hold t157 and r5 to hold t158. Then the move instructions will beunnecessary and will be deleted at that time.See also pages 157 and 251 for more discussion of the view shift.LOCAL VARIABLESSome local variables are kept in the frame; others are kept in registers. To allocate a new localvariable in a frame f, the translation phase callsf.allocLocal(false)This returns an InFrame access with an offset from the frame pointer. For example, to allocatetwo local variables on the Sparc, allocLocal would be called twice, returning successivelyInFrame(-4) and InFrame(-8), which are standard Sparc frame-pointer offsets for localvariables.The boolean argument to allocLocal specifies whether the new variable escapes and needsto go in the frame; if it is false, then the variable can be allocated in a register.
Thus,f.allocLocal(false) might create InReg(t481).For MiniJava, that no variables escape. This is because in MiniJava:••••there is no nesting of classes and methods;it is not possible to take the address of a variable;integers and booleans are passed by value; andobjects, including integer arrays, can be represented as pointers that are alsopassedbyvalue.115The calls to allocLocal need not come immediately after the frame is created.
In manylanguages, there may be variable-declaration blocks nested inside the body of a function. Forexample,void f(){int v=6;print(v);{int v=7;print(v);}print(v);{int v=8;print(v);}print(v);}In this case there are three different variables v. The program will print the sequence 6 7 6 8 6.As each variable declaration is encountered in processing the program, we will allocate atemporary or new space in the frame, associated with the name v. As each end (or closingbrace) is encountered, the association with v will be forgotten - but the space is still reservedin the frame. Thus, there will be a distinct temporary or frame slot for every variable declaredwithin the entire function.The register allocator will use as few registers as possible to represent the temporaries.
In thisexample, the second and third v variables (initialized to 7 and 8) could be held in the sameregister. A clever compiler might also optimize the size of the frame by noticing when twoframe-resident variables could be allocated to the same slot.TEMPORARIES AND LABELSThe compiler's translation phase will want to choose registers for parameters and localvariables, and choose machine-code addresses for procedure bodies. But it is too early todetermine exactly which registers are available, or exactly where a procedure body will belocated. We use the word temporary to mean a value that is temporarily held in a register, andthe word label to mean some machine-language location whose exact address is yet to bedetermined - just like a label in assembly language.Temps are abstract names for local variables; labels are abstract names for static memoryaddresses.
The Temp module manages these two distinct sets of names.package Temp;public class Temp {public String toString();public Temp();}public class Label {public String toString();public Label();public Label(String s);public Label(Symbol s);}public class TempList {...}public class LabelList {...}116new Temp.Temp() returns a new temporary from an infinite set of temps. new Temp.Label()returns a new label from an infinite set of labels. And new Temp.Label(string)) returns a newlabel whose assembly-language name is string.When processing the declaration m(…), a label for the address of m's machine code can beproduced by new Temp.Label(). It's tempting to call new Temp.Label("m") instead - theassembly-language program will be easier to debug if it uses the label m instead of L213 - butunfortunately there could be two different methods named m in different classes.
A better ideais to call new Temp.Label("C"+"$"+"m"), where C is the name of the class in which themethod m occurs.MANAGING STATIC LINKSThe Frame module should be independent of the specific source language being compiled.Many source languages, including MiniJava, do not have nested function declarations; thus,Frame should not know anything about static links.
Instead, this is the responsibility of thetranslation phase. The translation phase would know that each frame contains a static link.The static link would be passed to a function in a register and stored into the frame. Since thestatic link behaves so much like a formal parameter, we can treat it as one (as much aspossible).[1]Before about 1960, they were passed not on the stack but in statically allocated blocks ofmemory, which precluded the use of recursive functions.[2]However, with register allocation across function boundaries, local variables accessed byinner functions can sometimes go in registers, as long as the inner function knows where tolook.[3]However, some compilers spread out a large value into several registers for efficiency.[4]This program would be cleaner if show called write here instead of manipulating outputdirectly, but it would not be as instructive.PROGRAM FRAMESIf you are compiling for the Sparc, implement the Sparc package containingSparc/SparcFrame.java.
If compiling for the MIPS, implement the Mips package, and soon.If you are working on a RISC machine (such as MIPS or Sparc) that passes the first kparameters in registers and the rest in memory, keep things simple by handling only the casewhere there are k or fewer parameters.Supporting files available in $MINIJAVA/chap6 include:Temp/* The module supporting temporaries and labels.Util/BoolList.java The class for lists of booleans.Optional: Handle functions with more than k formal parameters.117FURTHER READINGThe use of a single contiguous stack to hold variables and return addresses dates from Lisp[McCarthy 1960] and Algol [Naur et al.
1963]. Block structure (the nesting of functions) andthe use of static links are also from Algol.Computers and compilers of the 1960s and '70s kept most program variables in memory, sothat there was less need to worry about which variables escaped (needed addresses). TheVAX, built in 1978, had a procedure-call instruction that assumed all arguments were pushedon the stack, and itself pushed program counter, frame pointer, argument pointer, argumentcount, and callee-save register mask on the stack [Leonard 1987].With the RISC revolution [Patterson 1985] came the idea that procedure calling can be donewith much less memory traffic.
Local variables should be kept in registers by default; storingand fetching should be done as needed, driven by "spilling" in the register allocator [Chaitin1982].Most procedures don't have more than five arguments and five local variables [Tanenbaum1978]. To take advantage of this, Chow et al. [1986] and Hopkins [1986] designed callingconventions optimized for the common case: The first four arguments are passed in registers,with the (rare) extra arguments passed in memory; compilers use both caller- and callee-saveregisters for local variables; leaf procedures don't even need stack frames of their own if theycan operate within the caller-save registers; and even the return address need not always bepushed on the stack.EXERCISES•6.1 Using the C compiler of your choice (or a compiler for another language), compilesome small test functions into assembly language.
On Unix this is usually done by cc-S. Turn on all possible compiler optimizations. Then evaluate the compiled programsby these criteria:a. a. Are local variables kept in registers?b. b. If local variable b is live across more than one procedure call, is it kept in acallee-save register? Explain how doing this would speed up the followingprogram:c.int f(int a) {int b; b=a+1; g(); h(b); return b+2;}d. c.
If local variable x is never live across a procedure call, is it properly kept in acaller-save register? Explain how doing this would speed up the followingprogram:e.•••void h(int y) {int x; x=y+1; f(y); f(2);}6.2 If you have a C compiler that passes parameters in registers, make it generateassembly language for this function:extern void h(int, int);void m(int x, int y) {h(y,y); h(x,x);}Clearly, if arguments to m(x, y) arrive in registers rarg1 and rarg2, and arguments to hmust be passed in rarg1 and rarg2, then x cannot stay in rarg1 during the marshalling ofarguments to h(y, y). Explain when and how your C compiler moves x out of the rarg1register so as to call h(y, y).••6.3 For each of the variables a, b, c, d, e in this C program, say whether the variableshould be kept in memory or a register, and why.int f(int a, int b)118•••••••••••••••{ int c[3], d, e;d=a+1;e=g(c, &b);return e+c[1]+b;}*6.4 How much memory should this program use?int f(int i) {int j,k; j=i*i; k=i?f(i-1):0; return k+j;}void main() {f(100000);}a.