Static binding of dynamically-dispatched calls in the...

Details Static binding of dynamically-dispatched calls in the... Static binding of dynamically-dispatched calls in the...

1999-03-10

2004-03-09

Nguyen-Ba, Antony (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S139000, C717S140000, C717S148000, C717S152000, C717S153000, C717S165000

Reexamination Certificate

active

06704927

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to runtime compilation of software. More specifically, the invention relates to techniques for performing static binding of dynamically-dispatched calls in the presence of dynamic linking and loading.
The fundamental idea behind object-oriented languages is the combination of both data and the methods (or functions) that operate on that data into a single unit, which is called an object. An object's functions typically provide the only way to access the data that is encapsulated by the object. The data is accessed by sending a message to the object instructing the object to invoke the method specified by the message.
Efficient message dispatch is of paramount importance in object-oriented languages. This is because message dispatch is a very frequent operation in object-oriented programs and is performed at runtime; therefore, it should be as fast as possible. Message dispatch, however, is far from being a trivial operation. Unlike procedural programming languages (e.g., the C programming language) that can determine a function's address before runtime, object-oriented languages must determine the method that handles a message that has been dispatched to a receiver object dynamically at runtime, and it may involve an extensive search.
In order to better understand the complexities of message dispatch, an example of a class hierarchy will be described.
FIG. 1
shows a class hierarchy including methods of each class. A class hierarchy
1
includes at its root a parent class A
3
that defines two virtual functions foo( ) and bar( ). Virtual functions are functions that may be defined in a parent class and redefined in associated children classes. Classes B
5
and class C
7
inherently include the data and methods of the parent class A
3
. As shown, class B
5
does not redefine either of the virtual functions foo( ) and bar( ). However, class C
7
redefines the virtual function foo( ). When an object of class C
7
is requested to invoke the method foo( ), the method invoked will be the method defined by the class C
7
, not the method defined in the parent class A
3
. Classes D
9
and E
11
also redefine the method foo( ).
As it is generally impossible to determine the class of an object statically, the search for the correct method associated with the object is performed during runtime execution or, more specifically, during message dispatch. For example, assume a method is as follows:
test( )
{
. . .
x.foo( );
. . .
}
If all of classes A-E are loaded at runtime execution, the determination of which function foo( ) to call will depend on which class x is an instance.
Furthermore, the test function may be compiled at runtime to increase performance. At runtime compilation, it is possible that only classes A
3
and B
5
are loaded. Accordingly, it appears from inspection of the loaded classes that one may assume that the message x.foo( ) will only invoke A::foo( ). Of course, if during runtime execution class C
7
is loaded, this assumption would prove to be false.
SUMMARY OF THE INVENTION
In general, embodiments of the present invention provide innovative techniques for performing static binding of dispatched-calls in the presence of dynamic linking and loading. As a method is being compiled at runtime, dynamically-dispatched calls are identified. The current class hierarchy is analyzed to determine how the calls may be optimized. The calls may be optimized and dependency information may be added to the compiled method so that when classes are loaded at runtime execution, it can be determined if the compiled method is still valid, should be interpreted (e.g., deoptimized), or recompiled (e.g., reoptimized).
According to one aspect of the present invention, a method for increasing the execution performance of a function at run-time includes compiling the function, which may either be interpreted or previously compiled, and identifying a call within the function to a process. The method also includes adding dependency information to the function. The dependency information is arranged to indicate a status of the function, and contains information pertaining to the class, the name, and the signature associated with the process.
In one embodiment, the process is a virtual process, and the method includes analyzing a class structure associated with the function in order to determine when the virtual process is a substantially unique target of the call. In such an embodiment, the virtual process may be inlined into the function when it is determined that the virtual process is the substantially unique target of the call. Alternatively, in such an embodiment, a direct call to the virtual process may be placed in the function.
According to another aspect of the present invention, a computer-implemented method for analyzing a first class associated with a class hierarchy of a system during run-time includes marking the first class and marking a second class that is a superclass of the first class to indicate an associated between the two class. A compiled function associated with the system is then inspected. The compiled function includes dependency information that is arranged to indicate a validity status of the compiled function as well as the optimization status of the compiled function. Inspecting the compiled function includes determining when at least one of the first class and the second class is identified in the dependency information. When it is determined that either the first class or both the first class and the second class is identified in the dependency information, a determination is made regarding whether the compiled function is invalid. In one embodiment, the method may include de-optimizing the compiled function when it is determined that the compiled function is invalid. De-optimizing the compiled function may return the function to an interpreted state.


REFERENCES:
patent: 5579518 (1996-11-01), Yasumatsu
patent: 5606699 (1997-02-01), De Pauw et al.
patent: 5613120 (1997-03-01), Palay et al.
patent: 5748961 (1998-05-01), Hanna et al.
patent: 5764989 (1998-06-01), Gustafsson et al.
patent: 5966537 (1999-10-01), Ravichandran
patent: 5983020 (1999-11-01), Sweeney et al.
patent: 5983021 (1999-11-01), Mitrovic
patent: 6063128 (2000-05-01), Bentley et al.
patent: 6085035 (2000-07-01), Ungar
patent: 6230314 (2001-05-01), Sweeney et al.
patent: 6240547 (2001-05-01), Holzle et al.
patent: 6260075 (2001-07-01), Cabrero et al.
patent: 6282581 (2001-08-01), Moore et al.
patent: WO 96/35990 (1996-11-01), None
Karkowski-Corporaal, Overcoming the Limitations of the Traditional Loop Parallelization, 1998, Delft University of Technology.*
J. Dean et al., “Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis”, Aug. 1995, ECOOP'95—Object-Oriented Programming. 9thEuropean Confrence.

Affiliated with

Also associated with

Rating

Static binding of dynamically-dispatched calls in the... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Static binding of dynamically-dispatched calls in the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Static binding of dynamically-dispatched calls in the... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3246105