Search

EP-4643213-B1 - OUT-OF-ORDER PROCESSOR WITH RENAME MAP TABLE RECOVERY FEATURES

EP4643213B1EP 4643213 B1EP4643213 B1EP 4643213B1EP-4643213-B1

Inventors

  • ESPER, John Michael
  • PRIYADARSHI, SHIVAM
  • CHIRRA, Vidisha Reddy
  • LEE, CHANG-CHIA
  • CHANG, Wan Yun

Dates

Publication Date
20260513
Application Date
20240307

Claims (15)

  1. A method (300) for recovering a rename map table for an out-of-order processor (100) after a flush operation, the method comprising: executing, by an out-of-order processor, instructions including a flush operation (132) resulting from a branch misprediction of a branch instruction, the out-of-order processor comprising a reorder buffer (122) tracking a program order for the instructions and a rename map table (124) mapping a plurality of logical registers to a plurality of physical registers (126); in response to executing the flush operation, grouping (302) the instructions, ordered from oldest to youngest according to the program order tracked in the reorder buffer, into a plurality of segments; comparing (304) the plurality of segments to identify one or more segments that contain a youngest superset of instructions that wrote to the plurality of logical registers between a head of the reorder buffer and the branch instruction; performing (306) a recovery walk of the identified one or more segments to recover the rename map table; and wherein comparing the plurality of segments to identify the one or more segments comprises: populating (402) a vector for each segment of the plurality of segments, wherein: each entry in the vector corresponds to a corresponding logical register of the plurality of logical registers; and when it is determined that an instruction in the segment wrote to the corresponding logical register, setting the entry in the vector for the corresponding logical register to a value indicating that the corresponding logical register was updated to in the segment; and comparing (404) the vectors to identify one or more vectors corresponding to the one or more segments that contain a superset of the values indicating that the logical registers were updated in the segment.
  2. The method of claim 1, wherein grouping the instructions comprises: grouping only the instructions between a pointer to a head of the reorder buffer to the branch instruction.
  3. The method of claim 2, the method further comprising: invalidating the instructions after the branch instruction in the program order.
  4. The method of claim 1, wherein the vector is a bit vector and the value indicating that the logical register was updated in the segment is 1.
  5. The method of claim 4, wherein comparing the vectors to identify the one or more vectors comprises: performing a logical bitOR operation between a vector of an older segment and a vector of a younger segment; and determining that the younger segment is a super set of the older segment when a result of the logical bitOR operation is equal to the vector of the younger segment.
  6. The method of claim 4, the method further comprising: recreating a new bit vector for a walking segment when a new instruction stream begins.
  7. The method of claim 1, wherein comparing the plurality of segments further comprises: grouping the plurality of segments into a plurality of banks; and comparing the plurality of banks to identify one or more banks that contain the youngest superset of segments of instructions that wrote to the plurality of logical registers between the head of the reorder buffer and the branch instruction.
  8. The method of claim 7, wherein intra-bank comparisons of segments are performed on the one or more identified banks; and optionally wherein: (i) the intra-bank comparisons are performed in parallel with the comparing of the plurality of banks; or (ii) the intra-bank comparisons are performed subsequently to the comparing of the plurality of banks.
  9. The method of claim 1, the method further comprising: identifying a first segment of the one or more identified segments to start the recovery walk and invalidating segments older than the first segment; and performing a recovery walk of the first segment.
  10. The method of claim 9, the method further comprising: identifying a next segment of the identified one or more segments; invalidating all segments older than the next segment after the recovery walk of the first segment is complete; and optionally: wherein the method is repeated until all of the identified one or more segments have been walked resulting in all the plurality of segments being invalidated.
  11. The method of claim 1, wherein the recovery walk of the identified one or more segments always includes a youngest segment that includes the branch instruction.
  12. An out-of-order processor (100) comprising: a plurality of physical registers (126); a rename map table (124) configured to map a plurality of logical registers to the plurality of physical registers in the out-of-order processor; and a reorder buffer (122) configured to tracking a program order for a plurality of instructions; wherein the out-of-order processor is configured to recover the rename map table after a flush operation resulting from a branch misprediction of a branch instruction using circuitry configured to: group (302) the plurality of instructions, ordered from oldest to youngest according to the program order tracked in the reorder buffer, into a plurality of segments; compare (304) the plurality of segments to identify one or more segments that collectively contain a youngest superset of instructions that wrote to the plurality of logical registers between a head of the reorder buffer and the branch instruction; and perform (306) a recovery walk of the identified one or more segments to recover the rename map table; and wherein comparing the plurality of segments to identify the one or more segments comprises: populating (402) a vector for each segment of the plurality of segments, wherein: each entry in the vector corresponds to a corresponding logical register of the plurality of logical registers; and when it is determined that an instruction in the segment wrote to the corresponding logical register, setting the entry in the vector for the corresponding logical register to a value indicating that the corresponding logical register was updated to in the segment; and comparing (404) the vectors to identify one or more vectors corresponding to the one or more segments that contain a superset of the values indicating that the logical registers were updated in the segment.
  13. The out-of-order processor of claim 12 further comprising: one or more bitOR logical gates, one or more XOR logical gates, and at least one mux configured to compare the plurality of segments to identify the one or more segments.
  14. The out-of-order processor of claim 12, wherein: the recovery walk starts from an oldest instruction in the one or more identified segments; or the recovery walk starts from a youngest instruction in the one or more identified segments.
  15. The out-of-order processor of claim 12, wherein out-of-order processor is configured to recover the rename map table before a next instruction is ready for execution.

