Intel Corporation

Reynold V D'Sa

David B Papworth

Bradley D Hoyt

Subramanian Natarajan

Michael A Fetterman

Sunil R Shenoy

Ashwani Kumar Gupta

Glenn J Hinton

Alan Beecher Kyker

Rebecca E Hebda

Robert F Krick

Stavros Kalafatis

Gustavo P Espinosa

Robert B Chaput

Slade A Morgan

Glenn I Hinton

Gad Shlomo Sheaffer

Chan W Lee

Gad S Sheaffer

Richard A Weier

The present invention provides for a method and apparatus for the detection and prevention of and recovery from bogus branch predictions in a microprocessor. Micro-ops, decoded from a macro instruction, are stored in a decoded micro-op cache. Branch prediction logic determines whether a branch is bogus or not. If the branch taken was determined to be bogus, the present invention causes the micro-ops which descend from the original bogus branch micro-op instruction to be flagged and subsequently moved to the back-end of the processor for retirement. Further, the branch prediction logic (the branch prediction logic storage buffer) is updated as to what the actual direction of the branch was. In this manner then, bogus branches are detected, recovered from and further prevented.

Detection, recovery and prevention of bogus branches

A method and apparatus for predicting the outcome of a branch instruction based on the branch history of preceding branch instruction. As a sequence of instructions passes through an instruction execution pipeline, a base branch instruction is chosen, a history index is generated for the base branch instruction and subsequent branch instructions, and a transform is created for the branch instruction to be predicted. When the sequence of instructions subsequently passes through the pipeline again, the transform is used to operate on the history index of the base branch instruction to produce a history index for the branch to be predicted. The result is used as an index into a prediction array to access the prediction logic for the branch instruction being predicted. By using the predetermined transform, a branch status prediction can be made before the branch to be predicted reaches the normal prediction stage in the pipeline.

Method and apparatus for performing sequential executions of elements in cooperation with a transform

A pipelined microprocessor is provided. The pipelined microprocessor includes a writeback stage which signals an event and sends a sequence number of an instruction which had the event. The event may be, for example, a fault, a trap or a branch misprediction. The pipelined microprocessor further includes a decode stage which stores recovering state information for respective instructions and is responsive to the writeback stage signaling the event by using the sequence number to access the stored information to retrieve recovery state information of the instruction which had the event. The recovery state information may include, for example, a pointer to a next linear instruction, a pointer to a branch target instruction, a branch prediction, or an instruction source. Event recovery micro-code determines a next instruction to execute using the recovery state information, the next instruction being executed after a machine recovery.

Recovery from writeback stage event signal or micro-branch misprediction using instruction sequence number indexed state information table

An instruction pipeline in a microprocessor is provided. The instruction pipeline includes a plurality of pipeline units, each of the plurality of pipeline units processing a plurality of instructions. At least two of the plurality of pipeline units are a source of at least some of the instructions for the pipeline. The pipeline further includes at least two speculative return address stacks, each of the speculative return address stacks coupled is coupled to at least one of the instruction source units. Each of the speculative return return address stacks are capable of storing at least two speculative return addresses.

System and method of maintaining and utilizing multiple return stack buffers

System and method of maintaining and utilizing multiple return stack

An instruction pipeline in a microprocessor is provided. The instruction pipeline includes a plurality of pipeline units, each of the pipeline units processing a plurality of instructions including branch instructions. The instruction pipeline further includes a plurality of storage device which store a respective branch information data. Each of the storage devices are associated with at least one of pipeline units. Each respective branch information data is determined as a function of at least one of the branch instructions processed. Two of the pipeline units include branch prediction circuitry for predicting branch direction as a function of the stored branch information data.

System and method for processing a plurality of branch instructions by a

A trace branch prediction unit includes a trace branch target buffer connected to a trace cache. The trace cache stores traces of micro-ops, with the micro-ops being stored non-sequentially. The trace branch target buffer generally reads a buffer entry corresponding to a particular trace line one clock cycle before the trace line is read to a processor. Using the entry, the trace branch target buffer predicts whether the trace cache should follow the existing trace or leave the trace. If the trace branch target buffer predicts that the trace cache should leave a trace, the trace branch target buffer provides a target address for a new trace. The trace branch target buffer also predicts when a trace is ending and provides a target address for the next trace.

