Patent Description:
One common feature of conventional modern processor devices is branch prediction, which employs mechanisms to both predict the direction of branches resulting from control flow instructions (such as conditional branch instructions), as well as enable the speculative execution of instructions on the predicted execution path. Because some branch predictions will invariably be incorrect, such branch prediction mechanisms also include hardware for recovering from the effects of speculative instruction execution resulting from mispredicted branches. To accomplish this recovery, the branch prediction mechanism must "flush" speculatively executed instructions that are younger than the mispredicted branch instruction from the execution pipeline, undo all updates performed by the speculatively executed instructions in different microarchitectural structures, and recover the original state of these structures as they existed prior to the mispredicted branch instruction. Pipeline flushes may also occur in response to other control hazards in addition to branch mispredictions. For example, an pipeline flush may have to be performed following an attempt to execute a load or store instruction for which a calculated address of a memory location is invalid or cannot be accessed.

One microarchitectural structure that is affected by flush recovery is the rename map table (RMT). The RMT, which is provided by processor devices that support register renaming, stores the most recent logical-register-to-physical-register mappings used by the processor device to establish true data dependencies. As mappings stored by the RMT may be modified by speculatively executed instructions, recovering from a flush requires each of the RMT mappings to be restored to a prior mapping state that existed when the instruction that triggered the flush ("target instruction") underwent register renaming. Restoring the RMT is a time-sensitive operation because instructions on the "correct" execution path that are fetched after the flush cannot proceed through the execution pipeline of the processor device until the RMT is restored to its prior mapping state. If the prior mapping state of the RMT is not recovered quickly enough, the processor device may be forced to stall the execution pipeline.

Existing techniques for RMT recovery may be generally classified according to the point at which the recovery process begins. Under one approach known as "lazy recovery," the recovery process does not begin until the target instruction becomes the oldest uncommitted instruction in a reorder buffer (ROB) (a queue that tracks the status of in-flight instructions in program order after register renaming). Once the target instruction is the oldest uncommitted instruction in the ROB, the RMT may be recovered simply by copying the contents of a committed mapping table (CMT) into the RMT. However, while lazy recovery is easy to implement, it can result in severely degraded processor performance in situations in which there are many older uncommitted instructions at the time the flush was initiated.

Another approach known as "immediate recovery" involves beginning the recovery process as soon as the flush is initiated. Some immediate recovery mechanisms may make use of RMT snapshots, which may be created for each branch instruction and used to restore the RMT if the corresponding branch instruction is determined to have been mispredicted. RMT snapshots may be used alone, or in conjunction with "walking" the ROB (i.e., sequentially accessing entries within the ROB between the entry for the target instruction and the point at which a snapshot of the RMT was taken, and undoing the changes made to the RMT by each corresponding instruction). Other immediate recovery techniques may involve using the contents of the CMT as a starting point, and walking the ROB from the oldest uncommitted instruction towards the target instruction while undoing the changes made by each corresponding instruction. Still another immediate recovery approach involves using the contents of the RMT as a starting point, and walking the ROB from the youngest uncommitted instruction towards the target instruction while undoing changes. Generally speaking, under each of these approaches, the performance of the immediate recovery mechanism may depend on the number of snapshots required and/or the number of instructions that need to be walked to restore the RMT's prior mapping state.

Accordingly, a mechanism for more efficiently restoring the RMT following an pipeline flush is desirable.

<CIT> describes a method and apparatus for dynamically allocating entries of microprocessor resources to particular instructions in an efficient manner to efficiently utilize buffer size and resources. The pipelined and superscalar microprocessor is capable of speculatively executing instructions and also out-of-order processing. Resources within the microprocessor include a store buffer, a load buffer, a reorder buffer and a reservation station. The reorder buffer contains a larger set of physical registers and also contains information related to speculative instructions and the reservation station comprises information related to instructions pending execution. The load buffer is only allocated to load instructions and is valid for an instruction from allocation pipestage to instruction retirement. The store buffer is only allocated to store instructions and is valid for an instruction from allocation to store performance. The reservation station is allocated to most instructions and is valid for an instruction from allocation to instruction dispatch. The reorder buffer is allocated to all instructions and is valid for a given instruction from allocation to retirement. The load buffer, store buffer, and reorder buffer are sequentially allocated while the reservation station is not. Resource allocation is performed dynamically (as needed by the operation) rather than as a full set of resources attached to each operation. Using the above allocation scheme, efficient usage of the microprocessor resources is accomplished.

<CIT> describes a reorder buffer which is configured into multiple lines of storage, wherein a line of storage includes sufficient storage for instruction results regarding a predefined maximum number of concurrently dispatchable instructions. A line of storage is allocated whenever one or more instructions are dispatched. A microprocessor employing the reorder buffer is also configured with fixed, symmetrical issue positions. The symmetrical nature of the issue positions may increase the average number of instructions to be concurrently dispatched and executed by the microprocessor. The average number of unused locations within the line decreases as the average number of concurrently dispatched instructions increases. One particular implementation of the reorder buffer includes a future file. The future file comprises a storage location corresponding to each register within the microprocessor. The reorder buffer tag (or instruction result, if the instruction has executed) of the last instruction in program order to update the register is stored in the future file. The reorder buffer provides the value (either reorder buffer tag or instruction result) stored in the storage location corresponding to a register when the register is used as a source operand for another instruction. Another advantage of the future file for microprocessors which allow access and update to portions of registers is that narrow-to-wide dependencies are resolved upon completion of the instruction which updates the narrower register.

