Flushable free register list

• US 20020194455A1
• Filed: 06/13/2001
• Published: 12/19/2002
• Est. Priority Date: 06/13/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Gold, Spencer M., Staraitis, Julie M., Eisenberg, Jason
• Granted Patent: US 7,055,020 B2
• Time in Patent Office: Days
• US Class Current: 712/217
• CPC Class Codes: G06F 9/3842 Speculative instruction execution
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming

Abstract

A method and apparatus is provided for restoring a free physical register list to its previous state without having to physically restore any data. The method and semiconductor device utilizes sets of pointers to manage physical register pointers in the physical register list. The physical register list is able to independently track physical registers for multiple threads of a multithreading microprocessor.

Claims

1. In a microprocessor performing speculative instruction execution, a method comprising the steps of:

providing a structure to track register allocation for a thread of said microprocessor; and

tracking a set of pointers in said structure assigned to manage said register allocation for an instruction of said thread of said microprocessor to prevent said register allocated as a destination operand for said instruction of said first thread from being overwritten before said instruction of said thread retires.

2. The method of claim 1, further comprising the step of tracking a second set of pointers in said structure assigned to manage a register allocation for an instruction of said second thread of said microprocessor to prevent a register allocated as a destination operand for said instruction of said second thread from being overwritten before said instruction of said second thread retires, whereby said first set of pointers and said second set of pointers track independently of each other.

3. The method of claim 1, wherein said structure comprises pointers to said registers allocated and pointers to registers deallocated, where said registers allocated and said registers deallocated are physical registers that operate as a destination operand for said instructions executing on said multithreading microprocessor where said destination operands identifies where data resulting from logical operations are to be written.

4. The method of claim 1, wherein said set of pointers comprises a read pointer, a write pointer, and a retire pointer where said read and write pointers are set apart by a fixed distance and move in unison up and down said structure.

5. The method of claim 2, wherein said second set of pointers comprises a read pointer, a write now pointer, and a retire pointer where said read and write pointers are set apart by a fixed distance and move in unison up and down said structure.

6. The method of claim 4, wherein said read pointer indicates said physical register location awaiting said register allocation as a said destination operand to identify where data should be written when said instruction of said first thread is executed by said microprocessor.

7. The method of claim 4, wherein said write pointer indicates said physical register location of said register allocated as a said destination operand to identify where data should be written for said instruction of said thread that committed.

8. The method of claim 4, wherein said retire pointer indicates said physical register location of said register allocated as a said destination operand for said instruction of said thread that is next to be retired.

9. The method of claim 5, wherein said read pointer indicates said physical register location awaiting said register allocation as a said destination operand to identify where data should be written when said instruction of said second thread is executed by said microprocessor.

10. The method of claim 5, wherein said write pointer indicates said physical register location of said register allocated as a said destination operand to identify where data should be written for said instruction of said second thread that committed.

11. The method of claim 5, wherein said retire pointer indicates said physical register location of said register allocated as a said destination operand for said instruction of said second thread that is next to be retired.

12. The method of claim 4, wherein the number of physical register pointers between said read pointer and said retire pointer of said first set of pointers indicates said physical registers available for said register allocation for said thread of said microprocessor.

13. The method of claim 5, wherein the number of physical register pointers between said read pointer and said retire pointer of said second set of pointers indicates said physical registers available for said register allocation for said second thread of said microprocessor.

14. The method of claim 4, wherein the number of physical register pointers between said retire pointer and said write pointer of said set of pointers indicates said registers allocated to said destination operand for a plurality of instructions of said thread that are to become available for reallocation upon retirement of said plurality of instructions.

15. The method of claim 5, wherein the number of physical register pointers between said retire pointer and said write pointer of said second set of pointers indicates said physical registers allocated to said destination operand for a plurality of instructions of said second thread that are to become available for reallocation upon retirement of said plurality of instructions.

16. The method of claim 4, wherein said register allocated for said plurality of instructions of said thread of said microprocessor that have not yet committed is defined by the number of physical register pointers bounded by said read pointer and said retire pointer minus said fixed distance between said read pointer and said write pointer of said set of pointers.

17. The method of claim 5, wherein said register allocated for said plurality of instructions said second thread of said multithreading microprocessor that have not yet committed is defined by the number of physical register pointers bounded by said read pointer and said retire pointer minus said fixed distance between said read pointer and said write pointer of said second set of pointers.

18. The method of claim 1, wherein said method of register allocation is performed in a modulo-8 memory array.

19. The method of claim 16, further comprising the step of restoring said register allocated for said instruction of said thread of said multithreading microprocessor that have not yet committed to their previous state in said thread of said microprocessor by pointing said read pointer of said set of pointers to said physical register pointer allocated to said physical register location corresponding to said instruction being flushed by said microprocessor.

