Elision of write barriers for stores whose values are in close proximity

• US 20040186863A1
• Filed: 03/21/2003
• Published: 09/23/2004
• Est. Priority Date: 03/21/2003
• Status: Abandoned Application

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Application Number:
  US10/394,813
• Publication Number:
  US 20040186863A1
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 12/0276 Generational garbage collection

Abstract

The present invention provides a technique for reducing the number of write barriers executed in mutator code without compromising garbage collector performance or correctness. Since garbage collectors typically scan a heap (or a portion of a heap) for reachable objects during their collection intervals, most collectors do not need to be notified of reference-writing instructions unless the instructions add new reachable objects to the heap. According to the illustrative embodiment, certain compile-time tests can be performed that, if passed, guarantee that the reference modification in question will make no otherwise unreachable object reachable. One or more of these tests is performed and no write barrier is emitted by the compiler for a given reference-writing instruction if the instruction passes such a test. For example, a compiler does not emit write-barrier code corresponding to mutator instructions that write a self-reference into an object reference field or copy a reference value from one object reference field to another located in the same object or card. By excluding such unnecessary write barrier overhead, the mutator may execute faster and more efficiently.

Claims

1. For employing a computer to compile source code that specifies operation of a mutator that includes at least one reference-writing instruction into object code for execution by a computer system, which includes memory, together with a garbage collector that relies on the mutator'"'"'s execution of write-barrier code to keep track of at least some reference modifications and operates in collection increments, in each of at least some of which it collects a respective collection set by reclaiming a portion of the memory that it determines to be occupied by objects that are no longer reachable, a method comprising:

(A) analyzing the source code to make a determination, for one of said at least one reference-writing instruction, whether that reference-writing instruction satisfies any elision criterion in a set of at least one elision criterion, where each criterion in said set of at least one elision criterion is satisfied only if execution of that reference-writing instruction will result in a heap state in which scanning the reference modified by that reference-writing instruction during any collection set'"'"'s collection will not affect the garbage collector'"'"'s ultimate determination of whether an object in that collection set is reachable; and

(B) generating object code that;

(i) directs the computer system to operate as the mutator;

(ii) includes that reference-writing instruction;

(iii) if said determination is negative, accompanies that reference-writing instruction with a write barrier that alerts the garbage collector to execution of the reference-writing instruction; and

(iv) if the result of said determination is affirmative, omits such a write barrier.

2. The method according to claim 1, wherein one criterion in said set of at least one elision criterion tests whether execution of said reference-writing instruction stores a self-reference in an object reference field.

3. The method according to claim 1, wherein at least one criterion in said set of at least one elision criterion depends on the garbage collector'"'"'s region of summarization.

4. The method according to claim 3, wherein when the garbage collector'"'"'s region of summarization is defined in accordance with an imprecise card-marking scheme, an elision criterion in said set of at least one elision criterion tests whether execution of said reference-writing instruction stores a source value located in an object into a destination address located in the same object.

5. The method according to claim 3, wherein when the garbage collector'"'"'s region of summarization is defined in accordance with a precise card-marking scheme, an elision criterion in said set of at least one elision criterion tests whether execution of said reference-writing instruction stores a source value located in a card into a destination address located in the same card.

6. The method according to claim 5, wherein analyzing the source code to make said determination includes:

determining whether said source value and said destination address are located in the same object; and

determining a byte-alignment in the memory of said destination address and an object reference field storing said source value.

7. The method according to claim 4, wherein analyzing the source code to make said determination includes:

generating a table having one or more entries that map a memory location associated with an object or variable to a value number.

8. The method according to claim 5, wherein analyzing the source code to make said determination further includes:

generating a table having one or more entries that map a memory location associated with an object or variable to a value number; and

generating a table having one or more entries that map a value number to (i) a memory location or value number associated with an object and (ii) a relative offset within the object.