METHOD AND SYSTEM FOR BRANCH TARGET PREDICTION USING PATH INFORMATION

• US 20030041230A1
• Filed: 12/30/1998
• Published: 02/27/2003
• Est. Priority Date: 12/30/1998
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: RAPPOPORT, LIHU, RONEN, RONNY, LEMPEL, ODED, KACEVAS, NICOLAS
• Granted Patent: US 6,601,161 B2
• Time in Patent Office: Days
• US Class Current: 712/238
• CPC Class Codes: G06F 9/30061 Multi-way branch instructions, e.g. CASE
• CPC Class Codes: G06F 9/322 for non-sequential address
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3848 using hybrid branch prediction, e.g. selection between prediction techniques

Abstract

A system and method for predicting a branch target for a current instruction in a microprocessor, the system comprising a cache storing indirect branch instructions and a path register. The path register is updated on certain branches by an XOR operation on the path register and the branch instruction, followed by the addition of one or more bits to the register. The cache is indexed by performing an operation on a portion of the current instruction address and the path register; the entry returned, if any, may be used to predict the target of the current instruction.

Claims

1. A system for predicting a branch target for a current branch instruction having a branch address in a processor, the system comprising:

a register holding a current register value, where at least a portion of the current register value is formed from a first computation, the first computation comprising a first operation on a previous register value and a set of bits from a previous branch address; and

a first table storing branch target values, the first table indexed by the result of second computation on the current register value and the branch address of the current branch instruction.

2. The system of claim 1 where the first operation is an XOR operation.

3. The system of claim 1 where the first computation further comprises:

a shift left operation; and

an OR operation.

4. The system of claim 2 further comprising a second table storing branch target values for indirect branches and branch target values for direct branches, where the first table stores branch target values for indirect branches.

5. The system of claim 4 where:

the-second table is a branch target buffer; and

the second table is indexed by a portion of the branch address of the current branch instruction.

6. The system of claim 3 where:

the first table is a cache;

the shift left operation shifts left one bit;

one operand of the OR operation is 0 if the previous branch address is for a first type of branch and 1 if the previous branch address is for a second type of branch.

7. The system of claim 6 where:

each branch target value corresponds to an indirect branch.

8. The system of claim 4 where:

the second table either provides a second table prediction and a type prediction for the current branch instruction or returns a second table miss;

the first table either provides a first table prediction for the current branch instruction or returns a first table miss; and

if, for the current branch instruction, a second table prediction is provided, a first table prediction is provided, and the type prediction is indirect, the system forms a branch target prediction from the contents of the first table.

9. The system of claim 1 further comprising:

a buffer storing branch target values, where;

the buffer either provides a buffer prediction for the current branch instruction or returns a buffer miss;

the first table either provides a first table prediction for the current branch instruction or returns a first table miss;

if a buffer prediction is provided, the system returns a prediction.

10. The system of claim 2 further comprising a second table storing branch target values for indirect branches and branch target values for direct branches, where:

the first table stores branch target values for indirect branches;

the first computation further comprises a shift left one bit operation and an OR operation, where one operand of the OR operation is 0 if the previous branch address is for a first type of branch and 1 if the previous branch address is for a second type of branch; and

an entry from the first table is returned as a prediction only if a second table hit occurs.

11. The system of claim 1 further comprising a second table having a plurality of entries, each entry storing a branch target value for a branch and a second table entry error counter, the second table entry error counter being recalculated when the second table entry provides a prediction;

where;

the first table comprises a plurality of entries, each entry storing a branch target value for an indirect branch;

if, for a second table entry, the second table error counter reaches a certain value, a first table entry corresponding to the second table entry is created; and

an entry from the first table is returned as a prediction only if a second table hit occurs.

12. A method for providing a predicted branch target for a current branch instruction, the current branch instruction having an address, the method comprising:

placing in a register the result of a first calculation on the register and a set of bits from an address of a completed branch instruction;

creating an index by performing a second calculation on the register and a set of bits from the address of the current branch instruction; and

