Method and apparatus for state recovery following branch misprediction in an out-of-order microprocessor

Claim 2

A circuit implemented method of handling exceptions in a pipelined out-of-order microprocessor, said pipelined out-of-order microprocessor comprising an instruction fetch section, a decoder section, a register renaming section, an out-of-order section, and an execution section, said method comprising the steps of: fetching consecutive instructions using said instruction fetch section; decoding said instructions within said decoder section to generate decoded instructions; placing said decoded instructions in a reorder buffer of said out-of-order section using said register renaming section; executing said instructions in said execution section and storing executed instruction results back into said reorder buffer; retiring said executed instruction results in an original program order, said step of retiring comprising the substeps of testing an exception field associated with executed instruction results stored said reorder buffer; and handling an exception if said exception field indicates an exception occurred during instruction execution.

Claim 3

The circuit implemented method of claim 1 wherein said step of handling an exception further comprises the step of testing an exception type field and handling said exception based upon an exception type specified in said exception type field.

Claim 4

The circuit implemented method of claim 2 wherein said step of handling an exception further comprises the step of detecting a user exception in said exception type field; and restarting said instruction fetch section using a user exception handing address.

Claim 5

The circuit implemented method of claim 2 wherein said step of handling an exception further comprises the step of detecting a microcode handled exception in said exception type field; and loading exception handling microcode into said reorder buffer; and executing said exception handling microcode.

Claim 6

The circuit implemented method of claim 1 wherein said step of handling an exception further comprises the step of flushing said instruction fetch section; flushing said decoder section; and flushing said reorder buffer in said out-of-order section.

Claim 7

The circuit implemented method of claim 1 wherein said step of handling an exception further comprises the step of adjusting an instruction pointer in a retirement register file; and restarting said instruction fetch unit to execute at said instruction pointer.

Claim 8

A microprocessor for executing instructions, said microprocessor comprising: an instruction fetch section for fetching instructions in an original program order; a decoder section for decoding said instructions to generate decoded instructions; a register renaming section for scheduling said decoded instructions; an out-of-order section for handling said decoded instructions out of said original program order, said out-of-order section comprising a reorder buffer for storing decoded instructions; an execution section for executing said instructions out of said original program order, said execution section storing executed instruction results back into said reorder buffer; and retirement logic, said retirement logic retiring said executed instruction results in said original program order, said retirement logic testing an exception field associated with executed instruction results stored said reorder buffer and handling an exception if said exception field indicates an exception occurred during instruction execution.

Claim 9

A microprocessor for executing instructions, said microprocessor comprising: an instruction fetch section for fetching instructions in an original program order; a decoder section for decoding said instructions to generate decoded instructions; a register renaming section for scheduling said decoded instructions; an out-of-order section for handling said decoded instructions out of said original program order, said out-of-order section comprising a reorder buffer for storing decoded instructions; an execution section for executing said instructions out of said original program order, said execution section storing executed instruction results back into said reorder buffer; and retirement logic, said retirement logic retiring said executed instruction results in said original program order, said retirement logic testing an exception field associated with executed instruction results stored said reorder buffer and handling an exception if said exception field indicates an exception occurred during instruction execution.

Claim 10

The microprocessor of claim 7 wherein said retirement logic tests an exception type field and handles said exception based upon an exception type specified in said exception type field.

Claim 11

The microprocessor of claim 8 wherein said retirement logic detects a user exception in said exception type field and restarts said instruction fetch section using a user exception handing address.

Claim 12

The microprocessor of claim 8 wherein said retirement logic detects microcode handled exception in said exception type field and loads exception handling microcode into said reorder buffer to handle said exception.

Claim 13

The microprocessor of claim 7 wherein said retirement logic flushes said instruction fetch section, said decoder section, and said reorder buffer when an exception is detected.

Claim 14

