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