20. The method of claim 17, further comprising the step of restoring said register allocated for said instruction of said second thread of said multithreading microprocessor that have not yet committed to their previous state in said second thread of said multithreading microprocessor by pointing said read pointer of said second set of pointers to said physical register pointer allocated to said physical register location corresponding to said instruction being flushed by said multithreading microprocessor.

21. In a multithreading microprocessor performing speculative instruction execution, a method comprising the steps of:

providing a structure to track register allocation for a first thread and a second thread of said multithreading microprocessor;

tracking a first set of pointers in said structure assigned to manage said register allocation for an instruction of said first thread of said multithreading processor to prevent said register allocated as a destination operand for said instruction of said first thread from being overwritten before said instruction of said first thread retires; and

tracking a second set of pointers in said structure assigned to manage said register allocation for an instruction of said second thread of said multithreading processor to prevent said register allocated as a destination operand for said instruction of said second thread from being overwritten before said instruction of said second thread retires, whereby said first set of pointers and said second set of pointers track independently of each other.

22. A semiconductor device having a plurality of physical registers that are assigned as destination registers for instructions to be executed by a microprocessor performing out-of-order execution, comprising:

a first module providing a structure for holding information identifying available physical registers for said microprocessor;

a first set of register pointers assigned to a of said structure to track said physical registers assigned as said destination registers for a thread of said microprocessor and when said microprocessor issues a flush request for an instruction in said thread, moving a read pointer of said set of register pointers to said physical register assigned as said destination register for said instruction being flushed in said thread to restore said physical register to a previous state.

23. The semiconductor device of claim 22, further comprising a second set of register pointers assigned to a second portion of said structure to track said physical registers assigned as said destination registers for a second thread of said microprocessor and when said microprocessor issues a flush request for an instruction in said second thread, moving a read pointer of said second set of register pointers to said physical register assigned as said destination register for said instruction being flushed in said second thread to restore said physical register to a previous state.

24. The semiconductor device of claim 22, wherein said structure comprises a free physical register list for said identification of said available physical requests for said microprocessor.

25. The semiconductor device of claim 22, wherein said first set of register pointers move independently of said second set of register pointers, wherein said first set of register pointers identify said physical registers assigned to instructions is said thread of said microprocessor that have not been committed and said second set of register pointers identify said physical registers assigned to instructions in said second thread of said microprocessor that have not been committed.

26. The semiconductor device of claim 22, wherein said first set of register pointers further comprises, a write row pointer and a retire row pointer, wherein said write row pointer identifies where a pointer pointing to said physical register of an instruction in said first thread should be written when said instruction commits and said retire row pointer identifies where a pointer pointing to said physical register of an instruction in said first thread that is next to be retired.

27. The semiconductor device of claim 22, wherein said second set of register pointers further comprises, a write row pointer and a retire row pointer, wherein said write now pointer identifies where a pointer pointing to said physical register of an instruction in said second thread that is committed should be written, and said retire now pointer identifies where a pointer pointing to said physical register of an instruction in said second thread that is next to be retired.

30. The computer readable medium of claim 29 further comprising the step of tracking a second set of pointers in said structure assigned to manage said register allocation for an instruction of said second thread of said processor to prevent said register allocated as a destination operand for said instruction of said second thread from being overwritten before said instruction of said second thread retires, whereby said first set of pointers and said second set of pointers track independently of each other.

31. The computer readable medium of claim 29, wherein said structure comprises pointers to said registers allocated and pointers to registers deallocated, where said registers allocated and said registers deallocated are physical registers that operate as a destination operands for said instruction executing on said microprocessor where said destination operands identifies where data resulting from logical operations are to be written.

32. The computer readable medium of claim 29, wherein said first set of pointers comprises a read pointer, a write pointer, and a retire pointer wherein said read pointer and said write pointer are set apart by a fixed distance and move in unison up and down said structure.

33. The computer readable medium of claim 29, wherein said second set of pointers comprises a read pointer, a write pointer, and a retire pointer wherein said read pointer and said write pointer are set apart by a fixed distance and move in unison up and down said structure.

34. The computer readable medium of claim 32, wherein said read pointer indicates said physical register location awaiting said register allocation as a said destination operand to identify where data should be written when said instruction of said first thread is executed by said multithreading microprocessor.

35. The computer readable medium of claim 32, wherein said write pointer indicates said physical register location of said register allocated as a said destination operand to identify where data should be written for said instruction of said first thread that committed.

36. The computer readable medium of claim 32, wherein said retire pointer indicates said physical register location of said register allocated as a said destination operand for said instruction of said first thread that is next to be retired.

