Return stack buffer having multiple address slots per stack entry
View Patent ↗A return stack buffer (RSB) is modified such that each entry comprises two or more address slots. When a function is called, the address following the function call is pushed to the RSB and stored in a selected one of the address slots in a top entry in the RSB. One or more pointer bits within the entry are set to indicate which slot the address was stored in.
1. A method of operating a processor, comprising:
in response to a function call, storing an address following the function call in one of a plurality of address slots in a top entry in a return stack buffer, updating a stack pointer and at least one stack pointer bit to point to the entry and the address slot in which the address was stored and setting a value of two or more pointer bits in the entry, the two or more pointer bits comprising a first part indicating at least a most recently written address slot in the entry and a second part indicating, for each of the plurality of address slots in the entry, a most recently written address slot in the previous entry at the time that the particular one of the plurality of address slots in the entry was written; and
in response to a function return, reading an address from an address slot in an entry in the return stack buffer identified by the stack pointer and at least one stack pointer bit, updating the stack pointer to point to the previous entry, and updating the at least one stack pointer bit based on the second part of the pointer bits for the entry and the address slot from which the address was read.
2. A method according to claim 1 , wherein the address following the function call is stored in a selected one of the plurality of address slots, wherein the address slot is selected using a replacement algorithm.
3. A method according to claim 2 , wherein the replacement algorithm selects a least recently used address slot in the entry.
4. A method according to claim 1 , wherein the method further comprises:
storing the stack pointer and the at least one stack pointer bit for the return stack buffer each time a prediction is made in the processor.
5. A method according to claim 1 , wherein the return stack buffer comprises a plurality of entries and each entry comprises two address slots and two or more pointer bits.
6. A method according to claim 5 , wherein the two or more pointer bits comprise:
a first part indicating which of the two address slots was most recently written; and
a second part comprising at least one bit associated with the first address slot and at least one bit associated with the second address slot, wherein the bits associated with an address slot are arranged to indicate a most recently written address slot in the previous entry in the return stack buffer at the time that the particular address slot was written.
7. A method according to claim 1 , wherein the return stack buffer comprises a plurality of entries and each entry comprises a plurality of address slots and two or more pointer bits for each address slot.
8. A method according to claim 7 , wherein the two or more pointer bits for each address slot comprise:
a first part indicating whether the address slot was most recently written; and
a second part arranged to indicate a most recently written address slot in the previous entry in the return stack buffer at the time that the address slot was written.
9. A method according to claim 1 , wherein the processor is an out-of-order processor.
10. A processor comprising:
a fetch stage; and
resources arranged to store a return stack buffer comprising more than one address slot in at least a top entry thereof, wherein the fetch stage is arranged:
in response to a function call, to store an address following the function call in a selected address slot in said top entry, to update a stack pointer and at least one stack pointer bit to point to the entry and the address slot in which the address was stored and to set a value of two or more pointer bits in the entry, the two or more pointer bits comprising a first part indicating at least a most recently written address slot in the entry and a second part indicating, for each of the plurality of address slots in the entry, a most recently written address slot in the previous entry at the time that the particular one of the plurality of address slots in the entry was written; and
in response to a function return, to read an address from an address slot in an entry in the return stack buffer identified by the stack pointer and at least one stack pointer bit, to update the stack pointer to point to the previous entry and to update the at least one stack pointer bit based on the second part of the pointer bits for the entry and the address slot from which the address was read.
11. A processor according to claim 10 , wherein the address following the function call is stored in a selected one of the plurality of address slots, wherein the address slot is selected using a replacement algorithm.
12. A processor according to claim 11 , wherein the replacement algorithm selects a least recently used address slot in the entry.
13. A processor according to claim 10 , wherein the processor further comprises a branch predictor and the fetch stage is further arranged to store the stack pointer and the at least one stack pointer bit for the return stack buffer each time a prediction is made in the processor.
14. A processor according to claim 10 , wherein the return stack buffer comprises a plurality of entries and each entry comprises at least two address slots and two or more pointer bits.
15. A processor according to claim 10 , wherein the return stack buffer comprises a plurality of entries and each entry comprises a plurality of address slots and two or more pointer bits for each address slot.
16. A processor according to claim 10 , wherein the processor is an out-of-order processor.
17. A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when executed at a computer system for generating a representation of a digital circuit from definitions of circuit elements and data defining rules for combining those circuit elements, cause the computer system to generate a processor comprising:
a fetch stage; and
resources arranged to store a return stack buffer comprising more than one address slot in at least a top entry thereof, wherein the fetch stage is arranged:
in response to a function call, to store an address following the function call in a selected address slot in said top entry, to update a stack pointer and at least one stack pointer bit to point to the entry and the address slot in which the address was stored and to set a value of two or more pointer bits in the entry, the two or more pointer bits comprising a first part indicating at least a most recently written address slot in the entry and a second part indicating, for each of the plurality of address slots in the entry, a most recently written address slot in the previous entry at the time that the particular one of the plurality of address slots in the entry was written; and
in response to a function return, to read an address from an address slot in an entry in the return stack buffer identified by the stack pointer and at least one stack pointer bit, to update the stack pointer to point to the previous entry and to update the at least one stack pointer bit based on the second part of the pointer bits for the entry and the address slot from which the address was read.
18. A computer readable storage medium according to claim 17 , wherein the processor is an out-of-order processor.