Patent ID: 7428632

Claim:
Apparatus for processing data, said apparatus comprising: a pipelined processing circuit configured to execute program instructions including conditional branch instructions generating branch outcomes; and a branch prediction circuit configured to generate predictions of branch outcomes of conditional branch program instructions to be executed by said pipelined processing circuit; and a prefetch circuit configured 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 configured 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 configured to store a first prediction of a branch outcome as either branch taken or branch not taken for a next conditional branch instruction following a given preceding sequence of branch outcomes corresponding to said given branch history value; an extended pattern cache configured to detect a length of one or more repeating patterns of branch outcomes that is greater than a length of those stored in said branch history register and terminated by terminal branch outcomes not following said repeating pattern and to store representations of a plurally of instances of such detected repeating patterns together with their respective final branch outcome for subsequent use as a second prediction when said repeating pattern of outcomes is detected; and a branch prediction selector configured to select for use by said prefetch circuit either said second prediction when said extended pattern cache subsequently detects said repeating pattern of branch outcomes or a first prediction from said branch prediction memory when said extended pattern cache subsequently does not detect said repeating pattern of branch outcomes.