System and method for using a working global history register

A method of processing branch history information is disclosed. The method retrieves branch instructions from an instruction cache and executes the branch instructions in a plurality of pipeline stages. The method verifies that a branch instruction has been identified. The method further receives branch history information during a first pipeline stage and loads the branch history information into a first register. The method further loads the branch history information into the second register during the second pipeline stage.

BACKGROUND

1. Field of Invention

The present invention relates generally to computer systems, and more particularly to a method and a system for using a working global history register.

2. Relevant Background

At the heart of the computer platform evolution is the processor. Early processors were limited by the technology available at that time. New advances in fabrication technology allow transistor designs to be reduced up to and exceeding 1/1000thof the size of early processors. These smaller processor designs are faster, more efficient and use substantially less power while delivering processing power exceeding prior expectations.

As the physical design of the processor evolved, innovative ways of processing information and performing functions have also changed. For example, “pipelining” of instructions has been implemented in processor designs since the early 1960's. One example of pipelining is the concept of breaking execution pipelines into units or stages, through which instructions flow sequentially in a stream. The stages are arranged so that several stages can be simultaneously processing the appropriate parts of several instructions. One advantage of pipelining is that the execution of the instructions is overlapped because the instructions are evaluated in parallel.

A processor pipeline is composed of many stages where each stage performs a function associated with executing an instruction. Each stage is referred to as a pipe stage or pipe segment. The stages are connected together to form the pipeline. Instructions enter at one end of the pipeline and exit at the other end.

Most programs executed by the processor include conditional branch instructions, the actual branching behavior of which is not known until the instruction is evaluated deep in the pipeline. To avoid a stall that would result from waiting for actual evaluation of the branch instruction, modern processors may employ some form of branch prediction, whereby the branching behavior of a conditional branch instruction is predicted early in the pipeline. Based on the predicted branch evaluation, the processor speculatively fetches and executes instructions from a predicted address—either the branch target address (if the branch is predicted to be taken) or the next sequential address after the branch instruction (if the branch is predicted not to be taken). Whether a conditional branch instruction is taken or not taken is referred to as determining the direction of the branch. Determining the direction of the branch may be made at prediction time and at actual branch resolution time. When the actual branch behavior is determined, if the branch was mispredicted, the speculatively fetched instructions must be flushed from the pipeline, and new instructions fetched from the correct address. Speculatively fetching instructions in response to an erroneous branch prediction can adversely impact processor performance and power consumption. Consequently, improving the accuracy of branch predictions is an important processor design goal.

One known form of branch prediction includes partitioning branch prediction into two predictors: an initial branch target address cache (BTAC) and a branch history table (BHT). The BTAC is indexed by an instruction fetch group address and contains the next fetched address, also referred to as the branch target, corresponding to the instruction fetch group address. Entries are added to the BTAC after a branch instruction has passed through the processor pipeline and its branch has been taken. If the BTAC becomes full, entries are removed from the BTAC using standard cache replacement algorithms (such as round robin or least-recently used) when the next entry is being added.

The BTAC may be a highly-associative cache design and is accessed early in the instruction execution pipeline. If the fetch group address matches a BTAC entry (a BTAC hit), the corresponding next fetch address or target address is fetched in the next cycle. This match and subsequent fetching of the target address is referred to as an implicit taken branch prediction. If there is no match (a BTAC miss), the next sequentially incremented address is fetched in the next cycle. This no match situation is also referred to an implicit not-taken prediction.

BTACs may be utilized in conjunction with a more accurate individual branch direction predictor such as a branch history table (BHT) also known as a pattern history table (PHT). A conventional BHT may contain a set of saturating predicted direction counters to produce a more accurate taken/not-taken decision for individual branch instructions. For example, each saturating predicted direction counter may comprise a 2-bit counter that assumes one of four states, each assigned a weighted prediction value, such as:

11—Strongly predicted taken

10—Weakly predicted taken

01—Weakly predicted not taken

00—Strongly predicted not taken

