Register mapping system having a log containing sequential listing of registers that were changed in preceding cycles for precise post-branch recovery

• US 5,197,132 A
• Filed: 06/29/1990
• Issued: 03/23/1993
• Est. Priority Date: 06/29/1990
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Sager, David J., Steely, Simon C. Jr.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): AN, MENG AI T
• Application Number:
  US07/546,411
• Time in Patent Office: 998 Days
• Field of Search: 395/800, 395/425, 395/200, 395/375
• US Class Current: 712/217
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

A register map having a free list of available physical locations in a register file, a log containing a sequential listing of logical registers changed during a predetermined number of cycles, a back-up map associating the logical registers with corresponding physical homes at a back-up point in a computer pipeline operation and a predicted map associating the logical registers with corresponding physical homes at a current point in the computer pipeline operation. A set of valid bits is associated with the maps to indicate whether a particular logical register is to be taken from the back-up map or the predicted map indication of a corresponding physical home. The valid bits can be "flash cleared" in a single cycle to back-up the computer pipeline to the back-up point during a trap event.

Claims

1. An arrangement for mapping m logical registers used in the execution of instructions processed through a computer pipeline, comprising:

a register file having n locations for storing values, said locations being physical homes of the m logical registers, where m<

n; and

a register map coupled to the register file and receiving instructions as input and generating mapped instructions as output to the register file, the register map comprising;

a free list that contains a number of locations p, each said free list location containing a register file location, the free list indicating which of said register file locations are free for use in a current cycle;

a log that contains a sequential listing of which of the m logical registers were changed in each of t cycles preceding a current cycle;

a backup map that contains a map associating m of the n physical homes to the m logical registers at a backup point, wherein the backup point is a preselected number of cycles preceding the current cycle and wherein the preselected number of cycles is equal to, or less than, t;

a predicted map that contains a map associating m of the n physical homes to the m logical registers during the current cycle; and

a register map control device coupled to each of the free list, log, backup map, and predicted map, the register map control device receiving the instructions input to the register map, maintaining the free list, log, backup map and predicted map, the backup map being maintained using the sequential listing of the log, the register map control device generating the mapped instructions output by the register map.

2. The arrangement of claim 1, wherein the register map further comprises a valid bits register coupled to the register map control device, the valid bits register including a set of valid bits, each one of the valid bits corresponding to one of the m logical registers for indicating whether the physical home, associated with the corresponding logical register, is to be taken from the backup map or the predicted map when mapping registers.

3. A method of maintaining a mapping of m logical registers to n physical homes contained in a register file, wherein m<

n, for instructions processed in a computer pipeline, comprising the steps of;

receiving an instruction, during a current cycle, the instruction specifying at least one address of one of the m logical registers to be mapped in a register map;

maintaining a free list that indicates which of the n physical homes in the register file are free for use in the current cycle;

mapping the at least one address of the received instruction into at least one of the free physical homes indicated in the free list and associating the one of the free physical homes with the corresponding one of the m logical registers;

maintaining in a log a sequential listing of which of the m logical registers were changed in each of t cycles preceding the current cycle;

utilizing the log to maintain in a backup map the physical home associated with each one of the m logical registers at a backup point, wherein the backup point is a preselected number of cycles preceding the current cycle and wherein the preselected number of cycles is equal to, or less than, t;

maintaining in a predicted map a map of the physical home associated with each one of the m logical registers during the current cycle;

maintaining a set of valid bits that indicate whether the physical home associated with a specific logical register is to be taken from the backup map or the predicted map when mapping registers.

4. The method of claim 3, further comprising the step of flash-clearing the set of valid bits in response to a control signal, to thereby indicate that a correct physical home for a logical register is to be taken from the backup map when backing up an instruction stream.

5. The method of claim 3, wherein the step of maintaining a freelist includes storing a present physical home for a logical register being changed, in a first location in the freelist, and assigning a new physical home to the logical register being changed from a second location in the freelist.

6. The method of claim 5, wherein the step of maintaining a freelist further includes aging of the present physical home that is stored by storing the present physical home for a period of time at least equal to a backup time before assigning the aged physical home as a new physical home to a logical register being changed, wherein the backup time is equal to the number of cycles occurring from the backup point to the current cycle.

7. The method of claim 6, wherein the step of maintaining in a predicted map includes storing the new physical home for the logical register being changed, into the predicted map at a location indexed by the logical register being changed.

8. The method of claim 7, wherein the step of maintaining a set of valid bits includes setting a valid bit that corresponds to the logical register being changed.

9. The method of claim 8, wherein the step of maintaining in a backup map includes addressing the log to identify a logical register that was changed a backup time ago, identifying from the freelist a physical home that was assigned to the logical register that was changed a backup time ago, and storing this physical home into the backup map at a location indexed by the logical register that was changed a backup time ago.

10. A method of assigning physical homes to logical registers used in executing instructions processed through a computer pipeline, comprising the steps of:

receiving in a register mapping station a new instruction to be executed during a current cycle;

identifying the logical register that is being written to in the current cycle;

identifying the logical registers that are being read in the current cycle;

maintaining a log that contains a sequential listing of which of the m logical registers were changed in each of t cycles preceding the current cycle, the step of maintaining the log

including the step of updating the log to include the register written to during the current cycle;

maintaining a backup map by using the sequential listing of the log, the backup map comprising a map of physical homes associated with the logical registers at a backup point, wherein the backup point is a preselected number of cycles preceding the current cycle and wherein the preselected number of cycles is equal to, or less than, t;

maintaining in a predicted map, a map of the physical home associated with each one of the m logical registers during the current cycle;

maintaining a set of valid bits, one valid bit being associated with each of the logical registers;

determining the state of valid bits associated with each of the logical registers that are being read in the current cycle;

providing a physical home for each logical register that is being read in the current cycle from the backup map if the state of the valid bit associated with that logical register is in a first state, and from the predicted map if the state of the valid bit associated with that logical register is in a second state; and

assigning from a freelist a new physical home to the logical register that is being written to in the current cycle;

wherein the number of physical homes is greater that the number of logical registers.