Method and apparatus for partial just in time compiling in a data processing system

[0002] 1. Technical Field

[0003] The present invention relates generally to an improved data processing system and in particular to a method and apparatus for processing instructions in a data processing system. Still more particularly, the present invention relates to a method and apparatus for partially Just In Time compiling instructions in a data processing system.

[0004] 2. Description of Related Art

[0005] Java is an object oriented programming language and environment focusing on defining data as objects and the methods that may be applied to those objects. “Java” is a trademark of Sun Microsystems, Inc. Java supports only a single inheritance, meaning that each class can inherit from only one other class at any given time. Java also allows for the creation of totally abstract classes known as interfaces, which allow the defining of methods that may be shared with several classes without regard for how other classes are handling the methods. Java provides a mechanism to distribute software to different computing platforms.

[0006] Java is able to support applications for many types of data processing systems, which may contain a variety of central processing units and operating system architectures. The Java Virtual Machine (JVM) is a virtual computer component that resides only in memory. The JVM allows Java programs to be executed on different platforms as opposed to only the one platform for which the code was compiled. Java programs are compiled for the JVM. In this manner Java is able to support applications for many types of data processing systems, which may contain a variety of central processing units and operating systems architectures. To enable a Java application to execute on different types of data processing systems, a compiler typically generates an architecture-neutral file format. The compiled code is executable on many processors, given the presence of the Java runtime system. The Java compiler generates bytecode instructions that are nonspecific to particular computer architectures. A bytecode is a machine independent code generated by the Java compiler and executed by a Java interpreter. A Java interpreter is a module in the JVM that alternatively decodes and executes a bytecode or bytecodes. These bytecode instructions are designed to be easy to interpret on any machine and easily translated on the fly into native machine code.

[0007] A development environment, such as the Java Development Kit (JDK) available from Sun Microsystems, Inc., may be used to build Java bytecode from Java language source code and libraries. This Java bytecode may be stored as a Java application or applet on a Web Server, where it can be downloaded over a network to a user's machine and executed on a local JVM.

[0008] When extra speed in executing a Java program is needed, a Just In Time (JIT) compiler may be used to translate bytecodes for a method or class into native machine instructions before executing them. Typically, this compilation only occurs once per method. Some JIT compilers may compile entire classes, rather than one method at a time.

[0009] Just In Time compilation of Java methods may provide significant performance boosts to Java programs. This benefit, however, comes at the cost of increased storage utilization and significant compile time.

[0010] Therefore, it would be advantageous to have an improved method and apparatus for Just In Time compiling, also referred to as JITing, of Java methods that would reduce the storage use and compile time.

[0011] The present invention provides a method and apparatus for just in time compilation of Java bytecode methods and provides a means to compile only the paths that are actually executed. An iterative process is employed whereby bytecodes are compiled up to the next conditional flow bytecode or return, the compiled code is executed and any attempt to enter uncompiled paths of the method is monitored. When an attempt is made to execute an uncompiled path control is returned to the compiler and the process is repeated starting with the first bytecode of that path. The process continues until all paths have been compiled or until it is deemed likely that all of the most commonly executed paths have been compiled. At that point, final optimizations and housekeeping are performed.

[0012] The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0013] FIG. 1 is a block diagram illustrating a data processing system in which the present invention may be implemented;

[0014] FIG. 2 is a block diagram of a Java virtual machine depicted in accordance with a preferred embodiment of the present invention;

[0015] FIG. 3 is a process for Just In Time compiling a selected method depicted in accordance with a preferred embodiment of the present invention;

[0016] FIG. 4 is a flowchart of a process for range selection depicted in accordance with a preferred embodiment of the present invention;

[0017] FIG. 5 is a flowchart of the process used by a taken branch monitor depicted in accordance with a preferred embodiment of the present invention;

[0018] FIG. 6 is a flowchart of the process for a fall through branch monitor depicted in accordance with a preferred embodiment of the present invention; and

[0019] FIG. 7 is a flowchart of a return monitor depicted in accordance with a preferred embodiment of the present invention.

