Just in time compiler technique

• US 6,324,686 B1
• Filed: 11/10/1998
• Issued: 11/27/2001
• Est. Priority Date: 11/11/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Momose, Hiroyuki, Komatsu, Hideaki, Ogata, Kazunori
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): ZHEN, WEI Y
• Application Number:
  US09/188,943
• Time in Patent Office: 1,113 Days
• Field of Search: 717/6, 717/7, 717/8, 717/5, 717/9
• US Class Current: 717/148
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

The present invention provides a compiler that can compile Java byte code at high speed while employing only limited resources. The technique converts byte code into intermediate code that employs, as an opcode, an address of an execution routine that corresponds to a byte code, and executes the execution routines in a sequential order corresponding to that of the intermediate code. The length of the intermediate code is constant and the bit location of the opcode is also constant. The execution routine is stored in sequential areas in a memory, and an offset of the execution routine group from the head address of the sequential memory area is employed as an opcode. Furthermore, by employing empty pipelines in the CPU, one part (operand generation and a jump) of an instruction group for jumping to the next intermediate code execution routine, and one part (prefetching of intermediate code and address calculation of a execution routine) of an instruction group for jumping to the next plus one intermediate execution routine can be executed in parallel to the original intermediate code process. Further, rule-based optimization using idioms is performed, without requiring analysis of the program structure.

Claims

1. A method for generating, from a first data sequence, a second data sequence, comprising the steps of:

reading a first data sequence;

determining whether the read first data sequence is identical to one of a plurality of predetermined rule sequences, each of the predetermined rule sequences comprising a set of data containable in the first data sequence; and

if the read first data sequence is identical to one of the rule sequences, converting a first data component in the read first data sequence to a second data type corresponding to the one of the rule sequences;

determining whether there is a probability that a data sequence other than the first read data sequence is identical to a data sequence included in said predetermined rule sequences; and

if it is ascertained that there is no probability, converting data next to said first read data sequence into a second kind of corresponding data.

2. The method according to claim 1, further comprising the step of:

if the read first data sequence is identical to one of the rule sequences, converting any remaining data components in the read first data sequence into a second kind of corresponding data.

3. The method according to claim 1, further comprising the step of:

performing said probability determining step for a data sequence in said first kind of read data sequence, said data sequence being not yet converted into the second kind of data sequence.

4. The method according to claim 1, wherein a structure of the first data sequence is not analyzed before said determining step.

5. The method according to claim 1, further comprising the steps of:

determining whether the data sequence in the read first data sequence that is not yet converted into the second kind of data is identical to said predetermined rule sequence if it is ascertained that there is a probability; and

if said data sequence is identical to said predetermined rule, converting the first data of said data sequence in said first kind of read data sequence, said data sequence not yet converted into the second kind of data, into the second kind of data corresponding to said predetermined rule sequence that is determined to be identical.

6. The method according to claim 1, wherein said converting step further comprises calculating an address for an execution routine corresponding to the first data component.

7. A method for converting a byte code sequence into an intermediate code sequence, comprising the steps of:

reading a byte code sequence;

determining whether the read byte code sequence is identical to one of a plurality of predetermined rule sequences, each of the said predetermined rule sequences comprising a byte code sequence which may be contained in the read byte code sequence; and

if the read byte code sequence is identical to one of the rule sequences, converting a first code portion of said read byte code sequence to intermediate code which corresponds to the one of the rule sequences.

8. The method according to claim 7, further comprising the steps of:

determining whether there is a probability that an additional byte code sequence other than the first code portion in said byte code sequence is identical to one of the rule sequences; and

if it is ascertained that there is no probability, converting a code following the first code portion into corresponding intermediate code.

9. Computer readable code stored on media and comprising a plurality of execution routines executable by a processor that can execute two or more instructions in one cycle, each of said plurality of execution routines including:

instructions originally required for an execution routine;

part of instructions for jumping to a second execution routine that is executed following the execution routine; and

part of instructions for jumping to a third execution routine that is executed following the second execution routine,

wherein each of said execution routines corresponds to each code in a code sequence that regulates the processing flow;

wherein said part of instructions for jumping to said second execution routine includes an operand generation instruction for said second execution routine and a jump instruction for jumping to said second execution routine; and

