Electrical computers and digital processing systems: processing – Processing control – Instruction modification based on condition
Reexamination Certificate
2000-09-28
2003-12-09
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Instruction modification based on condition
C712S234000
Reexamination Certificate
active
06662294
ABSTRACT:
BACKGROUND
1. Field of the Present Invention
The present invention generally relates to the field of microprocessor architectures and more particularly to a microprocessor utilizing an instruction group architecture and logic for detecting code sequences within an instruction group that are suitable for conversion to one or more predicated instruction.
2. History of Related Art
As microprocessor technology has enabled gigahertz performance, a major challenge for microprocessor designers is to take advantage of state-of-the-art technologies while maintaining compatibility with the enormous base of installed software designed for operation with a particular instruction set architecture (ISA). To address this problem, designers have implemented “layered architecture” microprocessors that are adapted to receive instructions formatted according to an existing ISA and to convert the instruction format of the received instructions to an internal ISA that is more suitable for operation in gigahertz execution pipelines.
Because a layered architecture adds to the processor pipeline and increases that number of instructions that are potentially “in flight,” at a given time, the branch mispredict penalty associated with a layered architecture is of great concern. One approach to minimizing branch misprediction penalties attempts simply to reduce the number of branch instructions. Since branch misprediction can only occur on a branch instruction, a code sequence containing no branch instructions can never be mispredicted. A well known method for reducing the number of branch instructions in a code sequence is includes the use of predicated instructions. Predicated instructions refer to instructions that perform a function, such as a fixed point add, if a condition that is specified in the predicated instruction itself, is satisfied. If the condition is not satisfied, instruction is treated as a NOP.
Predicated instructions can beneficially replace a code sequence that includes a condition setting instruction (such as a compare) followed by a conditional branch instruction and a short code sequence that is executed depending upon the status of the condition. In such a sequence, the conditional branch is used to branch around the relatively short code sequence depending upon the state of the condition. In the predicated instruction implementation of such a code sequence, the conditional branch statement is eliminated and each of the instructions in the short code sequence is replaced with a predicated instruction. As an example, the code sequence:
COMP R
1
,
0
//condition setting instruction
BEQ LBL //Branch to LBL
1
if R
1
=
0
ADD R
2
, R
3
, R
4
ADD R
2
, R
2
, R
5
LBL
1
, NOP
could be replaced with predicated instructions as follows:
COMP R
1
,
0
//condition setting instruction
PADD R
2
, R
3
, R
4
, NE //predicate add executed only if condition (NE) is true
PADD R
2
, R
2
, R
5
, NE //predicate add executed only if condition (NE) is true
Typically, predicated instructions are generated from high level source code by a compiler designed for use with an instruction set and hardware that support predicated instructions. The predicated instructions may have a distinct opcode from their non-predicated analogies. When compiling code for an instruction set that does not include predicated instructions, however, the compiler is forced to produce executable code that includes the conditional branch statement. It would be highly desirable to implement processor hardware capable of recognizing a code sequence characterized by a short branch and further capable of converting the sequence to a predicated code sequence during instruction decode or dispatch and executing the predicated code sequence. It would be further desirable if this predicated instruction conversion were transparent to system user such that recompiling of existing code would not be required to take advantage of the predicated execution hardware.
SUMMARY OF THE INVENTION
The goals described above are achieved with microprocessor and method of processing instructions therein as disclosed herein. Initially, a sequence of instructions is dispatched by a dispatch unit of the microprocessor. A code sequence recognition unit (CSR) is configured to detect a short branch sequence within the sequence of instruction, where the short branch sequence includes a condition setting instruction, a conditional branch, and at least one additional instruction that is executed if the conditional branch is not taken. The short branch sequence is then internally converted to a predicated instruction sequence that includes the condition setting instruction and a predicated instruction corresponding to each additional instruction in the short branch sequence. The predicated instruction sequence is then executed in at least one functional unit of the processor. Detecting the short branch sequence may include calculating the relative branch address associated with the conditional branch instruction and comparing the relative branch address to a specified maximum. In one embodiment, the received sequence of instructions may be converted into an instruction group by the processor. In this embodiment, the specified maximum number of instructions in a short branch sequence may be a function of the number of instructions in an instruction group. In an embodiment where the conditional branch statement is preferably allocated to the last slot of the instruction group, the additional instructions in the short branch sequence are located in the next subsequent instruction group. Converting the short branch sequence to the predicated instruction sequence may include converting each additional instruction in the short branch sequence to an analogous predicated instruction. In one embodiment, converting each additional instruction to its analogous predicated instruction includes determining a predicated instruction opcode for each additional instruction in the short branch sequence by adjusting the opcode of each additional instruction by a predetermined offset. In another embodiment, the opcode conversion may be accomplished with an opcode lookup table.
REFERENCES:
patent: 6052776 (2000-04-01), Miki et al.
patent: 6427234 (2002-07-01), Chambers et al.
patent: 6446258 (2002-09-01), McKinsey et al.
Mahlke et al., “Sentinel Scheduling for VLIW and Superscalar Processors”, Proceedings of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems, ACM, Oct. 1992, pp. 238-247.*
Gary S. Tyson, “The Effects of Predicated Execution on Branch Prediction”, Proceedings of the 27th Annual Symposium on Branch Prediction, ACM, Nov. 1994, pp. 196-206.
Kahle James Allan
Moore Charles Roberts
Emile Volel
Lally Joseph P.
Roberts Diana L.
Treat William M.
LandOfFree
Converting short branches to predicated instructions does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Converting short branches to predicated instructions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Converting short branches to predicated instructions will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3179472