Object oriented dispatch optimization

Abstract

An object oriented dispatch optimization method determines statically which body of code will be executed when a method is dispatched. The program code is examined to identify all procedure bodies that can be invoked for a given class and a given method. An identified procedure body is analyzed to determine whether a method invocation on a pointer can invoke only one procedure body. Based on this analysis, either the procedure body or the invocation mechanism is changed so a unique procedure is directly called without a test or dispatch being used.

Claims

Having thus described our invention, what we claim as new and desire to secure by Letters Patent is as follows:

1. A computer-implemented method for reducing an object oriented program, comprising the steps of:

identifying initial members of a set of live methods and procedures within said program, said initial members comprising methods and procedures that by definition in the program must be executed when the program is run;

identifying initial members of a set of live classes within said program, said initial members comprising classes that must be created when the program is run, based on said initial set of live methods and procedures;

identifying an additional set of live methods and procedures, comprising the additional methods and procedures reachable from the live methods and procedures within said set of live methods and procedures, and adding said additional set to said set of live methods and procedures;

identifying an additional set of live classes, comprising the additional classes potentially creatable by said identified set of additional live methods and procedures;

converting indirect methods invocations to direct method calls which do not perform a runtime type test or dynamic dispatch; and

repeating said steps of identifying an additional set of live methods and procedures and of identifying an additional set of live classes until no further methods or procedures are added to said set of live methods and procedures.

2. A computer-implemented method for reducing an object oriented program, comprising the steps of:

identifying initial members of a set of live methods and procedures within said program, said initial members comprising methods and procedures that by definition in the program must be executed when the program is run;

identifying initial members of a set of live classes within said program, said initial members comprising classes that must be created when the program is run, based on said initial set of live methods and procedures;

identifying an additional set of live methods and procedures, comprising the additional methods and procedures reachable from the live methods and procedures within said set of live methods and procedures, and adding said additional set to said set of live methods and procedures;

identifying an additional set of live classes, comprising the additional classes potentially creatable by said identified set of additional live methods and procedures;

repeating said steps of identifying an additional set of live methods and procedures and of identifying an additional set of live classes until no further methods or procedures are added to said set of live methods and procedures; and

removing methods and procedures not identified as live.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to dispatch optimization in an object oriented environment and, more particularly, to a method for determining statically which body of code will be executed when a method is dispatched.

2. Background Description

Object oriented programming (OOP) is the preferred environment for building user-friendly, intelligent computer software. Key elements of OOP are data encapsulation, inheritance of attributes and polymorphism (i.e., overloading of operator names). While these three key elements are common to OOP languages, most OOP languages implement the three key elements differently.

In a conventional programming language, such as C or Pascal, procedures and functions are written to manipulate data and obtain solutions. In contrast, object oriented programming allows the programmer to view concepts as a variety of units or objects in a hierarchy, without worrying about the data type, repeated variable names, or function names. This allows the programmer to concentrate on the program design, rather than programming rules. The programmer can represent relationships among components, objects, tasks to be performed, and conditions to be met in a way that allows the reuse of code components and reduces the bulkiness of code and the time and effort needed to develop programs.

Examples of OOP languages are Smalltalk, Object Pascal, Java, and C++, all of which are well known in the art of computer languages, compilers, and applications programming. Of these, Smalltalk may be characterized as a programming environment instead of merely a language. Smalltalk was developed in the Learning Research Group at Xerox's Palo Alto Research Center (PARC) in the early 1970s. In Smalltalk, a message is sent to an object to evaluate the object itself. Messages perform a task similar to that of function calls in conventional programming languages. The programmer does not need to be concerned with the type of data. Instead, the programmer need only be concerned with using the right message. Object Pascal, another OOP, was created by developers from Apple Computer, some of whom were involved in the development of Smalltalk at PARC, in conjunction with Niklaus Wirth, the designer of Pascal. C++ was developed by Bjarne Stroustrup at the AT&T Bell Laboratories in 1983 as an extension of C. C++ modules are compatible with C modules and can be linked freely so that existing C libraries may be used with C++ programs.

