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