The output of a conventional BHT, also referred to as a prediction value, is a taken or not taken decision which results in either fetching the target address of the branch instruction or the next sequential address in the next cycle. The BHT is commonly updated with branch outcome information as it becomes known.

In order to increase the accuracy of branch predictions, various other prediction techniques may be implemented which use recent branch history information from other branches as feedback. As those skilled in the art appreciate, current branch behavior may be correlated to the history of previously executed branch instructions. For example, the history of previously executed branch instructions may influence how a conditional branch instruction is predicted.

A Global History Register (GHR), also referred to in the art as a global branch history register or a global history shift register, may be used to keep track of the past history of previously executed branch instructions. As stored by the GHR, the branch history provides a view of the sequence of branch instructions encountered in the code path leading up to the presently executed branch instruction in order to achieve improved prediction results.

In some processors, identification of a branch instruction and its associated prediction information may occur only after an instruction decode stage. Commonly, the instruction decode stage may be a later stage in the instruction execution sequence. After an instruction is decoded and confirmed as a branch instruction, the GHR is loaded with appropriate branch history information. As the branch history information is identified it is shifted into the GHR. The output of the GHR is used to identify the prediction value stored in the BHT which is used to predict the next conditional branch instruction.

In a conventional processor using a GHR, the GHR may not reflect the actual branch history information encountered when multiple branch instructions are executed in parallel during a relatively short period of time. In this instance, the GHR may not be updated with the branch history information from the first branch instruction before the second branch instruction is predicted. As a result, an inaccurate value of the GHR may be used to identify the entry in the BHT for the second conditional branch instruction. Using an inaccurate value to index the entry in the BHT may affect the accuracy of the branch prediction. If the processor had been able to keep pace with the branch history information from the first conditional branch instruction, a different value would have been stored in the GHR and a different entry in the BHT would have been identified for the second conditional branch instruction.

SUMMARY

Accordingly, there exists a need in the industry to have a processor that may store and use branch history information sooner than the GHR in order to achieve more accurate branch predictions. The present disclosure recognizes this need and discloses a processor which identifies branch instructions early in the execution stages of the processor. Using the branch instruction information as input, the processor may steer the selection of prediction values for subsequent conditional branch instructions.

A method of processing branch history information is disclosed. The method identifies branch instructions during a first pipeline stage and loads the branch history information in a first register during the first pipeline stage. The method confirms the branch instructions in a second pipeline stage and the branch history information is loaded into a second register during the second pipeline stage.

A pipeline processor comprising a first register having branch history information and a second register having branch history information is disclosed. The pipeline processor has a plurality of pipeline stages wherein the first register is loaded with the branch history information in a first pipeline stage when a branch instruction is identified and, a second register is loaded with branch history information during a second pipeline stage.

A method of processing branch history information is disclosed. The method fetches a branch instruction, identifies the branch instructions during a first pipeline stage and loads the branch history information in a first register during the first pipeline stage. The method confirms the branch instructions in a second pipeline stage and the branch history information is loaded into a second register during the second pipeline stage.

DETAILED DESCRIPTION

The detailed description set forth below in connection with the appended drawings is intended as a description of various embodiments of the present invention and is not intended to represent the only embodiments in which the present invention may be practiced. The detailed description includes specific details for the purpose of providing a thorough understanding of the present invention. However, it will be apparent to those skilled in the art that the present invention may be practiced without these specific details. In some instances, well-known structures and components are shown in block diagram form in order to avoid obscuring the concepts of the present invention. Acronyms and other descriptive terminology may be used merely for convenience and clarity and are not intended to limit the scope of the invention.

FIG. 1shows a high level view of a superscalar processor100utilizing an embodiment as hereinafter described. The processor100has a central processing unit (CPU)102that is coupled via a dedicated high speed bus104to an instruction cache106. The instruction cache is also coupled via a general purpose bus116to memory114.

