High speed virtual machine and compiler

Abstract

A Just-In-Time compiler is provided for use with a virtual machine that executes a virtual machine instruction sequence under the control of a real machine. The compiler converts parts of the virtual machine instruction sequence into the real machine instruction sequence before execution and includes a block start information unit that determines whether the encoded block start information indicates a corresponding virtual machine instruction would correspond to the start of a basic block if the virtual machine instruction sequence was divided into basic blocks. A converting unit converts the virtual machine instructions into real machine instruction sequences and an outputting unit rearranges the real machine instruction sequences from the converting unit into basic blocks in accordance with the block start information. Additionally, the compiler can be enabled by a program stored on a computer readable recording medium.

Claims

What is claimed is:

1. A Just-In-Time (JIT) compiler for use with a virtual machine that executes a virtual machine instruction sequence under control of a real machine, the JIT compiler converting parts of the virtual machine instruction sequence into real machine instruction sequences before execution, and

the JIT compiler comprising:

block start information receiving means for receiving an input of block start information for each virtual machine instruction that composes the virtual machine instruction sequence, the block start information showing whether a corresponding virtual machine instruction would correspond to a start of a basic block if the virtual machine instruction sequence were divided into basic blocks;

converting means for converting virtual machine instructions in the virtual machine instruction sequence into real machine instruction sequences; and

outputting means for rearranging the real machine instruction sequences produced by the converting means into basic block units in accordance with the block start information received by the block start information receiving means.

2. The JIT compiler of claim 1, further comprising branch violation judging means for judging, when a real machine instruction at a start of a produced real machine instruction sequence corresponds to a virtual machine instruction whose block start information indicates that the virtual machine instruction would be a start of a basic block, whether the real machine instruction is going to be arranged in an address that violates an address alignment restriction of the real machine,

wherein if the real machine instruction is going to be arranged in an address that violates the address alignment restriction, the outputting means rearranges the real machine instruction sequence so that the real machine instruction is not arranged in the address.

3. The JIT compiler of claim 2, wherein the outputting means rearranges the real machine instruction sequence by inserting a necessary number of no-operation instructions at the start of the basic block to which the real machine instruction belongs.

4. The JIT compiler of claim 1, wherein the outputting means inserts a certain number of no-operation instructions at a start of each basic block, the number being a number of real machine instructions processed during a delay of a delayed branch.

5. A computer-readable recording medium that stores a program to have a computer function as a compiler that generates a program for a virtual machine with a stack architecture,

wherein the compiler comprises:

instruction sequence converting means for converting a source program into a virtual machine instruction sequence executable by the virtual machine;

succeeding instruction information generating means for generating sets of succeeding instruction information corresponding to virtual machine instructions in the virtual machine instruction sequence, each set of succeeding instruction information indicating a change in a storage state of data in the stack due to execution of a virtual machine instruction executed after a virtual machine instruction corresponding to the set of succeeding instruction information; and

associating means for associating each set of generated succeeding instruction information with a corresponding virtual machine instruction and outputting the set of succeeding instruction information and the virtual machine instruction.

6. A computer-readable recording medium that stores a program to have a computer function as a Just-In-Time (JIT) compiler used with a virtual machine that executes a virtual machine instruction sequence under control of a real machine, the JIT compiler converting parts of the virtual machine instruction sequence into real machine instruction sequences before execution,

wherein the compiler comprises:

block start information receiving means for receiving an input of block start information for each virtual machine instruction that composes the virtual machine instruction sequence, the block start information showing whether a corresponding virtual machine instruction would correspond to a start of a basic block if the virtual machine instruction sequence were divided into basic blocks;

converting means for converting virtual machine instructions in the virtual machine instruction sequence into real machine instruction sequences; and

outputting means for rearranging the real machine instruction sequences produced by the converting means into basic block units in accordance with the block start information received by the block start information receiving means.

7. A Just-In-Time (JIT) compiler for use with a virtual machine that executes a virtual machine instruction sequence under control of a real machine, the JIT compiler converting parts of the virtual machine instruction sequence into real machine instruction sequences before execution, and

the JIT compiler comprising:

block start information receiving unit for receiving an input of block start information for each virtual machine instruction that composes the virtual machine instruction sequence, the block start information showing whether a corresponding virtual machine instruction would correspond to a start of a basic block if the virtual machine instruction sequence were divided into basic blocks;

converting unit for converting virtual machine instructions in the virtual machine instruction sequence into real machine instruction sequences; and

outputting unit for rearranging the real machine instruction sequences produced by the converting means into basic block units in accordance with the block start information received by the block start information receiving unit.

8. The JIT compiler of claim 7, further comprising branch violation judging unit for judging, when a real machine instruction at a start of a produced real machine instruction sequence corresponds to a virtual machine instruction whose block start information indicates that the virtual machine instruction would be a start of a basic block, whether the real machine instruction is going to be arranged in an address that violates an address alignment restriction of the real machine,

wherein if the real machine instruction is going to be arranged in an address that violates the address alignment restriction, the outputting unit rearranges the real machine instruction sequence so that the real machine instruction is not arranged in the address.

9. The JIT compiler of claim 8, wherein the outputting unit rearranges the real machine instruction sequence by inserting a necessary number of no-operation instructions at the start of the basic block to which the real machine instruction belongs.

10. The JIT compiler of claim 7, wherein the outputting unit inserts a certain number of no-operation instructions at a start of each basic block, the number being a number of real machine instructions processed during a delay of a delayed branch.

Description

BACKGROUND OF THE INVENTION

(1) Field of the Invention

The present invention relates to virtual machines and to virtual machine compilers. In particular, the invention relates to a technique for increasing the execution speed of virtual machines.

(2) Description of the Prior Art

Standard Virtual Machine

Virtual machines are used to have a same program executed by computers, such as personal computers and workstations, that include different types of CPU. Virtual machines are useful in the field of communications, especially on a network to which different types of computers are connected, since they can overcome the differences in CPU architecture between computers and so allow the efficient and high-speed use of shared resources. Note that in this specification, CPUs are called "real machines".

