System and method for branch prediction using two branch history tables and presetting a global branch history register

• US 10,209,992 B2
• Filed: 10/31/2014
• Issued: 02/19/2019
• Est. Priority Date: 04/25/2014
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Inventors: Wilson, Sophie, Barrett, Geoffrey
• Primary Examiner(s): Mehta, Jyoti
• Application Number:
  US14/530,038
• Publication Number:
  US 20150309794A1
• Time in Patent Office: 1,572 Days
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3844 using dynamic branch prediction, e.g. using branch history tables
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A method and system for branch prediction are provided herein. The method includes executing a program, wherein the program comprising multiple procedures, and setting bits in a taken branch history register to indicate whether a branch is taken or not taken during execution of instructions in the program. The method further includes the steps of calling a procedure in the program and overwriting, responsive to calling the procedure, the contents of the taken branch history register to a start address for the procedure.

Claims

1. A method, comprising:

providing a program to be executed in accordance with a speculative address;

executing the program, the program comprising a procedure;

setting bits in a taken branch history register to indicate whether a branch is taken or not taken during execution of instructions in the program;

calling the procedure in the program; and

overwriting, responsive to calling the procedure, contents of the taken branch history register to a start address for the procedure;

accessing, using a hash block, a first branch history table based on contents of the taken branch history register for a first prediction of whether a current branch will be taken or not taken;

accessing, using the hash block, a second branch history table based on the contents of the taken branch history register for a second prediction of whether the current branch will be taken or not taken; and

determining whether the first prediction or the second prediction is used based on whether a selection value in a selection entry of a selector table is equal to or greater than a threshold value.

2. The method of claim 1, wherein accessing the first branch history table further comprises:

accessing the first branch history table based on the contents of the taken branch history register and a program counter register.

3. The method of claim 2, wherein accessing the first branch history table further comprises:

generating an index based on the contents of the taken branch history register and the program counter register to access an entry in the first branch history table, wherein the entry includes the first prediction.

4. The method of claim 3, wherein generating the index further comprises:

hashing the contents of the taken branch history register to produce a result having a number of bits that is less than a number of bits in the taken branch history register.

5. The method of claim 2, further comprising:

accessing the second branch history table based on the contents of the taken branch history register and the program counter register, wherein the first branch history table has more entries than the second branch history table.

6. The method of claim 5, wherein accessing the second branch history table further comprises:

generating an index based on the contents of the taken branch history register and the program counter register to access an entry in the second branch history table, wherein the entry includes the second prediction.

7. The method of claim 6, wherein generating the index further comprises:

hashing contents of the program counter register to produce a result having a number of bits that is less than a number of bits in the program counter register.

8. The method of claim 7, further comprising:

using the index to access the selection entry in the selection table.

9. The method of claim 6, further comprising:

using the index to access an update entry in an update table that stores an update value that indicates whether the first branch history table or the second branch history table is more accurate in a prediction of whether the branch will be taken, and

suppressing updating a prediction value, corresponding to the branch, in the first branch history table based on the update value indicating that the second branch history table is more accurate than the first branch history table in the prediction of whether the branch is taken.

10. The method of claim 1, wherein the procedure comprises:

a section of code within the program that is accessed upon execution of a call instruction and has an instruction that returns program execution to a next instruction after the call instruction.

11. An apparatus, comprising:

an instruction cache; and

a branch prediction unit configured to supply a speculative address to the instruction cache, the branch prediction unit comprising;

a taken branch history register configured to store bits that indicate whether a branch is taken during execution of instructions in a program, wherein the program includes a procedure;

a preset circuit configured to overwrite contents of the taken branch history register to a start address for the procedure;

a first branch history table including a first prediction of whether a current branch will be taken or not taken;

a second branch history table including a second prediction of whether the current branch will be taken or not taken;

a selector table including a selection value in a selection entry; and

a hash block configured to determine whether the first prediction or the second prediction is used based on whether the selection value is equal to or greater than a threshold value.

12. The apparatus of claim 11, wherein the hash block is further configured to access an entry in the first branch history table based on the contents of the taken branch history register and a program counter register.

13. The apparatus of claim 12, wherein the hash block is further configured to generate an index based on the contents of the taken branch history register and the program counter register to access the entry in the first branch history table, wherein the entry includes the first prediction.

14. The apparatus of claim 13, wherein the hash block is further configured to generate the index by hashing the contents of the taken branch history register to produce a result having a number of bits that is less than a number of bits in the taken branch history register.

15. The apparatus of claim 12, wherein the hash block is further configured to access the second branch history table based on the contents of the taken branch history register and the program counter register.

16. The apparatus of claim 15, wherein the hash block is further configured to generate an index based on the contents of the taken branch history register and the program counter register to access an entry in the second branch history table that includes the second prediction.

17. The apparatus of claim 16, wherein the hash block is further configured to generate the index by hashing contents of the program counter register to produce a result having a number of bits that is less than a number of bits in the program counter register.

18. The apparatus of claim 17, wherein the hash block is further configured to use the index to access an entry in the selection table.

19. The apparatus of claim 18, further comprising:

an update table, wherein the hash block is configured to access an update entry in an update table that stores an update value that indicates whether the first branch history table or the second branch history table is more accurate in a prediction of whether the current branch will be taken, and

logic circuits configured to suppress an update of a prediction value, corresponding to the current branch, in the first branch history table based on the update value indicating that the second branch history table is more accurate than the first branch history table in the prediction of whether the current branch is taken.

20. The apparatus of claim 11, wherein the procedure comprises:

a section of code within the program that is accessed upon execution of a call instruction; and

an instruction that returns program execution to a next instruction after the call instruction.

21. An apparatus, comprising:

a taken branch history register configured to store bits that indicate whether a branch is taken during execution of instructions in a program, wherein the program includes a procedure;

a preset circuit configured to overwrite contents of the taken branch history register to a start address for the procedure;

a first branch history table including a first prediction of whether a current branch will be taken or not taken;

a second branch history table including a second prediction of whether the current branch will be taken or not taken;

a selector table including a selection value in a selection entry; and

a hash block configured to determine whether the first prediction or the second prediction is used based on whether the selection value is equal to or greater than a threshold value.