Apparatus and method for target address replacement in speculative branch target address cache

An apparatus for writing a target address in a branch target address cache upon execution of a taken branch instruction, comprising:

• a branch target address cache (BTAC), comprising a plurality of storage elements for caching target addresses of executed branch instructions, each of said plurality of storage elements comprising first and second entries for storing a target address;
• a global indicator, configured to store a global indication of which of said first and second entries was last written to in any of said plurality of storage elements when at least one of said first and second entries were invalid in a last written one of said plurality of storage elements;
• and
• branch control logic, coupled to said global indicator, for selecting which of said first and second entries to write the taken branch instruction target address to based on said global indicator.

A method for replacing a target address in a branch target address cache (BTAC) having a plurality of storage locations each having an A and B entry for caching a target address, the method comprising:

• executing a branch instruction and generating a target address thereof,
• selecting one of the plurality of storage locations of the BTAC based on an instruction pointer of said branch instruction;
• determining whether both the A and B entries of said selected BTAC storage location are invalid;
• examining a replacement status flag shared globally by the plurality of BTAC storage locations, wherein said examining said replacement status flag comprises determining which of the A and B entries was last written to by a write to any of the plurality of storage locations in which at least one of the A and B entries was invalid;
• and
• writing said target address to one of the A and B entries of said selected BTAC storage location based on said replacement status flag if both the A and B entries of said selected BTAC storage location are invalid.

A method for replacing a target address in a branch target address cache (BTAC) having a plurality of storage locations each having N entries for caching a target address, wherein N is an integer greater than one, the method comprising:

• executing a branch instruction and generating a target address thereof;
• selecting one of the plurality of storage locations of the BTAC based on an instruction pointer of said branch instruction;
• determining whether all of the N entries of said selected BTAC storage location are invalid;
• examining a replacement status flag shared globally by the plurality of BTAC storage locations, wherein said examining said global replacement status flag comprises determining from said global replacement status flag which of the N entries was least recently written to among writes to any of the plurality of storage locations wherein all N entries were invalid;
• and
• writing said target address to one of the N entries of said selected BTAC storage location based on said global replacement status flag if all of the N entries of said selected BTAC storage location are invalid.

A pipelined microprocessor, comprising:

• a branch target address cache (BTAC), comprising a plurality of lines each having N target addresses stored therein, N being an integer greater than one;
• execution logic, coupled to said BTAC, configured to execute a branch instruction and generate a target address thereof for storage in said BTAC;
• address selection logic, coupled to said BTAC, configured to select an instruction pointer of said executed branch instruction for updating said BTAC;
• a status register, coupled to said execution logic, for storing replacement status global to said plurality of BTAC lines;
• and
• branch control logic, configured to select, for replacing with said branch instruction target address, one of said N target addresses that are stored in one of said plurality of lines selected by said instruction pointer, said branch control logic configured to select said one of said N target addresses as a function of said global replacement status stored in said status register, wherein said control logic selects a least recently written one of said N target addresses among previous writes to ones of said plurality of lines that has at least one invalid target address.

An apparatus for updating a branch target address cache (BTAC), the BTAC having a plurality of storage elements, each of the plurality of storage elements having two sides each for storing a target address of branch instruction, each of the two sides having a valid indicator for indicating whether the side is currently storing a valid target address, the apparatus comprising:

• an indicator, shared by all of the plurality of storage elements of the BTAC rather than being uniquely associated with any one of the plurality of storage elements;
• control logic, coupled to said indicator, configured to:
• read one of the plurality of storage elements of the BTAC, in response to fetching a cache line from an instruction cache, said cache line having first and second branch instructions therein;
• execute said first branch instruction to determine a first target address thereof, after reading one of the plurality of storage elements;
• select a first of the two sides of said one of the plurality of storage elements for writing said first target address into, in response to executing said first branch instruction;
• update said indicator to indicate said first of the two sides was selected for writing said first target address into;
• execute said second branch instruction to determine a second target address thereof, after updating said indicator to indicate said first of the two sides was selected for writing said first target address into;
• determine that both of the two sides of said one of the plurality of storage elements are storing an invalid target address, in response to executing said second branch instruction and based on reading one of the plurality of storage elements;
• determine from said indicator that said first of the two sides was selected for writing said first target address into, in response to determining that both of the two sides of said one of the plurality of storage elements are storing an invalid target address;
• and
• select the second of the two sides of said one of the plurality of storage elements for writing said second target address into, in response to determining from said indicator that said first of the two sides was selected for writing said first target address into.

A method for updating a branch target address cache (BTAC), the BTAC having a plurality of storage elements, each of the plurality of storage elements having two sides each for storing a target address of branch instruction, each of the two sides having a valid indicator for indicating whether the side is currently storing a valid target address, the apparatus comprising:

• reading one of the plurality of storage elements of the BTAC, in response to fetching a cache line from an instruction cache, said cache line having first and second branch instructions therein;
• executing said first branch instruction to determine a first target address thereof, after said reading one of the plurality of storage elements;
• selecting a first of the two sides of said one of the plurality of storage elements for writing said first target address into, in response to said executing said first branch instruction;
• updating an indicator to indicate said first of the two sides was selected for writing said first target address into, wherein said indicator is shared by all of the plurality of storage elements of the BTAC rather than being uniquely associated with said one of the plurality of storage elements;
• executing said second branch instruction to determine a second target address thereof, after said updating an indicator to indicate said first of the two sides was selected for writing said first target address into;
• determining that both of the two sides of said one of the plurality of storage elements are storing an invalid target address, in response to said executing said second branch instruction and based on said reading one of the plurality of storage elements;
• determining from said indicator that said first of the two sides was selected for writing said first target address into, in response to said determining that both of the two sides of said one of the plurality of storage elements are storing an invalid target address;
• and
• selecting the second of the two sides of said one of the plurality of storage elements for writing said second target address into, in response to said determining from said indicator that said first of the two sides was selected for writing said first target address into.