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