37. The computer readable medium of claim 32, wherein said read pointer indicates said physical register location awaiting said register allocation as a said destination operand to identify where data should be written when said instruction of said second thread is executed by said microprocessor.

38. The computer readable medium of claim 32, wherein said write pointer indicates said physical register location of said register allocated as a said destination operand to identify where data should be written for said instruction of said second thread that committed.

39. The computer readable medium of claim 32, wherein said retire pointer indicates said physical register location of said register allocated as a said destination operand for said instruction of said second thread that is next to be retired.

40. The computer readable medium of claim 32, wherein the number of physical register pointers between said read pointer and said retire pointer of said first set of pointers indicates said physical registers available for said register allocation for said first thread of said microprocessor.

41. The computer readable medium of claim 32, wherein the number of physical register pointers between said read pointer and said retire pointer of said second set of pointers indicates said physical registers available for said register allocation for said second thread of said microprocessor.

42. The computer readable medium of claim 32, wherein the number of physical register pointers between said retire pointer and said write pointer of said first set of pointers indicates said registers allocated to said destination operand for a plurality of instructions of said first thread that are to become available for reallocation upon retirement of said plurality of instructions.

43. The computer readable medium of claim 32, wherein the number of physical register pointers between said retire pointer and said write pointer of said second set of pointers indicates said physical registers allocated to said destination operand for a plurality of instructions of said second thread that are to become available for reallocation upon retirement of said plurality of instructions.

44. The computer readable medium of claim 32, wherein said register allocated for said plurality of instructions of said first thread of said microprocessor that have not yet committed is defined by the number of physical register pointers bounded by said read pointer and said retire pointer minus said fixed distance between said read pointer and said write pointer of said first set of pointers.

45. The computer readable medium of claim 32, wherein said register allocated for said plurality of instructions said second thread of said microprocessor that have not yet committed is defined by the number of physical register pointers bounded by said read pointer and said retire pointer minus said fixed distance between said read pointer and said write pointer of said second set of pointers.

46. The computer readable medium of claim 29, wherein said method of register allocation is performed in a modulo-8 memory array.

47. The computer readable medium of claim 45, further comprising the step of restoring said register allocated for said instruction of said first thread of said multithreading microprocessor that have not yet committed to their previous state in said first thread of said microprocessor by pointing said read pointer of said first set of pointers to said physical register pointer allocated to said physical register location corresponding to said instruction being flushed by said microprocessor.

48. The computer readable medium of claim 47, further comprising the step of restoring said register allocated for said instruction of said second thread of said microprocessor that have not yet committed to their previous state in said second thread of said microprocessor by pointing said read pointer of said second set of pointers to said physical register pointer allocated to said physical register location corresponding to said instruction being flushed by said microprocessor.

28. A semiconductor device having a plurality of physical registers that are assigned as destination registers for instructions to be executed by a microprocessor performing out-of-order execution, comprising:

a first module providing a structure for holding information identifying available physical registers for said microprocessor;

a first set of register pointers assigned to a first portion of said structure to track said physical registers assigned as said destination registers for a first thread of said microprocessor and when said microprocessor issues a flush request for an instruction in said first thread, moving a read pointer of said first set of register pointers to said physical register assigned as said destination register for said instruction being flushed in said first thread to restore said physical register to a previous state; and

a second set of register pointers assigned to a second portion of said structure to track said physical registers assigned as said destination registers for a second thread of said microprocessor and when said microprocessor issues a flush request for an instruction in said second thread, moving a read pointer of said second set of register pointers to said physical register assigned as said destination register for said instruction being flushed in said second thread to restore said physical register to a previous state.

29. A computer readable medium holding computer executable instructions for performing a method in a microprocessor performing speculative instruction execution, said method comprising the steps of:

providing a structure to track register allocation for a first thread of said microprocessor; and

tracking a first set of pointers in said structure assigned to manage said register allocation for an instruction of said first thread of said processor to prevent said register allocated as a destination operand for said instruction of said first thread from being overwritten before said instruction of said first thread retires.

49. A computer readable medium holding computer executable instructions for performing a method in a multithreading microprocessor performing speculative instruction execution, said method comprising the steps of:

providing a structure to track register allocation for a first thread and a second thread of said multithreading microprocessor;

tracking a first set of pointers in said structure assigned to manage said register allocation for an instruction of said first thread of said multithreading processor to prevent said register allocated as a destination operand for said instruction of said first thread from being overwritten before said instruction of said first thread retires; and

tracking a second set of pointers in said structure assigned to manage said register allocation for an instruction of said second thread of said multithreading processor to prevent said register allocated as a destination operand for said instruction of said second thread from being overwritten before said instruction of said second thread retires, whereby said first set of pointers and said second set of pointers track independently of each other.