Patent ID: 8103706

Claim:
A method for modifying a program to employ reference-counting garbage collection, the method comprising: generating one or more sets of overlooking roots for one or more respective points in the program, wherein generating one or more sets of overlooking roots comprises (a) and (b): (a) computing tie functions for procedures in the program, a tie function is a function which, for two roots, gives a set of fields and array types that tie the roots together; and (b) updating the tie functions, the updating comprising including additional fields or array types that tie the two roots together, the tie functions being updated for relevant statements in the program based on a categorization of the relevant statements, at least one of the relevant statement being categorized into at least one of the following categories: allocations and heap stores; and introducing reference-counting updates into the program based at least in part using the one or more sets of overlooking roots; wherein generating one or more sets of overlooking roots comprises performing the fixed-point computation to arrive at a stable set of overlooking roots; and wherein performing the fixed-point computation comprises (i)-(v): (i) computing a killed overlooking roots set consulting an incoming overlooking roots set and a tie function; (ii) computing a generated overlooking roots set from a modified version of the incoming overlooking roots set; (iii) weakly updating the tie function for a procedure; (iv) computing a meet operation at confluence points; and (v) repeating (i)-(iv) until a stable set of overlooking roots is calculated.