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