Patent ID: 7836288

Claim:
Apparatus for processing data, said apparatus comprising: a pipelined processing circuit operable to execute program instructions including conditional branch instructions generating branch outcomes; and a branch prediction circuit operable to generate predictions of branch outcomes of conditional branch program instructions to be executed by said pipelined processing circuit; and a prefetch circuit operable to supply a stream of program instructions to said pipelined processing circuit for execution in dependence upon said predictions; wherein said branch prediction circuit comprises: a branch history register operable to store a branch history value indicative of a preceding sequence of branch outcomes; a branch prediction memory having prediction memory storage locations addressed in dependence upon at least said branch history value, a prediction memory storage location addressed by a given branch history value being operable to store a first prediction of a branch outcome as either branch taken or branch not taken for a next branch instruction following a given preceding sequence of branch outcomes corresponding to said given branch history value; and a branch prediction cache for storing at least one branch history value together with a second prediction of a branch outcome for a next branch instruction following a preceding sequence of branch outcomes corresponding to said branch history value; a branch prediction selector operable to select for use by said prefetch circuit for a given history value either a second prediction when said branch prediction cache contains a second prediction for said given history value or a first prediction when said branch prediction cache does not contain a second prediction for said given history value; and a prediction updating circuit operable in response to detection of an incorrect prediction based upon said first prediction from said branch prediction memory for said given history value to store said given history value into said branch prediction cache together with a second prediction for said given history value.