A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 52

For single-inheritance languages, method lookuptakes only two instructions. This seems like a small cost, but:••Modern machines can jump to constant addresses more efficiently than to addressesfetched from tables. When the address is manifest in the instruction stream, theprocessor is able to pre-fetch the instruction cache at the destination and direct theinstruction-issue mechanism to fetch at the target of the jump.

Unpredictable jumpsstall the instruction-issue and -execution pipeline for several cycles.An optimizing compiler that does inline expansion or interprocedural analysis willhave trouble analyzing the consequences of a call if it doesn't even know whichmethod instance is called at a given site.For multiple-inheritance and classless languages, the dynamic method-lookup cost is evenhigher.Thus, optimizing compilers for object-oriented languages do global program analysis todetermine those places where a method call is always calling the same method instance; thenthe dynamic method call can be replaced by a static function call.For a method call c.f(), where c is of class C, type hierarchy analysis is used to determinewhich subclasses of C contain methods f that may override C_f. If there is no such method,then the method instance must be C_f.This idea is combined with type propagation, a form of static dataflow analysis similar toreaching definitions (see Section 17.2).

After an assignment c ← new C, the exact class of c isknown. This information can be propagated through the assignment d ← c, and so on. Whend.f() is encountered, the type-propagation information limits the range of the type hierarchythat might contribute method instances to d.Suppose a method f defined in class C calls method g on this. But g is a dynamic methodand may be overridden, so this call requires a dynamic method lookup. An optimizingcompiler may make a different copy of a method instance C_f for each subclass (e.g., D,E)that extends C. Then when the (new copy) D_f calls g, the compiler knows to call the instanceD_g without a dynamic method lookup.244PROGRAM MiniJava WITH CLASS EXTENSIONImplement class extension in your MiniJava compiler.FURTHER READINGDahl and Nygaard's Simula-67 language [Birtwistle et al. 1973] introduced the notion ofclasses, objects, single inheritance, static methods, instance testing, typecase, and the prefixtechnique to implement static single inheritance.

In addition it had coroutines and garbagecollection.Cohen [1991] suggested the display for constant-time testing of class membership.Dynamic methods and multiple inheritance appeared in Smalltalk [Goldberg et al. 1983], butthe first implementations used slow searches of parent classes to find method instances. Rose[1988] and Connor et al. [1989] discuss fast hash-based field- and method-access algorithmsfor multiple inheritance. The use of graph coloring in implementing multiple inheritance isdue to Dixon et al.

[1989]. Lippman [1996] shows how C++-style multiple inheritance isimplemented.Chambers et al. [1991] describe several techniques to make classless, dynamically typedlanguages perform efficiently: pseudo-class descriptors, multiple versions of methodinstances, and other optimizations. Diwan et al. [1996] describe optimizations for staticallytyped languages that can replace dynamic method calls by static function calls.Conventional object-oriented languages choose a method instance for a call a.f(x,y) basedonly on the class of the method receiver (a) and not other arguments (x,y).

Languages withmultimethods [Bobrow et al. 1989] allow dynamic method lookup based on the types of allarguments. This would solve the problem of orthogonal directions of modularity discussed onpage 93. Chambers and Leavens [1995] show how to do static type-checking formultimethods; Amiel et al. [1994] and Chen and Turau [1994] show how to do efficientdynamic multimethod lookup.Nelson [1991] describes Modula-3, Stroustrup [1997] describes C++, and Arnold and Gosling[1996] describe Java.EXERCISES••*14.1 A problem with the display technique (as explained on page 290) for testingclass membership is that the maximum class-nesting depth N must be fixed inadvance, and every class descriptor needs N words of space even if most classes arenot deeply nested. Design a variant of the display technique that does not suffer fromthese problems; it will be a couple of instructions more costly than the one describedon page 290.14.2 The hash-table technique for finding field offsets and method instances in thepresence of multiple inheritance is shown incompletely on page 289 − the case of f ≠ptrx is not resolved.

