Deferring and combining write barriers for a garbage-collected heap

• US 7,404,182 B1
• Filed: 10/03/2003
• Issued: 07/22/2008
• Est. Priority Date: 10/03/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T., Heller, Steven K.
• Primary Examiner(s): Zhen; Wei Y.
• Assistant Examiner(s): DENG, ANNA CHEN
• Application Number:
  US10/679,183
• Time in Patent Office: 1,754 Days
• Field of Search: 717140-141, 707205-206, 707103 R-103 Z, 718/104, 711/6
• US Class Current: 717/140
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

The present invention provides a technique for reducing the number of write barriers without compromising garbage collector performance or correctness. To that end, a compiler defers emitting write barriers until it reaches a subsequent instruction in the mutator code. At this point, the compiler may elide repeated or unnecessary write-barrier code so as to emit only those write barriers that provide useful information to the garbage collector. By eliminating write-barrier code in this manner, the amount of write-barrier overhead in the mutator can be minimized, consequently enabling the mutator to execute faster and more efficiently. Further, collocating write barriers after the predetermined instruction also enables the compiler to generate object code having better cache performance and more efficient use of guard code than is possible using conventional write-barrier implementations.

Claims

1. For employing a computer system to compile source code that specifies operation of a mutator, which includes at least one reference-modifying instruction, 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, a method comprising:

(A) deferring emission of write-barrier code corresponding to at least one reference-modifying instruction in the mutator by recording in a list a separate entry for each reference-modifying instruction whose write barrier emission has been deferred, wherein each list entry stores at least enough information to enable a write barrier to be generated for the entry'"'"'s corresponding reference-modifying instruction;

(B) combining or eliding one or more entries in the list if the one or more entries satisfy any elision criterion in a set of at least one elision criterion, each criterion being satisfied if the one or more entries correspond to reference-modifying instructions whose deferred write barriers, if executed, would provide unnecessary or redundant information to the garbage collector; and

(C) emitting, at a predetermined point in the mutator, at least one deferred write barrier corresponding to a list entry that was not combined or elided.

2. The method according to claim 1, wherein each elision criterion in said set of at least one elision criterion determines whether two or more deferred write barriers, if executed, would provide unnecessary or redundant information to a garbage collector.

3. The method according to claim 2, wherein one criterion in said set of at least one elision criterion determines whether the two or more deferred write barriers correspond to reference-modifying instructions that modify the same memory location.

4. The method according to claim 2, wherein one criterion in said set of at least one elision criterion determines whether the two or more deferred write barriers correspond to reference-modifying instructions that modify reference values located in the same object or card.

5. The method according to claim 2, wherein one criterion in said set of at least one elision criterion determines whether the two or more deferred write barriers correspond to reference-modifying instructions that modify reference values located within a known range of memory addresses.

6. The method according to claim 1, wherein the remaining deferred write barriers are emitted at successive locations in the mutator.

7. The method according to claim 1, further comprising:

emitting a guard-code instruction preceding the emission of one or more of the deferred write barriers, wherein the guard-code instruction, when executed, determines whether the one or more deferred write barriers following the guard-code instruction will be executed.

8. The method according to claim 1, wherein the predetermined point in the mutator is located after the last instruction in the mutator.

9. The method according to claim 1, wherein at least one of the deferred write barriers is deferred across a call instruction in the mutator.

10. The method according to claim 1, wherein at least one of the deferred write barriers is deferred from a first basic block to a second basic block in an extended basic block.

11. The method according to claim 1, further comprising:

emitting one or more of the deferred write barriers before the predetermined point in the mutator if a spilling instruction is about to be emitted in the mutator that will spill a register'"'"'s contents to a stack frame and the spilled register stores a value corresponding to a memory location that is not modified by reference-modifying mutator instructions located subsequent to the spilling instruction.

12. The method according to claim 1, further comprising:

