Reducing the fetch time of target instructions of a predicted taken branch instruction

• US 20060236080A1
• Filed: 04/19/2005
• Published: 10/19/2006
• Est. Priority Date: 04/19/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tsuchiya, Kenichi, Olsson, Brett, Doing, Richard William
• Granted Patent: US 7,437,543 B2
• Time in Patent Office: Days
• US Class Current: 712/238
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables

Abstract

A method and processor for reducing the fetch time of target instructions of a predicted taken branch instruction. Each entry in a buffer, referred to herein as a “branch target buffer”, may store an address of a branch instruction predicted taken and the instructions beginning at the target address of the branch instruction predicted taken. When an instruction is fetched from the instruction cache, a particular entry in the branch target buffer is indexed using particular bits of the fetched instruction. The address of the branch instruction in the indexed entry is compared with the address of the instruction fetched from the instruction cache. If there is a match, then the instructions beginning at the target address of that branch instruction are dispatched directly behind the branch instruction. In this manner, the fetch time of target instructions of a predicted taken branch instruction is reduced.

Claims

1. A method for reducing the normal fetch time of a predicted taken branch instruction comprising the steps of:

accessing an instruction cache to fetch an instruction;

indexing into an entry in a buffer using bits from said instruction fetched from said instruction cache, wherein said buffer comprises a plurality of entries, wherein each of said plurality of entries comprises an address of a branch instruction, a plurality of instructions beginning at a target address of said branch instruction, prediction information for any of said plurality of instructions that are branch instructions and an address of a next fetch group;

comparing an address of said instruction fetched from said instruction cache with said address of said branch instruction in said indexed entry of said buffer; and

selecting said plurality of instructions beginning at said target address of said branch instruction in said indexed entry of said buffer if said address of said instruction fetched from said instruction cache matches with said address of said branch instruction in said indexed entry of said buffer.

2. The method as recited in claim 1 further comprising the step of:

selecting said instruction retrieved from accessing said instruction cache if none of said plurality of instructions selected from said indexed entry of said buffer is a branch instruction.

3. The method as recited in claim 2 further comprising the step of:

selecting prediction information obtained from a branch history table if none of said plurality of instructions selected from said indexed entry of said buffer is a branch instruction.

4. The method as recited in claim 1 further comprising the step of:

selecting said prediction information from said indexed entry of said buffer if said address of said instruction fetched from said instruction cache matches with said address of said branch instruction in said indexed entry of said buffer.

5. The method as recited in claim 1 further comprising the step of:

determining if any of said plurality of instructions selected is a branch instruction.

6. The method as recited in claim 5 further comprising the step of:

loading a displacement and an address of a first of said plurality of instructions selected in a first and a second register, respectively, wherein said first of said plurality of instructions selected is a branch instruction predicted taken.

7. The method as recited in claim 6 further comprising the steps of:

updating said prediction information stored in said indexed entry in said buffer if a prediction of said first of said plurality of instructions selected is incorrect; and

updating said prediction information stored in a branch history table if said prediction of said first of said plurality of instructions selected is incorrect.

8. The method as recited in claim 1 further comprising the steps of:

loading a buffer queue coupled to said buffer with instructions selected from one of said instruction cache and said indexed entry in said buffer;

loading said buffer queue coupled to said buffer with prediction information selected from one of a branch history table and said indexed entry in said buffer; and

writing said instructions and prediction information stored in said buffer queue to said buffer if said instruction fetched from said instruction cache was a branch instruction actually taken.

9. A processor, comprising:

an instruction cache configured to store instructions, wherein an instruction is fetched from said instruction cache;

a buffer, wherein said buffer comprises a plurality of entries, wherein each of said plurality of entries in said buffer comprises an address of a branch instruction, a plurality of instructions beginning at a target address of said branch instruction, prediction information for any of said plurality of instructions that are branch instructions and an address of a next fetch group, wherein an entry of said plurality of entries in said buffer is indexed; and

a first selection mechanism coupled to said instruction cache and said buffer, wherein said selection mechanism is configured to select said plurality of instructions beginning at said target address of said branch instruction in said indexed entry if an address of said instruction fetched from said instruction cache matches with said address of said branch instruction in said indexed entry of said buffer.

10. The processor as recited in claim 9, wherein said entry in said buffer is indexed using bits from said instruction fetched from said instruction cache.

11. The processor as recited in claim 9 further comprising:

a second selection mechanism coupled to said first selection mechanism, wherein said second selection mechanism is configured to select an address of one of said plurality of instructions selected to be loaded into an instruction queue.

12. The processor as recited in claim 9 further comprising:

a third selection mechanism coupled to said buffer and to a branch history table, wherein said third selection mechanism is configured to select said prediction information from said indexed entry of said buffer if said address of said instruction fetched from said instruction cache matches with said address of said branch instruction in said indexed entry of said buffer.

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

a decode logic unit coupled to said first selection mechanism, wherein said decode logic unit is configured to determine if any of said plurality of instructions selected is a branch instruction if said address of said instruction fetched from said instruction cache matches with said address of said branch instruction in said indexed entry of said buffer.

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

a selection logic unit coupled to said third selection mechanism, wherein said selection logic unit is configured to select a first of said plurality of instructions selected.

15. The processor as recited in claim 14, wherein said first of said plurality of instructions selected is a branch instruction predicted taken.

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

a buffer reload unit coupled to a buffer queue, said buffer and to said branch history table, wherein said buffer reload unit is configured to update said prediction information stored in said indexed entry in said buffer if a prediction of said first of said plurality of instructions selected is incorrect, wherein said buffer reload unit is further configured to update said prediction information stored in said branch history table if said prediction of said first of said plurality of instructions selected is incorrect.

17. The processor as recited in claim 9 further comprising:

a buffer queue coupled to said buffer, wherein said buffer queue is configured to store instructions selected from said instruction cache, wherein said buffer queue is further configured to store prediction information selected from a branch history table.

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

a buffer reload unit coupled to said buffer queue and to said buffer, wherein said buffer reload unit is configured to write said instructions and prediction information stored in said buffer queue to said buffer if said instruction fetched from said instruction cache was a branch instruction actually taken.