Detecting raw hazards in an object-addressed memory hierarchy by comparing an object identifier and offset for a load instruction to object identifiers and offsets in a store queue

• US 7,600,097 B1
• Filed: 09/05/2006
• Issued: 10/06/2009
• Est. Priority Date: 09/05/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wright, Gregory M.
• Primary Examiner(s): Huisman; David J
• Application Number:
  US11/516,320
• Time in Patent Office: 1,127 Days
• Field of Search: 712/216, 712/217, 712/218, 712/219, 712/225
• US Class Current: 712/216
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/30167 of immediate specifier, e.g. constants
• CPC Class Codes: G06F 9/35 Indirect addressing
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding

Abstract

One embodiment of the present invention provides a system that processes memory-access instructions in an object-addressed memory hierarchy. During operation, the system receives a load instruction to be executed, wherein the load instruction loads a data item from an object, and wherein the load instruction specifies an object identifier (OID) for the object and an offset for the data item within the object. Next, the system compares the OID and the offset for the data item against OIDs and offsets for outstanding store instructions in a store queue. If the offset for the data item does not match any of the offsets for the outstanding store instructions in the store queue, and hence no read-after-write (RAW) hazard exists, the system performs a cache access to retrieve the data item for the load instruction.

Claims

1. A method for processing memory-access instructions in an object-addressed memory hierarchy, comprising:

receiving at least one store instruction to be executed, wherein the store instruction specifies an object identifier (OID) and an offset;

creating an entry in a store queue for the store instruction, wherein the entry includes a valid flag for the offset and a separate valid flag for the OID;

when the offset for the store instruction becomes available, storing the offset into the entry and setting the valid flag for the offset;

when the OID for the store instruction becomes available, storing the OID for the store instruction into the entry and setting the valid flag for the OID; and

when a data value for the store instruction becomes available, storing the data value into a data field of the entry;

receiving a load instruction to be executed, wherein the load instruction loads a data item from an object, and wherein the load instruction specifies an OID for the object and an offset for the data item within the object;

comparing the OID and the offset for the load instruction against OIDs and offsets for outstanding store instructions in the store queue; and

if the offset for the load instruction does not match any of the offsets for the outstanding store instructions in the store queue, and hence no read-after-write (RAW) hazard exists, performing a cache access to retrieve the data item for the load instruction.

2. The method of claim 1, wherein if the OID for the load instruction does not match any of the OIDs for outstanding store instructions in the store queue, and hence no RAW hazard exists, the method further comprises performing a cache access to retrieve the data item for the load instruction.

3. The method of claim 1, wherein if the offset for the load instruction matches offsets for one of more of the outstanding store instructions, the method further comprises:

waiting until the OID for the load instruction is compared against the OIDs for the outstanding store instructions; and

if the OID for the load instruction does not match the OIDs for the one or more outstanding store instructions with matching offsets, and hence no RAW hazard exists, performing a cache access to retrieve the data item for the load instruction.

4. The method of claim 1, wherein if both the OID and the offset for the load instruction match an OID and an offset for an outstanding store instruction, and hence a RAW hazard exists, the method further comprises avoiding the RAW hazard by retrieving the data item from an entry in the store queue for the outstanding store instruction, instead of retrieving the data item from a cache memory.

5. The method of claim 1, wherein the OID for the store instruction is contained in a register which is indexed by the store instruction, and hence the OID for the store instruction must first be retrieved from the register before the OID for the store instruction can be stored into the entry.

6. The method of claim 1, wherein the OID for the load instruction is contained in a register which is indexed by the load instruction, and hence the OID for the load instruction must first be retrieved from the register before the OID for the load instruction can be compared against OIDs for outstanding store instructions in the store queue.

7. An apparatus that efficiently processes memory-access instructions in an object-addressed memory hierarchy, comprising:

an instruction-processing mechanism configured to receive a load instruction to be executed, wherein the load instruction loads a data item from an object, and wherein the load instruction specifies an object identifier (OID) for the object and an offset for the data item within the object;

wherein the instruction-processing mechanism is further configured to receive at least one store instruction to be executed, wherein the store instruction specifies an OID and an offset, and wherein the instruction-processing mechanism is further configured to;

create an entry in a store queue for the store instruction, wherein the entry includes a valid flag for the offset for the store instruction and a separate valid flag for the OID for the store instruction;

when the offset for the store instruction becomes available, store the offset for the store instruction into the entry and set the valid flag for the offset for the store instruction;