recording in a list a separate entry for each reference-modifying instruction whose write barrier emission has been deferred, wherein each list entry stores at least enough information to enable a write barrier to be generated for the entry'"'"'s corresponding reference-modifying instruction.

13. The method according to claim 12, wherein each list entry stores at least a value number indicating a memory location of a reference value that is modified by the entry'"'"'s corresponding reference-modifying instruction.

14. The method according to claim 13, wherein the value number corresponds to the memory location of an object.

15. The method according to claim 13, wherein the value number corresponds to the memory location of an array.

16. The method according to claim 1, wherein at least one reference-modifying instruction in the mutator modifies a reference value stored in a super object.

17. For employing a computer system to compile source code that specifies operation of a mutator, which includes at least one reference-modifying instruction, 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, a method comprising:

(A) suspending execution of the mutator at a possible safe point in the mutator;

(B) locating, while the mutator is suspended, a list containing a separate entry for each reference-modifying instruction in the mutator that was executed without corresponding write-barrier code before the mutator was suspended, each list entry containing enough information to inform the garbage collector of the same information that the garbage collector would have received if a write barrier had been executed for the entry'"'"'s corresponding reference-modifying instruction;

(C) combining or eliding, while the mutator is suspended, one or more entries in the list if the one or more entries satisfy any elision criterion in a set of at least one elision criterion, each criterion being satisfied if the one or more list entries correspond to reference-modifying instructions whose deferred write barriers, if executed, would provide unnecessary or redundant information to the garbage collector; and

(D) performing garbage-collection operations based on the contents of the remaining list entries that are not combined or elided.

18. The method according to claim 17, wherein one criterion in said set of at least one elision criterion tests whether two or more entries in the list are identical.

19. The method according to claim 17, wherein one criterion in said set of at least one elision criterion tests whether two or more entries in the list correspond to reference-modifying instructions that modify reference values located in the same object or card.

20. The method according to claim 17, wherein one criterion in said set of at least one elision criterion tests whether two or more entries in the list correspond to reference-modifying instructions that modify reference values located within a known range of memory addresses.

21. The method according to claim 17, wherein each possible safe point in the mutator is associated with a list containing a separate entry for each reference-modifying instruction in the mutator that was executed without corresponding write-barrier code before the mutator'"'"'s execution reaches the possible safe point.

22. The method according to claim 21, wherein two or more possible safe points in the mutator are associated with the same list.

23. The method according to claim 21, wherein each list associated with a possible safe point is generated by a compiler at compile time.

24. The method according to claim 17, wherein the garbage collector accesses the list through a pointer located in a frame of a call stack associated with the mutator.

25. The method according to claim 24, wherein a trampoline code sets a value in a boundary frame of the call stack to notify the garbage collector of a set of lists to scan for deferred write barriers during a collection interval.

26. A computer system for reducing the amount of write-barrier code emitted in a mutator containing at least one reference-modifying instruction, the computer system comprising:

a processor; and

a computer-readable memory, to which the processor is responsive, that stores instructions executable by the processor for;

(A) deferring emission of write-barrier code corresponding to at least one reference-modifying instruction in the mutator by recording in a list a separate entry for each reference-modifying instruction whose write barrier emission has been deferred, wherein each list entry stores at least enough information to enable a write barrier to be generated for the entry'"'"'s corresponding reference-modifying instruction;

(B) combining or eliding one or more entries in the list if the one or more entries satisfy any elision criterion in a set of at least one elision criterion, each criterion being satisfied if the one or more entries correspond to reference-modifying instructions whose deferred write barriers, if executed, would provide unnecessary or redundant information to the garbage collector; and

(C) emitting, at a predetermined point in the mutator, at least one deferred write barrier corresponding to a list entry that was not combined or elided.

27. The computer system according to claim 26, wherein each elision criterion in said set of at least one elision criterion determines whether two or more deferred write barriers, if executed, would provide unnecessary or redundant information to a garbage collector.

