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             mapMethodContextToFlatNodeOwnershipGraph=new Hashtable<MethodContext, Hashtable<FlatNode, OwnershipGraph>>();
 509
 510             meAnalysis=new MethodEffectsAnalysis(methodEffects);
 511
 512
 513             if( writeAllDOTs ) {
 514               mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
 515             }
 516
 517
 518             double timeStartAnalysis = (double) System.nanoTime();
 519
 520
 521             if( state.TASK ) {
 522               // initialize methods to visit as the set of all tasks in the
 523               // program and then any method that could be called starting
 524               // from those tasks
 525               Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 526               while( taskItr.hasNext() ) {
 527                 Descriptor d = (Descriptor) taskItr.next();
 528                 scheduleAllCallees(d);
 529               }
 530
 531             } else {
 532               // we are not in task mode, just normal Java, so start with
 533               // the main method
 534               Descriptor d = typeUtil.getMain();
 535               scheduleAllCallees(d);
 536             }
 537
 538
 539             // before beginning analysis, initialize every scheduled method
 540             // with an ownership graph that has populated parameter index tables
 541             // by analyzing the first node which is always a FlatMethod node
 542             Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
 543             while( dItr.hasNext() ) {
 544               Descriptor d  = dItr.next();
 545               OwnershipGraph og = new OwnershipGraph();
 546
 547               FlatMethod fm;
 548               if( d instanceof MethodDescriptor ) {
 549                 fm = state.getMethodFlat( (MethodDescriptor) d);
 550               } else {
 551                 assert d instanceof TaskDescriptor;
 552                 fm = state.getMethodFlat( (TaskDescriptor) d);
 553               }
 554
 555               MethodContext mc = new MethodContext( d );
 556               assert !mapDescriptorToAllMethodContexts.containsKey( d );
 557               HashSet<MethodContext> s = new HashSet<MethodContext>();
 558               s.add( mc );
 559               mapDescriptorToAllMethodContexts.put( d, s );
 560
 561               //System.out.println("Previsiting " + mc);
 562
 563               meAnalysis.createNewMapping(mc);
 564
 565               og = analyzeFlatNode(mc, fm, fm, null, og);
 566               setGraphForMethodContext(mc, og);
 567             }
 568
 569             // as mentioned above, analyze methods one-by-one, possibly revisiting
 570             // a method if the methods that it calls are updated
 571             analyzeMethods();
 572             analysisComplete = true;
 573
 574
 575             double timeEndAnalysis = (double) System.nanoTime();
 576             double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 577             String treport = String.format( "The reachability analysis took %.3f sec.", dt );
 578             String justtime = String.format( "%.2f", dt );
 579             System.out.println( treport );
 580
 581             if( writeDOTs && !writeAllDOTs ) {
 582               writeFinalContextGraphs();
 583             }
 584
 585             if(methodEffects){
 586                 meAnalysis.writeMethodEffectsResult();
 587             }
 588
 589             if( aliasFile != null ) {
 590               if( state.TASK ) {
 591                 writeAllAliases(aliasFile, treport, justtime, state.OWNERSHIPALIASTAB, state.lines);
 592               } else {
 593                 writeAllAliasesJava(aliasFile, treport, justtime, state.OWNERSHIPALIASTAB, state.lines);
 594               }
 595             }
 596
 597   }
 598
 599   // called from the constructor to help initialize the set
 600   // of methods that needs to be analyzed by ownership analysis
 601   private void scheduleAllCallees(Descriptor d) {
 602     if( descriptorsToAnalyze.contains(d) ) {
 603       return;
 604     }
 605     descriptorsToAnalyze.add(d);
 606
 607     // start with all method calls to further schedule
 608     Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
 609
 610     if( d instanceof MethodDescriptor ) {
 611       // see if this method has virtual dispatch
 612       Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
 613       moreMethodsToCheck.addAll(virtualMethods);
 614     }
 615
 616     // keep following any further methods identified in
 617     // the call chain
 618     Iterator methItr = moreMethodsToCheck.iterator();
 619     while( methItr.hasNext() ) {
 620       Descriptor m = (Descriptor) methItr.next();
 621       scheduleAllCallees(m);
 622     }
 623   }
 624
 625
 626   // manage the set of tasks and methods to be analyzed
 627   // and be sure to reschedule tasks/methods when the methods
 628   // they call are updated
 629   private void analyzeMethods() throws java.io.IOException {
 630
 631     // first gather all of the method contexts to analyze
 632     HashSet<MethodContext> allContexts = new HashSet<MethodContext>();
 633     Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
 634     while( itrd2a.hasNext() ) {
 635       HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
 636       assert mcs != null;
 637
 638       Iterator<MethodContext> itrmc = mcs.iterator();
 639       while( itrmc.hasNext() ) {
 640         allContexts.add( itrmc.next() );
 641       }
 642     }
 643
 644     // topologically sort them according to the caller graph so leaf calls are
 645     // ordered first; use that ordering to give method contexts priorities
 646     LinkedList<MethodContext> sortedMethodContexts = topologicalSort( allContexts );
 647
 648     methodContextsToVisitQ   = new PriorityQueue<MethodContextQWrapper>();
 649     methodContextsToVisitSet = new HashSet<MethodContext>();
 650
 651     int p = 0;
 652     Iterator<MethodContext> mcItr = sortedMethodContexts.iterator();
 653     while( mcItr.hasNext() ) {
 654       MethodContext mc = mcItr.next();
 655       mapDescriptorToPriority.put( mc.getDescriptor(), new Integer( p ) );
 656       methodContextsToVisitQ.add( new MethodContextQWrapper( p, mc ) );
 657       methodContextsToVisitSet.add( mc );
 658       ++p;
 659     }
 660
 661     // analyze methods from the priority queue until it is empty
 662     while( !methodContextsToVisitQ.isEmpty() ) {
 663       MethodContext mc = methodContextsToVisitQ.poll().getMethodContext();
 664       assert methodContextsToVisitSet.contains( mc );
 665       methodContextsToVisitSet.remove( mc );
 666
 667       // because the task or method descriptor just extracted
 668       // was in the "to visit" set it either hasn't been analyzed
 669       // yet, or some method that it depends on has been
 670       // updated.  Recompute a complete ownership graph for
 671       // this task/method and compare it to any previous result.
 672       // If there is a change detected, add any methods/tasks
 673       // that depend on this one to the "to visit" set.
 674
 675       System.out.println("Analyzing " + mc);
 676
 677       Descriptor d = mc.getDescriptor();
 678       FlatMethod fm;
 679       if( d instanceof MethodDescriptor ) {
 680         fm = state.getMethodFlat( (MethodDescriptor) d);
 681       } else {
 682         assert d instanceof TaskDescriptor;
 683         fm = state.getMethodFlat( (TaskDescriptor) d);
 684       }
 685
 686       OwnershipGraph og = analyzeFlatMethod(mc, fm);
 687       OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
 688       if( !og.equals(ogPrev) ) {
 689         setGraphForMethodContext(mc, og);
 690
 691         Iterator<MethodContext> depsItr = iteratorDependents( mc );
 692         while( depsItr.hasNext() ) {
 693           MethodContext mcNext = depsItr.next();
 694
 695           if( !methodContextsToVisitSet.contains( mcNext ) ) {
 696             methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( mcNext.getDescriptor() ),
 697                                                                    mcNext ) );
 698             methodContextsToVisitSet.add( mcNext );
 699           }
 700         }
 701       }
 702     }
 703
 704   }
 705
 706
 707   // keep passing the Descriptor of the method along for debugging
 708   // and dot file writing
 709   private OwnershipGraph
 710   analyzeFlatMethod(MethodContext mc,
 711                     FlatMethod flatm) throws java.io.IOException {
 712
 713     // initialize flat nodes to visit as the flat method
 714     // because it is the entry point
 715
 716     flatNodesToVisit = new HashSet<FlatNode>();
 717     flatNodesToVisit.add(flatm);
 718
 719     // initilize the mapping of flat nodes in this flat method to
 720     // ownership graph results to an empty mapping
 721     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 722
 723     // initialize the set of return nodes that will be combined as
 724     // the final ownership graph result to return as an empty set
 725     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 726
 727
 728     while( !flatNodesToVisit.isEmpty() ) {
 729       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 730       flatNodesToVisit.remove(fn);
 731
 732       //System.out.println( "  "+fn );
 733
 734       // perform this node's contributions to the ownership
 735       // graph on a new copy, then compare it to the old graph
 736       // at this node to see if anything was updated.
 737       OwnershipGraph og = new OwnershipGraph();
 738
 739       // start by merging all node's parents' graphs
 740       for( int i = 0; i < fn.numPrev(); ++i ) {
 741         FlatNode pn = fn.getPrev(i);
 742         if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
 743           OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
 744           og.merge(ogParent);
 745         }
 746       }
 747
 748       // apply the analysis of the flat node to the
 749       // ownership graph made from the merge of the
 750       // parent graphs
 751       og = analyzeFlatNode(mc,
 752                            flatm,
 753                            fn,
 754                            returnNodesToCombineForCompleteOwnershipGraph,
 755                            og);
 756
 757
 758
 759
 760       if( takeDebugSnapshots &&
 761           mc.getDescriptor().getSymbol().equals( mcDescSymbolDebug ) ) {
 762         debugSnapshot(og,fn);
 763       }
 764
 765
 766       // if the results of the new graph are different from
 767       // the current graph at this node, replace the graph
 768       // with the update and enqueue the children for
 769       // processing
 770       OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
 771       if( !og.equals(ogPrev) ) {
 772         mapFlatNodeToOwnershipGraph.put(fn, og);
 773
 774         for( int i = 0; i < fn.numNext(); i++ ) {
 775           FlatNode nn = fn.getNext(i);
 776           flatNodesToVisit.add(nn);
 777         }
 778       }
 779     }
 780
 781     // end by merging all return nodes into a complete
 782     // ownership graph that represents all possible heap
 783     // states after the flat method returns
 784     OwnershipGraph completeGraph = new OwnershipGraph();
 785     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 786     while( retItr.hasNext() ) {
 787       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 788       assert mapFlatNodeToOwnershipGraph.containsKey(frn);
 789       OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
 790       completeGraph.merge(ogr);
 791     }
 792
 793     return completeGraph;
 794   }
 795
 796
 797   private OwnershipGraph
 798   analyzeFlatNode(MethodContext mc,
 799                   FlatMethod fmContaining,
 800                   FlatNode fn,
 801                   HashSet<FlatReturnNode> setRetNodes,
 802                   OwnershipGraph og) throws java.io.IOException {
 803
 804
 805     // any variables that are no longer live should be
 806     // nullified in the graph to reduce edges
 807     // NOTE: it is not clear we need this.  It costs a
 808     // liveness calculation for every method, so only
 809     // turn it on if we find we actually need it.
 810     //og.nullifyDeadVars( liveness.getLiveInTemps( fmContaining, fn ) );
 811
 812
 813     TempDescriptor lhs;
 814     TempDescriptor rhs;
 815     FieldDescriptor fld;
 816
 817     // use node type to decide what alterations to make
 818     // to the ownership graph
 819     switch( fn.kind() ) {
 820
 821     case FKind.FlatMethod:
 822       FlatMethod fm = (FlatMethod) fn;
 823
 824       // there should only be one FlatMethod node as the
 825       // parent of all other FlatNode objects, so take
 826       // the opportunity to construct the initial graph by
 827       // adding parameters labels to new heap regions
 828       // AND this should be done once globally so that the
 829       // parameter IDs are consistent between analysis
 830       // iterations, so if this step has been done already
 831       // just merge in the cached version
 832       OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
 833       if( ogInitParamAlloc == null ) {
 834
 835         // if the method context has aliased parameters, make sure
 836         // there is a blob region for all those param to reference
 837         Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
 838
 839         if( !aliasedParamIndices.isEmpty() ) {
 840           og.makeAliasedParamHeapRegionNode(fm);
 841         }
 842
 843         // set up each parameter
 844         for( int i = 0; i < fm.numParameters(); ++i ) {
 845           TempDescriptor tdParam    = fm.getParameter( i );
 846           TypeDescriptor typeParam  = tdParam.getType();
 847           Integer        paramIndex = new Integer( i );
 848
 849           if( typeParam.isImmutable() && !typeParam.isArray() ) {
 850             // don't bother with this primitive parameter, it
 851             // cannot affect reachability
 852             continue;
 853           }
 854
 855           if( aliasedParamIndices.contains( paramIndex ) ) {
 856             // use the alias blob but give parameters their
 857             // own primary obj region
 858             og.assignTempEqualToAliasedParam( tdParam,
 859                                               paramIndex, fm );
 860           } else {
 861             // this parameter is not aliased to others, give it
 862             // a fresh primary obj and secondary object
 863             og.assignTempEqualToParamAlloc( tdParam,
 864                                             mc.getDescriptor() instanceof TaskDescriptor,
 865                                             paramIndex, fm );
 866           }
 867         }
 868
 869         // add additional edges for aliased regions if necessary
 870         if( !aliasedParamIndices.isEmpty() ) {
 871           og.addParam2ParamAliasEdges( fm, aliasedParamIndices );
 872         }
 873
 874         // clean up reachability on initial parameter shapes
 875         og.globalSweep();
 876
 877         // this maps tokens to parameter indices and vice versa
 878         // for when this method is a callee
 879         og.prepareParamTokenMaps( fm );
 880
 881         // cache the graph
 882         OwnershipGraph ogResult = new OwnershipGraph();
 883         ogResult.merge(og);
 884         mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
 885
 886       } else {
 887         // or just leverage the cached copy
 888         og.merge(ogInitParamAlloc);
 889       }
 890       break;
 891
 892     case FKind.FlatOpNode:
 893       FlatOpNode fon = (FlatOpNode) fn;
 894       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 895         lhs = fon.getDest();
 896         rhs = fon.getLeft();
 897         og.assignTempXEqualToTempY(lhs, rhs);
 898       }
 899       break;
 900
 901     case FKind.FlatCastNode:
 902       FlatCastNode fcn = (FlatCastNode) fn;
 903       lhs = fcn.getDst();
 904       rhs = fcn.getSrc();
 905
 906       TypeDescriptor td = fcn.getType();
 907       assert td != null;
 908
 909       og.assignTempXEqualToCastedTempY(lhs, rhs, td);
 910       break;
 911
 912     case FKind.FlatFieldNode:
 913       FlatFieldNode ffn = (FlatFieldNode) fn;
 914       lhs = ffn.getDst();
 915       rhs = ffn.getSrc();
 916       fld = ffn.getField();
 917       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 918         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
 919       }
 920
 921       meAnalysis.analyzeFlatFieldNode(mc, og, rhs, fld);
 922
 923       break;
 924
 925     case FKind.FlatSetFieldNode:
 926       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 927       lhs = fsfn.getDst();
 928       fld = fsfn.getField();
 929       rhs = fsfn.getSrc();
 930       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 931         og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
 932       }
 933
 934       meAnalysis.analyzeFlatSetFieldNode(mc, og, lhs, fld);
 935
 936       break;
 937
 938     case FKind.FlatElementNode:
 939       FlatElementNode fen = (FlatElementNode) fn;
 940       lhs = fen.getDst();
 941       rhs = fen.getSrc();
 942       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 943
 944         assert rhs.getType() != null;
 945         assert rhs.getType().isArray();
 946
 947         TypeDescriptor  tdElement = rhs.getType().dereference();
 948         FieldDescriptor fdElement = getArrayField( tdElement );
 949
 950         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
 951       }
 952       break;
 953
 954     case FKind.FlatSetElementNode:
 955       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 956
 957       if( arrayReferencees.doesNotCreateNewReaching( fsen ) ) {
 958         // skip this node if it cannot create new reachability paths
 959         break;
 960       }
 961
 962       lhs = fsen.getDst();
 963       rhs = fsen.getSrc();
 964       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 965
 966         assert lhs.getType() != null;
 967         assert lhs.getType().isArray();
 968
 969         TypeDescriptor  tdElement = lhs.getType().dereference();
 970         FieldDescriptor fdElement = getArrayField( tdElement );
 971
 972         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
 973       }
 974       break;
 975
 976     case FKind.FlatNew:
 977       FlatNew fnn = (FlatNew) fn;
 978       lhs = fnn.getDst();
 979       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 980         AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 981
 982         if (mapMethodContextToLiveInAllocationSiteSet != null){
 983                 HashSet<AllocationSite> alllocSet=mapMethodContextToLiveInAllocationSiteSet.get(mc);
 984                 if(alllocSet!=null){
 985                         for (Iterator iterator = alllocSet.iterator(); iterator
 986                                         .hasNext();) {
 987                                 AllocationSite allocationSite = (AllocationSite) iterator
 988                                                 .next();
 989                                 if(allocationSite.flatNew.equals(as.flatNew)){
 990                                         as.setFlag(true);
 991                                 }
 992                         }
 993                 }
 994         }
 995
 996         og.assignTempEqualToNewAlloc(lhs, as);
 997       }
 998       break;
 999
