High speed virtual machine and compiler

A compiler that generates programs for a virtual machine with a stack architecture that includes a stack, comprising:

• 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.

A virtual machine that executes a virtual machine instruction sequence under control of a real machine, comprising:

• instruction storing means for storing the virtual machine instruction sequence;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the virtual machine instruction,
• wherein the decoding-executing means 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.

A virtual machine that executes a virtual machine instruction sequence under control of a real machine, comprising:

• instruction storing means for storing the virtual machine instruction sequence;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the read virtual machine instruction,
• wherein the decoding-executing means includes a
• 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.

A virtual machine that executes a virtual machine instruction sequence under control of a real machine, comprising:

• real machine program storing means for storing a plurality of subprograms composed of real machine instructions;
• instruction storing means 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 means;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the first area in the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the read virtual machine instruction,
• wherein the decoding-executing means 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.

A virtual machine that executes a virtual machine instruction sequence under control of a real machine, comprising:

• instruction storing means for storing the virtual machine instruction sequence;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the read virtual machine instruction,
• wherein the instruction storing means 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 means;
• 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 means 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.

A virtual machine that executes a virtual machine instruction sequence under control of a real machine, comprising:

• instruction storing means for storing a compressed virtual machine instruction sequence to be executed;
• read means for reading a compressed virtual machine instruction in the compressed virtual machine instruction sequence from the instruction storing means and decompressing the compressed virtual machine instruction to generate a decompressed virtual machine instruction;
• and
• decoding-executing means for specifying and executing operations corresponding to the decompressed virtual machine instruction,
• wherein the instruction storing means 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 means;
• 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 means 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.

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.

A storage method used by instruction storing means that stores a virtual machine instruction sequence to be executed by a virtual machine under control of a real machine,

• wherein the storage method results in:
• the instruction storing means being a plurality of instruction blocks that constitute the virtual machine instruction sequence, the instruction blocks corresponding to basic blocks;
• the instruction blocks each including:
• an identifier area for storing an identifier that specifies a start position of the instruction block in the instruction storing means;
• 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;
• and
• each branch instruction stored in the branch instruction area designating a branch destination using an identifier stored in one of the identifier areas.

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

• wherein the virtual machine comprises:
• stack means for temporarily storing data in a last-in first-out format;
• instruction storing means for storing a 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 means due to execution of a virtual machine instruction executed after the associated virtual machine instruction;
• read means for reading a virtual machine instruction and an associated set of succeeding instruction information from the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to a combination of the read virtual machine instruction and the read set of succeeding instruction information.

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.

A computer-readable recording medium that stores a program to have a computer function as a virtual machine,

• wherein the virtual machine comprises:
• instruction storing means for storing a virtual machine instruction sequence;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the virtual machine instruction,
• wherein the decoding-executing means 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.

A computer-readable recording medium that stores a program to have a computer function as a virtual machine,

• wherein the virtual machine comprises:
• instruction storing means for storing a virtual machine instruction sequence;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the read virtual machine instruction,
• wherein the decoding-executing means 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.

A computer-readable recording medium that stores a program to have a computer function as a virtual machine,

• wherein the virtual machine comprises:
• real machine program storing means for storing a plurality of subprograms composed of real machine instructions;
• instruction storing means that includes a first area for storing a virtual machine instruction sequence and a second area for storing a plurality of pointers to the subprograms in the real machine program storing means;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the first area in the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the read virtual machine instruction,
• wherein the decoding-executing means 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.

A computer-readable recording medium that stores a program to have a computer function as a virtual machine,

• wherein the virtual machine comprises:
• instruction storing means for storing a virtual machine instruction sequence;
• read means for reading a virtual machine instruction in the virtual machine instruction sequence from the instruction storing means;
• and
• decoding-executing means for specifying and executing operations corresponding to the read virtual machine instruction,
• wherein the instruction storing means 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 means;
• 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 means 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.

A computer-readable recording medium that stores a program to have a computer function as a virtual machine,

• wherein the virtual machine comprises:
• instruction storing means for storing a compressed virtual machine instruction sequence to be executed;
• read means for reading a compressed virtual machine instruction in the compressed virtual machine instruction sequence from the instruction storing means and decompressing the compressed virtual machine instruction to generate a decompressed virtual machine instruction;
• and
• decoding-executing means for specifying and executing operations corresponding to the decompressed virtual machine instruction,
• wherein the instruction storing means 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 means;
• 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 means 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.

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.