Method and apparatus for caching native code in a virtual machine interpreter

Techniques for increasing the performance of virtual machines are disclosed. It can be determined whether a program instruction which is to be executed by the virtual machine is a branch instruction, and whether a basic block of code is present in a code cache. If so, the basic block of code can be executed. The basic block includes code that can be executed for the program instruction. A cache can be used to store the basic block for program instructions that are executed by the virtual machine. The program instruction may be a bytecode and the code cache can be implemented as a native code cache.

BACKGROUND OF THE INVENTION

1. Field of Invention

The present invention relates generally to computing systems which use virtual machines. More particularly, the present invention relates to a technique increasing overall virtual machine performance.

2. Description of the Related Art

The Java™ programming language is an object-based high level programming language developed by Sun Microsystems, Inc. of Palo Alto, Calif. The Java™ programming language is designed to be portable enough to be executed on a wide range of computers which include, but are not limited to, small personal computing device and supercomputers.

Programs written in the Java™ programming language, i.e., Java™ programs, are compiled into class files which include virtual machine instructions, e.g., bytecodes, for a Java™ virtual machine. In essence, a Java™ virtual machine is a software emulator of a “generic” computer. Virtual machine instructions may be run, unmodified, on substantially any computer system that has a virtual machine implementation. As such, virtual machines are both portable and flexible. In addition, other programming languages may be compiled into Java™ virtual machine instructions and executed by a Java™ virtual machine.

A Java™ virtual machine has an interpreter that is executed as an interpreter program, i.e., software. Conventional interpreters are arranged to decode and to execute the virtual machine instructions of an interpreted program one instruction at a time during execution. Compilers, which are also associated with a virtual machine, decode source code into native machine instructions prior to execution so that decoding it is not necessary to perform decoding during execution. Conventional interpreters decode each instruction each time the instruction is executed. In other words, conventional interpreters repeatedly decode each instruction each time the instruction is executed. As such, since an instruction is decoded by a conventional interpreter each time the instruction is encountered, execution of interpreted programs is typically substantially slower than execution of compiled programs since the execution of compile programs may occur on an associated native machine or computer system without necessitating decoding.

As the popularity of small computing devices, e.g., cellular telephones and personal digital assistants, which execute code written in the Java™ programming language increases, the demand for better performing Java™ virtual machines is also increasing. One conventional method for increasing the execution speed and, hence the performance, of Java™-based interpreted programs of virtual machine instructions involves utilizes a just-in-time (JIT) compiler to translate Java™ bytecodes into native code substantially “on-the-fly.” A JIT compiler compiles an entire Java™ function just before the Java™ function is called. However, native code generated by a JIT compiler does not always run faster than code executed by an interpreter. For example, if the interpreter is not spending the majority of its time decoding the Java™ virtual machine instructions, then compiling the instructions with a JIT compiler may not increase the execution speed. In some instances, execution of the virtual machine may even be compromised by utilizing the JIT compiler, e.g., if the overhead associated with compiling the instructions is more than the overhead associated with interpreting the instructions.

In general, at least parts of a JIT compiler are platform specific. As a result, if a virtual machine with a JIT compiler is to be ported to a different platform, at least the platform-specific parts of the JIT compiler, e.g., a code generator, must be rewritten to accommodate the new platform. Rewriting platform-specific parts of a JIT compiler may be a time-consuming task.

Further, a JIT compiler is often associated with a substantial amount of code. That is, JIT compilers often require a relatively significant portion of memory. Even a “simple” JIT compiler such as a JIT compiler which is substantially arranged only to generate code and not to perform extensive optimizations, requires more memory than is typically available in small devices. As will be appreciated by those skilled in the art, a standard JIT compiler may require memory to store an intermediate representation of compiled code, to store JIT compiler code and data, and to store native code corresponding to entire Java™ methods.

Therefore, what is desired is a technique for reliably increasing the performance of virtual machines. More particularly, what is needed is a method and an apparatus for increasing the performance of virtual machines in environments with limited memory resources.

SUMMARY OF THE INVENTION