[0020] With reference now to FIG. 1, a block diagram illustrates a data processing system in which the present invention may be implemented. Data processing system 100 is an example of a client computer. Data processing system 100 employs a peripheral component interconnect (PCI) local bus architecture. Although the depicted example employs a PCI bus, other bus architectures such as Micro Channel and ISA may be used. Processor 102 and main memory 104 are connected to PCI local bus 106 through PCI bridge 108. PCI bridge 108 also may include an integrated memory controller and cache memory for processor 102. Additional connections to PCI local bus 106 may be made through direct component interconnection or through add-in boards. In the depicted example, local area network (LAN) adapter 110, SCSI host bus adapter 112, and expansion bus interface 114 are connected to PCI local bus 106 by direct component connection. In contrast, audio adapter 116, graphics adapter 118, and audio/video adapter 119 are connected to PCI local bus 106 by add-in boards inserted into expansion slots. Expansion bus interface 114 provides a connection for a keyboard and mouse adapter 120, modem 122, and additional memory 124. SCSI host bus adapter 112 provides a connection for hard disk drive 126, tape drive 128, and CD-ROM drive 130. Typical PCI local bus implementations will support three or four PCI expansion slots or add-in connectors.

[0021] An operating system runs on processor 102 and is used to coordinate and provide control of various components within data processing system 100 in FIG. 1. The operating system may be a commercially available operating system such as OS/2, which is available from International Business Machines Corporation. “OS/2” is a trademark of International Business Machines Corporation. An object oriented programming system such as Java may run in conjunction with the operating system and provides calls to the operating system from Java programs or applications executing on data processing system 100. “Java” is a trademark of Sun Microsystems, Inc. Instructions for the operating system, the object-oriented operating system, and applications or programs are located on storage devices, such as hard disk drive 126, and may be loaded into main memory 104 for execution by processor 102.

[0022] Those of ordinary skill in the art will appreciate that the hardware in FIG. 1 may vary depending on the implementation. Other internal hardware or peripheral devices, such as flash ROM (or equivalent nonvolatile memory) or optical disk drives and the like, may be used in addition to or in place of the hardware depicted in FIG. 1. Also, the processes of the present invention may be applied to a multiprocessor data processing system.

[0023] For example, data processing system 100, if optionally configured as a network computer, may not include SCSI host bus adapter 112, hard disk drive 126, tape drive 128, and CD-ROM 130, as noted by dotted line 132 in FIG. 1 denoting optional inclusion. In that case, the computer, to be properly called a client computer, must include some type of network communication interface, such as LAN adapter 110, modem 122, or the like. As another example, data processing system 100 may be a stand-alone system configured to be bootable without relying on some type of network communication interface, whether or not data processing system 100 comprises some type of network communication interface. As a further example, data processing system 100 may be a Personal Digital Assistant (PDA) device which is configured with ROM and/or flash ROM in order to provide nonvolatile memory for storing operating system files and/or user-generated data.

[0024] The depicted example in FIG. 1 and above-described examples are not meant to imply architectural limitations.

[0025] The present invention provides a method, apparatus, and instructions used to reduce storage utilization and reduce compile time for Java methods. The present invention also may be applied to other types of interpretive languages. The mechanism of the present invention involves Just In Time compiling, also referred to as “JITing”, only those paths of a method that are actually executed.

[0026] With reference now to FIG. 2, a block diagram of a Java virtual machine is depicted in accordance with a preferred embodiment of the present invention. Java virtual machine (JVM) 200 includes a class loader subsystem 202, which is a mechanism for loading types, such as classes and interfaces, given fully qualified names. JVM 200 also includes run time data areas 204, execution engine 206, and native method interface 208.

[0027] Execution engine 206 is a mechanism for executing instructions containing any method of classes loaded by class loader subsystem 202. In the depicted example, execution engine 206 includes a Just In Time compiler 210 and an interpreter 212. Bytecodes make up a method and are a sequence of instructions for JVM 200. Each instruction consists of a 1-byte opcode followed by zero or more fixed operands. The opcode indicates the operation to be performed. Variable operands and data appear on the Java operand stack 217 which appears within the Java stack 216. Interpreter 212 will cause the execution of the necessary code or instructions in response to this bytecode.

