Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 71

Programmers often use a block-level scope to create temporarystorage for code generated by a preprocessor macro or to create a localvariable whose scope is the body of a loop.c introduces another scope: the file-level scope. This scope includesnames declared as static that not enclosed in a procedure. Thus,static procedures and functions are in the file-level scope, as are anystatic variables declared at the outermost level in the file. Withoutthe static attribute, these names would be global variables. Names inthe file-level scope are visible to any procedure in the file, but are notvisible outside the file. Both variables and procedures can be declaredstatic.Scheme has a simple set of scope rules.

Almost all objects in Schemereside in a single global space. Objects can be data or executableexpressions. System-provided functions, such as cons, live alongsideuser-written code and data items. Code, which consists of an executableexpression, can create private objects by using a let expression.Nesting let expressions inside one another can create nested lexicalscopes of arbitrary depth.Separate compilation makes it hard for FORTRANcompilers to detect different declarations for acommon block in distinct files. Thus, the compilermust translate common-block references intohblock, offseti pairs to produce correct behavior.Static nameA variable declared as static retains its valueacross invocations of its defining procedure.Variables that are not static are called automatic.280 CHAPTER 6 The Procedure Abstraction6.3.2 Runtime Structures to Support Algol-likeLanguagesActivation recorda region of storage set aside to hold controlinformation and data storage associated with asingle instance of a single procedureTo implement the twin abstractions of procedure calls and scoped namespaces, the translation must establish a set of runtime structures.

The keydata structure involved in both control and naming is the activation record(ar), a private block of memory associated with a specific invocation of aspecific procedure. In principle, every procedure call gives rise to a new ar.nnnnThe compiler must arrange for each call to store the return addresswhere the callee can find it. The return address goes into the ar.The compiler must map the actual parameters at the call site into theformal parameter names by which they are known in the callee.

To doso, it stores ordered parameter information in the ar.The compiler must create storage space for variables declared in thecallee’s local scope. Since these values have lifetimes that match thelifetime of the return address, it is convenient to store them in the ar.The callee needs other information to connect it to the surroundingprogram, and to allow it to interact safely with other procedures. Thecompiler arranges to store that information in the callee’s ar.Since each call creates a new ar, when multiple instances of a procedureare active, each has its own ar.

Thus, recursion gives rise to multiple ars,each of which holds the local state for a different invocation of the recursiveprocedure.Activation record pointerTo locate the current AR the compiler arranges tokeep a pointer to the AR, the activation recordpointer, in a designated register.Figure 6.4 shows how the contents of an ar might be laid out. The entire aris addressed through an activation record pointer (arp), with various fieldsin the ar found at positive and negative offsets from the arp. The ars inFigure 6.4 have a number of fields.nnnnnnnThe parameter area holds actual parameters from the call site, in anorder that corresponds to their order of appearance at the call.The register save area contains enough space to hold registers that theprocedure must preserve due to procedure calls.The return-value slot provides space to communicate data from thecallee back to the caller, if needed.The return-address slot holds the runtime address where executionshould resume when the callee terminates.The “addressability” slot holds information used to allow the callee toaccess variables in surrounding lexical scopes (not necessarily thecaller).The slot at the callee’s arp stores the caller’s arp.

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.