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 checkAnalysisComplete();
24 return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
27 public AllocationSite getAllocationSiteFromFlatNew(FlatNew fn) {
28 checkAnalysisComplete();
29 return getAllocationSiteFromFlatNewPRIVATE(fn);
32 public AllocationSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
33 checkAnalysisComplete();
34 return mapHrnIdToAllocationSite.get(id);
37 public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
40 checkAnalysisComplete();
41 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
43 return og.hasPotentialAlias(paramIndex1, paramIndex2);
46 public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
48 AllocationSite alloc) {
49 checkAnalysisComplete();
50 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
52 return og.hasPotentialAlias(paramIndex, alloc);
55 public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
58 checkAnalysisComplete();
59 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
61 return og.hasPotentialAlias(paramIndex, alloc);
64 public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
65 AllocationSite alloc1,
66 AllocationSite alloc2) {
67 checkAnalysisComplete();
68 OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
70 return og.hasPotentialAlias(alloc1, alloc2);
74 protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) {
75 checkAnalysisComplete();
79 OwnershipGraph og = new OwnershipGraph( allocationDepth, typeUtil );
81 assert mapDescriptorToAllMethodContexts.containsKey( d );
82 HashSet<MethodContext> contexts = mapDescriptorToAllMethodContexts.get( d );
83 Iterator<MethodContext> mcItr = contexts.iterator();
84 while( mcItr.hasNext() ) {
85 MethodContext mc = mcItr.next();
87 OwnershipGraph ogContext = mapMethodContextToCompleteOwnershipGraph.get(mc);
88 assert ogContext != null;
90 og.merge( ogContext );
97 public String prettyPrintNodeSet( Set<HeapRegionNode> s ) {
98 checkAnalysisComplete();
102 Iterator<HeapRegionNode> i = s.iterator();
103 while( i.hasNext() ) {
104 HeapRegionNode n = i.next();
106 AllocationSite as = n.getAllocationSite();
108 out += " "+n.toString()+",\n";
110 out += " "+n.toString()+": "+as.toStringVerbose()+",\n";
119 // use the methods given above to check every possible alias
120 // between task parameters and flagged allocation sites reachable
122 public void writeAllAliases(String outputFile, String timeReport) throws java.io.IOException {
123 checkAnalysisComplete();
125 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
127 bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
128 bw.write(timeReport+"\n");
130 // look through every task for potential aliases
131 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
132 while( taskItr.hasNext() ) {
133 TaskDescriptor td = (TaskDescriptor) taskItr.next();
135 bw.write("\n---------"+td+"--------\n");
137 HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
139 Set<HeapRegionNode> common;
141 // for each task parameter, check for aliases with
142 // other task parameters and every allocation site
143 // reachable from this task
144 boolean foundSomeAlias = false;
146 FlatMethod fm = state.getMethodFlat(td);
147 for( int i = 0; i < fm.numParameters(); ++i ) {
149 // for the ith parameter check for aliases to all
150 // higher numbered parameters
151 for( int j = i + 1; j < fm.numParameters(); ++j ) {
152 common = createsPotentialAliases(td, i, j);
153 if( !common.isEmpty() ) {
154 foundSomeAlias = true;
155 bw.write("Potential alias between parameters "+i+" and "+j+".\n");
156 bw.write(prettyPrintNodeSet( common )+"\n" );
160 // for the ith parameter, check for aliases against
161 // the set of allocation sites reachable from this
163 Iterator allocItr = allocSites.iterator();
164 while( allocItr.hasNext() ) {
165 AllocationSite as = (AllocationSite) allocItr.next();
166 common = createsPotentialAliases(td, i, as);
167 if( !common.isEmpty() ) {
168 foundSomeAlias = true;
169 bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
170 bw.write(prettyPrintNodeSet( common )+"\n" );
175 // for each allocation site check for aliases with
176 // other allocation sites in the context of execution
178 HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
179 Iterator allocItr1 = allocSites.iterator();
180 while( allocItr1.hasNext() ) {
181 AllocationSite as1 = (AllocationSite) allocItr1.next();
183 Iterator allocItr2 = allocSites.iterator();
184 while( allocItr2.hasNext() ) {
185 AllocationSite as2 = (AllocationSite) allocItr2.next();
187 if( !outerChecked.contains(as2) ) {
188 common = createsPotentialAliases(td, as1, as2);
190 if( !common.isEmpty() ) {
191 foundSomeAlias = true;
192 bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
193 bw.write(prettyPrintNodeSet( common )+"\n" );
198 outerChecked.add(as1);
201 if( !foundSomeAlias ) {
202 bw.write("No aliases between flagged objects in Task "+td+".\n");
206 bw.write( "\n"+computeAliasContextHistogram() );
211 // this version of writeAllAliases is for Java programs that have no tasks
212 public void writeAllAliasesJava(String outputFile, String timeReport) throws java.io.IOException {
213 checkAnalysisComplete();
217 BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
219 bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
220 bw.write(timeReport+"\n\n");
222 boolean foundSomeAlias = false;
224 Descriptor d = typeUtil.getMain();
225 HashSet<AllocationSite> allocSites = getFlaggedAllocationSites(d);
227 // for each allocation site check for aliases with
228 // other allocation sites in the context of execution
230 HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
231 Iterator allocItr1 = allocSites.iterator();
232 while( allocItr1.hasNext() ) {
233 AllocationSite as1 = (AllocationSite) allocItr1.next();
235 Iterator allocItr2 = allocSites.iterator();
236 while( allocItr2.hasNext() ) {
237 AllocationSite as2 = (AllocationSite) allocItr2.next();
239 if( !outerChecked.contains(as2) ) {
240 Set<HeapRegionNode> common = createsPotentialAliases(d, as1, as2);
242 if( !common.isEmpty() ) {
243 foundSomeAlias = true;
244 bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n");
245 bw.write( prettyPrintNodeSet( common )+"\n" );
250 outerChecked.add(as1);
253 if( !foundSomeAlias ) {
254 bw.write("No aliases between flagged objects found.\n");
257 bw.write( "\n"+computeAliasContextHistogram() );
260 ///////////////////////////////////////////
262 // end public interface
264 ///////////////////////////////////////////
266 protected void checkAnalysisComplete() {
267 if( !analysisComplete ) {
268 throw new Error("Warning: public interface method called while analysis is running.");
276 // data from the compiler
278 public CallGraph callGraph;
279 public TypeUtil typeUtil;
280 public int allocationDepth;
282 // for public interface methods to warn that they
283 // are grabbing results during analysis
284 private boolean analysisComplete;
286 // used to identify HeapRegionNode objects
287 // A unique ID equates an object in one
288 // ownership graph with an object in another
289 // graph that logically represents the same
291 // start at 10 and increment to leave some
292 // reserved IDs for special purposes
293 static private int uniqueIDcount = 10;
295 // Use these data structures to track progress of
296 // processing all methods in the program, and by methods
297 // TaskDescriptor and MethodDescriptor are combined
298 // together, with a common parent class Descriptor
299 private Hashtable<MethodContext, OwnershipGraph> mapMethodContextToInitialParamAllocGraph;
300 private Hashtable<MethodContext, OwnershipGraph> mapMethodContextToCompleteOwnershipGraph;
301 private Hashtable<FlatNew, AllocationSite> mapFlatNewToAllocationSite;
302 private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
303 private Hashtable<MethodContext, Integer> mapMethodContextToNumUpdates;
304 private Hashtable<Descriptor, HashSet<MethodContext> > mapDescriptorToAllMethodContexts;
305 private Hashtable<MethodContext, HashSet<MethodContext> > mapMethodContextToDependentContexts;
306 private Hashtable<Integer, AllocationSite> mapHrnIdToAllocationSite;
308 // Use these data structures to track progress of one pass of
309 // processing the FlatNodes of a particular method
310 private HashSet <FlatNode> flatNodesToVisit;
311 private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
312 private HashSet <FlatReturnNode> returnNodesToCombineForCompleteOwnershipGraph;
314 // descriptorsToAnalyze identifies the set of tasks and methods
315 // that are reachable from the program tasks, this set is initialized
316 // and then remains static
317 public HashSet<Descriptor> descriptorsToAnalyze;
319 // descriptorsToVisit is initialized to descriptorsToAnalyze and is
320 // reduced by visiting a descriptor during analysis. When dependents
321 // must be scheduled, only those contained in descriptorsToAnalyze
322 // should be re-added to this queue
323 private PriorityQueue<MethodContextQWrapper> methodContextsToVisitQ;
324 private Set <MethodContext> methodContextsToVisitSet;
325 private Hashtable<Descriptor, Integer> mapDescriptorToPriority;
328 // special field descriptors for array elements
329 public static final String arrayElementFieldName = "___element_";
330 private static Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField =
331 new Hashtable<TypeDescriptor, FieldDescriptor>();
334 // for controlling DOT file output
335 private boolean writeDOTs;
336 private boolean writeAllDOTs;
338 // for controlling method effects
339 private boolean methodEffects;
341 //map each FlatNode to its own internal ownership graph
342 private MethodEffectsAnalysis meAnalysis;
344 //keep internal ownership graph by method context and flat node
345 private Hashtable<MethodContext, Hashtable<FlatNode, OwnershipGraph>> mapMethodContextToFlatNodeOwnershipGraph;
347 //map method context to a set of allocation sites of live-in vars
348 private Hashtable<MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet;
352 // this analysis generates an ownership graph for every task
354 public OwnershipAnalysis(State state,
359 boolean writeAllDOTs,
360 String aliasFile) throws java.io.IOException {
362 this.methodEffects = false;
363 init(state,tu,callGraph,allocationDepth,writeDOTs,writeAllDOTs,aliasFile);
367 public OwnershipAnalysis(State state,
372 boolean writeAllDOTs,
374 boolean methodEffects) throws java.io.IOException {
376 this.methodEffects = methodEffects;
377 init(state,tu,callGraph,allocationDepth,writeDOTs,writeAllDOTs,aliasFile);
381 // new constructor for on-demand disjoint analysis
382 public OwnershipAnalysis(
388 boolean writeAllDOTs,
390 boolean methodEffects,
391 Hashtable<MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet)
392 throws java.io.IOException {
394 this.methodEffects = methodEffects;
395 this.mapMethodContextToLiveInAllocationSiteSet=mapMethodContextToLiveInAllocationSiteSet;
396 init(state, tu, callGraph, allocationDepth, writeDOTs, writeAllDOTs,
401 private void init(State state,
406 boolean writeAllDOTs,
407 String aliasFile) throws java.io.IOException {
409 analysisComplete = false;
413 this.callGraph = callGraph;
414 this.allocationDepth = allocationDepth;
415 this.writeDOTs = writeDOTs;
416 this.writeAllDOTs = writeAllDOTs;
418 descriptorsToAnalyze = new HashSet<Descriptor>();
420 mapMethodContextToInitialParamAllocGraph =
421 new Hashtable<MethodContext, OwnershipGraph>();
423 mapMethodContextToCompleteOwnershipGraph =
424 new Hashtable<MethodContext, OwnershipGraph>();
426 mapFlatNewToAllocationSite =
427 new Hashtable<FlatNew, AllocationSite>();
429 mapDescriptorToAllocationSiteSet =
430 new Hashtable<Descriptor, HashSet<AllocationSite> >();
432 mapDescriptorToAllMethodContexts =
433 new Hashtable<Descriptor, HashSet<MethodContext> >();
435 mapMethodContextToDependentContexts =
436 new Hashtable<MethodContext, HashSet<MethodContext> >();
438 mapDescriptorToPriority =
439 new Hashtable<Descriptor, Integer>();
441 mapHrnIdToAllocationSite =
442 new Hashtable<Integer, AllocationSite>();
444 mapMethodContextToFlatNodeOwnershipGraph=new Hashtable<MethodContext, Hashtable<FlatNode, OwnershipGraph>>();
446 meAnalysis=new MethodEffectsAnalysis(methodEffects);
450 mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
454 double timeStartAnalysis = (double) System.nanoTime();
458 // initialize methods to visit as the set of all tasks in the
459 // program and then any method that could be called starting
461 Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
462 while( taskItr.hasNext() ) {
463 Descriptor d = (Descriptor) taskItr.next();
464 scheduleAllCallees(d);
468 // we are not in task mode, just normal Java, so start with
470 Descriptor d = typeUtil.getMain();
471 scheduleAllCallees(d);
475 // before beginning analysis, initialize every scheduled method
476 // with an ownership graph that has populated parameter index tables
477 // by analyzing the first node which is always a FlatMethod node
478 Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
479 while( dItr.hasNext() ) {
480 Descriptor d = dItr.next();
481 OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
484 if( d instanceof MethodDescriptor ) {
485 fm = state.getMethodFlat( (MethodDescriptor) d);
487 assert d instanceof TaskDescriptor;
488 fm = state.getMethodFlat( (TaskDescriptor) d);
491 MethodContext mc = new MethodContext( d );
492 assert !mapDescriptorToAllMethodContexts.containsKey( d );
493 HashSet<MethodContext> s = new HashSet<MethodContext>();
495 mapDescriptorToAllMethodContexts.put( d, s );
497 //System.out.println("Previsiting " + mc);
499 meAnalysis.createNewMapping(mc);
501 og = analyzeFlatNode(mc, fm, null, og);
502 setGraphForMethodContext(mc, og);
505 // as mentioned above, analyze methods one-by-one, possibly revisiting
506 // a method if the methods that it calls are updated
508 analysisComplete = true;
511 double timeEndAnalysis = (double) System.nanoTime();
512 double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
513 String treport = String.format( "The reachability analysis took %.3f sec.", dt );
514 System.out.println( treport );
516 if( writeDOTs && !writeAllDOTs ) {
517 writeFinalContextGraphs();
521 meAnalysis.writeMethodEffectsResult();
524 if( aliasFile != null ) {
526 writeAllAliases(aliasFile, treport);
528 writeAllAliasesJava(aliasFile, treport);
534 // called from the constructor to help initialize the set
535 // of methods that needs to be analyzed by ownership analysis
536 private void scheduleAllCallees(Descriptor d) {
537 if( descriptorsToAnalyze.contains(d) ) {
540 descriptorsToAnalyze.add(d);
542 // start with all method calls to further schedule
543 Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
545 if( d instanceof MethodDescriptor ) {
546 // see if this method has virtual dispatch
547 Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
548 moreMethodsToCheck.addAll(virtualMethods);
551 // keep following any further methods identified in
553 Iterator methItr = moreMethodsToCheck.iterator();
554 while( methItr.hasNext() ) {
555 Descriptor m = (Descriptor) methItr.next();
556 scheduleAllCallees(m);
561 // manage the set of tasks and methods to be analyzed
562 // and be sure to reschedule tasks/methods when the methods
563 // they call are updated
564 private void analyzeMethods() throws java.io.IOException {
566 // first gather all of the method contexts to analyze
567 HashSet<MethodContext> allContexts = new HashSet<MethodContext>();
568 Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
569 while( itrd2a.hasNext() ) {
570 HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
573 Iterator<MethodContext> itrmc = mcs.iterator();
574 while( itrmc.hasNext() ) {
575 allContexts.add( itrmc.next() );
579 // topologically sort them according to the caller graph so leaf calls are
580 // ordered first; use that ordering to give method contexts priorities
581 LinkedList<MethodContext> sortedMethodContexts = topologicalSort( allContexts );
583 methodContextsToVisitQ = new PriorityQueue<MethodContextQWrapper>();
584 methodContextsToVisitSet = new HashSet<MethodContext>();
587 Iterator<MethodContext> mcItr = sortedMethodContexts.iterator();
588 while( mcItr.hasNext() ) {
589 MethodContext mc = mcItr.next();
590 mapDescriptorToPriority.put( mc.getDescriptor(), new Integer( p ) );
591 methodContextsToVisitQ.add( new MethodContextQWrapper( p, mc ) );
592 methodContextsToVisitSet.add( mc );
596 // analyze methods from the priority queue until it is empty
597 while( !methodContextsToVisitQ.isEmpty() ) {
598 MethodContext mc = methodContextsToVisitQ.poll().getMethodContext();
599 assert methodContextsToVisitSet.contains( mc );
600 methodContextsToVisitSet.remove( mc );
602 // because the task or method descriptor just extracted
603 // was in the "to visit" set it either hasn't been analyzed
604 // yet, or some method that it depends on has been
605 // updated. Recompute a complete ownership graph for
606 // this task/method and compare it to any previous result.
607 // If there is a change detected, add any methods/tasks
608 // that depend on this one to the "to visit" set.
610 System.out.println("Analyzing " + mc);
612 Descriptor d = mc.getDescriptor();
614 if( d instanceof MethodDescriptor ) {
615 fm = state.getMethodFlat( (MethodDescriptor) d);
617 assert d instanceof TaskDescriptor;
618 fm = state.getMethodFlat( (TaskDescriptor) d);
621 OwnershipGraph og = analyzeFlatMethod(mc, fm);
622 OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
623 if( !og.equals(ogPrev) ) {
624 setGraphForMethodContext(mc, og);
626 Iterator<MethodContext> depsItr = iteratorDependents( mc );
627 while( depsItr.hasNext() ) {
628 MethodContext mcNext = depsItr.next();
630 if( !methodContextsToVisitSet.contains( mcNext ) ) {
631 methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( mcNext.getDescriptor() ),
633 methodContextsToVisitSet.add( mcNext );
642 // keep passing the Descriptor of the method along for debugging
643 // and dot file writing
644 private OwnershipGraph
645 analyzeFlatMethod(MethodContext mc,
646 FlatMethod flatm) throws java.io.IOException {
648 // initialize flat nodes to visit as the flat method
649 // because it is the entry point
651 flatNodesToVisit = new HashSet<FlatNode>();
652 flatNodesToVisit.add(flatm);
654 // initilize the mapping of flat nodes in this flat method to
655 // ownership graph results to an empty mapping
656 mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
658 // initialize the set of return nodes that will be combined as
659 // the final ownership graph result to return as an empty set
660 returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
663 while( !flatNodesToVisit.isEmpty() ) {
664 FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
665 flatNodesToVisit.remove(fn);
667 //System.out.println( " "+fn );
669 // perform this node's contributions to the ownership
670 // graph on a new copy, then compare it to the old graph
671 // at this node to see if anything was updated.
672 OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
674 // start by merging all node's parents' graphs
675 for( int i = 0; i < fn.numPrev(); ++i ) {
676 FlatNode pn = fn.getPrev(i);
677 if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
678 OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
683 // apply the analysis of the flat node to the
684 // ownership graph made from the merge of the
686 og = analyzeFlatNode(mc,
688 returnNodesToCombineForCompleteOwnershipGraph,
694 if( takeDebugSnapshots &&
695 mc.getDescriptor().getSymbol().equals( mcDescSymbolDebug ) ) {
696 debugSnapshot(og,fn);
701 // if the results of the new graph are different from
702 // the current graph at this node, replace the graph
703 // with the update and enqueue the children for
705 OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
706 if( !og.equals(ogPrev) ) {
707 mapFlatNodeToOwnershipGraph.put(fn, og);
709 for( int i = 0; i < fn.numNext(); i++ ) {
710 FlatNode nn = fn.getNext(i);
711 flatNodesToVisit.add(nn);
716 // end by merging all return nodes into a complete
717 // ownership graph that represents all possible heap
718 // states after the flat method returns
719 OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil);
720 Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
721 while( retItr.hasNext() ) {
722 FlatReturnNode frn = (FlatReturnNode) retItr.next();
723 assert mapFlatNodeToOwnershipGraph.containsKey(frn);
724 OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
725 completeGraph.merge(ogr);
728 return completeGraph;
732 private OwnershipGraph
733 analyzeFlatNode(MethodContext mc,
735 HashSet<FlatReturnNode> setRetNodes,
736 OwnershipGraph og) throws java.io.IOException {
742 // use node type to decide what alterations to make
743 // to the ownership graph
744 switch( fn.kind() ) {
746 case FKind.FlatMethod:
747 FlatMethod fm = (FlatMethod) fn;
749 // there should only be one FlatMethod node as the
750 // parent of all other FlatNode objects, so take
751 // the opportunity to construct the initial graph by
752 // adding parameters labels to new heap regions
753 // AND this should be done once globally so that the
754 // parameter IDs are consistent between analysis
755 // iterations, so if this step has been done already
756 // just merge in the cached version
757 OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
758 if( ogInitParamAlloc == null ) {
760 // if the method context has aliased parameters, make sure
761 // there is a blob region for all those param to reference
762 Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
764 if( !aliasedParamIndices.isEmpty() ) {
765 og.makeAliasedParamHeapRegionNode();
768 // set up each parameter
769 for( int i = 0; i < fm.numParameters(); ++i ) {
770 TempDescriptor tdParam = fm.getParameter( i );
771 TypeDescriptor typeParam = tdParam.getType();
772 Integer paramIndex = new Integer( i );
774 if( typeParam.isImmutable() && !typeParam.isArray() ) {
775 // don't bother with this primitive parameter, it
776 // cannot affect reachability
780 if( aliasedParamIndices.contains( paramIndex ) ) {
781 // use the alias blob but give parameters their
782 // own primary obj region
783 og.assignTempEqualToAliasedParam( tdParam,
786 // this parameter is not aliased to others, give it
787 // a fresh primary obj and secondary object
788 og.assignTempEqualToParamAlloc( tdParam,
789 mc.getDescriptor() instanceof TaskDescriptor,
794 // add additional edges for aliased regions if necessary
795 if( !aliasedParamIndices.isEmpty() ) {
796 og.addParam2ParamAliasEdges( fm, aliasedParamIndices );
799 // clean up reachability on initial parameter shapes
802 // this maps tokens to parameter indices and vice versa
803 // for when this method is a callee
804 og.prepareParamTokenMaps( fm );
807 OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
809 mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
812 // or just leverage the cached copy
813 og.merge(ogInitParamAlloc);
817 case FKind.FlatOpNode:
818 FlatOpNode fon = (FlatOpNode) fn;
819 if( fon.getOp().getOp() == Operation.ASSIGN ) {
822 og.assignTempXEqualToTempY(lhs, rhs);
826 case FKind.FlatCastNode:
827 FlatCastNode fcn = (FlatCastNode) fn;
831 TypeDescriptor td = fcn.getType();
834 og.assignTypedTempXEqualToTempY(lhs, rhs, td);
837 case FKind.FlatFieldNode:
838 FlatFieldNode ffn = (FlatFieldNode) fn;
841 fld = ffn.getField();
842 if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
843 og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
846 meAnalysis.analyzeFlatFieldNode(mc, og, rhs, fld);
850 case FKind.FlatSetFieldNode:
851 FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
853 fld = fsfn.getField();
855 if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
856 og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
859 meAnalysis.analyzeFlatSetFieldNode(mc, og, lhs, fld);
863 case FKind.FlatElementNode:
864 FlatElementNode fen = (FlatElementNode) fn;
867 if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
869 assert rhs.getType() != null;
870 assert rhs.getType().isArray();
872 TypeDescriptor tdElement = rhs.getType().dereference();
873 FieldDescriptor fdElement = getArrayField( tdElement );
875 og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
879 case FKind.FlatSetElementNode:
880 FlatSetElementNode fsen = (FlatSetElementNode) fn;
883 if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
885 assert lhs.getType() != null;
886 assert lhs.getType().isArray();
888 TypeDescriptor tdElement = lhs.getType().dereference();
889 FieldDescriptor fdElement = getArrayField( tdElement );
891 og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
896 FlatNew fnn = (FlatNew) fn;
898 if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
899 AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
901 if (mapMethodContextToLiveInAllocationSiteSet != null){
902 HashSet<AllocationSite> alllocSet=mapMethodContextToLiveInAllocationSiteSet.get(mc);
904 for (Iterator iterator = alllocSet.iterator(); iterator
906 AllocationSite allocationSite = (AllocationSite) iterator
908 if(allocationSite.flatNew.equals(as.flatNew)){
915 og.assignTempEqualToNewAlloc(lhs, as);
920 FlatCall fc = (FlatCall) fn;
921 MethodDescriptor md = fc.getMethod();
922 FlatMethod flatm = state.getMethodFlat(md);
923 OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil);
925 if( md.isStatic() ) {
926 // a static method is simply always the same, makes life easy
927 ogMergeOfAllPossibleCalleeResults = og;
929 Set<Integer> aliasedParamIndices =
930 ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
932 MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
933 Set contexts = mapDescriptorToAllMethodContexts.get( md );
934 assert contexts != null;
935 contexts.add( mcNew );
937 addDependent( mc, mcNew );
939 OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
941 if( onlyPossibleCallee == null ) {
942 // if this method context has never been analyzed just schedule it for analysis
943 // and skip over this call site for now
944 if( !methodContextsToVisitSet.contains( mcNew ) ) {
945 methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
947 methodContextsToVisitSet.add( mcNew );
951 ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc, null);
954 meAnalysis.createNewMapping(mcNew);
955 meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
959 // if the method descriptor is virtual, then there could be a
960 // set of possible methods that will actually be invoked, so
961 // find all of them and merge all of their results together
962 TypeDescriptor typeDesc = fc.getThis().getType();
963 Set possibleCallees = callGraph.getMethods(md, typeDesc);
965 Iterator i = possibleCallees.iterator();
966 while( i.hasNext() ) {
967 MethodDescriptor possibleMd = (MethodDescriptor) i.next();
968 FlatMethod pflatm = state.getMethodFlat(possibleMd);
970 // don't alter the working graph (og) until we compute a result for every
971 // possible callee, merge them all together, then set og to that
972 OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
975 Set<Integer> aliasedParamIndices =
976 ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
978 MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
979 Set contexts = mapDescriptorToAllMethodContexts.get( md );
980 assert contexts != null;
981 contexts.add( mcNew );
984 meAnalysis.createNewMapping(mcNew);
987 addDependent( mc, mcNew );
989 OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
991 if( ogPotentialCallee == null ) {
992 // if this method context has never been analyzed just schedule it for analysis
993 // and skip over this call site for now
994 if( !methodContextsToVisitSet.contains( mcNew ) ) {
995 methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
997 methodContextsToVisitSet.add( mcNew );
1001 ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc, null);
1004 ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
1006 meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
1011 og = ogMergeOfAllPossibleCalleeResults;
1014 case FKind.FlatReturnNode:
1015 FlatReturnNode frn = (FlatReturnNode) fn;
1016 rhs = frn.getReturnTemp();
1017 if( rhs != null && !rhs.getType().isImmutable() ) {
1018 og.assignReturnEqualToTemp(rhs);
1020 setRetNodes.add(frn);
1024 Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(mc);
1026 table=new Hashtable<FlatNode, OwnershipGraph>();
1029 mapMethodContextToFlatNodeOwnershipGraph.put(mc, table);
1035 // this method should generate integers strictly greater than zero!
1036 // special "shadow" regions are made from a heap region by negating
1038 static public Integer generateUniqueHeapRegionNodeID() {
1040 return new Integer(uniqueIDcount);
1044 static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
1045 FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
1046 if( fdElement == null ) {
1047 fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
1049 arrayElementFieldName,
1052 mapTypeToArrayField.put( tdElement, fdElement );
1058 private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og) {
1060 mapMethodContextToCompleteOwnershipGraph.put(mc, og);
1062 if( writeDOTs && writeAllDOTs ) {
1063 if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
1064 mapMethodContextToNumUpdates.put(mc, new Integer(0) );
1066 Integer n = mapMethodContextToNumUpdates.get(mc);
1068 og.writeGraph(mc, n, true, true, true, false, false, true);
1069 } catch( IOException e ) {}
1070 mapMethodContextToNumUpdates.put(mc, n + 1);
1075 private void addDependent( MethodContext caller, MethodContext callee ) {
1076 HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1077 if( deps == null ) {
1078 deps = new HashSet<MethodContext>();
1081 mapMethodContextToDependentContexts.put( callee, deps );
1084 private Iterator<MethodContext> iteratorDependents( MethodContext callee ) {
1085 HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1086 if( deps == null ) {
1087 deps = new HashSet<MethodContext>();
1088 mapMethodContextToDependentContexts.put( callee, deps );
1090 return deps.iterator();
1094 private void writeFinalContextGraphs() {
1095 // arguments to writeGraph are:
1096 // boolean writeLabels,
1097 // boolean labelSelect,
1098 // boolean pruneGarbage,
1099 // boolean writeReferencers
1100 // boolean writeParamMappings
1101 // boolean hideSubsetReachability
1103 Set entrySet = mapMethodContextToCompleteOwnershipGraph.entrySet();
1104 Iterator itr = entrySet.iterator();
1105 while( itr.hasNext() ) {
1106 Map.Entry me = (Map.Entry) itr.next();
1107 MethodContext mc = (MethodContext) me.getKey();
1108 OwnershipGraph og = (OwnershipGraph) me.getValue();
1111 og.writeGraph(mc, true, true, true, false, false, true);
1112 } catch( IOException e ) {}
1118 // return just the allocation site associated with one FlatNew node
1119 private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
1121 if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
1122 AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
1124 // the newest nodes are single objects
1125 for( int i = 0; i < allocationDepth; ++i ) {
1126 Integer id = generateUniqueHeapRegionNodeID();
1127 as.setIthOldest(i, id);
1128 mapHrnIdToAllocationSite.put( id, as );
1131 // the oldest node is a summary node
1132 Integer idSummary = generateUniqueHeapRegionNodeID();
1133 as.setSummary(idSummary);
1135 mapFlatNewToAllocationSite.put(fn, as);
1138 return mapFlatNewToAllocationSite.get(fn);
1142 // return all allocation sites in the method (there is one allocation
1143 // site per FlatNew node in a method)
1144 private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
1145 if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
1146 buildAllocationSiteSet(d);
1149 return mapDescriptorToAllocationSiteSet.get(d);
1153 private void buildAllocationSiteSet(Descriptor d) {
1154 HashSet<AllocationSite> s = new HashSet<AllocationSite>();
1157 if( d instanceof MethodDescriptor ) {
1158 fm = state.getMethodFlat( (MethodDescriptor) d);
1160 assert d instanceof TaskDescriptor;
1161 fm = state.getMethodFlat( (TaskDescriptor) d);
1164 // visit every node in this FlatMethod's IR graph
1165 // and make a set of the allocation sites from the
1166 // FlatNew node's visited
1167 HashSet<FlatNode> visited = new HashSet<FlatNode>();
1168 HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1171 while( !toVisit.isEmpty() ) {
1172 FlatNode n = toVisit.iterator().next();
1174 if( n instanceof FlatNew ) {
1175 s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
1181 for( int i = 0; i < n.numNext(); ++i ) {
1182 FlatNode child = n.getNext(i);
1183 if( !visited.contains(child) ) {
1189 mapDescriptorToAllocationSiteSet.put(d, s);
1193 private HashSet<AllocationSite> getFlaggedAllocationSites(Descriptor dIn) {
1195 HashSet<AllocationSite> out = new HashSet<AllocationSite>();
1196 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
1197 HashSet<Descriptor> visited = new HashSet<Descriptor>();
1201 while( !toVisit.isEmpty() ) {
1202 Descriptor d = toVisit.iterator().next();
1206 HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1207 Iterator asItr = asSet.iterator();
1208 while( asItr.hasNext() ) {
1209 AllocationSite as = (AllocationSite) asItr.next();
1210 if( as.getDisjointId() != null ) {
1215 // enqueue callees of this method to be searched for
1216 // allocation sites also
1217 Set callees = callGraph.getCalleeSet(d);
1218 if( callees != null ) {
1219 Iterator methItr = callees.iterator();
1220 while( methItr.hasNext() ) {
1221 MethodDescriptor md = (MethodDescriptor) methItr.next();
1223 if( !visited.contains(md) ) {
1234 private HashSet<AllocationSite>
1235 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1237 HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
1238 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
1239 HashSet<Descriptor> visited = new HashSet<Descriptor>();
1243 // traverse this task and all methods reachable from this task
1244 while( !toVisit.isEmpty() ) {
1245 Descriptor d = toVisit.iterator().next();
1249 HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1250 Iterator asItr = asSet.iterator();
1251 while( asItr.hasNext() ) {
1252 AllocationSite as = (AllocationSite) asItr.next();
1253 TypeDescriptor typed = as.getType();
1254 if( typed != null ) {
1255 ClassDescriptor cd = typed.getClassDesc();
1256 if( cd != null && cd.hasFlags() ) {
1262 // enqueue callees of this method to be searched for
1263 // allocation sites also
1264 Set callees = callGraph.getCalleeSet(d);
1265 if( callees != null ) {
1266 Iterator methItr = callees.iterator();
1267 while( methItr.hasNext() ) {
1268 MethodDescriptor md = (MethodDescriptor) methItr.next();
1270 if( !visited.contains(md) ) {
1282 private LinkedList<MethodContext> topologicalSort( HashSet<MethodContext> set ) {
1283 HashSet <MethodContext> discovered = new HashSet <MethodContext>();
1284 LinkedList<MethodContext> sorted = new LinkedList<MethodContext>();
1286 Iterator<MethodContext> itr = set.iterator();
1287 while( itr.hasNext() ) {
1288 MethodContext mc = itr.next();
1290 if( !discovered.contains( mc ) ) {
1291 dfsVisit( set, mc, sorted, discovered );
1298 private void dfsVisit( HashSet<MethodContext> set,
1300 LinkedList<MethodContext> sorted,
1301 HashSet <MethodContext> discovered ) {
1302 discovered.add( mc );
1304 Descriptor d = mc.getDescriptor();
1305 if( d instanceof MethodDescriptor ) {
1306 MethodDescriptor md = (MethodDescriptor) d;
1307 Iterator itr = callGraph.getCallerSet( md ).iterator();
1308 while( itr.hasNext() ) {
1309 Descriptor dCaller = (Descriptor) itr.next();
1311 // only consider the callers in the original set to analyze
1312 Set<MethodContext> callerContexts = mapDescriptorToAllMethodContexts.get( dCaller );
1313 if( callerContexts == null )
1316 // since the analysis hasn't started, there should be exactly one
1317 // context if there are any at all
1318 assert callerContexts.size() == 1;
1319 MethodContext mcCaller = callerContexts.iterator().next();
1320 assert set.contains( mcCaller );
1322 if( !discovered.contains( mcCaller ) ) {
1323 dfsVisit( set, mcCaller, sorted, discovered );
1328 sorted.addFirst( mc );
1333 private String computeAliasContextHistogram() {
1335 Hashtable<Integer, Integer> mapNumContexts2NumDesc =
1336 new Hashtable<Integer, Integer>();
1338 Iterator itr = mapDescriptorToAllMethodContexts.entrySet().iterator();
1339 while( itr.hasNext() ) {
1340 Map.Entry me = (Map.Entry) itr.next();
1341 HashSet<MethodContext> s = (HashSet<MethodContext>) me.getValue();
1343 Integer i = mapNumContexts2NumDesc.get( s.size() );
1345 i = new Integer( 0 );
1347 mapNumContexts2NumDesc.put( s.size(), i + 1 );
1353 itr = mapNumContexts2NumDesc.entrySet().iterator();
1354 while( itr.hasNext() ) {
1355 Map.Entry me = (Map.Entry) itr.next();
1356 Integer c0 = (Integer) me.getKey();
1357 Integer d0 = (Integer) me.getValue();
1359 s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
1362 s += String.format( "\n%4d total methods analayzed.\n", total );
1370 // insert a call to debugSnapshot() somewhere in the analysis
1371 // to get successive captures of the analysis state
1372 boolean takeDebugSnapshots = false;
1373 String mcDescSymbolDebug = "addFirst";
1374 boolean stopAfterCapture = true;
1376 // increments every visit to debugSnapshot, don't fiddle with it
1377 int debugCounter = 0;
1379 // the value of debugCounter to start reporting the debugCounter
1380 // to the screen to let user know what debug iteration we're at
1381 int numStartCountReport = 0;
1383 // the frequency of debugCounter values to print out, 0 no report
1384 int freqCountReport = 0;
1386 // the debugCounter value at which to start taking snapshots
1387 int iterStartCapture = 0;
1389 // the number of snapshots to take
1390 int numIterToCapture = 40;
1392 void debugSnapshot(OwnershipGraph og, FlatNode fn) {
1393 if( debugCounter > iterStartCapture + numIterToCapture ) {
1398 if( debugCounter > numStartCountReport &&
1399 freqCountReport > 0 &&
1400 debugCounter % freqCountReport == 0 ) {
1401 System.out.println(" @@@ debug counter = "+debugCounter);
1403 if( debugCounter > iterStartCapture ) {
1404 System.out.println(" @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
1405 String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
1407 graphName = graphName+fn;
1410 // arguments to writeGraph are:
1411 // boolean writeLabels,
1412 // boolean labelSelect,
1413 // boolean pruneGarbage,
1414 // boolean writeReferencers
1415 // boolean writeParamMappings
1417 //og.writeGraph(graphName, true, true, true, false, false);
1418 og.writeGraph(graphName, true, true, true, false, false);
1419 } catch( Exception e ) {
1420 System.out.println("Error writing debug capture.");
1425 if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) {
1426 System.out.println("Stopping analysis after debug captures.");
1431 public MethodEffectsAnalysis getMethodEffectsAnalysis(){
1435 public OwnershipGraph getOwnvershipGraphByMethodContext(MethodContext mc){
1436 return mapMethodContextToCompleteOwnershipGraph.get(mc);
1439 public HashSet<MethodContext> getAllMethodContextSetByDescriptor(Descriptor d){
1440 return mapDescriptorToAllMethodContexts.get(d);
1443 public MethodContext getCalleeMethodContext(MethodContext callerMC, FlatCall fc){
1445 Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(callerMC);
1447 // merge previous ownership graph to calculate corresponding method context
1448 OwnershipGraph mergeOG = new OwnershipGraph( allocationDepth, typeUtil );
1450 for(int i=0;i<fc.numPrev();i++){
1451 FlatNode prevNode=fc.getPrev(i);
1453 OwnershipGraph prevOG=table.get(prevNode);
1454 mergeOG.merge(prevOG);
1458 MethodDescriptor md=fc.getMethod();
1459 FlatMethod flatm = state.getMethodFlat(md);
1460 Set<Integer> aliasedParamIndices = mergeOG.calculateAliasedParamSet(fc, md.isStatic(), flatm);
1461 MethodContext calleeMC = new MethodContext( md, aliasedParamIndices );