Branch Recovery Mechanism to Reduce Processor Front End Stall Time by Providing Path Information for Both Correct and Incorrect Instructions Mixed in the Instruction Pool

The present invention relates to instruction pipelines in a processor, and more particularly, to an improved mechanism for recovering from a mispredicted branch.

In an effort to speed processor execution, prefetcher's were incorporated in the Intel x86 processor family (e.g., 8086, 80186, 80286, 80386, 80486). The prefetcher works on the assumption that the execution unit will want the next instruction from the next sequential memory location. While the execution unit is executing an instruction, the prefetcher takes advantage of idle bus time to fetch the next sequential instruction from memory and place this instruction in the processor's prefetch queue. This technique works fine for non-branch instructions. However, whenever a jump or branch instruction is encountered, the entire prefetch queue must be flushed and reloaded with the correct instructions, thereby slowing the processor.

The Pentium and Pentium Pro processor from Intel Corp. added branch prediction logic to permit the prefetcher to make more intelligent decisions regarding what information to prefetch from memory. The instruction pipeline 10 of the Pentium Pro processor is illustrated in FIG. 1 and includes eleven stages, including Instruction Fetch Units 12 (IFU1, IFU2, IFU3), Decode stages 14 (DEC1, DEC 2), the Register Alias Table and Allocator stage 16 (RAT), the ReOrder Buffer 18 (ROB) (also known as the instruction pool), the Dispatch stage 20 (DIS), the Execution stage (EX) 22, and the Retirement stages 24 (RET1, RET2).

The first seven stages of the instruction pipeline 10 (fetch 12, decode 14, RAT 14 and ROB 16 stages) are known as the In-Order Front End section 30 of the processor because the instructions are kept in strict program order. The Dispatch stage 20 and the Execution stage 22 are known as the Middle Out-of-Order section 32 of the processor because micro-ops can be executed in any order. The Retirement stages 24 are also known as the In-Order Rear End section 34 of the processor because micro-ops are retired in program order.

FIG. 2 illustrates the operation of the instruction pipeline of the Pentium Pro processor. The instructions are fetched by the Instruction Fetch Units 12 (FIG. 1) and placed into a prefetch streaming buffer 40. The instructions are decoded into micro-ops by the Decode stages 14 and stored in the instruction decode queue (ID Queue) 42. The micro-ops are then moved into the ROB (or instruction pool) 18 in strict program order to await execution.

The ROB 18 is a circular buffer with 40 entries and includes a start-of-buffer pointer and an end-of-buffer pointer. The start of buffer pointer points to the oldest (unretired) micro-op in the ROB 18. The end-of-buffer pointer points to where the next micro-op will be stored in the ROB 18. Initially the ROB 18 is empty and the start-of-buffer pointer and the end-of-buffer pointer point to the first ROB entry (entry 0). As instructions are decoded into micro-ops (up to three per clock), the micro-ops are placed in the ROB 18 starting at entry 0in strict program order and the end-of-buffer pointer is incremented once for each micro-op.

If any instructions are branches, the fetched memory addresses are provided to a Branch Target Buffer (BTB) for branch prediction. Whenever a branch instruction enters the instruction pipeline, the prediction logic predicts whether the branch will be taken (by examining the execution history of the instruction). The branch prediction is used to load instructions into the In-Order Front End section 30 corresponding to the predicted path.

Once the micro-ops are placed in the ROB (or instruction pool) 18 in strict program order, they are executed one or more at a time, as data and execution units for each micro-op become available. In the Dispatch stage 20 (FIG. 1), each micro-op is copied from the ROB 18 to a Reservation Station if all the data required by the micro-op is available. The micro-op is then dispatched by Dispatch stage 20 to an execution unit when one becomes available. The micro-ops can be executed out of order. Once executed, the results of the micro-ops' execution are stored in the ROB 18 at the ROB entry occupied by the micro-op. As each micro-op in the ROB completes execution, it is marked as ready for retirement.

