# US 2008/0189535 A1 · Method and System for Dependency Tracking and Flush Recovery for an Out-Of-Order Microprocessor

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0189535 A1
- Document ID: US20080189535A1
- Status: Published application
- Kind: A1
- Application number: 11/669,999
- Filed: 2007-02-01
- Published: 2008-08-07
- Earliest claimed: 2007-02-01
- Assignees: International Business Machines Corporation
- Inventors: Vikas Agarwal; William E. Burky; Krishnan Kailas; Balaram Sinharoy
- Web page: https://patentgrep.com/patent/US20080189535A1

## CPC

- G06F 9/3842: {Speculative instruction execution}
- G06F 9/3863: {using multiple copies of the architectural state, e.g. shadow registers}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for dependency tracking and flush recovery for an out-of-order processor includes recording, in a last definition (DEF) data structure, an identifier of a first instruction as the most recent instruction in an instruction sequence that defines contents of the particular logical register and recording, in a next DEF data structure, the identifier of the first instruction in association with an identifier of a previous second instruction also indicating an update to the particular logical register. In addition, a recovery array is updated to indicate which of the instructions in the instruction sequence updates each of the plurality of logical registers. In response to misspeculation during execution of the instruction sequence, the processor performs a recovery operation to place the identifier of the second instruction in the last DEF data structure by reference to the next DEF data structure and the recovery array.

## Claims

### Claim 1

In a processor, a method comprising:
in response to receipt of an instruction sequence, said instruction sequence including a first instruction indicating an update to a particular logical register among a plurality of logical registers and a previous second instruction also indicating an update to the particular logical register:
mapping said particular logical register to a physical register among a plurality of physical registers within a register file of the processor;
in a last definition (DEF) data structure, recording an identifier of the first instruction as the most recent instruction in the instruction sequence that defines contents of the particular logical register;
in a next DEF data structure, recording the identifier of the first instruction in association with an identifier of the previous second instruction;
in a recovery data structure, indicating which of the instructions in the instruction sequence updates each of said first plurality of logical registers;
executing instructions in the instruction sequence, wherein the executing includes executing at least some of the instructions speculatively; and
in response to misspeculation during execution of the instruction sequence, performing a recovery operation to place the identifier of the previous second instruction in the last DEF data structure by reference to said next DEF data structure and said recovery data structure.

### Claim 2 (depends on 1)

The method of claim 1, wherein:
said processor includes multiple orthogonal register files including the register file;
said method includes implementing a respective one of a plurality of next DEF data structures for each the multiple register files; and
said indicating further comprises making entries in said recovery data structure for logical registers mapped to any of said multiple register files.

### Claim 3 (depends on 1)

The method of claim 1, wherein:
said last DEF data structure comprises a last DEF table;
said next DEF data structure comprises a next DEF table; and
recording the identifier of the first instruction comprises recording an instruction tag of the first instruction in said last DEF table and the next DEF table.

### Claim 4 (depends on 1)

The method of claim 1, wherein performing said recovery operation comprises:
in response to the misspeculation, comparing each identifier of an instruction in said next DEF data structure to an indication of a location of the misspeculation in the instruction sequence;
in response to the comparison, outputting from said recovery data structure identifiers of instructions preceding the misspeculation in the instruction sequence; and
in response to said outputting, updating said last DEF data structure with said identifier of said second instruction.

### Claim 5 (depends on 4)

The method of claim 4, wherein said updating includes performing all updates to said last DEF data structure required for the recovery operation in a single cycle.

### Claim 6 (depends on 1)

The method of claim 1, wherein said recording an identifier of the first instruction comprises recording the identifier of the first instruction at dispatch time.

### Claim 7 (depends on 1)

The method of claim 1, wherein:
said step of mapping comprises mapping said particular logical register with a register mapper different from said last DEF data structure; and
said step of performing a recovery operation comprises performing the recovery operation without reference to the register mapper.

### Claim 8 (depends on 1)

The method of claim 1, wherein:
said executing includes predicting an outcome of a conditional branch instruction within the instruction sequence; and
said method further comprises detecting misspeculation of the conditional branch instruction.

### Claim 9

A processor, comprising:
instruction sequencing logic that fetches an instruction sequence for execution, said instruction sequence including a first instruction indicating an update to a particular logical register among a plurality of logical registers and a previous second instruction also indicating an update to the particular logical register;
a register file including a plurality of physical registers;
mapping logic that maps said particular logical register to a physical register among the plurality of physical registers within the register file;
a last definition (DEF) data structure that records an identifier of the first instruction as the most recent instruction in the instruction sequence that defines contents of the particular logical register;
a next DEF data structure that records the identifier of the first instruction in association with an identifier of the previous second instruction;
a recovery data structure indicating which of the instructions in the instruction sequence updates each of said plurality of logical registers; and
one or more execution units coupled to the register file and the instruction sequencing logic, wherein said one or more execution units execute the instruction sequence and execute at least some of the instructions in the instruction sequence speculatively;
wherein the instruction sequencing logic, responsive to misspeculation during execution of the instruction sequence, causes a recovery operation to be performed to place the identifier of the second instruction in the last DEF data structure by reference to said next DEF data structure and said recovery data structure.

### Claim 10 (depends on 9)

The processor of claim 9, wherein:
said processor includes:
multiple orthogonal register files including the register file; and
a plurality of next DEF data structures including the next DEF data structure, wherein each of the plurality of next DEF data structure is associated with a respective one of the multiple register files; and
said recovery data structure includes entries for logical registers mapped to any of said multiple register files.

### Claim 11 (depends on 9)

The processor of claim 9, wherein:
said last DEF data structure comprises a last DEF table;
said next DEF data structure comprises a next DEF table; and
the identifier of the first instruction comprises an instruction tag assigned to the first instruction by the instruction sequencing logic.

### Claim 12 (depends on 9)

The processor of claim 9, wherein in said recovery operation, the processor compares each identifier of an instruction in said next DEF data structure with an indication of a location of the misspeculation in the instruction sequence and, response thereto, outputs from said recovery data structure identifiers of instructions preceding the misspeculation in the instruction sequence, said identifiers including the identifier of the second instruction, and wherein said processor updates said last DEF data structure with said identifier of said second instruction.

### Claim 13 (depends on 12)

The processor of claim 12, wherein the processor performs all updates to said last DEF data structure required for the recovery operation in a single cycle.

### Claim 14 (depends on 9)

The processor of claim 9, said last DEF data structure records the identifier of the first instruction at dispatch time.

### Claim 15 (depends on 9)

The processor of claim 9, wherein said processor performs the recovery operation without reference to the register mapper.

### Claim 16 (depends on 9)

The processor of claim 9, wherein the instruction sequencing logic includes a branch prediction unit that predicts an outcome of a conditional branch instruction within the instruction sequence.

### Claim 17 (depends on 9)

A data processing system, comprising:
at least one processor in accordance with claim 9;
an interconnect fabric coupled to the processor; and
a system memory coupled to the interconnect fabric.
