Patent Description:
Microprocessors, also known as "processors," perform computational tasks for a wide variety of applications. A conventional microprocessor includes a central processing unit (CPU) that includes one or more processor cores, also known as "CPU cores. " The CPU executes computer program instructions ("instructions"), also known as "software instructions" to perform operations on data and generate a result. A data result generated by a producer instruction of an instruction sequence may be an interim data stored for use by a consumer instruction. To avoid delays that would be caused by storing the interim data to an external memory and then reading the interim data back from external memory into the processor, the interim data can be stored in a register within the processor. The consumer instruction can name the register as an input operand to consume produced data stored in the register.

Instruction set architectures (ISAs) make a certain number of registers available to be used as operands in instructions. However, it is generally desired to provide more registers to store interim data than the number of registers in the ISA, since there may not be enough registers available in the ISA to avoid multiple instructions in the instruction pipeline naming the same register. In this regard, processors employ a greater number of physical registers than specified in an ISA for storing interim data. Thus, the registers available in the ISA are logical registers so that the processor can assign more than one physical register to a logical register. The processor maps the logical registers in processed instructions to the physical registers via a register map table to indicate the actual physical register where the data is stored. The processor includes a register renaming circuit in the instruction pipeline to rename logical registers to physical registers for accessing data in a physical register for execution of the instruction. A logical register-to-physical register mapping in the register map table is freed up when the physical register is obsolete, complete and no longer in-use. Obsolete means a newer write to the same logical register has committed. Complete means the result corresponding to the physical register has been written into the physical register file. No longer in-use means that all instructions that need to consume the physical register are past the point of reading the register file. The processor stores renaming information associated with each instruction in program order in the reorder buffer (ROB), and keeps the latest rename state in the register map table. Once an executed instruction is committed, logical register-to-physical register renaming of the instruction is saved to the committed map table (CMT).

Control hazards can occur in an instruction pipeline where the next instruction in the instruction pipeline cannot be executed without leading to incorrect computation results. For example, a control hazard may occur as a result of execution of a control flow instruction that causes a precise interrupt in the processor. One example of a control flow instruction that can cause a control hazard is a conditional branch instruction. A conditional branch instruction may redirect the flow path of instruction execution based on a condition evaluated when the condition of the control branch instruction is executed. As a result, the processor may have to stall the fetching of additional instructions until a conditional branch instruction has executed, resulting in reduced processor performance and increased power consumption. One approach for maximizing processor performance involves utilizing a prediction circuit to speculatively predict the result of a condition of a conditional branch instruction. However, a mispredicted branch instruction causes a misprediction recovery process to have to be performed, whereby the instruction pipeline is flushed and the instruction pipeline fetch unit is redirected to fetch new instructions starting from the address of the conditional branch instruction. As part of this misprediction recovery process, the register map table that contains register mapping information for uncommitted instructions in the instruction pipeline has to be returned to its previous state of register mapping before the instructions in the correct branch are processed. Because the reorder buffer keeps the latest register rename states in the register map table for uncommitted instructions, the instruction entries containing the latest register rename states in the reorder buffer can be used to restore the previous state of register mapping that executed prior to the instruction that was speculatively mispredicted. It is desirable to restore the register states in the processor in misprediction recovery as quickly as possible to minimize performance losses due to speculative mispredictions.

<CIT> describes how out-of-order CPUs, devices and methods diminish the time penalty from stalling the pipe to rebuild a rename table, such as due to a misprediction. A microprocessor can include a pipe that has a decoder, a dispatcher, and at least one execution unit. A rename table stores rename data, and a check-point table ("CPT") stores rename data received from the dispatcher. A Re-Order Buffer ("ROB") stores ROB data, and has a static mapping relationship with the CPT. If the rename table is flushed, such as due to a misprediction, the rename table is rebuilt at least in part by concurrent copying of rename data stored in the CPT, in coordination with walking the ROB.

Exemplary aspects disclosed herein include minimizing traversal of a processor reorder buffer (ROB) for register rename map table (RMT) state recovery for interrupted instruction recovery in a processor. Although instructions may execute out of order in a pipelined processor, the final result of each instruction on the processor state must be committed in program order. As instructions are processed, the instructions that have a register operand gain access to a logical register designated by the processor's instruction set architecture (ISA). To avoid interference between instructions, logical registers for different instructions must be mapped to unique physical registers. The RMT is updated as each new instruction enters the pipeline and maintains a most recent logical register-to-physical register mapping for each logical register of the processor. Information about the logical register-to-physical register mapping resulting from each instruction is stored in entries in program order in the ROB. When the pipeline is interrupted by an instruction that fails to execute as intended, changing program flow, all instructions following the interrupting instruction may be flushed from the processor pipeline. It is important to return the state of the RMT to the state that existed when the interrupting instruction entered the pipeline and an entry for the instruction was allocated in the ROB.

In exemplary aspects disclosed herein, to recover the RMT state in response to an interrupting instruction that fails to execute as intended, the register mapping information in the ROB entries is traversed sequentially to either undo the effect of younger instructions that entered the pipeline after the interrupting instruction or replay the effect of older instructions that entered the pipeline before the interrupting instruction. During traversal, logical register-to-physical register mapping information obtained from the ROB entries is used to restore the RMT state. To minimize the traversal time of the entries in the ROB to recover the RMT state, in certain aspects disclosed herein, a register rename recover circuit (RRRC) is provided that is configured to determine a position of an oldest flushed instruction entry allocated for the oldest flushed instruction in the ROB and traverse the ROB in a direction from the position of the oldest flushed instruction entry. By traversing the ROB from the oldest flushed instruction, it may be possible to avoid traversing either all of the surviving instruction entries in the ROB or all the flushed instruction entries in the ROB.

In some embodiments, the RRRC is configured to dynamically determine a traversing direction to minimize traversing of the entries in the ROB by minimizing the ROB entries to be traversed to recover the RMT state. For example, it may be possible to traverse fewer ROB entries in a first direction by undoing younger instructions entering the pipeline after the interrupting instruction than in an opposite direction by replaying older instructions entering the pipeline before the interrupting instruction, or vice versa. In other aspects, the RRRC traverses the ROB entries in the ROB in a direction from the instruction entry of the ROB for the oldest flushed instruction entry to the instruction entry for the oldest uncommitted instruction in the ROB. By traversing from the oldest flushed instruction entry, it may be possible to recover the state of logical register to physical register mapping for logical registers in the RMT and make them available to the processor more quickly. In other aspects, the RRRC is configured to traverse the ROB entries in the ROB in a direction from the instruction entry of the oldest flushed instruction to the entry for the youngest uncommitted instruction in the ROB. By traversing in this direction, only the flushed instructions are traversed, and all updates to the RMT are addressed.

In yet other aspects, the RRRC is configured to dynamically determine whether to traverse the ROB entries in the first direction from the instruction entry of the oldest flushed instruction entry to the instruction entry for the oldest uncommitted instruction or in the second direction from the oldest flushed instruction entry instruction to the entry for the youngest uncommitted instruction. By dynamically determining a direction of traversal, the traversal may be minimized. In yet other aspects, the RRRC is configured to traverse the ROB entries in the ROB in the first direction from the instruction entry of the oldest flushed instruction entry to the instruction entry for the oldest uncommitted instruction and in the second direction from the oldest flushed instruction entry instruction to the entry for the youngest uncommitted instruction in parallel. By traversing in both directions, through surviving entries and flushed entries, simultaneously, the traversing time is minimized and the RMT recovery is expedited.

