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   //  Public interface to discover possible
  16   //  aliases in the program under analysis
  17   //
  18   ///////////////////////////////////////////
  19   /*
  20      public HashSet<AllocationSite>
  21       getFlaggedAllocationSitesReachableFromTask( TaskDescriptor td ) {
  22
  23       return getFlaggedAllocationSitesReachableFromTaskPRIVATE( td );
  24      }
  25
  26      public AllocationSite getAllocationSiteFromFlatNew( FlatNew fn ) {
  27       return getAllocationSiteFromFlatNewPRIVATE( fn );
  28      }
  29
  30      public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  31                                           int            paramIndex1,
  32                                           int            paramIndex2 ) {
  33
  34       OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  35       assert( og != null );
  36
  37       return createsPotentialAliases( og,
  38                                       getHeapRegionIDset( og, paramIndex1 ),
  39                                       getHeapRegionIDset( og, paramIndex2 ) );
  40      }
  41
  42      public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  43                                           int            paramIndex,
  44                                           AllocationSite alloc ) {
  45
  46       OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  47       assert( og != null );
  48
  49       return createsPotentialAliases( og,
  50                                       getHeapRegionIDset( og, paramIndex ),
  51                                       getHeapRegionIDset( alloc ) );
  52      }
  53
  54      public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  55                                           AllocationSite alloc,
  56                                           int            paramIndex ) {
  57
  58       OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  59       assert( og != null );
  60
  61       return createsPotentialAliases( og,
  62                                       getHeapRegionIDset( og, paramIndex ),
  63                                       getHeapRegionIDset( alloc ) );
  64      }
  65
  66      public boolean createsPotentialAliases( Descriptor     taskOrMethod,
  67                                           AllocationSite alloc1,
  68                                           AllocationSite alloc2 ) {
  69
  70       OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  71       assert( og != null );
  72
  73       return createsPotentialAliases( og,
  74                                       getHeapRegionIDset( alloc1 ),
  75                                       getHeapRegionIDset( alloc2 ) );
  76      }
  77
  78      public boolean createsPotentialAliases( Descriptor              taskOrMethod,
  79                                           AllocationSite          alloc,
  80                                           HashSet<AllocationSite> allocSet ) {
  81
  82       OwnershipGraph og = mapDescriptorToCompleteOwnershipGraph.get( taskOrMethod );
  83       assert( og != null );
  84
  85       return createsPotentialAliases( og,
  86                                       getHeapRegionIDset( alloc ),
  87                                       getHeapRegionIDset( allocSet ) );
  88      }
  89    */
  90
  91   // use the methods given above to check every possible alias
  92   // between task parameters and flagged allocation sites reachable
  93   // from the task
  94   public void writeAllAliases(String outputFile) throws java.io.IOException {
  95
  96     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
  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         HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask( td );
 104
 105         // for each task parameter, check for aliases with
 106         // other task parameters and every allocation site
 107         // reachable from this task
 108         FlatMethod fm = state.getMethodFlat( td );
 109         for( int i = 0; i < fm.numParameters(); ++i ) {
 110
 111             // for the ith parameter check for aliases to all
 112             // higher numbered parameters
 113             for( int j = i + 1; j < fm.numParameters(); ++j ) {
 114                 if( createsPotentialAliases( td, i, j ) ) {
 115                     bw.write( "Task "+td+" potentially aliases parameters "+i+" and "+j+".\n" );
 116                 }
 117             }
 118
 119             // for the ith parameter, check for aliases against
 120             // the set of allocation sites reachable from this
 121             // task context
 122             Iterator allocItr = allocSites.iterator();
 123             while( allocItr.hasNext() ) {
 124                 AllocationSite as = (AllocationSite) allocItr.next();
 125                 if( createsPotentialAliases( td, i, as ) ) {
 126                     bw.write( "Task "+td+" potentially aliases parameter "+i+" and "+as+".\n" );
 127                 }
 128             }
 129         }
 130
 131         // for each allocation site check for aliases with
 132         // other allocation sites in the context of execution
 133         // of this task
 134         Iterator allocItr = allocSites.iterator();
 135         while( allocItr.hasNext() ) {
 136             AllocationSite as = (AllocationSite) allocItr.next();
 137             if( createsPotentialAliases( td, as, allocSites ) ) {
 138                 bw.write( "Task "+td+" potentially aliases "+as+" and the rest of the set.\n" );
 139             }
 140         }
 141        }
 142
 143        bw.close();
 144      */
 145   }
 146
 147   ///////////////////////////////////////////
 148   //
 149   // end public interface
 150   //
 151   ///////////////////////////////////////////
 152
 153
 154
 155
 156
 157
 158
 159
 160   // data from the compiler
 161   private State state;
 162   private CallGraph callGraph;
 163   private int allocationDepth;
 164
 165   // used to identify HeapRegionNode objects
 166   // A unique ID equates an object in one
 167   // ownership graph with an object in another
 168   // graph that logically represents the same
 169   // heap region
 170   // start at 10 and incerement to leave some
 171   // reserved IDs for special purposes
 172   static private int uniqueIDcount = 10;
 173
 174
 175   // Use these data structures to track progress of
 176   // processing all methods in the program, and by methods
 177   // TaskDescriptor and MethodDescriptor are combined
 178   // together, with a common parent class Descriptor
 179   private Hashtable<Descriptor, OwnershipGraph>           mapDescriptorToCompleteOwnershipGraph;
 180   private Hashtable<FlatNew,    AllocationSite>           mapFlatNewToAllocationSite;
 181   private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
 182
 183   // Use these data structures to track progress of one pass of
 184   // processing the FlatNodes of a particular method
 185   private HashSet  <FlatNode>                 flatNodesToVisit;
 186   private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
 187   private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
 188
 189   // descriptorsToAnalyze identifies the set of tasks and methods
 190   // that are reachable from the program tasks, this set is initialized
 191   // and then remains static
 192   private HashSet<Descriptor> descriptorsToAnalyze;
 193
 194   // descriptorsToVisit is initialized to descriptorsToAnalyze and is
 195   // reduced by visiting a descriptor during analysis.  When dependents
 196   // must be scheduled, only those contained in descriptorsToAnalyze
 197   // should be re-added to this set
 198   private HashSet<Descriptor> descriptorsToVisit;
 199
 200   // a special field descriptor for all array elements
 201   private static FieldDescriptor fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 202                                                                  new TypeDescriptor( "Array[]" ),
 203                                                                  "elements",
 204                                                                  null,
 205                                                                  false);
 206
 207
 208   // this analysis generates an ownership graph for every task
 209   // in the program
 210   public OwnershipAnalysis(State state,
 211                            CallGraph callGraph,
 212                            int allocationDepth) throws java.io.IOException {
 213     this.state           = state;
 214     this.callGraph       = callGraph;
 215     this.allocationDepth = allocationDepth;
 216
 217
 218     descriptorsToAnalyze = new HashSet<Descriptor>();
 219
 220     mapDescriptorToCompleteOwnershipGraph =
 221       new Hashtable<Descriptor, OwnershipGraph>();
 222
 223     mapFlatNewToAllocationSite =
 224       new Hashtable<FlatNew, AllocationSite>();
 225
 226     mapDescriptorToAllocationSiteSet =
 227       new Hashtable<Descriptor, HashSet<AllocationSite> >();
 228
 229
 230     // initialize methods to visit as the set of all tasks in the
 231     // program and then any method that could be called starting
 232     // from those tasks
 233     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 234     while( taskItr.hasNext() ) {
 235       Descriptor d = (Descriptor) taskItr.next();
 236       scheduleAllCallees(d);
 237     }
 238
 239     // before beginning analysis, initialize every scheduled method
 240     // with an ownership graph that has populated parameter index tables
 241     // by analyzing the first node which is always a FlatMethod node
 242     Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
 243     while( dItr.hasNext() ) {
 244       Descriptor d  = dItr.next();
 245       OwnershipGraph og = new OwnershipGraph(allocationDepth);
 246
 247       FlatMethod fm;
 248       if( d instanceof MethodDescriptor ) {
 249         fm = state.getMethodFlat( (MethodDescriptor) d);
 250       } else {
 251         assert d instanceof TaskDescriptor;
 252         fm = state.getMethodFlat( (TaskDescriptor) d);
 253       }
 254
 255       System.out.println("Previsiting " + d);
 256
 257       analyzeFlatNode(d, fm, null, og);
 258       mapDescriptorToCompleteOwnershipGraph.put(d, og);
 259     }
 260
 261     System.out.println("");
 262
 263     // as mentioned above, analyze methods one-by-one, possibly revisiting
 264     // a method if the methods that it calls are updated
 265     analyzeMethods();
 266   }
 267
 268   // called from the constructor to help initialize the set
 269   // of methods that needs to be analyzed by ownership analysis
 270   private void scheduleAllCallees(Descriptor d) {
 271     if( descriptorsToAnalyze.contains(d) ) {
 272       return;
 273     }
 274     descriptorsToAnalyze.add(d);
 275
 276     // start with all method calls to further schedule
 277     Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
 278
 279     if( d instanceof MethodDescriptor ) {
 280       // see if this method has virtual dispatch
 281       Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
 282       moreMethodsToCheck.addAll(virtualMethods);
 283     }
 284
 285     // keep following any further methods identified in
 286     // the call chain
 287     Iterator methItr = moreMethodsToCheck.iterator();
 288     while( methItr.hasNext() ) {
 289       Descriptor m = (Descriptor) methItr.next();
 290       scheduleAllCallees(m);
 291     }
 292   }
 293
 294
 295   // manage the set of tasks and methods to be analyzed
 296   // and be sure to reschedule tasks/methods when the methods
 297   // they call are updated
 298   private void analyzeMethods() throws java.io.IOException {
 299
 300     descriptorsToVisit = (HashSet<Descriptor>)descriptorsToAnalyze.clone();
 301
 302     while( !descriptorsToVisit.isEmpty() ) {
 303       Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
 304       descriptorsToVisit.remove(d);
 305
 306       // because the task or method descriptor just extracted
 307       // was in the "to visit" set it either hasn't been analyzed
 308       // yet, or some method that it depends on has been
 309       // updated.  Recompute a complete ownership graph for
 310       // this task/method and compare it to any previous result.
 311       // If there is a change detected, add any methods/tasks
 312       // that depend on this one to the "to visit" set.
 313
 314       System.out.println("Analyzing " + d);
 315
 316       FlatMethod fm;
 317       if( d instanceof MethodDescriptor ) {
 318         fm = state.getMethodFlat( (MethodDescriptor) d);
 319       } else {
 320         assert d instanceof TaskDescriptor;
 321         fm = state.getMethodFlat( (TaskDescriptor) d);
 322       }
 323
 324       OwnershipGraph og = analyzeFlatMethod(d, fm);
 325       OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get(d);
 326       if( !og.equals(ogPrev) ) {
 327         mapDescriptorToCompleteOwnershipGraph.put(d, og);
 328
 329         /* boolean writeLabels,
 330            boolean labelSelect,
 331            boolean pruneGarbage,
 332            boolean writeReferencers */
 333         og.writeGraph(d, true, true, true, false);
 334
 335         // only methods have dependents, tasks cannot
 336         // be invoked by any user program calls
 337         if( d instanceof MethodDescriptor ) {
 338           MethodDescriptor md = (MethodDescriptor) d;
 339           Set dependents = callGraph.getCallerSet(md);
 340           if( dependents != null ) {
 341             Iterator depItr = dependents.iterator();
 342             while( depItr.hasNext() ) {
 343               Descriptor dependent = (Descriptor) depItr.next();
 344               if( descriptorsToAnalyze.contains(dependent) ) {
 345                 descriptorsToVisit.add(dependent);
 346               }
 347             }
 348           }
 349         }
 350       }
 351     }
 352
 353   }
 354
 355
 356   // keep passing the Descriptor of the method along for debugging
 357   // and dot file writing
 358   private OwnershipGraph
 359   analyzeFlatMethod(Descriptor mDesc,
 360                     FlatMethod flatm) throws java.io.IOException {
 361
 362     // initialize flat nodes to visit as the flat method
 363     // because all other nodes in this flat method are
 364     // decendents of the flat method itself
 365     flatNodesToVisit = new HashSet<FlatNode>();
 366     flatNodesToVisit.add(flatm);
 367
 368
 369     // A YUCKY HACK--this is to make sure that an initially empty
 370     // graph (no parameters) will get passed the first "any changes?"
 371     // test when it comes up for analysis.  It's ugly but throwing
 372     // a child in works.
 373     FlatNode fnJ = flatm.getNext(0);
 374     assert fnJ != null;
 375     flatNodesToVisit.add(fnJ);
 376
 377
 378     // initilize the mapping of flat nodes in this flat method to
 379     // ownership graph results to an empty mapping
 380     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 381
 382     // initialize the set of return nodes that will be combined as
 383     // the final ownership graph result to return as an empty set
 384     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 385
 386
 387     while( !flatNodesToVisit.isEmpty() ) {
 388       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 389       flatNodesToVisit.remove(fn);
 390
 391       // perform this node's contributions to the ownership
 392       // graph on a new copy, then compare it to the old graph
 393       // at this node to see if anything was updated.
 394       OwnershipGraph og = new OwnershipGraph(allocationDepth);
 395
 396       // start by merging all node's parents' graphs
 397       for( int i = 0; i < fn.numPrev(); ++i ) {
 398         FlatNode pn       = fn.getPrev(i);
 399         OwnershipGraph ogParent = getGraphFromFlatNode(pn);
 400         og.merge(ogParent);
 401       }
 402
 403       // apply the analysis of the flat node to the
 404       // ownership graph made from the merge of the
 405       // parent graphs
 406       analyzeFlatNode(mDesc,
 407                       fn,
 408                       returnNodesToCombineForCompleteOwnershipGraph,
 409                       og);
 410
 411       // if the results of the new graph are different from
 412       // the current graph at this node, replace the graph
 413       // with the update and enqueue the children for
 414       // processing
 415       OwnershipGraph ogPrev = getGraphFromFlatNode(fn);
 416
 417       if( !og.equals(ogPrev) ) {
 418         setGraphForFlatNode(fn, og);
 419
 420         for( int i = 0; i < fn.numNext(); i++ ) {
 421           FlatNode nn = fn.getNext(i);
 422           flatNodesToVisit.add(nn);
 423         }
 424       }
 425     }
 426
 427     // end by merging all return nodes into a complete
 428     // ownership graph that represents all possible heap
 429     // states after the flat method returns
 430     OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth);
 431     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 432     while( retItr.hasNext() ) {
 433       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 434       OwnershipGraph ogr = getGraphFromFlatNode(frn);
 435       completeGraph.merge(ogr);
 436     }
 437     return completeGraph;
 438   }
 439
 440
 441   private void
 442   analyzeFlatNode(Descriptor methodDesc,
 443                   FlatNode fn,
 444                   HashSet<FlatReturnNode> setRetNodes,
 445                   OwnershipGraph og) throws java.io.IOException {
 446
 447     TempDescriptor lhs;
 448     TempDescriptor rhs;
 449     FieldDescriptor fld;
 450
 451     // use node type to decide what alterations to make
 452     // to the ownership graph
 453     switch( fn.kind() ) {
 454
 455     case FKind.FlatMethod:
 456       FlatMethod fm = (FlatMethod) fn;
 457
 458       // there should only be one FlatMethod node as the
 459       // parent of all other FlatNode objects, so take
 460       // the opportunity to construct the initial graph by
 461       // adding parameters labels to new heap regions
 462       for( int i = 0; i < fm.numParameters(); ++i ) {
 463         TempDescriptor tdParam = fm.getParameter(i);
 464         og.assignTempEqualToParamAlloc(tdParam,
 465                                        methodDesc instanceof TaskDescriptor,
 466                                        new Integer(i) );
 467       }
 468
 469       break;
 470
 471     case FKind.FlatOpNode:
 472       FlatOpNode fon = (FlatOpNode) fn;
 473       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 474         lhs = fon.getDest();
 475         rhs = fon.getLeft();
 476         og.assignTempXEqualToTempY(lhs, rhs);
 477       }
 478       break;
 479
 480     case FKind.FlatFieldNode:
 481       FlatFieldNode ffn = (FlatFieldNode) fn;
 482       lhs = ffn.getDst();
 483       rhs = ffn.getSrc();
 484       fld = ffn.getField();
 485       if( !fld.getType().isPrimitive() ) {
 486         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
 487       }
 488       break;
 489
 490     case FKind.FlatSetFieldNode:
 491       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 492       lhs = fsfn.getDst();
 493       fld = fsfn.getField();
 494       rhs = fsfn.getSrc();
 495       og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
 496       break;
 497
 498     case FKind.FlatElementNode:
 499       FlatElementNode fen = (FlatElementNode) fn;
 500       lhs = fen.getDst();
 501       rhs = fen.getSrc();
 502       if( !lhs.getType().isPrimitive() ) {
 503         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
 504       }
 505       break;
 506
 507     case FKind.FlatSetElementNode:
 508       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 509       lhs = fsen.getDst();
 510       rhs = fsen.getSrc();
 511       if( !rhs.getType().isPrimitive() ) {
 512         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
 513       }
 514       break;
 515
 516     case FKind.FlatNew:
 517       FlatNew fnn = (FlatNew) fn;
 518       lhs = fnn.getDst();
 519       AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 520
 521       og.assignTempEqualToNewAlloc(lhs, as);
 522       break;
 523
 524     case FKind.FlatCall:
 525       FlatCall fc = (FlatCall) fn;
 526       MethodDescriptor md = fc.getMethod();
 527       FlatMethod flatm = state.getMethodFlat(md);
 528       OwnershipGraph ogAllPossibleCallees = new OwnershipGraph(allocationDepth);
 529
 530       if( md.isStatic() ) {
 531         // a static method is simply always the same, makes life easy
 532         OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get(md);
 533         ogAllPossibleCallees.merge(onlyPossibleCallee);
 534
 535       } else {
 536         // if the method descriptor is virtual, then there could be a
 537         // set of possible methods that will actually be invoked, so
 538         // find all of them and merge all of their graphs together
 539         TypeDescriptor typeDesc = fc.getThis().getType();
 540         Set possibleCallees = callGraph.getMethods(md, typeDesc);
 541
 542         Iterator i = possibleCallees.iterator();
 543         while( i.hasNext() ) {
 544           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 545           OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
 546           ogAllPossibleCallees.merge(ogPotentialCallee);
 547         }
 548       }
 549
 550       // Now we should have the following information to resolve this method call:
 551       //
 552       // 1. A FlatCall fc to query for the caller's context (argument labels, etc)
 553       //
 554       // 2. Whether the method is static; if not we need to deal with the "this" pointer
 555       //
 556       // *******************************************************************************************
 557       // 3. The original FlatMethod flatm to query for callee's context (paramter labels)
 558       //   NOTE!  I assume FlatMethod before virtual dispatch accurately describes all possible methods!
 559       // *******************************************************************************************
 560       //
 561       // 4. The OwnershipGraph ogAllPossibleCallees is a merge of every ownership graph of all the possible
 562       // methods to capture any possible references made.
 563       //
 564       og.resolveMethodCall(fc, md.isStatic(), flatm, ogAllPossibleCallees);
 565       break;
 566
 567     case FKind.FlatReturnNode:
 568       FlatReturnNode frn = (FlatReturnNode) fn;
 569       rhs = frn.getReturnTemp();
 570
 571       if( rhs != null ) {
 572         og.assignReturnEqualToTemp(rhs);
 573       }
 574
 575       setRetNodes.add(frn);
 576       break;
 577     }
 578   }
 579
 580
 581   // this method should generate integers strictly greater than zero!
 582   // special "shadow" regions are made from a heap region by negating
 583   // the ID
 584   static public Integer generateUniqueHeapRegionNodeID() {
 585     ++uniqueIDcount;
 586     return new Integer(uniqueIDcount);
 587   }
 588
 589
 590   private OwnershipGraph getGraphFromFlatNode(FlatNode fn) {
 591     if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) {
 592       mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) );
 593     }
 594
 595     return mapFlatNodeToOwnershipGraph.get(fn);
 596   }
 597
 598   private void setGraphForFlatNode(FlatNode fn, OwnershipGraph og) {
 599     mapFlatNodeToOwnershipGraph.put(fn, og);
 600   }
 601
 602
 603
 604   // return just the allocation site associated with one FlatNew node
 605   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
 606
 607     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
 608       AllocationSite as = new AllocationSite(allocationDepth, fn.getType() );
 609
 610       // the newest nodes are single objects
 611       for( int i = 0; i < allocationDepth; ++i ) {
 612         Integer id = generateUniqueHeapRegionNodeID();
 613         as.setIthOldest(i, id);
 614       }
 615
 616       // the oldest node is a summary node
 617       Integer idSummary = generateUniqueHeapRegionNodeID();
 618       as.setSummary(idSummary);
 619
 620       mapFlatNewToAllocationSite.put(fn, as);
 621     }
 622
 623     return mapFlatNewToAllocationSite.get(fn);
 624   }
 625
 626
 627   // return all allocation sites in the method (there is one allocation
 628   // site per FlatNew node in a method)
 629   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
 630     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
 631       buildAllocationSiteSet(d);
 632     }
 633
 634     return mapDescriptorToAllocationSiteSet.get(d);
 635
 636   }
 637
 638   private void buildAllocationSiteSet(Descriptor d) {
 639     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
 640
 641     FlatMethod fm;
 642     if( d instanceof MethodDescriptor ) {
 643       fm = state.getMethodFlat( (MethodDescriptor) d);
 644     } else {
 645       assert d instanceof TaskDescriptor;
 646       fm = state.getMethodFlat( (TaskDescriptor) d);
 647     }
 648
 649     // visit every node in this FlatMethod's IR graph
 650     // and make a set of the allocation sites from the
 651     // FlatNew node's visited
 652     HashSet<FlatNode> visited = new HashSet<FlatNode>();
 653     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 654     toVisit.add(fm);
 655
 656     while( !toVisit.isEmpty() ) {
 657       FlatNode n = toVisit.iterator().next();
 658
 659       if( n instanceof FlatNew ) {
 660         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
 661       }
 662
 663       toVisit.remove(n);
 664       visited.add(n);
 665
 666       for( int i = 0; i < n.numNext(); ++i ) {
 667         FlatNode child = n.getNext(i);
 668         if( !visited.contains(child) ) {
 669           toVisit.add(child);
 670         }
 671       }
 672     }
 673
 674     mapDescriptorToAllocationSiteSet.put(d, s);
 675   }
 676
 677
 678   private HashSet<AllocationSite>
 679   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
 680
 681     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
 682     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
 683     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
 684
 685     toVisit.add(td);
 686
 687     // traverse this task and all methods reachable from this task
 688     while( !toVisit.isEmpty() ) {
 689       Descriptor d = toVisit.iterator().next();
 690       toVisit.remove(d);
 691       visited.add(d);
 692
 693       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
 694       Iterator asItr = asSet.iterator();
 695       while( asItr.hasNext() ) {
 696         AllocationSite as = (AllocationSite) asItr.next();
 697         if( as.getType().getClassDesc().hasFlags() ) {
 698           asSetTotal.add(as);
 699         }
 700       }
 701
 702       // enqueue callees of this method to be searched for
 703       // allocation sites also
 704       Set callees = callGraph.getCalleeSet(d);
 705       if( callees != null ) {
 706         Iterator methItr = callees.iterator();
 707         while( methItr.hasNext() ) {
 708           MethodDescriptor md = (MethodDescriptor) methItr.next();
 709
 710           if( !visited.contains(md) ) {
 711             toVisit.add(md);
 712           }
 713         }
 714       }
 715     }
 716
 717
 718     return asSetTotal;
 719   }
 720
 721
 722
 723   private HashSet<Integer> getHeapRegionIDset(OwnershipGraph og,
 724                                               int paramIndex) {
 725
 726     assert og.paramIndex2id.containsKey(paramIndex);
 727     Integer idParam = og.paramIndex2id.get(paramIndex);
 728
 729     HashSet<Integer> idSet = new HashSet<Integer>();
 730     idSet.add(idParam);
 731
 732     return idSet;
 733   }
 734
 735
 736   private HashSet<Integer> getHeapRegionIDset(AllocationSite alloc) {
 737
 738     HashSet<Integer> idSet = new HashSet<Integer>();
 739
 740     for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 741       Integer id = alloc.getIthOldest(i);
 742       idSet.add(id);
 743     }
 744
 745     Integer idSummary = alloc.getSummary();
 746     idSet.add(idSummary);
 747
 748     return idSet;
 749   }
 750
 751   private HashSet<Integer> getHeapRegionIDset(HashSet<AllocationSite> allocSet) {
 752
 753     HashSet<Integer> idSet = new HashSet<Integer>();
 754
 755     Iterator allocItr = allocSet.iterator();
 756     while( allocItr.hasNext() ) {
 757       AllocationSite alloc = (AllocationSite) allocItr.next();
 758
 759       for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 760         Integer id = alloc.getIthOldest(i);
 761         idSet.add(id);
 762       }
 763
 764       Integer idSummary = alloc.getSummary();
 765       idSet.add(idSummary);
 766     }
 767
 768     return idSet;
 769   }
 770
 771   private boolean createsPotentialAliases(OwnershipGraph og,
 772                                           HashSet<Integer> idSetA,
 773                                           HashSet<Integer> idSetB) {
 774     boolean potentialAlias = false;
 775
 776     /*
 777        // first expand set B into the set of all heap region node ID's
 778        // reachable from the nodes in set B
 779        HashSet<Integer> idSetReachableFromB = og.getReachableSet( idSetB );
 780
 781        // then see if anything in A can reach a node in the set reachable
 782        // from B.  If so, there is a potential alias.
 783        Iterator i = idSetA.iterator();
 784        while( i.hasNext() ) {
 785         Integer id = (Integer) i.next();
 786         if( og.canIdReachSet( id, idSetB ) ) {
 787             return true;
 788         }
 789        }
 790      */
 791
 792     return false;
 793   }
 794 }