142 results about "Branch target address" patented technology

An instruction cache (I-Cache) for a processor is configured to include a Branch Target Extension associated with each Instruction Sector. When an Instruction Sector is fetched, the Branch Target Extension is simultaneously fetched. If the Instruction Sector has a branch instruction that is predicted taken, then the branch target address in the branch extension is used to access the next Instruction Sector. In other embodiments, each Instruction Sector has a plurality of Branch Target Extensions each corresponding to a potential branch instruction in an Instruction Sector. In this case, the Branch Target Extensions are partitioned into an instruction index field for locating branch instruction in the Instruction Sector, a local predictor field for predicted taken status and a target address field for the branch target address. The least significant bits of the instruction fetch address are compared to the instruction indexes to determine a particular Branch Target Extension to use.

A system and method for efficient improvement of branch prediction in a microprocessor with negligible impact on die-area, power consumption, and clock cycle period. It is determined if a program counter (PC) register contains a polymorphic indirect unconditional branch (PIUB) instruction. One determination may be searching a table with a portion or all of a PC of past PIUB instructions. If a hit occurs in this table, the global shift register (GSR) is updated by shifting a portion of the branch target address into the GSR, rather than updating the GSR with a taken / not-taken prediction bit. The stored value in the GSR is input into a hashing function along with the PC in order to index prediction tables such as a pattern history table (PHT), a branch target buffer (BTB), an indirect target array, or other. The updated value due to the PIUB instruction improves the accuracy of the prediction tables.

A multithreaded microprocessor includes an instruction fetch unit that may fetch and maintain a plurality of instructions belonging to one or more threads and one or more execution units that may concurrently execute the one or more threads. The instruction fetch unit includes a target branch prediction unit that may provide a predicted branch target address in response to receiving an instruction fetch address of a current indirect branch instruction. The branch prediction unit includes a primary storage and a control unit. The storage includes a plurality of entries, and each entry may store a predicted branch target address corresponding to a previous indirect branch instruction. The control unit may generate an index value for accessing the storage using a portion of the instruction fetch address of the current indirect branch instruction, and branch direction history information associated with a currently executing thread of the one or more threads.

A branch prediction instruction is provided that includes hint information for indicating a storage location for associated branch prediction information in a hierarchy of branch prediction storage structures. When the hint information is in a first state, branch prediction information is stored in a first structure that provides single cycle access to the stored information. When the hint information is in a second state, the branch prediction information is stored in a second structure that provides slower access to the stored information.

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 processor element, structured to execute a 32-bit fixed length instruction set architecture, is backward compatible with a 16-bit fixed length instruction set architecture by translating each of the 16-bit instructions into a sequence of one or more 32-bit instructions. Switching between 16-bit instruction execution and 32-bit instruction execution is accomplished by branch instructions that employ a least significant bit position of the address of the target of the branch to identify whether the target instruction is a 16-bit instruction or a 32-bit instruction.

For a processor having instruction codes of two instruction lengths (16 bits and 32 bits), methods of locating the instruction codes are limited to two types: (1) two 16-bit instruction codes are stored within 32-bit word boundaries, and (2) a single 32-bit instruction code is stored intactly within the 32-bit word boundaries. A branch destination address is specified only on the 32-bit word boundary. The MSB of each instruction code serves as a 1-bit instruction length identifier for controlling the execution sequence of the instruction codes. This provides two transfer paths from an instruction fetch portion to an instruction decode portion within the processor, achieving reduction in code side and in the amount of hardware and, accordingly, the increase in operating speed.

Under the present invention, a branch target address corresponding to a target instruction to be pre-fetched is predicted based on two values. The first value is a “predictor value” that is known for the branch target address. The second value is the address of the branch instruction from which the target instruction is branched to within the program code. Once these two values are provided, they can be processed (e.g., hashed) to yield an index value, which is used to obtain a predicted branch target address from a cache. This technique is generally implemented for branch instructions such as switch statements or polymorphic calls. In the case of the former, the predictor value is a selector operand, while in the case of the latter the predictor value is a class object address (in JAVA) or a virtual function table address (in C++).

An apparatus and method in a pipelined microprocessor for replacing one of two target addresses in a branch target address cache (BTAC) line. If only one of the two entries is invalid, the invalid entry is replaced. If both entries are valid, the least recently used entry is replaced. If both entries are invalid, the entry is replaced corresponding to the side of the BTAC, indicated by a global status register, not last written to with an invalid entry. In one embodiment, the global status is updated only if a side is written when both entries are invalid. In another embodiment, the BTAC stores N entries per line, where N is greater than 1. The status register maintains information for determining which of the N sides is least recently written. The least recently written side is chosen for replacement.

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 system and method for branch prediction in a microprocessor. A branch prediction unit stores an indication of a location of a branch target instruction relative to its corresponding branch instruction. For example, a target instruction may be located within a first region of memory as a branch instruction. Alternatively, the target instruction may be located outside the first region, but within a larger second region. The prediction unit comprises a branch target array corresponding to each region. Each array stores a bit range of a branch target address, wherein the stored bit range is based upon the location of the target instruction relative to the branch instruction. The prediction unit constructs a predicted branch target address by concatenating a bits stored in the branch target arrays.

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.

