Fast just-in-time (JIT) scheduler

• US 6,139,199 A
• Filed: 06/11/1997
• Issued: 10/31/2000
• Est. Priority Date: 06/11/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Rodriguez, John E.
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): DAM, TUAN QUANG
• Application Number:
  US08/877,870
• Time in Patent Office: 1,238 Days
• Field of Search: 395/709, 395/705, 395/704, 395/500, 395/390-395, 395/568, 395/570, 395/580, 395/581, 395/583, 395/588, 395/800.23, 395/800.08
• US Class Current: 717/159
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

A just-in-time (JIT) compiler typically generates code from bytecodes that have a sequence of assembly instructions forming a "template". It has been discovered that a just-in-time (JIT) compiler generates a small number, approximately 2.3, assembly instructions per bytecode. It has also been discovered that, within a template, the assembly instructions are almost always dependent on the next assembly instruction. The absence of a dependence between instructions of different templates is exploited to increase the size of issue groups using scheduling. A fast method for scheduling program instructions is useful in just-in-time (JIT) compilers. Scheduling of instructions is generally useful for just-in-time (JIT) compilers that are targeted to in-order superscalar processors because the code generated by the JIT compilers is often sequential in nature. The disclosed fast scheduling method has a complexity, and therefore an execution time, that is proportional to the number of instructions in an instruction block (N complexity), a substantial improvement in comparison to the N² complexity of conventional compiler schedulers. The described fast scheduler advantageously reorders instructions with a single pass, or few passes, through a basic instruction block while a conventional compiler scheduler such as the DAG scheduler must iterate over an instruction basic block many times. A fast scheduler operates using an analysis of a sliding window of three instructions, applying two rules within the three instruction window to determine when to reorder instructions. The analysis includes acquiring the opcodes and operands of each instruction in the three instruction window, and determining register usage and definition of the operands of each instruction with respect to the other instructions within the window. The rules are applied to determine ordering of the instructions within the window.

Claims

1. A fast scheduler for operating on a processor, the fast scheduler comprising:

a computer usable medium product having computable readable code embodied therein including;

a routine for acquiring a sliding window including three consecutive instruction from a memory which is coupled to the processor;

a routine for analyzing the tree-instruction sliding window in two successive examination operations; and

a routine for applying a plurality of rules to the three instructions within the sliding window to determine when to reorder scheduling of the instructions within the sliding window.

2. A fast scheduler according to claim 1 wherein the routine analyzing a sliding window of three instructions includes:

a routine a acquiring opcodes and operands of the instruction in the three instruction sliding window; and

a routine for determining register usage and definition of the operands of the instructions with respect to operands of other instructions within the three instruction sliding window.

3. A fast scheduler according to claim 1 wherein:

the routine for analyzing the three-instruction sliding window includes;

a routine for acquiring opcodes and operands of the instruction in the three instruction sliding window; and

a routine for determining register usage and definition of the operands of the instructions with respect to operands of other instructions within the three instruction sliding window, the instructions including a current instruction, a next instruction, and a last instruction, the routine for determining whether the current instruction defines a register that is used by the next instruction and for determining whether the next instruction defines a register that is used by the last instruction; and

the routine for applying a plurality of rules includes;

a routine for applying a first rule in which if the current instruction defines a register that is used in the next instruction and the next instruction does not define a register used in the last instruction, then the next instruction and the last instruction are switched; and

a routine for applying a second rule in which if the next instruction and the last instruction are switched by application of the first rule, then the sliding window is incremented by two instructions for a next application of the sliding window, and otherwise the sliding window is incremented by one instruction for the next application of the sliding window.

4. A fast scheduler according to claim 1 wherein:

the routine for analyzing the thee-instruction sliding window performs the sliding window in a single pass through an instruction block.

5. A fast scheduler according to claim 1 wherein:

the routine for analyzing the three-instruction sliding window performs the sliding window in a plurality of passes through an instruction block.

6. A fast scheduler according to claim 1 wherein:

the routine for applying a plurality of rules to the three instructions within the sliding window further comprises;

a routine for preventing switching of instructions including nop and branch instructions.

7. A fast scheduler according to claim 1 wherein:

the routine for applying a plurality of rules to the three instructions within the sliding window further comprises;