An exemplary embodiment of a register renaming recover circuit (RRRC) in a processor is disclosed herein. The RRRC is configured to receive a flush indicator indicating a flush of one or more instructions in the processor based on an interrupting instruction that caused the flush of the one or more instructions in the processor, and receive an interrupting instruction indicator indicating a position of an interrupting instruction entry allocated to the interrupting instruction in a reorder buffer in the processor. The RRRC is further configured to determine a position of an oldest flushed instruction entry allocated for an oldest instruction of the one or more instructions indicated to flush based on the interrupting instruction indicator; and traverse the reorder buffer in the processor in a first direction from the position of the oldest flushed instruction entry. To traverse the reorder buffer, the RRRC is configured to determine if a first instruction allocated to a first instruction entry in the reorder buffer in the first direction resulted in a logical register-to-physical register mapping in a map entry of a register mapping table in the processor, and in response to determining the first instruction allocated to the first instruction entry in the reorder buffer in the first direction resulted in a logical register-to-physical register mapping in a map entry of the register mapping table in the processor, recover the logical register-to-physical register mapping of the map entry in the register mapping table to a previous logical register-to-physical register mapping prior to the oldest instruction of the one or more instructions indicated to flush.

In another embodiment, a method in a register rename recover circuit is disclosed. The method includes receiving a flush indicator indicating a flush of one or more instructions in the processor based on an interrupting instruction that caused the flush of the one or more instructions in the processor, and receiving an interrupting instruction indicator indicating a position of an interrupting instruction entry allocated to the interrupting instruction in a reorder buffer in the processor. The method further includes determining a position of an oldest flushed instruction entry allocated for an oldest instruction of the one or more instructions indicated to flush based on the interrupting instruction indicator, and traversing the reorder buffer in the processor in a first direction from the position of the oldest flushed instruction entry. Traversing the reorder buffer further comprises determining if a first instruction allocated to a first instruction entry in the reorder buffer in the first direction resulted in a logical register-to-physical register mapping in a map entry of a register mapping table in the processor, and in response to determining that the first instruction allocated for the first instruction entry in the reorder buffer in the first direction resulted in a logical register-to-physical register mapping in a map entry of the register mapping table in the processor, recovering the logical register-to-physical register mapping of the map entry in the register mapping table to a previous logical register-to-physical register mapping prior to the oldest instruction of the one or more instructions indicated to flush.

In another exemplary embodiment, a register renaming recover circuit in a processor is disclosed. The register renaming recover circuit is configured to receive a flush indicator indicating a flush of one or more instructions in the processor based on an interrupting instruction that caused the flush of the one or more instructions in the processor, and receive an interrupting instruction indicator indicating a position of an interrupting instruction entry allocated to the interrupting instruction in a reorder buffer in the processor. The register renaming recover circuit is further configured to determine a position of an oldest flushed instruction entry allocated for an oldest instruction of the one or more instructions indicated to flush based on the interrupting instruction indicator, and determine if a number of survivor instruction entries in the reorder buffer from an instruction entry allocated for a next older instruction than the oldest instruction of the one or more instructions indicated to flush to an oldest instruction entry in the reorder buffer allocated for an oldest uncommitted instruction is less than a number of flushed instruction entries in the reorder buffer from the oldest flushed instruction entry to a youngest instruction entry in the reorder buffer allocated for a youngest uncommitted instruction. The register renaming recover circuit is configured to, in response to determining that the number of survivor instruction entries is less than the number of flushed instruction entries, traverse the reorder buffer in the processor in a first direction from the oldest instruction entry to the instruction entry allocated to the next older instruction than the oldest instruction of the one or more instructions indicated to flush. In response to determining that the number of survivor instruction entries is not less than the number of flushed instruction entries, the register renaming recover circuit is configured to traverse the reorder buffer in the processor in the first direction from the youngest instruction entry to the oldest flushed instruction entry.

In another exemplary aspect, a method in a register renaming recover circuit is disclosed, wherein the method includes receiving a flush indicator indicating a flush of one or more instructions in the processor based on an interrupting instruction that caused the flush of the one or more instructions in the processor, and receiving an interrupting instruction indicator indicating a position of an interrupting instruction entry allocated to the interrupting instruction in a reorder buffer in the processor. The method further includes determining a position of an oldest flushed instruction entry allocated for an oldest instruction of the one or more instructions indicated to flush based on the interrupting instruction indicator, and determining if a number of survivor instruction entries in the reorder buffer from an instruction entry allocated for a next older instruction than the oldest instruction of the one or more instructions indicated to flush to an oldest instruction entry in the reorder buffer allocated for an oldest uncommitted instruction is less than a number of flushed instruction entries in the reorder buffer from the oldest flushed instruction entry to a youngest instruction entry in the reorder buffer allocated for a youngest uncommitted instruction. The method further includes, in response to determining that the number of survivor instruction entries is less than the number of flushed instruction entries, traversing the reorder buffer in the processor in a first direction from the oldest instruction entry to the instruction entry allocated to the next older instruction than the oldest instruction of the one or more instructions indicated to flush. The method still further includes, in response to determining that the number of survivor instruction entries is not less than the number of flushed instruction entries, traversing the reorder buffer in the processor in the first direction from the youngest instruction entry to the oldest flushed instruction entry.

<FIG> illustrates an instruction processing circuit <NUM> that is provided in a CPU core <NUM> in a processor <NUM> in <FIG>. The instruction processing circuit <NUM> includes one or more instruction pipelines I<NUM>-IN for processing fetched computer instructions 106F fetched by an instruction fetch circuit <NUM> for execution from a series of instructions <NUM> stored in an instruction cache memory <NUM> or instruction memory <NUM>, as examples. The instruction fetch circuit <NUM> is configured to provide fetched instructions 106F into the one or more instruction pipelines I<NUM>-IN as an instruction stream <NUM> in the instruction processing circuit <NUM> to be pre-processed before the fetched instructions 106F reach an execution circuit <NUM> to be executed. The instruction pipelines I<NUM>-IN are provided across different processing circuits or stages of the instruction processing circuit <NUM> to pre-process and process the fetched instructions 106F in a series of steps that can be performed concurrently to increase throughput prior to execution of the fetched instructions 106F by the execution circuit <NUM>.

With continuing reference to <FIG>, the instruction processing circuit <NUM> includes an instruction decode circuit <NUM> configured to decode the fetched instructions 106F fetched by the instruction fetch circuit <NUM> into decoded instructions 106D to determine the instruction type and actions required. The decoded instructions 106D are placed in one or more of the instruction pipelines I<NUM>-IN and are next provided to a rename circuit <NUM> in the instruction processing circuit <NUM> to determine if any register names in the decoded instructions 106D need to be renamed to break any register dependencies that would prevent parallel or out-of-order processing. The rename circuit <NUM> is configured to call upon a RMT <NUM> to rename a logical source register operand and/or write a destination register operand of a decoded instruction 106D to available physical registers <NUM>(<NUM>)-<NUM>(X) (P<NUM>, P<NUM>,. , PX) in a physical register file (PRF) <NUM>. The RMT <NUM> contains a plurality of mapping entries each mapped to (i.e., associated with) a respective logical register R<NUM>-RP. The mapping entries are configured to store information in the form of an address pointer to point to a physical register <NUM>(<NUM>)-<NUM>(X) in the PRF <NUM>. Each physical register <NUM>(<NUM>)-<NUM>(X) in the PRF <NUM> is configured to store a data entry for the source and/or destination register operand of a decoded instruction 106D.

