got the hooks in place to get taints for rblocks
[IRC.git] / Robust / src / Analysis / Disjoint / DisjointAnalysis.java
1 package Analysis.Disjoint;
2
3 import Analysis.CallGraph.*;
4 import Analysis.Liveness;
5 import Analysis.ArrayReferencees;
6 import IR.*;
7 import IR.Flat.*;
8 import IR.Tree.Modifiers;
9 import java.util.*;
10 import java.io.*;
11
12
13 public class DisjointAnalysis {
14         
15           ///////////////////////////////////////////
16           //
17           //  Public interface to discover possible
18           //  aliases in the program under analysis
19           //
20           ///////////////////////////////////////////
21         
22           public HashSet<AllocSite>
23           getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
24             checkAnalysisComplete();
25             return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
26           }
27           
28           public AllocSite getAllocationSiteFromFlatNew(FlatNew fn) {
29                     checkAnalysisComplete();
30                     return getAllocSiteFromFlatNewPRIVATE(fn);
31            }      
32           
33           public AllocSite getAllocationSiteFromHeapRegionNodeID(Integer id) {
34                     checkAnalysisComplete();
35                     return mapHrnIdToAllocSite.get(id);
36           }
37           
38           public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
39               int paramIndex1,
40               int paramIndex2) {
41                   checkAnalysisComplete();
42                   ReachGraph rg=mapDescriptorToCompleteReachGraph.get(taskOrMethod);
43                   FlatMethod fm=state.getMethodFlat(taskOrMethod);
44                   assert(rg != null);
45                   return rg.mayReachSharedObjects(fm, paramIndex1, paramIndex2);
46           }
47           
48         public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
49                         int paramIndex, AllocSite alloc) {
50                 checkAnalysisComplete();
51                 ReachGraph rg = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
52             FlatMethod fm=state.getMethodFlat(taskOrMethod);
53                 assert (rg != null);
54                 return rg.mayReachSharedObjects(fm, paramIndex, alloc);
55         }
56
57         public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
58                         AllocSite alloc, int paramIndex) {
59                 checkAnalysisComplete();
60                 ReachGraph rg  = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
61                 FlatMethod fm=state.getMethodFlat(taskOrMethod);
62                 assert (rg != null);
63                 return rg.mayReachSharedObjects(fm, paramIndex, alloc);
64         }
65
66         public Set<HeapRegionNode> hasPotentialSharing(Descriptor taskOrMethod,
67                         AllocSite alloc1, AllocSite alloc2) {
68                 checkAnalysisComplete();
69                 ReachGraph rg  = mapDescriptorToCompleteReachGraph.get(taskOrMethod);
70                 assert (rg != null);
71                 return rg.mayReachSharedObjects(alloc1, alloc2);
72         }
73         
74         public String prettyPrintNodeSet(Set<HeapRegionNode> s) {
75                 checkAnalysisComplete();
76
77                 String out = "{\n";
78
79                 Iterator<HeapRegionNode> i = s.iterator();
80                 while (i.hasNext()) {
81                         HeapRegionNode n = i.next();
82
83                         AllocSite as = n.getAllocSite();
84                         if (as == null) {
85                                 out += "  " + n.toString() + ",\n";
86                         } else {
87                                 out += "  " + n.toString() + ": " + as.toStringVerbose()
88                                                 + ",\n";
89                         }
90                 }
91
92                 out += "}\n";
93                 return out;
94         }
95         
96   // use the methods given above to check every possible sharing class
97   // between task parameters and flagged allocation sites reachable
98   // from the task
99   public void writeAllSharing(String outputFile, 
100                               String timeReport,
101                               String justTime,
102                               boolean tabularOutput,
103                               int numLines
104                               )
105     throws java.io.IOException {
106     checkAnalysisComplete();
107
108     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile));
109
110     if (!tabularOutput) {
111       bw.write("Conducting ownership analysis with allocation depth = "
112                + allocationDepth + "\n");
113       bw.write(timeReport + "\n");
114     }
115
116     int numSharing = 0;
117
118     // look through every task for potential sharing
119     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
120     while (taskItr.hasNext()) {
121       TaskDescriptor td = (TaskDescriptor) taskItr.next();
122
123       if (!tabularOutput) {
124         bw.write("\n---------" + td + "--------\n");
125       }
126
127       HashSet<AllocSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
128
129       Set<HeapRegionNode> common;
130
131       // for each task parameter, check for sharing classes with
132       // other task parameters and every allocation site
133       // reachable from this task
134       boolean foundSomeSharing = false;
135
136       FlatMethod fm = state.getMethodFlat(td);
137       for (int i = 0; i < fm.numParameters(); ++i) {
138
139         // skip parameters with types that cannot reference
140         // into the heap
141         if( !shouldAnalysisTrack( fm.getParameter( i ).getType() ) ) {
142           continue;
143         }
144                           
145         // for the ith parameter check for sharing classes to all
146         // higher numbered parameters
147         for (int j = i + 1; j < fm.numParameters(); ++j) {
148
149           // skip parameters with types that cannot reference
150           // into the heap
151           if( !shouldAnalysisTrack( fm.getParameter( j ).getType() ) ) {
152             continue;
153           }
154
155
156           common = hasPotentialSharing(td, i, j);
157           if (!common.isEmpty()) {
158             foundSomeSharing = true;
159             ++numSharing;
160             if (!tabularOutput) {
161               bw.write("Potential sharing between parameters " + i
162                        + " and " + j + ".\n");
163               bw.write(prettyPrintNodeSet(common) + "\n");
164             }
165           }
166         }
167
168         // for the ith parameter, check for sharing classes against
169         // the set of allocation sites reachable from this
170         // task context
171         Iterator allocItr = allocSites.iterator();
172         while (allocItr.hasNext()) {
173           AllocSite as = (AllocSite) allocItr.next();
174           common = hasPotentialSharing(td, i, as);
175           if (!common.isEmpty()) {
176             foundSomeSharing = true;
177             ++numSharing;
178             if (!tabularOutput) {
179               bw.write("Potential sharing between parameter " + i
180                        + " and " + as.getFlatNew() + ".\n");
181               bw.write(prettyPrintNodeSet(common) + "\n");
182             }
183           }
184         }
185       }
186
187       // for each allocation site check for sharing classes with
188       // other allocation sites in the context of execution
189       // of this task
190       HashSet<AllocSite> outerChecked = new HashSet<AllocSite>();
191       Iterator allocItr1 = allocSites.iterator();
192       while (allocItr1.hasNext()) {
193         AllocSite as1 = (AllocSite) allocItr1.next();
194
195         Iterator allocItr2 = allocSites.iterator();
196         while (allocItr2.hasNext()) {
197           AllocSite as2 = (AllocSite) allocItr2.next();
198
199           if (!outerChecked.contains(as2)) {
200             common = hasPotentialSharing(td, as1, as2);
201
202             if (!common.isEmpty()) {
203               foundSomeSharing = true;
204               ++numSharing;
205               if (!tabularOutput) {
206                 bw.write("Potential sharing between "
207                          + as1.getFlatNew() + " and "
208                          + as2.getFlatNew() + ".\n");
209                 bw.write(prettyPrintNodeSet(common) + "\n");
210               }
211             }
212           }
213         }
214
215         outerChecked.add(as1);
216       }
217
218       if (!foundSomeSharing) {
219         if (!tabularOutput) {
220           bw.write("No sharing between flagged objects in Task " + td
221                    + ".\n");
222         }
223       }
224     }
225
226                 
227     if (tabularOutput) {
228       bw.write(" & " + numSharing + " & " + justTime + " & " + numLines
229                + " & " + numMethodsAnalyzed() + " \\\\\n");
230     } else {
231       bw.write("\nNumber sharing classes: "+numSharing);
232     }
233
234     bw.close();
235   }
236         
237   // this version of writeAllSharing is for Java programs that have no tasks
238   public void writeAllSharingJava(String outputFile, 
239                                   String timeReport,
240                                   String justTime,
241                                   boolean tabularOutput,
242                                   int numLines
243                                   )
244     throws java.io.IOException {
245     checkAnalysisComplete();
246
247     assert !state.TASK;
248
249     int numSharing = 0;
250
251     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile));
252     
253     bw.write("Conducting disjoint reachability analysis with allocation depth = "
254              + allocationDepth + "\n");
255     bw.write(timeReport + "\n\n");
256
257     boolean foundSomeSharing = false;
258
259     Descriptor d = typeUtil.getMain();
260     HashSet<AllocSite> allocSites = getFlaggedAllocationSites(d);
261
262     // for each allocation site check for sharing classes with
263     // other allocation sites in the context of execution
264     // of this task
265     HashSet<AllocSite> outerChecked = new HashSet<AllocSite>();
266     Iterator allocItr1 = allocSites.iterator();
267     while (allocItr1.hasNext()) {
268       AllocSite as1 = (AllocSite) allocItr1.next();
269
270       Iterator allocItr2 = allocSites.iterator();
271       while (allocItr2.hasNext()) {
272         AllocSite as2 = (AllocSite) allocItr2.next();
273
274         if (!outerChecked.contains(as2)) {
275           Set<HeapRegionNode> common = hasPotentialSharing(d,
276                                                            as1, as2);
277
278           if (!common.isEmpty()) {
279             foundSomeSharing = true;
280             bw.write("Potential sharing between "
281                      + as1.getDisjointAnalysisId() + " and "
282                      + as2.getDisjointAnalysisId() + ".\n");
283             bw.write(prettyPrintNodeSet(common) + "\n");
284             ++numSharing;
285           }
286         }
287       }
288
289       outerChecked.add(as1);
290     }
291
292     if (!foundSomeSharing) {
293       bw.write("No sharing classes between flagged objects found.\n");
294     } else {
295       bw.write("\nNumber sharing classes: "+numSharing);
296     }
297
298     bw.write("Number of methods analyzed: "+numMethodsAnalyzed()+"\n");
299
300     bw.close();
301   }
302           
303   ///////////////////////////////////////////
304   //
305   // end public interface
306   //
307   ///////////////////////////////////////////
308
309   protected void checkAnalysisComplete() {
310     if( !analysisComplete ) {
311       throw new Error("Warning: public interface method called while analysis is running.");
312     }
313   } 
314
315
316   // run in faster mode, only when bugs wrung out!
317   public static boolean releaseMode;
318
319   // use command line option to set this, analysis
320   // should attempt to be deterministic
321   public static boolean determinismDesired;
322
323   // when we want to enforce determinism in the 
324   // analysis we need to sort descriptors rather
325   // than toss them in efficient sets, use this
326   public static DescriptorComparator dComp =
327     new DescriptorComparator();
328
329
330   // data from the compiler
331   public State            state;
332   public CallGraph        callGraph;
333   public Liveness         liveness;
334   public ArrayReferencees arrayReferencees;
335   public TypeUtil         typeUtil;
336   public int              allocationDepth;
337   
338   // data structure for public interface
339   private Hashtable< Descriptor, HashSet<AllocSite> > 
340     mapDescriptorToAllocSiteSet;
341
342   
343   // for public interface methods to warn that they
344   // are grabbing results during analysis
345   private boolean analysisComplete;
346
347
348   // used to identify HeapRegionNode objects
349   // A unique ID equates an object in one
350   // ownership graph with an object in another
351   // graph that logically represents the same
352   // heap region
353   // start at 10 and increment to reserve some
354   // IDs for special purposes
355   static protected int uniqueIDcount = 10;
356
357
358   // An out-of-scope method created by the
359   // analysis that has no parameters, and
360   // appears to allocate the command line
361   // arguments, then invoke the source code's
362   // main method.  The purpose of this is to
363   // provide the analysis with an explicit
364   // top-level context with no parameters
365   protected MethodDescriptor mdAnalysisEntry;
366   protected FlatMethod       fmAnalysisEntry;
367
368   // main method defined by source program
369   protected MethodDescriptor mdSourceEntry;
370
371   // the set of task and/or method descriptors
372   // reachable in call graph
373   protected Set<Descriptor> 
374     descriptorsToAnalyze;
375
376   // current descriptors to visit in fixed-point
377   // interprocedural analysis, prioritized by
378   // dependency in the call graph
379   protected Stack<Descriptor>
380     descriptorsToVisitStack;
381   protected PriorityQueue<DescriptorQWrapper> 
382     descriptorsToVisitQ;
383   
384   // a duplication of the above structure, but
385   // for efficient testing of inclusion
386   protected HashSet<Descriptor> 
387     descriptorsToVisitSet;
388
389   // storage for priorities (doesn't make sense)
390   // to add it to the Descriptor class, just in
391   // this analysis
392   protected Hashtable<Descriptor, Integer> 
393     mapDescriptorToPriority;
394
395   // when analyzing a method and scheduling more:
396   // remember set of callee's enqueued for analysis
397   // so they can be put on top of the callers in
398   // the stack-visit mode
399   protected Set<Descriptor>
400     calleesToEnqueue;
401
402   // maps a descriptor to its current partial result
403   // from the intraprocedural fixed-point analysis--
404   // then the interprocedural analysis settles, this
405   // mapping will have the final results for each
406   // method descriptor
407   protected Hashtable<Descriptor, ReachGraph> 
408     mapDescriptorToCompleteReachGraph;
409
410   // maps a descriptor to its known dependents: namely
411   // methods or tasks that call the descriptor's method
412   // AND are part of this analysis (reachable from main)
413   protected Hashtable< Descriptor, Set<Descriptor> >
414     mapDescriptorToSetDependents;
415
416   // maps each flat new to one analysis abstraction
417   // allocate site object, these exist outside reach graphs
418   protected Hashtable<FlatNew, AllocSite>
419     mapFlatNewToAllocSite;
420
421   // maps intergraph heap region IDs to intergraph
422   // allocation sites that created them, a redundant
423   // structure for efficiency in some operations
424   protected Hashtable<Integer, AllocSite>
425     mapHrnIdToAllocSite;
426
427   // maps a method to its initial heap model (IHM) that
428   // is the set of reachability graphs from every caller
429   // site, all merged together.  The reason that we keep
430   // them separate is that any one call site's contribution
431   // to the IHM may changed along the path to the fixed point
432   protected Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >
433     mapDescriptorToIHMcontributions;
434
435   // additionally, keep a mapping from descriptors to the
436   // merged in-coming initial context, because we want this
437   // initial context to be STRICTLY MONOTONIC
438   protected Hashtable<Descriptor, ReachGraph>
439     mapDescriptorToInitialContext;
440
441   // make the result for back edges analysis-wide STRICTLY
442   // MONOTONIC as well, but notice we use FlatNode as the
443   // key for this map: in case we want to consider other
444   // nodes as back edge's in future implementations
445   protected Hashtable<FlatNode, ReachGraph>
446     mapBackEdgeToMonotone;
447
448
449   public static final String arrayElementFieldName = "___element_";
450   static protected Hashtable<TypeDescriptor, FieldDescriptor>
451     mapTypeToArrayField;
452
453   // for controlling DOT file output
454   protected boolean writeFinalDOTs;
455   protected boolean writeAllIncrementalDOTs;
456
457   // supporting DOT output--when we want to write every
458   // partial method result, keep a tally for generating
459   // unique filenames
460   protected Hashtable<Descriptor, Integer>
461     mapDescriptorToNumUpdates;
462   
463   //map task descriptor to initial task parameter 
464   protected Hashtable<Descriptor, ReachGraph>
465     mapDescriptorToReachGraph;
466
467   protected PointerMethod pm;
468
469   static protected Hashtable<FlatNode, ReachGraph> fn2rg =
470     new Hashtable<FlatNode, ReachGraph>();
471
472   private Hashtable<FlatCall, Descriptor> fc2enclosing;
473   
474
475
476   // allocate various structures that are not local
477   // to a single class method--should be done once
478   protected void allocateStructures() {
479     
480     if( determinismDesired ) {
481       // use an ordered set
482       descriptorsToAnalyze = new TreeSet<Descriptor>( dComp );      
483     } else {
484       // otherwise use a speedy hashset
485       descriptorsToAnalyze = new HashSet<Descriptor>();
486     }
487
488     mapDescriptorToCompleteReachGraph =
489       new Hashtable<Descriptor, ReachGraph>();
490
491     mapDescriptorToNumUpdates =
492       new Hashtable<Descriptor, Integer>();
493
494     mapDescriptorToSetDependents =
495       new Hashtable< Descriptor, Set<Descriptor> >();
496
497     mapFlatNewToAllocSite = 
498       new Hashtable<FlatNew, AllocSite>();
499
500     mapDescriptorToIHMcontributions =
501       new Hashtable< Descriptor, Hashtable< FlatCall, ReachGraph > >();
502
503     mapDescriptorToInitialContext =
504       new Hashtable<Descriptor, ReachGraph>();    
505
506     mapBackEdgeToMonotone =
507       new Hashtable<FlatNode, ReachGraph>();
508
509     mapHrnIdToAllocSite =
510       new Hashtable<Integer, AllocSite>();
511
512     mapTypeToArrayField = 
513       new Hashtable <TypeDescriptor, FieldDescriptor>();
514
515     if( state.DISJOINTDVISITSTACK ||
516         state.DISJOINTDVISITSTACKEESONTOP 
517         ) {
518       descriptorsToVisitStack =
519         new Stack<Descriptor>();
520     }
521
522     if( state.DISJOINTDVISITPQUE ) {
523       descriptorsToVisitQ =
524         new PriorityQueue<DescriptorQWrapper>();
525     }
526
527     descriptorsToVisitSet =
528       new HashSet<Descriptor>();
529
530     mapDescriptorToPriority =
531       new Hashtable<Descriptor, Integer>();
532     
533     calleesToEnqueue = 
534       new HashSet<Descriptor>();    
535
536     mapDescriptorToAllocSiteSet =
537         new Hashtable<Descriptor,    HashSet<AllocSite> >();
538     
539     mapDescriptorToReachGraph = 
540         new Hashtable<Descriptor, ReachGraph>();
541
542     pm = new PointerMethod();
543
544     fc2enclosing = new Hashtable<FlatCall, Descriptor>();
545   }
546
547
548
549   // this analysis generates a disjoint reachability
550   // graph for every reachable method in the program
551   public DisjointAnalysis( State            s,
552                            TypeUtil         tu,
553                            CallGraph        cg,
554                            Liveness         l,
555                            ArrayReferencees ar
556                            ) throws java.io.IOException {
557     init( s, tu, cg, l, ar );
558   }
559   
560   protected void init( State            state,
561                        TypeUtil         typeUtil,
562                        CallGraph        callGraph,
563                        Liveness         liveness,
564                        ArrayReferencees arrayReferencees
565                        ) throws java.io.IOException {
566           
567     analysisComplete = false;
568     
569     this.state                   = state;
570     this.typeUtil                = typeUtil;
571     this.callGraph               = callGraph;
572     this.liveness                = liveness;
573     this.arrayReferencees        = arrayReferencees;
574     this.allocationDepth         = state.DISJOINTALLOCDEPTH;
575     this.releaseMode             = state.DISJOINTRELEASEMODE;
576     this.determinismDesired      = state.DISJOINTDETERMINISM;
577
578     this.writeFinalDOTs          = state.DISJOINTWRITEDOTS && !state.DISJOINTWRITEALL;
579     this.writeAllIncrementalDOTs = state.DISJOINTWRITEDOTS &&  state.DISJOINTWRITEALL;
580
581     this.takeDebugSnapshots      = state.DISJOINTSNAPSYMBOL != null;
582     this.descSymbolDebug         = state.DISJOINTSNAPSYMBOL;
583     this.visitStartCapture       = state.DISJOINTSNAPVISITTOSTART;
584     this.numVisitsToCapture      = state.DISJOINTSNAPNUMVISITS;
585     this.stopAfterCapture        = state.DISJOINTSNAPSTOPAFTER;
586     this.snapVisitCounter        = 1; // count visits from 1 (user will write 1, means 1st visit)
587     this.snapNodeCounter         = 0; // count nodes from 0
588
589     assert
590       state.DISJOINTDVISITSTACK ||
591       state.DISJOINTDVISITPQUE  ||
592       state.DISJOINTDVISITSTACKEESONTOP;
593     assert !(state.DISJOINTDVISITSTACK && state.DISJOINTDVISITPQUE);
594     assert !(state.DISJOINTDVISITSTACK && state.DISJOINTDVISITSTACKEESONTOP);
595     assert !(state.DISJOINTDVISITPQUE  && state.DISJOINTDVISITSTACKEESONTOP);
596             
597     // set some static configuration for ReachGraphs
598     ReachGraph.allocationDepth = allocationDepth;
599     ReachGraph.typeUtil        = typeUtil;
600
601     ReachGraph.debugCallSiteVisitStartCapture
602       = state.DISJOINTDEBUGCALLVISITTOSTART;
603
604     ReachGraph.debugCallSiteNumVisitsToCapture
605       = state.DISJOINTDEBUGCALLNUMVISITS;
606
607     ReachGraph.debugCallSiteStopAfter
608       = state.DISJOINTDEBUGCALLSTOPAFTER;
609
610     ReachGraph.debugCallSiteVisitCounter 
611       = 0; // count visits from 1, is incremented before first visit
612     
613     
614
615     allocateStructures();
616
617     double timeStartAnalysis = (double) System.nanoTime();
618
619     // start interprocedural fixed-point computation
620     analyzeMethods();
621     analysisComplete=true;
622
623     double timeEndAnalysis = (double) System.nanoTime();
624     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
625     String treport = String.format( "The reachability analysis took %.3f sec.", dt );
626     String justtime = String.format( "%.2f", dt );
627     System.out.println( treport );
628
629     if( writeFinalDOTs && !writeAllIncrementalDOTs ) {
630       writeFinalGraphs();      
631     }
632
633     if( state.DISJOINTWRITEIHMS ) {
634       writeFinalIHMs();
635     }
636
637     if( state.DISJOINTWRITEINITCONTEXTS ) {
638       writeInitialContexts();
639     }
640
641     if( state.DISJOINTALIASFILE != null ) {
642       if( state.TASK ) {
643         writeAllSharing(state.DISJOINTALIASFILE, treport, justtime, state.DISJOINTALIASTAB, state.lines);
644       } else {
645         writeAllSharingJava(state.DISJOINTALIASFILE, 
646                             treport, 
647                             justtime, 
648                             state.DISJOINTALIASTAB, 
649                             state.lines
650                             );
651       }
652     }
653   }
654
655
656   protected boolean moreDescriptorsToVisit() {
657     if( state.DISJOINTDVISITSTACK ||
658         state.DISJOINTDVISITSTACKEESONTOP
659         ) {
660       return !descriptorsToVisitStack.isEmpty();
661
662     } else if( state.DISJOINTDVISITPQUE ) {
663       return !descriptorsToVisitQ.isEmpty();
664     }
665
666     throw new Error( "Neither descriptor visiting mode set" );
667   }
668
669
670   // fixed-point computation over the call graph--when a
671   // method's callees are updated, it must be reanalyzed
672   protected void analyzeMethods() throws java.io.IOException {  
673
674     // task or non-task (java) mode determines what the roots
675     // of the call chain are, and establishes the set of methods
676     // reachable from the roots that will be analyzed
677     
678     if( state.TASK ) {
679       System.out.println( "Bamboo mode..." );
680       
681       Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();      
682       while( taskItr.hasNext() ) {
683         TaskDescriptor td = (TaskDescriptor) taskItr.next();
684         if( !descriptorsToAnalyze.contains( td ) ) {
685           // add all methods transitively reachable from the
686           // tasks as well
687           descriptorsToAnalyze.add( td );
688           descriptorsToAnalyze.addAll( callGraph.getAllMethods( td ) );
689         }         
690       }
691       
692     } else {
693       System.out.println( "Java mode..." );
694
695       // add all methods transitively reachable from the
696       // source's main to set for analysis
697       mdSourceEntry = typeUtil.getMain();
698       descriptorsToAnalyze.add( mdSourceEntry );
699       descriptorsToAnalyze.addAll( callGraph.getAllMethods( mdSourceEntry ) );
700       
701       // fabricate an empty calling context that will call
702       // the source's main, but call graph doesn't know
703       // about it, so explicitly add it
704       makeAnalysisEntryMethod( mdSourceEntry );
705       descriptorsToAnalyze.add( mdAnalysisEntry );
706     }
707
708
709     // now, depending on the interprocedural mode for visiting 
710     // methods, set up the needed data structures
711
712     if( state.DISJOINTDVISITPQUE ) {
713     
714       // topologically sort according to the call graph so 
715       // leaf calls are last, helps build contexts up first
716       LinkedList<Descriptor> sortedDescriptors = 
717         topologicalSort( descriptorsToAnalyze );
718
719       // add sorted descriptors to priority queue, and duplicate
720       // the queue as a set for efficiently testing whether some
721       // method is marked for analysis
722       int p = 0;
723       Iterator<Descriptor> dItr;
724
725       // for the priority queue, give items at the head
726       // of the sorted list a low number (highest priority)
727       while( !sortedDescriptors.isEmpty() ) {
728         Descriptor d = sortedDescriptors.removeFirst();
729         mapDescriptorToPriority.put( d, new Integer( p ) );
730         descriptorsToVisitQ.add( new DescriptorQWrapper( p, d ) );
731         descriptorsToVisitSet.add( d );
732         ++p;
733       }
734
735     } else if( state.DISJOINTDVISITSTACK ||
736                state.DISJOINTDVISITSTACKEESONTOP 
737                ) {
738       // if we're doing the stack scheme, just throw the root
739       // method or tasks on the stack
740       if( state.TASK ) {
741         Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();      
742         while( taskItr.hasNext() ) {
743           TaskDescriptor td = (TaskDescriptor) taskItr.next();
744           descriptorsToVisitStack.add( td );
745           descriptorsToVisitSet.add( td );
746         }
747         
748       } else {
749         descriptorsToVisitStack.add( mdAnalysisEntry );
750         descriptorsToVisitSet.add( mdAnalysisEntry );
751       }
752
753     } else {
754       throw new Error( "Unknown method scheduling mode" );
755     }
756
757
758     // analyze scheduled methods until there are no more to visit
759     while( moreDescriptorsToVisit() ) {
760       Descriptor d = null;
761
762       if( state.DISJOINTDVISITSTACK ||
763           state.DISJOINTDVISITSTACKEESONTOP
764           ) {
765         d = descriptorsToVisitStack.pop();
766
767       } else if( state.DISJOINTDVISITPQUE ) {
768         d = descriptorsToVisitQ.poll().getDescriptor();
769       }
770
771       assert descriptorsToVisitSet.contains( d );
772       descriptorsToVisitSet.remove( d );
773
774       // because the task or method descriptor just extracted
775       // was in the "to visit" set it either hasn't been analyzed
776       // yet, or some method that it depends on has been
777       // updated.  Recompute a complete reachability graph for
778       // this task/method and compare it to any previous result.
779       // If there is a change detected, add any methods/tasks
780       // that depend on this one to the "to visit" set.
781
782       System.out.println( "Analyzing " + d );
783
784       if( state.DISJOINTDVISITSTACKEESONTOP ) {
785         assert calleesToEnqueue.isEmpty();
786       }
787
788       ReachGraph rg     = analyzeMethod( d );
789       ReachGraph rgPrev = getPartial( d );
790       
791       if( !rg.equals( rgPrev ) ) {
792         setPartial( d, rg );
793         
794         if( state.DISJOINTDEBUGSCHEDULING ) {
795           System.out.println( "  complete graph changed, scheduling callers for analysis:" );
796         }
797
798         // results for d changed, so enqueue dependents
799         // of d for further analysis
800         Iterator<Descriptor> depsItr = getDependents( d ).iterator();
801         while( depsItr.hasNext() ) {
802           Descriptor dNext = depsItr.next();
803           enqueue( dNext );
804
805           if( state.DISJOINTDEBUGSCHEDULING ) {
806             System.out.println( "    "+dNext );
807           }
808         }
809       }
810
811       // whether or not the method under analysis changed,
812       // we may have some callees that are scheduled for 
813       // more analysis, and they should go on the top of
814       // the stack now (in other method-visiting modes they
815       // are already enqueued at this point
816       if( state.DISJOINTDVISITSTACKEESONTOP ) {
817         Iterator<Descriptor> depsItr = calleesToEnqueue.iterator();
818         while( depsItr.hasNext() ) {
819           Descriptor dNext = depsItr.next();
820           enqueue( dNext );
821         }
822         calleesToEnqueue.clear();
823       }     
824
825     }   
826   }
827
828   protected ReachGraph analyzeMethod( Descriptor d ) 
829     throws java.io.IOException {
830
831     // get the flat code for this descriptor
832     FlatMethod fm;
833     if( d == mdAnalysisEntry ) {
834       fm = fmAnalysisEntry;
835     } else {
836       fm = state.getMethodFlat( d );
837     }
838     pm.analyzeMethod( fm );
839
840     // intraprocedural work set
841     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
842     flatNodesToVisit.add( fm );
843
844     // if determinism is desired by client, shadow the
845     // set with a queue to make visit order deterministic
846     Queue<FlatNode> flatNodesToVisitQ = null;
847     if( determinismDesired ) {
848       flatNodesToVisitQ = new LinkedList<FlatNode>();
849       flatNodesToVisitQ.add( fm );
850     }
851     
852     // mapping of current partial results
853     Hashtable<FlatNode, ReachGraph> mapFlatNodeToReachGraph =
854       new Hashtable<FlatNode, ReachGraph>();
855
856     // the set of return nodes partial results that will be combined as
857     // the final, conservative approximation of the entire method
858     HashSet<FlatReturnNode> setReturns = new HashSet<FlatReturnNode>();
859
860     while( !flatNodesToVisit.isEmpty() ) {
861
862       FlatNode fn;      
863       if( determinismDesired ) {
864         assert !flatNodesToVisitQ.isEmpty();
865         fn = flatNodesToVisitQ.remove();
866       } else {
867         fn = flatNodesToVisit.iterator().next();
868       }
869       flatNodesToVisit.remove( fn );
870
871       // effect transfer function defined by this node,
872       // then compare it to the old graph at this node
873       // to see if anything was updated.
874
875       ReachGraph rg = new ReachGraph();
876       TaskDescriptor taskDesc;
877       if(fn instanceof FlatMethod && (taskDesc=((FlatMethod)fn).getTask())!=null){
878           if(mapDescriptorToReachGraph.containsKey(taskDesc)){
879                   // retrieve existing reach graph if it is not first time
880                   rg=mapDescriptorToReachGraph.get(taskDesc);
881           }else{
882                   // create initial reach graph for a task
883                   rg=createInitialTaskReachGraph((FlatMethod)fn);
884                   rg.globalSweep();
885                   mapDescriptorToReachGraph.put(taskDesc, rg);
886           }
887       }
888
889       // start by merging all node's parents' graphs
890       for( int i = 0; i < pm.numPrev(fn); ++i ) {
891         FlatNode pn = pm.getPrev(fn,i);
892         if( mapFlatNodeToReachGraph.containsKey( pn ) ) {
893           ReachGraph rgParent = mapFlatNodeToReachGraph.get( pn );
894           rg.merge( rgParent );
895         }
896       }
897
898
899       if( takeDebugSnapshots && 
900           d.getSymbol().equals( descSymbolDebug ) 
901           ) {
902         debugSnapshot( rg, fn, true );
903       }
904
905
906       // modify rg with appropriate transfer function
907       rg = analyzeFlatNode( d, fm, fn, setReturns, rg );
908
909
910       if( takeDebugSnapshots && 
911           d.getSymbol().equals( descSymbolDebug ) 
912           ) {
913         debugSnapshot( rg, fn, false );
914         ++snapNodeCounter;
915       }
916           
917
918       // if the results of the new graph are different from
919       // the current graph at this node, replace the graph
920       // with the update and enqueue the children
921       ReachGraph rgPrev = mapFlatNodeToReachGraph.get( fn );
922       if( !rg.equals( rgPrev ) ) {
923         mapFlatNodeToReachGraph.put( fn, rg );
924
925         for( int i = 0; i < pm.numNext( fn ); i++ ) {
926           FlatNode nn = pm.getNext( fn, i );
927
928           flatNodesToVisit.add( nn );
929           if( determinismDesired ) {
930             flatNodesToVisitQ.add( nn );
931           }
932         }
933       }
934     }
935
936
937     // end by merging all return nodes into a complete
938     // reach graph that represents all possible heap
939     // states after the flat method returns
940     ReachGraph completeGraph = new ReachGraph();
941
942     assert !setReturns.isEmpty();
943     Iterator retItr = setReturns.iterator();
944     while( retItr.hasNext() ) {
945       FlatReturnNode frn = (FlatReturnNode) retItr.next();
946
947       assert mapFlatNodeToReachGraph.containsKey( frn );
948       ReachGraph rgRet = mapFlatNodeToReachGraph.get( frn );
949
950       completeGraph.merge( rgRet );
951     }
952
953
954     if( takeDebugSnapshots && 
955         d.getSymbol().equals( descSymbolDebug ) 
956         ) {
957       // increment that we've visited the debug snap
958       // method, and reset the node counter
959       System.out.println( "    @@@ debug snap at visit "+snapVisitCounter );
960       ++snapVisitCounter;
961       snapNodeCounter = 0;
962
963       if( snapVisitCounter == visitStartCapture + numVisitsToCapture && 
964           stopAfterCapture 
965           ) {
966         System.out.println( "!!! Stopping analysis after debug snap captures. !!!" );
967         System.exit( 0 );
968       }
969     }
970
971
972     return completeGraph;
973   }
974
975   
976   protected ReachGraph
977     analyzeFlatNode( Descriptor              d,
978                      FlatMethod              fmContaining,
979                      FlatNode                fn,
980                      HashSet<FlatReturnNode> setRetNodes,
981                      ReachGraph              rg
982                      ) throws java.io.IOException {
983
984     
985     // any variables that are no longer live should be
986     // nullified in the graph to reduce edges
987     //rg.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) );
988
989           
990     TempDescriptor  lhs;
991     TempDescriptor  rhs;
992     FieldDescriptor fld;
993
994     // use node type to decide what transfer function
995     // to apply to the reachability graph
996     switch( fn.kind() ) {
997
998     case FKind.FlatMethod: {
999       // construct this method's initial heap model (IHM)
1000       // since we're working on the FlatMethod, we know
1001       // the incoming ReachGraph 'rg' is empty
1002
1003       Hashtable<FlatCall, ReachGraph> heapsFromCallers = 
1004         getIHMcontributions( d );
1005
1006       Set entrySet = heapsFromCallers.entrySet();
1007       Iterator itr = entrySet.iterator();
1008       while( itr.hasNext() ) {
1009         Map.Entry  me        = (Map.Entry)  itr.next();
1010         FlatCall   fc        = (FlatCall)   me.getKey();
1011         ReachGraph rgContrib = (ReachGraph) me.getValue();
1012
1013         assert fc.getMethod().equals( d );
1014
1015         rg.merge( rgContrib );
1016       }
1017
1018       // additionally, we are enforcing STRICT MONOTONICITY for the
1019       // method's initial context, so grow the context by whatever
1020       // the previously computed context was, and put the most
1021       // up-to-date context back in the map
1022       ReachGraph rgPrevContext = mapDescriptorToInitialContext.get( d );
1023       rg.merge( rgPrevContext );      
1024       mapDescriptorToInitialContext.put( d, rg );
1025
1026     } break;
1027       
1028     case FKind.FlatOpNode:
1029       FlatOpNode fon = (FlatOpNode) fn;
1030       if( fon.getOp().getOp() == Operation.ASSIGN ) {
1031         lhs = fon.getDest();
1032         rhs = fon.getLeft();
1033         rg.assignTempXEqualToTempY( lhs, rhs );
1034       }
1035       break;
1036
1037     case FKind.FlatCastNode:
1038       FlatCastNode fcn = (FlatCastNode) fn;
1039       lhs = fcn.getDst();
1040       rhs = fcn.getSrc();
1041
1042       TypeDescriptor td = fcn.getType();
1043       assert td != null;
1044       
1045       rg.assignTempXEqualToCastedTempY( lhs, rhs, td );
1046       break;
1047
1048     case FKind.FlatFieldNode:
1049       FlatFieldNode ffn = (FlatFieldNode) fn;
1050       lhs = ffn.getDst();
1051       rhs = ffn.getSrc();
1052       fld = ffn.getField();
1053       if( shouldAnalysisTrack( fld.getType() ) ) {
1054         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld );
1055       }          
1056       break;
1057
1058     case FKind.FlatSetFieldNode:
1059       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1060       lhs = fsfn.getDst();
1061       fld = fsfn.getField();
1062       rhs = fsfn.getSrc();
1063       if( shouldAnalysisTrack( fld.getType() ) ) {
1064         rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs );
1065       }           
1066       break;
1067
1068     case FKind.FlatElementNode:
1069       FlatElementNode fen = (FlatElementNode) fn;
1070       lhs = fen.getDst();
1071       rhs = fen.getSrc();
1072       if( shouldAnalysisTrack( lhs.getType() ) ) {
1073
1074         assert rhs.getType() != null;
1075         assert rhs.getType().isArray();
1076         
1077         TypeDescriptor  tdElement = rhs.getType().dereference();
1078         FieldDescriptor fdElement = getArrayField( tdElement );
1079   
1080         rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement );
1081       }
1082       break;
1083
1084     case FKind.FlatSetElementNode:
1085       FlatSetElementNode fsen = (FlatSetElementNode) fn;
1086
1087       if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) {
1088         // skip this node if it cannot create new reachability paths
1089         break;
1090       }
1091
1092       lhs = fsen.getDst();
1093       rhs = fsen.getSrc();
1094       if( shouldAnalysisTrack( rhs.getType() ) ) {
1095
1096         assert lhs.getType() != null;
1097         assert lhs.getType().isArray();
1098         
1099         TypeDescriptor  tdElement = lhs.getType().dereference();
1100         FieldDescriptor fdElement = getArrayField( tdElement );
1101
1102         rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs );
1103       }
1104       break;
1105       
1106     case FKind.FlatNew:
1107       FlatNew fnn = (FlatNew) fn;
1108       lhs = fnn.getDst();
1109       if( shouldAnalysisTrack( lhs.getType() ) ) {
1110         AllocSite as = getAllocSiteFromFlatNewPRIVATE( fnn );   
1111         rg.assignTempEqualToNewAlloc( lhs, as );
1112       }
1113       break;
1114
1115     case FKind.FlatSESEEnterNode:
1116       FlatSESEEnterNode sese = (FlatSESEEnterNode) fn;
1117       rg.taintLiveTemps( sese,
1118                          liveness.getLiveInTemps( fmContaining, fn ) 
1119                          );
1120       break;
1121
1122     case FKind.FlatSESEExitNode:
1123       FlatSESEExitNode fsexn = (FlatSESEExitNode) fn;
1124       rg.removeInContextTaints( fsexn.getFlatEnter() );
1125       break;
1126       
1127     case FKind.FlatCall: {
1128       Descriptor mdCaller;
1129       if( fmContaining.getMethod() != null ){
1130         mdCaller = fmContaining.getMethod();
1131       } else {
1132         mdCaller = fmContaining.getTask();
1133       }      
1134       FlatCall         fc       = (FlatCall) fn;
1135       MethodDescriptor mdCallee = fc.getMethod();
1136       FlatMethod       fmCallee = state.getMethodFlat( mdCallee );
1137
1138
1139       boolean debugCallSite =
1140         mdCaller.getSymbol().equals( state.DISJOINTDEBUGCALLER ) &&
1141         mdCallee.getSymbol().equals( state.DISJOINTDEBUGCALLEE );
1142
1143       boolean writeDebugDOTs = false;
1144       boolean stopAfter      = false;
1145       if( debugCallSite ) {
1146         ++ReachGraph.debugCallSiteVisitCounter;
1147         System.out.println( "    $$$ Debug call site visit "+
1148                             ReachGraph.debugCallSiteVisitCounter+
1149                             " $$$"
1150                             );
1151         if( 
1152            (ReachGraph.debugCallSiteVisitCounter >= 
1153             ReachGraph.debugCallSiteVisitStartCapture)  &&
1154            
1155            (ReachGraph.debugCallSiteVisitCounter < 
1156             ReachGraph.debugCallSiteVisitStartCapture + 
1157             ReachGraph.debugCallSiteNumVisitsToCapture)
1158             ) {
1159           writeDebugDOTs = true;
1160           System.out.println( "      $$$ Capturing this call site visit $$$" );
1161           if( ReachGraph.debugCallSiteStopAfter &&
1162               (ReachGraph.debugCallSiteVisitCounter == 
1163                ReachGraph.debugCallSiteVisitStartCapture + 
1164                ReachGraph.debugCallSiteNumVisitsToCapture - 1)
1165               ) {
1166             stopAfter = true;
1167           }
1168         }
1169       }
1170
1171
1172       // calculate the heap this call site can reach--note this is
1173       // not used for the current call site transform, we are
1174       // grabbing this heap model for future analysis of the callees,
1175       // so if different results emerge we will return to this site
1176       ReachGraph heapForThisCall_old = 
1177         getIHMcontribution( mdCallee, fc );
1178
1179       // the computation of the callee-reachable heap
1180       // is useful for making the callee starting point
1181       // and for applying the call site transfer function
1182       Set<Integer> callerNodeIDsCopiedToCallee = 
1183         new HashSet<Integer>();
1184
1185       ReachGraph heapForThisCall_cur = 
1186         rg.makeCalleeView( fc, 
1187                            fmCallee,
1188                            callerNodeIDsCopiedToCallee,
1189                            writeDebugDOTs
1190                            );
1191
1192       if( !heapForThisCall_cur.equals( heapForThisCall_old ) ) {        
1193         // if heap at call site changed, update the contribution,
1194         // and reschedule the callee for analysis
1195         addIHMcontribution( mdCallee, fc, heapForThisCall_cur );        
1196
1197         // map a FlatCall to its enclosing method/task descriptor 
1198         // so we can write that info out later
1199         fc2enclosing.put( fc, mdCaller );
1200
1201         if( state.DISJOINTDEBUGSCHEDULING ) {
1202           System.out.println( "  context changed, scheduling callee: "+mdCallee );
1203         }
1204
1205         if( state.DISJOINTDVISITSTACKEESONTOP ) {
1206           calleesToEnqueue.add( mdCallee );
1207         } else {
1208           enqueue( mdCallee );
1209         }
1210
1211       }
1212
1213
1214       // the transformation for a call site should update the
1215       // current heap abstraction with any effects from the callee,
1216       // or if the method is virtual, the effects from any possible
1217       // callees, so find the set of callees...
1218       Set<MethodDescriptor> setPossibleCallees;
1219       if( determinismDesired ) {
1220         // use an ordered set
1221         setPossibleCallees = new TreeSet<MethodDescriptor>( dComp );        
1222       } else {
1223         // otherwise use a speedy hashset
1224         setPossibleCallees = new HashSet<MethodDescriptor>();
1225       }
1226
1227       if( mdCallee.isStatic() ) {        
1228         setPossibleCallees.add( mdCallee );
1229       } else {
1230         TypeDescriptor typeDesc = fc.getThis().getType();
1231         setPossibleCallees.addAll( callGraph.getMethods( mdCallee, 
1232                                                          typeDesc )
1233                                    );
1234       }
1235
1236       ReachGraph rgMergeOfEffects = new ReachGraph();
1237
1238       Iterator<MethodDescriptor> mdItr = setPossibleCallees.iterator();
1239       while( mdItr.hasNext() ) {
1240         MethodDescriptor mdPossible = mdItr.next();
1241         FlatMethod       fmPossible = state.getMethodFlat( mdPossible );
1242
1243         addDependent( mdPossible, // callee
1244                       d );        // caller
1245
1246         // don't alter the working graph (rg) until we compute a 
1247         // result for every possible callee, merge them all together,
1248         // then set rg to that
1249         ReachGraph rgCopy = new ReachGraph();
1250         rgCopy.merge( rg );             
1251                 
1252         ReachGraph rgEffect = getPartial( mdPossible );
1253
1254         if( rgEffect == null ) {
1255           // if this method has never been analyzed just schedule it 
1256           // for analysis and skip over this call site for now
1257           if( state.DISJOINTDVISITSTACKEESONTOP ) {
1258             calleesToEnqueue.add( mdPossible );
1259           } else {
1260             enqueue( mdPossible );
1261           }
1262           
1263           if( state.DISJOINTDEBUGSCHEDULING ) {
1264             System.out.println( "  callee hasn't been analyzed, scheduling: "+mdPossible );
1265           }
1266
1267
1268         } else {
1269           rgCopy.resolveMethodCall( fc, 
1270                                     fmPossible, 
1271                                     rgEffect,
1272                                     callerNodeIDsCopiedToCallee,
1273                                     writeDebugDOTs
1274                                     );
1275         }
1276         
1277         rgMergeOfEffects.merge( rgCopy );
1278       }
1279
1280
1281       if( stopAfter ) {
1282         System.out.println( "$$$ Exiting after requested captures of call site. $$$" );
1283         System.exit( 0 );
1284       }
1285
1286
1287       // now that we've taken care of building heap models for
1288       // callee analysis, finish this transformation
1289       rg = rgMergeOfEffects;
1290     } break;
1291       
1292
1293     case FKind.FlatReturnNode:
1294       FlatReturnNode frn = (FlatReturnNode) fn;
1295       rhs = frn.getReturnTemp();
1296       if( rhs != null && shouldAnalysisTrack( rhs.getType() ) ) {
1297         rg.assignReturnEqualToTemp( rhs );
1298       }
1299       setRetNodes.add( frn );
1300       break;
1301
1302     } // end switch
1303
1304     
1305     // dead variables were removed before the above transfer function
1306     // was applied, so eliminate heap regions and edges that are no
1307     // longer part of the abstractly-live heap graph, and sweep up
1308     // and reachability effects that are altered by the reduction
1309     //rg.abstractGarbageCollect();
1310     //rg.globalSweep();
1311
1312
1313     // back edges are strictly monotonic
1314     if( pm.isBackEdge( fn ) ) {
1315       ReachGraph rgPrevResult = mapBackEdgeToMonotone.get( fn );
1316       rg.merge( rgPrevResult );
1317       mapBackEdgeToMonotone.put( fn, rg );
1318     }
1319     
1320     // at this point rg should be the correct update
1321     // by an above transfer function, or untouched if
1322     // the flat node type doesn't affect the heap
1323     return rg;
1324   }
1325
1326
1327   
1328   // this method should generate integers strictly greater than zero!
1329   // special "shadow" regions are made from a heap region by negating
1330   // the ID
1331   static public Integer generateUniqueHeapRegionNodeID() {
1332     ++uniqueIDcount;
1333     return new Integer( uniqueIDcount );
1334   }
1335
1336
1337   
1338   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
1339     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
1340     if( fdElement == null ) {
1341       fdElement = new FieldDescriptor( new Modifiers( Modifiers.PUBLIC ),
1342                                        tdElement,
1343                                        arrayElementFieldName,
1344                                        null,
1345                                        false );
1346       mapTypeToArrayField.put( tdElement, fdElement );
1347     }
1348     return fdElement;
1349   }
1350
1351   
1352   
1353   private void writeFinalGraphs() {
1354     Set entrySet = mapDescriptorToCompleteReachGraph.entrySet();
1355     Iterator itr = entrySet.iterator();
1356     while( itr.hasNext() ) {
1357       Map.Entry  me = (Map.Entry)  itr.next();
1358       Descriptor  d = (Descriptor) me.getKey();
1359       ReachGraph rg = (ReachGraph) me.getValue();
1360
1361       rg.writeGraph( "COMPLETE"+d,
1362                      true,    // write labels (variables)                
1363                      true,    // selectively hide intermediate temp vars 
1364                      true,    // prune unreachable heap regions          
1365                      false,   // hide reachability altogether
1366                      true,    // hide subset reachability states         
1367                      true,    // hide predicates
1368                      false ); // hide edge taints                        
1369     }
1370   }
1371
1372   private void writeFinalIHMs() {
1373     Iterator d2IHMsItr = mapDescriptorToIHMcontributions.entrySet().iterator();
1374     while( d2IHMsItr.hasNext() ) {
1375       Map.Entry                        me1 = (Map.Entry)                       d2IHMsItr.next();
1376       Descriptor                         d = (Descriptor)                      me1.getKey();
1377       Hashtable<FlatCall, ReachGraph> IHMs = (Hashtable<FlatCall, ReachGraph>) me1.getValue();
1378
1379       Iterator fc2rgItr = IHMs.entrySet().iterator();
1380       while( fc2rgItr.hasNext() ) {
1381         Map.Entry  me2 = (Map.Entry)  fc2rgItr.next();
1382         FlatCall   fc  = (FlatCall)   me2.getKey();
1383         ReachGraph rg  = (ReachGraph) me2.getValue();
1384                 
1385         rg.writeGraph( "IHMPARTFOR"+d+"FROM"+fc2enclosing.get( fc )+fc,
1386                        true,   // write labels (variables)
1387                        true,   // selectively hide intermediate temp vars
1388                        true,   // hide reachability altogether
1389                        true,   // prune unreachable heap regions
1390                        true,   // hide subset reachability states
1391                        false,  // hide predicates
1392                        true ); // hide edge taints
1393       }
1394     }
1395   }
1396
1397   private void writeInitialContexts() {
1398     Set entrySet = mapDescriptorToInitialContext.entrySet();
1399     Iterator itr = entrySet.iterator();
1400     while( itr.hasNext() ) {
1401       Map.Entry  me = (Map.Entry)  itr.next();
1402       Descriptor  d = (Descriptor) me.getKey();
1403       ReachGraph rg = (ReachGraph) me.getValue();
1404
1405       rg.writeGraph( "INITIAL"+d,
1406                      true,   // write labels (variables)                
1407                      true,   // selectively hide intermediate temp vars 
1408                      true,   // prune unreachable heap regions          
1409                      false,  // hide all reachability
1410                      true,   // hide subset reachability states         
1411                      true,   // hide predicates
1412                      false );// hide edge taints                        
1413     }
1414   }
1415    
1416
1417   protected ReachGraph getPartial( Descriptor d ) {
1418     return mapDescriptorToCompleteReachGraph.get( d );
1419   }
1420
1421   protected void setPartial( Descriptor d, ReachGraph rg ) {
1422     mapDescriptorToCompleteReachGraph.put( d, rg );
1423
1424     // when the flag for writing out every partial
1425     // result is set, we should spit out the graph,
1426     // but in order to give it a unique name we need
1427     // to track how many partial results for this
1428     // descriptor we've already written out
1429     if( writeAllIncrementalDOTs ) {
1430       if( !mapDescriptorToNumUpdates.containsKey( d ) ) {
1431         mapDescriptorToNumUpdates.put( d, new Integer( 0 ) );
1432       }
1433       Integer n = mapDescriptorToNumUpdates.get( d );
1434       
1435       rg.writeGraph( d+"COMPLETE"+String.format( "%05d", n ),
1436                      true,   // write labels (variables)
1437                      true,   // selectively hide intermediate temp vars
1438                      true,   // prune unreachable heap regions
1439                      false,  // hide all reachability
1440                      true,   // hide subset reachability states
1441                      false,  // hide predicates
1442                      false); // hide edge taints
1443       
1444       mapDescriptorToNumUpdates.put( d, n + 1 );
1445     }
1446   }
1447
1448
1449
1450   // return just the allocation site associated with one FlatNew node
1451   protected AllocSite getAllocSiteFromFlatNewPRIVATE( FlatNew fnew ) {
1452
1453     if( !mapFlatNewToAllocSite.containsKey( fnew ) ) {
1454       AllocSite as = AllocSite.factory( allocationDepth, 
1455                                         fnew, 
1456                                         fnew.getDisjointId(),
1457                                         false
1458                                         );
1459
1460       // the newest nodes are single objects
1461       for( int i = 0; i < allocationDepth; ++i ) {
1462         Integer id = generateUniqueHeapRegionNodeID();
1463         as.setIthOldest( i, id );
1464         mapHrnIdToAllocSite.put( id, as );
1465       }
1466
1467       // the oldest node is a summary node
1468       as.setSummary( generateUniqueHeapRegionNodeID() );
1469
1470       mapFlatNewToAllocSite.put( fnew, as );
1471     }
1472
1473     return mapFlatNewToAllocSite.get( fnew );
1474   }
1475
1476
1477   public static boolean shouldAnalysisTrack( TypeDescriptor type ) {
1478     // don't track primitive types, but an array
1479     // of primitives is heap memory
1480     if( type.isImmutable() ) {
1481       return type.isArray();
1482     }
1483
1484     // everything else is an object
1485     return true;
1486   }
1487
1488   protected int numMethodsAnalyzed() {    
1489     return descriptorsToAnalyze.size();
1490   }
1491   
1492
1493   
1494   
1495   
1496   // Take in source entry which is the program's compiled entry and
1497   // create a new analysis entry, a method that takes no parameters
1498   // and appears to allocate the command line arguments and call the
1499   // source entry with them.  The purpose of this analysis entry is
1500   // to provide a top-level method context with no parameters left.
1501   protected void makeAnalysisEntryMethod( MethodDescriptor mdSourceEntry ) {
1502
1503     Modifiers mods = new Modifiers();
1504     mods.addModifier( Modifiers.PUBLIC );
1505     mods.addModifier( Modifiers.STATIC );
1506
1507     TypeDescriptor returnType = 
1508       new TypeDescriptor( TypeDescriptor.VOID );
1509
1510     this.mdAnalysisEntry = 
1511       new MethodDescriptor( mods,
1512                             returnType,
1513                             "analysisEntryMethod"
1514                             );
1515
1516     TempDescriptor cmdLineArgs = 
1517       new TempDescriptor( "args",
1518                           mdSourceEntry.getParamType( 0 )
1519                           );
1520
1521     FlatNew fn = 
1522       new FlatNew( mdSourceEntry.getParamType( 0 ),
1523                    cmdLineArgs,
1524                    false // is global 
1525                    );
1526     
1527     TempDescriptor[] sourceEntryArgs = new TempDescriptor[1];
1528     sourceEntryArgs[0] = cmdLineArgs;
1529     
1530     FlatCall fc = 
1531       new FlatCall( mdSourceEntry,
1532                     null, // dst temp
1533                     null, // this temp
1534                     sourceEntryArgs
1535                     );
1536
1537     FlatReturnNode frn = new FlatReturnNode( null );
1538
1539     FlatExit fe = new FlatExit();
1540
1541     this.fmAnalysisEntry = 
1542       new FlatMethod( mdAnalysisEntry, 
1543                       fe
1544                       );
1545
1546     this.fmAnalysisEntry.addNext( fn );
1547     fn.addNext( fc );
1548     fc.addNext( frn );
1549     frn.addNext( fe );
1550   }
1551
1552
1553   protected LinkedList<Descriptor> topologicalSort( Set<Descriptor> toSort ) {
1554
1555     Set<Descriptor> discovered;
1556
1557     if( determinismDesired ) {
1558       // use an ordered set
1559       discovered = new TreeSet<Descriptor>( dComp );      
1560     } else {
1561       // otherwise use a speedy hashset
1562       discovered = new HashSet<Descriptor>();
1563     }
1564
1565     LinkedList<Descriptor> sorted = new LinkedList<Descriptor>();
1566   
1567     Iterator<Descriptor> itr = toSort.iterator();
1568     while( itr.hasNext() ) {
1569       Descriptor d = itr.next();
1570           
1571       if( !discovered.contains( d ) ) {
1572         dfsVisit( d, toSort, sorted, discovered );
1573       }
1574     }
1575     
1576     return sorted;
1577   }
1578   
1579   // While we're doing DFS on call graph, remember
1580   // dependencies for efficient queuing of methods
1581   // during interprocedural analysis:
1582   //
1583   // a dependent of a method decriptor d for this analysis is:
1584   //  1) a method or task that invokes d
1585   //  2) in the descriptorsToAnalyze set
1586   protected void dfsVisit( Descriptor             d,
1587                            Set       <Descriptor> toSort,                        
1588                            LinkedList<Descriptor> sorted,
1589                            Set       <Descriptor> discovered ) {
1590     discovered.add( d );
1591     
1592     // only methods have callers, tasks never do
1593     if( d instanceof MethodDescriptor ) {
1594
1595       MethodDescriptor md = (MethodDescriptor) d;
1596
1597       // the call graph is not aware that we have a fabricated
1598       // analysis entry that calls the program source's entry
1599       if( md == mdSourceEntry ) {
1600         if( !discovered.contains( mdAnalysisEntry ) ) {
1601           addDependent( mdSourceEntry,  // callee
1602                         mdAnalysisEntry // caller
1603                         );
1604           dfsVisit( mdAnalysisEntry, toSort, sorted, discovered );
1605         }
1606       }
1607
1608       // otherwise call graph guides DFS
1609       Iterator itr = callGraph.getCallerSet( md ).iterator();
1610       while( itr.hasNext() ) {
1611         Descriptor dCaller = (Descriptor) itr.next();
1612         
1613         // only consider callers in the original set to analyze
1614         if( !toSort.contains( dCaller ) ) {
1615           continue;
1616         }
1617           
1618         if( !discovered.contains( dCaller ) ) {
1619           addDependent( md,     // callee
1620                         dCaller // caller
1621                         );
1622
1623           dfsVisit( dCaller, toSort, sorted, discovered );
1624         }
1625       }
1626     }
1627     
1628     // for leaf-nodes last now!
1629     sorted.addLast( d );
1630   }
1631
1632
1633   protected void enqueue( Descriptor d ) {
1634
1635     if( !descriptorsToVisitSet.contains( d ) ) {
1636
1637       if( state.DISJOINTDVISITSTACK ||
1638           state.DISJOINTDVISITSTACKEESONTOP
1639           ) {
1640         descriptorsToVisitStack.add( d );
1641
1642       } else if( state.DISJOINTDVISITPQUE ) {
1643         Integer priority = mapDescriptorToPriority.get( d );
1644         descriptorsToVisitQ.add( new DescriptorQWrapper( priority, 
1645                                                          d ) 
1646                                  );
1647       }
1648
1649       descriptorsToVisitSet.add( d );
1650     }
1651   }
1652
1653
1654   // a dependent of a method decriptor d for this analysis is:
1655   //  1) a method or task that invokes d
1656   //  2) in the descriptorsToAnalyze set
1657   protected void addDependent( Descriptor callee, Descriptor caller ) {
1658     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1659     if( deps == null ) {
1660       deps = new HashSet<Descriptor>();
1661     }
1662     deps.add( caller );
1663     mapDescriptorToSetDependents.put( callee, deps );
1664   }
1665   
1666   protected Set<Descriptor> getDependents( Descriptor callee ) {
1667     Set<Descriptor> deps = mapDescriptorToSetDependents.get( callee );
1668     if( deps == null ) {
1669       deps = new HashSet<Descriptor>();
1670       mapDescriptorToSetDependents.put( callee, deps );
1671     }
1672     return deps;
1673   }
1674
1675   
1676   public Hashtable<FlatCall, ReachGraph> getIHMcontributions( Descriptor d ) {
1677
1678     Hashtable<FlatCall, ReachGraph> heapsFromCallers = 
1679       mapDescriptorToIHMcontributions.get( d );
1680     
1681     if( heapsFromCallers == null ) {
1682       heapsFromCallers = new Hashtable<FlatCall, ReachGraph>();
1683       mapDescriptorToIHMcontributions.put( d, heapsFromCallers );
1684     }
1685     
1686     return heapsFromCallers;
1687   }
1688
1689   public ReachGraph getIHMcontribution( Descriptor d, 
1690                                         FlatCall   fc
1691                                         ) {
1692     Hashtable<FlatCall, ReachGraph> heapsFromCallers = 
1693       getIHMcontributions( d );
1694
1695     if( !heapsFromCallers.containsKey( fc ) ) {
1696       return null;
1697     }
1698
1699     return heapsFromCallers.get( fc );
1700   }
1701
1702
1703   public void addIHMcontribution( Descriptor d,
1704                                   FlatCall   fc,
1705                                   ReachGraph rg
1706                                   ) {
1707     Hashtable<FlatCall, ReachGraph> heapsFromCallers = 
1708       getIHMcontributions( d );
1709
1710     heapsFromCallers.put( fc, rg );
1711   }
1712
1713
1714   private AllocSite createParameterAllocSite( ReachGraph     rg, 
1715                                               TempDescriptor tempDesc,
1716                                               boolean        flagRegions
1717                                               ) {
1718     
1719     FlatNew flatNew;
1720     if( flagRegions ) {
1721       flatNew = new FlatNew( tempDesc.getType(), // type
1722                              tempDesc,           // param temp
1723                              false,              // global alloc?
1724                              "param"+tempDesc    // disjoint site ID string
1725                              );
1726     } else {
1727       flatNew = new FlatNew( tempDesc.getType(), // type
1728                              tempDesc,           // param temp
1729                              false,              // global alloc?
1730                              null                // disjoint site ID string
1731                              );
1732     }
1733
1734     // create allocation site
1735     AllocSite as = AllocSite.factory( allocationDepth, 
1736                                       flatNew, 
1737                                       flatNew.getDisjointId(),
1738                                       false
1739                                       );
1740     for (int i = 0; i < allocationDepth; ++i) {
1741         Integer id = generateUniqueHeapRegionNodeID();
1742         as.setIthOldest(i, id);
1743         mapHrnIdToAllocSite.put(id, as);
1744     }
1745     // the oldest node is a summary node
1746     as.setSummary( generateUniqueHeapRegionNodeID() );
1747     
1748     rg.age(as);
1749     
1750     return as;
1751     
1752   }
1753
1754 private Set<FieldDescriptor> getFieldSetTobeAnalyzed(TypeDescriptor typeDesc){
1755         
1756         Set<FieldDescriptor> fieldSet=new HashSet<FieldDescriptor>();
1757     if(!typeDesc.isImmutable()){
1758             ClassDescriptor classDesc = typeDesc.getClassDesc();                    
1759             for (Iterator it = classDesc.getFields(); it.hasNext();) {
1760                     FieldDescriptor field = (FieldDescriptor) it.next();
1761                     TypeDescriptor fieldType = field.getType();
1762                     if (shouldAnalysisTrack( fieldType )) {
1763                         fieldSet.add(field);                    
1764                     }
1765             }
1766     }
1767     return fieldSet;
1768         
1769 }
1770
1771   private HeapRegionNode createMultiDeimensionalArrayHRN(ReachGraph rg, AllocSite alloc, HeapRegionNode srcHRN, FieldDescriptor fd, Hashtable<HeapRegionNode, HeapRegionNode> map, Hashtable<TypeDescriptor, HeapRegionNode> mapToExistingNode, ReachSet alpha ){
1772
1773         int dimCount=fd.getType().getArrayCount();
1774         HeapRegionNode prevNode=null;
1775         HeapRegionNode arrayEntryNode=null;
1776         for(int i=dimCount;i>0;i--){
1777                 TypeDescriptor typeDesc=fd.getType().dereference();//hack to get instance of type desc
1778                 typeDesc.setArrayCount(i);
1779                 TempDescriptor tempDesc=new TempDescriptor(typeDesc.getSymbol(),typeDesc);
1780                 HeapRegionNode hrnSummary ;
1781                 if(!mapToExistingNode.containsKey(typeDesc)){
1782                         AllocSite as;
1783                         if(i==dimCount){
1784                                 as = alloc;
1785                         }else{
1786                           as = createParameterAllocSite(rg, tempDesc, false);
1787                         }
1788                         // make a new reference to allocated node
1789                     hrnSummary = 
1790                                 rg.createNewHeapRegionNode(as.getSummary(), // id or null to generate a new one
1791                                                            false, // single object?
1792                                                            true, // summary?
1793                                                            false, // out-of-context?
1794                                                            as.getType(), // type
1795                                                            as, // allocation site
1796                                                            alpha, // inherent reach
1797                                                            alpha, // current reach
1798                                                            ExistPredSet.factory(rg.predTrue), // predicates
1799                                                            tempDesc.toString() // description
1800                                                            );
1801                     rg.id2hrn.put(as.getSummary(),hrnSummary);
1802                     
1803                     mapToExistingNode.put(typeDesc, hrnSummary);
1804                 }else{
1805                         hrnSummary=mapToExistingNode.get(typeDesc);
1806                 }
1807             
1808             if(prevNode==null){
1809                     // make a new reference between new summary node and source
1810               RefEdge edgeToSummary = new RefEdge(srcHRN, // source
1811                                                         hrnSummary, // dest
1812                                                         typeDesc, // type
1813                                                         fd.getSymbol(), // field name
1814                                                         alpha, // beta
1815                                                   ExistPredSet.factory(rg.predTrue), // predicates
1816                                                   null
1817                                                         );
1818                     
1819                     rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
1820                     prevNode=hrnSummary;
1821                     arrayEntryNode=hrnSummary;
1822             }else{
1823                     // make a new reference between summary nodes of array
1824                     RefEdge edgeToSummary = new RefEdge(prevNode, // source
1825                                                         hrnSummary, // dest
1826                                                         typeDesc, // type
1827                                                         arrayElementFieldName, // field name
1828                                                         alpha, // beta
1829                                                         ExistPredSet.factory(rg.predTrue), // predicates
1830                                                         null
1831                                                         );
1832                     
1833                     rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
1834                     prevNode=hrnSummary;
1835             }
1836             
1837         }
1838         
1839         // create a new obj node if obj has at least one non-primitive field
1840         TypeDescriptor type=fd.getType();
1841     if(getFieldSetTobeAnalyzed(type).size()>0){
1842         TypeDescriptor typeDesc=type.dereference();
1843         typeDesc.setArrayCount(0);
1844         if(!mapToExistingNode.containsKey(typeDesc)){
1845                 TempDescriptor tempDesc=new TempDescriptor(type.getSymbol(),typeDesc);
1846                 AllocSite as = createParameterAllocSite(rg, tempDesc, false);
1847                 // make a new reference to allocated node
1848                     HeapRegionNode hrnSummary = 
1849                                 rg.createNewHeapRegionNode(as.getSummary(), // id or null to generate a new one
1850                                                            false, // single object?
1851                                                            true, // summary?
1852                                                            false, // out-of-context?
1853                                                            typeDesc, // type
1854                                                            as, // allocation site
1855                                                            alpha, // inherent reach
1856                                                            alpha, // current reach
1857                                                            ExistPredSet.factory(rg.predTrue), // predicates
1858                                                            tempDesc.toString() // description
1859                                                            );
1860                     rg.id2hrn.put(as.getSummary(),hrnSummary);
1861                     mapToExistingNode.put(typeDesc, hrnSummary);
1862                     RefEdge edgeToSummary = new RefEdge(prevNode, // source
1863                                         hrnSummary, // dest
1864                                         typeDesc, // type
1865                                         arrayElementFieldName, // field name
1866                                         alpha, // beta
1867                                                         ExistPredSet.factory(rg.predTrue), // predicates
1868                                                         null
1869                                         );
1870                     rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
1871                     prevNode=hrnSummary;
1872         }else{
1873           HeapRegionNode hrnSummary=mapToExistingNode.get(typeDesc);
1874                 if(prevNode.getReferenceTo(hrnSummary, typeDesc, arrayElementFieldName)==null){
1875                         RefEdge edgeToSummary = new RefEdge(prevNode, // source
1876                                         hrnSummary, // dest
1877                                         typeDesc, // type
1878                                         arrayElementFieldName, // field name
1879                                         alpha, // beta
1880                                                             ExistPredSet.factory(rg.predTrue), // predicates
1881                                                             null
1882                                         );
1883                     rg.addRefEdge(prevNode, hrnSummary, edgeToSummary);
1884                 }
1885                  prevNode=hrnSummary;
1886         }
1887     }
1888         
1889         map.put(arrayEntryNode, prevNode);
1890         return arrayEntryNode;
1891 }
1892
1893 private ReachGraph createInitialTaskReachGraph(FlatMethod fm) {
1894     ReachGraph rg = new ReachGraph();
1895     TaskDescriptor taskDesc = fm.getTask();
1896     
1897     for (int idx = 0; idx < taskDesc.numParameters(); idx++) {
1898         Descriptor paramDesc = taskDesc.getParameter(idx);
1899         TypeDescriptor paramTypeDesc = taskDesc.getParamType(idx);
1900         
1901         // setup data structure
1902         Set<HashMap<HeapRegionNode, FieldDescriptor>> workSet = 
1903             new HashSet<HashMap<HeapRegionNode, FieldDescriptor>>();
1904         Hashtable<TypeDescriptor, HeapRegionNode> mapTypeToExistingSummaryNode = 
1905             new Hashtable<TypeDescriptor, HeapRegionNode>();
1906         Hashtable<HeapRegionNode, HeapRegionNode> mapToFirstDimensionArrayNode = 
1907             new Hashtable<HeapRegionNode, HeapRegionNode>();
1908         Set<String> doneSet = new HashSet<String>();
1909         
1910         TempDescriptor tempDesc = fm.getParameter(idx);
1911         
1912         AllocSite as = createParameterAllocSite(rg, tempDesc, true);
1913         VariableNode lnX = rg.getVariableNodeFromTemp(tempDesc);
1914         Integer idNewest = as.getIthOldest(0);
1915         HeapRegionNode hrnNewest = rg.id2hrn.get(idNewest);
1916
1917         // make a new reference to allocated node
1918         RefEdge edgeNew = new RefEdge(lnX, // source
1919                                       hrnNewest, // dest
1920                                       taskDesc.getParamType(idx), // type
1921                                       null, // field name
1922                                       hrnNewest.getAlpha(), // beta
1923                                       ExistPredSet.factory(rg.predTrue), // predicates
1924                                       null
1925                                       );
1926         rg.addRefEdge(lnX, hrnNewest, edgeNew);
1927
1928         // set-up a work set for class field
1929         ClassDescriptor classDesc = paramTypeDesc.getClassDesc();
1930         for (Iterator it = classDesc.getFields(); it.hasNext();) {
1931             FieldDescriptor fd = (FieldDescriptor) it.next();
1932             TypeDescriptor fieldType = fd.getType();
1933             if (shouldAnalysisTrack( fieldType )) {
1934                 HashMap<HeapRegionNode, FieldDescriptor> newMap = new HashMap<HeapRegionNode, FieldDescriptor>();
1935                 newMap.put(hrnNewest, fd);
1936                 workSet.add(newMap);
1937             }
1938         }
1939         
1940         int uniqueIdentifier = 0;
1941         while (!workSet.isEmpty()) {
1942             HashMap<HeapRegionNode, FieldDescriptor> map = workSet
1943                 .iterator().next();
1944             workSet.remove(map);
1945             
1946             Set<HeapRegionNode> key = map.keySet();
1947             HeapRegionNode srcHRN = key.iterator().next();
1948             FieldDescriptor fd = map.get(srcHRN);
1949             TypeDescriptor type = fd.getType();
1950             String doneSetIdentifier = srcHRN.getIDString() + "_" + fd;
1951             
1952             if (!doneSet.contains(doneSetIdentifier)) {
1953                 doneSet.add(doneSetIdentifier);
1954                 if (!mapTypeToExistingSummaryNode.containsKey(type)) {
1955                     // create new summary Node
1956                     TempDescriptor td = new TempDescriptor("temp"
1957                                                            + uniqueIdentifier, type);
1958                     
1959                     AllocSite allocSite;
1960                     if(type.equals(paramTypeDesc)){
1961                     //corresponding allocsite has already been created for a parameter variable.
1962                         allocSite=as;
1963                     }else{
1964                       allocSite = createParameterAllocSite(rg, td, false);
1965                     }
1966                     String strDesc = allocSite.toStringForDOT()
1967                         + "\\nsummary";
1968                     TypeDescriptor allocType=allocSite.getType();
1969                     
1970                     HeapRegionNode      hrnSummary;
1971                     if(allocType.isArray() && allocType.getArrayCount()>0){
1972                       hrnSummary=createMultiDeimensionalArrayHRN(rg,allocSite,srcHRN,fd,mapToFirstDimensionArrayNode,mapTypeToExistingSummaryNode,hrnNewest.getAlpha());
1973                     }else{                  
1974                         hrnSummary = 
1975                                         rg.createNewHeapRegionNode(allocSite.getSummary(), // id or null to generate a new one
1976                                                                    false, // single object?
1977                                                                    true, // summary?
1978                                                                    false, // out-of-context?
1979                                                                    allocSite.getType(), // type
1980                                                                    allocSite, // allocation site
1981                                                                    hrnNewest.getAlpha(), // inherent reach
1982                                                                    hrnNewest.getAlpha(), // current reach
1983                                                                    ExistPredSet.factory(rg.predTrue), // predicates
1984                                                                    strDesc // description
1985                                                                    );
1986                                     rg.id2hrn.put(allocSite.getSummary(),hrnSummary);
1987                     
1988                     // make a new reference to summary node
1989                     RefEdge edgeToSummary = new RefEdge(srcHRN, // source
1990                                                         hrnSummary, // dest
1991                                                         type, // type
1992                                                         fd.getSymbol(), // field name
1993                                                         hrnNewest.getAlpha(), // beta
1994                                                         ExistPredSet.factory(rg.predTrue), // predicates
1995                                                         null
1996                                                         );
1997                     
1998                     rg.addRefEdge(srcHRN, hrnSummary, edgeToSummary);
1999                     }               
2000                     uniqueIdentifier++;
2001                     
2002                     mapTypeToExistingSummaryNode.put(type, hrnSummary);
2003                     
2004                     // set-up a work set for  fields of the class
2005                     Set<FieldDescriptor> fieldTobeAnalyzed=getFieldSetTobeAnalyzed(type);
2006                     for (Iterator iterator = fieldTobeAnalyzed.iterator(); iterator
2007                                         .hasNext();) {
2008                                 FieldDescriptor fieldDescriptor = (FieldDescriptor) iterator
2009                                                 .next();
2010                                 HeapRegionNode newDstHRN;
2011                                 if(mapToFirstDimensionArrayNode.containsKey(hrnSummary)){
2012                                         //related heap region node is already exsited.
2013                                         newDstHRN=mapToFirstDimensionArrayNode.get(hrnSummary);
2014                                 }else{
2015                                         newDstHRN=hrnSummary;
2016                                 }
2017                                  doneSetIdentifier = newDstHRN.getIDString() + "_" + fieldDescriptor;                                                            
2018                                  if(!doneSet.contains(doneSetIdentifier)){
2019                                  // add new work item
2020                                          HashMap<HeapRegionNode, FieldDescriptor> newMap = 
2021                                             new HashMap<HeapRegionNode, FieldDescriptor>();
2022                                          newMap.put(newDstHRN, fieldDescriptor);
2023                                          workSet.add(newMap);
2024                                   }                             
2025                         }
2026                     
2027                 }else{
2028                     // if there exists corresponding summary node
2029                     HeapRegionNode hrnDst=mapTypeToExistingSummaryNode.get(type);
2030                     
2031                     RefEdge edgeToSummary = new RefEdge(srcHRN, // source
2032                                                         hrnDst, // dest
2033                                                         fd.getType(), // type
2034                                                         fd.getSymbol(), // field name
2035                                                         srcHRN.getAlpha(), // beta
2036                                                         ExistPredSet.factory(rg.predTrue), // predicates  
2037                                                         null
2038                                                         );
2039                     rg.addRefEdge(srcHRN, hrnDst, edgeToSummary);
2040                     
2041                 }               
2042             }       
2043         }           
2044     }   
2045 //    debugSnapshot(rg, fm, true);
2046     return rg;
2047 }
2048
2049 // return all allocation sites in the method (there is one allocation
2050 // site per FlatNew node in a method)
2051 private HashSet<AllocSite> getAllocationSiteSet(Descriptor d) {
2052   if( !mapDescriptorToAllocSiteSet.containsKey(d) ) {
2053     buildAllocationSiteSet(d);
2054   }
2055
2056   return mapDescriptorToAllocSiteSet.get(d);
2057
2058 }
2059
2060 private void buildAllocationSiteSet(Descriptor d) {
2061     HashSet<AllocSite> s = new HashSet<AllocSite>();
2062
2063     FlatMethod fm;
2064     if( d instanceof MethodDescriptor ) {
2065       fm = state.getMethodFlat( (MethodDescriptor) d);
2066     } else {
2067       assert d instanceof TaskDescriptor;
2068       fm = state.getMethodFlat( (TaskDescriptor) d);
2069     }
2070     pm.analyzeMethod(fm);
2071
2072     // visit every node in this FlatMethod's IR graph
2073     // and make a set of the allocation sites from the
2074     // FlatNew node's visited
2075     HashSet<FlatNode> visited = new HashSet<FlatNode>();
2076     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
2077     toVisit.add(fm);
2078
2079     while( !toVisit.isEmpty() ) {
2080       FlatNode n = toVisit.iterator().next();
2081
2082       if( n instanceof FlatNew ) {
2083         s.add(getAllocSiteFromFlatNewPRIVATE( (FlatNew) n) );
2084       }
2085
2086       toVisit.remove(n);
2087       visited.add(n);
2088
2089       for( int i = 0; i < pm.numNext(n); ++i ) {
2090         FlatNode child = pm.getNext(n, i);
2091         if( !visited.contains(child) ) {
2092           toVisit.add(child);
2093         }
2094       }
2095     }
2096
2097     mapDescriptorToAllocSiteSet.put(d, s);
2098   }
2099
2100         private HashSet<AllocSite> getFlaggedAllocationSites(Descriptor dIn) {
2101
2102                 HashSet<AllocSite> out = new HashSet<AllocSite>();
2103                 HashSet<Descriptor> toVisit = new HashSet<Descriptor>();
2104                 HashSet<Descriptor> visited = new HashSet<Descriptor>();
2105
2106                 toVisit.add(dIn);
2107
2108                 while (!toVisit.isEmpty()) {
2109                         Descriptor d = toVisit.iterator().next();
2110                         toVisit.remove(d);
2111                         visited.add(d);
2112
2113                         HashSet<AllocSite> asSet = getAllocationSiteSet(d);
2114                         Iterator asItr = asSet.iterator();
2115                         while (asItr.hasNext()) {
2116                                 AllocSite as = (AllocSite) asItr.next();
2117                                 if (as.getDisjointAnalysisId() != null) {
2118                                         out.add(as);
2119                                 }
2120                         }
2121
2122                         // enqueue callees of this method to be searched for
2123                         // allocation sites also
2124                         Set callees = callGraph.getCalleeSet(d);
2125                         if (callees != null) {
2126                                 Iterator methItr = callees.iterator();
2127                                 while (methItr.hasNext()) {
2128                                         MethodDescriptor md = (MethodDescriptor) methItr.next();
2129
2130                                         if (!visited.contains(md)) {
2131                                                 toVisit.add(md);
2132                                         }
2133                                 }
2134                         }
2135                 }
2136
2137                 return out;
2138         }
2139  
2140     
2141 private HashSet<AllocSite>
2142 getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
2143
2144   HashSet<AllocSite> asSetTotal = new HashSet<AllocSite>();
2145   HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
2146   HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
2147
2148   toVisit.add(td);
2149
2150   // traverse this task and all methods reachable from this task
2151   while( !toVisit.isEmpty() ) {
2152     Descriptor d = toVisit.iterator().next();
2153     toVisit.remove(d);
2154     visited.add(d);
2155
2156     HashSet<AllocSite> asSet = getAllocationSiteSet(d);
2157     Iterator asItr = asSet.iterator();
2158     while( asItr.hasNext() ) {
2159         AllocSite as = (AllocSite) asItr.next();
2160         TypeDescriptor typed = as.getType();
2161         if( typed != null ) {
2162           ClassDescriptor cd = typed.getClassDesc();
2163           if( cd != null && cd.hasFlags() ) {
2164             asSetTotal.add(as);
2165           }
2166         }
2167     }
2168
2169     // enqueue callees of this method to be searched for
2170     // allocation sites also
2171     Set callees = callGraph.getCalleeSet(d);
2172     if( callees != null ) {
2173         Iterator methItr = callees.iterator();
2174         while( methItr.hasNext() ) {
2175           MethodDescriptor md = (MethodDescriptor) methItr.next();
2176
2177           if( !visited.contains(md) ) {
2178             toVisit.add(md);
2179           }
2180         }
2181     }
2182   }
2183
2184   return asSetTotal;
2185 }
2186
2187   public Set<Descriptor> getDescriptorsToAnalyze() {
2188     return descriptorsToAnalyze;
2189   }
2190
2191   
2192   
2193   // get successive captures of the analysis state, use compiler
2194   // flags to control
2195   boolean takeDebugSnapshots = false;
2196   String  descSymbolDebug    = null;
2197   boolean stopAfterCapture   = false;
2198   int     snapVisitCounter   = 0;
2199   int     snapNodeCounter    = 0;
2200   int     visitStartCapture  = 0;
2201   int     numVisitsToCapture = 0;
2202
2203
2204   void debugSnapshot( ReachGraph rg, FlatNode fn, boolean in ) {
2205     if( snapVisitCounter > visitStartCapture + numVisitsToCapture ) {
2206       return;
2207     }
2208
2209     if( in ) {
2210
2211     }
2212
2213     if( snapVisitCounter >= visitStartCapture ) {
2214       System.out.println( "    @@@ snapping visit="+snapVisitCounter+
2215                           ", node="+snapNodeCounter+
2216                           " @@@" );
2217       String graphName;
2218       if( in ) {
2219         graphName = String.format( "snap%03d_%04din",
2220                                    snapVisitCounter,
2221                                    snapNodeCounter );
2222       } else {
2223         graphName = String.format( "snap%03d_%04dout",
2224                                    snapVisitCounter,
2225                                    snapNodeCounter );
2226       }
2227       if( fn != null ) {
2228         graphName = graphName + fn;
2229       }
2230       rg.writeGraph( graphName,
2231                      true,   // write labels (variables)
2232                      true,   // selectively hide intermediate temp vars
2233                      true,   // prune unreachable heap regions
2234                      false,  // hide reachability
2235                      true,   // hide subset reachability states
2236                      true,   // hide predicates
2237                      false );// hide edge taints
2238     }
2239   }
2240
2241 }