Method and system for managing registers in a data processing system supports out-of-order and speculative instruction execution

• US 6,356,918 B1
• Filed: 07/26/1995
• Issued: 03/12/2002
• Est. Priority Date: 07/26/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chuang, Chiao-Mei, Le, Hung Qui
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US08/507,542
• Time in Patent Office: 2,421 Days
• Field of Search: 707/203, 707/202, 712/34, 712/218-219, 712/228, 712/230, 712/233, 712/234, 712/239, 711/109, 708/709
• US Class Current: 1/1
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating
• CPC Class Codes: G06F 9/3858 Result writeback, i.e. updating the architectural state or memory
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method and a system in a data processing system for managing registers in a register array wherein the data processing system has M architected registers and the register array has greater than M registers. A first physical register address is selected from a group of available physical register addresses in a renamed table in response to dispatching a register-modifying instruction that specifies an architected target register address. The architected target register address is then associated with the first physical register address, and a result of executing the register-modifying instruction is stored in a physical register pointed to by the first physical register address. In response to completing the register-modifying instruction, the first physical address in the rename table is exchanged with a second physical address in a completion renamed table, wherein the second physical address is located in the completion rename table at a location pointed to by the architected target register address. Therefore, upon instruction completion, the completion rename table contains pointers that map architected register addresses to physical register addresses. The rename table maps architected register addresses to physical register addresses for instructions currently being executed, or for instructions that have “finished” and have not yet been “completed.” Bits indicating the validity of an association between an architected register address and a physical register address are stored before instructions are speculatively executed following an unresolved conditional branch.

Claims

1. A method in a data processing system for managing a register array, wherein said data processing system includes M architected registers and said register array includes M registers and N additional registers, and wherein said data processing system dispatches instructions to a selected one of a plurality of execution units, said method comprising the steps of:

in response to dispatching a register-modifying instruction having an architected target register address, selecting a first physical register address from a rename table;

associating said architected target register address with said first physical register address;

storing a result of executing said register-modifying instruction in a register pointed to by said first physical register address; and

in response to completing said register-modifying instruction, exchanging said first physical address in said rename table with a second physical address in a completion rename table that is stored at a location pointed to by said architected target register address, wherein said register-modifying instruction is associated with said first physical register address from said rename table, and, upon completion of said register-modifying instruction, said second physical address is moved to said rename table to be available for association with a subsequent register-modifying instruction.

2. The method in a data processing system for managing a register array according to claim 1 wherein said rename table includes a content addressable memory, and wherein said step of associating said architected target register address with said first physical register address includes storing said architected target register address in a same table entry with said first physical register address.

3. The method in a data processing system for managing a register array according to claim 2 wherein said rename table includes a head pointer for pointing to a rename table entry, and wherein said step of storing said architected target register address in a same table entry with said first physical register address includes the steps of:

storing said architected target register address in a same table entry with said first physical register address at a table entry pointed to by said head pointer; and

incrementing said head pointer to point to a next table entry in said rename table.

4. The method in a data processing system for managing a register array according to claim 2 wherein said rename table includes a valid field, and wherein said method further includes the steps of:

in response to associating said architected target register address with said first physical register address, indicating said association between said architected target register address and said first physical register address in said table entry in said rename table is valid by setting a valid bit in said valid field; and

in response to exchanging said first physical address in said rename table with a second physical address in a completion rename table that is stored at a location pointed to by said architected target register address, indicating said association between said architected target register address and said second physical register address in said table entry in said rename table is invalid by resetting said valid bit in said valid field.

5. The method in a data processing system for managing a register array according to claim 4 wherein said data processing system can speculatively dispatch register-modifying instructions, and wherein said rename table includes a V1 field, wherein said method further includes the steps of:

in response to speculatively dispatching a first register-modifying instruction in a first speculative instruction path in response to a first conditional branch instruction, copying bits in each of said valid fields to a corresponding one of said V1 fields for storing a condition of said rename table prior to said speculatively dispatched first register-modifying instruction; and

in response to determining said first conditional branch instruction was mispredicted, copying bits in each of said V1 fields to a corresponding one of said valid fields for restoring said condition of said rename table prior to said speculatively dispatched first register-modifying instruction.

6. The method in a data processing system for managing a register array according to claim 5 wherein said re name table includes a V2 field, and wherein said method further includes the steps of:

in response to speculatively dispatching a second register-modifying instruction in a second speculative instruction path in response to a second conditional branch instruction before said first conditional branch instruction is resolved, copying bits in each of said valid fields to a corresponding one of said V2 fields for storing a condition of said rename table prior to sa id speculatively dispatched second register-modifying instruction; and

in response to determining said second conditional branch instruction was mispredicted, copying bits in each of said V2 fields to a corresponding one of said valid fields for restoring said condition of said rename table prior to said speculatively dispatched second register-modifying instruction.

