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       // if the results of the new graph are different from
 752       // the current graph at this node, replace the graph
 753       // with the update and enqueue the children for
 754       // processing
 755       OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
 756       if( !og.equals(ogPrev) ) {
 757         mapFlatNodeToOwnershipGraph.put(fn, og);
 758
 759         for( int i = 0; i < fn.numNext(); i++ ) {
 760           FlatNode nn = fn.getNext(i);
 761           flatNodesToVisit.add(nn);
 762         }
 763       }
 764     }
 765
 766     // end by merging all return nodes into a complete
 767     // ownership graph that represents all possible heap
 768     // states after the flat method returns
 769     OwnershipGraph completeGraph = new OwnershipGraph();
 770     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 771     while( retItr.hasNext() ) {
 772       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 773       assert mapFlatNodeToOwnershipGraph.containsKey(frn);
 774       OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
 775       completeGraph.merge(ogr);
 776     }
 777
 778     return completeGraph;
 779   }
 780
 781
 782   private OwnershipGraph
 783   analyzeFlatNode(MethodContext mc,
 784                   FlatNode fn,
 785                   HashSet<FlatReturnNode> setRetNodes,
 786                   OwnershipGraph og) throws java.io.IOException {
 787
 788     TempDescriptor lhs;
 789     TempDescriptor rhs;
 790     FieldDescriptor fld;
 791
 792     // use node type to decide what alterations to make
 793     // to the ownership graph
 794     switch( fn.kind() ) {
 795
 796     case FKind.FlatMethod:
 797       FlatMethod fm = (FlatMethod) fn;
 798
 799       // there should only be one FlatMethod node as the
 800       // parent of all other FlatNode objects, so take
 801       // the opportunity to construct the initial graph by
 802       // adding parameters labels to new heap regions
 803       // AND this should be done once globally so that the
 804       // parameter IDs are consistent between analysis
 805       // iterations, so if this step has been done already
 806       // just merge in the cached version
 807       OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
 808       if( ogInitParamAlloc == null ) {
 809
 810         // if the method context has aliased parameters, make sure
 811         // there is a blob region for all those param to reference
 812         Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
 813
 814         if( !aliasedParamIndices.isEmpty() ) {
 815           og.makeAliasedParamHeapRegionNode();
 816         }
 817
 818         // set up each parameter
 819         for( int i = 0; i < fm.numParameters(); ++i ) {
 820           TempDescriptor tdParam    = fm.getParameter( i );
 821           TypeDescriptor typeParam  = tdParam.getType();
 822           Integer        paramIndex = new Integer( i );
 823
 824           if( typeParam.isImmutable() && !typeParam.isArray() ) {
 825             // don't bother with this primitive parameter, it
 826             // cannot affect reachability
 827             continue;
 828           }
 829
 830           if( aliasedParamIndices.contains( paramIndex ) ) {
 831             // use the alias blob but give parameters their
 832             // own primary obj region
 833             og.assignTempEqualToAliasedParam( tdParam,
 834                                               paramIndex );
 835           } else {
 836             // this parameter is not aliased to others, give it
 837             // a fresh primary obj and secondary object
 838             og.assignTempEqualToParamAlloc( tdParam,
 839                                             mc.getDescriptor() instanceof TaskDescriptor,
 840                                             paramIndex );
 841           }
 842         }
 843
 844         // add additional edges for aliased regions if necessary
 845         if( !aliasedParamIndices.isEmpty() ) {
 846           og.addParam2ParamAliasEdges( fm, aliasedParamIndices );
 847         }
 848
 849         // clean up reachability on initial parameter shapes
 850         og.globalSweep();
 851
 852         // this maps tokens to parameter indices and vice versa
 853         // for when this method is a callee
 854         og.prepareParamTokenMaps( fm );
 855
 856         // cache the graph
 857         OwnershipGraph ogResult = new OwnershipGraph();
 858         ogResult.merge(og);
 859         mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
 860
 861       } else {
 862         // or just leverage the cached copy
 863         og.merge(ogInitParamAlloc);
 864       }
 865       break;
 866
 867     case FKind.FlatOpNode:
 868       FlatOpNode fon = (FlatOpNode) fn;
 869       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 870         lhs = fon.getDest();
 871         rhs = fon.getLeft();
 872         og.assignTempXEqualToTempY(lhs, rhs);
 873       }
 874       break;
 875
 876     case FKind.FlatCastNode:
 877       FlatCastNode fcn = (FlatCastNode) fn;
 878       lhs = fcn.getDst();
 879       rhs = fcn.getSrc();
 880
 881       TypeDescriptor td = fcn.getType();
 882       assert td != null;
 883
 884       og.assignTypedTempXEqualToTempY(lhs, rhs, td);
 885       break;
 886
 887     case FKind.FlatFieldNode:
 888       FlatFieldNode ffn = (FlatFieldNode) fn;
 889       lhs = ffn.getDst();
 890       rhs = ffn.getSrc();
 891       fld = ffn.getField();
 892       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 893         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
 894       }
 895
 896       meAnalysis.analyzeFlatFieldNode(mc, og, rhs, fld);
 897
 898       break;
 899
 900     case FKind.FlatSetFieldNode:
 901       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 902       lhs = fsfn.getDst();
 903       fld = fsfn.getField();
 904       rhs = fsfn.getSrc();
 905       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 906         og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
 907       }
 908
 909       meAnalysis.analyzeFlatSetFieldNode(mc, og, lhs, fld);
 910
 911       break;
 912
 913     case FKind.FlatElementNode:
 914       FlatElementNode fen = (FlatElementNode) fn;
 915       lhs = fen.getDst();
 916       rhs = fen.getSrc();
 917       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 918
 919         assert rhs.getType() != null;
 920         assert rhs.getType().isArray();
 921
 922         TypeDescriptor  tdElement = rhs.getType().dereference();
 923         FieldDescriptor fdElement = getArrayField( tdElement );
 924
 925         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
 926       }
 927       break;
 928
 929     case FKind.FlatSetElementNode:
 930       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 931       lhs = fsen.getDst();
 932       rhs = fsen.getSrc();
 933       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 934
 935         assert lhs.getType() != null;
 936         assert lhs.getType().isArray();
 937
 938         TypeDescriptor  tdElement = lhs.getType().dereference();
 939         FieldDescriptor fdElement = getArrayField( tdElement );
 940
 941         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
 942       }
 943       break;
 944
 945     case FKind.FlatNew:
 946       FlatNew fnn = (FlatNew) fn;
 947       lhs = fnn.getDst();
 948       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 949         AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 950
 951         if (mapMethodContextToLiveInAllocationSiteSet != null){
 952                 HashSet<AllocationSite> alllocSet=mapMethodContextToLiveInAllocationSiteSet.get(mc);
 953                 if(alllocSet!=null){
 954                         for (Iterator iterator = alllocSet.iterator(); iterator
 955                                         .hasNext();) {
 956                                 AllocationSite allocationSite = (AllocationSite) iterator
 957                                                 .next();
 958                                 if(allocationSite.flatNew.equals(as.flatNew)){
 959                                         as.setFlag(true);
 960                                 }
 961                         }
 962                 }
 963         }
 964
 965         og.assignTempEqualToNewAlloc(lhs, as);
 966       }
 967       break;
 968
 969     case FKind.FlatCall:
 970       FlatCall fc = (FlatCall) fn;
 971       MethodDescriptor md = fc.getMethod();
 972       FlatMethod flatm = state.getMethodFlat(md);
 973       OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph();
 974
 975       if( md.isStatic() ) {
 976         // a static method is simply always the same, makes life easy
 977         ogMergeOfAllPossibleCalleeResults = og;
 978
 979         Set<Integer> aliasedParamIndices =
 980           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
 981
 982         MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
 983         Set contexts = mapDescriptorToAllMethodContexts.get( md );
 984         assert contexts != null;
 985         contexts.add( mcNew );
 986
 987         addDependent( mc, mcNew );
 988
 989         OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 990
 991         if( onlyPossibleCallee == null ) {
 992           // if this method context has never been analyzed just schedule it for analysis
 993           // and skip over this call site for now
 994           if( !methodContextsToVisitSet.contains( mcNew ) ) {
 995             methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
 996                                                                    mcNew ) );
 997             methodContextsToVisitSet.add( mcNew );
 998           }
 999
