K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 79
Текст из файла (страница 79)
The procedure linkageensures interoperability of procedures between the user’s code, as translatedby the compiler, and code from other sources, including system libraries,application libraries, and code written in other programming languages.Typically, all of the compilers for a given combination of target machineand operating system use the same linkage, to the extent possible.The linkage convention isolates each procedure from the different environments found at call sites that invoke it. Assume that procedure p has aninteger parameter x. Different calls to p might bind x to a local variable storedin the caller’s stack frame, to a global variable, to an element of some staticarray, and to the result of evaluating an integer expression such as y + 2.Because the linkage convention specifies how to evaluate the actual parameter and store its value, as well as how to access x in the callee, the compilercan generate code for the callee that ignores the differences between the runtime environments at the different calls sites.
As long as all the proceduresobey the linkage convention, the details will mesh to create the seamlesstransfer of values promised by the source-language specification.The linkage convention is, of necessity, machine dependent. For example, itdepends implicitly on information such as the number of registers availableon the target machine and the mechanisms for executing a call and a return.Figure 6.10 shows how the pieces of a standard procedure linkage fittogether. Each procedure has a prologue sequence and an epilogue sequence.Each call site includes both a precall sequence and a postreturn sequence.Procedure pPrologueProcedure qPrecallPostreturnEpiloguen FIGURE 6.10 A Standard Procedure Linkage.llPrologueCaReturnEpilogue6.5 Standardized Linkages 309nPrecall Sequence The precall sequence begins the process ofconstructing the callee’s environment.
It evaluates the actualparameters, determines the return address, and, if necessary, the addressof space reserved to hold a return value. If a call-by-reference parameteris currently allocated to a register, the precall sequence needs to store itinto the caller’s ar so that it can pass that location’s address to thecallee.Many of the values shown in the diagrams of the ar can be passed tothe callee in registers. The return address, an address for the returnvalue, and the caller’s arp are obvious candidates.
The first k actualparameters can be passed in registers as well—a typical value for kmight be 4. If the call has more than k parameters, the remainingactual parameters must be stored in either the callee’s ar or thecaller’s ar.nPostreturn Sequence The postreturn sequence undoes the actions of theprecall sequence. It must restore any call-by-reference andcall-by-value-result parameters that need to be returned to registers.
Itrestores any caller-saved registers from the register save area. It mayneed to deallocate all or part of the callee’s ar.nPrologue Sequence The prologue for a procedure completes the task ofcreating the callee’s runtime environment. It may create space in thecallee’s ar to store some of the values passed by the caller in registers.It must create space for local variables and initialize them, as necessary.If the callee references a procedure-specific static data area, it may needto load the label for that data area into a register.nEpilogue Sequence The epilogue for a procedure begins the processof dismantling the callee’s environment and reconstructing thecaller’s environment. It may participate in deallocating the callee’s ar.If the procedure returns a value, the epilogue may be responsiblefor storing the value into the address specified by the caller.(Alternatively, the code generated for a return statement may performthis task.) Finally, it restores the caller’s arp and jumps to the returnaddress.This framework provides general guidance for building a linkage convention.
Many of the tasks can be shifted between caller and callee. In general,moving work into the prologue and epilogue code produces more compact code. The precall and postreturn sequences are generated for each call,while the prologue and epilogue occur once per procedure. If proceduresare called, on average, more than once, then there are fewer prologue andepilogue sequences than precall and postreturn sequences.310 CHAPTER 6 The Procedure AbstractionMORE ABOUT TIMEIn a typical system, the linkage convention is negotiated between the compiler implementors and the operating-system implementors at an earlystage of the system’s development. Thus, issues such as the distinctionbetween caller-saves and callee-saves registers are decided at designtime. When the compiler runs, it must emit procedure prologue andepilogue sequences for each procedure, along with precall and postreturn sequences for each call site.
This code executes at runtime. Thus, thecompiler cannot know the return address that it should store into a callee’sAR. (Neither can it know, in general, the address of that AR.) It can, however,include a mechanism that will generate the return address at link time(using a relocatable assembly language label) or at runtime (using someoffset from the program counter) and store it into the appropriate locationin the callee’s AR.Similarly, in a system that uses a display to provide addressability forlocal variables of other procedures, the compiler cannot know the runtimeaddresses of the display or the AR.
Nonetheless, it emits code to maintainthe display. The mechanism that achieves this requires two pieces of information: the lexical nesting level of the current procedure and the addressof the global display. The former is known at compile time; the latter canbe determined at link time by using a relocatable assembly language label.Thus, the prologue can simply load the current display entry for the procedure’s level (using a loadAO from the display address) and store it intothe AR (using a storeAO relative to the ARP).
Finally, it stores the addressof the new AR into the display slot for the procedure’s lexical level.Saving RegistersCaller-saves registersThe registers designated for the caller to saveare caller-saves registers.Callee-saves registersThe registers designated for the callee to saveare callee-saves registers.At some point in the call sequence, any register values that the caller expectsto survive across the call must be saved into memory.Either the caller or thecallee can perform the actual save; there is an advantage to either choice.If the caller saves registers, it can avoid saving values that it knows are notuseful across the call; that knowledge might allow it to preserve fewer values.Similarly, if the callee saves registers, it can avoid saving values of registersthat it does not use; again, that knowledge might result in fewer saved values.In general, the compiler can use its knowledge of the procedure being compiled to optimize register save behavior.
For any specific division of laborbetween caller and callee, we can construct programs for which it workswell and programs for which it does not. Most modern systems take a middleground and designate a portion of the register set for caller-saves treatmentand a portion for callee-saves treatment. In practice, this seems to work well.It encourages the compiler to put long-lived values in callee-saves registers,where they will be stored only if the callee actually needs the register. It6.5 Standardized Linkages 311encourages the compiler to put short-lived values in caller-saves registers,where it may avoid saving them at a call.Allocating the Activation RecordIn the most general case, both the caller and the callee need access to thecallee’s ar. Unfortunately, the caller cannot know, in general, how large thecallee’s ar must be (unless the compiler and linker can contrive to havethe linker paste the appropriate values into each call site).With stack-allocated ars, a middle ground is possible.
Since allocation consists of incrementing the stack-top pointer, the caller can begin the creationof the callee’s ar by bumping the stack top and storing values into theappropriate places. When control passes to the callee, it can extend the partially built ar by incrementing the stack top to create space for local data.The postreturn sequence can then reset the stack-top pointer, performing theentire deallocation in a single step.With heap-allocated ars, it may not be possible to extend the callee’s arincrementally. In this situation, the compiler writer has two choices.1.
The compiler can pass the values that it must store in the callee’s ar inregisters; the prologue sequence can then allocate an appropriately sizedar and store the passed values in it. In this scheme, the compiler writerreduces the number of values that the caller passes to the callee byarranging to store the parameter values in the caller’s ar. Access tothose parameters uses the copy of the caller’s arp that is stored in thecallee’s ar.2. The compiler writer can split the ar into multiple distinct pieces, one tohold the parameter and control information generated by the caller andthe others to hold space needed by the callee but unknown to the caller.The caller cannot, in general, know how large to make the local dataarea.
The compiler can store this number for each callee using mangledlabels; the caller can then load the value and use it. Alternatively, thecallee can allocate its own local data area and keep its base address in aregister or in a slot in the ar created by the caller.Heap-allocated ars add to the overhead cost of a procedure call. Care in theimplementation of the calling sequence and the allocator can reduce thosecosts.Managing Displays and Access LinksEither mechanism for managing nonlocal access requires some work in thecalling sequence. Using a display, the prologue sequence updates the display record for its own level and the epilogue sequence restores it. If the312 CHAPTER 6 The Procedure Abstractionprocedure never calls a more deeply nested procedure, it can skip this step.Using access links, the precall sequence must locate the appropriate firstaccess link for the callee.
The amount of work varies with the differencein lexical level between caller and callee. As long as the callee is known atcompile time, either scheme is reasonably efficient. If the callee is unknown(if it is, for example, a function-valued parameter), the compiler may needto emit special-case code to perform the appropriate steps.SECTION REVIEWThe procedure linkage ties together procedures. The linkage conventionis a social contract between the compiler, the operating system, andthe underlying hardware. It governs the transfer of control betweenprocedures, the preservation of the caller’s state and the creation of thecallee’s state, and the rules for passing values between them.Standard procedure linkages allow us to assemble executable programsfrom procedures that have different authors, that are translated atdifferent times, and that are compiled with different compilers.Procedure linkages allow each procedure to operate safely and correctly.The same conventions allow application code to invoke system andlibrary calls.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
