Method and apparatus for precalculating a direct branch partial target address during a misprediction correction process

An example method of storing a partial target address in an instruction cache includes receiving a branch instruction. The method also includes predicting a direction of the branch instruction as being not taken. The method further includes calculating a destination address based on executing the branch instruction. The method also includes determining a partial target address using the destination address. The method further includes in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in an instruction cache with the partial target address.

FIELD OF DISCLOSURE

The present disclosure generally relates to processors, and more particularly to storing an address in an instruction cache.

BACKGROUND

Many portable products, such as cell phones, laptop computers, personal digital assistants (PDAs) or the like, incorporate one or more processors executing programs that support communication and multimedia applications. A processor for such products conventionally has a hierarchical memory configuration with multi-levels of caches including an instruction cache, a data cache, and system memory. The processor may need to operate with high performance and efficiency to support the plurality of computationally intensive functions for such products.

Further, the processor may be pipelined and support execution of conditional branch instructions. The execution of a conditional branch instruction in a pipelined processor may stall the pipeline pending the determination of the condition. To avoid stalling the processor, some form of branch prediction may be employed early in the pipeline. The branch prediction may allow the processor to speculatively fetch and execute instructions based on a predicted branch behavior.

BRIEF SUMMARY

This disclosure relates to processors. Methods, systems, and techniques for storing an address in an instruction cache are provided.

According to an embodiment, a method of storing a partial target address in an instruction cache includes receiving a branch instruction. The method also includes predicting a direction of the branch instruction as being not taken. The method further includes calculating a destination address based on executing the branch instruction. The method also includes determining a partial target address using the destination address. The method further includes in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in an instruction cache with the partial target address.

According to another embodiment, an apparatus for storing a partial target address in an instruction cache includes a processor that is operable to receive a branch instruction. The processor is also operable to predict a direction of the branch instruction as being not taken. The processor is further operable to calculate a destination address based on executing the branch instruction. The processor is also operable determine a partial target address using the destination address. The processor is further operable to in response to the predicted direction of the branch instruction changing from not taken to taken, replace an offset in an instruction cache with the partial target address.

According to another embodiment, a non-transitory computer-readable medium has stored thereon computer-executable instructions for performing operations including receiving a branch instruction; predicting a direction of the branch instruction as being not taken; calculating a destination address based on executing the branch instruction; determining a partial target address using the destination address; and in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in an instruction cache with the partial target address.

According to another embodiment, an apparatus for storing a partial target address in an instruction cache includes means for receiving a branch instruction; means for predicting a direction of the branch instruction as being not taken; means for calculating a destination address based on executing the branch instruction; means for determining a partial target address using the destination address; and means for in response to the predicted direction of the branch instruction changing from not taken to taken, replacing an offset in an instruction cache with the partial target address.

DETAILED DESCRIPTION

I. OverviewII. Example Processor ArchitectureA. Initialize Prediction Direction of Branch Instruction As Not TakenB. Calculate Partial Target AddressIII. Change Predicted Direction of Branch InstructionsA. Not Taken to TakenB. Taken to not TakenC. Maintain the CacheD. Bimodal PredictionIV. Example MethodV. Example Wireless Device
I. Overview

It is to be understood that the following disclosure provides many different embodiments, or examples, for implementing different features of the present disclosure. Some embodiments may be practiced without some or all of these specific details. Specific examples of components, modules, and arrangements are described below to simplify the present disclosure. These are, of course, merely examples and are not intended to be limiting.

A processor may support execution of conditional branch instructions. A branch instruction may be a conditional jump instruction that directs program execution to a designated instruction that breaks the sequential program flow (branch instruction is taken) or to the next instruction (falls through). The branch instruction may also be an unconditional jump instruction that always jumps to a new location in the program.

The destination address of a direct jump instruction may be calculated by adding the current program counter to the immediate offset included in the instruction. For example, an immediate offset may be bits [23:11] of a 32-bit encoding instruction and stored in a cache. This process of adding the current program counter to the immediate offset, however, may occupy a long timing delay. This may be especially true for 32-bit or 64-bit processors.

This disclosure provides techniques to quickly determine the destination address when the direction of the branch instruction is predicted as being taken. A partial target address of a direct jump instruction may be recalculated and replace the immediate offset in the cache. When the direct jump instruction is encountered, the partial target address in the cache may be used to determine the destination address of the direct jump instruction. Accordingly, when the direct jump instruction is encountered and the direct jump instruction is predicted as being taken, it may be unnecessary to add the current program counter to the immediate offset.

