1997-06-11
2000-10-31
Hafiz, Tariq R.
395704, 395706, 395390, 395393, 39580023, G06F 944
Patent
active
061391999
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.sup.2 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.
REFERENCES:
patent: 5704053 (1997-12-01), Santhanam
patent: 5797013 (1998-08-01), Mahadevan et al.
patent: 5802373 (1998-09-01), Yates et al.
Per Bothner, "A Gcc-based Java Implementation," IEEE Compcon '97. Proceedings, pp. 174-178, Feb. 1997.
Cramer et al., "Compiling Java Just in Time," IEEE Micro., vol. 17, Issue 3, pp. 36-43, May-Jun. 1997.
Hsieh et al., "Optimizing NET Compilers for improved Java performance," Computer, vol. 30, Issue 6, pp. 67-75, Jun. 1997.
Cierniak et al., "Briki: an optimizing Java compiler," IEEE Compcon '97. Proceedings, pp. 179-184, Feb. 1997.
Rompaey et al., "Just in Time scheduling," IEEE 1992 International Conference on Computer Design, ICCD '92. Proceedings, pp. 295-300, Oct. 1992.
Dubey et al., "Instruction window size trade-offs and characterization of program parallelism," IEEE Transaction on Computers, vol. 43, Issue 4, pp. 431-442, Apr. 1994.
Dam Tuan Q.
Hafiz Tariq R.
Koestner Ken J.
Sun Microsystems Inc.
LandOfFree
Fast just-in-time (JIT) scheduler does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast just-in-time (JIT) scheduler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast just-in-time (JIT) scheduler will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2044268