Granted Patent B2

US 9,298,467 · App. 14/153,188 · Granted Mar 29, 2016

Abstract

Claims (58)

1. A method to predict a target location of a switch statement in a program executed by a processor, the method comprising:

storing, in a register table maintained by a branch predictor, a current value for at least one monitored register, each monitored register having been identified as storing an input variable to a jump table switch statement, a jump table switch statement being a switch statement that has been compiled to a jump table;

receiving at the branch predictor an instruction for prediction;

prior to the received instruction being executed, determining, using the branch predictor, whether the received instruction writes to one of the monitored registers with an update value;

in response to determining that the received instruction writes to one of the monitored registers with an update value, updating the current value in the register table for the monitored register the received instruction writes to with the update value; and

predicting, using the branch predictor, the target location of a jump table switch statement instruction using the current value.

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

receiving at the branch predictor another instruction for prediction;

determining, at the branch predictor, whether the other instruction is a jump table switch statement instruction;

in response to determining that the other instruction is a jump table switch statement instruction, determining whether the register table comprises a current value for the input variable to the jump table switch statement instruction; and

in response to determining that the register table comprises a current value for the input variable to the jump table switch statement instruction, predicting the target location of the jump table switch statement instruction using the current value.

3. The method according to claim 2 , wherein determining whether the other instruction is a jump table switch statement instruction comprises determining if the other instruction has a predetermined pattern.

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

in response to determining that the other instruction is a jump table switch statement instruction, making the register used to store the input variable to the jump table switch statement instruction a monitored register.

5. The method according to claim 4 , wherein making the register used to store the input variable to the jump table switch statement instruction a monitored register comprises storing in the register table information identifying the register used to store the input variable to the jump table switch statement instruction.

6. The method according to claim 5 , wherein determining whether the received instruction writes to one of the monitored registers comprises comparing the information in the register table identifying the registers used to store the input variables to the jump table switch statements to information in the received instruction identifying a write register.

7. The method according to claim 2 , further comprising:

in response to determining that the other instruction is a jump table switch statement instruction, determining whether the current value is to be used to predict the target location; and

in response to determining that the current value is to be used to predict the target location, predicting the target location of the jump table switch statement instruction using the current value.

8. The method according to claim 7 , wherein:

the register table further comprises at least one of a valid bit, a counter and a confidence value for each monitored register; and

determining whether the current value is to be used in predicting the target location comprises analyzing at least one of the valid bit, the counter and the confidence value.

9. The method according to claim 8 , wherein the register table comprises a valid bit for each monitored register, each valid bit indicates whether the current value for the monitored register is valid.

10. The method according to claim 8 , wherein the register table comprises a counter for each monitored register, each counter indicates how many times the current value for the monitored register has been used to predict a target location since it was updated; and determining whether the current value is to be used in predicting the target location comprises comparing the counter to a threshold value.

11. The method according to claim 8 , wherein the register table comprises a confidence value for each monitored register, each confidence value indicates the likelihood that that the current value for the monitored register will correctly predict the target location for the associated jump table switch statement; and determining whether the current value is to be used in predicting the target location comprises comparing the confidence value to a threshold value.

12. The method according to claim 1 , wherein predicting the target location of the jump table switch statement instruction using the current value comprises combining the program counter for the jump table switch statement instruction and the current value.

13. The method according to claim 12 , wherein combining the program counter for the jump table switch statement instruction and the current value comprises:

determining a program counter for the instruction immediately following the jump table switch statement instruction based on the program counter for the jump table switch statement instruction; and

multiplying the current value by a factor N to generate a scaled current value, wherein N is the size of an instruction; and

summing the program counter for the instruction immediately following the jump table switch statement instruction and the scaled current value.

14. The method according to claim 1 , wherein the register table comprises a plurality of rows and the rows are ordered in the register table based on how recently they have been accessed.

15. A branch predictor comprising:

a register table, the register table storing a current value for at least one monitored register, each monitored register storing an input variable to a jump table switch statement, a jump table switch statement being a switch statement that has been compiled to a jump table; and

a logic unit in communication with the register table, the logic unit configured to:

receive an instruction for prediction;

prior to the received instruction being executed, determine whether the received instruction writes to one of the monitored registers with an update value;

in response to determining that the received instruction writes to one of the monitored registers with an update value, update the current value in the register table for the monitored register the received instruction writes to with the update value; and

predict the target location of a jump table switch statement instruction using the current value.

16. The branch predictor according to claim 15 , wherein the logic unit is further configured to:

receive another instruction for prediction;

determine whether the other instruction is a jump table switch statement instruction;

in response to determining that the other instruction is a jump table switch statement instruction, determine whether the register table comprises a current value for the input variable to the jump table switch statement instruction; and

in response to determining that the register table comprises a current value for the input variable to the jump table switch statement instruction, predict the target location of the jump table switch statement instruction using the current value.

17. The branch predictor according to claim 16 , wherein the logic unit is further configured to:

in response to determining that the other instruction is a jump table switch statement instruction, make the register used to store the input variable to the jump table switch statement instruction a monitored register.

18. The branch predictor according to claim 16 , wherein

the register table is configured to store a confidence value for each monitored register, each confidence value in the register table indicates the likelihood that the current value for the monitored register will correctly predict the target location for the associated jump table switch statement; and

the logic unit is further configured to:

in response to determining that the other instruction is a jump table switch statement instruction, determine whether the current value is to be used to predict the target location by comparing the confidence value to a threshold value; and

in response to determining that the current value is to be used to predict the target location, predicting the target location of the jump table switch statement instruction using the current value.

19. The branch predictor according to claim 15 wherein predicting the target location of a jump table switch statement instruction using the current value comprises combining the program counter for the jump table switch statement instruction and the current value.

20. A processor comprising a branch predictor, the branch predictor comprising:

a register table, the register table storing a current value for at least one monitored register, each monitored register having been identified as storing an input variable to a jump table switch statement, a jump table switch statement being a switch statement that has been compiled to a jump table; and

a logic unit in communication with the register table, the logic unit configured to:

receive an instruction for prediction;

prior to the received instruction being executed, determine whether the received instruction writes to one of the monitored registers with an update value;

in response to determining that the received instruction writes to one of the monitored registers with an update value, update the current value in the register table for the monitored register the received instruction writes to with the update value; and

predict the target location of a jump table switch statement instruction using the current value.

Assignments (8)