1000         } else {
1001           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc, null);
1002         }
1003
1004         meAnalysis.createNewMapping(mcNew);
1005         meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
1006
1007
1008       } else {
1009         // if the method descriptor is virtual, then there could be a
1010         // set of possible methods that will actually be invoked, so
1011         // find all of them and merge all of their results together
1012         TypeDescriptor typeDesc = fc.getThis().getType();
1013         Set possibleCallees = callGraph.getMethods(md, typeDesc);
1014
1015         Iterator i = possibleCallees.iterator();
1016         while( i.hasNext() ) {
1017           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
1018           FlatMethod pflatm = state.getMethodFlat(possibleMd);
1019
1020           // don't alter the working graph (og) until we compute a result for every
1021           // possible callee, merge them all together, then set og to that
1022           OwnershipGraph ogCopy = new OwnershipGraph();
1023           ogCopy.merge(og);
1024
1025           Set<Integer> aliasedParamIndices =
1026             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
1027
1028           MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
1029           Set contexts = mapDescriptorToAllMethodContexts.get( md );
1030           assert contexts != null;
1031           contexts.add( mcNew );
1032
1033
1034         meAnalysis.createNewMapping(mcNew);
1035
1036
1037           addDependent( mc, mcNew );
1038
1039           OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
1040
1041           if( ogPotentialCallee == null ) {
1042             // if this method context has never been analyzed just schedule it for analysis
1043             // and skip over this call site for now
1044             if( !methodContextsToVisitSet.contains( mcNew ) ) {
1045               methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
1046                                                                      mcNew ) );
1047               methodContextsToVisitSet.add( mcNew );
1048             }
1049
1050           } else {
1051             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc, null);
1052           }
1053
1054           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
1055
1056           meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
1057         }
1058
1059       }
1060
1061       og = ogMergeOfAllPossibleCalleeResults;
1062       break;
1063
1064     case FKind.FlatReturnNode:
1065       FlatReturnNode frn = (FlatReturnNode) fn;
1066       rhs = frn.getReturnTemp();
1067       if( rhs != null && !rhs.getType().isImmutable() ) {
1068         og.assignReturnEqualToTemp(rhs);
1069       }
1070       setRetNodes.add(frn);
1071       break;
1072     }
1073
1074     Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(mc);
1075     if(table==null){
1076         table=new     Hashtable<FlatNode, OwnershipGraph>();
1077     }
1078     table.put(fn, og);
1079     mapMethodContextToFlatNodeOwnershipGraph.put(mc, table);
1080
1081     return og;
1082   }
1083
1084
1085   // this method should generate integers strictly greater than zero!
1086   // special "shadow" regions are made from a heap region by negating
1087   // the ID
1088   static public Integer generateUniqueHeapRegionNodeID() {
1089     ++uniqueIDcount;
1090     return new Integer(uniqueIDcount);
1091   }
1092
1093
1094   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
1095     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
1096     if( fdElement == null ) {
1097       fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
1098                                       tdElement,
1099                                       arrayElementFieldName,
1100                                       null,
1101                                       false);
1102       mapTypeToArrayField.put( tdElement, fdElement );
1103     }
1104     return fdElement;
1105   }
1106
1107
1108   private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og) {
1109
1110     mapMethodContextToCompleteOwnershipGraph.put(mc, og);
1111
1112     if( writeDOTs && writeAllDOTs ) {
1113       if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
1114         mapMethodContextToNumUpdates.put(mc, new Integer(0) );
1115       }
1116       Integer n = mapMethodContextToNumUpdates.get(mc);
1117       try {
1118         og.writeGraph(mc+"COMPLETE"+String.format("%05d", n),
1119                       true,  // write labels (variables)
1120                       true,  // selectively hide intermediate temp vars
1121                       true,  // prune unreachable heap regions
1122                       false, // show back edges to confirm graph validity
1123                       false, // show parameter indices (unmaintained!)
1124                       true,  // hide subset reachability states
1125                       true); // hide edge taints
1126       } catch( IOException e ) {}
1127       mapMethodContextToNumUpdates.put(mc, n + 1);
1128     }
1129   }
1130
1131
1132   private void addDependent( MethodContext caller, MethodContext callee ) {
1133     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1134     if( deps == null ) {
1135       deps = new HashSet<MethodContext>();
1136     }
1137     deps.add( caller );
1138     mapMethodContextToDependentContexts.put( callee, deps );
1139   }
1140
1141   private Iterator<MethodContext> iteratorDependents( MethodContext callee ) {
1142     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1143     if( deps == null ) {
1144       deps = new HashSet<MethodContext>();
1145       mapMethodContextToDependentContexts.put( callee, deps );
1146     }
1147     return deps.iterator();
1148   }
1149
1150
1151   private void writeFinalContextGraphs() {
1152     Set entrySet = mapMethodContextToCompleteOwnershipGraph.entrySet();
1153     Iterator itr = entrySet.iterator();
1154     while( itr.hasNext() ) {
1155       Map.Entry      me = (Map.Entry)      itr.next();
1156       MethodContext  mc = (MethodContext)  me.getKey();
1157       OwnershipGraph og = (OwnershipGraph) me.getValue();
1158
1159       try {
1160         og.writeGraph(mc+"COMPLETE",
1161                       true,  // write labels (variables)
1162                       true,  // selectively hide intermediate temp vars
1163                       true,  // prune unreachable heap regions
1164                       false, // show back edges to confirm graph validity
1165                       false, // show parameter indices (unmaintained!)
1166                       true,  // hide subset reachability states
1167                       true); // hide edge taints
1168       } catch( IOException e ) {}
1169     }
1170   }
1171
1172
1173
1174   // return just the allocation site associated with one FlatNew node
1175   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
1176
1177     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
1178       AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
1179
1180       // the newest nodes are single objects
1181       for( int i = 0; i < allocationDepth; ++i ) {
1182         Integer id = generateUniqueHeapRegionNodeID();
1183         as.setIthOldest(i, id);
1184         mapHrnIdToAllocationSite.put( id, as );
1185       }
1186
1187       // the oldest node is a summary node
1188       Integer idSummary = generateUniqueHeapRegionNodeID();
1189       as.setSummary(idSummary);
1190
1191       mapFlatNewToAllocationSite.put(fn, as);
1192     }
1193
1194     return mapFlatNewToAllocationSite.get(fn);
1195   }
1196
1197
1198   // return all allocation sites in the method (there is one allocation
1199   // site per FlatNew node in a method)
1200   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
1201     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
1202       buildAllocationSiteSet(d);
1203     }
1204
1205     return mapDescriptorToAllocationSiteSet.get(d);
1206
1207   }
1208
1209   private void buildAllocationSiteSet(Descriptor d) {
1210     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
1211
1212     FlatMethod fm;
1213     if( d instanceof MethodDescriptor ) {
1214       fm = state.getMethodFlat( (MethodDescriptor) d);
1215     } else {
1216       assert d instanceof TaskDescriptor;
1217       fm = state.getMethodFlat( (TaskDescriptor) d);
1218     }
1219
1220     // visit every node in this FlatMethod's IR graph
1221     // and make a set of the allocation sites from the
1222     // FlatNew node's visited
1223     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1224     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1225     toVisit.add(fm);
1226
1227     while( !toVisit.isEmpty() ) {
1228       FlatNode n = toVisit.iterator().next();
1229
1230       if( n instanceof FlatNew ) {
1231         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
1232       }
1233
1234       toVisit.remove(n);
1235       visited.add(n);
1236
1237       for( int i = 0; i < n.numNext(); ++i ) {
1238         FlatNode child = n.getNext(i);
1239         if( !visited.contains(child) ) {
1240           toVisit.add(child);
1241         }
1242       }
1243     }
1244
1245     mapDescriptorToAllocationSiteSet.put(d, s);
1246   }
1247
1248
1249   private HashSet<AllocationSite> getFlaggedAllocationSites(Descriptor dIn) {
1250
1251     HashSet<AllocationSite> out     = new HashSet<AllocationSite>();
1252     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1253     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1254
1255     toVisit.add(dIn);
1256
1257     while( !toVisit.isEmpty() ) {
1258       Descriptor d = toVisit.iterator().next();
1259       toVisit.remove(d);
1260       visited.add(d);
1261
1262       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1263       Iterator asItr = asSet.iterator();
1264       while( asItr.hasNext() ) {
1265         AllocationSite as = (AllocationSite) asItr.next();
1266         if( as.getDisjointId() != null ) {
1267           out.add(as);
1268         }
1269       }
1270
1271       // enqueue callees of this method to be searched for
1272       // allocation sites also
1273       Set callees = callGraph.getCalleeSet(d);
1274       if( callees != null ) {
1275         Iterator methItr = callees.iterator();
1276         while( methItr.hasNext() ) {
1277           MethodDescriptor md = (MethodDescriptor) methItr.next();
1278
1279           if( !visited.contains(md) ) {
1280             toVisit.add(md);
1281           }
1282         }
1283       }
1284     }
1285
1286     return out;
1287   }
1288
1289
1290   private HashSet<AllocationSite>
1291   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1292
1293     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
1294     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1295     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1296
1297     toVisit.add(td);
1298
1299     // traverse this task and all methods reachable from this task
1300     while( !toVisit.isEmpty() ) {
1301       Descriptor d = toVisit.iterator().next();
1302       toVisit.remove(d);
1303       visited.add(d);
1304
1305       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1306       Iterator asItr = asSet.iterator();
1307       while( asItr.hasNext() ) {
1308         AllocationSite as = (AllocationSite) asItr.next();
1309         TypeDescriptor typed = as.getType();
1310         if( typed != null ) {
1311           ClassDescriptor cd = typed.getClassDesc();
1312           if( cd != null && cd.hasFlags() ) {
1313             asSetTotal.add(as);
1314           }
1315         }
1316       }
1317
1318       // enqueue callees of this method to be searched for
1319       // allocation sites also
1320       Set callees = callGraph.getCalleeSet(d);
1321       if( callees != null ) {
1322         Iterator methItr = callees.iterator();
1323         while( methItr.hasNext() ) {
1324           MethodDescriptor md = (MethodDescriptor) methItr.next();
1325
1326           if( !visited.contains(md) ) {
1327             toVisit.add(md);
1328           }
1329         }
1330       }
1331     }
1332
1333
1334     return asSetTotal;
1335   }
1336
1337
1338   private LinkedList<MethodContext> topologicalSort( HashSet<MethodContext> set ) {
1339     HashSet   <MethodContext> discovered = new HashSet   <MethodContext>();
1340     LinkedList<MethodContext> sorted     = new LinkedList<MethodContext>();
1341
1342     Iterator<MethodContext> itr = set.iterator();
1343     while( itr.hasNext() ) {
1344       MethodContext mc = itr.next();
1345
1346       if( !discovered.contains( mc ) ) {
1347         dfsVisit( set, mc, sorted, discovered );
1348       }
1349     }
1350
1351     return sorted;
1352   }
1353
1354   private void dfsVisit( HashSet<MethodContext> set,
1355                          MethodContext mc,
1356                          LinkedList<MethodContext> sorted,
1357                          HashSet   <MethodContext> discovered ) {
1358     discovered.add( mc );
1359
1360     Descriptor d = mc.getDescriptor();
1361     if( d instanceof MethodDescriptor ) {
1362       MethodDescriptor md = (MethodDescriptor) d;
1363       Iterator itr = callGraph.getCallerSet( md ).iterator();
1364       while( itr.hasNext() ) {
1365         Descriptor dCaller = (Descriptor) itr.next();
1366
1367         // only consider the callers in the original set to analyze
1368         Set<MethodContext> callerContexts = mapDescriptorToAllMethodContexts.get( dCaller );
1369         if( callerContexts == null )
1370           continue;
1371
1372         // since the analysis hasn't started, there should be exactly one
1373         // context if there are any at all
1374         assert callerContexts.size() == 1;
1375         MethodContext mcCaller = callerContexts.iterator().next();
1376         assert set.contains( mcCaller );
1377
1378         if( !discovered.contains( mcCaller ) ) {
1379           dfsVisit( set, mcCaller, sorted, discovered );
1380         }
1381       }
1382     }
1383
1384     sorted.addFirst( mc );
1385   }
1386
1387
1388
1389   private String computeAliasContextHistogram() {
1390
1391     Hashtable<Integer, Integer> mapNumContexts2NumDesc =
1392       new Hashtable<Integer, Integer>();
1393
1394     Iterator itr = mapDescriptorToAllMethodContexts.entrySet().iterator();
1395     while( itr.hasNext() ) {
1396       Map.Entry me = (Map.Entry) itr.next();
1397       HashSet<MethodContext> s = (HashSet<MethodContext>) me.getValue();
1398
1399       Integer i = mapNumContexts2NumDesc.get( s.size() );
1400       if( i == null ) {
1401         i = new Integer( 0 );
1402       }
1403       mapNumContexts2NumDesc.put( s.size(), i + 1 );
1404     }
1405
1406     String s = "";
1407     int total = 0;
1408
1409     itr = mapNumContexts2NumDesc.entrySet().iterator();
1410     while( itr.hasNext() ) {
1411       Map.Entry me = (Map.Entry) itr.next();
1412       Integer c0 = (Integer) me.getKey();
1413       Integer d0 = (Integer) me.getValue();
1414       total += d0;
1415       s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
1416     }
1417
1418     s += String.format( "\n%4d total methods analayzed.\n", total );
1419
1420     return s;
1421   }
1422
1423   private int numMethodsAnalyzed() {
1424     return descriptorsToAnalyze.size();
1425   }
1426
1427
1428
1429
1430   // insert a call to debugSnapshot() somewhere in the analysis
1431   // to get successive captures of the analysis state
1432   boolean takeDebugSnapshots = false;
1433   String mcDescSymbolDebug = "addFirst";
1434   boolean stopAfterCapture = true;
1435
1436   // increments every visit to debugSnapshot, don't fiddle with it
1437   int debugCounter = 0;
1438
1439   // the value of debugCounter to start reporting the debugCounter
1440   // to the screen to let user know what debug iteration we're at
1441   int numStartCountReport = 0;
1442
1443   // the frequency of debugCounter values to print out, 0 no report
1444   int freqCountReport = 0;
1445
1446   // the debugCounter value at which to start taking snapshots
1447   int iterStartCapture = 0;
1448
1449   // the number of snapshots to take
1450   int numIterToCapture = 40;
1451
1452   void debugSnapshot(OwnershipGraph og, FlatNode fn) {
1453     if( debugCounter > iterStartCapture + numIterToCapture ) {
1454       return;
1455     }
1456
1457     ++debugCounter;
1458     if( debugCounter > numStartCountReport &&
1459         freqCountReport > 0 &&
1460         debugCounter % freqCountReport == 0 ) {
1461       System.out.println("    @@@ debug counter = "+debugCounter);
1462     }
1463     if( debugCounter > iterStartCapture ) {
1464       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
1465       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
1466       if( fn != null ) {
1467         graphName = graphName+fn;
1468       }
1469       try {
1470         og.writeGraph(graphName,
1471                       true,  // write labels (variables)
1472                       true,  // selectively hide intermediate temp vars
1473                       true,  // prune unreachable heap regions
1474                       false, // show back edges to confirm graph validity
1475                       false, // show parameter indices (unmaintained!)
1476                       true,  // hide subset reachability states
1477                       true); // hide edge taints
1478       } catch( Exception e ) {
1479         System.out.println("Error writing debug capture.");
1480         System.exit(0);
1481       }
1482     }
1483
1484     if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) {
1485       System.out.println("Stopping analysis after debug captures.");
1486       System.exit(0);
1487     }
1488   }
1489
1490   public MethodEffectsAnalysis getMethodEffectsAnalysis(){
1491           return meAnalysis;
1492   }
1493
1494   public OwnershipGraph getOwnvershipGraphByMethodContext(MethodContext mc){
1495           return mapMethodContextToCompleteOwnershipGraph.get(mc);
1496   }
1497
1498   public HashSet<MethodContext> getAllMethodContextSetByDescriptor(Descriptor d){
1499           return mapDescriptorToAllMethodContexts.get(d);
1500   }
1501
1502   public MethodContext getCalleeMethodContext(MethodContext callerMC, FlatCall fc){
1503
1504           Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(callerMC);
1505
1506           // merge previous ownership graph to calculate corresponding method context
1507           OwnershipGraph mergeOG = new OwnershipGraph();
1508
1509           for(int i=0;i<fc.numPrev();i++){
1510                   FlatNode prevNode=fc.getPrev(i);
1511                   if(prevNode!=null){
1512                           OwnershipGraph prevOG=table.get(prevNode);
1513                           mergeOG.merge(prevOG);
1514                   }
1515           }
1516
1517           MethodDescriptor md=fc.getMethod();
1518           FlatMethod flatm = state.getMethodFlat(md);
1519           Set<Integer> aliasedParamIndices = mergeOG.calculateAliasedParamSet(fc, md.isStatic(), flatm);
1520           MethodContext calleeMC = new MethodContext( md, aliasedParamIndices );
1521
1522           return calleeMC;
1523   }
1524
1525
1526 }