Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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