49 results about "Branch history table" patented technology

Apparatus and methods implemented in a processor semiconductor logic chip for providing novel “hint instructions” that uniquely preserve and reuse branch predictions replaced in a branch history table (BHT). A branch prediction is lost in the BHT after its associated instruction is replaced in an instruction cache. The unique “hint instructions” are generated and stored in a unique instruction cache which associates each hint instruction with a line of instructions. The hint instructions contains the latest branch history for all branch instructions executed in an associated line of instructions, and they are stored in the instruction cache during instruction cache hits in the associated line. During an instruction cache miss in an instruction line, the associated hint instruction is stored in a second level cache with a copy of the associated instruction line being replaced in the instruction cache. In the second level cache, the copy of the line is located through the instruction cache directory entry associated with the line being replaced in the instruction cache. Later, the hint instruction can be retrieved into the instruction cache when its associated instruction line is fetched from the second level cache, and then its associated hint instruction is also retrieved and used to restore the latest branch predictions for that instruction line. In the prior art this branch prediction would have been lost. It is estimated that this invention improves program performance for each replaced branch prediction by about 80%, due to increasing the probability of BHT bits correctly predicting the branch paths in the program from about 50% to over 90%. Each incorrect BHT branch prediction may result in the loss of many execution cycles, resulting in additional instruction re-execution overhead when incorrect branch paths are belatedly discovered.

An apparatus for branch prediction includes a history register which stores therein history of previous branch instructions, an index generation circuit which generates a first index from an instruction address and the history stored in the history register, a history table which stores therein a portion of the instruction address as a tag and a first value indicative of likelihood of branching in association with the first index, a branch destination buffer which stores therein a branch destination address or predicted branch destination address of an instruction indicated by the instruction address and a second value indicative of likelihood of branching in association with a second index that is at least a portion of the instruction address, and a selection unit which makes a branch prediction by selecting one of the first value and the second value.

Improved conditional branch instruction prediction by detecting branch aliasing in a branch history table. Each entry in an aliasing table is associated with only one of a plurality of conditional branch instructions tracked by the branch history table. Prior to executing a conditional branch instruction, outcome of the execution of the conditional branch instruction is predicted utilizing the branch history table entry associated with the conditional branch instruction. Outcome of the execution of the conditional branch instruction is also predicted utilizing the aliasing table entry associated with the conditional branch instruction. Branch aliasing is detected by comparing the prediction made utilizing the branch history table with the prediction made utilizing the aliasing table. In response to the predictions being different, a determination is made that branch aliasing occurred, and the prediction made utilizing the aliasing table is utilized for predicting the outcome of the execution of the conditional branch instruction.

A branch history memory stores the branch history. The branch history represents the results in the past. When processing of a branch instruction is finished, a branch history update section updates the branch history corresponding to the branch instruction, based on the processing result. A branch history table update section updates the branch history in a branch history table. The branch history stores the number of recent continuous branching successful and the number recent of continuous branching failures.

The invention relates to branch checkout for reduction of non-control flow commands. Some micro processors are used for checking branch forecast information in a branch history list and / or a branch target buffer. To check the branch forecast information, the micro processors can identify which commands are control flow commands and which are non-control flow commands. To reduce power consumption in the branch history list and / or the branch target buffer, the branch history list and / or the branch target buffer can be used for checking the branch forecast information corresponding to control flow commands, but not the branch forecast information corresponding to non-control flow commands.

One or more methods and systems of reducing the size of memory used in implementing a predictive scheme for executing conditional branch instructions are presented. In one embodiment, a conditional branch instruction addresses a first bit array and a second bit array of a branch history table. The branch history table comprises a first bit array and a second bit array in which the second bit array contains a fraction of the number of entries of said first bit array. In one or more embodiments, the size of the branch history table is reduced by at least twenty five percent, resulting in a reduction of memory required for implementing the predictive scheme.

An information processing apparatus is capable of speculatively performing an execution, such as a pipeline / superscalar / out-of-order execution and equipped with a branch prediction mechanism (a branch history). The information processing apparatus, in order to process an instruction sequence that includes a subroutine at a high speed, is further equipped with a return address stack, of which the stack operation is activated at a time of completing execution of an subroutine call / return correspondent instruction and an entry designating unit (pointer), in order to adjust a time difference resulting from an instruction fetch being executed prior to completing an instruction, pointing to a position relative to the stack front and adjusting a time difference between an instruction fetch performed speculatively in advance and completion of an instruction both at a time of completing execution of a branch instruction that is correspondent to a subroutine call / return and at a time of predicting a subroutine call / return in synchrony to the instruction fetch. An entry position correspondent to a stack position pointed to by the entry designation unit is adopted as a subroutine call / return prediction address and consequently the prediction of the subroutine return address becomes more accurate and the processing speed becomes higher.