The retirement stages 24 constantly check the status of the three oldest micro-ops in the ROB 18 to determine when all three of them have been executed and marked as ready for retirement. The micro-ops are then retired (by RET2) in original program order. As each is retired, the micro-op's execution result is committed to architectural state by copying the micro-op's execution result from the ROB entry into the processor's real register set. The respective ROB entry is then deleted or flushed and the start-of-buffer pointer is incremented to point to the oldest unretired micro-op in the ROB 18.

FIG. 3 illustrates the operation of the instruction pipeline 10 of FIG. 1. Instructions are fetched, decoded into micro-ops, and stored in the ROB 18 to await execution. Steps A-C illustrate some examples of the type of operations performed in the instruction pipeline 10. At step A, a micro-op is stored at sequence number 4 in the ROB 18 (ROB entry 4) and the End-of-Buffer pointer 48 is incremented from ROB entry 4 to ROB entry 5 (where the next decoded micro-op will be stored in the ROB 18).

After the micro-op of sequence number 1 (ROB entry 1) has completed execution, the execution result is stored in the ROB entry 1 and ROB entry 1 is marked as executed (a 1 is marked in the Executed bit for ROB entry 1). At step B, the micro-op of ROB entry 1 is retired by copying the micro-op's execution result from ROB entry 1 into the processor's real register set. The micro-op and other information in ROB entry 1 is then deleted and the start-of-buffer pointer 46 is incremented to point to ROB entry 2, which is the oldest (unretired) micro-op in ROB 18. ROB entry 1 is now available to receive a new micro-op.

At step C, the branch micro-op at sequence number 2 is executed and validated. In this example, during validation, it is determined that the branch of sequence number 2 has been incorrectly predicted, and therefore, the instructions that were prefetched and stored in the ROB after the branch entry 2 (micro-ops for ROB entries 3 and 4) are incorrect (were mispredicted). The micro-ops for ROB entries 3 and 4 correspond to the mispredicted path 75. In addition, the instructions in the pipeline stages earlier than the ROB 18 (e.g., the Instruction Fetch Units 12, the prefetch streaming buffer 40, the Decode stages 14, the RAT 16, the ID Queue 42) also correspond to the incorrect path and must be flushed. After flushing the micro-ops in the pipeline stages earlier than the ROB, the instructions corresponding to the correct path are then fetched and decoded. However, the ROB 18 cannot be flushed and the new micro-ops corresponding to the correct path cannot be loaded from the Front End section 30 into the ROB 18 until all instructions prior to and including the mispredicted branch (at ROB entry 2) have been executed and retired. When the mispredicted branch has been retired, then the ROB 18 is flushed or cleared and the micro-ops corresponding to the correct path can be loaded into the ROB 18.

In the example of FIG. 3, there are no unexecuted instructions before the mispredicted branch. Generally, however, because the branch operation may have been executed out of order (before one or more older instructions), the Front End section 30 can stall (wait) at the out of order boundary and cannot load the new (correct path) micro-ops from the Front End section 30 (e.g., Decode stages 14) into the ROB 18 until the mispredicted branch instruction has been retired and the ROB 18 flushed. (The out of order boundary refers to where the in order Front End section 30 meets the out of order Middle section 32). In other words, the Pentium does not mix correct and incorrect micro-ops in the ROB 18.

To determine when the correct path can be loaded into ROB 18, the Retirement stages 24 check the status of the three oldest micro-ops in the ROB 18. When the Retirement stages 24 find that the oldest executed micro-op in the ROB 18 is the mispredicted branch, this indicates that all previous (older) micro-ops have been executed and retired. The mispredicted branch can then be committed to architectural state and retired. The ROB 18 is then completely flushed or cleared and the stall is released. The micro-ops of the correct path are then loaded from the Decode stages 14 into the ROB 18 beginning at the first ROB entry.

