/** Given a call to MethodDescriptor, lists the methods which
could actually be call by that method. */
+ public Set getMethodCalls(TaskDescriptor td) {
+ return getMethodCalls( (Descriptor) td );
+ }
+
public Set getMethodCalls(MethodDescriptor md) {
+ return getMethodCalls( (Descriptor) md );
+ }
+
+ public Set getMethodCalls(Descriptor d) {
+ assert d instanceof MethodDescriptor ||
+ d instanceof TaskDescriptor;
+
HashSet ns=new HashSet();
- ns.add(md);
- Set s=(Set)mapCaller2CalleeSet.get(md);
+ ns.add(d);
+ Set s=(Set)mapCaller2CalleeSet.get(d);
if (s!=null)
for(Iterator it=s.iterator(); it.hasNext();) {
- MethodDescriptor md2=(MethodDescriptor)it.next();
- ns.addAll(getMethodCalls(md2));
+ MethodDescriptor md=(MethodDescriptor)it.next();
+ ns.addAll(getMethodCalls(md));
}
return ns;
}
}
}
- public void writeToDot(String graphName) throws java.io.IOException {
- // each task or method only needs to be labeled once
- // in a dot file
+
+ public void writeVirtual2ImplemToDot(String graphName) throws java.io.IOException {
HashSet labeledInDot = new HashSet();
- // write out the call graph using the callees mapping
- BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallees.dot") );
- bw.write("digraph "+graphName+"byCallees {\n");
- Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
+ BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
+ bw.write("digraph "+graphName+" {\n");
+ Iterator mapItr = mapVirtual2ImplementationSet.entrySet().iterator();
while( mapItr.hasNext() ) {
- Map.Entry me = (Map.Entry)mapItr.next();
- MethodDescriptor callee = (MethodDescriptor) me.getKey();
- HashSet callerSet = (HashSet) me.getValue();
+ Map.Entry me = (Map.Entry) mapItr.next();
+ MethodDescriptor virtual = (MethodDescriptor) me.getKey();
+ HashSet implemSet = (HashSet) me.getValue();
- if( !labeledInDot.contains(callee) ) {
- labeledInDot.add(callee);
- bw.write(" " + callee.getNum() + "[label=\"" + callee + "\"];\n");
+ if( !labeledInDot.contains(virtual) ) {
+ labeledInDot.add(virtual);
+ bw.write(" "+virtual.getNum()+"[label=\""+virtual+"\"];\n");
}
- Iterator callerItr = callerSet.iterator();
- while( callerItr.hasNext() ) {
- Descriptor caller = (Descriptor) callerItr.next();
+ Iterator implemItr = implemSet.iterator();
+ while( implemItr.hasNext() ) {
+ Descriptor implem = (Descriptor) implemItr.next();
- if( !labeledInDot.contains(caller) ) {
- labeledInDot.add(caller);
- bw.write(" " + caller.getNum() + "[label=\"" + caller + "\"];\n");
+ if( !labeledInDot.contains(implem) ) {
+ labeledInDot.add(implem);
+ bw.write(" "+implem.getNum()+"[label=\""+implem+"\"];\n");
}
- bw.write(" " + callee.getNum() + "->" + caller.getNum() + ";\n");
+ bw.write(" "+virtual.getNum()+"->"+implem.getNum()+";\n");
}
}
bw.write("}\n");
bw.close();
+ }
+
+ public void writeCaller2CalleesToDot(String graphName) throws java.io.IOException {
// write out the call graph (should be equivalent) by
// using the callers mapping
- labeledInDot = new HashSet();
- bw = new BufferedWriter(new FileWriter(graphName+"byCallers.dot") );
+ HashSet labeledInDot = new HashSet();
+ BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallers.dot") );
bw.write("digraph "+graphName+"byCallers {\n");
- mapItr = mapCaller2CalleeSet.entrySet().iterator();
+ Iterator mapItr = mapCaller2CalleeSet.entrySet().iterator();
while( mapItr.hasNext() ) {
Map.Entry me = (Map.Entry)mapItr.next();
Descriptor caller = (Descriptor) me.getKey();
HashSet calleeSet = (HashSet) me.getValue();
+ String callerString = caller.toString().replaceAll("[\\W]", "");
+
+ /*
if( !labeledInDot.contains(caller) ) {
labeledInDot.add(caller);
- bw.write(" " + caller.getNum() + "[label=\"" + caller + "\"];\n");
+ bw.write(" " + caller.getNum() + "[label=\"" + callerString + "\"];\n");
}
+ */
Iterator calleeItr = calleeSet.iterator();
while( calleeItr.hasNext() ) {
MethodDescriptor callee = (MethodDescriptor) calleeItr.next();
+ String calleeString = callee.toString().replaceAll("[\\W]", "");
+
+ /*
if( !labeledInDot.contains(callee) ) {
labeledInDot.add(callee);
- bw.write(" " + callee.getNum() + "[label=\"" + callee + "\"];\n");
+ bw.write(" " + callee.getNum() + "[label=\"" + calleeString + "\"];\n");
}
+ */
+ bw.write(" " + caller.getNum() + "->" + callee.getNum() + ";\n");
+
+
+ //bw.write(" " + callerString + "->" + calleeString + ";\n");
+ }
+ }
+ bw.write("}\n");
+ bw.close();
+ }
+
+
+ public void writeCallee2CallersToDot(String graphName) throws java.io.IOException {
+ // each task or method only needs to be labeled once
+ // in a dot file
+ HashSet labeledInDot = new HashSet();
+
+ // write out the call graph using the callees mapping
+ BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+"byCallees.dot") );
+ bw.write("digraph "+graphName+"byCallees {\n");
+ Iterator mapItr = mapCallee2CallerSet.entrySet().iterator();
+ while( mapItr.hasNext() ) {
+ Map.Entry me = (Map.Entry)mapItr.next();
+ MethodDescriptor callee = (MethodDescriptor) me.getKey();
+ HashSet callerSet = (HashSet) me.getValue();
+
+ String calleeString = callee.toString().replaceAll("[\\W]", "");
+
+ /*
+ if( !labeledInDot.contains(callee) ) {
+ labeledInDot.add(callee);
+ bw.write(" " + callee.getNum() + "[label=\"" + calleeString + "\"];\n");
+ }
+ */
+
+ Iterator callerItr = callerSet.iterator();
+ while( callerItr.hasNext() ) {
+ Descriptor caller = (Descriptor) callerItr.next();
+ String callerString = caller.toString().replaceAll("[\\W]", "");
+
+ /*
+ if( !labeledInDot.contains(caller) ) {
+ labeledInDot.add(caller);
+ bw.write(" " + caller.getNum() + "[label=\"" + callerString + "\"];\n");
+ }
+ */
+
+ bw.write(" " + caller.getNum() + "->" + callee.getNum() + ";\n");
+
- bw.write(" " + callee.getNum() + "->" + caller.getNum() + ";\n");
+ //bw.write(" " + callerString + "->" + calleeString + ";\n");
}
}
bw.write("}\n");
// processing all methods in the program, and by methods
// TaskDescriptor and MethodDescriptor are combined
// together, with a common parent class Descriptor
- private HashSet <Descriptor> descriptorsToVisit;
private Hashtable<Descriptor, OwnershipGraph> mapDescriptorToCompleteOwnershipGraph;
private Hashtable<FlatNew, AllocationSite> mapFlatNewToAllocationSite;
private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
private HashSet <FlatReturnNode> returnNodesToCombineForCompleteOwnershipGraph;
+ // descriptorsToAnalyze identifies the set of tasks and methods
+ // that are reachable from the program tasks, this set is initialized
+ // and then remains static
+ private HashSet<Descriptor> descriptorsToAnalyze;
+
+ // descriptorsToVisit is initialized to descriptorsToAnalyze and is
+ // reduced by visiting a descriptor during analysis. When dependents
+ // must be scheduled, only those contained in descriptorsToAnalyze
+ // should be re-added to this set
+ private HashSet<Descriptor> descriptorsToVisit;
+
+
// this analysis generates an ownership graph for every task
// in the program
this.allocationDepth = allocationDepth;
- descriptorsToVisit = new HashSet<Descriptor>();
+ descriptorsToAnalyze = new HashSet<Descriptor>();
mapDescriptorToCompleteOwnershipGraph =
new Hashtable<Descriptor, OwnershipGraph>();
mapDescriptorToAllocationSiteSet =
new Hashtable<Descriptor, HashSet<AllocationSite> >();
- // use this set to prevent infinite recursion when
- // traversing the call graph
- HashSet<Descriptor> calleesScheduled = new HashSet<Descriptor>();
-
// initialize methods to visit as the set of all tasks in the
// program and then any method that could be called starting
Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
while( taskItr.hasNext() ) {
Descriptor d = (Descriptor) taskItr.next();
- descriptorsToVisit.add(d);
-
- // recursively find all callees from this task
- scheduleAllCallees(calleesScheduled, d);
+ scheduleAllCallees(d);
}
// before beginning analysis, initialize every scheduled method
// with an ownership graph that has populated parameter index tables
// by analyzing the first node which is always a FlatMethod node
- Iterator<Descriptor> dItr = calleesScheduled.iterator();
+ Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
while( dItr.hasNext() ) {
Descriptor d = dItr.next();
OwnershipGraph og = new OwnershipGraph(allocationDepth);
// called from the constructor to help initialize the set
// of methods that needs to be analyzed by ownership analysis
- private void scheduleAllCallees(HashSet<Descriptor> calleesScheduled,
- Descriptor d) {
- if( calleesScheduled.contains(d) ) {
+ private void scheduleAllCallees(Descriptor d) {
+ if( descriptorsToAnalyze.contains(d) ) {
return;
}
- calleesScheduled.add(d);
+ descriptorsToAnalyze.add(d);
- Set callees = callGraph.getCalleeSet(d);
- if( callees == null ) {
- return;
+ // start with all method calls to further schedule
+ Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls( d );
+
+ if( d instanceof MethodDescriptor ) {
+ // see if this method has virtual dispatch
+ Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d );
+ moreMethodsToCheck.addAll( virtualMethods );
}
- Iterator methItr = callees.iterator();
+ // keep following any further methods identified in
+ // the call chain
+ Iterator methItr = moreMethodsToCheck.iterator();
while( methItr.hasNext() ) {
- MethodDescriptor md = (MethodDescriptor) methItr.next();
- descriptorsToVisit.add(md);
-
- // recursively find all callees from this task
- scheduleAllCallees(calleesScheduled, md);
+ Descriptor m = (Descriptor) methItr.next();
+ scheduleAllCallees(m);
}
}
// and be sure to reschedule tasks/methods when the methods
// they call are updated
private void analyzeMethods() throws java.io.IOException {
+
+ descriptorsToVisit = (HashSet<Descriptor>)descriptorsToAnalyze.clone();
while( !descriptorsToVisit.isEmpty() ) {
Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
boolean pruneGarbage,
boolean writeReferencers
*/
- og.writeGraph(d, true, true, true, false);
+ og.writeGraph(d, true, true, false, false);
// only methods have dependents, tasks cannot
// be invoked by any user program calls
MethodDescriptor md = (MethodDescriptor) d;
Set dependents = callGraph.getCallerSet(md);
if( dependents != null ) {
- descriptorsToVisit.addAll(dependents);
+ Iterator depItr = dependents.iterator();
+ while( depItr.hasNext() ) {
+ Descriptor dependent = (Descriptor) depItr.next();
+ if( descriptorsToAnalyze.contains( dependent ) ) {
+ descriptorsToVisit.add(dependent);
+ }
+ }
}
}
}
}
- int x = 0;
-
-
// keep passing the Descriptor of the method along for debugging
// and dot file writing
private OwnershipGraph
if( !og.equals(ogPrev) ) {
setGraphForFlatNode(fn, og);
-
-
- x++;
- if( x > 0 ) {
- String s = String.format("debug%04d", x);
- //og.writeGraph( s, true, true, true, false );
- }
-
-
-
for( int i = 0; i < fn.numNext(); i++ ) {
FlatNode nn = fn.getNext(i);
flatNodesToVisit.add(nn);
break;
case FKind.FlatCall:
- FlatCall fc = (FlatCall) fn;
- MethodDescriptor md = fc.getMethod();
- FlatMethod flatm = state.getMethodFlat(md);
- //HashSet<AllocationSite> allocSiteSet = getAllocationSiteSet( md );
- OwnershipGraph ogAllPossibleCallees = new OwnershipGraph(allocationDepth);
+ FlatCall fc = (FlatCall) fn;
+ MethodDescriptor md = fc.getMethod();
+ FlatMethod flatm = state.getMethodFlat(md);
+ OwnershipGraph ogAllPossibleCallees = new OwnershipGraph(allocationDepth);
if( md.isStatic() ) {
// a static method is simply always the same, makes life easy
OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get(md);
ogAllPossibleCallees.merge(onlyPossibleCallee);
- /*
- if( onlyPossibleCallee != null ) {
- onlyPossibleCallee.writeGraph( "only", false, false );
- System.out.println( "There was only one possible callee, "+md );
- }
- */
-
} else {
// if the method descriptor is virtual, then there could be a
// set of possible methods that will actually be invoked, so
// find all of them and merge all of their graphs together
- TypeDescriptor typeDesc = fc.getThis().getType();
+ TypeDescriptor typeDesc = fc.getThis().getType();
Set possibleCallees = callGraph.getMethods(md, typeDesc);
- //int j = 0;
-
Iterator i = possibleCallees.iterator();
while( i.hasNext() ) {
MethodDescriptor possibleMd = (MethodDescriptor) i.next();
- //allocSiteSet.addAll( getAllocationSiteSet( possibleMd ) );
OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
-
- /*
- if( ogPotentialCallee != null ) {
- ogPotentialCallee.writeGraph( "potential"+j, false, false );
- ++j;
- }
- */
-
ogAllPossibleCallees.merge(ogPotentialCallee);
}
-
- //System.out.println( "There were "+j+" potential callees merged together." );
}
-
- //System.out.println( "AllocationSiteSet has "+allocSiteSet.size()+" items." );
-
- // now we should have the following information to resolve this method call:
+
+ // Now we should have the following information to resolve this method call:
//
// 1. A FlatCall fc to query for the caller's context (argument labels, etc)
//
// 4. The OwnershipGraph ogAllPossibleCallees is a merge of every ownership graph of all the possible
// methods to capture any possible references made.
//
- // 5. The Set of AllocationSite objects, allocSiteSet that is the set of allocation sites from
- // every possible method we might have chosen
- //
og.resolveMethodCall(fc, md.isStatic(), flatm, ogAllPossibleCallees);
break;
projects / IRC.git / commitdiff