using the index to find a target address for the second branch address in a first table, where the first table either provides a first table prediction for the current branch instruction or returns a first table miss.

13. The method of claim 12 where the first calculation comprises an XOR operation.

14. The method of claim 13 where the first calculation further comprises:

a shift left operation; and

an OR operation.

15. The method of claim 14 where:

each of a subset of the target addresses corresponds to an indirect branch.

16. The method of claim 14 further comprising:

creating a second table index from a calculation on the current branch instruction address; and

using the second table index to access a second table.

17. The method of claim 16 where the second table is a branch target buffer.

18. The method of claim 17 where the second table is a cache and the first calculation occurs as a result of an indirect branch or a direct branch.

19. The method of claim 12 further comprising:

accessing a second table to either provide a second table prediction and a type prediction for the current branch instruction or return a second table miss, the type prediction being a first type or a second type; and

if, for the current branch instruction, a second table prediction is provided, a first table prediction is provided, and the type prediction is a first type, forming a branch target prediction from the contents of the first table.

20. The method of claim 19 where:

the first table is a cache;

the second table is a cache;

the first type corresponds to an indirect branch; and

the second type corresponds to a direct branch.

21. The method of claim 15 further comprising the step of accessing a second table, where:

the second table comprises a plurality of second table entries; and

the first table comprises a plurality of first table entries, each first table entry being capable of providing a prediction, each first table entry in a subset of the first table entries corresponding to a second table entry.

22. The method of claim 21 where each second table entry comprises a second table prediction and a second table error counter, the second table error counter being recalculated when the second table entry provides a prediction, the method further comprising:

if, for a second table entry, the second table error counter reaches a certain value, a first table entry corresponding to the second table entry is created.

23. The method of claim 12 where the first table prediction is correct or incorrect, the method further comprising:

accessing a second table to either provide a second table prediction and a type prediction for the current branch instruction or return a second table miss, the type prediction being a first type or a second type, the second table prediction being correct or incorrect; and

if a second table prediction is provided and a first table prediction is provided, if the type prediction is a first type providing as a branch prediction the first table prediction and if the type prediction is a second type providing as a branch prediction the second table prediction.

24. The method of claim 23 where:

the first type corresponds to an indirect branch; and

if a second table prediction is provided, if the type of the current branch instruction is of the first type, and the second table prediction is incorrect, the second table entry is corrected.

25. The method of claim 24 where:

each target address is associated with an LRU counter;

if a second table prediction is provided, a first table prediction comprising a target address is provided, the type of the current branch instruction is of the first type, the second table prediction is incorrect, and the first table prediction is correct, the LRU associated with the target address is updated to indicate the associated target address is most recently used.

26. The method of claim 12 further comprising:

adding entries to the first table only for branch instructions which have not been marked as being predictable.

27. The method of claim 12 further comprising:

accessing a second table to either provide a second table prediction and a type prediction for the current branch instruction or return a second table miss, the type prediction being a first type or a second type; and

if the type prediction is of a first type, and a first table prediction is provided, the first table prediction is provided as a branch prediction;

if a second table miss is returned and a first table prediction is provided, the first table prediction is provided as a branch prediction;

if the type prediction is of a second type, a second table prediction is provided.

28. The method of claim 13 where the first table is a cache.

29. The method of claim 23 where the first table is a cache and the second table is a cache.

30. A system for predicting a branch target for a current branch address comprising:

an instruction cache;

an instruction decode unit;

an instruction fetch unit;

a register storing a history value, the history value computed from the XOR operation of the history value and a set of bits from a previous branch address, a shift of the history value, and an OR operation with a set of bits; and

a first cache holding branch target addresses for indirect branches, the first cache accessed by an index, the index being a set of bits from the result of an XOR operation of the history value and the current branch address.

31. The system of claim 30 further comprising:

a second cache, the second cache storing a set of branch target addresses, the second cache being indexed by a set of bits of the current branch address.