Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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