Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-06-09
2004-03-09
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S024000
Reexamination Certificate
active
06704862
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to techniques for improving computer system performance. More specifically, the present invention relates to a method and an apparatus for supporting exception handling through use of a conditional trap instruction.
2. Related Art
As increasing semiconductor integration densities allow more transistors to be integrated onto a microprocessor chip, computer designers are investigating different methods of using these transistors to increase computer system performance. Some recent computer architectures exploit “instruction level parallelism,” in which a single central processing unit (CPU) issues multiple instructions in a single cycle. Given proper compiler support, instruction level parallelism has proven effective at increasing computational performance across a wide range of computational tasks. However, inter-instruction dependencies generally limit the performance gains realized from using instruction level parallelism to a factor of two or three.
Another method for increasing computational speed is “speculative execution” in which a processor executes multiple branch paths simultaneously, or predicts a branch, so that the processor can continue executing without waiting for the result of the branch operation. By reducing dependencies on branch conditions, speculative execution can increase the total number of instructions issued.
Unfortunately, conventional speculative execution typically provides a limited performance improvement because only a small number of instructions can be speculatively executed. One reason for this limitation is that conventional speculative execution is typically performed at the basic block level, and basic blocks tend to include only a small number of instructions. Another reason is that conventional hardware structures used to perform speculative execution can only accommodate a small number of speculative instructions.
What is needed is a method and apparatus that facilitates speculative execution of program instructions at a higher level of granularity so that many more instructions can be speculatively executed.
One challenge in designing a system that supports speculative execution is to provide an efficient mechanism to support exception handling for a speculative thread. Exception handling can cause code to execute slowly because testing for exceptions typically involves using control flow statements (such as if statements). These control flow statements can severely restrict a compiler's ability to move code around during the code optimization process in order to achieve an efficient scheduling of program instructions. Achieving an efficient scheduling of program instructions is particularly important for computer systems with multiple functional units.
Hence, what is needed is a method and an apparatus for providing exception handling without unnecessarily limiting a compiler's ability to move code around during the code optimization process.
SUMMARY
One embodiment of the present invention provides a system that supports exception handling through use of a conditional trap instruction. The system supports a head thread that executes program instructions and a speculative thread that speculatively executes program instructions in advance of the head thread. During operation, the system uses the speculative thread to execute code, which includes an instruction that can cause an exception condition. After the instruction is executed, the system determines if the instruction caused the exception condition. If so, the system writes an exception condition indicator to a register. At some time in the future, the system executes a conditional trap instruction which examines a value in the register. If the value in the register is an exception condition indicator, the system executes a trap handling routine to handle the exception condition. Otherwise, the system proceeds with execution of the code.
In one embodiment of the present invention, prior to executing the instruction, the system allows a compiler to optimize a program containing the instruction. This optimization process includes scheduling an exception testing instruction associated with the instruction to occupy a free instruction slot following the instruction. This exception testing instruction determines if the instruction causes the exception condition. In a variation on this embodiment, the system additionally performs register allocation as part of the optimization process. In a variation on this embodiment, the compiler operates as part of a just-in-time compilation mechanism.
In one embodiment of the present invention, the trap handling routine triggers a rollback operation to undo operations performed by the speculative thread.
In one embodiment of the present invention, prior to executing the instruction, the system inserts the conditional trap instruction in the vicinity of a return from a code module containing the instruction. In this way, the conditional trap instruction is executed at the end of the code module, which allows the condition trap instruction to detect whether instructions within the code module caused an exception condition.
In one embodiment of the present invention, the instruction can include a number of different instructions, including a getfield instruction, that generates an exception condition if a reference to an object containing the field is a null pointer. The instruction can also include a putfield instruction, that generates an exception condition if a reference to the object containing the field is a null pointer. The instruction can alternatively include a check cast instruction that assigns a value to a first variable if the value originates from a second variable with a type that matches the type of the first variable, and if not generates an exception condition. The instruction may additionally include an array store instruction that assigns a value to an array element if the type of the array element matches the type of a variable from which the value originates, and if not generates an exception condition.
In one embodiment of the present invention, the conditional trap instruction is located within a very long instruction word (VLIW) instruction.
REFERENCES:
patent: 5367696 (1994-11-01), Abe
patent: 5634023 (1997-05-01), Adler et al.
patent: 5778219 (1998-07-01), Amerson et al.
patent: 5802337 (1998-09-01), Fielden
patent: 5815719 (1998-09-01), Goebel
patent: 5835776 (1998-11-01), Tirumalai et al.
patent: 6301705 (2001-10-01), Doshi et al.
patent: 6487716 (2002-11-01), Choi et al.
patent: WO 99/19795 (1999-04-01), None
Chaudhry Shailender
Tremblay Marc
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
Treat William M.
LandOfFree
Method and apparatus for facilitating exception handling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for facilitating exception handling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for facilitating exception handling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3232733