Branch prediction using a leading value of a call stack storing function arguments

1. A branch prediction device, comprising:

an instruction execution unit operable to execute instructions;

a function call notification unit operable to make a notification of execution of a function call instruction by the instruction execution unit;

a call stack that stores therein at least one argument of a function that is called by the function call instruction when notified by the function call notification unit of the execution of the function call instruction;

a branch instruction notification unit operable to make a notification of execution of a branch instruction by the instruction execution unit, the branch instruction being included in the function that is called by the function call instruction;

a branch result buffer that stores therein branch result entries each showing the following (i), (ii), and (iii) in correspondence: (i) a branch instruction address; (ii) a leading value of the call stack at branch instruction execution time; and (iii) a branch destination;

a branch prediction unit operable to (i) when notified by the branch instruction notification unit of the execution of the branch instruction, search the branch result buffer for any branch result entry therein that matches a branch instruction address of the executed branch instruction and an argument stored at a top of the call stack when the branch instruction is executed, and (ii) if a branch result entry that matches is found, regard a branch result of the branch result entry that matches as a predicted result of branching by the branch instruction;

an instruction fetch unit operable to fetch instructions in accordance with the predicted result predicted by the branch prediction unit;

a branch result record unit operable to, after the execution of the branch instruction is complete, record in the branch result buffer one branch result entry showing the following (i), (ii), and (iii) in correspondence: (i) the branch instruction address of the executed branch instruction; (ii) an address of a branch destination that has been branched to via the execution of the branch instruction; and (iii) a leading value of the call stack at execution time of the branch instruction; and

a function return notification unit operable to make a notification of execution of a function return instruction by the instruction execution unit, wherein

the call stack is cleared of any arguments of a function corresponding to the function return instruction when notified by the function return notification unit of the execution of the function return instruction.

2. The branch prediction device of claim 1 , wherein

the branch instruction is a conditional branch instruction having a fixed branch destination, and

when the branch instruction is a conditional branch instruction having a fixed branch destination, the branch result entry recorded by the branch result record unit shows, in correspondence, information indicating whether or not branching has occurred as a result of the conditional branch instruction being executed, instead of the address of the branch destination.

3. The branch prediction device of claim 1 , wherein

the branch result entry recorded in the branch result buffer by the branch result record unit further shows, in correspondence, count information indicating a branch count denoting a number of times the branch destination of the branch instruction has been reached, and

when, in searching, a plurality of branch result entries that match are found, the branch prediction unit regards the branch destination of one of the branch result entries with count information indicating a greatest branch count as the predicted result of the branching by the branch instruction.

4. The branch prediction device of claim 3 , wherein the branch result record unit, when the branch instruction is executed, increments by one frequency information for a branch result entry that matches the branch instruction address of the branch instruction and the leading value of the call stack at the execution time of the branch instruction and that also shows the branch destination actually branched to at the execution time of the branch instruction, and decrements by one frequency information for any other branch result entry that matches the branch instruction address of the branch instruction and the leading value of the call stack at the execution time of the branch instruction but that shows a different branch destination than the branch destination actually branched to at the execution time of the branch instruction.

5. The branch prediction device of claim 1 , wherein

the instruction execution unit includes a plurality of registers for storing arguments therein, and

the call stack obtains and stores therein a value stored in one predetermined specific register among the plurality of registers.

6. A branch prediction method used by an information processing device for predicting a branch destination for a branch instruction included in a function, comprising the steps of:

(a) making a notification of execution of a function call instruction;

(b) storing in a call stack at least one argument of a function that is called by the function call instruction when notified of the execution of the function call instruction during step (a);

(c) making a notification of execution of a branch instruction included in the function that is called by the function call instruction;

