US 6,675,288 B2Granted

Apparatus for mapping instructions using a set of valid and invalid logical to physical register assignments indicated by bits of a valid vector together with a logical register list

AssigneeHewlett-Packard Development Company, L.P.

InventorsJames Arthur Farrell, Sharon Marie Britton, Harry Ray Fair, III, Bruce Gieseke, Daniel Lawrence Leibholz, Derrick R. Meyer

Life of this patent

Estimating the term…

patentgrep

Loading patent…

Abstract

A technique for managing register assignments. The technique involves maintaining, in a register list memory circuit having entries that respectively correspond to physical registers, a list of register assignments that assign logical registers to the physical registers. The technique further involves maintaining, in a vector memory circuit having bits that respectively correspond to the physical registers, a valid vector that forms, in combination with the list of register assignments, a list of valid register assignments. Furthermore, the technique involves storing, for an instruction that is mapped by the data processor, a copy of the valid vector from the vector memory circuit to a silo memory circuit. Preferably, the processor using the technique has the ability to execute branches of instructions speculatively, and to recover if it is determined that the processor executed down an incorrect instruction branch.

Claims16

Dependent claims

An apparatus for mapping instructions in a data processing system to resolve dependencies in an original register assignment such that Write-After-Write (WAW) and Read-After-Write (RAW) dependencies are eliminated in an output mapped instructions, thereby permitting issuance of the output mapped instructions in any order relative to each other, the apparatus comprising:

means for maintaining a logical register list having entries, each entry corresponding to each of a plurality of physical registers, each entry indicating a possible assignment of a logical register to a physical register,
means for maintaining a valid vector, the valid vector having a number of bits corresponding to the plurality of physical registers, the bits of the valid vector indicating, together with the logical register list, a list of valid and invalid logical to physical register assignments, with logical false bits indicating a corresponding invalid logical register to physical register assignments, and logical true bits indicating a corresponding valid logical register to physical register assignments;
means for obtaining an instruction to be mapped, the instruction including potentially source operands and destination operands;
and
means for mapping the instruction, the means for mapping examining the instruction to be mapped to determine whether each of the source operands includes a reference to a logical register, and if the instruction to be mapped includes logical source operand, the means for mapping also including replacing the logical source operand with a physical source operand by examining existing register assignments stored in the logical register list and their associated bits of the valid vector;
if the instruction to be mapped includes a logical destination operand, the means for mapping also actuating:
means for identifying a new logical register assignment from the existing register assignments stored in the logical register list and the valid vector;
means for replacing the logical destination operand with a physical destination operand that identifies a physical register to which the identified new logical register is assigned;
means for locating an entry in the logical register list previously assigning the referenced logical register to another physical register, and clearing a corresponding bit in the valid vector to a false state, in order to invalidate that previous assignment;
and
means for selecting an unused entry in the logical register list and setting contents of that selected entry to identify the new logical register, and thus considering the new logical register to be assigned to the physical register corresponding to the selected entry;
and means for storing, for an instruction that is mapped, a copy of the valid vector to a vector silo memory.

9 more elements

a logical register list memory circuit having entries, each entry corresponding to each of a plurality of physical registers, each entry indicating a possible assignment of a logical register to a physical register;
a valid vector memory circuit storing, in a valid vector, a number of bits corresponding to the plurality of physical registers, the bits of the valid vector indicating, together with the logical register list memory circuit, a list of valid and invalid logical to physical register assignments, with logical false bits indicating a corresponding invalid logical register to physical register assignments, and logical true bits indicating a corresponding valid logical register to physical register assignments;
and
an instruction mapper for mapping an instruction, the instruction including potentially source operands and destination operands, wherein:
the instruction mapper examines the instruction to be mapped to determine whether each of the source operands includes a reference to a logical register, and if the instruction to be mapped includes logical source operand, the instruction mapper replaces the logical source operand with a physical source operand by examining existing register assignments stored in the logical register list memory circuit and their associated bits of the valid vector memory circuit;
if the instruction to be mapped includes a logical destination operand, the instruction mapper
identifies a new logical register assignment from the existing register assignments stored in the logical register list memory circuit and the valid vector memory circuit;
replaces the logical destination operand with a physical destination operand that identifies a physical register to which the identified new logical register is assigned;
locates an entry in the logical register list memory circuit previously assigning the referenced logical register to another physical register, and clears a corresponding bit in the valid vector memory circuit to a false state, in order to invalidate that previous assignment;
and
selects an unused entry in the logical register list memory circuit and sets contents of that selected entry to identify the new logical register, and thus considers the new logical register to be assigned to the physical register corresponding to the selected entry;
and stores, for an instruction that is mapped, a copy of the valid vector to a vector silo memory.

9 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/144,097Filed 9 May 2002 · continuation
Priority: 24 Aug 1998
Published: US 2002/0069346 A124 Oct 2002
Granted: 6 Jan 2004
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 9/3863
Recovery, e.g. branch miss-prediction, exception handling: using multiple copies of the architectural state, e.g. shadow registers
G06F 9/3836
Concurrent instruction execution, e.g. pipeline or look ahead: instruction issuing, e.g. dynamic instruction scheduling or out of order…
G06F 9/3838
Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution: dependency mechanisms, e.g. register scoreboarding
G06F 9/384
Dependency mechanisms, e.g. register scoreboarding: register renaming

Family

Application09/138,957Parent of this continuation · filed 24 Aug 1998
US 6,405,304 B1Parent of this continuation · filed 11 Jun 2002
US 2002/0156997 A1Pre-grant publication · published 24 Oct 2002
US 2002/0069346 A1Published application
US 6,675,288 B2This patent

From the US filing history. Foreign family members aren’t listed.