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