Patent ID: 7069426

Claim:
A method comprising: providing a first taken/not-taken prediction responsive to an address using a saturating counter branch predictor; providing (1) a second taken/not-taken prediction responsive to the address resulting in a hit in a local branch history table, and (2) a hit/miss indication for the address, wherein the second prediction is generated by a decision function that accepts, as an input, a history value from a matching entry of the local branch history table and produces, as an output, the second prediction, the decision function being implemented by combinational logic that has no memory so as to reduce on-chip area; selecting for the address one of (1) the second prediction if the indication is a hit, and (2) the first prediction if the indication is a miss; updating a replacement field for the matching entry in the local branch history table only if the first prediction was incorrect; and updating a history field for the matching entry in the local branch history table with the outcome of an executed branch instruction only if the first prediction was incorrect and the second prediction was correct.