In a fixed-instruction length processor, the base address is easily loaded into the instruction cache via an interface between the instruction cache and outside memory (e.g., main memory, L2 cache, or L3 cache). This is because the base address may be easily determined in a fixed-instruction length processor. Thus, the partial address calculation may be determined by adding the known base address and offset.

In a dynamic-instruction length processor, however, the process of calculating and storing the partial address calculation is much more difficult. A reason for this difficulty is that in the dynamic-instruction length processor, the base address is not easily determined. In an example, for a very long instruction word (VLIW) processor, the instruction packet may contain a dynamic number of instructions, and the packet may cross cache lines. The program counter of the first instruction in the packet may calculate the jump instruction destination address. In cross cache line cases, however, the first instruction program counter may not be easily determined when the precalculation is performed. A complex method may be implemented to determine within a packet the first instruction program counter in another cache line. In a dynamic-instruction length processor, the immediate extension in one packet may be determined. If the extension is in a different cache line from the jump instruction, the base address is not easily identified in the instruction cache and the precalculation is very difficult to determine.

II. Example Processor Architecture

FIG. 1is a block diagram illustrating a processor complex100for storing a partial target address in an instruction cache, according to an embodiment. Peripheral devices that may connect to processor complex100are not shown for clarity of discussion.

Processor complex100includes a processor104including a processor pipeline106and a control circuit108including a program counter (PC)109. PC109may be a processor register that indicates where the processor is in its instruction sequence. Instructions may be retrieved sequentially from memory, and PC109may be incremented automatically after fetching an instruction. Some instructions may interrupt the sequential processing of the program flow by placing a new value in PC109such that an instruction different from the next sequential instruction in the program flow is executed.

Processor104is coupled to an instruction cache130(e.g., Level 1 instruction cache). Instruction cache130may optimize the fetching of instructions from, for example, main memory or an L2 cache, by storing instructions to be executed.

Processor pipeline106may include an instruction fetch stage114, a decode and predict stage116having a predict logic circuit117and a bimodal predictor118, and an execute stage122.

Although four stages in processor pipeline106are shown, other embodiments having fewer than four or more than four stages are within the scope of this disclosure. Further, although a single processor pipeline106is shown, the processing of instructions using decode and predict stage116is applicable to superscalar designs and other architectures implementing parallel pipelines. For example, a superscalar processor designed for high clock rates may have two or inure parallel pipelines supporting multiple threads and each pipeline may divide instruction fetch stage114, decode stage116, and execute stage122into two or more pipelined stages increasing the overall processor pipeline depth to support a high clock rate. Also, for design, implementation, or other reasons, predict logic circuit117may be located elsewhere in processor104. For example, predict logic circuit117may be located in control circuit108.

In processor pipeline106, instruction fetch stage114may be associated with program counter109and may fetch instructions from instruction cache130for processing by later stages. If an instruction fetch misses in instruction cache130, meaning that the instruction to be fetched is not in instruction cache130, the instruction may be fetched from a different memory system. In an example, the instruction is fetched from a Level 2 (L2) cache. In another example, the instruction is fetched from main memory. Further, instructions may be loaded into main memory or the L2 cache from other sources, such as a boot read-only memory (ROM), a hard drive, an optical disk, or from an external interface, such as a network.

In a decode stage116, the fetched instruction is decoded, and in an execute stage122, the instruction is executed. Result operands from execution stage122may take multiple execution cycles to determine a condition used by a conditional branch instruction. During these cycles, processor pipeline106may wait until the result operand is available.

When the branch instruction is in execute stage122, the condition may be determined and the predict logic117may be informed over predict signal123to make forward transitions if the branch instruction is taken and to make reverse transitions if the branch instruction is not taken. The updated state is then passed over bit signal140to store the bimodal prediction bits in the associated branch instruction at a next available write cycle in instruction cache130. The changed bits in the stored branch instruction affect a prediction of a next branch target address the next time the branch instruction is fetched without affecting the function of the instruction.

A. Initialize Prediction Direction of Branch Instruction as not Taken

In instruction fetch stage114, processor104may fetch a branch instruction144from instruction cache130. In a decode and predict stage116, processor104may predict whether the fetched branch instruction144is to be taken or not taken. In an embodiment, processor104predicts a direction of branch instruction144as being not taken. Processor104may predict the direction of branch instruction144as being not taken regardless of whether branch instruction144is a conditional jump instruction or an unconditional jump instruction.

