Decode history table for conditional branch instructions

Claim 1

In a computing machine, apparatus for predicting the outcome of conditional branch instructions, the combination comprising: an address queue in which the addresses of conditional branch instructions that have been successfully decoded, but have not finished being executed are stored; an address and history table in which at least a portion of the addresses of conditional branch instructions are stored, including at least one stored history bit associated with each of said conditional branch instructions which is indicative of whether or not the previous executions of the associated conditional branch instruction resulted in a branch being taken; an instruction address register in which the address of a given conditional branch instruction is stored during the instruction decode cycle, wherein said address contains a match portion and a read portion, including means for transferring said address of said given conditional branch instruction to said address queue, and applying said read portion to said address and history table for reading out said at least a portion of the address of said given conditional branch instruction and its associated said at least one history bit; a compare network which has the match portion of the address of said given conditional branch instruction applied to a first input thereof from said instruction address register, and which has said at least a portion of the address of said given conditional branch instruction read out from said address and history table applied to a second input thereof, with said compare network having a MATCH output and a NO MATCH output, which provide a gating signal at the respective outputs when the address information applied to said first and second inputs does and does not match, respectively; a combinational circuit to which said at least one history bit read out of said address and history table is applied, with said combinational circuit providing a one bit binary output signal which indicates that execution of said conditional branch instruction will result in a branch being taken or not taken when in a first binary state or a second binary state, respectively; and first means for indicating the probable outcome of said given conditional branch instruction based on the one binary output signal from said combinational circuit whenever there is a gating output signal provided at the MATCH output of said compare network.