Exemplary embodiments disclosed herein include performing flush recovery using parallel walks of sliced reorder buffers (SROBs). In this regard, in one exemplary embodiment, a processor device includes a register mapping circuit that provides a rename mapping table (RMT). The RMT includes a plurality of RMT entries, each of which represents a mapping of a logical register number (LRN) to a physical register number (PRN). The register mapping circuit also provides an SROB, which includes a plurality of SROB slices. Each SROB slice corresponds to a respective LRN, and includes a plurality of SROB slice entries. Each SROB slice is similar in functionality to a conventional reorder buffer (ROB), except that the SROB slice tracks only uncommitted instructions that write to the LRN corresponding to that SROB slice, and maintains those instructions in program order only with respect to each other. In exemplary operation, the register mapping circuit, upon detecting an uncommitted instruction writing to an LRN in an execution pipeline of the processor device, allocates an SROB slice entry for the uncommitted instruction in the SROB slice corresponding to the LRN. If the register mapping circuit subsequently receives an indication of an pipeline flush from a target instruction within the execution pipeline, the register mapping circuit restores the plurality of RMT entries of the RMT to their prior mapping states based on parallel walks of the SROB slices of the SROB. Because the walks of the SROB slices are performed in parallel, and because each SROB slice is likely to contain fewer instructions than a conventional ROB, flush recovery may be accomplished more efficiently than conventional approaches.

In some embodiments, a count of the SROB slice entries within each SROB slice may be the same size as a count of ROB entries in a ROB provided by the register mapping circuit, or may be smaller than the count of the ROB entries in the ROB. In the latter case, if the register mapping circuit needs to allocate an SROB slice entry to an uncommitted instruction but no SROB slice entries are available within the appropriate SROB slice, the register mapping circuit in some embodiments may initiate a stall of the execution pipeline, causing it to stall until an SROB slice entry becomes available within the SROB slice. Some embodiments may provide that, instead of initiating a stall of the execution pipeline, the register mapping circuit may allocate the oldest SROB slice entry for the uncommitted instruction. Subsequently, if the register mapping circuit determines that the overwritten contents of the oldest SROB slice entry are necessary for flush recovery, the register mapping circuit may perform a walk of the ROB. Similarly, some embodiments may provide a partially serial ROB (PSROB) to which the oldest SROB slice entry may be evicted before being allocated for the uncommitted instruction. In such embodiments, if the register mapping circuit determines that the overwritten contents of the evicted oldest SROB slice entry are necessary for flush recovery, the register mapping circuit may perform a walk of the PSROB.

In another exemplary embodiment, a register mapping circuit in a processor device is provided. The register mapping circuit includes an RMT comprising a plurality of RMT entries each representing a mapping of an LRN among a plurality of LRNs to a PRN among a plurality of PRNs. The register mapping circuit further includes an SROB subdivided into a plurality of SROB slices each corresponding to a respective LRN among the plurality of LRNs, and each comprising a plurality of SROB slice entries. The register mapping circuit is configured to detect, within an execution pipeline of the processor device, an uncommitted instruction comprising a write instruction to a destination LRN among the plurality of LRNs. The register mapping circuit is further configured to allocate, to the uncommitted instruction, an SROB slice entry among the plurality of SROB slice entries of an SROB slice corresponding to the destination LRN among the plurality of SROB slices of the SROB. The register mapping circuit is also configured to receive an indication of an pipeline flush from a target instruction within the execution pipeline. The register mapping circuit is additionally configured to, responsive to receiving the indication of the pipeline flush, restore the plurality of RMT entries to a corresponding plurality of prior mapping states, based on parallel walks of the plurality of SROB slices corresponding to LRNs of the plurality of RMT entries.

In another exemplary embodiment, a method for performing flush recovery using parallel walks of SROBs is provided. The method includes detecting, by a register mapping circuit of a processor device, an uncommitted instruction within an execution pipeline of the processor device, the uncommitted instruction comprising a write instruction to a destination LRN among a plurality of LRNs. The method further includes allocating, to the uncommitted instruction, an SROB slice entry among a plurality of SROB slice entries of an SROB slice corresponding to the destination LRN among a plurality of SROB slices of an SROB of the processor device, wherein each SROB slice of the plurality of SROB slices corresponds to a respective LRN among the plurality of LRNs. The method also includes receiving an indication of an pipeline flush from a target instruction within the execution pipeline. The method additionally includes, responsive to receiving the indication of the pipeline flush, restoring a plurality of RMT entries of an RMT to a corresponding plurality of prior mapping states, based on parallel walks of the plurality of SROB slices corresponding to LRNs of the plurality of RMT entries.

