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

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.

Unfortunately, the term object-oriented hasbeen given so many different meanings and implementations that it has cometo signify a wide range of language features and programming paradigms.As we shall see, not all ools can be compiled, in the traditional sense ofa translation that finalizes all of the details about the executable program.Features of some ools create name spaces that cannot be understood untilruntime. Implementations of these languages rely on runtime mechanismsthat run from interpretation to runtime compilation (so-called just-in-timecompilers or jits). Because interpreters and jits use many of the same structures as a compiler, we describe the problem as it might be implemented ina traditional compiler.From the compiler’s perspective, ools reorganize the program’s name space.Most ools retain the procedure-oriented lexical scoping conventions ofan all for use within procedural code.

They augment this classic namingscheme with a second set of conventions for naming, one organized aroundthe layout of data—specifically, the definitions of objects. This data-centricnaming discipline leads to a second hierarchy of scopes and a second mechanism for resolving names—that is, for mapping a source-language name intoa runtime address so that the compiled code can access the data associatedwith that name.Just-in-time compilerSchemes that perform some of the tasks of atraditional compiler at runtime are often calledjust-in-time compilers or JITs.In a JIT, compile time becomes part of runtime,so JITs place an emphasis on compile-timeefficiency.286 CHAPTER 6 The Procedure AbstractionTERMINOLOGY FOR OBJECT-ORIENTED LANGUAGESThe diversity of object-oriented languages has led to some ambiguity inthe terms that we use to discuss them. To make the discussion in thischapter concrete, we will use the following terms:1.

Object An object is an abstraction with one or more members. Thosemembers can be data items, code that manipulates those data items,or other objects. An object with code members is a class. Each objecthas internal state—data whose lifetimes match the object’s lifetime.2. Class A class is a collection of objects with the same abstract structureand characteristics. A class defines the set of data members in eachinstance of the class and defines the code members (methods) that arelocal to that class. Some methods are public, or externally visible,others are private, or invisible outside the class.3.

Inheritance Inheritance refers to a relationship among classes thatdefines a partial order on the name scopes of classes. Each class mayhave a superclass from which it inherits both code and data members.If a is the superclass of b, b is a subclass of a. Some languages allow aclass to have multiple superclasses.4. Receiver Methods are invoked relative to some object, called themethod’s receiver. The receiver is known by a designated name, suchas this or self, inside the method.The complexity and the power of an OOL arise, in large part, from theorganizational possibilities presented by its multiple name spaces.The syntax and terminology used to specifysubclasses varies between languages.

In Java,a subclass extends its superclass, while in C++, asubclass is derived from its superclass.Inheritance imposes an ancestor relation on the classes in an application.Each class has, by declaration, one or more parent classes, or superclasses.Inheritance changes both the name space of the application and the mappingof method names to implementations. If α is a superclass of β, then β isa subclass of α and any method defined in α must operate correctly on anobject of class β, if it is visible in β. The converse is not true; a methoddeclared in class β cannot be applied to an object of its superclass α, as themethod from β may need fields present in an object of class β that are absentfrom an object of class α.VisibilityWhen a method runs, it can reference names defined in multiple scope hierarchies.

The method is a procedure, with its own name space defined by theset of lexical scopes in which it is declared; the method can access names inthose scopes using the familiar conventions defined for alls. The methodwas invoked relative to some receiver; it can access that object’s own members. The method is defined in the receiver’s class. The method can access6.3 Name Spaces 287the members of that class and, by inheritance, of its superclasses.

Finally,the program creates some global name space and executes in it. The runningmethod can access any names that are contained in that global name space.To make these issues concrete, consider the abstracted example shown inFigure 6.6. It defines a class, Point, of objects with integer fields x and yand methods draw and move. ColorPoint is a subclass of Point that extendsPoint with an additional field c of type Color. It uses Point’s method formove, overrides its method for draw and defines a new method test thatperforms some computation and then invokes draw.

Finally, class C defineslocal fields and methods and uses ColorPoint.Now, consider the names that are visible inside method m of class C. Methodm maps x and y to their declarations in C. It expressly references the classnames Point and ColorPoint. The assignment y = p.x takes its right-handside from the field x in the object p, which p has by inheritance from classPoint. The left-hand side refers to m’s local variable y. The call to drawmaps to the method defined in ColorPoint. Thus, m refers to definitionsfrom all three classes in the example.class Point {public int x, y;public void draw() { ...