28. The computer system according to claim 27, wherein one criterion in said set of at least one elision criterion determines whether the two or more deferred write barriers correspond to reference-modifying instructions that modify the same memory location.

29. The computer system according to claim 27, wherein one criterion in said set of at least one elision criterion determines whether the two or more deferred write barriers correspond to reference-modifying instructions that modify reference values located in the same object or card.

30. The computer system according to claim 27, wherein one criterion in said set of at least one elision criterion determines whether the two or more deferred write barriers correspond to reference-modifying instructions that modify reference values located within a known range of memory addresses.

31. A computer system to compile source code that specifies operation of a mutator, which includes at least one reference-modifying instruction, 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, the computer system comprising:

a processor; and

a computer-readable memory, to which the processor is responsive, that stores instructions executable by the processor for;

suspending execution of the mutator at a possible safe point in the mutator;

locating a list, while the mutator is suspended, containing a separate entry for each reference-modifying instruction in the mutator that was executed without corresponding write-barrier code before the mutator was suspended, each list entry containing enough information to inform the garbage collector of the same information that the garbage collector would have received if a write barrier had been executed for the entry'"'"'s corresponding reference modifying instruction;

combining or eliding, while the mutator is suspended, one or more entries in the list if the one or more entries satisfy any elision criterion in a set of at least one elision criterion, each criterion being satisfied if the one or more list entries correspond to reference-modifying instructions whose deferred write barriers, if executed, would provide unnecessary or redundant information to the garbage collector; and

performing garbage-collection operations based on the contents of the remaining list entries that are not combined or elided.

32. The computer system according to claim 31, wherein one criterion in said set of at least one elision criterion tests whether two or more entries in the list are identical.

33. The computer system according to claim 31, wherein one criterion in said set of at least one elision criterion tests whether two or more entries in the list correspond to reference-modifying instructions that modify reference values located in the same object or card.

34. The computer system according to claim 31, wherein one criterion in said set of at least one elision criterion tests whether two or more entries in the list correspond to reference-modifying instructions that modify reference values located within a known range of memory addresses.

35. A computer readable medium comprising program instructions stored therein for execution on a processor for the practice of a method for reducing the amount of write-barrier code emitted in a mutator containing at least one reference-modifying instruction, the method comprising:

(A) deferring emission of write-barrier code corresponding to at least one reference-modifying instruction in the mutator by recording in a list a separate entry for each reference-modifying instruction whose write barrier emission has been deferred, wherein each list entry stores at least enough information to enable a write barrier to be generated for the entry'"'"'s corresponding reference-modifying instruction;

(B) combining or eliding one or more entries in the list if the one or more entries satisfy any elision criterion in a set of at least one elision criterion, each criterion being satisfied if the one or more entries correspond to reference-modifying instructions whose deferred write barriers, if executed, would provide unnecessary or redundant information to the garbage collector; and

(C) emitting, at a predetermined point in the mutator, at least one deferred write barrier corresponding to a list entry that was not combined or elided.

36. A computer readable medium comprising program instructions stored therein for execution on a processor for the practice of a method for employing a computer system to compile source code that specifies operation of a mutator, which includes at least one reference-modifying instruction, 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, the method comprising:

(A) suspending execution of the mutator at a possible safe point in the mutator;

(B) locating, while the mutator is suspended, a list containing a separate entry for each reference-modifying instruction in the imitator that was executed without corresponding write-barrier code before the mutator was suspended, each list entry containing enough information to inform the garbage collector of the same information that the garbage collector would have received if a write barrier had been executed for the entry'"'"'s corresponding reference-modifying instruction;

(C) combining or eliding, while the mutator is suspended, one or more entries in the list if the one or more entries satisfy any elision criterion in a set of at least one elision criterion, each criterion being satisfied if the one or more list entries correspond to reference-modifying instructions whose deferred write barriers, if executed, would provide unnecessary or redundant information to the garbage collector; and

(D) performing garbage-collection operations based on the contents of the remaining list entries that are not combined or elided.