A virtual machine is a virtual processor, which is to say, a processor achieved by executing software. A virtual machine decodes and executes executable programs (hereinafter referred to as "virtual machine programs" or "virtual machine instruction sequences") that are sequences of instructions (hereinafter, "virtual machine instructions") specific to the virtual machine. Virtual machines are normally realized by programs (hereinafter, "real machine programs" or "real machine instruction sequences" composed of instructions (hereinafter, "real machine instructions") specific to a target real machine on which the virtual program is to be run. Maintaining a high execution speed is a central issue for virtual machines, so that many virtual machines have a stack architecture.

One example of conventional virtual machines are the JAVA (trademark) virtual machines developed by SUN MICROSYSTEMS, INC.

FIG. 1 is a block diagram showing a construction of a conventional virtual machine 4400 with a stack architecture, such as a JAVA virtual machine. The virtual machine 4400 comprises the instruction storing unit 4401, the decoding unit 4402, the executing unit 4410, and the stack 4420. The instruction storing unit 4401 stores a virtual machine program to be executed. The decoding unit 4402 reads and decodes a virtual machine instruction. The execution unit 4410 executes operations according to the decoded data produced by the decoding unit 4402. The stack 4420, which is a LIFO (last-in first-out) memory area, temporarily stores data used in the processing of the execution unit 4410. In FIG. 1, solid lines show the data flows, while dotted lines show the control flows.

The decoding unit 4402 includes the decode table 4406, the program counter (PC) 4404, the instruction reading unit 4403, and the search unit 4405. The decode table 4406 stores data, such as jump addresses of microprograms (stored in the executing unit 4410) that correspond to all of the virtual machine instructions that can be executed by the virtual machine 4400 with a stack architecture. The program counter (PC) 4404 holds the address of the next instruction to be read from the instruction storing unit 4401. The instruction reading unit 4403 reads this next instruction. The search unit 4405 refers to the decode table 4406 to find a jump address corresponding to the read instruction and outputs the jump address to the execution unit 4410. In this specification, a microprogram is a real machine program that corresponds to a virtual machine instruction.

The executing unit 4410 includes a microprogram storing unit 4411 and a stack pointer (SP) 4412. The microprogram storing unit 4411 stores microprograms, which are real machine programs corresponding to virtual machine instructions, in advance at locations indicated by jump addresses. The stack pointer (SP) 4412 indicates the address at the top of the stack 4420.

FIG. 2 is a table for describing the instruction set of the virtual machine 4400. In FIG. 2, all of the virtual machine instructions that the virtual machine 4400 can decode and execute are shown in mnemonic form, along with the operation content of each instruction, changes in the content of the stack 4420 caused by each instruction, and the value of the SP 4412 after execution. In FIG. 2, the legend "s0" indicates the value at the top of the stack 4420, while "s1" indicates the second highest value. As one example, the notation "sp.rarw.s0+s1" for the virtual machine instruction "Add" denotes that the value at the top of the stack is set equal to a sum of the top and second highest values of the stack before execution. The notation "sp.rarw.sp-1" denotes that the height of the stack decreases by one due to the execution of the "Add" instruction.

FIG. 3 shows the stored contents of the decode table 4406 shown in FIG. 1. This decode table 4406 includes opcodes 4406a that indicate the operation types of virtual machine instructions, jump addresses 4406b which are the addresses of microprograms in the microprogram storing unit 4411 that correspond to these virtual machine instructions, and numbers of operands 4406c that show the number of operands in each virtual machine instruction. Here, each opcode is set as 1-byte long, and operands are counted in one-byte units. Virtual machine instructions, which may include only an opcode or only an operand, that are represented by a physical bit pattern are hereinafter referred to as "virtual machine code".

FIGS. 4A-4D show examples of the microprograms stored in the microprogram storing unit 4411 in FIG. 1. The microprograms in FIGS. 4A-4C respectively correspond to the virtual machine instructions "Push", "Add", and "Mult", while the microprogram in FIG. 4D shows a microprogram that forms the common latter part of each of the microprograms in FIGS. 4A-4C. This microprogram in FIG. 4D is a real machine program for jumping to the next virtual machine instruction. The operation contents of the real machine instructions in these microprograms are shown in FIG. 5. The virtual machine 4400 itself is realized by a real machine that can decode and execute the real machine instructions shown in FIG. 5. Note that the PC 4404 is physically realized by register #2 (r2) of the real machine, and the SP 4423 by register #3 (r3).

FIG. 6 is a flowchart showing the processing of decoding unit 4404 shown in FIG. 1. The instruction reading unit 4403 is instructed by the execution unit 4410 via a signal line R to read the next instruction (steps 4502-4503) and so reads the virtual machine instruction with the address stored in the PC 4404 from the instruction storage unit 4401 (steps 4504-4505). Following this, search unit 4405 refers to the decode table 4406 to find a jump address and operands corresponding to the read virtual machine instruction, outputs the jump address and operands (if any) to the executing unit 4410 as decoded data (step 4506), and gives the executing unit 4410 a "read end" notification via the signal line R (step 4507). This "read end" notification marks the completion of decoding for one virtual machine instruction.

FIG. 7 is a flowchart showing the processing in step 4506 in detail. The search unit 4405 compares 1-byte of virtual machine code (the opcode) read by reading 4403 with one opcode 4406a in decode table 4406 at a time until a match is found (steps 4802-4807). The search unit 4405 then reads the jump address 4406b and the number of operands 4406c corresponding to the matching opcode 4406a from the decode table 4406. The search unit 4405 outputs the read jump address 4406b to the executing unit 4410 (step 4808), has the instruction reading unit 4403 read as many operands as are indicated by the number of operands 4406c from the instruction storing unit 4401, and outputs the operands to execution unit 4410 (steps 4809-4813).

The flowcharts of FIGS. 6 and 7 show the processing when decoded data sent from the decoding unit 4402 is directly transferred to the executing unit 4410. The flowchart in FIG. 8 shows the case when the decoded data is transferred to the executing unit 4410 via a buffer that is capable of storing sets of decoded data. In this latter case, the reading of virtual machine instructions from the instruction storing unit 4401 and the subsequent decoding may be performed independently of the execution by the executing unit 4410 and repeated as long as there is space in the buffer (steps 4605-4613).

FIG. 9 shows the processing of executing unit 4410 in FIG. 1. The executing unit 4410 initializes SP 4412 and PC 4404 (step 4702) and repeats the processing described below for each virtual machine instruction (steps 4703-4707). That is, the executing unit 4410 instructs the instruction reading unit 4403 via the signal line R to read the next virtual machine instruction (step 4703). The executing unit 4410 then reads decoded data transmitted from the search unit 4405, jumps to a jump address that is included in the decoded data and that specifies a microprogram stored in the microprogram storing unit 4411, the microprogram corresponding to the read virtual machine instruction, and executes the microprogram until the executing unit 4410 receives a "read end" notification via the signal line R (steps 4704-4707).

FIG. 10A shows a sample program for describing a specific example of the processing of the virtual machine 4400. In this example, instruction storing unit 4401 stores a virtual machine program for calculating the arithmetic expression "2*(3+4)" shown in FIG. 10B.

FIG. 10C shows the decoded data that is sequentially outputted from the decoding unit 4402 when the virtual machine program shown in FIG. 10A is decoded and executed by the conventional virtual machine 4400. The decoding unit 4402 successively outputs jump addresses and the necessary operands corresponding to the decoded virtual machine instructions as decoded data to the executing unit 4410.

FIGS. 11A and 11B show the states of the PC 4404, the SP 4412, and the stack 4420 before and after the execution of the each virtual machine instruction when the executing unit 4410 executes the virtual machine program shown in FIG. 10A in accordance with the decoded data sequences shown in FIG. 10C. These figures show the processing of the virtual machine program split into a former and a latter part. Here, PC 4404 indicates the address of the next virtual machine instruction to be executed in the virtual machine program. The addresses of virtual machine instructions are the numbers shown to the left of the virtual machine instructions in FIG. 10A. The initial value of the PC 4404 is "1". The SP 4412 indicates the top of stack 4420, and so marks a position at which an item was most recently stored or read. The initial value of SP 4412 is "-1" and indicates that the stack 4420 is empty. As can be understood from FIGS. 11A and 11B, the calculation of the arithmetic expression "2*(3+4)" is completed when PC 4404 indicates "9".

The major problem for conventional virtual machines like virtual machine 4400 is how to increase execution speed. Processes such as the decoding of virtual machine instructions generate overheads, so that virtual machines end up operating at a much slower speed than when an equivalent real machine program is directly executed by a real machine. To improve the performance speed of virtual machines, the following methods have been proposed.

First Conventional Technique

In this first conventional technique, the storage area at the top of the stack (TOS) is assigned not to memory but to a specified register of a real machine. Hereinafter, such a storage area is called the TOS variable (See pp315-327 "PLDI" (1995), ACM).

FIGS. 12A-12D are microprograms corresponding to the principal virtual machine instructions that are stored in a microprogram storage unit of a virtual machine based on this first conventional technique. These figures correspond to FIGS. 4A-4D that were used to describe the virtual machine 4400. This example uses the following physical mapping. The TOS variable is assigned to register #0 (r0) of the real machine and, as in FIGS. 4A-4D, PC 4404 to register #2 (r2), and SP 4421 to register #3 (r3).

FIGS. 13A and 13B show the changes in the states of the PC 4404, the SP 4412, the TOS variable 4421, and the memory stack 4422 (the part of the stack 4420 that is allocated to memory) as a virtual machine provided with the microprograms shown in FIGS. 12A.about.12D executes the virtual machine program shown in FIG. 10A. These figures shows the processing split into a former and a latter part and correspond to the FIGS. 11A and 11B that were used to describe the operation of the virtual machine 4400. As before, the calculation of the arithmetic expression "2*(3+4)" is completed in FIGS. 13A and 13B when the PC 4404 indicates "9".

As can be seen by comparing FIGS. 12A.about.12D with FIGS. 4A.about.4D, the first conventional technique makes fewer accesses to the memory. When the virtual machine 4400 executes a virtual machine instruction such as an addition "Add" or a multiplication "Mult", two reads and one write are performed for the stack 4420, making a total of three memory accesses for one virtual machine instruction. With the first conventional technique, the assigning of the TOS variable to a register enables the same instruction to be executed with only one access to the memory stack 4422. This results in the execution speed being increased in proportion to the reduction in the number of memory accesses.

Second Conventional Technique

A second conventional technique uses a "native coding" method, in which a predetermined part of a virtual machine programs is written in real machine instructions and is directly executed by a real machine. As a result, identifiers are used to indicate that such predetermined part is written using real machine instructions.

As one example, a JAVA virtual machine can store the constant name "ACC_NATIVE" (256) into an access flag (such as the 16-bit flag "access_flags" that forms part of the "method_info" structure) of a class file that includes a virtual machine program to show that part of the program is written in real machine instructions (see the Java Bytecodes and the JAVA Virtual Machine Specification, 1995 editions, produced by SUN MICROSYSTEMS, INC.).

In this way, this second conventional technique improves execution speed by having the real machine directly execute a predetermined part of a program.

Third Conventional Technique

A third conventional technique uses a "just-in-time" (JIT) compiler that compiles parts of a virtual machine program as required during execution. Here, compiling refers to the replacement of virtual machine instructions with real machine instructions (see Laura Lemay et al., Java Gengo Nyumon (An Introduction to JAVA), Prentice Hall, 1996, and Laura Lemay and Charles L. Perkins, Teach yourself JAVA in 21 days). Virtual machines that use a JIT compiler have the real machine directly execute compiled parts of a virtual machine program, and so increase the overall execution speed of virtual machine programs.

Fourth Conventional Technique

A fourth conventional technique is used when computers on a network execute virtual machine programs that they download from a server computer. In this technique, the code in a virtual machine program is compressed beforehand using LZ (Lempel-Zif) methods or Huffman coding to reduce the time taken by file transfer (see Japanese Laid-Open Patent Application H07-121352 or H08-263263).

With this technique, an increase in execution speed can be obtained if the time taken to transfer the virtual machine program forms a large part of the overall processing time required to execute the virtual machine program.

The first to fourth conventional techniques described above have the following problems.

Problems with the First Conventional Technique

The first conventional technique, where the TOS variable is allocated to a register of a real machine, has a drawback in that it is not suited to real machines with superscalar architecture that have become increasingly inexpensive in recent years. This means that the improvements in the execution speed for a superscalar real machine (hereinafter, "superscalar machine") are relatively small when compared with the improvement for a standard real machine (hereinafter called a "standard machine") that is incapable of parallel processing. This is described in more detail below.

The following describes the standard operation and notation of a pipeline used by a register machine, such as a superscalar machine or a standard machine, with reference to FIGS. 14-22.

FIG. 14 shows the mnemonics used to indicate each stage included in the pipeline. The superscalar machine and a standard machine described below are assumed to each have a pipeline containing the five stages shown in this figure.

FIG. 15 shows the ideal pipeline flow for a standard machine. In this example, four real machine instructions are sequentially processed with each pipeline stage taking exactly one clock cycle. Each pipeline stage is performed in parallel for a different real machine instruction so that as the long-term average, one instruction is executed in one clock cycle.

FIG. 16 shows an ideal pipeline flow for a superscalar machine. This superscalar machine has two separate pipelines. In FIG. 16, two real machine instructions are executed in one clock cycle as the long-term average, giving the superscalar machine a throughput twice that of the standard machine.

FIG. 17 shows a pipeline flow for a standard machine when pipeline hazards occur. Here, instruction B uses the execution result of instruction A, which is to say, instruction B has a true dependency (also called a data dependency) on the preceding instruction A. Since the execution result of instruction A cannot be obtained until the memory access stage MEM is completed, the execution of instruction B is delayed, which causes the hazard as shown by "-" in the figure.

When the processing of an instruction is delayed in a real machine with a pipeline structure, the processing of the following instructions is also delayed. This is shown in FIG. 17, where the processing of instruction C, which follows instruction B, is also delayed.

FIG. 18 shows a pipeline flow for a superscalar machine when pipeline hazards occur. Here, instruction B1 has a true dependency on the preceding instructions A1 and A2. Here, the reason that a pipeline hazard occurs in the fifth clock cycle for the instruction C2 is that the two processing-units (arithmetic logic units or "ALUs") provided in the processor are busy with the execution of the preceding instructions B1 and C1. This means that instruction C2 cannot be executed in that cycle.

FIGS. 19 and 20 correspond to FIGS. 17 and 18, and show pipeline flows when two clock cycles need to pass before values obtained through memory access (MEM) can be used. In reality, in most real machines, obtaining a value from the primary cache takes two clock cycles. Note that obtaining a value from the secondary cache takes more clock cycles.

FIGS. 21 and 22 respectively show pipeline flows for a standard machine and superscalar machine when instructions A1 and A2 are instructions that indicate a jump destination using a register. The jump destinations of these instructions are not known until the register reference stage (RF) is completed, so that the succeeding instructions B, B1, and B2 that are fetched as per normal during the register reference operation are canceled (as shown by the "x" in FIGS. 21 and 22) in the third clock cycle following the RF stages.

The following describes the specific problems of a superscalar machine and a real machine of the first conventional technique, with reference to FIGS. 23-26.

FIGS. 23-26 show pipeline flows when the virtual machine of the first conventional technique is realized by a real machine executing the virtual machine program shown in FIG. 10A. In detail, these figures show the pipeline flow for the latter part (the jump processing shown in FIG. 12D) of the microprogram (of FIG. 12A) with the address 7 that corresponds to the virtual machine instruction "Add" and the pipeline flow for the former part (the multiplication processing) of the microprogram (of FIG. 12C) with the address 8 that corresponds to the virtual machine instruction "Mult". FIGS. 23 and 24 respectively show the pipeline flows for a standard machine and a superscalar machine where one clock cycle needs to pass before a value read during a memory access can be used, while FIGS. 25 and 26 respectively show the pipeline flows for a standard machine and a superscalar machine where two clock cycles needs to pass before a value read during a memory access can be used.

This series of microprograms shown in FIGS. 12D and 12A contain two significant true dependencies. The first is in the microprogram for jump processing shown in FIG. 12D corresponding to the virtual machine instruction "Add", and exists between the instruction "Load" for reading a jump address and the instruction "Jump" for jumping to the address. The second is in the microprogram shown in FIG. 12C corresponding to the virtual machine instruction "Mult" for multiplication processing and exists between the instruction "Load" for reading a variable from the memory stack and the instruction "Mult" for multiplication processing.

In the pipeline shown in FIG. 23, the first data dependency is absorbed by the real machine instruction "Inc" that is inserted between the instructions "Load" and "Jump". The second data dependency is absorbed by the real machine instruction "Dec" that is inserted between the instructions "Load" and "Mult". The processing in this pipeline is only disturbed by the cancellation of one instruction that is necessitated by the execution of the real machine instruction "Jmp". As a result, the entire procedure is completed in 11 cycle clocks.

In the pipeline shown in FIG. 24, the first and second data dependencies are not absorbed. As a result, the processing in these pipelines is disturbed at three points. The first disturbance is the hazard in the fourth clock cycle caused by the first data dependency, the second is the cancellation of five instructions necessitated by the execution of real machine instruction "Jmp", and the third is the hazard in the eighth clock cycle caused by the second data dependency. As was the case with FIG. 24, the entire procedure is completed in 11 clock cycles in FIG. 23.

As in FIG. 24, the above first and second data dependencies are not absorbed in the pipeline shown in FIG. 25, so that the processing in this pipeline is disturbed at three points. The first disturbance is the hazard in the fifth clock cycle caused by the first data dependency, the second is the cancellation of one instruction necessitated by the execution of the real machine instruction "Jmp", and the third is the hazard in the tenth clock cycle caused by the second data dependency. The entire procedure is completed in 13 clock cycles.

As in FIG. 24, the above first and second data dependencies are not absorbed in the pipeline shown in FIG. 26, so that the processing is disturbed at three points. The first disturbance is the hazards caused in the fourth and fifth clock cycles by the first data dependency, the second is the cancellation of seven instructions necessitated by the execution of the real machine instruction "Jmp", and the third is the hazards caused in the eighth and tenth clock cycles by the second data dependency. As in FIG. 25, the entire procedure is completed in 13 clock cycles.

Considering that the processing shown in either of FIGS. 23 and 24 requires 11 clock cycles and that the processing shown in either of FIGS. 25 and 26 requires 13 clock cycles, it is clear that there is no difference in execution time between a standard machine and a superscalar machine for this first conventional technique. This means that no advantage is gained from using a superscalar machine capable of parallel processing.

In this way, this first conventional technique causes a large drop in the processing efficiency of a superscalar machine. Another drawback is the lack of provisions for exception handling, such as for errors, or interrupt handling, which is required for debugging.

As a result, a virtual machine that uses this first conventional technique needs to detect an interrupt state and to perform interrupt handling every time the machine executes a virtual machine instruction. This means that another memory access (i.e., data transfer of a variable in the memory that indicates an interrupt state into a register) is required every time a virtual machine instruction is executed. This cancels out the advantage of this first conventional technique, wherein assigning the TOS variable to a register reduces the number of memory accesses, so that the overall execution speed is not improved.

Problems with the Second Conventional Technique

The second conventional technique, which is to say the use of native coding, has a problem in that it is difficult to provide common virtual machine programs to real machines with different architectures. This is because part of the virtual machine program is written in real machine instructions for a specific type of real machine. As a result, when a virtual machine program is to be provided on a network for common use by five types of computers with different real-machine architectures, it becomes necessary to provide real machine programs of all five real machines.

Since there are also differences in system configuration between computers, there is no guarantee that real machine instructions will have a faster execution speed than virtual machine instructions, even for real machines with the same architecture. As one example, if programs are written for RISC (Reduced Instruction Set Computers) type real machines where code size is generally large, the use of insufficient memory will lead to frequent page swapping between main and virtual memory when virtual machine instructions are replaced with real machine instructions. This reduces the overall execution speed.

Problems with the Third Conventional Technique

The third conventional technique, which uses a JIT compiler, has a problem in that the compiling of the virtual machine program can take a long time. The reasons for this are explained below.

A first reason is that the processing must satisfy the specific restrictions of the target real machine concerning jump destinations. As one example, when the target machine has a restriction that the address of a jump destination must be within word (basic word length) boundaries in the main memory, simple conversion of the virtual machine instructions to corresponding real machine instructions will result in a violation of this restriction.

FIG. 27 is a program list for a sample virtual machine program for explaining this first reason. FIG. 28 is a flowchart for this sample virtual machine program.

The present virtual machine program calculates the total of ten integers from zero to nine. It is composed of a setting of initial values (step 7002, Addresses 0.about.6), judgment of the end of calculation (step 7003, Addresses 8.about.13), addition and setting of the next value to be added (step 7004, Addresses 15.about.29), and end processing (step 7005, Address 31).

FIG. 29 is a conversion table that is used when compiling this virtual machine program according to this third conventional technique. This conversion table is a correspondence table that associates virtual machine instructions with the real machine programs into which they are to be converted. Note that for reference purposes, the conversion table in FIG. 29 also shows the code size of each real machine program.

FIG. 30 shows the code arrangement of the real machine program that is obtained when the sample virtual machine program shown in FIG. 27 is compiled using the conversion table shown in FIG. 29. In FIG. 30, relative addresses in original virtual machine program are given for each real machine program to show the correspondence between the real machine program and the virtual machine program.

If the target real machine has a restriction whereby only jump destinations complying with a two-word alignment can be indicated, it can be seen from FIG. 30 that the virtual machine instruction "Stop" with address 31 that is the jump destination indicated by the virtual machine instruction "Brz" at address 13 is arranged at odd-numbered addresses in the real machine program. Since this address does not correspond to the two-word alignment, this branch instruction violates the restrictions concerning jump destinations. As a result, processing that rectifies this violation needs to be performed.

A second reason for the above problem is that special processing that accompanies branches can be necessary for the target real machine. Some CPUs with RISC architecture, such as CPUs with SPARC (Registered Trademark) architecture produced by SPARC INTERNATIONAL, INC. and CPUs produced by MIPS TECHNOLOGIES, INC., have special rules that are used when executing a number of instructions located after a branch instruction. Specific examples of these rules are the execution of a specific succeeding instruction regardless of whether a branch is performed (called a "delayed branch") or the execution of a specific succeeding instruction only when a branch is performed (called a "canceling branch").

When the target real machine is of this type, special processing needs to be performed, such as scheduling that analyzes the instructions and changes their order or the insertion of no operation instructions (such as NOP codes) directly after branch instructions.

Problems with the Fourth Conventional Technique

The fourth conventional technique, which is to say the compression of virtual machine programs in advance, has a problem in that there is no resolving means for dealing with problems that occur due to the execution of branch instructions in the compressed virtual machine program.

FIG. 31A shows a compression table for explaining this problem. This compression table associates variable-length codes 9300a with virtual machine instructions 9300b. FIG. 31B is example code that is obtained by encoding the virtual machine instruction sequence A using the compression table shown in FIG. 31A.

If the example code shown in FIG. 31B is decoded starting from the first bit, the original virtual machine instruction A ("babc") will be obtained. However, when the execution flow moves to point B in FIG. 31B due to a branch instruction, decoding the code sequence "0010110" that starts at point B using the compression table in FIG. 31A gives the mistaken virtual machine instruction "aabc".

Problems Common to the First.about.Fourth Conventional Techniques

The first.about.fourth conventional techniques described above have a common problem in that none of them is able to raise the efficiency of cache processing. As a result, the market is still waiting for the realization of a high-speed virtual machine that makes full use of the processing power of real machines and computers that are equipped with a cache memory.

FIG. 32 is a block diagram showing the program counter 6901 and the instruction cache 6902 of a virtual machine. This drawing will be used to explain the problems that can occur for a virtual machine that is equipped with a cache memory.

The instruction cache 6902 is equipped with a cache table 6904 that stores addresses for specifying each cache block in the cache memory, where a cache block is an instruction sequence 6903 composed of the data in ten consecutive addresses. FIG. 33 shows the case where the sample virtual machine program shown in FIG. 27 is stored in the cache memory, with the boundary lines A, B, and C marking the boundaries between the cache blocks. These boundary lines simply divide the virtual machine program into cache blocks of an equal size, as can be seen from the boundary line C that splits the virtual machine instruction "Br 8" into the opcode "Br" and the operand "8". Accordingly, when dividing a virtual machine program into cache blocks, it is necessary to judge whether any of the virtual machine instructions that changes the value of the program counter 6901 will end up spanning a boundary between cache blocks. This increases the complexity of the processing and results in an actual decrease in the overall execution speed of a virtual machine when a cache is provided.

It would be conceivably possible to devise a method for storing an entire virtual machine program in cache memory or a method for arranging the virtual machine program in the cache based on analysis of the virtual machine program by a JIT compiler. However, the former of these methods uses cache memory inefficiently and has a further problem in that the time required for file transfer in a network environment is greatly increased. The latter method, meanwhile, has a problem in that writing the virtual machine program into cache memory is very time-consuming. Accordingly, both of these methods result in a marked decrease in the overall execution efficiency of a virtual machine.

SUMMARY OF THE INVENTION

In view of the above problems, the present invention has an overall aim of providing a virtual machine that executes a virtual machine program at a higher execution speed than a conventional virtual machine, a virtual machine compiler that generates a program for this virtual machine (hereafter, a virtual machine and a virtual machine compiler are together called a virtual machine system), and a JIT compiler. Here, a virtual machine compiler refers to a program that translates a source program written in a high-level language such as C into a virtual machine program.

To achieve the above aim, the invention has the following six specific objects.

The first object is to provide a virtual machine system that can diminish disadvantages caused by true data dependencies so that high execution speed is maintained.

The second object is to provide a high-speed virtual machine system by minimizing the decreases in execution efficiency caused by interrupt handling.

The third object is to provide a virtual machine system with which "native coding" for different real machines can be performed without decreasing overall execution speed, even when the virtual machine is used by real machines with different architectures. Such a virtual machine is highly independent of real machine architectures without decreasing execution speed.

The fourth object is to provide a high-speed virtual machine system that can be used by a real machine with a cache system without decreases in execution efficiency which may result from a virtual machine instruction program being divided into cache blocks or from complicated resolving addresses being performed when using a JIT compiler.

The fifth object is to provide a high-speed virtual machine system that can decompress a compressed virtual machine program correctly even when the compressed program contains branch instructions.

The sixth object is to provide a high-speed JIT compiler that does not need to perform a complex resolving of addresses.

The first object can be achieved by a virtual machine of claim 1.

The virtual machine executes a virtual machine instruction sequence under control of a real machine, the virtual machine comprising: a stack unit for temporarily storing data in a last-in first-out format; an instruction storing unit for storing the virtual machine instruction sequence and a plurality of sets of succeeding instruction information, wherein each virtual machine instruction in the virtual machine instruction sequence is associated with a set of succeeding instruction information that indicates a change in a storage state of the data in the stack unit due to execution of a virtual machine instruction executed after the associated virtual machine instruction; a read unit for reading a virtual machine instruction and an associated set of succeeding instruction information from the instruction storing unit; and a decoding-executing unit for specifying and executing operations corresponding to a combination of the read virtual machine instruction and the read set of succeeding instruction information.

With the above construction, the instruction storing unit stores next instruction information in addition to virtual machine instructions and the decoding-executing unit performs not only operations for the decoded virtual machine instruction but also a stack handling in advance for a virtual machine instruction executed immediately after the decoded virtual machine instruction. Performing appropriate stack handling in advance in machine cycles where pipeline hazards (which occur especially frequently in superscalar machines) would otherwise occur, enables the detrimental effects of true data dependencies to be absorbed and so increases the execution speed of the virtual machine.

Here, the decoding-executing unit may include: a real machine instruction sequence storing unit for storing a plurality of real machine instruction sequences that correspond to all combinations of virtual machine instructions and sets of succeeding instruction information; a specifying unit for specifying a real machine instruction sequence in the real machine instruction sequence storing unit, the real machine instruction sequence corresponding to a combination of the virtual machine instruction and the set of succeeding instruction information read by the read unit; and an executing unit for executing the specified real machine instruction sequence.

In this way, advance stack handling for absorbing data dependencies can be included in the real machine instruction sequence corresponding to a virtual machine instruction.

Here, each set of succeeding instruction information may indicate a change in a number of sets of data in the stack unit due to execution of a virtual machine instruction executed after a virtual machine instruction associated with the set of succeeding instruction information, and at least one real machine instruction sequence stored in the real machine instruction sequence storing unit may contain real machine instructions that perform a stack handling in the stack unit in advance for a virtual machine instruction that is to be executed based on a set of succeeding instruction information associated with a currently executed virtual machine instruction.

With this construction, when a change in a number of stack levels due to execution of a given instruction is canceled out by execution of an instruction executed immediately after the given instruction, needless stack handling can be avoided, which improves the execution speed of the virtual machine.

Here, the real machine instruction sequences stored in the real machine instruction sequence storing unit may be composed with a premise that regions of the stack unit used to store two sets of data to be read first and second are mapped to two registers in the real machine.

The above construction replaces the load and store stack operations that are frequently performed by stack-type virtual machines with read/write operations for the internal registers of the real machine. Such operations are suited for rearrangement as the advance stack handling performed in machine cycles where pipeline hazards would otherwise occur. In this way, execution efficiency of the virtual machine is raised.

Here, the instruction storing unit may include a first storage area for storing the virtual machine instruction sequence and a second storage area for storing the sets of succeeding instruction information, wherein each location that stores a virtual machine instruction in the first storage area may be associated with a location that stores an associated set of succeeding instruction information in the second storage area, and the read unit may read the virtual machine instruction from a location in the first storage area and the associated set of succeeding instruction information from a location in the second storage area, the location in the first storage area being associated with the location in the second storage area.

In this way, a virtual machine instruction sequence and next instruction information are stored separately, which means that a virtual machine instruction sequence of the present virtual machine has the same data format as a conventional virtual machine instruction sequence. Compatibility of instruction data format with a conventional virtual machine is therefore maintained.

Here, the virtual machine instruction sequence stored in the instruction storing unit may be an extended virtual machine instruction sequence that includes extended virtual machine instructions, the extended virtual machine instructions being combinations of virtual machine instructions and associated sets of succeeding instruction information, wherein the read unit may read an extended virtual machine instruction from the instruction storing unit, and wherein the decoding-executing unit may specify and execute operations corresponding to the extended virtual machine instruction.

In this way, since an extended virtual machine instruction is a combination of a virtual machine instruction and next instruction information, next instruction information need not be processed or stored separately. This means that a virtual machine with a similar architecture to a conventional computer can be provided.

The first object can be also achieved by a virtual machine compiler. The compiler generates programs for a virtual machine with a stack architecture that includes a stack, the compiler including: an instruction sequence converting unit for converting a source program into a virtual machine instruction sequence executable by the virtual machine; a succeeding instruction information generating unit for generating sets of succeeding instruction information corresponding to virtual machine instructions in the virtual machine instruction sequence, each set of succeeding instruction information indicating a change in a storage state of data in the stack due to execution of a virtual machine instruction executed immediately after a virtual machine instruction corresponding to the set of succeeding instruction information; and an associating unit for associating each set of generated succeeding instruction information with a corresponding virtual machine instruction and outputting the set of succeeding instruction information and the virtual machine instruction.

In this way, the above virtual machine compiler generates not only virtual machine instructions but also next instruction information which can be used by a virtual machine to absorb true data dependencies. Thus, the present virtual machine compiler can generate programs for a virtual machine whose execution speed is improved by having data dependencies absorbed.

The second object can be achieved by a virtual machine. The virtual machine executes a virtual machine instruction sequence under control of a real machine, the virtual machine including: an instruction storing unit for storing the virtual machine instruction sequence; a read unit for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing unit; and a decoding-executing unit for specifying and executing operations corresponding to the virtual machine instruction, wherein the decoding-executing unit includes a branch instruction judging unit for judging if the virtual machine instruction is a branch instruction and an interrupt handling unit for detecting, if the virtual machine instruction is judged to be a branch instruction, whether there is an interrupt request, and, if so, performing a corresponding interrupt handling in addition to executing the branch instruction.

In this way, an interrupt handling is only performed whenever a branch instruction is executed, which is sufficient for most virtual machine programs. This suppresses decreases in execution speed caused by performing interrupt more frequently.

Here, the decoding-executing unit may further include a real machine instruction sequence storing unit for storing real machine instruction sequences corresponding to every virtual machine instruction and real machine instruction sequences for having interrupt handling performed corresponding to each interrupt request and an executing unit for executing a real machine instruction sequence corresponding to the virtual machine instruction read by the read unit, wherein if the virtual machine instruction is judged to be the branch instruction and an interrupt request is detected, the interrupt handling unit has the executing unit execute a real machine instruction sequence for having the corresponding interrupt handling performed and then the real machine instruction sequence corresponding to the branch instruction.

With this construction, an interrupt handling to be additionally performed can be specified by a real machine instruction sequence. This realizes a virtual machine capable of performing an interrupt handling with a simpler architecture.

The second object can be also achieved by a virtual machine. The virtual machine executes a virtual machine instruction sequence under control of a real machine, the virtual machine including: an instruction storing unit for storing the virtual machine instruction sequence; a read unit for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing unit; and a decoding-executing unit for specifying and executing operations corresponding to the read virtual machine instruction, wherein the decoding-executing unit includes a block judging unit for judging if the read virtual machine instruction is a virtual machine instruction representative of a block, a block being a predetermined number of virtual machine instructions and an interrupt handling unit for detecting, if the read virtual machine instruction is judged to be the representative virtual machine instruction, whether there is an interrupt request to the virtual machine, and if so, performing a corresponding interrupt handling in addition to executing the representative virtual machine instruction.

In this way, an interrupt handling is performed every time a predetermined number of virtual machine instructions are executed, and a frequency to perform interrupt handling can be controlled by changing this number in advance. This avoids decreases in execution speed caused by performing interrupt handling more frequently.

Here, the decoding-executing unit may include a real machine instruction sequence storing unit for storing a plurality of real machine instruction sequences corresponding to every virtual machine instruction and at least one real machine instruction sequence for having interrupt handling performed in response to an interrupt request and an executing unit for executing a real machine instruction sequence corresponding to the read virtual machine instruction, wherein the block judging unit may judge that the read virtual machine instruction is a virtual machine instruction representative of the block when a number of virtual machine instructions that have been read is equal to a multiple of the predetermined number and wherein if the read virtual machine instruction is judged to be a representative virtual machine instruction and an interrupt request has been detected, the interrupt handling unit may have the executing unit execute a real machine instruction sequence for having the interrupt handling performed and then the real machine instruction sequence corresponding to the representative virtual machine instruction.

With this construction, an interrupt handling to be additionally performed can be specified by a real machine instruction sequence. As a result, a virtual machine that is capable of performing an interrupt handling with a simpler architecture can be achieved.

The third object may be achieved by a virtual machine. The virtual machine executes a virtual machine instruction sequence under control of a real machine, the virtual machine including: a real machine program storing unit for storing a plurality of subprograms composed of real machine instructions; an instruction storing unit that includes a first area for storing the virtual machine instruction sequence and a second area for storing a plurality of pointers to the subprograms in the real machine program storing unit; a read unit for reading a virtual machine instruction in the virtual machine instruction sequence from the first area in the instruction storing unit; and a decoding-executing unit for specifying and executing operations corresponding to the read virtual machine instruction, wherein the decoding-executing unit includes an area judging unit for judging whether the virtual machine instruction is an instruction that transfers control flow to a location in the second area and an address converting-executing unit for executing, if the virtual machine instruction is judged to be an instruction that transfers control flow to a location in the second area, a subprogram indicated by a pointer stored in the location.

With this construction, execution of either a virtual machine function or a real machine function is solely determined by a corresponding location in an area of the memory map in the virtual machine, so a setting of whether a virtual machine function or a real machine function is executed for a function can be easily changed. This makes it possible to use "native-coding" in virtual machine programs for real machines with different architectures.

Here, the first area and the second area in the instruction storing unit may be two adjacent storage areas whose boundary is marked by an address, and the area judging unit may judge, when the read virtual machine instruction is a call instruction for a subprogram, whether the virtual machine instruction is an instruction that transfers control flow, by comparing a call address of the call instruction with the address.

With this construction, control over switches between executing a virtual machine function and a real machine function can be easily achieved by shifting the boundary line between areas in the memory map of the virtual machine. As a result, virtual machines that have improved execution speed and are suited to different real machine environments can be realized.

The fourth object can be achieved by a virtual machine. The virtual machine executes a virtual machine instruction sequence under control of a real machine, the virtual machine including: an instruction storing unit for storing the virtual machine instruction sequence; a read unit for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing unit; and a decoding-executing unit for specifying and executing operations corresponding to the read virtual machine instruction, wherein the instruction storing unit is a plurality of instruction blocks that constitute the virtual machine instruction sequence, the instruction blocks corresponding to basic blocks, wherein the instruction blocks each include: an identifier area for storing an identifier that specifies a start position of the instruction block in the instruction storing unit; a non-branch instruction area for storing non-branch instructions belonging to a corresponding basic block; and a branch instruction area for storing at least one branch instruction belonging to the corresponding basic block, wherein each branch instruction stored in the branch instruction area designates a branch destination using an identifier stored in one of the identifier areas, and wherein if the read virtual machine instruction is a branch instruction, the decoding-executing unit has control flow branch to a start position of a non-branch instruction area in an instruction block having an identifier designated by the branch instruction as a branch destination.

With this construction, there is always only one entry point for each instruction block, which is the start of the instruction block. As a result, the address analysis for branch destinations of branch instructions is simplified, and the timing taken by compiling is reduced. Also, by caching instructions in instruction block units, the judgment processing regarding the cache boundaries is simplified, and decreases in execution efficiency that occur when a cache is provided for the virtual machine can be made smaller than in conventional techniques.

Here, the decoding-executing unit may include a program counter composed of (a) an identifier register for storing an identifier of an instruction block to which a virtual machine instruction to be read belongs and (b) an offset counter for storing an offset that indicates a relative storage position of the virtual machine instruction in the instruction block, wherein the read unit may read the virtual machine instruction based on the identifier and the offset in the program counter, wherein the decoding-executing unit may update, if the read virtual machine instruction is the branch instruction, the program counter by writing the identifier designated as the branch destination by the branch instruction into the identifier register and by setting an initial value in the offset counter, and if the read virtual machine instruction is a non-branch instruction, update the program counter by incrementing the offset counter, and the read unit may read a virtual machine instruction to be executed next based on the program counter updated by the decoding-executing unit.

Accordingly, each instruction block is specified only by a value of the identifier segment register, and each relative instruction storage position of a virtual machine instruction by a value of the offset counter. As a result, an address converting technique according to a conventional "segment method" can be used.

Here, the decoding-executing unit may include a real machine instruction sequence storing unit that stores a plurality of real machine instruction sequences that each correspond to a different virtual machine instruction, the instruction blocks in the instruction storing unit each may include a decoded data sequence area for storing a decoded data sequence that specifies real machine instruction sequences in the real machine instruction sequence storing unit, the real machine instruction sequences corresponding to virtual machine instructions stored in the non-branch instruction area and the branch instruction area of the instruction block, wherein if a decoded data sequence is stored in an instruction block where reading is to be performed, the read unit may read a set of decoded data in the decoded data sequence instead of a virtual machine instruction, and if not, the read unit may read the virtual machine instruction and then generate a set of decoded data to specify a real machine instruction sequence in the real machine instruction sequence storing unit that corresponds to the virtual machine instruction, and wherein the decoding-executing unit may read from the real machine instruction sequence storing unit the real machine instruction sequence specified by the set of decoded data that has been either read or generated by the read unit, and executes the real machine instruction sequence.

With this construction of the virtual machine, in addition to the effects achieved in the virtual machine that manages a virtual machine program in units of instruction blocks, a time to decode a virtual machine instruction is shortened for the instruction blocks that already have a decoded data sequence. This is because the decoded data sequence is executed directly instead of virtual machine instructions. As a result, the execution speed of the virtual machine is improved.

Here, the decoded data sequence area in the instruction storing unit may include a flag area for storing a flag that indicates whether the decoded data sequence is stored in the decoded data sequence area, wherein the decoding-executing unit may include a current flag storing unit for storing a flag that is read from a flag area in a branch destination instruction block by the decoding-executing unit when executing a branch instruction, and wherein the read unit may read a set of decoded data or a virtual machine instruction depending on the flag in the current flag storing unit.

For this construction, a flag indicating whether a decoded data sequence exists is provided to each instruction block and read from the instruction block to be held by the virtual machine. As a result, when executing virtual machine instructions in an instruction block that has a decoded data sequence, the virtual machine need not refer to a flag every time it executes one virtual machine instruction.

Here, each instruction block in the instruction storing unit may further include a flag area for storing a flag that indicates whether a decoded data sequence is stored in the decoded data sequence area of the instruction block, and the decoding-executing unit may include a decoded data sequence writing unit for judging, after a branch instruction has been executed, whether the instruction block designated as the branch destination by the branch instruction stores a decoded data sequence by referring to a flag stored in a flag area of the instruction block, and if no decoded data sequence is stored, having a virtual machine instruction sequence in the instruction block read, decoding the read virtual machine instruction sequence to produce a decoded data sequence, and writing the decoded data sequence into a decoded data sequence area in the instruction block.

For this construction, a decoded data sequence is generated when an instruction block is executed for the first time. As a result, when the same instruction block needs to be repeatedly executed as in loop processing, the time required for executing instructions corresponding to the block is reduced from the second execution of the block onwards.

The fifth object can be achieved by a virtual machine. The virtual machine executes a virtual machine instruction sequence under control of a real machine, the virtual machine including: an instruction storing unit for storing a compressed virtual machine instruction sequence to be executed; a read unit for reading a compressed virtual machine instruction in the compressed virtual machine instruction sequence from the instruction storing unit and decompressing the compressed virtual machine instruction to generate a decompressed virtual machine instruction; and a decoding-executing unit for specifying and executing operations corresponding to the decompressed virtual machine instruction, wherein the instruction storing unit is a plurality of instruction blocks containing compressed virtual machine instructions constituting the compressed virtual machine instruction sequence, the instruction blocks corresponding to basic blocks, wherein the instruction blocks each include: an identifier area for storing an identifier that specifies a start position of the instruction block in the instruction storing unit; a non-branch instruction area for storing compressed non-branch instructions belonging to a corresponding basic block; and a branch instruction area for storing at least one compressed branch instruction belonging to the corresponding basic block, wherein each compressed branch instruction stored in a branch instruction area designates a branch destination using an identifier stored in one of the identifier areas, and wherein if the decompressed virtual machine instruction is a branch instruction, the decoding-executing unit has control flow branch to a start position of a non-branch instruction area in an instruction block having an identifier designated by the branch instruction as a branch destination.

For this construction, the compressed virtual machine program is stored in units of the instruction blocks based on basic blocks and is decompressed by the decoding-executing unit. As a result, malfunctions caused when compressed bit sequences are mistakenly decoded starting midway through do not occur to this virtual machine.

Here, each instruction block may include a decompression table area for storing a decompression table for use during decompression of compressed virtual machine instructions in the instruction block, the decompression table containing at least one combination of a compressed virtual machine instruction stored in the instruction block and a corresponding decompressed virtual machine instruction and wherein the read unit may read the compressed virtual machine instruction from the instruction storing unit and decompresses the compressed virtual machine instruction by referring to a decompression table in an instruction block to which the compressed virtual machine instruction belongs to generate the decompressed virtual machine instruction.

With this virtual machine, each instruction block stores a decompression table, and a different decompression table is referred for execution of instructions belonging to each instruction block. Accordingly, the present virtual machine assures that even when each instruction block is compressed in a different format, decompression can be correctly performed.

The sixth object can be achieved by JIT compilers. The JIT compiler is for use with a virtual machine that executes a virtual machine instruction sequence under control of a real machine, the JIT compiler converting parts of the virtual machine instruction sequence into real machine instruction sequences before execution, the JIT compiler including: a block start information receiving unit for receiving an input of block start information for each virtual machine instruction that composes the virtual machine instruction sequence, the block start information showing whether a corresponding virtual machine instruction would correspond to a start of a basic block if the virtual machine instruction sequence were divided into basic blocks; a converting unit for converting virtual machine instructions in the virtual machine instruction sequence into real machine instruction sequences; and an outputting unit for rearranging the real machine instruction sequences produced by the converting unit into basic block units in accordance with the block start information received by the block start information receiving unit. Here, this JIT compiler may further include a branch violation judging unit for judging, when a real machine instruction at a start of a produced real machine instruction sequence corresponds to a virtual machine instruction whose block start information indicates that the virtual machine instruction would be a start of a basic block, whether the real machine instruction is going to be arranged in an address that violates an address alignment restriction of the real machine, wherein if the real machine instruction is going to be arranged in an address that violates the address alignment restriction, the outputting unit may rearrange the real machine instruction sequence so that the real machine instruction is not arranged in the address.

Accordingly, without performing the complicated processing for analyzing branch destinations of branch instructions, the present JIT compiler can produce a real machine instruction program at a higher speed in which branch destinations are arranged at addresses complying with a two-word alignment.

Here, the outputting unit may insert a certain number of no-operation instructions at a start of each basic block, the number being a number of real machine instructions processed during a delay of a delayed branch.

As a result, the above JIT compiler is capable of dealing with delayed branch by inserting no-operation instructions at a start of each basic block without performing a complicated delayed branch analyzing.

As has been described, the present invention improves execution speed of virtual machines and is especially valuable as a technique to promote efficient and high-speed use of shared resources by different types of computers connected on a network environment.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other objects, advantages and features of the invention will become apparent from the following description thereof taken in conjunction with the accompanying drawings which illustrate a specific embodiment of the invention. In the drawings:

FIG. 1 is a block diagram showing a conventional virtual machine with a stack architecture;

FIG. 2 is an explanation drawing that shows a virtual machine instruction set used in the conventional technique and the present invention;

FIG. 3 shows contents of the decode table shown in FIG. 1;

FIG. 4 shows microprogram lists stored in the microprogram storing unit shown in FIG. 1;

FIG. 5 shows operation contents of real machine instructions of the conventional technique and the present invention;

FIG. 6 is a flowchart showing the processing of the decoding unit shown in FIG. 1;

FIG. 7 is a flowchart showing the specific processing of step 4506 in FIG. 6;

FIG. 8 is a flowchart showing the processing of decoding unit 4402 in a case where decoded data transmitted from the decoding unit is transferred to the executing unit via a buffer;

FIG. 9 is a flowchart showing the processing of the executing unit shown in FIG. 1;

FIG. 10A shows a sample program list;

FIG. 10B shows the arithmetic expression "2*(3+4)" based on FIG. 10A;

FIG. 10C shows decoded data transmitted from the decoding unit in order;

FIG. 11 shows changing internal states of the conventional virtual machine when the executing unit of the virtual machine processes the decoded data shown in FIG. 10C;

FIGS. 12A-12D show a microprogram list for the conventional virtual machine that uses the TOS variable;

FIG. 13 shows changing internal states of the conventional virtual machine that stores microprograms shown in FIGS. 12A-12D when the virtual machine executes the virtual machine program shown in FIG. 10A;

FIG. 14 is an explanation drawing that shows abbreviated symbols for pipeline stages;

FIG. 15 shows an ideal pipeline flow of the standard machine;

FIG. 16 shows an ideal pipeline flow of the superscalar machine;

FIG. 17 shows a pipeline flow of the standard machine when hazzards occur;

FIG. 18 shows a pipeline flow of the superscalar machine when hazzards occur;

FIG. 19 shows a pipeline flow when two clock cycles need to pass before values obtained through memory access can be used in the case shown in FIG. 17;

FIG. 20 shows a pipeline flow when two clock cycles need to pass before values obtained through memory access can be used in the case shown in FIG. 18;

FIG. 21 shows a pipeline flow for the standard machine when instructions A1 and A2 are instructions that indicate jump destinations using a register;

FIG. 22 shows a pipeline flow for the superscalar machine when instructions A1 and A2 are instructions that indicate a jump destination using a register;

FIG. 23 shows a pipeline flow when the virtual machine of the first conventional technique is realized by a standard machine where one clock cycle needs to pass before values obtained through memory access can be used and the virtual machine program shown in FIG. 10A is executed;

FIG. 24 shows a pipeline flow corresponding to FIG. 23 when the virtual machine of the first conventional technique is realized by a superscalar machine;

FIG. 25 shows a pipeline flow for the standard machine when two clock cycles need to pass before values obtained through memory access can be used;

FIG. 26 shows a pipeline flow corresponding to FIG. 25 in the case of the superscalar machine;

FIG. 27 shows a virtual machine program list as a sample;

FIG. 28 is a flowchart for the sample program list shown in FIG. 27;

FIG. 29 is a conversion table that is used by the conventional JIT compiler;

FIG. 30 shows the code arrangement of the real machine program that is obtained when the sample virtual machine program shown in FIG. 27 is compiled using the conversion table shown in FIG. 29;

FIG. 31A shows an example of a compression table;

FIG. 31B shows an example code that is obtained using the compression table shown in FIG. 31A;

FIG. 32 is a drawing for explaining a problem likely to occur to the conventional virtual machine that includes a cache memory;

FIG. 33 shows the case where the sample virtual machine program shown in FIG. 27 is stored in the cache memory, with the boundary lines A, B, and C marking the boundaries between the cache blocks;

FIG. 34 is a hardware construction drawing of a computer system where the virtual machine systems of the first to ninth embodiments are used;

FIG. 35 is a block diagram showing the construction of the virtual machine in the first embodiment;

FIG. 36A shows the next instruction information stored in the next instruction information storing unit of the virtual machine shown in FIG. 35;

FIG. 36B shows the virtual machine program that is stored in the instruction storing unit and that corresponds to the next instruction information shown in FIG. 36A;

FIG. 37 shows stored contents of the decode table of the first embodiment;

FIGS. 38A and 38B show microprograms corresponding to virtual machine instructions "Push" assigned "U" and "D", respectively;

FIGS. 39A and 39B show microprograms corresponding to virtual machine instructions "Add" assigned "U" and "D", respectively;

FIGS. 40A and 40B show microprograms corresponding to virtual machine instructions "Mult" assigned "U" and "D", respectively;

FIG. 41A shows a microprogram corresponding to the latter half of the microprograms assigned "U" shown in FIGS. 39A and 40A;

FIG. 41B shows a microprogram corresponding to the latter half of the microprograms assigned "D" shown in FIGS. 39B and 40B;

FIG. 42 is a state transition diagram showing changes in virtual machine instruction types to be executed by the virtual machine of the first embodiment;

FIG. 43 is a flowchart showing the processing of the decoding unit of the virtual machine of the first embodiment;

FIG. 44 is a flowchart showing the initial half of the detailed processing of step 4907 for table searching in FIG. 43;

FIG. 45 is a flowchart showing the latter half of the detailed processing of step 4907 for table searching in FIG. 43;

FIG. 46 shows a decoded data sequence successively outputted from the decoding unit to the executing unit of the virtual machine in the first embodiment;

FIGS. 47A and 47B show changes in the internal states of the virtual machine when its executing unit operates according to the decoded data sequence shown in FIG. 46;

FIG. 48 shows a pipeline flow for the standard real machine when one clock cycle needs to pass before values obtained through memory access can be used;

FIG. 49 shows a pipeline flow for the superscalar real machine when one clock cycle needs to pass before values obtained through memory access can be used;

FIG. 50 shows a pipeline flow for the standard real machine when two clock cycles need to pass before values obtained through memory access can be used;

FIG. 51 shows a pipeline flow for the superscalar real machine when two clock cycles need to pass before values obtained through memory access can be used;

FIG. 52 is a block diagram showing the construction of the virtual machine compiler in the first embodiment;

FIG. 53 shows the data construction of the source program to be inputted into the instruction sequence converting unit of the virtual machine compiler;

FIG. 54 shows the data construction of each node shown in FIG. 53;

FIG. 55 is a flowchart showing a general procedure of the instruction sequence converting unit of the virtual machine compiler;

FIG. 56 is a flowchart showing the detailed processing of step 5405 in FIG. 55;

FIG. 57 is a flowchart showing the detailed processing of step 5613 in FIG. 56;

FIG. 58 is a flowchart showing the processing of the next instruction information generating unit of the virtual machine compiler;

FIG. 59 is a flowchart showing the processing of the relation associating unit of the virtual machine compiler;

FIG. 60 is a block diagram showing the construction of the virtual machine in the second embodiment;

FIG. 61 is a flowchart showing the detailed processing for table search and decoded data output by the decoding unit of the virtual machine;

FIG. 62 is a flowchart showing the processing of the branch instruction detecting unit of the virtual machine;

FIG. 63 is a flowchart showing the processing of the instruction inserting unit of the virtual machine;

FIG. 64 is a block diagram showing the construction of the virtual machine in the third embodiment;

FIG. 65 is a flowchart showing the processing of the block converting unit of the virtual machine;

FIG. 66 is a block diagram showing the construction of the virtual machine of the fourth embodiment;

FIG. 67 shows a memory map of the instruction storing unit of the virtual machine;

FIG. 68 shows the construction of the real machine function table shown in FIG. 67;

FIG. 69 is a flowchart showing the processing of the execution unit of the virtual machine;

FIG. 70 shows a modification example of a memory map of the instruction storing unit of the virtual machine;

FIG. 71 is a block diagram showing the construction of the virtual machine in the fifth embodiment;

FIG. 72 shows an example of states of virtual machine programs stored in the instruction storing unit of the virtual machine;

FIG. 73 shows a control flow of the virtual machine programs shown in FIG. 72;

FIG. 74 shows a data format obtained by the addressing by the PC of the virtual machine;

FIG. 75 is a flowchart showing the processing of the branch destination converting unit of the executing unit of the virtual machine;

FIG. 76 shows the address conversion by the branch destination converting unit, where logical addresses and identifiers in the virtual machine program shown in FIG. 72 are replaced with physical addresses;

FIG. 77 is a block diagram showing the virtual machine compiler in the fifth embodiment;

FIG. 78 shows the construction of the branch address conversion table of the virtual machine compiler;

FIG. 79 is a flowchart showing the processing of the block converting unit of the virtual machine compiler;

FIG. 80 is a flowchart showing the detailed processing of step 7607 in FIG. 79;

FIG. 81 is a flowchart showing the detailed processing of step 7704 in FIG. 79;

FIG. 82 is a flowchart showing the detailed processing of step 7609 in FIG. 79;

FIG. 83 shows the relationship between the PC, the instruction block storing areas, and the cache table when caching is performed by the virtual machine in instruction block units;

FIG. 84 is a flowchart showing the instruction processing of branch instructions by the executing unit when instructions are cached in instruction block units in the virtual machine;

FIG. 85 is a block diagram showing the construction of the virtual machine in the sixth embodiment;

FIGS. 86A to 86C show examples of the stored state of virtual machine programs in the instruction storing unit;

FIG. 87 is a flowchart showing the processing of the decoding unit of the virtual machine;

FIG. 88 is a flowchart showing the processing of the executing unit of the virtual machine;

FIG. 89 is a flowchart showing the control performed for the decoding unit when the executing unit of the virtual machine executes a branch instruction;

FIG. 90 is a block diagram showing the construction of the virtual machine in the seventh embodiment;

FIG. 91 is a flowchart showing the processing of the decoded instruction sequence writing unit, the current flag read control unit, and the branch destination converting unit when the virtual machine executes a branch instruction;

FIG. 92 is a flowchart showing the detailed processing of step 9110 in FIG. 91;

FIG. 93 is a flowchart showing the operation of the decoding unit when viewed from the executing unit;

FIG. 94 is a block diagram showing the construction of the virtual machine in the eighth embodiment;

FIG. 95A shows an example of the decompression table stored in the restoring information storing unit of the virtual machine;

FIG. 95B shows the rules governing codes in the decompression table shown in FIG. 95A;

FIGS. 96A to 96C show examples of the stored states of a virtual machine program that is stored in the instruction storing unit of the virtual machine;

FIG. 97 is a flowchart showing the processing of the decoding unit of the virtual machine;

FIG. 98 is a flowchart showing the detailed processing of step 9602 in FIG. 97;

FIG. 99 is a block diagram showing the construction of the entire compiler system including the JIT compiler of the ninth embodiment;

FIG. 100 is a flowchart showing the processing of the block start information generating unit of the virtual machine compiler;

FIG. 101 is a flowchart showing the processing of the real machine instruction converting unit, the branch position amending unit, and the real machine address storing unit;

FIG. 102 is a table showing the block start information generated by the block start information generating unit, the timing of the generation of "Nop" real machine instructions generated by the branch position amending unit of the JIT compiler, and other related information; and,

FIG. 103 shows a modification example of a virtual machine instruction format used by the virtual machine of the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENT(S)

The following explains embodiments of the present invention, with reference to figures.

First Embodiment

The following describes the virtual machine system of the first embodiment that can absorb a true data dependency.

FIG. 34 shows a hardware construction of the computer system 200 that operates the virtual machine system of the present embodiment. The computer system 200 comprises a real machine 201, a memory 200, a keyboard 203, a mouse 204, a display screen 206, a hard disks 207, a network card 208, and internal busses 205A-205C that connect these elements. This hardware construction is the same as that of a normal personal computer.

The virtual machine and the virtual machine compiler of the present embodiment are programs written with instructions for the real machine 201. These programs are stored in the hard disks 207 and loaded into the memory 202 according to instructions from the user or from another program that is being executed by the real machine 201. The real machine 201 is a CPU that decodes and executes the real machine instructions shown in FIG. 5 in the same way as described in the prior art.

Virtual Machine Construction

FIG. 35 is a block diagram showing the construction of a virtual machine 100 of the present embodiment. This figure corresponds to FIG. 1 in the explanation of the prior art. This virtual machine 100 includes a next instruction information storing unit 101, an instruction storing unit 102, a decoding unit 103, an executing unit 110 and a stack 120.

The instruction storing unit 102 is a storage area to store a virtual machine program to be processed, and the next instruction information storage unit 101 is an area to store sets of next instruction information that correspond to virtual machine instructions constituting the virtual machine program. A set of next instruction information refers to one-bit information indicating whether a virtual machine instruction that immediately follows a currently executed instruction is an instruction whose execution results in the level of the stack 120 being increased or decreased. Next instruction information indicating the former is written as "U" and the latter as "D". This information is generated together with the virtual machine program from a source program using a virtual machine compiler of the present embodiment, which will be described later.

FIGS. 36A and 36B respectively show examples of next instruction information stored in the next instruction information storing unit 101 and virtual machine codes stored in the instruction storing unit 102. These virtual machine codes and next instruction information correspond to a virtual machine program with the same contents as the virtual machine program shown in FIG. 10A, i.e. a calculation of "2*(3+4)". For example, next instruction information "U" is stored in locations specified by addresses "1" and "2" in the next instruction storing unit 101, since the corresponding virtual machine instruction "Push 2" in addresses "1" and "2" in the instruction storing unit 102 precedes an instruction "Push 3", that raises the level of the stack 120.

The decoding unit 103 reads virtual machine instructions successively from the instruction storing unit 102, decodes the virtual machine instruction referring to a corresponding set of next instruction information stored in the instruction storing unit 102, and outputs the result of the decoding to the executing unit 110. The decoding unit 103 includes a next instruction information reading unit 104, an instruction reading unit 105, a search unit 106, a program counter (PC) 107, and a decode table 108.

The PC 107 is a storage area to hold the address of a virtual machine instruction to be read next from the instruction storing unit 102 and the address of the corresponding next instruction information in the next instruction information storing unit 101. In the present embodiment, these addresses are assigned the same address number and are updated by the executing unit 110. The PC 107 is allocated physically to register #2 (r2) of the real machine 201.

The instruction reading unit 105 reads a virtual machine instruction from the instruction storing unit 102 according to the address indicated by the PC 107 and outputs the read virtual machine instruction to the search unit 106. In the same way, the next instruction information reading unit 104 reads a set of next instruction information from the next instruction information storing unit 101 specified by the address in the PC 107 and outputs the read information to the search unit 106. This processing by the next instruction unit 104 is synchronized with the instruction reading unit 105.

The decode table 108 stores the combinations of the next instruction information and opcodes corresponding to all the virtual machine instructions shown in FIG. 2 to be decoded and executed by the virtual machine 100, a jump address of a microprogram in the microprogram storing unit 111 to which each combination jumps, and a number of operands that accompany each opcode. Each opcode has one combination with the next instruction information "U", and one with the next instruction "D". As in the prior art, opcodes are 1-byte long, and operands are counted in units of one byte.

FIG. 37 shows the stored contents of the decode table 108, which corresponds to the decode table 4406 shown in FIG. 3 in the description of the prior art. Unlike the conventional decode table 4406, the jump address 108C and the number of operands 108D in this decode table 108 correspond to two cases when the opcode 108A is associated with next instruction information 108B "U" and "D". As one example, for the opcode "Push", a jump address to a microprogram that processes "Push" assigned "U" is provided for cases when the opcode "Push" is associated with the next instruction information "U", and a jump address to a microprogram that processes "Push" assigned "D" is provided for cases when the opcode "Push" is associated with the next instruction information "D".

The search unit 106 receives an opcode of a virtual machine instruction from the instruction reading unit 105 and the next instruction information from the next instruction reading unit 104 as a combination, specifies an entry corresponding to the combination out of the decode table 108, reads a jump address stored in the specified entry to output it as the decoded data to the executing unit 101.

The executing unit 110 executes a microprogram corresponding to a virtual machine instruction using the decoded data sent from the search unit 106. This executing unit 110 includes a microprogram storing unit 111 and a stack pointer (SP) 112.

The microprogram storing unit 111 stores microprograms corresponding to the combinations of the virtual machine instructions to be decoded and executed by the virtual machine 100 and the next instruction information. These microprograms will be explained later in detail.

The SP 112 is a storage area to store an address of the top of the stack 120 as described in the prior art, and is allocated physically to a register #3 (r3) of the real machine 201.

The stack 120 is a temporary LIFO storage area used by the executing unit 110 to execute microprograms for the decoded virtual machine program. This stack 120 includes the TOS variable 121, the SOS (Second Of Stack) 122 and the memory stack 123. The TOS variable 121 is a storage area for a value at the top of the stack 120 and is physically allocated to register #0 (r0) of the real machine 201. The SOS variable 122 is a storage area for a value on the second level of the stack 120 and is physically allocated to register #4 (r4) of the real machine 201. The memory stack 123 is a storage area for values on the third and lower levels and is allocated physically to the memory 202.

Contents of the Microprogram Storing Unit 111

FIGS. 38A and 38B respectively show microprograms in the microprogram storing unit 111 that correspond to the virtual machine instructions "Push" assigned "U" and "Push" assigned "D". FIGS. 39A, 39B, 40A, and 40B show microprograms corresponding to virtual machine instructions "Push" assigned "U" and "D", and virtual machine instructions "Mult" assigned "U" and "D". The instruction sequence shown in FIG. 41A forms the common latter part of the microprograms shown in FIGS. 39A and 40A that correspond to virtual machine instructions assigned "U". In the same way, the instruction sequence shown in FIG. 41B forms the common latter part of the microprograms shown in FIGS. 39B and 40B that correspond to virtual machine instructions assigned "D". The operation content of each real machine instruction in these microprograms are shown in FIG. 5.

By comparing these microprograms with the conventional microprograms shown in FIGS. 4A-4D and 12A-12D, it can be seen that the microprograms in the microprogram storing unit 111 of the virtual machine 100 in the present embodiment have the following characteristic. That is, with the present embodiment, different microprograms are prepared for a same type of virtual machine instruction and are selectively used depending on the next instruction information assigned to the virtual machine instruction. By considering how stack handling will be performed during the execution of the next virtual machine instruction, needless stack operations and pipeline disturbances due to true data dependency can be avoided. For instance, while the microprogram shown in FIG. 38B is for the virtual machine instruction "Push", it does not include an instruction to push a value stored in the SOS variable 122 to the memory stack 123 because the next instruction information assigned to this virtual machine instruction is "D", meaning that the execution of the next instruction will result in a pop. In this way, needless pushes to the memory are avoided in advance.

The virtual machine 100 has also another characteristic in that not only the storage area at the top of the stack 120 (the TOS variable 121), but also the storage area on the second level of the stack 120 (the SOS variable 122) are allocated to registers, not the memory. By doing so, both values used by an operation such as an addition can be held in registers, so that data transfer between the real machine 201 and the memory 202 can be performed less frequently. For instance, when an addition is performed, no data transfer between the registers and the memory 202 is necessary.

FIG. 42 is a state transition diagram showing changes in virtual machine instruction types. Here, each state in the state transition corresponds to an instruction type for each virtual machine instruction to be executed by the virtual machine 100 of the present embodiment. These instruction types are obtained by classifying all the combinations of virtual machine instructions to be decoded and executed by the virtual machine 100 and next instruction information, into the groups or instruction types, as indicated in the ovals in the figure, according to operations performed in the stack 120. Three numbers "X,Y(Z)" enclosed by each circle respectively denote a number of values used out of the stack by an operation, an increase in the number of stack levels due to the execution of the operation, and the next instruction information. For example, the "2, -1(U)" instruction type represents all virtual machine instructions that require two values for their operation, whose execution reduces the stack by one level, and that are assigned the next instruction information "U". An example of such is the virtual machine instruction "Add" that is assigned the next instruction information "U". The equation next to each oval of instruction type shows changes in the TOS variable 1221 and the SOS variable 122 resulting from the execution of the virtual machine instruction type in the oval, with "X" denoting an operand.

In this figure, any instruction belonging to an instruction type from which an arrow starts can be executed prior to the execution of any instruction belonging to the other instruction type indicated by the arrow. Different operations that can be executed prior to the execution of a next instruction are distinguished by arrows. Hereafter, these operations, which can be performed prior to the execution of the nest instruction, are called preceding operations. In FIG. 42, all arrows that start at a same instruction type are the same type. After the execution of an instruction belonging to the instruction type "2, -1(D)", for instance, a preceding operation shown by the arrow indicating "Pop SOS" can be executed before a next instruction which belongs to one of the following six instruction types: "2, -1(U)", "2, -1(D)", "1,0(U)", "1,0(D)2, "1, -1(U)", and "1, -1(D)". These operations "Pop SOS" pops the value at the top of the memory stack 123 onto the SOS variable 122. Note that the unconditional branch instruction "Br" and the end instruction "Stop" are represented by "1,0(U)" or "1,0(D)", which indicate that an empty operation is performed for a value stored in the TOS variable 121.

In this way, this state transition diagram can be thought of as showing analyzing results which indicate the preceding operations for each virtual machine instruction of the virtual machine 100. These analysis results are reflected in the microprograms stored in the microprogram storing unit 111, so that preceding operations (shown by the different types of arrows) are included in the corresponding microprograms.

Operation of Virtual Machine

The following explains the processing of the virtual machine 100 whose construction has been explained above.

FIG. 43 is a flowchart showing the processing of the decoding unit 103 of this virtual machine. This figure corresponds to FIG. 6 in the description of the prior art. By comparing FIGS. 43 and 6, it can be observed that the processing flow of this decoding unit 103 is basically the same as that of the conventional decoding unit 4402, except that a new step (step 4906) has been added and that specific contents of the processing to search the decode table (step 4907) are different. In the new step, the next instruction information storing unit 101 reads next instruction information from the next instruction storing unit 101 in synchronization with the instruction reading unit 105.

FIGS. 44 and 45 are flowcharts respectively showing former and latter halves of the detailed processing for searching the decode table 108 shown in step 4907 in FIG. 43. This figure corresponds to FIG. 7 in the description of the prior art. As can be seen by comparing FIG. 7 with FIGS. 44 and 45, the processing for searching tables in the present embodiment differs from the conventional art in that the following steps are newly added. The search unit 106 refers to not only an opcode of a virtual machine instruction outputted from the instruction reading unit 105 but also the next instruction information outputted from the next instruction information reading unit 104 (steps 5003 and 5007). The search unit 106 then finds an entry corresponding to the combination of the opcode and the next instruction information from the decode table 108 when "Yes" is given in steps 5008 and 5009, refers to a jump address 108C and a number of operands 108D, and outputs them as decoded data to the executing unit 110.

FIG. 46 shows decoded data to be outputted successively to the executing unit 110 when the next instruction information and the virtual machine instructions are stored in the next instruction information storing unit 101 and the instruction storing unit 102 as shown in FIGS. 36A and 36B, respectively. FIG. 46 corresponds to FIG. 10C in the description of the prior art. As shown in the figure, jump addresses to microprograms that correspond to combinations of the next instruction information and a virtual machine instruction are outputted.

The processing of the executing unit 110 is basically the same as that of the prior art shown in FIG. 9. That is, the executing unit 110 initializes the PC 107 and the SP112 (step 4702) and repeats the following processing from steps 4703-4707, where the executing unit 110 reads decoded data transmitted from the decoding unit 103 (step 4704) and branches to a microprogram specified by a jump address included in the decoded data for its execution (step 4705).

FIGS. 47A and 47B show the states of the PC 107, the SP 112, the TOS variable 121, the SOS variable 122, and the stack 4420 before and after the execution of the each virtual machine instruction when the executing unit 110 executes the virtual machine program shown in FIG. 36B. This figure corresponds to FIGS. 11A and 11B, or FIGS. 13A and 13B in the description of the prior art. A set of next instruction information and a virtual machine instruction to be executed is shown on the left and right of a slash "/", within a transition arrow pattern. The calculation of the arithmetic expression "2*(3+4)" is completed when PC 4404 indicates "9", as in the description of the prior art.

The characteristics observed in states shown in FIGS. 47A and 47B are, for instance, that after the execution of the virtual machine instruction "U/Push 3", the value in the SOS variable 122 has already been stored on the top of the memory stack 123, or that after the execution of the virtual machine instruction "D/Push 4", contents of the SP 112 and the memory stack 123 have not changed. These are the result of the execution of the preceding operations based on the analysis shown by the state transition diagram described above.

FIGS. 48-51 show pipeline flows of the real machine 201 when the virtual machine 100 of the present embodiment executes a part of the virtual machine program show in FIG. 36B, more specifically microprograms shown in FIGS. 41B and 40B, that respectively correspond to jump processing of the latter half of the virtual machine instruction "Add" assigned "D" with address "7" and multiplication processing of the first half of the instruction "Mult" assigned "D" with address "8". FIGS. 48 and 49 show the cases when one clock cycle is required before using a value obtained through memory reference (MEM) for a standard machine and a superscalar machine, respectively. FIGS. 50 and 51 show the cases requiring two clock cycles for a standard machine and a superscalar machine, respectively. These four figures correspond to FIGS. 23-26 for the first conventional technique.

This series of microprograms shown in FIGS. 12D and 12B contain two significant true dependencies between instructions. The first exists between instruction "Load" for reading a jump address and instruction "Jump" for jumping to that address. These instructions are included in the microprogram for jump processing shown in FIG. 12D corresponding to a virtual machine instruction "Add". The second true dependency exists between instruction "Load" for reading a variable from the memory stack and "Mult" for multiplication processing. These instructions are included in the microprogram shown in FIG. 12C corresponding to a virtual machine instruction "Mult" for multiplication processing.

In the pipeline flow shown in FIG. 48, the processing is only disturbed by one instruction cancellation caused in relation to the execution of the preceding real machine instruction "Jmp", so that the whole processing is completed in 11 cycle clocks. As can be seen by comparing this flow with that of FIG. 23, the execution speed of this virtual machine is the same as that of the conventional virtual machine described in the first conventional technique when the real machine 201 is a standard machine capable of using a memory reference value one clock cycle after a memory reference.

In the pipeline flow shown in FIG. 49, the first and the second data dependencies described in the first conventional technique are absorbed by the virtual machine 100 of the present embodiment. As a result, this pipeline flow is only disturbed by three instruction cancellations caused in relation to the execution of the preceding real machine instruction "Jmp r1", so that the whole processing is completed in 9 clock cycles. As can be seen by comparing this figure with that shown in FIG. 24, when the real machine 201 is a superscalar machine capable of using a memory reference value one clock cycle after a memory reference, the virtual machine 100 of the present embodiment has an execution speed 22% higher than that of the virtual machine described in the first conventional technique that requires 11 clock cycles.

In the microprogram corresponding to the virtual machine instruction "Add", instructions for the preceding operations, which are "Load r4, [r2]" and "Dec r3", for the next virtual machine instruction "Mult" are executed, and as a result, a sufficient time is secured between a memory reference (Load r1, [r2]) and a branch (Jmp r1) so that the disturbance in the pipeline flow is absorbed. Here, "Load r4, [r2]" and "Dec r3" for the preceding operations denote the popping from the memory stack 123 to the SOS variable 122 and a decrementing of the SP 112, respectively.

In the pipeline shown in FIG. 50, for the same reason described above, with the virtual machine 100 of the present embodiment, the first and the second data dependencies described in the first prior art are absorbed. As a result, the pipeline flow is only disturbed by the cancellation of one instruction necessitated by the execution of the preceding real machine instruction "Jmp r1", so that the whole processing is completed in 11 clock cycles. As can be seen by comparing this pipeline flow with that shown in FIG. 25, when the real machine 201 is a standard machine capable of using a memory reference value two clock cycles after a memory reference, the virtual machine 100 of the present embodiment has a performance speed 18% higher than that of the conventional virtual machine described in the first conventional technique that requires 13 clock cycles.

In the pipeline shown in FIG. 51, a number of hazards caused by the first data dependency decreases and the second data dependency is absorbed by the virtual machine 100 of the present embodiment. As a result, the pipeline flow is only disturbed by a hazard for one clock cycle resulting from the first data dependency and by the cancellation of five instructions due to the execution of the preceding real machine instruction "Jmp r1", so that the whole processing is completed in 10 clock cycles. As can be seen by comparing this pipeline flow with that shown in FIG. 26, when the real machine 201 is a standard machine capable of using a memory reference value two clock cycles after a memory reference, the virtual machine 100 of the present embodiment has a performance speed 30% higher than that of the virtual machine described as the first conventional technique that requires 13 clock cycles.

As has been described, the virtual machine 100 of the present embodiment executes a virtual machine instruction by referring to the corresponding next instruction information and performing stack handling, which is a preceding operation for the execution of the immediately following virtual machine instruction, between executions of two real machine instructions that have a true dependency with one another.

Construction of the Virtual Machine Compiler

The following explains a virtual machine compiler for the above virtual machine 100.

FIG. 52 is a block diagram showing the construction of a virtual machine compiler 3400 for the above virtual machine 100. The input to this virtual machine compiler is a source program 3404 written in a high-level language. The virtual machine compiler 3400 is a cross compiler for generating a virtual machine program 3405A composed of the specific virtual machine instructions shown in FIG. 2 of the above virtual machine 100 and sets of next instruction information 3405B that correspond to the virtual machine instructions. This virtual machine compiler 3400 includes an instruction sequence converting unit 3402, a next instruction information generating unit 3401, and a relation associating unit 3403.

The instruction sequence converting unit 3402 receives the source program 3404 via a circuit S from the network card 208 or the hard disk 207, and performs syntactic analysis to convert the source program 3404 into a virtual machine instruction sequence containing virtual machine instructions specific to the above virtual machine 100. The instruction sequence converting unit 3402 successively outputs the converted virtual machine sequence to the next instruction information generating unit 3401 and the relation associating unit 3403 via circuits C1 and C3.

The next instruction information unit 3401 receives virtual machine instructions from the instruction sequence converting unit 3402, specifies a set of next instruction information for each virtual machine instruction, and outputs the specified sets of next instruction information to the relation associating unit 3403 in order via a circuit C2. The instruction sequence converting unit 3402 and the next instruction information generating unit 3401 adjust timing for outputting the virtual machine instructions and the next instruction information so that inputs of a virtual machine instruction and a corresponding set of next instruction information to the relation associating unit 3403 are synchronized.

The relation associating unit 3403 associates a virtual machine instruction outputted from the instruction sequence converting unit 3402 with a corresponding set of next instruction information outputted from the next instruction information generating unit 3401 as a pair, and outputs each virtual machine instruction and next instruction information to a storage area like the memory 202 or the hard disk 207 as a final output program 3405 via circuits D1 and D2.

FIGS. 53 and 54 shows data constructions of the source program 3404 to input to the instruction sequence converting unit 3402 via the circuit S. FIG. 53 shows a tree construction corresponding to an instruction sequence "x:=(1+2)*(3+4)" of the source program 3404, and FIG. 54 shows a data construction of each node constituting the tree. A node corresponds to each instruction making up the instruction sequence in the source program 3404, and contains an instruction type 5201, a pointer to left sub-tree 5202, and a pointer to right sub-tree 5203.

Operation of Virtual Machine Compiler

The following describes the processing of the virtual machine compiler 3400 that processes the source program 3404 that has the data construction described above.

FIG. 55 is a flowchart showing the procedure of the instruction sequence converting unit 3402. The instruction sequence converting unit 3402 reads an instruction sequence of the source program 3404 represented by the tree structure (step 5402) and initializes a calculation stack used to track each branch of the tree construction (step 5403). The instruction sequence converting unit 3402 then sets a pointer to a root node in the variable ptr (step 5404), generates a virtual machine instruction sequence, i.e. virtual machine code corresponding to the instruction sequence represented in the tree construction (step 5405), and outputs it in units of bytes to the next instruction information generating unit 3401 and the relation associating unit 3403.

FIG. 56 shows the detailed processing of step 5405 in FIG. 55. The instruction converting unit 3402 repeats the following processing, where a node placed on the left branch is processed (steps 5603-5606) before a node on the right branch (steps 5607-5610). Numerical values and addresses included in instruction types 5201 are outputted as they are, and other codes are outputted after being converted to a corresponding virtual machine code (steps 5611-5613). Note that the processing from steps 5601-5614 is invoked on a recursive call in steps 5605 and 5609 so that this processing is repeated for all the nodes contained in the tree construction.

FIGS. 57A-57D are flowcharts showing the detailed processing of step 5613 in FIG. 56. These flowcharts correspond to the source program shown in FIG. 53. The instruction sequence converting unit 3402 generates either "Push", "Mult", "Pop", or "Add" opcode of a virtual machine instruction according to a stored value in the variable knd of each instruction type 5201 of a node (steps 5901-5909).

FIG. 58 is a flowchart showing the processing of the next instruction information generating unit 3401. The next instruction information generating unit 3401 receives virtual machine codes, which are successively outputted from the instruction sequence converting unit 3402, in units of bytes (step 5502), and judges whether each virtual machine code except for the virtual machine code sent using the first one byte is an operand, "Push" opcode of a virtual machine instruction, or an other opcode. The next instruction information generating unit 3401 then specifies a set of next instruction information Next corresponding to the virtual machine code and outputs the information Next to the relation associating unit 3403 (steps 5503-5509). Here, a set of next instruction information to be output last is fixed as "U" (step 5510).

FIG. 59 shows the processing of the relation associating unit 3403. The relation associating unit 3403 initializes a variable prv that stores a set of next instruction information of a virtual machine instruction processed immediately before and an address Addr of a virtual machine code and associated next instruction information to be generated (step 6002). The relation associating unit 3403 then repeats the following processing (steps 6004-6010) until it judges that there are no virtual machine code to be read from the instruction sequence converting unit 3402 (step 6003).

The relation associating unit 3403 receives a 1-byte virtual machine code and the corresponding next instruction information Next from the instruction sequence converting unit 3402 and the next instruction information generating unit 3401 via the circuits C1 and C2, respectively (steps 6004 and 6005). The relation associating unit 3403 then judges whether the next instruction information Next is "X" indicating that the present next instruction information is the same as the immediately preceding information (step 6006), and determines the next instruction information now of the virtual machine code (steps 6007 and 6008). Following this, the relation associating unit 3403 outputs the determined next instruction information now and the virtual machine code as a pair to a location specified by the address Addr in a storage area, such as the memory 202, (step 6009) and prepares for the processing of the next virtual machine code (step 6010).

In this way, the virtual machine compiler 3400 of the present embodiment generates a virtual machine program used for the virtual machine 100 of the present embodiment from the source program 3404 written in high-level language. This generated virtual machine program contains a virtual machine instruction sequence and sets of next instruction information, to be respectively stored in the instruction storing unit 102 and the next instruction information storing unit 101 of the virtual machine 100 shown in FIG. 35.

Here, note that input to the virtual machine compiler 3400 of the present embodiment is not limited to a source program represented with a tree construction such as the source program 3403, but may be text written in a programming language such as C. In such a case, the instruction sequence converting unit 3402 may perform a preceding operation to convert the text to intermediate code using a tree construction or a three-operand method.

Second Embodiment

The following describes the virtual machine of the second embodiment, which execution rate is not affected by an interrupt processing.

Construction of the Virtual Machine

FIG. 60 is a block diagram showing the construction of the virtual machine 3500 of the present embodiment. This virtual machine 3500 includes an instruction storing unit 4401, a decoding unit 3502, an interrupt controlling unit 3510, an executing unit 4410, and a stack 4420.

As can be seen by comparing. FIG. 60 with FIG. 1, this virtual machine 3500 includes basically the same elements as the conventional virtual machine 4400. These elements in the two figures are assigned common numbers, and explanation of these elements will be omitted here.

The differences between the conventional virtual machine 4400 and this virtual machine 3500 are as follows. First, in addition to the elements included in the conventional machine 4400, this virtual machine 4400 includes an interrupt controlling unit 3510 for controlling and executing processing that corresponds to an interrupt request to this virtual machine 3500. Secondly, the decoding unit 3502 outputs a control signal and decoded data to the branch instruction detecting unit 3505. Finally, the microprogram storing unit 4411 of the executing unit 3515 newly stores an interrupt handling program 3516 which is a real machine program for interrupt handling. The following explanation focuses on these new aspects of the virtual machine 3500 that are not included in the conventional virtual machine 4400.

The interrupt controlling unit 3510 detects if there is an interrupt request every time the virtual machine 3500 decodes and executes a branch instruction, and controls the processing to have the executing unit 4410 perform necessary interrupt handling. The interrupt controlling unit 3510 includes a branch instruction detecting unit 3505, an interrupt instruction inserting unit 3506, and an interrupt state storing unit 3507.

The branch instruction detecting unit 3505 receives decoded data from the search unit 4405 via a signal line D1, and judges if the received decoded data is a jump address of a microprogram corresponding to one of the following branch instructions of "Br", "Brz", "Brnz", "Call", and "Ret". If so, the branch instruction detecting unit 3505 turns on the signal line C2 and outputs the decoded data to the interrupt instruction inserting unit 3506, and if not, outputs the data with the signal line C2 left off.

The interrupt state storing unit 3507 is a storage area to store a state variable ID for specifying if an interrupt request to the virtual machine 3500 exists and, if so, a type of the interrupt. This interrupt state storing unit 3507 is physically allocated to a register of the memory 202 or the network card 208, for instance.

The interrupt instruction inserting unit 3506 is notified via the signal line C2 that the branch instruction detecting unit 3505 has detected a branch instruction. The interrupt instruction inserting unit 3506 then checks if there is an interrupt request by referring to the state variable ID stored at that point in the interrupt state storing unit 3507. If there is an interrupt request, the interrupt instruction inserting unit 3506 outputs the state variable ID and the decoded data for having an interrupt handling performed which is a jump address of the interrupt handling program 3516 of the microprogram storing unit 4410. This output is performed preceding the output of another decoded data for the detected branch instruction.

The interrupt handling program 3516 is a real machine program that reads an interrupt vector stored in the address on the memory 202 based on the state variable ID outputted from the interrupt instruction inserting unit 3506, and processes a subroutine in a location indicated by the interrupt vector.

Operation of Virtual Machine

The following describes the processing of the virtual machine 3500 that has the above construction.

FIG. 61 is a flowchart showing the detailed processing for outputting decoded data and searching the table by the decoding unit 3502. This figure corresponds to FIG. 7 in the description of the prior art.

The difference between these flowcharts lies in the processing for outputting decoded data (steps 6108-6111). That is, the search unit 4405 reads a jump address corresponding to an opcode of a virtual machine instruction outputted from the instruction reading unit 4403 (step 6106), and outputs the read jump address as decoded data to the branch instruction detecting unit 3505 via a signal line D1 with a signal line Cl on (steps 6108-6110).

FIG. 62 is a flowchart showing the processing of the branch instruction detecting unit 3505. The branch instruction detecting unit 3505 reads decoded data via a signal line D1, stores it temporarily as ddata (steps 6202-6203), and judges if the decoded data ddata is a jump address of a microprogram by referring to a state of the signal line C1 (step 6204). If so, the branch instruction detecting unit 3505 also judges if the jump address is for a microprogram corresponding to one of the branch instructions "Br", "Brz", "Brnz", "Call", and "Ret" that are stored in the branch instruction detecting unit 3505 in advance (step 6205). If so, the branch instruction detecting unit 3505 turns the signal line C2 on (step 6206) and outputs the decoded data ddata, which has been temporarily stored (steps 6206-6208). If not, the decoded data ddata is outputted with the signal line C2 turned off (steps 6207-6208).

FIG. 63 is a flowchart showing the processing of the interrupt instruction inserting unit 3506. The interrupt instruction inserting unit 3506 reads decoded data via the signal line D2, stores it as ddata2 temporarily (steps 6302-6303), and judges if the read decoded data ddata2 is a jump address of a microprogram corresponding to one of the above branch instructions referring to a state of the signal line C2 (step 6304). If so, the interrupt instruction inserting unit 3506 reads a state variable ID from the interrupt state storing unit 3507 (step 6305), and judges if an interrupt has been generated by referring to the state variable ID (step 6303). If so, the interrupt instruction inserting unit 3506 outputs the state variable ID and the jump address of the interrupt handling program 3516 to the executing unit 4410 as decoded data for having a predetermined interrupt handling performed (step 6307). Following this, the interrupt instruction inserting unit 3506 outputs other decoded data ddata2 for the branch instruction that has been temporarily stored to the executing unit 4410 (step 6308). As a result, the executing unit 3515 executes the interrupt handling program 3516 based on the state variable ID prior to the execution of the branch instruction.

On the other hand, if the interrupt instruction inserting unit 3506 judges that the decoded data inputted via the signal line D2 is not a jump address of a microprogram for a branch instruction (step 6304), or that no interrupt has been generated (step 6306), then the temporarily stored decoded data ddata2 is simply outputted to the executing unit 4410 (step 6308).

In this way, the virtual machine 3500 of the present embodiment checks whether an interrupt has occurred to the virtual machine 3500 each time it decodes and executes a branch virtual machine instruction, and if so, interrupt handling is additionally performed.

Compared with a conventional virtual machine 4400, the virtual machine 3500 of the present embodiment needs to execute one extra branch instruction for interrupt handling each time a virtual machine branch instruction is executed. As a result, the number of accesses to memory increases by one for each virtual machine branch instruction. However, in a normal machine program, an average of six non-branch instructions exist between branch instructions, so that the increased number of accesses to the memory for one instruction becomes less than 0.2. Accordingly, by using the above interrupt handling function of the present embodiment for the virtual machine 100 of the first embodiment, the number of accesses to the memory can be reduced as a whole, and a virtual machine with an interrupt handling function and improved performance speed can be achieved without overriding the effect of the TOS variable.

As has been described, the virtual machine 3500 of the present embodiment includes the interrupt contr