In an example, for each branch instruction, the compiler may initialize the prediction of the direction of the branch instruction as being not taken. The prediction of the direction of the branch instruction as being not taken may be statically determined by the compiler, and the compiler may initialize each branch instruction as being not taken, regardless of whether the branch instruction is a conditional jump instruction or an unconditional jump instruction.

In an example, branch instruction144is a conditional jump instruction, and processor104predicts the direction of the conditional jump instruction as being not taken. In an example, branch instruction144is an unconditional jump instruction, and processor104predicts the direction of the unconditional jump instruction as being not taken.

Predict logic117may predict the direction of the branch instruction as being not taken. If branch instruction114is not taken, predict logic117predicted the direction of the branch instruction correctly. If predict logic117mispredicted the direction of the branch instruction, however, and branch instruction114is taken, processor104may calculate the destination address based on executing the branch instruction. Processor104may then determine a partial target address using the destination address.

B. Calculate Partial Target Address

FIG. 2is a block diagram200illustrating a partial get address being calculated and stored in the instruction cache.

Diagram200includes a 32-bit instruction format202including a jump code, a 23-bit offset206, and a predict bit208. The predict bit in a conditional branch instruction, such as predict bit208, may be statically determined prior to loading a program. In an embodiment, the prediction bit predicts the direction of the branch instruction. In an example, all branch instructions are initially predicted by a compiler as being not taken. The prediction bit may be embedded in the operation code

In an example, when predict bit208has a value of one, the branch instruction is predicted as not taken, and when predict bit208has a value of zero, the branch instruction is predicted as taken. In another embodiment, when predict bit208has a value of zero, the branch instruction is predicted as not taken, and when predict bit208has a value of one, the branch instruction is predicted as taken. Although predict bit208is illustrated inFIG. 2as including one bit, other embodiments having predict bit208including more than one bit are within the scope of this disclosure.

To determine a destination address of the jump code, offset206my be added to the current program counter. Further, some of the bits in the direct jump destination address may be used to access instruction cache130. In an embodiment illustrated inFIG. 2, in the whole destination program counter, only bits [11:5] of the partial destination is timing critical. These bits may be retrieved and used to determine the destination address.

Referring toFIG. 1, instruction fetch stage114may include an adder that adds the current program counter to the offset to determine fetch the appropriate instruction. It may be beneficial to eliminate this adder. Further, when the branch instruction is mispredicted, the associated speculatively fetched instructions may be flushed from processor pipeline106and new instructions may be fetched from the determined branch address. Such misprediction may reduce processor performance and increase power usage.

This disclosure describes a technique that may overcome these disadvantages. For example, by writing the partial target address to instruction cache130after a misprediction occurs, it may be unnecessary to include the adder in instruction fetch stage114. Rather, bimodal predictor118may include an adder to calculate the destination address and the adder may be used based on a misprediction, thus eliminating the adder in instruction fetch stage114. In this way, the amount of area needed to sustain adders may be reduced.

Further, writing the partial target address to instruction cache130after a misprediction occurs may have an additional advantage of consuming less power. In particular, rather than predict logic117attempting to predict each branch instruction accurately and calculating every possible target address, the prediction of the direction of the branch instruction may be initialized as being not taken, and this may consume less power from the beginning of program execution. Although a misprediction may artificially occur because the direction of the branch instruction is initially set to being not taken (even if the branch instruction is taken or has a high probably of being taken), the slight delay due to the initial mispredict may be tolerable because at some point before predict logic117predicts the direction of the branch instruction as being taken, the proper target address for the branch instruction will already have been computed. Accordingly, when predict logic117predicts the direction of the branch instruction as being taken, it may be unnecessary to add the current program counter and the offset because the proper target address is already stored in the cache.

After one or more predictions that the direction of the branch is not taken, a misprediction may occur based on the branch instruction actually being taken. Predict logic117may calculate the destination address based on executing the branch instruction. InFIG. 2, base program counter [31:0] may be concatenated with partial destination [13:0] to determine the destination address. Further, partial destination PC[11:5] may be used to touch the set associative cache. To access instruction cache130, it may be unnecessary for processor104to know the whole destination address. Rather, processor may access instruction cache130by using only the partial target address. The partial target address may be represented by the lower N bits of the base address (e.g., bits11-5of the base address) and may be used as an index into instruction cache130.

