Storing look-up table indexes in a return stack buffer
View Patent ↗A return stack buffers (RSB) is modified to store index values instead of addresses. When a function is called, the address following the function call is stored in a look-up table and the index at which the address is stored is pushed to the RSB. When a function returns, an index is popped from the RSB and used to identify an address in the look-up table. In another embodiment, the 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 an entry in a look-up table and pushing an index of the entry into a return stack buffer; and
in response to a function return, removing a most recently written index from the return stack buffer and using the removed index to access an address stored in the look-up table.
2. A method according to claim 1 , wherein an index comprises a smaller number of bits than an address.
3. A method according to claim 1 , wherein the method further comprises:
storing a copy of the entire return stack buffer and a pointer to a top of the return stack buffer each time a prediction is made in the processor.
4. A method according to claim 3 , further comprising:
in response to identifying a mis-prediction, restoring the return stack buffer using data stored when the prediction was made, the data comprising at least a subset of a return stack buffer and a pointer to a top of the return stack buffer.
5. A method according to claim 4 , further comprising, in response to identifying a mis-prediction:
removing or invalidating every entry in the look-up table which is not referenced in the restored return stack buffer.
6. A method according to claim 1 , wherein the method further comprises:
storing a subset of the return stack buffer and a pointer to a top of the return stack buffer each time a prediction is made in the processor.
7. A method according to claim 1 , further comprising, in response to a function call and prior to storing the address following the function call:
determining if the look-up table is full; and
in response to determining that the look-up table is full, removing or invalidating an entry from the look-up table using a replacement algorithm.
8. A method according to claim 7 , wherein the replacement algorithm selects a least recently used entry in the look-up table.
9. A method according to claim 1 , further comprising:
in response to a function return instruction being committed, removing or invalidating an entry corresponding to the function from the look-up table.
10. A method according to claim 1 , wherein the processor is an out-of-order processor.
11. A processor comprising:
a fetch stage; and
resources arranged to store a return stack buffer and a look-up table,
wherein the fetch stage is arranged:
in response to a function call, to store an address following the function call in an entry in the look-up table and to push an index of the entry into the return stack buffer; and
in response to a function return, to remove a most recently written index from the return stack buffer and to use the removed index to access an address stored in the look-up table.
12. A processor according to claim 11 , wherein each entry in the return stack buffer has an associated validity bit to indicate whether the entry is valid or invalid.
13. A processor according to claim 11 , wherein the processor further comprises a branch predictor, and wherein the fetch stage is arranged to store a copy of the entire return stack buffer and a pointer to a top of the return stack buffer each time a prediction is made in the processor.
14. A processor according to claim 13 , wherein the fetch stage is further arranged, in response to identifying a mis-prediction, to restore the return stack buffer using data stored when the prediction was made, the data comprising at least a subset of a return stack buffer and a pointer to a top of the return stack buffer.
15. A processor according to claim 14 , wherein the fetch stage is further arranged, in response to identifying a mis-prediction, to remove or invalidate every entry in the look-up table which is not referenced in the restored return stack buffer.
16. A processor according to claim 11 , wherein the processor further comprises a branch predictor, and wherein the fetch stage is arranged to store a subset of the return stack buffer and a pointer to a top of the return stack buffer each time a prediction is made in the processor.
17. A processor according to claim 11 , wherein the fetch stage is further arranged, in response to a function call and prior to storing the address following the function call:
to determine if the look-up table is full; and
in response to determining that the look-up table is full, to remove or invalidate an entry from the look-up table using a replacement algorithm.
18. A processor according to claim 11 , wherein the fetch stage is further arranged, in response to a function return instruction being committed, to remove or invalidate an entry corresponding to the function from the look-up table.
19. A processor according to claim 11 , wherein the processor is an out-of-order processor.
20. 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 and a look-up table,
wherein the fetch stage is arranged:
in response to a function call, to store an address following the function call in an entry in the look-up table and to push an index of the entry into the return stack buffer; and
in response to a function return, to remove a most recently written index from the return stack buffer and to use the removed index to access an address stored in the look-up table.