Two-level branch prediction cache

Claim 2

In a computer system that includes decode logic responsive to encountered instructions having addresses, a branch prediction device comprising: a first level branch prediction cache (BPC) having a first number N1 of lines for storing prediction information on up to N1 previously encountered branch instructions, each line in said first level BPC being configured to store an entry providing prediction information at a first level of detail, said first level BPC being responsive to a first set of address bits of an encountered instruction, and including first means for enabling a given first level BPC entry to be output in the event that said first set of address bits and the given first level BPC entry satisfy a predetermined condition; and a second level BPC having a second number N2 of lines, larger than said first number of lines, for storing prediction information on up to N2 previously encountered branch instructions, each line in said second level BPC being configured to store an entry providing prediction information at a second level of detail, lower than said first level of detail, said second level BPC being responsive to a second set of address bits of the encountered instruction and including second means for enabling a second level BPC entry to be output for use in the event that said predetermined condition is not met.

Claim 3

The branch prediction device of claim 1 wherein said first level BPC is fully associative.

Claim 4

The branch prediction device of claim 1 wherein said second level BPC is direct mapped.

Claim 5

The branch prediction device of claim 1, wherein said first set of address bits includes a first subset of address bits from an input program counter (PC) containing the address of the encountered instruction, and said second set of address bits includes a second subset of address bits from the input PC.

Claim 6

The branch prediction device of claim 1 wherein the said second means enables a second level BPC entry to be output in response to said second set of address bits regardless of whether said predetermined condition is met.

Claim 7

The branch prediction device of claim 1, wherein said prediction information stored in each line of said first level BPC comprises: an address of a previously encountered branch instruction; a full target address to which said previously encountered branch instruction last branched; and target instruction information starting at said target address; and wherein said first means for enabling includes means for communicating said target instruction information to the decode logic.

Claim 8

The branch prediction device of claim 6, wherein said prediction information stored in each line of said first level BPC further comprises branch history information representing the direction taken during at least one previous execution of said previously encountered branch instruction.

Claim 9

The branch prediction device of claim 6, wherein said target instruction information comprises 24 instruction bytes.

Claim 10

The branch prediction device of claim 6, wherein said target instruction information includes a plurality of groups of instruction bytes.

Claim 11

The branch prediction device of claim 9, wherein each of said plurality of groups of instruction bytes comprises eight instruction bytes.

Claim 12

The branch prediction device of claim 9, wherein said plurality of groups comprises three groups.

Claim 13

In a computer system that includes decode logic responsive to encountered instructions having addresses, a branch prediction device comprising: a first level branch prediction cache (BPC) having a first number N1 of lines for storing prediction information on up to N1 previously encountered branch instructions, each line in said first level BPC being configured to store an entry providing prediction information at a first level of detail, said first level BPC being responsive to a first set of address bits of an encountered instruction, and including a first associative memory, said first associative memory enabling a given first level BPC entry to be output in the event that said first set of address bits results in a match associated with said given first level BPC entry; and a second level BPC having a second number N2 of lines, larger than said first number of lines, for storing prediction information on up to N2 previously encountered branch instructions, each line in said second level BPC being configured to store an entry providing prediction information at a second level of detail, lower than said first level of detail, said second level BPC being responsive to a second set of address bits of the encountered instruction, and including a second memory, said second memory enabling a second level BPC entry to be output for use in the event that said first set of address bits does not result in a match associated with any first level BPC entry.

Claim 14

In a computer system that includes decode logic responsive to encountered instructions having addresses, a branch prediction device comprising: a first level branch prediction cache (BPC) having a first number N1 of lines for storing prediction information on up to N1 previously encountered branch instructions, each line in said first level BPC being configured to store an entry providing prediction information at a first level of detail, said first level BPC being responsive to a first set of address bits of an encountered instruction, and including a first associative memory, said first associative memory enabling a given first level BPC entry to be output in the event that said first set of address bits results in a match associated with said given first level BPC entry; and a second level BPC having a second number N2 of lines, larger than said first number of lines, for storing prediction information on up to N2 previously encountered branch instructions, each line in said second level BPC being configured to store an entry providing prediction information at a second level of detail, lower than said first level of detail, said second level BPC being responsive to a second set of address bits of the encountered instruction, and including a second memory, said second memory enabling a second level BPC entry to be output for use in the event that said first set of address bits does not result in a match associated with any first level BPC entry.

Claim 15

The branch prediction device of claim 12 wherein said second level BPC is direct mapped.

Claim 16

The branch prediction device of claim 12, wherein said first set of address bits includes a first subset of address bits from an input program counter (PC) containing the address of the encountered instruction, and said second set of address bits includes a second subset of address bits from the input PC.

Claim 17

