Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-04-27
2001-02-20
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
Reexamination Certificate
active
06192516
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to software interpreter implementation and generation. More specifically, implementing and generating an interpreter for the Java™ virtual machine that utilizes registers to optimize the stack-based operations.
The Java™ programming language is an object-oriented high level programming language developed by Sun Microsystems and designed to be portable enough to be executed on a wide range of computers ranging from small personal computers up to supercomputers. Computer programs written in Java (and other languages) may be compiled into virtual machine instructions for execution by a Java virtual machine. In general the Java virtual machine is an interpreter that decodes and executes the virtual machine instructions.
The virtual machine instructions for the Java virtual machine are bytecodes, meaning they include one or more bytes. The bytecodes are stored in a particular file format called a “class file.” In addition to the bytecodes, the class file includes a symbol table as well as other ancillary information.
A computer program embodied as Java bytecodes in one or more class files is platform independent. The computer program may be executed, unmodified, on any computer that is able to run an implementation of the Java virtual machine. The Java virtual machine is a software emulator of a “generic” computer which is a major factor in allowing computer programs for the Java virtual machine to be platform independent.
The Java virtual machine is commonly implemented as an software interpreter. Conventional interpreters decode and execute the virtual machine instructions of an interpreted program one instruction at a time during execution. Compilers, on the other hand, decode source code into native machine instructions prior to execution so that decoding is not performed during execution. Because conventional interpreters decode each instruction before it is executed repeatedly each time the instruction is encountered, execution of interpreted programs is typically quite slower than compiled programs because the native machine instructions of compiled programs can be executed on the native machine or computer system without necessitating decoding.
As a software interpreter must be executing in order to decode and execute an interpreted program, the software interpreter consumes resources (e.g., memory) that will therefore no longer be available to the interpreted program. This is in stark contrast to compiled programs that execute as native machine instructions so they may be directly executed on the target computer and are therefore generally free to utilize more resources than interpreted programs.
Accordingly, there is a need for new techniques for increasing the execution speed of computer programs that are being interpreted. Additionally, there is a need to provide interpreters that are efficient in terms of the resources they require.
SUMMARY OF THE INVENTION
In general, some embodiments of the present invention provide innovative systems and methods for increasing the execution speed of computer programs executed by an interpreter. The interpreter includes an operand stack that is utilized to execute the virtual machine instructions. The value for the top of the operand stack is stored in one or more registers which allows the execution speed of stack-based virtual machine instructions to be increased. A state of the interpreter is utilized to indicate the data type of the value for the top of the operand stack stored in the one or more registers. With the invention, the programs may be interpreted in a more efficient manner utilizing registers. Additionally, the size of the interpreter may kept small which allows more resources to be available for the interpreted program. Several embodiments of the invention are described below.
In one embodiment, a computer implemented method for implementing an interpreter including an operand stack is provided. A value for the top of the operand stack is stored in at least one register of the computer instead of on the stack. Many conventional computers have registers for storing different data types. Accordingly, the value for the top of the stack is stored in one or more registers appropriate for its data type and the state of the interpreter is utilized to indicate the data type of the value for the top of the operand stack that is stored in the one or more registers. In preferred embodiments, the interpreter is a Java virtual machine and the states of the interpreter may include integer, long integer, single-precision floating point, and double-precision floating point.
In another embodiment, a computer implemented method for generating an interpreter that stores a value for the top of an operand stack in one or more registers is provided. The state of the interpreter indicates a data type of the value for the top of the operand stack that is stored in the one or more registers. In order to generate the interpreter, the computer may loop through all the possible virtual instructions and states of the interpreter. In each iteration, a virtual machine instruction and a state of the interpreter may be selected. If the selected state differs from the state of the interpreter that is expected prior to the execution of the selected virtual machine instructions, computer code for the interpreter is generated to put the interpreter in the expected state. Once it is known that the interpreter is in the expected state prior to the execution of the selected virtual machine instruction, computer code for the interpreter is generated to execute the selected virtual machine instruction. The expected state for the selected virtual machine instruction may be obtained by accessing a table indexed by virtual machine instructions that stores expected states of the interpreter before execution of the virtual machine instructions and current states of the interpreter after execution of the virtual machine instructions. Additionally, the computer code for the interpreter to execute the selected virtual machine instruction may be generated by calling a function specified in the table.
In another embodiment, a data structure stored by a computer readable medium for an interpreter of virtual machine instructions is provided. The data structure is a table indexed by virtual machine instructions and having multiple fields. In one field of the table, expected states of the interpreter before execution of the virtual machine instructions are stored. In another field of the table is stored current states of the interpreter after execution of the virtual machine instructions. Additionally, a field of the table may be utilized to store pointers to functions that generate computer code for the interpreter to execute the virtual machine instructions. In a preferred embodiment, a state of the interpreter indicates the data type of a value for the top of an operand stack of the interpreter that is stored in one or more registers.
In another embodiment, a data structure stored by a computer readable medium for an interpreter of virtual machine instructions is provided. The data structure is a table indexed by virtual machine instructions and having multiple fields, each field being associated with a state of the interpreter and storing a pointer to a location in the interpreter that executes the indexed virtual machine instructions. The state of the interpreter may indicate the data type of a value for the top of an operand stack of the interpreter that is stored in one or more registers. In preferred embodiments, the state of the interpreter may be integer, long integer, single-precision floating point, and double-precision floating point.
Other features and advantages of the invention will become readily apparent upon review of the following detailed description in association with the accompanying drawings.
REFERENCES:
patent: 5678044 (1997-10-01), Pastilha et al.
patent: 5684996 (1997-11-01), Westerholm et al.
patent: 5758162 (1998-05-01), Takayama
patent: 5999731 (1999-12-01), Yellin et al.
patent: 0
Beyer Weaver&Thomas, LLP
Chavis John Q
Powell Mark R.
Sun Microsystems Inc.
LandOfFree
Interpreter generation and implementation utilizing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interpreter generation and implementation utilizing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interpreter generation and implementation utilizing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571185