Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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