Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-01-27
2003-04-08
Morse, Gregory (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S150000, C717S140000, C717S151000, C712S233000, C712S234000
Reexamination Certificate
active
06546550
ABSTRACT:
DETAILED DESCRIPTION OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for dynamically using a compiler in executing a bytecode which is an intermediate code of Java™ (a trademark of Sun Microsystems, Inc.), Smalltalk, and the like.
2. Background of the Invention
Conventionally, in a bytecode interpreter of a virtual machine in Java™, Smalltalk, and the like, optimization is often performed by compiling (at execution time) those bytecodes which are frequently executed. This optimization is achieved by determining the frequency that each method is called and comparing the results to a threshold value. Only those methods with call frequencies that exceed the threshold are compiled, saving overall compilation time.
However, in the above-mentioned conventional method, frequency of calling a method is a trigger for compilation; therefore, even if a loop whose iteration number is huge is included in a method, it is not selected for compilation
SUMMARY OF THE INVENTION
An object of the present invention is to solve the above-mentioned problem and detect a method including a loop and estimate an effect of compiling the method at a low cost at an execution time so as to provide a method for a more efficient bytecode execution by selecting an execution mode according to the estimation.
Another object of the present invention is to provide a method for enabling more efficient processing of an interpreter and a compiler by recording an execution history of a conditional branch instruction and the like simultaneously with detection of a loop.
In the method for determining a dynamic compilation time which is the first form of the present invention, first, at a time of a bytecode execution by an interpreter, if an instruction to be executed is a backward conditional branch instruction, it is determined whether the backward conditional branch instruction is a back edge of a loop. And if it is determined the instruction is a back edge of a loop, the number of the loop iteration is estimated and stored into a storage. The time of compilation is determined according to the estimated number of the loop iteration.
In the method for selecting a bytecode execution mode which is the second form of the present invention, first, at a time of a bytecode execution by an interpreter, if an instruction to be executed is a backward conditional branch instruction, it is determined whether the backward conditional branch instruction is a back edge of a loop. And if it is determined the instruction is a back edge of a loop, the number of the loop iteration is estimated and stored into a storage. A bytecode execution mode is selected according to the estimated number of the loop iteration.
In a suitable form of embodiment, an execution mode comprises the modes of immediately compiling a method including a loop; and having the interpreter execute a bytecode. In a further suitable form of embodiment, the mode of immediately compiling a method including a loop comprises a predetermined number of modes whose optimization levels were changed according to the estimated number of the loop iteration. It is also possible, in the mode of having the interpreter execute a bytecode, to organize it so that the time of compiling a method including a loop is determined according to the estimated number of the loop iteration.
Determination in the first and second forms of the present invention, of whether the backward conditional branch instruction is a back edge of a loop, is suitably performed by pattern matching using state transition of a bytecode sequence comprised of a predetermined number of instructions prior to the conditional branch instruction and a bytecode sequence corresponding to an actual back edge of a loop. In addition, suitably, the number of the loop iteration is estimated from operands of a predetermined number of instructions prior to the conditional branch instruction. More suitably, an operation code of the conditional branch instruction which determined whether the instruction is a back edge of a loop is modified to indicate that it is already determined and/or whether a conditional branch has been taken.
While a flow of processing of the present invention is explained as above, the present invention can also be implemented by a device for implementing these processes or in a form of a program for having a computer implement these processes. Storing of this program on storage media such as a floppy disk, CD-ROM, or any other form of storage is well understood by one having ordinary skill in the art.
REFERENCES:
patent: 4755966 (1988-07-01), Lee et al.
patent: 5428786 (1995-06-01), Sites
patent: 5748964 (1998-05-01), Gosling
patent: 5768593 (1998-06-01), Walters et al.
patent: 5881278 (1999-03-01), Tran et al.
patent: 5887152 (1999-03-01), Tran
patent: 5966538 (1999-10-01), Granston et al.
patent: 5970249 (1999-10-01), Holzle et al.
patent: 5995754 (1999-11-01), Holzle et al.
patent: 6118940 (2000-09-01), Alexander, III et al.
patent: 6237141 (2001-05-01), Holzle et al.
patent: 6282702 (2001-08-01), Ungar
patent: 6336213 (2002-01-01), Beadle et al.
patent: 6374349 (2002-04-01), McFarling
patent: 6374351 (2002-04-01), Tremblay
patent: 6393549 (2002-05-01), Tran et al.
patent: 6397379 (2002-05-01), Yates, Jr. et al.
patent: 6401196 (2002-06-01), Lee et al.
patent: 8-87417 (1996-04-01), None
Title: A Dynamic Programming Technique for Compacting Loop, Vegdahl, ACM, 1992.*
Title: Improving Data-flow Analysis with path profiles, author: Ammons et al, ACM, May 1998.*
Title: Two-Level Adaptive Training Branch Prediction, author: Yeh et al, ACM, 1991.*
Title: Reducing the Branch Penalty in Pipelined Processors, author Lilja, IEEE, 1988. Title: Reducing the branch Penalty in pipelined processors, author: lilja, IEEE, 1988.*
Java World, vol. 2, No. 7, issued by IDG Communications, Col, Ltd, pp. 40-51.
Dohji Hiroshi
Komatsu Hideaki
Ogata Kazunori
Das Chameli C.
International Business Machines - Corporation
Morse Gregory
Roth Steven W.
LandOfFree
Method to determine dynamic compilation time and to select... 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 to determine dynamic compilation time and to select..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method to determine dynamic compilation time and to select... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3090618