Multi-prediction branch prediction mechanism

A multi-prediction branch prediction mechanism for predicting the outcome of branch instructions in a computer having a pipeline processor including an instruction buffer connected to a memory for temporarily storing fetched instructions, an instruction decode circuit connected to said instruction buffer and decoding instructions temporarily stored in said instruction buffer, an address generate circuit responsive to said decoded instructions from said instruction decode circuit addressing said memory to fetch instructions to said instruction buffer, and an execution unit responsive to decoded instructions from said instruction decode circuit for performing operations in accordance with decoded instructions, said multi-branch prediction mechanism comprising:

• at least two, independent branch prediction means connected to said pipeline processor for independently predicting branch instructions at different stages of said pipeline, said at least two, independent branch prediction mean comprising an instruction-fetch branch prediction means connected to said instruction buffer and to said address generate circuit for generating an initial branch prediction based on a limited history of branches taken and supplying to said address generate circuit a target address, and a decode-time branch prediction means connected to said instruction decoded circuit and to said instruction-fetch branch prediction means for generating a branch prediction based on a history of branches executed;
• means responsive to said two, independent branch prediction means for resolving those instances when prediction from each of said two, independent branch prediction means differ, said means responsive to said branch prediction means comprising comparing means for comparing said initial branch prediction from said instruction-fetch branch prediction means and said branch prediction from said decode-time branch prediction means, and selection means responsive to said comparing means for accepting said initial branch prediction from said instruction-fetch branch prediction means when a match occurs between said initial branch prediction and said branch prediction from said decode-time branch prediction means but overriding said initial branch prediction by selecting said branch prediction from said decode-time branch prediction means and restarting said pipeline when said initial branch prediction and said branch prediction from said decode-time branch prediction means do not match;
• and
• means responsive to said execution unit for updating said two, independent branch prediction means based on execution of a branch instruction.