Branch target buffer compression
AssigneeAdvanced Micro Devices, Inc.
InventorSteven R. Havlir
Life of this patent
Estimating the term…
Abstract
Techniques for improving branch target buffer (“BTB”) operation. A compressed BTB is included within a branch prediction unit along with an uncompressed BTB. To support prediction of up to two branch instructions per cycle, the uncompressed BTB includes entries that each store data for up to two branch predictions. The compressed BTB includes entries that store data for only a single branch instruction for situations where storing that single branch instruction in the uncompressed BTB would waste space in that buffer. Space would be wasted in the uncompressed BTB due to the fact that, in order to support two branch lookups per cycle, prediction data for two branches must have certain features in common (such as cache line address) in order to be stored together in a single entry.
Claims20
A method for manipulating branch target buffer data, the method comprising:
- identifying first branch target data for a single branch to be stored in the branch target buffer;
- determining that storing the first branch target data within an uncompressed branch target buffer would result in a non-full branch target buffer entry, because the first branch target data does not share a cache line address with another branch target data that could be stored in the non-full branch target buffer entry, the uncompressed branch target buffer being configured to store entries that include data for more than one branch located in the same cache line;
- responsive to the determining, storing a first compressed branch target buffer entry in a compressed branch target buffer that is configured to store entries that each include data for only a single branch;
- providing a lookup tag to the compressed branch target buffer and the uncompressed branch target buffer;
- identifying a branch target buffer entry from one or both of the compressed branch target buffer and the uncompressed branch target buffer based on the lookup tag;
- and
- outputting data corresponding to the branch target buffer entry to branch prediction logic for predicting a branch.
A branch prediction unit comprising:
- a predictor;
- a compressed branch target buffer, configured to store entries that each include data for only a single branch;
- and
- an uncompressed branch target buffer, configured to store entries that include data for more than one branch located in the same cache line,
- wherein the predictor is configured to:
- identify first branch target data for a single branch to be stored in the branch target buffer,
- determine that storing the first branch target data within the uncompressed branch target buffer would result in a non-full branch target buffer entry, because the first branch target data does not share a cache line address with another branch target data that could be stored in the non-full branch target buffer entry, and
- responsive to the determining, cause a first compressed branch target buffer entry to be stored in the compressed branch target buffer, and
- wherein both the compressed branch target buffer and the uncompressed branch target buffer are configured to:
- identify one or more branch target buffer entries based on a provided lookup tag, and
- output data corresponding to the identified one or more branch target buffer entries to prediction logic for predicting a branch.
A processor, comprising:
- a branch prediction unit configured to output branch prediction results;
- an instruction fetch unit configured to output instructions for execution based on the branch prediction results;
- and
- an instruction execution pipeline configured to execute the instructions output from the instruction fetch unit,
- wherein the branch prediction unit comprises:
- a predictor;
- a compressed branch target buffer, configured to store entries that each include data for only a single branch;
- and
- a uncompressed branch target buffer, configured to store entries that include data for more than one branch located in the same cache line,
- wherein the predictor is configured to:
- identify first branch target data for a single branch to be stored in the branch target buffer,
- determine that storing the first branch target data within the uncompressed branch target buffer would result in a non-full branch target buffer entry, because the first branch target data does not share a cache line address with another branch target data that could be stored in the non-full branch target buffer entry, and
- responsive to the determining, cause a first compressed branch target buffer entry to be stored in the compressed branch target buffer, and
- wherein both the compressed branch target buffer and the uncompressed branch target buffer are configured to:
- identify one or more branch target buffer entries based on a provided lookup tag, and
- output data corresponding to the identified one or more branch target buffer entries to prediction logic for predicting a branch.
Dependencies are inferred from the claim text.