The present invention relates to the efficient implementation of a virtual machine in a computing environment. According to one aspect of the present invention, a method for increasing the performance of a virtual machine includes obtaining a program instruction to be executed by the virtual machine, determining whether the program instruction is a branch instruction, and determining whether a basic block is present in a code cache if the program instruction is a branch instruction. The basic block includes code, and the code cache is associated with the virtual machine. Finally, the method includes executing the code included in the basic block when if the basic block is present. In one embodiment, the program instruction is a bytecode and the code cache is a native code cache.

In another embodiment, when the basic block is not present in the code cache, the method includes interpreting the program instruction and copying code corresponding to the program instruction into the code cache. In such an embodiment, the method may also include allocating space in the code cache for the code corresponding to the program instruction, in addition to providing the code corresponding to the program instruction with a label.

According to another aspect of the present invention, a computing system includes a virtual machine which has a code cache and an interpreter. The interpreter is arranged to obtaining a bytecode and to determine whether the bytecode is a branch bytecode. The interpreter is also arranged to determine whether a basic block is present in the code cache if the bytecode is a branch bytecode. The basic block includes native code, and the interpreter causes the native code to be executed when it is determined that the basic block is present. In one embodiment, the interpreter is further arranged to interpret the bytecode when it is determined that the bytecode is not a branch bytecode.

According to yet another aspect of the present invention, a computer-implemented method for increasing the performance of an interpreter includes identifying a portion of compiled code which corresponds to a block of source code, and copying the portion of compiled code directly into a code cache without first generating an intermediate representation. In one embodiment, the code cache is a native code cache, and the portion of compiled code is native code.

These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Although just-in-time (JIT) compilers are effective for translating bytecodes, e.g., bytecodes associated with the Java™ programming language developed by Sun Microsystems, Inc., of Palo Alto, Calif., JIT compilers generally require a substantial amount of memory, and may involve significant overhead. As small computing devices generally have a limited amount of memory, while users all small computing devices have an expectation of a relatively high level of performance, however, the use of JIT compilers is not always desirable.

By copying native code, e.g., native binary code, corresponding to a bytecode into a cache, and adding interpreter code which labels the code copied into the cache, the native code may be available on the cache for future use. As will be understood by those skilled in the art, code and data associated with most processor architectures is addressed independently. Hence, when a piece of code in a code segment is copied to a new location, the results of executing the piece of code from within the data segment and from the new location will be the same, provided that no branch instructions which have references outside the piece of code exist.

In one embodiment, interpreter code which copies native code corresponding to a just-executed bytecode into a native code cache may be added to an interpreted program. By copying native code into a native code cache, a substantially compiled version of a basic block is then available on the native code cache. Hence, porting is not needed, and the need to recompile native code for different platforms is avoided. Instead, substantially only an interpreter with JIT compilation technology would be recompiled for different platforms.

Generally, an interpreter may execute a bytecode program by repeatedly executing an execute step, an advance step, and a dispatch step. An execute step executes a current bytecode, an advance step advances a bytecode pointer to a subsequent bytecode, and a dispatch step fetches the bytecode identified by the bytecode pointer. The dispatch step also jumps to the piece of native machine code that implements the identified bytecode, e.g., the dispatch operation jumps to an execution step. As will be understood by those skilled in the art, the execution of the execute-advance-dispatch sequence for a bytecode is often referred to as an “interpretation cycle.”

With reference toFIGS. 1a–e, the execution of a source code statement X:=A+B after the source code statement is compiled into bytecodes will be described in accordance with an embodiment of the present invention. Instructions104associated with the source code statement X:=A+B may be executed by a virtual machine. As will be understood by those skilled in the art, a virtual machine may be implemented as a stack based machine that includes a stack110with frames114a–fwhich are indexed by a stack pointer118.