a routine for preventing switching of instructions in the sliding window when the instructions include a SAVE instruction or a RESTORE instruction.

8. A fast scheduler according to claim 1, wherein:

the routine for applying a plurality of rules to the three instructions within the sliding window further comprises;

a routine for preventing switching of instructions in the sliding window when the instructions include a jump and link (JMPL) instruction or a CALL instruction.

9. A fast scheduler according to claim 1 wherein:

the routine for applying a plurality of rules to the three instructions within the sliding window further comprises;

a routine for preventing switching of instructions in the sliding window when the switch operation would cause an instruction to bypass a STORE instruction.

10. A fast scheduler according to claim 1 wherein:

the routine for applying a plurality of rules to the three instructions within the sliding window further comprises;

a routine for preventing switching of instructions in the sliding window when the switch operation would cause a LOAD instruction to bypass a LOAD instruction.

11. A fast scheduler according to claim 1, wherein:

the fast scheduler is part of a Java™

just-in-time (JIT) compiler.

12. A fast scheduler according to claim 1, wherein the computer usable medium product includes a computer having computable readable code embodied therein for implementing of the acquiring, analzing, and applying routines thereof.

13. A computer system that executes instructions and prepares for instruction execution by fast scheduling the instructions, the computer system comprising:

a processor that fast schedules the instructions and executes the scheduled instructions;

a memory coupled to the processor, the memory including a computable readable code embodied therein for usage by a fast scheduler including;

code for acquiring a sliding window including three consecutive instruction from the memory;

code for analyzing the three instructions sliding window in two successive examination operations; and

code for applying a plurality of rules to the three instructions within the sliding window to determine when to reorder scheduling of the instructions within the sliding window.

14. A method of scheduling instructions for usage in a compiler comprising:

defining a first instruction pointer, a second instruction pointer, and a third instruction pointer designating a three instruction sliding window and identifying a first instruction, a second instruction, and a third instruction as a consecutive sequence of instructions;

in the sliding instruction window, determining whether the second instruction is dependent on the first instruction and whether the third instruction is dependent on the second instruction;

switching the second instruction and the third instruction when the second instruction is dependent on the first instruction and the third instruction is not dependent on the second instruction;

incrementing by two the first instruction pointer, the second instruction pointer, and the third instruction pointer if the second and third instructions are switched in the switching operation; and

incrementing by one the first instruction pointer, the second instruction pointer, and the third instruction pointer otherwise.

15. A method according to claim 14, further comprising:

looping through the determining step, the switching step, and the incrementing steps so long as instructions remain in an instruction block.

16. A method according to claim 14, further comprising:

initializing the first instruction pointer, the second instruction pointer, and the third instruction pointer to sequential initial values having a relative increment of a single instruction length.

17. A method according to claim 14, further comprising:

looping through the instructions in an instruction block in a single-pass.

18. A method according to claim 14, further comprising:

looping through the instructions in an instruction block in a plurality of iterative passes.

19. A method according to claim 14, wherein the operation of determining whether the second instruction is dependent on the first instruction includes:

examining the source operands of the second instruction and the destination operand of the first instruction;

designating a dependence condition when the destination operand of the first instruction is the same as a source operand of the second instruction; and

otherwise designating a non-dependence condition.

20. A method according to claim 14, wherein:

the compiler is a just-in-time (JIT) compiler.

21. A method according to claim 14, wherein:

the compiler is a Java™

just-in-time (JIT) compiler.

22. A fast scheduler according to claim 14, including a computer-usable medium product embodying a computer program having computable readable code embodied therein for implementing execution of the operations of defining, conditional determining switching, incrementing by one and incrementing by two.

23. A computer system that executes instruction and prepares for instruction execution by fast scheduling the instructions, the computer system comprising:

a processor that fast schedules the instructions and executes the scheduled instruction;

a memory coupled to the processor, the memory including a computable readable code embodied therein for usage by a fast scheduler including;

code for defining a first instruction pointer, a second instruction pointer, and a third instruction pointer designating a three instruction sliding window and identifying a first instruction, a second instruction, and a third instruction as a consecutive sequence of instruction;

