|
![](deleteCallSite.gif)
Home |
DMP |
Project |
Journal |
Contact
Relevant Java Classes |
Delete Call Site |
Template Call Graph |
Research |
Final Report
Propagate/Update
ALGORITHM Delete_Call_Site(G, M, CS)
- Input:
- G: template call graph
M: method being edited
CS: call site x = q.m(...) being deleted
- Output:
- Updated template call graph G'
- for each template node T of method M do
- for each template C in calleesof(T, CS) do
delete_edge_and_save_template(T, C);
delete_types_after(CS, x) = union of gen_types(C, x) for all C;
add_types_after(CS, x) = union of reaching_types_out(p, x) for all p in pred(CS), for all C;
propagate_update(CS, x, delete_types_after, add_types_after, T);
Let del_types(T) = set of deleted reaching types at return from T;
Let add_types(T) = set of added reaching types at return from T;
- end for
- for each template CT in caller(M) do
- for each C in callsite(CT) to callee M do
Let y = variable storing return value at C;
delete_types_after(C, y) = union of del_types(T) for all templates T of M;
add_types_after(C, y) = union of add_types(T) for all templates T of M;
propagate_update(C, y, delete_types_after, add_types_after, CT);
end for
- end for
Temporary Variables
First Outer For Loop (to callees)
- T - template node of modified method M
- C - template in calleesof(T, CS)
- delete_types_after - set of reaching types generated by CS
- add_types_after - set of reaching types that now reach past the deleted call site CS
- del_types - set of deleted reaching types at return from a template T associated with the modified method M
- add_types - set of added reaching types at return from T
Second Outer For Loop (to callers)
- CT - template in caller(M)
- C - call site in the caller CT that calls M
- y - variable storing return value at call site C
- delete_types_after - union of deleted reaching types (del_types(T)) at return from each template T of M
- add_types_after - union of added reaching types (add_types(T)) at return from each template T of M
- T - template node of M (same T as above)
Secondary Functions
delete_edge_and_save_template(template, call site)
propagate_update(call site, return variable, set, set, template) - algorithm already proposed
English Walkthrough
- Delete all edges in the template call graph G that correspond to the deleted call site CS and save the template and corresponding subgraph associated with each deleted edge. There will be a set of edges, as multiple templates could be mapped to the single modified method M, and polymorphic call sites have a set of bound receiver objects (q), each with its own relevant method (m1, m2, ... , mn).
for each template node T of method M do
for each template C in calleesof(T, CS) do
delete_edge_and_save_template(T, C);
- Update the type information propagated from the modified method M - through the actual parameters - to the potential callees at CS (m1, ..., mn). Type information reaching each mi from other callers is examined and the call subgraph of each mi is updated to reflect the new reaching type information.
for each template node T of method M do
for each template C in calleesof(T, CS) do
delete_edge_and_save_template(T, C);
- The new set of types bound to the return variable x from the set of all callees m1, ..., mn is used to compute changes in the reaching types of x immediately after CS in M. In other words, the set of types bound to x at CS must be computed in order to update subsequent call sites reached by the return variable types. Both killed and newly reaching types are considered. delete_types_after is the set of types generated by CS - the set of return types from each mi - while add_types_after is the set of types that now reach past the deleted call site.
delete_types_after(CS, x) = union of gen_types(C, x) for all C;
add_types_after(CS, x) = union of reaching_types_out(p, x) for all p in pred(CS), for all C;
- The type information propagating to any potential subsequent callees in the modified method M and to those callees' subgraphs must be updated. The Propagate_Update algorithm performs this function. It has input 5 parameters:
- CS: the call site affecting reaching type information in template T
- v: the variable for which reaching type information is changing
- del_set: the set of deleted reaching types immediately after CS
- add_set: the set of added reaching types immediately after CS
- T: the template associated with the method containing call site CS
propagate_update(CS, x, delete_types_after, add_types_after, T);
- The sets of deleted and added types reaching the return of each template T associated with the modified method M are computed. The return type set of M is updated (if necessary) to correspond to the updated types associated with the deleted call site.
Let del_types(T) = set of deleted reaching types at return from T;
Let add_types(T) = set of added reaching types at return from T;
- The callers of M (and their subsequent callees and callers) must be updated to reflect changes in the return type information - sets of added and deleted reaching types - propagating back to each caller.
First, all callers of the modified method M must be located. For every call site C in a caller that calls M, the types that must be deleted and added at call sites after C are calculated by taking the union of the del_types and add_types for each template corresponding to M. Propagate_Update is then called to execute the changes.
for each template CT in caller(M) do
for each C in callsite(CT) to callee M do
Let y = variable storing return value at C;
delete_types_after(C, y) = union of del_types(T) for all templates T of M;
add_types_after(C, y) = union of add_types(T) for all templates T of M;
propagate_update(C, y, delete_types_after, add_types_after, CT);
end for
end for
Required Data Representations and Access -> Java Data Structures
- Template call graph and subgraphs -> MetaCallGraph
- Templates -> MetaMethods
- Edges of call graph -> Relationships stored in instance variables callees1_cmpct and callees2_cmpct (caller to callees in general and at specific call sites)
- Methods -> HMethods
- Call sites within methods -> CALL (a Quad)
- Call sites to specific callee -> CALL.method() (Returns an HMethod.)
- Return variable -> Temp; found with CALL.retval()
- Sets of reaching types (added and deleted) -> Set
- Determination of callees and callers for a given method -> MetaCallGraph.getCallees and MetaAllCallers.getCallers
- Template repository -> Split relation mapping each HMethod to its corresponding MetaMethods
Home |
DMP |
Project |
Journal |
Contact
Relevant Java Classes |
Delete Call Site |
Template Call Graph |
Research |
Final Report
Propagate/Update
©2002, Katie Heise
|
|