A circuit implemented method of executing branch instructions in a pipelined out-of-order microprocessor, said pipelined out-of-order microprocessor comprising an instruction fetch section, a section, a register renaming section, an out-of-order section, and an execution section, said method comprising the steps of: predicting a predicted branch target address of a branch instruction using said instruction fetch section; decoding said branch instruction within said decoder section to generate a decoded branch instruction; placing said decoded branch instruction in a reorder buffer of said out-of-order section using said register renaming section; executing said branch instruction in an execution unit of said execution section to determine a final branch target address; comparing said predicted branch target address with said final branch target address; correcting for a mispredicted branch instruction when said predicted branch target address does not match said final branch target address by performing the substeps of flushing said instruction fetch section and restarting said instruction fetch section with said final branch target address; blocking said register renaming section from instructions from placing in said reorder buffer of said out-of-order section until said branch instruction is retired; retiring said branch instruction using retirement logic of said out-of-order section and flushing said reorder buffer; and unblocking said register renaming section such that instructions may again be placed in said reorder buffer of said out-of-order section.

Claim 15

A circuit implemented method of executing branch instructions in a pipelined out-of-order microprocessor, said pipelined out-of-order microprocessor comprising an instruction fetch section, a section, a register renaming section, an out-of-order section, and an execution section, said method comprising the steps of: predicting a predicted branch target address of a branch instruction using said instruction fetch section; decoding said branch instruction within said decoder section to generate a decoded branch instruction; placing said decoded branch instruction in a reorder buffer of said out-of-order section using said register renaming section; executing said branch instruction in an execution unit of said execution section to determine a final branch target address; comparing said predicted branch target address with said final branch target address; correcting for a mispredicted branch instruction when said predicted branch target address does not match said final branch target address by performing the substeps of flushing said instruction fetch section and restarting said instruction fetch section with said final branch target address; blocking said register renaming section from instructions from placing in said reorder buffer of said out-of-order section until said branch instruction is retired; retiring said branch instruction using retirement logic of said out-of-order section and flushing said reorder buffer; and unblocking said register renaming section such that instructions may again be placed in said reorder buffer of said out-of-order section.

Claim 16

The circuit implemented method of claim 12 wherein the step of correcting for a mispredicted branch is not performed if an earlier mispredicted branch instruction exists in said reorder buffer.

Claim 17

The circuit implemented method of claim 12 wherein said retirement logic retires instructions in said reorder buffer in an original program order.

Claim 18

The circuit implemented method of claim 12 wherein said decoded branch instruction comprises one or more micro-operations.

Claim 19

The circuit implemented method of claim 12 further comprising the step of predicting said branch instruction within an instruction stream using said instruction fetch section.

Claim 20

A state recovery method for recovering state following branch misprediction in a processor that includes an instruction fetch unit and a decoder section having a branch prediction mechanism, said processor including a re-order buffer (ROB) coupled to the decoder section and an out-of-order execution section coupled to the ROB, said out-of-order execution section including a branch execution unit, said processor including an in-order retirement section coupled to the ROB and the out-of-order execution section to retire the results therefrom in-order, said state recovery method comprising the steps of: (a) executing an execution-verifiable branch instruction in said branch execution unit including determining an actual target address and determining whether said branch instruction is taken or not taken, and thereby determining whether the subsequent instruction following the branch instruction is correct; (b) if the instruction following the branch instruction is correct, then continuing execution of subsequent instructions in said out-of-order execution unit, otherwise, determining if there is any other branch instruction in the out-of-order execution section is (1) earlier in the program sequence, (2) earlier executed, and (3) mispredicted, and if so, then continuing execution of subsequent instructions in said out-of-order execution unit, but if not, then performing the following steps (c) and (d); (c) asserting a JEClear signal thereby clearing the instruction fetch unit and the decoder section, changing the instruction pointer to point to the actual branch target address computed in the step (a), and then fetching and decoding instructions in the instruction fetch unit section beginning at said actual branch target address, but not issuing any of said instructions to the out-of-order execution section until after the following step (d) has been completed; and (d) waiting until the branch instruction has retired, and then asserting an ROClear signal to flush the out-of-order execution section and then allowing instructions to issue to the out-of-order execution section.

Claim 21

