Apparatus and method of controlling instruction fetch

Abstract

An instruction control apparatus, and method, used with a device including a cache memory, a lower memory, an instruction fetch device issuing an instruction fetch request for a target of a first branch instruction to the cache memory, and an instruction control device processing a instruction sequence stored in the cache memory. The apparatus and method pre-prefetch a target instruction sequence for a target of a second branch instruction. A predetermined instruction sequence based on a past history is preliminarily transferred from the lower memory to the cache memory when the target instruction sequence for the target of the first branch instruction is not in the cache memory.

1 . An instruction fetch control device controlling instruction fetch in an instruction control device having a cache memory unit, a lower memory unit, and an execution unit speculatively executing an instruction sequence stored in the cache memory unit, comprising: 
 an instruction fetch unit issuing an instruction fetch request to the cache memory unit;    an address generation unit obtaining a branch target instruction address if branching occurs when a conditional branch instruction or an unconditional branch instruction is executed; and    a branch target instruction prefetch unit prefetching a branch target instruction for requesting the cache memory unit to fetch the branch target instruction if the branch target instruction address is requested when branching occurs for the branch instruction.    
   
   
       2 . The apparatus according to  claim 1 , further comprising: 
 a branch prediction unit predicting success or failure of a branch instruction, and a branch target address in case of success of the branch instruction, wherein    said instruction prefetch unit requests said cache memory unit to perform instruction fetch of an instruction address when branching does not occur in executing a branch instruction predicted by said branch prediction unit.    
   
   
       3 . The apparatus according to  claim 2 , further comprising: 
 a priority determination unit setting a priority of a branch instruction to which a request can be issued for branch instruction prefetch by one or more branch instructions being executed, and allowing said branch target instruction prefetch unit to request branch instruction prefetch based on the priority.    
   
   
       4 . The apparatus according to  claim 1 , further comprising: 
 at least one instruction buffer unit holding an instruction sequence using one or more branch instruction prefetch requests.    
   
   
       5 . The apparatus according to  claim 1 , wherein: 
 fetching and executing an instruction subsequent to a branch instruction is stopped when execution and a branch target of the branch instruction are determined;    branch instruction prefetch corresponding to the branch instruction is changed into actual instruction fetch;    said branch instruction fetch is continued or terminated; and    a branch target instruction of said branch instruction is executed.    
   
   
       6 . The apparatus according to  claim 2 , wherein: 
 when the branch instruction predicted by said branch prediction unit is executed, and a non-branch is determined or it is determined that branching occurs to a branch target different from a predicted branch target, instruction fetch and execution of a predicted branch target instruction of the branch instruction is suspended and canceled; branch instruction prefetch of a subsequent instruction corresponding to the branch instruction is changed into actual instruction fetch; subsequent instruction fetch is continued or suspended; and the subsequent instruction is executed.    
   
   
       7 . The apparatus according to  claim 1 , wherein: 
 when said branch instruction is a conditional branch instruction, said branch instruction is executed; or    the branch instruction prefetch which has been performed is canceled when it is determined that no branching occurs and a subsequent instruction is executed, or when it is determined that the branch instruction is not executed.    
   
   
       8 . The apparatus according to  claim 2 , wherein: 
 said branch instruction for which a branch prediction is made by said branch prediction unit is executed; or    said branch instruction prefetch being performed is canceled when it is determined that a branch target instruction of the predicted branch instruction is executed.    
   
   
       9 . The apparatus according to  claim 1 , further comprising: 
 a detection unit detecting that there is a possibility of rewriting an instruction sequence to be branch-instruction-prefetched as a result of executing an instruction.    
   
   
       10 . The apparatus according to  claim 9 , wherein: 
 said detection unit detects a possibility of rewriting an instruction sequence using an address of a store instruction and an address of a branch instruction issuing a branch instruction prefetch request, or an address of a branch target instruction of the branch instruction.    
   
   
       11 . The apparatus according to  claim 9 , wherein: 
 when it is determined that an instruction sequence to be branch-instruction-prefetch is rewritten when said instruction is executed, said branch instruction prefetch request is canceled.    
   
   
       12 . The apparatus according to  claim 1 , wherein: 
 when said cache memory unit does not store an instruction corresponding to an address of a branch target instruction of a branch instruction when the address of the branch target instruction of the branch instruction is obtained, it is requested to transfer the branch target instruction from said lower memory unit to said cache memory unit.    
   
   
       13 . The apparatus according to  claim 2 , wherein: 
 when it is determined that said cache memory unit does not store a subsequent instruction sequence corresponding to an instruction address in case of a non-branch during execution of a branch instruction for which a branch is predicted by said branch prediction unit, it is requested to transfer the subsequent instruction sequence from said lower memory unit to said cache memory unit.    
   
   
       14 . The apparatus according to  claim 1 , wherein 
 said instruction prefetch unit prefetches instructions in a prefetched instruction sequence.    
   
   
       15 . The apparatus according to  claim 14 , further comprising 
 a suppression unit preventing the instruction prefetch request from being infinitely issued.    
   
   
       16 . The apparatus according to  claim 14 , further comprising 
 an address register for the instruction prefetch.    
   
   
       17 . The apparatus according to  claim 16 , wherein 
 a flag indicating whether or not a value of said address register is valid is held.    
   
   
       18 . The apparatus according to  claim 16 , wherein 
 when an instruction sequence to be actually executed has to be executed again, said address register is nullified.    
   
   
       19 . The apparatus according to  claim 14 , wherein 
 when an instruction is prefetched from the prefetched instruction sequence, a branch prediction mechanism is used.    
   
   
       20 . An instruction control method used with a device having cache memory, lower memory, and an instruction fetch device issuing an instruction fetch request to said cache memory, comprising: 
 (a) obtaining a branch target instruction address when branching occurs during execution of a conditional branch instruction or an unconditional branch instruction; and    (b) performing branch instruction prefetch in which instruction fetch of a branch instruction is requested when a branch target instruction address is obtained when branching occurs for the branch instruction.    
   
   
       21 . The method according to  claim 20 , further comprising: 
 (c) predicting a branch target instruction of the branch instruction, wherein    in said (b), requesting instruction fetch of an instruction address when branching does not occur in executing a branch instruction predicted in said (a).    
   
   
       22 . The method according to  claim 21 , further comprising: 
 (d) setting a priority of an instruction to which a request can be issued for branch instruction prefetch by one or more branch instructions being executed, and requesting branch instruction prefetch based on the priority in step (b).    
   
   
       23 . The method according to  claim 20 , further comprising: 
 holding an instruction sequence using one or more branch instruction prefetch request.    
   
   
       24 . The method according to  claim 20 , wherein: 
 fetching and executing an instruction subsequent to a branch instruction is stopped when execution and a branch target of the branch instruction are determined;    branch instruction prefetch corresponding to the branch instruction is changed into actual instruction fetch;    said branch instruction fetch is continued or terminated; and    a branch target instruction of said branch instruction is executed.    
   
   
       25 . The method according to  claim 21 , wherein: 
 when the branch instruction predicted in said (a) is executed, and a non-branch is determined or it is determined that branching occurs to a branch target different from a predicted branch target, instruction fetch and execution of a predicted branch target instruction of the branch instruction is suspended and canceled; branch instruction prefetch of a subsequent instruction corresponding to the branch instruction is changed into actual instruction fetch; subsequent instruction fetch is continued or suspended; and the subsequent instruction is executed.    
   
   
       26 . The method according to  claim 20 , wherein: 
 when said branch instruction is a conditional branch instruction, said branch instruction is executed; and the branch instruction prefetch which has been performed is canceled when it is determined that no branching occurs and a subsequent instruction is executed, or when it is determined that the branch instruction is not executed.    
   
   
       27 . The method according to  claim 21 , wherein: 
 said branch instruction for which a branch prediction is made in said (a) is executed; and    said branch instruction prefetch being performed is canceled when it is determined that a branch target instruction of the predicted branch instruction is executed.    
   
   
       28 . The method according to claim,  20 , further comprising: 
 (e) detecting that there is a possibility of rewriting an instruction sequence to be branch-instruction-prefetched as a result of executing an instruction.    
   
   
       29 . The method according to  claim 28 , wherein: 
 in said (e), detecting a possibility of rewriting an instruction sequence using an address of a branch instruction issuing a branch instruction prefetch request, and an address of a branch target instruction.    
   
   
       30 . The method according to  claim 28 , wherein: 
 when it is determined that an instruction sequence to be branch-instruction-prefetched is rewritten when said instruction is executed, said branch instruction prefetch request is canceled.    
   
   
       31 . The method according to  claim 20 , wherein: 
 when said cache memory unit does not store an instruction corresponding to an address of a branch target instruction of a branch instruction when the address of the branch target instruction of the branch instruction is obtained, it is requested to transfer the branch target instruction from said lower memory unit to said cache memory unit.    
   
   
       32 . The method according to  claim 21 , wherein: 
 when it is determined that said cache memory unit does not store a subsequent instruction sequence corresponding to an instruction address in case of a non-branch during execution of a branch instruction for which a branch is predicted in said (a), it is requested to transfer the subsequent instruction sequence from said lower memory unit to said cache memory unit.    
   
   
       33 . The method according to  claim 20 , wherein 
 in said steps (a) and (b), an instruction in the prefetched instruction sequence is prefetched.