Description

BACKGROUND Out-of-order processors are designed to optimize computational efficiency by executing instructions in a sequence different from their original program order. Out-of-order processors are designed to minimize potential delays that would otherwise occur while the processor is waiting for an operation to complete. For example, a processor can be designed to complete other instructions while waiting for fetching data from memory. Out-of-order processors are configured to ensure that the final outcomes align with the original program order, thereby maintaining the integrity of the program execution with the reordering of the instructions during execution. Out-of-order processors can significantly enhance processing speed and overall performance of a computing system. Out-of-order processors use speculation techniques such as branch prediction to improve the flow in the instruction pipeline by trying to guess which way a branch (e.g., an if-then-else structure) will go before the result is known definitively. Branch prediction can mitigate delays that occur when a processor is waiting for certain operations to complete and allow for further rearranging of the order of operations during these waiting periods. US 2014/0040595 A1 discloses a processor may efficiently implementing register renaming and checkpoint repair even in instruction set architectures with large numbers of wide (bit-width) registers by (i) renaming all destination operand register twets, (ii) implementing free list and architectural-to-physical mapping table as a combined array storage with unitary (or common) read, write and checkpoint pointer indexing and (iiii) storing checkpoints as snapshots of the mapping table, rather than of actual register contents. In this way, uniformity (and timing simplicity) of the decode pipeline may be accentuated and architectural-tophysical mappings (or allocable mappings) may be efficiently shuttled between free-list, reorder buffer and mapping table stores in correspondence with instruction dispatch and completion as well as checkpoint creation, retirement and restoration. SUMMARY This specification describes technologies relating to an out-of-order processor with rename map table recovery features. In some implementations, in order to recover from a speculative misprediction (e.g., a branch misprediction, a memory dependence misprediction), the out-of-order processor is configured to identify the youngest write instructions before a branch instruction, corresponding to the speculative misprediction, for the logical registers that are mapped by the rename map table. The out-of-order processor walks the identified youngest write instructions to recover the rename map table to the state it was in prior to the branch instruction. In some implementations, the out-of-order processor groups the instructions older than the branch instructions into segments. In these implementations, the out-of-order processor identifies the segments that contain the youngest write instructions, that are older than the branch instruction, for the logical registers that are mapped by the rename map table, and walks the instructions in the identified segments to recover the rename map table. In one aspect, a method for recovering a rename map table for an out-of-order processor after a flush operation is disclosed. The method includes executing, by an out-of-order processor, instructions including a flush operation resulting from a branch misprediction of a branch instruction. The out-of-order processor includes a reorder buffer tracking a program order for the instructions and a rename map table mapping multiple logical registers to multiple physical registers. The method also includes, in response to executing the flush operation, grouping the instructions, ordered from oldest to youngest according to the program order tracked in the reorder buffer, into multiple of segments, comparing the multiple segments to identify segments that contain a youngest superset of instructions that wrote to the multiple logical registers between a head of the reorder buffer and the branch instruction, and performing a recovery walk of the identified segments to recover the rename map table. In another aspect, an out-of-order processor is disclosed. The out-of-order processor includes multiple physical registers. a rename map table configured to map multiple logical registers to the multiple physical registers in the out-of-order processor, and a reorder buffer configured to track a program order for instructions. The out-of-order processor is configured to recover the rename map table after a flush operation resulting from a branch misprediction of a branch instruction using circuitry. The circuitry is configured to group the instructions, ordered from oldest to youngest according to the program order tracked in the reorder buffer, into multiple segments, compare the multiple segments to identify segments that contain a youngest superset o