Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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