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

In some frame layouts, FP is a separateregister; the old value of FP is saved in memory (in the frame) and the new FP becomes theold SP. When f exits, it just copies FP back to SP and fetches back the saved FP. Thisarrangement is useful if f 's frame size can vary, or if frames are not always contiguous on thestack. But if the frame size is fixed, then for each function f the FP will always differ from SPby a known constant, and it is not necessary to use a register for FP at all − FP is a "fictional"register whose value is always SP + framesize.Why talk about a frame pointer at all? Why not just refer to all variables, parameters, etc., bytheir offset from SP, if the frame size is constant? The frame size is not known until quite latein the compilation process, when the number of memory-resident temporaries and savedregisters is determined.

But it is useful to know the offsets of formal parameters and localvariables much earlier. So, for convenience, we still talk about a frame pointer. And we putthe formals and locals right near the frame pointer at offsets that are known early; thetemporaries and saved registers go farther away, at offsets that are known later.REGISTERSA modern machine has a large set of registers (typically 32 of them). To make compiledprograms run fast, it's useful to keep local variables, intermediate results of expressions, andother values in registers instead of in the stack frame. Registers can be directly accessed byarithmetic instructions; on most machines, accessing memory requires separate load and storeinstructions. Even on machines whose arithmetic instructions can access memory, it is fasterto access registers.A machine (usually) has only one set of registers, but many different procedures and functionsneed to use registers.

Suppose a function f is using register r to hold a local variable and callsprocedure g, which also uses r for its own calculations. Then r must be saved (stored into astack frame) before g uses it and restored (fetched back from the frame) after g is finishedusing it. But is it f 's responsibility to save and restore the register, or g's? We say that r is acaller-save register if the caller (in this case, f) must save and restore the register, and r iscallee-save if it is the responsibility of the callee (in this case, g).On most machine architectures, the notion of caller-save or callee-save register is notsomething built into the hardware, but is a convention described in the machine's referencemanual.

On the MIPS computer, for example, registers 16-23 are preserved across procedurecalls (callee-save), and all other registers are not preserved across procedure calls (callersave).Sometimes the saves and restores are unnecessary. If f knows that the value of some variable xwill not be needed after the call, it may put x in a caller-save register and not save it whencalling g.

Conversely, if f hasalocal variable i that is needed before and after several functioncalls, it may put i in some callee-save register ri, andsave ri just once (upon entry to f )andfetch it back just once (before returning from f ). Thus, the wise selection of a caller-save orcallee-save register for each local variable and temporary can reduce the number of stores and108fetches a program executes. We will rely on our register allocator to choose the appropriatekind of register for each local variable and temporary value.PARAMETER PASSINGOn most machines whose calling conventions were designed in the 1970s, function argumentswere passed on the stack.[1] But this causes needless memory traffic. Studies of actualprograms have shown that very few functions have more than four arguments, and almostnone have more than six. Therefore, parameter-passing conventions for modern machinesspecify that the first k arguments (for k = 4 or k = 6, typically) of a function are passed inregisters rp, …, rp+ k−1, and the rest of the arguments are passed in memory.Now, suppose f(a1, …, an) (which received its parameters in r1, …, rn, for example) calls h(z).It must pass the argument z in r1; so f saves the old contents of r1 (the value a1) in its stackframe before calling h.

But there is the memory traffic that was supposedly avoided bypassing arguments in registers! How has the use of registers saved any time?There are four answers, any or all of which can be used at the same time:1. Some procedures don't call other procedures - these are called leaf procedures. Whatproportion of procedures are leaves? Well, if we make the (optimistic) assumption thatthe average procedure calls either no other procedures or calls at least two others, thenwe can describe a "tree" of procedure calls in which there are more leaves thaninternal nodes. This means that most procedures called are leaf procedures.Leaf procedures need not write their incoming arguments to memory. In fact, oftenthey don't need to allocate a stack frame at all.

This is an important savings.2. Some optimizing compilers use interprocedural register allocation, analyzing all thefunctions in an entire program at once. Then they assign different procedures differentregisters in which to receive parameters and hold local variables. Thus f(x) mightreceive x in r1, but call h(z) with z in r7.3. Even if f is not a leaf procedure, it might be finished with all its use of the argument xby the time it calls h (technically, x is a dead variable at the point where h is called).Then f can overwrite r1 without saving it.4.

