Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-07-21
2001-02-13
An, Meng-Ai T. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S233000, C712S234000, C710S260000, C710S261000, C710S262000, C710S263000
Reexamination Certificate
active
06189093
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of microprocessors and, more particularly, a method and circuit for storing exception information within architectured registers.
2. Description of the Relevant Art
Instruction scheduling is a well-known process of rearranging instructions of an application program before execution by a microprocessor in order to increase instruction execution and thus application program execution frequency. Instruction scheduling is typically implemented at an intermediate language level. Scheduling must preserve data dependencies between instructions in addition to fulfilling other considerations.
Instruction scheduling finds advantage when performed in connection with pipelined microprocessors. Pipelined microprocessors allow increased throughput by overlapping instruction execution. As an example of the efficiency connected with pipelined microprocessors, if there is a one-clock cycle delay between requesting data and data being available for the execution of an instruction, it would be desirable to insert one instruction into the one-clock cycle delay where the inserted instruction is independent of the data fetched and is ready to be executed.
Instruction scheduling can be employed in reduced instruction set computers (RISC). RISC-based systems provide a basis for high speed execution of instructions.
These systems typically require streamlining application instructions in order to achieve high speed operations. RISC-based systems typically employ instruction scheduling to take full advantage of pipelining and thereby to improve performance. Instruction scheduling is performed by compilers which generate code for the RISC processors. The compilers typically schedule instructions at the basic block level.
Microprocessors with multi-functional units (i.e, superscalar microprocessors) can execute several instructions each clock cycle. Pipelined microprocessors seek to issue a new instruction each cycle. However, compilers for each type of microprocessor seek to identify instructions that are data independent to allow scheduling of instructions that better utilize the microprocessor resources which, in turn, increases instruction throughput.
Data independent instructions can be found within basic blocks. However, it was a common view that there was no need to move instructions beyond basic block boundaries. A basic block is a sequence of consecutive instructions for which the flow of control enters at the beginning of the sequence and exits at the end without a possible branch, except at the point of exit. Virtually all prior art implementations of instruction scheduling focused on scheduling instructions within basic blocks.
As noted above, new architectures employ superscalar implementations which allow more than one instruction to issue per clock cycle. Superscalar microprocessors present more serious challenges to compilers, since instruction scheduling at the basic block level fails to generate code that utilizes microprocessor resources to the desired extent.
Scheduling instructions beyond the scope of basic blocks has been investigated resulting in considerable improvements of instruction throughput. However, the effect of moving instructions beyond block boundaries is limited unless the instructions can be scheduled speculatively. Speculative scheduling means that instructions are executed ahead of time before a preceding conditional branch is performed. As a result, the results of some speculatively scheduled instructions are not used in the subsequent execution of the program.
An important speculative instruction is the speculative load instruction. Computational sequences generally start with an instruction which loads operands from memory into registers. However, if load instructions are scheduled speculatively, an undesired exception may arise in program execution due to an access to a nonexistent or protected memory location.
Traditionally, load instructions must be performed within the basic block in order to avoid generating access exceptions. The following sequence of instructions is an example of a basic block with a load instruction contained therein:
LISTING 1:
INSTRUCTION
OPERATION
move RY,<pointer>
Move pointer (memory address) into
register RY
beq RY,zero,NULLP
Branch to NULLP of pointer equals
zero
Load RZ,(RY)
Load data into register RZ from
memory at pointer
<perform operation on RZ data>
Perform some operation
on data in RZ
Store RZ,(RY)
Store results of operation
In this example sequence, the prior art would not schedule the load instruction load RX,(RY) prior to the branch beq RY,zero,NULLP because in the case of a null pointer, an exception is generated that otherwise would not have occurred.
One prior art method for scheduling a load instruction beyond the boundaries of a basic block (thereby creating a speculative load) involves coupling the speculative load with an exception checking instruction. In this prior art method, the speculative load is moved outside the basic block and will not generate an exception. Rather, this prior art method saves a potential exception condition within some registers. Once inside the basic block where the load instruction originally was positioned prior to scheduling, a special instruction is provided and used to check for the potential exception. Shown below is an example of a sequence in which a load instruction is scheduled outside a basic block and an exception checking instruction is inserted therefore:
LISTING 2:
INSTRUCTION
OPERATION
move RY,<pointer>
Move pointer (memory address) into
register RY
load.s RZ,(RY)
Speculatively load data into RZ from
memory at pointer
beq RY,zero,NULLP
Branch to NULLP if pointer equals
zero
Check.s RZ,RY
Check for potential exception caused
by speculative load.s
<perform operation on RZ data>
Perform some operation on
data in RZ
Store RZ,(RY)
Store results of operation
Here the load instruction has been scheduled outside the basic block, i.e., prior to the branch instruction. The check.s instruction initiates an exception routine if the load.s has created one. However, in most cases, the check.s instruction will be executed quickly (more quickly than, for example, a load instruction with/without cache miss) because the load instruction has completed and there were no exceptions.
Clearly, microprocessors which avoid scheduling speculative loads suffer from the disadvantage that the load instructions must stay within the basic blocks to which they belong. Since load instructions can take several cycles to execute, such as in the case of a cache miss, it is clearly desirable to have load instructions scheduled as early as possible in the code.
In microprocessor architectures which support load.s/check.s instruction pairs described above, the load instructions can be scheduled outside the basic block, thereby increasing performance. However, since each original load instruction is replaced with a load plus a check.s instruction, compiled code will increase which, in turn, reduces microprocessor speed. Speed may also be degraded due to the “potential” cycle use by the check.s instruction.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by circuit and method which stores exception information for later use if required. In one embodiment of the method, exception information is generated in response to a memory access exception caused by a speculative load instruction for loading a first register for data from memory. The exception information, once generated, is stored within the first register. Thereafter, an instruction for operating on data stored in a second register is received and decoded. In response to receiving and decoding the instruction, the second register is accessed and checked to determine whether it contains exception information. If the second register contains exception information, then an exception routine is initiated. However, if the second register does not contain exception information, then the instruction for operating
Ekner Hartvig
Zilmer Morten
An Meng-Ai T.
El-Hady Nabil
LSI Logic Corporation
LandOfFree
System for initiating exception routine in response to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for initiating exception routine in response to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for initiating exception routine in response to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2563405