[0028] Compiler 210 is a Just In Time compiler in which the bytecodes of a method are normally compiled to native machine code the first time the method is invoked after it has been selected as a candidate for compilation. Selection may be based on a method's former CPU consumption, number of invokes or some other criteria or it is possible that all methods may be selected for compilation without regard to criteria. The native machine code for the method is then cached or stored in a buffer, so the code can be reused the next time the same method is invoked. In the depicted examples, the mechanism of the present invention allows for partial just in time compiling or JITing of the method.

[0029] Native method interface 208 is used as an interface to allow a Java program to interact with the host by invoking native methods. Native methods are typically stored in a dynamic link library. An example of a particular native method interface is a Java native interface (JNI). In essence, native method interface 208 allows access to resources in the underlying operating system.

[0030] Run time data areas 204 includes native method stacks 214, Java stacks 216, PC registers 218, method area 220, heap 222, and JIT station 224. Run time data areas 204 also contains method block 226. These different data areas represent the organization of memory needed by JVM 200 to execute a program. Native method stacks 214 stores the state of invocations of native methods. Java stacks 216 are used to store the state of Java method invocations while PC registers 218 are used to indicate the next instruction to be executed. Method area 220 contains class data while heap 222 contains all instantiated objects. JIT station 224 is used to store all information needed for compilation of the method such as flow control information, register assignments, virtual operand stack content. The JIT station may be located as a single contiguous area of memory or may be multiple noncontiguous areas of memory and may be dynamically allocated or reusable.

[0031] Method block 226 contains the compiler lock 227 which is used to serialize compilation of the method. This lock must be held whenever compilation is performed for a method including initialization and finalization. This maintains the integrity of JIT station data and ensures that the same path is not compiled by multiple threads. However, the lock is not held while the compiled code is being executed, even when the method is only partially compiled. This provides for improved performance by obviating the need to acquire/release the lock during method invocation. It also allows multiple threads to concurrently run the compiled code.

[0032] When a method is selected as a candidate for compilation, the invoker field 228 of method block 226 is set to point to the JIT initialization code. In this way, control is passed to the JIT when the method is next invoked. Upon receiving control, the JIT attempts to acquire the compiler lock for the method. If the lock is unavailable (indicating another thread is compiling the method), control is passed to the interpreter to execute the method. Otherwise, following housekeeping and any initial passes, the compilation process commences with the first bytecode of the method. The bytecodes are compiled up to and including the first/next conditional flow bytecode (if/switch) or return. The depicted example actually identifies the bytecodes to be compiled and then compiles the bytecodes. Of course, the bytecodes could be compiled as they are encountered, depending on the implementation.

[0033] While most bytecodes can be compiled in an implementation dependent manner, flow control bytecodes must be handled specially as they may cause flow to pass to what is yet uncompiled code. Branch monitors must be used to insure control is returned to the compiler when an attempt is made to enter an uncompiled path. Branch monitors may be implemented using hardware or software breakpoints with appropriate interrupt handlers or more practically using branch instructions coupled with information logged in the JIT station. For example on an X86 platform the following code could serve as branch and fallthru monitors for the Java bytecode ifeq:

[0034] 800 test eax, eax

[0035] 801 jeq taken_monitor_handler1

[0036] 802 jmp falltru_monitor_handler1

[0037] 803 unused

[0038] Here eax is assumed to hold the top of stack value upon entry to the code segment. The code at taken_monitor_handler1 would merely push a 1 onto the stack to indicate which monitor had been hit and pass control to the common taken monitor handler. Similar code would be found at fallthru_monitor_handler1. The JIT station would contain a branch monitor table where entry 1 would represent these branch monitors and contain such information as the fallthru and target bytecode addresses, indication of which monitors are active and the address of the native code that comprises the branch monitor.