Within the processor100, an Instruction Fetch Unit (IFU)122controls the loading of instructions from memory114into the instruction cache106. Once the instruction cache106is loaded with instructions, the CPU102is able to access them via the high speed bus104. The instruction cache106may be a separate memory structure as shown inFIG. 1, or it may be integrated as an internal component of the CPU102. The integration may hinge on the size of the instruction cache106as well as the complexity and power dissipation of the CPU102. Also coupled to the IFU122is a Branch Target Address Cache130(BTAC), a Branch History Table140(BHT) and two lower pipelines160and170.

Instructions may be fetched and decoded from the instruction cache106several instructions at a time. Within the instruction cache106instructions are grouped into sections known as cache lines. Each cache line may contain multiple instructions as well as associated data. The number of instructions fetched may depend upon the required fetch bandwidth as well as the number of instructions in each cache line. Within the IFU122, the fetched instructions are analyzed for operation type and data dependencies. After analyzing the instructions, the processor100may distribute the instructions from the IFU122to lower functional units or lower pipelines160or170for further execution.

Lower pipelines160and170may contain various Execution Units (EU)118including arithmetic logic units, floating point units, store units, load units and the like. For example, an EU118such as an arithmetic logic unit may execute a wide range of arithmetic functions, such as integer addition, subtraction, simple multiplication, bitwise logic operations (e.g. AND, NOT, OR, XOR), bit shifting and the like. Additionally, the lower pipelines160and170may have a resolution stage (not shown), during which the actual results of a conditional branch instruction are identified. Once the actual results of the branch instruction are identified, the processor100may compare the actual results to the predicted results and, if they don't match, a mispredict has occurred.

Those skilled in the art appreciate that the BTAC130may be similar to a Branch Target Buffer (BTB) or a Branch Target Instruction Cache (BTIC). A BTB or BTIC stores both the address of a branch and the instruction data (or opcodes) of the target branch. For ease of illustration, the BTAC130is used in conjunction with the various embodiments of the present invention. Other embodiments of the invention may alternatively include a BTB or BTIC instead of the BTAC130.

The first time a branch instruction is executed, there is no entry in the BTAC130and a BTAC miss occurs. After the branch instruction finishes its execution, the BTAC130may be subsequently updated to reflect the target address of the particular conditional branch instruction as well as a processor mode (e.g. Arm vs. Thumb operation in the advanced RISC processor architecture). Any time thereafter that the branch instruction is fetched again, the information stored in the BTAC130will be fetched on the next processor cycle, even without completely decoding the fetched branch instruction.

A BTAC hit (e.g. when the fetch group address matches an address in the BTAC130) may occur for either a conditional or unconditional branch instruction. This is due to the fact that the BTAC130may store information relating to both conditional branch instructions as well as unconditional branch instructions. In the case of a BTAC hit for an unconditional branch instruction, the predicted target address, predicted mode of the processor as well as the fact that the branch instruction is unconditional may be stored. In situations where an unconditional branch instruction address is stored in an entry in the BTAC130, the entry will indicate a branch direction of taken.

FIG. 2displays a more detailed illustration of an exemplary Branch History Table (BHT)140used by the processor100. The BHT140may be organized into 2mlines202which are indexed using an address having m address bits. In one embodiment, nine bits of address are used which results in a BHT140having 512 lines. Within each line202there are 2ncounters204, where n is the number of bits used to select the appropriate counter. Additionally, 3 bits of address may be used to select the counter204, resulting in a BHT140that has eight counters204per line202. In one exemplary embodiment, fetch group address bits12through4may be used to select the line202in the BHT140. Bits3-1of the fetch group address may be used to select the specific counter204.

