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