Processor with registers storing committed/speculative data and a RAT state history recovery mechanism with retire pointer

• US 6,633,970 B1
• Filed: 12/28/1999
• Issued: 10/14/2003
• Est. Priority Date: 12/28/1999
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Clift, David W., Sager, David J., Boggs, Darrell D.
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US09/472,840
• Time in Patent Office: 1,386 Days
• Field of Search: 712/23, 712/217, 712/218
• US Class Current: 712/217
• CPC Class Codes: G06F 9/384 Register renaming
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

A mechanism is provided for allowing a processor to recover from a failure of a predicted path of instructions (e.g., from a mispredicted branch or other event). The mechanism includes a plurality of physical registers, each physical register can store either architectural data or speculative data. The apparatus also includes a primary array to store a mapping from logical registers to physical registers, the primary array storing a speculative state of the processor. The apparatus also includes a buffer coupled to the primary array to store information identifying which physical registers store architectural data and which physical registers store speculative data. According to another embodiment, a history buffer is coupled to the secondary array and stores historical physical register to logical register mappings performed for each of a plurality of instructions part of a predicted path. The secondary array is movable to a particular speculative state based on the mappings stored in the history buffer, such as to a location where a path failure may occur. The secondary array can then be copied to the primary array when a failure is detected in a predicted path of instructions near where the secondary array is located to allow the processor to recover from the predicted path failure.

Claims

1. An apparatus for allowing a processor to recover from a failure of a predicted path of instructions comprising:

a plurality of physical registers to store architectural data and speculative data, each physical register to store one of architectural data and speculative data;

a primary array to store a speculative state of the processor including mappings from logical registers to physical registers;

a history buffer coupled to the primary array to store information identifying physical registers in a mapped sequence; and

a retirement pointer associated with the buffer, the retirement pointer to identify which physical registers in the mapped sequence store architectural data.

2. The apparatus of claim 1, further comprising logic to change the retirement pointer when one of the physical registers stores architectural data.

3. The apparatus of claim 1, wherein the information stored within the buffer comprises a bit to identify whether a respective physical register stores architectural data.

4. The apparatus of claim 1, wherein the buffer allows recovery from a mispredicted event.

5. The apparatus of claim 1, wherein the buffer comprises an array having a free/old field and a retire field, the free/old field to identify available physical registers and previous physical registers based on corresponding information in the retire field.

6. The apparatus of claim 1, wherein the retirement pointer identifies the next physical address to be allocated.

7. A method of allocating registers in a speculative processor comprising the steps of:

receiving an instruction specifying a logical register for storing an execution result;

allocating a physical register for storing the instruction, said physical register being one of a plurality of registers to store architectural data and speculative data, each physical register to store one of architectural data and speculative data;

storing in a history buffer information identifying physical registers in an allocated sequence; and

moving a retirement pointer associated with the history buffer to identify whether an execution result stored in the physical register in the allocated sequence is architectural data.

8. An apparatus for allowing a processor to recover from a failure of a predicted path of instructions comprising:

a plurality of physical registers to store architectural data and speculative data, each physical register to store one of architectural data and speculative data;

a primary array storing a mapping from logical registers to physical registers, the primary array storing a current speculative state of the processor;

an allocator allocating an available physical register as the physical destination for storing the execution results of an instruction, the allocated physical register corresponding to a logical register;

a history buffer coupled to the secondary array and storing information related to historical remapping of logical registers from previous physical registers to current physical registers;

a secondary array coupled to the primary array and the history buffer, the secondary array storing a secondary speculative state of the processor including a mapping from logical registers to physical registers, the secondary array being movable to any instruction between the point of physical register allocation and retirement based on the history buffer, the secondary array being movable to any location or instruction independent of which instructions have been executed;

wherein the secondary array can be copied to the primary array to allow the processor to recover from the failure in the predicted path.

9. The apparatus of claim 8, further comprising a retirement pointer associated with the history buffer to identify which physical registers store architectural data.

10. The apparatus of claim 8 wherein said secondary array is moved to an estimated location of a next failure in the predicted path, the secondary array being adjusted to a correct state if necessary and then copied into the primary array if a path failure occurs to allow the primary array recover from the path failure to the correct state.

11. The apparatus of claim 8 wherein the processor attempts to maintain the secondary array at an estimate of the next mispredicted branch instruction or other instruction which may generate an event that would result in a failure of the subsequent path.

12. The apparatus of claim 8 wherein the secondary array comprises a plurality of secondary arrays, at least some of the secondary arrays being located at different locations, one of the secondary arrays being selected and copied into the primary array if predicted path failure occurs to restore the primary array to a correct state.

13. The apparatus of claim 11 wherein each of the secondary arrays is located at a different location in the history buffer.

14. The apparatus of claim 8 wherein the history buffer includes path information that allows the processor to distinguish between:

a) register mappings for any instructions after a path failure which are part of failed or incorrect path which should not be executed, and b) register mappings for instructions after a path failure which are part of a correct path.

15. The apparatus of claim 8 wherein the history buffer includes a list of free or available physical registers.

16. The apparatus of claim 8 wherein the history buffer comprises one or more pointers to the history buffer, including:

an allocation pointer identifying the next available physical register to be allocated for the next instruction;

a retirement pointer identifying the entry in the history buffer corresponding to the next instruction to be retired; and

a secondary pointer identifying the current location or state of the secondary array.

17. The apparatus of claim 8 wherein the secondary array comprises a plurality of secondary arrays, each secondary array storing a secondary speculative state of the processor including a mapping from logical registers to physical registers, each of the secondary arrays being movable to any instruction between the point of physical register allocation and retirement based on the history buffer, each of the secondary arrays being movable to any location or instruction independent of which instructions have been executed;

