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   static private int uniqueIDcount = 0;
 170
 171
 172   // Use these data structures to track progress of
 173   // processing all methods in the program, and by methods
 174   // TaskDescriptor and MethodDescriptor are combined
 175   // together, with a common parent class Descriptor
 176   private HashSet  <Descriptor>                           descriptorsToVisit;
 177   private Hashtable<Descriptor, OwnershipGraph>           mapDescriptorToCompleteOwnershipGraph;
 178   private Hashtable<FlatNew,    AllocationSite>           mapFlatNewToAllocationSite;
 179   private Hashtable<Descriptor, HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
 180
 181   // Use these data structures to track progress of one pass of
 182   // processing the FlatNodes of a particular method
 183   private HashSet  <FlatNode>                 flatNodesToVisit;
 184   private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
 185   private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
 186
 187
 188   // this analysis generates an ownership graph for every task
 189   // in the program
 190   public OwnershipAnalysis(State state,
 191                            CallGraph callGraph,
 192                            int allocationDepth) throws java.io.IOException {
 193     this.state           = state;
 194     this.callGraph       = callGraph;
 195     this.allocationDepth = allocationDepth;
 196
 197     // temporary for debugging
 198     this.allocationDepth = 1;
 199
 200     descriptorsToVisit = new HashSet<Descriptor>();
 201
 202     mapDescriptorToCompleteOwnershipGraph =
 203       new Hashtable<Descriptor, OwnershipGraph>();
 204
 205     mapFlatNewToAllocationSite =
 206       new Hashtable<FlatNew, AllocationSite>();
 207
 208     mapDescriptorToAllocationSiteSet =
 209       new Hashtable<Descriptor, HashSet<AllocationSite> >();
 210
 211     // use this set to prevent infinite recursion when
 212     // traversing the call graph
 213     HashSet<Descriptor> calleesScheduled = new HashSet<Descriptor>();
 214
 215
 216     // initialize methods to visit as the set of all tasks in the
 217     // program and then any method that could be called starting
 218     // from those tasks
 219     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 220     while( taskItr.hasNext() ) {
 221       Descriptor d = (Descriptor) taskItr.next();
 222       descriptorsToVisit.add(d);
 223
 224       // recursively find all callees from this task
 225       scheduleAllCallees(calleesScheduled, d);
 226     }
 227
 228     // before beginning analysis, initialize every scheduled method
 229     // with an ownership graph that has populated parameter index tables
 230     // by analyzing the first node which is always a FlatMethod node
 231     Iterator<Descriptor> dItr = calleesScheduled.iterator();
 232     while( dItr.hasNext() ) {
 233       Descriptor d  = dItr.next();
 234       OwnershipGraph og = new OwnershipGraph(allocationDepth);
 235
 236       FlatMethod fm;
 237       if( d instanceof MethodDescriptor ) {
 238         fm = state.getMethodFlat( (MethodDescriptor) d);
 239       } else {
 240         assert d instanceof TaskDescriptor;
 241         fm = state.getMethodFlat( (TaskDescriptor) d);
 242       }
 243
 244       analyzeFlatNode(d, fm, null, og);
 245       mapDescriptorToCompleteOwnershipGraph.put(d, og);
 246     }
 247
 248     // as mentioned above, analyze methods one-by-one, possibly revisiting
 249     // a method if the methods that it calls are updated
 250     analyzeMethods();
 251   }
 252
 253   // called from the constructor to help initialize the set
 254   // of methods that needs to be analyzed by ownership analysis
 255   private void scheduleAllCallees(HashSet<Descriptor> calleesScheduled,
 256                                   Descriptor d) {
 257     if( calleesScheduled.contains(d) ) {
 258       return;
 259     }
 260     calleesScheduled.add(d);
 261
 262     Set callees = callGraph.getCalleeSet(d);
 263     if( callees == null ) {
 264       return;
 265     }
 266
 267     Iterator methItr = callees.iterator();
 268     while( methItr.hasNext() ) {
 269       MethodDescriptor md = (MethodDescriptor) methItr.next();
 270       descriptorsToVisit.add(md);
 271
 272       // recursively find all callees from this task
 273       scheduleAllCallees(calleesScheduled, md);
 274     }
 275   }
 276
 277
 278   // manage the set of tasks and methods to be analyzed
 279   // and be sure to reschedule tasks/methods when the methods
 280   // they call are updated
 281   private void analyzeMethods() throws java.io.IOException {
 282
 283     while( !descriptorsToVisit.isEmpty() ) {
 284       Descriptor d = (Descriptor) descriptorsToVisit.iterator().next();
 285       descriptorsToVisit.remove(d);
 286
 287       // because the task or method descriptor just extracted
 288       // was in the "to visit" set it either hasn't been analyzed
 289       // yet, or some method that it depends on has been
 290       // updated.  Recompute a complete ownership graph for
 291       // this task/method and compare it to any previous result.
 292       // If there is a change detected, add any methods/tasks
 293       // that depend on this one to the "to visit" set.
 294
 295       System.out.println("Analyzing " + d);
 296
 297       FlatMethod fm;
 298       if( d instanceof MethodDescriptor ) {
 299         fm = state.getMethodFlat( (MethodDescriptor) d);
 300       } else {
 301         assert d instanceof TaskDescriptor;
 302         fm = state.getMethodFlat( (TaskDescriptor) d);
 303       }
 304
 305       OwnershipGraph og     = analyzeFlatMethod(d, fm);
 306       OwnershipGraph ogPrev = mapDescriptorToCompleteOwnershipGraph.get(d);
 307       if( !og.equals(ogPrev) ) {
 308         mapDescriptorToCompleteOwnershipGraph.put(d, og);
 309
 310         /*
 311            boolean writeLabels,
 312            boolean labelSelect,
 313            boolean pruneGarbage,
 314            boolean writeReferencers
 315          */
 316         og.writeGraph(d, true, true, true, false);
 317
 318         // only methods have dependents, tasks cannot
 319         // be invoked by any user program calls
 320         if( d instanceof MethodDescriptor ) {
 321           MethodDescriptor md = (MethodDescriptor) d;
 322           Set dependents = callGraph.getCallerSet(md);
 323           if( dependents != null ) {
 324             descriptorsToVisit.addAll(dependents);
 325           }
 326         }
 327       }
 328     }
 329
 330   }
 331
 332
 333   int x = 0;
 334
 335
 336   // keep passing the Descriptor of the method along for debugging
 337   // and dot file writing
 338   private OwnershipGraph
 339   analyzeFlatMethod(Descriptor mDesc,
 340                     FlatMethod flatm) throws java.io.IOException {
 341
 342     // initialize flat nodes to visit as the flat method
 343     // because all other nodes in this flat method are
 344     // decendents of the flat method itself
 345     flatNodesToVisit = new HashSet<FlatNode>();
 346     flatNodesToVisit.add(flatm);
 347
 348     // initilize the mapping of flat nodes in this flat method to
 349     // ownership graph results to an empty mapping
 350     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 351
 352     // initialize the set of return nodes that will be combined as
 353     // the final ownership graph result to return as an empty set
 354     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 355
 356     while( !flatNodesToVisit.isEmpty() ) {
 357       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 358       flatNodesToVisit.remove(fn);
 359
 360       // perform this node's contributions to the ownership
 361       // graph on a new copy, then compare it to the old graph
 362       // at this node to see if anything was updated.
 363       OwnershipGraph og = new OwnershipGraph(allocationDepth);
 364
 365       // start by merging all node's parents' graphs
 366       for( int i = 0; i < fn.numPrev(); ++i ) {
 367         FlatNode pn       = fn.getPrev(i);
 368         OwnershipGraph ogParent = getGraphFromFlatNode(pn);
 369         og.merge(ogParent);
 370       }
 371
 372       // apply the analysis of the flat node to the
 373       // ownership graph made from the merge of the
 374       // parent graphs
 375       analyzeFlatNode(mDesc,
 376                       fn,
 377                       returnNodesToCombineForCompleteOwnershipGraph,
 378                       og);
 379
 380       // if the results of the new graph are different from
 381       // the current graph at this node, replace the graph
 382       // with the update and enqueue the children for
 383       // processing
 384       OwnershipGraph ogPrev = getGraphFromFlatNode(fn);
 385
 386       if( !og.equals(ogPrev) ) {
 387         setGraphForFlatNode(fn, og);
 388
 389
 390
 391         x++;
 392         if( x > 0 ) {
 393           String s = String.format("debug%04d", x);
 394           //og.writeGraph( s, true, true, true, false );
 395         }
 396
 397
 398
 399         for( int i = 0; i < fn.numNext(); i++ ) {
 400           FlatNode nn = fn.getNext(i);
 401           flatNodesToVisit.add(nn);
 402         }
 403       }
 404     }
 405
 406     // end by merging all return nodes into a complete
 407     // ownership graph that represents all possible heap
 408     // states after the flat method returns
 409     OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth);
 410     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 411     while( retItr.hasNext() ) {
 412       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 413       OwnershipGraph ogr = getGraphFromFlatNode(frn);
 414       completeGraph.merge(ogr);
 415     }
 416     return completeGraph;
 417   }
 418
 419
 420   private void
 421   analyzeFlatNode(Descriptor methodDesc,
 422                   FlatNode fn,
 423                   HashSet<FlatReturnNode> setRetNodes,
 424                   OwnershipGraph og) throws java.io.IOException {
 425
 426     TempDescriptor src;
 427     TempDescriptor dst;
 428     FieldDescriptor fld;
 429
 430     // use node type to decide what alterations to make
 431     // to the ownership graph
 432     switch( fn.kind() ) {
 433
 434     case FKind.FlatMethod:
 435       FlatMethod fm = (FlatMethod) fn;
 436
 437       // there should only be one FlatMethod node as the
 438       // parent of all other FlatNode objects, so take
 439       // the opportunity to construct the initial graph by
 440       // adding parameters labels to new heap regions
 441       for( int i = 0; i < fm.numParameters(); ++i ) {
 442         TempDescriptor tdParam = fm.getParameter(i);
 443         og.assignParameterAllocationToTemp(methodDesc instanceof TaskDescriptor,
 444                                            tdParam,
 445                                            new Integer(i) );
 446       }
 447
 448       break;
 449
 450     case FKind.FlatOpNode:
 451       FlatOpNode fon = (FlatOpNode) fn;
 452       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 453         src = fon.getLeft();
 454         dst = fon.getDest();
 455         og.assignTempYToTempX(src, dst);
 456       }
 457       break;
 458
 459     case FKind.FlatFieldNode:
 460       FlatFieldNode ffn = (FlatFieldNode) fn;
 461       src = ffn.getSrc();
 462       dst = ffn.getDst();
 463       fld = ffn.getField();
 464       if( !fld.getType().isPrimitive() ) {
 465         og.assignTempYFieldFToTempX(src, fld, dst);
 466       }
 467       break;
 468
 469     case FKind.FlatSetFieldNode:
 470       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 471       src = fsfn.getSrc();
 472       dst = fsfn.getDst();
 473       fld = fsfn.getField();
 474       og.assignTempYToTempXFieldF(src, dst, fld);
 475       break;
 476
 477     case FKind.FlatNew:
 478       FlatNew fnn = (FlatNew) fn;
 479       dst = fnn.getDst();
 480       AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 481
 482       og.assignNewAllocationToTempX(dst, as);
 483       break;
 484
 485     case FKind.FlatCall:
 486       FlatCall fc           = (FlatCall) fn;
 487       MethodDescriptor md           = fc.getMethod();
 488       FlatMethod flatm        = state.getMethodFlat(md);
 489       //HashSet<AllocationSite> allocSiteSet = getAllocationSiteSet( md );
 490       OwnershipGraph ogAllPossibleCallees  = new OwnershipGraph(allocationDepth);
 491
 492       if( md.isStatic() ) {
 493         // a static method is simply always the same, makes life easy
 494         OwnershipGraph onlyPossibleCallee = mapDescriptorToCompleteOwnershipGraph.get(md);
 495         ogAllPossibleCallees.merge(onlyPossibleCallee);
 496
 497         /*
 498            if( onlyPossibleCallee != null ) {
 499             onlyPossibleCallee.writeGraph( "only", false, false );
 500             System.out.println( "There was only one possible callee, "+md );
 501            }
 502          */
 503
 504       } else {
 505         // if the method descriptor is virtual, then there could be a
 506         // set of possible methods that will actually be invoked, so
 507         // find all of them and merge all of their graphs together
 508         TypeDescriptor typeDesc        = fc.getThis().getType();
 509         Set possibleCallees = callGraph.getMethods(md, typeDesc);
 510
 511         //int j = 0;
 512
 513         Iterator i = possibleCallees.iterator();
 514         while( i.hasNext() ) {
 515           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 516           //allocSiteSet.addAll( getAllocationSiteSet( possibleMd ) );
 517           OwnershipGraph ogPotentialCallee = mapDescriptorToCompleteOwnershipGraph.get(possibleMd);
 518
 519           /*
 520              if( ogPotentialCallee != null ) {
 521               ogPotentialCallee.writeGraph( "potential"+j, false, false );
 522            ++j;
 523              }
 524            */
 525
 526           ogAllPossibleCallees.merge(ogPotentialCallee);
 527         }
 528
 529         //System.out.println( "There were "+j+" potential callees merged together." );
 530       }
 531
 532       //System.out.println( "AllocationSiteSet has "+allocSiteSet.size()+" items." );
 533
 534       // now we should have the following information to resolve this method call:
 535       //
 536       // 1. A FlatCall fc to query for the caller's context (argument labels, etc)
 537       //
 538       // 2. Whether the method is static; if not we need to deal with the "this" pointer
 539       //
 540       // *******************************************************************************************
 541       // 3. The original FlatMethod flatm to query for callee's context (paramter labels)
 542       //   NOTE!  I assume FlatMethod before virtual dispatch accurately describes all possible methods!
 543       // *******************************************************************************************
 544       //
 545       // 4. The OwnershipGraph ogAllPossibleCallees is a merge of every ownership graph of all the possible
 546       // methods to capture any possible references made.
 547       //
 548       // 5. The Set of AllocationSite objects, allocSiteSet that is the set of allocation sites from
 549       // every possible method we might have chosen
 550       //
 551       og.resolveMethodCall(fc, md.isStatic(), flatm, ogAllPossibleCallees);
 552       break;
 553
 554     case FKind.FlatReturnNode:
 555       FlatReturnNode frn = (FlatReturnNode) fn;
 556       setRetNodes.add(frn);
 557       break;
 558     }
 559   }
 560
 561
 562   // this method should generate integers strictly greater than zero!
 563   // special "shadow" regions are made from a heap region by negating
 564   // the ID
 565   static public Integer generateUniqueHeapRegionNodeID() {
 566     ++uniqueIDcount;
 567     return new Integer(uniqueIDcount);
 568   }
 569
 570
 571   private OwnershipGraph getGraphFromFlatNode(FlatNode fn) {
 572     if( !mapFlatNodeToOwnershipGraph.containsKey(fn) ) {
 573       mapFlatNodeToOwnershipGraph.put(fn, new OwnershipGraph(allocationDepth) );
 574     }
 575
 576     return mapFlatNodeToOwnershipGraph.get(fn);
 577   }
 578
 579   private void setGraphForFlatNode(FlatNode fn, OwnershipGraph og) {
 580     mapFlatNodeToOwnershipGraph.put(fn, og);
 581   }
 582
 583
 584
 585
 586
 587
 588   // return just the allocation site associated with one FlatNew node
 589   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
 590
 591     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
 592       AllocationSite as = new AllocationSite(allocationDepth, fn.getType() );
 593
 594       // the newest nodes are single objects
 595       for( int i = 0; i < allocationDepth; ++i ) {
 596         Integer id = generateUniqueHeapRegionNodeID();
 597         as.setIthOldest(i, id);
 598       }
 599
 600       // the oldest node is a summary node
 601       Integer idSummary = generateUniqueHeapRegionNodeID();
 602       as.setSummary(idSummary);
 603
 604       mapFlatNewToAllocationSite.put(fn, as);
 605     }
 606
 607     return mapFlatNewToAllocationSite.get(fn);
 608   }
 609
 610
 611   // return all allocation sites in the method (there is one allocation
 612   // site per FlatNew node in a method)
 613   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
 614     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
 615       buildAllocationSiteSet(d);
 616     }
 617
 618     return mapDescriptorToAllocationSiteSet.get(d);
 619
 620   }
 621
 622   private void buildAllocationSiteSet(Descriptor d) {
 623     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
 624
 625     FlatMethod fm;
 626     if( d instanceof MethodDescriptor ) {
 627       fm = state.getMethodFlat( (MethodDescriptor) d);
 628     } else {
 629       assert d instanceof TaskDescriptor;
 630       fm = state.getMethodFlat( (TaskDescriptor) d);
 631     }
 632
 633     // visit every node in this FlatMethod's IR graph
 634     // and make a set of the allocation sites from the
 635     // FlatNew node's visited
 636     HashSet<FlatNode> visited = new HashSet<FlatNode>();
 637     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
 638     toVisit.add(fm);
 639
 640     while( !toVisit.isEmpty() ) {
 641       FlatNode n = toVisit.iterator().next();
 642
 643       if( n instanceof FlatNew ) {
 644         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
 645       }
 646
 647       toVisit.remove(n);
 648       visited.add(n);
 649
 650       for( int i = 0; i < n.numNext(); ++i ) {
 651         FlatNode child = n.getNext(i);
 652         if( !visited.contains(child) ) {
 653           toVisit.add(child);
 654         }
 655       }
 656     }
 657
 658     mapDescriptorToAllocationSiteSet.put(d, s);
 659   }
 660
 661
 662   private HashSet<AllocationSite>
 663   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
 664
 665     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
 666     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
 667     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
 668
 669     toVisit.add(td);
 670
 671     // traverse this task and all methods reachable from this task
 672     while( !toVisit.isEmpty() ) {
 673       Descriptor d = toVisit.iterator().next();
 674       toVisit.remove(d);
 675       visited.add(d);
 676
 677       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
 678       Iterator asItr = asSet.iterator();
 679       while( asItr.hasNext() ) {
 680         AllocationSite as = (AllocationSite) asItr.next();
 681         if( as.getType().getClassDesc().hasFlags() ) {
 682           asSetTotal.add(as);
 683         }
 684       }
 685
 686       // enqueue callees of this method to be searched for
 687       // allocation sites also
 688       Set callees = callGraph.getCalleeSet(d);
 689       if( callees != null ) {
 690         Iterator methItr = callees.iterator();
 691         while( methItr.hasNext() ) {
 692           MethodDescriptor md = (MethodDescriptor) methItr.next();
 693
 694           if( !visited.contains(md) ) {
 695             toVisit.add(md);
 696           }
 697         }
 698       }
 699     }
 700
 701
 702     return asSetTotal;
 703   }
 704
 705
 706
 707   private HashSet<Integer> getHeapRegionIDset(OwnershipGraph og,
 708                                               int paramIndex) {
 709
 710     assert og.paramIndex2id.containsKey(paramIndex);
 711     Integer idParam = og.paramIndex2id.get(paramIndex);
 712
 713     HashSet<Integer> idSet = new HashSet<Integer>();
 714     idSet.add(idParam);
 715
 716     return idSet;
 717   }
 718
 719
 720   private HashSet<Integer> getHeapRegionIDset(AllocationSite alloc) {
 721
 722     HashSet<Integer> idSet = new HashSet<Integer>();
 723
 724     for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 725       Integer id = alloc.getIthOldest(i);
 726       idSet.add(id);
 727     }
 728
 729     Integer idSummary = alloc.getSummary();
 730     idSet.add(idSummary);
 731
 732     return idSet;
 733   }
 734
 735   private HashSet<Integer> getHeapRegionIDset(HashSet<AllocationSite> allocSet) {
 736
 737     HashSet<Integer> idSet = new HashSet<Integer>();
 738
 739     Iterator allocItr = allocSet.iterator();
 740     while( allocItr.hasNext() ) {
 741       AllocationSite alloc = (AllocationSite) allocItr.next();
 742
 743       for( int i = 0; i < alloc.getAllocationDepth(); ++i ) {
 744         Integer id = alloc.getIthOldest(i);
 745         idSet.add(id);
 746       }
 747
 748       Integer idSummary = alloc.getSummary();
 749       idSet.add(idSummary);
 750     }
 751
 752     return idSet;
 753   }
 754
 755   private boolean createsPotentialAliases(OwnershipGraph og,
 756                                           HashSet<Integer> idSetA,
 757                                           HashSet<Integer> idSetB) {
 758     boolean potentialAlias = false;
 759
 760     /*
 761        // first expand set B into the set of all heap region node ID's
 762        // reachable from the nodes in set B
 763        HashSet<Integer> idSetReachableFromB = og.getReachableSet( idSetB );
 764
 765        // then see if anything in A can reach a node in the set reachable
 766        // from B.  If so, there is a potential alias.
 767        Iterator i = idSetA.iterator();
 768        while( i.hasNext() ) {
 769         Integer id = (Integer) i.next();
 770         if( og.canIdReachSet( id, idSetB ) ) {
 771             return true;
 772         }
 773        }
 774      */
 775
 776     return false;
 777   }
 778 }