Some architectures have register windows, so that each function invocation canallocate a fresh set of registers without memory traffic.If f needs to write an incoming parameter into the frame, where in the frame should it go?Ideally, f 's frame layout should matter only in the implementation of f .

A straightforwardapproach would be for the caller to pass arguments a1, …; ak in registers and ak+1, …; an at theend of its own frame - the place marked outgoing arguments in Figure 6.2 - which become theincoming arguments of the callee. If the callee needed to write any of these arguments tomemory, it would write them to the area marked local variables.The C programming language actually allows you to take the address of a formal parameterand guarantees that all the formal parameters of a function are at consecutive addresses! Thisis the varargs feature that printf uses.

Allowing programmers to take the address of aparameter can lead to a dangling reference if the address outlives the frame - as the address ofx will in int *f(int x){return &x;} - and even when it does not lead to bugs, theconsecutive-address rule for parameters constrains the compiler and makes stack-frame layout109more complicated. To resolve the contradiction that parameters are passed in registers, buthave addresses too, the first k parameters are passed in registers; but any parameter whoseaddress is taken must be written to a memory location on entry to the function.

To satisfyprintf, the memory locations into which register arguments are written must all beconsecutive with the memory locations in which arguments k + 1, k + 2, etc., are written.Therefore, C programs can't have some of the arguments saved in one place and some savedin another - they must all be saved contiguously.So in the standard calling convention of many modern machines the calling function reservesspace for the register arguments in its own frame, next to the place where it writes argument k+ 1. But the calling function does not actually write anything there; that space is written intoby the called function, and only if the called function needs to write arguments into memoryfor any reason.A more dignified way to take the address of a local variable is to use call-by-reference. Withcall-by-reference, the programmer does not explicitly manipulate the address of a variable x.Instead, if x is passed as the argument to f(y), where y is a "by-reference" parameter, thecompiler generates code to pass the address of x instead of the contents of x.

At any use of ywithin the function, the compiler generates an extra pointer dereference. With call-byreference, there can be no "dangling reference", since y must disappear when f returns, and freturns before x's scope ends.RETURN ADDRESSESWhen function g calls function f, eventually f must return. It needs to know where to go backto. If the call instruction within g is at address a, then (usually) the right place to return to is a+ 1, the next instruction in g.

This is called the return address.On 1970s machines, the return address was pushed on the stack by the call instruction.Modern science has shown that it is faster and more flexible to pass the return address in aregister, avoiding memory traffic and also avoiding the need to build any particular stackdiscipline into the hardware.On modern machines, the call instruction merely puts the return address (the address of theinstruction after the call) in a designated register. A nonleaf procedure will then have to writeit to the stack (unless interprocedural register allocation is used), but a leaf procedure will not.FRAME-RESIDENT VARIABLESSo a modern procedure-call convention will pass function parameters in registers, pass thereturn address in a register, and return the function result in a register.

Many of the localvariables will be allocated to registers, as will the intermediate results of expressionevaluation. Values are written to memory (in the stack frame) only when necessary for one ofthese reasons:••••the variable will be passed by reference, so it must have a memory address (or, in theC language the & operator is anywhere applied to the variable);the variable is accessed by a procedure nested inside the current one;[2]the value is too big to fit into a single register;[3]the variable is an array, for which address arithmetic is necessary to extractcomponents;110••the register holding the variable is needed for a specific purpose, such as parameterpassing (as described above), though a compiler may move such values to otherregisters instead of storing them in memory;or there are so many local variables and temporary values that they won't all fit inregisters, in which case some of them are "spilled" into the frame.We will say that a variable escapes if it is passed by reference, its address is taken (using C's &operator), or it is accessed from a nested function.When a formal parameter or local variable is declared, it's convenient to assign it a location either in registers or in the stack frame - right at that point in processing the program.

Then,when occurrences of that variable are found in expressions, they can be translated intomachine code that refers to the right location. Unfortunately, the conditions in our list don'tmanifest themselves early enough. When the compiler first encounters the declaration of avariable, it doesn't yet know whether the variable will ever be passed by reference, accessedin a nested procedure, or have its address taken; and it doesn't know how many registers thecalculation of expressions will require (it might be desirable to put some local variables in theframe instead of in registers). An industrial-strength compiler must assign provisionallocations to all formals and locals, and decide later which of them should really go inregisters.STATIC LINKSIn languages that allow nested function declarations (such as Pascal, ML, and Java), the innerfunctions may use variables declared in outer functions.