Patent ID: 7565386

Claim:
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.