The instruction processing circuit <NUM> also includes a register access (RACC) circuit <NUM> configured to access a physical register <NUM>(<NUM>)-<NUM>(X) in the PRF <NUM> based on a mapping entry mapped to a logical register R<NUM>-RP in the RMT <NUM> of a source register operand of a decoded instruction 106D to retrieve a produced value from an executed instruction 106E in the execution circuit <NUM>. Also, in the instruction processing circuit <NUM>, a scheduler circuit <NUM> is provided in the instruction pipelines I<NUM>-IN and is configured to store decoded instructions 106D in reservation entries until all source register operands for the decoded instructions 106D are available. A write circuit <NUM> is also provided in the instruction processing circuit <NUM> to write back or commit produced values from executed instructions 106E to memory, such as the PRF <NUM>, a cache memory system (not shown) or a main memory (not shown).

With continuing reference to <FIG>, the instruction processing circuit <NUM> also includes a flow control prediction circuit <NUM>. The flow control prediction circuit <NUM> is configured to speculatively predict the outcome of a condition of a fetched conditional flow control instruction 106F, such as a conditional branch instruction, that controls whether the taken or not taken path in the instruction control flow path of the instruction stream <NUM> is fetched into the instruction pipelines I<NUM>-IN for execution. In this manner, the condition of the fetched conditional flow control instruction 106F does not have to be resolved in execution by the execution circuit <NUM> before the instruction processing circuit <NUM> can continue processing speculatively fetched instructions 106F. The prediction made by the flow control prediction circuit <NUM> can be provided as prediction information <NUM> to the instruction fetch circuit <NUM> to be used by the instruction fetch circuit <NUM> to determine the next instructions <NUM> to fetch.

However, if the condition of the conditional flow control instruction 106F is determined to have been mispredicted when the conditional flow control instruction 106F is executed in the execution circuit <NUM>, the instruction 106F is interrupted. The speculatively fetched instructions 106F that were processed in the instruction processing circuit <NUM> after the conditional flow control instruction 106F are flushed because the direction of program flow is changed and will not include processing of these instructions. Load or store instructions 106F for which a calculated address of a memory location may be invalid or cannot be accessed for some other reason can also cause a flush of subsequent instructions 106F. The program flow of the instruction processing circuit <NUM> is interrupted under these conditions, and the instruction processing circuit <NUM> is returned to a previous state. The previous state to which the processor is restored depends on the type of interrupted instruction and may be a state that existed either prior to or as a result of the instruction 106F that is interrupted ("interrupting instruction"). In particular, the present disclosure is directed to recovering the previous state of the RMT <NUM> to restore logical register-to-physical register mappings that have been changed by instructions that entered the instruction processing circuit <NUM> after the interrupting instruction <NUM> ("younger instructions").

With continuing reference to <FIG>, the instruction processing circuit <NUM> also includes a ROB <NUM> containing entries ("ROB entries") <NUM> allocated to each instruction <NUM> that is being processed by the instruction processing circuit <NUM> but has not been committed. A ROB index identifies the position of each ROB entry <NUM> in the ROB <NUM>. The ROB entries <NUM> are allocated sequentially in program order to instructions <NUM>. The ROB index for each instruction <NUM> is reported back to the instruction processing circuit <NUM> when the ROB entry <NUM> is initially allocated. In this way, the instruction processing circuit <NUM> can associate a ROB index to the interrupting instruction. Information about changes to the mapping of the logical registers R<NUM>-RP as a result of an instruction <NUM> is stored in the ROB entry <NUM> corresponding to the instruction <NUM>. The ROB <NUM> includes a Read Pointer RD_PTR pointing to the ROB index of the ROB entry <NUM> from which information about the oldest uncommitted instruction <NUM> is read when it is committed. The Read Pointer RD_PTR is updated each time an uncommitted instruction <NUM> is committed. The ROB <NUM> also includes a Write Pointer WR_PTR indicating the ROB index of the last ROB entry <NUM> to which information is written about the youngest uncommitted instruction <NUM>. When an instruction <NUM> updates a logical register-to-physical register mapping of a logical register R<NUM>-RP in the RMT <NUM>, the ROB index of a ROB entry <NUM> of the instruction <NUM> is associated with that logical register R<NUM>-RP. Therefore, the ROB index corresponding to the last instruction <NUM> that updated the mapping of a logical register R<NUM>-RP is stored in the RMT <NUM> with the entry for the logical register R<NUM>-RP. As will be explained in detail below, the information stored for uncommitted instructions <NUM> in ROB entries <NUM> is used to achieve RMT recovery in response to a flush.

With continuing reference to <FIG>, the instruction processing circuit <NUM> also includes a committed map table (CMT) <NUM> which stores the logical register-to-physical register mapping of each logical register R<NUM>-RP of the processor <NUM> as a result of committed instructions <NUM>. The CMT <NUM> is only updated when an instruction <NUM> is committed. The CMT <NUM> is not changed by the recovery of the RMT <NUM> in response to a flush.

The instruction processing circuit <NUM> also includes a mapping control circuit <NUM>, which includes a register rename recover circuit (RRRC) <NUM> for controlling the RMT flush recovery. The mapping control circuit <NUM> is configured to allocate new ROB entries <NUM> to new instructions <NUM> entering the pipeline I<NUM>-IN and set the Write Pointer WR_PTR accordingly. Therefore, the ROB entries <NUM> may also be referred to herein as instruction entries <NUM>. The mapping control circuit <NUM> also deallocates an entry <NUM> when an oldest uncommitted instruction <NUM> is committed. This includes moving the Read Pointer RD_PTR to the next oldest uncommitted instruction. The RRRC <NUM> will be discussed further with reference to <FIG>.

<FIG> is an illustration of components of the instruction processing circuit <NUM> in <FIG>, including the RMT <NUM>, the ROB <NUM>, the CMT <NUM>, and the mapping control circuit <NUM>, including the RRRC <NUM>. When a flush occurs due to an interrupting instruction <NUM>, as discussed above, the instruction processing circuit <NUM> provides a flush indicator <NUM> indicating a flush of one or more instructions in the instruction processing circuit <NUM>. The instruction processing circuit <NUM> also provides the ROB index of the ROB entry <NUM> of the interrupting instruction <NUM>, which may be referred to herein as the "interrupting instruction indicator". The flush indicator <NUM> and the interrupting instruction indicator are received by the RRRC <NUM> to control the RMT flush recovery. The interrupting instruction indicator points to the ROB index of the ROB entry <NUM> of the interrupting instruction <NUM> that caused the flush. Based on the interrupting instruction indicator, an oldest flushed instruction entry, identified by an oldest flush instruction pointer (OF_PTR) indicates the oldest instruction in the ROB <NUM> that is to be flushed. In the RMT recovery, the oldest flushed instruction indicated by the oldest flushed instruction entry and any younger instructions will be flushed. The interrupting instruction <NUM> may be the oldest instruction to be flushed, depending on the instruction type of the interrupting instruction <NUM>. Alternatively, the interrupting instruction <NUM> may not be flushed, depending on the instruction type. In this case, the interrupting instruction <NUM> is the youngest surviving instruction. Any logical register-to-physical register mapping changes that resulted from a flushed instruction must be negated (i.e., undone) to restore the RMT <NUM> to the desired previous state.

With further reference to <FIG>, an example state of the RMT <NUM>, the ROB <NUM>, and the CMT <NUM> are shown. The example state shown in <FIG> is used as a starting point for the examples of RMT recovery illustrated in <FIG>, <FIG>, and 5A-5B.

The RMT <NUM> in <FIG> is illustrated as a table including a row for each logical register R<NUM>-RP with logical registers R<NUM>-R<NUM> labeled. The column entries in each row indicate, for each of the logical registers R<NUM>-R<NUM>, a logical register number (LOG), a physical register number (PHY) to which the logical register R<NUM>-R<NUM> is mapped, the ROB index (IDX) of the ROB entry <NUM> of the instruction <NUM> that resulted in the logical register-to-physical register mapping of the logical register R<NUM>-R<NUM>, and a recover indication (RCVR) used in the recovery of the RMT <NUM>. The RCVR is described further below.

