Method and apparatus for branch prediction based on branch targets utilizing tag and data arrays

• US 7,266,676 B2
• Filed: 03/21/2003
• Issued: 09/04/2007
• Est. Priority Date: 03/21/2003
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Tran, Thang M., Singh, Ravi Pratap, Duraiswamy, Deepa, Kannan, Srikanth
• Primary Examiner(s): Lai; Vincent
• Application Number:
  US10/394,820
• Publication Number:
  US 20040186985A1
• Time in Patent Office: 1,628 Days
• Field of Search: 712/233, 712/237, 712/238, 712/239, 712/240
• US Class Current: 712/238
• CPC Class Codes: A61P 31/04 Antibacterial agents
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• 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

Abstract

Methods and apparatus are provided for branch prediction in a digital processor. A method includes providing a branch target buffer having a tag array and a data array, wherein each entry in the tag array provides an index to a corresponding entry in the data array, storing in a selected entry in the tag array information representative of a branch target of a current branch instruction, storing in a corresponding entry in the data array information representative of a branch target of a next branch instruction, and providing the information representative of the branch target of the next branch instruction in response to a match to an entry in the tag array. The information representative of the branch target of the next branch instruction may include a taken branch target address of the next branch instruction and an offset value. The offset value may represent an address of a next sequential instruction following the next branch instruction.

Claims

1. A method for branch prediction in a digital processor, comprising:

providing a branch target buffer having a tag array and a data array, wherein each entry in the tag array provides an index to a corresponding entry in the data array;

storing in a selected entry in the tag array a target address of a current branch instruction;

storing in a corresponding entry in the data array a target address of a next branch instruction; and

providing the target address of the next branch instruction in response to accessing the tag array with the target address of the current branch instruction.

2. A method as defined in claim 1, wherein storing a target address of a current branch instruction comprises storing a taken branch target address of the current branch instruction in the case of a taken branch.

3. A method as defined in claim 1, wherein storing a target address of a current branch instruction comprises storing an address of a next sequential instruction following the current branch instruction in the case of a not taken branch.

4. A method as defined in claim 1, wherein storing a target address of a next branch instruction comprises storing a taken branch target address of the next branch instruction and an offset value.

5. A method as defined in claim 4, wherein the offset value represents an address of a next sequential instruction following the next branch instruction.

6. A method as defined in claim 5, further comprising performing a block size calculation by subtracting the offset value from a current fetch address and redirecting instruction fetching to the branch target buffer when the difference between the offset value and the current fetch address is less than a predetermined value.

7. A method as defined in claim 6, wherein the predetermined value represents the length of a fetch buffer.

8. A method as defined in claim 1, wherein storing a target address of a next branch instruction further comprises storing prediction information corresponding to the next branch instruction.

9. A method as defined in claim 8, wherein storing a target address of a next branch instruction further comprises updating the prediction information following execution of the next branch instruction.

10. A method as defined in claim 8, further comprising selecting a taken branch target address of the next branch instruction or a next sequential address in response to the prediction information.

11. A method as defined in claim 1, wherein providing the target address of the next branch instruction comprises determining when the next branch instruction is to be executed in response to the target address of the next branch instruction.

12. A method as defined in claim 1, further comprising storing the target address of the next branch instruction in a buffer for use upon branch resolution of the current branch instruction.

13. A method as defined in claim 1, wherein storing a target address of a next branch instruction comprises storing a taken branch target address of the next branch instruction and a not taken branch target address of the next branch instruction.

14. Apparatus for predicting branches in a program executed on a digital processor, comprising:

a branch target buffer having a tag array and a data array, wherein each entry in the tag array provides an index to a corresponding entry in the data array;

means for storing in a selected entry in the tag array a target address of a current branch instruction;

means for storing in a corresponding entry in the data array a target address of a next branch instruction; and

means for providing from the branch target buffer the target address of the next branch instruction in response to accessing the tag array with the target address of the current branch instruction.

15. Apparatus as defined in claim 14, wherein said means for storing a target address of a current branch instruction comprises means for storing a taken branch target address of the current branch instruction in the case of a taken branch.

16. Apparatus as defined in claim 14, wherein said means for storing a target address of a current branch instruction comprises means for storing an address of a next sequential instruction following the current branch instruction in the case of a not taken branch.

17. Apparatus as defined in claim 14, wherein said means for storing a target address of a next branch instruction comprises means for storing a taken branch target address of the next branch instruction and an offset value.

18. Apparatus as defined in claim 17, wherein the offset value represents an address of a next sequential instruction following the next branch instruction.

19. Apparatus as defined in claim 14, wherein said means for storing a target address of a next branch instruction comprises means for storing a taken branch target address of the next branch instruction and a not taken branch target address of the next branch instruction.

20. Apparatus as defined in claim 18, further comprising a block size calculation unit for subtracting the offset value from a current fetch address and for redirecting instruction fetching to the branch target buffer when the difference between the offset value and the current fetch address is less than a predetermined value.

21. Apparatus as defined in claim 20, wherein the predetermined value represents the length of a fetch buffer.

22. Apparatus as defined in claim 21, wherein the block size calculation unit comprises a subtractor for subtracting the offset value from the current fetch address and a comparator for redirecting instruction fetching to the branch target buffer when the difference between the offset value and the current fetch address is less than the predetermined value.

23. Apparatus as defined in claim 14, wherein said means for storing a target address of a next branch instruction comprises means for storing prediction information corresponding to the next branch instruction.

24. Apparatus as defined in claim 23, wherein said means for storing a target address of a next branch instruction further comprises means for updating the prediction information following execution of the next branch instruction.

25. Apparatus as defined in claim 23, further comprising means for selecting a taken branch target address of the next branch instruction or a next sequential address in response to the prediction information.

26. Apparatus as defined in claim 14, further comprising a buffer for storing the target address of the next branch instruction for use upon branch resolution of the current branch instruction.

27. Apparatus for predicting branches in a program executed on a digital processor, comprising:

a branch target buffer having a tag array and a data array, wherein each entry in the tag array provides an index to a corresponding entry in the data array, wherein a selected entry in the tag array stores a target address of a current branch instruction and a corresponding entry in the data array stores a taken branch target address of a next branch instruction, a not taken branch target address of the next branch instruction and prediction information corresponding to the next branch instruction;

an address selector for selecting the taken branch target address or the not taken branch target address in response to the prediction information; and

a block size calculation unit for redirecting instruction fetching to the branch target buffer when the difference between the not taken branch target address and the current fetch address is less than a predetermined value.

28. Apparatus as defined in claim 27, wherein the not taken branch target address comprises an address of a next sequential instruction following the next branch instruction.

29. Apparatus as defined in claim 27, wherein the block size calculation unit comprises a subtractor for subtracting the not taken branch target address from the current fetch address and a comparator for redirecting instruction fetching to the branch target buffer when the difference between the not taken branch target address and the current fetch address is less than the predetermined value.

30. Apparatus as defined in claim 27, further comprising a buffer for storing the target address of the next branch instruction for use upon branch resolution of the current branch instruction.