Diagram200includes a 32-bit instruction format202including the jump code, a 23-bit partial target address216, and predict bit218. Partial target address216may replace offset206in instruction cache130. Further, because the branch instruction was taken, predict bit218may be set to one. Accordingly, when the branch instruction is encountered next time, predict logic117may predict the direction of the branch instruction as being taken. When the branch instruction is predicted as being taken, the partial target address is stored in instruction cache130.

III. Change Predicted Direction of Branch Ins

A. Not Taken to Taken

In response to the predicted direction of the branch instruction changing from not taken to taken, processor104may replace an offset in an instruction cache with the partial target address. The direction of the branch instruction may transition from taken to not taken or from not taken to taken for various reasons. In an example, if the branch instruction is actually taken, the predicted direction of the branch instruction becomes or stays at taken. Similarly, if the branch instruction is actually not taken, the predicted direction of the branch instruction becomes or stays at not taken.

The instruction cache may include the proper target address such that when the direction of the branch instruction is eventually predicted as being taken, the proper target address may be retrieved from the cache and used. In this way, it may be unnecessary to calculate the proper target address when predict logic117predicts the direction of the branch instruction as being taken. Accordingly, the penalty of using the adder to add the current program counter and the offset is not incurred when predict logic117predicts the direction of the branch instruction as being taken.

B. Taken to not Taken

After the branch instruction has been changed to taken, it may be changed back to not taken. In an embodiment, in response to the predicted direction of the branch instruction changing from taken to not taken, processor104replaces the partial target address in the instruction cache with the offset.

The offset may be recalculated by subtracting the program counter from the destination address. In response to the predicted direction of the branch instruction changing from not taken to taken, the destination address may be known. Further, the value of the current program counter may be known. Thus, the offset may be determined based on knowing the current value of the program counter and knowing the destination address. Further, it may be unnecessary to store both the offset and the partial target address in the cache because the offset and/or partial target address may be recalculated based on knowing the value of the current program counter and destination address.

C. Maintain the Cache

The cache may include the offset or the partial target address. It may be desirable to keep track of which value is in the cache so that values do not improperly overwrite the offset value and/or partial target address in the cache. For example, in response to the predicted direction of the branch instruction maintaining its state, it may be undesirable to add the base address again to the value in the cache. In particular, in response to the predicted direction of the branch instruction changing from not taken to taken, an offset in an instruction cache is replaced with the partial target address. The partial target address is the sum of the current program counter and the offset. When the predicted direction of the branch instruction changes again from not taken to taken, it may be undesirable to perform this action again because an incorrect value would be placed in the cache (e.g., current program counter+current program counter+offset).

The indication of whether the cache includes the offset or the partial target address may be implemented in various ways. For example, in an embodiment; the branch instruction may include a separate bit that indicates whether the cache has been updated with the partial target address. In an example, the bit may be set to 0 when the cache includes the offset and may be set to 1 when the cache includes the partial target address. When the state transitions from not taken to taken, the bit may be set to 1. When the state transitions from taken to not taken, the bit may already be set, indicating that the cache already includes the correct partial target address. Accordingly, the cache may stay as is.

In another embodiment, processor104stores a register the bit indicating whether the cache has been updated with the partial target address, in another embodiment, processor104stores in main memory the bit indicating whether the cache has been updated with the partial target address.

In an embodiment, decode and predict stage116includes a finite state machine implementation of bimodal predictor circuit118.

FIG. 3is an illustration of a finite state machine implementation, according to an embodiment. In an example; a branch instruction includes prediction bit208and a Q bit (not shown) that may be set to a one value to indicate a strong prediction, and to a zero value to indicate a weak prediction. An initial or default setting for the Q bit may be zero, for example. Both of the bimodal predictor bits may be statically determined by an analysis of a program and specified in the branch instruction prior to executing the program.

In an example, the branch instruction is initiated in a strongly not taken state (“00”)302. If the branch instruction is taken, the branch instruction may enter a weakly not taken state (“01”)304. If the branch instruction is not taken, however, the branch instruction may maintain its state. From the weakly not taken state, if the branch instruction is taken, the branch instruction may enter a weakly taken state (“10”)306. If the branch instruction is not taken, however, the branch instruction may enter a strongly not taken state (“00”)302, and so on. Similarly, from the weakly taken state, if the branch instruction is taken, the branch instruction may enter a strongly taken state (“11”)308. If the branch instruction is not taken, however, the branch instruction may enter the weakly not taken state (“01”)304. Similarly, from the strongly taken state, if the branch instruction is taken, the branch instruction may maintain its state. If the branch instruction is not taken, however, the branch instruction may enter a weakly taken state (“10”)306.

