Branch prediction unit which approximates a larger number of branch

Abstract

A branch prediction unit includes a cache-line based branch prediction storage having a branch prediction storage location assigned to each cache line of an instruction cache within the microprocessor employing the branch prediction unit. Although each branch prediction storage location is assigned to a particular cache line, the branch prediction storage location stores an alternate target indication indicating whether a branch prediction within the storage location corresponds to a branch instruction within the cache line to which the storage location is assigned or to a branch instruction within a different cache line. The different cache line has a predetermined relationship to the cache line to which the storage location is assigned. In various embodiments, the different cache line is at an index one less than the index of the storage location or is within a different way of the same index. The branch prediction unit described herein approximates having multiple branch predictions per cache line even though only one branch prediction storage location is assigned to the cache line. In cases in which a branch prediction would have been unused due to a lack of sufficient predicted-taken branch instructions within a cache line, the unused branch prediction may be used by a different cache line having a large number of branch instructions.