[0039] When the code is executed, control is passed to either the fallthru or the taken branch monitor handler. For the fallthru case, the corresponding branch monitor entry would be updated to indicate the fallthru monitor is no longer active, location 802 would become the new target address for depositing native code and the fallthru bytecode would become the current bytecode. The first instruction(s) of the newly compiled path would then overlay the jmp instruction at location 802. If the taken case were the first hit, the fallthru branch monitor would be converted to a taken branch monitor by moving the fallthru bytecode address of the entry to the taken address, the entry would be updated to indicate that the fallthru monitor is no longer active, location 802 would become the new target address for depositing native code, the target bytecode would become current and the jeq at 801 would be converted to:

[0040] 801 jne taken_monitor_handler1

[0041] Again, the first instruction(s) of the newly compiled path would then overlay the jmp instruction at location 802. Note that whichever path is taken first is treated as the fallthru path and the resulting code is emitted immediately following the conditional branch thereby improving I cache efficiency. If the branch at 801 is subsequently taken, an unused location in the compile buffer would be allocated and become the target of the branch. Compilation would continue using the fallthru address as the current bytecode and the compiled code would be deposited at the newly allocated buffer address.

[0042] Another bytecode that requires special treatment is goto. The Java compiler most commonly uses gotos to implement if else constructions and to enter for loops. While it is possible to “fold out” gotos by rearranging the code, the resultant code may be less efficient for certain native architectures. Specifically, an extra branch instruction may be required at the end of a for loop. In accordance with a preferred embodiment of the present invention, when a bytecode range is selected for compilation it never includes gotos that target uncompiled code outside the selected range. This is accomplished by extending the selected range to ensure all such targets are included and could result in the selection of the entire method. From a practical standpoint, this allows loops to be compiled in an efficient manner and rarely causes the inclusion of code that is not part of the current path.

[0043] The final class of bytecodes requiring special treatment are the returns. If a return is encountered and the method has one or more untaken branches, a return monitor is inserted into the native code. The return monitor provides for finalization (see below) of a method after it has been invoked sufficiently often to determine that any untaked branches are not likely to initiate commonly executed paths. The return monitor decrements a counter and performs a normal return if the counter is non-zero. When the counter goes to zero the method is finalized. The counter may be initialized at compilation startup and may be a fixed constant or may be a function of the number of conditional flow control instructions. Alternatively, the counter could be incremented by some value each time a branch monitor is added. The idea is to allow the method sufficient invocations to give all paths a fair chance to be executed because once the method is finalized all uncompiled paths will be interpreted.

[0044] Methods are finalized when the compilation process is deemed complete. The resources comprising the JIT station are released and final optimizations are performed. The native code may be relocated from a temporary buffer in the JIT station to the final JIT buffer. Any untaken branches are converted to interpreter invocations for the uncompiled paths. Because the finalization process releases significant resources and typically improves the performance of native code, it is desirable to finalize methods as early as possible. However, premature finalization could leave significant paths uncompiled. Therefore, it is a goal of the current invention to provide a means to finalize a method as soon as the commonly executed paths are likely to have been compiled. Of course if all the paths of a method have been compiled, the method will be finalized immediately.

[0045] A time stamp may be used to force asynchronous finalization of methods that cease running or that infrequently or never exit. The time stamp can be set when a method is initialized for compilation or each time a path has been compiled and the method is about to be executed. Asynchronous finalization can be performed periodically or in response to requests for compiler resources. According to the preferred embodiment of this invention, all methods with expired time stamps will be finalized whenever a new JIT station is allocated.

[0046] With reference now to FIG. 3, a process for Just In Time compiling a selected method is depicted in accordance with a preferred embodiment of the present invention. The process begins by attempting to lock the method that is to be JITed (step 300). In accordance with a preferred embodiment of the present invention, the method is locked when the initial compilation occurs. The lock then is released prior to executing the code. The method also is locked prior to resuming compilation via a branch monitor.