In the Pentium processor, the time required to flush and fully reload the Front End section 30 with the correct path was typically greater than the time required for the mispredicted branch to be retired. Therefore, in the Pentium processor, the Front End section 30 of the processor rarely stalled or waited for the mispredicted branch to be retired before reloading the ROB 18 with micro-ops of the correct path.

However, improved techniques have increased the speed of the Instruction Fetch Units 12 and Decode stages 14, thereby, greatly increasing the Front End section 30 stall time after a mispredicted branch. As a result, a need exists for a more efficient technique to recover from a mispredicted branch in order to reduce the Front End stall time.

According to the branch recovery mechanism of the present invention, the problem of Front End stall time can be reduced. According to an embodiment of the branch recovery mechanism of the present invention, a branch instruction is decoded and it is predicted whether the branch will be taken. The branch instruction and one or more instructions corresponding to a predicted path are loaded from a Front End section of an instruction pipeline to an instruction pool. Next, it is determined whether the branch instruction is mispredicted. If the branch instruction is mispredicted, then the following steps are performed: The Front End section is flushed and reloaded with instructions corresponding to a correct path. And, instructions corresponding to the correct path are loaded from the Front End section into the instruction pool before the mispredicted branch instruction is retired.

FIG. 1 is a block diagram illustrating an instruction pipeline for a processor.

FIG. 2 is a block diagram illustrating the operation of the instruction pipeline of FIG. 1.

FIG. 3 is another block diagram illustrating the operation of the instruction pipeline of FIG. 1.

FIG. 4A is a block diagram of a ReOrder Buffer (ROB) of an instruction pipeline for illustrating the branch recovery mechanism according to an embodiment of the present invention.

FIG. 4B is a block diagram of the ReOrder Buffer of FIG. 4A after detection of a mispredicted branch for illustrating the branch recovery mechanism according to an embodiment of the present invention.

FIG. 5 is a flow chart illustrating the operation of the branch recovery mechanism according to an embodiment of the present invention.

Referring to the drawings in detail, wherein like numerals indicate like elements, FIG. 4A is a block diagram of a ReOrder Buffer (ROB) (or instruction pool) 70 of an instruction pipeline for illustrating the branch recovery mechanism according to an embodiment of the present invention. FIG. 4B is a block diagram of the ReOrder Buffer 70 of FIG. 4A after detection of a mispredicted branch for illustrating the branch recovery mechanism according to an embodiment of the present invention.

The instruction pipeline 10 according to an embodiment of the present invention is similar to the instruction pipeline 10 of FIGS. 1-3, except that ROB 70 in FIGS. 4A and 4B of the present invention replaces ROB 18 in the instruction pipeline 10 of FIG. 1. In addition, the instruction pipeline 10 of the present invention operates differently from the instruction pipeline of FIGS. 1-3, as described in greater detail below.

Referring to FIG. 4A, each entry in ROB 70 includes a ROB sequence (or entry) number 72, the micro-op 74, an execute bit 76 indicating whether the micro-op has been executed, a mispredict (MP) bit 78 indicating whether a branch was mispredicted, path information 80 identifying the path of the micro-op, and a Retired bit 82 (RET) indicating whether the micro-op has been marked ready for retirement. Although not shown in FIG. 4A, each ROB entry can include space for storing the execution results for each micro-op. Alternatively, execution results can be stored in a register, and a pointer in the ROB can point to the register storing the execution results for an instruction.

Six micro-ops are stored in ROB 70 of FIG. 4A, including micro-ops for ROB entries N through N+5. Micro-ops N, N+1 and N+3 through N+5 are non-branch micro-ops. Micro-op number N+2 is a branch instruction. A 1 in the Execute bit 76 and a 1 in the Retired bit 82 of ROB entry N indicate that the micro-op of ROB entry N has been executed and marked ready for retirement, respectively. No other micro-ops in ROB 70 have been executed.

The start-of-buffer pointer 46 in FIG. 4A currently points to micro-op N, which is the oldest (unretired) micro-op in ROB 70. The end-of-buffer pointer 48 in FIG. 4A points to ROB entry N+6, which is where the next micro-op from Decode stages 14 will be stored in the ROB 70.

