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