Hashing indexer for branch cache

Claim 1

In a pipelined digital processor employing macro-instructions utilizing interpretation by micro-instructions, each of said macro-instructions being identifiable by an assoicated address and each of said micro-instructions being identifiable by an associated addresss, a lookahead fetch system for transmitting predicted brach addresses to a prefetch section prior to decoding of respective brach instructions, comprising: branch cache means coupled to said prefetch section, said branch cache means receiving prefetch information from said prefetch section, and said branch cache means transmitting to said prefetch section predicted branch address information, said branch cache means including a plurality of indexed memory loations for storing an indexed table of branch target addresses, each of said branch target addresses corresponding to an addresss of a previously fetched instruction that resulted from a succeeding execution of said instruction, hashing means for simultaniously receiving and combining a predetermined number of bits representative of the address of a macro-instruction being fetched with a predetermined number of bits representative of the address of a micro-instruction invoked by said macro-instruction, and index means, in communication with said hashing means and said branch cache means, for applying an address, generated by combinations of bits produced by said hashing means, to said branch cache means, to read out a branch target address; whereby a branch target address that is predictive of a branch of a micro-instruction interpreting a macro-instruction is read out of the branch cache means.

Claim 14

A method for predicting branch target addresses for a pipelined digital processing system having a branch cache which holds the branch target addresses comprising the steps of: (a) executing a sequence of macro-instructions, each of which invokes the execution of a sequence of micro-instructions; (b) determining when a micro-instruction of the sequence of micro-instructions indicates a branch is to occur; (c) hashing a predetermined number of bits of the address of the micro-instruction indicating the occurrence of a branch with a predetermined number of bits of the address of the macro-instruction that invoked the micro-insturciton; and (d) using the hashing result to address the branch cache and read out a branch target address.

Claim 15

A method for predicting branch target addresses for a pipelined digital processing system having a branch cache which holds the branch target addresses comprising the steps of: (a) executing a sequence of macro-instructions, each of which invokes the execution of a sequence of micro-instructions; (b) determining when a micro-instruction of the sequence of micro-instructions indicates a branch is to occur; (c) hashing a predetermined number of bits of the address of the micro-instruction indicating the occurrence of a branch with a predetermined number of bits of the address of the macro-instruction that invoked the micro-insturciton; and (d) using the hashing result to address the branch cache and read out a branch target address.