Once a first instruction106aof instructions104is interpreted by an interpreter120, a value of A is pushed onto stack110at a location114aidentified by stack pointer118which points to a “current” location within stack110, as shown inFIG. 1b. After interpreter120executes first instruction106a, interpreter120advances to a second instruction106b, and dispatches second instruction106b, as shown inFIG. 1c. Like first instruction106aofFIG. 1b, second instruction106bis a load or push instruction. Hence, the execution of second instruction106bplaces a value of B onto stack110at a location114gspecified by stack pointer118.

As shown inFIG. 1d, once interpreter120completes an interpretation cycle associated with second instruction106b, a third instruction106cmay be executed. In the described embodiment, third instruction106cis an add operation which adds values A and B, and pushes the result of adding values A and B onto location114aof stack110. It should be appreciated that once the sum of values A and B is determined, the result of the sum is stored on stack110such that values A and B are displaced from stack110. Finally, after interpreter120completes another interpretation cycle, a fourth instruction106dis executed, and the result stored in location114ais removed as shown inFIG. 1d. Once the result is removed from location114a, the result is effectively placed into location114cwhich is associated with variable X.

In essence, with respect toFIGS. 1a–e, after the values of A and B are loaded onto the stack using an interpreted program, the values of A and B may be added and removed from the stack with the result of the summation of A and B being placed on the stack. The result of the summation placed on the stack may then be stored in a location associated with variable X, and the result of the summation may be removed from the stack.

While running an interpreted program, blocks of code associated with instructions may be executed by effectively “jumping to” an appropriate block of code when the associated instruction is executed.FIG. 2ais a diagrammatic representation of instructions of an interpreted program which are associated with blocks of code in accordance with an embodiment of the present invention. An interpreted program202may include instructions206such as a load instruction206aand an add instruction206b. While executing interpreted program202, when an interpreter executes load instruction206a, interpreter effectively executes a block210of code that is associated with load instruction206a, i.e., block210a.

As shown, block210aincludes code written in the C programming language that executes a load operation. That is, block210acontains C code that is associated with interpreted load instruction206a. The code contained in block210amay be native C code. Just as code contained in block210amay be native C code associated with load instruction206a, code contained in block210bmay be native C code associated with add instruction206b. It should be understood that although blocks210have been described as including code written in the C programming language, the code associated with blocks210may instead by written in substantially any computing language which allows copying of blocks of code segments.

Native code generally includes native machine instructions which are machine instructions that are essentially designed for a specific microprocessor or computer architecture. As will be appreciated by those skilled in the art, a machine instruction is an instruction that directs a computer to perform an operation specified by an operation code and, in some cases, one or more operands.

FIG. 2bis a diagrammatic representation of a system which includes a native code cache in accordance with an embodiment of the present invention. As shown, a stream of bytecodes252corresponds to source code256for an interpreter. Although source code256may be written in substantially any computing language, in one embodiment, source code256may be written in the C computer language.

Source code256generally includes a switch operator which “executes” bytecodes252as long as there are bytecodes252to obtain. Source code256includes cases which correspond to actions performed on specific arguments associated with bytecodes252. The cases include case blocks260which correspond to specific bytecodes252. As shown, bytecode252acorresponds to case block260a, bytecode252bcorresponds to case block260b, and bytecode252ccorresponds to case block260c.

Conventionally, case blocks252would generally be compiled into compiled code or an intermediate representation, which would then be transformed into instructions, e.g., native code, which would be executed by a processor. In the described embodiment, however, compiled code, or an intermediate representation of source code256, is not generated. Instead, case blocks252may be copied substantially directly into a native code cache264. It should be understood by those skilled in the art that case blocks252generally include only indirect calls due to addressing issues.

To facilitate the copying of case blocks252substantially directly into native code cache264, labels may be implemented around case blocks252to delineate the beginning and end of a specific case block, e.g., case block252c. By way of example, a beginning label270and an ending label272may be inserted before case block252and at the end of case block252, respectively. Ending label272is placed before a break instruction which typically terminates each case. The use of labels270and272enables code which is to be copied into native code cache264to be denoted and, hence, readily identified.

In addition to having boundaries on case blocks252, or blocks of source code, such that case blocks252may be substantially exactly identified, case blocks252are arranged to be manipulated at a source code level. The ability to manipulate case blocks252at a source code level enables a target to be substantially platform independent.

