Flushable free register list having selected pointers moving in unison

• US 7,055,020 B2
• Filed: 06/13/2001
• Issued: 05/30/2006
• 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
• Primary Examiner(s): Coleman, Eric
• Application Number:
  US09/881,071
• Publication Number:
  US 20020194455A1
• Time in Patent Office: 1,812 Days
• Field of Search: 712/23, 712/228, 712/218, 712/227, 712/217
• 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 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 microprocessor to prevent a register allocated as a destination operand for said instruction of said first thread from being overwritten before said instruction of said first thread retires, said first set of pointers includes at least two pointers set apart by a fixed distance and move in unison, at all times, up and down said structure.

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 a 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 a 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 first 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, at all times, 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, at all times, up and down said structure.

6. The method of claim 4, wherein said read pointer of said first set of pointers indicates said physical register location awaiting said register allocation as 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 of said first set of pointers indicates said physical register location of said register allocated as said destination operand to identify where data should be written for said instruction of said first thread that committed.

8. The method of claim 4, wherein said retire pointer of said first set of pointers indicates said physical register location of said register allocated as 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 of said second set of pointers indicates said physical register location awaiting said register allocation as 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 of said second set of pointers indicates said physical register location of said register allocated as 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 of said second set of pointers indicates said physical register location of said register allocated as 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 first 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 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.

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 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.

17. The method of claim 5, wherein said register allocated for said plurality of instructions of 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.

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 first thread of said microprocessor that has not yet committed to its 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.

20. The method of claim 17, further comprising the step of restoring said register allocated for said instruction of said second thread of said microprocessor that has not yet committed to its 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.

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

providing a single 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 a 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 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.

50. The method of claim 21, wherein the single structure includes at least one protected register region identifying physical register pointers allocated to instructions having a logical destination register decoded and issued but not yet retired.

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 first portion of said structure to track said physical registers assigned as said destination registers for a first thread of said microprocessor, said first set of register pointers includes a retire row pointer to identify where a pointer pointing to at least one of said plurality of physical registers assigned as a destination register for an instruction in said first thread that is next to be retired and a read pointer to identify where a pointer pointing to an available physical register available for assignment as a destination operand for an instruction for said first thread, wherein when said microprocessor issues a flush request for said instruction in said first thread, moving said 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.

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 23, 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 in said first 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, 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.

27. The semiconductor device of claim 23, wherein said second 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 second thread that is committed should be written, and said retire row pointer identifies where a pointer pointing to said physical register of an instruction in said second thread that is next to be retired.

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 microprocessor to prevent a register allocated as a destination operand for said instruction of said first thread from being overwritten before said instruction of said first thread retires, said first set of pointers includes a first pointer and a second pointer always set apart by a fixed distance and move in unison, at all times, up and down said structure.

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 a 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.

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 of said first thread 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 further 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, at all times, up and down said structure.

33. The computer readable medium of claim 30, 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, at all times, up and down said structure.

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

35. The computer readable medium of claim 32, wherein said write pointer of said first set of pointers 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 of said first set of pointers 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 33, wherein said read pointer indicates said physical register location awaiting said register allocation as 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 33, wherein said write pointer of said first set of pointers 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 33, wherein said retire pointer of said first set of pointers 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 33, 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 33, 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 instruction 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 33, wherein said register allocated for said 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 44, further comprising the step of restoring said register allocated for said instruction of said first thread of said microprocessor that has not yet committed to its 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 45, further comprising the step of restoring said register allocated for said instruction of said second thread of said microprocessor that has not yet committed to its 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.

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 single 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 a 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 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.