Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-07-21
2001-09-11
An, Meng-Al T. (Department: 2154)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S235000
Reexamination Certificate
active
06289445
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 executing speculative load instructions with implicit exception checking.
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 efficiency. 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 execution 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 if 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 RZ,(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 therefor:
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 checks instruction initiates an exception routine if the loads 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 size 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 a circuit and method for storing exception information in a register 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 one of a plurality of first registers with data from memory. The exception information, once generated, is stored within one of a plurality of second registers, wherein each of the second registers corresponds to at least one of the plurality of first registers and is configured to store exception information. Thereafter, an instruction for operating on data stored in a first register is received and decoded. In response to receiving and decoding this instruction, the contents of a second register corresponding to the first regist
An Meng-Al T.
Chang Jung-won
LSI Logic Corporation
LandOfFree
Circuit and method for initiating exception routines using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit and method for initiating exception routines using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit and method for initiating exception routines using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2438469