The branch prediction device of claim 12 wherein said second memory enables a second level BPC entry to be output in response to said second set of address bits regardless of whether said first set of address bits results in a match associated with any first level BPC entry.

Claim 18

The branch prediction device of claim 12, wherein said prediction information stored in each line of said first level BPC comprises: an address of a previously encountered branch instruction; a full target address to which said previously encountered branch instruction last branched; and target instruction information starting at said target address; and wherein said target instruction information is coupled to said decode logic subsequent to said match associated with said given first level BPC entry.

Claim 19

The branch prediction device of claim 16, wherein said prediction information stored in each line of said first level BPC further comprises branch history information representing the direction taken during at least one previous execution of said previously encountered branch instruction.

Claim 20

The branch prediction device of claim 16 wherein said target instruction information comprises 24 instruction bytes.

Claim 21

The branch prediction device of claim 16, wherein said target instruction information includes a plurality of groups of instruction bytes.

Claim 22

The branch prediction device of claim 19, wherein each of said plurality of groups of instruction bytes comprises eight instruction bytes.

Claim 23

The branch prediction device of claim 20, wherein said plurality of groups comprises three groups.

Claim 24

A branch prediction method comprising: providing a first branch prediction cache (BPC); providing a second BPC; presenting a first set of address bits of an encountered instruction to said first BPC; presenting a second set of address bits of the encountered instruction to said second BPC; reading a first set of information from said first BPC, if there is a match on said first set of address bits in said first BPC; enabling the output of said second BPC, at least if said match in said first BPC does not occur; and reading a second set of information from said second BPC, at least if said match in said first BPC does not occur.

Claim 25

A branch prediction method comprising: providing a first branch prediction cache (BPC); providing a second BPC; presenting a first set of address bits of an encountered instruction to said first BPC; presenting a second set of address bits of the encountered instruction to said second BPC; reading a first set of information from said first BPC, if there is a match on said first set of address bits in said first BPC; enabling the output of said second BPC, at least if said match in said first BPC does not occur; and reading a second set of information from said second BPC, at least if said match in said first BPC does not occur.

Claim 26

The branch prediction method of claim 22, wherein said first set of address bits includes a first subset of address bits from an input program counter (PC) containing the address of the encountered instruction, and said second set of address bits includes a second subset of address bits from the input PC.

Claim 27

The branch prediction method of claim 22 wherein said step of enabling the output of said second level BPC is performed regardless of whether said match in said first BPC occurs.

Claim 28

The branch prediction method of claim 22, wherein said first set of information includes: an address of a previously encountered branch instruction; a full target address to which said previously encountered branch instruction last branched; and target instruction information starting at said target address.

Claim 29

The branch prediction method of claim 25, wherein said first set of information further includes branch history information representing the direction taken during at least one previous execution of said previously encountered branch instruction.

Claim 30

The branch prediction method of claim 25, wherein said target instruction information comprises 24 instruction bytes.

Claim 31

The branch prediction method of claim 25, wherein said target instruction information includes a plurality of groups of instruction bytes.

Claim 32

The branch prediction device of claim 28, wherein each of said plurality of groups of instruction bytes comprises eight instruction bytes.

Claim 33

The branch prediction device of claim 29, wherein said plurality of groups comprises three groups.

Claim 34

A branch prediction method comprising: providing a first branch prediction cache (BPC); providing a second BPC; presenting a first set of address bits to said first BPC, said first set of address bits including a first subset of address bits from an input program counter (PC) containing the address of an encountered instruction; presenting a second set of address bits to said second BPC, said second set of address bits including a second subset of address bits from the input PC; if there is a match on said first set of address bits presented to said first BPC, reading a first set of information from said first BPC, said first set of information including an address of a previously encountered branch instruction, a full target address to which said previously encountered branch instruction last branched, branch history information representing the direction taken during at least one previous execution of said previously encountered branch instruction, and three groups of eight target instruction bytes, said instruction bytes starting at said target address; enabling an output of said second BPC; and if said match does not occur, reading a second set of information from said second BPC.

Claim 35

A branch prediction method comprising: providing a first branch prediction cache (BPC); providing a second BPC; presenting a first set of address bits to said first BPC, said first set of address bits including a first subset of address bits from an input program counter (PC) containing the address of an encountered instruction; presenting a second set of address bits to said second BPC, said second set of address bits including a second subset of address bits from the input PC; if there is a match on said first set of address bits presented to said first BPC, reading a first set of information from said first BPC, said first set of information including an address of a previously encountered branch instruction, a full target address to which said previously encountered branch instruction last branched, branch history information representing the direction taken during at least one previous execution of said previously encountered branch instruction, and three groups of eight target instruction bytes, said instruction bytes starting at said target address; enabling an output of said second BPC; and if said match does not occur, reading a second set of information from said second BPC.