The ROB <NUM> is illustrated as a table including a row for each ROB entry <NUM>. The column entries in each row indicate, for each of the ROB entries <NUM>, the ROB index (IDX) of the ROB entry <NUM>, the logical register number (LOG) of the logical register R<NUM>-RP whose mapping was changed by the instruction <NUM> associated with the ROB entry <NUM>, the new physical register (P_NEW) to which the logical register R<NUM>-RP is mapped, and the old physical register (P_OLD) to which the logical register R<NUM>-RP was previously mapped. In <FIG>, the ROB <NUM> is shown with ROB entries <NUM> having ROB indexes A-I.

The CMT <NUM> is also illustrated as a table including a row for each logical register R<NUM>-RP with logical registers R<NUM>-R<NUM> labeled. Each row has a column entry indicating the logical register number (LOG) and the corresponding physical register (PHY) to which the logical register R<NUM>-RP in the same row is mapped.

The arrowed lines in <FIG> show bidirectional flow between the mapping control circuit <NUM> and each of the RMT <NUM>, the ROB <NUM>, the CMT <NUM>, and the instruction processing circuit <NUM>. The purpose of some of these signals may be described below as needed but generally indicate flow of control signals and/or data to accomplish operations described herein. The instruction processing circuit <NUM> according to the present disclosure is not limited to the dimensions, contents or labels of the tables shown in <FIG>. The RMT <NUM>, the ROB <NUM>, and the CMT <NUM> according to the present disclosure may contain any number of rows, additional columns providing other information for each row, and different names than those illustrated in <FIG>. The entries of the RCVR column illustrated as being included in the RMT <NUM> in <FIG> may be maintained and/or stored separately from the RMT <NUM> and still provide the functions disclosed herein.

Information about any logical register-to-physical register mapping of logical registers R<NUM>-RP updated since the last committed instruction is stored in the ROB entries <NUM> in program order. The logical register-to-physical register mapping of each of the logical registers R<NUM>-RP whose mapping was updated as a result of an instruction <NUM> to be flushed must be recovered to the state of the mapping that existing at the time of the interrupting instruction <NUM>. Each entry <NUM> contains information about the logical register mapping change that resulted from the particular instruction <NUM> to which that ROB entry <NUM> is allocated. Because the information in an entry <NUM> includes both the new physical register (P_NEW) and the old physical register (P_OLD) to which a logical register R<NUM>-RP is mapped, the information from the ROB entries <NUM> can be used to negate ("undo") or recreate ("redo") the logical mapping of any logical register(s) R<NUM>-RP updated since the last committed instruction. Examples of how the ROB entries <NUM> are traversed by the RRRC <NUM> for RMT recovery are provided.

All ROB entries <NUM> having a ROB index from the oldest flushed instruction and younger may have changed the logical register-to-physical register mapping of a logical register R<NUM>-RP. Therefore, when a flush indicator <NUM> is received from the instruction processing circuit <NUM>, the ROB indexes associated with each logical register map in the RMT <NUM> are compared to the OF_PTR to identify all of the logical registers that were mapped to a new physical register as a result of an instruction that is to be flushed.

<FIG> and <FIG> illustrate an exemplary sequence of, in response to a flush indicator <NUM>, traversing the ROB entries <NUM> in the ROB <NUM> in the instruction processing circuit <NUM> of <FIG> to recover a previous state of the RMT <NUM> existing prior to the oldest flushed instruction <NUM> entering the instruction processing circuit <NUM>. The RRRC <NUM> obtains information in the ROB entries <NUM> to recover the RMT <NUM> from a state existing when the flush indicator <NUM> is received to a previous state existing at the time the oldest flushed instruction <NUM> entered the instruction processing circuit <NUM>. The CMT <NUM> is shown for reference but is unaffected by the recovery process. Respective combined states of the CMT <NUM>, RMT <NUM>, and ROB <NUM> shown in <FIG> are referred to herein as "processor states" <NUM>-<NUM>. Since the RMT recovery according to the circuits and methods disclosed herein do not change the instruction processing circuit <NUM>, it is not shown in these examples.

Beginning with processor state <NUM>, the ROB entry <NUM>(B) is allocated to the oldest uncommitted instruction, and the ROB entry <NUM>(H) is allocated to the youngest uncommitted instruction. Since none of the instructions to which ROB entries <NUM> are allocated have been committed, these instructions will be referred to as the oldest and youngest instructions in the ROB <NUM>, respectively. In processor state <NUM>, the RRRC <NUM> receives a flush indicator <NUM> indicating a flush of one or more instructions in the processor <NUM> based on an interrupting instruction <NUM> that caused the flush of the one or more instructions in the processor <NUM>. The RRRC <NUM> also receives an interrupting instruction indicator indicating the position of an interrupting instruction entry <NUM> for the interrupting instruction <NUM> in the ROB <NUM> in the processor <NUM>.

The RRRC <NUM> determines a position of an oldest flushed instruction entry OF_PTR allocated for the oldest instruction of the one or more instruction indicated to be flushed based on the interrupting instruction indicator. The oldest flushed instruction entry OF_PTR is set to point to the oldest flushed instruction. The dotted line highlighting the ROB entry <NUM>(E) is the interrupting instruction <NUM>, which is optionally flushed, depending on the type of interrupting instruction.

A traversal pointer TR_PTR, used to identify a current entry during steps of the RMT recovery, is set to the first ROB entry <NUM> of the oldest instruction to be flushed. The RRRC <NUM> traverses the ROB entries <NUM> in the ROB <NUM> in the processor <NUM> in a first direction from the position of the oldest flushed instruction entry OF_PTR. The RRRC <NUM> traverses the ROB entries <NUM> in the ROB <NUM> by determining if a first instruction allocated to the first instruction entry <NUM> in the ROB <NUM> in the first direction resulted in a logical register-to-physical register mapping in a map entry of the RMT <NUM>. Since the interrupting instruction <NUM> is not flushed in this example, the traversal pointer TR_PTR is set to point to the ROB entry <NUM>(F) for the oldest flushed instruction.

The ROB indexes associated with each of the logical registers R<NUM>-R<NUM> are compared to the ROB index F because they may have been mapped to new physical registers as a result of a flushed instruction. If any logical registers R<NUM>-R<NUM> have an associated ROB index of F or alphabetically following F, a recovery is needed. If none of the ROB indexes associated with logical registers R<NUM>-R<NUM> in the RMT <NUM> have an associated ROB index of F or alphabetically following F, no recovery is needed. Therefore, the RRRC <NUM> is configured to determine that at least one map entry in the RMT <NUM> is not recovered based on the ROB index in the at least one map entry in the RMT <NUM> corresponding to a ROB index of a ROB entry <NUM> allocated for an instruction after the interrupting instruction entry <NUM> is allocated for the one or more instructions indicated to be flushed.

