private CallGraph callGraph;
private int allocationDepth;
+
+ static private int uniqueIDcount = 0;
+
+
// Use these data structures to track progress of
// 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;
+
// Use these data structures to track progress of one pass of
// processing the FlatNodes of a particular method
private HashSet <FlatReturnNode> returnNodesToCombineForCompleteOwnershipGraph;
- // for generating unique ownership node ID's throughout the
- // ownership analysis
- static private int uniqueIDcount = 0;
-
- static public Integer generateUniqueID() {
- ++uniqueIDcount;
- return new Integer( uniqueIDcount );
- }
-
-
// this analysis generates an ownership graph for every task
// in the program
public OwnershipAnalysis( State state,
mapDescriptorToCompleteOwnershipGraph =
new Hashtable<Descriptor, OwnershipGraph>();
+ mapFlatNewToAllocationSite =
+ new Hashtable<FlatNew, AllocationSite>();
+
// initialize methods to visit as the set of all tasks
descriptorsToVisit = new HashSet<Descriptor>();
Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
analyzeMethods();
}
+
+ // manage the set of tasks and methods to be analyzed
+ // and be sure to reschedule tasks/methods when the methods
+ // they call are updated
private void analyzeMethods() throws java.io.IOException {
while( !descriptorsToVisit.isEmpty() ) {
Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
descriptorsToVisit.remove( d );
- System.out.println( "Analyzing " + d );
-
// because the task or method descriptor just extracted
- // in the "to visit" set it either hasn't been analyzed
+ // was in the "to visit" set it either hasn't been analyzed
// yet, or some method that it depends on has been
// updated. Recompute a complete ownership graph for
// this task/method and compare it to any previous result.
// If there is a change detected, add any methods/tasks
// that depend on this one to the "to visit" set.
- OwnershipGraph og = new OwnershipGraph( allocationDepth );
+ System.out.println( "Analyzing " + d );
+
+ boolean isTask;
+ FlatMethod fm;
+ if( d instanceof MethodDescriptor ) {
+ isTask = false;
+ fm = state.getMethodFlat( (MethodDescriptor) d );
+ } else {
+ assert d instanceof TaskDescriptor;
+ isTask = true;
+ fm = state.getMethodFlat( (TaskDescriptor) d );
+ }
+ OwnershipGraph og = analyzeFlatMethod( isTask, fm );
OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get( d );
if( !og.equals( ogPrev ) ) {
-
mapDescriptorToCompleteOwnershipGraph.put( d, og );
// only methods have dependents, tasks cannot
if( d instanceof MethodDescriptor ) {
MethodDescriptor md = (MethodDescriptor) d;
Set dependents = callGraph.getCallerSet( md );
+ System.out.println( " Caller set is: " + dependents );
descriptorsToVisit.addAll( dependents );
}
}
}
-
- /*
- for( Iterator it_tasks=state.getTaskSymbolTable().getDescriptorsIterator();
- it_tasks.hasNext();
- ) {
-
- // initialize the mapping of flat nodes to ownership graphs
- // every flat node in the IR graph has its own ownership graph
- flatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
-
- TaskDescriptor td = (TaskDescriptor) it_tasks.next();
- FlatMethod fm = state.getMethodFlat( td );
-
- // give every node in the flat IR graph a unique label
- // so a human being can inspect the graph and verify
- // correctness
- flatnodetolabel = new Hashtable<FlatNode, Integer>();
- visited = new HashSet<FlatNode>();
- labelindex = 0;
- labelFlatNodes( fm );
-
- String methodname = td.getSymbol();
- analyzeFlatIRGraph( fm, methodname );
- }
- */
}
- /*
- private OwnershipGraph getGraphFromFlatNode( FlatNode fn ) {
- if( !flatNodeToOwnershipGraph.containsKey( fn ) ) {
- flatNodeToOwnershipGraph.put( fn, new OwnershipGraph( newDepthK ) );
- }
- return flatNodeToOwnershipGraph.get( fn );
- }
+ private OwnershipGraph
+ analyzeFlatMethod( boolean isTask,
+ FlatMethod flatm ) throws java.io.IOException {
- private void setGraphForFlatNode( FlatNode fn, OwnershipGraph og ) {
- flatNodeToOwnershipGraph.put( fn, og );
- }
+ // initialize flat nodes to visit as the flat method
+ // because all other nodes in this flat method are
+ // decendents of the flat method itself
+ flatNodesToVisit = new HashSet<FlatNode>();
+ flatNodesToVisit.add( flatm );
+
+ // initilize the mapping of flat nodes in this flat method to
+ // ownership graph results to an empty mapping
+ mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
- private void analyzeFlatMethod( FlatMethod flatm, String methodname ) throws java.io.IOException {
- toVisit=new HashSet<FlatNode>();
- toVisit.add( flatm );
+ // initialize the set of return nodes that will be combined as
+ // the final ownership graph result to return as an empty set
+ returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
- while( !toVisit.isEmpty() ) {
- FlatNode fn = (FlatNode) toVisit.iterator().next();
- toVisit.remove( fn );
+ while( !flatNodesToVisit.isEmpty() ) {
+ FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
+ flatNodesToVisit.remove( fn );
// perform this node's contributions to the ownership
// graph on a new copy, then compare it to the old graph
// at this node to see if anything was updated.
- OwnershipGraph og = new OwnershipGraph( newDepthK );
+ OwnershipGraph og = new OwnershipGraph( allocationDepth );
// start by merging all node's parents' graphs
for( int i = 0; i < fn.numPrev(); ++i ) {
og.merge( ogParent );
}
- analyzeFlatNode( fn );
+ // apply the analysis of the flat node to the
+ // ownership graph made from the merge of the
+ // parent graphs
+ analyzeFlatNode( isTask, fn, og );
// if the results of the new graph are different from
// the current graph at this node, replace the graph
// with the update and enqueue the children for
// processing
- OwnershipGraph ogOld = getGraphFromFlatNode( fn );
+ OwnershipGraph ogPrev = getGraphFromFlatNode( fn );
- if( !og.equals( ogOld ) ) {
+ if( !og.equals( ogPrev ) ) {
setGraphForFlatNode( fn, og );
for( int i = 0; i < fn.numNext(); i++ ) {
- FlatNode nn = fn.getNext( i );
- visited.remove( nn );
- toVisit.add( nn );
+ FlatNode nn = fn.getNext( i );
+ flatNodesToVisit.add( nn );
}
}
}
+
+ // end by merging all return nodes into a complete
+ // ownership graph that represents all possible heap
+ // states after the flat method returns
+ OwnershipGraph completeGraph = new OwnershipGraph( allocationDepth );
+ Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
+ while( retItr.hasNext() ) {
+ FlatReturnNode frn = (FlatReturnNode) retItr.next();
+ OwnershipGraph ogr = getGraphFromFlatNode( frn );
+ completeGraph.merge( ogr );
+ }
+ return completeGraph;
}
- private void analyzeFlatNode( FlatNode fn, String methodname ) {
- TempDescriptor src;
- TempDescriptor dst;
- FieldDescriptor fld;
- String nodeDescription = "No description";
- boolean writeGraph = false;
+ private void
+ analyzeFlatNode( boolean isTask,
+ FlatNode fn,
+ OwnershipGraph og ) throws java.io.IOException {
- // use node type to decide what alterations to make
- // to the ownership graph
- switch( fn.kind() ) {
-
- case FKind.FlatMethod:
- FlatMethod fm = (FlatMethod) fn;
+ //System.out.println( "Analyszing a flat node" );
+ TempDescriptor src;
+ TempDescriptor dst;
+ FieldDescriptor fld;
+ //String nodeDescription = "No description";
+ //boolean writeGraph = false;
+
+ // use node type to decide what alterations to make
+ // to the ownership graph
+ switch( fn.kind() ) {
+
+ case FKind.FlatMethod:
+ FlatMethod fm = (FlatMethod) fn;
+
+ if( isTask ) {
// add method parameters to the list of heap regions
// and remember names for analysis
for( int i = 0; i < fm.numParameters(); ++i ) {
TempDescriptor tdParam = fm.getParameter( i );
- og.parameterAllocation( tdParam );
- og.addAnalysisRegion( tdParam );
- }
-
- nodeDescription = "Method";
- writeGraph = true;
- break;
-
- case FKind.FlatOpNode:
- FlatOpNode fon = (FlatOpNode) fn;
- if( fon.getOp().getOp() == Operation.ASSIGN ) {
- src = fon.getLeft();
- dst = fon.getDest();
- og.assignTempToTemp( src, dst );
- nodeDescription = "Op";
- writeGraph = true;
+ og.taskParameterAllocation( tdParam );
+ //og.addAnalysisRegion( tdParam );
}
- break;
-
- case FKind.FlatFieldNode:
- FlatFieldNode ffn = (FlatFieldNode) fn;
- src = ffn.getSrc();
- dst = ffn.getDst();
- fld = ffn.getField();
- if( !fld.getType().isPrimitive() ) {
- og.assignTempToField( src, dst, fld );
- nodeDescription = "Field";
- writeGraph = true;
- }
- break;
-
- case FKind.FlatSetFieldNode:
- FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
- src = fsfn.getSrc();
- dst = fsfn.getDst();
- fld = fsfn.getField();
- og.assignFieldToTemp( src, dst, fld );
- nodeDescription = "SetField";
- writeGraph = true;
- break;
-
- case FKind.FlatNew:
- FlatNew fnn = (FlatNew) fn;
- dst = fnn.getDst();
- og.assignTempToNewAllocation( dst, fnn );
-
- // !!!!!!!!!!!!!!
- // do this if the new object is a flagged type
- //og.addAnalysisRegion( tdParam );
-
- nodeDescription = "New";
- writeGraph = true;
- break;
-
- case FKind.FlatReturnNode:
- nodeDescription = "Return";
- writeGraph = true;
- og.writeCondensedAnalysis( makeCondensedAnalysisName( methodname, flatnodetolabel.get(fn) ) );
- break;
}
-
- if( writeGraph ) {
- og.writeGraph( makeNodeName( methodname,
- flatnodetolabel.get( fn ),
- nodeDescription ) );
+ break;
+
+ /*
+ case FKind.FlatOpNode:
+ FlatOpNode fon = (FlatOpNode) fn;
+ if( fon.getOp().getOp() == Operation.ASSIGN ) {
+ src = fon.getLeft();
+ dst = fon.getDest();
+ og.assignTempToTemp( src, dst );
+ //nodeDescription = "Op";
+ //writeGraph = true;
+ og.writeGraph( fn );
+ }
+ break;
+
+ case FKind.FlatFieldNode:
+ FlatFieldNode ffn = (FlatFieldNode) fn;
+ src = ffn.getSrc();
+ dst = ffn.getDst();
+ fld = ffn.getField();
+ if( !fld.getType().isPrimitive() ) {
+ og.assignTempToField( src, dst, fld );
+ //nodeDescription = "Field";
+ //writeGraph = true;
+ og.writeGraph( fn );
}
+ break;
+
+ case FKind.FlatSetFieldNode:
+ FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
+ src = fsfn.getSrc();
+ dst = fsfn.getDst();
+ fld = fsfn.getField();
+ og.assignFieldToTemp( src, dst, fld );
+ //nodeDescription = "SetField";
+ //writeGraph = true;
+ og.writeGraph( fn );
+ break;
+
+ case FKind.FlatNew:
+ FlatNew fnn = (FlatNew) fn;
+ dst = fnn.getDst();
+ og.assignTempToNewAllocation( dst, fnn );
+
+ // !!!!!!!!!!!!!!
+ // do this if the new object is a flagged type
+ //og.addAnalysisRegion( tdParam );
+
+ //nodeDescription = "New";
+ //writeGraph = true;
+ og.writeGraph( fn );
+
+ break;
+
+ */
+
+ case FKind.FlatCall:
+ FlatCall fc = (FlatCall) fn;
+ MethodDescriptor md = fc.getMethod();
+ descriptorsToVisit.add( md );
+ break;
+
+ case FKind.FlatReturnNode:
+ //nodeDescription = "Return";
+ //writeGraph = true;
+ //og.writeCondensedAnalysis( makeCondensedAnalysisName( methodname, flatnodetolabel.get(fn) ) );
+ //og.writeGraph( fn );
+ break;
+ }
+
+ /*
+ if( writeGraph ) {
+ og.writeGraph( makeNodeName( methodname,
+ flatnodetolabel.get( fn ),
+ nodeDescription ) );
+ }
+ */
}
+ static public Integer generateUniqueHeapRegionNodeID() {
+ ++uniqueIDcount;
+ return new Integer( uniqueIDcount );
+ }
- private String makeNodeName( String methodname, Integer id, String type ) {
- String s = String.format( "%05d", id );
- return "method_"+methodname+"_FN"+s+"_"+type;
+ private OwnershipGraph getGraphFromFlatNode( FlatNode fn ) {
+ if( !mapFlatNodeToOwnershipGraph.containsKey( fn ) ) {
+ mapFlatNodeToOwnershipGraph.put( fn, new OwnershipGraph( allocationDepth ) );
+ }
+
+ return mapFlatNodeToOwnershipGraph.get( fn );
}
- private String makeCondensedAnalysisName( String methodname, Integer id ) {
- return "method_"+methodname+"_Ownership_from"+id;
+ private void setGraphForFlatNode( FlatNode fn, OwnershipGraph og ) {
+ mapFlatNodeToOwnershipGraph.put( fn, og );
+ }
+
+ private AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) {
+ if( !mapFlatNewToAllocationSite.containsKey( fn ) ) {
+ AllocationSite as = new AllocationSite( allocationDepth );
+
+ // the first k-1 nodes are single objects
+ for( int i = 0; i < allocationDepth - 1; ++i ) {
+ //HeapRegionNode hrn = createNewHeapRegionNode( null, true, false, false );
+ Integer id = generateUniqueHeapRegionNodeID();
+ as.setIthOldest( i, id );
+ }
+
+ // the kth node is a summary node
+ //HeapRegionNode hrnNewSummary = createNewHeapRegionNode( null, false, false, true );
+ Integer id2 = generateUniqueHeapRegionNodeID();
+ as.setIthOldest( allocationDepth - 1, id2 );
+
+ mapFlatNewToAllocationSite.put( fn, as );
+ }
+
+ return mapFlatNewToAllocationSite.get( fn );
}
- */
}
projects / IRC.git / blobdiff