[go: up one dir, main page]

WO2010134330A1 - 分岐予測装置、その分岐予測方法、コンパイラ、そのコンパイル方法及び分岐予測プログラム記録媒体 - Google Patents

分岐予測装置、その分岐予測方法、コンパイラ、そのコンパイル方法及び分岐予測プログラム記録媒体 Download PDF

Info

Publication number
WO2010134330A1
WO2010134330A1 PCT/JP2010/003357 JP2010003357W WO2010134330A1 WO 2010134330 A1 WO2010134330 A1 WO 2010134330A1 JP 2010003357 W JP2010003357 W JP 2010003357W WO 2010134330 A1 WO2010134330 A1 WO 2010134330A1
Authority
WO
WIPO (PCT)
Prior art keywords
branch
instruction
argument
result
function
Prior art date
Application number
PCT/JP2010/003357
Other languages
English (en)
French (fr)
Inventor
天野克重
Original Assignee
パナソニック株式会社
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by パナソニック株式会社 filed Critical パナソニック株式会社
Priority to CN2010800021370A priority Critical patent/CN102099781A/zh
Priority to JP2011514333A priority patent/JP5347023B2/ja
Priority to US13/001,852 priority patent/US8694760B2/en
Publication of WO2010134330A1 publication Critical patent/WO2010134330A1/ja

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3836—Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution
    • G06F9/3842—Speculative instruction execution
    • G06F9/3844—Speculative instruction execution using dynamic branch prediction, e.g. using branch history tables
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
    • G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
    • G06F9/3802—Instruction prefetching
    • G06F9/3804—Instruction prefetching for branches, e.g. hedging, branch folding
    • G06F9/3806—Instruction prefetching for branches, e.g. hedging, branch folding using address prediction, e.g. return stack, branch history buffer