In processor state <NUM>, the ROB indexes G and H indicate that mapping of the logical registers R<NUM> and R<NUM> will need to be recovered. In response to determining that at least one map entry in the RMT <NUM> is not recovered based on an index of an instruction entry <NUM> in the ROB <NUM> allocated for the one or more instructions indicated to be flushed, for each of the at least one map entry of the RMT <NUM>, the RRRC <NUM> is configured to set the recovery indicator RCVR (e.g., to "R" for recover) for logical registers R<NUM> and R<NUM> to indicate that the logical register-to-physical register mapping in the map entry needs to be recovered. Other mechanisms for tracking which of the RMT entries have been recovered or not recovered is within the scope of this disclosure. Referring to the ROB <NUM>, the ROB entries <NUM> with ROB indexes F and H show that logical register R<NUM> was mapped from old physical register P_OLD <NUM> to new physical register P_NEW <NUM> by the instruction associated with ROB index F, and then subsequently mapped to new physical register P_NEW <NUM> by the instruction associated with ROB index H. In addition, the ROB entry <NUM> with ROB index G shows that logical register R<NUM> was mapped from old physical register P_OLD <NUM> to new physical register P_NEW <NUM>.

The RMT recovery in the example shown in <FIG>, is performed by the RRRC <NUM>, which is configured to traverse the ROB entries <NUM> in the ROB <NUM> in a first direction from the position of the oldest flushed instruction entry. The RRRC <NUM> determines the position of the oldest flushed instruction entry, allocated for the oldest instruction of the one or more instructions indicated to be flushed, based on the interrupting instruction indicator, and further based on the type of the interrupting instruction <NUM>. Starting with the ROB entry <NUM>(F), the RRRC <NUM> determines if a first instruction <NUM> allocated to the first instruction entry of the ROB <NUM> in the first direction (i.e., ROB entry <NUM>(F)) resulted in a logical register-to-physical register mapping in a map entry of the RMT <NUM>. As shown, the instruction <NUM> allocated to the ROB entry <NUM>(F) resulted in a change to the mapping of logical register R<NUM>. In response to determining the first instruction <NUM> allocated to the first instruction entry (ROB entry <NUM>(F)) in the first direction resulted in a logical register-to-physical register mapping in the map entry for logical register R<NUM> in the RMT <NUM>, the RRRC <NUM> recovers the logical register-to-physical register mapping of the logical register R<NUM> in the RMT <NUM> to a previous logical register-to-physical register mapping prior to an oldest instruction of the one or more instructions indicated to be flushed.

Moving to processor state <NUM> in <FIG>, the logical register-to-physical register mapping of logical register R<NUM> in the RMT <NUM> is recovered to physical register <NUM>, based on the old physical register P_OLD value in ROB entry <NUM>(F), which is the state after the interrupting instruction <NUM> completed. In response to recovering the logical register-to-physical register mapping of the map entry in the RMT <NUM> to the previous logical register-to-physical register mapping prior to the oldest instruction of the one or more instructions indicated to be flushed, the RRRC <NUM> sets the recovery indicator RCVR for the map entry for which the logical register-to-physical register mapping is recovered to indicate that the logical register-to-physical register mapping in the recovered map entry is recovered. Thus, the RCVR associated with the logical register R<NUM> is set to indicate that the logical register R<NUM> is recovered, which further indicates to the instruction processing circuit <NUM> that logical register R<NUM> in the RMT <NUM> is available for use as the program flow proceeds in a new direction following the interrupt.

Since recovery of logical register R<NUM> based on information in the ROB entry <NUM>(F) is complete, the traversal pointer TR_PTR is set to point to the ROB entry <NUM>(G). The RRRC <NUM> will determine if a second instruction, allocated for a second ROB entry <NUM> in the ROB <NUM> in the first direction, resulted in a logical register-to-physical register mapping in a map entry of a logical register R<NUM>-R<NUM> in the RMT <NUM>. In response to such determination, the RRRC <NUM> determines if the recovery indicator RCVR for the map entry of the logical register R<NUM>-R<NUM> in the RMT <NUM> indicates that the logical register-to-physical register mapping in the map entry is not recovered. In response to determining such map entry is not recovered, the RRRC <NUM> recovers the logical register-to-physical register mapping of the map entry for the logical register R<NUM>-R<NUM> in the RMT <NUM> to the previous logical register-to-physical register mapping prior to the oldest instruction of the one or more instructions indicated to be flushed, and sets the recovery indicator RCVR to indicate that the logical register-to-physical register mapping in the map entry is recovered.

In the example in <FIG>, the RRRC <NUM> determines that the instruction allocated to ROB entry <NUM>(G) resulted in a change to the logical register-to-physical register mapping of logical register R<NUM> in the RMT <NUM>. In response, the RRRC <NUM> determines whether the recovery indicator RCVR for logical register R<NUM> in the RMT <NUM> indicates that the mapping for logical register R<NUM> needs to be recovered. As shown in processor state <NUM>, the RRRC <NUM> determines that the recovery indicator RCVR for logical register R<NUM> indicates that the mapping for logical register R<NUM> needs to be recovered, so the RRRC <NUM> recovers the state of the map entry of logical register R<NUM> in the RMT <NUM> based on the information in ROB entry <NUM>(G). Specifically, the logical register-to-physical register mapping of logical register R<NUM> is set to map logical register R<NUM> to physical register <NUM> based on the old physical register P_OLD value in ROB entry <NUM>(G), which is the state of the mapping of logical register R<NUM> after the interrupting instruction caused a change to the RMT <NUM>. This mapping recovery of logical register R<NUM> is shown in the RMT <NUM> in processor state <NUM> in <FIG>.

With reference to processor state <NUM> in <FIG>, the recovery indicator RCVR for logical register R<NUM> is set to indicate that the logical register-to-physical register mapping for logical register (<NUM>) in the RMT <NUM> is recovered. The traversal pointer TR_PTR is also moved to point to the next ROB entry <NUM>(H) in the first direction of traversal. The RRRC <NUM> determines if an instruction <NUM> allocated to the ROB entry <NUM>(H) resulted in a logical register-to-physical register mapping of a logical register R<NUM>-R<NUM> in the RMT <NUM> and, if so, determines if the recovery indicator RCVR corresponding to the logical register R<NUM>-R<NUM> in the RMT <NUM> indicates that the logical register-to-physical register mapping of the logical register R<NUM>-R<NUM> is recovered. As an alternative, the RRRC <NUM> may first determine whether any recovery indicator RCVR is set to "R" in the RMT <NUM> and, if so, then determine if an instruction <NUM> allocated to the ROB entry <NUM>(H) resulted in a logical register-to-physical register mapping of a logical register R<NUM>-R<NUM> in the RMT <NUM>. In processor state <NUM>, no recovery indicator RCVR is set to "R", meaning that no logical registers in the RMT <NUM> need to be recovered. Since the RMT recovery is complete, no further entries need to be traversed, and the Write Pointer WR_PTR is moved to point to the ROB entry <NUM> for the youngest instruction in the ROB, which is the interrupting instruction <NUM> that was not flushed. This final recovery state is shown in processor state <NUM>. The mapping control circuit <NUM> in the processor <NUM> can proceed to allocate new ROB entries <NUM> for instructions <NUM> according to the new program flow.

<FIG> and <FIG> illustrate an exemplary sequence of, in response to a flush indicator <NUM>, traversing the ROB entries <NUM> in the ROB <NUM> in the processor <NUM> of <FIG> to recover a previous state of the RMT <NUM> existing when the interrupting instruction <NUM>, which is to be flushed, entered the instruction processing circuit <NUM>. The example in <FIG> and <FIG> begins with the same processor state as the example in <FIG> and <FIG>, but differs because the interrupting instruction <NUM> in the example in <FIG> and <FIG> is flushed, whereas the interrupting instruction <NUM> in the example in <FIG> and <FIG> was not flushed. The example in <FIG> and <FIG> also differs from the example in <FIG> and <FIG> by the direction in which the ROB entries <NUM> are traversed by the RRRC <NUM> in the RMT recovery. In <FIG> and <FIG>, the ROB entries <NUM> in the ROB <NUM> are traversed from the position of the interrupting instruction <NUM> to the position of the oldest instruction associated with the ROB entry <NUM> indicated by the Read Pointer RD_PTR. Here, the oldest flushed instruction entry OF_PTR points to the ROB entry <NUM>(E), and the traversal pointer TR_PTR points to the ROB entry <NUM>(D), which is the youngest unflushed instruction in processor state <NUM> and will be the first ROB entry <NUM> traversed by the RRRC <NUM> in the RMT recovery.