when the OID for the store instruction becomes available, store the OID for the store instruction into the entry and set the valid flag for the OID for the store instruction; and

when a data value for the store instruction becomes available, store the data value into a data field of the entry;

a comparison mechanism configured to compare the OID and the offset for the load instruction against OIDs and offsets for outstanding store instructions in the store queue; and

wherein if the offset for the load instruction does not match any of the offsets for the outstanding store instructions in the store queue, and hence no RAW hazard exists, the instruction-processing mechanism is configured to perform a cache access to retrieve the data item for the load instruction.

8. The apparatus of claim 7, wherein if the OID for the load instruction does not match any of the OIDs for outstanding store instructions in the store queue, and hence no RAW hazard exists, the instruction-processing mechanism is configured to perform a cache access to retrieve the data item for the load instruction.

9. The apparatus of claim 7, wherein if the offset for the load instruction matches offsets for one of more of the outstanding store instructions, the instruction-processing mechanism is configured to:

wait until the OID for the load instruction is compared against the OIDs for the outstanding store instructions; and

if the OID for the load instruction does not match the OIDs for the one or more outstanding store instructions with matching offsets, and hence no RAW hazard exists, perform a cache access to retrieve the data item for the load instruction.

10. The apparatus of claim 7, wherein if both the OID and the offset for the load instruction match an OID and an offset for an outstanding store instruction, and hence a RAW hazard exists, the instruction-processing mechanism is configured to avoid the RAW hazard by retrieving the data item from an entry in the store queue for the outstanding store instruction, instead of retrieving the data item from a cache memory.

11. The apparatus of claim 7, wherein the OID for the store instruction is contained in a register which is indexed by the store instruction, and hence the OID for the store instruction must first be retrieved from the register before the OID for the store instruction can be stored into the entry.

12. The apparatus of claim 7, wherein the OID for the load instruction is contained in a register which is indexed by the load instruction, and hence the OID for the load instruction must first be retrieved from the register before the OID for the load instruction can be compared against OIDs for outstanding store instructions in the store queue.

13. A computer system which is configured to efficiently processes memory-access instructions in an object-addressed memory hierarchy, comprising:

a processor;

a memory;

an instruction-processing mechanism within the processor configured to receive a load instruction to be executed, wherein the load instruction loads a data item from an object, and wherein the load instruction specifies an object identifier (OID) for the object and an offset for the data item within the object;

wherein the instruction-processing mechanism is further configured to receive at least one store instruction to be executed, wherein the store instruction specifies an OID and an offset, and wherein the instruction-processing mechanism is further configured to;

create an entry in a store queue for the store instruction, wherein the entry includes a valid flag for the offset for the store instruction and a separate valid flag for the OID for the store instruction;

when the offset for the store instruction becomes available, store the offset into the entry and set the valid flag for the offset for the store instruction;

when the OID for the store instruction becomes available, store the OID for the store instruction into the entry and set the valid flag for the OID for the store instruction; and

when a data value for the store instruction becomes available, store the data value into a data field of the entry;

a comparison mechanism within the processor configured to compare the OID and the offset for the load instruction against OIDs and offsets for outstanding store instructions in the store queue; and

wherein if the offset for the load instruction does not match any of the offsets for the outstanding store instructions in the store queue, and hence no RAW hazard exists, the instruction-processing mechanism is configured to perform a cache access to retrieve the data item for the load instruction.

14. The computer system of claim 13, wherein if the OID for the load instruction does not match any of the OIDs for outstanding store instructions in the store queue, and hence no RAW hazard exists, the instruction-processing mechanism is configured to perform a cache access to retrieve the data item for the load instruction.

15. The computer system of claim 13, wherein if the offset for the load instruction matches offsets for one of more of the outstanding store instructions, the instruction-processing mechanism is configured to:

wait until the OID for the load instruction is compared against the OIDs for the outstanding store instructions; and

if the OID for the load instruction does not match the OIDs for the one or more outstanding store instructions with matching offsets, and hence no RAW hazard exists, perform a cache access to retrieve the data item for the load instruction.

16. The computer system of claim 13, wherein if both the OID and the offset for the load instruction match an OID and an offset for an outstanding store instruction, and hence a RAW hazard exists, the instruction-processing mechanism is configured to avoid the RAW hazard by retrieving the data item from an entry in the store queue for the outstanding store instruction, instead of retrieving the data item from a cache memory.