Multi instruction register mapper

• US 5,519,841 A
• Filed: 11/12/1992
• Issued: 05/21/1996
• Est. Priority Date: 11/12/1992
• 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., Fite, David B. Jr.
• Primary Examiner(s): Lane, Jack A.
• Application Number:
  US07/974,776
• Time in Patent Office: 1,286 Days
• Field of Search: 395/400, 395/425, 395/375, 395/775, 395/412, 395/413
• US Class Current: 711/202
• CPC Class Codes: G06F 9/32 Address formation of the next instruction, e.g. by incrementing the instruction counter G06F9/38 takes precedence
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3814 Implementation provisions of instruction buffers, e.g. prefetch buffer; banks
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags
• 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

Abstract

A pipelined processor includes an instruction unit including a register mapper, to map register operand fields of a set of instructions and an instruction scheduler, fed by the set of instructions, to reorder the issuance of the set of instructions from the processor. The mapped register operand fields are associated with the corresponding instructions of the reordered set of instructions prior to issuance of the instructions. The processor further includes a branch prediction table which maps a stored pattern of past histories associated with a branch instruction to a more likely prediction direction of the branch instruction. The processor further includes a memory reference tagging store associated with the instruction scheduler so that the scheduler can reorder memory reference instructions without knowing the actual memory location addressed by the memory reference instruction.

Claims

1. Apparatus for mapping logical registers, comprising:

a map comprising;

means for storing a current set of register numbers which are available for assignment in a current cycle and for storing a previous set of register numbers which were assigned in a previous cycle;

means for storing a current set of logical register destination operands and for storing a previous set of logical register destination operands;

a plurality of register files corresponding to a number of instructions to be mapped in a cycle, said register files each having a plurality of locations, each register file having a plurality of write ports corresponding to said number of instructions to be mapped in a cycle, with said write ports of each of said register files having a write address port and a write data port, and with a first write port of a first one of said register files having the corresponding write address port fed by a first one of the logical destination register operands of a previous set of instructions and the corresponding write data port fed by a first one of the register numbers of the previous set of instructions, and a last write port of a first one of said register files having the corresponding write address port fed by a last one of the logical destination register operands of the previous set of instructions and the corresponding write data port fed by a last one of the register numbers of the previous set of instructions.

2. The apparatus as recited in claim 1 wherein a first write port of a second one of said register files has the corresponding write address port fed by a second one of the logical destination register operands of the previous set of instructions and the corresponding write data port fed by a second one of the register numbers of the previous set of instructions, and a last write port of the second one of said register files having the corresponding write address port fed by a first one of the logical destination register operands of the current set of instructions and the corresponding write data port fed by a first one of the register numbers of the current set of instructions.

3. The apparatus of claim 1 wherein said means for storing said current and previous set of register numbers, further comprises:

means for maintaining a list of destination operands which are free to be used in a current cycle.

4. The apparatus as recited in claim 3 wherein each one of said plurality of register files further includes:

three read ports each port having an address port fed by one of a pair of source logical operand register and a destination logical operand register to provide in response thereto a new register number corresponding to a physical location containing the corresponding logical register operands.

5. The apparatus as recited in claim 4 further comprising:

means for maintaining a list of each logical register operand which was reassigned in a previous number of cycles.

6. The apparatus as recited in claim 5 further comprising:

means for delaying reuse of assigned register numbers until a selected number of cycles has elapsed.

7. The apparatus as recited in claim 6 further comprising:

means for compressing the delayed register numbers to provide a complete set of available register numbers.

8. The apparatus as recited in claim 7 further comprising:

means, responsive to said complete set of available registers, for freeing up the use of registers assigned by said means for maintaining a list.

9. The apparatus as recited in claim 1 further comprising:

a backup map comprising;

means for storing a first previous set of register numbers which were assigned in a corresponding first cycle of a previous set of cycles of the register mapper and for storing a second previous set of register numbers which were assigned in a second cycle of the previous set of cycles of the register mapper;

means for storing a first previous set of logical register destination operands and for storing a second previous set of logical register destination operands associated with said first and second previous cycles of the previous set of cycles;