The path information 80 identifies the micro-ops that correspond to a particular path. A new "path" is created after each mispredicted branch. According to the present invention, the path information 80 is used to more efficiently recover from a mispredicted branch in order to reduce the Front End stall time. The path information 80 allows the processor to distinguish between micro-ops corresponding to the mispredicted (or incorrect) path and micro-ops that correspond to the correct path.

The path information 80 can include different types of identification information. In the embodiment illustrated in FIG. 4A, the micro-ops for ROB entries N through N+5 correspond to a green path. Other colors (such as blue or red) can be used to identify different paths. Rather than colors, other types of information can be used to identify different paths, such as PathA, PathB, PathC, or Path1, Path2 and Path3, etc. The path information 80 can be implemented as one or more bits for uniquely identifying the path for each micro-op in ROB 70.

When the branch instruction (of ROB entry 2 in FIG. 4A) enters the instruction pipeline 10 of the present invention, the Branch Prediction Unit (in the Front End section 30) predicts whether the branch will be taken (by examining the execution history of the instruction). The branch prediction is used to load micro-ops into the Front End section 30 corresponding to the predicted path. In the embodiment of the present invention illustrated in FIG. 4A, the micro-ops of ROB entries N through N+2 are part of an actual path because there is no prediction involved. As a result, these micro-ops of ROB entries N through N+2 will always be executed and have their execution results committed to architectural state (retired). The micro-ops for ROB entries N+3 through N+5 (after the branch instruction) correspond to the path predicted by the Branch Prediction Unit (the "predicted path"). The micro-ops for ROB entries N+3 through N+5 may or may not be executed and have their execution results committed to architectural state depending on whether the branch was correctly predicted or mispredicted.

The branch micro-op of ROB entry N+2 and the three predicted micro-ops at ROB entries N+3 through N+5 are loaded into the ROB 70 in strict program order. Eventually, the branch micro-op at ROB entry N+2 is executed and validated. During validation, it is determined that this branch micro-op was incorrectly predicted. At the time it is determined that the branch instruction was mispredicted, the last micro-op to be loaded into the ROB is the micro-op at ROB entry N+5. The end-of-buffer pointer 48 points to ROB entry N+6, which is where the next micro-op from Decode stages 14 will be stored in ROB 70.

FIG. 4B is a block diagram of the ReOrder Buffer of FIG. 4A after the detection of the mispredicted branch. The instructions for ROB entries N+3 through N+5 are part of the mispredicted path 75. The instructions in the Front End section 30 also correspond to a portion of the mispredicted path. The mispredicted path 75 is also identified by the path information 80 as part of the green path.

After the mispredicted branch is detected by the execution stage 22, the Front End section 30 is flushed and reloaded with instructions corresponding to the correct path. After the Front End section 30 is flushed and reloaded with the correct path, the correct path micro-ops are then loaded from the Front End section 30 into the ROB 70 beginning at the ROB entry N+6 (where the end-of buffer pointer 48 points at the time the mispredicted branch is detected).

In FIG. 4B, four micro-ops corresponding to the correct path 85 have been loaded in program order from the Front End section 30 into the ROB 70 at ROB entries N+6 through N+9. After loading the micro-ops corresponding to the correct path 85, the end of buffer pointer 48 is updated to point to ROB entry N+10. The start of buffer pointer 46 also has been updated to point to ROB entry N+3 because the mispredicted branch micro-op has been retired. Micro-ops N+3, N+4 and N+5 are known to be erroneous (the mispredicted path 75) because these micro-ops have the same path information 80 as the mispredicted branch (the Green path) and have a sequence number that is greater than the mispredicted branch instruction (sequence number 2).

FIG. 5 is a flow chart illustrating the operation of the branch recovery mechanism according to the embodiment of the present invention illustrated in FIGS. 4A and 4B.

