Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-07-22
2001-02-27
Hafiz, Tariq R. (Department: 2762)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06195793
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the data processing field and compiler optimization techniques, and more particularly, relates to a computer implemented method and computer program compiler product for implementing adaptive inlining in a computer system.
DESCRIPTION OF THE RELATED ART
Many languages, particularly object-oriented languages such as Java and C++, encourage a programming style in which procedure calls occur frequently and procedure sizes are small. For such languages, a compiler optimization technique called inlining is extremely important to performance. Although the details can be somewhat complex, the idea is simple. With inlining, a call to a procedure can be replaced by a duplicate of the body of the called procedure. The advantages of inlining are (1) removal of the call overhead required by the procedure calling conventions, and (2) increased optimization opportunities that may arise when the compiler can see the called procedure's instructions in context.
There are disadvantages to inlining as well. One of the most important is the problem of code bloat. If every procedure call in a program was inlined, the program could become extremely large. When this happens, the gains from reduced call overhead and increased optimization can be quickly overwhelmed by the negative caching and paging effects of the enlarged program. Therefore, it is incumbent upon an optimizer to be selective about which procedure calls it chooses to inline.
Most known inliners use the concept of a budget to determine how much code bloat can be tolerated. Inline candidates are ordered on a list according to some heuristic preference, and then candidates from the list are processed until the budget is exhausted. The budget is usually expressed in terms of the amount of expansion that a compile unit is permitted to undergo, although some researchers have suggested using an estimate of compile time as their budget. This is a minority viewpoint.
Determining the best set of call sites to inline within the constraints of a code bloat budget is known to be difficult to solve. Any approach for selecting which sites to inline is necessarily heuristic. There are two techniques described in the literature for selecting which sites to inline. Both techniques require that a call graph be built first, in which each node represents a procedure, and an arc represents a call from the originating node's procedure to the target node's procedure.
The first technique processes the call graph bottom up from the leaves, inlining any procedure that matches some criterion, such as, small size, frequency of execution, and the like, that makes the procedure a good candidate. This is done until the code bloat budget is exhausted. One problem with this technique is that there may be better inline candidates or arcs further up the tree, and the budget may be exhausted before these arcs are reached.
The second technique tries to solve this problem by ordering the arcs in the call graph according to decreasing order of frequency, then selecting the corresponding procedure calls for inlining from the beginning of the list, until the budget is used up. This also has a problem, in that the code bloat estimates may be very inaccurate, and hence the budget may be heavily overspent.
For example, consider a set of procedures in which A calls B, and B calls C, D, E, and F. Each procedure originally consists of 100 instructions. Suppose that our code bloat budget is 500 instructions. Looking at each of these five procedure calls in isolation, the optimizer will estimate the code bloat for each as 100 instructions, and choose to inline all of these calls. Once C, D, E, and F are inlined into B, however, B's size has swollen to 500 instructions, rather than 100. Assuming that B, C, D, E, and F are all called from other procedures and therefore cannot be eliminated, we have increased the program's size by 900 instructions, rather than 500.
A need exists for an effective inlining technique in a computer system, capable of selecting important inline candidates without excessive code bloat.
SUMMARY OF THE INVENTION
A principal object of the present invention is to provide a method and computer program product for implementing adaptive inlining in a computer system. Other important objects of the present invention are to provide such method and computer program product for implementing adaptive inlining substantially without negative effect and that overcome some of the disadvantages of prior art arrangements.
In brief, a method and computer program product are provided for implementing adaptive inlining in a computer system. Call sites in a call multigraph are identified for possible inlining. A first approximation of initial call sites of the identified possible call sites are identified for inlining. Procedures in the call multigraph are processed in a determined order where a first procedure is only processed after all second procedures called by the first procedure are processed. The processing of the first procedure comprises the steps of determining whether any call site within the first procedure has been selected for inlining, and whether the second procedure called from the call site contains confirmed inlined call sites. If true, it is determined whether to confirm or reject the first approximation to inline the second procedure into the first procedure at the call site utilizing at least one predetermined criterion.
REFERENCES:
patent: 5230050 (1993-07-01), Iitsuka et al.
patent: 5740443 (1998-04-01), Carini
patent: 5768595 (1998-06-01), Gillies
patent: 5857105 (1999-01-01), Ayers et al.
patent: 5920723 (1999-07-01), Peyton, Jr. et al.
patent: 6009273 (1999-12-01), Ayers et al.
patent: 6041179 (2000-03-01), Bacon et al.
patent: 6101326 (2000-08-01), Mattson, Jr.
Title: Towards better inlining decisions using inlining, author: Dean J.; Chambers, C, 1994 ACM.
Title: A compiler for selective procedure inlining, author: Holland, A.; McDaniel, R, ACM, 1993.
Title: Reducing Indirect Function Call Overhead In C++ Program, author: Calder et al, ACM in 1994.
Title: Flow-directed Inlining, author: Jagannathan et al, ACM in 1996.
Title: Optimizing direct threaded code by selective inlining, author: Plumarta et al, ACM 1998.
Das Chameli C.
Hafiz Tariq R.
International Business Machines - Corporation
Pennington Joan
LandOfFree
Method and computer program product for adaptive inlining in... 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 adaptive inlining in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and computer program product for adaptive inlining in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605998