In another exemplary embodiment, a non-transitory computer-readable medium is provided. The non-transitory computer-readable medium stores computer-executable instructions that, when executed by a processor device, cause the processor device to detect an uncommitted instruction within an execution pipeline of the processor device, the uncommitted instruction comprising a write instruction to a destination LRN among a plurality of LRNs. The computer-executable instructions further cause the processor device to allocate, to the uncommitted instruction, an SROB slice entry among a plurality of SROB slice entries of an SROB slice corresponding to the destination LRN among a plurality of SROB slices of an SROB of the processor device, wherein each SROB slice of the plurality of SROB slices corresponds to a respective LRN among the plurality of LRNs. The computer-executable instructions also cause the processor device to receive an indication of an pipeline flush from a target instruction within the execution pipeline. The computer-executable instructions additionally cause the processor device to, responsive to receiving the indication of the pipeline flush, restore a plurality of RMT entries of an RMT to a corresponding plurality of prior mapping states, based on parallel walks of the plurality of SROB slices corresponding to LRNs of the plurality of RMT entries.

Those skilled in the art will appreciate the scope of the present disclosure and realize additional embodiments thereof after reading the following detailed description of the preferred embodiments in association with the accompanying drawing figures.

The accompanying drawing figures incorporated in and forming a part of this specification illustrate several embodiments of the disclosure, and together with the description serve to explain the principles of the disclosure.

In some embodiments, a count of the SROB slice entries within each SROB slice may be the same size as a count of ROB entries in a ROB provided by the register mapping circuit, or may be smaller than the count of the ROB entries in the ROB. In the latter case, if the register mapping circuit needs to allocate an SROB slice entry to an uncommitted instruction but no SROB slice entries are available within the appropriate SROB slice, the register mapping circuit in some embodiments may initiate a stall of the execution pipeline, causing it to stall until an SROB slice entry becomes available within the SROB slice. Some embodiments may provide that, instead of initiating a stall of the execution pipeline, the register mapping circuit may allocate the oldest SROB slice entry for the uncommitted instruction. Subsequently, if the register mapping circuit determines that overwritten contents of the oldest SROB slice entry are necessary for flush recovery, the register mapping circuit may perform a walk of the ROB. Similarly, some embodiments may provide a partially serial ROB (PSROB) to which the oldest SROB slice entry may be evicted before being allocated for the uncommitted instruction. In such embodiments, if the register mapping circuit determines that the overwritten contents of the evicted oldest SROB slice entry are necessary for flush recovery, the register mapping circuit may perform a walk of the PSROB.

In this regard, <FIG> illustrates an exemplary processor-based device <NUM> that provides a processor device <NUM> for processing executable instructions. The processor device <NUM> in some embodiments may be one of a plurality of processor devices of the processor-based device <NUM>. The processor device <NUM> of <FIG> includes an execution pipeline <NUM> comprising circuitry configured to perform execution of an instruction stream <NUM> comprising computer-executable instructions. In the example of <FIG>, the execution pipeline <NUM> includes a fetch circuit <NUM> that is configured to fetch the instruction stream <NUM> of executable instructions from an instruction memory <NUM>. The instruction memory <NUM> may be provided in or as part of a system memory (not shown) of the processor-based device <NUM>, as a non-limiting example. An instruction cache <NUM> may also be provided in the processor device <NUM> to cache instructions fetched from the instruction memory <NUM> to reduce latency in the fetch circuit <NUM>. The fetch circuit <NUM> in the example of <FIG> is configured to provide instructions into one or more instruction pipelines I<NUM>-IN to be preprocessed before the instructions reach an execution circuit ("EXEC CIRCUIT") <NUM> to be executed. The instruction pipelines I<NUM>-IN are provided across different processing circuits (or "stages") of the execution pipeline <NUM> to concurrently process fetched instructions to increase throughput prior to execution of the fetched instructions in the execution circuit <NUM>.

The execution pipeline <NUM> of <FIG> additionally includes a decode circuit <NUM> that is configured to decode instructions fetched by the fetch circuit <NUM> into decoded instructions to determine the instruction type and actions required, and further to determine into which instruction pipeline I<NUM>-IN the decoded instructions should be placed. The decoded instructions are then placed into one or more of the instruction pipelines I<NUM>-IN, and are next provided to a rename circuit <NUM>. The rename circuit <NUM> determines whether any register names in decoded instructions should be renamed to avoid register dependencies that could prevent parallel or out-of-order processing of instructions.