Definitions

  • the present invention relates to branch prediction of an instruction executed in an information processing apparatus.
  • Processor instructions may include branch instructions that jump to a specified address.
  • instructions are executed in a pipelined structure.
  • an instruction located at an address ahead is fetched in advance before execution of an instruction is completed.
  • the branch instruction is executed, the flow of the program is changed, and the fetched instruction may be unnecessary. Therefore, the fetched instruction becomes unnecessary, and it is necessary to newly fetch the address of the branch destination instruction.
  • the re-fetching of this instruction causes the abandonment of the instruction processing which has advanced to the middle of the pipeline (this is called a pipeline hazard), and is a factor which degrades the execution performance of the processor.
  • conditional branch instruction is a branch instruction which determines whether or not a branch is generated depending on the result of the operation at each time. If the branch does not occur, the subsequent instruction is executed. If the branch occurs, the instruction specified by the fixed address of the branch destination is executed.
  • conditional branch instruction there is a technique of determining a branch destination by inferring whether or not a branch occurs from the result of a branch in the past. That is, statistics of whether or not a branch occurs in the past branch result are taken, and the one with the higher probability of whether or not a branch occurs is predicted as the branch destination. This can improve the branch prediction accuracy of the conditional branch instruction.
  • the indirect branch is a branch whose jump destination is undefined, such as a jump instruction to a value set in a certain register, a jump by address assignment of a program counter, or the like.
  • the jump destination in addition to the indeterminacy as to whether or not to branch by the conditional branch, the jump destination is also indeterminate, so it is impossible to predict the branch destination in the simple branch prediction function.
  • One conventional technique for predicting indirect branches is the return stack. Since the return destination after function execution varies depending on the caller of the function, the address of the caller is stored in a stack on the memory, etc., and the address is jumped to when returning from the function. The return address is saved on a dedicated return stack when the function is called, and when fetching the return instruction from the function, it returns from the return stack prior to the processing of the jump by obtaining the return address on the memory. The address is obtained and used as a prediction of the address to be fetched next.
  • a programmer predicts branch destinations by specifying key information in the program using a dedicated implicit operation instruction in the program. There is a thing (refer patent document 1).
  • the present invention is intended to reduce the time and effort, and predict a branch of a program including an indirect branch with respect to any program without incorporating dedicated processing such as the above-described implicit operation instruction in the program. It aims at providing a branch prediction device.
  • the branch prediction device includes an instruction execution unit that executes an instruction, a function call notification unit that notifies execution of a function call instruction by the instruction execution unit, and the function call notification unit.
  • an argument stack storing at least one argument of the function call instruction and a branch instruction included in a function called by the function call instruction by the instruction execution unit are executed.
  • a branch result entry that associates the branch instruction notification unit that notifies that, the address at which the branch instruction is located, the top value of the argument stack when the branch instruction is executed, and the branch result that indicates the address of the branch destination Branch result storage unit for storing the branch result, and the branch result description unit when the branch instruction notification unit notifies that a branch instruction is to be executed.
  • branch prediction unit which is a prediction result of the branch by the branch instruction, an instruction fetch unit which fetches an instruction based on the prediction result predicted by the branch prediction unit, and an address at which the branch instruction executed after completion of execution of the branch instruction ,
  • the branch result indicating the address of the branch destination branched by the execution of the branch instruction, and the head value of the argument stack when the branch instruction is executed, and the branch result storage unit as a branch result entry
  • a branching result recording unit for recording the information.
  • the function means a so-called subroutine in a computer program.
  • the branch prediction device when the branch prediction device executes a function call, the argument stack acquires an argument of the function, and when the branch instruction is executed, the argument held by the argument stack; Branching can be predicted using past branch results.
  • the branch prediction device automatically takes an argument of a function to which the branch instruction belongs as key information for branch prediction Branch prediction can be realized, and indirect branch branch prediction can be realized in any program.
  • FIG. 1 is a functional block diagram showing a functional configuration of the branch prediction device according to the embodiment.
  • FIG. 2 is a schematic diagram showing how to pass arguments to the argument stack 113.
  • FIG. 3 is a data conceptual diagram showing a configuration example of branch result information stored in the branch result buffer.
  • FIG. 4 is a schematic diagram showing how a program is executed and arguments are stored on the argument stack.
  • FIG. 5 is a schematic diagram showing how to search for branch prediction performed by the branch prediction unit 117.
  • FIG. 6 is a flowchart showing an operation related to branch prediction of the information processing apparatus 100.
  • FIG. 7 is a relationship diagram showing the relationship between the high-level language program, the assembler code of the high-level language program, and the arguments stored in the argument stack.
  • FIG. 8 is a flowchart showing the operation of the compiler 119 in compiling.
  • FIG. 9 is a flowchart showing the operation of the instruction execution unit 110 when the compiler 119 executes the compiled instruction.
  • FIG. 10 is a relationship diagram showing the relationship among function arguments, branch instruction arguments, and arguments stored in the argument stack.
  • FIG. 11 is a functional block diagram showing another configuration example of the information processing apparatus 300 according to the modification.
  • FIG. 12 is a diagram illustrating a specific example of how to pass arguments to the argument stack of the information processing device 300 according to the modification.
  • FIG. 13 is a diagram illustrating another specific example of how to pass an argument to the argument stack of the information processing device 300 according to the modification.
  • FIG. 14 is a schematic diagram showing how a branch prediction unit searches when a branch instruction of the program shown in FIG. 8 is executed.
  • FIG. 15 is a diagram showing another example of how to pass arguments to the argument stack.
  • FIG. 16 is a diagram showing a specific example of how to pass arguments of the argument stack shown in FIG.
  • FIG. 17 is a diagram showing another configuration example of the argument stack.
  • FIG. 1 is a functional block diagram showing a functional configuration of the information processing apparatus 100.
  • the information processing apparatus 100 includes an instruction execution unit 110, a function call notification unit 111, a function return notification unit 112, an argument stack 113, a branch instruction notification unit 114, and a branch result recording unit 115. , Classification result buffer 116, branch prediction unit 117, instruction fetch unit 118, and compiler 119.
  • the information processing apparatus 100 is a processor that is connected to the storage device 200 and sequentially reads and executes instructions stored in the storage device 200.
  • the instruction execution unit 110 has a function of fetching from the storage device 200 the instruction sequence converted by the compiler 119 into the execution format and sequentially executing the instruction sequence.
  • the function call notification unit 111 has a function of detecting that the instruction execution unit 110 has made a function call and notifying the argument stack 113 of that fact.
  • the function referred to here is a so-called subroutine call, and refers to a call of a routine for executing one or more instructions.
  • the functions in the high-level language are compiled by the compiler 119 into processor instruction sequences and executed.
  • the compiler 119 uses a specific instruction for compiling the calling part of the function
  • the function call notification unit 111 detects that the function call is executed by detecting the execution of the specific instruction.
  • the specific instruction is, for example, an instruction that holds the next address of the jump instruction as a return address at the same time as the jump and holds it in a specific register called a return register.
  • the function call notification unit 111 stores what kind of instruction a particular instruction is, assuming that the instruction sequence is compiled according to the standard, and executes the predetermined specific instruction. By detecting it, it notifies that the function call is executed.
  • the function return notification unit 112 has a function of monitoring whether or not the instruction execution unit 110 has completed the function, that is, returned, and when returning, notifies the argument stack 113 of that effect. Since the compiler 119 is compiled using a specific instruction at the return of the function as well as the function call, the function return notification unit 112 detects the return of the function by detecting the execution of the specific instruction by the compiler 119. Do.
  • the argument stack 113 acquires the value stored in a specific register of the instruction execution unit 110 as an argument of the called function.
  • Push i.e., have the function of storing.
  • the function return notification unit 112 also has a function of outputting, i.e., popping, the last stored argument when notified that the function has ended, that is, returned.
  • the argument stack 113 is a so-called first in last out (FILO) type memory, and in the present specification, the value output when popping an argument held from the argument stack 113 is the top of the argument stack 113 Write as a value.
  • FIG. 2 is a diagram showing details of the processing on the argument stack 113, that is, how to obtain the arguments.
  • the way of passing arguments to functions is also predetermined, and the arguments of functions are generally assigned to each register of the register group 120 held by the instruction execution unit 110 in the order described in the high-level language program.
  • the items are stored in order from the smallest number. That is, arguments are stored in each register such that register 0 is the first argument of the function, register 1 is the second argument of the function, register 2 is the third argument of the function, and so on.
  • the argument stack 113 acquires and stores the argument stored in the register 0.
  • FIG. 4 shows one specific example of the procedure of storing arguments in the argument stack 113.
  • the function funcA of the program 400 receives the arguments a0, a1, a2. This argument a 0 is stored in register 0 and pushed onto the argument stack 113.
  • the program 400 calls the function funcB.
  • the function funcB receives the arguments b0, b1, b2.
  • the argument b 0 is stored in register 0 and pushed on the argument stack 113.
  • the program 400 calls the function funcC.
  • the function funcC receives arguments c0, c1 and c2.
  • the argument c 0 is stored in register 0 and pushed on the argument stack 113.
  • FIG. 4 shows the information of the arguments held at that time in the argument stack 113, and it is apparent from FIG. 4 that the first of the function funcC called last is The argument c0 is the first value. In FIG. 4, the upper side of the argument stack 113 is the leading value.
  • the branch instruction notification unit 114 determines whether the instruction executed by the instruction execution unit 110 is a branch instruction, and when an affirmative determination is made, the branch result recording unit 115 branches that effect. It has a function of notifying the prediction unit 117.
  • the branch result recording unit 115 When notified of the execution of the branch instruction from the branch instruction notification unit 114, the branch result recording unit 115 acquires the address of the branch instruction executed by the instruction execution unit 110, and executes the branch instruction in the instruction execution unit 110. As a result, the branch destination address is obtained. The branch result recording unit 115 also acquires the top value of the argument stack 113 when the branch instruction is executed. Then, the branch result recording unit 115 associates the acquired address of the branch instruction, the head value of the argument stack 113 at the time of branch, and the address of the branch destination of the branch instruction, and records them in the branch result buffer 116 It has a function.
  • the branch result buffer 116 stores a branch result entry in which the address at which the branch instruction is located, the head value of the argument stack when the branch instruction is executed, and the address of the branch destination of the branch instruction are associated. It is a memory.
  • FIG. 3 is a data conceptual diagram showing an example of the data configuration of the branch result information stored in the branch result buffer 116. As shown in FIG.
  • the branch result information is information in which branch result entries in which the branch instruction address 301, the top value 302 of the argument stack, and the branch destination 303 are associated with one another are integrated.
  • the branch instruction address 301 is information indicating the address at which the branch instruction is located.
  • the top value 302 of the argument stack is information indicating an argument stored in the argument stack 113 when the corresponding branch instruction is executed.
  • the branch destination 303 is information indicating the address of the branch destination at which the branch instruction is actually executed and branched.
  • the branch prediction unit 117 can execute branch prediction.
  • the branch prediction unit 117 when the branch prediction unit 117 receives the notification from the branch instruction notification unit 114, the branch prediction unit 117 acquires the address of the branch instruction transmitted along with the notification and the leading value of the argument stack 113 at that time.
  • the branch prediction unit 117 searches the branch result buffer 116 for a branch result entry that matches both the acquired address of the branch instruction and the start value of the argument stack 113. Then, the branch prediction unit 117 has a function of notifying the instruction fetch unit 118 of the branch destination of the branch result entry as the prediction target of the branch instruction when there is a matching branch result entry.
  • FIG. 5 is a schematic diagram showing how the branch prediction unit 117 searches the branch result buffer.
  • the branch prediction unit 117 searches the branch result buffer 116 for a branch result entry corresponding to the address at which the branch instruction is located and the argument acquired from the argument stack 113 at that time. . That is, the branch prediction unit 117 acquires the address of the branch instruction to be executed, and searches whether there is an address that matches the acquired address of the branch instruction.
  • the branch destination of the branch result entry matching the two is predicted as the branch destination of the branch instruction.
  • the instruction fetch unit 118 has a function of fetching an instruction from the storage device 200.
  • the instruction fetch unit 118 has a function of fetching an instruction from the notified address when notified of the address of the instruction to be executed next from the branch prediction unit 117.
  • FIG. 6 is a flowchart showing the branch prediction operation of the information processing apparatus 100. The operation in the branch prediction of the information processing apparatus 100 will be described based on this flowchart.
  • the branch instruction notification unit 114 of the information processing apparatus 100 detects that a branch instruction is executed, and notifies the branch prediction unit 117 to that effect (step S601).
  • the branch prediction unit 117 When notified of the execution of the branch instruction from the branch instruction notification unit 114, the branch prediction unit 117 acquires the top value of the argument stack 113 at that time. The branch prediction unit 117 also acquires the address of the branch instruction to be executed from the branch instruction notification unit 114 (step S602).
  • step S603 it is searched whether or not a branch result entry matching the acquired address of the branch instruction and the top value of the argument stack 113 is stored in the branch result buffer 116 (step S603).
  • branch prediction unit 117 determines the branch result entry that matches the address of the branch instruction to be executed and the top value of argument stack 113.
  • the branch destination 303 is predicted as the branch destination of the branch instruction (step S604).
  • the instruction fetch unit 118 calls the instruction at the address notified from the branch prediction unit 117 from the storage device 200, and fetches the instruction to the instruction execution unit 110 (step S605).
  • step S603 If no branch result entry is stored in the branch result buffer 116 (NO in step S603), the branch prediction unit 117 outputs information indicating no prediction to the instruction fetch unit 118. Then, the instruction fetch unit 118 fetches the instruction at the address next to the branch instruction.
  • the branch result recording unit 115 When the branch instruction is actually executed (step S 607), the branch result recording unit 115 includes the address of the branch instruction, the leading value of the argument stack 113 at the time the branch instruction is executed, and the branch instruction. A branch result entry in which the branch destination address branched as a result of execution is associated is recorded in the branch result buffer 116 (step S608).
  • the above is the operation of the information processing apparatus 100 at the time of execution of the branch prediction of the branch prediction unit 117 and the branch instruction.
  • FIG. 7 is a diagram showing a high-level language program, a compiled processor instruction sequence, and arguments stored in the argument stack 113 when the instruction sequence is executed.
  • the function interpreter of the high-level language program 701 shown in FIG. 7 is an execution function of the interprinter language having the pseudo instruction inst as an argument.
  • Java (registered trademark) Script or the like interprets a program of a text file and compiles it into pseudo instructions, and then processes the pseudo instructions with an interprinter.
  • a function that implements an interprinter implements processing according to each pseudo language in a switch to case statement as shown in FIG.
  • a processor instruction sequence 702 shown in FIG. 7 shows the function interpreter as a pseudo processor instruction sequence.
  • the argument inst is stored in the register r0 by the mv instruction
  • a jump (function call) to the top of the function interpreter is performed by the bl instruction.
  • the function func is first called as an a as an argument as a lower function.
  • the tst instruction determines whether the register r0, that is, the argument of the function interpreter is A. When it is equal to A, the value 0x01000 is stored in the register r1. Similarly, if r0 is B, 0x2000 is stored in the register r1. The value of the register r1 is substituted in the program counter (pc) by the mv instruction located at the address 0x0100, and a branch occurs. In other words, if the argument inst of the function interpreter is A, it branches to 0x1000, and if it is B, it branches to 0x2000.
  • FIG. 7 shows the state of the argument stack 113 in the process of executing the processor instruction sequence 702.
  • each branch destination address is obtained as a predicted value when the branch instruction located at the address 0x0100 is executed.
  • FIG. 8 is a flowchart showing the operation of the compiler 119 in compiling.
  • FIG. 8 particularly shows the operation of function compilation at the time of function invocation.
  • the operation of only the part related to the invention of the present embodiment will be described, and the details of the other operations will be omitted according to the conventional compilation.
  • the compiler 119 determines, at the time of function compilation, whether or not a specific argument determines a branch destination in the function (step S801).
  • the function is analyzed to search for a branch instruction in the function. Then, when there is a branch instruction, it is determined whether or not the data used for the branch condition of the branch instruction is included in the argument of the function. This determines whether the function argument determines the branch destination.
  • the argument for determining the branch destination is a register for which the argument stack 113 acquires a value.
  • Code to be stored is generated (step S802). That is, a code is generated which causes the register 0 to store a specific argument included in the argument of the function. For example, if the argument that determines the branch destination is the first argument of the function, the first argument is the register 0 and the argument that determines the branch destination is the third argument of the function Generate code that causes the third argument to be stored in register 0.
  • the compiler 119 generates code specifying which register argument is to be acquired on the argument stack 113 (step S 803).
  • the compiler 119 generates code on the argument stack 113 for acquiring the value of the register 0.
  • the compiler 119 compiles each instruction in the function as usual and terminates.
  • step S801 If the particular argument does not determine the branch destination (NO in step S801), the compiler 119 compiles each instruction of the function and terminates as usual.
  • FIG. 9 is a flowchart showing the link operation of the object file in the code sequence compiled according to the operation shown in FIG. The operation indicates the method of storing the value at the time of instruction execution, and the other operations conform to the conventional instruction execution method and will not be described here.
  • the instruction execution unit 110 determines whether the function of the call destination holds information specifying a register for passing an argument (step S901).
  • step S901 If the compiler 119 holds information specifying a register to which an argument is to be passed (YES in step S901), the compiler 119 corrects the code for storing the argument in the register of the function call part according to the information (step S902). That is, if there is a code that specifies which argument is stored in which register, the specified argument is corrected to the code stored in register 0. If not specified, function arguments are stored in ascending order of register numbers in the order described in the high-level language program.
  • step S903 It is determined whether all the function call links have been completed (step S903), and if it has been completed (step S903), the link processing of the object file has been completed, and if it has not been completed, the step Return to S901.
  • FIG. 10 shows a specific example in which a function is called and a branch instruction is executed in the function.
  • a switch to case statement is shown as an example of a branch instruction.
  • the switch-case statement is, for example, a language such as C language, C ++, PHP (Hypertext Preprocessor, where PHP is an abbreviation of Personal Home Page tools, but PHP originally intended is Hypertext Preprocessor). Used in In order for the branch prediction unit of the information processing apparatus 100 according to the present embodiment to make prediction successful, it is necessary to store, in the argument stack 113, an argument of a function that affects the branch.
  • FIG. 10 shows how to store the arguments in the register for that purpose.
  • the argument affecting the switch statement is that the argument of the switch statement is a0, so it can be understood that the argument related to the branch is also a0. Therefore, when the function funcA is called, the argument a0 needs to be passed to the argument stack 113. Therefore, the first argument of funcA, a0, is stored in the register 0.
  • the code generated by the compiler 119 in this case is realized, for example, by an instruction that stores the first argument in the register 0, for example, “mv r0 (a0)” or the like. As described above, since the argument passed to the argument stack 113 is the value stored in the register 0, this causes the argument related to the branch to be stored in the argument stack 113.
  • the argument related to the switch statement is b1.
  • the argument b1 is the second argument of the function funcB. Therefore, in the case of FIG. 10B, the second argument b1 of funcB is stored in the register 0.
  • the argument stack 113 stores the arguments related to the branch.
  • the configuration in which the second argument is stored is realized by specifying how to store the argument in the register at the time of compilation by the compiler 119.
  • FIG. 11 is a functional block diagram showing a functional configuration of the information processing device 300. As shown in FIG.
  • the information processing apparatus 300 includes an instruction execution unit 122 that operates partially different from the instruction execution unit 110, and the argument number notification unit 121 that the information processing apparatus 100 did not have. Equipped with The other configurations of the information processing apparatus 300 are the same as those of the information processing apparatus 100.
  • the instruction execution unit 122 executes the instruction fetched from the storage device 200 by the instruction fetch unit 118, further interprets an instruction specifying an argument of a function affecting a branch, and notifies the argument number notification unit 21 of the instruction. Have. Instructions that specify arguments are to be added automatically by the compiler analyzing the program at compile time.
  • the argument number notification unit 121 has a function of acquiring the number of the designated argument from the instruction execution unit 122 and notifying the argument stack 123 of the acquired argument number.
  • the argument stack 123 has a function of receiving a notification from the argument number notification unit 121 and pushing a designated argument.
  • the argument stack 123 like the argument stack 113, pushes a function argument after receiving a notification from the function call notification unit 111, receives a notification from the function return notification unit 112, and pops an argument of the function. Do. That is, the top value of the argument stack 123 holds the argument of the function currently being executed.
  • the branch prediction mechanism 1100 of the information processing apparatus 100 can store the argument affecting the branch on the argument stack more reliably.
  • FIG. 12 shows an example in which function arguments in the argument stack 123 are saved.
  • FIG. 12 shows a procedure for acquiring an argument of a function using the argument number notification unit 121.
  • the argument that affects the switch-case statement to be branched is a0.
  • the instruction arg shown in FIG. 12A notifies an argument that affects a branch.
  • the operand 0 of the instruction arg in FIG. 12A indicates the register number of the register group 120 in which the argument affecting the branch is stored. Therefore, in the case of FIG. 12A, the argument stack 123 pushes the value of the register 0 designated by the arg instruction.
  • the argument affecting the branch is b1.
  • the operand of the instruction arg in FIG. 12B is 1.
  • the register number of the register group 120 affecting the branch is the register 1
  • the argument stack 123 pushes the value of the register 1 designated by the arg instruction at the time of the function call.
  • the compiler 119 needs to generate this arg instruction at compile time.
  • the compiler 119 generates a code for specifying which argument is to be stored in register 0 (the value to be stored in the register is specified by the mv instruction), but in this modification Generates code that specifies which register's value the argument stack pushes.
  • the information processing apparatus 100 includes an argument stack that acquires an argument when performing a function call. Then, in the stage where the branch instruction is executed, the branch result is predicted by searching for the branch result in the past from the start value of the values stored in the argument stack and the address at which the branch instruction is to be executed. Do.
  • the function call notification unit 111 detects that the instruction executed by the instruction execution unit 110 is compiled by the compiler 119 with a specific instruction, and executes the function call. It is configured to notify that it is done.
  • the method of detecting the function call is not limited to this, and the instruction to be executed may be analyzed to detect whether there is an instruction that matches a predetermined specific instruction statement.
  • the function call notification unit 111 may detect the execution of the function call by generating a dedicated instruction for notifying the function call and outputting the instruction to the function call notification unit 111.
  • the function return notification unit 112 detects the execution of a specific instruction by the compiler 119 as described in the above embodiment, and does not detect the execution of the return of the function, but the method described above, For example, the function return may be detected using a method such as receiving notification of execution of a function return from a compiler.
  • the branch prediction unit 117 showed the method of predicting using the top value of the argument stack 113, but when the branch instruction is executed, in which function the branch instruction is executed.
  • the arguments corresponding to the function are stored in association with each other, not the top value of the argument stack 113 but a required argument may be referred to.
  • the argument stack 113 stores the information indicating the function called at that time in association with one another, and when the branch prediction unit 117 is notified of the execution of the branch instruction, The information on the function including the branch instruction may be received, and an argument corresponding to the function indicated by the information on the function may be acquired from the argument stack 113.
  • the branch result entry may be further associated with the above-described content for obtaining the frequency of whether or not the branch has taken place. That is, each branch result entry may further be associated with a branch count value. The branch count value is incremented by one when the branch instruction indicated by the branch result entry actually branches to the branch destination indicated by the branch result entry, and is decremented by one when the branch instruction is not branched.
  • the branch prediction unit 117 uses the branch destination of the branch result entry with the highest branch count value as the branch destination of the branch instruction to be executed.
  • the address may be notified to 118.
  • the branch count value may be any value as long as it indicates the branch probability of the branch result entry, and the configuration to decrement the branch counter of the branch result entry not branched above is -1 It is not necessary to provide it.
  • the value to be added may not be 1 and may be a predetermined value.
  • the value to be added may not be 1 and may be a predetermined value.
  • FIG. 13 shows an example of specifying an argument that affects a branch in order by an instruction that specifies an argument.
  • the arguments a1 and a0 affect the branch for each branch. Therefore, as indicated by the arg instruction of the processor instruction sequence, the order of a0 and a1 in the order of arguments (a0, a1, a2) at the time of function call of the high-level language program is compiled as an instruction sequence.
  • the argument stack 123 pushes arguments in this order. That is, push a0 first, and then push a1.
  • the arguments associated with each branch instruction can be used as key information for branch prediction.
  • the prediction of the branch and the storage in the branch result entry to the branch result buffer use the argument popped from the argument stack.
  • the configuration shown in FIG. 13 (a) can also be realized by the configuration shown in FIG. 13 (b). That is, as shown in FIG. 13B, the argument stack 123 can hold a plurality of arguments.
  • FIG. 13B shows the case where the argument stack 123 can hold a plurality of arguments in one step.
  • the branch prediction unit 117 sequentially uses the values stored at the same stage of the argument stack 123 in branch prediction.
  • FIG. 14 shows an example of recording in the branch result buffer 116 when the branch destination is fixed.
  • the tst instruction determines whether the value of the register r0 is equal to a, and the result determines whether the conditional branch instruction bleq is to be executed.
  • the bleq instruction is executed, a branch to the address indicated by r1 occurs.
  • the branch result information stored in the branch result buffer 116 is associated with the branch instruction address 301 at which the branch instruction is located, the top value 302 of the argument stack 113, and the branch result as to whether or not a branch has occurred. .
  • the branch prediction unit 117 determines whether the branch result buffer 116 has a branch result entry that matches the address at which the conditional branch instruction is located and the head value of the argument stack 113 at that time. If there is a search, if there is a branch result entry branch 304 indicates that a branch has taken place, the address of the fixed branch destination is notified to the instruction fetch unit 118 and the branch is not taken. In the case of indicating, the instruction fetch unit 118 is notified of the address following the conditional branch instruction.
  • the configuration other than the configuration in which the instruction execution unit 110 includes the register group 120 will be described. That is, the case where the instruction execution unit 110 is configured to store an argument in the storage device 200 will be described with reference to FIG.
  • the instruction execution unit 110 includes a stack pointer register 1501 indicating where the argument is stored. Then, the storage device 200 stores the arguments of the function in the stack 1502 indicated by the stack pointer register 1501. The argument stack 113 acquires the value of the stack pointer register 1501 from the instruction execution unit 110 when the function call notification unit 112 notifies of a function call, and the stack 1502 indicated by the stack pointer register 1501 of the storage device 200 Get and store the value stored in as an argument.
  • the argument stack 113 can push arguments at the time of function call related to the branch instruction.
  • FIG. 15 A specific example in the case of acquiring an argument using the method shown in FIG. 15 is shown in FIG.
  • the stack pointer register 1501 stores the top address of the stack 1602.
  • the stack pointer register 1501 stores the top address of the stack 1602.
  • FIG. 17A shows an example where the capacity of the argument stack 113 is increased and not only the arguments stored in the register 0 but all the arguments received at the time of function call are stored.
  • arguments received at the time of the function call may be configured to store a plurality of arguments among them.
  • the argument a0, the argument a1, and the argument a2 may be stored in the argument stack.
  • three arguments stored in register 0 to register 2 may be stored.
  • the argument stack 113 may not only store the argument of the register 0, but may also use the argument stack 113 as a return stack. That is, in a processor using a return stack, push and pop of the return address are performed at the same timing as the argument stack, so the return address and the argument may be held in pairs in the same stack.
  • addressA, addressB, and addressC indicate the return addresses of funcA, funcB, and funcC, respectively. This makes it possible to use it with the return stack.
  • the argument stack is used to hold the arguments of the function, but what is used as the argument stack is not necessarily limited to the stack format, and is shown as the argument stack in the above embodiment It may be anything that can execute the content.
  • the functional units of the information processing apparatuses 100 and 300 illustrated in FIGS. 1 and 11 may be integrated and realized by one or more LSIs (Large Scale Integration). Also, multiple functional units may be realized by one LSI.
  • An LSI may be referred to as an integrated circuit (IC), a system LSI, a very large scale integration (VLSI), a super large scale integration (SLSI), an ultra large scale integration (ULSI), or the like depending on the degree of integration.
  • IC integrated circuit
  • system LSI system LSI
  • VLSI very large scale integration
  • SLSI super large scale integration
  • ULSI ultra large scale integration
  • the method of circuit integration is not limited to LSI's, and implementation using dedicated circuitry or general purpose processors is also possible.
  • a field programmable gate array FPGA
  • a reconfigurable processor that can reconfigure connection and setting of circuit cells in the LSI may be used.
  • the control program composed of the code can be recorded in a recording medium, or distributed and distributed via various communication paths (for example, telecommunication lines, wireless or wired communication lines, networks represented by the Internet as a representative) or the like.
  • Such recording media include an IC card, a hard disk, an optical disk, a flexible disk, a ROM, and the like.
  • the control program distributed and distributed is used by being stored in a memory or the like that can be read by a processor, and the processor executes the control program to realize various functions as described in the embodiment. Will be (11) An embodiment of the branch prediction device according to the present invention and its effects will be described below.
  • the branch prediction device comprises an instruction execution unit that executes an instruction, a function call notification unit that notifies execution of a function call instruction by the instruction execution unit, and notification of execution of a function call instruction by the function call notification unit.
  • An instruction stack storing at least one argument of the function call instruction, and a branch instruction notification notifying that a branch instruction included in a function called by the function call instruction is executed by the instruction execution unit
  • Branch result storage unit that stores a branch result entry that associates a branch result, the address at which the branch instruction is located, the head value of the argument stack when the branch instruction is executed, and the branch result indicating the address of the branch destination
  • the branch result storage unit determines the number of minutes to be executed.
  • Branch prediction unit an instruction fetch unit for fetching an instruction based on the prediction result predicted by the branch prediction unit, an address at which a branch instruction executed after completion of execution of the branch instruction, and execution of the branch instruction
  • a branch result recording unit that records a branch result indicating an address of a branched branch destination and a head value of the argument stack when the branch instruction is executed, in the branch result storage unit as a branch result entry
  • a branch prediction device characterized by comprising:
  • the present invention is a branch prediction method in which an information processing apparatus predicts a branch destination of a branch instruction included in a function, the function call notification step of notifying execution of a function call instruction, and the function call notification step
  • a storage step of storing at least one argument of the function call instruction on an argument stack and a branch instruction included in the function called by the function call instruction are executed
  • the branch instruction notification step of notifying that the branch instruction is executed by the branch instruction notification step, the address at which the branch instruction is located when the branch instruction is notified, and the argument stack when the branch instruction is executed
  • the group storing the branch result entry in which the top value is associated with the branch result indicating the address of the branch destination
  • the branch result storage medium connected to the computer is searched for whether or not the branch result entry matching the address of the branch instruction to be executed and the argument stored in the argument stack is recorded,
  • the present invention is a computer-readable branch prediction program recording medium storing a branch prediction program for causing a computer to execute branch prediction processing for predicting a branch destination of a branch instruction when executing a program.
  • the branch prediction process includes a function call notification step for notifying execution of a function call instruction, and an argument for storing at least one argument of the function call instruction when execution of the function call instruction is notified by the function call notification step.
  • a storage step stored in the stack a branch instruction notification step notifying that a branch instruction included in a function called by the function call instruction is executed, and notification that a branch instruction is executed by the branch instruction notification step Address of the branch instruction, and
  • the branch to be executed from the branch result storage medium connected to the computer storing the branch result entry in which the top value of the argument stack when the instruction is executed is associated with the branch result indicating the address of the branch destination It is searched whether a branch result entry matching the address of the instruction and the argument stored in the argument stack is recorded, and if there is, the branch result of the branch result entry is the predicted result of the branch by the branch instruction Branch instruction step, an instruction fetch step of fetching an instruction based on the prediction result predicted in the prediction step, an address at which a branch instruction executed after completion of execution of the branch instruction, and execution of the branch instruction Branch result indicating the address of the target branch destination, and the argument stack when the branch instruction is executed
  • a branch prediction program recording medium characterized in that it comprises a branch result recording step of
  • the argument stack is configured to acquire an argument of the function when the function is called, and the branch result storage unit holds information in which the argument is associated with the branch result in the past, and the timing at which the branch instruction is actually executed.
  • the branch prediction unit searches the branch result storage unit from the branch result storage unit in the past based on the address of the branch instruction and the top value of the argument stack, and the branch destination of the branch result entry when the search hits Can be predicted as the branch destination of the branch instruction.
  • the branch prediction device further includes a function return notification unit for notifying execution of a function return instruction by the instruction execution unit, and the argument stack is notified of execution of a function return instruction from the function return notification unit.
  • the function argument corresponding to the function return instruction may be deleted.
  • the apparatus can use the arguments of the function that definitely includes the branch instruction as information for branch prediction.
  • the branch instruction is a conditional branch instruction
  • the branch result recording unit further includes a branch result entry associated with information indicating whether the conditional branch instruction is executed or not. It may be recorded.
  • the branch instruction is a conditional branch instruction
  • by associating information on the success or failure of the conditional branch for example, it is judged whether the conditional branch is established or not based on the success or failure, and the branch prediction is executed. can do.
  • the branch result recording unit records, in the branch result storage unit, a branch result entry in which frequency information indicating a branch frequency is associated for each branch destination of the branch instruction, in the branch result storage unit.
  • the section may use the branch destination address of the branch result entry with the highest frequency of branching as the prediction result.
  • the branch result recording unit matches the branch destination address of the branch instruction with the head value of the argument stack when the branch instruction is executed.
  • the frequency information of the branch destination having branch destination is incremented by one, and the branch destination address of the other branch instruction and the branch instruction when the branch instruction is executed The frequency information may be decremented by 1 with respect to branch result entries having a match with the top value of the argument stack but having a different branch destination actually branched.
  • the branch result entry is associated with the information for specifying the frequency at which each branch entry was executed, and the branch result entry corresponding to the address of the branch instruction to be executed and the top value of the argument stack If there are a plurality of branch result entries, the branch result entry with the highest execution frequency among those branch result entries can be predicted as a branch destination. This can increase the accuracy of branch prediction.
  • the instruction execution unit includes a plurality of registers for storing the arguments.
  • the argument stack may acquire and store a value stored in a predetermined specific register of the plurality of registers.
  • the device can be easily manufactured on the premise of this.
  • the present invention is a compiler that changes a source program indicating a function including a branch instruction into an instruction code string of executable form executable by a computer, wherein the computer is for predicting a branch destination of the branch instruction.
  • the information stack includes an argument stack for storing an argument of the function, and the compiler stores an argument related to the branch instruction among the arguments of the function in the argument stack when the call of the function is executed. It is also possible to generate an instruction code for causing the
  • the present invention is a compiling method for changing a source program indicating a function including a branch instruction into an instruction code string of executable form executable by a computer, wherein the computer predicts the branch destination of the branch instruction.
  • the information processing apparatus further includes an argument stack for storing an argument of the function as the information to be executed, and the compiling method includes, among the arguments of the function, an argument related to the branch instruction when the call of the function is executed.
  • a stored code generation step may be included to generate an instruction code to be stored on the argument stack.
  • the computer can be controlled so that the arguments passed to the argument stack are always stored in a specific register when the function is called, so the argument stack that reliably determines the branch destination of the branch instruction in the function is reliably stored. Can be guaranteed to be stored.
  • the branch prediction apparatus is useful as one that contributes to the improvement of program execution performance and promotes the improvement of the processing speed of a processor. Therefore, if a processor is used, it is effective in a wide range of fields. For example, it can be used not only in the form of a large computer and a personal computer, but also in various home appliances, communication devices such as mobile phones, industrial devices, control devices and the like.

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Advance Control (AREA)
  • Executing Machine-Instructions (AREA)