The key concept of all OOP is the class, which is a user-defined type. Classes provide object oriented programming features. Further information on object oriented programming concepts may be obtained by referring to one of several standard text books, such as Object Oriented Design with Applications by Grady Booch, The Benjamin/Cummings Publishing Co., Inc. (1991).

To focus this description on the instant invention, and minimize unnecessary discussion of background information known to persons skilled in the art, descriptive terms will be used where appropriate which, except where noted or where clear from the context, are familiar terms known to ones of ordinary skill in OOP. More particularly, as used herein, a class is a definition of a type of object, describing its methods and the kinds of data that can be placed in the object. During execution of the program various objects are created. When an object is created based on a class, that is called an instance of that class and the names of the individual pieces of data are called instance variables.

The procedures that can be invoked on the data in an instance of a class are the methods of that class. The class definition therefore contains descriptions of both the instance variables and the methods.

Further, a class such as, for example, foo, can be defined in terms of another class such as, for example, bar, by declaring that foo is like bar except that it may contain additional instance variables, additional methods, or that some of the methods have a different definition. In this way the definition of foo can be much shorter than bar's. In this case, foo is said to inherit from bar. Foo is said to be a derived class of bar. Moreover, bar is said to be a base class of foo. If baz is a derived class of foo, then baz is also a base class of bar, which is to say the derived class (and base class) relations are transitive.

A class and its derived class may contain different definitions for an identically named method. For example, foo and bar may both have a method called, for example, addsub, and both have an instance variable named, for example, I, but when addsub is invoked on an instance of foo, I is increased by one, and when it is invoked on an instance of bar, I is decreased by one. The method body, also known as function body, for addsub when the instance is of type foo is the method body which increases I, and the method body for addsub when the instance is of type bar is that which decreases I by one.

It is, in general, not possible to determine (either by compilers or by humans) when looking at a program which invokes a method on an instance what class that instance will be. The reason is that, as the program proceeds, the same code can be applied to instances of many different classes. Therefore, at the time the program is executing the code must determine the class of an instance and invoke the appropriate function body. This process of determining the class of an instance and invoking the appropriate function body is called method dispatch. Method dispatch consists of using both information about the class of the instance and the name of the method to determine which code should be executed next.

In Smalltalk, all method dispatches are made dynamically. In other words, the actual method body that will be invoked at a particular method invocation site is determined by a combination of the class of the object and the name of the method. This may be done by following a pointer from the object to its class, and then looking up the method in the classes' method table. In contrast, C++ allows the programmer to decide whether a particular method should be dispatched statically or dynamically. Methods that are dispatched dynamically are called "virtual methods." The present invention is concerned only with virtual method invocations and, therefore, methods that are dispatched statically will not be described. Accordingly, when the following description references C++ programs, the terms "method dispatch" or "method invocation," unless otherwise qualified, shall mean "virtual method dispatch" or "virtual method invocation." Note that in the C++ literature, a virtual method dispatch is also referred to as a "virtual function call."

Method dispatches are a major source of complexity when trying to optimize the programs. More particularly, there is a direct cost associated with method dispatches in the form of the extra instructions required for the dynamic dispatch, including extra memory operations, and pipeline penalties caused by branching to an unknown address. For C++ programs, these costs have been estimated as ranging from 0% of the total run time, for programs that make no significant use of method dispatch, to 6%, for programs that make moderate use of method dispatch, to 27%, for programs that make extensive use of method dispatch.

There is also an indirect cost relating to inlining" which, in many cases, may be even more significant. As is known in the art, inlining is the process whereby a procedure call is replaced with a copy of the body of the called procedure. Inlining is much more important in object oriented languages than in non-object oriented languages, such as C or Fortran, because object oriented languages encourage smaller, more modularized functions, and often have a linguistic mechanism to support inlining. Studies have shown that C++ functions do in fact have significantly smaller static and dynamic instruction counts than C programs. However, when a method dispatch is dynamic, inlining cannot be performed.

Another cost associated with method dispatch is compilation speed and compiled code size. The compiled code size is increased, and hence the compilation speed is decreased because, without any information about the potential targets of a method dispatch, all the possible methods must be linked into the program. This slows down linkage and causes unused methods to bloat the object file.