The rename circuit <NUM> is configured to call upon a rename map table (RMT) <NUM>, provided by a register mapping circuit <NUM>, to rename a logical source register operand and/or a logical destination register operand of a decoded instruction to correspond to one of a plurality of physical registers <NUM>(<NUM>)-<NUM>(P) (each corresponding to one of a plurality of physical register numbers (PRNs) (PRN<NUM>, PRN<NUM>,. PRNP) in a physical register file (PRF) <NUM>. Each of the physical registers <NUM>(<NUM>)-<NUM>(P) in the PRF <NUM> is configured to store data for a source register operand and/or a destination register operand of a decoded instruction. The RMT <NUM> contains a plurality of RMT entries <NUM>(<NUM>)-<NUM>(L), each of which corresponds to a respective one of a plurality of logical register numbers (LRNs) LRN<NUM>-LRNL. The RMT entries <NUM>(<NUM>)-<NUM>(L) are configured to store information in the form of an address pointer to a physical register of the plurality of physical registers <NUM>(<NUM>)-<NUM>(P) in the PRF <NUM>. In some embodiments, the RMT entries <NUM>(<NUM>)-<NUM>(L) are also associated with respective program order identifiers <NUM>(<NUM>)-<NUM>(L), each of which provides an indication of the program order location of the instruction that caused the logical-register-to-physical-register mapping represented by the RMT entries <NUM>(<NUM>)-<NUM>(L) to be created. In the event of a flush, the program order identifiers <NUM>(<NUM>)-<NUM>(L) may be used to determine which of the RMT entries <NUM>(<NUM>)-<NUM>(L) were updated by speculatively executed instructions older than a target instruction, and thus should be restored to a prior mapping state.

The execution pipeline <NUM> of <FIG> also includes a register access circuit ("RACC CIRCUIT") <NUM> that is configured to access one of the physical registers <NUM>(<NUM>)-<NUM>(P) in the PRF <NUM> named by a mapping entry of the RMT entries <NUM>(<NUM>)-<NUM>(L) corresponding to one of the logical register numbers LRN<NUM>-LRNL indicated as a source register operand of a decoded instruction. The RACC circuit <NUM> retrieves a value in the PRF <NUM> produced by a previously executed instruction in the execution circuit <NUM>. The execution pipeline <NUM> further provides a scheduler circuit ("SCHED CIRCUIT") <NUM> that is configured to store decoded instructions in reservation entries (not shown) until all source register operands for the decoded instructions are available. Additionally, a write circuit <NUM> is provided in the execution pipeline <NUM> to write back (i.e., commit) produced values from executed instructions to memory, such as the PRF <NUM>, a data cache memory system (not shown), or a main memory (not shown). It is to be understood that, in some embodiments, elements of the execution pipeline <NUM> may be provided in a different configuration or order than shown in <FIG>. For example, according to some embodiments, the register access circuit <NUM> may follow the scheduler circuit <NUM> within the execution pipeline <NUM> rather than preceding the scheduler circuit <NUM> as shown in <FIG>.

Also provided by the execution pipeline <NUM> of <FIG> is a branch prediction circuit <NUM>. The branch prediction circuit <NUM> is configured to speculatively predict the outcome of a condition of a fetched conditional flow control instruction (not shown), such as a conditional branch instruction, that controls which path in the instruction control flow path of the instruction stream <NUM> is fetched into the instruction pipelines I<NUM>-IN for execution. With accurate speculative prediction methods, the condition of the fetched conditional flow control instruction does not have to be resolved in execution by the execution circuit <NUM> before the execution pipeline <NUM> can continue processing speculatively fetched instructions.

However, if the condition of the conditional flow control instruction is determined to have been mispredicted when the conditional flow control instruction is executed in the execution circuit <NUM>, the speculatively fetched instructions following the mispredicted conditional flow instruction (i.e., the target instruction) in the execution pipeline <NUM> are flushed, because the direction of program flow is not as predicted and will not include processing of those speculatively fetched instructions. When a flush occurs (e.g., as a result of branch misprediction), the register mapping circuit <NUM> is configured to restore a prior mapping state (i.e., logical-register-to-physical-register mapping for each of the RMT entries <NUM>(<NUM>)-<NUM>(L) of the RMT <NUM>) that may have been changed by instructions that entered the instruction pipelines I<NUM>-IN of the execution pipeline <NUM> after the target instruction.

To facilitate restoring the prior mapping state of the RMT <NUM>, the register mapping circuit <NUM> provides a reorder buffer (ROB) <NUM> containing a plurality of ROB entries <NUM>(<NUM>)-<NUM>(R) that are allocated to "in-flight" instructions that are being processed by the execution pipeline <NUM> but have not been committed (i.e., "uncommitted instructions"). The ROB entries <NUM>(<NUM>)-<NUM>(R) are allocated sequentially in program order to uncommitted instructions. Information about changes to the mapping of the logical register numbers LRN<NUM>-LRNL by the RMT <NUM> (i.e., "register mapping information") by an instruction is stored in association with each ROB entry <NUM>(<NUM>)-<NUM>(R) allocated to the instruction. The register mapping information stored by the RMT <NUM> for uncommitted instructions may be used according to conventional techniques to achieve recovery in response to a flush. The register mapping circuit <NUM> of <FIG> also includes a committed map table (CMT) <NUM> providing a plurality of mapping entries <NUM>(<NUM>)-<NUM>(L) in which the logical-register-to-physical-register mapping resulting from committed instructions are stored. The CMT <NUM> is only updated when an instruction is committed, and consequently is not changed in response to a flush.

As noted above, conventional techniques for restoring the RMT <NUM> to a prior mapping state following a flush, including lazy recovery and immediate recovery techniques, may be inefficient in circumstances involving a large number of older uncommitted instructions at the time of the flush. Accordingly, exemplary embodiments disclosed herein provide a sliced ROB (SROB) <NUM>. The SROB <NUM> is subdivided into a plurality of SROB slices ("SLICE") <NUM>(<NUM>)-<NUM>(L), each comprising a plurality of SROB slice entries such as SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X). Each of the SROB slices <NUM>(<NUM>)-<NUM>(L ) functions in a manner similar to the ROB <NUM>, except that each SROB slice <NUM>(<NUM>)-<NUM>(L) corresponds to a respective one of the plurality of LRNs LRN<NUM>-LRNL, and tracks only uncommitted instructions that write to a destination LRN corresponding to that SROB slice <NUM>(<NUM>)-<NUM>(L). For example, the SROB slice <NUM>(<NUM>) in the example of <FIG> corresponds to LRN<NUM>, and thus tracks uncommitted instructions that comprise a write instruction to the destination LRN LRN<NUM>. The SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) store the same data for their respective uncommitted instructions as the ROB entries <NUM>(<NUM>)-<NUM>(R), and are allocated sequentially in program order with respect to other SROB slice entries within the same SROB slice <NUM>(<NUM>)-<NUM>(L).

