1 package Analysis.OwnershipAnalysis;
3 import Analysis.CallGraph.*;
6 import IR.Tree.Modifiers;
11 public class OwnershipAnalysis {
14 ///////////////////////////////////////////
16 // Public interface to discover possible
17 // aliases in the program under analysis
19 ///////////////////////////////////////////
21 public HashSet<AllocationSite>
22 getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
23 return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
26 public AllocationSite getAllocationSiteFromFlatNew(FlatNew fn) {
27 return getAllocationSiteFromFlatNewPRIVATE(fn);
31 public boolean createsPotentialAliases(Descriptor taskOrMethod,
35 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
37 return og.hasPotentialAlias(paramIndex1, paramIndex2);
40 public boolean createsPotentialAliases(Descriptor taskOrMethod,
42 AllocationSite alloc) {
44 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
46 return og.hasPotentialAlias(paramIndex, alloc);
49 public boolean createsPotentialAliases(Descriptor taskOrMethod,
53 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
55 return og.hasPotentialAlias(paramIndex, alloc);
58 public boolean createsPotentialAliases(Descriptor taskOrMethod,
59 AllocationSite alloc1,
60 AllocationSite alloc2) {
62 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
64 return og.hasPotentialAlias(alloc1, alloc2);
68 protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) {
71 OwnershipGraph og = new OwnershipGraph( allocationDepth, typeUtil );
73 assert mapDescriptorToAllMethodContexts.containsKey( d );
74 HashSet<MethodContext> contexts = mapDescriptorToAllMethodContexts.get( d );
75 Iterator<MethodContext> mcItr = contexts.iterator();
76 while( mcItr.hasNext() ) {
77 MethodContext mc = mcItr.next();
79 OwnershipGraph ogContext = mapMethodContextToCompleteOwnershipGraph.get(mc);
80 assert ogContext != null;
82 og.merge( ogContext );
89 // use the methods given above to check every possible alias
90 // between task parameters and flagged allocation sites reachable
92 public void writeAllAliases(String outputFile) throws java.io.IOException {
94 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
96 bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth);
98 // look through every task for potential aliases
99 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
100 while( taskItr.hasNext() ) {
101 TaskDescriptor td = (TaskDescriptor) taskItr.next();
103 bw.write("\n---------"+td+"--------\n");
105 HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
107 // for each task parameter, check for aliases with
108 // other task parameters and every allocation site
109 // reachable from this task
110 boolean foundSomeAlias = false;
112 FlatMethod fm = state.getMethodFlat(td);
113 for( int i = 0; i < fm.numParameters(); ++i ) {
115 // for the ith parameter check for aliases to all
116 // higher numbered parameters
117 for( int j = i + 1; j < fm.numParameters(); ++j ) {
118 if( createsPotentialAliases(td, i, j) ) {
119 foundSomeAlias = true;
120 bw.write("Potential alias between parameters "+i+" and "+j+".\n");
124 // for the ith parameter, check for aliases against
125 // the set of allocation sites reachable from this
127 Iterator allocItr = allocSites.iterator();
128 while( allocItr.hasNext() ) {
129 AllocationSite as = (AllocationSite) allocItr.next();
130 if( createsPotentialAliases(td, i, as) ) {
131 foundSomeAlias = true;
132 bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
137 // for each allocation site check for aliases with
138 // other allocation sites in the context of execution
140 HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
141 Iterator allocItr1 = allocSites.iterator();
142 while( allocItr1.hasNext() ) {
143 AllocationSite as1 = (AllocationSite) allocItr1.next();
145 Iterator allocItr2 = allocSites.iterator();
146 while( allocItr2.hasNext() ) {
147 AllocationSite as2 = (AllocationSite) allocItr2.next();
149 if( !outerChecked.contains(as2) &&
150 createsPotentialAliases(td, as1, as2) ) {
151 foundSomeAlias = true;
152 bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
156 outerChecked.add(as1);
159 if( !foundSomeAlias ) {
160 bw.write("No aliases between flagged objects in Task "+td+".\n");
167 ///////////////////////////////////////////
169 // end public interface
171 ///////////////////////////////////////////
180 // data from the compiler
182 private TypeUtil typeUtil;
183 private CallGraph callGraph;
184 private int allocationDepth;
186 // used to identify HeapRegionNode objects
187 // A unique ID equates an object in one
188 // ownership graph with an object in another
189 // graph that logically represents the same
191 // start at 10 and increment to leave some
192 // reserved IDs for special purposes
193 static private int uniqueIDcount = 10;
196 // Use these data structures to track progress of
197 // processing all methods in the program, and by methods
198 // TaskDescriptor and MethodDescriptor are combined
199 // together, with a common parent class Descriptor
200 private Hashtable<MethodContext, OwnershipGraph> mapMethodContextToInitialParamAllocGraph;
201 private Hashtable<MethodContext, OwnershipGraph> mapMethodContextToCompleteOwnershipGraph;
202 private Hashtable<FlatNew, AllocationSite> mapFlatNewToAllocationSite;
203 private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
204 private Hashtable<MethodContext, Integer> mapMethodContextToNumUpdates;
205 private Hashtable<Descriptor, HashSet<MethodContext> > mapDescriptorToAllMethodContexts;
207 // Use these data structures to track progress of one pass of
208 // processing the FlatNodes of a particular method
209 private HashSet <FlatNode> flatNodesToVisit;
210 private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
211 private HashSet <FlatReturnNode> returnNodesToCombineForCompleteOwnershipGraph;
213 // descriptorsToAnalyze identifies the set of tasks and methods
214 // that are reachable from the program tasks, this set is initialized
215 // and then remains static
216 private HashSet<Descriptor> descriptorsToAnalyze;
218 // descriptorsToVisit is initialized to descriptorsToAnalyze and is
219 // reduced by visiting a descriptor during analysis. When dependents
220 // must be scheduled, only those contained in descriptorsToAnalyze
221 // should be re-added to this set
222 private HashSet<MethodContext> methodContextsToVisit;
224 // a special field descriptor for all array elements
225 private static FieldDescriptor fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
226 new TypeDescriptor("Array[]"),
231 // a special temp descriptor for setting more than one parameter label
232 // to the all-aliased-parameters heap region node
233 protected static TempDescriptor tdAliasedParams = new TempDescriptor("_AllAliasedParams___");
236 // for controlling DOT file output
237 private boolean writeDOTs;
238 private boolean writeAllDOTs;
242 // this analysis generates an ownership graph for every task
244 public OwnershipAnalysis(State state,
249 boolean writeAllDOTs,
250 String aliasFile) throws java.io.IOException {
252 double timeStartAnalysis = (double) System.nanoTime();
256 this.callGraph = callGraph;
257 this.allocationDepth = allocationDepth;
258 this.writeDOTs = writeDOTs;
259 this.writeAllDOTs = writeAllDOTs;
261 descriptorsToAnalyze = new HashSet<Descriptor>();
263 mapMethodContextToInitialParamAllocGraph =
264 new Hashtable<MethodContext, OwnershipGraph>();
266 mapMethodContextToCompleteOwnershipGraph =
267 new Hashtable<MethodContext, OwnershipGraph>();
269 mapFlatNewToAllocationSite =
270 new Hashtable<FlatNew, AllocationSite>();
272 mapDescriptorToAllocationSiteSet =
273 new Hashtable<Descriptor, HashSet<AllocationSite> >();
275 mapDescriptorToAllMethodContexts =
276 new Hashtable<Descriptor, HashSet<MethodContext> >();
280 mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
285 // initialize methods to visit as the set of all tasks in the
286 // program and then any method that could be called starting
288 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
289 while( taskItr.hasNext() ) {
290 Descriptor d = (Descriptor) taskItr.next();
291 scheduleAllCallees(d);
295 // we are not in task mode, just normal Java, so start with
297 Descriptor d = tu.getMain();
298 scheduleAllCallees(d);
301 Iterator classItr = state.getClassSymbolTable().getDescriptorsIterator();
302 while( classItr.hasNext() ) {
303 ClassDescriptor cd = (ClassDescriptor) classItr.next();
305 Iterator methItr = cd.getMethods();
306 while( methItr.hasNext() ) {
307 Descriptor d = (Descriptor) methItr.next();
309 if( d.getSymbol().equals( "main" ) ) {
310 scheduleAllCallees(d);
318 // before beginning analysis, initialize every scheduled method
319 // with an ownership graph that has populated parameter index tables
320 // by analyzing the first node which is always a FlatMethod node
321 Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
322 while( dItr.hasNext() ) {
323 Descriptor d = dItr.next();
324 OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
327 if( d instanceof MethodDescriptor ) {
328 fm = state.getMethodFlat( (MethodDescriptor) d);
330 assert d instanceof TaskDescriptor;
331 fm = state.getMethodFlat( (TaskDescriptor) d);
334 MethodContext mc = new MethodContext( d );
335 assert !mapDescriptorToAllMethodContexts.containsKey( d );
336 HashSet<MethodContext> s = new HashSet<MethodContext>();
338 mapDescriptorToAllMethodContexts.put( d, s );
340 //System.out.println("Previsiting " + mc);
342 og = analyzeFlatNode(mc, fm, null, og);
343 setGraphForMethodContext(mc, og);
346 //System.out.println("");
348 // as mentioned above, analyze methods one-by-one, possibly revisiting
349 // a method if the methods that it calls are updated
352 //System.out.println("");
354 double timeEndAnalysis = (double) System.nanoTime();
355 double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
356 String treport = String.format( "The analysis took %.3f sec.", dt );
357 System.out.println( treport );
359 if( aliasFile != null ) {
360 writeAllAliases(aliasFile);
364 // called from the constructor to help initialize the set
365 // of methods that needs to be analyzed by ownership analysis
366 private void scheduleAllCallees(Descriptor d) {
367 if( descriptorsToAnalyze.contains(d) ) {
370 descriptorsToAnalyze.add(d);
372 // start with all method calls to further schedule
373 Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
375 if( d instanceof MethodDescriptor ) {
376 // see if this method has virtual dispatch
377 Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
378 moreMethodsToCheck.addAll(virtualMethods);
381 // keep following any further methods identified in
383 Iterator methItr = moreMethodsToCheck.iterator();
384 while( methItr.hasNext() ) {
385 Descriptor m = (Descriptor) methItr.next();
386 scheduleAllCallees(m);
391 // manage the set of tasks and methods to be analyzed
392 // and be sure to reschedule tasks/methods when the methods
393 // they call are updated
394 private void analyzeMethods() throws java.io.IOException {
396 methodContextsToVisit = new HashSet<MethodContext>();
397 Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
398 while( itrd2a.hasNext() ) {
399 HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
402 Iterator<MethodContext> itrmc = mcs.iterator();
403 while( itrmc.hasNext() ) {
404 methodContextsToVisit.add( itrmc.next() );
408 while( !methodContextsToVisit.isEmpty() ) {
409 MethodContext mc = methodContextsToVisit.iterator().next();
410 methodContextsToVisit.remove(mc);
413 // because the task or method descriptor just extracted
414 // was in the "to visit" set it either hasn't been analyzed
415 // yet, or some method that it depends on has been
416 // updated. Recompute a complete ownership graph for
417 // this task/method and compare it to any previous result.
418 // If there is a change detected, add any methods/tasks
419 // that depend on this one to the "to visit" set.
421 System.out.println("Analyzing " + mc);
423 Descriptor d = mc.getDescriptor();
425 if( d instanceof MethodDescriptor ) {
426 fm = state.getMethodFlat( (MethodDescriptor) d);
428 assert d instanceof TaskDescriptor;
429 fm = state.getMethodFlat( (TaskDescriptor) d);
432 OwnershipGraph og = analyzeFlatMethod(mc, fm);
433 OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
434 if( !og.equals(ogPrev) ) {
435 setGraphForMethodContext(mc, og);
437 // only methods have dependents, tasks cannot
438 // be invoked by any user program calls
439 if( d instanceof MethodDescriptor ) {
440 MethodDescriptor md = (MethodDescriptor) d;
441 Set dependents = callGraph.getCallerSet(md);
442 if( dependents != null ) {
443 Iterator depItr = dependents.iterator();
444 while( depItr.hasNext() ) {
445 Descriptor dependent = (Descriptor) depItr.next();
446 if( descriptorsToAnalyze.contains(dependent) ) {
448 HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( dependent );
451 Iterator<MethodContext> itrmc = mcs.iterator();
452 while( itrmc.hasNext() ) {
453 methodContextsToVisit.add( itrmc.next() );
465 // keep passing the Descriptor of the method along for debugging
466 // and dot file writing
467 private OwnershipGraph
468 analyzeFlatMethod(MethodContext mc,
469 FlatMethod flatm) throws java.io.IOException {
471 // initialize flat nodes to visit as the flat method
472 // because it is the entry point
474 flatNodesToVisit = new HashSet<FlatNode>();
475 flatNodesToVisit.add(flatm);
477 // initilize the mapping of flat nodes in this flat method to
478 // ownership graph results to an empty mapping
479 mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
481 // initialize the set of return nodes that will be combined as
482 // the final ownership graph result to return as an empty set
483 returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
486 while( !flatNodesToVisit.isEmpty() ) {
487 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
488 flatNodesToVisit.remove(fn);
490 //System.out.println( " "+fn );
492 // perform this node's contributions to the ownership
493 // graph on a new copy, then compare it to the old graph
494 // at this node to see if anything was updated.
495 OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
497 // start by merging all node's parents' graphs
498 for( int i = 0; i < fn.numPrev(); ++i ) {
499 FlatNode pn = fn.getPrev(i);
500 if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
501 OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
506 // apply the analysis of the flat node to the
507 // ownership graph made from the merge of the
509 og = analyzeFlatNode(mc,
511 returnNodesToCombineForCompleteOwnershipGraph,
515 //debugSnapshot(og,fn);
519 // if the results of the new graph are different from
520 // the current graph at this node, replace the graph
521 // with the update and enqueue the children for
523 OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
524 if( !og.equals(ogPrev) ) {
525 mapFlatNodeToOwnershipGraph.put(fn, og);
527 for( int i = 0; i < fn.numNext(); i++ ) {
528 FlatNode nn = fn.getNext(i);
529 flatNodesToVisit.add(nn);
534 // end by merging all return nodes into a complete
535 // ownership graph that represents all possible heap
536 // states after the flat method returns
537 OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil);
538 Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
539 while( retItr.hasNext() ) {
540 FlatReturnNode frn = (FlatReturnNode) retItr.next();
541 assert mapFlatNodeToOwnershipGraph.containsKey(frn);
542 OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
543 completeGraph.merge(ogr);
546 return completeGraph;
550 private OwnershipGraph
551 analyzeFlatNode(MethodContext mc,
553 HashSet<FlatReturnNode> setRetNodes,
554 OwnershipGraph og) throws java.io.IOException {
560 // use node type to decide what alterations to make
561 // to the ownership graph
562 switch( fn.kind() ) {
564 case FKind.FlatMethod:
565 FlatMethod fm = (FlatMethod) fn;
567 // there should only be one FlatMethod node as the
568 // parent of all other FlatNode objects, so take
569 // the opportunity to construct the initial graph by
570 // adding parameters labels to new heap regions
571 // AND this should be done once globally so that the
572 // parameter IDs are consistent between analysis
573 // iterations, so if this step has been done already
574 // just merge in the cached version
575 OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
576 if( ogInitParamAlloc == null ) {
578 // if the method context has aliased parameters, make sure
579 // there is a blob region for all those param labels to
581 Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
582 if( !aliasedParamIndices.isEmpty() ) {
583 og.makeAliasedParamHeapRegionNode( tdAliasedParams );
586 // set up each parameter
587 for( int i = 0; i < fm.numParameters(); ++i ) {
588 TempDescriptor tdParam = fm.getParameter( i );
589 Integer paramIndex = new Integer( i );
591 if( aliasedParamIndices.contains( paramIndex ) ) {
592 // just point this one to the alias blob
593 og.assignTempEqualToAliasedParam( tdParam,
597 // this parameter is not aliased to others, give it
598 // a fresh parameter heap region
600 og.assignTempEqualToParamAlloc(tdParam,
601 mc.getDescriptor() instanceof TaskDescriptor,
607 OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
609 mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
612 // or just leverage the cached copy
613 og.merge(ogInitParamAlloc);
617 case FKind.FlatOpNode:
618 FlatOpNode fon = (FlatOpNode) fn;
619 if( fon.getOp().getOp() == Operation.ASSIGN ) {
622 og.assignTempXEqualToTempY(lhs, rhs);
626 case FKind.FlatFieldNode:
627 FlatFieldNode ffn = (FlatFieldNode) fn;
630 fld = ffn.getField();
631 if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
632 og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
636 case FKind.FlatSetFieldNode:
637 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
639 fld = fsfn.getField();
641 if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
642 og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
646 case FKind.FlatElementNode:
647 FlatElementNode fen = (FlatElementNode) fn;
650 if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
651 og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
655 case FKind.FlatSetElementNode:
656 FlatSetElementNode fsen = (FlatSetElementNode) fn;
659 if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
660 og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
665 FlatNew fnn = (FlatNew) fn;
667 if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
668 AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
669 og.assignTempEqualToNewAlloc(lhs, as);
674 FlatCall fc = (FlatCall) fn;
675 MethodDescriptor md = fc.getMethod();
676 FlatMethod flatm = state.getMethodFlat(md);
677 OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil);
679 if( md.isStatic() ) {
680 // a static method is simply always the same, makes life easy
681 ogMergeOfAllPossibleCalleeResults = og;
683 Set<Integer> aliasedParamIndices =
684 ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
685 MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
686 OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
688 if( onlyPossibleCallee == null ) {
689 // if this method context has never been analyzed just schedule it for analysis
690 // and skip over this call site for now
691 methodContextsToVisit.add( mcNew );
694 ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee);
698 // if the method descriptor is virtual, then there could be a
699 // set of possible methods that will actually be invoked, so
700 // find all of them and merge all of their results together
701 TypeDescriptor typeDesc = fc.getThis().getType();
702 Set possibleCallees = callGraph.getMethods(md, typeDesc);
704 Iterator i = possibleCallees.iterator();
705 while( i.hasNext() ) {
706 MethodDescriptor possibleMd = (MethodDescriptor) i.next();
707 FlatMethod pflatm = state.getMethodFlat(possibleMd);
709 // don't alter the working graph (og) until we compute a result for every
710 // possible callee, merge them all together, then set og to that
711 OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
714 Set<Integer> aliasedParamIndices =
715 ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
716 MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
717 OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
719 if( ogPotentialCallee == null ) {
720 // if this method context has never been analyzed just schedule it for analysis
721 // and skip over this call site for now
722 methodContextsToVisit.add( mcNew );
725 ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee);
728 ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
732 og = ogMergeOfAllPossibleCalleeResults;
735 case FKind.FlatReturnNode:
736 FlatReturnNode frn = (FlatReturnNode) fn;
737 rhs = frn.getReturnTemp();
738 if( rhs != null && !rhs.getType().isImmutable() ) {
739 og.assignReturnEqualToTemp(rhs);
741 setRetNodes.add(frn);
749 // insert a call to debugSnapshot() somewhere in the analysis to get
750 // successive captures of the analysis state
751 int debugCounter = 0;
752 int numStartCountReport = 0;
753 int freqCountReport = 1000;
754 int iterStartCapture = 20000;
755 int numIterToCapture = 400;
756 void debugSnapshot(OwnershipGraph og, FlatNode fn) {
758 if( debugCounter > numStartCountReport &&
759 debugCounter % freqCountReport == 0 ) {
760 System.out.println(" @@@ debug counter = "+debugCounter);
762 if( debugCounter > iterStartCapture ) {
763 System.out.println(" @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
764 String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
766 graphName = graphName+fn;
769 og.writeGraph(graphName, true, true, false, false, false);
770 } catch( Exception e ) {
771 System.out.println("Error writing debug capture.");
775 if( debugCounter == iterStartCapture + numIterToCapture ) {
776 System.out.println("Stopping analysis after debug captures.");
783 // this method should generate integers strictly greater than zero!
784 // special "shadow" regions are made from a heap region by negating
786 static public Integer generateUniqueHeapRegionNodeID() {
788 return new Integer(uniqueIDcount);
792 private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og)
795 mapMethodContextToCompleteOwnershipGraph.put(mc, og);
797 // arguments to writeGraph are:
798 // boolean writeLabels,
799 // boolean labelSelect,
800 // boolean pruneGarbage,
801 // boolean writeReferencers
802 // boolean writeParamMappings
806 if( !writeAllDOTs ) {
807 og.writeGraph(mc, true, true, true, false, false);
810 if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
811 mapMethodContextToNumUpdates.put(mc, new Integer(0) );
813 Integer n = mapMethodContextToNumUpdates.get(mc);
814 og.writeGraph(mc, n, true, true, true, false, false);
815 mapMethodContextToNumUpdates.put(mc, n + 1);
821 // return just the allocation site associated with one FlatNew node
822 private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
824 if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
825 AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
827 // the newest nodes are single objects
828 for( int i = 0; i < allocationDepth; ++i ) {
829 Integer id = generateUniqueHeapRegionNodeID();
830 as.setIthOldest(i, id);
833 // the oldest node is a summary node
834 Integer idSummary = generateUniqueHeapRegionNodeID();
835 as.setSummary(idSummary);
837 mapFlatNewToAllocationSite.put(fn, as);
840 return mapFlatNewToAllocationSite.get(fn);
844 // return all allocation sites in the method (there is one allocation
845 // site per FlatNew node in a method)
846 private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
847 if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
848 buildAllocationSiteSet(d);
851 return mapDescriptorToAllocationSiteSet.get(d);
855 private void buildAllocationSiteSet(Descriptor d) {
856 HashSet<AllocationSite> s = new HashSet<AllocationSite>();
859 if( d instanceof MethodDescriptor ) {
860 fm = state.getMethodFlat( (MethodDescriptor) d);
862 assert d instanceof TaskDescriptor;
863 fm = state.getMethodFlat( (TaskDescriptor) d);
866 // visit every node in this FlatMethod's IR graph
867 // and make a set of the allocation sites from the
868 // FlatNew node's visited
869 HashSet<FlatNode> visited = new HashSet<FlatNode>();
870 HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
873 while( !toVisit.isEmpty() ) {
874 FlatNode n = toVisit.iterator().next();
876 if( n instanceof FlatNew ) {
877 s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
883 for( int i = 0; i < n.numNext(); ++i ) {
884 FlatNode child = n.getNext(i);
885 if( !visited.contains(child) ) {
891 mapDescriptorToAllocationSiteSet.put(d, s);
895 private HashSet<AllocationSite>
896 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
898 HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
899 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
900 HashSet<Descriptor> visited = new HashSet<Descriptor>();
904 // traverse this task and all methods reachable from this task
905 while( !toVisit.isEmpty() ) {
906 Descriptor d = toVisit.iterator().next();
910 HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
911 Iterator asItr = asSet.iterator();
912 while( asItr.hasNext() ) {
913 AllocationSite as = (AllocationSite) asItr.next();
914 TypeDescriptor typed = as.getType();
915 if( typed != null ) {
916 ClassDescriptor cd = typed.getClassDesc();
917 if( cd != null && cd.hasFlags() ) {
923 // enqueue callees of this method to be searched for
924 // allocation sites also
925 Set callees = callGraph.getCalleeSet(d);
926 if( callees != null ) {
927 Iterator methItr = callees.iterator();
928 while( methItr.hasNext() ) {
929 MethodDescriptor md = (MethodDescriptor) methItr.next();
931 if( !visited.contains(md) ) {