Patent Publication Number: US-7725879-B2

Title: Method and apparatus for executing instructions of java virtual machine and transforming bytecode

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application claims priority from Korean Patent Application No. 10-2005-0033235 filed on Apr. 21, 2005 in the Korean Intellectual Property Office, the disclosure of which is incorporated herein by reference in its entirety. 
   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   Methods and apparatuses consistent with the present invention relate to executing an instruction of a Java virtual machine, and more particularly, to executing an instruction of a Java virtual machine in which bytecode executed in a Java virtual machine is transformed into a second code using 16-bit memory elements, thereby considerably improving the speed of executing instructions. 
   2. Description of the Related Art 
   Although Java programming language has rapidly proliferated as a standard object-oriented programming language since its advent in the mid-1990s, it has several disadvantages, including a lower execution speed than the C programming language or the C++ programming language. In order to speed up the execution of the Java programming language, a dynamic code generation system, such as a Java virtual machine adopting a just-in-time (JIT) compiler, and a static code generation system, such as a Java virtual machine adopting an ahead-of-time (AOT) compiler, have been developed. 
   A Java platform consists of a Java virtual machine and a plurality of classes. Each class consists of information corresponding to a data structure of the class, field information, and method information. Execution code of a method is written in bytecodes independent of a hardware device or an operating system. 
   Conventional Java virtual machines can be classified into interpreter-type Java virtual machines, JIT compiler-type Java virtual machines, interpreter-and-JIT compiler-type Java virtual machines, and AOT compiler-type Java virtual machines according to the types of their respective execution engines. 
   An interpreter-type Java virtual machine interprets a plurality of bytecodes of a method to be executed one by one, and executes an application program of the method. 
   A JIT compiler-type Java virtual machine compiles the bytecodes of the method to obtain machine codes dependent upon a Java platform, and executes the machine codes to execute the application program of the method. 
     FIG. 1  is a diagram illustrating a structure of a conventional Java class file. 
   Referring to  FIG. 1 , the Java class file includes a class or interface definition and is comprised of various attributes, field information, method information and so on that are defined in the class. The method information defines a byte stream, which is called a bytecode and can be executed in the interpreter. This bytecode can be obtained from compiling a file (e.g., a file having an extension of “java”) containing a Java source language statement. 
   The bytecode is similar to a program module ready for execution because the bytecode is executed within a computer one byte at a time. However, the instructions of the bytecode are actual instructions transmitted to the logical and abstract Java virtual machine. The bytecode can be compiled again by the JIT compiler so that the bytecode can be compatible with a particular system platform. This also ensures that the byte code is interpreted by one byte only once, thereby accelerating the execution speed of the Java program. 
     FIG. 2  illustrates a bytecode to be executed in a conventional Java virtual machine. 
   Referring to  FIG. 2 , the instructions of the bytecode are composed of an operand and an opcode, both of which have a size of one byte to discriminate performed operations. One opcode may include several operands. Both the opcode and each operand are stored in the unit of one byte, so that they are represented as consecutive bytes in order to represent the operands having a size of one or more bytes. For example, a 16-bit value consists of two consecutive bytes, and a 32-bit value consists of four consecutive bytes. 
   In  FIG. 2 , the first line denotes the hexadecimal values of the actual bytecode, and the second line denotes the bytecode divided into opcodes and operands. 
     FIG. 3  is a flowchart for explaining a method of executing each instruction code performed by a conventional Java interpreter. 
   An application class is loaded by a class loader of a Java virtual machine and goes through a linking process and an initialization process, and then associated information is stored in a data structure within a runtime system, and the method is executed by the execution engine such as an interpreter or a JIT compiler. 
   In a typical interpreter, the bytecode is executed in the manner shown in  FIG. 3 . When a method is invoked in the interpreter, a program counter indicating the bytecode of the method is incremented (S 310 ). Next, it is determined whether the bytecode of the method is the last bytecode (S 320 ). If it is determined that the bytecode of the method is not the last bytecode (NO in operation S 320 ), a one-byte opcode is fetched (S 330 ). Subsequently, the control goes to a handler corresponding to the fetched one-byte opcode using a switch statement in the program (S 340 ), so that the handler is executed (S 350 ). This process is repeated as many times as necessary depending on the size of the bytecode, and then the interpreting process for the method is terminated. 
   The process shown in  FIG. 5  can be represented with a pseudo-code as follows: 
   
     
       
         
             
             
           
             
                 
                 
             
           
          
             
                 
               Loop { 
             
             
                 
                 Op = *pc++; 
             
             
                 
                 switch (Op) { 
             
             
                 
                   case op_1: 
             
             
                 
                     // op_1&#39;s implementation 
             
             
                 
                     break; 
             
             
                 
                   case op_2: 
             
             
                 
                     // op_2&#39;s implementation 
             
             
                 
                     break; 
             
             
                 
                   case op_3: 
             
             
                 
                     // op_3&#39;s implementation 
             
             
                 
                     break; 
             
             
                 
                   ... 
             
             
                 
                    } 
             
             
                 
                 
             
          
         
       
     
   
   In the handler for the respective opcodes, if the data size of the operand required by the opcode is larger than one byte, the values of the operand are stored in consecutive bytes. Thus, the consecutive bytes are reconstructed into one significant value through an OR operator and a Shift operator according to each bit. For example, in a central processing unit (CPU) using the “little-endian” format, if operands required by a certain opcode A are in subsequent bytes byte 1 , byte 2 , byte 3  and byte 4 , then byte 4  represents the first bit to the eighth bit of a 32-bit value to be logically indicated, byte 3  represents the ninth bit to the sixteenth bit of the 32-bit value to be logically indicated, byte 2  represents the seventeenth bit to the twenty-fourth bit of the 32-bit value to be logically indicated, and byte 1  represents the twenty-fifth bit to the thirty-second bit of the 32-bit value to be logically indicated. 
   Therefore, the 32-bit value actually required by the opcode A can be obtained by an operation like “(byte 1 &lt;&lt;24)|(byte 2 &lt;&lt;16)|(byte 3 &lt;&lt;8)|byte 4 ”. In the existing Java virtual machine, processes for combining such operands occur whenever the method is executed. 
   For the operand, when the data size of the operand is greater than one byte, the operand will be arranged in consecutive bytes, and the consecutive bytes will be reconstructed through the OR operator and the Shift operator according to each bit whenever the method is executed. This process may function as considerable overhead when the Java program is executed. Therefore, there is a need to improve the performance of the Java virtual machine by overcoming these restraints. 
   SUMMARY OF THE INVENTION 
   The present invention provides a method and apparatus for executing an instruction of a Java virtual machine in which the speed of executing Java programs can be enhanced by performing a precomputation operation for transforming bytecode into a second code using 16-bit memory elements before interpretation of the bytecode. 
   The present invention also provides a method and apparatus for executing an instruction of a Java virtual machine in which bytecode is transformed into a second code using 16-bit memory elements, thus considerably reducing overhead compared to the transformation of bytecode into code requiring a large memory capacity. 
   According to an aspect of the present invention, there is provided a method of executing an instruction of a Java virtual machine, the method including extracting bytecode of a method of a Java class; transforming the bytecode into a second code which comprises information regarding a location of an opcode handler and uses 16-bit memory elements, the opcode handler performing an operation corresponding to an opcode included in the bytecode; and executing the second code. 
   According to another aspect of the present invention, there is provided a Java virtual machine including a bytecode extraction unit which extracts a bytecode of a method of a Java class, a second code transformation unit which transforms the bytecode into a second code which comprises information regarding a location of an opcode handler and uses 16-bit memory elements, the opcode handler performing an operation corresponding to an opcode included in the bytecode, and an instruction execution unit which executes the second code. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The above and other aspects of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which: 
       FIG. 1  is a diagram illustrating a structure of a conventional Java class file; 
       FIG. 2  illustrates a bytecode to be executed in a conventional Java virtual machine. 
       FIG. 3  is a flowchart illustrating a method of executing each instruction code performed by a conventional Java interpreter; 
       FIG. 4  is a block diagram of a Java virtual machine according to an exemplary embodiment of the present invention; 
       FIG. 5  is a flowchart illustrating a method of executing an instruction by the Java virtual machine shown in  FIG. 4 ; 
       FIG. 6  is a flowchart illustrating an operation of transforming a bytecode into second code shown in  FIG. 5 ; 
       FIG. 7  is a diagram illustrating a method of transforming a bytecode into a second code according to an exemplary embodiment of the present invention; 
       FIG. 8  is a diagram illustrating a method of transforming a bytecode into a second code according to another exemplary embodiment of the present invention; 
       FIG. 9  is a diagram illustrating a method of transforming a bytecode into a second code according to another exemplary embodiment of the present invention; and 
       FIG. 10  is a diagram illustrating the format of an opcode handler offset-opcode table according to an exemplary embodiment of the present invention. 
   

   DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS OF THE INVENTION 
   Advantages and features of the present invention and methods of accomplishing the same may be understood more readily by reference to the following detailed description of exemplary embodiments and the accompanying drawings. The present invention may, however, be embodied in many different forms and should not be construed as being limited to the exemplary embodiments set forth herein. Rather, these exemplary embodiments are provided so that this disclosure will be thorough and complete and will fully convey the concept of the invention to those skilled in the art, and the present invention will only be defined by the appended claims. Like reference numerals refer to like elements throughout the specification. 
   The present invention will now be described more fully with reference to the accompanying drawings, in which exemplary embodiments of the invention are shown. 
     FIG. 4  is a block diagram of a Java virtual machine  400  according to an exemplary embodiment of the present invention. 
   Referring to  FIG. 4 , the Java virtual machine  400  according to an exemplary embodiment of the present invention includes a bytecode extraction unit  420 , a second code transformation unit  430 , a linking unit  440 , an initialization unit  450 , and an instruction execution unit  460 . 
   The bytecode extraction unit  420  extracts bytecode of a method from a class  410  loaded into the Java virtual machine  400  and provides the bytecode to the second code transformation unit  430 . 
   The second code transformation unit  430  transforms a bytecode, which is written in units of eight bits, into a second code using 16-bit memory elements. The transforming of the bytecode into the second code may include transforming opcode of the bytecode into a 16-bit opcode handler offset; and, if the opcode includes an operand, transforming the 16-bit opcode handler offset into a 16-bit or 32-bit index or memory address by appropriately combining bits of the operand. The transforming of the bytecode into the second code will later be described in further detail with reference to  FIGS. 6 through 10 . 
   The linking unit  440  performs a linking operation, including verification of the transformed second code, preparation and resolution, and combines the result of the linking operation into a runtime state of the Java virtual machine  400 . 
   The initialization unit  450  initializes the linked second code by executing a static initializer and an initializer for a static field declared in the class  410 . An interpreter-type Java virtual machine interprets a plurality of bytecodes of a method to be executed one by one, and executes an application program of the method. 
   The instruction execution unit  460  interprets and executes the result of the initialization operation. In one exemplary embodiment of the present invention, the instruction execution unit  460  may be an interpreter. In an alternative exemplary embodiment of the present invention, the instruction execution unit  460  may be a compiler. A JIT compiler-type Java virtual machine compiles the bytecodes of the method to obtain machine codes dependent upon a Java platform, and executes the machine codes to execute the application program of the method. 
   The term “module”, as used in  FIG. 4 , means, but is not limited to, a software or hardware component, such as a Field Programmable Gate Array (FPGA) or Application Specific Integrated Circuit (ASIC), which performs certain tasks. A module may advantageously be configured to reside on the addressable storage medium and configured to execute on one or more processors. The functionality provided for in the components and modules may be combined into fewer components and modules or further separated into additional components and modules. In addition, the components and modules may be implemented such that they execute one or more computers in a communication system. 
     FIG. 5  is a flowchart illustrating a method of executing an instruction by the Java virtual machine shown in  FIG. 4 . 
   Referring to  FIGS. 4 and 5 , when the class  410  is loaded into the Java virtual machine  400  by a class loader, the bytecode extraction unit  420  extracts bytecode for executing a method from the class  410  in operation S 510 . In operation S 520 , the second code transformation unit  430  transforms the extracted bytecode into a second code using 16-bit memory elements. In operation S 530 , the linking unit  440  performs a linking operation on the second code and combines the result of the linking operation into a runtime state of the Java virtual machine  400 . Here, the linking operation includes verification, preparation and resolution. In operation S 540 , the initialization unit  450  initializes the linked second code by executing a static initializer and an initializer for a static field declared in the class  410 . In operation S 550 , the instruction execution unit  460  translates or compiles the initialized second code into a machine language and then executes the machine language. 
   The transforming of the byte-code into the second code (operation S 520  of  FIG. 5 ) will now be described in more detail with reference to  FIG. 6 . 
   As described above with reference to  FIG. 2 , the bytecode is composed of an operand and an opcode. The bytecode is transformed into the second code in the following manner. 
   In operation S 610 , a one-byte (eight-bit) opcode is replaced with a 16-bit offset of an associated opcode handler. A memory address of the opcode handler performing the associated opcode function can be obtained by adding an offset value with a predetermined base address. Therefore, if the second code is executed by an interpreter or a compiler, the memory address of the handler can be obtained directly from the opcode handler offset, so that the routine goes to a handler corresponding to the one-byte opcode without a necessity of executing a switch statement in the interpreter loop shown in  FIG. 3 , thereby shortening the execution time of the Java program. 
   Next it is determined whether an opcode includes an operand in operation S 620 . If the opcode includes an operand (YES in operation S 620 ), a one-byte operand is transformed into a 16-bit operand. For example, a one-byte operand is transformed into a signed or unsigned word and then is packed with 16-bits in the second code. A two-byte operand in a bytecode is transformed into a signed or unsigned word and is then packed with two consecutive 16 bits in the second code. A four-byte operand in a bytecode is transformed into a signed or unsigned word and then is packed in the second code as an operand consisting of four consecutive 16 bits. 
   Next, it is determined whether the operand is an index in operation S 630 . When the one-byte operand is transformed into the 16-bit operand, the operand may be either an index or an offset value. In the former case (YES in operation S 630 ), the index is transformed to be compatible with 16-bit memory elements in operation S 640 . In the present invention, 16-bit memory elements are used, and thus, an index value of second code is generated by bit-shifting the index to the left by two bits. An example of the transforming of bytecode having an index as an operand will be described later in further detail with reference to  FIG. 7 . 
   In the latter case (NO in operation S 630 ), the offset value is added to a predetermined base address to be transformed into a 32-bit memory address in operation S 650 . An example of the transforming of bytecode having an offset value as an operand will be described later in further detail with reference to  FIGS. 8 and 9 . 
   The process of the second code being translated and executed can be represented with a Pseudo-code as follows: 
   
     
       
         
             
             
           
             
                 
                 
             
           
          
             
                 
               nop_label: 
             
             
                 
                ++pc; goto *(nop_label+pc[0]); 
             
             
                 
               aconst_null_label: 
             
             
                 
                *sp=0; 
             
             
                 
                ++sp; 
             
             
                 
                ++pc; goto *(nop_label+pc[0]); 
             
             
                 
               ... 
             
             
                 
               // other opcode handlers 
             
             
                 
                 
             
          
         
       
     
   
   The linking process in the Java virtual machine operation (operation S 530  of  FIG. 5 ) is a process of combining the second code into a runtime state of the Java virtual machine using a binary-type class or an interface-type class. In the present exemplary embodiment, the linking process has been described as being performed before the execution of the bytecode or in the middle of the execution of the bytecode. 
   In the present exemplary embodiment, the transforming of the bytecode into the second code is carried out before the verification of the second code. Thus, the verification of the second code is carried out in consideration of the layout of second code instructions and transforming and pre-computations of instruction operands. A handler offset-opcode lookup table may be used in the verification of the second code to determine what opcode is verified. The format of the handler offset-opcode lookup table will later be described in detail with reference to  FIG. 10 . 
     FIG. 7  is a diagram illustrating a method of transforming a bytecode into second code according to an exemplary embodiment of the present invention; 
   Referring to  FIG. 7 , a bytecode instruction, for example, “aload” or “astore”, which comprises an eight-bit opcode  710  and an eight-bit operand, i.e., a local variable index  720 , is transformed into second code consisting of a 16-bit opcode handler offset  730  and a 16-bit operand  740 . If a target processor provides only byte-addressing mode, the 16-bit operand  740  may have a local variable index which is bit-shifted to the left by two bits. 
     FIG. 8  is a diagram illustrating a method of transforming a bytecode into second code according to another exemplary embodiment of the present invention. 
   Referring to  FIG. 8 , a bytecode instruction, for example, ‘goto’ or ‘if’, which comprises an eight-bit opcode  810  and a two-byte operand consisting of first and second branch offsets  820  and  830 , is transformed into second code consisting of three 16-bit elements. The three 16-bit elements include a 16-bit opcode handler offset  840  and a 32-bit branch address  850 , which is to be used in the execution of the bytecode instruction. 
   A bytecode instruction, for example, “getfield_quick” or “putfield_quick”, which may comprise a eight-bit opcode and a two-byte operand consisting of two field offsets, may also be transformed into a second code consisting of three 16-bit elements. The three 16-bit elements may include an opcode handler offset and a 32-bit field offset consisting of two 16-bit elements. If a target processor provides only byte-addressing mode, 16-bit elements for an operand may include a 32-bit field offset which is bit-shifted to the left by two bits. 
   A wide operation instruction, for example, “goto_w” or “jsr_w”, comprises an eight-bit opcode and a four-byte operand. The transforming of a bytecode into a second code does not distinguish a normal operation from a wide operation. Therefore, the eight-bit opcode of the wide operation instruction is replaced with a handler offset for a normal operation instruction (e.g., “goto”), and two consecutive 16-bit elements are used to generate a 32-bit operand for the four-byte operand. 
   While the illustrative embodiment has shown that an operand of a second code is a 32-bit address, it will be obvious to those skilled in the art that offsets of the corresponding bytecode may be combined to be transformed into a 32-bit offset value without substantially departing from the principles of the present invention. 
     FIG. 9  is a diagram illustrating a method of transforming a bytecode into second code according to another exemplary embodiment of the present invention. 
   Referring to  FIG. 9 , a bytecode instruction “tableswitch”, which is comprised of N bytes, may be transformed into a second code instruction which begins with a 16-bit opcode handler offset  910 . The 16-bit opcode handler offset  910  is followed by a selective pad  930  for 32-bit array. A lower limit address  960 , labeled LOWER LIMIT ADDRESS  1  and LOWER LIMIT ADDRESS  2 , is generated by adding a lower limit byte  950 , labeled LOWER LIMIT BYTE  1  through LOWER LIMIT BYTE  4 , to a default byte  940 , labeled DEFAULT BYTE  1  through DEFAULT BYTE  4 , and an upper limit address  980 , labeled UPPER LIMIT ADDRESS  1  and UPPER LIMIT ADDRESS  2 , is generated by adding an upper limit byte  970 , labeled UPPER LIMIT BYTE  1  through UPPER LIMIT BYTE  4 , to the default byte  940 . Every four consecutive branch offsets  990 , labeled BRANCH OFFSET  1 _ 1  through BRANCH OFFSET N_ 4 , of the bytecode instruction ‘tableswitch’ are transformed into 32-bit branch addresses  995 , labeled BRANCH ADDRESS  1 _ 1  through BRANCH ADDRESS N_ 2 . 
   While the illustrative embodiment has shown that an operand of a second code is a 32-bit address, it will be obvious to those skilled in the art that offsets of the corresponding bytecode may be combined to be transformed into a 32-bit offset value without substantially departing from the principles of the present invention. 
     FIG. 10  is a diagram illustrating the format of an opcode handler offset-opcode table according to an exemplary embodiment of the present invention. 
   Referring to  FIG. 10 , a Java virtual machine uses opcodes sometimes for a predetermined instruction. In this case, a handler offset-opcode lookup table illustrated in  FIG. 10  can be used to conveniently look up an opcode corresponding to a predetermined offset. The handler offset-opcode lookup table presents a plurality of opcode handler offsets and respective corresponding opcodes as indexes and array elements, respectively. 
   In order to compute a stack map for a second code, a Java virtual machine scans a second code instruction. During the scanning operation, the handler offset-opcode lookup table can be used. 
   As described above, according to the present invention, it is possible to enhance the speed of executing a Java program while considerably reducing the overhead associated with an increase in the memory capacity compared to the transformation of a bytecode into a code requiring a large memory capacity. 
   While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the following claims. Therefore, it is to be understood that the above-described exemplary embodiments have been provided only in a descriptive sense and will not be construed as placing any limitation on the scope of the invention.