In exemplary operation, the register mapping circuit <NUM>, upon detecting an uncommitted instruction writing to a destination LRN in the execution pipeline <NUM>, allocates one of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) for the uncommitted instruction in the SROB slice <NUM>(<NUM>)-<NUM>(L) corresponding to the destination LRN. If the register mapping circuit <NUM> subsequently receives an indication of an pipeline flush from a target instruction within the execution pipeline <NUM>, the register mapping circuit <NUM> restores the plurality of RMT entries <NUM>(<NUM>)-<NUM>(L) of the RMT <NUM> to their prior mapping states based on parallel walks of the SROB slices <NUM>(<NUM>)-<NUM>(L) of the SROB <NUM>. For example, the register mapping circuit <NUM> may perform a walk of each of the SROB slices <NUM>(<NUM>)-<NUM>(L) in parallel by accessing SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) corresponding to uncommitted instructions younger than a target instruction that caused a flush, and using the data stored in each of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) to undo the changes made by the uncommitted instructions to the RMT entries <NUM>(<NUM>)-<NUM>(L) corresponding to the LRN for each SROB slice <NUM>(<NUM>)-<NUM>(L). Because the walks of the SROB slices <NUM>(<NUM>)-<NUM>(L) are performed in parallel, and because each of the SROB slices <NUM>(<NUM>)-<NUM>(L) is likely to contain fewer instructions than the ROB <NUM>, flush recovery may be accomplished more efficiently than conventional approaches.

In some embodiments, the count of each of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) may be the same as the count of the ROB entries <NUM>(<NUM>)-<NUM>(R) (i.e., X=R). Such embodiments may offer improved performance, because the SROB slices <NUM>(<NUM>)-<NUM>(L) are sized large enough to handle situations in which every uncommitted write instruction in the ROB <NUM> targets the same destination LRN among the plurality of LRNs LRN<NUM>-LRNL. However, the improved performance comes at the cost of increased processor resources needed to implement the SROB <NUM>.

Other embodiments may provide that the count of each of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) may be less than the count of the ROB entries <NUM>(<NUM>)-<NUM>(R) (i.e., X<R). In such embodiments, the register mapping circuit <NUM> provides special handling for circumstances in which none of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) are available for allocation to a new uncommitted instruction. According to some embodiments, if none of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) are available for allocation, the register mapping circuit <NUM> may initiate a stall of the execution pipeline <NUM> until one of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) within the appropriate SROB slice <NUM>(<NUM>)-<NUM>(L) becomes available for allocation. Once the stall is resolved (i.e., when one of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) becomes available), the register mapping circuit <NUM> then allocates one of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) within the appropriate SROB slice <NUM>(<NUM>)-<NUM>(L).

In some embodiments, in response to determining that none of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) are available for allocation, the register mapping circuit <NUM> may overwrite an oldest SROB slice entry <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) for the new uncommitted instruction. If the register mapping circuit <NUM> later determines that the overwritten contents of the oldest SROB slice entry <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) are necessary for flush recovery, the register mapping circuit <NUM> may perform a walk of the ROB <NUM> in conventional fashion to restore the RMT entries <NUM>(<NUM>)-<NUM>(L) of the RMT <NUM> to a prior mapping state. Because performing a walk of the ROB <NUM> may incur the same performance penalties as conventional mechanisms for flush recovery, the register mapping circuit <NUM> in some embodiments may provide a partially serial ROB (PSROB) <NUM> comprising a plurality of PSROB entries <NUM>(<NUM>)-<NUM>(P). The PSROB <NUM> in such embodiments functions in a manner similar to the ROB <NUM>, but allocates PSROB entries <NUM>(<NUM>)-<NUM>(P) only to store SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) that are evicted from the SROB slices <NUM>(<NUM>)-<NUM>(L) if there are no free SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) to allocate for the new uncommitted instruction. If the register mapping circuit <NUM> later determines that the overwritten contents of the oldest SROB slice entry <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) are necessary for flush recovery, the register mapping circuit <NUM> may perform a walk of the PSROB <NUM> to restore the RMT entries <NUM>(<NUM>)-<NUM>(L) of the RMT <NUM> to a prior mapping state.

