Input:

CS: call site affecting reaching type information in template T
v: variable for which reaching type information is changing
del_set: set of deleted reaching types immediately after CS
add_set: set of added reaching types immediately after CS
T: template associated with the method containing call site CS

Output:

Updated propagation of reaching type and call graph changes

worklist = incre_df_update(del_set, CS, T, v);

for each call site C in worklist do

y = variable storing return value of C;
for each template CT in calleesof(T, C) do

Let del_types = set of reaching types deleted at C;
Let parameter_types(CT) = set of types in type signature of CT;
if(the intersection of del_types and parameter_types != null) then
delete_edge_and_save_template(T, CT);

endfor
delete_types_after(C, y) = (union of old_gen_types(CT, y) for all CT) - (union of new_gen_types(CT, y) for all CT);
propagate_update(C, y, delete_types_after, {}, T);

endfor

worklist = incre_df_update(add_set, CS, T, v);

for each call site C in worklist do

y = variable storing return value of C;
for each template CT in calleesof(T, C) do

Let add_types = set of reaching types added at C;
Let parameter_types(CT) = set of types in type signature of CT;
if(add_types - parameter_types != null) then
temp_list = compute_new_templates(add_types - parameter_types);
analyze_and_add_new_templates(temp_list);

endfor
add_types_after(C, y) = (union of new_gen_types(CT, y) for all CT) - (union of old_gen_types(CT, y) for all CT);
propagate_update(C, y, {}, add_types_after, T);

endfor

First, the deleted types are processed. An intraprocedural incremental data flow update is performed in T based on the set of deleted reaching types at CS. This analysis returns a worklist containing all call sites in T influenced by the deleted reaching types at CS.

Each call site C in this worklist is analyzed. If the set of deleted reaching types at C has any elements in common with the parameter types of a callee template CT of C, the edge from caller to callee templates (T to CT) is deleted. After each CT is analyzed for the call site C, the impact of the changed return types at C is collected in delete_types_after. Propagate_Update is called recursively to propagate those changes to the remaining call sites.

In the second phase of the algorithm, a worklist for added reaching type information is created through a separate incremental data flow update in T. Processing is similar to that of the delete stage, but new templates and edges are added as updated reaching type information is determined at a call site C. The subfunction analyze_and_add_new_templates performs an abbreviated version of the exhaustive algorithm for creating a template call graph, starting at the new template and reusing existing templates. Changes in return type information from added templates are propagated by recursive calls to Propagate_Update.