Stack pointer value prediction
View Patent ↗Methods and apparatus for predicting the value of a stack pointer which store data when an instruction is seen which grows the stack. The information which is stored includes a size parameter which indicates by how much the stack is grown and one or both of: the register ID currently holding the stack pointer value or the current stack pointer value. When a subsequent instruction shrinking the stack is seen, the stored data is searched for one or more entries which has a corresponding size parameter. If such an entry is identified, the other information stored in that entry is used to predict the value of the stack pointer instead of using the instruction to calculate the new stack pointer value. Where register renaming is used, the information in the entry is used to remap the stack pointer to a different physical register.
1. A method of predicting stack pointer values for a stack in a processor, the stack having an associated stack pointer, the method comprising:
in response to detection of an instruction growing the stack, storing a data entry in a data structure different from the stack using at least one processor, the data entry comprising a size value corresponding to an amount by which the instruction grows the stack and at least one of:
a register ID of a physical register storing a value of the stack pointer prior to the instruction growing the stack; and
the value of the stack pointer prior to the instruction growing the stack; and
in response to subsequent detection of an instruction shrinking the stack, comparing a size value corresponding to an amount by which the instruction shrinks the stack to the stored size value in the data structure;
in response to detecting a correspondence between the size value corresponding to an amount by which the instruction shrinks the stack and the stored size value in the data structure,
updating the stack pointer based on at least one of the register ID and the value of the stack pointer in the data entry comprising the stored size value used in the comparison and removing from the data structure the data entry comprising the stored size value used in the comparison; and
in response to failing to detect a correspondence between the size value corresponding to an amount by which the instruction shrinks the stack and the stored size value, removing the data entry from the data structure.
2. A method according to claim 1 , wherein the stored data entry comprises a size value corresponding to an amount by which an instruction grows the stack and a register ID of a physical register storing a value of the stack pointer prior to the instruction growing the stack.
3. A method according to claim 1 , wherein the stored data entry comprises a size value corresponding to an amount by which an instruction grows the stack and a value of the stack pointer prior to the instruction growing the stack.
4. A method according to claim 1 , wherein comparing a size value corresponding to an amount by which the instruction shrinks the stack to stored size value in the data structure comprises:
comparing a size value corresponding to an amount by which the instruction shrinks the stack to a size value in a single most recent entry the data structure.
5. A method according to claim 1 , wherein comparing a size value corresponding to an amount by which the instruction shrinks the stack to the stored size value in the data structure comprises:
comparing a size value corresponding to an amount by which the instruction shrinks the stack to a stored size value in an entry in the data structure prior to an entry including a register ID of the current stack pointer.
6. A method according to claim 5 , further comprising:
in response to detecting an instruction setting a frame pointer based on the value of a stack pointer, adding a new data entry to the data structure with a size value of zero.
7. A method according to claim 5 , further comprising:
removing from the data structure all most recent data entries up to an including the entry including the register ID of the current stack pointer.
8. A method according to claim 1 , wherein comparing a size value corresponding to an amount by which the instruction shrinks the stack to the stored size value in the data structure comprises:
comparing a size value corresponding to an amount by which the instruction shrinks the stack to a size value in x most recent entries the data structure, where x=1; and
in response to detecting no correspondence between the size value corresponding to an amount by which the instruction shrinks the stack and the size value in x most recent entries in the data structure, repeating the comparison with a value of x increased by 1 until a correspondence is detected or x exceeds a predefined threshold.
9. A method according to claim 1 , wherein comparing a size value corresponding to an amount by which the instruction shrinks the stack to the stored size value in the data structure comprises:
(i) comparing a size value corresponding to an amount by which the instruction shrinks the stack to a size value in a single most recent entry the data structure;
(ii) in response to detecting no correspondence between the size value corresponding to an amount by which the instruction shrinks the stack and the size value in the most recent entry the data structure, determining whether a maximum number of iterations has been reached or a top entry in the data structure is empty;
(iii) in response to determining that a maximum number of iterations has not been reached and a top entry in the data structure is not empty, determining whether the size value corresponding to an amount by which the instruction shrinks the stack is greater than the size value in the most recent entry in the data structure;
(iv) in response to determining that the size value corresponding to an amount by which the instruction shrinks the stack is greater than the size value in the most recent entry in the data structure, removing the most recent entry from the data structure and reducing the size value corresponding to an amount by which the instruction shrinks the stack by the size value in the removed entry from the data structure and returning to block (i) in a further iteration; and
(v) in response to determining that the size value corresponding to an amount by which the instruction shrinks the stack is not greater than the size value in the most recent entry in the data structure, reducing a size value in a next most recent entry in the data structure by a difference between the amount by which the instruction shrinks the stack and the size value in the removed most recent entry.
10. A method according to claim 1 , further comprising, in a load-store unit in the processor:
detecting a change in a stack pointer; and
in response to detecting a change in the stack pointer, storing a register ID of a physical register storing a value of the stack pointer prior to the change and the value of the stack pointer prior to the change.
11. A method according to claim 1 , further comprising in response to detecting an interrupt, removing any entries from the data structure.
12. A processor comprising:
memory arranged to store a stack, the stack having an associated stack pointer; a stack pointer value prediction module; and
memory arranged to store a data structure different from the stack, wherein the stack pointer value prediction module is arranged:
in response to detection of an instruction growing the stack, to store, in the data structure, a data entry comprising a size value corresponding to an amount by which the instruction grows the stack and at least one of:
a register ID of a physical register storing a value of the stack pointer prior to the instruction growing the stack; and
the value of the stack pointer prior to the instruction growing the stack; and in response to subsequent detection of an instruction shrinking the stack, to compare a size value corresponding to an amount by which the instruction shrinks the stack to stored size value in the data structure;
in response to detecting a correspondence between the size value corresponding to an amount by which the instruction shrinks the stack and the stored size value in the data structure, to update the stack pointer based on at least one of the register ID and the value of the stack pointer in the data entry comprising the stored size value used in the comparison and removing from the data structure the data entry comprising the stored size value used in the comparison; and
in response to failing to detect a correspondence between the size value corresponding to an amount by which the instruction shrinks the stack and the stored size value, to remove the data entry from the data structure.
13. A processor according to claim 12 , wherein the stored data entry in the data structure comprises a size value corresponding to an amount by which an instruction grows the stack and a register ID of a physical register storing a value of the stack pointer prior to the instruction growing the stack.
14. A processor according to claim 12 , wherein the stored data entry in the data structure comprises a size value corresponding to an amount by which an instruction grows the stack and a value of the stack pointer prior to the instruction growing the stack.
15. A processor according to claim 12 , wherein comparing a size value corresponding to an amount by which the instruction shrinks the stack to stored size value in the data structure comprises:
comparing a size value corresponding to an amount by which the instruction shrinks the stack to a size value in a single most recent entry the data structure.
16. A processor according to claim 12 , wherein comparing a size value corresponding to an amount by which the instruction shrinks the stack to the stored size value in the data structure comprises:
comparing a size value corresponding to an amount by which the instruction shrinks the stack to a stored size value in an entry in the data structure prior to an entry including a register ID of the current stack pointer.
17. A processor according to claim 16 , wherein the stack pointer value prediction module is further arranged, in response to detecting an instruction setting a frame pointer based on the value of a stack pointer, to add a new data entry to the data structure with a size value of zero.
18. A processor according to claim 16 , wherein the stack pointer value prediction module is further arranged to remove from the data structure all most recent data entries up to an including the entry including the register ID of the current stack pointer.
19. A processor according to claim 12 , wherein the processor is an out-of-order processor.
20. A method of predicting stack pointer values for a stack in a processor, the stack having an associated stack pointer and the method comprising, in a load-store unit in the processor:
detecting a change in a stack pointer;
in response to detecting a change in the stack pointer, storing a register ID of a physical register storing a value of the stack pointer prior to the change and the value of the stack pointer prior to the change; and
in response to receiving an instruction to load/store using a physical register corresponding to a stored register ID, calculating an address for the load/store using the stored value of the stack pointer associated with the stored register ID.