Choose a collision-resolution technique, explain how it works, and•analyze the extra cost (in instructions) in the case that f = ptrx(no collision) and f ≠ ptrx(collision).*14.3 Consider the following class hierarchy, which contains five method-call sites.The task is to show which of the method-call sites call known method instances, and245(in each case) show which method instance. For example, you might say that "methodinstance X_g always calls Y_f; method Z_g may call more than one instance of f."••••••classclassclassclassclassclassABCDEFextendsextendsextendsextendsextendsABCAE{{{{{{intintintintintintf()g()f()g()g()g(){{{{{{return 1;this.f();this.g();this.f();this.f();this.f();} }returnreturnreturnreturnreturn2;3;4;5;6;}}}}}}}}}}Do this analysis for each of the following assumptions:••••a.

This is the entire program, and there are no other subclasses of these modules.b. This is part of a large program, and any of these classes may be extendedelsewhere.c. Classes C and E are local to this module, and cannot be extended elsewhere; theother classes may be extended.*14.4 Use method replication to improve your analysis of the program in Exercise14.3. That is, make every class override f and g. For example, in class B (which doesnot already override f), put a copy of method A_f, and in D put acopyof C_F:class B extends A { ...

int f() { return 1; } }class D extends C { ... int f() { this.g(); return 3; } }Similarly, add new instances E_f, F_f, and C_g. Now, for each set of assumptions (a),(b), and (c), show which method calls go to known static instances.•**14.5 Devise an efficient implementation mechanism for any typecase that onlymentions final classes.

A final class is one that cannot be extended. (In Java, thereis a final keyword; but even in other object-oriented languages, a class that is notexported from a module is effectively final, and a link-time whole-program analysiscan discover which classes are never extended, whether declared final or not.)You may make any of the following assumptions, but state which assumptions youneed to use:a. The linker has control over the placement of class-descriptor records.b. Class descriptors are integers managed by the linker that index into a table ofdescriptor records.c. The compiler explicitly marks final classes (in their descriptors).d. Code for typecase can be generated at link time.e.

After the program is running, no other classes and subclasses are dynamicallylinked into the program.246Appendix A: MiniJava Language ReferenceManualMiniJava is a subset of Java. The meaning of a MiniJava program is given by its meaning as aJava program. Overloading is not allowed in MiniJava. The MiniJava statementSystem.out.println( …); can only print integers.

The MiniJava expression e.length onlyapplies to expressions of type int[].A.1 LEXICAL ISSUESIdentifiers: An identifier is a sequence of letters, digits, and underscores, starting with aletter. Uppercase letters are distinguished from lowercase. In this appendix the symbol idstands for an identifier.Integer literals: A sequence of decimal digits is an integer constant that denotes thecorresponding integer value.

In this appendix the symbol INTEGER_LITERAL stands for aninteger constant.Binary operators: A binary operator is one of&& < + - *In this appendix the symbol op stands for a binary operator.Comments: A comment may appear between any two tokens. There are two forms ofcomments: One starts with /*, ends with */, and may be nested; another begins with // andgoes to the end of the line.A.2 GRAMMARIn the MiniJava grammar, we use the notation N*, where N is a nonterminal, to mean 0, 1, ormore repetitions of N.GRAMMAR A.2Program → MainClass ClassDecl*MainClass → class id { public static void main ( String [] id ){ Statement }}ClassDecl → class id { VarDecl* MethodDecl* }→ class id extends id { VarDecl* MethodDecl* }VarDecl → Type id ;MethodDecl → public Type id ( FormalList ){ VarDecl* Statement* return Exp ;}FormalList → Type id FormalRest*→FormalRest →, Type idType → int []→ boolean→ int247→ idStatement → { Statement* }→ if ( Exp ) Statement else Statement→ while ( Exp ) Statement→ System.out.println ( Exp ) ;→ id = Exp ;→ id [ Exp ]= Exp ;Exp → Exp op Exp→ Exp [ Exp ]→ Exp .

length→ Exp . id ( ExpList )→ INTEGER LITERAL→ true→ false→ id→ this→ new int [ Exp ]→ new id ()→ ! Exp→ ( Exp )ExpList → Exp ExpRest*ExpRest→→,ExpA.3 SAMPLE PROGRAMclass Factorial {public static void main(String[] a) {System.out.println(new Fac().ComputeFac(10));}}class Fac {public int ComputeFac(int num) {int num_aux;if (num < 1)num_aux = 1;elsenum_aux = num * (this.ComputeFac(num-1));return num_aux;}248.