Patent Publication Number: US-7222227-B2

Title: Control device for speculative instruction execution with a branch instruction insertion, and method for same

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application is based upon and claims the benefit of priority from the prior Japanese patent application No. 2002-307591, filed on Oct. 22, 2002; the entire contents of which are incorporated herein by reference. 
   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to a speculative instruction execution control device and a method for the same. In particular, in a processor that has a prediction unit for speculatively executing computer instructions in order to increase processing speed, it relates to technology for easily implementing with a simple hardware configuration value prediction verification control for speculative instruction execution, and a recovery control when a prediction error occurs. 
   2. Description of Related Art 
   Speculative instruction execution is used as a method for increasing computer speed, namely processor speed. Speculative execution means that an instruction is speculatively executed in conformity with a prediction made by a prediction mechanism in a computer. Various methods have been suggested. Generally, such speculative execution is utilized in a pipelined processor. 
   A first example of this speculative execution includes branch prediction, that is, prediction of which instruction is the branch destination instruction of a branch instruction. With this branch instruction, instruction to be subsequently executed (i.e., fetched) by a processor, which is determined as a result of branch instruction execution, is predicted in order for the subsequent instruction to be fetched without waiting for branch instruction execution. 
   When branch prediction is not performed, a processor cannot fetch the subsequent instruction until the execution result of this branch instruction is obtained after fetching the branch instruction. Accordingly, in a pipelined processor, a bubble, namely a cycle in which no processing is performed, occurs between the branch instruction and instruction subsequent to this branch instruction. This occurrence of a bubble becomes a factor in the drop in processing speed of a processor. 
   Meanwhile, when performing branch prediction, since subsequent instruction is fetched without waiting for branch instruction execution, bubbles are reduced and this allows an increase in the processing speed of the processor if branch prediction is correct. However, if branch prediction is incorrect (i.e., prediction error) when branch prediction is performed, since speculatively fetched instructions are instructions not normally executed, it is necessary to disable such instructions and re-fetch correct instructions. The number of times (cycles) required to disable these instructions and re-execute correct instructions when a prediction error occurs are referred to as the prediction error penalty. 
   The overhead (the drop in processing speed of the processor) due to this prediction error penalty often exceeds the overhead in the case where branch prediction is not performed. This is because extra cycles may be needed to disable speculatively executed instructions. In recent years, processors have aimed to reduce this overhead due to such prediction error and increase processing speed by improving the accuracy of branch prediction. 
   A second example of speculative execution includes load value prediction, that is, prediction of a load value, which is the data value to be loaded into a processor in conformity with a load instruction. One of the problems in increasing the speed of a processor is that, in comparison with instruction for performing an arithmetic operation or logical operation, the delay time of an instruction for performing data access such as a load instruction or store instruction is longer. In recent years, while reduction in the processing time required to access data in memory still lags, progress has been made in shortening the processing time for arithmetic operations and logical operations. As a result, the difference between the two has become wider. It should be noted that memory herein may be a main memory located external to a processor, or in a processor including cache memory (also simply referred to as a cache), it may be cache memory. 
   For example, assuming that an arithmetic operation instruction that uses data loaded as a result of a load instruction is included in a program, this operation cannot be executed until the value to be loaded is obtained as a result of the load instruction since this subsequent arithmetic operation instruction has dependency on this load instruction. Accordingly, as the time required for load instruction execution increases, the lag of the instruction execution having dependency on this load instruction increases, and as a result, the processing speed of the processor drops. 
   In load value prediction, the data value to be loaded with a load instruction is predicted, and this predicted data value is used for instructions subsequent to this load instruction (a. load value prediction). It is possible to speculatively execute subsequent instructions having dependency on this load instruction while executing the load instruction using the predicted data value (b. speculative execution of subsequent instructions). 
   In the case where the load value prediction is correct, that is, in the case where the predicted load value is equal to the actual execution result of the load instruction, subsequent instructions speculatively executed may be completed at the point in time where load instruction is completed. Accordingly, in comparison with the case where load value prediction is not performed, the processing speed of the processor may increase for the number of cycles required to execute subsequent instructions that were speculatively executed. On the other hand, as with other prediction mechanisms for, for example, branch prediction, in the case where a load value prediction is incorrect, it is necessary to disable the speculatively executed subsequent instruction and re-execute that instruction, which results in a prediction error penalty occurring (c. prediction verification, d. disabling and re-execution of instruction). 
   Various algorithms have been suggested as the prediction algorithm for performing load value prediction. Since a value to be loaded from memory by the load instruction may be known only upon executing a program, predicting a value to be loaded when compiling a program, or static prediction, is difficult. Accordingly, a load value is predicted wholly by using data during program execution (dynamic prediction). This load value prediction is based on the knowledge that the same load instruction, in other words a load instruction in the same address in the program, has a statistically high probability of loading the same value. In other words, since the same load instruction has a high probability of reloading a value that was loaded in the past, there may be a high probability of obtaining the correct prediction value. 
   Next, an example of a conventional processor configuration for executing load value prediction is described. 
     FIG. 1  is an example of a processor configuration having a load value prediction unit. 
   Main memory  121  is a memory located external to a processor  110 , and stores instructions (programs) and data. 
   An instruction fetch unit (IFU)  111  includes a program counter (PC)  111   b,  and fetches instruction (D 11 ) (instruction fetch) to the processor  110  from an address in main memory  121  specified by value of the program counter  111   b.  The fetched instruction is temporarily held in an instruction window buffer (IWB)  112 . 
   The instruction window buffer  112  may hold a plurality of instructions. The instruction window buffer  112  issues instructions to appropriate execution units  114   a,    114   b,  or a load/ store unit  113 . 
   The load/store unit (LSU)  113  and execution units (EX)  114   a  and  114   b  are units for executing the respective calculations thereof. 
   The load/store unit  113  executes load instructions and store instructions. The execution units  114   a  and  114   b  perform operations other than load instructions and store instructions. For example, integer operations, logical operations, and floating point operations are performed, but they are not limited to these operations. 
   A register file (RF)  117  is a group of registers included in the processor. The register file  117  transmits necessary operands (operation values) to the load/store unit  113  and execution units  114   a  and  114   b , respectively, and writes the operation results from those units into the internal register. 
   A commit unit (CMT)  118  controls the timing when the operation result is written in the register file  117  (or memory in the case of store instruction) based on a comparison result input from a comparator  120  (D 14 ). The program execution results must be written in the register file  117  or memory in accordance with the execution sequence of the program. This is because, when writing a value into memory in the same address, results change depending on the order in which written. This is also because, even if the final result is the same, intermediate results conforming to the program execution order become necessary when an exception occurs. 
   A load value prediction unit (LPU)  116  predicts the value to be loaded by a load instruction, and transmits the predicted value (D 12 ) to a value prediction buffer  119  and register file  117 . There are various algorithms suggested for the load value prediction algorithm, however, since the present invention does not suppose a specific load value prediction algorithm, and may be applied regardless of the load value prediction algorithm, specific mentioned is not made herein. To give an example of a load value prediction algorithm, there is a method where a value that has been loaded in conformity with a load instruction is stored in the address (program counter value) of that load instruction, and then, when the next load instruction is fetched, the value previously loaded and stored is used as a prediction value. 
   A value prediction buffer (VPB)  119  is a buffer that stores a load prediction value input from the load value prediction unit  116 . The predicted value stored in this value prediction buffer  119  is used for comparison by a comparator  120  with a value (D 13 ) actually loaded later through load instruction execution. 
   The comparator  120  compares a load prediction value predicted by the load value prediction unit  116  with a value actually loaded by the load instruction. 
   Next, operations of instruction execution and load value prediction in the processor in  FIG. 1  are described. 
   (1) Operation When Load Value Prediction is not Performed 
   1. The instruction fetch unit  111  fetches an instruction from the main memory  121  in conformity with the program counter  111   b.    
   2. The fetched instruction is temporarily held in the instruction window buffer  112 . 
   3. The instruction window buffer  112  issues an issuable instruction to an execution unit  114   a,    114   b,  or load/store unit  113  appropriate for executing the instruction. 
   4. The register file  117  issues the operands necessary for instruction execution to the load/store unit  113  or execution unit  114   a  or  114   b.    
   5. The load/store unit  113 , or execution unit  114   a  or  114   b  executes instruction. In other words, when the instruction is a load instruction, the load/store unit  113  loads data from the main memory  121 . When the instruction is store instruction, the load/store unit  113  prepares for writing data in the main memory  121 . In the case of other instructions, the execution units  114   a  and  114   b  execute calculation. 
   6. The commit unit  118  controls the timing of writing in the register file  117  or main memory  121 . In other words, when the instruction is a load instruction, the loaded data is written in a register of the register file  117 . When the instruction is a store instruction, data is written in the main memory  12 . When the instruction is a branch instruction, the program counter  111   b  in the instruction fetch unit  111  is updated in conformity with the result of the branch instruction. In the case of other instructions, the operation result is written in the register of the register file  117 . 
   It is assumed herein that each processing  1  through  6  mentioned above is executed for every processor cycle. Generally, there are many pipelined processors having pipelined structure that execute processing for every cycle. 
   (2) Operation When Load Value Prediction is Performed 
   1. The instruction fetch unit  111  fetches instruction from the main memory  121  in conformity with the program counter  111   b.    
   2. The load value prediction unit  116  determines whether or not the fetched instruction is a load instruction that is a subject to prediction. If the fetched instruction is a load instruction that is the subject to prediction, a load prediction value is written in the register in which the result of the load instruction is to be written. 
   3. The fetched instruction is temporarily held in the instruction window buffer  112 . 
   4. The instruction window buffer  112  issues a load instruction to the load/store unit  113 . 
   5. The register file  117  supplies operands required for load instruction execution to the load/store unit  113 . 
   6. The instruction window buffer  112  issues an instruction subsequent to the load instruction. 
   7. The comparator  120  compares the loaded value obtained through the load instruction execution with the predicted value after the results of the load instruction are obtained. 
   8. When a prediction verification result is obtained from the comparator  120 :
         In the case where the prediction is correct, the load instruction and subsequent instruction that was speculatively executed become committable. The commit unit  118  writes the execution results of such instructions in the register or main memory  121  and commits (completes) the instructions with the appropriate timing.   Meanwhile, in the case where the prediction is incorrect, a load value is written in the register in which the execution result of the load instruction is to be written and the load instruction is committed (completed). However, all subsequent instructions are disabled and these instructions are fetched and executed again.       

   It should be noted that the above-mentioned processing that disables an instruction and starts over beginning with fetching an instruction is referred to as a “flush”. In addition, processing that becomes necessary when prediction is incorrect is referred to as “recovery”. 
     FIG. 2  is a flowchart illustrating recovery processing that becomes necessary when this load value prediction is incorrect. 
   Here, it is assumed that the group of instructions in  FIG. 3  is given as specific instruction sequence. It should be noted that S 1 , S 2 , S 3 , and S 10  in  FIG. 3  indicate respective register names (register numbers). 
   To begin with, the instruction fetch unit  111  fetches instructions in the order of lw (load word), addi, and add instructions (step S 21 ), and the instruction window buffer  112  holds instructions in the same order. Here, in the case where the fetched lw instruction is a target for prediction (step S 22 Y), the load value prediction unit  116  writes the load prediction value in the register S 1  (register in the register file  117  corresponding to the S 1  in the instruction) (step S 23 ). 
   The instruction window buffer  112  determines whether the instruction is issuable. Here, issuable means the status where the necessary operand is available, and an execution unit of destination to which instruction is to be issued is available or other instructions are not using the execution unit. It should be noted that the instruction window buffer  112  herein is regarded as employing the in-order issuance mechanism. This in-order issuance means that instruction is issued in the fetched order. Accordingly, when the first fetched instruction of instructions held in the instruction window buffer  112  becomes issuable, the instruction window buffer  112  herein issues that instruction. The issued instruction is removed from the instruction window buffer  112 . This first fetched instruction of the instructions in the instruction window buffer  112  is given as that which is to be controlled to be always located at the head of the instruction window buffer  112 . 
   In the example of  FIG. 3 , if a lw instruction is located at the head of the instruction window buffer  112 , a value in the register S 10  is available, and the load/store unit  113  is available, then the lw instruction is issued to the load/store unit  113  (step S 24 ). The load/store unit  113  loads the value to be loaded from the main memory  121 . 
   While the load/store unit  113  is executing the load instruction, an addi instruction, which is an instruction subsequent to the load instruction, is issued to the execution unit  114   a  or  114   b.  This is because it is not necessary to wait for the load instruction execution results since this addi instruction may use the load prediction value as a value of the register S 1 . Similarly, further subsequent add instruction is issued to the execution unit  114   a  or  114   b.  It should be noted that if load value prediction is not performed, subsequent addi instruction and add instruction are not issued to the execution unit  114   a  or  114   b  from the instruction window buffer  112  until the lw instruction execution results are obtained. 
   When the load/store unit  113  obtains the load value that is the load instruction execution result (step S 25 Y), the comparator  120  compares the previously predicted load value held in the value prediction buffer  119  with the load value that is the actual load instruction execution result, and notifies the commit unit  118  of the comparison result (step S 27 ). 
   When the two match, that is, when load value prediction is correct (step S 27 Y), the load instruction is committed (completed) (step S 28 ), the subsequent addi instruction and add instructions are committed (completed) as the respective operation results are obtained (step S 29 ), and the operation results are written in the register files S 2  and S 3 . 
   Meanwhile, when the two do not match or when load value prediction is incorrect (step S 27 N), the value loaded through actual load instruction execution is overwritten in the register corresponding to S 1  in the register file  117 , the load instruction is committed (step S 30 ), and the addi instruction and add instruction subsequent to the load instruction are disabled (step S 31 ). The instruction fetch unit  111  again starts a fetch from an addi instruction (step S 32 ). 
   Mikko H. Lipasti, et al., “Exceeding the Dataflow Limit via Value Prediction” (IEEE, 1072-4451/96, 1996, p. 226-237) is incorporated herein by reference. 
   However, conventional instruction prediction for, for example, the load value and the like, has the following problems that need to be solved. 
   Firstly, hardware costs increase because of controls for prediction verification and prediction error recovery operation. In other words, during load value prediction, whether the predicted value is correct is verified after the value actually loaded through load instruction execution is obtained. If the value prediction is incorrect, it is necessary to re-execute, using the correct values, subsequent instructions that have been speculatively executed. Specialized hardware, such as the value prediction buffer  119  and comparator  120  shown in  FIG. 1 , becomes necessary for this recovery operation. 
   If an in-order issuing processor such as that described in  FIG. 1  and  FIG. 2  is used, since the order in which the load value prediction unit  116  predicts the load instruction value matches the order with which the load/store unit  113  executes the load instruction, it is sufficient for the value prediction buffer  119  to be a buffer having a first-in first-out (FIFO) configuration. Nevertheless, with an out-of-order issuing processor, since the order in which the load value prediction unit  116  predicts the load instruction value is different from the order with which the load/store unit  113  executes load instruction, there is no option but to use hardware having a more complicated configuration, for example, a content-addressable memory (CAM) configuration as this value prediction buffer. 
   Secondly, in order to implement prediction verification and recovery operation for a prediction error, items requiring specialized control become necessary, including for example, determination of whether or not a prediction error has occurred, or which instruction must be re-executed first when a prediction error has occurred. As the items requiring specialized control increase, the control unit becomes more complicated, and mounting of this control unit and verification operation becomes more difficult. In particular, since recovery processing affects many function blocks, it has a strong tendency to become the critical path during design, and if the control unit that performs recovery processing is complicated, it alone becomes an obstacle to satisfying the timing restrictions of the processor. 
   SUMMARY OF THE INVENTION 
   According to an aspect of the present invention, there is provided a control device for speculative instruction execution, comprising: an instruction fetch unit configured to fetch an instruction to be executed by a processor; a value prediction unit configured to predict a value obtained as an execution result of a target instruction for prediction in the case where instruction fetched by the instruction fetch unit is the target instruction for prediction; a branch instruction insertion unit configured to dynamically insert, based on a signal transmitted from the value prediction unit, a branch instruction subsequent to the target instruction for prediction in a group of instructions comprising a target instruction for prediction for which a value is predicted by the value prediction unit and an instruction subsequent to the target instruction for prediction; an instruction issuing unit configured to hold a fetched instruction and speculatively issue an instruction subsequent to the target instruction for prediction to an execution unit without waiting for an execution result for the target instruction for prediction using the value predicted by the value prediction unit; an execution unit configured to execute an instruction issued from the instruction issuing unit; a branch prediction control unit configured to prediet a branch destination for a branch instruction and perform verification of a branch prediction; and a commit unit configured to commit each instruction in a group of instructions executed by the execution unit, and invalidate and re-execute a speculatively executed instruction when the predicted value and execution result do not match; wherein the branch prediction control unit verifies a value prediction by comparing the predicted value predicted by the value prediction unit and the execution result of the target instruction for prediction executed by the execution unit upon execution of the inserted branch instruction, and transmits to the commit unit a signal that indicates that a predicted value and execution result do not match when the predicted value and the execution result do not match. 
   According to another aspect of the present invention, there is provided a method for controlling speculative instruction execution, comprising: fetching an instruction to be executed by a processor; predicting a value to be obtained as an execution result of the instruction using a value prediction unit when the fetched instruction is a target instruction for prediction; dynamically inserting, based on a signal transmitted from the value prediction unit, a branch instruction subsequent to the target instruction for prediction into a group of instructions comprising the target instruction for prediction for which a value is predicted by the value prediction unit and an instruction subsequent to the target instruction for prediction; holding fetched instructions and speculatively issuing an instruction subsequent to the target instruction for prediction to an execution unit without waiting for the execution result of the target instruction for prediction using the value predicted by the value prediction unit; executing instructions issued from the instruction issuing unit; verifying value prediction by comparing the predicted value predicted by the value prediction unit with the execution result of the target instruction for prediction executed by the execution unit upon execution of the inserted branch instruction; and committing each instruction in a group of instructions executed by the execution unit, and invalidating and re-executing speculatively executed instructions when the predicted value and execution result do not match. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a block diagram illustrating an exemplary configuration of a processor having a load value prediction unit; 
       FIG. 2  is a flowchart illustrating recovery processing that becomes necessary when load value prediction is incorrect; 
       FIG. 3  is a diagram illustrating an example of instruction sequence for describing recovery processing in  FIG. 2 ; 
       FIG. 4  is a block diagram illustrating an exemplary configuration of a processor having a speculative instruction execution control unit according to a first embodiment of the present invention; 
       FIG. 5  is a diagram illustrating an example of instruction sequence for describing operation of a register renaming unit in the first embodiment; 
       FIG. 6  is a diagram illustrating instruction sequence which is the instruction sequence shown in  FIG. 5  renamed by using the register renaming unit in the first embodiment; 
       FIG. 7  is a block diagram illustrating the internal configuration of the branch prediction unit  23  shown in  FIG. 4 ; 
       FIG. 8  is a flowchart illustrating an example of branch prediction control in the branch prediction unit  23  in  FIG. 7 ; 
       FIG. 9  is a flowchart for describing a series of operations after an instruction is fetched, including load value prediction, speculative instruction execution, prediction verification, and recovery when a prediction error occurs in the first embodiment; 
       FIG. 10  is a diagram illustrating the instruction sequence obtained through execution of register renaming processing and branch instruction insertion processing according to the first embodiment, which corresponds to the instruction sequence shown in  FIG. 3 ; 
       FIG. 11  is a diagram illustrating the instruction sequence obtained through execution of register renaming processing and branch instruction insertion processing according to a second embodiment, which corresponds to the instruction sequence shown in  FIG. 3 ; 
       FIG. 12  is a diagram illustrating the instruction sequence obtained through execution of register renaming processing and branch instruction insertion processing according to a fourth embodiment which corresponds to the instruction sequence shown in  FIG. 3 ; 
       FIG. 13  is a diagram illustrating an example of instruction sequence for describing processing in a fifth embodiment; 
       FIG. 14  is a diagram illustrating the instruction sequence obtained through execution of register renaming processing and branch instruction insertion processing according to a fifth embodiment which corresponds to the instruction sequence shown in  FIG. 13 ; 
       FIG. 15  is a flowchart illustrating recovery operation control when a load value prediction error occurs according to a sixth embodiment; 
       FIG. 16  is a block diagram illustrating an exemplary configuration of a processor having a conventional value prediction unit; 
       FIG. 17  is a block diagram illustrating an exemplary configuration of a processor having a value prediction unit according to an eighth embodiment; and 
       FIG. 18  is a block diagram illustrating an exemplary configuration of a processor having a load value prediction unit according to a ninth embodiment. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   A speculative instruction execution control device and a method for the same according to embodiments of the present invention is described forthwith in detail while referencing  FIG. 4  through  FIG. 18 . 
   First Embodiment 
   A first embodiment uses an existing register renaming unit (to be described later) and branch prediction unit realizes a control unit for prediction verification in speculative instruction execution and a flush and recovery when a prediction error occurs. It should be noted that in the first embodiment, a processor capable of out-of-order instruction issuing, and configured with a register renaming unit; a branch prediction unit; and a load instruction value prediction unit, is described as an example, however, the first embodiment is not limited to this configuration. 
     FIG. 4  illustrates an exemplary configuration of a processor having a speculative instruction execution control unit according to the first embodiment of the present invention. 
   As shown in  FIG. 4 , a processor having a speculative instruction execution control unit according to the first embodiment, is configured with an instruction fetch unit  11 , a program counter  11   b,  an instruction window buffer  12 , a load/store unit  13 , execution units  14   a  and  14   b,  a load value prediction unit  16 , a register file  17 , a commit unit  18 , a reorder buffer  18   a,  a register renaming unit  19 , an architecture register map  20 , a branch insertion unit  21 , and a branch prediction unit  23 . 
   A main memory  2  is a memory located external to the processor  1 , and stores instructions (programs) and data. 
   The instruction fetch unit (IFU)  11  includes a program counter (PC)  11   b,  and fetches instruction (D 1 ) (instruction fetch) to the processor  1  from an address in main memory  2  specified by a value of the program counter  11   b.  The fetched instruction is temporarily held in the instruction window buffer (IWB)  12 . 
   The instruction window buffer  12  may hold a plurality of instructions. The instruction window buffer  12  issues an instruction to the appropriate load/store unit  13 , or the execution unit  14   a  or  14   b.  In the first embodiment, this instruction window buffer  12  has an out-of-order issuance configuration where an instruction is dynamically scheduled and issued, however, it is not limited to this configuration. An instruction issuance mechanism carried out by the instruction window buffer  12  in the first embodiment is similar to the conventional in-order issuing instruction window buffer except in that an instruction is issued in an order different from the fetched order when the instruction becomes issuable. 
   Out-of-order issuance is a method for issuing reordered (scheduled) instruction to the execution unit by reordering the instruction execution order so that final completion of the execution becomes faster when the final result is the same even in the case where the instruction execution order is different from the order in the program (fetched order). For example, if an instruction at the head of the instruction window buffer  12  is not issuable but a subsequently fetched instruction is issuable, and the two instructions have no dependency, the out-of-order instruction window buffer  12  issues this issuable instruction first. 
   The load/store unit (LSU)  13  and execution units (EX)  14   a  and  14   b  are units that respectively execute calculations. There are many variations in the types and numbers of these execution units (execution blocks) depending on the processor, and the execution units are naturally not limited to those shown in  FIG. 4 . In the first embodiment, arbitrary execution blocks other than the load/store unit  13  relevant to the load instruction may be used. 
   The load/store unit  13  executes load instruction and store instruction, and transfers data among the processor  1  and main memory  2 . The execution units  14   a  and  14   b  perform operations other than load instruction and store instruction. For example, integer operation, logical operation, floating point operation, and branch condition determination are performed, but they are not limited to these operations. 
   The register file (RF)  17  is a physical group of registers referenced from the processor. The register file  17  transmits necessary operands (operation values) to the load/store unit  13 , and execution units  14   a  and  14   b  respectively, and writes the operation results by those units in the internal register. 
   The commit unit (CMT)  18  controls the timing of when the operation results are written in the register (or memory in the case of a store instruction) (D 6 ). The program execution results must be written in the register or memory in conformity with the execution order of the program. This is because, when writing a value into the same address in memory, results change depending on the order in which they are written. This is also because, even if the final result is the same, the intermediate results conforming to the program execution order become necessary when an exception occurs. 
   A load value prediction unit (LPU)  16  predicts the value to be loaded with a load instruction, and transmits this predicted value (D 4 ) to the register file  17 . There are various algorithms suggested for this load value prediction algorithm, however, since this embodiment does not assume a specific load value prediction algorithm, and may be applied regardless of the load value prediction algorithm, specific mention is not made herein. To give an example of a load value prediction algorithm, there is a method where a value that has been loaded in conformity with a load instruction is stored in the address (program counter value) of that load instruction, and then, when the next load instruction is fetched, the value previously loaded and stored is used as the prediction value. 
   The reorder buffer  18   a  reorders instructions executed out of order into the fetched order, namely “in order”, and performs control for terminating the instructions in the “in order” sequence. This reorder buffer  18   a  administers a group of instructions that are issued from the instruction window buffer  12  but not yet committed (completed), and reorders such instructions. 
   The register renaming unit  19  performs register renaming (to be described later). 
   The architecture register map  20  is a table of correspondence between physical registers and architecture registers to which software may refer. 
   In conjunction with the load value prediction unit  16 , the branch insertion unit (BIU)  21  inserts a branch instruction in the instruction window buffer  12  immediately after the load instruction for which a load value is to be predicted. 
   The branch prediction unit (BPU)  23  executes the branch prediction, verification of this branch prediction, and processing (branch error recovery) when the branch prediction is incorrect (prediction error). 
   Next, register renaming in the first embodiment is described. 
   Register renaming is a method for improving parallelism of instruction execution. A processor having this register renaming unit includes more physical registers than the architecture registers to which software may refer. The register renaming unit  19  in  FIG. 4  maps the architecture registers to the physical registers (mapping). This mapped status is stored in the architecture register map  20 . 
   The register renaming unit  19  contrives register mapping to hold the intermediate operation results in the proper register and reduce hazards contributed to the register number. In addition, with a processor performing speculative instruction execution, a speculatively executed result, or a result which has the possibility of being an incorrect value, is written in a physical register to which software cannot refer, and maps the physical register in which the result has been written in the architecture register to which software may refer when the speculative execution result is determined as being correct. Through this mapping, if the software accesses the architecture register, the physical register mapped to the architecture register is accessed. 
   The software (program) refers to only correct results of committed (completed) instruction. Accordingly, not only the register renaming unit  19  that performs mapping of registers, but also the commit unit  18  that controls instruction completion is involved in implementation of the register renaming function. Furthermore, with an out-of-order executing processor, the reorder buffer  18   a  that administers the order for committing (completing) instruction is also involved. 
   Register renaming is more specifically described with the exemplary instruction sequence shown in  FIG. 5 . 
   In  FIG. 5 , S 1 , S 2 , S 3 , S 4 , S 10  and S 11  are respective architecture registers. 
   In  FIG. 5 , since a lw instruction (load word instruction) in the fourth line and an addi instruction in the fifth line use the same register S 1  as the lw instruction, addi instruction, and add instruction in the first line through the third line, it is not possible to execute the lw instruction in the fourth line until instructions from the first line through third line are completed. However, since the register S 1  is only used for holding the intermediate value of instructions from the first line through the third line, it is possible to substitute the register S 1  with another register if another register is available. In other words, instructions in the fourth line and fifth line essentially have no dependency on instructions in the first line through third line. 
     FIG. 6  illustrates instruction sequence that are the instruction sequence shown in  FIG. 5  renamed using the register renaming unit of the first embodiment. With the instruction sequence renamed by the register renaming unit and shown in  FIG. 6 , instructions subsequent to the fourth line may be issued without waiting for completion of instructions in the first line through third line. 
   In  FIG. 6 , R 1 , R 2 , R 3 , R 4 , R 10 , R 11  and R 40  are respective physical registers. With the instruction sequence of  FIG. 6 , the S 1  register for instructions in the first line through the third line in  FIG. 5  is renamed the R 40  register; and the S 1  register for instructions in the fourth line and fifth line in  FIG. 5  is renamed the R 1  register. This causes the dependency between the instructions in the first line through third line and the instructions in the fourth line and fifth line to be severed. If the S 1 , S 2 , S 3 , S 4 , S 10 , and S 11  registers are mapped to the R 1 , R 2 , R 3 , R 4 , R 10 , and R 11  registers, respectively, upon completion of instructions in the first line through the fifth line in  FIG. 6 , the software is allowed to reference the correct value. 
   Next, configuration and operation of a branch prediction unit  23  of the first embodiment is described. 
     FIG. 7  is a block diagram illustrating the internal configuration of the branch prediction unit  23  shown in  FIG. 4 . 
   As shown in  FIG. 7 , the branch prediction unit  23  according to the first embodiment is configured with a branch prediction section  231 , branch prediction buffer  232 , and comparator  233 . 
   The branch prediction unit  23  includes a section for predicting a branch and a section for verifying the branch prediction result. 
   The branch prediction section  231  corresponds to the section for actually predicting a branch. Since the first embodiment may be applied regardless of the branch prediction algorithm, and the specifics of the branch algorithm do not directly relate to this embodiment, specific mention is not made in this specification. 
     FIG. 8  is a flowchart illustrating an example of branch prediction control in the branch prediction unit  23  in  FIG. 7 . 
   To begin with, the instruction fetch unit  11  fetches instruction based on the program counter  11   b  (step S 51 ). If the fetched instruction is a branch instruction (step S 52 Y), then branch prediction is performed (step S 53 ); whereas, if it is not a branch instruction (step S 52 N), then processing returns to step S 51 . 
   A branch prediction algorithm used by the branch prediction section  231  may include, for example, a branch target buffer (BTB). This BTB, is a cache having the program counter (PC) of a branch instruction as a tag, and stores the PC of the branch destination (branch target) and the history of that branch instruction in the cache thereof. When the program counter for the fetched branch instruction hits that of the BTB, the history in the BTB entry hit is referenced. Whether or not the branch of branch instruction has been taken or not taken is determined from the referenced history. If taken, then the target instruction in the entry hit is subsequently fetched. In the case where it is not taken, the instruction is fetched from the program counter in an address immediately following to the branch instruction. 
   A branch prediction buffer  232  and comparator  233  correspond to the section for verifying branch prediction. 
   The branch prediction buffer  232  temporarily holds results predicted by the branch prediction section  231 . When a branch instruction is issued (step S 54 ) and the actually calculated result of the branch instruction is obtained (step S 55 Y), the branch prediction value held in the branch prediction buffer is read out (step S 56 ). The comparator  233  compares the actual branch result (D 233 ) and predicted result (step S 57 ). The commit unit  18  is notified of this comparison result (D 234 ). 
   When the predicted branch result is correct (step S 57 Y), the commit unit  18  commits (completes) the branch instruction (step S 58 ), and commits, in the normal manner, instructions subsequent to this branch instruction including speculatively executed instructions (step S 59 ). 
   Meanwhile, if the predicted branch result is incorrect (step S 57 N), the branch instruction is committed (step S 60 ), however, all instructions subsequent to this branch instruction are disabled (flushed) (step S 61 ). The original correct instruction address (i.e., a target address when the branch is taken; or an address of instruction subsequent to that branch instruction when the branch is not taken) is set to the program counter  11   b  in the instruction fetch unit  11 , and instruction fetch is resumed from that point (step S 62 ). 
   In the first embodiment, the hardware inserts into the instruction window buffer  12  the branch instruction subsequent to the load instruction for which a load value is to be predicted. Corresponding to this, as shown in  FIG. 7 , information on the virtual branch instruction inserted from the branch insertion unit  21  is added into the branch prediction buffer  232 . More specifically, information saying that the branch has been predicted as being not taken is always written in this virtual branch instruction. 
   This virtual branch instruction, which is automatically inserted by the hardware when load instruction whose load value is to be predicted is fetched, is a branch instruction for subsequently “determining whether or not the load value prediction is correct, and re-executing speculatively executed instructions, if incorrect”. 
   Next, operation of a load value prediction control unit in the first embodiment is described. Operation of the processor  1  after a load instruction is fetched is described in the following using a time series. 
     FIG. 9  is a flowchart describing a series of operations after an instruction is fetched, including load value prediction, speculative instruction execution, prediction verification, and recovery when a prediction error occurs in the first embodiment. 
   To begin with, as shown in  FIG. 9 , the instruction fetch unit  11  fetches instruction (step S 1 ). Here, if the fetched instruction is a target for prediction (step S 2 Y), the register renaming section  19  executes register renaming (step S 3 ). The load value prediction unit  16  writes the load prediction value in the register file (step S 4 ). 
   The branch insertion unit  21  inserts a virtual branch instruction into the instruction window buffer  12 , and adds an entry to the branch prediction buffer  232  (step S 5 ). 
   The instruction window buffer  12  issues a load instruction to the load/store unit  13  (step S 6 ). The load/store unit  13  loads the value to be loaded from the main memory  2 . 
   The load/store unit  13  waits for determination of the load value in conformity with load instruction execution (step S 7 ). When the load value of the load instruction execution result is obtained (step S 7 Y), the instruction window buffer  12  issues the inserted virtual branch instruction to the execution unit  14   a  or  14   b  (step S 8 ). The execution unit  14   a  or  14   b  waits for determination of the branch instruction execution result (step S 9 ). When the result of the branch instruction is obtained (step S 9 Y), the branch prediction unit  23  reads out the branch instruction prediction result (step S 10 ), compares the read out branch instruction prediction result and the result obtained in conformity with branch instruction execution (step S 11 ), and notifies the commit unit  18  of the comparison result. 
   When the two match, that is, when branch prediction is correct (step S 11 Y), the commit unit  18  commits (completes) the load instruction and branch instruction (step S 12 ), and also commits (completes) subsequent instructions that have been speculatively executed (step S 13 ). 
   Meanwhile, when the two do not match, that is, when branch prediction is incorrect (step S 11 N), the commit unit  18  commits the load instruction and branch instruction (step S 14 ) and disables (flushes) instructions subsequent to the load instruction (step S 15 ). The instruction fetch unit  11  again starts the fetch of a subsequent instruction (step S 16 ). 
   The register renaming and the branch instruction insertion described above are performed as follows. 
   The physical register in which the predicted load instruction result is written and the physical register in which this predicted value is written are mapped as different registers. Here, the former physical register is given as Rm, and the latter physical register as Rn. 
   The predicted load instruction is renamed to be an instruction that writes the load result in the register Rm in the instruction window buffer  12 . A branch instruction for determining whether the values in the Rm and Rn match is inserted immediately after this load instruction. In addition, subsequent instructions that use the load instruction result are renamed as instructions that use the value in the register Rn as the load value to be used in the instruction window buffer  12 . 
     FIG. 10  illustrates the instruction sequence obtained in conformity with execution of register renaming processing and branch instruction insertion processing which corresponds to the instruction sequence shown in  FIG. 3 . 
   In  FIG. 10 , Rm, Rn, R 2 , R 3 , and R 10  are respective physical registers. The result of actual load instruction execution is stored in the Rm. The load value predicted by the load value prediction unit  16  is stored in the Rn, and subsequent instructions that use the load instruction execution result are renamed to use the Rn value as the load instruction result. This allows speculative issuance of subsequent instructions without waiting for the execution results of the load instruction and inserted branch instruction by employing an out-of-order issuance mechanism. 
   Branch instruction (bne instruction) in  FIG. 10  is a virtual branch instruction inserted by the branch insertion unit  21 . With this branch instruction, the actual load result (Rm) and load prediction value (Rn) are compared, and if the two do not match, processing branches to a label L 1 . Since this branch instruction has dependency on the immediately preceding load instruction result (Rm), the branch instruction is issued after this load instruction result becomes available by employing the instruction issuance mechanism of the instruction window buffer  12 . In other words, steps S 7  and S 8  in  FIG. 9  are implemented through the out-of-order instruction issuance mechanism of the instruction window buffer  12 . 
   The branch instruction in  FIG. 10  ultimately branches to the same address regardless of whether the branch is taken or not taken. However, the difference between the two lies in the following: when the branch is taken, that is, when load value prediction and the result do not match, subsequent instructions are disabled (flushed) by the same unit as when prediction is not taken in the branch prediction. Otherwise, when the branch is not taken, that is, when load value prediction and the result match, subsequent instructions that have been speculatively executed are committed since branch prediction matches. 
   In order to re-execute subsequent instructions, the instructions that use the load instruction result should be renamed using Rm since the load instruction result has already been obtained in the register Rm. 
   It should be noted that each of out-of-order issuance (dynamic scheduling), register renaming, and branch prediction used in the first embodiment is a method generally used as a method for increasing the speed of the processor independent of load value prediction. Accordingly, in the first embodiment, existing hardware associated with these prediction units, such as the register renaming unit  19 , out-of-order instruction window buffer  12 , reorder buffer  18   a , and branch prediction unit  23 , may be used as the instruction prediction unit for, for example, a load value and the like. 
   In the first embodiment, the newly added branch insertion unit  21  is a simple function unit that only inserts branch instruction in conformity with the register renaming processing by the register renaming unit  19  with timing that is predicted by the load value prediction unit  16 . Therefore, in comparison with the case of using the conventional value prediction buffer  119  and comparator  120  described in  FIG. 1 , hardware costs are drastically reduced. 
   In addition, in the first embodiment, steps S 7  and S 8  in  FIG. 9  are implemented with the out-of-order issuance mechanism of the normal instruction window buffer  12 ; and steps S 9  through S 16  are implemented with the prediction error recovery mechanism provided by the branch prediction unit  23 . 
   Accordingly, in comparison with the conventional control flowchart described in  FIG. 2 , this may be considered as equivalent to the case where specific controls subsequent to load instruction issuance in step S 24  are omitted, or more specifically, the control mechanism provided by other unit may be seen as implementing the specific controls. 
   In addition, in comparison with the flowchart prior to load instruction issuance processing in step S 24 , register renaming processing, branch instruction insertion, and addition of the branch prediction entry (steps S 3  and S 5 ) are added in  FIG. 9 . Since the existing unit independent of load value prediction may be used for this register renaming processing, substantially only branch instruction insertion and addition of the branch prediction entry are added. 
   Accordingly, with the first embodiment, the recovery processing control for load value prediction may be seen as being simplified. 
   With the first embodiment, the following effects may be obtained. 
   In other words, the first embodiment easily realizes the load value prediction control unit using the above-mentioned register renaming mechanism (register renaming unit  19  and architecture register map  20 ) and branch prediction unit  23 . In addition, by using such existing hardware, it is possible to reduce hardware costs for the load value prediction control unit and furthermore, the prediction unit. 
   Second Embodiment 
   Next, while referencing  FIG. 11 , only those points of a speculative computer instruction execution control device and method for the same according to a second embodiment of the present invention that differ from the first embodiment are described. 
   The second embodiment differs from the first embodiment in that the branch destination of the branch instruction executed by the branch insertion unit  21  in  FIG. 4  that is described in the first embodiment is changed to the “address of the predicted load instruction itself” instead of the “address of the instruction immediately after the predicted load instruction”. 
   Since the configuration of a processor having a speculative instruction execution control device according to the second embodiment is similar to the processor of the first embodiment shown in  FIG. 4 , and branch prediction control processing according to the second embodiment is similar to the case of the first embodiment shown in  FIG. 8 , respective descriptions thereof are omitted. 
     FIG. 11  illustrates the instruction sequence obtained in conformity with the execution of register renaming processing and branch instruction insertion processing according to the second embodiment, which corresponds to the instruction sequence shown in  FIG. 3 . 
   In  FIG. 11 , the Rm, Rn, R 2 , R 3  and R 10  are respective physical registers. The result of the actual load instruction execution is stored in Rm. The load value predicted by the load value prediction unit  16  is stored in Rn, and subsequent instructions that use the load instruction execution result are renamed to use the Rn value as the load instruction result. By using an out-of-order issuance mechanism, this allows speculative issuance without waiting for the execution results of load instruction and inserted branch instruction. 
   The branch instruction (bne instruction) in  FIG. 11  is a virtual branch instruction inserted by the branch insertion unit  21  according to the first embodiment. With this branch instruction, the actual load result (Rm) and load prediction value (Rn) are compared, and if the two do not match, processing branches to the label L 1 . 
   When load value prediction is incorrect (load value prediction error), re-fetching is carried out from the load instruction (lw instruction) without committing (completing) the load instruction (lw instruction) and inserted branch instruction (bne instruction) of  FIG. 11 . 
   In the second embodiment, the load instruction during re-execution has the same load instruction already executed immediately beforehand. Accordingly, if a processor has a cache, then the value to be loaded is stored in cache, and it is possible to obtain the correct execution result for the load instruction with little time delay. It should be noted that the branch insertion unit  21  does not insert branch instruction since load value prediction is not performed during re-execution of the load instruction. 
   Third Embodiment 
   Next, only those points of a speculative computer instruction execution control device and method for the same according to a third embodiment of the present invention differing from the second embodiment are described. 
   The third embodiment is different from the second embodiment in that load value prediction processing and branch prediction processing are performed in the re-executing load instruction described in the second embodiment. Accordingly, the branch instruction insertion processing and branch prediction addition processing in steps S 3  through S 5  in  FIG. 9  are also re-executed. 
   Since the configuration of a processor having a speculative instruction execution control device according to the third embodiment is similar to the processor of the first embodiment shown in  FIG. 4 , and branch prediction control processing according to the second embodiment is similar to the case of the first embodiment shown in  FIG. 8 , descriptions thereof are omitted. 
   It is possible to perform correct prediction using a load value that is a result of the previously executed load instruction as the load prediction value for re-execution when load value prediction is re-executed. 
   According to the third embodiment, since load value prediction is performed when both executing and re-executing the first load instruction, controls for the respective cases of performing prediction and not performing prediction are simplified. 
   In addition, since load value prediction processing is also performed when re-executing a load instruction, it is possible to issue subsequent instructions having dependency on a load instruction earlier than in the case of the second embodiment. 
   Fourth Embodiment 
   Next, only those points of a speculative computer instruction execution control device and method for the same according to a fourth embodiment of the present invention differing from the first embodiment are described while referencing  FIG. 12 . 
   The fourth embodiment is different from the first embodiment in that with the branch instruction insertion performed by the branch insertion unit  21  in  FIG. 4  described in the first embodiment, branch instruction is inserted so that where, between the load instruction execution result and the predicted value, “if there is a match, then branch taken is predicted”, or “if there is no match, then branch not taken is predicted” is inserted. 
   The branch insertion unit  21  writes information that “branch taken is predicted” in the prediction entry to be added in the branch prediction buffer  232 . 
   Since the configuration of a processor having a speculative instruction execution control device according to the fourth embodiment is similar to the processor of the first embodiment shown in  FIG. 4 , and branch prediction control processing according to the fourth embodiment is similar to the case of the first embodiment shown in  FIG. 8 , descriptions thereof are omitted. 
     FIG. 12  illustrates the instruction sequence obtained through the execution of register renaming processing and branch instruction insertion processing according to the fourth embodiment, which corresponds to the instruction sequence shown in  FIG. 3 . 
   In  FIG. 12 , the Rm, Rn, R 2 , R 3  and R 10  are respective physical registers. The actual executed result of the load instruction is stored in Rm. Since the load value predicted by the load value prediction unit  16  is stored in Rn, and subsequent instructions that use the load instruction execution result are renamed to use the Rn value as the load instruction result, speculative issuance may be performed without waiting for the execution results of the load instruction and inserted branch instruction using the out-of-order issuance mechanism. 
   With the fourth embodiment, operations similar to the first embodiment may be implemented. In conformity with the branch instruction in  FIG. 12 , if the predicted load value and the load instruction execution result do not match, the inserted branch instruction is not taken. This is because branch error recovery occurs since this branch instruction not taken is inconsistent with the “branch taken” in branch prediction. 
   Fifth Embodiment 
   Next, only those points of a speculative computer instruction execution control device and method for the same according to a fifth embodiment of the present invention differing from the first embodiment are only described while referencing  FIG. 13  and  FIG. 14 . 
   The fifth embodiment is different from the first embodiment in that with the recovery processing for load value prediction error in steps S 14  through S 16  of  FIG. 9  described in the first embodiment, re-execution starts from the first instruction having dependency on the load instruction for which a load value is predicted. 
   Since the configuration of a processor having a speculative instruction execution control device according to the fifth embodiment is similar to the processor of the first embodiment shown in  FIG. 4 , and branch prediction control processing according to the fifth embodiment is similar to the case of the first embodiment shown in  FIG. 8 , descriptions thereof are omitted. 
   There are various methods for the recovery operation in load value prediction. A recovery operation is an operation that disables speculatively executed instructions and the results thereof, and re-executes such instructions. With this recovery operation, it is not necessary to actually disable non-speculatively executed instructions (non-speculative instructions). Nevertheless, in order to simplify the operation control, a part or all of the non-speculative instructions may be disabled and re-executed. 
   Accordingly, there are various variations in recovery operation depending on which instruction is disabled, and from which stage the processor re-executes the disabled instruction. These operation variations have the same effects as far as keeping the calculation result in the correct status, however, the penalties for a prediction error differ. Generally, complicated recovery operation has fewer penalties. In other words, there is a trade-off relationship between complicating the operation and reducing the penalties. 
   In the first embodiment, “all instructions following the predicted load instruction” are disabled, and re-execution starts from “fetching the instruction” of the disabled instructions. This recovery operation in the first embodiment may be implemented with a relatively simple control. Meanwhile, the fifth embodiment is an embodiment wherein the control for recovery operation is more complicated in order to reduce prediction error penalties. 
   In other hand, in the fifth embodiment, if a load value prediction is incorrect, only “the first instruction and subsequent instructions having dependency on this load instruction” of the instructions subsequent to the load instruction are disabled, and the instruction fetch is started again from “the first instruction having dependency on this load instruction”. Accordingly, if an instruction having no dependency on this load instruction is executed between a load instruction for which load value is predicted and an instruction having dependency on this load instruction, this instruction having no dependency on the load instruction is not disabled. 
   It is assumed that the group of instructions in  FIG. 13  is given as the specific instruction sequence. It should be noted that S 1 , S 2 , S 3 , S 4 , S 5 , S 6  and S 10  in  FIG. 13  indicate respective architecture register names (register numbers). 
   In the group of instructions in  FIG. 13 , a subtract instruction (sub instruction) has no dependency on a load instruction (lw instruction). 
     FIG. 14  illustrates the instruction sequence obtained through the execution of register renaming processing and branch instruction insertion processing according to the fifth embodiment, which corresponds to the instruction sequence shown in  FIG. 13 . 
   In  FIG. 14 , the Rm, Rn, R 2 , R 3 , R 4 , R 5 , R 6  and R 10  are respective physical registers. The actual execution result of the load instruction is stored in Rm. The load value predicted by the load value prediction unit  16  is stored in Rn, and subsequent instructions that use the load instruction execution result are renamed to use the Rn value as the load instruction result. This allows speculative issuance without waiting for the execution results of the load instruction and inserted branch instruction by using the out-of-order issuance mechanism. 
   Since the branch destination of the branch instruction shown in  FIG. 14  is an immediate add instruction (addi instruction), only the instructions subsequent to the inserted branch instruction are disabled by the recovery operation for a branch prediction error when load value prediction is incorrect (prediction error). 
   In the fifth embodiment, the branch insertion unit  21  inserts a branch instruction immediately before “the first instruction having dependency on the predicted load instruction”. 
   In the fifth embodiment, a function for detecting this “first instruction having dependency on the predicted load instruction” becomes necessary. Accordingly, the branch insertion unit  21  must be informed by the register renaming section  19  that instruction using the register Rn is fetched in  FIG. 14 , which makes control performed by the branch insertion unit  21  is somewhat complicated. 
   Nevertheless, with the fifth embodiment, the number of times the instruction having no dependency on load instruction is re-executed may be reduced, which allows reduction of prediction error penalties. 
   Sixth Embodiment 
   Next, only those points of a speculative computer instruction execution control device and method for the same according to a sixth embodiment of the present invention differing from the fifth embodiment are described while referencing  FIG. 15 . 
   While the fifth embodiment re-executes “instruction fetch” first for the first instruction having dependency on the load value predicted load instruction and instructions subsequent to the first instruction in steps S 14  through S 16  described in  FIG. 9 , the sixth embodiment re-executes “instruction issuance” first for the first instruction having dependency on load instruction for which load value is predicted and the instructions subsequent to the first instruction. 
   In the sixth embodiment, the instruction window buffer  21  holds a issued instruction until the instruction is committed (completed) and it must be made re-issuable in recovery operation for a prediction error. Thus, a unit that implements such functions becomes necessary. 
   In addition, in the fifth embodiment, the recovery control unit in the branch prediction unit  23  is unified with the recovery control unit for a load value prediction error. Although “instruction fetch” is re-executed first for the conventional branch prediction error, the sixth embodiment re-executes “instruction issuance” first for the virtual branch instruction prediction error, therefore a part of recovery control unit in the branch prediction unit  23  may not be unified (shared-used) for the recovery for the load value prediction error. 
     FIG. 15  is a flowchart illustrating recovery operation control for a load value prediction error according to the sixth embodiment. 
   In comparison with the flowchart of the first embodiment shown in  FIG. 9 , a step for determining which is the first instruction having dependency on load instruction (step S 4   b ) is added in order to determine an insertion point prior to the insertion processing for a branch instruction (step S 5 ) executed by the branch insertion unit  21 . (This step S 4   b  also becomes necessary for the above-mentioned fifth embodiment.) In addition, when the branch prediction error occurs, it is determined whether it is either the case where a prediction error has occurred due to a branch instruction that is inserted by the branch insertion unit  21 , or the case of a prediction error other than the former case (step S 17 ). In the case of a prediction error of a branch instruction inserted by the branch insertion unit  21  (step S 17 Y), instructions subsequent to the branch instruction inserted by the branch insertion unit  21  in the reorder buffer  18   a  are disabled (step S 18 ) and disabled subsequent instructions are re-issued (step S 19 ). The reorder buffer  18   a  administers an “issued but not committed instruction”. Accordingly, instructions to be re-issued are disabled in the reorder buffer  18   a,  and they are properly re-issued by being made re-issuable in the instruction window buffer  12  at the same time. 
   Meanwhile, in the case of a prediction error other than that occurring due to a branch instruction that is inserted by the branch insertion unit  21  (step S 17 N), recovery operation for a branch prediction error as with the above-mentioned embodiments is executed (step S 15  and step S 16 ). 
   With the sixth embodiment, control for a prediction error is more complicated than that with the fifth embodiment, however, prediction error penalties may be reduced further. 
   Seventh Embodiment 
   Next, only those points of a speculative computer instruction execution control device and method for the same according to a seventh embodiment of the present invention differing from the sixth embodiment are described. 
   In the sixth embodiment, instruction issuance is re-executed first for “the first instruction having dependency on the predicted load instruction and instructions subsequent to the first instruction” in steps S 18  and S 19  described in  FIG. 5 , whereas, in the seventh embodiment, instruction issuance is re-executed first for “all of the instructions of the issued instructions having dependency on the predicted load instruction”. 
   In the seventh embodiment, instructions that have no dependency on load instruction for which load value is predicted are not re-executed. 
   A reorder buffer  18   a  according to the seventh embodiment selects and disables only instructions having dependency on the load instruction of the issued instructions when the load value prediction error occurs. In addition, an instruction window buffer  21  according to the seventh embodiment makes issuable only those instructions having dependency on the load instruction for which load value prediction error has occurred, of the issued instructions, and starts re-issuance of such instructions. 
   With the seventh embodiment, control for the prediction error becomes more complicated than the sixth embodiment, however, prediction error penalties may be further reduced since only the instructions having dependency on the load instruction are selectively re-executed. 
   Eighth Embodiment 
   Next, only those points of a speculative computer instruction execution control device and method for the same according to an eighth embodiment of the present invention differing from the first embodiment are described while referencing  FIG. 16  and  FIG. 17 . 
   The eighth embodiment is different from the first embodiment in that the prediction control and recovery function for load value prediction described in the first embodiment is applied to value prediction that is not limited to load instruction. 
   The recovery control of the load value prediction unit described in the above embodiments may be applied to the recovery control of a prediction unit other than that for load value prediction. In other words, the recovery control of the prediction unit of the above embodiments may be applied to any prediction unit (prediction unit other than branch prediction) capable of verifying whether prediction is correct by branch instruction and is not limited to load value prediction. 
     FIG. 16  illustrates an example of the configuration of a processor having a conventional value prediction unit. In comparison with the configuration of a processor having the conventional load value prediction unit shown in  FIG. 1 , the load value prediction unit  116  in  FIG. 1  is substituted with the value prediction unit  116   b  in  FIG. 16 . In addition, when comparing the predicted value with a value that is obtained through actual instruction execution, only the load instruction result output from the load/store unit  113  is compared in  FIG. 1 , whereas, in the processor having the value prediction unit shown in  FIG. 16 , the results output from all execution units including the load/store unit  113 , execution units  114   a  and  114   b  are targets for comparison. 
     FIG. 17  illustrates an example of the configuration of a processor having a value prediction unit according to the eighth embodiment. In comparison with the configuration of the processor having the load value prediction unit according to the first embodiment shown in  FIG. 4 , the load value prediction unit  16  in  FIG. 4  is substituted with the value prediction unit  16   b.    
   As shown in  FIG. 17 , while, in the configuration of the processor having the load value prediction unit according to the first embodiment shown in  FIG. 4 , value prediction is performed only for the load instruction; a processor having a value prediction unit according to the eighth embodiment performs value prediction for arbitrary instructions. When the value prediction unit  16  gives notification that an instruction that is a target for prediction is fetched, the branch insertion unit  21  according to the eighth embodiment inserts a branch instruction subsequent to the predicted instruction. 
   With the eighth embodiment, it is possible to speculatively execute not only load instruction, but also subsequent instructions based on value prediction of arbitrary instructions. 
   Ninth Embodiment 
   Next, only those points of a speculative computer instruction execution control device and method for the same according to a ninth embodiment of the present invention differing from the first embodiment are described while referencing  FIG. 18 . 
   The ninth embodiment is different from the first embodiment in that an out-of-order instruction issuing processor having a load value prediction unit described in the first embodiment is substituted with an in-order instruction issuing processor. 
     FIG. 18  illustrates an example of the configuration of a processor having a load value prediction unit according to the ninth embodiment. In comparison with the configuration of the processor having the load value prediction unit according to the first embodiment shown in  FIG. 4 , the configuration of a processor according to the ninth embodiment is different from the processor configuration according to the first embodiment in that the out-of-order instruction issuing instruction window buffer  12  in  FIG. 4  is substituted with an in-order instruction issuing instruction window buffer  12   b  in  FIG. 18 , and the reorder buffer  18   a  in  FIG. 4  is not included in  FIG. 18 . 
   If instructions subsequent to the branch that is the instruction inserted by the branch insertion unit  21 , are executed without waiting for the predicted load instruction execution result even in the case of in-order instruction issuance, the processing speed of a processor increases through speculative instruction execution with value prediction. In other words, it is possible to execute subsequent instructions speculatively when the inserted branch instruction issued from the instruction window buffer  12   b  prior to the predicted load instruction execution result is obtained. 
   To give the instruction sequence obtained in the first embodiment shown in  FIG. 10  as an example, if a branch instruction in the second line is issued prior to when the result of load instruction in the first line is obtained, subsequent addi instruction and add instruction may be issued (executed) without waiting for the load instruction execution result. 
   Even in the case of in-order instruction issuance, it may be assumed that the inserted branch instruction is issued prior to when the predicted load instruction execution result is obtained. 
   For example, in the case of a system where the load instruction execution result is bypassed to the branch instruction execution unit, even when branch instruction is issued prior to the load instruction result being determined, a necessary value, in other words the load result required for the execution unit or the execution units  14   a  and  14   b  that execute branch instruction in the branch instruction execution, becomes available. Accordingly, it is possible to issue inserted branch instruction prior to the predicted load instruction result is obtained. 
   To give another example, there is a system in which each execution unit has the function of holding instructions issued to the execution unit without executing the instructions. A unit implementing such a instruction holding function is generally called a reservation station. This reservation station holds instructions issued to each execution unit until the necessary operand becomes available and becomes executable in the execution unit. Accordingly, in such a system, instruction may be issued prior to the necessary operand becoming available. 
   More specifically, when a branch instruction inserted by the branch insertion unit  21  and an instruction subsequent to this branch instruction are respectively issued to different execution units, in other words, when they are held in different reservation stations, instructions subsequent to the branch instruction, that is, instructions subsequent to the load instruction become speculatively executable. This is because instructions subsequent to the branch instruction become executable independent of the execution of the branch instruction by being issued to different execution units. 
   With the ninth embodiment, even in an in-order instruction issuing processor, it is possible to obtain effects similar to the above embodiments. 
   In the above embodiments of the present invention, with the speculative instruction execution of the processor, it is possible to hold down increases in the cost of hardware required for verifying whether value prediction is correct and performing recovery control for a prediction error. 
   In addition, it is possible to implement verification of value prediction and recovery control for a prediction error with simple control without adding complicated control unit in order to perform value prediction that accompanies the speculative instruction execution. Accordingly, it becomes easy to verify and mount a control unit onto a processor. 
   It should be fully understood that the various embodiments that are not mentioned herein are included in the present invention. Accordingly, the present invention should not be limited only by the invention-specific materials related to the disclosure through the appropriate claims.