Reference-counting subsumption analysis

• US 7,565,386 B2
• Filed: 02/10/2006
• Issued: 07/21/2009
• Est. Priority Date: 02/10/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Joisha, Pramod Gundimajalu
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Morrison; Jay A
• Application Number:
  US11/351,642
• Publication Number:
  US 20070226281A1
• Time in Patent Office: 1,257 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0261 using reference counting
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

An eager reference-counting garbage collection system performs a static analysis on the intermediate representation of a program. The system then uses liveness information to inject eager reference-counting updates into the program. Through the use of the liveness information, reference-counting decrements can be made earlier in execution than in traditional reference-counting schemes, freeing up memory more efficiently. Additionally, a reference-counting subsumption optimization tool identifies redundant reference-counting updates and removes them, lowering the number of garbage collection update calls and improving execution throughput. Reference-counting subsumption can also be used as a throughput enhancer in traditional reference-counting schemes that maintain up-to-date tallies of references from the stack.

Claims

1. A method of lowering a number of reference-counting updates in a program utilizing reference-counting garbage collection, the method comprising:

determining subsumed references which are subsumed by subsuming references in the program; and

removing reference-counting updates on the subsumed references;

wherein a first reference is considered to be subsumed by a second reference when the first and second references satisfy the following conditions;

1) every live range of the first reference is contained in a live range of the second reference;

2) the first reference is never live through a redefinition of either the first or the second reference; and

3) a set of every object which is reachable from the first reference is a subset of a set of every object which is reachable from the second reference;

wherein determining references which are subsumed by other references in the program comprises;

generating a reference-counting subsumption graph for each of one or more functions in the program by;

(a) building a live-range subsumption graph for the function;

(b) building an uncut live-range subsumption graph for the function; and

(c) building the reference-counting subsumption graph for the function; and

analyzing the reference-counting subsumption graph to determine which references are represented in the graph as being subsumed by other references.

2. The method of claim 1, further comprising performing a static analysis on references in the program to obtain reference information;

and

wherein the subsumed references are determined based at least in part on the reference information.

3. The method of claim 1, wherein determining subsumed references which are subsumed by subsuming references comprises for pairs of references in the program, determining if the three conditions are satisfied.

4. The method of claim 1, wherein building the live-range subsumption graph for the function comprises:

creating a first graph with vertices representing references in the function;

for a first reference and a second reference out of the references represented in the graph, adding an edge from a vertex representing the first reference to a vertex representing the second reference if, at a program point in the function, the first reference is live and the second reference is dead; and

generating a complement graph from the first graph as the live-range subsumption graph.

5. The method of claim 1, wherein building the uncut live-range subsumption graph comprises, for a first reference and a second reference, deleting an edge from the live-range subsumption graph between vertices who represent the first and second references if the first reference is live through a redefinition of either the first or second reference.

6. The method of claim 1, wherein building the reference-counting subsumption graph comprises deleting edges from the uncut live-range subsumption graph between vertices which represent first and second references such that a maximal set of objects reachable by the first reference is not a subset of a maximal set of objects reachable by the second reference.

7. The method of claim 6, wherein deleting edges from the uncut live-range subsumption graph comprises:

approximating one or more overlooking roots'"'"' sets for statements and references in the function;

analyzing the approximated overlooking roots'"'"' sets to determine edges to delete; and

deleting the determined edges.

8. The method of claim 7, wherein approximating one or more overlooking roots'"'"' sets comprises adding references to an overlooking roots'"'"' set based at least in part on constraints on usage of references.

9. The method of claim 8, wherein adding references to the overlooking roots'"'"' set comprises, for a statement of type u:

=v.g, where g is a read-only field and u is live leaving the statement, adding v to the overlooking roots'"'"' set which corresponds to u and the statement.

10. A computer-implemented program analysis system for determining redundant reference-counting updates in a program, the system comprising:

one or more computer processors; and

a reference-counting subsumption analysis module operable to execute on the one or more computer processors, the module configured to accept a control-flow graph for a program and produce one or more reference-counting subsumption graphs which indicate references in the control-flow graph that are subsumed by other references;

wherein the reference-counting subsumption analysis module comprises;

a live-range subsumption graph module configured to generate one or more live-range subsumption graphs from the control flow graph, wherein each live-range subsumption graph indicates a relation between a first and a second reference if every live range of the first reference is contained in a live range of the second reference;

an uncut live-range subsumption graph module, configured to generate one or more uncut live-range subsumption graphs from the one or more live-range subsumption graphs, wherein each uncut live-range subsumption graph indicates a relation between a third and a fourth reference if the third reference is never live through a redefinition of either the third or the fourth reference; and

a reference-counting subsumption graph module, configured to generate one or more reference-counting subsumption graph from the one or more uncut live-range subsumption graphs, wherein each reference-counting subsumption graph indicates a relation between a fifth and a sixth reference if a set of objects reachable from the fifth reference is always a subset of a set of objects reachable from the sixth reference.

11. The computer-implemented program analysis system of claim 10, wherein the reference-counting subsumption graph module is configured to generate the one or more reference-counting subsumption graphs at least in part by utilizing approximated overlooking roots'"'"' sets.

12. One or more storage media comprising computer-executable instructions for performing a method for identifying unnecessary reference-counting updates in a function contained in a program that uses reference-counting garbage collection, the method comprising:

determining references which are subsumed in the function; and

removing reference-counting updates for the subsumed references from the function;

wherein a first reference is considered to be subsumed by a second reference when the first and second references satisfy the following conditions;

1) every live range of the first reference is contained in a live range of the second reference;

2) the first reference is never live through a redefinition of either the first or the second reference; and

3) a set of every object which is reachable from the first reference is a subset of a set of every object which is reachable from the second reference;

wherein determining subsumed references comprises;

determining the three conditions for a third reference and a fourth reference in the function by;

(a) generating a reference-counting subsumption graph; and

(b) using information represented in the reference-counting subsumption graph for the third and fourth references to identify whether reference-counting updates to the a reference out of the third and fourth references are unnecessary; and

if the conditions are met, considering the third reference to be subsumed by the fourth reference.

13. The storage media of claim 12, wherein the method further comprises performing static analysis on the function in order to determine liveness information and overlooking roots'"'"' sets and the reference-counting subsumption graph is generated at least in part based on the liveness information and the overlooking roots'"'"' sets.