59 results about "Branch target address cache" patented technology

An apparatus for speculatively predicting the direction of a branch instruction in a pipelined microprocessor in a hybrid fashion. A branch target address cache (BTAC) stores a direction prediction about executed branch instructions. The BTAC is indexed by an instruction cache fetch address. The BTAC is accessed in parallel with the instruction cache access, such that the direction prediction is provided before the actual instruction is decoded which is presumed to be a branch instruction corresponding to the direction prediction stored in the BTAC. In parallel with the BTAC access, a branch history table (BHT) is accessed to provide a second speculative direction prediction. The BHT is indexed with a gshare function of the instruction cache fetch address and a global branch history stored in a global branch history register. The BTAC also provides a selector that selects between the two speculative direction predictions.

A branch control apparatus in a microprocessor. The apparatus includes a branch target address cache (BTAC) that caches indications of whether a branch instruction wraps across two cache lines. When an instruction cache fetch address of a first cache line containing the first part of the branch instruction hits in the BTAC, the BTAC outputs a target address of the branch instruction and indicates the wrap condition. The target address is stored in a register. The next sequential fetch address selects a second cache line containing the second part of the branch instruction. After the two cache lines containing the branch instruction are fetched, the target address from the register is provided to the instruction cache in order to fetch a third cache line containing a target instruction of the branch. The three cache lines are stored in order in an instruction buffer for decoding.

A branch control apparatus in a microprocessor. A register receives a first cache line containing a branch instruction from an instruction cache in response to a fetch address. The fetch address hits in a BTAC that provides a target address of the branch instruction. The BTAC also provides an offset of the instruction following the branch instruction. The instructions following the branch instruction are invalidated based on the offset. Muxing logic packs only the valid instructions into a byte-wide instruction buffer that is directly coupled to instruction format logic. The instruction cache provides a second cache line containing the target instructions to the register in response to the target address. The instructions preceding the target instructions are invalidated based on the lower bits of the target address. The muxing logic packs only the valid target instructions into the instruction buffer immediately adjacent to the branch instruction bytes.

A processor includes an execution unit and instruction sequencing logic that fetches instructions for execution. The instruction sequencing logic includes a branch target address cache having a branch target buffer containing a plurality of entries each associating at least a portion of a branch instruction address with a predicted branch target address. The branch target address cache accesses the branch target buffer using a branch instruction address to obtain a predicted branch target address for use as an instruction fetch address. The branch target address cache also includes a filter buffer that buffers one or more candidate branch target address predictions. The filter buffer associates a respective confidence indication indicative of predictive accuracy with each candidate branch target address prediction. The branch target address cache promotes candidate branch target address predictions from the filter buffer to the branch target buffer based upon their respective confidence indications.

A branch control apparatus in a microprocessor. The branch control apparatus includes an instruction buffer having a plurality of stages that buffer cache lines of instruction bytes received from an instruction cache. A multiplexer selects one of the bottom three stages in the instruction buffer to provide to instruction format logic. The multiplexer selects a stage based on a branch indicator, an instruction wrap indicator, and a carry indicator. The branch indicator indicates whether the processor previously branched to a target address provided by a branch target address cache. The branch indicator and target address are previously stored in association with the stage containing the branch instruction for which the target address is cached. The wrap indicator indicates whether the currently formatted instruction wraps across two cache lines. The carry indicator indicates whether the current instruction being formatted occupies the last byte of the currently formatted instruction buffer stage.

A branch prediction apparatus having a primary predictor and a secondary predictor that selectively overrides the primary predictor based on the type of branch instruction decoded. A branch target address cache in the primary branch predictor speculatively predicts a branch target address and direction based on an instruction cache fetch address prior to decoding the instruction, and the processor branches to the speculative target address if the speculative direction is predicted taken. Later in the pipeline, decode logic decodes the instruction and determines the branch instruction type, such as whether the branch instruction is a conditional branch, a return instruction, a program counter-relative type branch, an indirect branch, etc. Depending upon the branch type, if the primary and secondary predictions do not match, the processor branches based on the secondary prediction to override the branch taken based on the primary prediction.

A microprocessor caches in a branch target address cache (BTAC), for each of a plurality of previously executed branch instructions: a prediction of whether the branch instruction will be taken and is present in a cache line of instruction bytes provided by an instruction cache in response to a fetch address, a target address of the branch instruction, and a location of an opcode byte of the branch instruction within the cache line. The instruction cache provides the cache line to an instruction buffer and the BTAC provides the prediction, the target address, and the location in response to the fetch address. The microprocessor branches to the target address. A byte in the cache line within the instruction buffer indicated by the location provided by the BTAC is marked. An instruction decoder formats the instruction bytes in the cache line. The microprocessor erroneously branched to the target address if the instruction decoder indicates the marked byte is in a non-opcode location within one of the formatted instructions.

A branch control apparatus in a microprocessor. The apparatus includes a branch target address cache (BTAC) that caches indications of whether a branch instruction wraps across two cache lines. When an instruction cache fetch address of a first cache line containing the first part of the branch instruction hits in the BTAC, the BTAC outputs a target address of the branch instruction and indicates the wrap condition. The target address is stored in a register. The next sequential fetch address selects a second cache line containing the second part of the branch instruction. After the two cache lines containing the branch instruction are fetched, the target address from the register is provided to the instruction cache in order to fetch a third cache line containing a target instruction of the branch. The three cache lines are stored in order in an instruction buffer for decoding.

