Granted Patent B2

US 9,792,123 · App. 14/169,771 · Granted Oct 17, 2017

Abstract

Claims (55)

1. A method to predict a target address of an indirect branch instruction in a program executed by a processor, the method comprising:

storing in an indirect branch predicted target table a plurality of predicted target addresses for indirect branch instructions, each predicted target address being indexed by a combination of an indirect path history and a taken and not-taken history, the indirect path history comprising at least a portion of target addresses for a plurality of previous indirect branch instructions, the taken and not-taken history comprising outcomes for a plurality of previous conditional branch instructions;

receiving at an index generator information identifying an indirect branch instruction, the information identifying the indirect branch instruction comprising an address of the indirect branch instruction;

obtaining at the index generator a running indirect path history and a running taken and not-taken history, the running indirect path history comprising at least a portion of predicted target addresses for a plurality of previously predicted indirect branch instructions, the running taken and not-taken history comprising outcomes for a plurality of previously predicted conditional branch instructions;

amending one of the running indirect path history and the running taken and not-taken history to comprise at least a portion of the address of the indirect branch instruction;

subsequent to the amending, combining at the index generator the running indirect path history and the running taken and not-taken history to generate an index for the identified indirect branch instruction;

identifying a predicted target address in the indirect branch predicted target table using the index for the identified indirect branch instruction; and

if the identified predicted target address is valid, predicting the target address of the identified indirect branch instruction to be the identified predicted target address.

2. The method according to claim 1 , wherein combining the running indirect path history and the running taken and not-taken history comprises performing a hashing function on at least a portion of the running indirect path history and at least a portion of the running taken and not-taken history.

3. The method according to claim 2 , wherein the hashing function is an exclusive-OR function.

4. The method according to claim 1 , further comprising:

receiving at an update logic unit information related to an executed indirect branch instruction, the information related to the executed indirect branch instruction comprising an actual target address for the executed indirect branch instruction; and

at the update logic unit, updating the indirect branch predicted target table based on the actual target address.

5. The method according to claim 4 , wherein updating the indirect branch predicted target table comprises:

obtaining at the update logic unit a committed indirect path history and a committed taken and not-taken history;

combining at the update logic unit the committed indirect path history and the committed taken and not-taken history to generate an index for the executed indirect branch instruction;

identifying a predicted target address of the indirect branch predicted target table using the index for the executed indirect branch instruction; and

replacing the predicted target address identified by the index for the executed indirect branch instruction with the actual target address for the executed indirect branch instruction.

6. The method according to claim 5 , wherein the committed indirect path history comprises at least a portion of actual target addresses for a plurality of previously executed indirect branch instructions.

7. The method according to claim 5 , wherein the committed taken and not-taken history comprises outcomes for a plurality of previously executed conditional branch instructions.

8. The method according to claim 1 , further comprising if the identified predicted target address is not valid, stalling a fetch stage of the processor.

9. The method according to claim 1 , wherein generating the index for the identified indirect branch instruction comprises combining only the running indirect path history and the running taken and not-taken history.

10. An indirect branch predictor logic unit to predict a target address of an indirect branch instruction in a program executed by a processor the indirect branch predictor logic unit comprising:

an indirect branch predicted target table configured to store a plurality of predicted target addresses for indirect branch instructions, each predicted target address being indexed by a combination of an indirect path history and a taken and not-taken history, the indirect path history comprising at least a portion of target addresses for a plurality of previous indirect branch instructions, the taken and not-taken history comprising outcomes for a plurality of previous conditional branch instructions;

an index generator in communication with the indirect branch predicted target table, the index generator configured to:

receive information identifying an indirect branch instruction, the information identifying the indirect branch instruction comprising an address of the indirect branch instruction;

obtain a running indirect path history and a running taken and not-taken history, the running indirect path history comprising at least a portion of predicted target addresses for a plurality of previously predicted indirect branch instructions, the running taken and not-taken history comprising outcomes for a plurality of previously predicted conditional branch instructions;

