System and method for permitting out-of-order execution of load and store instructions

• US 6,301,654 B1
• Filed: 12/16/1998
• Issued: 10/09/2001
• Est. Priority Date: 12/16/1998
• Status: Expired due to Term

• Current Assignee: Intellectual Discovery Co., Ltd.
• Original Assignee: International Business Machines Corporation
• Inventors: Shippy, Dave, Ronchetti, Bruce Joseph, Thatcher, Larry Edward
• Primary Examiner(s): Hjerpe, Richard
• Assistant Examiner(s): Monestime, Mackly
• Application Number:
  US09/213,331
• Time in Patent Office: 1,028 Days
• Field of Search: 712/225, 712/218, 712/204, 712/205, 712/244, 712/210
• US Class Current: 712/225
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3842 Speculative instruction execution

Abstract

In a load/store unit within a microprocessor, load and store instructions are executed out of order. The load and store instructions are assigned tags in a predetermined manner, and then assigned to load and store reorder queues for keeping track of the program order of the load and store instructions. Then when new load or store instructions are issued, the new load or store instructions are compared to entries within the load and store reorder queues to detect out of order problems.

Claims

1. A method for assigning tags to load and store instructions, comprising the steps of:

assigning first tags to each of the load and store instructions, wherein the first tags are incremented for each store instruction in program order; and

assigning second tags to each of the load and store instructions, wherein the second tags are incremented for each store instruction in program order that is preceded by a load instruction.

2. The method as recited in claim 1, wherein the second tags are not incremented for a store instruction that is preceded by a store instruction.

3. The method as recited in claim 1, wherein the second tags are incremented for each load instruction in program order that is preceded by a load instruction.

4. The method as recited in claim 1, wherein when the second tags are incremented for each store instruction in program order that is preceded by a load instruction, there is no other store instruction between the each store instruction and a preceding load instruction in program order.

5. The method as recited in claim 2, wherein when the second tags are not incremented for a store instruction that is preceded by a store instruction, there is no other store instruction between the store instruction and its preceding store instruction in program order.

6. The method as recited in claim 3, wherein when the second tags are incremented for each load instruction in program order that is preceded by a load instruction, there is no other load instruction between the each load instruction and its preceding load instruction in program order.

7. The method as recited in claim 1, wherein the load and store instructions are arranged in blocks of a plurality of such instructions, wherein a third tag is assigned to each block.

8. The method as recited in claim 1, further comprising the steps of:

storing addresses of the load instructions in a load reorder queue in an order in accordance to the assigned second tags; and

storing addresses of the store instructions in a store reorder queue in an order in accordance to the assigned first tags.

9. A method for assigning tags to load and store instructions in a load/store unit, comprising the steps of:

assigning a store tag N and a load tag M to a first store instruction;

if a next load or store instruction in program order from the first store instruction is a second store instruction, then assigning a store tag N+1 and a load tag M to the second store instruction; and

if the next load or store instruction in program order from the first store instruction is a first load instruction, then assigning a store tag N and a load tag M to the first load instruction.

10. The method as recited in claim 9, further comprising the steps of:

if a next load or store instruction in program order from the first load instruction is a third store instruction, then assigning a store tag N+1 and a load tag M+1 to the third store instruction; and

if the next load or store instruction in program order from the first store instruction is a second load instruction, then assigning a store tag N and a load tag M+1 to the second load instruction.

11. A processor comprising:

a load/store unit further comprising;

circuitry for issuing for execution load and store instructions in an out of order manner;

circuitry for assigning first tags to each of the load and store instructions, wherein the first tags are incremented for each store instruction in program order; and

circuitry for assigning second tags to each of the load and store instructions, wherein the second tags are incremented for each store instruction in program order that is preceded by a load instruction.

12. The processor as recited in claim 11, wherein the second tags arc not incremented for a store instruction that is preceded by a store instruction.

13. The processor as recited in claim 12, wherein the second tags are incremented for each load instruction in program order that is preceded by a load instruction.

14. The processor as recited in claim 13, wherein when the second tags are incremented for each store instruction in program order that is preceded by a load instruction, there is no other store instruction between the each store instruction and a preceding load instruction in program order.

15. The processor as recited in claim 14, wherein when the second tags are not incremented for a store instruction that is preceded by a store instruction, there is no second store instruction between the store instruction and its preceding store instruction in program order.

16. The processor as recited in claim 15, wherein when the second tags are incremented for each load instruction in program order that is preceded by a load instruction, there is no second load instruction between the each load instruction and its preceding load instruction in program order.

17. The processor as recited in claim 16, wherein the load and store instructions are arranged in blocks of a plurality of such instructions, wherein a third tag is assigned to each block.

18. The processor as recited in claim 11, further comprising:

a load reorder queue for storing addresses of the load instructions in an order in accordance to the assigned second tags.

19. A data processing system comprising:

a processor coupled by a bus system to a memory device, a storage device, an output device, and an input device, wherein the processor includes a plurality of execution units including a load/store unit comprising;

circuitry for assigning a store tag N and a load tag M to a first store instruction;

if a next load or store instruction in program order from the first store instruction is a second store instruction, then circuitry for assigning a store tag N+1 and a load tag M to the second store instruction; and

if the next load or store instruction in program order from the first store instruction is a first load instruction, then circuitry for assigning a store tag N and a load tag M to the first load instruction.

20. The system as recited in claim 19, further comprising:

if a next load or store instruction in program order from the first load instruction is a third store instruction, then circuitry for assigning a store tag N+1 and a load tag M+1 to the third store instruction; and

if the next load or store instruction in program order from the first store instruction is a second load instruction, then circuitry for assigning a store tag N and a load tag M+1 to the second load instruction.

21. The system as recited in claim 19, further comprising:

circuitry for executing the first load instruction;

circuitry for executing the first store instruction after the first load instruction;

a load reorder queue for detecting that the first load instruction and the first store instruction have an address byte overlap; and

circuitry for flushing the first load instruction in response to the load reorder queue detecting that the first load instruction and the first store instruction have the address byte overlap.