At step 505 the Instruction Fetch Units 12 fetch a branch instruction which is input to Decode stages 14. Decode stages 14 then decode the branch instruction.

At step 510, the Branch Prediction unit, which is part of the Front End section 30, predicts whether or not the branch instruction will be taken.

At step 515 the branch prediction made by the Branch Prediction unit is used to fetch and decode instructions corresponding to the predicted path. The Instruction Fetch Unit 12 fetches instructions corresponding to the predicted path and stores these instructions in the prefetch streaming buffer 40. Decode stages 14 then decode the instructions into one or more micro-ops which are placed in ID Queue 42.

At step 520, the branch micro-op and at least a portion of the predicted path are loaded from the Front End section 30 into ROB 70 (or instruction pool) beginning at entry number N+2. The branch micro-op is stored at ROB entry N+2, as indicated in FIG. 4A. Referring to FIG. 4A, the micro-ops corresponding to the predicted path 75 are stored in the ROB 70 at ROB entries N+3 through N+5. The path information 80 for each of these micro-ops identifies each of these micro-ops as part of the green path (the same path information as the branch instruction at N+2).

At step 525, the Execution stage 22 executes the branch instruction at ROB entry N+2. Instructions in the ROB 70 are stored in strict program order, however, instructions may be executed out of program order. Therefore, at the time the branch micro-op is executed, only the micro-op of entry No. N has been executed and marked ready for retirement. Therefore, the branch micro-op of ROB entry N+2 is executed before the micro-op of ROB entry N+1.

At step 530, the Execution stage 22 of the Front End section 30 determines whether or not the predicted path (predicted at step 510) was correct based on the branch micro-op of ROB entry N+2. If the path was correctly predicted, the processor continues operating normally to fetch, decode, execute and retire instructions without flushing and reloading the Front End section 30 and the ROB 70. If, however, the predicted path was mispredicted, then the steps of 535, 540, and 545 will be performed.

At step 535, the Front End section 30 is flushed and reloaded with the instructions corresponding to the correct path. This is performed, for example, by the Instruction Fetch Units 12 fetching instructions from the correct path. The fetched instructions corresponding to the correct path are placed in the prefetch streaming buffer 40 which are then output to Decode stages 14. Decode stages 14 then decode each of the instructions corresponding to the correct path into one or more micro-ops.

At step 540, micro-ops corresponding to the correct path are loaded from the Front End section 30 to the ROB 70 without waiting for the mispredicted branch to be retired (i.e., correct micro-ops are loaded into ROB 70 before the mispredicted branch is retired). As illustrated in FIG. 4B, there are four instructions corresponding to the correct path 85 that are loaded into ROB 70 extending from entry no. N+6 through entry no. N+9. The path information 80 for each micro-op stored in the ROB 70 corresponding to the correct path 85 is identified as part of the blue path. The path information 80 and the sequence number 72 allow the processor to distinguish between the mispredicted path 75 (part of the green path) at ROB entries N+3 through N+5, and the correct path 85 (the blue path) at ROB entries N+6 through N+9.

According to an embodiment of the present invention, the Front End section 30 is flushed and reloaded with the correct path (step 535). However, unlike prior art instruction pipelines, the Front End Section 30 of the present invention does not stall or wait for the mispredicted branch instruction to be retired before loading the ROB 70 with the correct path. According to the present invention, the ROB 70 is immediately loaded with micro-ops from the Front End Section 30 corresponding to the correct path before the mispredicted branch (of sequence number N+2) is retired. As a result, the Front End stall time is reduced.

At step 545, the micro-ops in the ROB 70 corresponding the mispredicted path 75 are deleted from ROB 70 without committing their execution results to architectural state. These instructions corresponding to the mispredicted path 75 after the branch instruction include the micro-ops at entries N+3 through N+5 and should be deleted from ROB 70 without committing their execution results to architectural state because they are incorrect (were mispredicted). The micro-ops at sequence numbers N+3, N+4 and N+5 are known to be part of the mispredicted path 75 because these micro-ops have the same path information 80 (the green path) as the mispredicted branch instruction and have a sequence number that is greater than the mispredicted branch instruction (a sequence number greater than N+2).