The RRRC <NUM> determines that at least one map entry in the RMT <NUM> is not recovered based on comparing the ROB index associated with each map entry for logical registers R<NUM>-R<NUM> in the RMT <NUM> to the oldest flushed instruction entry OF_PTR. Since the interrupting instruction <NUM> in ROB entry <NUM> (E) is flushed in this example, the state of the RMT <NUM> in processor state <NUM> differs from the processor state <NUM> in the example in <FIG> and <FIG> in that the recovery indicator RCVR for logical register R<NUM> is set to "R" to indicate the logical register R<NUM> needs to be recovered. The recovery indicator RCVR for logical register R<NUM> is set to "R" because the interrupting instruction <NUM>, which is flushed, resulted in a logical register-to-physical register mapping change in logical register R<NUM> in the RMT <NUM>. The RRRC <NUM> traverses the first instruction entry in the traversal direction in <FIG> as described above with regard to <FIG>. In particular, in response to receiving the flush indicator <NUM>, the RRRC <NUM> determines the instruction allocated to ROB entry <NUM>(D) resulted in a logical register-to-physical register mapping in a map entry for logical register R<NUM> in the RMT <NUM>, and recovers the logical register-to-physical register mapping in the map entry of logical register R<NUM> in the RMT <NUM> to physical register <NUM>, based on the value of the new physical register P_NEW in the ROB entry <NUM>(D). As a result, the logical register R<NUM> is recovered to the state of the map entry for logical register R<NUM> existing when the interrupting instruction <NUM> entered the processor <NUM>, so the recovery indicator RCVR for logical register R<NUM> can be set to indicate the logical register R<NUM> in the RMT <NUM> is recovered.

Accordingly, in processor state <NUM>, the recovery indicator RCVR for logical register R<NUM> is no longer set to "R" in the RMT <NUM>, and the traversal pointer TR_PTR has been changed to point to the next ROB entry <NUM> in the traversing direction in this example (i.e., to ROB entry <NUM>(C)). Before proceeding, the RRRC <NUM> may check the recovery indicator RCVR for each logical register R<NUM>-R<NUM> in the RMT <NUM> to see if at least one is set to indicate that a mapping in a corresponding map entry needs to be recovered. The RRRC <NUM> determines whether the instruction allocated to ROB entry <NUM>(C) resulted in a logical register-to-physical register mapping in a map entry of the RMT <NUM>. In response to determining that the instruction allocated to ROB entry <NUM>(C) resulted in a logical register-to-physical register mapping of logical register R<NUM>, the RRRC <NUM> checks the recovery indicator RCVR for logical register R<NUM>. In response to the recovery indicator RCVR for logical register R<NUM> indicating that the logical register R<NUM> needs to be recovered, the RRRC <NUM> recovers the logical register-to-physical register mapping in the map entry of logical register R<NUM> to the physical register <NUM> based on the new physical register P_NEW value in ROB entry <NUM>(C). This is shown in processor state <NUM>. As a result, the logical register R<NUM> is recovered to the state existing when the interrupting instruction <NUM> entered the processor <NUM>, and the recovery indicator RCVR can be set to indicate that logical register R<NUM> is recovered.

Finally, proceeding in the traversing direction in the example in <FIG> and <FIG>, the RRRC <NUM> determines whether the instruction allocated to ROB entry <NUM>(B) resulted in a logical register-to-physical register mapping in a map entry of the RMT <NUM>. In response to determining that the instruction allocated to ROB entry <NUM>(B) resulted in a logical register-to-physical register mapping of logical register R<NUM>, the RRRC <NUM> checks the recovery indicator RCVR for logical register R<NUM>. In response to the recovery indicator RCVR for logical register R<NUM> indicating that the logical register R<NUM> is recovered (as shown in processor state <NUM>), no recovery is performed. Next, the RRRC <NUM> determines if the instruction in the ROB entry <NUM>(B) is the oldest uncommitted instruction for which an entry was allocated in the ROB <NUM>. ROB entry <NUM>(B) is allocated for the oldest uncommitted instruction, as indicated by the Read Pointer RD_PTR. In response to determining that the instruction in the ROB entry <NUM>(B) is the oldest uncommitted instruction, the RRRC <NUM> determines if the recovery indicator RCVR for any logical register R<NUM>-R<NUM> in the RMT <NUM> indicates that the logical register-to-physical register mapping in any map entry in the RMT <NUM> is not recovered. If any recovery indicator RCVR indicates that a map entry for any logical register R<NUM>-R<NUM> in the RMT <NUM> is not recovered, the RRRC <NUM>, for each of the map entries for which the recovery indicator RCVR indicates that the logical register-to-physical register mapping is not recovered, determines a logical register-to-physical register mapping in the CMT <NUM> for the logical register R<NUM>-R<NUM> having a mapping in the (unrecovered) map entry, and sets the logical register-to-physical register mapping in the map entry in the RMT <NUM> to the logical register-to-physical register mapping for the logical register R<NUM>-R<NUM> in the CMT <NUM>.

Restating, when the RRRC <NUM> receives the flush indicator <NUM>, the recovery indicator RCVR for a logical register R<NUM>-R<NUM> in the RMT <NUM> is set to "R" to indicate that the map entry for the logical register R<NUM>-R<NUM> needs to be recovered if the map entry for the logical register R<NUM>-R<NUM> was changed as a result of any flushed instruction. However, those logical registers R<NUM>-R<NUM> whose map entries were changed by flushed instructions may not have been changed by any of the uncommitted instructions that entered the pipeline before the interrupting instruction <NUM>. As a result, when traversing the ROB entries <NUM> in the direction in the example in <FIG> and <FIG>, and the oldest uncommitted instruction is reached, there may still be some logical registers R<NUM>-R<NUM> that need to be recovered. To accomplish this, the logical register-to-physical register mapping existing in the CMT <NUM> for such logical registers R<NUM>-R<NUM> is copied to the corresponding map entry in the RMT <NUM>.

This final step of copying map entries from the CMT <NUM> to the RMT <NUM> is not needed for traversing the ROB entries <NUM> in the direction in the example in <FIG> and <FIG>. Thus, rather than statically setting a direction for the RRRC <NUM> to traverse the ROB entries <NUM>, in some embodiments disclosed herein, the RRRC <NUM> is configured to dynamically determine a direction to minimize traversal of the ROB entries in the ROB <NUM> for recovery of the RMT <NUM>. Examples of dynamically determining the traversal direction are illustrated in <FIG>.

The starting points for the examples 500A and 500B in <FIG> differ from the previous examples in that there is no instruction allocated to the ROB entry <NUM>(H). In 500A, the interrupting instruction <NUM> is allocated to ROB entry <NUM>(D) and is flushed. Thus, the oldest flushed instruction entry OF_PTR points to the ROB entry <NUM>(D). To dynamically determine a traversal direction, the RRRC <NUM> determines a traversal direction that appears to minimize the time for traversing the ROB entries <NUM> to complete the RMT recovery. In some embodiments, the method for minimizing traversal of the ROB entries <NUM> in the ROB <NUM> is to compare the number of entries that may be traversed in each direction and select the direction in which traversal would appear to be completed in less time or with fewer entries traversed.