Abstract

情報処理装置１００に含まれる分岐予測機構１０００は、関数呼び出しを行うタイミングで、当該関数の引数をスタックする引数スタック１１３を備える。引数スタック１１３には、関数内の分岐命令に関連する引数が格納される。分岐予測機構１０００は、分岐命令が位置するアドレスと、その分岐命令が実行されたタイミングにおける引数スタック１１３の先頭値と、分岐命令が実行されたときの分岐先のアドレスとを対応付けた情報を分岐結果バッファ１１６に記憶している。分岐予測部１１７は、分岐命令の実行が通知されたときに、当該分岐命令の位置するアドレスと、そのときの引数スタック１１３の先頭値とを取得して、当該アドレスと先頭値とに対応する分岐先が分岐結果バッファ１１６にあるかどうかを検索し、検索して得られた分岐先を実行される分岐命令の分岐先として予測する。命令フェッチ部１１８は、分岐予測部１１７が予測した分岐先にある命令をフェッチする。

Description

分岐予測装置、その分岐予測方法、コンパイラ、そのコンパイル方法及び分岐予測プログラム記録媒体
　本発明は、情報処理装置において実行される命令の分岐予測に関する。
　プロセッサの命令には、指定したアドレスへジャンプする分岐命令が含まれていることがある。現在のプロセッサでは、命令はパイプライン構造で実行される。
　パイプラインでの命令実行では、ある命令の実行が完了する前に、その先のアドレスに位置する命令を先行してフェッチしている。ここで、分岐命令が実行されるとプログラムのフローが変更されて、フェッチした命令が不要となることがある。そのため、フェッチした命令は不要となり、新たに分岐先の命令のアドレスをフェッチする必要がある。
　この命令のフェッチのやり直しは、パイプラインの途中まで進んでいる命令処理の放棄（これをパイプラインハザードという）を引き起こし、プロセッサの実行性能を低下させる一要因となっている。
　そこで、プロセッサにとって、分岐命令の分岐先を予測することが重要となる。
　分岐命令の一種に、条件分岐命令がある。条件分岐命令とは、その時々の演算結果により分岐が発生するかどうかが決まる分岐命令のことである。分岐が発生しない場合には、後続する命令が実行され、分岐が発生する場合は、固定の分岐先のアドレスで指定される命令が実行される。
　当該条件分岐命令においては、分岐が発生するか否かを過去の分岐結果から推測して分岐先を決定する技術がある。即ち、過去の分岐結果で分岐が発生するか否かの統計をとっておいて、分岐が発生したか否かの確率の高い方を分岐先と予測する。これによって、条件分岐命令の分岐予測の確度を高めることができる。
　しかし、分岐命令には、より複雑な分岐として間接分岐と呼ばれるものがある。間接分岐とは、あるレジスタに設定された値へのジャンプ命令や、プログラムカウンタのアドレス代入によるジャンプ等、ジャンプ先が不定の分岐である。
　間接分岐では、条件分岐による分岐するか否かの不定に加え、ジャンプ先も不定となるため、単純な分岐予測機能では分岐先の予測は不可能である。
　間接分岐を予測する一つの従来の技術として、リターンスタックがある。関数実行後の戻り先は、関数の呼び出し元によって変わるので、呼び出し元のアドレスをメモリ上のスタックなどに記録しておき、関数からの復帰（リターン）時にはこのアドレスへとジャンプする。関数呼び出し時に戻り先アドレスを専用のリターンスタックに保存されており、関数からのリターン命令をフェッチした際は、メモリ上の戻り先アドレスを取得してのジャンプの処理に先駆けて、リターンスタックより戻りアドレスを取得して次にフェッチすべきアドレスの予測として用いる。
　また、間接分岐に対する分岐予測の技術の一つとして、間接分岐の結果に寄与するキー情報を、プログラム中でプログラマが専用の暗示オペレーション命令を用いてキー情報を指定して、分岐先を予測するものがある（特許文献１参照）。
特表２００４－５３３６９５号公報
　しかしながら、上記特許文献１に記載の技術では、専用の暗示オペレーション命令を用いてプロセッサにキー情報を通知する必要があり、予測対象となるプログラム内に暗示オペレーション命令を組み込む手間が存在する。
　本発明は、上記手間を軽減するためのものであり、プログラムに上述の暗示オペレーション命令のような専用の処理を組み込むことなく、任意のプログラムに対して、間接分岐を含むプログラムの分岐を予測する分岐予測装置を提供することを目的とする。
　上記課題を解決するため、本発明に係る分岐予測装置は、命令を実行する命令実行部と、前記命令実行部による関数呼び出し命令の実行を通知する関数呼び出し通知部と、前記関数呼び出し通知部により関数呼び出し命令の実行が通知されたときに、当該関数呼び出し命令の少なくとも一つの引数を格納する引数スタックと、前記命令実行部により前記関数呼び出し命令により呼び出される関数に含まれる分岐命令が実行されることを通知する分岐命令通知部と、分岐命令の位置するアドレスと、当該分岐命令が実行されたときの引数スタックの先頭値と、分岐先のアドレスを示す分岐結果とを対応付けた分岐結果エントリを記憶する分岐結果記憶部と、前記分岐命令通知部が分岐命令が実行されることを通知した場合に、前記分岐結果記憶部に、実行される当該分岐命令のアドレスと前記引数スタックに格納されている引数に一致する分岐結果エントリが記録されているかどうかを検索し、あった場合に、当該分岐結果エントリの分岐結果を当該分岐命令による分岐の予測結果とする分岐予測部と、前記分岐予測部の予測した予測結果に基づき命令をフェッチする命令フェッチ部と、分岐命令の実行完了後に実行された分岐命令の位置するアドレスと、当該分岐命令の実行により分岐した分岐先のアドレスを示す分岐結果と、当該分岐命令が実行されたときの前記引数スタックの先頭値とを対応付けて、分岐結果エントリとして前記分岐結果記憶部に記録する分岐結果記録部と、を備えることを特徴としている。
　ここで、関数とは、コンピュータプログラムにおける所謂サブルーチンのことをいう。
　上述のような構成によって、分岐予測装置は、関数の呼び出しを実行する際に、その関数の引数を引数スタックが取得して、分岐命令が実行される場合に、引数スタックが保持する引数と、過去の分岐結果を用いて、分岐を予測することができる。これにより、ユーザがプログラムに上記特許文献１における暗示オペレーション命令のような特殊の命令を組み込まずとも分岐予測装置が分岐予測のためのキーとなる情報として自動的にその分岐命令が属する関数の引数を取得して分岐予測を実現でき、任意のプログラムで間接分岐の分岐予測を実現できる。
図１は、実施の形態に係る分岐予測装置の機能構成を示した機能ブロック図である。 図２は、引数スタック１１３への引数の渡し方を示す概要図である。 図３は、分岐結果バッファに格納されている分岐結果情報の構成例を示すデータ概念図である。 図４は、プログラムが実行されて引数が引数スタックに格納される様子を示す概要図である。 図５は、分岐予測部１１７が実行する分岐予測の際の検索の仕方を示す概要図である。 図６は、情報処理装置１００の分岐予測に係る動作を示したフローチャートである。 図７は、高級言語プログラムと、当該高級言語プログラムのアセンブラコードと、引数スタックに格納される引数の関係とを示す関係図である。 図８は、コンパイラ１１９のコンパイルにおける動作を示すフローチャートである。 図９は、コンパイラ１１９がコンパイルした命令を実行する際の命令実行部１１０の動作を示すフローチャートである。 図１０は、関数の引数と、分岐命令の引数と、引数スタックに格納される引数との関係を示す関係図である。 図１１は、変形例に係る情報処理装置３００の別構成例を示す機能ブロック図である。 図１２は、変形例に係る情報処理装置３００の引数スタックへの引数の渡し方の具体例を示す図である。 図１３は、変形例に係る情報処理装置３００の引数スタックへの引数の渡し方の別具体例を示す図である。 図１４は、図８に示すプログラムの分岐命令を実行した場合の分岐予測部の検索の仕方を示す概要図である。 図１５は、引数スタックへの引数の渡し方の別例を示す図である。 図１６は、図１５に示す引数スタックの引数の渡し方の具体例を示す図である。 図１７は、引数スタックの別構成例を示した図である。
＜実施の形態＞
　本発明に係る分岐予測装置の一実施形態である分岐予測機構１０００が含まれる情報処理装置１００について図面を参照しながら説明する。
＜構成＞
　図１は、情報処理装置１００の機能構成を示した機能ブロック図である。図１に示すように情報処理装置１００は、命令実行部１１０と、関数呼び出し通知部１１１と、関数リターン通知部１１２と、引数スタック１１３と、分岐命令通知部１１４と、分岐結果記録部１１５と、分類結果バッファ１１６と、分岐予測部１１７と、命令フェッチ部１１８と、コンパイラ１１９とを含んで構成される。
　情報処理装置１００は、記憶装置２００に接続されており、記憶装置２００に格納されている命令を逐次読み出して実行するプロセッサである。
　命令実行部１１０は、コンパイラ１１９が実行形式に変換した命令列を、記憶装置２００からフェッチされ、順次実行する機能を有する。
　関数呼び出し通知部１１１は、命令実行部１１０が関数呼び出しを行った場合にそれを検知して、その旨を引数スタック１１３に通知する機能を有する。ここでいう関数は所謂サブルーチンの呼び出しのことであり、１以上の命令を実行するためのルーチンの呼び出しのことをいう。高級言語における関数は、コンパイラ１１９によりプロセッサの命令列にコンパイルされて実行される。関数呼び出し通知部１１１は、コンパイラ１１９が関数の呼び出し部分のコンパイルに特定の命令を用いる場合に、当該特定の命令の実行を検知することで、関数呼び出しが実行されることを検出する。特定の命令とは、例えば、ジャンプと同時に、そのジャンプ命令の次のアドレスを戻り番地としてリターンレジスタと呼ばれる特定のレジスタに保持する命令等である。関数をどのようにコンパイルするのかは、情報処理装置１００が用いるコンパイルの規約に従って定められている。関数呼び出し通知部１１１は、その規約に従って命令列がコンパイルされることを想定して、特定の命令がどのような命令であるかを記憶しておき、その予め定められた特定の命令の実行を検知することで関数の呼び出しが実行されることを通知する。
　関数リターン通知部１１２は、命令実行部１１０が関数を終了した、即ちリターンしたかどうかを監視し、リターンした場合にその旨を引数スタック１１３に通知する機能を有する。関数の呼び出しと同様に関数のリターンにおいてもコンパイラ１１９が特定の命令を用いてコンパイルされるので、コンパイラ１１９による当該特定の命令の実行を検知することで関数リターン通知部１１２は関数のリターンを検知する。
　引数スタック１１３は、関数呼び出し通知部１１１から関数の呼び出しがあったことを通知された場合に、命令実行部１１０の特定のレジスタに格納されている値を、呼び出された関数の引数として取得し、プッシュ、即ち、記憶する機能を有する。また、関数リターン通知部１１２から、関数が終了した、即ちリターンしたことを通知された場合に、一番最後に格納した引数を出力、即ち、ポップする機能も有する。なお、引数スタック１１３は所謂ＦＩＬＯ（First In Last Out）型のメモリであり、本明細書においては、引数スタック１１３から保持している引数をポップさせる場合に出力される値を引数スタック１１３の先頭値と記載する。上述のプッシュとポップを行うことにより、引数スタック１１３の先頭値には、必ず、現在実行されている関数の引数が保持される構成となっている。
　図２は引数スタック１１３における処理、即ち引数の取得の仕方の詳細を示す図である。
　関数への引数の渡し方についても予め定められており、関数の引数は、通常、高級言語プログラムにおいて記載されている順に、命令実行部１１０が保持するレジスタ群１２０の各レジスタに割り当てられている番号の小さいものから順に、格納されていく。つまり、レジスタ０が関数の第１引数を、レジスタ１が関数の第２引数を、レジスタ２が関数の第３引数を、・・・というように各レジスタに引数が格納される。こうして、レジスタに格納されている引数のうち、本実施の形態においては、図２に示すように、引数スタック１１３は、レジスタ０に格納されている引数を取得して、記憶する。
　また、図４は、引数スタック１１３への引数の格納の手順の一具体例を示している。
　プログラム４００の関数ｆｕｎｃＡは、引数ａ０、ａ１、ａ２を受け取る。この引数ａ０は、レジスタ０に格納され、引数スタック１１３にプッシュされる。関数ｆｕｎｃＡ内において、プログラム４００は、関数ｆｕｎｃＢを呼び出す。関数ｆｕｎｃＢは、引数ｂ０、ｂ１、ｂ２を受け取る。引数ｂ０は、レジスタ０に格納され、引数スタック１１３にプッシュされる。関数ｆｕｎｃＢ内において、プログラム４００は、関数ｆｕｎｃＣを呼び出す。関数ｆｕｎｃＣは、引数ｃ０、ｃ１、ｃ２を受け取る。引数ｃ０は、レジスタ０に格納され、引数スタック１１３にプッシュされる。図４のプログラム４００の右横には、そのときの引数スタック１１３の保持している引数の情報を示しており、図４を見れば明らかなように、最後に呼び出された関数ｆｕｎｃＣの第１引数であるｃ０が先頭値となっている。なお、図４においては、引数スタック１１３の上側が先頭値となる。
　図１に戻って、分岐命令通知部１１４は、命令実行部１１０が実行する命令が分岐命令であるかを判定し、肯定的な判定をした場合に、その旨を分岐結果記録部１１５と分岐予測部１１７に通知する機能を有する。
　分岐結果記録部１１５は、分岐命令通知部１１４から分岐命令の実行が通知されると、命令実行部１１０が実行した当該分岐命令のアドレスを取得するとともに、命令実行部１１０における当該分岐命令の実行の結果、分岐した分岐先のアドレスとを取得する。また、分岐結果記録部１１５は、分岐命令を実行したときの引数スタック１１３の先頭値も取得する。分岐結果記録部１１５は、そして、取得した分岐命令のアドレスと、分岐の時点での引数スタック１１３の先頭値と、分岐命令の分岐先のアドレスとを対応付けて、分岐結果バッファ１１６に記録する機能を有する。
　分岐結果バッファ１１６は、分岐命令が位置するアドレスと、当該分岐命令が実行されるときの引数スタックの先頭値と、分岐命令の分岐先のアドレスとを対応付けた分岐結果エントリを記憶しているメモリである。
　図３に、分岐結果バッファ１１６が記憶している分岐結果情報のデータ構成例を示すデータ概念図を示す。
　分岐結果情報は、分岐命令アドレス３０１と、引数スタックの先頭値３０２と、分岐先３０３とを対応付けた分岐結果エントリを統合した情報である。
　分岐命令アドレス３０１は、分岐命令の位置するアドレスを示す情報である。
　引数スタックの先頭値３０２は、対応する分岐命令が実行されたときの、引数スタック１１３に格納されていた引数を示す情報である。
　分岐先３０３は、分岐命令が実際に実行されて、分岐した分岐先のアドレスを示す情報である。
　当該分岐結果情報が分岐結果バッファ１１６に記憶されていることにより、分岐予測部１１７は、分岐の予測を実行できる。
　図１に戻って分岐予測部１１７は、分岐命令通知部１１４からの通知を受けると、当該通知とともに伝達される分岐命令のアドレスと、そのときの引数スタック１１３の先頭値とを取得する。分岐予測部１１７は、取得した分岐命令のアドレスと、引数スタック１１３の先頭値の両方とに一致する分岐結果エントリが分岐結果バッファ１１６にあるかどうかを検索する。そして、分岐予測部１１７は、一致する分岐結果エントリがあった場合に、当該分岐結果エントリの分岐先を、分岐命令の予測先として、命令フェッチ部１１８に通知する機能を有する。
　図５は、その分岐予測部１１７が分岐結果バッファを検索する際の検索の仕方を示した概要図である。
　図５に示すように、分岐予測部１１７は、分岐命令の位置するアドレスとそのときに引数スタック１１３から取得した引数とが対応する分岐結果エントリが、分岐結果バッファ１１６にあるかどうかを検索する。即ち、分岐予測部１１７は、実行される分岐命令のアドレスを取得し、取得した分岐命令のアドレスと一致するアドレスがあるかどうかを検索する。
　次に、分岐命令のアドレスと一致する分岐結果エントリがある場合に次に、その分岐結果エントリのうち、引数スタック１１３から取得した引数について引数スタックの先頭値３０２に一致するものがあるかどうかを検索する。
　こうして、両者に一致する分岐結果エントリの分岐先を、分岐命令の分岐先として予測する。
　再度、図１に戻って、命令フェッチ部１１８は、記憶装置２００より命令をフェッチする機能を有する。命令フェッチ部１１８は、分岐予測部１１７から、次に実行する命令のアドレスを通知されていた場合に、通知されたアドレスから命令のフェッチを行う機能を有する。
　以上が、情報処理装置１００の各機能部の説明である。　
＜動作＞
　図６は、情報処理装置１００の分岐予測の動作を示したフローチャートである。本フローチャートに基づいて、情報処理装置１００の分岐予測における動作を説明する。
　図６に示すように、情報処理装置１００の分岐命令通知部１１４は、分岐命令が実行されることを検知して、その旨を分岐予測部１１７に通知する（ステップＳ６０１）。
　分岐予測部１１７は、分岐命令通知部１１４から、分岐命令の実行を通知されると、そのときの引数スタック１１３の先頭値を取得する。また、分岐予測部１１７は、分岐命令通知部１１４からは、実行される分岐命令のアドレスも取得する（ステップＳ６０２）。
　そして、取得した分岐命令のアドレスと、引数スタック１１３の先頭値とに一致する分岐結果エントリが、分岐結果バッファ１１６に記憶されているかどうかを検索する（ステップＳ６０３）。
　分岐予測部１１７は、分岐結果バッファ１１６に分岐結果エントリが記憶されていた場合（ステップＳ６０３のＹＥＳ）、実行される分岐命令のアドレスと、引数スタック１１３の先頭値とに一致する分岐結果エントリの分岐先３０３を、当該分岐命令の分岐先として予測する（ステップＳ６０４）。
　命令フェッチ部１１８は、分岐予測部１１７から通知されたアドレスの命令を記憶装置２００から呼び出して、命令実行部１１０にフェッチする（ステップＳ６０５）。
　分岐結果バッファ１１６に分岐結果エントリが記憶されていなかった場合（ステップＳ６０３のＮＯ）、分岐予測部１１７は、命令フェッチ部１１８に予測なしを示す情報を出力する。すると命令フェッチ部１１８は、当該分岐命令の次のアドレスの命令をフェッチする。
　そして、実際に分岐命令が実行される（ステップＳ６０７）と、分岐結果記録部１１５は、当該分岐命令のアドレスと、当該分岐命令が実行された時点における引数スタック１１３の先頭値と、分岐命令の実行の結果分岐した分岐先のアドレスとを対応付けた分岐結果エントリを分岐結果バッファ１１６に記録する（ステップＳ６０８）。
　以上が、分岐予測部１１７の分岐予測並びに分岐命令の実行時の情報処理装置１００の動作である。
　図７は、高級言語プログラムと、コンパイルされたプロセッサ命令列、そして、その命令列が実行されることによって、引数スタック１１３に格納される引数を示す図である。
　図７に示す高級言語プログラム７０１の関数ｉｎｔｅｒｐｒｅｔｅｒは、擬似命令ｉｎｓｔを引数とするインタープリンタ言語の実行関数である。Ｊａｖａ（登録商標）Ｓｃｒｉｐｔなどは、テキストファイルのプログラムを解釈して擬似命令にコンパイルした後、その擬似命令をインタープリンタで処理する。典型的には、インタープリンタを実装する関数は、図７に示したように個々の擬似言語に応じた処理をｓｗｉｔｃｈ～ｃａｓｅ文で実現する。
　図７に示すプロセッサ命令列７０２は、関数ｉｎｔｅｒｐｒｅｔｅｒを、擬似的なプロセッサ命令列で示したものである。ここでは、ｍｖ命令で引数ｉｎｓｔをレジスタｒ０に格納した後、ｂｌ命令で関数ｉｎｔｅｒｐｒｅｔｅｒの先頭へのジャンプ（関数呼び出し）が行われる。
　関数ｉｎｔｅｒｐｒｅｔｅｒ内においては、まず下位関数として、関数ｆｕｎｃが、引数をａとして呼び出される。
　その後、レジスタｒ０、即ち関数ｉｎｔｅｒｐｒｅｔｅｒの引数がＡであるかをｔｓｔ命令で判定する。Ａと等しい場合にレジスタｒ１に数値０ｘ０１０００が格納される。同様にｒ０がＢならばレジスタｒ１には０ｘ２０００が格納される。アドレス０ｘ０１００に位置するｍｖ命令にてプログラムカウンタ（ｐｃ）にレジスタｒ１の値が代入され、分岐が発生する。つまり関数ｉｎｔｅｒｐｒｅｔｅｒの引数ｉｎｓｔがＡならば０ｘ１０００への、Ｂならば０ｘ２０００への分岐となる。
　図７の右段には、プロセッサ命令列７０２が実行されていく過程における引数スタック１１３の状態を示している。
　関数ｉｎｔｅｒｐｒｅｔｅｒの呼び出し時には、引数ｉｎｓｔが引数スタック１１３にプッシュされる。また、その後に呼び出される下位関数ｆｕｎｃの呼び出し時には、下位関数ｆｕｎｃの引数ａが引数スタック１１３にプッシュされる。この時点で引数ａが引数スタックの先頭値になる。
　また、関数ｆｕｎｃのリターン時には、引数ａがポップされ、引数ｉｎｓｔが再び引数スタック１１３の先頭値になる。アドレス０ｘ０１００の分岐が発生した際、引数ｉｎｓｔがＡの際は分岐結果バッファ１１６に分岐先アドレスが０ｘ１０００の分岐結果エントリが作られる。アドレス０ｘ０１００の分岐が発生した際、引数ｉｎｓｔがＢの際は分岐結果バッファ１１６に分岐先アドレスが０ｘ２０００の分岐結果エントリが作られる。
　当該分岐結果エントリができるとそれ以降に引数ＡやＢで関数ｉｎｔｅｒｐｒｅｔｅｒを実行した際、アドレス０ｘ０１００に位置する分岐命令の実行時に、それぞれの分岐先アドレスが予測値として得られるようになる。
　図８は、コンパイラ１１９のコンパイルにおける動作を示すフローチャートである。図８は、特に、関数の呼び出し時の関数のコンパイルの動作を示している。なお、ここでは、本実施の形態の発明に係る部分のみの動作を記載するものとし、その他の動作についての詳細は従来のコンパイルに準ずるものとして割愛する。
　コンパイラ１１９は、関数のコンパイル時に、当該関数内において、特定の引数が分岐先を決定するかどうかを判定する（ステップＳ８０１）。
　当該判定には、以下の手順を踏む。まず、関数を解析し、関数内に分岐命令があるかどうかを検索する。そして、分岐命令があった場合に、当該分岐命令の分岐の条件に用いられるデータが、関数の引数に含まれているかどうかを判定する。これによって、関数の引数が分岐先を決定するかどうかを判定する。
　関数の呼び出し時に当該関数の引数のうち、特定の引数が分岐先を決定すると判定された場合に（ステップＳ８０１のＹＥＳ）、分岐先を決定する引数を、引数スタック１１３が値を取得するレジスタに格納するコードを生成する（ステップＳ８０２）。即ち、関数の引数に含まれる特定の引数をレジスタ０に格納させるコードを生成する。例えば、分岐先を決定する引数が関数の第１引数であった場合には、当該第１引数をレジスタ０に、分岐先を決定する引数が関数の第３引数であった場合には、当該第３引数をレジスタ０に格納させるコードを生成する。
　そして、コンパイラ１１９は、引数スタック１１３にどのレジスタの引数を取得するのかを指定するコードを生成する（ステップＳ８０３）。ここでは、コンパイラ１１９は、引数スタック１１３に、レジスタ０の値を取得するコードを生成する。
　そして、コンパイラ１１９は、関数内の各命令を通常通りコンパイルして終了する。
　特定の引数が分岐先を決定しない場合（ステップＳ８０１のＮＯ）、コンパイラ１１９は、通常通り、関数の各命令をコンパイルして終了する。
　図９は、図８に示した動作に従ってコンパイルされたコード列においてオブジェクトファイルのリンク動作を示すフローチャートである。当該動作は、命令実行時の値のレジスタへの格納の仕方を示すものであり、それ以外の動作については、従来の命令の実行の仕方に準ずるものとし、ここでは割愛する。
　図９に示すように、命令実行部１１０は、呼び出し先の関数が引数を渡すレジスタを指定する情報を保持しているか否かを判定する（ステップＳ９０１）。
　引数を渡すレジスタを指定する情報を保持している場合には（ステップＳ９０１のＹＥＳ）、コンパイラ１１９は、その情報に従って、関数呼び出し部分のレジスタへ引数を格納するコードを修正する（ステップＳ９０２）。つまり、どの引数をどのレジスタに格納するのかを指定するコードがある場合に、指定されている引数をレジスタ０に格納するコードに修正する。指定されていない場合には、高級言語プログラムに記載されている順で、関数の引数がレジスタ番号の若い順に格納される。
　全ての関数呼び出しのリンクを終了したかどうかを判定し（ステップＳ９０３）、終了していた場合には（ステップＳ９０３）、オブジェクトファイルのリンク処理を終了し、終了していなかった場合には、ステップＳ９０１に戻る。
　このコンパイル方法に従って、関数呼び出しが実行され、分岐命令が実行された場合の例を、図１０を用いて説明する。図１０は、関数が呼び出されて、その関数内で分岐命令が実行される場合の一具体例を示している。ここでは、分岐命令の一例として、ｓｗｉｔｃｈ～ｃａｓｅ文を示している。ｓｗｉｔｃｈ～ｃａｓｅ文は、例えば、Ｃ言語や、Ｃ＋＋、ＰＨＰ（Hypertext Preprocessor。なお、ＰＨＰは、Personal Home Page toolsの略であるがＰＨＰの本来意味するところは、Hypertext Preprocessorである。）などの言語で用いられる。本実施の形態に係る情報処理装置１００の分岐予測部が予測を成功にさせるためには、分岐に影響する関数の引数を、引数スタック１１３に記憶する必要がある。図１０では、その為の引数のレジスタへの格納の仕方を示している。
　図１０（ａ）のプログラム１００１では、ｓｗｉｔｃｈ文に影響する引数は、ｓｗｉｔｃｈ文の引数がａ０であることから、分岐に関連する引数もａ０であることがわかる。そこで、関数ｆｕｎｃＡの呼び出し時には、引数スタック１１３には、引数ａ０が渡される必要がある。そのため、ｆｕｎｃＡの第１引数であるａ０がレジスタ０に格納される構成をとる。この場合のコンパイラ１１９が生成するコードは、例えば、第１引数をレジスタ０に格納する命令、例えば、「ｍｖ　ｒ０（ａ０）」などによって実現される。上述の通り、引数スタック１１３に渡される引数は、レジスタ０に格納されている値なので、これにより、分岐に関連する引数が引数スタック１１３に格納されることとなる。
　一方、図１０（ｂ）のプログラム１００２では、ｓｗｉｔｃｈ文に関連する引数は、ｂ１である。当該引数ｂ１は、関数ｆｕｎｃＢの第２引数となっている。そこで、図１０（ｂ）の場合においては、ｆｕｎｃＢの第２引数ｂ１がレジスタ０に格納される構成となる。これにより、引数スタック１１３に分岐に関連する引数が格納されることとなる。この第２引数が格納される構成はコンパイラ１１９によるコンパイル時に引数のレジスタへの格納の際の格納の仕方を指定することにより実現される。
＜変形例＞
　上記実施の形態において示した情報処理装置１００を変形した別構成例の情報処理装置３００について説明する。本変形例においては、上記実施の形態に示した情報処理装置１００との差異についてのみ説明するものとし、その他の情報処理装置１００に共通する内容については、説明を割愛する。
　図１１は、情報処理装置３００の機能構成を示す機能ブロック図である。
　情報処理装置３００は、情報処理装置１００とは異なり、命令実行部１１０とは一部別の動作をする命令実行部１２２を備え、また、情報処理装置１００が備えていなかった引数番号通知部１２１を備える。その他の構成については、情報処理装置３００は情報処理装置１００と同様の構成をとる。
　命令実行部１２２は、命令フェッチ部１１８により記憶装置２００からフェッチされた命令を実行し、更に、分岐に影響する関数の引数を指定する命令を解釈して、引数番号通知部２１に通知する機能を有する。引数を指定する命令は、コンパイル時にコンパイラがプログラムを解析し、自動的に付加するものとする。
　引数番号通知部１２１は、指定された引数の番号を命令実行部１２２から取得し、取得した引数番号を引数スタック１２３に通知する機能を有する。
　引数スタック１２３は、引数番号通知部１２１から通知を受けて、指定された引数をプッシュする機能を有する。引数スタック１２３は、引数スタック１１３と同様に、関数呼び出し通知部１１１からの通知を受けて、その関数の引数をプッシュし、関数リターン通知部１１２からの通知を受けて、その関数の引数をポップする。即ち、引数スタック１２３の先頭値には現在実行中の関数の引数が保持される。
　当該構成を備えることにより、情報処理装置１００の分岐予測機構１１００は、分岐に影響する引数をより確実に引数スタックに格納することができる。
　図１２は、引数スタック１２３における、関数の引数を保存した例を示している。図１２は、引数番号通知部１２１を用いて関数の引数を取得する手順を示している。図１２（ａ）では、分岐となるｓｗｉｔｃｈ～ｃａｓｅ文に影響する引数は、ａ０である。図１２（ａ）に示される命令ａｒｇが分岐に影響する引数を通知する。図１２（ａ）の命令ａｒｇのオペランド０は、分岐に影響する引数が格納されたレジスタ群１２０のレジスタ番号を示す。ゆえに、図１２（ａ）の場合、引数スタック１２３は、ａｒｇ命令で指定されたレジスタ０の値をプッシュする。
　図１２（ｂ）では、分岐に影響する引数は、ｂ１である。図１２（ｂ）の命令ａｒｇのオペランドは、１となっている。これにより、分岐に影響するレジスタ群１２０のレジスタ番号がレジスタ１であることがわかり、引数スタック１２３は、関数呼び出しの際に、ａｒｇ命令で指定されたレジスタ１の値をプッシュする。
　当該構成を実現するために、コンパイラ１１９は、コンパイル時にこのａｒｇ命令を生成する必要がある。上記実施の形態においては、コンパイラ１１９は、どの引数をレジスタ０に格納するかを指定するコードを生成した（ｍｖ命令でレジスタに格納する値を指定していた）のに対し、本変形例においては、どのレジスタの値を引数スタックがプッシュするのかを指定するコードを生成する。
＜まとめ＞
　上記実施の形態、及び、その変形例において示してきたように、情報処理装置１００は、関数呼び出しを行う際に、その引数を取得する引数スタックを備える。そして、分岐命令が実行される段において、その引数スタックに格納されている値の先頭値と、実行される分岐命令の位置するアドレスとから、過去の分岐結果を検索して、分岐先を予測する。また、分岐命令が実際に実行された場合に、その分岐命令の位置するアドレスと、その時点での引数スタックの先頭値と、分岐先のアドレスとを対応付けた分岐結果エントリを記憶しておくことで、以降において実行される分岐命令の分岐先の予測の確度を高めていくことができる。関数呼び出しにおいて、その引数を取得する引数スタックを備えることにより、従来技術のような暗示オペレーション命令という分岐予測のキー情報を指定する命令を組み込まずとも、間接分岐の分岐予測を実現できる。即ち、任意のプログラムにおいて、そのプログラム内に含まれる分岐命令の分岐先の予測が可能となる。
＜補足＞
　上記実施の形態において、本発明の実施の手法について説明してきたが、本発明の実施形態がこれに限られないことは勿論である。以下、上記実施形態以外に本発明として含まれる各種の変形例について説明する。
（１）上記実施の形態においては、関数呼び出し通知部１１１は、命令実行部１１０が実行する命令がコンパイラ１１９により特定の命令を以ってコンパイルされることを検知して、関数の呼び出しが実行されることを通知する構成とした。しかし、関数の呼び出しを検知する手法はこれに限るものではなく、実行される命令を解析して、予め定められた特定の命令文と一致する命令があるかどうかで検知してもよい。あるいは、コンパイラ１１９が関数呼び出しを通知する専用の命令を生成して、関数呼び出し通知部１１１に当該命令を出力することで、関数呼び出し通知部１１１が関数呼び出しの実行を検知することとしてもよい。
　同様に、関数リターン通知部１１２も上記実施の形態において示したようにコンパイラ１１９が特定の命令を実行したことを検知することで、関数のリターンの実行を検知するのではなく、上述した手法、例えば、コンパイラからの関数リターンの実行の通知を受けるなどの手法用いて関数のリターンを検知することとしてもよい。
（２）上記実施の形態においては、分岐予測部１１７が、引数スタック１１３の先頭値を用いて予測する手法を示したが、分岐命令実行時に、その分岐命令がどの関数内において実行されるのか、また、その関数に対応する引数がどれであるのかを対応付けて記憶されているのであれば、引数スタック１１３の先頭値ではなく、必要とする引数を参照する構成としてもよい。つまり、引数スタック１１３は、引数を取得する際に、そのとき呼び出された関数を示す情報とを対応付けて記憶するものとし、分岐予測部１１７は、分岐命令の実行を通知されたときに、その分岐命令が含まれる関数の情報を受け取り、当該関数の情報で示される関数に対応する引数を引数スタック１１３から取得する構成としてもよい。
（３）上記実施の形態においては、分岐予測部１１７が分岐命令のアドレスと、引数スタック１１３の先頭値とが一致する分岐結果エントリが複数ある場合について詳細に説明しなかった。ここでは、その説明をする。
　分岐結果エントリは上述した内容に更に、分岐したかどうかの頻度を求めるための情報も対応付けられていてもよい。即ち、各分岐結果エントリは、更に分岐カウント値も対応付けられていてもよい。当該分岐カウント値は、その分岐結果エントリに示される分岐命令が実際にその分岐結果エントリで示される分岐先に分岐した場合に＋１され、分岐しなかった場合に－１される。
　そして、分岐予測部１１７は、検索の結果該当する分岐結果エントリが複数ある場合には、分岐カウント値が最も高い分岐結果エントリの分岐先を、実行される分岐命令の分岐先として、命令フェッチ部１１８にアドレスを通知してよい。
　これにより、分岐予測の確度を高めることができる。
　なお、上述の分岐カウント値において、当該分岐カウント値は、分岐結果エントリの分岐の確度を示すためのものであればよく、上述の分岐しなかった分岐結果エントリの分岐カウンタを－１する構成は設けなくともよい。
　また、加算する値も１でなくともよく、予め定められた値であってもよい。
（４）上記実施の形態においては、分岐に影響する引数が１つの場合の具体例を示したが、分岐に影響する引数が複数ある場合がある。
　ここでは、その場合についての情報処理装置３００における動作について図１３を参照しながら説明する。
　図１３は、このような場合に、引数を指定する命令で、順に分岐に影響する引数を指定する例を示している。
　図１３のｓｗｉｔｃｈ文に示されるように、その引数は、各分岐に引数ａ１、ａ０が分岐に影響する。そのため、プロセッサ命令列のａｒｇ命令で示されるように、高級言語プログラムの関数呼び出し時の引数の順序（ａ０、ａ１、ａ２）におけるａ０とａ１の順序とは逆に命令列としてコンパイルされる。
　そして、引数スタック１２３は、この順序で引数をプッシュする。即ち、先にａ０をプッシュし、その後にａ１をプッシュする。こうすることで、分岐命令の実行時に、各分岐命令に関連する引数を分岐予測のキー情報として用いることができる。なお、分岐の予測、分岐結果バッファへの分岐結果エントリへの格納は、引数スタックからポップさせた引数を利用する。
　なお、図１３（ａ）に示した構成は、図１３（ｂ）に示すような構成によっても実現できる。即ち図１３（ｂ）に示すように引数スタック１２３が複数の引数を保持できる構成である。図１３（ｂ）には、引数スタック１２３が一段階で複数の引数を保持できる場合を示している。分岐予測部１１７は、分岐予測の際には、引数スタック１２３の同じ段階に格納された値を順に用いる。
　どの引数をどのレジスタに格納するかについては、上記実施の形態、変形例に示したように、コンパイラ１１９が、レジスタに格納する変数を指定するコードを生成することによって実現できる。
（５）上記実施の形態においては、間接分岐の例を示したが、分岐先が固定されている分岐命令の条件実行時に、予測することも可能である。
　図１４は、分岐先が固定されている場合の分岐結果バッファ１１６への記録の例を示している。図１４のプログラム例では、ｔｓｔ命令でレジスタｒ０の値がａと等しいかが判断され、その結果によって条件分岐命令ｂｌｅｑが実行されるかが決まる。ｂｌｅｑ命令が実行されるとｒ１で示されるアドレスへの分岐が発生する。
　分岐結果バッファ１１６に格納されている分岐結果情報は、分岐命令の位置する分岐命令アドレス３０１と、引数スタック１１３の先頭値３０２と、分岐が発生したか否かの分岐結果が対応付けられている。
　分岐予測部１１７は、条件分岐命令が実行される場合に、分岐結果バッファ１１６に当該条件分岐命令の位置するアドレスと、そのときの引数スタック１１３の先頭値とに一致する分岐結果エントリがあるかどうかを検索し、あった場合に、その分岐結果エントリの分岐３０４が分岐したことを示す場合に、固定となっている分岐先のアドレスを命令フェッチ部１１８に通知し、分岐しなかったことを示す場合に、条件分岐命令の次のアドレスを命令フェッチ部１１８に通知する。
　この構成によって、間接分岐だけでなく、条件分岐の分岐予測も可能となる。
（６）上記実施の形態においては、命令実行部１１０が引数を格納するためのレジスタ群１２０を備える構成を示した。
　ここでは、命令実行部１１０が、レジスタ群１２０を備える構成以外の構成について説明する。即ち、命令実行部１１０が、引数を記憶装置２００に記憶する構成にした場合を、図１５を用いて説明する。
　この場合、命令実行部１１０は、引数をどこに格納したかを示すスタックポインタレジスタ１５０１を備える。そして、記憶装置２００は、スタックポインタレジスタ１５０１で示されるスタック１５０２に、関数の引数を記憶する。引数スタック１１３は、関数呼び出し通知部１１２により関数の呼び出しが通知された場合に、命令実行部１１０からスタックポインタレジスタ１５０１の値を取得し、記憶装置２００の当該スタックポインタレジスタ１５０１で示されるスタック１５０２に格納されている値を引数として取得して記憶する。
　このような構成にしても、引数スタック１１３は分岐命令に関連する関数呼び出し時の引数をプッシュできる。
　図１５に示す手法を用いて、引数の取得を行った場合の具体例を図１６に示す。
　図１６（ａ）に示すように、プログラム５０１中のｆｕｎｃＡが呼び出された際に、その関数ａ０、ａ１、ａ２がスタック１６０２の先頭にａ０が来るように格納される。このときスタックポインタレジスタ１５０１にはスタック１６０２の先頭アドレスが格納される。
　そして、分岐命令（図１６（ａ）のｓｗｉｔｃｈ文）が実行されるタイミングで、引数スタック１１３には、スタックポインタレジスタ１５０１で示されるアドレスであるスタック１６０２の先頭に保持されているａ０が引数スタック１１３に格納される。
　また、図１６（ｂ）に示すように、プログラム５０２中のｆｕｎｃＢが呼び出された際に、その関数ｂ０、ｂ１、ｂ２がスタック１６０２の先頭に分岐命令に関連するｂ１が来るように格納される。このときスタックポインタレジスタ１５０１にはスタック１６０２の先頭アドレスが格納される。
　そして、分岐命令（図１６（ｂ）のｓｗｉｔｃｈ文）が実行されるタイミングで、引数スタック１１３には、スタックポインタレジスタ１５０１で示されるアドレスであるスタック１６０２の先頭に保持されているｂ１が引数スタック１１３に格納される。
（７）上記実施の形態においては、引数スタック１１３にレジスタ０に格納されている値のみを格納する構成を示した。
　ここでは、本発明の思想として含まれるそれ以外の実施の形態を示す。
　図１７（ａ）は、引数スタック１１３の容量を多くとり、レジスタ０に格納されている引数だけでなく、関数呼び出しの際に受け取る引数全てを格納する例を示している。
　また、ここでは、全ての引数を引数スタックに渡す場合を記載しているが、関数呼び出しの際に受け取る引数全てでなくとも、そのうちの複数の引数を格納する構成としてもよい。例えば、図１７（ａ）の例で言えば、引数ａ０と引数ａ１と引数ａ２とを引数スタックに格納する構成としてもよい。この場合には、例えば、レジスタ０～レジスタ２に格納されている３つの引数を格納するという構成にすればよい。
　これにより引数１つのみで、分岐予測を行う場合に比して、分岐予測の確度を高めることができる。
　また、図１７（ｂ）に示すように、引数スタック１１３は、レジスタ０の引数を格納するだけでなく、更に、引数スタック１１３をリターンスタックと兼用してもよい。即ち、リターンスタックを用いるプロセッサにおいては、引数スタックと同じタイミングで、リターンアドレスのプッシュとポップが行われるので、同じスタック内にリターンアドレスと引数とを組にして保持してもよい。なお、図１７（ｂ）において、ａｄｄｒｅｓｓＡ、ａｄｄｒｅｓｓＢ、ａｄｄｒｅｓｓＣは、それぞれｆｕｎｃＡ、ｆｕｎｃＢ、ｆｕｎｃＣのリターンアドレスを示している。こうすることで、リターンスタックとの併用が可能になる。
（８）上記実施の形態においては、関数の引数を保持するのに引数スタックを用いたが、引数スタックとして用いるものは必ずしもスタック形式に限るものではなく、上記実施の形態において引数スタックとして示した内容を実行できるものであればよい。
（９）図１及び図１１に示した情報処理装置１００、３００の各機能部は集積化されて１又は複数のＬＳＩ（Large Scale Integration）により実現されてもよい。また、複数の機能部が１のＬＳＩにより実現されてもよい。
　ＬＳＩは集積度の違いにより、ＩＣ（Integrated Circuit）、システムＬＳＩ、ＶＬＳＩ（Very Large Scale Integration）、ＳＬＳＩ（Super Large Scale Integration）、ＵＬＳＩ（Ultra Large Scale Integration）などと呼称されることもある。
　また、集積回路化の手法はＬＳＩに限られるものではなく、専用回路または汎用プロセッサで実現しても良い。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用しても良い。
　さらに、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行っても良い。バイオ技術の適応等が可能性としてあり得る。
（１０）上述の実施形態で示した分岐予測に係る動作、分岐予測の処理等（図６等参照）を情報処理装置等のプロセッサ、及びそのプロセッサに接続された各種回路に実行させるためのプログラムコードからなる制御プログラムを、記録媒体に記録すること、又は各種通信路（例えば、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク）等を介して流通させ頒布させることもできる。このような記録媒体には、ＩＣカード、ハードディスク、光ディスク、フレキシブルディスク、ＲＯＭ等がある。流通、頒布された制御プログラムはプロセッサに読み出され得るメモリ等に格納されることにより利用に供され、そのプロセッサがその制御プログラムを実行することにより、実施形態で示したような各種機能が実現されるようになる。
（１１）以下に本発明に係る分岐予測装置の実施態様とその効果について説明する。
　本発明に係る分岐予測装置は、命令を実行する命令実行部と、前記命令実行部による関数呼び出し命令の実行を通知する関数呼び出し通知部と、前記関数呼び出し通知部により関数呼び出し命令の実行が通知されたときに、当該関数呼び出し命令の少なくとも一つの引数を格納する引数スタックと、前記命令実行部により前記関数呼び出し命令により呼び出される関数に含まれる分岐命令が実行されることを通知する分岐命令通知部と、分岐命令の位置するアドレスと、当該分岐命令が実行されたときの引数スタックの先頭値と、分岐先のアドレスを示す分岐結果とを対応付けた分岐結果エントリを記憶する分岐結果記憶部と、前記分岐命令通知部が分岐命令が実行されることを通知した場合に、前記分岐結果記憶部に、実行される当該分岐命令のアドレスと前記引数スタックに格納されている引数に一致する分岐結果エントリが記録されているかどうかを検索し、あった場合に、当該分岐結果エントリの分岐結果を当該分岐命令による分岐の予測結果とする分岐予測部と、前記分岐予測部の予測した予測結果に基づき命令をフェッチする命令フェッチ部と、分岐命令の実行完了後に実行された分岐命令の位置するアドレスと、当該分岐命令の実行により分岐した分岐先のアドレスを示す分岐結果と、当該分岐命令が実行されたときの前記引数スタックの先頭値とを対応付けて、分岐結果エントリとして前記分岐結果記憶部に記録する分岐結果記録部と、を備えることを特徴とする分岐予測装置である。
　また、本発明は、情報処理装置が関数中に含まれる分岐命令の分岐先を予測する分岐予測方法であって、関数呼び出し命令の実行を通知する関数呼び出し通知ステップと、前記関数呼び出し通知ステップにより関数呼び出し命令の実行が通知されたときに、当該関数呼び出し命令の少なくとも一つの引数を格納する引数スタックに格納する格納ステップと、前記関数呼び出し命令により呼び出される関数に含まれる分岐命令が実行されることを通知する分岐命令通知ステップと、前記分岐命令通知ステップにより分岐命令が実行されることを通知された場合に、分岐命令の位置するアドレスと、当該分岐命令が実行されたときの引数スタックの先頭値と、分岐先のアドレスを示す分岐結果とを対応付けた分岐結果エントリを記憶する前記コンピュータに接続された分岐結果記憶媒体から、実行される当該分岐命令のアドレスと前記引数スタックに格納されている引数に一致する分岐結果エントリが記録されているかどうかを検索し、あった場合に、当該分岐結果エントリの分岐結果を当該分岐命令による分岐の予測結果とする分岐予測ステップと、前記分岐予測ステップにおいて予測した予測結果に基づき命令をフェッチする命令フェッチステップと、分岐命令の実行完了後に実行された分岐命令の位置するアドレスと、当該分岐命令の実行により分岐した分岐先のアドレスを示す分岐結果と、当該分岐命令が実行されたときの前記引数スタックの先頭値とを対応付けて、分岐結果エントリとして前記分岐結果記憶部に記録する分岐結果記録ステップとを含むことを特徴とする分岐予測方法である。
　また、本発明は、プログラムを実行する際の分岐命令の分岐先を予測する分岐予測処理をコンピュータが実行するための分岐予測プログラムを記録したコンピュータ読み取り可能な分岐予測プログラム記録媒体であって、前記分岐予測処理は、関数呼び出し命令の実行を通知する関数呼び出し通知ステップと、前記関数呼び出し通知ステップにより関数呼び出し命令の実行が通知されたときに、当該関数呼び出し命令の少なくとも一つの引数を格納する引数スタックに格納する格納ステップと、前記関数呼び出し命令により呼び出される関数に含まれる分岐命令が実行されることを通知する分岐命令通知ステップと、前記分岐命令通知ステップにより分岐命令が実行されることを通知された場合に、分岐命令の位置するアドレスと、当該分岐命令が実行されたときの引数スタックの先頭値と、分岐先のアドレスを示す分岐結果とを対応付けた分岐結果エントリを記憶する前記コンピュータに接続された分岐結果記憶媒体から、実行される当該分岐命令のアドレスと前記引数スタックに格納されている引数に一致する分岐結果エントリが記録されているかどうかを検索し、あった場合に、当該分岐結果エントリの分岐結果を当該分岐命令による分岐の予測結果とする分岐予測ステップと、前記予測ステップにおいて予測した予測結果に基づき命令をフェッチする命令フェッチステップと、分岐命令の実行完了後に実行された分岐命令の位置するアドレスと、当該分岐命令の実行により分岐した分岐先のアドレスを示す分岐結果と、当該分岐命令が実行されたときの前記引数スタックの先頭値とを対応付けて、分岐結果エントリとして前記分岐結果記憶部に記録する分岐結果記録ステップとを含むことを特徴とする分岐予測プログラム記録媒体である。
　引数スタックが関数呼び出し時にその関数の引数を取得する構成を備え、当該引数と、過去の分岐結果を対応付けた情報を分岐結果記憶部が保持しており、実際に分岐命令が実行されるタイミングにおいて、分岐予測部が、分岐命令のアドレスと、引数スタックの先頭値とに基づいて、過去の分岐結果を分岐結果記憶部から検索して、検索がヒットした場合に、分岐結果エントリの分岐先を分岐命令の分岐先として予測することができる。
　また、実際に分岐命令が実行された際には、その分岐命令の位置するアドレスと、引数スタックの先頭値と、分岐先のアドレスとが対応付けられた分岐結果エントリが分岐結果記憶部に追加されるので、以降において分岐命令が実行される場合の分岐予測の確度を高めることができる。
　前記分岐予測装置は、更に、前記命令実行部による関数リターン命令の実行を通知する関数リターン通知部を備え、前記引数スタックは、前記関数リターン通知部から関数リターン命令の実行が通知されたときに、当該関数リターン命令に対応する関数の引数を削除することとしてもよい。
　これにより、関数がリターンされると、引数スタックに格納されている引数が削除されることにより、常に、引数スタックの先頭値を、現在実行されている関数の引数とすることができ、分岐予測装置は、間違いなく分岐命令が含まれる関数の引数を分岐の予測のための情報として用いることができる。
　また、前記分岐予測装置において、前記分岐命令は条件付分岐命令であり、前記分岐結果記録部は、更に、条件付分岐命令が実行されたか否かを示す情報が対応付けられた分岐結果エントリを記録することとしてもよい。
　これにより、分岐命令が条件分岐命令である場合に、その条件分岐の成否の情報を対応付けることにより、例えば、その成否に基づいて、条件分岐が成立するかどうかを判定して、分岐予測を実行することができる。
　また、前記分岐予測装置において、前記分岐結果記録部は、分岐命令の分岐先それぞれについて、分岐した頻度を示す頻度情報を対応付けた分岐結果エントリを前記分岐結果記憶部に記録し、前記分岐予測部は、検索された分岐結果エントリが複数ある場合に、最も分岐した頻度が高い分岐結果エントリの分岐先アドレスを予測結果とすることとしてもよい。
　また、前記分岐予測装置において、前記分岐結果記録部は、分岐命令が実行された場合に、当該分岐命令の分岐先アドレスと、当該分岐命令が実行されたときの引数スタックの先頭値とが一致する分岐結果エントリについて、当該分岐命令が実際に実行されて分岐した分岐先を有するものの頻度情報を１加算し、それ以外の当該分岐命令の分岐先アドレスと、当該分岐命令が実行されたときの引数スタックの先頭値とが一致するものの実際に分岐した分岐先が異なる分岐結果エントリについて、その頻度情報を１減算することとしてもよい。
　これにより、分岐結果エントリは、各分岐エントリが実行された頻度を特定するための情報が対応付けられており、実行される分岐命令のアドレスと、引数スタックの先頭値とに対応する分岐結果エントリが複数あった場合に、それらの分岐結果エントリの中で最も実行頻度の高い分岐結果エントリを分岐先として予測することができる。これにより、分岐予測の確度を高めることができる。
　また、前記分岐予測装置において、前記命令実行部は、前記引数を格納するための複数のレジスタを備え、
　前記引数スタックは、前記複数のレジスタのうちの予め定められた特定のレジスタが格納している値を取得して格納することとしてもよい。
　これにより、命令実行部の予め定められたレジスタに格納された値を引数として引数スタックに渡すことができるので、これを前提とした装置作りが容易となる。
　また、本発明は、分岐命令を含む関数を示すソースプログラムをコンピュータが実行可能な実行形式の命令コード列に変更するコンパイラであって、前記コンピュータは、前記分岐命令の分岐先を予測するための情報として、前記関数の引数を格納する引数スタックを備え、前記コンパイラは、前記関数の呼び出しを実行する際に、当該関数の引数のうち、前記分岐命令に関連する引数を、前記引数スタックに格納させるための命令コードを生成することとしてもよい。
　また、本発明は、分岐命令を含む関数を示すソースプログラムをコンピュータが実行可能な実行形式の命令コード列に変更するためのコンパイル方法であって、前記コンピュータは、前記分岐命令の分岐先を予測するための情報として、前記関数の引数を格納する引数スタックを備え、前記コンパイル方法は、前記関数の呼び出しを実行する際に、当該関数の引数のうち、前記分岐命令に関連する引数を、前記引数スタックに格納させるための命令コードを生成する格納コード生成ステップを含むこととしてもよい。
　これにより、引数スタックに渡される引数を、関数の呼び出し時に必ず特定のレジスタに格納するようにコンピュータを制御することができるので、関数内の分岐命令の分岐先を決定する引数を確実に引数スタックに格納することを保障することができる。
　本発明に係る分岐予測装置は、プログラムの実行性能の向上に寄与し、プロセッサの処理速度の向上を促すものとして有用である。よって、プロセッサを用いるものであれば、幅広い分野において有効である。例えば、大型計算機や、パーソナルコンピュータのような形態のみならず、各種の家電機器、携帯電話機のような通信機器、産業機器、制御機器などでも利用可能である。
１００、３００　情報処理装置
１１０、１２２　命令実行部
１１１　関数呼び出し通知部
１１２　関数リターン通知部
１１３、１２３　引数スタック
１１４　分岐命令通知部
１１５　分岐結果記録部
１１６　分岐結果バッファ
１１７　分岐予測部
１１８　命令フェッチ部
１２０　レジスタ群
１２１　引数番号通知部
２００　記憶装置
１０００、１１００　分岐予測機構