As shown inFIG. 2c, when a stream280of bytecodes282is interpreted by an interpreter283which includes case blocks284, the case blocks284may be copied substantially directly, e.g., without the creation of an intermediate representation, into native code cache286. When a processor finishes executing a code segment, e.g., a segment including case blocks284a–c, in native code cache286, a jump back instruction288in native code cache286effectively returns control to interpreter283, which has no control while a processor executes code segments in native code cache286.

With reference toFIG. 3, the processing of a bytecode associated with a program will be described in accordance with an embodiment of the present invention. A process300begins when the “next” instruction or bytecode in a program is to be executed. In step302, a determination is made as to whether there is a bytecode to obtain. If there is no bytecode to obtain, then the process terminates. Alternatively, when it is determined that there is a bytecode to obtain, then process flow proceeds to step303in which the next bytecode to obtain is obtained.

After the bytecode is obtained, a determination is made in step304regarding whether the obtained bytecode, i.e., the next bytecode to be executed, is a branch bytecode. A branch bytecode, in one embodiment, may be a bytecode that has a corresponding section or block that is to be run, as described above with respect toFIG. 2. If it is determined in step304that the bytecode is not a branch bytecode, then the bytecode is a “regular” bytecode. Accordingly, in step308, the bytecode is interpreted. Once the bytecode is interpreted, then process flow returns to step302and the determination of whether there are more bytecodes to be obtained. Alternatively, if it is determined in step304that the bytecode is a branch bytecode, then the implication is that the bytecode has an associated block of code. As such, process flow proceeds to step312in which a target is computed. Computing a target involves interpreting bytecodes.

Once a target is computed in step312, a determination is made in step316as to whether a basic block which corresponds to the target is found in a native code cache. In one embodiment, such a determination may be made by searching through a “label” table which effectively lists labels associated with basic blocks which are present in the native cache. Specifically, the target may be compared against labels in the label table to determine if a corresponding basic block, e.g., case block260cofFIG. 2b, is present in the native code cache. If it is determined in step316that a basic block corresponding to the target is cached in the native code cache, the code associated with the basic block is executed in step320. After the code is executed, process flow returns to step302in which a determination is made as to whether there is another bytecode to obtain. Typically, the code associated with the basic block ends with a branch, or jump, instruction to return from the basic block to approximately the point in the program which resulted in the execution of the basic block. A basic block is generally a sequence of instructions which start and end at the same place. That is, a basic block is a section of code with no branching and no internal labels. Typically, a basic block ends with a branch instruction.

When it is determined in step316that a basic block corresponding to the target is not already in the native code cache, process flow moves from step316to step324in which a new basic block may be labeled. In the described embodiment, labeling the new basic block also includes indexing the label in the label table, as well as allocating space in the native code cache. Substantially any suitable method may be used to allocate space in the native code cache, as will be appreciated by those skilled in the art. Once space is allocated in the native code cache, then the bytecode is interpreted in step328. After the bytecode is interpreted, the native code corresponding to the bytecode is copied into the native code cache in step332. Specifically, the native code corresponding to the bytecode is copied into the native code cache in the space that was allocated in step324. Once the native code is copied, process flow returns to step302and the determination of whether there is another bytecode to obtain.

In one embodiment, code which allows the copying of the native code to be performed may be inserted within a program. Such code may effectively be code which determines where a block of native code is located, identifies where the block begins and ends, and copies the native code. The code which allows copying may be written in substantially any suitable programming language, as for example, the C programming language.

The copying of native code into a native code cache effectively removes the need for a compiler such as a JIT compiler. That is, no intermediate representation, e.g., no compiled representation, is needed to generate native code, and native code may be obtained substantially immediately. As such, the compilation overhead associated with a compiler such as a JIT compiler may be avoided.