The processor100may identify branch instructions earlier in the instruction execution process prior to an instruction decode stage. When branch instructions are identified earlier, branch history information, such as the prediction value (conditional branch instruction) or taken branch direction (unconditional branch instruction) may also be identified at the same time. A Working Global History Register (WGHR), as will be described in the discussion ofFIG. 4, may be used by the processor100to receive and process the branch history information earlier in the instruction execution process. For example, a WGHR may store the prediction values of conditional branch instructions as well as branch directions of unconditional branch instructions. Alternatively, a WGHR may store only the prediction values of conditional branch instructions. The output of the WGHR may be employed to index a corresponding entry in the BHT140for the next conditional branch instruction.FIG. 3shows a state transition diagram300. A state310, having a most significant bit of 1 and a least significant bit of 1, may transition to a state320, having a most significant bit of 1 and a least significant bit of 0. The state310may also transition into itself. The state320may transition to a state330, having a most significant bit of 0 and a least significant bit of 1. The state330may transition to a state340, having a most significant bit of 0 and a least significant bit of 0. The state340may transition into itself The state340may also transition to the state330, which may also transition to the state320, which may also transition to the state310.

FIG. 4displays a lower level logic block diagram400of the processor100including a Working Global History Register (WGHR)416. In the lower level block diagram400is an upper pipe450. Coupled to the top of the upper pipe is fetch logic circuit402. The upper pipe450includes four instruction execution stages, an Instruction Cache1Stage (IC1)404, an Instruction Cache2Stage (IC2)406, an Instruction Data Alignment Stage (IDA)408and a Decode Stage (DCD)410. It should be noted that pipe stages may be added to or subtracted from upper pipe450without limiting the scope of the present disclosure. The fetch logic circuit402as well as the upper pipe450, the Working Global History Register (WGHR)416, Global History Register (GHR)414, Branch Correction logic circuit (BCL)440, selection mux422, and address hashing logic circuit420may also be located within the IFU122.

As the processor100begins executing instructions, the fetch logic circuit402determines what instructions are to be fetched during the IC1stage404. In order to retrieve the instructions, the fetch logic circuit402sends the fetch group address to the Instruction Cache106. If the fetch group address is found within the Instruction Cache106(e.g. an instruction cache hit) the instructions are read from the hit cache line in the Instruction Cache106during the IC2stage406.

In parallel, during the IC1stage404, the processor100sends the fetch group address to the BTAC130. If the processor100encounters a BTAC hit, the information stored within the BTAC for the fetch group address is received during the IC2Stage406. As mentioned previously, information stored within the BTAC130may include branch information such as a branch target, processor mode, as well as a taken branch direction (in the case of an unconditional branch instruction).

Also during the IC1stage404, the fetch logic sends the fetch group address to the address hashing logic circuit420. Within the addressing hashing logic circuit420, bits12-4of the fetch group address are exclusively or'd (XOR'd) with the output of the selection mux422. The output of the address hashing logic circuit420(e.g. the XOR function) provides the address index into the BHT140. As mentioned previously, bits3-1of the fetch group address may provide the selection bits to select the appropriate counter204.

During the IC2stage406, the processor100reads the results from sending the instruction fetch group address to the Instruction Cache106, the BTAC130and the BHT140. In the IC2stage406, the processor100determines if a BTAC hit has occurred. When a BTAC hit is confirmed during the IC2stage406the processor100also determines if the branch is a conditional or unconditional branch instruction. In the IC2stage406the prediction value from the BHT140is also received and stored.

Since each cache line in the Instruction Cache106may contain multiple instructions, the individual instructions may need to be separated from a cache line. As well, data may be intertwined with the instructions in the cache line. The information from the cache line may need to be formatted and aligned in order to properly analyze and execute the instructions. The alignment and formatting of the instructions into individual executable instructions occurs during the IDA stage408.

After the instructions are processed during the IDA stage408, they pass through the Decode (DCD) stage410. During the DCD stage410, the instructions are analyzed to determine the type of instruction and what additional information or resources may be required for further processing. Depending on the type of instruction or the current instruction load, the processor100may hold the instruction in the DCD stage410or the processor100may pass it on to either of the lower pipelines160or170for further execution. In the DCD stage410the processor100confirms the instruction as a conditional branch instruction and confirms the instruction's prediction value (read during the IC2stage406) from the BHT140. The accuracy of the prediction value will be verified during a later stage of instruction execution in either of the lower pipelines160or170. Until a branch prediction is determined to be incorrect (e.g. a mispredict), the processor100assumes that the prediction value is the true value and proceeds fetching instructions based on this prediction.

