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