[0047] Thereafter, a determination is made as to whether the method has been locked (step 302). If the method has not been locked, the process then runs the interpreted code using an interpreter (step 304) with the process terminating thereafter.

[0048] With reference again to (step 302), if the method has been locked, then methods with expired time stamps are finalized (step 306). Next, a JIT station is created or selected for use in processing the method (step 308). A JIT station in this example is a storage partition that is used to store all of the needed information for compiling the method.

[0049] Thereafter, initial passes through the method may be made (step 310). These passes are implementation dependent and may involve identification of basic blocks, flow determination, initial register assignment, variable use analysis, etc. While these passes typically would not generate native code, they could produce intermediate code and if so it would be this intermediate code and not the bytecode that is used in the subsequent steps. Such a conversion is compiler dependent and may not occur. The process then performs a range selection process (step 314) with the process then terminating.

[0050] With reference now to FIG. 4, a flowchart of a process for range selection is depicted in accordance with a preferred embodiment of the present invention. The process illustrated in FIG. 4 is a more detailed description of step 314 in FIG. 3. Range selection takes part of the method and compiles that portion of the method and allows it to execute. The compilation of the bytecode into native code is performed until a conditional branch is encountered.

[0051] The process begins by examining the current bytecode in the method (step 400). When compilation begins the current bytecode is the 1st bytecode of the method. When entering via a branch monitor, the current bytecode is the 1st bytecode of the path selected by the conditional flow. A determination is made as to whether the bytecode being examined is a conditional branch or a return bytecode (step 402). If the bytecode is neither, then a determination is made as to whether the bytecode is a goto bytecode (step 404). If the bytecode is not a goto bytecode, the process returns to step 400 to examine the next bytecode.

[0052] Otherwise, a determination is made as to whether the target of the goto bytecode is within the scope (step 406). The scope is the range of bytecodes that have been compiled previously or have been selected in the current range. If the target is not within the scope, then a goto target record (GTR) is created (step 408) with the process then returning to step 400. If the target is within the scope, the process proceeds to step 410 as described below.

[0053] Returning to step 402, if the bytecode is a conditional flow or return, a determination is made as to whether any GTRs are out of scope for the method (step 410). If any GTRs are out of scope, the process returns to step 400 to examine the next bytecode. This step allows for additional identification of bytecodes to be within the scope in an attempt to include the target as part of the scope. It is possible to include the entire method during this process.

[0054] If none of the GTRs are out of scope, then the range of bytecodes selected is compiled (step 414). Branch monitors also are created and resolved (step 416). The branch monitors are in native code and are used in the process of the present invention to initiated additional JITing of the method when they are encountered during execution of the native code for the method. Branch monitors are described in more detail in the description of FIGS. 5 and 6 below. More than one conditional flow bytecode may be present for resolution because of goto bytecodes and making sure that the targets of the goto bytecodes are within the scope of bytecodes to be JITed. It is also possible that the targets of conditional branches have previously been compiled or are part of the current range. In this case, normal branch instructions are generated and branch monitors are not created. Additionally, the new range may include target(s) of previously created branch monitors. In this case the branch monitors are converted to normal branches. The return count is incremented by 5 for each newly created branch monitor.

[0055] A determination is then made as to whether any branch monitors are present (step 418). If branch monitors are not present, then the process has finished the compiling of bytecodes for the method, and the method is finalized (step 420). Thereafter, the method is unlocked (step 422), the time stamp is set to the current time plus 20 seconds (step 423) and the compiled code is run (step 424) with the process terminating thereafter.

[0056] With reference again to (step 418), if branch monitors are still present, then return monitors are created in the appropriate places (step 426) with the process then proceeding to step 422 as described above. Return monitors are native code and cause additional processes to be executed before the return to the calling method actually occurs. Return monitors are described in more detail in the description of FIG. 7 below.

[0057] With reference now to FIG. 5, a flowchart of the process used by a taken branch monitor is depicted in accordance with a preferred embodiment of the present invention.