According to an embodiment of the present invention, after some micro-ops corresponding to the correct path have been loaded into the ROB 70, the ROB 70 includes correct micro-ops up to and including the mispredicted branch (e.g., micro-ops for ROB entries N through N+2, FIG. 4B), incorrect micro-ops corresponding to the mispredicted path 75 (e.g., ROB entries N+3 through N+5), and one or more micro-ops of the correct path 85 (e.g., Blue path micro-ops including ROB entries N+6 though N+9). Therefore, unlike prior systems, the present invention mixes correct micro-ops and incorrect micro-ops in the ROB 70 after detecting a mispredicted branch to avoid stalling or waiting for the mispredicted branch to be retired. Because the ROB 70 will at least temporarily include both correct and incorrect micro-ops, the processor of the present invention determines whether or not each micro-op in the ROB 70 should be executed and/or committed to architectural state based on path information 80 and sequence number 72 for each micro-op.

The micro-ops (having the same path information 80 as the mispredicted branch) up to and including the mispredicted branch instruction (ROB entries N through N+2 of the green path) are correct, and therefore, are executed and committed to architectural state. Similarly, the micro-ops in the ROB 70 after the mispredicted branch that are identified by path information 80 as being part of a different path from the branch instruction (e.g., the correct or blue path 85 including the micro-ops at ROB entries N+6 through N+9 of ) are also correct and are therefore executed and committed to architectural state. Execution can occur out of order. There are several ways in which the execution results can be committed to the architectural state. For example, the micro-ops execution results can be committed to the architectural state by copying the execution result from the corresponding ROB entry into the processor's real register set. This can be done directly by copying the execution result, or can be done indirectly by the use of pointers.

However, the micro-ops having path information that is the same as the mispredicted branch (e.g., green path) and having a sequence number greater than (e.g., after) the mispredicted branch (e.g., ROB entries N+3 through N+5) are part of the mispredicted path 75 and should be deleted from ROB 70 without committing their execution results to architectural state. Unnecessary execution of these micro-ops corresponding to the mispredicted path 75 wastes system resources needed for execution of the correct micro-ops. Therefore, to improve the speed of recovery from the mispredicted branch, the micro-ops corresponding to the mispredicted path 75 should be deleted from ROB 70 as soon as possible after detecting the mispredicted branch to minimize use of system resources.

According to one embodiment of the present invention, an incorrect micro-op (corresponding to the mispredicted path 75) can be (and should be) deleted from ROB 70 after detection of the mispredicted branch if execution of the incorrect micro-op has not begun. In the event that execution of an erroneous or incorrect instruction cannot be prevented (e.g., where execution has already begun), there are several techniques that can be used to reduce use of system resources for these erroneous instructions.

First, memory operations typically access cache for data operands. However, if the data is not in the cache, this will cause a cache miss where data must be retrieved from main memory. However, when a memory operation is part of a mispredicted path (an erroneous instruction), the data retrieval step should be canceled after a cache miss to save main memory and bus bandwidth.

In addition, the resources of the system scheduler should not be tied up. For example, if an erroneous micro-op (corresponding to mispredicted path 75) depends on data from other micro-ops, the micro-op should be allowed to execute without waiting for the dependent data. The micro-op should be allowed to execute as if the data from the other micro-op was already available to thereby speed the execution and of the micro-op. Other techniques may be used to speed the execution of the micro-ops corresponding to the mispredicted path 75. After the micro-ops corresponding to the mispredicted path 75 have been executed (if necessary), the micro-op's execution results are not committed to architectural state (because these micro-ops are incorrect or erroneous). Rather, these incorrect micro-ops are deleted from ROB 70.

Several embodiments of the present invention are specifically illustrated and/or described herein. However, it will be appreciated that modifications and variations of the present invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.