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
  31   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  32                                          int paramIndex1,
  33                                          int paramIndex2) {
  34
  35     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  36     assert(og != null);
  37     return og.hasPotentialAlias(paramIndex1, paramIndex2);
  38   }
  39
  40   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  41                                          int paramIndex,
  42                                          AllocationSite alloc) {
  43
  44     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  45     assert(og != null);
  46     return og.hasPotentialAlias(paramIndex, alloc);
  47   }
  48
  49   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  50                                          AllocationSite alloc,
  51                                          int paramIndex) {
  52
  53     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  54     assert(og != null);
  55     return og.hasPotentialAlias(paramIndex, alloc);
  56   }
  57
  58   public Set<HeapRegionNode> createsPotentialAliases(Descriptor taskOrMethod,
  59                                          AllocationSite alloc1,
  60                                          AllocationSite alloc2) {
  61
  62     OwnershipGraph og = getGraphOfAllContextsFromDescriptor(taskOrMethod);
  63     assert(og != null);
  64     return og.hasPotentialAlias(alloc1, alloc2);
  65   }
  66
  67
  68   protected OwnershipGraph getGraphOfAllContextsFromDescriptor(Descriptor d) {
  69     assert d != null;
  70
  71     OwnershipGraph og = new OwnershipGraph( allocationDepth, typeUtil );
  72
  73     assert mapDescriptorToAllMethodContexts.containsKey( d );
  74     HashSet<MethodContext> contexts = mapDescriptorToAllMethodContexts.get( d );
  75     Iterator<MethodContext> mcItr = contexts.iterator();
  76     while( mcItr.hasNext() ) {
  77       MethodContext mc = mcItr.next();
  78
  79       OwnershipGraph ogContext = mapMethodContextToCompleteOwnershipGraph.get(mc);
  80       assert ogContext != null;
  81
  82       og.merge( ogContext );
  83     }
  84
  85     return og;
  86   }
  87
  88
  89   public String prettyPrintNodeSet( Set<HeapRegionNode> s ) {
  90     String out = "{\n";
  91
  92     Iterator<HeapRegionNode> i = s.iterator();
  93     while( i.hasNext() ) {
  94       HeapRegionNode n = i.next();
  95
  96       AllocationSite as = n.getAllocationSite();
  97       if( as == null ) {
  98         out += "  "+n.toString()+",\n";
  99       } else {
 100         out += "  "+n.toString()+": "+as.toStringVerbose()+",\n";
 101       }
 102     }
 103
 104     out += "}\n";
 105     return out;
 106   }
 107
 108
 109   // use the methods given above to check every possible alias
 110   // between task parameters and flagged allocation sites reachable
 111   // from the task
 112   public void writeAllAliases(String outputFile, String timeReport) throws java.io.IOException {
 113
 114     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
 115
 116     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
 117     bw.write(timeReport+"\n");
 118
 119     // look through every task for potential aliases
 120     Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 121     while( taskItr.hasNext() ) {
 122       TaskDescriptor td = (TaskDescriptor) taskItr.next();
 123
 124       bw.write("\n---------"+td+"--------\n");
 125
 126       HashSet<AllocationSite> allocSites = getFlaggedAllocationSitesReachableFromTask(td);
 127
 128       Set<HeapRegionNode> common;
 129
 130       // for each task parameter, check for aliases with
 131       // other task parameters and every allocation site
 132       // reachable from this task
 133       boolean foundSomeAlias = false;
 134
 135       FlatMethod fm = state.getMethodFlat(td);
 136       for( int i = 0; i < fm.numParameters(); ++i ) {
 137
 138         // for the ith parameter check for aliases to all
 139         // higher numbered parameters
 140         for( int j = i + 1; j < fm.numParameters(); ++j ) {
 141           common = createsPotentialAliases(td, i, j);
 142           if( !common.isEmpty() ) {
 143             foundSomeAlias = true;
 144             bw.write("Potential alias between parameters "+i+" and "+j+".\n");
 145             bw.write(prettyPrintNodeSet( common )+"\n" );
 146           }
 147         }
 148
 149         // for the ith parameter, check for aliases against
 150         // the set of allocation sites reachable from this
 151         // task context
 152         Iterator allocItr = allocSites.iterator();
 153         while( allocItr.hasNext() ) {
 154           AllocationSite as = (AllocationSite) allocItr.next();
 155           common = createsPotentialAliases(td, i, as);
 156           if( !common.isEmpty() ) {
 157             foundSomeAlias = true;
 158             bw.write("Potential alias between parameter "+i+" and "+as.getFlatNew()+".\n");
 159             bw.write(prettyPrintNodeSet( common )+"\n" );
 160           }
 161         }
 162       }
 163
 164       // for each allocation site check for aliases with
 165       // other allocation sites in the context of execution
 166       // of this task
 167       HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
 168       Iterator allocItr1 = allocSites.iterator();
 169       while( allocItr1.hasNext() ) {
 170         AllocationSite as1 = (AllocationSite) allocItr1.next();
 171
 172         Iterator allocItr2 = allocSites.iterator();
 173         while( allocItr2.hasNext() ) {
 174           AllocationSite as2 = (AllocationSite) allocItr2.next();
 175
 176           if( !outerChecked.contains(as2) ) {
 177             common = createsPotentialAliases(td, as1, as2);
 178
 179             if( !common.isEmpty() ) {
 180               foundSomeAlias = true;
 181               bw.write("Potential alias between "+as1.getFlatNew()+" and "+as2.getFlatNew()+".\n");
 182               bw.write(prettyPrintNodeSet( common )+"\n" );
 183             }
 184           }
 185         }
 186
 187         outerChecked.add(as1);
 188       }
 189
 190       if( !foundSomeAlias ) {
 191         bw.write("No aliases between flagged objects in Task "+td+".\n");
 192       }
 193     }
 194
 195     bw.write( "\n"+computeAliasContextHistogram() );
 196     bw.close();
 197   }
 198
 199
 200   // this version of writeAllAliases is for Java programs that have no tasks
 201   public void writeAllAliasesJava(String outputFile, String timeReport) throws java.io.IOException {
 202     assert !state.TASK;
 203
 204     BufferedWriter bw = new BufferedWriter(new FileWriter(outputFile) );
 205
 206     bw.write("Conducting ownership analysis with allocation depth = "+allocationDepth+"\n");
 207     bw.write(timeReport+"\n\n");
 208
 209     boolean foundSomeAlias = false;
 210
 211     Descriptor d = typeUtil.getMain();
 212     HashSet<AllocationSite> allocSites = getFlaggedAllocationSites(d);
 213
 214     // for each allocation site check for aliases with
 215     // other allocation sites in the context of execution
 216     // of this task
 217     HashSet<AllocationSite> outerChecked = new HashSet<AllocationSite>();
 218     Iterator allocItr1 = allocSites.iterator();
 219     while( allocItr1.hasNext() ) {
 220       AllocationSite as1 = (AllocationSite) allocItr1.next();
 221
 222       Iterator allocItr2 = allocSites.iterator();
 223       while( allocItr2.hasNext() ) {
 224         AllocationSite as2 = (AllocationSite) allocItr2.next();
 225
 226         if( !outerChecked.contains(as2) ) {
 227           Set<HeapRegionNode> common = createsPotentialAliases(d, as1, as2);
 228
 229           if( !common.isEmpty() ) {
 230             foundSomeAlias = true;
 231             bw.write("Potential alias between "+as1.getDisjointId()+" and "+as2.getDisjointId()+".\n");
 232             bw.write( prettyPrintNodeSet( common )+"\n" );
 233           }
 234         }
 235       }
 236
 237       outerChecked.add(as1);
 238     }
 239
 240     if( !foundSomeAlias ) {
 241       bw.write("No aliases between flagged objects found.\n");
 242     }
 243
 244     bw.write( "\n"+computeAliasContextHistogram() );
 245     bw.close();
 246   }
 247   ///////////////////////////////////////////
 248   //
 249   // end public interface
 250   //
 251   ///////////////////////////////////////////
 252
 253
 254
 255
 256
 257
 258
 259
 260   // data from the compiler
 261   private State state;
 262   private TypeUtil typeUtil;
 263   private CallGraph callGraph;
 264   private int allocationDepth;
 265
 266   // used to identify HeapRegionNode objects
 267   // A unique ID equates an object in one
 268   // ownership graph with an object in another
 269   // graph that logically represents the same
 270   // heap region
 271   // start at 10 and increment to leave some
 272   // reserved IDs for special purposes
 273   static private int uniqueIDcount = 10;
 274
 275
 276   // Use these data structures to track progress of
 277   // processing all methods in the program, and by methods
 278   // TaskDescriptor and MethodDescriptor are combined
 279   // together, with a common parent class Descriptor
 280   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToInitialParamAllocGraph;
 281   private Hashtable<MethodContext, OwnershipGraph>           mapMethodContextToCompleteOwnershipGraph;
 282   private Hashtable<FlatNew,       AllocationSite>           mapFlatNewToAllocationSite;
 283   private Hashtable<Descriptor,    HashSet<AllocationSite> > mapDescriptorToAllocationSiteSet;
 284   private Hashtable<MethodContext, Integer>                  mapMethodContextToNumUpdates;
 285   private Hashtable<Descriptor,    HashSet<MethodContext> >  mapDescriptorToAllMethodContexts;
 286   private Hashtable<MethodContext, HashSet<MethodContext> >  mapMethodContextToDependentContexts;
 287
 288   // Use these data structures to track progress of one pass of
 289   // processing the FlatNodes of a particular method
 290   private HashSet  <FlatNode>                 flatNodesToVisit;
 291   private Hashtable<FlatNode, OwnershipGraph> mapFlatNodeToOwnershipGraph;
 292   private HashSet  <FlatReturnNode>           returnNodesToCombineForCompleteOwnershipGraph;
 293
 294   // descriptorsToAnalyze identifies the set of tasks and methods
 295   // that are reachable from the program tasks, this set is initialized
 296   // and then remains static
 297   private HashSet<Descriptor> descriptorsToAnalyze;
 298
 299   // descriptorsToVisit is initialized to descriptorsToAnalyze and is
 300   // reduced by visiting a descriptor during analysis.  When dependents
 301   // must be scheduled, only those contained in descriptorsToAnalyze
 302   // should be re-added to this queue
 303   private PriorityQueue<MethodContextQWrapper> methodContextsToVisitQ;
 304   private Set          <MethodContext>         methodContextsToVisitSet;
 305   private Hashtable<Descriptor, Integer> mapDescriptorToPriority;
 306
 307
 308   // special field descriptors for array elements
 309   public static final String arrayElementFieldName = "___element_";
 310   private static Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField =
 311     new Hashtable<TypeDescriptor, FieldDescriptor>();
 312
 313
 314   // a special temp descriptor for setting more than one parameter label
 315   // to the all-aliased-parameters heap region node
 316   protected static TempDescriptor tdAliasedParams = new TempDescriptor("_AllAliasedParams___");
 317
 318
 319   // for controlling DOT file output
 320   private boolean writeDOTs;
 321   private boolean writeAllDOTs;
 322
 323
 324
 325   // this analysis generates an ownership graph for every task
 326   // in the program
 327   public OwnershipAnalysis(State state,
 328                            TypeUtil tu,
 329                            CallGraph callGraph,
 330                            int allocationDepth,
 331                            boolean writeDOTs,
 332                            boolean writeAllDOTs,
 333                            String aliasFile) throws java.io.IOException {
 334
 335     double timeStartAnalysis = (double) System.nanoTime();
 336
 337     this.state           = state;
 338     this.typeUtil        = tu;
 339     this.callGraph       = callGraph;
 340     this.allocationDepth = allocationDepth;
 341     this.writeDOTs       = writeDOTs;
 342     this.writeAllDOTs    = writeAllDOTs;
 343
 344     descriptorsToAnalyze = new HashSet<Descriptor>();
 345
 346     mapMethodContextToInitialParamAllocGraph =
 347       new Hashtable<MethodContext, OwnershipGraph>();
 348
 349     mapMethodContextToCompleteOwnershipGraph =
 350       new Hashtable<MethodContext, OwnershipGraph>();
 351
 352     mapFlatNewToAllocationSite =
 353       new Hashtable<FlatNew, AllocationSite>();
 354
 355     mapDescriptorToAllocationSiteSet =
 356       new Hashtable<Descriptor, HashSet<AllocationSite> >();
 357
 358     mapDescriptorToAllMethodContexts =
 359       new Hashtable<Descriptor, HashSet<MethodContext> >();
 360
 361     mapMethodContextToDependentContexts =
 362       new Hashtable<MethodContext, HashSet<MethodContext> >();
 363
 364     mapDescriptorToPriority =
 365       new Hashtable<Descriptor, Integer>();
 366
 367
 368     if( writeAllDOTs ) {
 369       mapMethodContextToNumUpdates = new Hashtable<MethodContext, Integer>();
 370     }
 371
 372
 373     if( state.TASK ) {
 374       // initialize methods to visit as the set of all tasks in the
 375       // program and then any method that could be called starting
 376       // from those tasks
 377       Iterator taskItr = state.getTaskSymbolTable().getDescriptorsIterator();
 378       while( taskItr.hasNext() ) {
 379         Descriptor d = (Descriptor) taskItr.next();
 380         scheduleAllCallees(d);
 381       }
 382
 383     } else {
 384       // we are not in task mode, just normal Java, so start with
 385       // the main method
 386       Descriptor d = typeUtil.getMain();
 387       scheduleAllCallees(d);
 388     }
 389
 390
 391     // before beginning analysis, initialize every scheduled method
 392     // with an ownership graph that has populated parameter index tables
 393     // by analyzing the first node which is always a FlatMethod node
 394     Iterator<Descriptor> dItr = descriptorsToAnalyze.iterator();
 395     while( dItr.hasNext() ) {
 396       Descriptor d  = dItr.next();
 397       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 398
 399       FlatMethod fm;
 400       if( d instanceof MethodDescriptor ) {
 401         fm = state.getMethodFlat( (MethodDescriptor) d);
 402       } else {
 403         assert d instanceof TaskDescriptor;
 404         fm = state.getMethodFlat( (TaskDescriptor) d);
 405       }
 406
 407       MethodContext mc = new MethodContext( d );
 408       assert !mapDescriptorToAllMethodContexts.containsKey( d );
 409       HashSet<MethodContext> s = new HashSet<MethodContext>();
 410       s.add( mc );
 411       mapDescriptorToAllMethodContexts.put( d, s );
 412
 413       og = analyzeFlatNode(mc, fm, null, og);
 414       setGraphForMethodContext(mc, og);
 415     }
 416
 417     // as mentioned above, analyze methods one-by-one, possibly revisiting
 418     // a method if the methods that it calls are updated
 419     analyzeMethods();
 420
 421     double timeEndAnalysis = (double) System.nanoTime();
 422     double dt = (timeEndAnalysis - timeStartAnalysis)/(Math.pow( 10.0, 9.0 ) );
 423     String treport = String.format( "The analysis took %.3f sec.", dt );
 424     System.out.println( treport );
 425
 426     if( writeDOTs && !writeAllDOTs ) {
 427       writeFinalContextGraphs();
 428     }
 429
 430     if( aliasFile != null ) {
 431       if( state.TASK ) {
 432         writeAllAliases(aliasFile, treport);
 433       } else {
 434         writeAllAliasesJava(aliasFile, treport);
 435       }
 436     }
 437   }
 438
 439   // called from the constructor to help initialize the set
 440   // of methods that needs to be analyzed by ownership analysis
 441   private void scheduleAllCallees(Descriptor d) {
 442     if( descriptorsToAnalyze.contains(d) ) {
 443       return;
 444     }
 445     descriptorsToAnalyze.add(d);
 446
 447     // start with all method calls to further schedule
 448     Set moreMethodsToCheck = moreMethodsToCheck = callGraph.getMethodCalls(d);
 449
 450     if( d instanceof MethodDescriptor ) {
 451       // see if this method has virtual dispatch
 452       Set virtualMethods = callGraph.getMethods( (MethodDescriptor)d);
 453       moreMethodsToCheck.addAll(virtualMethods);
 454     }
 455
 456     // keep following any further methods identified in
 457     // the call chain
 458     Iterator methItr = moreMethodsToCheck.iterator();
 459     while( methItr.hasNext() ) {
 460       Descriptor m = (Descriptor) methItr.next();
 461       scheduleAllCallees(m);
 462     }
 463   }
 464
 465
 466   // manage the set of tasks and methods to be analyzed
 467   // and be sure to reschedule tasks/methods when the methods
 468   // they call are updated
 469   private void analyzeMethods() throws java.io.IOException {
 470
 471     // first gather all of the method contexts to analyze
 472     HashSet<MethodContext> allContexts = new HashSet<MethodContext>();
 473     Iterator<Descriptor> itrd2a = descriptorsToAnalyze.iterator();
 474     while( itrd2a.hasNext() ) {
 475       HashSet<MethodContext> mcs = mapDescriptorToAllMethodContexts.get( itrd2a.next() );
 476       assert mcs != null;
 477
 478       Iterator<MethodContext> itrmc = mcs.iterator();
 479       while( itrmc.hasNext() ) {
 480         allContexts.add( itrmc.next() );
 481       }
 482     }
 483
 484     // topologically sort them according to the caller graph so leaf calls are
 485     // ordered first; use that ordering to give method contexts priorities
 486     LinkedList<MethodContext> sortedMethodContexts = topologicalSort( allContexts );
 487
 488     methodContextsToVisitQ   = new PriorityQueue<MethodContextQWrapper>();
 489     methodContextsToVisitSet = new HashSet<MethodContext>();
 490
 491     int p = 0;
 492     Iterator<MethodContext> mcItr = sortedMethodContexts.iterator();
 493     while( mcItr.hasNext() ) {
 494       MethodContext mc = mcItr.next();
 495       mapDescriptorToPriority.put( mc.getDescriptor(), new Integer( p ) );
 496       methodContextsToVisitQ.add( new MethodContextQWrapper( p, mc ) );
 497       methodContextsToVisitSet.add( mc );
 498       ++p;
 499     }
 500
 501     // analyze methods from the priority queue until it is empty
 502     while( !methodContextsToVisitQ.isEmpty() ) {
 503       MethodContext mc = methodContextsToVisitQ.poll().getMethodContext();
 504       assert methodContextsToVisitSet.contains( mc );
 505       methodContextsToVisitSet.remove( mc );
 506
 507       // because the task or method descriptor just extracted
 508       // was in the "to visit" set it either hasn't been analyzed
 509       // yet, or some method that it depends on has been
 510       // updated.  Recompute a complete ownership graph for
 511       // this task/method and compare it to any previous result.
 512       // If there is a change detected, add any methods/tasks
 513       // that depend on this one to the "to visit" set.
 514
 515       System.out.println("Analyzing " + mc);
 516
 517       Descriptor d = mc.getDescriptor();
 518       FlatMethod fm;
 519       if( d instanceof MethodDescriptor ) {
 520         fm = state.getMethodFlat( (MethodDescriptor) d);
 521       } else {
 522         assert d instanceof TaskDescriptor;
 523         fm = state.getMethodFlat( (TaskDescriptor) d);
 524       }
 525
 526       OwnershipGraph og = analyzeFlatMethod(mc, fm);
 527       OwnershipGraph ogPrev = mapMethodContextToCompleteOwnershipGraph.get(mc);
 528       if( !og.equals(ogPrev) ) {
 529         setGraphForMethodContext(mc, og);
 530
 531         Iterator<MethodContext> depsItr = iteratorDependents( mc );
 532         while( depsItr.hasNext() ) {
 533           MethodContext mcNext = depsItr.next();
 534
 535           if( !methodContextsToVisitSet.contains( mcNext ) ) {
 536             //System.out.println( "  queuing "+mcNext );
 537             methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( mcNext.getDescriptor() ),
 538                                                                    mcNext ) );
 539             methodContextsToVisitSet.add( mcNext );
 540           }
 541         }
 542       }
 543     }
 544
 545   }
 546
 547
 548   // keep passing the Descriptor of the method along for debugging
 549   // and dot file writing
 550   private OwnershipGraph
 551   analyzeFlatMethod(MethodContext mc,
 552                     FlatMethod flatm) throws java.io.IOException {
 553
 554     // initialize flat nodes to visit as the flat method
 555     // because it is the entry point
 556
 557     flatNodesToVisit = new HashSet<FlatNode>();
 558     flatNodesToVisit.add(flatm);
 559
 560     // initilize the mapping of flat nodes in this flat method to
 561     // ownership graph results to an empty mapping
 562     mapFlatNodeToOwnershipGraph = new Hashtable<FlatNode, OwnershipGraph>();
 563
 564     // initialize the set of return nodes that will be combined as
 565     // the final ownership graph result to return as an empty set
 566     returnNodesToCombineForCompleteOwnershipGraph = new HashSet<FlatReturnNode>();
 567
 568
 569     while( !flatNodesToVisit.isEmpty() ) {
 570       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 571       flatNodesToVisit.remove(fn);
 572
 573       //System.out.println( "  "+fn );
 574
 575       // perform this node's contributions to the ownership
 576       // graph on a new copy, then compare it to the old graph
 577       // at this node to see if anything was updated.
 578       OwnershipGraph og = new OwnershipGraph(allocationDepth, typeUtil);
 579
 580       // start by merging all node's parents' graphs
 581       for( int i = 0; i < fn.numPrev(); ++i ) {
 582         FlatNode pn = fn.getPrev(i);
 583         if( mapFlatNodeToOwnershipGraph.containsKey(pn) ) {
 584           OwnershipGraph ogParent = mapFlatNodeToOwnershipGraph.get(pn);
 585           og.merge(ogParent);
 586         }
 587       }
 588
 589       // apply the analysis of the flat node to the
 590       // ownership graph made from the merge of the
 591       // parent graphs
 592       og = analyzeFlatNode(mc,
 593                            fn,
 594                            returnNodesToCombineForCompleteOwnershipGraph,
 595                            og);
 596
 597
 598
 599
 600       if( takeDebugSnapshots &&
 601           mc.getDescriptor().getSymbol().equals( mcDescSymbolDebug ) ) {
 602         debugSnapshot(og,fn);
 603       }
 604
 605
 606
 607       // if the results of the new graph are different from
 608       // the current graph at this node, replace the graph
 609       // with the update and enqueue the children for
 610       // processing
 611       OwnershipGraph ogPrev = mapFlatNodeToOwnershipGraph.get(fn);
 612       if( !og.equals(ogPrev) ) {
 613         mapFlatNodeToOwnershipGraph.put(fn, og);
 614
 615         for( int i = 0; i < fn.numNext(); i++ ) {
 616           FlatNode nn = fn.getNext(i);
 617           flatNodesToVisit.add(nn);
 618         }
 619       }
 620     }
 621
 622     // end by merging all return nodes into a complete
 623     // ownership graph that represents all possible heap
 624     // states after the flat method returns
 625     OwnershipGraph completeGraph = new OwnershipGraph(allocationDepth, typeUtil);
 626     Iterator retItr = returnNodesToCombineForCompleteOwnershipGraph.iterator();
 627     while( retItr.hasNext() ) {
 628       FlatReturnNode frn = (FlatReturnNode) retItr.next();
 629       assert mapFlatNodeToOwnershipGraph.containsKey(frn);
 630       OwnershipGraph ogr = mapFlatNodeToOwnershipGraph.get(frn);
 631       completeGraph.merge(ogr);
 632     }
 633
 634     return completeGraph;
 635   }
 636
 637
 638   private OwnershipGraph
 639   analyzeFlatNode(MethodContext mc,
 640                   FlatNode fn,
 641                   HashSet<FlatReturnNode> setRetNodes,
 642                   OwnershipGraph og) throws java.io.IOException {
 643
 644     TempDescriptor lhs;
 645     TempDescriptor rhs;
 646     FieldDescriptor fld;
 647
 648     // use node type to decide what alterations to make
 649     // to the ownership graph
 650     switch( fn.kind() ) {
 651
 652     case FKind.FlatMethod:
 653       FlatMethod fm = (FlatMethod) fn;
 654
 655       // there should only be one FlatMethod node as the
 656       // parent of all other FlatNode objects, so take
 657       // the opportunity to construct the initial graph by
 658       // adding parameters labels to new heap regions
 659       // AND this should be done once globally so that the
 660       // parameter IDs are consistent between analysis
 661       // iterations, so if this step has been done already
 662       // just merge in the cached version
 663       OwnershipGraph ogInitParamAlloc = mapMethodContextToInitialParamAllocGraph.get(mc);
 664       if( ogInitParamAlloc == null ) {
 665
 666         // if the method context has aliased parameters, make sure
 667         // there is a blob region for all those param labels to
 668         // reference
 669         Set<Integer> aliasedParamIndices = mc.getAliasedParamIndices();
 670         boolean aliasedPiIsSuperOfPj = false;
 671         if( !aliasedParamIndices.isEmpty() ) {
 672           og.makeAliasedParamHeapRegionNode( tdAliasedParams );
 673
 674           // if one parameter type is a super class of any other
 675           // then we cannot separate the primary parameter objects
 676           // from the alias blob, so look for it
 677           boolean keepLooking = true;
 678
 679           Iterator<Integer> apItrI = aliasedParamIndices.iterator();
 680           while( apItrI.hasNext() && keepLooking ) {
 681             Integer i = apItrI.next();
 682
 683             Iterator<Integer> apItrJ = aliasedParamIndices.iterator();
 684             while( apItrJ.hasNext() ) {
 685               Integer j = apItrJ.next();
 686
 687               if( !i.equals( j ) ) {
 688                 TypeDescriptor typeI = fm.getParameter( i ).getType();
 689                 TypeDescriptor typeJ = fm.getParameter( j ).getType();
 690
 691                 if( typeUtil.isSuperorType( typeI, typeJ ) ||
 692                     typeUtil.isSuperorType( typeJ, typeI )    ) {
 693
 694                   aliasedPiIsSuperOfPj = true;
 695                   keepLooking = false;
 696                   break;
 697                 }
 698               }
 699             }
 700           }
 701         }
 702
 703         // set up each parameter
 704         for( int i = 0; i < fm.numParameters(); ++i ) {
 705           TempDescriptor tdParam    = fm.getParameter( i );
 706           TypeDescriptor typeParam  = tdParam.getType();
 707           Integer        paramIndex = new Integer( i );
 708
 709           if( typeParam.isImmutable() && !typeParam.isArray() ) {
 710             // don't bother with this primitive parameter, it
 711             // cannot affect reachability
 712             continue;
 713           }
 714
 715           if( aliasedParamIndices.contains( paramIndex ) ) {
 716             // use the alias blob but give parameters their
 717             // own primary obj region if they are not super
 718             // classes of one another
 719             og.assignTempEqualToAliasedParam( tdParam,
 720                                               tdAliasedParams,
 721                                               paramIndex,
 722                                               aliasedPiIsSuperOfPj );
 723           } else {
 724             // this parameter is not aliased to others, give it
 725             // a fresh parameter heap region
 726             og.assignTempEqualToParamAlloc( tdParam,
 727                                             mc.getDescriptor() instanceof TaskDescriptor,
 728                                             paramIndex );
 729           }
 730         }
 731
 732         // clean up reachability on initial parameter shapes
 733         og.globalSweep();
 734
 735         // cache the graph
 736         OwnershipGraph ogResult = new OwnershipGraph(allocationDepth, typeUtil);
 737         ogResult.merge(og);
 738         mapMethodContextToInitialParamAllocGraph.put(mc, ogResult);
 739
 740       } else {
 741         // or just leverage the cached copy
 742         og.merge(ogInitParamAlloc);
 743       }
 744       break;
 745
 746     case FKind.FlatOpNode:
 747       FlatOpNode fon = (FlatOpNode) fn;
 748       if( fon.getOp().getOp() == Operation.ASSIGN ) {
 749         lhs = fon.getDest();
 750         rhs = fon.getLeft();
 751         og.assignTempXEqualToTempY(lhs, rhs);
 752       }
 753       break;
 754
 755     case FKind.FlatCastNode:
 756       FlatCastNode fcn = (FlatCastNode) fn;
 757       lhs = fcn.getDst();
 758       rhs = fcn.getSrc();
 759
 760       TypeDescriptor td = fcn.getType();
 761       assert td != null;
 762
 763       og.assignTypedTempXEqualToTempY(lhs, rhs, td);
 764       break;
 765
 766     case FKind.FlatFieldNode:
 767       FlatFieldNode ffn = (FlatFieldNode) fn;
 768       lhs = ffn.getDst();
 769       rhs = ffn.getSrc();
 770       fld = ffn.getField();
 771       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 772         og.assignTempXEqualToTempYFieldF(lhs, rhs, fld);
 773       }
 774       break;
 775
 776     case FKind.FlatSetFieldNode:
 777       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 778       lhs = fsfn.getDst();
 779       fld = fsfn.getField();
 780       rhs = fsfn.getSrc();
 781       if( !fld.getType().isImmutable() || fld.getType().isArray() ) {
 782         og.assignTempXFieldFEqualToTempY(lhs, fld, rhs);
 783       }
 784       break;
 785
 786     case FKind.FlatElementNode:
 787       FlatElementNode fen = (FlatElementNode) fn;
 788       lhs = fen.getDst();
 789       rhs = fen.getSrc();
 790       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 791
 792         assert rhs.getType() != null;
 793         assert rhs.getType().isArray();
 794
 795         TypeDescriptor  tdElement = rhs.getType().dereference();
 796         FieldDescriptor fdElement = getArrayField( tdElement );
 797
 798         og.assignTempXEqualToTempYFieldF(lhs, rhs, fdElement);
 799       }
 800       break;
 801
 802     case FKind.FlatSetElementNode:
 803       FlatSetElementNode fsen = (FlatSetElementNode) fn;
 804       lhs = fsen.getDst();
 805       rhs = fsen.getSrc();
 806       if( !rhs.getType().isImmutable() || rhs.getType().isArray() ) {
 807
 808         assert lhs.getType() != null;
 809         assert lhs.getType().isArray();
 810
 811         TypeDescriptor  tdElement = lhs.getType().dereference();
 812         FieldDescriptor fdElement = getArrayField( tdElement );
 813
 814         og.assignTempXFieldFEqualToTempY(lhs, fdElement, rhs);
 815       }
 816       break;
 817
 818     case FKind.FlatNew:
 819       FlatNew fnn = (FlatNew) fn;
 820       lhs = fnn.getDst();
 821       if( !lhs.getType().isImmutable() || lhs.getType().isArray() ) {
 822         AllocationSite as = getAllocationSiteFromFlatNewPRIVATE(fnn);
 823         og.assignTempEqualToNewAlloc(lhs, as);
 824       }
 825       break;
 826
 827     case FKind.FlatCall:
 828       FlatCall fc = (FlatCall) fn;
 829       MethodDescriptor md = fc.getMethod();
 830       FlatMethod flatm = state.getMethodFlat(md);
 831       OwnershipGraph ogMergeOfAllPossibleCalleeResults = new OwnershipGraph(allocationDepth, typeUtil);
 832
 833       if( md.isStatic() ) {
 834         // a static method is simply always the same, makes life easy
 835         ogMergeOfAllPossibleCalleeResults = og;
 836
 837         Set<Integer> aliasedParamIndices =
 838           ogMergeOfAllPossibleCalleeResults.calculateAliasedParamSet(fc, md.isStatic(), flatm);
 839
 840         MethodContext mcNew = new MethodContext( md, aliasedParamIndices );
 841         Set contexts = mapDescriptorToAllMethodContexts.get( md );
 842         assert contexts != null;
 843         contexts.add( mcNew );
 844
 845         addDependent( mc, mcNew );
 846
 847         OwnershipGraph onlyPossibleCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 848
 849         if( onlyPossibleCallee == null ) {
 850           // if this method context has never been analyzed just schedule it for analysis
 851           // and skip over this call site for now
 852           if( !methodContextsToVisitSet.contains( mcNew ) ) {
 853             methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
 854                                                                    mcNew ) );
 855             methodContextsToVisitSet.add( mcNew );
 856           }
 857
 858         } else {
 859           ogMergeOfAllPossibleCalleeResults.resolveMethodCall(fc, md.isStatic(), flatm, onlyPossibleCallee, mc);
 860         }
 861
 862       } else {
 863         // if the method descriptor is virtual, then there could be a
 864         // set of possible methods that will actually be invoked, so
 865         // find all of them and merge all of their results together
 866         TypeDescriptor typeDesc = fc.getThis().getType();
 867         Set possibleCallees = callGraph.getMethods(md, typeDesc);
 868
 869         Iterator i = possibleCallees.iterator();
 870         while( i.hasNext() ) {
 871           MethodDescriptor possibleMd = (MethodDescriptor) i.next();
 872           FlatMethod pflatm = state.getMethodFlat(possibleMd);
 873
 874           // don't alter the working graph (og) until we compute a result for every
 875           // possible callee, merge them all together, then set og to that
 876           OwnershipGraph ogCopy = new OwnershipGraph(allocationDepth, typeUtil);
 877           ogCopy.merge(og);
 878
 879           Set<Integer> aliasedParamIndices =
 880             ogCopy.calculateAliasedParamSet(fc, possibleMd.isStatic(), pflatm);
 881
 882           MethodContext mcNew = new MethodContext( possibleMd, aliasedParamIndices );
 883           Set contexts = mapDescriptorToAllMethodContexts.get( md );
 884           assert contexts != null;
 885           contexts.add( mcNew );
 886
 887           addDependent( mc, mcNew );
 888
 889           OwnershipGraph ogPotentialCallee = mapMethodContextToCompleteOwnershipGraph.get( mcNew );
 890
 891           if( ogPotentialCallee == null ) {
 892             // if this method context has never been analyzed just schedule it for analysis
 893             // and skip over this call site for now
 894             if( !methodContextsToVisitSet.contains( mcNew ) ) {
 895               methodContextsToVisitQ.add( new MethodContextQWrapper( mapDescriptorToPriority.get( md ),
 896                                                                      mcNew ) );
 897               methodContextsToVisitSet.add( mcNew );
 898             }
 899
 900           } else {
 901             ogCopy.resolveMethodCall(fc, possibleMd.isStatic(), pflatm, ogPotentialCallee, mc);
 902           }
 903
 904           ogMergeOfAllPossibleCalleeResults.merge(ogCopy);
 905         }
 906       }
 907
 908       og = ogMergeOfAllPossibleCalleeResults;
 909       break;
 910
 911     case FKind.FlatReturnNode:
 912       FlatReturnNode frn = (FlatReturnNode) fn;
 913       rhs = frn.getReturnTemp();
 914       if( rhs != null && !rhs.getType().isImmutable() ) {
 915         og.assignReturnEqualToTemp(rhs);
 916       }
 917       setRetNodes.add(frn);
 918       break;
 919     }
 920
 921     return og;
 922   }
 923
 924
 925   // this method should generate integers strictly greater than zero!
 926   // special "shadow" regions are made from a heap region by negating
 927   // the ID
 928   static public Integer generateUniqueHeapRegionNodeID() {
 929     ++uniqueIDcount;
 930     return new Integer(uniqueIDcount);
 931   }
 932
 933
 934   static public FieldDescriptor getArrayField( TypeDescriptor tdElement ) {
 935     FieldDescriptor fdElement = mapTypeToArrayField.get( tdElement );
 936     if( fdElement == null ) {
 937       fdElement = new FieldDescriptor(new Modifiers(Modifiers.PUBLIC),
 938                                       tdElement,
 939                                       arrayElementFieldName,
 940                                       null,
 941                                       false);
 942       mapTypeToArrayField.put( tdElement, fdElement );
 943     }
 944     return fdElement;
 945   }
 946
 947
 948   private void setGraphForMethodContext(MethodContext mc, OwnershipGraph og) {
 949
 950     mapMethodContextToCompleteOwnershipGraph.put(mc, og);
 951
 952     if( writeDOTs && writeAllDOTs ) {
 953       if( !mapMethodContextToNumUpdates.containsKey(mc) ) {
 954         mapMethodContextToNumUpdates.put(mc, new Integer(0) );
 955       }
 956       Integer n = mapMethodContextToNumUpdates.get(mc);
 957       try {
 958         og.writeGraph(mc, n, true, true, true, false, false);
 959       } catch( IOException e ) {}
 960       mapMethodContextToNumUpdates.put(mc, n + 1);
 961     }
 962   }
 963
 964
 965   private void addDependent( MethodContext caller, MethodContext callee ) {
 966     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
 967     if( deps == null ) {
 968       deps = new HashSet<MethodContext>();
 969     }
 970     deps.add( caller );
 971     mapMethodContextToDependentContexts.put( callee, deps );
 972   }
 973
 974   private Iterator<MethodContext> iteratorDependents( MethodContext callee ) {
 975     HashSet<MethodContext> deps = mapMethodContextToDependentContexts.get( callee );
 976     if( deps == null ) {
 977       deps = new HashSet<MethodContext>();
 978       mapMethodContextToDependentContexts.put( callee, deps );
 979     }
 980     return deps.iterator();
 981   }
 982
 983
 984   private void writeFinalContextGraphs() {
 985     // arguments to writeGraph are:
 986     // boolean writeLabels,
 987     // boolean labelSelect,
 988     // boolean pruneGarbage,
 989     // boolean writeReferencers
 990     // boolean writeParamMappings
 991
 992     Set entrySet = mapMethodContextToCompleteOwnershipGraph.entrySet();
 993     Iterator itr = entrySet.iterator();
 994     while( itr.hasNext() ) {
 995       Map.Entry      me = (Map.Entry)      itr.next();
 996       MethodContext  mc = (MethodContext)  me.getKey();
 997       OwnershipGraph og = (OwnershipGraph) me.getValue();
 998
 999       try {
1000         og.writeGraph(mc, true, true, true, false, false);
1001       } catch( IOException e ) {}
1002     }
1003   }
1004
1005
1006   // return just the allocation site associated with one FlatNew node
1007   private AllocationSite getAllocationSiteFromFlatNewPRIVATE(FlatNew fn) {
1008
1009     if( !mapFlatNewToAllocationSite.containsKey(fn) ) {
1010       AllocationSite as = new AllocationSite(allocationDepth, fn, fn.getDisjointId());
1011
1012       // the newest nodes are single objects
1013       for( int i = 0; i < allocationDepth; ++i ) {
1014         Integer id = generateUniqueHeapRegionNodeID();
1015         as.setIthOldest(i, id);
1016       }
1017
1018       // the oldest node is a summary node
1019       Integer idSummary = generateUniqueHeapRegionNodeID();
1020       as.setSummary(idSummary);
1021
1022       mapFlatNewToAllocationSite.put(fn, as);
1023     }
1024
1025     return mapFlatNewToAllocationSite.get(fn);
1026   }
1027
1028
1029   // return all allocation sites in the method (there is one allocation
1030   // site per FlatNew node in a method)
1031   private HashSet<AllocationSite> getAllocationSiteSet(Descriptor d) {
1032     if( !mapDescriptorToAllocationSiteSet.containsKey(d) ) {
1033       buildAllocationSiteSet(d);
1034     }
1035
1036     return mapDescriptorToAllocationSiteSet.get(d);
1037
1038   }
1039
1040   private void buildAllocationSiteSet(Descriptor d) {
1041     HashSet<AllocationSite> s = new HashSet<AllocationSite>();
1042
1043     FlatMethod fm;
1044     if( d instanceof MethodDescriptor ) {
1045       fm = state.getMethodFlat( (MethodDescriptor) d);
1046     } else {
1047       assert d instanceof TaskDescriptor;
1048       fm = state.getMethodFlat( (TaskDescriptor) d);
1049     }
1050
1051     // visit every node in this FlatMethod's IR graph
1052     // and make a set of the allocation sites from the
1053     // FlatNew node's visited
1054     HashSet<FlatNode> visited = new HashSet<FlatNode>();
1055     HashSet<FlatNode> toVisit = new HashSet<FlatNode>();
1056     toVisit.add(fm);
1057
1058     while( !toVisit.isEmpty() ) {
1059       FlatNode n = toVisit.iterator().next();
1060
1061       if( n instanceof FlatNew ) {
1062         s.add(getAllocationSiteFromFlatNewPRIVATE( (FlatNew) n) );
1063       }
1064
1065       toVisit.remove(n);
1066       visited.add(n);
1067
1068       for( int i = 0; i < n.numNext(); ++i ) {
1069         FlatNode child = n.getNext(i);
1070         if( !visited.contains(child) ) {
1071           toVisit.add(child);
1072         }
1073       }
1074     }
1075
1076     mapDescriptorToAllocationSiteSet.put(d, s);
1077   }
1078
1079
1080   private HashSet<AllocationSite> getFlaggedAllocationSites(Descriptor dIn) {
1081
1082     HashSet<AllocationSite> out     = new HashSet<AllocationSite>();
1083     HashSet<Descriptor>     toVisit = new HashSet<Descriptor>();
1084     HashSet<Descriptor>     visited = new HashSet<Descriptor>();
1085
1086     toVisit.add(dIn);
1087
1088     while( !toVisit.isEmpty() ) {
1089       Descriptor d = toVisit.iterator().next();
1090       toVisit.remove(d);
1091       visited.add(d);
1092
1093       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1094       Iterator asItr = asSet.iterator();
1095       while( asItr.hasNext() ) {
1096         AllocationSite as = (AllocationSite) asItr.next();
1097         if( as.getDisjointId() != null ) {
1098           out.add(as);
1099         }
1100       }
1101
1102       // enqueue callees of this method to be searched for
1103       // allocation sites also
1104       Set callees = callGraph.getCalleeSet(d);
1105       if( callees != null ) {
1106         Iterator methItr = callees.iterator();
1107         while( methItr.hasNext() ) {
1108           MethodDescriptor md = (MethodDescriptor) methItr.next();
1109
1110           if( !visited.contains(md) ) {
1111             toVisit.add(md);
1112           }
1113         }
1114       }
1115     }
1116
1117     return out;
1118   }
1119
1120
1121   private HashSet<AllocationSite>
1122   getFlaggedAllocationSitesReachableFromTaskPRIVATE(TaskDescriptor td) {
1123
1124     HashSet<AllocationSite> asSetTotal = new HashSet<AllocationSite>();
1125     HashSet<Descriptor>     toVisit    = new HashSet<Descriptor>();
1126     HashSet<Descriptor>     visited    = new HashSet<Descriptor>();
1127
1128     toVisit.add(td);
1129
1130     // traverse this task and all methods reachable from this task
1131     while( !toVisit.isEmpty() ) {
1132       Descriptor d = toVisit.iterator().next();
1133       toVisit.remove(d);
1134       visited.add(d);
1135
1136       HashSet<AllocationSite> asSet = getAllocationSiteSet(d);
1137       Iterator asItr = asSet.iterator();
1138       while( asItr.hasNext() ) {
1139         AllocationSite as = (AllocationSite) asItr.next();
1140         TypeDescriptor typed = as.getType();
1141         if( typed != null ) {
1142           ClassDescriptor cd = typed.getClassDesc();
1143           if( cd != null && cd.hasFlags() ) {
1144             asSetTotal.add(as);
1145           }
1146         }
1147       }
1148
1149       // enqueue callees of this method to be searched for
1150       // allocation sites also
1151       Set callees = callGraph.getCalleeSet(d);
1152       if( callees != null ) {
1153         Iterator methItr = callees.iterator();
1154         while( methItr.hasNext() ) {
1155           MethodDescriptor md = (MethodDescriptor) methItr.next();
1156
1157           if( !visited.contains(md) ) {
1158             toVisit.add(md);
1159           }
1160         }
1161       }
1162     }
1163
1164
1165     return asSetTotal;
1166   }
1167
1168
1169   private LinkedList<MethodContext> topologicalSort( HashSet<MethodContext> set ) {
1170     HashSet   <MethodContext> discovered = new HashSet   <MethodContext>();
1171     LinkedList<MethodContext> sorted     = new LinkedList<MethodContext>();
1172
1173     Iterator<MethodContext> itr = set.iterator();
1174     while( itr.hasNext() ) {
1175       MethodContext mc = itr.next();
1176
1177       if( !discovered.contains( mc ) ) {
1178         dfsVisit( set, mc, sorted, discovered );
1179       }
1180     }
1181
1182     return sorted;
1183   }
1184
1185   private void dfsVisit( HashSet<MethodContext> set,
1186                          MethodContext mc,
1187                          LinkedList<MethodContext> sorted,
1188                          HashSet   <MethodContext> discovered ) {
1189     discovered.add( mc );
1190
1191     Descriptor d = mc.getDescriptor();
1192     if( d instanceof MethodDescriptor ) {
1193       MethodDescriptor md = (MethodDescriptor) d;
1194       Iterator itr = callGraph.getCallerSet( md ).iterator();
1195       while( itr.hasNext() ) {
1196         Descriptor dCaller = (Descriptor) itr.next();
1197
1198         // only consider the callers in the original set to analyze
1199         Set<MethodContext> callerContexts = mapDescriptorToAllMethodContexts.get( dCaller );
1200         if( callerContexts == null )
1201           continue;
1202
1203         // since the analysis hasn't started, there should be exactly one
1204         // context if there are any at all
1205         assert callerContexts.size() == 1;
1206         MethodContext mcCaller = callerContexts.iterator().next();
1207         assert set.contains( mcCaller );
1208
1209         if( !discovered.contains( mcCaller ) ) {
1210           dfsVisit( set, mcCaller, sorted, discovered );
1211         }
1212       }
1213     }
1214
1215     sorted.addFirst( mc );
1216   }
1217
1218
1219
1220   private String computeAliasContextHistogram() {
1221
1222     Hashtable<Integer, Integer> mapNumContexts2NumDesc =
1223       new Hashtable<Integer, Integer>();
1224
1225     Iterator itr = mapDescriptorToAllMethodContexts.entrySet().iterator();
1226     while( itr.hasNext() ) {
1227       Map.Entry me = (Map.Entry) itr.next();
1228       HashSet<MethodContext> s = (HashSet<MethodContext>) me.getValue();
1229
1230       Integer i = mapNumContexts2NumDesc.get( s.size() );
1231       if( i == null ) {
1232         i = new Integer( 0 );
1233       }
1234       mapNumContexts2NumDesc.put( s.size(), i + 1 );
1235     }
1236
1237     String s = "";
1238     int total = 0;
1239
1240     itr = mapNumContexts2NumDesc.entrySet().iterator();
1241     while( itr.hasNext() ) {
1242       Map.Entry me = (Map.Entry) itr.next();
1243       Integer c0 = (Integer) me.getKey();
1244       Integer d0 = (Integer) me.getValue();
1245       total += d0;
1246       s += String.format( "%4d methods had %4d unique alias contexts.\n", d0, c0 );
1247     }
1248
1249     s += String.format( "\n%4d total methods analayzed.\n", total );
1250
1251     return s;
1252   }
1253
1254
1255
1256   // insert a call to debugSnapshot() somewhere in the analysis
1257   // to get successive captures of the analysis state
1258   boolean takeDebugSnapshots = false;
1259   String mcDescSymbolDebug = "main";
1260   boolean stopAfterCapture = true;
1261
1262   // increments every visit to debugSnapshot, don't fiddle with it
1263   int debugCounter = 0;
1264
1265   // the value of debugCounter to start reporting the debugCounter
1266   // to the screen to let user know what debug iteration we're at
1267   int numStartCountReport = 100;
1268
1269   // the frequency of debugCounter values to print out, 0 no report
1270   int freqCountReport = 0;
1271
1272   // the debugCounter value at which to start taking snapshots
1273   int iterStartCapture = 134;
1274
1275   // the number of snapshots to take
1276   int numIterToCapture = 50;
1277
1278   void debugSnapshot(OwnershipGraph og, FlatNode fn) {
1279     if( debugCounter > iterStartCapture + numIterToCapture ) {
1280       return;
1281     }
1282
1283     ++debugCounter;
1284     if( debugCounter > numStartCountReport &&
1285         freqCountReport > 0 &&
1286         debugCounter % freqCountReport == 0 ) {
1287       System.out.println("    @@@ debug counter = "+debugCounter);
1288     }
1289     if( debugCounter > iterStartCapture ) {
1290       System.out.println("    @@@ capturing debug "+(debugCounter-iterStartCapture)+" @@@");
1291       String graphName = String.format("snap%04d",debugCounter-iterStartCapture);
1292       if( fn != null ) {
1293         graphName = graphName+fn;
1294       }
1295       try {
1296         og.writeGraph(graphName, true, true, true, false, false);
1297       } catch( Exception e ) {
1298         System.out.println("Error writing debug capture.");
1299         System.exit(0);
1300       }
1301     }
1302
1303     if( debugCounter == iterStartCapture + numIterToCapture && stopAfterCapture ) {
1304       System.out.println("Stopping analysis after debug captures.");
1305       System.exit(0);
1306     }
1307   }
1308 }