[0058] The process begins by locking the method (step 500). A determination is then made as to whether the attempt to lock method was successful (step 502). If the attempt was successful, a determination is made as to whether a fall through branch monitor is present (step 504). This determination is made to see whether the fall through case has occurred. If a fall through monitor is not present, then the fall through case has occurred and the branch instruction is pointed to the next available buffer slot (step 506). This step is used to provide for a linear management of the buffer or memory in which the native code is placed when produced from JITing of the method. The determination in step 504 is made to identify whether a case is present in which either branch has been taken. When a branch is taken, it is necessary to place the code in a place somewhere in memory. The compiler does not know which path will be taken, but the process knows that if the branch case is taken that is best to place the just compiled code right afterwards rather than placing it in a noncontiguous spot in memory. This provides for I cache efficiency.

[0059] Thereafter, the taken branch monitor is removed (step 508) and the process then sets the current bytecode to the 1st bytecode of the taken path (step 509). Finally, control is passed to the perform range selection process (step 510) with the process terminating thereafter. The range selection process step in step 510 is described in more detail in FIG. 4.

[0060] With reference again to step 504, if a fall through monitor is present, then the fall through monitor is converted to a taken monitor (step 512). The step removing the taken branch monitor is that of the monitor encountered and initiating the process in FIG. 5 instead of the monitor converted in step 512.

[0061] Thereafter, the condition of the branch is reversed (step 514) and the process proceeds to step 508 as described above.

[0062] With reference again to step 502, if the attempt to lock the method was unsuccessful, then the interpreted code is run (step 516) with the process then terminating for the taken branch monitor.

[0063] With reference now to FIG. 6, a flowchart of the process for a fall through branch monitor is depicted in accordance with a preferred embodiment of the present invention. The process in FIG. 6 is triggered when a fall through branch monitor is encountered during execution of the compiled code. The fall through branch monitor is written in native instructions specific to the data processing system on which the instructions are executing. The process begins by attempting to lock the method (step 600). Thereafter, a determination is made as to whether the method has been locked (step 602). If the method has been locked, the fall through monitor is removed (step 604). The next bytecode is set to the fall through target (step 606) with the process then proceeding to the range selection process in FIG. 4 (step 608) with the process terminating thereafter.

[0064] With reference again to step 602, if the attempt to lock the method has been unsuccessful, then the interpreted code is run (step 608) with the process terminating thereafter.

[0065] With reference now to FIG. 7, a flowchart of a return monitor is depicted in accordance with a preferred embodiment of the present invention. The process begins by decrementing the return count (step 700). Thereafter, a determination is made as to whether the return count is equal to zero (step 702). If the return count is equal to zero an attempt is made to obtain a lock for the method (step 704). A determination is then made as to whether the method has been locked (step 706). If the method has been locked, the method is then finalized (step 708). Thereafter, the process returns to the calling method (step 710) with the process terminating thereafter.

[0066] With reference again to step 706, if the attempt to lock the method was unsuccessful, the process proceeds to step 710 as described above. Further, if the return count is not equal to zero in step 702, the process also proceeds to step 710.

[0067] For methods with exception tables, it may be desirable to JIT entire try and catch blocks to avoid exception table explosion.

[0068] It is important to note that while the present invention has been described in the context of a fully functioning data processing system, those of ordinary skill in the art will appreciate that the processes of the present invention are capable of being distributed in the form of a computer readable medium of instructions and a variety of forms and that the present invention applies equally regardless of the particular type of signal bearing media actually used to carry out the distribution. Examples of computer readable media include recordable-type media such a floppy disc, a hard disk drive, a RAM, and CD-ROMs and transmission-type media such as digital and analog communications links.

[0069] The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. For example, although the depicted embodiment is directed towards processing bytecodes in Java, the processes of the present invention may be applied to other programming languages and environments that process instructions, which are nonspecific to a computer on which the instructions are to be executed. In such a case, a virtual machine on the computer may interpret the instructions or send the instructions to a compiler to generate code suitable for execution by the computer in which the virtual machine is located. The embodiment was chosen and described in order to best explain the principles of the invention, the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.