There are methods in the relevant art directed to reducing, at least partially, the above-identified problems relating to inlining and compilation speed and compiled code size, but each has limitations in performance, or requires so large of a processing time as to be impracticable.

One of these methods, which will be referred to as the Resolution by Unique Name method, is described by Brad Calder and Dirk Grunwald (hereinafter referenced as "Calder and Grunwald") in their article entitled "Reducing Indirect Function Call Overhead in C++ Programs," Conference Record of the 21st ACM Symposium on Principles of Programming Languages, Portland, Oreg., January 1994, pp. 397-408. In the referenced article, Calder and Grunwald observed that in C++ if there is only one method body defined for a given method signature in the entire program, then all dispatches for that method must be to that one method body. The method signature or function signature in a typed language like C++, Java, or Modula-3 is its name and the number and types of its arguments; for untyped languages like Smalltalk it is just the name and the number of arguments.

It can be seen that if one can determine that for all dispatches from a particular point in the program a particular method body must be invoked, then that dispatch can be replaced by a direct call to the appropriate body of code without modifying the end result of the program, and hence this replacement can safely be done automatically. Calder and Grunwald have published some preliminary measurements stating that, in their selected set of particular benchmark programs, it is possible with the Resolution by Unique Name Method to replace approximately one third of the method dispatches by a direct call.

Calder and Grunwald's Resolution by Unique Name Method can be summarized as being an algorithm for determining when a method dispatch can go only to a single method body, which consists of the steps of:

examining the entire program;

determining which methods have only one method body associated with that method signature;

examining a method dispatch; and

determining whether that method is one of the methods previously determined to have only one function and, if so, converting the dispatch to a direct call.

There is at least one problem with the Resolution by Unique Name Method, though, which is that the replacement of a dispatch by a direct call cannot be done by a traditional compiler. The major reason is that a compiler is usually not given an entire program at a time, but only a piece of the program. The entire program is composed by a program called a linker. Hence, the Resolution by Unique Name Method is generally referred to as a link-time optimization. It is possible for Calder and Grunwald's method to be performed at other times, if it is given appropriate information. For example, if a database of information about an entire program is built first, then when a compiler is used to compile a piece of a program, it can refer to information in the built database about the rest of the program. However, if the rest of the program changes, and the information which was relied upon changes, the program may have to be recompiled using the new information.

Another related method directed to resolving virtual function dispatch is called class hierarchy analysis (henceforth "CHA"), and is described by Dean, Grove and Chambers in "Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis", in the Proceedings of the Ninth European Conference on Object-Oriented Programming, Springer-Verlag, 1995. CHA uses the type information supplied only in statically typed languages, therefore, is not applicable to a dynamically-typed OOP languages such as Smalltalk.

The meaning of statically-typed, which relates to OOP languages such as C++ is as follows: When a virtual function call is made in C++, it is dispatched through a pointer or a reference to an object, and that pointer has a particular type. The type is either specified explicitly, i.e., statically, by the programmer, or is statically derivable by the compiler from other type information, as shown in the example below:

    ______________________________________
    class A {public: virtual void bar();};
    class B: public A {public: void bar();
    A* top;};
    class C: public B {public: virtual void glorp();
    };
    void example (B* p) {
    p .fwdarw. bar(); // Call via explicit type "B"
    p .fwdarw. top .fwdarw. bar(); // Call via implicit type "A"
    ______________________________________

• Inventors
  Bacon, David Francis; Wegman, Mark N.; Zadeck, Frank Kenneth;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Mar-21-2000
• Current US Classes:
  717/116
  717/151
• Application #
  723058
• International Classes
  G06F 013/00
• Field of Search
  395/703 395/702 395/700 395/685 395/683 395/650 395/707 395/709
• Examiner
  Voeltz; Emanuel Todd
• Agent
  Whitham, Curtis & Whitham, Percello; Louis J.
• US Patent References:
  5450583
  5499371
  5579518
  5600838
  5659751
  5675801