BRANCH PREDICTION FOR INDIRECT BRANCH INSTRUCTIONS

• US 20200133678A1
• Filed: 10/26/2018
• Published: 04/30/2020
• Est. Priority Date: 10/26/2018
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gellerich, Wolfgang, Held, Peter M., Koch, Gerrit, Schwidefsky, Martin
• Granted Patent: US 11,099,851 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30058 Conditional branch instructions
• CPC Class Codes: G06F 9/3012 Organisation of register space, e.g. banked or distributed register file
• CPC Class Codes: G06F 9/323 for indirect branch instructions
• 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

Examples of techniques for branch prediction for indirect branch instructions are described herein. An aspect includes detecting a first register setting instruction in an instruction pipeline of a processor, wherein the first register setting instruction stores a target instruction address in a first register of the processor. Another aspect includes looking up the first register setting instruction in a first table. Another aspect includes, based on there being a hit for the first register setting instruction in the first table, determining instruction address data corresponding to a first indirect branch instruction that is associated with the first register setting instruction in a first entry in the first table. Another aspect includes updating a branch prediction for the first indirect branch instruction in a branch prediction logic of the processor based on the target instruction address.

Claims

1. A system, comprising a processor to:

detect a first register setting instruction in an instruction pipeline of the processor, wherein the first register setting instruction stores a target instruction address in a first register of the processor;

look up the first register setting instruction in a first table;

based on there being a hit for the first register setting instruction in the first table, determine instruction address data corresponding to a first indirect branch instruction that is associated with the first register setting instruction in a first entry in the first table; and

update a branch prediction for the first indirect branch instruction in a branch prediction logic of the processor based on the target instruction address.

2. The system of claim 1, wherein the instruction address data corresponding to the first indirect branch instruction in the first entry in the first table comprises a hash derived from a full instruction address of the first indirect branch instruction.

3. The system of claim 2, wherein the hash derived from the full instruction address of the first indirect branch instruction is based on a hash function that corresponds to a hash function that is used in the branch prediction logic of the processor.

4. The system of claim 1, wherein the processor is to:

store instruction address data corresponding to the first register setting instruction in a first entry in a second table, the first entry in the second table being associated with the first register.

5. The system of claim 4, wherein the instruction address data corresponding to the first register setting instruction in the first entry in the second table comprises a hash derived from a full instruction address of the first register setting instruction.

6. The system of claim 4, wherein the processor is to:

detect a second indirect branch instruction in the instruction pipeline of the processor;

identify a second register that is used by the second indirect branch instruction;

look up the second register in the second table;

determine instruction address data corresponding to a second register setting instruction that is associated with the second register in a second entry in the second table; and

store a second entry in the first table, the second entry in the first table including instruction address data corresponding to the second register setting instruction associated with instruction address data corresponding to the second indirect branch instruction.

7. The system of claim 1, wherein the target instruction address is a full instruction address.

8. A computer-implemented method, comprising:

detecting a first register setting instruction in an instruction pipeline of a processor, wherein the first register setting instruction stores a target instruction address in a first register of the processor;

looking up the first register setting instruction in a first table;

based on there being a hit for the first register setting instruction in the first table, determining instruction address data corresponding to a first indirect branch instruction that is associated with the first register setting instruction in a first entry in the first table; and

updating a branch prediction for the first indirect branch instruction in a branch prediction logic of the processor based on the target instruction address.

9. The computer-implemented method of claim 8, wherein the instruction address data corresponding to the first indirect branch instruction in the first entry in the first table comprises a hash derived from a full instruction address of the first indirect branch instruction.

10. The computer-implemented method of claim 9, wherein the hash derived from the full instruction address of the first indirect branch instruction is based on a hash function that corresponds to a hash function that is used in the branch prediction logic of the processor.

11. The computer-implemented method of claim 8, comprising:

storing instruction address data corresponding to the first register setting instruction in a first entry in a second table, the first entry in the second table being associated with the first register.

12. The computer-implemented method of claim 11, wherein the instruction address data corresponding to the first register setting instruction in the first entry in the second table comprises a hash derived from a full instruction address of the first register setting instruction.

13. The computer-implemented method of claim 11, comprising:

detecting a second indirect branch instruction in the instruction pipeline of the processor;

identifying a second register that is used by the second indirect branch instruction;

looking up the second register in the second table;

determining instruction address data corresponding to a second register setting instruction that is associated with the second register in a second entry in the second table; and

storing a second entry in the first table, the second entry in the first table including instruction address data corresponding to the second register setting instruction associated with instruction address data corresponding to the second indirect branch instruction.

14. The computer-implemented method of claim 8, wherein the target instruction address is a full instruction address.

15. An apparatus, comprising hardware logic configured to:

detect a first register setting instruction in an instruction pipeline of a processor, wherein the first register setting instruction stores a target instruction address in a first register of the processor;

look up the first register setting instruction in a first table;

based on there being a hit for the first register setting instruction in the first table, determine instruction address data corresponding to a first indirect branch instruction that is associated with the first register setting instruction in a first entry in the first table; and

update a branch prediction for the first indirect branch instruction in a branch prediction logic of the processor based on the target instruction address.

16. The apparatus of claim 15, wherein the instruction address data corresponding to the first indirect branch instruction in the first entry in the first table comprises a hash derived from a full instruction address of the first indirect branch instruction.

17. The apparatus of claim 16, wherein the hash derived from the full instruction address of the first indirect branch instruction is based on a hash function that corresponds to a hash function that is used in the branch prediction logic of the processor.

18. The apparatus of claim 15, wherein the hardware logic is to:

store instruction address data corresponding to the first register setting instruction in a first entry in a second table, the first entry in the second table being associated with the first register.

19. The apparatus of claim 18, wherein the instruction address data corresponding to the first register setting instruction in the first entry in the second table comprises a hash derived from a full instruction address of the first register setting instruction.

20. The apparatus of claim 18, wherein the hardware logic is to:

detect a second indirect branch instruction in the instruction pipeline of the processor;

identify a second register that is used by the second indirect branch instruction;

look up the second register in the second table;

determine instruction address data corresponding to a second register setting instruction that is associated with the second register in a second entry in the second table; and

store a second entry in the first table, the second entry in the first table including instruction address data corresponding to the second register setting instruction associated with instruction address data corresponding to the second indirect branch instruction.