As mentioned above with respect toFIG. 3, a label table is used in one embodiment to determine whether a particular basic block of native code is cached in a native cache.FIG. 4is a diagrammatic representation of an interpreted program, a label table, and a native cache in accordance with an embodiment of the present invention. When an instruction or a bytecode406a–bin a program402is to be executed, it is determined whether there is a basic block418a–bassociated with bytecode406. A label table410is used to effectively map bytecodes406to blocks418stored within native code cache414. If there in no entry in label table410for a particular bytecode406, and it is appropriate for the particular bytecode406to have an entry, then space may be allocated within native code cache414for a block418that corresponds to the particular bytecode406, and a label for the particular bytecode406may be created.

In order to facilitate identifying basic blocks to be put in a native code cache, labels or identifiers may be placed at the beginning of blocks. Specifically, a block of code pertaining to a load instruction may have a “beginning” label which identifies the beginning of the block of code, as well as an “ending” label which identifies the end of the block of code. By way of example, as shown inFIG. 5, a block of native code502may be identified by a beginning label504and an ending label506. Identifying where a block of native code begins and ends enables the block to be readily identified and copied into a native code cache.

As described above with respect toFIG. 3, a basic block may end with a branch or a jump instruction. Typically, a basic block may be entered subtantially only at a start point, and exited only at the branch instruction. In one embodiment, an extended basic block may be used in lieu of a basic block. Typically, an extended basic block is a sequence of instructions that may be entered at more than one start point, but includes only one exit point.

Table 1 below provides a code listing which implements the present invention. It should be understood that the code shown in Table 1 is an example of an embodiment of the present invention. In general, substantially any language which enables blocks of code to be copied may be used to implement the present invention.

FIG. 6illustrates a typical, general-purpose computer system suitable for implementing the present invention. The computer system1030includes at least one processor1032(also referred to as a central processing unit, or CPU) that is coupled to memory devices including primary storage devices1036(typically a read only memory, or ROM) and primary storage devices1034(typically a random access memory, or RAM).

Computer system1030or, more specifically, CPUs1032, may be arranged to support a virtual machine, as will be appreciated by those skilled in the art. One example of a virtual machine that may be supported on computer system1030will be described below with reference toFIG. 7. As is well known in the art, ROM acts to transfer data and instructions uni-directionally to the CPUs1032, while RAM is used typically to transfer data and instructions in a bi-directional manner. CPUs1032may generally include any number of processors. Both primary storage devices1034,1036may include any suitable computer-readable media. A secondary storage medium1038, which is typically a mass memory device, is also coupled bi-directionally to CPUs1032and provides additional data storage capacity. The mass memory device1038is a computer-readable medium that may be used to store programs including computer code, data, and the like. Typically, mass memory device1038is a storage medium such as a hard disk or a tape which generally slower than primary storage devices1034,1036. Mass memory storage device1038may take the form of a magnetic or paper tape reader or some other well-known device. It will be appreciated that the information retained within the mass memory device1038, may, in appropriate cases, be incorporated in standard fashion as part of RAM1036as virtual memory. A specific primary storage device1034such as a CD-ROM may also pass data uni-directionally to the CPUs1032.

CPUs1032are also coupled to one or more input/output devices1040that may include, but are not limited to, devices such as video monitors, track balls, mice, keyboards, microphones, touch-sensitive displays, transducer card readers, magnetic or paper tape readers, tablets, styluses, voice or handwriting recognizers, or other well-known input devices such as, of course, other computers. Finally, CPUs1032optionally may be coupled to a computer or telecommunications network, e.g., an internet network or an intranet network, using a network connection as shown generally at1012. With such a network connection, it is contemplated that the CPUs1032might receive information from the network, or might output information to the network in the course of performing the above-described method steps. Such information, which is often represented as a sequence of instructions to be executed using CPUs1032, may be received from and outputted to the network, for example, in the form of a computer data signal embodied in a carrier wave. The above-described devices and materials will be familiar to those of skill in the computer hardware and software arts.