To illustrate exemplary contents of the ROB <NUM> and the SROB <NUM> of <FIG> according to some embodiments, <FIG> is provided. In <FIG>, the register mapping circuit <NUM>, the ROB <NUM>, and the SROB <NUM> of <FIG> are shown. The ROB <NUM> includes the ROB entries <NUM>(<NUM>)-<NUM>(<NUM>), each of which corresponds to the uncommitted instructions I<NUM>-I<NUM>. The instructions I<NUM>-I<NUM> include instructions that write to destination LRNs LRN<NUM> and LRNi, which in the example of <FIG> correspond to the SROB slices <NUM>(<NUM>) and <NUM>(<NUM>), respectively, of <FIG>. In exemplary operation, the register mapping circuit <NUM> detects the uncommitted instructions I<NUM>-I<NUM> (e.g., in the execution pipeline <NUM> of <FIG>), and allocates the ROB entries <NUM>(<NUM>)-<NUM>(<NUM>) for the uncommitted instructions I<NUM>-I<NUM> respectively. For the instructions I<NUM>, I<NUM>, I<NUM>, and I<NUM>, the register mapping circuit <NUM> also allocates SROB slice entries <NUM>(<NUM>), <NUM>(<NUM>), <NUM>(<NUM>), and <NUM>(<NUM>), respectively.

During execution of the instructions I<NUM>-I<NUM>, a target instruction I<NUM> fails to execute as expected (e.g., because the target instruction I<NUM> is determined to be a mispredicted branch instruction, or because the target instruction I<NUM> is a load or store instruction for which a calculated address of a memory location may be invalid or cannot be accessed). An pipeline flush is triggered, causing the register mapping circuit <NUM> to receive an indication <NUM> of the pipeline flush from the target instruction I<NUM>. The pipeline flush results in all instructions younger than the target instruction I<NUM> (i.e., instructions I<NUM>-I<NUM>) being flushed from the execution pipeline <NUM>, and requires that the RMT <NUM> of <FIG> be restored to a prior mapping state corresponding to the state the RMT <NUM> was in when execution of the target instruction I<NUM> was attempted.

Instead of walking the ROB <NUM> in conventional fashion to restore the RMT <NUM>, the register mapping circuit <NUM> performs parallel walks of the SROB slices <NUM>(<NUM>) and <NUM>(<NUM>) to identify SROB slice entries that correspond to any of the flushed instructions I<NUM>-I<NUM> and to undo any mapping changes made to the RMT <NUM> by the flushed instructions I<NUM>-I<NUM>. In the example of <FIG>, the parallel walks of the SROB slices <NUM>(<NUM>) and <NUM>(<NUM>) result in the register mapping circuit <NUM> identifying SROB slice entries <NUM>(<NUM>) and <NUM>(<NUM>) as corresponding to instructions I<NUM> and I<NUM>, the uncommitted instructions that are younger than the target instruction I<NUM> and that modified mappings in the RMT <NUM>. The register mapping circuit <NUM> then uses the data in the SROB slice entries <NUM>(<NUM>) and <NUM>(<NUM>) to restore RMT entries corresponding to LRN<NUM> and LRN<NUM> in the RMT <NUM> (e.g., the RMT entries <NUM>(<NUM>) and <NUM>(<NUM>) in <FIG>) to a prior mapping state.

In some examples, the register mapping circuit <NUM> may employ the program order identifiers <NUM>(<NUM>)-<NUM>(L) of the RMT entries <NUM>(<NUM>)-<NUM>(L) to determine which of the LRNs LRN<NUM>-LRNL need to be restored to a prior mapping state. For example, the register mapping circuit <NUM> may determine, based on the program order identifiers <NUM>(<NUM>)-<NUM>(L), that a mapping state of one of the RMT entries <NUM>(<NUM>)-<NUM>(L) was modified by an uncommitted instruction older than the target instruction I<NUM>. The register mapping circuit <NUM> may then optimize the restoration of the RMT <NUM> by not performing a walk of the SROB slice <NUM>(<NUM>)-<NUM>(L) that corresponds to the LRN of that particular RMT entry.

<FIG> provides a flowchart <NUM> illustrating exemplary operations of the register mapping circuit <NUM> of <FIG> for performing flush recovery using parallel walks of the SROB <NUM> of <FIG>, according to some embodiments. Elements of <FIG> and <FIG> are referenced in describing <FIG> for the sake of clarity. In <FIG>, operations begin with the register mapping circuit <NUM> of the processor device <NUM> detecting an uncommitted instruction, such as the instruction I<NUM> of <FIG>, within the execution pipeline <NUM> of the processor device <NUM>, the uncommitted instruction I<NUM> comprising a write instruction to a destination LRN LRN<NUM> among a plurality of LRNs LRN<NUM>-LRNL (block <NUM>). The register mapping circuit <NUM> allocates, to the uncommitted instruction I<NUM>, an SROB slice entry <NUM>(<NUM>) among the plurality of SROB slice entries <NUM>(<NUM>)-<NUM>(X) of an SROB slice <NUM>(<NUM>) corresponding to the destination LRN LRN<NUM> among the plurality of SROB slices <NUM>(<NUM>)-<NUM>(L) of the SROB <NUM> of the processor device <NUM>, wherein each SROB slice of the plurality of SROB slices <NUM>(<NUM>)-<NUM>(L) corresponds to a respective LRN among the plurality of LRNs LRN<NUM>-LRNL (block <NUM>). In some embodiments, the register mapping circuit <NUM> also allocates the plurality of ROB entries <NUM>(<NUM>)-<NUM>(R) of the ROB <NUM> to a corresponding plurality of uncommitted instructions (such as the instructions I<NUM>-I<NUM> of <FIG>) in the execution pipeline <NUM> of the processor device <NUM>, wherein the plurality of uncommitted instructions I<NUM>-I<NUM> comprises the uncommitted instruction I<NUM> (block <NUM>).

