Method and computer program product for implementing method...

Details Method and computer program product for implementing method... Method and computer program product for implementing method...

1998-07-15

2001-01-16

Chaki, Kakali (Department: 2762)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000

Reexamination Certificate

active

06175956

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the data processing field and compiler optimization techniques, and more particularly, relates to a method and computer program product for implementing method calls in a computer system.
DESCRIPTION OF THE RELATED ART
A pervasive feature of object oriented languages such as Java and C++ is the virtual method call. By default, classes in these languages can be inherited from or subclassed. A variable whose type is a given class may, during run time, reference an instance of that class or of any subclass of that class. A subclass can override a method inherited from its parent class with a different implementation specific to that class. A method that can be overridden is called a virtual method. Because objects of different exact type may be referenced by a single variable, access to methods associated with a variable must be done indirectly. Typically the object associated with the variable contains a reference to a data structure kept with its class and known as a virtual method table, containing slots that point to the actual methods to be called.
Thus a virtual method call is more expensive than a procedure call in which the target procedure is known at compile time (a so-called bound call). Not only is it more costly to perform the indirection to find the method address, but the presence of this indirection inhibits optimization. For example, the targeted method body cannot be inlined, even though it may be that there is only one method that could be called from a given call site. Since virtual method calls typically occur frequently, any speedup of the virtual call mechanism can produce noticeable performance improvements.
Devirtualization is a technique for replacing a virtual method call with one or more bound procedure calls. Devirtualization relies upon knowing which potential targets are most likely to be called at a given call site. This data is usually obtained using some form of program profiling. In its simplest form, a virtual call to a.foo() that usually ends up calling Y.foo() (where a is of type X, and Y is a subclass of X) can be replaced by:
if (guard) then
Y.foo();
else
a.foo();
end if;
Here guard is a conditional test that determines whether Y.foo() is really the correct method to call. For this to be profitable, the cost of testing the guard condition and performing the bound call must be less expensive than the original virtual call. Devirtualization is thus most useful when the known call target, Y.foo() in the above example, can be inlined at the call site, removing the procedure call/return overhead and often improving other optimization opportunities.
If a virtual call site has more than one common target, it may sometimes be profitable to use a chain of tests; for example:
if (guard1) then
Y.foo();
else if (guard2) then
Z.foo();
else
a.foo();
end if;
Two kinds of guard conditions have been used in existing systems. One possibility is to test directly whether the address of the procedure in the virtual call table is equal to the address of the expected procedure. This may appear to not be profitable, since once the address has been computed the procedure can simply be called, and so little saving is apparent. However, if the expected procedure can be inlined and further optimized, this technique can still be profitable. In the past, it has been used chiefly when type information is not available. An example environment for this is C++ without RTTI.
A guard condition that is often more efficient is available when each object has an associated runtime type. The type of the object can typically be assessed more quickly than the virtual function address with at least one less indirection. Thus we can test whether the type of the current object is equal to the type of the expected object at lower cost than the address test.
Previous systems have used one or the other of these guard conditions, but not both. However, neither of these guard conditions is always the best choice. Typically the address test has been avoided when type information is available, since it is apparently less expensive, but an example will illustrate that the address test is sometimes preferable as follows.
Suppose that profile data indicates that a virtual call site invokes X.foo() 65% of the time, Y.foo() 30% of the time, and other procedures the remaining 5% of the time. Suppose further that Y is a subclass of X that overrides foo. Then one of the following code snippets in table 1 or table 2 could be generated using type tests:
TABLE 1
if(a.type == X) then
X.foo();
else
a.foo();
end if;
TABLE 2
if (a.type == X) then
X.foo();
else if (a.type == Y) then
Y.foo();
else
a.foo();
end if;
The type tests are cheaper than the address testing of whether a.foo==X.foo, etc. However, now suppose that Y does not override foo. Then X.foo and Y.foo are really the same function. In the table 1 code snippet, an object of type Y will fail the type test and use the indirect virtual call, despite the fact that X.foo() is the correct function to be called. In the table 2 code snippet, an object of type Y will require two type tests before calling the correct function, instead of just one. Furthermore, inlining both X.foo and Y.foo needlessly doubles the amount of code bloat incurred, since both are the same function.
This illustrates that using either address information or type information is not sufficient. A need exists for a flexible method for devirtualization of virtual method calls.
SUMMARY OF THE INVENTION
A principal object of the present invention is to provide a method and computer program product for implementing method calls in a computer system. Other important objects of the present invention are to provide such method and computer program product for implementing method calls substantially without negative effect and that overcome many of the disadvantages of prior art arrangements.
In brief, a computer implemented method and computer program compiler product are provided for implementing method calls in a computer system. Virtual method calls are identified in an intermediate instruction stream representation. Responsive to an identified virtual method call, profile data for the identified call site are read. A most frequently called procedure for the identified call site is compared with a first threshold value. Responsive to the most frequently called procedure being called less than the first threshold value, the virtual method call is maintained in a revised instruction stream representation. Responsive to the most frequently called procedure being called greater than or equal to the first threshold value, a guarded call to the most frequently called procedure is inserted at the identified call site in the revised instruction stream representation.
In accordance with features of the invention, checking whether one object type accounts for more than a second threshold value of the calls to the most frequently called procedure at the identified call site is performed. Responsive to one object type accounting for more than or equal to the second threshold value, a type guard and a call to the most frequently called procedure are inserted at the identified call site in the revised instruction stream representation. Responsive to one object type accounting for less than the second threshold value, an address guard and a call to the most frequently called procedure are inserted at the identified call site in the revised instruction stream representation.


REFERENCES:
patent: 5222221 (1993-06-01), Houri et al.
patent: 5740443 (1998-04-01), Carini
patent: 5768595 (1998-06-01), Gillies
patent: 5787285 (1998-07-01), Lanning
patent: 5828883 (1998-10-01), Hall
patent: 5857097 (1999-01-01), Henzinger et al.
patent: 5857103 (1999-01-01), Grove
patent: 5896538 (1999-04-01), Blandy et al.
patent: 5915250 (1999-06-01), Jain et al.
patent: 5940618 (1999-08-01), Blandy et al.
patent: 5940622 (1999-08-01), Patel
patent: 5963740 (1999-10-01), Srivastava et al.
patent

Affiliated with

Also associated with

Rating

Method and computer program product for implementing method... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and computer program product for implementing method..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and computer program product for implementing method... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2551140