a second plurality of register files corresponding to the number of instructions to be backed up during the previous set of cycles, said register files each having a plurality of locations, each register file having a like plurality of write ports, with said write ports of each of said register files having a write address port and a write data port, and with a first write port of a first one of said register files having the corresponding write address port fed by a first one of the logical destination register operands of the second cycle of the previous set of cycles and the corresponding write data port fed by a first one of the register numbers of the second cycle of the previous set of cycles, and a last write port of a first one of said register files having the corresponding write address port fed by a last one of the logical destination register operands of the second cycle of the previous set of cycles and the corresponding write data port fed by a last one of the register numbers of the second cycle of the previous set of cycles.

10. The apparatus as recited in claim 9 wherein a first write port of a second one of said files has the corresponding write address port fed by a second one of the logical destination register operands of the second cycle of the previous set of cycles and the corresponding write data port fed by a second one of the register numbers of the second cycles of the previous set of cycles, and a last write port of the second one of said files having the corresponding write address port fed by a first one of the logical destination register operands of the first cycles of the previous set of cycles and the corresponding write data port fed by a first one of the register numbers of the first cycle of the previous set of cycles.

11. The apparatus of claim 10 wherein said means for storing said current and previous sets of register numbers, further comprises:

means for maintaining a list of destination operands which are free to be used in a current cycle.

12. The apparatus as recited in claim 11 wherein each one of said plurality of register files further includes:

three read ports each port having an address port fed by one of a pair of source logical operands and a destination logical operand of a selected one of the set of instructions and to provide in response thereto a new register number corresponding to a physical location of the contents of the corresponding logical register operands.

13. The apparatus as recited in claim 12 further comprising:

means for maintaining a list of each logical register operand which was reassigned in a previous number of cycles.

14. The apparatus as recited in claim 13 further comprising:

means for delaying reuse of assigned register numbers until a selected number of cycles has elapsed.

15. The apparatus as recited in claim 14 further comprising:

means for compressing the delayed register numbers to provide a complete set of available registers.

16. The apparatus as recited in claim 15 further comprising:

means, responsive to said complete set of available registers, for freeing up the use of registers assigned by said list maintaining means.

17. Apparatus for mapping n logical registers used in the execution of a plurality of instructions, comprising:

a map comprising;

a plurality of register files corresponding to the number of instructions to be mapped in a cycle, said register files each having a plurality of locations, each register file having a like plurality of write ports and three read ports for providing an output from said register file, with said write ports of each of said register files having a write address port and a write data port;

means for maintaining a list of locations in each of said register files which are free to be used in a current cycle, said means further comprising;

means for storing a current set of register numbers which are available for assignment in the current cycle;

means for storing a previous set of register numbers which were assigned in the previous cycle;

means for storing a current set of logical register destination operands and for storing a previous set of logical register destination operands;

means for providing the previous and current sets of register numbers as data to said register files with a first one of said register files having a first one of said register numbers as data to a first data port of said register file, and each succeeding one of said register files having each succeeding one of said register numbers input as data to a first data port of each of said succeeding files, and for providing the previous and current sets of register operands as addresses to said register files with a first one of said files having a first one of said register operands as an address to a first address port of said first file, and each succeeding one of said files having each succeeding one of said register operands as an address to a first address port of each of said succeeding files;

means for providing addresses to said read ports of each of said files to provide at the output of said files a register address corresponding to a physical home of each of said previous logical register destination operands; and

means for maintaining a list of each logical register operand which was reassigned in a previous number of cycles.

18. The apparatus as recited in claim 17 further comprising:

a backup map, comprising;

a plurality of register files corresponding to the number of instructions mapped in a previous first set of cycles, said files each having a plurality of locations, each file having a like plurality of write ports and three read ports with said write ports of each of said register files having a write address port and a write data port;

means for storing a first one of a previous set of register numbers which were assigned in the previous first set of cycles;

means for storing a second one of a previous set of register numbers which were assigned in the previous first set of cycles;

means for storing a first one of a previous set of logical register destination operands and for storing a second one of a previous set of logical destination register operands;

means for providing output from a first one of said register files having a first one of said register numbers of the second one of the first previous set of cycles as data to a first data port of said file, and each succeeding one of said files having each succeeding one of said register numbers of said second one of said first previous set of cycles as data to a first data port of each of said succeeding files, and for providing a first one of said register operands of the first previous set of cycles as an address to a first address port of said first file, and each succeeding one of said register operands of said first previous set of cycles as an address to a first address port of each of said succeeding files; and

means for providing addresses to said read ports of each of said files to provide at the output of said files a register address corresponding to a physical home of each of said logical register operands.