Branch target preloading using a multiplexer and hash circuit to reduce incorrect branch predictions

Patent metadata

Field	Value
Publication number	US-9519480-B2
Application number	US-2925808-A
Country	US
Kind code	B2
Filing date	Feb 11, 2008
Priority date	Feb 11, 2008
Publication date	Dec 13, 2016
Grant date	Dec 13, 2016

Abstract

A system provides complex branch execution hardware and a hardware-based Multiplexer (MUX) to multiplex a fetch address of a future branch and a preloaded branch fetch address to create an index hash value that is used to index a branch target prediction table for execution by a processor core, in order to reduce branch mis-prediction by preloading.

First claim

What is claimed is:

1. A computer processor comprising:
a Multiplex device (MUX) comprised of a first input, a second input, and one MUX output, wherein the first input is coupled to a source of a branch fetch address, the second input is coupled to a read port of a branch computation register that stores a first branch fetch address of a branch instruction to be predicted, and the MUX output is coupled to a branch target prediction table;
a branch target register that provides a predicted target address to the branch target prediction table;
logic circuits for:
autonomously determining when a preload instruction is being executed; and
in response to autonomously determining the preload instruction is being executed:
directing the MUX to select the first branch fetch address of the branch instruction from the branch computation register;
reading an index value at the MUX output;
computing, via an index hash logic circuit, an index hash of the index value at the MUX output, wherein the index hash logic circuit is directly connected at an input to the MUX output and at an output to the branch target prediction table;
indexing the branch target prediction table using the index hash; and
writing the predicted target address from the branch target register to the branch target prediction table, wherein the predicted target address is written at a location within the branch target prediction table corresponding to the index hash; and

a processor core coupled to the branch target prediction table, wherein the processor core:
in response to fetching the branch instruction after writing the predicted target address at the location within the branch target prediction table corresponding to the index hash, provides the first branch fetch address to the first input of the MUX;
reads the branch target prediction table at a hash index calculated from the first branch fetch address to retrieve the predicted target address; and
in response to the branch instruction being predicted taken, redirects fetching to the predicted target address stored in the branch target prediction table.

2. The computer processor of claim 1 , further comprising a complex branch execution logic circuit for executing one or more complex branch instructions using the read port of the branch computation register.

3. The computer processor of claim 2 , wherein the complex branch execution logic circuit further comprises logic for executing a decrement-and-branch-if-zero instruction.

4. The computer processor of claim 2 , wherein the complex branch execution logic circuit comprises logic for executing a compare-and-branch instruction.

5. A data processing system comprising:
a memory;
a system bus coupled to the memory; and
a computer processor coupled to the system bus, wherein the computer processor comprises:
a Multiplex device (MUX) comprised of a first input, a second input, and one MUX output, wherein the first input is coupled to a source of a branch fetch address, the second input is coupled to a read port of a branch computation register that stores a first branch fetch address of a branch instruction to be predicted, and the MUX output is coupled to a branch target prediction table;
a branch target register that provides a predicted target address to the branch target prediction table;
logic circuits that:
autonomously determine when a preload instruction is being executed; and
in response to autonomously determining the preload instruction is being executed:
direct the MUX to select the first branch fetch address of the of the branch instruction from the branch computation register;
read an index value at the MUX output;
compute, via an index hash logic circuit, an index hash of the index value at the MUX output, wherein the index hash logic circuit is directly connected at an input to the MUX output and at an output to the branch target prediction table;
index the branch target prediction table using the index hash; and
write the predicted target address from the branch target register to the branch target prediction table, wherein the predicted target address is written at a location within the branch target prediction table corresponding to the index hash; and

a processor core coupled to the branch target prediction table, wherein the processor core:
in response to fetching the branch instruction after writing the predicted target address at the location within the branch target prediction table corresponding to the index hash, provides the first branch fetch address to the first input of the MUX;
reads the branch target prediction table at a hash index calculated from the first branch fetch address to retrieve the predicted target address; and
in response to the branch instruction being predicted taken, redirects fetching to the predicted target address stored in the branch target prediction table.

6. The data processing system of claim 5 , further comprising a complex branch execution logic circuit for executing one or more complex branch instructions using the read port of the branch computation register.

7. The data processing system of claim 6 , wherein the complex branch execution logic circuit further comprises logic that executes a decrement-and-branch-if-zero instruction.

8. The data processing system of claim 6 , wherein the complex branch execution logic circuit further comprises logic that executes a compare-and-branch instruction.

9. A computer processor comprising:
a Multiplex device (MUX) comprised of a first input, a second input, and one MUX output, wherein the first input is coupled to a source of a hash index of a branch fetch address, and the second input is coupled to an output of a hash logic circuit, wherein an input of the hash logic circuit is directly coupled to a read port of a branch computation register that stores a first branch fetch address of a branch instruction to be predicted, and wherein the MUX output is coupled to a branch target prediction table;
a branch target register that provides a predicted target address to the branch target prediction table;
logic circuits for:
autonomously determining when a preload instruction is being executed; and
in response to autonomously determining the preload instruction is being executed:
computing, via the hash logic circuit, a hash of the first branch fetch address;
directing the MUX to select the hash of the first branch fetch address at the output of the hash logic circuit;
reading an index hash at the MUX output;
indexing the branch target prediction table using the index hash; and
writing the predicted target address from the branch target register to the branch target prediction table, wherein the predicted target address is written at a location within the branch target prediction table corresponding to the index hash; and

a processor core coupled to the branch target prediction table, wherein the processor core:
in response to fetching the branch instruction after writing the predicted target address at the location within the branch target prediction table corresponding to the index hash, calculates a hash index on the first branch fetch address;
reads the branch target prediction table at the calculated hash index to retrieve the predicted target address; and
in response to the branch instruction being predicted taken, redirects fetching to the predicted target address stored in the branch target prediction table.

10. The computer processor of claim 9 , further comprising a complex branch execution logic circuit for executing one or more complex branch instructions using the read port of the branch computation register.

11. The computer processor of claim 10 , wherein the co

Assignees

• Alexander Gregory W
• Blanchard Anton
• Miller Ii Milton D
• Venton Todd A
• Wright Kenneth L
• IBM

Inventors

• Alexander Gregory W
• Blanchard Anton
• Miller Ii Milton D
• Venton Todd A
• Wright Kenneth L

Classifications

• G06F9/3005

  to perform operations for flow control · CPC title

• G06F9/3806

  using address prediction, e.g. return stack, branch history buffer · CPC title

• G06F9/3804 Primary

  for branches, e.g. hedging, branch folding · CPC title

• G06F9/30043 Primary

  LOAD or STORE instructions; Clear instruction · CPC title