Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import Analysis.CallGraph.*;
   4 import IR.*;
   5 import IR.Flat.*;
   6 import IR.Tree.Modifiers;
   7 import java.util.*;
   8 import java.io.*;
   9
  10
  11 public class OwnershipAnalysis {
  12
  13
  14   ///////////////////////////////////////////
  15   //
  16   //  Public interface to discover possible
  17   //  aliases in the program under analysis
  18   //
  19   ///////////////////////////////////////////
  20
  21   public HashSet<AllocationSite>
  22   getFlaggedAllocationSitesReachableFromTask(TaskDescriptor td) {
  23     return getFlaggedAllocationSitesReachableFromTaskPRIVATE(td);
  24   }
  25
  26   public AllocationSite getAllocationSiteFromFlatNew(FlatNew fn) {
  27     return getAllocationSiteFromFlatNewPRIVATE(fn);
  28   }
  29
  30
  31   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  32                                          int paramIndex1,
  33                                          int paramIndex2) {
  34
  35     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  36     assert(og != null);
  37     return og.hasPotentialAlias(paramIndex1, paramIndex2);
  38   }
  39
  40   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  41                                          int paramIndex,
  42                                          AllocationSite alloc) {
  43
  44     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  45     assert(og != null);
  46     return og.hasPotentialAlias(paramIndex, alloc);
  47   }
  48
  49   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  50                                          AllocationSite alloc,
  51                                          int paramIndex) {
  52
  53     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  54     assert(og != null);
  55     return og.hasPotentialAlias(paramIndex, alloc);
  56   }
  57
  58   public boolean createsPotentialAliases(Descriptor taskOrMethod,
  59                                          AllocationSite alloc1,
  60                                          AllocationSite alloc2) {
  61
  62     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  63     assert(og != null);
  64     return og.hasPotentialAlias(alloc1, alloc2);
  65   }
  66
  67
  68   protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) {
  69     assert d != null;
  70
  71     OwnershipGraph og = new OwnershipGraph( allocationDepth, typeUtil );
  72
  73     assert mapDescriptorToAllMethodContexts.containsKey( d );
  74     HashSet<MethodContext> contexts = mapDescriptorToAllMethodContexts.get( d );
  75     Iterator<MethodContext> mcItr = contexts.iterator();
  76     while( mcItr.hasNext() ) {
  77       MethodContext mc = mcItr.next();
  78
  79       OwnershipGraph ogContext = mapMethodContextToCompleteOwnershipGraph.get(mc);
  80       assert ogContext != null;
  81
  82       og.merge( ogContext );
  83     }
  84
  85     return og;
  86   }
  87
  88
  89   // use the methods given above to check every possible alias
  90   // between task parameters and flagged allocation sites reachable
  91   // from the task
  92   public void writeAllAliases(String outputFile) throws java.io.IOException {
  93
  94     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
  95
  96     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth);
  97
  98     // look through every task for potential aliases
  99     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 100     while( taskItr.hasNext() ) {
 101       TaskDescriptor td = (TaskDescriptor) taskItr.next();
 102
 103       bw.write("\n---------"+td+"--------\n");
 104
 105       HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
 106
 107       // for each task parameter, check for aliases with
 108       // other task parameters and every allocation site
 109       // reachable from this task
 110       boolean foundSomeAlias = false;
 111
 112       FlatMethod fm = state.getMethodFlat(td);
 113       for( int i = 0; i < fm.numParameters(); ++i ) {
 114
 115         // for the ith parameter check for aliases to all
 116         // higher numbered parameters
 117         for( int j = i + 1; j < fm.numParameters(); ++j ) {
 118           if( createsPotentialAliases(td, i, j) ) {
 119             foundSomeAlias = true;
 120             bw.write("Potential alias between parameters "+i+" and "+j+".\n");
 121           }
 122         }
 123
 124         // for the ith parameter, check for aliases against
 125         // the set of allocation sites reachable from this
 126         // task context
 127         Iterator allocItr = allocSites.iterator();
 128         while( allocItr.hasNext() ) {
 129           AllocationSite as = (AllocationSite) allocItr.next();
 130           if( createsPotentialAliases(td, i, as) ) {
 131             foundSomeAlias = true;
 132             bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
 133           }
 134         }
 135       }
 136
 137       // for each allocation site check for aliases with
 138       // other allocation sites in the context of execution
 139       // of this task
 140       HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
 141       Iterator allocItr1 = allocSites.iterator();
 142       while( allocItr1.hasNext() ) {
 143         AllocationSite as1 = (AllocationSite) allocItr1.next();
 144
 145         Iterator allocItr2 = allocSites.iterator();
 146         while( allocItr2.hasNext() ) {
 147           AllocationSite as2 = (AllocationSite) allocItr2.next();
 148
 149           if( !outerChecked.contains(as2) &&
 150               createsPotentialAliases(td, as1, as2) ) {
 151             foundSomeAlias = true;
 152             bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
 153           }
 154         }
 155
 156         outerChecked.add(as1);
 157       }
 158
 159       if( !foundSomeAlias ) {
 160         bw.write("No aliases between flagged objects in Task "+td+".\n");
 161       }
 162     }
 163
 164     bw.close();
 165   }
 166
 167
 168   // this version of writeAllAliases is for Java programs that have no tasks
 169   public void writeAllAliasesJava(String outputFile) throws java.io.IOException {
 170     assert !state.TASK;
 171
 172     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
 173
 174     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
 175     boolean foundSomeAlias = false;
 176
 177     Descriptor d = typeUtil.getMain();
 178     HashSet<AllocationSite> allocSites = getFlaggedAllocationSites(d);
 179
 180     // for each allocation site check for aliases with
 181     // other allocation sites in the context of execution
 182     // of this task
 183     HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
 184     Iterator allocItr1 = allocSites.iterator();
 185     while( allocItr1.hasNext() ) {
 186       AllocationSite as1 = (AllocationSite) allocItr1.next();
 187
 188       Iterator allocItr2 = allocSites.iterator();
 189       while( allocItr2.hasNext() ) {
 190         AllocationSite as2 = (AllocationSite) allocItr2.next();
 191
 192         if( !outerChecked.contains(as2) &&
 193             createsPotentialAliases(d, as1, as2) ) {
 194           foundSomeAlias = true;
 195           bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n");
 196         }
 197       }
 198
 199       outerChecked.add(as1);
 200     }
 201
 202     if( !foundSomeAlias ) {
 203       bw.write("No aliases between flagged objects found.\n");
 204     }
 205
 206     bw.close();
 207   }
 208   ///////////////////////////////////////////
 209   //
 210   // end public interface
 211   //
 212   ///////////////////////////////////////////
 213
 214
 215
 216
 217
 218
 219
 220
 221   // data from the compiler
 222   private State state;
 223   private TypeUtil typeUtil;
 224   private CallGraph callGraph;
 225   private int allocationDepth;
 226
 227   // used to identify HeapRegionNode objects
 228   // A unique ID equates an object in one
 229   // ownership graph with an object in another
 230   // graph that logically represents the same
 231   // heap region
 232   // start at 10 and increment to leave some
 233   // reserved IDs for special purposes
 234   static private int uniqueIDcount = 10;
 235
 236
 237   // Use these data structures to track progress of
 238   // processing all methods in the program, and by methods
 239   // TaskDescriptor and MethodDescriptor are combined
 240   // together, with a common parent class Descriptor
 241   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToInitialParamAllocGraph;
 242   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToCompleteOwnershipGraph;
 243   private Hashtable<FlatNew,       AllocationSite>           mapFlatNewToAllocationSite;
 244   private Hashtable<Descriptor,    HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
 245   private Hashtable<MethodContext, Integer>                  mapMethodContextToNumUpdates;
 246   private Hashtable<Descriptor,    HashSet<MethodContext> >  mapDescriptorToAllMethodContexts;
 247
 248   // Use these data structures to track progress of one pass of
 249   // processing the FlatNodes of a particular method
 250   private HashSet  <FlatNode>                 flatNodesToVisit;
 251   private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
 252   private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
 253
 254   // descriptorsToAnalyze identifies the set of tasks and methods
 255   // that are reachable from the program tasks, this set is initialized
 256   // and then remains static
 257   private HashSet<Descriptor> descriptorsToAnalyze;
 258
 259   // descriptorsToVisit is initialized to descriptorsToAnalyze and is
 260   // reduced by visiting a descriptor during analysis.  When dependents
 261   // must be scheduled, only those contained in descriptorsToAnalyze
 262   // should be re-added to this set
 263   private HashSet   <MethodContext> methodContextsToVisit;
 264
 265   // used in conjunction with the methodContextsToVisit set, fill with
 266   // a topological sort of methodContextsToVisit and then empty that set
 267   // algorithm should analyze something in the linked list until it is
 268   // empty, and then work on the set as normal.  The sorted linked list
 269   // is just another, specially sorted bucket that is part of the
 270   // methodContextsToVisit set
 271   private LinkedList<MethodContext> sortedMethodContextsToVisit;
 272
 273
 274   // special field descriptors for array elements
 275   private Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
 276
 277   // special field descriptors for variables with type, no field name
 278   private Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToVarField;
 279
 280
 281   // a special temp descriptor for setting more than one parameter label
 282   // to the all-aliased-parameters heap region node
 283   protected static TempDescriptor tdAliasedParams = new TempDescriptor("_AllAliasedParams___");
 284
 285
 286   // for controlling DOT file output
 287   private boolean writeDOTs;
 288   private boolean writeAllDOTs;
 289
 290
 291
 292   // this analysis generates an ownership graph for every task
 293   // in the program
 294   public OwnershipAnalysis(State state,
 295                            TypeUtil tu,
 296                            CallGraph callGraph,
 297                            int allocationDepth,
 298                            boolean writeDOTs,
 299                            boolean writeAllDOTs,
 300                            String aliasFile) throws java.io.IOException {
 301
 302     double timeStartAnalysis = (double) System.nanoTime();
 303
 304     this.state           = state;
 305     this.typeUtil        = tu;
 306     this.callGraph       = callGraph;
 307     this.allocationDepth = allocationDepth;
 308     this.writeDOTs       = writeDOTs;
 309     this.writeAllDOTs    = writeAllDOTs;
 310
 311     descriptorsToAnalyze = new HashSet<Descriptor>();
 312
 313     mapMethodContextToInitialParamAllocGraph =
 314       new Hashtable<MethodContext, OwnershipGraph>();
 315
 316     mapMethodContextToCompleteOwnershipGraph =
 317       new Hashtable<MethodContext, OwnershipGraph>();
 318
 319     mapFlatNewToAllocationSite =
 320       new Hashtable<FlatNew, AllocationSite>();
 321
 322     mapDescriptorToAllocationSiteSet =
 323       new Hashtable<Descriptor, HashSet<AllocationSite> >();
 324
 325     mapDescriptorToAllMethodContexts =
 326       new Hashtable<Descriptor, HashSet<MethodContext> >();
 327
 328     mapTypeToArrayField =
 329       new Hashtable<TypeDescriptor, FieldDescriptor>();
 330
 331     mapTypeToVarField =
 332       new Hashtable<TypeDescriptor, FieldDescriptor>();
 333
 334     if( writeAllDOTs ) {
 335       mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
 336     }
 337
 338
 339     if( state.TASK ) {
 340       // initialize methods to visit as the set of all tasks in the
 341       // program and then any method that could be called starting
 342       // from those tasks
 343       Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 344       while( taskItr.hasNext() ) {
 345         Descriptor d = (Descriptor) taskItr.next();
 346         scheduleAllCallees(d);
 347       }
 348
 349     } else {
 350       // we are not in task mode, just normal Java, so start with
 351       // the main method
 352       Descriptor d = typeUtil.getMain();
 353       scheduleAllCallees(d);
 354     }
 355
 356
 357     // before beginning analysis, initialize every scheduled method
 358     // with an ownership graph that has populated parameter index tables
 359     // by analyzing the first node which is always a FlatMethod node
 360     Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
 361     while( dItr.hasNext() ) {
 362       Descriptor d  = dItr.next();
 363       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 364
 365       FlatMethod fm;
 366       if( d instanceof MethodDescriptor ) {
 367         fm = state.getMethodFlat( (MethodDescriptor) d);
 368       } else {
 369         assert d instanceof TaskDescriptor;
 370         fm = state.getMethodFlat( (TaskDescriptor) d);
 371       }
 372
 373       MethodContext mc = new MethodContext( d );
 374       assert !mapDescriptorToAllMethodContexts.containsKey( d );
 375       HashSet<MethodContext> s = new HashSet<MethodContext>();
 376       s.add( mc );
 377       mapDescriptorToAllMethodContexts.put( d, s );
 378
 379       //System.out.println("Previsiting " + mc);
 380
 381       og = analyzeFlatNode(mc, fm, null, og);
 382       setGraphForMethodContext(mc, og);
 383     }
 384
 385     // as mentioned above, analyze methods one-by-one, possibly revisiting
 386     // a method if the methods that it calls are updated
 387     analyzeMethods();
 388
 389     double timeEndAnalysis = (double) System.nanoTime();
 390     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 391     String treport = String.format( "The analysis took %.3f sec.", dt );
 392     System.out.println( treport );
 393
 394     if( writeDOTs && !writeAllDOTs ) {
 395       writeFinalContextGraphs();
 396     }
 397
 398     if( aliasFile != null ) {
 399       if( state.TASK ) {
 400         writeAllAliases(aliasFile);
 401       } else {
 402         writeAllAliasesJava(aliasFile);
 403       }
 404     }
 405   }
 406
 407   // called from the constructor to help initialize the set
 408   // of methods that needs to be analyzed by ownership analysis
 409   private void scheduleAllCallees(Descriptor d) {
 410     if( descriptorsToAnalyze.contains(d) ) {
 411       return;
 412     }
 413     descriptorsToAnalyze.add(d);
 414
 415     // start with all method calls to further schedule
 416     Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
 417
 418     if( d instanceof MethodDescriptor ) {
 419       // see if this method has virtual dispatch
 420       Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
 421       moreMethodsToCheck.addAll(virtualMethods);
 422     }
 423
 424     // keep following any further methods identified in
 425     // the call chain
 426     Iterator methItr = moreMethodsToCheck.iterator();
 427     while( methItr.hasNext() ) {
 428       Descriptor m = (Descriptor) methItr.next();
 429       scheduleAllCallees(m);
 430     }
 431   }
 432
 433
 434   // manage the set of tasks and methods to be analyzed
 435   // and be sure to reschedule tasks/methods when the methods
 436   // they call are updated
 437   private void analyzeMethods() throws java.io.IOException {
 438
 439     methodContextsToVisit       = new HashSet   <MethodContext>();
 440     sortedMethodContextsToVisit = new LinkedList<MethodContext>();
 441
 442     Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
 443     while( itrd2a.hasNext() ) {
 444       HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
 445       assert mcs != null;
 446
 447       Iterator<MethodContext> itrmc = mcs.iterator();
 448       while( itrmc.hasNext() ) {
 449         methodContextsToVisit.add( itrmc.next() );
 450       }
 451     }
 452
 453     sortedMethodContextsToVisit = topologicalSort( methodContextsToVisit );
 454     methodContextsToVisit.clear();
 455
 456     while( !methodContextsToVisit.isEmpty()       ||
 457            !sortedMethodContextsToVisit.isEmpty()    ) {
 458
 459       MethodContext mc = null;
 460
 461       if( !sortedMethodContextsToVisit.isEmpty() ) {
 462         mc = sortedMethodContextsToVisit.removeFirst();
 463       } else {
 464         mc = methodContextsToVisit.iterator().next();
 465         methodContextsToVisit.remove(mc);
 466       }
 467
 468
 469       // because the task or method descriptor just extracted
 470       // was in the "to visit" set it either hasn't been analyzed
 471       // yet, or some method that it depends on has been
 472       // updated.  Recompute a complete ownership graph for
 473       // this task/method and compare it to any previous result.
 474       // If there is a change detected, add any methods/tasks
 475       // that depend on this one to the "to visit" set.
 476
 477       System.out.println("Analyzing " + mc);
 478
 479       Descriptor d = mc.getDescriptor();
 480       FlatMethod fm;
 481       if( d instanceof MethodDescriptor ) {
 482         fm = state.getMethodFlat( (MethodDescriptor) d);
 483       } else {
 484         assert d instanceof TaskDescriptor;
 485         fm = state.getMethodFlat( (TaskDescriptor) d);
 486       }
 487
 488       OwnershipGraph og = analyzeFlatMethod(mc, fm);
 489       OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
 490       if( !og.equals(ogPrev) ) {
 491         setGraphForMethodContext(mc, og);
 492
 493         // only methods have dependents, tasks cannot
 494         // be invoked by any user program calls
 495         if( d instanceof MethodDescriptor ) {
 496           MethodDescriptor md = (MethodDescriptor) d;
 497           Set dependents = callGraph.getCallerSet(md);
 498           if( dependents != null ) {
 499             Iterator depItr = dependents.iterator();
 500             while( depItr.hasNext() ) {
 501               Descriptor dependent = (Descriptor) depItr.next();
 502               if( descriptorsToAnalyze.contains(dependent) ) {
 503
 504                 HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( dependent );
 505                 assert mcs != null;
 506
 507                 Iterator<MethodContext> itrmc = mcs.iterator();
 508                 while( itrmc.hasNext() ) {
 509                   methodContextsToVisit.add( itrmc.next() );
 510                 }
 511               }
 512             }
 513           }
 514         }
 515       }
 516     }
 517
 518   }
 519
 520
 521   // keep passing the Descriptor of the method along for debugging
 522   // and dot file writing
 523   private OwnershipGraph
 524   analyzeFlatMethod(MethodContext mc,
 525                     FlatMethod flatm) throws java.io.IOException {
 526
 527     // initialize flat nodes to visit as the flat method
 528     // because it is the entry point
 529
 530     flatNodesToVisit = new HashSet<FlatNode>();
 531     flatNodesToVisit.add(flatm);
 532
 533     // initilize the mapping of flat nodes in this flat method to
 534     // ownership graph results to an empty mapping
 535     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 536
 537     // initialize the set of return nodes that will be combined as
 538     // the final ownership graph result to return as an empty set
 539     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 540
 541
 542     while( !flatNodesToVisit.isEmpty() ) {
 543       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 544       flatNodesToVisit.remove(fn);
 545
 546       //System.out.println( "  "+fn );
 547
 548       // perform this node's contributions to the ownership
 549       // graph on a new copy, then compare it to the old graph
 550       // at this node to see if anything was updated.
 551       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 552
 553       // start by merging all node's parents' graphs
 554       for( int i = 0; i < fn.numPrev(); ++i ) {
 555         FlatNode pn = fn.getPrev(i);
 556         if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
 557           OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
 558           og.merge(ogParent);
 559         }
 560       }
 561
 562       // apply the analysis of the flat node to the
 563       // ownership graph made from the merge of the
 564       // parent graphs
 565       og = analyzeFlatNode(mc,
 566                            fn,
 567                            returnNodesToCombineForCompleteOwnershipGraph,
 568                            og);
 569
 570       /*
 571       if( mc.getDescriptor().getSymbol().equals( "addFlightPlan" ) ) {
 572         debugSnapshot(og,fn);
 573       }
 574       */
 575
 576
 577       // if the results of the new graph are different from
 578       // the current graph at this node, replace the graph
 579       // with the update and enqueue the children for
 580       // processing
 581       OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
 582       if( !og.equals(ogPrev) ) {
 583         mapFlatNodeToOwnershipGraph.put(fn, og);
 584
 585         for( int i = 0; i < fn.numNext(); i++ ) {
 586           FlatNode nn = fn.getNext(i);
 587           flatNodesToVisit.add(nn);
 588         }
 589       }
 590     }
 591
 592     // end by merging all return nodes into a complete
 593     // ownership graph that represents all possible heap
 594     // states after the flat method returns
 595     OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil);
 596     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 597     while( retItr.hasNext() ) {
 598       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 599       assert mapFlatNodeToOwnershipGraph.containsKey(frn);
 600       OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
 601       completeGraph.merge(ogr);
 602     }
 603
 604     return completeGraph;
 605   }
 606
 607
 608   private OwnershipGraph
 609   analyzeFlatNode(MethodContext mc,
 610                   FlatNode fn,
 611                   HashSet<FlatReturnNode> setRetNodes,
 612                   OwnershipGraph og) throws java.io.IOException {
 613
 614     TempDescriptor lhs;
 615     TempDescriptor rhs;
 616     FieldDescriptor fld;
 617
 618     // use node type to decide what alterations to make
 619     // to the ownership graph
 620     switch( fn.kind() ) {
 621
 622     case FKind.FlatMethod:
 623       FlatMethod fm = (FlatMethod) fn;
 624
 625       // there should only be one FlatMethod node as the
 626       // parent of all other FlatNode objects, so take
 627       // the opportunity to construct the initial graph by
 628       // adding parameters labels to new heap regions
 629       // AND this should be done once globally so that the
 630       // parameter IDs are consistent between analysis
 631       // iterations, so if this step has been done already
 632       // just merge in the cached version
 633       OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
 634       if( ogInitParamAlloc == null ) {
 635
 636         // if the method context has aliased parameters, make sure
 637         // there is a blob region for all those param labels to
 638         // reference
 639         Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
 640         if( !aliasedParamIndices.isEmpty() ) {
 641           og.makeAliasedParamHeapRegionNode( tdAliasedParams );
 642         }
 643
 644         // set up each parameter
 645         for( int i = 0; i < fm.numParameters(); ++i ) {
 646           TempDescriptor tdParam = fm.getParameter( i );
 647           Integer        paramIndex = new Integer( i );
 648
 649           if( aliasedParamIndices.contains( paramIndex ) ) {
 650             // just point this one to the alias blob
 651             og.assignTempEqualToAliasedParam( tdParam,
 652                                               tdAliasedParams,
 653                                               paramIndex );
 654           } else {
 655             // this parameter is not aliased to others, give it
 656             // a fresh parameter heap region
 657
 658             og.assignTempEqualToParamAlloc(tdParam,
 659                                            mc.getDescriptor() instanceof TaskDescriptor,
 660                                            paramIndex );
 661           }
 662         }
 663
 664         // cache the graph
 665         OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
 666         ogResult.merge(og);
 667         mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
 668
 669       } else {
 670         // or just leverage the cached copy
 671         og.merge(ogInitParamAlloc);
 672       }
 673       break;
 674
 675     case FKind.FlatOpNode:
 676       FlatOpNode fon = (FlatOpNode) fn;
 677       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 678         lhs = fon.getDest();
 679         rhs = fon.getLeft();
 680         og.assignTempXEqualToTempY(lhs, rhs);
 681       }
 682       break;
 683
 684     case FKind.FlatCastNode:
 685       FlatCastNode fcn = (FlatCastNode) fn;
 686       lhs = fcn.getDst();
 687       rhs = fcn.getSrc();
 688       TypeDescriptor td = fcn.getType();
 689       assert td != null;
 690
 691       FieldDescriptor fd = mapTypeToVarField.get( td );
 692       if( fd == null ) {
 693         fd = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 694                                  td,
 695                                  "",
 696                                  null,
 697                                  false);
 698         mapTypeToVarField.put( td, fd );
 699       }
 700
 701       og.assignTypedTempXEqualToTempY(lhs, rhs, fd);
 702       break;
 703
 704     case FKind.FlatFieldNode:
 705       FlatFieldNode ffn = (FlatFieldNode) fn;
 706       lhs = ffn.getDst();
 707       rhs = ffn.getSrc();
 708       fld = ffn.getField();
 709       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 710         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
 711       }
 712       break;
 713
 714     case FKind.FlatSetFieldNode:
 715       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 716       lhs = fsfn.getDst();
 717       fld = fsfn.getField();
 718       rhs = fsfn.getSrc();
 719       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 720         og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
 721       }
 722       break;
 723
 724     case FKind.FlatElementNode:
 725       FlatElementNode fen = (FlatElementNode) fn;
 726       lhs = fen.getDst();
 727       rhs = fen.getSrc();
 728       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 729
 730         assert rhs.getType() != null;
 731         assert rhs.getType().isArray();
 732
 733         TypeDescriptor  tdElement = rhs.getType().dereference();
 734         FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
 735         if( fdElement == null ) {
 736           fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 737                                           tdElement,
 738                                           "_element",
 739                                           null,
 740                                           false);
 741           mapTypeToArrayField.put( tdElement, fdElement );
 742         }
 743
 744         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
 745       }
 746       break;
 747
 748     case FKind.FlatSetElementNode:
 749       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 750       lhs = fsen.getDst();
 751       rhs = fsen.getSrc();
 752       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 753
 754         assert lhs.getType() != null;
 755         assert lhs.getType().isArray();
 756
 757         TypeDescriptor  tdElement = lhs.getType().dereference();
 758         FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
 759         if( fdElement == null ) {
 760           fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 761                                           tdElement,
 762                                           "_element",
 763                                           null,
 764                                           false);
 765           mapTypeToArrayField.put( tdElement, fdElement );
 766         }
 767
 768         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
 769       }
 770       break;
 771
 772     case FKind.FlatNew:
 773       FlatNew fnn = (FlatNew) fn;
 774       lhs = fnn.getDst();
 775       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 776         AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 777         og.assignTempEqualToNewAlloc(lhs, as);
 778       }
 779       break;
 780
 781     case FKind.FlatCall:
 782       FlatCall fc = (FlatCall) fn;
 783       MethodDescriptor md = fc.getMethod();
 784       FlatMethod flatm = state.getMethodFlat(md);
 785       OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil);
 786
 787       if( md.isStatic() ) {
 788         // a static method is simply always the same, makes life easy
 789         ogMergeOfAllPossibleCalleeResults = og;
 790
 791         Set<Integer> aliasedParamIndices =
 792           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
 793         MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
 794         OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 795
 796         if( onlyPossibleCallee == null ) {
 797           // if this method context has never been analyzed just schedule it for analysis
 798           // and skip over this call site for now
 799           methodContextsToVisit.add( mcNew );
 800
 801         } else {
 802           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee);
 803         }
 804
 805       } else {
 806         // if the method descriptor is virtual, then there could be a
 807         // set of possible methods that will actually be invoked, so
 808         // find all of them and merge all of their results together
 809         TypeDescriptor typeDesc = fc.getThis().getType();
 810         Set possibleCallees = callGraph.getMethods(md, typeDesc);
 811
 812         Iterator i = possibleCallees.iterator();
 813         while( i.hasNext() ) {
 814           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 815           FlatMethod pflatm = state.getMethodFlat(possibleMd);
 816
 817           // don't alter the working graph (og) until we compute a result for every
 818           // possible callee, merge them all together, then set og to that
 819           OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
 820           ogCopy.merge(og);
 821
 822           Set<Integer> aliasedParamIndices =
 823             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
 824           MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
 825           OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 826
 827           if( ogPotentialCallee == null ) {
 828             // if this method context has never been analyzed just schedule it for analysis
 829             // and skip over this call site for now
 830             methodContextsToVisit.add( mcNew );
 831
 832           } else {
 833             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee);
 834           }
 835
 836           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
 837         }
 838       }
 839
 840       og = ogMergeOfAllPossibleCalleeResults;
 841       break;
 842
 843     case FKind.FlatReturnNode:
 844       FlatReturnNode frn = (FlatReturnNode) fn;
 845       rhs = frn.getReturnTemp();
 846       if( rhs != null && !rhs.getType().isImmutable() ) {
 847         og.assignReturnEqualToTemp(rhs);
 848       }
 849       setRetNodes.add(frn);
 850       break;
 851     }
 852
 853     return og;
 854   }
 855
 856
 857   // insert a call to debugSnapshot() somewhere in the analysis to get
 858   // successive captures of the analysis state
 859   int debugCounter        = 0;
 860   int numStartCountReport = 0;
 861   int freqCountReport     = 1;
 862   int iterStartCapture    = 0;
 863   int numIterToCapture    = 500;
 864   void debugSnapshot(OwnershipGraph og, FlatNode fn) {
 865     if( debugCounter > numStartCountReport + numIterToCapture ) {
 866       return;
 867     }
 868
 869     ++debugCounter;
 870     if( debugCounter > numStartCountReport &&
 871         debugCounter % freqCountReport == 0 ) {
 872       System.out.println("    @@@ debug counter = "+debugCounter);
 873     }
 874     if( debugCounter > iterStartCapture ) {
 875       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
 876       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
 877       if( fn != null ) {
 878         graphName = graphName+fn;
 879       }
 880       try {
 881         og.writeGraph(graphName, true, true, false, false, false);
 882       } catch( Exception e ) {
 883         System.out.println("Error writing debug capture.");
 884         System.exit(0);
 885       }
 886     }
 887     /*
 888     if( debugCounter == iterStartCapture + numIterToCapture ) {
 889       System.out.println("Stopping analysis after debug captures.");
 890       System.exit(0);
 891     }
 892     */
 893   }
 894
 895
 896
 897   // this method should generate integers strictly greater than zero!
 898   // special "shadow" regions are made from a heap region by negating
 899   // the ID
 900   static public Integer generateUniqueHeapRegionNodeID() {
 901     ++uniqueIDcount;
 902     return new Integer(uniqueIDcount);
 903   }
 904
 905
 906   private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og) {
 907
 908     mapMethodContextToCompleteOwnershipGraph.put(mc, og);
 909
 910     if( writeDOTs && writeAllDOTs ) {
 911       if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
 912         mapMethodContextToNumUpdates.put(mc, new Integer(0) );
 913       }
 914       Integer n = mapMethodContextToNumUpdates.get(mc);
 915       try {
 916         og.writeGraph(mc, n, true, true, true, false, false);
 917       } catch( IOException e ) {}
 918       mapMethodContextToNumUpdates.put(mc, n + 1);
 919     }
 920   }
 921
 922
 923   private void writeFinalContextGraphs() {
 924     // arguments to writeGraph are:
 925     // boolean writeLabels,
 926     // boolean labelSelect,
 927     // boolean pruneGarbage,
 928     // boolean writeReferencers
 929     // boolean writeParamMappings
 930
 931     Set entrySet = mapMethodContextToCompleteOwnershipGraph.entrySet();
 932     Iterator itr = entrySet.iterator();
 933     while( itr.hasNext() ) {
 934       Map.Entry      me = (Map.Entry)      itr.next();
 935       MethodContext  mc = (MethodContext)  me.getKey();
 936       OwnershipGraph og = (OwnershipGraph) me.getValue();
 937
 938       try {
 939         og.writeGraph(mc, true, true, true, false, false);
 940       } catch( IOException e ) {}
 941     }
 942   }
 943
 944
 945   // return just the allocation site associated with one FlatNew node
 946   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
 947
 948     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
 949       AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
 950
 951       // the newest nodes are single objects
 952       for( int i = 0; i < allocationDepth; ++i ) {
 953         Integer id = generateUniqueHeapRegionNodeID();
 954         as.setIthOldest(i, id);
 955       }
 956
 957       // the oldest node is a summary node
 958       Integer idSummary = generateUniqueHeapRegionNodeID();
 959       as.setSummary(idSummary);
 960
 961       mapFlatNewToAllocationSite.put(fn, as);
 962     }
 963
 964     return mapFlatNewToAllocationSite.get(fn);
 965   }
 966
 967
 968   // return all allocation sites in the method (there is one allocation
 969   // site per FlatNew node in a method)
 970   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
 971     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
 972       buildAllocationSiteSet(d);
 973     }
 974
 975     return mapDescriptorToAllocationSiteSet.get(d);
 976
 977   }
 978
 979   private void buildAllocationSiteSet(Descriptor d) {
 980     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
 981
 982     FlatMethod fm;
 983     if( d instanceof MethodDescriptor ) {
 984       fm = state.getMethodFlat( (MethodDescriptor) d);
 985     } else {
 986       assert d instanceof TaskDescriptor;
 987       fm = state.getMethodFlat( (TaskDescriptor) d);
 988     }
 989
 990     // visit every node in this FlatMethod's IR graph
 991     // and make a set of the allocation sites from the
 992     // FlatNew node's visited
 993     HashSet<FlatNode> visited = new HashSet<FlatNode>();
 994     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 995     toVisit.add(fm);
 996
 997     while( !toVisit.isEmpty() ) {
 998       FlatNode n = toVisit.iterator().next();
 999
1000       if( n instanceof FlatNew ) {
1001         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
1002       }
1003
1004       toVisit.remove(n);
1005       visited.add(n);
1006
1007       for( int i = 0; i < n.numNext(); ++i ) {
1008         FlatNode child = n.getNext(i);
1009         if( !visited.contains(child) ) {
1010           toVisit.add(child);
1011         }
1012       }
1013     }
1014
1015     mapDescriptorToAllocationSiteSet.put(d, s);
1016   }
1017
1018
1019   private HashSet<AllocationSite> getFlaggedAllocationSites(Descriptor dIn) {
1020
1021     HashSet<AllocationSite> out     = new HashSet<AllocationSite>();
1022     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1023     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1024
1025     toVisit.add(dIn);
1026
1027     while( !toVisit.isEmpty() ) {
1028       Descriptor d = toVisit.iterator().next();
1029       toVisit.remove(d);
1030       visited.add(d);
1031
1032       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1033       Iterator asItr = asSet.iterator();
1034       while( asItr.hasNext() ) {
1035         AllocationSite as = (AllocationSite) asItr.next();
1036         if( as.getDisjointId() != null ) {
1037           out.add(as);
1038         }
1039       }
1040
1041       // enqueue callees of this method to be searched for
1042       // allocation sites also
1043       Set callees = callGraph.getCalleeSet(d);
1044       if( callees != null ) {
1045         Iterator methItr = callees.iterator();
1046         while( methItr.hasNext() ) {
1047           MethodDescriptor md = (MethodDescriptor) methItr.next();
1048
1049           if( !visited.contains(md) ) {
1050             toVisit.add(md);
1051           }
1052         }
1053       }
1054     }
1055
1056     return out;
1057   }
1058
1059
1060   private HashSet<AllocationSite>
1061   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1062
1063     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
1064     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1065     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1066
1067     toVisit.add(td);
1068
1069     // traverse this task and all methods reachable from this task
1070     while( !toVisit.isEmpty() ) {
1071       Descriptor d = toVisit.iterator().next();
1072       toVisit.remove(d);
1073       visited.add(d);
1074
1075       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1076       Iterator asItr = asSet.iterator();
1077       while( asItr.hasNext() ) {
1078         AllocationSite as = (AllocationSite) asItr.next();
1079         TypeDescriptor typed = as.getType();
1080         if( typed != null ) {
1081           ClassDescriptor cd = typed.getClassDesc();
1082           if( cd != null && cd.hasFlags() ) {
1083             asSetTotal.add(as);
1084           }
1085         }
1086       }
1087
1088       // enqueue callees of this method to be searched for
1089       // allocation sites also
1090       Set callees = callGraph.getCalleeSet(d);
1091       if( callees != null ) {
1092         Iterator methItr = callees.iterator();
1093         while( methItr.hasNext() ) {
1094           MethodDescriptor md = (MethodDescriptor) methItr.next();
1095
1096           if( !visited.contains(md) ) {
1097             toVisit.add(md);
1098           }
1099         }
1100       }
1101     }
1102
1103
1104     return asSetTotal;
1105   }
1106
1107
1108   private LinkedList<MethodContext> topologicalSort( HashSet<MethodContext> set ) {
1109     HashSet   <MethodContext> discovered = new HashSet   <MethodContext>();
1110     LinkedList<MethodContext> sorted     = new LinkedList<MethodContext>();
1111
1112     Iterator<MethodContext> itr = set.iterator();
1113     while( itr.hasNext() ) {
1114       MethodContext mc = itr.next();
1115
1116       if( !discovered.contains( mc ) ) {
1117         dfsVisit( set, mc, sorted, discovered );
1118       }
1119     }
1120
1121     return sorted;
1122   }
1123
1124   private void dfsVisit( HashSet<MethodContext> set,
1125                          MethodContext mc,
1126                          LinkedList<MethodContext> sorted,
1127                          HashSet   <MethodContext> discovered ) {
1128     discovered.add( mc );
1129
1130     Descriptor d = mc.getDescriptor();
1131     if( d instanceof MethodDescriptor ) {
1132       MethodDescriptor md = (MethodDescriptor) d;
1133       Iterator itr = callGraph.getCallerSet( md ).iterator();
1134       while( itr.hasNext() ) {
1135         Descriptor dCaller = (Descriptor) itr.next();
1136
1137         // only consider the callers in the original set to analyze
1138         Set<MethodContext> callerContexts = mapDescriptorToAllMethodContexts.get( dCaller );
1139         if( callerContexts == null )
1140           continue;
1141
1142         // since the analysis hasn't started, there should be exactly one
1143         // context if there are any at all
1144         assert callerContexts.size() == 1;
1145         MethodContext mcCaller = callerContexts.iterator().next();
1146         assert set.contains( mcCaller );
1147
1148         if( !discovered.contains( mcCaller ) ) {
1149           dfsVisit( set, mcCaller, sorted, discovered );
1150         }
1151       }
1152     }
1153
1154     sorted.addFirst( mc );
1155   }
1156 }