1000     case FKind.FlatCall:
1001       FlatCall fc = (FlatCall) fn;
1002       MethodDescriptor md = fc.getMethod();
1003       FlatMethod flatm = state.getMethodFlat(md);
1004       OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph();
1005
1006       if( md.isStatic() ) {
1007         // a static method is simply always the same, makes life easy
1008         ogMergeOfAllPossibleCalleeResults = og;
1009
1010         Set<Integer> aliasedParamIndices =
1011           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
1012
1013         MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
1014         Set contexts = mapDescriptorToAllMethodContexts.get( md );
1015         assert contexts != null;
1016         contexts.add( mcNew );
1017
1018         addDependent( mc, mcNew );
1019
1020         OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
1021
1022         if( onlyPossibleCallee == null ) {
1023           // if this method context has never been analyzed just schedule it for analysis
1024           // and skip over this call site for now
1025           if( !methodContextsToVisitSet.contains( mcNew ) ) {
1026             methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
1027                                                                    mcNew ) );
1028             methodContextsToVisitSet.add( mcNew );
1029           }
1030
1031         } else {
1032           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc, null);
1033         }
1034
1035         meAnalysis.createNewMapping(mcNew);
1036         meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
1037
1038
1039       } else {
1040         // if the method descriptor is virtual, then there could be a
1041         // set of possible methods that will actually be invoked, so
1042         // find all of them and merge all of their results together
1043         TypeDescriptor typeDesc = fc.getThis().getType();
1044         Set possibleCallees = callGraph.getMethods(md, typeDesc);
1045
1046         Iterator i = possibleCallees.iterator();
1047         while( i.hasNext() ) {
1048           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
1049           FlatMethod pflatm = state.getMethodFlat(possibleMd);
1050
1051           // don't alter the working graph (og) until we compute a result for every
1052           // possible callee, merge them all together, then set og to that
1053           OwnershipGraph ogCopy = new OwnershipGraph();
1054           ogCopy.merge(og);
1055
1056           Set<Integer> aliasedParamIndices =
1057             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
1058
1059           MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
1060           Set contexts = mapDescriptorToAllMethodContexts.get( md );
1061           assert contexts != null;
1062           contexts.add( mcNew );
1063
1064
1065         meAnalysis.createNewMapping(mcNew);
1066
1067
1068           addDependent( mc, mcNew );
1069
1070           OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
1071
1072           if( ogPotentialCallee == null ) {
1073             // if this method context has never been analyzed just schedule it for analysis
1074             // and skip over this call site for now
1075             if( !methodContextsToVisitSet.contains( mcNew ) ) {
1076               methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
1077                                                                      mcNew ) );
1078               methodContextsToVisitSet.add( mcNew );
1079             }
1080
1081           } else {
1082             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc, null);
1083           }
1084
1085           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
1086
1087           meAnalysis.analyzeFlatCall(ogMergeOfAllPossibleCalleeResults, mcNew, mc, fc);
1088         }
1089
1090       }
1091
1092       og = ogMergeOfAllPossibleCalleeResults;
1093       break;
1094
1095     case FKind.FlatReturnNode:
1096       FlatReturnNode frn = (FlatReturnNode) fn;
1097       rhs = frn.getReturnTemp();
1098       if( rhs != null && !rhs.getType().isImmutable() ) {
1099         og.assignReturnEqualToTemp(rhs);
1100       }
1101       setRetNodes.add(frn);
1102       break;
1103     }
1104
1105
1106     Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(mc);
1107     if(table==null){
1108         table=new     Hashtable<FlatNode, OwnershipGraph>();
1109     }
1110     table.put(fn, og);
1111     mapMethodContextToFlatNodeOwnershipGraph.put(mc, table);
1112
1113     return og;
1114   }
1115
1116
1117   // this method should generate integers strictly greater than zero!
1118   // special "shadow" regions are made from a heap region by negating
1119   // the ID
1120   static public Integer generateUniqueHeapRegionNodeID() {
1121     ++uniqueIDcount;
1122     return new Integer(uniqueIDcount);
1123   }
1124
1125
1126   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
1127     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
1128     if( fdElement == null ) {
1129       fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
1130                                       tdElement,
1131                                       arrayElementFieldName,
1132                                       null,
1133                                       false);
1134       mapTypeToArrayField.put( tdElement, fdElement );
1135     }
1136     return fdElement;
1137   }
1138
1139
1140   private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og) {
1141
1142     mapMethodContextToCompleteOwnershipGraph.put(mc, og);
1143
1144     if( writeDOTs && writeAllDOTs ) {
1145       if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
1146         mapMethodContextToNumUpdates.put(mc, new Integer(0) );
1147       }
1148       Integer n = mapMethodContextToNumUpdates.get(mc);
1149       try {
1150         og.writeGraph(mc+"COMPLETE"+String.format("%05d", n),
1151                       true,  // write labels (variables)
1152                       true,  // selectively hide intermediate temp vars
1153                       true,  // prune unreachable heap regions
1154                       false, // show back edges to confirm graph validity
1155                       false, // show parameter indices (unmaintained!)
1156                       true,  // hide subset reachability states
1157                       true); // hide edge taints
1158       } catch( IOException e ) {}
1159       mapMethodContextToNumUpdates.put(mc, n + 1);
1160     }
1161   }
1162
1163
1164   private void addDependent( MethodContext caller, MethodContext callee ) {
1165     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1166     if( deps == null ) {
1167       deps = new HashSet<MethodContext>();
1168     }
1169     deps.add( caller );
1170     mapMethodContextToDependentContexts.put( callee, deps );
1171   }
1172
1173   private Iterator<MethodContext> iteratorDependents( MethodContext callee ) {
1174     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
1175     if( deps == null ) {
1176       deps = new HashSet<MethodContext>();
1177       mapMethodContextToDependentContexts.put( callee, deps );
1178     }
1179     return deps.iterator();
1180   }
1181
1182
1183   private void writeFinalContextGraphs() {
1184     Set entrySet = mapMethodContextToCompleteOwnershipGraph.entrySet();
1185     Iterator itr = entrySet.iterator();
1186     while( itr.hasNext() ) {
1187       Map.Entry      me = (Map.Entry)      itr.next();
1188       MethodContext  mc = (MethodContext)  me.getKey();
1189       OwnershipGraph og = (OwnershipGraph) me.getValue();
1190
1191       try {
1192         og.writeGraph(mc+"COMPLETE",
1193                       true,  // write labels (variables)
1194                       true,  // selectively hide intermediate temp vars
1195                       true,  // prune unreachable heap regions
1196                       false, // show back edges to confirm graph validity
1197                       false, // show parameter indices (unmaintained!)
1198                       true,  // hide subset reachability states
1199                       true); // hide edge taints
1200       } catch( IOException e ) {}
1201     }
1202   }
1203
1204
1205
1206   // return just the allocation site associated with one FlatNew node
1207   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
1208
1209     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
1210       AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
1211
1212       // the newest nodes are single objects
1213       for( int i = 0; i < allocationDepth; ++i ) {
1214         Integer id = generateUniqueHeapRegionNodeID();
1215         as.setIthOldest(i, id);
1216         mapHrnIdToAllocationSite.put( id, as );
1217       }
1218
1219       // the oldest node is a summary node
1220       Integer idSummary = generateUniqueHeapRegionNodeID();
1221       as.setSummary(idSummary);
1222
1223       mapFlatNewToAllocationSite.put(fn, as);
1224     }
1225
1226     return mapFlatNewToAllocationSite.get(fn);
1227   }
1228
1229
1230   // return all allocation sites in the method (there is one allocation
1231   // site per FlatNew node in a method)
1232   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
1233     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
1234       buildAllocationSiteSet(d);
1235     }
1236
1237     return mapDescriptorToAllocationSiteSet.get(d);
1238
1239   }
1240
1241   private void buildAllocationSiteSet(Descriptor d) {
1242     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
1243
1244     FlatMethod fm;
1245     if( d instanceof MethodDescriptor ) {
1246       fm = state.getMethodFlat( (MethodDescriptor) d);
1247     } else {
1248       assert d instanceof TaskDescriptor;
1249       fm = state.getMethodFlat( (TaskDescriptor) d);
1250     }
1251
1252     // visit every node in this FlatMethod's IR graph
1253     // and make a set of the allocation sites from the
1254     // FlatNew node's visited
1255     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1256     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1257     toVisit.add(fm);
1258
1259     while( !toVisit.isEmpty() ) {
1260       FlatNode n = toVisit.iterator().next();
1261
1262       if( n instanceof FlatNew ) {
1263         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
1264       }
1265
1266       toVisit.remove(n);
1267       visited.add(n);
1268
1269       for( int i = 0; i < n.numNext(); ++i ) {
1270         FlatNode child = n.getNext(i);
1271         if( !visited.contains(child) ) {
1272           toVisit.add(child);
1273         }
1274       }
1275     }
1276
1277     mapDescriptorToAllocationSiteSet.put(d, s);
1278   }
1279
1280
1281   private HashSet<AllocationSite> getFlaggedAllocationSites(Descriptor dIn) {
1282
1283     HashSet<AllocationSite> out     = new HashSet<AllocationSite>();
1284     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1285     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1286
1287     toVisit.add(dIn);
1288
1289     while( !toVisit.isEmpty() ) {
1290       Descriptor d = toVisit.iterator().next();
1291       toVisit.remove(d);
1292       visited.add(d);
1293
1294       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1295       Iterator asItr = asSet.iterator();
1296       while( asItr.hasNext() ) {
1297         AllocationSite as = (AllocationSite) asItr.next();
1298         if( as.getDisjointId() != null ) {
1299           out.add(as);
1300         }
1301       }
1302
1303       // enqueue callees of this method to be searched for
1304       // allocation sites also
1305       Set callees = callGraph.getCalleeSet(d);
1306       if( callees != null ) {
1307         Iterator methItr = callees.iterator();
1308         while( methItr.hasNext() ) {
1309           MethodDescriptor md = (MethodDescriptor) methItr.next();
1310
1311           if( !visited.contains(md) ) {
1312             toVisit.add(md);
1313           }
1314         }
1315       }
1316     }
1317
1318     return out;
1319   }
1320
1321
1322   private HashSet<AllocationSite>
1323   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1324
1325     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
1326     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1327     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1328
1329     toVisit.add(td);
1330
1331     // traverse this task and all methods reachable from this task
1332     while( !toVisit.isEmpty() ) {
1333       Descriptor d = toVisit.iterator().next();
1334       toVisit.remove(d);
1335       visited.add(d);
1336
1337       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1338       Iterator asItr = asSet.iterator();
1339       while( asItr.hasNext() ) {
1340         AllocationSite as = (AllocationSite) asItr.next();
1341         TypeDescriptor typed = as.getType();
1342         if( typed != null ) {
1343           ClassDescriptor cd = typed.getClassDesc();
1344           if( cd != null && cd.hasFlags() ) {
1345             asSetTotal.add(as);
1346           }
1347         }
1348       }
1349
1350       // enqueue callees of this method to be searched for
1351       // allocation sites also
1352       Set callees = callGraph.getCalleeSet(d);
1353       if( callees != null ) {
1354         Iterator methItr = callees.iterator();
1355         while( methItr.hasNext() ) {
1356           MethodDescriptor md = (MethodDescriptor) methItr.next();
1357
1358           if( !visited.contains(md) ) {
1359             toVisit.add(md);
1360           }
1361         }
1362       }
1363     }
1364
1365
1366     return asSetTotal;
1367   }
1368
1369
1370   private LinkedList<MethodContext> topologicalSort( HashSet<MethodContext> set ) {
1371     HashSet   <MethodContext> discovered = new HashSet   <MethodContext>();
1372     LinkedList<MethodContext> sorted     = new LinkedList<MethodContext>();
1373
1374     Iterator<MethodContext> itr = set.iterator();
1375     while( itr.hasNext() ) {
1376       MethodContext mc = itr.next();
1377
1378       if( !discovered.contains( mc ) ) {
1379         dfsVisit( set, mc, sorted, discovered );
1380       }
1381     }
1382
1383     return sorted;
1384   }
1385
1386   private void dfsVisit( HashSet<MethodContext> set,
1387                          MethodContext mc,
1388                          LinkedList<MethodContext> sorted,
1389                          HashSet   <MethodContext> discovered ) {
1390     discovered.add( mc );
1391
1392     Descriptor d = mc.getDescriptor();
1393     if( d instanceof MethodDescriptor ) {
1394       MethodDescriptor md = (MethodDescriptor) d;
1395       Iterator itr = callGraph.getCallerSet( md ).iterator();
1396       while( itr.hasNext() ) {
1397         Descriptor dCaller = (Descriptor) itr.next();
1398
1399         // only consider the callers in the original set to analyze
1400         Set<MethodContext> callerContexts = mapDescriptorToAllMethodContexts.get( dCaller );
1401         if( callerContexts == null )
1402           continue;
1403
1404         // since the analysis hasn't started, there should be exactly one
1405         // context if there are any at all
1406         assert callerContexts.size() == 1;
1407         MethodContext mcCaller = callerContexts.iterator().next();
1408         assert set.contains( mcCaller );
1409
1410         if( !discovered.contains( mcCaller ) ) {
1411           dfsVisit( set, mcCaller, sorted, discovered );
1412         }
1413       }
1414     }
1415
1416     sorted.addFirst( mc );
1417   }
1418
1419
1420
1421   private String computeAliasContextHistogram() {
1422
1423     Hashtable<Integer, Integer> mapNumContexts2NumDesc =
1424       new Hashtable<Integer, Integer>();
1425
1426     Iterator itr = mapDescriptorToAllMethodContexts.entrySet().iterator();
1427     while( itr.hasNext() ) {
1428       Map.Entry me = (Map.Entry) itr.next();
1429       HashSet<MethodContext> s = (HashSet<MethodContext>) me.getValue();
1430
1431       Integer i = mapNumContexts2NumDesc.get( s.size() );
1432       if( i == null ) {
1433         i = new Integer( 0 );
1434       }
1435       mapNumContexts2NumDesc.put( s.size(), i + 1 );
1436     }
1437
1438     String s = "";
1439     int total = 0;
1440
1441     itr = mapNumContexts2NumDesc.entrySet().iterator();
1442     while( itr.hasNext() ) {
1443       Map.Entry me = (Map.Entry) itr.next();
1444       Integer c0 = (Integer) me.getKey();
1445       Integer d0 = (Integer) me.getValue();
1446       total += d0;
1447       s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
1448     }
1449
1450     s += String.format( "\n%4d total methods analayzed.\n", total );
1451
1452     return s;
1453   }
1454
1455   private int numMethodsAnalyzed() {
1456     return descriptorsToAnalyze.size();
1457   }
1458
1459
1460
1461
1462   // insert a call to debugSnapshot() somewhere in the analysis
1463   // to get successive captures of the analysis state
1464   boolean takeDebugSnapshots = false;
1465   String mcDescSymbolDebug = "insertElementAt";
1466   boolean stopAfterCapture = true;
1467
1468   // increments every visit to debugSnapshot, don't fiddle with it
1469   // IMPORTANT NOTE FOR SETTING THE FOLLOWING VALUES: this
1470   // counter increments just after every node is analyzed
1471   // from the body of the method whose symbol is specified
1472   // above.
1473   int debugCounter = 0;
1474
1475   // the value of debugCounter to start reporting the debugCounter
1476   // to the screen to let user know what debug iteration we're at
1477   int numStartCountReport = 0;
1478
1479   // the frequency of debugCounter values to print out, 0 no report
1480   int freqCountReport = 0;
1481
1482   // the debugCounter value at which to start taking snapshots
1483   int iterStartCapture = 0;
1484
1485   // the number of snapshots to take
1486   int numIterToCapture = 300;
1487
1488   void debugSnapshot(OwnershipGraph og, FlatNode fn) {
1489     if( debugCounter > iterStartCapture + numIterToCapture ) {
1490       return;
1491     }
1492
1493     ++debugCounter;
1494     if( debugCounter > numStartCountReport &&
1495         freqCountReport > 0 &&
1496         debugCounter % freqCountReport == 0 ) {
1497       System.out.println("    @@@ debug counter = "+debugCounter);
1498     }
1499     if( debugCounter > iterStartCapture ) {
1500       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
1501       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
1502       if( fn != null ) {
1503         graphName = graphName+fn;
1504       }
1505       try {
1506         og.writeGraph(graphName,
1507                       true,  // write labels (variables)
1508                       true,  // selectively hide intermediate temp vars
1509                       true,  // prune unreachable heap regions
1510                       false, // show back edges to confirm graph validity
1511                       false, // show parameter indices (unmaintained!)
1512                       true,  // hide subset reachability states
1513                       true); // hide edge taints
1514       } catch( Exception e ) {
1515         System.out.println("Error writing debug capture.");
1516         System.exit(0);
1517       }
1518     }
1519
1520     if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) {
1521       System.out.println("Stopping analysis after debug captures.");
1522       System.exit(0);
1523     }
1524   }
1525
1526   public MethodEffectsAnalysis getMethodEffectsAnalysis(){
1527           return meAnalysis;
1528   }
1529
1530   public OwnershipGraph getOwnvershipGraphByMethodContext(MethodContext mc){
1531           return mapMethodContextToCompleteOwnershipGraph.get(mc);
1532   }
1533
1534   public HashSet<MethodContext> getAllMethodContextSetByDescriptor(Descriptor d){
1535           return mapDescriptorToAllMethodContexts.get(d);
1536   }
1537
1538   public MethodContext getCalleeMethodContext(MethodContext callerMC, FlatCall fc){
1539
1540           Hashtable<FlatNode, OwnershipGraph> table=mapMethodContextToFlatNodeOwnershipGraph.get(callerMC);
1541
1542           // merge previous ownership graph to calculate corresponding method context
1543           OwnershipGraph mergeOG = new OwnershipGraph();
1544
1545           for(int i=0;i<fc.numPrev();i++){
1546                   FlatNode prevNode=fc.getPrev(i);
1547                   if(prevNode!=null){
1548                           OwnershipGraph prevOG=table.get(prevNode);
1549                           mergeOG.merge(prevOG);
1550                   }
1551           }
1552
1553           MethodDescriptor md=fc.getMethod();
1554           FlatMethod flatm = state.getMethodFlat(md);
1555           Set<Integer> aliasedParamIndices = mergeOG.calculateAliasedParamSet(fc, md.isStatic(), flatm);
1556           MethodContext calleeMC = new MethodContext( md, aliasedParamIndices );
1557
1558           return calleeMC;
1559   }
1560
1561
1562 }