# US 2014/0195789 A1 · Usefulness Indication For Indirect Branch Prediction Training > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195789 A1 - Document ID: US20140195789A1 - Status: Published application - Kind: A1 - Application number: 13/735,694 - Filed: 2013-01-07 - Published: 2014-07-10 - Earliest claimed: 2013-01-07 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Sandeep Gupta; Shyam Sundar; Wei-Han Lien; Gerard R. Williams, III; Conrado Blasco-Allue - Web page: https://patentgrep.com/patent/US20140195789A1 ## CPC - G06F 9/3844: {using dynamic branch prediction, e.g. using branch history tables} - G06F 9/323: {for indirect branch instructions} - G06F 9/3806: {using address prediction, e.g. return stack, branch history buffer} - G06F 9/30072: {to perform conditional operations, e.g. using predicates or guards} - G06F 9/3848: {using hybrid branch prediction, e.g. selection between prediction techniques} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A circuit for implementing a branch target buffer. The branch target buffer may include a memory that stores a plurality of entries. Each entry may include a tag value, a target value, and a prediction accuracy value. A received index value corresponding to an indirect branch instruction may be used to select one of entries of the plurality of entries, and a received tag value may then be compared to the tag value of the selected entries in the memory. An entry in the memory may be selected in response to a determination that the received tag does not match the tag value of compared entries. The selected entry may be allocated to the indirect instruction branch dependent upon the prediction accuracy values of the plurality of entries. ## Claims ### Claim 1 An apparatus, comprising: a memory configured to store a plurality of entries, wherein each entry of the plurality of entries includes a tag value, a target value, and a prediction accuracy value; and a control module coupled to the memory and configured to receive an index value and a tag value corresponding to an indirect instruction branch, wherein the index value is used to read one or more entries of the plurality of entries; wherein the control module is configured to, in response to a determination that the received tag value does not match the tag value of read entries, selecting an entry in the plurality of entries dependent upon the prediction accuracy values of the stored plurality of entries, and allocating the selected entry to the instruction branch. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the control module is further configured to prevent allocation of the selected entry responsive to a determination that the prediction accuracy value of the selected entry is indicative of a correct prediction from the entry. ### Claim 3 (depends on 2) The apparatus of claim 2, wherein the control module is further configured to reset the prediction accuracy value of the selected entry responsive to the prevention of allocation. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein the control module is further configured to, in response to a determination that the received tag value matches the tag value of one of the one of more read entries in the plurality of entries, set the prediction accuracy value to a value indicative of a correct prediction from the one of the one or more read entries. ### Claim 5 (depends on 1) The apparatus of claim 1, wherein the memory comprises a cache memory. ### Claim 6 A method, comprising: storing, in a memory, a plurality of entries, wherein each entry of the plurality of entries includes a tag value, a target value, and prediction accuracy value; receiving an index value and a tag value corresponding to an indirect branch; comparing, dependent upon the received index value, the tag values one of more entries of the plurality of entries to the received tag value; selecting, in response to a determination that the received tag value does not match the tag value of compared entries, an entry of the plurality of entries dependent upon the prediction accuracy values of the plurality of entries; allocating the selected entry to the indirect branch; and setting the prediction accuracy value of the allocated entry to indicate an accurate prediction. ### Claim 7 (depends on 6) The method of claim 6, further comprising, preventing the allocation of the selected entry responsive to a determination that the prediction accuracy value of the selected entry is indicative of an accurate prediction. ### Claim 8 (depends on 7) The method of claim 7, further comprising, re-setting the prediction accuracy value of the selected entry responsive to the prevention of the allocation. ### Claim 9 (depends on 6) The method of claim 6, further comprising, in response to a determination that the received tag value matches the tag value of an entry of the compared entries, setting the prediction accuracy value of the entry whose tag value matches the received tag value to a value indicative of an accurate prediction. ### Claim 10 (depends on 6) The method of claim 6, further comprising, updating the tag value and the target value of the selected entry of the plurality of entries. ### Claim 11 A system, comprising: a processor; and one or more memories; wherein the processor includes a branch target buffer, and a control module coupled to the branch target buffer, and configured to receive an indirect branch; wherein the branch target buffer is configured to store a plurality of entries, wherein each entry includes a tag value, a target value, and a prediction accuracy value; wherein the control module is further configured to, in response to a determination that the received indirect branch does not match an entry in the branch target buffer, select a least frequently used entry in the branch target buffer, and allocate the received indirect branch to the least frequently used entry dependent upon the prediction accuracy value of the least frequently used entry. ### Claim 12 (depends on 11) The system of claim 11, wherein the control module is further configured to, in response to a determination that the received indirect branch matches an entry in the branch target buffer, increase the prediction accuracy value of the matched entry. ### Claim 13 (depends on 11) The system of claim 11, wherein the control module is further configured to update the tag value and the target value of the least frequently used entry responsive to the allocation. ### Claim 14 (depends on 11) The system of claim 11, wherein the control module is further configured to decrease the prediction accuracy value of the least frequently used entry responsive to the allocation. ### Claim 15 (depends on 11) The system of claim 11, wherein the branch target buffer comprises a cache memory. ### Claim 16 A branch predictor, comprising: a first branch target buffer configured to store a first plurality of entries, wherein each entry of the first plurality of entries includes a tag value, a target value, and a prediction accuracy value; a second branch target buffer configured to store a second plurality of entries, where in each entry of the second plurality of entries includes a tag value, a target value, a prediction accuracy value, and a hysteresis value; and a control module coupled to the first branch target buffer and the second branch target buffer, and configured to receive an indirect branch; wherein the control module is configured to, in response to a determination that the received indirect branch does not match an entry in either the first plurality of entries and the second plurality of entries, select a least frequently used entry in the first branch target buffer, and allocate the indirect branch to the selected least frequently used entry dependent upon the accuracy of the selected least frequently used entry. ### Claim 17 (depends on 16) The branch predictor of claim 16, wherein the control module is further configured to update a path history. ### Claim 18 (depends on 17) The branch predictor of claim 17, the determination that the received indirect branch does not match an entry in either the first plurality of entries and the second plurality of entries comprises combining the path history with the received indirect branch. ### Claim 19 (depends on 16) The branch predictor of claim 16, wherein the control module is further configured to, in response to a determination that the received indirect branch matches an entry in the second branch target buffer, train the second branch target buffer with the received indirect branch. ### Claim 20 (depends on 16) The branch predictor of claim 16, wherein the first branch target buffer comprises a 2-way set associative cache memory. ### Claim 21 A method, comprising: storing, in a first table, a first plurality of entries, wherein each entry of the plurality of entries includes a tag value, a target value, and prediction accuracy value; storing, in a second table, a second plurality of entries, wherein each entry of the plurality of entries includes a tag value, a target value, and prediction accuracy value; receiving an index value and a tag value, wherein the index value and the tag value correspond to an indirect instruction branch; comparing, dependent upon the received index value, the received tag value to tag values of first plurality of entries and the second plurality of entries; selecting, in response to a determination that the received tag value does not match the tag value of each compared entry in the first plurality of entries and the second plurality of entries, an entry in the first plurality of entries dependent upon the prediction accuracy values of the first plurality of entries; allocating the selected entry to the indirect instruction branch; and setting the prediction accuracy of the allocated selected entry in the first plurality to indicate an accurate prediction. ### Claim 22 (depends on 21) The method of claim 21, further comprising preventing the allocation of the selected entry to the indirect instruction branch, in response to a determination that prediction accuracy value of the selected entry is indicative of an accurate prediction. ### Claim 23 (depends on 22) The method of claim 22, further comprising, in response to the prevention of the allocation, re-setting the prediction accuracy value of the selected entry. ### Claim 24 (depends on 21) The method of claim 21, further comprising, selecting, in response to a determination that the prediction accuracies of the plurality of first entries indicate accurate predictions, an entry in the second plurality of entries dependent upon the prediction accuracies of the second plurality of entries. ### Claim 25 (depends on 21) The method of claim 21, further comprising, setting, in response to a determination that the received tag value matches the tag value of an entry in the second plurality of entries, the prediction accuracy value of the matched entry in the second plurality of entries to indicate an accurate prediction.