These bits may be embedded in the operation code, and the bimodal prediction bits in the retrieved branch instruction may be used in decode and predict stage116to predict whether the fetched conditional branch instruction is to be taken or not taken. Further instructions may be speculatively fetched based on the prediction.

In an embodiment, when the predicted direction of the branch instruction changes from not taken to taken, the offset in the instruction cache is replaced with the partial target address. Further, when the predicted direction of the branch instruction changes from taken to not taken, the partial target address in the instruction cache is replaced with the offset. In this embodiment, before the offset replaces the partial target address, or vice versa, a state transition from taken to not taken (or vice versa) occurred. Accordingly, when the state changes from weakly not taken to strongly not taken (or vice versa) or changes from weakly taken to strongly taken, the offset in the instruction cache is not replaced with the partial target address and the partial target address in the instruction cache is not replaced with the offset.

IV. Example Method

FIG. 4is a flowchart illustrating a method400of storing a partial target address in an instruction cache, according to an embodiment. Method400is not meant to be limiting and may be used in other applications.

Method400includes steps410-450. In a step410, a branch instruction is received. InFIG. 1, instruction fetch114may receive a branch instruction. In an example, the branch instruction is a conditional jump instruction. In another example, the branch instruction is an unconditional jump instruction.

In a step420, a direction of the branch instruction is predicted as being not taken. Predict logic217may predict a direction of the branch instruction as being not taken. The branch instruction may include a bit that indicates whether or not the branch instruction is predicted as being taken or not taken. For example, inFIG. 2, predict bits208and218may indicate whether or not the branch instruction is predicted as being taken or not taken. The compiler may determine this and place this prediction in the branch instruction. In an embodiment, all branch instructions are predicted as being not taken. If the branch instruction was not taken, then predict logic217was correct and program flow should continue. If the branch was taken, then predict logic217was incorrect and the destination address should be calculated.

In a step430, a destination address is calculated based on executing the branch instruction. Bimodal predictor118may calculate a destination address based on executing the branch instruction. When predict logic117incorrectly mispredicts, the destination address is calculated to determine the correct address that stores the next instruction in the program.

In a step440, a partial target address is determined using the destination address. Bimodal predictor118may determine a partial target address using the destination address. In an example, the partial target address may be a particular number of bits in the destination address.

In a step450, in response to the predicted direction of the branch instruction changing from not taken to taken, an offset in an instruction cache is replaced with the partial target address. In an example, in response to the predicted direction of the branch instruction changing from not taken to taken, bimodal predictor118may replace an offset in an instruction cache with the partial target address. InFIG. 2, partial target address216my replace offset206in the jump opcode. The jump opcode storing partial target address216may be stored in the cache. When the direction of the branch instruction is predicted as being taken, the jump opcode storing partial target address216may be retrieved from the cache and used to determine the destination address.

It is also understood that additional method steps may be performed before, during, or after steps410-450discussed above. For example, method400may include steps of splitting an instruction into a plurality of phases and executing the instruction in the plurality of phases. It is also understood that one or more of the steps of method500described herein may be omitted, combined, or performed in a different sequence as desired.

V. Example Wireless Device

Embodiments may be suitable employed in any processor system supporting branch prediction and supporting a memory hierarchy having one or more caches.

FIG. 5is a block diagram illustrating a wireless device500including a digital signal processor, according to an embodiment. Device500includes a processor, such as a digital signal processor (DSP)501to process one or more instructions. DSP501may include processor pipeline106and control circuit108, and a memory550may include branch instruction144. In an example, DSP501processes branch instruction144according toFIG. 1and the method ofFIG. 4, or any combination thereof.

FIG. 5also shows a display controller530that is coupled to DSP501and to a display532. A coder/decoder (CODEC)534may also be coupled to DSP501. A speaker536and a microphone538may be coupled to CODEC534. Additionally, a wireless controller540may be coupled to DSP501and to a wireless antenna548. In an embodiment, DSP501, display controller532, memory550, CODEC534, and wireless controller540are included in a system-in-package or system-on-chip device556.

In an embodiment, input device530and a power supply560are coupled to system-on-chip device556. Moreover, in an embodiment, as illustrated inFIG. 5, display528, input device530, speaker536, microphone538, wireless antenna548, and power supply560are external to system-on-chip device556. Each of display532, input device530, speaker536, microphone538, wireless antenna548, and power supply560may be coupled to a component of system-on-chip device556, such as an interface or a controller.