Deferring and combining write barriers for a garbage-collected heap
First Claim
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 Assignments
0 Petitions
Accused Products
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.
143 Citations
36 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25)
-
-
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. - View Dependent Claims (27, 28, 29, 30)
-
-
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. - View Dependent Claims (32, 33, 34)
-
-
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.
-
Specification