The register mapping circuit <NUM> then receives the indication <NUM> of an pipeline flush from the target instruction I<NUM> within the execution pipeline <NUM> (block <NUM>). In response, the register mapping circuit <NUM> restores the plurality of RMT entries <NUM>(<NUM>)-<NUM>(L) of the RMT <NUM> to a corresponding plurality of prior mapping states, based on parallel walks of the plurality of SROB slices <NUM>(<NUM>)-<NUM>(L) corresponding to LRNs of the plurality of RMT entries <NUM>(<NUM>)-<NUM>(L) (block <NUM>). In some embodiments, the register mapping circuit <NUM> may restore the plurality of RMT entries <NUM>(<NUM>)-<NUM>(L) to the corresponding plurality of prior mapping states further based on the plurality of program order identifiers <NUM>(<NUM>)-<NUM>(L) of the plurality of RMT entries <NUM>(<NUM>)-<NUM>(L) (block <NUM>).

To illustrate exemplary operations of the register mapping circuit <NUM> of <FIG> for allocating new SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) according to some embodiments, <FIG> provides a flowchart <NUM>. For the sake of clarity, elements of <FIG> are referenced in describing <FIG>. In <FIG>, it is assumed that the count of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) of the SROB <NUM> of <FIG> is less than the count of the ROB entries <NUM>(<NUM>)-<NUM>(R) of the ROB <NUM> of <FIG>. In <FIG>, operations begin with the register mapping circuit <NUM> determining whether an SROB slice entry among the plurality of SROB slice entries <NUM>(<NUM>)-<NUM>(X) of an SROB slice (e.g., the SROB slice <NUM>(<NUM>)) is available for allocation (block <NUM>). If so, the register mapping circuit <NUM> allocates an SROB slice entry, such as the SROB slice entry <NUM>(<NUM>) (block <NUM>).

However, if the register mapping circuit <NUM> determines at decision block <NUM> that no SROB slice entries are available for allocation, the register mapping circuit <NUM> initiates a stall of the execution pipeline <NUM> of the processor device <NUM> (block <NUM>). Once the stall has been resolved (i.e., by one of the SROB slice entries <NUM>(<NUM>)-<NUM>(X) becoming available for allocation), the register mapping circuit <NUM> allocates an SROB slice entry, such as the SROB slice entry <NUM>(<NUM>) (block <NUM>).

<FIG> provides a flowchart <NUM> illustrating exemplary operations of the register mapping circuit <NUM> of <FIG> for allocating new SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) in embodiments that evict old entries to the ROB <NUM> of <FIG>. Elements of <FIG> are referenced in describing <FIG> for the sake of clarity. It is assumed in <FIG> that the count of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) of the SROB <NUM> of <FIG> is less than the count of the ROB entries <NUM>(<NUM>)-<NUM>(R) of the ROB <NUM> of <FIG>. Operations in <FIG> begin with the register mapping circuit <NUM> determining whether an SROB slice entry among the plurality of SROB slice entries <NUM>(<NUM>)-<NUM>(X) of an SROB slice (e.g., the SROB slice <NUM>(<NUM>)) is available for allocation (block <NUM>). If so, the register mapping circuit <NUM> allocates an SROB slice entry, such as the SROB slice entry <NUM>(<NUM>) (block <NUM>).

However, if the register mapping circuit <NUM> determines at decision block <NUM> that no SROB slice entries are available for allocation, the register mapping circuit <NUM> allocates an oldest SROB slice entry, such as the SROB slice entry <NUM>(<NUM>) (block <NUM>). Subsequently, the register mapping circuit <NUM>, in the course of performing flush recovery, determines whether the overwritten contents of the oldest SROB slice entry <NUM>(<NUM>) are necessary for flush recovery (block <NUM>). For example, the register mapping circuit <NUM> may determine that the oldest of the remaining SROB slice entries <NUM>(<NUM>)-<NUM>(X) of the SROB slice <NUM>(<NUM>) corresponds to an instruction that follows the target instruction in program order. If the overwritten contents of the oldest SROB slice entry <NUM>(<NUM>) are determined to be necessary for flush recovery, the register mapping circuit restores the plurality of RMT entries <NUM>(<NUM>)-<NUM>(L) to the corresponding plurality of prior mapping states further based on a walk of the ROB <NUM> (block <NUM>). Otherwise, processing continues as described in embodiments disclosed herein (block <NUM>).