Coupled to the upper pipe450is the Working Global History Register416(WGHR). The WGHR416allows the processor100to store and process branch history information associated with branch instructions which have been identified prior to the DCD stage410. In one embodiment, the WGHR416may be loaded with the prediction value from the BHT140for a conditional branch instruction when a BTAC hit occurs. As stated previously, a BTAC hit signifies that the instruction being fetched is a branch instruction and has associated branch history information (e.g. prediction value for a conditional branch instruction or a taken direction for an unconditional branch instruction). Based on this condition, the processor100can utilize the branch history information earlier for subsequent branch predictions (i.e the branch history information is more current) as opposed to waiting until the branch instruction is confirmed during the DCD stage410. The output of the WGHR416is sent to the address hashing logic circuit420to determine the address index for the next entry in the BHT140.

When the branch history information becomes available is dependent upon on how fast the branch history information may be retrieved from the BHT140and how fast a BTAC hit may be acknowledged. In some processor designs, the branch history information and BTAC hit may be received during the IC2stage406. In other processor designs, the branch history information and BTAC hit may be received during the IDA stage408. In yet other processor designs incorporating stages other than the stages previously described, branch history information and BTAC hit may be available during those stages prior to a decoding stage.

In one embodiment, the branch history information for conditional branch instructions is shifted in to the WGHR416during the IC2stage406(when a BTAC hit occurs). In yet another embodiment, branch history information for both conditional branch instructions and unconditional branch instructions are shifted into the WGHR416. In a further embodiment, the WGHR416may be updated during the IDA stage408with branch history information. This situation may occur when the prediction value stored in the BHT140or the BTAC hit information is not available until the IDA stage408.

The selection mux422is configured to receive the output of WGHR416. In one embodiment, the output of the WGHR416is a nine bit value containing the branch history of the last nine branch instructions processed by the processor100. The output of the selection mux422is used as input into the address hashing logic circuit420which indexes into the BHT140for the next conditional branch instruction.

The GHR414operates much like the WGHR416, except the GHR414may be loaded with the branch history information during the DCD stage410. The contents of the GHR414will mirror the contents of the WGHR416once the branch instruction passes through the DCD stage410. Depending on the circumstances the output of the GHR414may be used to index the prediction value.

The output of the GHR414is coupled to the selection mux422. When a BTAC miss occurs and it is determined during the DCD stage410that the instruction is confirmed as a taken branch instruction, the selection mux422is directed to select the output of the GHR414to be used by the address hashing logic circuit420for indexing. In this instance, the GHR414is used because the WGHR416does not yet have the branch history information for the taken branch (due to the BTAC miss). Alternatively, the output of the GHR414may also be used by the address hashing logic circuit420when a BTAC miss occurs because the WGHR416may have been updated by a subsequently fetched branch instruction prior to indexing the BHT140for the current branch instruction. In this instance, the WGHR416may not reflect the proper value for the current branch instruction and if used by the address hashing logic circuit420an incorrect entry in the BHT140may be indexed.

The output of the GHR414is also coupled to Branch Correction Logic circuit (BCL)440. The BCL440uses the GHR414to provide a “true” copy of the branch history information which is used for recovery purposes should a mispredict occur.

When a mispredict occurs, the BCL440restores the branch history information in both the GHR414and WGHR416. As mentioned previously, a mispredict occurs when a branch instruction reaches a resolution stage and the actual results do not match the predicted results.

When a mispredict occurs, the BCL440sends information to the fetch logic circuit402which directs the fetch logic circuit402to flush instructions that were fetched based on the mispredicted conditional branch instruction. In order to be more efficient, the BCL440may restore the GHR414and the WGHR416to the correct branch history information at the same time it provides the correct branch history information to the selection mux422. When the mispredict occurs, the processor100may select the output of the BCL440(through the selection mux422) to be directed to the address hashing logic circuit420for use in indexing the appropriate counter204.