Claims (10)

  1. 　命令を実行する命令実行部と、
    　前記命令実行部による関数呼び出し命令の実行を通知する関数呼び出し通知部と、
    　前記関数呼び出し通知部により関数呼び出し命令の実行が通知されたときに、当該関数呼び出し命令の少なくとも一つの引数を格納する引数スタックと、
    　前記命令実行部により前記関数呼び出し命令により呼び出される関数に含まれる分岐命令が実行されることを通知する分岐命令通知部と、
    　分岐命令の位置するアドレスと、当該分岐命令が実行されたときの引数スタックの先頭値と、分岐先のアドレスを示す分岐結果とを対応付けた分岐結果エントリを記憶する分岐結果記憶部と、
    　前記分岐命令通知部が分岐命令が実行されることを通知した場合に、前記分岐結果記憶部に、実行される当該分岐命令のアドレスと前記引数スタックに格納されている引数に一致する分岐結果エントリが記録されているかどうかを検索し、あった場合に、当該分岐結果エントリの分岐結果を当該分岐命令による分岐の予測結果とする分岐予測部と、
    　前記分岐予測部の予測した予測結果に基づき命令をフェッチする命令フェッチ部と、
    　分岐命令の実行完了後に実行された分岐命令の位置するアドレスと、当該分岐命令の実行により分岐した分岐先のアドレスを示す分岐結果と、当該分岐命令が実行されたときの前記引数スタックの先頭値とを対応付けて、分岐結果エントリとして前記分岐結果記憶部に記録する分岐結果記録部と、
    　を備えることを特徴とする分岐予測装置。
  2. 　前記分岐予測装置は、更に、
    　前記命令実行部による関数リターン命令の実行を通知する関数リターン通知部を備え、
    　前記引数スタックは、前記関数リターン通知部から関数リターン命令の実行が通知されたときに、当該関数リターン命令に対応する関数の引数を削除する
    　ことを特徴とする請求項１記載の分岐予測装置。
  3. 　前記分岐命令は条件付分岐命令であり、
    　前記分岐結果記録部は、更に、条件付分岐命令が実行されたか否かを示す情報が対応付けられた分岐結果エントリを記録する
    　ことを特徴とする請求項２記載の分岐予測装置。
  4. 　前記分岐結果記録部は、分岐命令の分岐先それぞれについて、分岐した頻度を示す頻度情報を対応付けた分岐結果エントリを前記分岐結果記憶部に記録し、
    　前記分岐予測部は、検索された分岐結果エントリが複数ある場合に、最も分岐した頻度が高い分岐結果エントリの分岐先アドレスを予測結果とする
    　ことを特徴とする請求項２記載の分岐予測装置。
  5. 　前記分岐結果記録部は、分岐命令が実行された場合に、当該分岐命令の分岐先アドレスと、当該分岐命令が実行されたときの引数スタックの先頭値とが一致する分岐結果エントリについて、当該分岐命令が実際に実行されて分岐した分岐先を有するものの頻度情報を１加算し、それ以外の当該分岐命令の分岐先アドレスと、当該分岐命令が実行されたときの引数スタックの先頭値とが一致するものの実際に分岐した分岐先が異なる分岐結果エントリについて、その頻度情報を１減算する
    　ことを特徴とする請求項４記載の分岐予測装置。
  6. 　前記命令実行部は、前記引数を格納するための複数のレジスタを備え、
    　前記引数スタックは、前記複数のレジスタのうちの予め定められた特定のレジスタが格納している値を取得して格納する
    　ことを特徴とする請求項２記載の分岐予測装置。
  7. 　情報処理装置が関数中に含まれる分岐命令の分岐先を予測する分岐予測方法であって、
    　関数呼び出し命令の実行を通知する関数呼び出し通知ステップと、
    　前記関数呼び出し通知ステップにより関数呼び出し命令の実行が通知されたときに、当該関数呼び出し命令の少なくとも一つの引数を格納する引数スタックに格納する格納ステップと、
    　前記関数呼び出し命令により呼び出される関数に含まれる分岐命令が実行されることを通知する分岐命令通知ステップと、
    　前記分岐命令通知ステップにより分岐命令が実行されることを通知された場合に、分岐命令の位置するアドレスと、当該分岐命令が実行されたときの引数スタックの先頭値と、分岐先のアドレスを示す分岐結果とを対応付けた分岐結果エントリを記憶する前記コンピュータに接続された分岐結果記憶媒体から、実行される当該分岐命令のアドレスと前記引数スタックに格納されている引数に一致する分岐結果エントリが記録されているかどうかを検索し、あった場合に、当該分岐結果エントリの分岐結果を当該分岐命令による分岐の予測結果とする分岐予測ステップと、
    　前記分岐予測ステップにおいて予測した予測結果に基づき命令をフェッチする命令フェッチステップと、
    　分岐命令の実行完了後に実行された分岐命令の位置するアドレスと、当該分岐命令の実行により分岐した分岐先のアドレスを示す分岐結果と、当該分岐命令が実行されたときの前記引数スタックの先頭値とを対応付けて、分岐結果エントリとして前記分岐結果記憶部に記録する分岐結果記録ステップとを含む
    　ことを特徴とする分岐予測方法。
  8. 　分岐命令を含む関数を示すソースプログラムをコンピュータが実行可能な実行形式の命令コード列に変更するコンパイラであって、
    　前記コンピュータは、前記分岐命令の分岐先を予測するための情報として、前記関数の引数を格納する引数スタックを備え、
    　前記コンパイラは、前記関数の呼び出しを実行する際に、当該関数の引数のうち、前記分岐命令に関連する引数を、前記引数スタックに格納させるための命令コードを生成する
    　ことを特徴とするコンパイラ。
  9. 　分岐命令を含む関数を示すソースプログラムをコンピュータが実行可能な実行形式の命令コード列に変更するためのコンパイル方法であって、
    　前記コンピュータは、前記分岐命令の分岐先を予測するための情報として、前記関数の引数を格納する引数スタックを備え、
    　前記コンパイル方法は、前記関数の呼び出しを実行する際に、当該関数の引数のうち、前記分岐命令に関連する引数を、前記引数スタックに格納させるための命令コードを生成する格納コード生成ステップを含む
    　ことを特徴とするコンパイル方法。
  10. 　プログラムを実行する際の分岐命令の分岐先を予測する分岐予測処理をコンピュータが実行するための分岐予測プログラムを記録したコンピュータ読み取り可能な分岐予測プログラム記録媒体であって、
    　前記分岐予測処理は、
    　関数呼び出し命令の実行を通知する関数呼び出し通知ステップと、
    　前記関数呼び出し通知ステップにより関数呼び出し命令の実行が通知されたときに、当該関数呼び出し命令の少なくとも一つの引数を格納する引数スタックに格納する格納ステップと、
    　前記関数呼び出し命令により呼び出される関数に含まれる分岐命令が実行されることを通知する分岐命令通知ステップと、
    　前記分岐命令通知ステップにより分岐命令が実行されることを通知された場合に、分岐命令の位置するアドレスと、当該分岐命令が実行されたときの引数スタックの先頭値と、分岐先のアドレスを示す分岐結果とを対応付けた分岐結果エントリを記憶する前記コンピュータに接続された分岐結果記憶媒体から、実行される当該分岐命令のアドレスと前記引数スタックに格納されている引数に一致する分岐結果エントリが記録されているかどうかを検索し、あった場合に、当該分岐結果エントリの分岐結果を当該分岐命令による分岐の予測結果とする分岐予測ステップと、
    　前記予測ステップにおいて予測した予測結果に基づき命令をフェッチする命令フェッチステップと、
    　分岐命令の実行完了後に実行された分岐命令の位置するアドレスと、当該分岐命令の実行により分岐した分岐先のアドレスを示す分岐結果と、当該分岐命令が実行されたときの前記引数スタックの先頭値とを対応付けて、分岐結果エントリとして前記分岐結果記憶部に記録する分岐結果記録ステップとを含む
    　ことを特徴とする分岐予測プログラム記録媒体。