In one embodiment, a processor implements an indirect branch target predictor to predict target addresses of indirect branch instructions. The indirect branch target predictor may store target addresses generated during previous executions of indirect branches, and may use the stored target addresses as predictions for current indirect branches. The indirect branch target predictor may also store a validation tag corresponding to each stored target address. The validation tag may be compared to similar data corresponding to the current indirect branch being predicted. If the validation tag does not match, the indirect branch is presumed to be mispredicted (since the branch target address actually belongs to a different instruction). The indirect branch target predictor may inhibit speculative execution subsequent to the mispredicted indirect branch until the redirect is signalled for the mispredicted indirect branch.

Execution of non-native operating system images within a virtualized computer system is improved by providing a mechanism for retrieving translated code physical addresses corresponding to un-translated code branch target addresses using a host code map. Hardware acceleration mechanisms, such as content-accessible look-up tables, directory hardware, or processor instructions that operate on tables in memory can be provided to accelerate the performance of the translation mechanism. The virtual address of the branch instruction target is used as a key to look up a corresponding record that contains a physical address of the translated code page containing the translated branch instruction target, and execution is directed to the physical address obtained from the record, once the physical page containing the translated code corresponding the target address is loaded in memory.

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 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.

Apparatus and techniques for predicting a storage address based on contents of a first program accessible register (PAR) specified in a first instruction, wherein the first PAR correlates with a target address specified by a second PAR in a second instruction. Information is speculatively fetched at the predicted storage address prior to execution of the second instruction. The first instruction is an advance correlating notification (ADVCN) instruction, the second instruction is an indirect branch instruction, and the information is a plurality of instructions beginning at the predicted storage address. The predicted storage address is a branch target address for the indirect branch instruction from which instructions are speculatively fetched. The prediction is based on contents of the first PAR specified in the ADVCN instruction. The contents of the first PAR correlate with a taken evaluation of the branch instruction.

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.

The invention provides a production-line processor device for rapidly disposing a prediction error of a branch instruction. The production-line processor device comprises a production-line processor, a branch prediction unit, a branch result detection unit, a branch instruction fetching redirection unit and a production-line control unit, wherein the production-line processor at least comprises an instruction fetching section, a decoding section, an emission section, an execution section and a retirement section in sequence; the branch prediction unit is used for early predicting a branch direction and a target address; the branch result detection unit is used for computing an actual branch direction and an actual target address, comparing the predicted branch direction and target address which are delivered by the branch prediction unit with the actual branch direction and the actual target address, and judging whether a prediction error of the branch instruction happens or not; the branch instruction fetching redirection unit is used for receiving a detection result and the actual branch target address, and if the prediction error of the branch instruction happens, an instruction fetching member is immediately informed; and the production-line control unit is used for receiving the detection result generated by the branch result detection unit, and if the prediction error of the branch instruction is found, all levels of production lines are controlled to handle the branch prediction error. According to the production-line processor device provided by the invention, the production-line do-nothing operation caused by the prediction error of the branch instruction can be eliminated or greatly reduced and the performance of the production-line processor is improved.

A microcode patch apparatus including a patch array, a mux, and a RAM. The patch array receives a microcode ROM address and determines that the microcode ROM address matches one of a plurality of entries within the patch array. The patch array outputs a corresponding branch instruction and asserts a hit signal. The branch instruction prescribes a microcode branch target address. The mux receives the branch instruction from the patch array and a micro instruction corresponding to the microcode ROM address from a microcode ROM. The mux provides the micro instruction or the corresponding branch instruction to an instruction register based upon the state of the hit signal. The RAM stores a plurality of patch instructions that are to be executed in place of the micro instruction. The first one of the plurality of patch instructions is stored at a location in the RAM corresponding to the microcode branch target address.

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.

Methods and apparatus are provided for branch prediction in a digital processor. A method includes providing a branch target buffer having a tag array and a data array, wherein each entry in the tag array provides an index to a corresponding entry in the data array, storing in a selected entry in the tag array information representative of a branch target of a current branch instruction, storing in a corresponding entry in the data array information representative of a branch target of a next branch instruction, and providing the information representative of the branch target of the next branch instruction in response to a match to an entry in the tag array. The information representative of the branch target of the next branch instruction may include a taken branch target address of the next branch instruction and an offset value. The offset value may represent an address of a next sequential instruction following the next branch instruction.

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 method and data processing system allocates entries in a branch target buffer (BTB). Instructions are fetched from a plurality of instructions and one of the plurality of instructions is determined to be a branch instruction. A corresponding branch target address is determined. A determination is made whether the branch target address is stored in a branch target buffer (BTB). When the branch target address is not stored in the branch target buffer, an entry in the branch target buffer is identified for allocation to receive the branch target address based upon stored metrics such as data processing cycle saving information and branch prediction state. In one form the stored metrics are stored in predetermined fields of the entries of the BTB.