When the processor100encounters a mispredict, the BCL440restores the GHR414and WGHR416to their proper values. In one embodiment, the BCL440may take a snapshot of the GHR414after the GHR414is loaded with a prediction value for a conditional branch instruction. The BCL440may then invert the most recent prediction value (e.g. the MSB) of the GHR414. By taking the opposite of the prediction value, the BCL440prepares a corrected value which should be reflected in the GHR414and WGHR416if a mispredict occurs. For example, if after identifying a conditional branch instruction and its prediction value during the DCD stage410, the GHR414and the BCL440are loaded with the value “101011111” (MSB =>LSB). The BCL440may flip the MSB corresponding to the conditional branch instruction and store the corrected value “001011111” linked to the conditional branch instruction. Thus, if the conditional branch instruction is incorrectly predicted, the corrected value is ready to be sent to the GHR414, the WGHR416and the selection mux422.

FIG. 5displays a detailed view500of the WGHR416, the GHR414and the BCL440. Within the detailed view500, a WGHR selection mux502receives branch history information from the IC2stage406, the DCD stage410as well as corrected branch history information from the BCL440. A GHR selection mux504receives branch history information from the DCD stage410and corrected branch history information from the BCL440.

The WGHR selection mux502selects which input is used to load the WGHR416with branch history information. When a mispredict occurs, the input from the BCL440has priority over information being sent from the IC2Stage406or DCD stage410. The BCL440has priority because subsequent branch history information following a mispredict may be associated with conditional branch instructions fetched down the incorrectly predicted branch path. Therefore, the branch history information passed by the IC2stage406or DCD stage410may also be incorrect.

If no mispredict occurs, the input selection for the WGHR selection mux502may be determined according to the following examples listed from highest to lowest priority:a) If a branch instruction returns a BTAC miss during the IC2stage406but ends up predicted taken after being decoded during the DCD stage410, the branch history value confirmed during the DCD stage410is shifted into the WGHR416. The DCD stage410has priority in this case because instructions fetched after the predicted taken branch instruction need to be flushed. Therefore, any branch history information identified during the IC2stage406for a subsequent branch instruction which may be ready to write into the WGHR416during the same processor cycle is discarded.b) If the DCD stage410is not executing a branch instruction associated with a BTAC miss, the IC2stage406will have the next highest priority. As long as a BTAC hit occurs for the branch instruction, the branch history information identified during the IC2stage406is shifted in to the WGHR416.c) If a branch instruction has been previously identified as a BTAC hit and the associated branch history information was loaded according to the previously described example (b), the WGHR416will be rewritten once more from the DCD stage410. As well, if a conditional branch instruction is a BTAC miss and the branch instruction is predicted not taken, the WGHR416is written with this branch history information. The writing of the WGHR416ensures that the GHR414and the WGHR416will be synchronized after the instruction passes through the decode stage410.

The GHR selection mux504selects the appropriate input used to update the GHR414. Similar to the WGHR selection logic502, the GHR selection mux504gives the input from the BCL440the highest priority for the same reasons as explained above. Thus if no mispredict occurs, the GHR414is updated with branch history information identified during the DCD stage410for a particular branch instruction.

FIG. 6shows a timing diagram600of an exemplary group of instructions as they move through the upper pipe450. Within the exemplary group of instructions800ofFIG. 8are multiple branch instructions. The X-axis602ofFIG. 6depicts the processor cycle and the Y-Axis604illustrates the execution stage within upper pipe450the instruction passes through as well as the contents of the GHR414and WGHR416. The contents of the GHR414and the WGHR416are written to during one processor cycle and latched at the beginning of the next processor cycle. As reflected in the timing diagram600, the latched contents are of the GHR414and WGHR416are displayed. For ease of illustration, only the three most significant bits of the GHR414and the WGHR416are shown. As the instructions are executed, the instructions move down the Y-axis604.

