Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 79
Текст из файла (страница 79)
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. While the details of the linkage convention vary from systemto system, the basic concepts are similar across most combinations oftarget machine, operating system, and compiler.Review Questions1.
What role does the linkage convention play in the construction of largeprograms? Of interlanguage programs? What facts would the compilerneed to know in order to generate code for an interlanguage call?2. If the compiler knows, at a procedure call, that the callee does not,itself, contain any procedure calls, what steps might it omit from thecalling sequence? Are there any fields in the AR that the callee wouldnever need?6.6 ADVANCED TOPICSThe compiler must arrange for the allocation of space to hold the various runtime structures discussed in Section 6.3.
For some languages, thosestructures have lifetimes that do not fit well into the first-in first-out discipline of a stack. In such cases, the language implementation allocates spacein the runtime heap—a region of memory set aside for such objects andmanaged by routines in a runtime support library. The compiler must alsoarrange storage for other objects that have lifetimes unrelated to the flow of6.6 Advanced Topics 313control, such as many lists in a Scheme program or many objects in a Javaprogram.We assume a simple interface to the heap, namely, a routine allocate(size) and a routine free(address). The allocate routine takes aninteger argument size and returns the address of a block of space in theheap that contains at least size bytes. The free routine takes the addressof a block of previously allocated space in the heap and returns it to thepool of free space.
The critical issues that arise in designing algorithms forexplicitly managing the heap are the speeds of both allocate and free andthe extent to which the pool of free space becomes fragmented into smallblocks.This section sketches the algorithms involved in allocation and reclamation of space in a runtime heap. Section 6.6.1 focuses on techniques forexplicit management of the heap.
Along the way, it describes how toimplement free for each of the schemes. Section 6.6.2 examines implicitdeallocation—techniques that avoid the need for free.6.6.1 Explicit Heap ManagementMost language implementations include a runtime system that provides support functions for the code generated by the compiler. The runtime systemtypically includes provision for management of a runtime heap.
The actualroutines that implement the heap may be language specific, as in a Schemeinterpreter or a Java virtual machine, or they may be part of the underlyingoperating system, as in the Posix implementations of malloc and free.While many techniques have been proposed to implement allocate andfree, most of those implementations share common strategies and insights.This section explores a simple strategy, first-fit allocation, that exposes mostof the issues, and then shows how a strategy such as first fit is used toimplement a modern allocator.First-Fit AllocationThe goal of a first-fit allocator is to allocate and free space in the heapquickly.
First fit emphasizes speed over memory utilization. Every blockin the heap has a hidden field that holds its size. In general, the size field islocated in the word preceding the address returned by allocate, as shownin Figure 6.11a. Blocks available for allocation reside on a list called the freelist. In addition to the mandatory size field, blocks on the free list have additional fields, as shown in Figure 6.11b. Each free block has a pointer to thenext block on the free list (set to null in the last block) and a pointer to theblock itself in the last word of the block.
To initialize the heap, the allocatorcreates a free list that contains a single large unallocated block.314 CHAPTER 6 The Procedure Abstractionsizesizenext(a) Allocated Block(b) Free Blockn FIGURE 6.11 Blocks in a First-Fit Allocator.A call allocate(k) causes the following sequence of events: The allocate routine walks the free list until it discovers a block with size greaterthan or equal to k plus one word for the size field. Assume it finds an appropriate block, bi . It removes bi from the free list. If bi is larger than necessary,allocate creates a new free block from the excess space at the end of biand places that block on the free list. The allocate routine returns a pointerto the second word of bi .If allocate fails to find a large enough block, it tries to extend the heap.If it succeeds in extending the heap, it returns a block of appropriate sizefrom this newly allocated portion of the heap. If extending the heap fails,allocate reports failure (typically by returning a null pointer).To deallocate a block, the program calls free with the address of the block,b j .
The simplest implementation of free adds b j to the head of the free listand returns. This produces a fast free routine. Unfortunately, it leads to anallocator that, over time, fragments memory into small blocks.To overcome this flaw, the allocator can use the pointer at the end of a freedblock to coalesce adjacent free blocks. The free routine loads the word preceding b j ’s size field, which is the end-of-block pointer for the block thatimmediately precedes b j in memory. If that word contains a valid pointer,and it points to a matching block header (one whose address plus size fieldpoints to the start of b j ), then both b j and its predecessor are free.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
