Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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