Trace branch prediction unit

A Branch Target Buffer Circuit in a computer processor that predicts branch instructions with a stream of computer instructions is disclosed. The Branch Target Buffer Circuit uses a Branch Target Buffer Cache that stores branch information about previously executed branch instructions. The branch information stored in the Branch Target Buffer Cache is addressed by the last byte of each branch instruction. When an Instruction Fetch Unit in the computer processor fetches a block of instructions it sends the Branch Target Buffer Circuit an instruction pointer. Based on the instruction pointer, the Branch Target Buffer Circuit looks in the Branch Target Buffer Cache to see if any of the instructions in the block being fetched is a branch instruction. When the Branch Target Buffer Circuit finds an upcoming branch instruction in the Branch Target Buffer Cache, the Branch Target Buffer Circuit informs an Instruction Fetch Unit about the upcoming branch instruction.

Method and apparatus for implementing a set-associative branch target

A buffer is used to store information about the branch instructions within a pipelined microprocessor that can speculatively execute instructions. When a branch instruction in the microprocessor is decoded, the address of the instruction immediately following the branch instruction (the Next Linear Instruction Pointer or NLIP) and some processor state information is written into a Branch Instruction Pointer Table. The branch instruction then proceeds down the microprocessor pipeline. Eventually, the branch instruction is executed. The resolved branch outcome for the branch instruction is compared with a predicted branch outcome. If the branch prediction was correct, the microprocessor continues execution along the current path. However, if the branch prediction was wrong then the execution unit flushes the front-end microprocessor pipeline and restores the microprocessor state information that was stored in the Branch IP Table. If the branch was mispredicted as not taken, the execution unit instructs an Instruction Fetch Unit to resume execution at a final branch target address. Alternatively, if the branch was mispredicted as taken when the branch should not have been taken, the execution unit instructs the Instruction Fetch Unit to resume execution at the Next Linear Instruction Pointer (NLIP) address stored in the Branch IP Table.

Method and apparatus for a branch instruction pointer table

Method and apparatus for implementing a branch target buffer in CISC

A four stage branch instruction resolution system for a pipelined processor is disclosed. A first stage of the branch instruction resolution system predicts the existence and outcome of branch instructions within an instruction stream such that an instruction fetch unit can continually fetch instructions. A second stage decodes all the instructions fetched. If the decode stage determines that a branch instruction predicted by the first stage is not a branch instruction, the decode stage flushes the pipeline and restarts the processor at a corrected address. The decode stage verifies all branch predictions made by the branch prediction stage. Finally, the decode stage makes branch predictions for branches not predicted by the branch prediction stage. A third stage executes all the branch instructions to determine a final branch outcome and a final branch target address. The branch execution stage compares the final branch outcome and final branch target address with the predicted branch outcome and predicted branch target address to determine if the processor must flush the front-end of the microprocessor pipeline and restart at a corrected address. A final branch resolution stage retires all branch instructions. The retirement stage ensures that any instructions fetched after a mispredicted branch are not committed into permanent state.

Dual prediction branch system having two step of branch recovery process

A method and apparatus for resolving Return From Subroutine instructions in a computer processor are disclosed. The method and apparatus resolve Return From Subroutine instructions in four stages. A first stage predicts Call Subroutine instructions and Return From Subroutine instructions within the instruction stream. The first stage stores a return address in a return register when a Call Subroutine instruction is predicted. The first stage predicts a return to the return address in the return register when a Return From Subroutine instruction is predicted. A second stage decodes each Call Subroutine and Return From Subroutine instruction in order to maintain a Return Stack Buffer that stores a stack of return addresses. Each time the second stage decodes a Call Subroutine instruction, a return address is pushed onto the Return Stack Buffer. Correspondingly, each time the second stage decodes a Return From Subroutine instruction, a return address is popped off of the Return Stack Buffer. The second stage verifies predictions made by the first stage and predicts return addresses for Return From Subroutine instructions that were not predicted by the first stage. A third stage executes Return From Subroutine instructions such that the predictions are verified. Finally, a fourth stage retires Return From Subroutine instructions and ensures that no instructions fetch after a mispredicted return address are committed into permanent state.

Growing community of inventors

Aloha, OR, United States of America

Reynold V D'Sa