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

This language feature is called blockstructure. For example, consider Program 6.3, which is written with a Pascal-like syntax. Thefunction write refers to the outer variable output, and indent refers to outer variables n andoutput. To make this work, the function indent must have access not only to its own frame(for variables i and s) but also to the frames of show (for variable n) and prettyprint (forvariable output).PROGRAM 6.3: Nested functions.12345678910111213141516171819202122type tree = {key: string, left: tree, right: tree}function prettyprint(tree: tree) : string =letvar output := ""function write(s: string) =output := concat(output,s)function show(n:int, t: tree) =let function indent(s: string) =(for i := 1 to ndo write(" ");output := concat(output,s); write("\n"))in if t=nil then indent(".")else (indent(t.key);show(n+1,t.left);show(n+1,t.right))endin show(0,tree); outputend111There are several methods to accomplish this:•••Whenever a function f is called, it can be passed a pointer to the frame of the functionstatically enclosing f ; this pointer is the static link.A global array can be maintained, containing - in position i - a pointer to the frame ofthe most recently entered procedure whose static nesting depth is i.

This array is calleda display.When g calls f, each variable of g that is actually accessed by f (or by any functionnested inside f ) is passed to f as an extra argument. This is called lambda lifting.We will describe in detail only the method of static links. Which method should be used inpractice? See Exercise 6.6.Whenever a function f is called, it is passed a pointer to the stack frame of the "current" (mostrecently entered) activation of the function g that immediately encloses f in the text of theprogram.For example, in Program 6.3:Line#21 prettyprint calls show, passing prettyprint's own frame pointer as show's static link.10 show stores its static link (the address of prettyprint's frame) into its own frame.15 show calls indent, passing its own frame pointer as indent's static link.17 show calls show, passing its own static link (not its own frame pointer) as the static link.12 indent uses the value n from show's frame.

To do so, it fetches at an appropriate offsetfrom indent's static link (which points at the frame of show).13 indent calls write. It must pass the frame pointer of prettyprint as the static link. Toobtain this, it first fetches at an offset from its own static link (from show's frame), the staticlink that had been passed to show.14 indent uses the variable output from prettyprint'sframe.Todosoit starts with its ownstatic link, then fetches show's, then fetches output.[4]So on each procedure call or variable access, a chain of zero or more fetches is required; thelength of the chain is just the difference in static nesting depth between the two functionsinvolved.6.2 FRAMES IN THE MiniJava COMPILERWhat sort of stack frames should the MiniJava compiler use? Here we face the fact that everytarget-machine architecture will have a different standard stack frame layout.

If we wantMiniJava functions to be able to call C functions, we should use the standard layout. But wedon't want the specifics of any particular machine intruding on the implementation of thetranslation module of the MiniJava compiler.112Thus we must use abstraction. Just as the Symbol module provides a clean interface, andhides the internal representation of Symbol.Table from its clients, we must use an abstractrepresentation for frames.The frame interface will look something like this:package Frame;import Temp.Temp; import Temp.Label;public abstract class Access { ... }public abstract class AccessList {...head;...tail;...

}public abstract class Frame {abstract public Frame newFrame(Label name,Util.BoolList formals);public Label name;public AccessList formals;abstract public Access allocLocal(boolean escape);/* ... other stuff, eventually ... *}The abstract class Frame is implemented by a module specific to the target machine. Forexample, if compiling to the MIPS architecture, there would bepackage Mips;class Frame extends Frame.Frame { ... }In general, we may assume that the machine-independent parts of the compiler have access tothis implementation of Frame; for example,// in class Main.Main:Frame.Frame frame = new Mips.Frame(...);In this way the rest of the compiler may access frame without knowing the identity of thetarget machine (except an occurrence of the word Mips here and there).The class Frame holds information about formal parameters and local variables allocated inthis frame.

To make a new frame for a function f with k formal parameters, call newFrame(f,l), where l is a list of k booleans: true for each parameter that escapes and false for eachparameter that does not. (In MiniJava, no parameters ever escape.) The result will be a Frameobject. For example, consider a three-argument function named g whose first argumentescapes (needs to be kept in memory). Thenframe.newFrame(g,new BoolList(true,new BoolList(false,new BoolList(false, null))))returns a new frame object.The Access class describes formals and locals that may be in the frame or in registers. This isan abstract data type, so its implementation as a pair of subclasses is visible only inside theFrame module:package Mips;class InFrame extends Frame.Access {int offset; ...

}class InRegextends Frame.Access {Temp temp; ... }113InFrame(X) indicates a memory location at offset X from the frame pointer; InReg(t84)indicates that it will be held in "register" t84. Frame.Access is an abstract data type, so outsideof the module the InFrame and InReg constructors are not visible. Other modules manipulateaccesses using interface functions to be described in the next chapter.The formals field is a list of k "accesses" denoting the locations where the formal parameterswill be kept at run time, as seen from inside the callee.

Parameters may be seen differently bythe caller and the callee. For example, if parameters are passed on the stack, the caller mayput a parameter at offset 4 from the stack pointer, but the callee sees it at offset 4 from theframe pointer. Or the caller may put a parameter into register 6, but the callee may want tomove it out of the way and always access it from register 13. On the Sparc architecture, withregister windows, the caller puts a parameter into register o1, butthe save instruction shiftsregister windows so the callee sees this parameter in register i1.Because this "shift of view" depends on the calling conventions of the target machine, it mustbe handled by the Frame module, starting with newFrame. For each formal parameter,newFrame must calculate two things:••How the parameter will be seen from inside the function (in a register, or in a framelocation).What instructions must be produced to implement the "view shift."For example, a frame-resident parameter will be seen as "memory at offset X from the framepointer", and the view shift will be implemented by copying the stack pointer to the framepointer on entry to the procedure.REPRESENTATION OF FRAME DESCRIPTIONSThe implementation module Frame is supposed to keep the representation of Frame objectssecret from any clients of the Frame module.

But really it's an object holding:••••the locations of all the formals,instructions required to implement the "view shift",the number of locals allocated so far,and the label at which the function's machine code is to begin (see page 131).Table 6.4 shows the formals of the three-argument function g (see page 127) as newFramewould allocate them on three different architectures: the Pentium, MIPS, and Sparc.

The firstparameter escapes, so it needs to be InFrame on all three machines. The remaining parametersare InFrame on the Pentium, but InReg on the other machines.Table 6.4: Formal parameters for g(x1, x2, x3) where x1 escapes.PentiumMIPSSparc1InFrame(8)Formals 2 InFrame(12)3InFrame(16)InFrame(0)InFrame(68)InReg(t157)InReg(t157)InReg(t158)InReg(t158)save %sp,-K,%spM[sp + 0] ← fp sp ← sp − K114Table 6.4: Formal parameters for g(x1, x2, x3) where x1 escapes.PentiumMIPSSparcView Shift fp ← spsp ← sp − KM[sp + K + 0] ← r4 M[fp + 68] ← i0t157 ← r5t157 ← i1t158 ← r6t158 ← i2The freshly created temporaries t157 and t158, and the move instructions that copy r4 and r5into them (or on the Sparc, i1 and i2), may seem superfluous. Why shouldn't the body of gjust access these formals directly from the registers in which they arrive? To see why not,considervoid m(int x, int y) { h(y,y); h(x,x); }If x stays in "parameter register 1" throughout m, and y is passed to h in parameter register 1,then there is a problem.The register allocator will eventually choose which machine register should hold t157.