wherein said part of instructions for jumping to said third execution routine includes an instruction for fetching a code corresponding to said third execution routine, and an instruction for calculating an address of said third execution routine.

10. Computer readable code according to claim 9, wherein each of said execution routines corresponds to each code in a code sequence that regulates the processing flow;

and wherein a rule execution routine, which is a set of a plurality of execution routines, includes an instruction for fetching a code corresponding to said second execution routine from said code sequence, an instruction for calculating an address of said second execution routine, an operand generation instruction for said second execution routine, an instruction for jumping to said second execution routine, an instruction for fetching a code corresponding to said third execution routine from said code sequence, and an instruction for calculating an address of said third execution routine.

11. In a computing environment, a system for generating from a first kind of data sequence, a second kind of data sequence, comprising:

a module for reading a first kind of data sequence;

a module for determining whether the read first kind of data sequence is identical to one of predetermined idiom rules, each said predetermined idiom rules comprising a set of the first kind of data; and

a conversion module for converting the first data in said first kind of read data sequence to a second kind of data corresponding to said one of the idiom rules, if said first kind of read data sequence is identical to said one of the idiom rules,

wherein said conversion module includes a module for calculating an address of an execution routine that corresponds to said first kind of data.

12. The system according to claim 11, further comprising:

a second determination module for determining whether there is a probability that a data sequence other than said first data in said first kind of read data sequence is identical to a data sequence included in said predetermined idiom rule, wherein if it is ascertained that there is no probability, said conversion module converts data next to said first data into said second kind of corresponding data.

13. The system according to claim 11, wherein said execution routines are executed by a processor that can execute two or more instructions during one cycle;

wherein said system further comprises a storage device for storing said execution routines;

wherein each of said execution routines includes;

instructions originally required for an execution routine;

part of instructions for jumping to a second execution routine that is performed following said execution routine; and

part of instructions for jumping to a third execution routine that is performed following said second execution routine.

14. A system for converting a byte code sequence into an intermediate code sequence, comprising:

a processor;

a memory;

a program to be executed by a processor, said program including;

a module for reading a byte code sequence;

a module for determining whether the read byte code sequence is identical to one of a plurality of rule code sequences each of the plurality of rule code sequences comprising a set of byte codes; and

a conversion module for converting a first code portion of said read byte code sequence to an intermediate code corresponding to the identical rule code sequence, if said determining module determines the read byte code sequence is identical to one of the rule code sequences.

15. The system according to claim 14, wherein said memory stores execution routines that correspond to individual byte code portions, and wherein said conversion module performs a process for calculating an address of an execution routine corresponding to said byte code.

16. The system according to claim 15, wherein said processor executes a plurality of instructions in one cycle;

wherein an execution routine that corresponds to said rule code sequence includes an instruction for fetching a first intermediate code to be executed next to said rule code sequence, said first intermediate code corresponding to a second execution routine, an instruction for calculating an address of said second execution routine, an operand generation instruction for said second execution routine, an instruction for jumping to said second execution routine, an instruction for fetching a second intermediate code to be executed next and next to said rule code sequence, said second intermediate code corresponding to a third execution routine, and an instruction for calculating an address of said third execution routine.

17. A computer program stored on storage medium for causing a computer to generate from a first kind of data sequence, a second kind of data sequence, said program comprising the steps of:

reading a first kind of data;

determining whether the first kind of read data sequence is identical to one of a plurality of predetermined rule data, each said predetermined rule data comprising a set of said first kind of data;

converting the first data in said first kind of read data sequence to a second kind of data corresponding to said predetermined rule data, if said first kind of read data sequence is identical to said one of the predetermined rule data; and

calculating an address of an execution routine that corresponds to said first kind of data.

18. A computer program for causing a computer to convert a byte code sequence into an intermediate code sequence, said program comprising the steps of:

reading a byte code sequence;

determining whether the read byte code sequence is identical to one of a plurality of predetermined idiom code sequences, each said predetermined idiom code sequence comprising a set of said byte codes; and

converting the first byte code of said read byte code sequence to an intermediate code associated with an identical one of the idiom code sequences, if said read byte code sequence is identical to one of the idiom code sequences.