Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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