PCT/JP2010/003357 2009-05-19 2010-05-19 分岐予測装置、その分岐予測方法、コンパイラ、そのコンパイル方法及び分岐予測プログラム記録媒体 WO2010134330A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
CN2010800021370A CN102099781A (zh) 2009-05-19 2010-05-19 分支预测装置、其分支预测方法、编译器、其编译方法及分支预测程序记录介质
JP2011514333A JP5347023B2 (ja) 2009-05-19 2010-05-19 分岐予測装置、その分岐予測方法、コンパイラ、そのコンパイル方法及び分岐予測プログラム記録媒体
US13/001,852 US8694760B2 (en) 2009-05-19 2010-05-19 Branch prediction using a leading value of a call stack storing function arguments

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2009-120583 2009-05-19
JP2009120583 2009-05-19

Publications (1)

Publication Number Publication Date
WO2010134330A1 true WO2010134330A1 (ja) 2010-11-25

Family

ID=43126023

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2010/003357 WO2010134330A1 (ja) 2009-05-19 2010-05-19 分岐予測装置、その分岐予測方法、コンパイラ、そのコンパイル方法及び分岐予測プログラム記録媒体

Country Status (4)

Country Link
US (1) US8694760B2 (ja)
JP (1) JP5347023B2 (ja)
CN (1) CN102099781A (ja)
WO (1) WO2010134330A1 (ja)

