Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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