Patent Publication Number: US-7711934-B2

Title: Processor core and method for managing branch misprediction in an out-of-order processor pipeline

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is related to commonly owned U.S. application Ser. No. 11/261,655, filed on Oct. 31, 2005, entitled “Processor Core And Method For Managing Program Counter Redirection In An Out-Of-Order Processor Pipeline,” which is incorporated herein by reference in its entirety. 
     FIELD OF THE INVENTION 
     The present invention relates generally to microprocessors. More particularly, it relates to a microprocessor having an out-of-order processor pipeline. 
     BACKGROUND OF THE INVENTION 
     Processor pipelining is a known technique used to make microprocessors operate more quickly. This technique enables a microprocessor to work on different steps of an instruction at the same time and thereby take advantage of parallelism that exists among the steps needed to execute an instruction. As a result, a microprocessor can execute more instructions in a shorter period of time. 
     Many microprocessors, especially those used in the embedded market, are relatively simple in-order machines. As a result, they are subject to data hazard stalls. More complex microprocessors have out-of-order pipelines, which allow execution of instructions to be scheduled around hazards that would stall an in-order processor pipeline. 
     Speculation is used to resolve branch instructions and predict whether a conditional branch is taken or not taken in an out-of-order machine. When a branch resolution results in a misprediction, all younger instructions in a program stream must be cleared from the pipeline. Conventionally, this is accomplished using an age-based comparison technique across the entire processor pipeline. While this conventional technique works for its intended purpose, it requires maintaining and updating a number of register renaming maps, especially in microprocessors that employ a pipeline having a large number of processing stages. 
     What is needed is a new technique for clearing an out-of-order pipeline of a microprocessor following a branch misprediction, which overcomes the deficiencies noted above. 
     BRIEF SUMMARY OF THE INVENTION 
     The present invention provides a processor core and a method for managing branch misprediction in an out-of-order processor pipeline. In one embodiment, the pipeline of the processor core includes a front-end instruction fetch portion, a back-end instruction execution portion, and pipeline control logic. Operation of the instruction fetch portion is decoupled from operation of the instruction execution portion. Following detection of a control transfer misprediction, at least one signal generated in the instruction execution portion of the processor pipeline causes pipeline control logic to clear/invalidate instructions residing in the instruction fetch portion and halt the flow of instructions from the instruction fetch portion to the instruction execution portion of the pipeline. Operation of the instruction execution portion continues until the control transfer instruction associated with the misprediction reaches a selected stage of the instruction execution portion of the processor pipeline. When the instruction associated with the misprediction reaches the selected stage, pipeline control logic clears/invalidates instructions residing in the instruction execution portion of the pipeline. The flow of instructions from the instruction fetch portion to the instruction execution portion of the processor pipeline is restarted after pipeline control logic clears/invalidates instructions residing in the instruction execution portion of the processor pipeline. 
     In one embodiment, an instruction fetch portion of a pipeline of a processor core according to the present invention includes a program counter selector, an instruction buffer, and a branch predictor. The program counter selector selects addresses/program counter values used to fetch instructions from memory. If a fetched instruction is a control transfer instruction such as, for example, a branch instruction or a jump instruction, the branch predictor predicts whether a conditional branch associated with the instruction is taken or not taken. The instruction buffer stores fetched instructions until they are selected for execution by an instruction execution portion of the pipeline. 
     In one embodiment, an instruction execution portion of a pipeline of a processor core according to the present invention includes an instruction decoder, an instruction identification generator, a buffer, an arithmetic logic unit, and a mispredict instruction identification checker. The instruction decoder decodes instructions read from an instruction buffer. The instruction identification generator associates or assigns instruction identification tags to instructions. The instruction identification tags are used by the mispredict instruction identification checker to determine a program order of a first control transfer instruction relative to a second control transfer instruction. The buffer of the instruction execution portion of the pipeline stores decoded instructions until they are executed by the arithmetic logic unit. If a decoded instruction is a control transfer instruction such as, for example, a branch instruction or a jump instruction, the arithmetic logic unit determines whether a branch prediction made by a branch predictor residing in an instruction fetch portion of the pipeline is correct. If the prediction is incorrect, the mispredict instruction identification checker compares the instruction&#39;s identification tag to an identification tag and/or a valid bit stored in a register of the mispredict instruction identification checker to determine if the instruction is permitted to redirect the instruction fetch portion of the pipeline. 
     In one embodiment of the present invention, the processor core is capable of executing instructions from multiple program threads. 
     In one embodiment of the present invention, the processor core is capable of executing instructions having different bit-widths (e.g., instructions having 16-bits, 32-bits, et cetera). 
     In one embodiment of the present invention, the processor core includes a pipeline that includes multiple parallel processing paths. 
     Further embodiments, features, and advantages of the present invention, as well as the structure and operation of the various embodiments of the present invention, are described in detail below with reference to the accompanying drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS/FIGURES 
       The accompanying drawings, which are incorporated herein and form a part of the specification illustrate the present invention and together with the description further serve to explain the principles of the invention and to enable a person skilled in the pertinent art to make and use the invention. In the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit of the reference number indicates a drawing in which the reference number first appears. 
         FIG. 1  is a diagram of a processor core according to a first embodiment of the present invention. 
         FIG. 2  is a diagram of a mispredict instruction identification checker according to an embodiment of the present invention. 
         FIG. 3  is a diagram of an instruction fetch portion of a processor pipeline according to an embodiment of the present invention. 
         FIG. 4  is a diagram of an instruction execution portion of a processor pipeline according to an embodiment of the present invention. 
         FIG. 5  is a diagram illustrating the association of instruction identification tags with instructions according to an embodiment of the present invention. 
         FIG. 6  is a flowchart of a method for clearing/invalidating a processor pipeline according to an embodiment of the present invention. 
         FIGS. 7A and 7B  are a flowchart of a method for controlling program counter redirection in an out-of-order processor pipeline according to an embodiment of the present invention. 
         FIG. 8  is a diagram of a processor core according to a second embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention provides a processor core and a method for managing branch misprediction in an out-of-order processor pipeline. In the detailed description of the invention that follows, references to “one embodiment”, “an embodiment”, “an example embodiment”, etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to effect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described. 
       FIG. 1  is a diagram of a microprocessor  100  according to an embodiment of the present invention. Microprocessor  100  includes a processor core  102 , instruction memory  104 , and a register file  106 . Processor core  102  has a pipeline that includes an instruction fetch portion  108  and an instruction execution portion  110 . 
     As shown in  FIG. 1 , instruction fetch portion  108  of processor core  102  includes a program counter (PC) selector  112 , an optional recoder  114 , and an instruction buffer  116 . Instruction fetch portion  108  also includes a branch predictor  118  and a portion of pipeline control logic  120 . 
     Program counter selector  112  selects an address or program counter value to be used to fetch a program instruction from memory. In one embodiment, PC selector  112  can select a sequentially incremented program counter value, a redirect program counter value, or a program counter value for a new program thread. PC selector  112  receives one or more signals generated by pipeline control logic  120  and/or a mispredict instruction identification checker  134 , which cause PC selector  112  to select a redirect program counter value following a branch misprediction associated with a control transfer instruction. 
     Processor core  102  is preferably capable of executing both a standard width instruction (e.g., a 32-bit instruction) and a compressed-format width instruction (e.g., a 16-bit instruction). Accordingly, in one embodiment, processor core  102  includes optional recoder  114 . If a compressed-format instruction is fetched from instruction memory  104 , it is recoded by recoder  114  to a format width that can be decoded by decoder/renamer  122  and executed by arithmetic logic unit  126 . In one embodiment, both standard width instructions and compressed-format width instructions are recoded by recoder  114  to an instruction width having more bits than a standard width instruction. Instructions are passed from optional recoder  114  to instruction buffer  116 . 
     Instruction buffer  116  is capable of holding multiple instructions. In one embodiment, in which processor core  102  implements multithreading, instructions from different program threads are stored, for example, in separate portions of instruction buffer  116 . Multithreading refers to an ability of an operating system to execute different parts of a program, called threads, simultaneously. In another embodiment, in which processor core  102  implements multithreading, instructions from different program threads are stored in separate instruction buffers, for example, one instruction buffer for each program thread. 
     In instances where a control transfer instruction such as, for example, a branch instruction or a jump instruction, is fetched from instruction memory  104 , branch predictor  118  predicts whether a conditional branch associated with the control transfer instruction is taken or not taken. Any known branch prediction algorithm can be used. In one embodiment, branch predictor  118  includes a branch prediction table that is used in predicting whether a conditional branch is taken or not taken. 
     Instruction fetch portion  108  of processor core  102  preferably fetches multiple instructions per fetch cycle. 
     Instruction execution portion  110  of processor core  102  includes a decoder/renamer  122 , a buffer  124 , an arithmetic logic unit (ALU)  126 , and a completion buffer  128 . A scheduler  130  dynamically schedules instructions for execution by instruction execution portion  110  of processor core  102 . Also included in instruction execution portion  110  are an instruction identification generator  132 , a mispredict instruction identification checker  134  that includes a register  136 , and a portion of pipeline control logic  120 . 
     Instructions are read from instruction buffer  116  and decoded by decoder/renamer  122 . Decoder/renamer  122  performs the functions of decoding instructions and updating a register renaming map (not shown). During the decoding/renaming process, each instruction is associated with/assigned an instruction identification tag. The instruction identification tags are generated by instruction identification generator  132 . 
     In one embodiment, the instruction identification tags are sequentially generated multi-bit values. The number of bits that are generated is dependent on how many instructions are executed simultaneously within instruction execution portion  110  of processor core  102 . In one embodiment, in which processor core  102  performs multithreading, instruction identification tags are generated and assigned on a per thread basis. 
     Instructions are read from buffer  124  and executed by arithmetic logic unit  126  in accordance with a schedule determined by scheduler  130 . Scheduler  130  schedules instructions for execution once their operands are ready and preferably in accordance with their age. Results in arithmetic logic unit  126  are written to completion buffer  128  and stored until instructions graduate and their results are written to register file  106 . The register renaming map (not shown) is updated when an instruction graduates. As will be understood by persons skilled in the relevant arts given the description herein, the present invention eliminates the need to save multiple renaming map states, which are required by conventional out-of-order processors for every renamed instruction. 
     During execution of a control transfer instruction such as, for example, a branch instruction or a jump instruction, arithmetic logic unit  126  determines whether a branch prediction made by branch predictor  118  is correct. If the prediction is incorrect, mispredict instruction identification checker  134  compares the instruction&#39;s identification tag to an identification tag and/or a valid bit stored in register  136  of mispredict instruction identification checker  134  to determine if the instruction is permitted to redirect instruction fetch portion  108  of processor core  102 . As described in more detail below, if the result of the comparison indicates that the control transfer instruction was issued out-of-program-order relative to a second control transfer instruction that mispredicted, and that is awaiting graduation, then mispredict instruction identification checker  134  will enable the control transfer instruction currently being considered to redirect instruction fetching. 
     Instruction memory  104  is any memory accessible to processor core  102  such as, for example, an instruction cache, a scratch pad, a loop buffer, et cetera. In one embodiment, memory  104  includes multiple memories and/or multiple types of memories. 
     Register file  106  includes a plurality of general purpose registers (not shown), which are visible to a programmer. 
     Operation of instruction fetch portion  108  of the pipeline of processor core  102  is decoupled from operation of instruction execution portion  110 . Following detection of a conditional branch/control transfer misprediction, at least one signal generated in instruction execution portion  110  causes pipeline control logic  120  to clear/invalidate instructions residing in instruction fetch portion  108 . Additionally, the flow of instructions from instruction fetch portion  108  to instruction execution portion  110  of the pipeline is halted. Operation of instruction execution portion  110  continues until a control transfer instruction associated with a misprediction reaches a selected stage of instruction execution portion  110  of the processor pipeline. When the instruction associated with the misprediction reaches the selected stage, pipeline control logic  120  clears/invalidates instructions residing in instruction execution portion  110 . The flow of instructions from instruction fetch portion  108  to instruction execution portion  110  is enabled/restarted after pipeline control logic  120  clears/invalidates instructions residing in instruction execution portion  110  of the pipeline. 
     In one embodiment, in which processor core  102  performs multithreading, pipeline control logic  120  only clears/invalidates instructions belonging to the program thread associated with the misprediction. Instructions are cleared/invalidated, for example, by changing a valid bit or tag associated with each instruction to indicate that the instructions are no longer valid instructions. Invalid instruction are prevented from writing their results to register file  106 . 
       FIG. 2  is a more detailed diagram of mispredict instruction identification checker  134 . As shown in  FIG. 2 , mispredict instruction identification checker  134  includes compare logic  200  and a register  136  that includes an instruction identification tag portion  202  and a valid portion  204 . In one embodiment, in which processor core  102  supports multithreading, a register  136  is maintained for each program thread. 
     Mispredict instruction identification checker  134  is used to determine whether a current control transfer instruction being executed by arithmetic logic unit  126  is permitted to redirect instruction fetch portion  108  of the pipeline of processor core  102 . In one embodiment, following detection of a conditional branch misprediction associated with the current control transfer instruction, compare logic  200  of mispredict instruction identification checker  134  compares the instruction identification tag of the current control transfer instruction to values residing in register  136  of mispredict instruction identification checker  134 . If the valid portion  204  of register  136  is set (e.g., contains a valid bit equal to one), register  136  contains the instruction identification tag of an earlier executed control transfer instruction that was involved in a branch misprediction and that has not yet graduated. In this case, if the current control transfer instruction is determined to precede the earlier control transfer instruction in program order, based on the instruction identification tag comparison, register  136  is updated to contain the instruction identification tag of the current control transfer instruction and the current control transfer instruction is permitted to redirect instruction fetching. If however the earlier control transfer instruction is determined to precede the current control transfer instruction in program order, register  136  is not updated to contain the instruction identification tag of the current control transfer instruction, and the current control transfer instruction does not redirect instruction fetching. If the valid portion  204  of register  136  is reset (e.g., contains a valid bit equal to zero), the instruction identification tag of the current control transfer instruction is stored in register  136  and the current control transfer instruction is permitted to redirect instruction fetch portion  108 . 
     When a control transfer instruction graduates and its instruction identification tag is stored in register  136 , the valid portion  204  of register  136  is reset so that a control transfer instruction occurring later in program order will be permitted to redirect instruction fetching following detection of a branch misprediction. In one embodiment, if an instruction identification tag of a graduating control transfer instruction matches the identification tag held in register  136 , a valid bit in register  136  is reset/cleared. 
     Generally speaking, when a conditional branch misprediction associated with a control transfer instruction is detected by arithmetic logic unit  126 , the control transfer instruction should be permitted to redirect instruction fetching. This is not the case, however, if the control transfer instruction (e.g., instruction BNE- 2  shown in  FIG. 5 ) follows in program order another control transfer instruction (e.g., instruction BNE- 1  shown in  FIG. 5 ) that has redirected instruction fetching but that has not yet graduated. Assuming that both control transfer instructions (BNE- 1  and BNE- 2 ) belong to a single program thread, redirection by the second control transfer instruction (BNE- 2 ) is not required and should be suppressed. 
     The operation of processor core  102  will now be described in more detail with reference to  FIGS. 3-5 . As will become apparent to persons skilled in the relevant art(s) given the description herein, the present invention permits an early restart of instruction fetch operations following a branch misprediction. The present invention also eliminates any need for an explicit age-based comparison of instructions across the entire pipeline of a microprocessor and the need for maintaining multiple renaming map states. 
       FIG. 3  is a diagram illustrating one embodiment of instruction fetch portion  108  of processor core  102 . In the embodiment shown in  FIG. 3 , instruction fetch portion  108  includes five pipeline stages. These five pipeline stages are illustrative and not intended to limit the present invention. In other embodiments, instruction fetch portion  108  can have more or less than 5 pipeline stages. The number of pipeline stages that are implemented in any embodiment of the present invention is a design choice. 
     As shown in  FIG. 3 , the five pipeline stages of instruction fetch portion  108  are stage  302  (select program counter), stage  304  (check instruction tags), stage  306  (fetch instruction), stage  308  (recode instruction if required), and stage  310  (write instruction to instruction buffer). 
     In stage  302 , PC selector  112  selects amongst a variety of program counter values to be used to fetch an instruction from instruction memory  104 . In one embodiment, the program counter value selected can be the program counter value of a new program thread, the next sequential program counter value for an existing program thread, or a redirect program counter value associated with a branch instruction or a jump instruction. 
     In stage  304 , the instruction tags associated with an instruction to be fetched from instruction memory  104  are checked. In one embodiment, the instruction tags contain precode bits for each instruction indicating instruction type. If these precode bits indicate that an instruction is a control transfer instruction, a branch history table is accessed and used to determine whether the control transfer instruction is likely to branch or likely not to branch. 
     In stage  306 , one or more instructions are fetched from instruction memory  104 . In one embodiment, if a fetched control transfer instruction is predicted as not likely to branch, computation of a conditional branch target address for the instruction is started during stage  306 . 
     In stage  308 , any compressed-format instructions are recoded into a format that can be decoded and executed by instruction execution portion  110  of processor core  102 . For example, in one embodiment in which processor core  102  executes both 16-bit instructions and 32-bit instructions, any 16-bit compressed-format instructions are recoded by recoder  114  to form instructions having 32 bits. In another embodiment, recoder  114  recodes both 16-bit instructions and 32-bit instructions to a format having more than 32 bits. 
     In stage  310 , instructions are written to instruction buffer  116 . In one multithreading embodiment, processor core  102  includes one instruction buffer for each program thread. In this embodiment, instructions associated with a particular program thread are written into an instruction buffer reserved for the particular program thread. In one embodiment, stage  310  can be bypassed and instructions can be dispatched directly to decoder/renamer  122 . 
       FIG. 4  is a diagram illustrating one embodiment of instruction execution portion  110  of processor core  102 . In the embodiment shown in  FIG. 4 , instruction execution portion  110  includes five pipeline stages. These five pipeline stages are illustrative and not intended to limit the present invention. Other embodiments have more or less than five pipeline stages. 
     As shown in  FIG. 4 , the five pipeline stages of instruction execution portion  110  are stage  402  (read from instruction buffer), stage  404  (decode instruction), stage  406  (execute instruction), stage  408  (write to completion buffer), and stage  410  (write to register file). 
     In stage  402 , instructions are read from instruction buffer  116 . In one embodiment that uses delay slots following a branch instruction, a branch instruction and its delay slot are always read together in stage  402 . As described herein, following resolution of a branch misprediction, the ability to read instructions from instruction buffer  116  may be temporarily halted until selected instructions residing within instruction execution portion  110  of the pipeline are cleared/invalidated by pipeline control logic  120 . 
     In stage  404 , instructions are decoded. In parallel with decoding, register renaming map(s) are updated and used to determine whether required source operands are available, for example, in register file  106  and/or completion buffer  128 . A register renaming map is a structure that holds the mapping information between programmer visible architectural registers and internal physical registers. Register renaming map(s) indicate whether data is available and where data is available. In one embodiment, the register renaming map(s) also include an active bit that indicates whether a latest producer, if there is one, of a corresponding general purpose register has been issued into the pipeline or not. In one embodiment, in which processor core  102  includes accumulation registers, a separate renaming map is maintained for the accumulation registers. This renaming map is similar to the renaming map maintained for general purpose registers. 
     Instructions in stage  404  receive a completion buffer identification tag and an instruction identification tag. The completion buffer identification tag determines the location in completion buffer  128  where arithmetic logic unit  126  can write calculated results for an instruction. In one embodiment, each instruction identification tag is a thread-specific sequentially generated value that uniquely determines the program order of instructions residing in instruction execution portion  110  of processor core  102 . At the end of stage  404 , decoded instructions are placed in buffer  124 . Scheduler  130  then selects instructions residing in buffer  124  for execution by arithmetic logic unit  126 . 
     In stage  406 , instructions are executed by arithmetic logic unit  126  and control transfer instructions such as, for example, branch instructions and jump instructions are resolved. For control transfer instructions, resolved paths are compared against predicted paths. If a misprediction has occurred, and redirection is required, the correct address is provided to instruction fetch portion  108  of processor core  102 , the branch history table is updated, and instruction fetch portion  108  is redirected to start fetching instructions from the redirect address (program counter value). In one embodiment, selected instructions such as, for example, floating point instructions are processed by a coprocessor (not shown) coupled to arithmetic logic unit  126 . 
     In one embodiment of the present invention, an adder in the arithmetic logic unit  126  is used to compute both a target address and a fall through address. Arithmetic logic unit  126  compares the branch outcome and determines the direction of the branch, which is compared to the predicted direction. If there is a misprediction, the instruction execution portion  110  signals instruction fetch portion  108  of the misprediction and provides instruction fetch portion  108  with the correct prediction. In embodiments of the present invention, depending on the type of control transfer instruction involved in a misprediction, instruction fetch portion  108  may either immediately restart fetching, stall until pipeline control logic  120  invalidates selected instructions in the pipeline once the control transfer instruction involved in the misprediction reaches a selected stage in the pipeline (e.g., upon instruction graduation), or instruction fetch portion  108  may stall and wait for a restart signal from instruction execution portion  110 . In each case, the control transfer instruction involved in the misprediction is preferably marked mispredicted, and it continues to flow through the pipeline eventually carrying this status to completion buffer  128 . 
     Because branch instructions can be issued out-of-order in instruction execution portion  110 , mispredict instruction identification checker  134  keeps track of the instruction identification tag of the last redirected branch. If a new resolution results in a mispredict, the identification tag of the new branch instruction is compared against the identification tag of the last redirected branch that has not yet graduated. If the program order of the new branch is prior to the previous branch, the instruction fetch portion  108  is redirected according to the new branch instruction. Register indirect jumps, which have been predicted with a return stack are also compared against the real register value in stage  406 . If there is a mispredict, the correct target is sent to instruction fetch portion  108 . 
     The results of branch decisions are prioritized and communicated to instruction fetch portion  108  of the pipeline during stage  406 . In addition to the branch redirects, there can be redirects from graduating instructions. These redirects are prioritized over the branch redirects and a final redirect is forwarded to PC selector  112  of instruction fetch portion  108  via pipeline control logic  120 . A valid redirect will cause instruction fetch portion  108  to clear/invalidate its current fetch stream of all instructions in instruction fetch portion  108  associated with the redirect. A new fetch is started with the newly received target address. 
     In stage  408 , results generated by arithmetic logic unit  126  and/or a coprocessor are written to completion buffer  128 . As noted above, instructions that are accepted into instruction execution portion  110  of processor core  102  are assigned a completion buffer identification number. 
     In one embodiment, the assignment of completion buffer identification numbers is done using a free list. The free list contains as many entries as the number of entries in each completion buffer. In one embodiment, up to two entries can be read from and written to the free list, for example, every cycle during normal operation. Following a branch mispredict, however, all the entries may be released and data written into the free list. Additionally, in multithreading embodiments, particular program threads can be released and data written into the free list without effecting entries for other program threads. Because of this requirement, the free list preferably is not implemented as a simple stack. 
     In one embodiment, the free list is implemented using a bitmap to represent the entries in completion buffer  128 . A first bit of the bitmap indicates whether the completion buffer entry is either available (e.g., if the bit has a value of one) or unavailable (e.g., if the bit has a value of zero). In a multithreading embodiment, if completion buffer identification numbers are assigned regardless of a thread content to which an instruction belongs, instruction identification tags are preferably assigned on a per thread basis. In one embodiment, an instruction identification tag is assigned to all incoming instructions regardless of whether the instructions write to a destination register. 
     Assigned completion buffer identification numbers are written into a graduation first-in, first-out buffer at a location identified by a write pointer and/or a write pointer plus an offset value. Completion buffer completion bits associated with newly renamed instructions are reset/cleared to indicate incomplete results. As instructions complete execution, their corresponding completion buffer completion bits are set, thereby enabling the instructions to graduate and release their associated completion buffer identification numbers. Pipeline control logic  120  ensures that one thread content does not consume more than its share of completion buffer entries. 
     In one embodiment of the present invention, separate structures are used to hold the program counter and other attributes of instructions that need not be piped along with the instruction at every stage of the processor pipeline. One such structure is a program counter completion buffer, which can be implemented as a field in completion buffer  128  and managed using read and write pointers. 
     As noted herein, register renaming is done for destination registers to remove output dependencies and to ensure there is a single producer of a given register in processor core  102  at any given time. The source registers are renamed so that data is obtained from a producer at the earliest opportunity instead of waiting for the processor core&#39;s architectural state to be updated. This also aids in reducing dependency check complexity in any coprocessor coupled, for example, to arithmetic logic unit  126 . 
     In stage  410 , results from completion buffer  128  are written to register file  106  as instructions graduate and register renaming map(s) are updated. Each instruction preferably graduates according to program order. 
     Control transfer instructions such as, for example, branch instructions and jump instructions require special processing in order to allow these instructions to graduate in program order. As noted herein, control transfer instructions are preferably resolved during stage  406  of the processor pipeline. However, some control transfer instructions such as, for example, some branch instructions cannot be resolved until stage  410  because of a need for an architectural condition evaluation. Coprocessor conditional branch instructions, for example, are evaluated at graduation. This is due to the fact that arithmetic logic unit  126  may not have access to floating point generated information. In case of a misprediction, the redirection program counter is read from a completion buffer written to by the floating point coprocessor. This program counter is then sent to the instruction fetch portion  108  on a mispredict. 
     As a part of instruction graduation, information pertaining to each instruction that is stored in completion buffer  128  and/or a graduation first-in/first-out buffer is read. The read information includes both data and status information. The data information corresponds, for example, to results calculated by arithmetic logic unit  126  and/or a coprocessor coupled to arithmetic logic unit  126 . The status information includes, for example, completion status, exception information, branch resolution information, et cetera. Data read from completion buffer  128  is committed to an architecturally visible general purpose register (register file  106 ) if no flush and redirect due to an exception or other special case is required. If a redirect of the program counter is required, pipeline control logic  120  generates signals needed to accomplish the redirect. 
     In one embodiment, when a control transfer instruction reaches the head of a first-in first-out buffer, all instructions that belong to that program thread are invalidated in instruction execution portion  110  of the pipeline. The fetch instruction portion does not have to invalidate instructions that belong to the program thread at this point in time as any instruction that needed to be invalidated would have been invalidated when the misprediction was first identified. 
     In one embodiment of the present invention, branch likely instructions are handled differently due to their particular behavior. Instruction fetch portion  108  fetches an issued instruction according to the architectural specification. However, if there is a mispredict, instruction fetch portion  108  is required to replay the branch instruction sequence with the correct prediction. The branch is marked mispredicted, and it flows through the pipeline eventually carrying this status to completion buffer  128 . When the branch instruction eventually reaches the head of a first-in first-out buffer, all instructions that belong to that program thread are invalidated in the instruction execution portion  110  of the pipeline, and redirection information (e.g., a replay address from the program counter completion buffer) is sent to instruction fetch portion  108 . This causes a replay of the branch likely instruction using a corrected prediction. 
       FIG. 5  illustrates two tables  502  and  504  that illustrate how instruction identification tags can be assigned to instructions in a way that allows the instruction identification tags to be used to identify a program order of one instruction relative to another instruction. Table  502  illustrates seven instructions, in program order, fetched from addresses  1  through  7 . Table  504  shows a possible execution order for the same seven instructions along with assigned instruction identification tags that identify the instructions&#39; program order. 
     As can be seen from a review of tables  502  and  504 , there are two branch instructions. Branch-if-not-equal instruction  1  (BNE- 1 ) and branch-if-not-equal instruction  2  (BNE- 2 ). Due to out-of-order processing by processor core  102 , two issue scenarios are possible. The two branch instructions can be issued either in-order or out-of-order. As described herein, if the branch instructions are issued in-order and both instructions are assigned incorrect branch predictions by branch predictor  118 , the second branch instruction (BNE- 2 ) should be suppressed from redirecting instruction fetch portion  108  because this branch instruction was issued incorrectly on a speculative basis and the first branch instruction (BNE- 1 ) will have already provided instruction fetch portion  108  of the pipeline with the correct redirection. 
     Two method embodiments of the present invention will now be described with regards to  FIGS. 6 ,  7 A, and  7 B. 
       FIG. 6  depicts a flowchart of a method  600  for clearing a processor pipeline according to an embodiment of the present invention. As shown in  FIG. 6 , method  600  includes five steps  602 ,  604 ,  606 ,  608 , and  610 . Method  600  is capable of being implemented, for example, using processor core  102  described above, but it is not limited to being implemented in processor core  102 . 
     In step  602 , a conditional program counter redirect misprediction is detected during execution of a control transfer instruction. The misprediction is detected in an instruction execution portion of a processor pipeline such as, for example, instruction execution portion  110  of processor core  102  described above. 
     In step  604 , movement of instructions from an instruction fetch portion of the processor pipeline to the instruction execution portion of the processor pipeline is halted in response to the conditional program counter redirect misprediction. Operation of the instruction fetch portion of the pipeline is decoupled from operation of the instruction execution portion of the pipeline. This allows, for example, the instruction execution portion of the pipeline to continue operating while the instruction fetch portion is halted. 
     In step  606 , instructions residing within the instruction fetch portion of the processor pipeline are invalidated. In one embodiment, all instructions residing in the instruction fetch portion are invalidated. In another embodiment, only instructions belonging to the same program thread as the control transfer instruction associated with the misprediction are invalidated. Instructions can be invalidated, for example, by changing a validity bit associated with each instruction to show the instruction is no longer a valid instruction. Instruction fetching is preferably restarted at a redirected address as soon as instructions residing within the instruction fetch portion of the processor pipeline have been invalidated. 
     In step  608 , once the control transfer instruction associated with the misprediction has reached a selected stage within the instruction execution portion of the processor pipeline, instructions residing within the instruction execution portion of the processor pipeline are invalidated. In one embodiment, all instructions residing in the instruction execution portion are invalidated. In another embodiment, only instructions belonging to the same program thread as the control transfer instruction associated with the misprediction are invalidated. In one embodiment, the selected stage is a stage prior to instruction graduation. 
     In step  610 , movement of instructions from the instruction fetch portion of the processor pipeline to the instruction execution portion of the processor pipeline is restarted. 
       FIGS. 7A and 7B  depict a flowchart of a method  700  for controlling program counter redirection in an out-of-order processor pipeline according to an embodiment of the present invention. As shown in  FIGS. 7A and 7B , method  700  includes six steps  702 ,  704 ,  706 ,  708 ,  710 , and  712 . Method  700  is capable of being implemented, for example, using processor core  102  described above, but it is not limited to being implemented in processor core  102 . 
     In step  702 , a first instruction identification tag is associated with a first control transfer instruction and a second instruction identification tag is associated with a second control transfer instruction. These tags are associated at a first stage in an out-of-order processor pipeline. The first instruction identification tag and the second instruction identification tag identify a program order of the first control transfer instruction relative to the second control transfer instruction. 
     In step  704 , a first conditional program counter redirect misprediction is detected during execution of the first control transfer instruction. The detection occurs in a second stage of the processor pipeline. 
     In step  706 , the first instruction identification tag is stored in a register of a mispredict instruction identification checker. 
     In step  708 , a second conditional program counter redirect misprediction is detected during execution of the second control transfer instruction. This second misdirection is detected in the second stage of the processor pipeline. 
     In step  710 , the second instruction identification tag is compared to the first instruction identification tag stored in the register of the mispredict instruction identification checker. 
     In step  712 , if the comparison of the second instruction identification tag to the first instruction identification tag indicates that the second control transfer instruction executed out of program order relative to the first control transfer instruction, a program counter redirect enable signal is generated. The program counter redirect enable signal causes an instruction fetch portion of the processor pipeline to fetch instructions according to the second control transfer instruction. 
       FIG. 8  is a diagram of a microprocessor  800  according to another embodiment of the present invention. Microprocessor  800  includes a processor core  802 , instruction memory  104 , and a register file  106 . Processor core  802  has a pipeline that includes an instruction fetch portion  808  and an instruction execution portion  810 . 
     As shown in  FIG. 8 , instruction fetch portion  808  of processor core  802  includes a program counter (PC) selector  112 , an optional recoder  114 , and an instruction buffer  116 . Instruction fetch portion  808  also includes a branch predictor  118  and a portion of pipeline control logic  820 . 
     Instruction execution portion  810  of processor core  802  includes a decoder/renamer  122 , two buffers  124   a  and  124   b , two arithmetic logic units (ALUs)  126   a  and  126   b , and two completion buffers  128   a  and  128   b . A scheduler  830  dynamically schedules instructions for execution by one of the two parallel pipelines of instruction execution portion  810  of processor core  802 . Also included in instruction execution portion  810  are at least one instruction identification generator  132 , at least one mispredict instruction identification checker  134  that includes at least one register  136 , and a portion of pipeline control logic  820 . 
     Microprocessor  800  operates similarly to microprocessor  100  except that microprocessor  800  includes two parallel instruction execution pipelines. These two instruction execution pipelines can be similar, or they can be specialized to execute selected instructions. In one embodiment, the pipeline represented by buffer  124   a , arithmetic logic unit  126   a , and completion buffer  128   a  is used to execute control transfer instructions. This eliminates the need for having more than one mispredict instruction identification checker  134 . 
     While the foregoing is a complete description of exemplary embodiments of the invention, it should be evident that various modifications, alternatives, and equivalents may be made and used. It is also to be appreciated that the detailed description of the present invention provided herein, and not the summary and abstract sections, is intended to be used to interpret the claims. The summary and abstract sections may set forth one or more but not all exemplary embodiments of the present invention as contemplated by the inventors. 
     For example, in addition to implementations using hardware (e.g., within or coupled to a Central Processing Unit (“CPU”), microprocessor, microcontroller, digital signal processor, processor core, System on Chip (“SOC”), or any other programmable or electronic device), implementations may also be embodied in software (e.g., computer readable code, program code, instructions and/or data disposed in any form, such as source, object or machine language) disposed, for example, in a computer usable (e.g., readable) medium configured to store the software. Such software can enable, for example, the function, fabrication, modeling, simulation, description, and/or testing of the apparatus and methods described herein. For example, this can be accomplished through the use of general programming languages (e.g., C, C++), GDSII databases, hardware description languages (HDL) including Verilog HDL, VHDL, and so on, or other available programs, databases, and/or circuit (i.e., schematic) capture tools. Such software can be disposed in any known computer usable medium including semiconductor, magnetic disk, optical disk (e.g., CD-ROM, DVD-ROM, etc.) and as a computer data signal embodied in a computer usable (e.g., readable) transmission medium (e.g., carrier wave or any other medium including digital, optical, or analog-based medium). As such, the software can be transmitted over communication networks including the Internet and intranets. 
     It is understood that the apparatus and method embodiments described herein may be included in a semiconductor intellectual property core, such as a microprocessor core (e.g., embodied in HDL) and transformed to hardware in the production of integrated circuits. Additionally, the apparatus and methods described herein may be embodied as a combination of hardware and software. Thus, the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalence.