OPTIMIZING OBJECT-ORIENTED PROGRAMS

An optimization of particular importance to object-oriented languages (which also benefit from most optimizations that apply to coding languages in general) is the conversion of dynamic method calls to static method-instance calls. Compared with an ordinary function call, at each method call site there is a dynamic method lookup to determine the method instance. For single-inheritance languages, method lookup takes only two instructions. This seems like a small cost, but:

• Modern machines can jump to constant addresses more efficiently than to addresses fetched from tables. When the address is manifest in the instruction stream, the processor is able to pre-fetch the instruction cache at the destination and direct the instruction-issue mechanism to fetch at the target of the jump. Unpredictable jumps stall the instruction-issue and -execution pipeline for several cycles.
• An optimizing compiler that does inline expansion or interprocedural analysis will have trouble analyzing the consequences of a call if it doesn't even know which method instance is called at a given site.

For multiple-inheritance and classless languages, the dynamic method-lookup cost is even higher. Thus, optimizing compilers for object-oriented languages do global program analysis to determine those places where a method call is always calling the same method instance; then the 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 determine which 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 to reaching definitions (see ). After an assignment c ← new C, the exact class of c is known. This information can be propagated through the assignment d ← c, and so on. When d.f() is encountered, the type-propagation information limits the range of the type hierarchy that might contribute method instances to d.

Suppose a method f defined in class C calls method g on this. But g is a dynamic method and may be overridden, so this call requires a dynamic method lookup. An optimizing compiler 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 instance D_g without a dynamic method lookup.