×

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
First Claim
Patent Images

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.

View all claims
  • 2 Assignments
Timeline View
Assignment View
    ×
    ×