7. The method in a data processing system for managing a register array according to claim 6 wherein said data processing system includes a pending branch table, and wherein said method further includes the steps of:

in response to speculatively dispatching said first register-modifying instruction in said first speculative instruction path in response to said first conditional branch instruction, saving data in a first table entry in said pending branch table for determining if said first speculative instruction path was correctly taken, and for restoring said rename table to a condition that existed before said first conditional branch instruction; and

in response to speculatively dispatching a second register-modifying instruction in a second speculative instruction path in response to a second conditional branch instruction before said first conditional branch instruction is resolved, saving data in a second table entry in said pending branch table for determining if said second speculative instruction path was correctly taken, and for restoring said rename table to a condition that existed before said second conditional branch instruction.

8. A data processing system for managing a register array, wherein said data processing system includes M architected registers and said register array includes M registers and N additional registers, and wherein said data processing system dispatches instructions to a selected one of a plurality of execution units, said data processing system comprising:

means for selecting a first physical register address from a rename table in response to dispatching a register-modifying instruction having an architected target register address;

means for associating said architected target register address with said first physical register address;

means for storing a result of executing said register-modifying instruction in a register pointed to by said first physical register address; and

means for exchanging said first physical address in said rename table with a second physical address in a completion rename table that is stored at a location pointed to by said architected target register address in response to completing said register-modifying instruction, wherein said register-modifying instruction is associated with said first physical register address from said rename table, and, upon completion of said register-modifying instruction, said second physical address is moved to said rename table to be available for association with a subsequent register-modifying instruction.

9. The data processing system for managing a register array according to claim 8 wherein said rename table includes a content addressable memory, and wherein said means for associating said architected target register address with said first physical register address includes means for storing said architected target register address in a same table entry with said first physical register address.

11. The data processing system for managing a register array according to claim 9 wherein said rename table includes a valid field, and wherein said data processing system further includes:

means for indicating said association between said architected target register address and said first physical register address in said table entry in said rename table is valid by setting a valid bit in said valid field in response to associating said architected target register address with said first physical register address; and

means for indicating said association between said architected target register address and said second physical register address in said table entry in said rename table is invalid by resetting said valid bit in said valid field in response to exchanging aid first physical address in said rename table with a second physical address in a completion rename table that is stored at a location pointed to by said architected target register address.

12. The data processing system for managing a register array according to claim 11 wherein said data processing system can speculatively dispatch register-modifying instructions, and wherein said rename table includes a V1 field, wherein said data processing system further includes:

means for copying bits in each of said valid fields to a corresponding one of said V1 fields for storing a condition of said rename table prior to said speculatively dispatched first register-modifying instruction in response to speculatively dispatching a first register-modifying instruction in a first speculative instruction path in response to a first conditional branch instruction; and

means for copying bits in each of said V1 fields to a corresponding one of said valid fields for restoring said condition of said rename table prior to said speculatively dispatched first register-modifying instruction in response to determining said first conditional branch instruction was mispredicted.

13. The method in a data processing system for managing a register array according to claim 12 wherein said rename table includes a V2 field, and wherein said method further includes the steps of:

in response to speculatively dispatching a second register-modifying instruction in a second speculative instruction path in response to a second conditional branch instruction before said first conditional branch instruction is resolved, copying bits in each of said valid fields to a corresponding one of said V2 fields for storing a condition of said rename table prior to said speculatively dispatched second register-modifying instruction; and

in response to determining said second conditional branch instruction was mispredicted, copying bits in each of said V2 fields to a corresponding one of said valid fields for restoring said condition of said rename table prior to said speculatively dispatched second register-modifying instruction.

14. The data processing system for managing a register array according to claim 13 wherein said data processing system includes a pending branch table, and wherein said data processing system further includes:

means for saving data in a first table entry in said pending branch table for determining if said first speculative instruction path was correctly taken, and for restoring said rename table to a condition that existed before said first conditional branch instruction, in response to speculatively dispatching said first registers modifying instruction in said first speculative instruction path in response to said first conditional branch instruction; and

means for saving data in a second table entry in said pending branch table for determining if said second speculative instruction path was correctly taken, and for restoring said rename table to a condition that existed before said second conditional branch instruction, in response to speculatively dispatching a second register-modifying instruction in a second speculative instruction path in response to a second conditional branch instruction before said first conditional branch instruction is resolved.

10. The data processing system for managing a register array according to claim wherein said rename table includes a head pointer for pointing to a rename table entry, and wherein said means for storing said architected target register address in a same table en try with said first physical register address includes:

means for storing said architected target register address in a same table entry with said first physical register address at a table entry pointed to by said head pointer; and

means for incrementing said head pointer to point to a next table entry in said rename table.