Branch target address cache using hashed fetch addresses

1. Apparatus for processing data comprising:

prefetch circuitry configured to prefetch from a sequence of addresses within a memory program instructions to be executed;

a branch target address cache coupled to said prefetch circuitry and configured to store:

branch target data indicative of branch target addresses of previously encountered branch instructions fetched from said memory; and

for each of said previously encountered branch instructions, a tag value indicative of a fetch address of said previously encountered branch instruction; and

tag value generating circuitry configured to generate said tag value by performing a hashing function upon a portion of said fetch address, said tag value having bit length less than a bit length of said portion of said fetch address;

wherein the branch target address cache is configured to detect a hit for the branch target data associated with one of said previously encountered branch instructions when a tag value generated by the tag value generating circuitry by performing the hashing function upon a portion of said fetch address is detected to match the tag value stored in the branch target address cache for said one of said previously encountered branch instructions, even if said one of said previously encountered branch instructions was fetched from a different address to said fetch address,

wherein said hashing function operates upon a plurality of contiguous fields of contiguous bits of said fetch address, and

wherein a first field of said plurality of contiguous fields has a lowest bit order within said fetch address of said plurality of contiguous fields and comprises a number of bits equal to a number of bits of said tag value and each bit in descending bit order within said tag value is dependent upon a bit within said first field following a descending bit order within said fetch address.

2. The apparatus as claimed in claim 1 , wherein said hashing function generates said tag value such that each bit of said tag value is dependent upon a different subset of bits of said fetch address and at least one bit of said tag value is dependent upon a plurality of bits of said fetch address.

3. The apparatus as claimed in claim 2 , wherein at least one bit of said tag value is dependent upon a single of bit of said fetch address.

4. The apparatus as claimed in claim 2 , wherein different bits of said tag value are dependent upon respective ones of a plurality of different subsets of bits of said fetch address and said plurality of different subsets are pairwise disjoint.

5. The apparatus as claimed in claim 2 , wherein said previously encountered branch instructions have a given statistical distribution of fetch addresses within said memory and said hashing function is dependent upon said bits of said fetch address to reduce a probability of two different fetch addresses of branch instructions within said statistical distribution of fetch addresses generating a same tag value compared with an average of a random dependence of each bit of said tag value upon a different subset of bits of said fetch address.

6. The apparatus as claimed in claim 2 , wherein said previously encountered branch instructions have a given statistical distribution of fetch addresses within said memory and said hashing function is dependent upon said bits of said fetch address substantially to minimise a probability of two different fetch addresses of branch instructions within said statistical distribution of fetch addresses generating a same tag value.

7. The apparatus as claimed in claim 1 , wherein said hashing function is software programmable.

8. The apparatus as claimed in claim 1 , wherein each bit of said tag value is dependent upon a parity of a different subset of bits of said fetch address.

9. The apparatus as claimed in claim 1 , further comprising a multi-stage instruction pipeline including an instruction prefetch stage that includes the prefetch circuitry and wherein said branch target address cache is part of said instruction prefetch stage.

10. The apparatus as claimed in claim 1 , wherein performing said hashing function upon said fetch address and a lookup within said branch target address cache all occur within one clock cycle of a clock signal controlling said apparatus.

11. Apparatus for processing data comprising:

prefetch circuitry configured to prefetch from a sequence of addresses within a memory program instructions to be executed;

a branch target address cache coupled to said prefetch circuitry and configured to store:

branch target data indicative of branch target addresses of previously encountered branch instructions fetched from said memory; and

for each of said previously encountered branch instructions, a tag value indicative of a fetch address of said previously encountered branch instruction; and

tag value generating circuitry configured to generate said tag value by performing a hashing function upon a portion of said fetch address, said tag value having bit length less than a bit length of said portion of said fetch address;

wherein said hashing function generates said tag value such that each bit of said tag value is dependent upon a different subset of bits of said fetch address and at least one bit of said tag value is dependent upon a plurality of bits of said fetch address;

wherein said hashing function operates upon a plurality of contiguous fields of contiguous bits of said fetch address; and

wherein a first field of said plurality of contiguous fields has a lowest bit order within said fetch address of said plurality of contiguous fields and comprises a number of bits equal to a number of bits of said tag value and each bit in descending bit order within said tag value is dependent upon a bit within said first field following a descending bit order within said fetch address.

12. The apparatus as claimed in claim 11 , wherein:

said plurality of contiguous fields comprises a sequence, in ascending bit order within said fetch address, of N further fields each comprising X bits, where X monotonically decreases as N increases and N is a positive integer greater than one; and

for each one of said N further fields, a highest order X bits of said tag value in descending bit order are each dependent upon a respective bit within said one of said N further fields following a descending order within said fetch address.

13. The apparatus for processing data comprising:

prefetch means for prefetching from a sequence of addresses within a memory program instructions to be executed;

means, coupled to said prefetch means, for storing:

branch target data indicative of branch target addresses of previously encountered branch instructions fetched from said memory; and

for each of said previously encountered branch instructions, a tag value indicative of a fetch address of said previously encountered branch instruction; and

tag value generating means for generating said tag value by performing a hashing function upon a portion of said fetch address, said tag value having bit length less than a bit length of said portion of said fetch address;

wherein the means for storing is configured to detect a hit for the branch target data associated with one of said previously encountered branch instructions when a tag value generated by the tag value generating means by performing the hashing function upon a portion of said fetch address is detected to match the tag value stored in the means for storing for said one of said previously encountered branch instructions, even if said one of said previously encountered branch instructions was fetched from a different address to said fetch address,

wherein said hashing function operates upon a plurality of contiguous fields of contiguous bits of said fetch address, and

wherein a first field of said plurality of contiguous fields has a lowest bit order within said fetch address of said plurality of contiguous fields and comprises a number of bits equal to a number of bits of said tag value and each bit in descending bit order within said tag value is dependent upon a bit within said first field following a descending bit order within said fetch address.

14. A method of processing data comprising the steps of:

prefetching from a sequence of addresses within a memory program instructions to be executed;

storing within a branch target address cache:

branch target data indicative of branch target addresses of previously encountered branch instructions fetched from said memory; and

for each of said previously encountered branch instructions, a tag value indicative of a fetch address of said previously encountered branch instruction; and

generating said tag value by performing a hashing function upon a portion of said fetch address, said tag value having bit length less than a bit length of said portion of said fetch address; and

detecting a hit in the branch target address cache for the branch target data associated with one of said previously encountered branch instructions when a tag value generated by performing the hashing function upon a portion of said fetch address is detected to match the tag value stored in the branch target address cache for said one of said previously encountered branch instructions, even if said one of said previously encountered branch instructions was fetched from a different address to said fetch address,

wherein said hashing function operates upon a plurality of contiguous fields of contiguous bits of said fetch address, and

wherein a first field of said plurality of contiguous fields has a lowest bit order within said fetch address of said plurality of contiguous fields and comprises a number of bits equal to a number of bits of said tag value and each bit in descending bit order within said tag value is dependent upon a bit within said first field following a descending bit order within said fetch address.