Predicting a branch instruction classified as simple or hard to predict based on a confidence counter in a branch type table

A computing system comprising:

• a memory;
• and
• a processor, wherein the processor comprises:
• a processor pipeline comprising one or more execution units configured to execute one or more branch instructions;
• a branch predictor associated with the processor pipeline and configured to predict an outcome of each of the one or more branch instructions;
• and
• a branch classification unit coupled to the processor pipeline and the branch predictor, and configured to classify each of the one or more branch instructions as at least one of the following:
• a simple branch and a hard-to-predict branch, wherein the branch classification unit comprises a direct-mapped branch type table (BTT),
• wherein the BTT comprises one or more BTT entries, wherein each of the one or more BTT entries includes a branch type BTT field and a confidence counter BTT field;
• and,
• wherein, the branch classification unit is configured to, in response to detecting a first branch instruction, determine a type of the first branch instruction by:
• extracting an index from an instruction address of the first branch instruction;
• using the index to identify a BTT entry corresponding to the first branch instruction in the BTT;
• determining whether a value in the confidence counter BTT field in the identified BTT entry is greater than 0;
• and
• if the value in the confidence counter BTT field in the identified BTT entry is greater than 0:
• determining the type of the first branch instruction using a value in the branch type BTT field of the identified BTT entry by predicting, by the branch predictor, a predicted outcome of the first branch instruction, and
• updating the value in the confidence counter BTT field based on an actual outcome and the predicted outcome of the first branch instruction using one or more of the following rules:
• increment the value in the confidence counter BTT field in the identified BTT entry by 1 if the branch type BTT field in the identified BTT entry indicates simple and the predicted outcome of the first branch instruction matches the actual outcome of the first branch instruction,
• increment the value in the confidence counter BTT field in the identified BTT entry by 1 if the branch type BTT field in the identified BTT entry indicates hard to predict and the predicted outcome of the first branch instruction does not match the actual outcome of the first branch instruction,
• decrement the value in the confidence counter BTT field in the identified BTT entry by 1 if the branch type BTT field in the identified BTT entry indicates simple and the predicted outcome of the first branch instruction does not match the actual outcome of the first branch instruction, and
• decrement the value in the confidence counter BTT field in the identified BTT entry by 1 if the branch type BTT field in the identified BTT entry indicates hard to predict and the predicted outcome of the first branch instruction matches the actual outcome of the first branch instruction.

A computing system comprising:

• a memory;
• and
• a processor, wherein the processor comprises:
• a processor pipeline comprising one or more execution units configured to execute one or more branch instructions;
• a branch predictor coupled to the processor pipeline and configured to predict an outcome of each of the one or more branch instructions;
• and
• a branch classification unit associated with the processor pipeline and the branch predictor, and configured to classify each of the one or more branch instructions as at least one of the following:
• a simple branch and a hard-to-predict branch, wherein the branch classification unit comprises a direct-mapped branch type table (BTT) and a branch classification table (BCT), and
• wherein the BTT comprises one or more BTT entries, wherein each of the one or more BTT entries includes a branch type BTT field and a confidence counter BTT field, and
• wherein the branch classification unit is configured to, in response to detecting a first branch instruction, determine a type of the first branch instruction by:
• using an index to identify a BTT entry in the BTT corresponding to the first branch instruction;
• determining whether a value in the confidence counter BTT field in the identified BTT entry is greater than a threshold;
• and
• if the value in the confidence counter BTT field in the identified BTT entry is less than or equal to the threshold, using the BCT to classify the first branch instruction, wherein the BCT is configured to classify the first branch instruction by:
• updating a field in the BCT to record an actual outcome of the first branch instruction and updating a field in the BCT to record a predicted outcome of the first branch instruction;
• computing a set of classifier parameters using a BCT value included in the updated BCT;
• classifying the first branch instruction based on the set of classifier parameters;
• and
• updating the branch type BTT field in the identified BTT entry in the BTT.