To illustrate exemplary operations of the register mapping circuit <NUM> of <FIG> for allocating new SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) in embodiments that evict old entries to the PSROB <NUM> of <FIG>, <FIG> provides a flowchart <NUM>. For the sake of clarity, elements of <FIG> are referenced in describing <FIG>. It is assumed in <FIG> that the count of the SROB slice entries <NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X) of the SROB <NUM> of <FIG> is less than the count of the ROB entries <NUM>(<NUM>)-<NUM>(R) of the ROB <NUM> of <FIG>. In <FIG>, operations begin with the register mapping circuit <NUM> determining whether an SROB slice entry among the plurality of SROB slice entries <NUM>(<NUM>)-<NUM>(X) of an SROB slice (e.g., the SROB slice <NUM>(<NUM>)) is available for allocation (block <NUM>). If so, the register mapping circuit <NUM> allocates an SROB slice entry, such as the SROB slice entry <NUM>(<NUM>) (block <NUM>).

However, if the register mapping circuit <NUM> determines at decision block <NUM> that no SROB slice entries are available for allocation, the register mapping circuit <NUM> evicts an oldest SROB slice entry, such as the SROB slice entry <NUM>(<NUM>), of the plurality of SROB slice entries <NUM>(<NUM>)-<NUM>(X) of the SROB slice <NUM>(<NUM>) to the PSROB <NUM> (block <NUM>). The register mapping circuit <NUM> then allocates the oldest SROB slice entry <NUM>(<NUM>) (block <NUM>). The register mapping circuit <NUM> later determines, in the course of performing flush recovery, whether the overwritten contents of the evicted oldest SROB slice entry <NUM>(<NUM>) are necessary for flush recovery (block <NUM>). If so, the register mapping circuit restores the plurality of RMT entries <NUM>(<NUM>)-<NUM>(L) to the corresponding plurality of prior mapping states further based on a walk of the PSROB <NUM> (block <NUM>). Otherwise, processing continues as described in embodiments disclosed herein (block <NUM>).

<FIG> is a block diagram of an exemplary processor-based device <NUM>, such as the processor-based device <NUM> of <FIG>, that provides exception stack management using stack panic fault exceptions. The processor-based device <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 device <NUM> includes a processor <NUM>. The processor <NUM> represents one or more general-purpose processing circuits, such as a microprocessor, central processing unit, or the like, and may correspond to the processor device <NUM> of <FIG>. 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 and an instruction processing circuit <NUM>. Fetched or prefetched instructions from a memory, such as from a system 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> and the system memory <NUM> are coupled to the system bus <NUM> and can intercouple peripheral devices included in the processor-based device <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 system memory <NUM> as an example of a peripheral 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 system memory <NUM>. The memory array <NUM> is comprised of an array of storage bit cells for storing data. The system 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 system memory <NUM>, one or more input device(s) <NUM>, one or more output device(s) <NUM>, a modem <NUM>, and one or more display controller(s) <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 display(s) <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 device <NUM> in <FIG> may include a set of instructions <NUM> that may be encoded with the reach-based explicit consumer naming model to be executed by the processor <NUM> for any application desired according to the instructions. The instructions <NUM> may be stored in the system memory <NUM>, the processor <NUM>, and/or the 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 system 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 the 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 store the one or more sets of instructions <NUM>. 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 a processing device and that cause 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 process.

The embodiments disclosed herein may be provided as a computer program product, or software process, 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.

Unless otherwise expressly stated, it is in no way intended that any method set forth herein be construed as requiring that its steps be performed in a specific order. Accordingly, where a method claim does not actually recite an order to be followed by its steps, or it is not otherwise specifically stated in the claims or descriptions that the steps are to be limited to a specific order, it is in no way intended that any particular order be inferred.

Claim 1:
A register mapping circuit (<NUM>) in a processor device (<NUM>), the register mapping circuit comprising:
a rename map table, RMT, (<NUM>) comprising a plurality of RMT entries (<NUM>(<NUM>)-<NUM>(L)) each representing a mapping of a logical register number, LRN, among a plurality of LRNs (LRN<NUM>-LRNL) to a physical register number, PRN, among a plurality of PRNs (PRN<NUM>-PRNP); and
a sliced reorder buffer, SROB, (<NUM>) subdivided into a plurality of SROB slices (<NUM>(<NUM>)-<NUM>(L)) each corresponding to a respective LRN among the plurality of LRNs, and each comprising a plurality of SROB slice entries (<NUM>(<NUM>)-<NUM>(X), <NUM>(<NUM>)-<NUM>(X));
the register mapping circuit configured to:
detect (<NUM>), within an execution pipeline (<NUM>) of the processor device, an uncommitted instruction (I<NUM>) comprising a write instruction to a destination LRN (LRN<NUM>) among the plurality of LRNs;
allocate (<NUM>), to the uncommitted instruction, an SROB slice entry (<NUM>(<NUM>)) among the plurality of SROB slice entries of an SROB slice (<NUM>(<NUM>)) corresponding to the destination LRN among the plurality of SROB slices of the SROB;
receive (<NUM>) an indication (<NUM>) of a pipeline flush from a target instruction (I<NUM>) within the execution pipeline; and
responsive to receiving the indication of the pipeline flush, restore (<NUM>) the plurality of RMT entries (<NUM>(<NUM>)-<NUM>(L)) to a corresponding plurality of prior mapping states, based on parallel walks of the plurality of SROB slices corresponding to LRNs of the plurality of RMT entries (<NUM>(<NUM>)-<NUM>(L)).