Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java

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