Link stack repair of erroneous speculative update

1. A method of managing a link stack comprising a plurality of entries, each entry operative to store a link address, the method comprising:

speculatively reading a first link address from a link stack entry of the link stack;

saving the first link address in a link stack restore buffer in response to determining that a speculative write following the speculative read would overwrite the first link address at the link stack entry, wherein determining that the speculative write following the speculative read would overwrite the first link address at the link stack entry comprises:

maintaining a first count of a total number of uncommitted link stack write instructions in a pipeline;

maintaining a second count, associated with each uncommitted branch instruction, of a number of uncommitted link stack write instructions ahead of the uncommitted branch instruction in the pipeline; and

upon detecting that a branch was mispredicted, comparing the second count to the first count and detecting that the first and second counts are not the same; and

speculatively writing a second link address to the link stack entry after speculatively reading the first link address, wherein the first link address of the link stack entry is overwritten by the second link address.

2. The method of claim 1 , wherein the link stack restore buffer is separate from the link stack.

3. The method of claim 1 , further comprising:

detecting that a branch evaluation was mispredicted; and

restoring the saved first link address from the link stack restore buffer to the link stack in response to detecting that the link stack was speculatively written.

4. The method of claim 1 , further comprising storing a link stack index of the link stack entry corresponding to the first link address in the link stack restore buffer.

5. The method of claim 1 , wherein the link stack restore buffer comprises a plurality of entries.

6. The method of claim 1 , wherein maintaining the first count of the total number of uncommitted link stack write instructions in the pipeline comprises:

incrementing a first counter upon decoding a link stack write instruction; and

decrementing the first counter when the link stack write instruction commits for execution.

7. The method of claim 6 , wherein maintaining the second count of each uncommitted branch instruction, of the uncommitted link stack write instructions ahead of it in the pipeline comprises:

copying a value of the first counter to a second counter associated with the branch instruction upon decoding the branch instruction; and

decrementing the second counter when the link stack write instruction commits for execution.

8. The method of claim 1 , wherein the second counter associated with the branch instruction is a field in a branch instruction queue entry associated with the branch instruction.

9. A processor comprising:

a link stack comprising a plurality of entries, each entry operative to store a link address;

a read circuit configured to speculatively read a first link address from a link stack entry of the link stack;

a detection circuit configured to generate an indication that a speculative write following the speculative read would overwrite the first link address at the link stack entry, wherein the detection circuit comprises:

a first counter configured to maintain a first count of a total number of uncommitted link stack write instructions in a pipeline;

a second counter configured to maintain a second count, associated with each uncommitted branch instruction, of a number of uncommitted link stack write instructions ahead of the uncommitted branch instruction in the pipeline; and

comparison logic configured to compare the second count to the first count upon detecting that a branch was mispredicted, and the comparison logic further configured to generate an indication if the first and second counts are not the same;

a link stack restore buffer configured to save the first link address in response to the indication from the detection circuit; and

a write circuit configured to speculatively write a second link address to the link stack entry after the speculative read of the first link address, wherein the first link address of the link stack entry is overwritten by the second link address.

10. The processor of claim 9 , wherein the link stack restore buffer is separate from the link stack.

11. The processor of claim 9 , further comprising:

a branch evaluation circuit configured to detect that a branch evaluation was mispredicted; and

the write circuit further configured to restore the saved first link address from the link stack restore buffer to the link stack in response to a detection that the link stack was speculatively written.

12. The processor of claim 9 , wherein the link stack restore buffer is further configured to store a link stack index of the link stack entry corresponding to the first link address.

13. The processor of claim 9 , wherein the link stack restore buffer comprises a plurality of entries.

14. The processor of claim 9 , wherein:

the first counter is configured to be incremented upon decoding a link stack write instruction; and

the first counter is configured to be decremented when the link stack write instruction commits for execution.

15. The processor of claim 14 , wherein

the second counter is further configured to store the first count as the second count, upon decoding the branch instruction; and

the second counter is configured to decrement the second count when the link stack write instruction commits for execution.

16. The processor of claim 9 , wherein the second counter is a field in a branch instruction queue entry associated with the branch instruction.

17. A system for managing a link stack comprising a plurality of entries, each entry operative to store a link address, the system comprising:

means for speculatively reading a first link address from a link stack entry of the link stack;

means for generating an indication that a speculative write following the speculative read would overwrite the first link address at the link stack entry, wherein the means for generating an indication that the speculative write following the speculative read would overwrite the first link address at the link stack entry comprises:

means for maintaining a first count of a total number of uncommitted link stack write instructions in a pipeline;

means for maintaining a second count, associated with each uncommitted branch instruction, of a number of uncommitted link stack write instructions ahead of the uncommitted branch instruction in the pipeline; and

means for comparing the second count to the first count upon detecting that a branch was mispredicted, and means for detecting that the first and second counts are not the same;

buffer means for saving the first link address in response to the indication; and

means for speculatively writing a second link address to the link stack entry after speculatively reading the first link address, wherein the first link address of the link stack entry is overwritten by the second link address.

18. The system of claim 17 , wherein the buffer means is separate from the link stack.

19. The method of claim 17 , further comprising:

means for detecting that a branch evaluation was mispredicted; and

means for restoring the saved first link address from the buffer means to the link stack in response to detecting that the link stack was speculatively written.

20. The system of claim 17 , further comprising means storing a link stack index of the link stack entry corresponding to the first link address in the buffer means.

21. The system of claim 17 , wherein the buffer means comprises a plurality of entries.

22. The system of claim 17 , wherein the means for maintaining the first count of the total number of uncommitted link stack write instructions in the pipeline comprises:

means for incrementing a the first count upon decoding a link stack write instruction; and

means for decrementing the first count when the link stack write instruction commits for execution.

23. The system of claim 22 , wherein means for maintaining the second count of each uncommitted branch instruction, of the uncommitted link stack write instructions ahead of it in the pipeline comprises:

means for copying the first count to the second count; and

means for decrementing the second count when the link stack write instruction commits for execution.

24. A non-transitory computer-readable storage medium comprising code, which, when executed by a processor, causes the processor to perform operations for managing a link stack comprising a plurality of entries, each entry operative to store a link address, the non-transitory computer-readable storage medium comprising:

code for speculatively reading a first link address from a link stack entry of the link stack;

code for generating an indication that a speculative write following the speculative read would overwrite the first link address at the link stack entry, wherein the code for generating an indication that the speculative write following the speculative read would overwrite the first link address at the link stack entry comprises:

code for maintaining a first count of a total number of uncommitted link stack write instructions in a pipeline;

code for maintaining a second count, associated with each uncommitted branch instruction, of a number of uncommitted link stack write instructions ahead of the uncommitted branch instruction in the pipeline; and

code for comparing the second count to the first count upon detecting that a branch was mispredicted, and means for detecting that the first and second counts are not the same;

code for saving the first link address in a link stack restore buffer, in response to the indication; and

code for speculatively writing a second link address to the link stack entry after speculatively reading the first link address, wherein the first link address of the link stack entry is overwritten by the second link address.