Abstract:
An embodiment of the invention is a processor for processing loop branch instructions. The processor includes an instruction unit for fetching and decoding instructions including at least one loop branch instruction. A branch prediction unit predicts target instructions to be fetched and decoded by the instruction unit in response to the loop branch instruction. An execution unit executes instructions from the instruction unit and maintains a counter indicating an iteration of a loop. The execution unit includes detection logic for detecting when the counter equals a threshold and notifies the branch prediction unit when the counter equals the threshold.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    The invention relates to computer systems and in particular to a computer processor for processing loop branch instructions.  
           [0002]    The present application is related to the following co-pending patent application filed concurrently herewith:  
           [0003]    U.S. Patent application entitled METHOD AND SYSTEM FOR ALTERING PROCESSOR EXECUTION OF A GROUP OF INSTRUCTIONS, attorney docket POU920030070US 1.  
           [0004]    This co-pending application and the present application are owned by one and the same assignee, International Business Machines Corporation of Armonk, New York. The description set forth in this co-pending application is hereby incorporated into the present application by this reference.  
           [0005]    Trademarks: IBM® is a registered trademark of International Business Machines Corporation, Armonk, N.Y., U.S.A. S/390, Z900 and z990 and other product names may be registered trademarks or product names of International Business Machines Corporation or other companies.  
           [0006]    Advanced microprocessor designs employ pipelining techniques that divide instruction fetching, decoding, cache access, execution, etc. into separate pipeline stages. The frequency of the processor depends on how much logic exists in each stage. Deeper pipeline designs can be operated at higher frequencies but with increased instruction latencies. Branches, representing control points in a program, are commonly executed instructions that make up to 20-25% of the dynamic instruction count in typical workloads.  
           [0007]    Designers of computer systems try to compute the branch resolution (i.e., taken vs. not taken) as early as possible in the processor pipeline to minimize the amount of speculative execution and to minimize branch penalties in case of executing instructions on the wrong path. The speculation on the branch path, usually referred to as “branch prediction” is decided based on a history table of the previously executed branches and other global factors.  
           [0008]    The branch prediction logic is typically at the front end of the pipeline steering instructions to be executed down the pipe. However, the branch resolution is determined at bottom end of the pipeline typically in the execution stage. Since the resolution of these branches occurs late in the pipeline, an accurate branch prediction becomes crucial for performance. Loop branches (i.e., a branch instruction present in a code loop) are often taken (branch is taken in most cases) but prediction is usually wrong during the last loop when the count value reaches a value of zero. A wrong prediction results in a “flush” of the pipeline and to eventual performance degradation.  
           [0009]    Branches usually test a set of conditions and resolute on the presence or absence of the conditions. RISC-type architecture computers usually branch on a certain value of a condition code or in some cases work (decrement) on dedicated count-registers to minimize dependencies on these registers. CISC-type computers have complicated branches that do some arithmetic computation on general purpose registers (GPR) and resolute on the result. Resolution on branches in CISC computers is usually made during the instruction execution pipeline stage since branches are typically dependent on operands that are read from the GPR array, or on results of proceeding instructions.  
           [0010]    A subset of branches known as “loop branches” are common in most architectures. They are used as counters in program loops decrementing the counter value in each iteration until the counter reaches a value of zero. Loop branches usually require two cycles of execution; one to do the arithmetic operation and the other cycle to compute the branch resolution and send the information back to the instruction fetch pipeline stage.  
           [0011]    Existing processors require two cycles to resolve loop branch instructions. During the first cycle, the operand is decremented by “1” and the result is stored in a storage register. During the second cycle, the branch resolution is calculated based on the result being zero or not and information is sent to branch prediction logic. Further, in existing processors, the branch prediction logic does not distinguish between the last iteration of a loop branch from the rest of the iterations, often resulting in wrong branch prediction during that last iteration.  
         BRIEF SUMMARY OF THE INVENTION  
         [0012]    An embodiment of the invention is a processor for processing loop branch instructions. The processor includes an instruction unit for fetching and decoding instructions including at least one loop branch instruction. A branch prediction unit predicts target instructions to be fetched and decoded by the instruction unit in response to the loop branch instruction. An execution unit executes instructions from the instruction unit and maintains a counter indicating an iteration of a loop. The execution unit includes detection logic for detecting when the counter equals a threshold and notifies the branch prediction unit when the counter equals the threshold. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0013]    Referring now to the drawings wherein like elements are numbered alike in the several FIGURES:  
         [0014]    [0014]FIG. 1 illustrates exemplary processor pipeline stages;  
         [0015]    [0015]FIG. 2 is a high-level block diagram of an exemplary processor;  
         [0016]    [0016]FIG. 3 illustrates one execution unit pipe stage where loop branches are executed;  
         [0017]    [0017]FIG. 4 is a flowchart of an exemplary process implemented by the processor.  
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0018]    Prior to discussing processing of loop branch instructions, the overall processing of instructions is described. FIG. 1 shows the pipeline stages for an IBM z900 processor which represents one embodiment of the present invention. It is understood that the invention may be utilized with other architectures.  
         [0019]    The decode stage  1  is where the instructions are decoded. Stage  2  (address add) is where operand address calculations are made. Stages  3  and  4  (C 1  and C 2 ) are the cache access stages and stage  5  (EX) is the execution stage where instructions are executed. Instructions that require more than one cycle of execution use the EX stage for the required number of cycles. The write back (WB) stage  6  is when the result is stored away in general purpose registers (GPR) or in storage. The loop branch instructions are executed and resolved in the execution unit during the EX stage of FIG. 1.  
         [0020]    [0020]FIG. 2 is a high-level block diagram of a processor  100  in an embodiment of the invention. As shown in FIG. 2, the processor  100  includes an instruction unit  102  having an instruction fetcher  104  that retrieves and decodes instructions from memory. An instruction queue  106  stores instructions and forwards instructions to dispatcher  110  that provides instructions to execution unit  112 . A branch prediction unit  108  receives branch instructions and predicts whether the branch will be taken. Based on the prediction, the branch prediction unit  108  provides target addresses to fetcher  104  to retrieve further instructions.  
         [0021]    Instructions are provided to the execution unit  112  for execution. As described in further detail herein, the execution unit includes general purpose registers (GPR)  22 . Once the execution unit  112  has processed a branch instruction, the branch is resolved to determine whether the branch prediction was correct. Thus, the branch prediction unit  108  typically works well ahead of the execution unit  112 , and predicts the direction of the branch before the branch is decoded in the decode stage (stage  1 ) of FIG. 1.  
         [0022]    When processing loop branch instructions, the branch prediction unit  108  often attempts branch prediction before prior occurrences of the loop branch instruction have been resolved. This is particularly problematic on the final iteration of the loop where, as described above, branch prediction is often incorrect.  
         [0023]    Embodiments of the invention decouple the normal execution of the loop branch instruction (decrement the operand in the GPR  114  by one and update it with the new value) from the branch resolution logic (initiated when the value of updated GPR  114  is 0) that determines if the branch is taken or not. The resolution of the branch can be determined before the operand is decremented by checking if the value before decrementing is “1” or not. The method utilizes the zero detection logic that exists in most processors and modifies it to detect a value of “1”.  
         [0024]    [0024]FIG. 3 shows exemplary components of the execution unit  112  for processing loop branch instructions. Detection logic  26  works in parallel with a decrementor  21  (e.g., a binary adder/subtractor) to evaluate loop branch resolution. Also during execution of loop branch instructions, the counter is checked by detection logic  26  to determine if the counter is equal to a threshold. If the counter equals the threshold, a signal is sent to the branch prediction unit  108  for branch prediction as shown at  28 .  
         [0025]    The threshold indicates the number of unresolved loop branch instructions may exist when performing a branch prediction on the last iteration of the loop. The threshold may vary, and in one embodiment is between 1 and 4. The threshold is dependent on implementation since the branch prediction and instruction fetch work ahead of execution and while a loop branch is in execution, the branch prediction unit might already be predicting the path of next occurrence of the branch. Different implementations allow a different number of outstanding (not resolved) branches.  
         [0026]    [0026]FIG. 3 shows a fixed point unit (FXU) pipe where loop branch instructions are executed in execution unit  112  in an embodiment of the invention. The arithmetic logic unit (ALU)  21  has two inputs from registers, Reg-A  25  and Reg-B  24 , and one output loaded into another register Reg-C  29 . For the loop branches that are executed in the FXU, the decrement operation is done using a binary adder. Register  24  holds the operand data to be decremented, register  25  holds −1, and the ALU  21  performs the decrement operation by adding the two register values.  
         [0027]    The execution unit may operate on 64 bit or 32 bit instructions. For 64-bit loop branches, GPR  22  provides 64 bits to bits  0 : 63  of register  24 . For 32-bit branch loops, the high word of register  24  (bits  0 : 31 ) is set to all zero&#39;s. This allows the branch loops to use the same detection logic  26  to detect when the operand reaches the threshold and when the operand reaches one.  
         [0028]    Branch resolution is calculated by examining the operand value directly and not waiting for the result of the ALU  21 . As shown in FIG. 3, when the detection logic  26  detects that the operand has reached 1, a loop branch resolution signal  27  is issued to the instruction unit  102 . The instruction unit  102  will consider the loop branch taken until receiving the loop branch not taken signal from the execution unit  112 . At this point, the branch prediction unit  108  indicates the next instructions to be fetched. As noted above, the detection logic  26  that exists in most processors is modified to detect when the operand reaches a value of one and when the operand reaches the threshold.  
         [0029]    During the execution (EX) stage, the branch resolution signal  27  is formed by the following logical equation: Loop_branches_not_taken&lt;=(Reg-B( 0 : 63 )=“000 . . . 0001”). In other words, the loop branch is not taken when the register  24  has a binary value of one or less. Similarly, for a threshold value of  3 , the threshold is reached if register  24  has a value of 3(i.e., 000 . . . 0011).  
         [0030]    [0030]FIG. 4 is a flowchart of operation of the execution unit  112 . The process begins when a loop branch instruction is encountered and branch prediction unit  108  determines whether the branch will be taken at step  210 . If so, a counter representing the number of iterations in the program loop is obtained at step  212 .  
         [0031]    Loop branch instructions are executed at step  214 , which includes decrementing the counter until the loop is complete (e.g., counter reaches zero). While the loop branch instruction is being executed, the detection logic  26  simultaneously determines whether the counter equals the threshold at step  218 . The detection is determined by the detection logic  26 . If so, the branch prediction unit  108  is instructed to perform the branch prediction for the final iteration of the program loop at step  220 . Since the branch prediction unit  108  knows how many iterations of the loop remain to be executed, a more accurate prediction is derived.  
         [0032]    Step  222  is implemented in parallel with step  218  and  214 . At step  222 , it is determined whether the counter equals one. Again, detection logic  26  makes this determination. If so, the loop branch resolution is indicated at step  224  by loop branch resolution signal  27 . The execution unit  112  continues to process the loop branch instruction until the number of iterations have been executed.  
         [0033]    The processing disclosed herein results in the loop branch instruction resolving a cycle earlier than existing techniques since resolution is no longer dependent on the decrement result. Furthermore, accurate branch prediction during the last iteration of the loop is enabled. The earlier resolution is a result of de-coupling the resolution logic from the branch execution by performing these steps in parallel. The resolution checks if the value of counter is “1” in parallel to the decrement of the counter. Also, branch prediction is enhanced by informing the branch prediction unit when the counter value reaches a threshold (greater than 0). The threshold value is dependent on implementation and may vary between value of 1 to 4 depending on how many unresolved branches are allowed. Unresolved or outstanding branches refers to the branches that have be decoded but not yet resolved. The threshold detection is used by branch prediction logic to predict correctly during the last iteration when the counter reaches a value of 0. The enhancements on the loop branches do not affect the cycle time of the processor or impact any other aspect of the micro-architecture.  
         [0034]    Embodiments of the invention result in the saving of one cycle each time a loop branch instruction is executed, and result in accurate branch prediction for the last iteration. These performance improvements are helpful for in-order, super-scalar pipeline processors such as the IBM z900 processor.  
         [0035]    While preferred embodiments have been shown and described, various modifications and substitutions may be made thereto without departing from the spirit and scope of the invention. Accordingly, it is to be understood that the present invention has been described by way of illustration and not limitation.