As previously mentioned, a virtual machine may execute on computer system1030.FIG. 7is a diagrammatic representation of a virtual machine which is supported by computer system1030ofFIG. 6, and is suitable for implementing the present invention. When a computer program, e.g., a computer program written in the Jav programming language, is executed, source code1110is provided to a compiler1120within compile-time environment1105. Compiler1120translates source code1110into bytecodes1130. In general, source code1110is translated into bytecodes1130at the time source code1110is created by a software developer.

Bytecodes1130may generally be reproduced, downloaded, or otherwise distributed through a network, e.g., network1012ofFIG. 6, or stored on a storage device such as primary storage1034ofFIG. 6. In the described embodiment, bytecodes1130are platform independent. That is, bytecodes1130may be executed on substantially any computer system that is running on a suitable virtual machine1140.

Bytecodes1130are provided to a runtime environment1135which includes virtual machine1140. Runtime environment1135may generally be executed using a processor or processors such as CPUs1032ofFIG. 6. Virtual machine1140includes a compiler1142, an interpreter1144, and a runtime system1146. Bytecodes1130may be provided either to compiler1142or interpreter1144.

When bytecodes1130are provided to compiler1142, methods contained in bytecodes1130are compiled into machine instructions. In one embodiment, compiler1142is a just-in-time compiler which delays the compilation of methods contained in bytecodes1130until the methods are about to be executed. When bytecodes1130are provided to interpreter1144, bytecodes1130are read into interpreter1144one bytecode at a time. Interpreter1144then performs the operation defined by each bytecode as each bytecode is read into interpreter1144. That is, interpreter1144“interprets” bytecodes1130, as will be appreciated by those skilled in the art. In general, interpreter1144processes bytecodes1130and performs operations associated with bytecodes1130substantially continuously.

When a method is invoked by another method, or is invoked from runtime environment1135, if the method is interpreted, runtime system1146may obtain the method from runtime environment1135in the form of a sequence of bytecodes1130, which may be directly executed by interpreter1144. If, on the other hand, the method which is invoked is a compiled method which has not been compiled, runtime system1146also obtains the method from runtime environment1135in the form of a sequence of bytecodes1130, then may go on to activate compiler1142. Compiler1142then generates machine instructions from bytecodes1130, and the resulting machine-language instructions may be executed directly by CPUs1032. In general, the machine-language instructions are discarded when virtual machine1140terminates. The operation of virtual machines or, more particularly, Java virtual machines, is described in more detail inThe Java™ Virtual Machine Specificationby Tim Lindholm and Frank Yellin (ISBN 0-201-63452-X), which is incorporated herein by reference.

Although only a few embodiments of the present invention have been described, it should be understood that the present invention may be embodied in many other specific forms without departing from the spirit or the scope of the present invention. By way of example, although the present invention has generally been described in terms of a Java virtual machine, it should be appreciated that the present invention may generally be applied to any suitable virtual machine. Examples of suitable virtual machines include, but are not limited to, a Smalltalk virtual machine.

The basic blocks of the present invention, as well as the blocks of code associated with instructions such as load or push instructions, may generally include instructions written in the C programming language. However, it should be understood that blocks of code such as basic blocks may generally be associated with instructions written in substantially any suitable programming language.

The steps associated with executing a bytecode or an instruction may be varied. Steps may be added, removed, altered, and re-ordered. For example, the process of executing a bytecode may be such that when a jump is made to a native code cache in order to execute a block of native code, it may be possible for a jump not to be made back from the block of native code until after a next instruction is obtained.

It should be understood that the copying of native code into a native code cache without the need to generate an intermediate representation of the code is generally applicable to any interpreter which is coded to have distinguishable blocks of source code that is responsible for interpretation of different input instructions. A suitable interpreter would generally also be coded such that there are effectively no jumps from within one block into another. As described above, such an interpreter may be coded to include a switch instruction which uses case blocks, as described above with respect toFIG. 2b. Alternatively, such an interpreter may be implemented with a series of “if” and “else if” statements without departing from the spirit or the scope of the present invention. Therefore, the present examples are to be considered as illustrative and not restrictive, and the invention is not to be limited to the details given herein, but may be modified within the scope of the appended claims.