wherein one of the secondary arrays can be copied to the primary array to allow the processor to recover from the failure in the predicted path.

18. The apparatus of claim 17 wherein each of the secondary arrays storing a speculative state at an estimate of where a path failure is likely to occur, the apparatus using branch prediction logic to identify estimates where the path failures are likely to occur.

19. An apparatus for allowing a processor to recover from a failure of a predicted path of instructions comprising:

a plurality of physical registers to store architectural data and speculative data, each physical register to store one of architectural data and speculative data;

a primary array storing a first speculative state of the processor including a mapping from logical registers to physical registers,

a secondary array coupled to the primary array, the secondary array storing a second speculative state including a mapping from logical registers to physical registers, the second speculative state of the processor being previous to the primary speculative state of the processor; and

a history buffer coupled to the secondary array and storing information related to historical remapping of logical registers from previous physical registers to current physical registers.

20. The apparatus of claim 19 wherein the secondary array being movable to a particular speculative state based on the mappings stored in the history buffer, wherein the secondary array can be copied to the primary array when a failure is detected in a predicted path of instructions to allow the processor to recover from the failure in the predicted path.

21. The apparatus of claim 19 wherein the history buffer identifies the following information for each instruction:

a logical register that is the logical destination for the execution results of the instruction;

a new physical register selected from available physical registers and that is allocated as the physical destination for the execution results of the instruction, the new physical register being mapped to the logical register; and

an old physical register previously mapped to the logical register.

22. The apparatus of claim 21 wherein the predicted path failure comprises at least one of the following:

a mispredicted branch instruction;

an instruction that generated a fault; and

an instruction that generated a trap.

23. The apparatus of claim 19 wherein the primary array includes a pointer to a physical register for each logical register.

24. The apparatus of claim 19 wherein the secondary array includes a pointer to a physical register for each logical register.

25. The apparatus of claim 19, further comprising a retirement pointer associated with the history buffer to identify which physical registers store architectural data.

26. An apparatus comprising:

a plurality of registers to store architecturally committed data and speculative data, each one of said plurality of registers to store one of architecturally committed data and speculative data;

logic to store a plurality of states including a speculative state and at least one shadow state, each of said plurality of states including mappings from logical registers to physical registers in said plurality of registers;

a history buffer storing information identifying physical registers in a mapped sequence and information related to historical remapping of logical registers from previous physical registers to current physical registers; and

logic to change a retirement pointer associated with the history buffer, the retirement pointer to identify which physical pointers in the mapped sequence store architecturally committed data.

27. The apparatus of claim 26 and further comprising:

logic to advance a plurality of pointers, one of said plurality of pointers being an allocation pointer that indicates a primary state that is advanced by speculatively executed instructions, one of said plurality of pointers being a shadow pointer that indicates a shadow state having a lesser degree of speculation than said primary state.

28. The apparatus of claim 27 and further comprising:

speculation recovery logic to copy said shadow state to said primary state to undo at least a portion of completed speculative execution.

29. The apparatus of claim 27 wherein said logic to advance said plurality of pointers is capable independently advancing each of said plurality of pointers.

30. The apparatus of claim 28 wherein said at least one shadow state comprises a plurality of shadow states, each of said plurality of shadow states reflecting a different degree of speculation that is lesser than said primary state, and wherein said speculation recovery logic is capable of copying any of said plurality of shadow states to said primary state to undo speculative execution.

31. The apparatus of claim 26 wherein said logic to store a plurality of states comprises:

a primary array to store said speculative state;

a secondary array to store said shadow state; and

logic to update said primary array upon retirement of an instruction.

32. The apparatus of claim 31 wherein the logic to update said primary array comprises a history buffer coupled to the secondary array, said history buffer to store historical physical register to logical register mappings performed for each of a plurality of instructions of a predicted path.

33. The apparatus of claim 26, wherein the logic changes the retirement pointer when one of the physical registers stores architecturally committed data.

34. The apparatus of claim 26, further comprising a history buffer associated with the retirement pointer, the retirement pointer to identify a specific entry in the history buffer.

35. The apparatus of claim 34, wherein the information stored within the buffer comprises a bit to identify whether a respective physical register stores architectural data.

36. The apparatus of claim 34, wherein the history buffer allows recovery from a mispredicted event.

37. The apparatus of claim 34, wherein the history buffer comprises an array having a free/old field and a retire field, the free/old field to identify available physical registers and previous physical registers based on corresponding information in the retire field.

38. The apparatus of claim 34, wherein the retirement pointer identifies the next physical address to be allocated.

39. An apparatus comprising:

a plurality of physical registers to store architecturally committed data and speculative data, each one of said plurality of registers to store one of architecturally committed data and speculative data;

a primary array to store a speculative state of a processor including a mapping from logical registers to physical registers;

a history buffer to store information related to historical remapping of logical registers from previous physical registers to current physical registers in a mapped sequence; and

a pointer controlled by logic so as to identify a location within the history buffer, the location to identify which physical registers in the mapped sequence store architectural data.

40. The apparatus of claim 39, further comprising logic to change the retirement pointer when one of the physical registers stores architectural data.

41. The apparatus of claim 39, wherein the information stored within the history buffer comprises a bit to identify whether a respective physical register stores architectural data.

42. The apparatus of claim 39, wherein the history buffer allows recovery from a mispredicted event.

43. The apparatus of claim 39, wherein the history buffer comprises an array having a free/old field and a retire field, the free/old field to identify available physical registers and previous physical registers based on corresponding information in the retire field.

44. The apparatus of claim 39, wherein the retirement pointer identifies the next physical address to be allocated.