Families Citing this family (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9652245B2 (en) 2012-07-16 2017-05-16 Lenovo Enterprise Solutions (Singapore) Pte. Ltd. Branch prediction for indirect jumps by hashing current and previous branch instruction addresses
CN103984525B (zh) * 2013-02-08 2017-10-20 上海芯豪微电子有限公司 指令处理系统及方法
US9639368B2 (en) * 2014-06-13 2017-05-02 International Business Machines Corporation Branch prediction based on correlating events
US20170090927A1 (en) * 2015-09-30 2017-03-30 Paul Caprioli Control transfer instructions indicating intent to call or return
CN105718241B (zh) * 2016-01-18 2018-03-13 北京时代民芯科技有限公司 一种基于sparc v8体系结构的分类式混合分支预测系统
CN106648636B (zh) * 2016-12-08 2020-01-03 北京航空航天大学 一种基于图挖掘的软件函数变更预测系统及方法
JP2018200545A (ja) * 2017-05-26 2018-12-20 ルネサスエレクトロニクス株式会社 プロセッサ装置
EP3640796A4 (en) * 2017-06-02 2020-06-03 Mitsubishi Electric Corporation PROGRAM CODE GENERATION DEVICE AND TWO-DIMENSIONAL CODE GENERATION PROGRAM
JP6720993B2 (ja) * 2018-03-07 2020-07-08 オムロン株式会社 サポート装置およびサポートプログラム
CN108897699A (zh) * 2018-07-03 2018-11-27 中国人民解放军国防科技大学 一种基于函数调用栈的数据预取方法和装置
CN109240815B (zh) * 2018-08-24 2021-07-23 珠海格力电器股份有限公司 一种共享堆栈的多任务运行方法、装置及设备
CN111176729A (zh) * 2018-11-13 2020-05-19 深圳市中兴微电子技术有限公司 一种信息处理方法、装置及计算机可读存储介质

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004533695A (ja) * 2001-06-29 2004-11-04 コーニンクレッカ　フィリップス　エレクトロニクス　エヌ　ヴィ 分岐目標を予測する方法、プロセッサ、及びコンパイラ

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4763245A (en) * 1985-10-30 1988-08-09 International Business Machines Corporation Branch prediction mechanism in which a branch history table is updated using an operand sensitive branch table
US5333283A (en) * 1991-10-29 1994-07-26 International Business Machines Corporation Case block table for predicting the outcome of blocks of conditional branches having a common operand
JP2000132390A (ja) * 1998-10-23 2000-05-12 Toshiba Corp プロセッサ及び分岐予測器
US20030131345A1 (en) * 2002-01-09 2003-07-10 Chris Wilkerson Employing value prediction with the compiler
US20070088937A1 (en) * 2005-10-13 2007-04-19 International Business Machines Corporation Computer-implemented method and processing unit for predicting branch target addresses
US7444501B2 (en) * 2006-11-28 2008-10-28 Qualcomm Incorporated Methods and apparatus for recognizing a subroutine call
US7870371B2 (en) * 2007-12-17 2011-01-11 Microsoft Corporation Target-frequency based indirect jump prediction for high-performance processors

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2004533695A (ja) * 2001-06-29 2004-11-04 コーニンクレッカ　フィリップス　エレクトロニクス　エヌ　ヴィ 分岐目標を予測する方法、プロセッサ、及びコンパイラ

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
AMIR ROTH ET AL.: "Improving virtual function call target prediction via dependence-based pre-computation", PROCEEDINGS OF THE 13TH INTERNATIONAL CONFERENCE ON SUPERCOMPUTING, ACM, vol. 1999, 1999, pages 356 - 364 *
TAKASHI TOYOSHIMA ET AL.: "Register Indirect Jump Target Forwarding", SYMPOSIUM ON ADVANCED COMPUTING SYSTEMS AND INFRASTRUCTURES SACSIS2006 RONBUNSHU, vol. 2006, no. 5, 22 May 2006 (2006-05-22) *

Also Published As

Publication number Publication date
US20110119472A1 (en) 2011-05-19
JP5347023B2 (ja) 2013-11-20
US8694760B2 (en) 2014-04-08
CN102099781A (zh) 2011-06-15
JPWO2010134330A1 (ja) 2012-11-08

Similar Documents

Publication Publication Date Title
WO2010134330A1 (ja) 分岐予測装置、その分岐予測方法、コンパイラ、そのコンパイル方法及び分岐予測プログラム記録媒体
US11216258B2 (en) Direct function call substitution using preprocessor
US9134973B2 (en) Dynamic compiling and loading at runtime
US8612944B2 (en) Code evaluation for in-order processing
US20030140338A1 (en) Method, apparatus and article for generation of debugging information
US7299462B2 (en) Relocation format for linking
US20080091923A1 (en) Register-based instruction optimization for facilitating efficient emulation of an instruction stream
US9626170B2 (en) Method and computer program product for disassembling a mixed machine code
JP5579694B2 (ja) 復帰スタックを管理する方法および装置
US6684394B1 (en) Relocation format for linking with relocation instructions containing operations for combining section data
WO2013079006A1 (en) Systems and Methods for Customizing Optimization/Transformation/ Processing Strategies
US20090187884A1 (en) Refining tail call optimizations at link-time
US20160259643A1 (en) Confidence-driven selective predication of processor instructions
US11379195B2 (en) Memory ordering annotations for binary emulation
CN116266119A (zh) 生成依赖于使用的代码嵌入的方法、装置和制品
US6704928B1 (en) Relocation format for linking
GB2358491A (en) A relocation format for linking
CN114253554A (zh) 一种代码处理方法、装置及存储介质
US6802060B1 (en) Linker using relocation sequences
CN118069142B (zh) 编译优化方法、装置、电子设备及存储介质
JP4719415B2 (ja) 情報処理システム及びコード生成方法
US11567744B2 (en) Removing branching paths from a computer program
US9600284B2 (en) Computer program instruction analysis
JP2000163266A (ja) 命令実行方式
US7155709B2 (en) Displaying user readable information during linking

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 201080002137.0

Country of ref document: CN

WWE Wipo information: entry into national phase

Ref document number: 13001852

Country of ref document: US

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 10777568

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2011514333

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 10777568

Country of ref document: EP

Kind code of ref document: A1