According to the above method, the RRRC <NUM> determines if a number of survivor ROB entries <NUM> in the ROB <NUM> from the instruction entry allocated for the next older instruction than the oldest instruction of the one or more instructions indicated to be flushed, to an oldest entry in the ROB <NUM> allocated for an oldest uncommitted instruction, is less than a number of flushed ROB entries <NUM> in the ROB <NUM> from the oldest flushed instruction entry OF_PTR to a youngest instruction entry in the ROB <NUM> allocated for a youngest uncommitted instruction.

Referring to the example 500A in <FIG>, the RRRC <NUM> compares the number of survivor ROB entries <NUM> (from ROB entry <NUM>(C) to ROB entry <NUM>(A)) and the number of flushed ROB entries <NUM> (from the ROB entry <NUM> (D)to ROB entry <NUM>(G)). In response to determining that the number of survivor ROB entries <NUM> is less than the number of flushed ROB entries <NUM>, the RRRC <NUM> traverses the ROB <NUM> in a first direction from the position of the next older instruction than the oldest instruction of the one or more instructions indicated to be flushed, to an oldest entry in the ROB <NUM> allocated for an oldest uncommitted instruction (RD_PTR).

Referring to the example 500B in <FIG>, the interrupting instruction <NUM> at ROB entry <NUM>(E) is flushed. In this example, the RRRC <NUM> determines if a number of survivor ROB entries <NUM> in the ROB <NUM> from the position of the instruction entry next to the oldest flushed instruction entry OF_PTR to the oldest uncommitted entry (Read Pointer RD_PTR) is less than a number of flushed ROB entries <NUM> in the ROB <NUM> from the position of the oldest flushed instruction entry OF_PTR to a ROB entry <NUM> in the ROB <NUM> allocated for a youngest uncommitted instruction (Write Pointer WR_PTR).

By the above method, the RRRC <NUM> would dynamically determine that the number of survivor ROB entries <NUM> from the ROB entry <NUM>(C) to the ROB entry <NUM> (A) is not less than the number of ROB flushed entries <NUM> from the ROB entry <NUM>(D) to the ROB entry <NUM>(G) and, in response, would traverse the ROB <NUM> in a direction from the position of the instruction entry next to the oldest flushed instruction OF_PTR to the ROB entry <NUM> allocated for the youngest uncommitted instruction (Read Pointer WR_PTR). If the RRRC <NUM> determines that the number of survivor ROB entries <NUM> is not less than the number of flushed ROB entries <NUM>, the RRRC <NUM> traverses the ROB <NUM> in the direction from the position of the oldest flushed instruction entry OF_PTR to the ROB entry <NUM> allocated to the youngest uncommitted instruction (Write Pointer WR_PTR).

In some embodiments, the RRRC <NUM> traverses the ROB <NUM> in the processor <NUM> in the first direction from the position of the oldest flushed instruction entry OF_PTR by traversing the ROB <NUM> in the processor <NUM> in the direction from the instruction entry allocated to the next older instruction than the oldest instruction of the one or more instructions indicated to be flushed (i.e., the oldest flushed instruction entry OF_PTR) to the oldest instruction entry.

In some embodiments, the RRRC <NUM> traverses the ROB <NUM> in the processor <NUM> in the first direction from the position of the oldest flushed instruction entry OF_PTR by traversing the ROB <NUM> in the processor <NUM> in the first direction from the oldest flushed instruction entry OF_PTR to the youngest instruction entry.

In some embodiments, the RRRC <NUM> is configured to traverse the ROB <NUM> in the processor in a second direction from the oldest flushed instruction entry OF_PTR to the youngest instruction entry by being configured to determine if a second instruction allocated to a second instruction entry in the ROB <NUM> in the second direction resulted in a logical register-to-physical register mapping in a map entry of the RMT <NUM> in the processor <NUM>. The RRRC <NUM> is configured to, in response to determining the second instruction allocated for the second instruction entry in the ROB <NUM> in the second direction resulted in a logical register-to-physical register mapping in a map entry of the RMT <NUM> in the processor <NUM>, recover the logical register-to-physical register mapping of the map entry in the RMT <NUM> to a previous logical register-to-physical register mapping prior to the oldest instruction of the one or more instructions indicated to be flushed.

<FIG> is a flowchart illustrating an exemplary process of traversing entries in the ROB in the instruction processing circuit of <FIG> in a first direction from the position of an interrupting instruction entry to recover the RMT to a previous state. The method of the register rename recover circuit includes receiving a flush indicator indicating a flush of one or more instructions in the processor based on an interrupting instruction that caused the flush of the one or more instructions in the processor (block <NUM>, <FIG>), and receiving an interrupting instruction indicator indicating a position of an interrupting instruction entry allocated to the interrupting instruction in a reorder buffer in the processor (block <NUM>, <FIG>). The method in <FIG> further includes determining a position of an oldest flushed instruction entry allocated for an oldest instruction of the one or more instructions indicated to flush based on the interrupting instruction indicator (block <NUM>, <FIG>), and traversing a reorder buffer in the processor in a first direction from the position of the oldest flushed instruction entry (block <NUM>, <FIG>). In the method in <FIG>, the traversing the reorder buffer further includes determining if a first instruction allocated to a first instruction entry in the reorder buffer in the first direction resulted in a logical register-to-physical register mapping in a map entry of a register mapping table in the processor and, in response to determining that the first instruction allocated for the first instruction entry in the reorder buffer in the first direction resulted in a logical register-to-physical register mapping in a map entry of the register mapping table in the processor (decision block <NUM>, <FIG>), the method further includes recovering the logical register-to-physical register mapping of the map entry in the register mapping table to a previous logical register-to-physical register mapping prior to the oldest instruction of the one or more instructions indicated to flush (block <NUM>, <FIG>).

<FIG> is a flowchart illustrating an exemplary process of dynamically determining a traversal direction of a ROB to minimize traversal time in a RMT recovery in the processing circuit in <FIG> and <FIG>. The method in <FIG> includes the register rename recovery circuit determining if a number of survivor instruction entries in the reorder buffer from an instruction entry allocated for a next older instruction than the oldest instruction of the one or more instructions indicated to flush to an oldest instruction entry in the reorder buffer allocated for an oldest uncommitted instruction is less than a number of flushed instruction entries in the reorder buffer from the oldest flushed instruction entry to a youngest instruction entry in the reorder buffer allocated for a youngest uncommitted instruction, and in response to determining that the number of survivor instruction entries is less than the number of flushed instruction entries (decision block <NUM>, <FIG>), traversing the reorder buffer in the processor in the first direction from the position of the oldest flushed instruction entry (block <NUM>, <FIG>), including traversing the reorder buffer in the processor in the first direction from the instruction entry allocated to the next older instruction than the oldest instruction of the one or more instructions indicated to flush to the oldest instruction entry (block <NUM>, <FIG>). Alternatively, in response to determining that the number of survivor instruction entries is not less than the number of flushed instruction entries (decision block <NUM>, <FIG>), the method includes traversing the reorder buffer in the processor in the first direction from the position of the oldest flushed instruction entry (block <NUM>, <FIG>), including traversing the reorder buffer in the processor in the first direction from the oldest flushed instruction entry to the youngest instruction entry (block <NUM>, <FIG>).