(d) when notified of the execution of the branch instruction during step (c), (i) searching a branch result storage medium that is connected to the information processing device and that stores therein branch result entries each showing the following (I), (II), and (III) in correspondence: (I) a branch instruction address; (II) a leading value of the call stack at branch instruction execution time; and (III) a branch destination, for any branch result entry therein that matches a branch instruction address of the executed branch instruction and an argument stored at the top of the call stack when the branch instruction is executed; and (ii) if a branch result entry that matches is found, regarding a branch result of the branch result entry that matches as a predicted result of branching by the branch instruction;

(e) fetching instructions in accordance with the predicted result predicted in step (d);

(f) after the execution of the branch instruction is complete, recording in the branch result storage medium one branch result entry showing the following (i), (ii), and (iii) in correspondence: (i) the branch instruction address of the executed branch instruction; (ii) an address of a branch destination that has been branched to via the execution of the branch instruction; and (iii) a leading value of the call stack at execution time of the branch instruction; and

(g) making a notification of execution of a function return instruction, and

(h) clearing the call stack of any arguments of a function corresponding to the function return instruction when notified of the execution of the function return instruction during step (g).

7. A non-transitory computer readable recording medium having stored thereon a compiler that converts source code indicating a function that includes a branch instruction into an instruction code sequence in a format executable by a computer, wherein

the computer includes a call stack which stores therein arguments of the function as information for predicting a branch destination of the branch instruction, and from which the computer clears any arguments of a function corresponding to a function return instruction when notified of execution of the function return instruction, and

the compiler judges whether or not the branch destination of the branch instruction is determined by a specific argument within the function at a function call time in the source code, and only in response to judging affirmatively, generates instruction code for storing in the call stack at least one argument relating to the branch instruction out of all arguments of the function that includes the branch instruction when a call for the function is executed.

8. A compile method for converting source code indicating a function that includes a branch instruction into an instruction code sequence in a format executable by a computer, the compile method being executed by a compiler device, wherein

the computer includes a call stack which stores therein arguments of the function as information for predicting a branch destination of the branch instruction, and from which the computer clears any arguments of the function corresponding to a function return instruction when notified of execution of the function return instruction, and

the compile method includes a step of judging whether or not the branch destination of the branch instruction is determined by a specific argument within the function at function call time in the source code, and only in response to judging affirmatively, generating code for storing in the call stack at least one argument relating to the branch instruction out of all arguments of the function that includes the branch instruction when a call for the function is executed.

9. A non-transitory computer readable recording medium having stored thereon a branch prediction program in order for a computer to execute branch prediction processing for predicting a branch destination for branch instructions for program execution, the branch prediction process comprising the steps of:

(a) making a notification of execution of a function call instruction;

(b) storing in a call stack at least one argument of a function that is called by the function call instruction when notified of the execution of the function call instruction during step (a);

(c) making a notification of execution of a branch instruction included in the function that is called by the function call instruction;

(d) when notified of the execution of the branch instruction during step (c), (i) searching a branch result storage medium that is connected to the computer and that stores therein branch result entries each showing the following (I), (II), and (III) in correspondence: (I) a branch instruction address; (II) a leading value of the call stack at branch instruction execution time; and (III) a branch destination, for any branch result entry therein that matches a branch instruction address of the executed branch instruction and an argument stored at the top of the call stack when the branch instruction is executed; and (ii) if a branch result entry that matches is found, regarding a branch result of the branch result entry that matches as a predicted result of branching by the branch instruction;

(e) fetching instructions in accordance with the predicted result predicted in step (d);

(f) after the execution of the branch instruction is complete, recording in the branch result storage medium one branch result entry showing the following (i), (ii), and (iii) in correspondence: (i) the branch instruction address of the executed branch instruction; (ii) an address of a branch destination that has been branched to via the execution of the branch instruction; and (iii) a leading value of the call stack at execution time of the branch instruction; and

(g) making a notification of execution of a function return instruction, and

(h) clearing the call stack of any arguments of a function corresponding to the function return instruction when notified of the execution of the function return instruction during step (g).