A state recovery method for recovering state following branch misprediction in a processor that includes an instruction fetch unit and a decoder section having a branch prediction mechanism, said processor including a re-order buffer (ROB) coupled to the decoder section and an out-of-order execution section coupled to the ROB, said out-of-order execution section including a branch execution unit, said processor including an in-order retirement section coupled to the ROB and the out-of-order execution section to retire the results therefrom in-order, said state recovery method comprising the steps of: (a) executing an execution-verifiable branch instruction in said branch execution unit including determining an actual target address and determining whether said branch instruction is taken or not taken, and thereby determining whether the subsequent instruction following the branch instruction is correct; (b) if the instruction following the branch instruction is correct, then continuing execution of subsequent instructions in said out-of-order execution unit, otherwise, determining if there is any other branch instruction in the out-of-order execution section is (1) earlier in the program sequence, (2) earlier executed, and (3) mispredicted, and if so, then continuing execution of subsequent instructions in said out-of-order execution unit, but if not, then performing the following steps (c) and (d); (c) asserting a JEClear signal thereby clearing the instruction fetch unit and the decoder section, changing the instruction pointer to point to the actual branch target address computed in the step (a), and then fetching and decoding instructions in the instruction fetch unit section beginning at said actual branch target address, but not issuing any of said instructions to the out-of-order execution section until after the following step (d) has been completed; and (d) waiting until the branch instruction has retired, and then asserting an ROClear signal to flush the out-of-order execution section and then allowing instructions to issue to the out-of-order execution section.

Claim 22

A speculative branch instruction processing method in a pipelined microprocessor that includes an instruction fetch unit and a decoder section for fetching, decoding, and issuing instructions to an out-of-order execution section, said speculative branch instruction processing method comprising the steps of: (a) predicting a branch location responsive to a branch instruction in the instruction fetch unit; (b) fetching and decoding a sequence of instructions beginning at said branch location; (c) if it is subsequently determined that the instruction following the branch instruction was correctly predicted, then continuing execution without changing instruction flow, but otherwise, determining if there is any other branch instruction in the out-of-order section that is (1) earlier in the program sequence, (2) earlier executed, and (3) mispredicted, and if so, then continuing execution without changing instruction flow, but if not, then continuing with the following steps (d) and (e); (d) asserting a JEClear signal to clear the instruction fetch unit and the decoder section, changing the instruction pointer to the actual branch target, and then continuing processing in the instruction fetch unit and decoder section, but issuing none of the decoded operations to the out-of-order execution section until after the following step (e) has completed; and (e) when said branch instruction has completed execution, and it is an oldest entry in the reorder buffer, then asserting an ROClear signal retiring said branch instruction and that cause the steps of: (e)(1) flushing the out-of-order execution unit, and (e)(2) supplying instructions from the decoder section to the out-of-order execution unit.

Claim 23

A speculative branch instruction processing method in a pipelined microprocessor that includes an instruction fetch unit and a decoder section for fetching, decoding, and issuing instructions to an out-of-order execution section, said speculative branch instruction processing method comprising the steps of: (a) predicting a branch location responsive to a branch instruction in the instruction fetch unit; (b) fetching and decoding a sequence of instructions beginning at said branch location; (c) if it is subsequently determined that the instruction following the branch instruction was correctly predicted, then continuing execution without changing instruction flow, but otherwise, determining if there is any other branch instruction in the out-of-order section that is (1) earlier in the program sequence, (2) earlier executed, and (3) mispredicted, and if so, then continuing execution without changing instruction flow, but if not, then continuing with the following steps (d) and (e); (d) asserting a JEClear signal to clear the instruction fetch unit and the decoder section, changing the instruction pointer to the actual branch target, and then continuing processing in the instruction fetch unit and decoder section, but issuing none of the decoded operations to the out-of-order execution section until after the following step (e) has completed; and (e) when said branch instruction has completed execution, and it is an oldest entry in the reorder buffer, then asserting an ROClear signal retiring said branch instruction and that cause the steps of: (e)(1) flushing the out-of-order execution unit, and (e)(2) supplying instructions from the decoder section to the out-of-order execution unit.