In Processor Cycle1, the fetch logic circuit402sends a fetch group address to the Instruction Cache106, the BTAC130and address hashing logic circuit420for instruction A. This is shown in the timing diagram600as instruction A enters the IC1Stage404. Also in Processor Cycle1, the three most significant bits of the GHR414and WGHR416are all zeros indicating that the last three branch instructions executed were all not taken.

In Processor Cycle2the results of sending the fetch group address to the instruction cache106, the BTAC130and the BHT140are received. This is displayed in the timing diagram as instruction A entering the IC2stage406. Since the instruction cache106stores multiple instructions, instruction A+4 is also shown retrieved along with instruction A in the IC2stage406. Logic circuitry within the IC2stage406analyzes the information received from the BTAC130and BHT140. During the IC2stage406, the processor100determines that instruction A is a conditional branch instruction (based on the information from a BTAC hit) as well as the prediction value returned from the BHT140. In this example, instruction A is predicted taken. The actual entry in the BHT140for instruction A may be either strongly taken (11) or weakly taken (10). At the end of Processor Cycle2the processor100loads in a “1” in the MSB of the WGHR416to reflect the prediction value associated with conditional branch instruction A. Since instruction A is predicted taken, the next sequential instruction (A+4) is flushed after instruction A passes through the IC2stage406since instruction A+4 will not be the next instruction to be executed. As shown in the timing diagram600, the value “100” is latched into the WGHR416at the start of Processor Cycle3.

During Processor Cycle3, instruction A enters the IDA stage408. While in the IDA stage408, instruction A is formatted and aligned, thus preparing the instruction to enter the DCD stage410. While instruction A moves through the IDA stage408, the fetch group address for instruction B is sent to the instruction cache106, the BTAC130and BHT140during the IC1stage404.

In Processor Cycle4, instruction A enters the DCD stage410, the results from the fetch request for instructions B and B+4 are received (the IC2stage406) and the fetch group address for instruction B+8 is sent to the instruction cache106, the BTAC130and BHT140(the IC1Stage404). The contents of WGHR416(“100”) are selected by the selection mux422and are used by the address hashing logic circuit420for indexing the entry into the BHT140for instruction B+8. When instruction A is in the DCD stage410, the processor100confirms that instruction A is a conditional branch instruction and as a result the prediction value (“1”) is shifted into the GHR414. The processor100will not see the updated value of the GHR414from instruction A until the beginning of Processor Cycle5when the processor100latches GHR414. At the end of Processor Cycle4, instruction A leaves the upper pipe450and is directed to lower pipelines160or170for further execution.

In a conventional processor that does not utilize a WGHR416and employs only a GHR to store branch history information and executed the exemplary group of instructions, the predicted value returned from a BHT for instruction B+8 may not be accurate. This is because the address hashing logic circuit would use the value of the GHR in Processor Cycle4to determine the entry in the BHT for instruction B+8, (e.g. the value “000” would have been used). This value of the GHR does not accurately reflect the actual branch history encountered by the processor because the branch history information for instruction A was not accurately reflected. If the same instruction sequence was subsequently executed, but this time, the processor experienced a delay when fetching instruction B+8, (i.e. the contents of the GHR were updated by the time the address hashing logic circuit used the value of the GHR to access the BHT entry) a different entry into the BHT may be accessed. In this case, a processor using only a GHR to store branch history information could access two different BHT entries for the same conditional branch instruction having the same instruction execution sequence.

In one embodiment, when instruction A is in the DCD stage410, the WGHR416is rewritten with the prediction value the same time the GHR414is loaded. By writing both registers with the same prediction value at the same time, the two registers are synchronized for instruction A. Since it is uncommon that two conditional branch instructions will be predicted taken immediately following one another, there is little chance that synchronizing the two registers will lose any branch history information.