<FIG> is a block diagram of an exemplary processor-based system <NUM> that includes a processor <NUM> (e.g., a microprocessor) that includes an instruction processing circuit <NUM>. The processor-based system <NUM> can be the processor-based system <NUM> in <FIG> as an example. The instruction processing circuit <NUM> can be the instruction processing circuit <NUM> in <FIG> as an example. The processor-based system <NUM> may be a circuit or circuits included in an electronic board card, such as a printed circuit board (PCB), a server, a personal computer, a desktop computer, a laptop computer, a personal digital assistant (PDA), a computing pad, a mobile device, or any other device, and may represent, for example, a server, or a user's computer. In this example, the processor-based system <NUM> includes the processor <NUM>. The processor <NUM> represents one or more general-purpose processing circuits, such as a microprocessor, central processing unit, or the like. More particularly, the processor <NUM> may be an EDGE instruction set microprocessor, or other processor implementing an instruction set that supports explicit consumer naming for communicating produced values resulting from execution of producer instructions. The processor <NUM> is configured to execute processing logic in instructions for performing the operations and steps discussed herein. In this example, the processor <NUM> includes an instruction cache <NUM> for temporary, fast access memory storage of instructions accessible by the instruction processing circuit <NUM>. Fetched or prefetched instructions from a memory, such as from a main memory <NUM> over a system bus <NUM>, are stored in the instruction cache <NUM>. The instruction processing circuit <NUM> is configured to process instructions fetched into the instruction cache <NUM> and process the instructions for execution.

The processor <NUM> can include a register rename recover circuit <NUM> to recover a state of a register rename map table in the instruction processing circuit <NUM> in response to a flush indication indicating a flush of some instruction in an instruction pipeline due to a failed instruction. The processor <NUM> may be the processor <NUM> in any of <FIG> and <FIG>, which may be configured to minimize traversal of the reorder buffer in the register rename map table recovery.

The processor <NUM> and the main memory <NUM> are coupled to the system bus <NUM> and can intercouple peripheral devices included in the processor-based system <NUM>. As is well known, the processor <NUM> communicates with these other devices by exchanging address, control, and data information over the system bus <NUM>. For example, the processor <NUM> can communicate bus transaction requests to a memory controller <NUM> in the main memory <NUM> as an example of a slave device. Although not illustrated in <FIG>, multiple system buses <NUM> could be provided, wherein each system bus constitutes a different fabric. In this example, the memory controller <NUM> is configured to provide memory access requests to a memory array <NUM> in the main memory <NUM>. The memory array <NUM> is comprised of an array of storage bit cells for storing data. The main memory <NUM> may be a read-only memory (ROM), flash memory, dynamic random access memory (DRAM), such as synchronous DRAM (SDRAM), etc., and a static memory (e.g., flash memory, static random access memory (SRAM), etc.), as non-limiting examples.

Other devices can be connected to the system bus <NUM>. As illustrated in <FIG>, these devices can include the main memory <NUM>, one or more input device(s) <NUM>, one or more output device(s) <NUM>, a modem <NUM>, and one or more display controllers <NUM>, as examples. The input device(s) <NUM> can include any type of input device, including but not limited to input keys, switches, voice processors, etc. The output device(s) <NUM> can include any type of output device, including but not limited to audio, video, other visual indicators, etc. The modem <NUM> can be any device configured to allow exchange of data to and from a network <NUM>. The network <NUM> can be any type of network, including but not limited to a wired or wireless network, a private or public network, a local area network (LAN), a wireless local area network (WLAN), a wide area network (WAN), a BLUETOOTH™ network, and the Internet. The modem <NUM> can be configured to support any type of communications protocol desired. The processor <NUM> may also be configured to access the display controller(s) <NUM> over the system bus <NUM> to control information sent to one or more displays <NUM>. The display(s) <NUM> can include any type of display, including but not limited to a cathode ray tube (CRT), a liquid crystal display (LCD), a plasma display, etc..

The processor-based system <NUM> in <FIG> may include a set of instructions <NUM> to be executed by the processor <NUM> for any application desired according to the instructions. The instructions <NUM> may be stored in the main memory <NUM>, processor <NUM>, and/or instruction cache <NUM> as examples of a non-transitory computer-readable medium <NUM>. The instructions <NUM> may also reside, completely or at least partially, within the main memory <NUM> and/or within the processor <NUM> during their execution. The instructions <NUM> may further be transmitted or received over the network <NUM> via the modem <NUM>, such that the network <NUM> includes computer-readable medium <NUM>.

While the computer-readable medium <NUM> is shown in an exemplary embodiment to be a single medium, the term "computer-readable medium" should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that stores the one or more sets of instructions. The term "computer-readable medium" shall also be taken to include any medium that is capable of storing, encoding, or carrying a set of instructions for execution by the processing device and that causes the processing device to perform any one or more of the methodologies of the embodiments disclosed herein. The term "computer-readable medium" shall accordingly be taken to include, but not be limited to, solid-state memories, optical medium, and magnetic medium.

The embodiments disclosed herein include various steps. The steps of the embodiments disclosed herein may be formed by hardware components or may be embodied in machine-executable instructions, which may be used to cause a general-purpose or special-purpose processor programmed with the instructions to perform the steps. Alternatively, the steps may be performed by a combination of hardware and software.

The embodiments disclosed herein may be provided as a computer program product, or software, that may include a machine-readable medium (or computer-readable medium) having stored thereon instructions, which may be used to program a computer system (or other electronic devices) to perform a process according to the embodiments disclosed herein. A machine-readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes: a machine-readable storage medium (e.g., ROM, random access memory ("RAM"), a magnetic disk storage medium, an optical storage medium, flash memory devices, etc.); and the like.

Those of skill in the art will further appreciate that the various illustrative logical blocks, modules, circuits, and algorithms described in connection with the embodiments disclosed herein may be implemented as electronic hardware, instructions stored in memory or in another computer-readable medium and executed by a processor or other processing device, or combinations of both. The components of the distributed antenna systems described herein may be employed in any circuit, hardware component, integrated circuit (IC), or IC chip, as examples. Memory disclosed herein may be any type and size of memory and may be configured to store any type of information desired. To clearly illustrate this interchangeability, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. How such functionality is implemented depends on the particular application, design choices, and/or design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present embodiments.

Claim 1:
A register renaming recover circuit (<NUM>) in a processor (<NUM>, <NUM>) configured to:
receive a flush indicator indicating a flush of one or more instructions (<NUM>) in the processor (<NUM>, <NUM>) based on an interrupting instruction that caused the flush of the one or more instructions in the processor (<NUM>, <NUM>);
receive an interrupting instruction indicator indicating a position of an interrupting instruction entry allocated to the interrupting instruction in a reorder buffer (<NUM>) in the processor (<NUM>, <NUM>);
determine a position of an oldest flushed instruction entry (OF_PTR, <NUM>) allocated for an oldest instruction of the one or more instructions indicated to flush based on the interrupting instruction indicator; and
traverse the reorder buffer (<NUM>) in the processor (<NUM>, <NUM>) in a first direction wherein the first direction is either from the position of the oldest flushed instruction entry (OF_PTR, <NUM>) to an oldest instruction entry in the reorder buffer (<NUM>) or from the position of the oldest flushed instruction entry (OF_PRT, <NUM>) to a youngest instruction entry in the reorder buffer (<NUM>) by being configured to:
determine if a first instruction allocated to a first instruction entry (<NUM>) in the reorder buffer (<NUM>) in the first direction resulted in a logical register-to-physical register mapping in a map entry of a register mapping table (<NUM>) in the processor (<NUM>, <NUM>); and
in response to determining the first instruction allocated to the first instruction entry (<NUM>) in the reorder buffer (<NUM>) in the first direction resulted in a logical register-to-physical register mapping in a map entry of the register mapping table (<NUM>) in the processor (<NUM>, <NUM>) recover the logical register-to-physical register mapping of the map entry in the register mapping table (<NUM>) to a previous logical register-to-physical register mapping prior to the oldest instruction of the one or more instructions indicated to flush.