Reference-counting subsumption analysis

• US 20070226281A1
• Filed: 02/10/2006
• Published: 09/27/2007
• Est. Priority Date: 02/10/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Joisha, Pramod
• Granted Patent: US 7,565,386 B2
• Time in Patent Office: Days
• 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.

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 a first and second reference;

determining if every live range of the first reference is contained in a live range of the second reference;

determining if the first reference is never live through a redefinition of either the first or the second reference; and

determining if a set of objects reachable from the first reference is a subset of a set of objects reachable from the second reference.

4. The method of claim 1, wherein determining references which are subsumed by other references in the program comprises generating one or more reference-counting subsumption graphs for the program;

and

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

5. The method of claim 4, wherein generating one or more reference-counting subsumption graphs comprises generating a reference-counting subsumption graph for each of one or more functions in the program.

6. The method of claim 5, wherein generating the reference-counting subsumption graph for a function comprises:

building a live-range subsumption graph for the function;

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

building the reference-counting subsumption graph for the function.

7. The method of claim 6, 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.

8. The method of claim 6, 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.

9. The method of claim 6, 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.

10. The method of claim 9, 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.

11. The method of claim 10, 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.

12. The method of claim 11, 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.

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

a reference-counting subsumption analysis module which is 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.

14. The computer-executable program analysis system of claim 13, wherein the subsumption analyses module comprises:

a live-range subsumption graph module, configured to generate one or more live-range subsumption graphs from the control-flow graph;

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; and

a reference-counting subsumption graph module, configured to generate one or more reference-counting subsumption graphs from the one or more uncut live-range subsumption graphs.

15. The computer-executable program analysis system of claim 14, wherein:

the 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;

the 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

the 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.

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

17. One or more computer-readable 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.

18. The computer-readable media of claim 17 wherein determining subsumed references comprises:

determining three conditions for a first reference and a second reference, the conditions comprising;

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

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

whether a set of objects reachable from the first reference is a subset of a set of objects reachable from the second reference; and

if the conditions are met, considering the first reference to be subsumed by the second reference.

19. The computer-readable media of claim 18 wherein determining three conditions for the first reference and the second reference comprises:

generating a reference-counting subsumption graph; and

using information represented in the reference-counting subsumption graph for the first and second references to identify whether reference-counting updates to the first reference are unnecessary.

20. The computer-readable media of claim 19, 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.