A branch prediction apparatus having two two-way set associative cache memories each indexed by a lower portion of an instruction cache fetch address is disclosed. The index selects a group of four entries, one from each way of each cache. Each entry stores a single target address of a different previously executed branch instruction. For some groups, the four entries cache target addresses for one branch instruction in each of four different cache lines, to obtain four-way group associativity; for other groups, the four entries cache target addresses for one branch instruction in each of two different cache lines and two branch instructions in a third different cache line, to effectively obtain three-way group associativity, depending on the distribution of the branch instructions in the program. The apparatus trades off associativity for number of predictable branches per cache line on an index-by-index basis to efficiently use storage space.

A data processing system includes an instruction fetching circuit 2, an instruction queue 4 and further processing circuits 6. A branch target cache, which maybe a branch target address cache 8, a branch target instruction cache 10 or both, is used to store branch target addresses or blocks of instructions starting at the branch target respectively. A control circuit 12 is responsive to the contents of the instruction queue 4 when a branch instruction is encountered to determine whether or not storage resources within the branch target cache 8, 10 should be allocated to that branch instruction. Storage resources within the branch target cache 8, 10 will be allocated when the number of program instructions within the instruction queue is below a threshold number and / or the estimated execution time of the program instructions is below a threshold time.

The invention provides a branch predictor and a method for operating the same. The branch predictor contains a block address capable of being used for accessing an instruction byte block of an instruction cache and a first / second byte offset in the instruction byte block. Hash logic performs hash operation on a branch pattern and a first / second address formed by the block address and the first / second byte offset to generate a first / second index. A condition branch predictor receives the first / second index and provides a first / second direction prediction of a first / second condition branch instruction in the instruction byte block in response to the first / second index. In an embodiment, a branch target address cache (BTAC) provides the byte offset, and the first / second direction prediction is statically associated with a first / second target address also provided by the BTAC. Instead, the byte offset is a predetermined value, and the first / second direction prediction is dynamically associated with the first / second target address based on the relative size of the byte offset provided by the BTAC.

A microprocessor includes a branch target address cache (BTAC), each entry thereof configured to store branch prediction information for at most N branch instructions. An execution unit executes a branch instruction previously fetched in a fetch quantum. Update logic determines whether the BTAC is already storing information for N branch instructions within the fetch quantum (N is at least two), updates the BTAC for the branch instruction if the BTAC is not already storing information for N branch instructions, determines whether a type of the branch instruction has a higher replacement priority than a type of the N branch instructions if the BTAC is already storing information for N branch instructions, and updates the BTAC for the branch instruction if the type of the branch instruction has a higher replacement priority than the type of the N branch instructions already stored in the BTAC.

A microprocessor with a write queue for a branch target address cache (BTAC) is disclosed. The BTAC is read in parallel with an instruction cache in order to predict a target address of a branch instruction in the accessed cache line. In one embodiment, the BTAC is single-ported; hence, the single port must be shared for reading and writing. When the BTAC needs updating, such as when a branch target address is resolved, the microprocessor stores the branch target address and related information in the write queue. Thus, the write queue potentially enables updating of the BTAC to be delayed until the BTAC is not being read, such as when the instruction cache is idle, a misprediction by the BTAC is being corrected, or a prediction by the BTAC is being overridden. If the write queue becomes full, then it updates the BTAC anyway.

A multiple stage branch prediction system includes a branch target address cache (BTAC) and a branch predictor circuit. The BTAC is configured to store a BTAC entry. The branch predictor circuit is configured to store state information. The branch predictor circuit utilizes the state information to predict the direction of a branch instruction and to manage the BTAC entry based on modified state information prior to resolution of the branch instruction.

A processor includes an execution unit and instruction sequencing logic that fetches instructions from a memory system for execution. The instruction sequencing logic includes branch logic that outputs predicted branch target addresses for use as instruction fetch addresses. The branch logic includes a level one branch target address cache (BTAC) and a level two BTAC each having a respective plurality of entries each associating at least a tag with a predicted branch target address. The branch logic accesses the level one and level two BTACs in parallel with a tag portion of a first instruction fetch address to obtain a first predicted branch target address from the level one BTAC for use as a second instruction fetch address in a first processor clock cycle and a second predicted branch target address from the level two BTAC for use as a third instruction fetch address in a later second processor clock cycle.

A microprocessor with a write queue for a branch target address cache (BTAC) is disclosed. The BTAC is read in parallel with an instruction cache in order to predict a target address of a branch instruction in the accessed cache line. In one embodiment, the BTAC is single-ported; hence, the single port must be shared for reading and writing. When the BTAC needs updating, such as when a branch target address is resolved, the microprocessor stores the branch target address and related information in the write queue. Thus, the write queue potentially enables updating of the BTAC to be delayed until the BTAC is not being read, such as when the instruction cache is idle, a misprediction by the BTAC is being corrected, or a prediction by the BTAC is being overridden. If the write queue becomes full, then it updates the BTAC anyway.

A Branch Target Address Cache (BTAC) stores a plurality of entries, each BTAC entry associated with a block of two or more instructions that includes at least one branch instruction having been evaluated taken. The BTAC entry includes an indicator of which instruction within the associated block is a taken branch instruction. The BTAC entry also includes the Branch Target Address (BTA) of the taken branch. The block size may, but does not necessarily, correspond to the number of instructions per instruction cache line.