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