little changes to keep, debugging removed
[IRC.git] / Robust / src / Analysis / OwnershipAnalysis / OwnershipAnalysis.java
1 package Analysis.OwnershipAnalysis;
2
3 import Analysis.CallGraph.*;
4 import IR.*;
5 import IR.Flat.*;
6 import IR.Tree.Modifiers;
7 import java.util.*;
8 import java.io.*;
9
10
11 public class OwnershipAnalysis {
12
13
14   ///////////////////////////////////////////
15   //
16   //  Public interface to discover possible
17   //  aliases in the program under analysis
18   //
19   ///////////////////////////////////////////
20
21   public HashSet<AllocationSite>
22   getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
23     checkAnalysisComplete();
24     return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
25   }
26
27   public AllocationSite getAllocationSiteFromFlatNew(FlatNew fn) {
28     checkAnalysisComplete();
29     return getAllocationSiteFromFlatNewPRIVATE(fn);
30   }
31
32   public AllocationSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
33     checkAnalysisComplete();
34     return mapHrnIdToAllocationSite.get(id);
35   }
36
37   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
38                                          int paramIndex1,
39                                          int paramIndex2) {
40     checkAnalysisComplete();
41     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
42     assert(og != null);
43     return og.hasPotentialAlias(paramIndex1, paramIndex2);
44   }
45
46   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
47                                          int paramIndex,
48                                          AllocationSite alloc) {
49     checkAnalysisComplete();
50     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
51     assert(og != null);
52     return og.hasPotentialAlias(paramIndex, alloc);
53   }
54
55   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
56                                          AllocationSite alloc,
57                                          int paramIndex) {
58     checkAnalysisComplete();
59     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
60     assert(og != null);
61     return og.hasPotentialAlias(paramIndex, alloc);
62   }
63
64   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
65                                          AllocationSite alloc1,
66                                          AllocationSite alloc2) {
67     checkAnalysisComplete();
68     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
69     assert(og != null);
70     return og.hasPotentialAlias(alloc1, alloc2);
71   }
72
73
74   protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) {
75     checkAnalysisComplete();
76
77     assert d != null;
78
79     OwnershipGraph og = new OwnershipGraph();
80
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();
86
87       OwnershipGraph ogContext = mapMethodContextToCompleteOwnershipGraph.get(mc);
88       assert ogContext != null;
89
90       og.merge( ogContext );
91     }
92
93     return og;
94   }
95
96
97   public String prettyPrintNodeSet( Set<HeapRegionNode> s ) {    
98     checkAnalysisComplete();
99
100     String out = "{\n";
101
102     Iterator<HeapRegionNode> i = s.iterator();
103     while( i.hasNext() ) {
104       HeapRegionNode n = i.next();
105
106       AllocationSite as = n.getAllocationSite();
107       if( as == null ) {
108         out += "  "+n.toString()+",\n";
109       } else {
110         out += "  "+n.toString()+": "+as.toStringVerbose()+",\n";
111       }
112     }
113
114     out += "}\n";
115     return out;
116   }
117
118
119   // use the methods given above to check every possible alias
120   // between task parameters and flagged allocation sites reachable
121   // from the task
122   public void writeAllAliases(String outputFile, 
123                               String timeReport,
124                               String justTime,
125                               boolean tabularOutput,
126                               int numLines
127                               ) throws java.io.IOException {
128     checkAnalysisComplete();
129
130     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
131
132     if( !tabularOutput ) {
133       bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
134       bw.write(timeReport+"\n");
135     }
136     
137     int numAlias = 0;
138
139     // look through every task for potential aliases
140     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
141     while( taskItr.hasNext() ) {
142       TaskDescriptor td = (TaskDescriptor) taskItr.next();
143
144       if( !tabularOutput ) {
145         bw.write("\n---------"+td+"--------\n");
146       }
147
148       HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
149
150       Set<HeapRegionNode> common;
151       
152       // for each task parameter, check for aliases with
153       // other task parameters and every allocation site
154       // reachable from this task
155       boolean foundSomeAlias = false;
156
157       FlatMethod fm = state.getMethodFlat(td);
158       for( int i = 0; i < fm.numParameters(); ++i ) {
159
160         // for the ith parameter check for aliases to all
161         // higher numbered parameters
162         for( int j = i + 1; j < fm.numParameters(); ++j ) {
163           common = createsPotentialAliases(td, i, j);
164           if( !common.isEmpty() ) {
165             foundSomeAlias = true;
166             if( !tabularOutput ) {
167               bw.write("Potential alias between parameters "+i+" and "+j+".\n");
168               bw.write(prettyPrintNodeSet( common )+"\n" );
169             } else {
170               ++numAlias;
171             }
172           }
173         }
174         
175         // for the ith parameter, check for aliases against
176         // the set of allocation sites reachable from this
177         // task context
178         Iterator allocItr = allocSites.iterator();
179         while( allocItr.hasNext() ) {
180           AllocationSite as = (AllocationSite) allocItr.next();
181           common = createsPotentialAliases(td, i, as);
182           if( !common.isEmpty() ) {
183             foundSomeAlias = true;
184             if( !tabularOutput ) {
185               bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
186               bw.write(prettyPrintNodeSet( common )+"\n" );
187             } else {
188               ++numAlias;
189             }
190           }
191         }
192       }
193       
194       // for each allocation site check for aliases with
195       // other allocation sites in the context of execution
196       // of this task
197       HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
198       Iterator allocItr1 = allocSites.iterator();
199       while( allocItr1.hasNext() ) {
200         AllocationSite as1 = (AllocationSite) allocItr1.next();
201
202         Iterator allocItr2 = allocSites.iterator();
203         while( allocItr2.hasNext() ) {
204           AllocationSite as2 = (AllocationSite) allocItr2.next();
205           
206           if( !outerChecked.contains(as2) ) {
207             common = createsPotentialAliases(td, as1, as2);
208             
209             if( !common.isEmpty() ) {
210               foundSomeAlias = true;
211               if( !tabularOutput ) {
212                 bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
213                 bw.write(prettyPrintNodeSet( common )+"\n" );
214               } else {
215                 ++numAlias;
216               }
217             }
218           }
219         }
220
221         outerChecked.add(as1);
222       }
223
224       if( !foundSomeAlias ) {
225         if( !tabularOutput ) {
226           bw.write("No aliases between flagged objects in Task "+td+".\n");
227         }
228       }
229     }
230
231     if( !tabularOutput ) {
232       bw.write( "\n"+computeAliasContextHistogram() );
233     } else {
234       bw.write( " & "+numAlias+
235                 " & "+justTime+
236                 " & "+numLines+
237                 " & "+numMethodsAnalyzed()+
238                 " \\\\\n" );
239     }
240     
241     bw.close();
242   }
243
244
245   // this version of writeAllAliases is for Java programs that have no tasks
246   public void writeAllAliasesJava(String outputFile, 
247                                   String timeReport,
248                                   String justTime,
249                                   boolean tabularOutput,
250                                   int numLines
251                                   ) throws java.io.IOException {
252     checkAnalysisComplete();
253
254     assert !state.TASK;    
255
256     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
257
258     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
259     bw.write(timeReport+"\n\n");
260
261     boolean foundSomeAlias = false;
262
263     Descriptor d = typeUtil.getMain();
264     HashSet<AllocationSite> allocSites = getFlaggedAllocationSites(d);
265
266     // for each allocation site check for aliases with
267     // other allocation sites in the context of execution
268     // of this task
269     HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
270     Iterator allocItr1 = allocSites.iterator();
271     while( allocItr1.hasNext() ) {
272       AllocationSite as1 = (AllocationSite) allocItr1.next();
273       
274       Iterator allocItr2 = allocSites.iterator();
275       while( allocItr2.hasNext() ) {
276         AllocationSite as2 = (AllocationSite) allocItr2.next();
277         
278         if( !outerChecked.contains(as2) ) {       
279           Set<HeapRegionNode> common = createsPotentialAliases(d, as1, as2);
280
281           if( !common.isEmpty() ) {
282             foundSomeAlias = true;
283             bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n");
284             bw.write( prettyPrintNodeSet( common )+"\n" );
285           }
286         }
287       }
288       
289       outerChecked.add(as1);
290     }
291     
292     if( !foundSomeAlias ) {
293       bw.write("No aliases between flagged objects found.\n");
294     }
295
296     bw.write( "\n"+computeAliasContextHistogram() );
297     bw.close();
298   }
299   ///////////////////////////////////////////
300   //
301   // end public interface
302   //
303   ///////////////////////////////////////////
304
305   protected void checkAnalysisComplete() {
306     if( !analysisComplete ) {
307       throw new Error("Warning: public interface method called while analysis is running.");
308     }
309   }
310
311
312
313
314
315   // data from the compiler
316   public State     state;
317   public CallGraph callGraph;
318   public TypeUtil  typeUtil;
319   public int       allocationDepth;
320
321   // for public interface methods to warn that they
322   // are grabbing results during analysis
323   private boolean analysisComplete;
324
325   // used to identify HeapRegionNode objects
326   // A unique ID equates an object in one
327   // ownership graph with an object in another
328   // graph that logically represents the same
329   // heap region
330   // start at 10 and increment to leave some
331   // reserved IDs for special purposes
332   static private int uniqueIDcount = 10;
333
334   // Use these data structures to track progress of
335   // processing all methods in the program, and by methods
336   // TaskDescriptor and MethodDescriptor are combined
337   // together, with a common parent class Descriptor
338   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToInitialParamAllocGraph;
339   private  Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToCompleteOwnershipGraph;
340   private Hashtable<FlatNew,       AllocationSite>           mapFlatNewToAllocationSite;
341   private Hashtable<Descriptor,    HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
342   private Hashtable<MethodContext, Integer>                  mapMethodContextToNumUpdates;
343   private Hashtable<Descriptor,    HashSet<MethodContext> >  mapDescriptorToAllMethodContexts;
344   private Hashtable<MethodContext, HashSet<MethodContext> >  mapMethodContextToDependentContexts;
345   private Hashtable<Integer,       AllocationSite>           mapHrnIdToAllocationSite;
346
347   // Use these data structures to track progress of one pass of
348   // processing the FlatNodes of a particular method
349   private HashSet  <FlatNode>                 flatNodesToVisit;
350   private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
351   private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
352
353   // descriptorsToAnalyze identifies the set of tasks and methods
354   // that are reachable from the program tasks, this set is initialized
355   // and then remains static
356   public HashSet<Descriptor> descriptorsToAnalyze;
357
358   // descriptorsToVisit is initialized to descriptorsToAnalyze and is
359   // reduced by visiting a descriptor during analysis.  When dependents
360   // must be scheduled, only those contained in descriptorsToAnalyze
361   // should be re-added to this queue
362   private PriorityQueue<MethodContextQWrapper> methodContextsToVisitQ;
363   private Set          <MethodContext>         methodContextsToVisitSet;
364   private Hashtable<Descriptor, Integer> mapDescriptorToPriority;
365
366
367   // special field descriptors for array elements
368   public static final String arrayElementFieldName = "___element_";
369   private static Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField =
370     new Hashtable<TypeDescriptor, FieldDescriptor>();
371
372
373   // for controlling DOT file output
374   private boolean writeDOTs;
375   private boolean writeAllDOTs;
376   
377   // for controlling method effects
378   private boolean methodEffects;
379   
380     //map each FlatNode to its own internal ownership graph
381         private MethodEffectsAnalysis meAnalysis;
382         
383         //keep internal ownership graph by method context and flat node
384         private Hashtable<MethodContext, Hashtable<FlatNode, OwnershipGraph>> mapMethodContextToFlatNodeOwnershipGraph;
385         
386         //map method context to a set of allocation sites of live-in vars
387         private Hashtable<MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet;
388
389
390
391   // this analysis generates an ownership graph for every task
392   // in the program
393   public OwnershipAnalysis(State state,
394                            TypeUtil tu,
395                            CallGraph callGraph,
396                            int allocationDepth,
397                            boolean writeDOTs,
398                            boolean writeAllDOTs,
399                            String aliasFile) throws java.io.IOException {
400           
401           this.methodEffects = false;
402           init(state,tu,callGraph,allocationDepth,writeDOTs,writeAllDOTs,aliasFile);
403           
404   }
405   
406   public OwnershipAnalysis(State state,
407           TypeUtil tu,
408           CallGraph callGraph,
409           int allocationDepth,
410           boolean writeDOTs,
411           boolean writeAllDOTs,
412           String aliasFile,
413           boolean methodEffects) throws java.io.IOException {
414           
415           this.methodEffects = methodEffects;
416           init(state,tu,callGraph,allocationDepth,writeDOTs,writeAllDOTs,aliasFile);
417           
418   }
419   
420   // new constructor for on-demand disjoint analysis
421         public OwnershipAnalysis(
422                         State state,
423                         TypeUtil tu,
424                         CallGraph callGraph,
425                         int allocationDepth,
426                         boolean writeDOTs,
427                         boolean writeAllDOTs,
428                         String aliasFile,
429                         boolean methodEffects,
430                         Hashtable<MethodContext, HashSet<AllocationSite>> mapMethodContextToLiveInAllocationSiteSet)
431                         throws java.io.IOException {
432
433                 this.methodEffects = methodEffects;
434                 this.mapMethodContextToLiveInAllocationSiteSet=mapMethodContextToLiveInAllocationSiteSet;
435                 init(state, tu, callGraph, allocationDepth, writeDOTs, writeAllDOTs,
436                                 aliasFile);
437
438         }
439   
440   private void init(State state,
441           TypeUtil tu,
442           CallGraph callGraph,
443           int allocationDepth,
444           boolean writeDOTs,
445           boolean writeAllDOTs,
446           String aliasFile) throws java.io.IOException {
447
448             analysisComplete = false;
449
450             this.state           = state;
451             this.typeUtil        = tu;
452             this.callGraph       = callGraph;
453             this.allocationDepth = allocationDepth;
454             this.writeDOTs       = writeDOTs;
455             this.writeAllDOTs    = writeAllDOTs;
456
457             // set some static configuration for OwnershipGraphs
458             OwnershipGraph.allocationDepth   = allocationDepth;
459             OwnershipGraph.typeUtil          = typeUtil;
460             OwnershipGraph.debugCallMapCount = state.OWNERSHIPDEBUGCALLCOUNT;
461             OwnershipGraph.debugCallee       = state.OWNERSHIPDEBUGCALLEE;
462             OwnershipGraph.debugCaller       = state.OWNERSHIPDEBUGCALLER;
463             if( OwnershipGraph.debugCallee != null &&
464                 OwnershipGraph.debugCaller != null ) {
465               OwnershipGraph.debugCallMap = true;
466             }
467
468             descriptorsToAnalyze = new HashSet<Descriptor>();
469
470             mapMethodContextToInitialParamAllocGraph =
471               new Hashtable<MethodContext, OwnershipGraph>();
472
473             mapMethodContextToCompleteOwnershipGraph =
474               new Hashtable<MethodContext, OwnershipGraph>();
475
476             mapFlatNewToAllocationSite =
477               new Hashtable<FlatNew, AllocationSite>();
478
479             mapDescriptorToAllocationSiteSet =
480               new Hashtable<Descriptor, HashSet<AllocationSite> >();
481
482             mapDescriptorToAllMethodContexts = 
483               new Hashtable<Descriptor, HashSet<MethodContext> >();
484
485             mapMethodContextToDependentContexts =
486               new Hashtable<MethodContext, HashSet<MethodContext> >();
487
488             mapDescriptorToPriority = 
489               new Hashtable<Descriptor, Integer>();
490
491             mapHrnIdToAllocationSite =
492               new Hashtable<Integer, AllocationSite>();
493             
494             mapMethodContextToFlatNodeOwnershipGraph=new Hashtable<MethodContext, Hashtable<FlatNode, OwnershipGraph>>();
495             
496             meAnalysis=new MethodEffectsAnalysis(methodEffects);
497
498
499             if( writeAllDOTs ) {
500               mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
501             }
502
503
504             double timeStartAnalysis = (double) System.nanoTime();
505
506
507             if( state.TASK ) {
508               // initialize methods to visit as the set of all tasks in the
509               // program and then any method that could be called starting
510               // from those tasks
511               Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
512               while( taskItr.hasNext() ) {
513                 Descriptor d = (Descriptor) taskItr.next();
514                 scheduleAllCallees(d);
515               }
516
517             } else {
518               // we are not in task mode, just normal Java, so start with
519               // the main method
520               Descriptor d = typeUtil.getMain();
521               scheduleAllCallees(d);
522             }
523
524
525             // before beginning analysis, initialize every scheduled method
526             // with an ownership graph that has populated parameter index tables
527             // by analyzing the first node which is always a FlatMethod node
528             Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
529             while( dItr.hasNext() ) {
530               Descriptor d  = dItr.next();
531               OwnershipGraph og = new OwnershipGraph();
532
533               FlatMethod fm;
534               if( d instanceof MethodDescriptor ) {
535                 fm = state.getMethodFlat( (MethodDescriptor) d);
536               } else {
537                 assert d instanceof TaskDescriptor;
538                 fm = state.getMethodFlat( (TaskDescriptor) d);
539               }
540
541               MethodContext mc = new MethodContext( d );
542               assert !mapDescriptorToAllMethodContexts.containsKey( d );
543               HashSet<MethodContext> s = new HashSet<MethodContext>();
544               s.add( mc );
545               mapDescriptorToAllMethodContexts.put( d, s );
546
547               //System.out.println("Previsiting " + mc);
548
549               meAnalysis.createNewMapping(mc);
550
551               og = analyzeFlatNode(mc, fm, null, og);
552               setGraphForMethodContext(mc, og);
553             }
554
555             // as mentioned above, analyze methods one-by-one, possibly revisiting
556             // a method if the methods that it calls are updated
557             analyzeMethods();
558             analysisComplete = true;
559
560
561             double timeEndAnalysis = (double) System.nanoTime();
562             double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
563             String treport = String.format( "The reachability analysis took %.3f sec.", dt );
564             String justtime = String.format( "%.2f", dt );
565             System.out.println( treport );
566
567             if( writeDOTs && !writeAllDOTs ) {
568               writeFinalContextGraphs();      
569             }  
570
571             if(methodEffects){
572                 meAnalysis.writeMethodEffectsResult();
573             }
574
575             if( aliasFile != null ) {
576               if( state.TASK ) {
577                 writeAllAliases(aliasFile, treport, justtime, state.OWNERSHIPALIASTAB, state.lines);
578               } else {
579                 writeAllAliasesJava(aliasFile, treport, justtime, state.OWNERSHIPALIASTAB, state.lines);
580               }
581             }
582           
583   }
584
585   // called from the constructor to help initialize the set
586   // of methods that needs to be analyzed by ownership analysis
587   private void scheduleAllCallees(Descriptor d) {
588     if( descriptorsToAnalyze.contains(d) ) {
589       return;
590     }
591     descriptorsToAnalyze.add(d);
592
593     // start with all method calls to further schedule
594     Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
595
596     if( d instanceof MethodDescriptor ) {
597       // see if this method has virtual dispatch
598       Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
599       moreMethodsToCheck.addAll(virtualMethods);
600     }
601
602     // keep following any further methods identified in
603     // the call chain
604     Iterator methItr = moreMethodsToCheck.iterator();
605     while( methItr.hasNext() ) {
606       Descriptor m = (Descriptor) methItr.next();
607       scheduleAllCallees(m);
608     }
609   }
610
611
612   // manage the set of tasks and methods to be analyzed
613   // and be sure to reschedule tasks/methods when the methods
614   // they call are updated
615   private void analyzeMethods() throws java.io.IOException {  
616
617     // first gather all of the method contexts to analyze
618     HashSet<MethodContext> allContexts = new HashSet<MethodContext>();
619     Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
620     while( itrd2a.hasNext() ) {
621       HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
622       assert mcs != null;
623
624       Iterator<MethodContext> itrmc = mcs.iterator();
625       while( itrmc.hasNext() ) {
626         allContexts.add( itrmc.next() );
627       }
628     }
629
630     // topologically sort them according to the caller graph so leaf calls are
631     // ordered first; use that ordering to give method contexts priorities
632     LinkedList<MethodContext> sortedMethodContexts = topologicalSort( allContexts );   
633
634     methodContextsToVisitQ   = new PriorityQueue<MethodContextQWrapper>();
635     methodContextsToVisitSet = new HashSet<MethodContext>();
636
637     int p = 0;
638     Iterator<MethodContext> mcItr = sortedMethodContexts.iterator();
639     while( mcItr.hasNext() ) {
640       MethodContext mc = mcItr.next();
641       mapDescriptorToPriority.put( mc.getDescriptor(), new Integer( p ) );
642       methodContextsToVisitQ.add( new MethodContextQWrapper( p, mc ) );
643       methodContextsToVisitSet.add( mc );
644       ++p;
645     }
646
647     // analyze methods from the priority queue until it is empty
648     while( !methodContextsToVisitQ.isEmpty() ) {
649       MethodContext mc = methodContextsToVisitQ.poll().getMethodContext();
650       assert methodContextsToVisitSet.contains( mc );
651       methodContextsToVisitSet.remove( mc );
652
653       // because the task or method descriptor just extracted
654       // was in the "to visit" set it either hasn't been analyzed
655       // yet, or some method that it depends on has been
656       // updated.  Recompute a complete ownership graph for
657       // this task/method and compare it to any previous result.
658       // If there is a change detected, add any methods/tasks
659       // that depend on this one to the "to visit" set.
660
661       System.out.println("Analyzing " + mc);
662
663       Descriptor d = mc.getDescriptor();
664       FlatMethod fm;
665       if( d instanceof MethodDescriptor ) {
666         fm = state.getMethodFlat( (MethodDescriptor) d);
667       } else {
668         assert d instanceof TaskDescriptor;
669         fm = state.getMethodFlat( (TaskDescriptor) d);
670       }
671
672       OwnershipGraph og = analyzeFlatMethod(mc, fm);
673       OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
674       if( !og.equals(ogPrev) ) {
675         setGraphForMethodContext(mc, og);
676
677         Iterator<MethodContext> depsItr = iteratorDependents( mc );
678         while( depsItr.hasNext() ) {
679           MethodContext mcNext = depsItr.next();
680
681           if( !methodContextsToVisitSet.contains( mcNext ) ) {
682             methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( mcNext.getDescriptor() ), 
683                                                                    mcNext ) );
684             methodContextsToVisitSet.add( mcNext );
685           }
686         }
687       }
688     }
689
690   }
691
692
693   // keep passing the Descriptor of the method along for debugging
694   // and dot file writing
695   private OwnershipGraph
696   analyzeFlatMethod(MethodContext mc,
697                     FlatMethod flatm) throws java.io.IOException {
698
699     // initialize flat nodes to visit as the flat method
700     // because it is the entry point
701
702     flatNodesToVisit = new HashSet<FlatNode>();
703     flatNodesToVisit.add(flatm);
704
705     // initilize the mapping of flat nodes in this flat method to
706     // ownership graph results to an empty mapping
707     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
708
709     // initialize the set of return nodes that will be combined as
710     // the final ownership graph result to return as an empty set
711     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
712
713
714     while( !flatNodesToVisit.isEmpty() ) {
715       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
716       flatNodesToVisit.remove(fn);
717
718       //System.out.println( "  "+fn );
719
720       // perform this node's contributions to the ownership
721       // graph on a new copy, then compare it to the old graph
722       // at this node to see if anything was updated.
723       OwnershipGraph og = new OwnershipGraph();
724
725       // start by merging all node's parents' graphs
726       for( int i = 0; i < fn.numPrev(); ++i ) {
727         FlatNode pn = fn.getPrev(i);
728         if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
729           OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
730           og.merge(ogParent);
731         }
732       }
733
734       // apply the analysis of the flat node to the
735       // ownership graph made from the merge of the
736       // parent graphs
737       og = analyzeFlatNode(mc,
738                            fn,
739                            returnNodesToCombineForCompleteOwnershipGraph,
740                            og);
741
742       
743
744      
745       if( takeDebugSnapshots && 
746           mc.getDescriptor().getSymbol().equals( mcDescSymbolDebug ) ) {
747         debugSnapshot(og,fn);
748       }
749
750
751       // if the results of the new graph are different from
752       // the current graph at this node, replace the graph
753       // with the update and enqueue the children for
754       // processing
755       OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
756       if( !og.equals(ogPrev) ) {
757         mapFlatNodeToOwnershipGraph.put(fn, og);
758
759         for( int i = 0; i < fn.numNext(); i++ ) {
760           FlatNode nn = fn.getNext(i);
761           flatNodesToVisit.add(nn);
762         }
763       }
764     }
765
766     // end by merging all return nodes into a complete
767     // ownership graph that represents all possible heap
768     // states after the flat method returns
769     OwnershipGraph completeGraph = new OwnershipGraph();
770     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
771     while( retItr.hasNext() ) {
772       FlatReturnNode frn = (FlatReturnNode) retItr.next();
773       assert mapFlatNodeToOwnershipGraph.containsKey(frn);
774       OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
775       completeGraph.merge(ogr);
776     }
777
778     return completeGraph;
779   }
780
781
782   private OwnershipGraph
783   analyzeFlatNode(MethodContext mc,
784                   FlatNode fn,
785                   HashSet<FlatReturnNode> setRetNodes,
786                   OwnershipGraph og) throws java.io.IOException {
787           
788     TempDescriptor lhs;
789     TempDescriptor rhs;
790     FieldDescriptor fld;
791
792     // use node type to decide what alterations to make
793     // to the ownership graph
794     switch( fn.kind() ) {
795
796     case FKind.FlatMethod:
797       FlatMethod fm = (FlatMethod) fn;
798
799       // there should only be one FlatMethod node as the
800       // parent of all other FlatNode objects, so take
801       // the opportunity to construct the initial graph by
802       // adding parameters labels to new heap regions
803       // AND this should be done once globally so that the
804       // parameter IDs are consistent between analysis
805       // iterations, so if this step has been done already
806       // just merge in the cached version
807       OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
808       if( ogInitParamAlloc == null ) {
809
810         // if the method context has aliased parameters, make sure
811         // there is a blob region for all those param to reference
812         Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
813
814         if( !aliasedParamIndices.isEmpty() ) {
815           og.makeAliasedParamHeapRegionNode();
816         }
817
818         // set up each parameter
819         for( int i = 0; i < fm.numParameters(); ++i ) {
820           TempDescriptor tdParam    = fm.getParameter( i );
821           TypeDescriptor typeParam  = tdParam.getType();
822           Integer        paramIndex = new Integer( i );
823
824           if( typeParam.isImmutable() && !typeParam.isArray() ) {
825             // don't bother with this primitive parameter, it
826             // cannot affect reachability
827             continue;
828           }
829
830           if( aliasedParamIndices.contains( paramIndex ) ) {
831             // use the alias blob but give parameters their
832             // own primary obj region
833             og.assignTempEqualToAliasedParam( tdParam,
834                                               paramIndex );         
835           } else {
836             // this parameter is not aliased to others, give it
837             // a fresh primary obj and secondary object
838             og.assignTempEqualToParamAlloc( tdParam,
839                                             mc.getDescriptor() instanceof TaskDescriptor,
840                                             paramIndex );
841           }
842         }
843         
844         // add additional edges for aliased regions if necessary
845         if( !aliasedParamIndices.isEmpty() ) {
846           og.addParam2ParamAliasEdges( fm, aliasedParamIndices );
847         }
848         
849         // clean up reachability on initial parameter shapes
850         og.globalSweep();
851
852         // this maps tokens to parameter indices and vice versa
853         // for when this method is a callee
854         og.prepareParamTokenMaps( fm );
855
856         // cache the graph
857         OwnershipGraph ogResult = new OwnershipGraph();
858         ogResult.merge(og);
859         mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
860
861       } else {
862         // or just leverage the cached copy
863         og.merge(ogInitParamAlloc);
864       }
865       break;
866       
867     case FKind.FlatOpNode:
868       FlatOpNode fon = (FlatOpNode) fn;
869       if( fon.getOp().getOp() == Operation.ASSIGN ) {
870         lhs = fon.getDest();
871         rhs = fon.getLeft();
872         og.assignTempXEqualToTempY(lhs, rhs);
873       }
874       break;
875
876     case FKind.FlatCastNode:
877       FlatCastNode fcn = (FlatCastNode) fn;
878       lhs = fcn.getDst();
879       rhs = fcn.getSrc();
880
881       TypeDescriptor td = fcn.getType();
882       assert td != null;
883       
884       og.assignTypedTempXEqualToTempY(lhs, rhs, td);
885       break;
886
887     case FKind.FlatFieldNode:
888       FlatFieldNode ffn = (FlatFieldNode) fn;
889       lhs = ffn.getDst();
890       rhs = ffn.getSrc();
891       fld = ffn.getField();
892       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
893         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
894       }
895       
896       meAnalysis.analyzeFlatFieldNode(mc, og, rhs, fld);
897       
898       break;
899
900     case FKind.FlatSetFieldNode:
901       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
902       lhs = fsfn.getDst();
903       fld = fsfn.getField();
904       rhs = fsfn.getSrc();
905       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
906         og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
907       }
908       
909       meAnalysis.analyzeFlatSetFieldNode(mc, og, lhs, fld);
910       
911       break;
912
913     case FKind.FlatElementNode:
914       FlatElementNode fen = (FlatElementNode) fn;
915       lhs = fen.getDst();
916       rhs = fen.getSrc();
917       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
918
919         assert rhs.getType() != null;
920         assert rhs.getType().isArray();
921         
922         TypeDescriptor  tdElement = rhs.getType().dereference();
923         FieldDescriptor fdElement = getArrayField( tdElement );
924   
925         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
926       }
927       break;
928
929     case FKind.FlatSetElementNode:
930       FlatSetElementNode fsen = (FlatSetElementNode) fn;
931       lhs = fsen.getDst();
932       rhs = fsen.getSrc();
933       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
934
935         assert lhs.getType() != null;
936         assert lhs.getType().isArray();
937         
938         TypeDescriptor  tdElement = lhs.getType().dereference();
939         FieldDescriptor fdElement = getArrayField( tdElement );
940
941         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
942       }
943       break;
944
945     case FKind.FlatNew:
946       FlatNew fnn = (FlatNew) fn;
947       lhs = fnn.getDst();
948       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
949         AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
950         
951         if (mapMethodContextToLiveInAllocationSiteSet != null){
952                 HashSet<AllocationSite> alllocSet=mapMethodContextToLiveInAllocationSiteSet.get(mc);
953                 if(alllocSet!=null){
954                         for (Iterator iterator = alllocSet.iterator(); iterator
955                                         .hasNext();) {
956                                 AllocationSite allocationSite = (AllocationSite) iterator
957                                                 .next();
958                                 if(allocationSite.flatNew.equals(as.flatNew)){
959                                         as.setFlag(true);
960                                 }
961                         }
962                 }
963         }
964         
965         og.assignTempEqualToNewAlloc(lhs, as);
966       }
967       break;
968
969     case FKind.FlatCall:
970       FlatCall fc = (FlatCall) fn;
971       MethodDescriptor md = fc.getMethod();
972       FlatMethod flatm = state.getMethodFlat(md);
973       OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph();
974
975       if( md.isStatic() ) {
976         // a static method is simply always the same, makes life easy
977         ogMergeOfAllPossibleCalleeResults = og;
978
979         Set<Integer> aliasedParamIndices = 
980           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
981
982         MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
983         Set contexts = mapDescriptorToAllMethodContexts.get( md );
984         assert contexts != null;
985         contexts.add( mcNew );
986
987         addDependent( mc, mcNew );
988
989         OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
990
991         if( onlyPossibleCallee == 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 ), 
996                                                                    mcNew ) );
997             methodContextsToVisitSet.add( mcNew );
998           }
999           
1000         } else {
1001           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc, null);
1002         }
1003         
1004         meAnalysis.createNewMapping(mcNew);
1005         meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
1006         
1007
1008       } else {
1009         // if the method descriptor is virtual, then there could be a
1010         // set of possible methods that will actually be invoked, so
1011         // find all of them and merge all of their results together
1012         TypeDescriptor typeDesc = fc.getThis().getType();
1013         Set possibleCallees = callGraph.getMethods(md, typeDesc);
1014
1015         Iterator i = possibleCallees.iterator();
1016         while( i.hasNext() ) {
1017           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
1018           FlatMethod pflatm = state.getMethodFlat(possibleMd);
1019
1020           // don't alter the working graph (og) until we compute a result for every
1021           // possible callee, merge them all together, then set og to that
1022           OwnershipGraph ogCopy = new OwnershipGraph();
1023           ogCopy.merge(og);
1024
1025           Set<Integer> aliasedParamIndices = 
1026             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
1027
1028           MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
1029           Set contexts = mapDescriptorToAllMethodContexts.get( md );
1030           assert contexts != null;
1031           contexts.add( mcNew );
1032           
1033                 
1034         meAnalysis.createNewMapping(mcNew);
1035                 
1036           
1037           addDependent( mc, mcNew );
1038
1039           OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
1040
1041           if( ogPotentialCallee == null ) {
1042             // if this method context has never been analyzed just schedule it for analysis
1043             // and skip over this call site for now
1044             if( !methodContextsToVisitSet.contains( mcNew ) ) {
1045               methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ), 
1046                                                                      mcNew ) );
1047               methodContextsToVisitSet.add( mcNew );
1048             }
1049             
1050           } else {
1051             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc, null);
1052           }
1053                 
1054           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
1055           
1056           meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
1057         }
1058         
1059       }
1060
1061       og = ogMergeOfAllPossibleCalleeResults;
1062       break;
1063
1064     case FKind.FlatReturnNode:
1065       FlatReturnNode frn = (FlatReturnNode) fn;
1066       rhs = frn.getReturnTemp();
1067       if( rhs != null && !rhs.getType().isImmutable() ) {
1068         og.assignReturnEqualToTemp(rhs);
1069       }
1070       setRetNodes.add(frn);
1071       break;
1072     }
1073     
1074     Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(mc);
1075     if(table==null){
1076         table=new     Hashtable<FlatNode, OwnershipGraph>();            
1077     }
1078     table.put(fn, og);
1079     mapMethodContextToFlatNodeOwnershipGraph.put(mc, table);
1080     
1081     return og;
1082   }
1083
1084
1085   // this method should generate integers strictly greater than zero!
1086   // special "shadow" regions are made from a heap region by negating
1087   // the ID
1088   static public Integer generateUniqueHeapRegionNodeID() {
1089     ++uniqueIDcount;
1090     return new Integer(uniqueIDcount);
1091   }
1092
1093
1094   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
1095     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
1096     if( fdElement == null ) {
1097       fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
1098                                       tdElement,
1099                                       arrayElementFieldName,
1100                                       null,
1101                                       false);
1102       mapTypeToArrayField.put( tdElement, fdElement );
1103     }
1104     return fdElement;
1105   }
1106
1107   
1108   private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og) {
1109
1110     mapMethodContextToCompleteOwnershipGraph.put(mc, og);
1111
1112     if( writeDOTs && writeAllDOTs ) {
1113       if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
1114         mapMethodContextToNumUpdates.put(mc, new Integer(0) );
1115       }
1116       Integer n = mapMethodContextToNumUpdates.get(mc);
1117       try {
1118         og.writeGraph(mc+"COMPLETE"+String.format("%05d", n),
1119                       true,  // write labels (variables)
1120                       true,  // selectively hide intermediate temp vars
1121                       true,  // prune unreachable heap regions
1122                       false, // show back edges to confirm graph validity
1123                       false, // show parameter indices (unmaintained!)
1124                       true,  // hide subset reachability states
1125                       true); // hide edge taints
1126       } catch( IOException e ) {}
1127       mapMethodContextToNumUpdates.put(mc, n + 1);
1128     }
1129   }
1130
1131
1132   private void addDependent( MethodContext caller, MethodContext callee ) {
1133     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1134     if( deps == null ) {
1135       deps = new HashSet<MethodContext>();
1136     }
1137     deps.add( caller );
1138     mapMethodContextToDependentContexts.put( callee, deps );
1139   }
1140
1141   private Iterator<MethodContext> iteratorDependents( MethodContext callee ) {
1142     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1143     if( deps == null ) {
1144       deps = new HashSet<MethodContext>();
1145       mapMethodContextToDependentContexts.put( callee, deps );
1146     }
1147     return deps.iterator();
1148   }
1149
1150
1151   private void writeFinalContextGraphs() {
1152     Set entrySet = mapMethodContextToCompleteOwnershipGraph.entrySet();
1153     Iterator itr = entrySet.iterator();
1154     while( itr.hasNext() ) {
1155       Map.Entry      me = (Map.Entry)      itr.next();
1156       MethodContext  mc = (MethodContext)  me.getKey();
1157       OwnershipGraph og = (OwnershipGraph) me.getValue();
1158
1159       try {
1160         og.writeGraph(mc+"COMPLETE",
1161                       true,  // write labels (variables)
1162                       true,  // selectively hide intermediate temp vars
1163                       true,  // prune unreachable heap regions
1164                       false, // show back edges to confirm graph validity
1165                       false, // show parameter indices (unmaintained!)
1166                       true,  // hide subset reachability states
1167                       true); // hide edge taints
1168       } catch( IOException e ) {}    
1169     }
1170   }
1171   
1172   
1173
1174   // return just the allocation site associated with one FlatNew node
1175   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
1176
1177     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
1178       AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
1179
1180       // the newest nodes are single objects
1181       for( int i = 0; i < allocationDepth; ++i ) {
1182         Integer id = generateUniqueHeapRegionNodeID();
1183         as.setIthOldest(i, id);
1184         mapHrnIdToAllocationSite.put( id, as );
1185       }
1186
1187       // the oldest node is a summary node
1188       Integer idSummary = generateUniqueHeapRegionNodeID();
1189       as.setSummary(idSummary);
1190
1191       mapFlatNewToAllocationSite.put(fn, as);
1192     }
1193
1194     return mapFlatNewToAllocationSite.get(fn);
1195   }
1196
1197
1198   // return all allocation sites in the method (there is one allocation
1199   // site per FlatNew node in a method)
1200   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
1201     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
1202       buildAllocationSiteSet(d);
1203     }
1204
1205     return mapDescriptorToAllocationSiteSet.get(d);
1206
1207   }
1208
1209   private void buildAllocationSiteSet(Descriptor d) {
1210     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
1211
1212     FlatMethod fm;
1213     if( d instanceof MethodDescriptor ) {
1214       fm = state.getMethodFlat( (MethodDescriptor) d);
1215     } else {
1216       assert d instanceof TaskDescriptor;
1217       fm = state.getMethodFlat( (TaskDescriptor) d);
1218     }
1219
1220     // visit every node in this FlatMethod's IR graph
1221     // and make a set of the allocation sites from the
1222     // FlatNew node's visited
1223     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1224     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1225     toVisit.add(fm);
1226
1227     while( !toVisit.isEmpty() ) {
1228       FlatNode n = toVisit.iterator().next();
1229
1230       if( n instanceof FlatNew ) {
1231         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
1232       }
1233
1234       toVisit.remove(n);
1235       visited.add(n);
1236
1237       for( int i = 0; i < n.numNext(); ++i ) {
1238         FlatNode child = n.getNext(i);
1239         if( !visited.contains(child) ) {
1240           toVisit.add(child);
1241         }
1242       }
1243     }
1244
1245     mapDescriptorToAllocationSiteSet.put(d, s);
1246   }
1247
1248
1249   private HashSet<AllocationSite> getFlaggedAllocationSites(Descriptor dIn) {
1250     
1251     HashSet<AllocationSite> out     = new HashSet<AllocationSite>();
1252     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1253     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1254
1255     toVisit.add(dIn);
1256
1257     while( !toVisit.isEmpty() ) {
1258       Descriptor d = toVisit.iterator().next();
1259       toVisit.remove(d);
1260       visited.add(d);
1261
1262       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1263       Iterator asItr = asSet.iterator();
1264       while( asItr.hasNext() ) {
1265         AllocationSite as = (AllocationSite) asItr.next();
1266         if( as.getDisjointId() != null ) {
1267           out.add(as);
1268         }
1269       }
1270
1271       // enqueue callees of this method to be searched for
1272       // allocation sites also
1273       Set callees = callGraph.getCalleeSet(d);
1274       if( callees != null ) {
1275         Iterator methItr = callees.iterator();
1276         while( methItr.hasNext() ) {
1277           MethodDescriptor md = (MethodDescriptor) methItr.next();
1278
1279           if( !visited.contains(md) ) {
1280             toVisit.add(md);
1281           }
1282         }
1283       }
1284     }
1285     
1286     return out;
1287   }
1288
1289
1290   private HashSet<AllocationSite>
1291   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1292
1293     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
1294     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1295     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1296
1297     toVisit.add(td);
1298
1299     // traverse this task and all methods reachable from this task
1300     while( !toVisit.isEmpty() ) {
1301       Descriptor d = toVisit.iterator().next();
1302       toVisit.remove(d);
1303       visited.add(d);
1304
1305       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1306       Iterator asItr = asSet.iterator();
1307       while( asItr.hasNext() ) {
1308         AllocationSite as = (AllocationSite) asItr.next();
1309         TypeDescriptor typed = as.getType();
1310         if( typed != null ) {
1311           ClassDescriptor cd = typed.getClassDesc();
1312           if( cd != null && cd.hasFlags() ) {
1313             asSetTotal.add(as);
1314           }
1315         }
1316       }
1317
1318       // enqueue callees of this method to be searched for
1319       // allocation sites also
1320       Set callees = callGraph.getCalleeSet(d);
1321       if( callees != null ) {
1322         Iterator methItr = callees.iterator();
1323         while( methItr.hasNext() ) {
1324           MethodDescriptor md = (MethodDescriptor) methItr.next();
1325
1326           if( !visited.contains(md) ) {
1327             toVisit.add(md);
1328           }
1329         }
1330       }
1331     }
1332
1333
1334     return asSetTotal;
1335   }
1336
1337
1338   private LinkedList<MethodContext> topologicalSort( HashSet<MethodContext> set ) {
1339     HashSet   <MethodContext> discovered = new HashSet   <MethodContext>();
1340     LinkedList<MethodContext> sorted     = new LinkedList<MethodContext>();
1341   
1342     Iterator<MethodContext> itr = set.iterator();
1343     while( itr.hasNext() ) {
1344       MethodContext mc = itr.next();
1345           
1346       if( !discovered.contains( mc ) ) {
1347         dfsVisit( set, mc, sorted, discovered );
1348       }
1349     }
1350     
1351     return sorted;
1352   }
1353   
1354   private void dfsVisit( HashSet<MethodContext> set,
1355                          MethodContext mc,
1356                          LinkedList<MethodContext> sorted,
1357                          HashSet   <MethodContext> discovered ) {
1358     discovered.add( mc );
1359     
1360     Descriptor d = mc.getDescriptor();
1361     if( d instanceof MethodDescriptor ) {
1362       MethodDescriptor md = (MethodDescriptor) d;      
1363       Iterator itr = callGraph.getCallerSet( md ).iterator();
1364       while( itr.hasNext() ) {
1365         Descriptor dCaller = (Descriptor) itr.next();
1366         
1367         // only consider the callers in the original set to analyze
1368         Set<MethodContext> callerContexts = mapDescriptorToAllMethodContexts.get( dCaller );
1369         if( callerContexts == null )
1370           continue;     
1371         
1372         // since the analysis hasn't started, there should be exactly one
1373         // context if there are any at all
1374         assert callerContexts.size() == 1;      
1375         MethodContext mcCaller = callerContexts.iterator().next();
1376         assert set.contains( mcCaller );
1377
1378         if( !discovered.contains( mcCaller ) ) {
1379           dfsVisit( set, mcCaller, sorted, discovered );
1380         }
1381       }
1382     }
1383
1384     sorted.addFirst( mc );
1385   }
1386
1387
1388
1389   private String computeAliasContextHistogram() {
1390     
1391     Hashtable<Integer, Integer> mapNumContexts2NumDesc = 
1392       new Hashtable<Integer, Integer>();
1393   
1394     Iterator itr = mapDescriptorToAllMethodContexts.entrySet().iterator();
1395     while( itr.hasNext() ) {
1396       Map.Entry me = (Map.Entry) itr.next();
1397       HashSet<MethodContext> s = (HashSet<MethodContext>) me.getValue();
1398       
1399       Integer i = mapNumContexts2NumDesc.get( s.size() );
1400       if( i == null ) {
1401         i = new Integer( 0 );
1402       }
1403       mapNumContexts2NumDesc.put( s.size(), i + 1 );
1404     }   
1405
1406     String s = "";
1407     int total = 0;
1408
1409     itr = mapNumContexts2NumDesc.entrySet().iterator();
1410     while( itr.hasNext() ) {
1411       Map.Entry me = (Map.Entry) itr.next();
1412       Integer c0 = (Integer) me.getKey();
1413       Integer d0 = (Integer) me.getValue();
1414       total += d0;
1415       s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
1416     }
1417
1418     s += String.format( "\n%4d total methods analayzed.\n", total );
1419
1420     return s;
1421   }
1422
1423   private int numMethodsAnalyzed() {    
1424     return descriptorsToAnalyze.size();
1425   }
1426   
1427
1428
1429
1430   // insert a call to debugSnapshot() somewhere in the analysis 
1431   // to get successive captures of the analysis state
1432   boolean takeDebugSnapshots = false;
1433   String mcDescSymbolDebug = "addFirst";
1434   boolean stopAfterCapture = true;
1435
1436   // increments every visit to debugSnapshot, don't fiddle with it
1437   int debugCounter = 0;
1438
1439   // the value of debugCounter to start reporting the debugCounter
1440   // to the screen to let user know what debug iteration we're at
1441   int numStartCountReport = 0;
1442
1443   // the frequency of debugCounter values to print out, 0 no report
1444   int freqCountReport = 0;
1445
1446   // the debugCounter value at which to start taking snapshots
1447   int iterStartCapture = 0;
1448
1449   // the number of snapshots to take
1450   int numIterToCapture = 40;
1451
1452   void debugSnapshot(OwnershipGraph og, FlatNode fn) {
1453     if( debugCounter > iterStartCapture + numIterToCapture ) {
1454       return;
1455     }
1456
1457     ++debugCounter;
1458     if( debugCounter > numStartCountReport &&
1459         freqCountReport > 0 &&
1460         debugCounter % freqCountReport == 0 ) {
1461       System.out.println("    @@@ debug counter = "+debugCounter);
1462     }
1463     if( debugCounter > iterStartCapture ) {
1464       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
1465       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
1466       if( fn != null ) {
1467         graphName = graphName+fn;
1468       }
1469       try {
1470         og.writeGraph(graphName,
1471                       true,  // write labels (variables)
1472                       true,  // selectively hide intermediate temp vars
1473                       true,  // prune unreachable heap regions
1474                       false, // show back edges to confirm graph validity
1475                       false, // show parameter indices (unmaintained!)
1476                       true,  // hide subset reachability states
1477                       true); // hide edge taints
1478       } catch( Exception e ) {
1479         System.out.println("Error writing debug capture.");
1480         System.exit(0);
1481       }
1482     }
1483
1484     if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) {
1485       System.out.println("Stopping analysis after debug captures.");
1486       System.exit(0);
1487     }
1488   }
1489   
1490   public MethodEffectsAnalysis getMethodEffectsAnalysis(){
1491           return meAnalysis;
1492   }
1493   
1494   public OwnershipGraph getOwnvershipGraphByMethodContext(MethodContext mc){
1495           return mapMethodContextToCompleteOwnershipGraph.get(mc);
1496   }
1497   
1498   public HashSet<MethodContext> getAllMethodContextSetByDescriptor(Descriptor d){
1499           return mapDescriptorToAllMethodContexts.get(d);
1500   }
1501   
1502   public MethodContext getCalleeMethodContext(MethodContext callerMC, FlatCall fc){
1503           
1504           Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(callerMC);
1505           
1506           // merge previous ownership graph to calculate corresponding method context
1507           OwnershipGraph mergeOG = new OwnershipGraph();
1508           
1509           for(int i=0;i<fc.numPrev();i++){
1510                   FlatNode prevNode=fc.getPrev(i);
1511                   if(prevNode!=null){
1512                           OwnershipGraph prevOG=table.get(prevNode);              
1513                           mergeOG.merge(prevOG);
1514                   }
1515           }
1516           
1517           MethodDescriptor md=fc.getMethod();
1518           FlatMethod flatm = state.getMethodFlat(md);
1519           Set<Integer> aliasedParamIndices = mergeOG.calculateAliasedParamSet(fc, md.isStatic(), flatm);
1520           MethodContext calleeMC = new MethodContext( md, aliasedParamIndices );
1521           
1522           return calleeMC;        
1523   }
1524   
1525   
1526 }