code operative in the sliding instruction window for determining whether the second instruction is dependent on the first instruction and whether the third instruction is dependent on the second instruction;

code for switching the second instruction and the third instruction when the second instruction is dependent on the first instruction and the third instruction is not dependent on the second instruction;

code for incrementing by two first instruction pointer, the second instruction pointer and the third instruction pointer if the second and third instruction are switched in the switching operation; and

code for incrementing by one the first instruction pointer, the second instruction pointer, and the third instruction pointer otherwise.

24. A method of scheduling instructions for execution in a superscalar processor comprising:

acquiring a sliding window including three consecutive instructions from a memory which is coupled to the processor;

analyzing the sliding window of three instructions in two successive examination operations; and

applying a plurality of rules to the three instructions within the sliding window to determine when to reorder scheduling of the instructions within the sliding window.

25. A method according to claim 24 wherein:

the operation of analyzing a sliding window of three instructions includes;

monitoring opcodes of the instructions within the sliding window;

relatively comparing operands of the instructions in the three instruction window; and

determining register usages and definitions of the operands of the instructions with respect to operands of other instructions within the three instruction window.

26. A method according to claim 24 wherein:

the operation of analyzing a sliding window of three instructions includes;

monitoring the opcodes of the instructions within the sliding window;

relatively comparing the operands of the instructions in the three instruction window; and

determining register usages and definitions of the operands of the instructions with respect to operands of other instructions within the three instruction window, the instructions including a current instruction, a next instruction, and a last instruction, the routine for determining whether the current instruction defines a register that is used by the next instruction and for determining whether the next instruction defines a register that is used by the last instruction; and

the operation of applying a plurality of rules includes;

applying a first rule in which if the current instruction defines a register that is used in the next instruction and the next instruction does not define a register used in the last instruction, then the next instruction and the last instruction are switched; and

applying a second rule in which if the next instruction and the last instruction are switched by application of the first rule, then the sliding window is incremented by two instructions for a next application of the sliding window, and otherwise the sliding window is incremented by one instruction for the next application of the sliding window.

27. A method according to claim 24 wherein:

the operation of analyzing a sliding window of three instructions performs the sliding window in a single pass through an instruction block.

28. A method according to claim 24 wherein:

the operation of analyzing a sliding window of three instructions performs the sliding window in a plurality of passes through an instruction block.

29. A method according to claim 24 wherein:

the operation of applying a plurality of rules to the three instructions within the sliding window further comprises;

preventing switching of instructions including nop and branch instructions.

30. A method according to claim 24 wherein:

the operation of applying a plurality of rules to the three instructions within the sliding window further comprises;

preventing switching of instructions in the sliding window when the instructions include a SAVE instruction or a RESTORE instruction.

31. A method according to claim 24 wherein:

the operation of applying a plurality of rules to the three instructions within the sliding window further comprises;

preventing switching of instructions in the sliding window when the instructions include a jump and link (JMPL) instruction or a CALL instruction.

32. A method according to claim 24 wherein:

the operation of applying a plurality of rules to the three instructions within the sliding window further comprises;

preventing switching of instructions in the sliding window when the switch operation would cause an instruction to bypass a STORE instruction.

33. A method according to claim 24 wherein:

the operation of applying a plurality of rules to the three instructions within the sliding window further comprises;

preventing switching of instructions in the sliding window when the switch operation would cause a LOAD instruction to bypass a LOAD instruction.

34. A method according to claim 24 wherein:

the method is a fast scheduling method as a pan of a Java™

just-in-time (JIT) compiler.

35. A fast scheduler according to claim 24, wherein the computer usable medium product includes a computer program having computable readable code embodied therein for implementing execution of the acquiring, analyzing and applying, routines thereof.

36. A computer system that executes instructions and prepares for instruction execution by fast scheduling the instructions the computer system comprising:

a superscalar processor that fast schedules the instructions and executes the scheduled instructions;

a memory coupled to the superscalar processor, the memory including a computable readable code embodied therein for usage by a fast scheduler including;

code for acquiring a sliding window including three consecutive instructions from the memory;

code for analyzing the three instruction sliding window in two successive examination operation; and

code for applying a plurality of rules to the three instructions within the sliding window to determine when to reorder scheduling of the instructions within the sliding window.