In Processor Cycle5, instructions B and B+4 enter the IDA stage408while instructions B+8 and B+12 enter the IC2stage406. Also in Processor Cycle5, the fetch group address for instructions B+16 and B+20 are sent to the instruction cache106, BTAC130and BHT140. In the IC2Stage406, instruction B+8 returns a BTAC hit. Since instruction B+8 is a BTAC hit, the processor100also determines that instruction B+8 is a conditional branch instruction and its prediction value returned from the BHT140during the IC2stage406is shifted into the WGHR416. In this example, instruction B+8 is also predicted taken. The actual entry in the BHT140may be either strongly taken (11) or weakly taken (10). Because instruction B+8 is a predicted taken branch instruction, instructions B+12, B+16 and B+20 will be flushed by the fetch logic circuit402after instruction B+8 leaves the IC2stage406and the target address reflecting instruction C (received from the BTAC hit) is directed to the fetch logic circuit402. The contents of the WGHR416are updated with the prediction value of taken (“1”) and the value is latched at the beginning of Processor Cycle6as reflected in the timing diagram600.

In Processor Cycle6, instructions B and B+4 enter the DCD stage410while instruction B+8 enters the IDA stage408. Also during Processor Cycle6, the fetch group address for instruction C is sent to the Instruction Cache106, BTAC130and BHT140(IC1stage404). At the end of Processor Cycle6, instructions B and B+4 leave the upper pipe450and are directed to lower pipelines160or170for further execution.

In Processor Cycle7, instruction B+8 is processed during the DCD stage410. During the DCD stage410, instruction B+8 is confirmed as a conditional branch instruction and its prediction value is also confirmed. The prediction value identified for instruction B+8 is shifted into the GHR414and reloaded into the WGHR416during Processor Cycle7. Instructions C and C+4 are returned from the Instruction Cache106during the IC2stage406. At the end of Processor Cycle7, instruction B+8 leaves the upper pipe450and is directed to lower pipelines160or170for further execution.

In code segments where branch instructions may be executed in close proximity to one another (based on the depth of the pipeline), the latest branch history information is used to process branch predictions.

During Processor Cycle8, the value of the GHR414is latched along with the WGHR416. Instructions C and C+4 are processed during the IDA stage408and any sequential instructions following instruction C and C+4 may be fetched and executed.

FIG. 7is a flow chart displaying an instruction process flow700taken by the processor100executing nstructions using a Working Global History Register (WGHR)416. The instruction process flow700starts at block702. The instruction process flow proceeds to block704where the fetch logic circuit402sends the fetch group address to the BTAC130and the address hashing logic circuit420(for indexing into the BHT140). As mentioned previously, the sending of the fetch group address may occur during the IC1stage404in the processor100. At block704, results of searching the BTAC130(to determine if the instruction being fetched is a branch instruction) are returned. The results are returned during the IC2stage406. From block704, the instruction process flow700proceeds to decision block706. The processor100determines if a BTAC hit has occurred at decision block706. This determination may also occur during the IC2stage406. As explained previously, a BTAC hit may occur for a conditional branch instruction or a taken unconditional branch instruction. If there is no BTAC hit (e.g. a BTAC miss), the instruction process flow700proceeds directly to block712.

If there is a BTAC hit, the instruction process flow700proceeds to block710. At block710, the WGHR416is updated by shifting the prediction value retrieved from the BHT140into the WGHR416. For example, a “1” is shifted into the WGHR416if the branch instruction is predicted taken or a “0” is shifted in if the prediction is not taken. Depending upon the implementation, the prediction value may be returned during any processor execution stage prior to a decode stage. In the embodiment as previously described the WGHR416is updated during the IC2stage406.

The instruction process flow700proceeds to block712where the instruction passes through a Decode Stage (e.g. the DCD Stage410). During the Decode Stage, at block712, the instruction may be confirmed as a branch instruction. After the instruction is executed in the decode stage, the instruction process flow700proceeds to decision block714. If at decision block714, the instruction is not a branch instruction, the instruction process flow700ends at block720.

If at block714, the processor100confirms that the instruction is a branch instruction, the instruction process flow700proceeds to block716. At block716, the WGHR416and GHR414are updated with the appropriate branch history information and the instruction process flow ends at block720.