Branch cache system with instruction boundary determination independent of parcel boundary

• US 4,860,197 A
• Filed: 07/31/1987
• Issued: 08/22/1989
• Est. Priority Date: 07/31/1987
• Status: Expired due to Fees

• Current Assignee: Computervision Corp. (PTC Inc.)
• Original Assignee: Prime Computer, Inc. (DR Holdings, Inc. of Delaware)
• Inventors: Johnson, Neil J., Langendorf, Brian K.
• Primary Examiner(s): Zache, Raulfe B.
• Application Number:
  US07/080,457
• Time in Patent Office: 753 Days
• Field of Search: 364/200 MS File, 364/ 900 MS File
• US Class Current: 712/238
• CPC Class Codes: G06F 9/30152 Determining start or end of instruction; determining instruction length
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3816 Instruction alignment, e.g. cache line crossing

Abstract

A branch cache system for use with a pipelined processor having overlapping parcel prefetch and execution stages. The system includes a plurality of memory sets for storing a plurality of indexed sets of predicted branch addresses, and control circuitry which determines whether there is stored in one of the memory sets a predicted branch address which corresponds to a branch instruction fetched by the prefetch stage. The execution stage is commanded, responsive to detection of a predicted branch address corresponding to that branch instruction, to execute the branch instruction to the predicted branch address. Alternatively, the system includes one or more memory sets for storing predicted branch addresses and corresponding alignment values which represent whether the boundary of a prefetched branch instruction, which is prefetched as one or more parcels, aligns with the fixed boundary of the one or more parcels containing that instruction. The execution stage is commanded to disregard the prefetched parcel containing a portion of the prefetched branch instruction if the alignment value corresponding to the predicted branch address for that prefetched instruction indicates that the boundary for the prefetched instruction does not align with the boundary of the prefetched parcel.

Claims

1. In a branch cache system for a pipelined processor having overlapping parcel prefetch and execution stages, the improvement comprising

plural memory set means, for storing plural indexed sets of branch address prediction data words, each of said address prediction data words being representative of branch address predictions, and

control circuitry means, connected to said plural memory set means, for determining whether there is stored in said plural memory set means an address prediction data word corresponding to a branch instruction fetched by said prefetch stage, and for causing, a responsive to detection of a data word corresponding to said branch instruction, said execution stage to execute said branch instruction to the branch address represented by said data word.

2. In a branch cache system for a pipelined processor having overlapping parcel prefetch and execution stages for processing instructions having variable boundaries, wherein said prefetch stage fetches portions of said instructions as parcels having fixed boundaries, the system comprising

first means for storing an indexed set of branch address prediction data words,

second means for storing, in association with said branch address prediction data words, a field of corresponding alignment bits having values representative of whether boundaries of a branch instruction fetched by said prefetch stage align with said fixed prefetch boundaries, and

control circuitry means, connected to said second storage means and responsive to said alignment bit values, for causing said execution stage to execute a branch instruction being fetched if said branch instruction corresponds to an address prediction data word stored in said first storage means, and for causing said execution stage to disregard the parcel being prefetched if an alignment bit value corresponding to said data word indicates that the boundary of said branch instruction does not align with the fixed boundary of said parcel.

3. In a branch cache system for a pipelined processor having overlapping parcel prefetch and execution stages for processing instructions having variable boundaries, wherein said prefetch stage fetches portions of said instructions as parcels having fixed boundaries, the improvement comprising

plural memory set means, for storing plural indexed sets of branch address prediction data words and an associated field of corresponding alignment bits having values representative of whether boundaries of a branch instruction being processed align with said fixed prefetch parcel boundaries, and

control circuitry means, for (i) determining whether there is stored in said plural memory set means address prediction data words corresponding to a branch instruction fetched by said prefetch stage, for (ii) selecting, responsive to alignment bit values associated with said data words, one of said data words, wherein said selected data word has an associated alignment bit value indicative of alignment of said corresponding branch instruction and said parcel boundaries, and (iii) for causing said execution stage to execute said branch instruction to the branch address represented by said selected data word.

4. A branch cache system, for use in a pipelined processor having overlapping parcel prefetch and execution stages for processing instructions having variable boundaries, wherein said prefetch stage fetches portions of said instructions as parcels having fixed boundaries, the system predicting branch addresses to change program flow when the instructions are branch instructions to be executed, the system comprising:

at least a first memory set for storing predicted branch addresses, each of said predicted branch addresses having an associated alignment value representing the relationship between the boundary of a prefetched branch instruction, corresponding to that predicted branch address, and the boundary of the parcel containing that instruction;

program counter means for indicating the address of an instruction currently being prefetched; and

controller means, connected to said first memory set and said program counter means, for comparing a preselected portion of the indicated instruction address with the alignment value to select from said first memory set a predicted branch address corresponding to the indicated instruction.

5. The branch cache system of claim 4 further including a second memory set, connected to said controller means, for storing predicted branch addresses and associated alignment values, said controller means selecting form said first and second memory sets a predicted branch address corresponding to the indicated instruction.

6. The branch cache system of claim 4 in which said controller means further includes means for providing said selected predicted branch address to said prefetch state to be utilized as the address of a succeeding instruction prefetch.

7. A branch cache system, for use in a pipelined processor having overlapping parcel prefetch and execution stages for processing instructions having variable boundaries, wherein said prefetch stage fetches portions of said instructions as parcels having fixed boundaries, the system predicting branch addresses to change program flow when the instructions are branch instructions to be executed, the system comprising:

at least first and second memory sets for storing predicted branch addresses;

instruction prefetch means for prefetching instructions;

index means, connected to said instruction prefetch means and to said first and second memory sets, for receiving from said instruction prefetch means a preselected number of bits of the address of a branch instruction currently being prefetched and a corresponding branch target address to which program flow is to be changed, for determining an alignment value representing the relationship between the boundary of the prefetched branch instruction and the boundary of the parcel containing that instruction, and for selectively writing said branch target address and said alignment value to said first and second memory sets, said branch target address serving as a predicted branch address for that branch instruction;

program counter means for indicating the address of an instruction currently being prefetched; and

controller means, connected to said first and second memory sets and said program counter means, for comparing a preselected number of bits of the indicated instruction address with the alignment value to select from said first and second memory sets of predicted branch address corresponding to the indicated instruction.

8. The branch cache system of claim 7 in which said controller means further includes means for providing said selected predicted branch address to said instruction prefetch means to be utilized as the address of a succeeding instruction prefetch.