K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 72
Текст из файла (страница 72)
The callee needs thispointer so that it can restore the caller’s environment when it terminates.The local data area holds variables declared in the callee’s local scope.6.3 Name Spaces 281Local-Data AreaARP + nARPLocal-Data AreaCaller’s ARPAddressabilityReturn AddressCaller’s ARPAddressabilityReturn AddressReturn ValueReturn ValueRegister-Save AreaRegister-Save AreaParametersParametersCaller’s ARARP-m…Callee’s ARn FIGURE 6.4 Typical Activation Records.For the sake of efficiency, some of the information shown in Figure 6.4 maybe kept in dedicated registers.Local StorageThe ar for an invocation of procedure q holds the local data and state information for that invocation.
Each separate call to q generates a separate ar.All data in the ar is accessed through the arp. Because procedures typicallyaccess their ar frequently, most compilers dedicate a hardware register tohold the arp of the current procedure. In iloc, we refer to this dedicatedregister as rarp .The arp always points to a designated location in the ar. The central partof the ar has a static layout; all the fields have known fixed lengths. Thisensures that the compiled code can access those items at fixed offsets fromthe arp. The ends of the ar are reserved for storage areas whose sizesmay change from one invocation to another; typically one holds parameterstorage while the other holds local data.Reserving Space for Local DataEach local data item may need space in the ar.
The compiler should assigneach such item an appropriately sized area and record the current lexicallevel and its offset from the arp in the symbol table. This pair, the lexicallevel and offset, become the item’s static coordinate. Then, the variable canbe accessed using an operation like loadAO, with rarp and the offset as itsarguments, to provide efficient access to local variables.282 CHAPTER 6 The Procedure AbstractionThe compiler may not know the sizes of some local variables at compiletime. For example, the program might read the size of an array from externalmedia or determine it from work done in an earlier phase of the computation.For such variables, the compiler can leave space in the local data area for apointer to the actual data or to a descriptor for an array (see Section 7.5.3 onpage 362).
The compiler arranges to allocate the actual storage elsewhere,at runtime, and to fill the reserved slot with the address of the dynamicallyallocated memory. In this case, the static coordinate leads the compiler tothe pointer’s location, and the actual access either uses the pointer directlyor uses the pointer to calculate an appropriate address in the variable-lengthdata area.Initializing VariablesIf the source language allows the program to specify an initial value fora variable, the compiler must arrange for that initialization to occur. If thevariable is allocated statically—that is, it has a lifetime that is independentof any procedure—and the initial value is known at compile time, the datacan be inserted directly into the appropriate locations by the loader. (Staticvariables are usually stored outside all ars. Having one instance of sucha variable provides the needed semantics—a single value preserved acrossall the calls.
Using a separate static data area—either one per procedure orone for the entire program—lets the compiler use the initialization featurescommonly found in loaders.)Local variables, on the other hand, must be initialized at runtime. Becausea procedure may be invoked multiple times, the only feasible way to setinitial values is to generate instructions that store the necessary values tothe appropriate locations.
In effect, these initializations are assignments thatexecute before the procedure’s first statement, each time it is invoked.Space for Saved Register ValuesWhen p calls q, one of them must save the register values that p needsafter the call. It may be necessary to save all the register values; on theother hand, a subset may suffice. On return to p, these saved values mustbe restored. Since each activation of p stores a distinct set of values, itmakes sense to store these saved registers in the ar of either p or q, or both.If the callee saves a register, its value is stored in the callee’s register savearea. Similarly, if the caller saves a register, its value is stored in the caller’sregister save area.
For a caller p, only one call inside p can be active at atime. Thus, a single register save area in p’s ar suffices for all the calls thatp can make.6.3 Name Spaces 283Allocating Activation RecordsWhen p calls q at runtime, the code that implements the call must allocate anar for q and initialize it with the appropriate values. If all the fields shown inFigure 6.4 are stored in memory, then the ar must be available to the caller,p, so that it can store the actual parameters, return address, caller’s arp, andaddressability information. This forces allocation of q’s ar into p, wherethe size of its local data area may not be known.
On the other hand, if thesevalues are passed in registers, actual allocation of the ar can be performed inthe callee, q. This lets q allocate the ar, including any space required for thelocal data area. After allocation, it may store into its ar some of the valuespassed in registers.The compiler writer has several options for allocating activation records.This choice affects both the cost of procedure calls and the cost of implementing advanced language features, such as building a closure. It alsoaffects the total amount of memory needed for activation records.Stack Allocation of Activation RecordsIn many cases, the contents of an ar are only of interest during the lifetime of the procedure whose activation causes the ar’s creation. In short,most variables cannot outlive the procedure that creates them, and most procedure activations cannot outlive their callers.
With these restrictions, callsand returns are balanced; they follow a last-in, first-out (lifo) discipline. Acall from p to q eventually returns, and any returns that occur between thecall from p to q and the return from q to p must result from calls made (eitherdirectly or indirectly) by q. In this case, the activation records also follow thelifo ordering; thus, they can be allocated on a stack. Pascal, c, and Java aretypically implemented with stack-allocated ars.Keeping activation records on a stack has several advantages.
Allocationand deallocation are inexpensive; each requires one arithmetic operationon the value that marks the stack’s top. The caller can begin the processof setting up the callee’s ar. It can allocate all the space up to the localdata area. The callee can extend the ar to include the local data area byincrementing the top-of-stack (tos) pointer. It can use the same mechanism to extend the current ar incrementally to hold variable-size objects,as shown in Figure 6.5. Here, the callee has copied the tos pointer intothe local data area slot for A and then incremented the tos pointer bythe size of A.
Finally, with stack-allocated ars, a debugger can walk thestack from its top to its base to produce a snapshot of the currently activeprocedures.284 CHAPTER 6 The Procedure AbstractionNewTOSSpace for AOldTOSLocal-Data AreaPointer to AARPCaller ARP…n FIGURE 6.5 Stack Allocation of a Dynamically Sized Array.Heap Allocation of Activation RecordsIf a procedure can outlive its caller, the stack discipline for allocating arsbreaks down. Similarly, if a procedure can return an object, such as a closure,that includes, explicitly or implicitly, references to its local variables, stackallocation is inappropriate because it will leave behind dangling pointers.In these situations, ars can be kept in heap storage (see Section 6.6).Implementations of Scheme and ml typically use heap-allocated ars.A modern memory allocator can keep the cost of heap allocation low.
Withheap-allocated ars, variable-size objects can be allocated as separate objectson the heap. If heap objects need explicit deallocation, then the code for procedure return must free the ar and its variable-size extensions. With implicitdeallocation (see Section 6.6.2), the garbage collector frees them when theyare no longer useful.Static Allocation of Activation RecordsLeaf procedurea procedure that contains no callsIf a procedure q calls no other procedures, then q can never have multiple active invocations.
We call q a leaf procedure since it terminates a paththrough a graph of the possible procedure calls. The compiler can staticallyallocate activation records for leaf procedures. This eliminates the runtimecosts of ar allocation. If the calling convention requires the caller to save itsown registers, then q’s ar needs no register save area.If the language does not allow closures, the compiler can do better thanallocating a static ar for each leaf procedure. At any point during execution,only one leaf procedure can be active. (To have two such procedures active,the first one would need to call another procedure, so it would not be a leaf.)Thus, the compiler can allocate a single static ar for use by all of the leafprocedures.
The static ar must be large enough to accommodate any of the6.3 Name Spaces 285program’s leaf procedures. The static variables declared in any of the leafprocedures can be laid out together in that single ar. Using a single staticar for leaf procedures reduces the space overhead of separate static ars foreach leaf procedure.Coalescing Activation RecordsIf the compiler discovers a set of procedures that are always invoked ina fixed sequence, it may be able to combine their activation records. Forexample, if a call from p to q always results in calls to r and s, the compilermay find it profitable to allocate the ars for q, r, and s at the same time.Combining ars can save on the costs of allocation; the benefits will varydirectly with allocation costs.
In practice, this optimization is limited by separate compilation and the use of function-valued parameters. Both limit thecompiler’s ability to determine the calling relationships that actually occurat runtime.6.3.3 Name Spaces of Object-Oriented LanguagesMuch has been written about object-oriented design, object-oriented programming, and object-oriented languages. Languages such as Simula,Smalltalk, c++, and Java all support object-oriented programming. Manyother languages have extensions that provide them with features to supportobject-oriented programming.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