amend one of the running indirect path history and the running taken and not-taken history to comprise at least a portion of the address of the indirect branch instruction; and

subsequent to the amendment, combine the running indirect path history and the running taken and not-taken history to generate an index for the identified indirect branch instruction; and

a decision logic unit in communication with the indirect branch predicted target table, the decision logic unit configured to:

identify a predicted target address of the indirect branch predicted target table using the index for the identified indirect branch;

if the identified predicted target address is valid, predict the target address of the identified indirect branch instruction to be the identified predicted target address.

11. The indirect branch predictor logic unit according to claim 10 , wherein combining the running indirect path history and the running taken and not-taken history comprises performing a hashing function on a least a portion of the running indirect path history and at least a portion of the running taken and not-taken history.

12. The indirect branch predictor logic unit according to claim 11 , wherein the hashing function is an exclusive-OR function.

13. The indirect branch predictor logic unit according to claim 10 , further comprising an update logic unit in communication with the indirect branch predicted target table, the update logic unit configured to:

receive information related to an executed indirect branch instruction, the information related to the executed indirect branch instruction comprising an actual target address for the executed indirect branch instruction; and

update the indirect branch predicted target table based on the actual target address.

14. The indirect branch predictor logic unit according to claim 13 , wherein updating the indirect branch predicted target table comprises:

obtaining a committed indirect path history and a committed taken and not-taken history;

combining the committed indirect path history and the committed taken and not-taken history to generate an index for the executed indirect branch instruction;

identifying a predicted target address of the indirect branch predicted target table using the index for the executed indirect branch instruction; and

replacing the predicted target address identified by the index for the executed indirect branch instruction with the actual target address for the executed indirect branch instruction.

15. The indirect branch predictor logic unit according to claim 14 , wherein the committed indirect path history comprises at least a portion of actual target addresses for a plurality of previously executed indirect branch instructions.

16. The indirect branch predictor logic unit according to claim 14 , wherein the committed taken and not-taken history comprises outcomes for a plurality of previously executed conditional branch instructions.

17. The indirect branch predictor logic unit according to claim 10 , wherein the decision logic unit is further configured to, if the identified predicted target address is not valid, stall a fetch stage of the processor.

18. The indirect branch predictor logic unit according to claim 10 , wherein the index generator is configured to generate the index for the identified indirect branch instruction by combining only the running indirect path history and the running taken and not-taken history.

19. A non-transitory computer readable storage medium having encoded thereon computer readable program code for generating a processor comprising the indirect branch predictor logic unit of claim 10 .

20. A non-transitory computer readable storage medium having encoded thereon computer readable program code for generating a processor configured to perform a method comprising:

storing in an indirect branch predicted target table a plurality of predicted target addresses for indirect branch instructions, each predicted target address being indexed by a combination of an indirect path history and a taken and not-taken history, the indirect path history comprising at least a portion of target addresses for a plurality of previous indirect branch instructions, the taken and not-taken history comprising outcomes for a plurality of previous conditional branch instructions;

receiving at an index generator information identifying an indirect branch instruction, the information identifying the indirect branch instruction comprising an address of the indirect branch instruction;

obtaining at the index generator a running indirect path history and a running taken and not-taken history, the running indirect path history comprising at least a portion of predicted target addresses for a plurality of previously predicted indirect branch instructions, the running taken and not-taken history comprising outcomes for a plurality of previously predicted conditional branch instructions;

amending one of the running indirect path history and the running taken and not-taken history to comprise at least a portion of the address of the indirect branch instruction;

subsequent to the amending, combining at the index generator the running indirect path history and the running taken and not-taken history to generate an index for the identified indirect branch instruction;

identifying a predicted target address in the indirect branch predicted target table using the index for the identified indirect branch instruction; and

if the identified predicted target address is valid, predicting the target address of the identified indirect branch instruction to be the identified predicted target address.

Assignments (8)