Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8 public class OwnershipGraph {
   9
  10   private int allocationDepth;
  11
  12   // there was already one other very similar reason
  13   // for traversing heap nodes that is no longer needed
  14   // instead of writing a new heap region visitor, use
  15   // the existing method with a new mode to describe what
  16   // actions to take during the traversal
  17   protected static final int VISIT_HRN_WRITE_FULL = 0;
  18
  19
  20   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  21   public Hashtable<TempDescriptor, LabelNode     > td2ln;
  22   public Hashtable<Integer,        Integer       > id2paramIndex;
  23   public Hashtable<Integer,        Integer       > paramIndex2id;
  24   public Hashtable<Integer,        TempDescriptor> paramIndex2tdQ;
  25
  26   public HashSet<AllocationSite> allocationSites;
  27
  28
  29   public OwnershipGraph(int allocationDepth) {
  30     this.allocationDepth = allocationDepth;
  31
  32     id2hrn         = new Hashtable<Integer,        HeapRegionNode>();
  33     td2ln          = new Hashtable<TempDescriptor, LabelNode     >();
  34     id2paramIndex  = new Hashtable<Integer,        Integer       >();
  35     paramIndex2id  = new Hashtable<Integer,        Integer       >();
  36     paramIndex2tdQ = new Hashtable<Integer,        TempDescriptor>();
  37
  38     allocationSites = new HashSet <AllocationSite>();
  39   }
  40
  41
  42   // label nodes are much easier to deal with than
  43   // heap region nodes.  Whenever there is a request
  44   // for the label node that is associated with a
  45   // temp descriptor we can either find it or make a
  46   // new one and return it.  This is because temp
  47   // descriptors are globally unique and every label
  48   // node is mapped to exactly one temp descriptor.
  49   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  50     assert td != null;
  51
  52     if( !td2ln.containsKey(td) ) {
  53       td2ln.put(td, new LabelNode(td) );
  54     }
  55
  56     return td2ln.get(td);
  57   }
  58
  59
  60   // the reason for this method is to have the option
  61   // creating new heap regions with specific IDs, or
  62   // duplicating heap regions with specific IDs (especially
  63   // in the merge() operation) or to create new heap
  64   // regions with a new unique ID.
  65   protected HeapRegionNode
  66   createNewHeapRegionNode(Integer id,
  67                           boolean isSingleObject,
  68                           boolean isFlagged,
  69                           boolean isNewSummary,
  70                           boolean isParameter,
  71                           AllocationSite allocSite,
  72                           ReachabilitySet alpha,
  73                           String description) {
  74
  75     if( id == null ) {
  76       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  77     }
  78
  79     if( alpha == null ) {
  80       if( isFlagged || isParameter ) {
  81         alpha = new ReachabilitySet(new TokenTuple(id,
  82                                                    !isSingleObject,
  83                                                    TokenTuple.ARITY_ONE)
  84                                     ).makeCanonical();
  85       } else {
  86         alpha = new ReachabilitySet(new TokenTupleSet()
  87                                     ).makeCanonical();
  88       }
  89     }
  90
  91     HeapRegionNode hrn = new HeapRegionNode(id,
  92                                             isSingleObject,
  93                                             isFlagged,
  94                                             isNewSummary,
  95                                             allocSite,
  96                                             alpha,
  97                                             description);
  98     id2hrn.put(id, hrn);
  99     return hrn;
 100   }
 101
 102
 103
 104   ////////////////////////////////////////////////
 105   //
 106   //  Low-level referencee and referencer methods
 107   //
 108   //  These methods provide the lowest level for
 109   //  creating references between ownership nodes
 110   //  and handling the details of maintaining both
 111   //  list of referencers and referencees.
 112   //
 113   ////////////////////////////////////////////////
 114   protected void addReferenceEdge(OwnershipNode referencer,
 115                                   HeapRegionNode referencee,
 116                                   ReferenceEdge edge) {
 117     assert referencer != null;
 118     assert referencee != null;
 119     assert edge       != null;
 120     assert edge.getSrc() == referencer;
 121     assert edge.getDst() == referencee;
 122
 123     referencer.addReferencee(edge);
 124     referencee.addReferencer(edge);
 125   }
 126
 127   protected void removeReferenceEdge(OwnershipNode referencer,
 128                                      HeapRegionNode referencee,
 129                                      FieldDescriptor fieldDesc) {
 130     assert referencer != null;
 131     assert referencee != null;
 132
 133     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 134                                                    fieldDesc);
 135     assert edge != null;
 136     assert edge == referencee.getReferenceFrom(referencer,
 137                                                fieldDesc);
 138
 139     referencer.removeReferencee(edge);
 140     referencee.removeReferencer(edge);
 141   }
 142
 143   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 144                                          FieldDescriptor fieldDesc,
 145                                          boolean removeAll) {
 146     assert referencer != null;
 147
 148     // get a copy of the set to iterate over, otherwise
 149     // we will be trying to take apart the set as we
 150     // are iterating over it, which won't work
 151     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 152     while( i.hasNext() ) {
 153       ReferenceEdge edge = i.next();
 154
 155       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 156         HeapRegionNode referencee = edge.getDst();
 157
 158         removeReferenceEdge(referencer,
 159                             referencee,
 160                             edge.getFieldDesc() );
 161       }
 162     }
 163   }
 164
 165   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 166                                        FieldDescriptor fieldDesc,
 167                                        boolean removeAll) {
 168     assert referencee != null;
 169
 170     // get a copy of the set to iterate over, otherwise
 171     // we will be trying to take apart the set as we
 172     // are iterating over it, which won't work
 173     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 174     while( i.hasNext() ) {
 175       ReferenceEdge edge = i.next();
 176
 177       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 178         OwnershipNode referencer = edge.getSrc();
 179         removeReferenceEdge(referencer,
 180                             referencee,
 181                             edge.getFieldDesc() );
 182       }
 183     }
 184   }
 185
 186
 187   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
 188                                           ChangeTupleSet c0,
 189                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
 190                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
 191
 192     HashSet<HeapRegionNode> todoNodes
 193     = new HashSet<HeapRegionNode>();
 194     todoNodes.add(nPrime);
 195
 196     HashSet<ReferenceEdge> todoEdges
 197     = new HashSet<ReferenceEdge>();
 198
 199     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 200     = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 201     nodePlannedChanges.put(nPrime, c0);
 202
 203     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
 204     = new Hashtable<ReferenceEdge, ChangeTupleSet>();
 205
 206
 207     while( !todoNodes.isEmpty() ) {
 208       HeapRegionNode n = todoNodes.iterator().next();
 209       ChangeTupleSet C = nodePlannedChanges.get(n);
 210
 211       Iterator itrC = C.iterator();
 212       while( itrC.hasNext() ) {
 213         ChangeTuple c = (ChangeTuple) itrC.next();
 214
 215         if( n.getAlpha().contains(c.getSetToMatch() ) ) {
 216           ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
 217           n.setAlphaNew(n.getAlphaNew().union(withChange) );
 218           nodesWithNewAlpha.add(n);
 219         }
 220       }
 221
 222       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 223       while( referItr.hasNext() ) {
 224         ReferenceEdge edge = referItr.next();
 225         todoEdges.add(edge);
 226
 227         if( !edgePlannedChanges.containsKey(edge) ) {
 228           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
 229         }
 230
 231         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 232       }
 233
 234       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
 235       while( refeeItr.hasNext() ) {
 236         ReferenceEdge edgeF = refeeItr.next();
 237         HeapRegionNode m     = edgeF.getDst();
 238
 239         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 240
 241         Iterator<ChangeTuple> itrCprime = C.iterator();
 242         while( itrCprime.hasNext() ) {
 243           ChangeTuple c = itrCprime.next();
 244           if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
 245             changesToPass = changesToPass.union(c);
 246           }
 247         }
 248
 249         if( !changesToPass.isEmpty() ) {
 250           if( !nodePlannedChanges.containsKey(m) ) {
 251             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
 252           }
 253
 254           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
 255
 256           if( !changesToPass.isSubset(currentChanges) ) {
 257
 258             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 259             todoNodes.add(m);
 260           }
 261         }
 262       }
 263
 264       todoNodes.remove(n);
 265     }
 266
 267     propagateTokensOverEdges(todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta);
 268   }
 269
 270
 271   protected void propagateTokensOverEdges(
 272     HashSet<ReferenceEdge>                   todoEdges,
 273     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
 274     HashSet<HeapRegionNode>                  nodesWithNewAlpha,
 275     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
 276
 277
 278     while( !todoEdges.isEmpty() ) {
 279       ReferenceEdge edgeE = todoEdges.iterator().next();
 280       todoEdges.remove(edgeE);
 281
 282       if( !edgePlannedChanges.containsKey(edgeE) ) {
 283         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
 284       }
 285
 286       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
 287
 288       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 289
 290       Iterator<ChangeTuple> itrC = C.iterator();
 291       while( itrC.hasNext() ) {
 292         ChangeTuple c = itrC.next();
 293         if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
 294           ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
 295           edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
 296           edgesWithNewBeta.add(edgeE);
 297           changesToPass = changesToPass.union(c);
 298         }
 299       }
 300
 301       OwnershipNode onSrc = edgeE.getSrc();
 302
 303       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 304         HeapRegionNode n = (HeapRegionNode) onSrc;
 305
 306         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 307         while( referItr.hasNext() ) {
 308           ReferenceEdge edgeF = referItr.next();
 309
 310           if( !edgePlannedChanges.containsKey(edgeF) ) {
 311             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
 312           }
 313
 314           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
 315
 316           if( !changesToPass.isSubset(currentChanges) ) {
 317             todoEdges.add(edgeF);
 318             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
 319           }
 320         }
 321       }
 322     }
 323   }
 324
 325
 326   ////////////////////////////////////////////////////
 327   //
 328   //  Assignment Operation Methods
 329   //
 330   //  These methods are high-level operations for
 331   //  modeling program assignment statements using
 332   //  the low-level reference create/remove methods
 333   //  above.
 334   //
 335   //  The destination in an assignment statement is
 336   //  going to have new references.  The method of
 337   //  determining the references depends on the type
 338   //  of the FlatNode assignment and the predicates
 339   //  of the nodes and edges involved.
 340   //
 341   ////////////////////////////////////////////////////
 342   public void assignTempYToTempX(TempDescriptor y,
 343                                  TempDescriptor x) {
 344
 345     LabelNode lnX = getLabelNodeFromTemp(x);
 346     LabelNode lnY = getLabelNodeFromTemp(y);
 347
 348     clearReferenceEdgesFrom(lnX, null, true);
 349
 350     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 351     while( itrYhrn.hasNext() ) {
 352       ReferenceEdge edgeY       = itrYhrn.next();
 353       HeapRegionNode referencee = edgeY.getDst();
 354       ReferenceEdge edgeNew    = edgeY.copy();
 355       edgeNew.setSrc(lnX);
 356
 357       addReferenceEdge(lnX, referencee, edgeNew);
 358     }
 359   }
 360
 361
 362   public void assignTempYFieldFToTempX(TempDescriptor y,
 363                                        FieldDescriptor f,
 364                                        TempDescriptor x) {
 365
 366     LabelNode lnX = getLabelNodeFromTemp(x);
 367     LabelNode lnY = getLabelNodeFromTemp(y);
 368
 369     clearReferenceEdgesFrom(lnX, null, true);
 370
 371     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 372     while( itrYhrn.hasNext() ) {
 373       ReferenceEdge edgeY = itrYhrn.next();
 374       HeapRegionNode hrnY  = edgeY.getDst();
 375       ReachabilitySet betaY = edgeY.getBeta();
 376
 377       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 378       while( itrHrnFhrn.hasNext() ) {
 379         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 380         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 381         ReachabilitySet betaHrn = edgeHrn.getBeta();
 382
 383         if( edgeHrn.getFieldDesc() == null ||
 384             edgeHrn.getFieldDesc() == f ) {
 385
 386           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 387                                                     hrnHrn,
 388                                                     f,
 389                                                     false,
 390                                                     betaY.intersection(betaHrn) );
 391
 392           addReferenceEdge(lnX, hrnHrn, edgeNew);
 393         }
 394       }
 395     }
 396   }
 397
 398
 399   public void assignTempYToTempXFieldF(TempDescriptor y,
 400                                        TempDescriptor x,
 401                                        FieldDescriptor f) {
 402
 403     LabelNode lnX = getLabelNodeFromTemp(x);
 404     LabelNode lnY = getLabelNodeFromTemp(y);
 405
 406     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 407     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 408
 409     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 410     while( itrXhrn.hasNext() ) {
 411       ReferenceEdge edgeX = itrXhrn.next();
 412       HeapRegionNode hrnX  = edgeX.getDst();
 413       ReachabilitySet betaX = edgeX.getBeta();
 414
 415       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 416
 417       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 418       while( itrYhrn.hasNext() ) {
 419         ReferenceEdge edgeY = itrYhrn.next();
 420         HeapRegionNode hrnY  = edgeY.getDst();
 421         ReachabilitySet O     = edgeY.getBeta();
 422
 423
 424         // propagate tokens over nodes starting from hrnSrc, and it will
 425         // take care of propagating back up edges from any touched nodes
 426         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 427         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 428
 429
 430         // then propagate back just up the edges from hrn
 431         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 432
 433         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 434
 435         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 436           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 437
 438         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 439         while( referItr.hasNext() ) {
 440           ReferenceEdge edgeUpstream = referItr.next();
 441           todoEdges.add(edgeUpstream);
 442           edgePlannedChanges.put(edgeUpstream, Cx);
 443         }
 444
 445         propagateTokensOverEdges(todoEdges,
 446                                  edgePlannedChanges,
 447                                  nodesWithNewAlpha,
 448                                  edgesWithNewBeta);
 449
 450
 451
 452         //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
 453
 454         // create the actual reference edge hrnX.f -> hrnY
 455         ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
 456                                                   hrnY,
 457                                                   f,
 458                                                   false,
 459                                                   edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
 460                                                   //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
 461                                                   );
 462         addReferenceEdge(hrnX, hrnY, edgeNew);
 463
 464         /*
 465            if( f != null ) {
 466             // we can do a strong update here if one of two cases holds
 467             // SAVE FOR LATER, WITHOUT STILL CORRECT
 468             if( (hrnX.getNumReferencers() == 1)                           ||
 469                 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
 470               ) {
 471                 clearReferenceEdgesFrom( hrnX, f, false );
 472             }
 473
 474             addReferenceEdge( hrnX, hrnY, edgeNew );
 475
 476            } else {
 477             // if the field is null, or "any" field, then
 478             // look to see if an any field already exists
 479             // and merge with it, otherwise just add the edge
 480             ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
 481
 482             if( edgeExisting != null ) {
 483                 edgeExisting.setBetaNew(
 484                   edgeExisting.getBetaNew().union( edgeNew.getBeta() )
 485                                        );
 486                 // a new edge here cannot be reflexive, so existing will
 487                 // always be also not reflexive anymore
 488                 edgeExisting.setIsInitialParamReflexive( false );
 489
 490             } else {
 491                 addReferenceEdge( hrnX, hrnY, edgeNew );
 492             }
 493            }
 494          */
 495       }
 496     }
 497
 498     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 499     while( nodeItr.hasNext() ) {
 500       nodeItr.next().applyAlphaNew();
 501     }
 502
 503     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
 504     while( edgeItr.hasNext() ) {
 505       edgeItr.next().applyBetaNew();
 506     }
 507   }
 508
 509
 510   public void assignParameterAllocationToTemp(boolean isTask,
 511                                               TempDescriptor td,
 512                                               Integer paramIndex) {
 513     assert td != null;
 514
 515     LabelNode lnParam = getLabelNodeFromTemp(td);
 516     HeapRegionNode hrn = createNewHeapRegionNode(null,
 517                                                  false,
 518                                                  isTask,
 519                                                  false,
 520                                                  true,
 521                                                  null,
 522                                                  null,
 523                                                  "param" + paramIndex);
 524
 525     // this is a non-program-accessible label that picks up beta
 526     // info to be used for fixing a caller of this method
 527     TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
 528     LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
 529
 530     // keep track of heap regions that were created for
 531     // parameter labels, the index of the parameter they
 532     // are for is important when resolving method calls
 533     Integer newID = hrn.getID();
 534     assert !id2paramIndex.containsKey(newID);
 535     assert !id2paramIndex.containsValue(paramIndex);
 536     id2paramIndex.put(newID, paramIndex);
 537     paramIndex2id.put(paramIndex, newID);
 538     paramIndex2tdQ.put(paramIndex, tdParamQ);
 539
 540     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
 541                                                               true,
 542                                                               TokenTuple.ARITY_ONE) );
 543
 544     // heap regions for parameters are always multiple object (see above)
 545     // and have a reference to themselves, because we can't know the
 546     // structure of memory that is passed into the method.  We're assuming
 547     // the worst here.
 548
 549     ReferenceEdge edgeFromLabel =
 550       new ReferenceEdge(lnParam, hrn, null, false, beta);
 551
 552     ReferenceEdge edgeFromLabelQ =
 553       new ReferenceEdge(lnParamQ, hrn, null, false, beta);
 554
 555     ReferenceEdge edgeReflexive =
 556       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 557
 558     addReferenceEdge(lnParam,  hrn, edgeFromLabel);
 559     addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
 560     addReferenceEdge(hrn,      hrn, edgeReflexive);
 561   }
 562
 563
 564   public void assignNewAllocationToTempX(TempDescriptor x,
 565                                          AllocationSite as) {
 566     assert x  != null;
 567     assert as != null;
 568
 569     age(as);
 570
 571     // after the age operation the newest (or zero-ith oldest)
 572     // node associated with the allocation site should have
 573     // no references to it as if it were a newly allocated
 574     // heap region, so make a reference to it to complete
 575     // this operation
 576
 577     Integer idNewest  = as.getIthOldest(0);
 578     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 579     assert hrnNewest != null;
 580
 581     LabelNode lnX = getLabelNodeFromTemp(x);
 582     clearReferenceEdgesFrom(lnX, null, true);
 583
 584     ReferenceEdge edgeNew =
 585       new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
 586
 587     addReferenceEdge(lnX, hrnNewest, edgeNew);
 588   }
 589
 590
 591   // use the allocation site (unique to entire analysis) to
 592   // locate the heap region nodes in this ownership graph
 593   // that should be aged.  The process models the allocation
 594   // of new objects and collects all the oldest allocations
 595   // in a summary node to allow for a finite analysis
 596   //
 597   // There is an additional property of this method.  After
 598   // running it on a particular ownership graph (many graphs
 599   // may have heap regions related to the same allocation site)
 600   // the heap region node objects in this ownership graph will be
 601   // allocated.  Therefore, after aging a graph for an allocation
 602   // site, attempts to retrieve the heap region nodes using the
 603   // integer id's contained in the allocation site should always
 604   // return non-null heap regions.
 605   public void age(AllocationSite as) {
 606
 607     // aging adds this allocation site to the graph's
 608     // list of sites that exist in the graph, or does
 609     // nothing if the site is already in the list
 610     allocationSites.add(as);
 611
 612     // get the summary node for the allocation site in the context
 613     // of this particular ownership graph
 614     HeapRegionNode hrnSummary = getSummaryNode(as);
 615
 616     // merge oldest node into summary
 617     Integer idK  = as.getOldest();
 618     HeapRegionNode hrnK = id2hrn.get(idK);
 619     mergeIntoSummary(hrnK, hrnSummary);
 620
 621     // move down the line of heap region nodes
 622     // clobbering the ith and transferring all references
 623     // to and from i-1 to node i.  Note that this clobbers
 624     // the oldest node (hrnK) that was just merged into
 625     // the summary
 626     for( int i = allocationDepth - 1; i > 0; --i ) {
 627
 628       // move references from the i-1 oldest to the ith oldest
 629       Integer idIth     = as.getIthOldest(i);
 630       HeapRegionNode hrnI      = id2hrn.get(idIth);
 631       Integer idImin1th = as.getIthOldest(i - 1);
 632       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 633
 634       transferOnto(hrnImin1, hrnI);
 635     }
 636
 637     // as stated above, the newest node should have had its
 638     // references moved over to the second oldest, so we wipe newest
 639     // in preparation for being the new object to assign something to
 640     Integer id0th = as.getIthOldest(0);
 641     HeapRegionNode hrn0  = id2hrn.get(id0th);
 642     assert hrn0 != null;
 643
 644     // clear all references in and out of newest node
 645     clearReferenceEdgesFrom(hrn0, null, true);
 646     clearReferenceEdgesTo(hrn0, null, true);
 647
 648
 649     // now tokens in reachability sets need to "age" also
 650     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 651     while( itrAllLabelNodes.hasNext() ) {
 652       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 653       LabelNode ln = (LabelNode) me.getValue();
 654
 655       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 656       while( itrEdges.hasNext() ) {
 657         ageTokens(as, itrEdges.next() );
 658       }
 659     }
 660
 661     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 662     while( itrAllHRNodes.hasNext() ) {
 663       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
 664       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 665
 666       ageTokens(as, hrnToAge);
 667
 668       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
 669       while( itrEdges.hasNext() ) {
 670         ageTokens(as, itrEdges.next() );
 671       }
 672     }
 673
 674
 675     // after tokens have been aged, reset newest node's reachability
 676     if( hrn0.isFlagged() ) {
 677       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
 678                                           new TokenTuple(hrn0)
 679                                           )
 680                                         ).makeCanonical()
 681                     );
 682     } else {
 683       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
 684                                         ).makeCanonical()
 685                     );
 686     }
 687   }
 688
 689
 690   protected HeapRegionNode getSummaryNode(AllocationSite as) {
 691
 692     Integer idSummary  = as.getSummary();
 693     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
 694
 695     // If this is null then we haven't touched this allocation site
 696     // in the context of the current ownership graph, so allocate
 697     // heap region nodes appropriate for the entire allocation site.
 698     // This should only happen once per ownership graph per allocation site,
 699     // and a particular integer id can be used to locate the heap region
 700     // in different ownership graphs that represents the same part of an
 701     // allocation site.
 702     if( hrnSummary == null ) {
 703
 704       boolean hasFlags = false;
 705       if( as.getType().isClass() ) {
 706         hasFlags = as.getType().getClassDesc().hasFlags();
 707       }
 708
 709       hrnSummary = createNewHeapRegionNode(idSummary,
 710                                            false,
 711                                            hasFlags,
 712                                            true,
 713                                            false,
 714                                            as,
 715                                            null,
 716                                            as + "\\n" + as.getType() + "\\nsummary");
 717
 718       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 719         Integer idIth = as.getIthOldest(i);
 720         assert !id2hrn.containsKey(idIth);
 721         createNewHeapRegionNode(idIth,
 722                                 true,
 723                                 hasFlags,
 724                                 false,
 725                                 false,
 726                                 as,
 727                                 null,
 728                                 as + "\\n" + as.getType() + "\\n" + i + " oldest");
 729       }
 730     }
 731
 732     return hrnSummary;
 733   }
 734
 735
 736   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
 737
 738     Integer idShadowSummary  = -(as.getSummary());
 739     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
 740
 741     if( hrnShadowSummary == null ) {
 742
 743       boolean hasFlags = false;
 744       if( as.getType().isClass() ) {
 745         hasFlags = as.getType().getClassDesc().hasFlags();
 746       }
 747
 748       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
 749                                                  false,
 750                                                  hasFlags,
 751                                                  true,
 752                                                  false,
 753                                                  as,
 754                                                  null,
 755                                                  as + "\\n" + as.getType() + "\\nshadowSum");
 756
 757       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 758         Integer idShadowIth = -(as.getIthOldest(i));
 759         assert !id2hrn.containsKey(idShadowIth);
 760         createNewHeapRegionNode(idShadowIth,
 761                                 true,
 762                                 hasFlags,
 763                                 false,
 764                                 false,
 765                                 as,
 766                                 null,
 767                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
 768       }
 769     }
 770
 771     return hrnShadowSummary;
 772   }
 773
 774
 775   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
 776     assert hrnSummary.isNewSummary();
 777
 778     // transfer references _from_ hrn over to hrnSummary
 779     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
 780     while( itrReferencee.hasNext() ) {
 781       ReferenceEdge edge       = itrReferencee.next();
 782       ReferenceEdge edgeMerged = edge.copy();
 783       edgeMerged.setSrc(hrnSummary);
 784
 785       HeapRegionNode hrnReferencee = edge.getDst();
 786       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
 787
 788       if( edgeSummary == null ) {
 789         // the merge is trivial, nothing to be done
 790       } else {
 791         // otherwise an edge from the referencer to hrnSummary exists already
 792         // and the edge referencer->hrn should be merged with it
 793         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 794       }
 795
 796       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
 797     }
 798
 799     // next transfer references _to_ hrn over to hrnSummary
 800     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
 801     while( itrReferencer.hasNext() ) {
 802       ReferenceEdge edge         = itrReferencer.next();
 803       ReferenceEdge edgeMerged   = edge.copy();
 804       edgeMerged.setDst(hrnSummary);
 805
 806       OwnershipNode onReferencer = edge.getSrc();
 807       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
 808
 809       if( edgeSummary == null ) {
 810         // the merge is trivial, nothing to be done
 811       } else {
 812         // otherwise an edge from the referencer to alpha_S exists already
 813         // and the edge referencer->alpha_K should be merged with it
 814         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 815       }
 816
 817       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
 818     }
 819
 820     // then merge hrn reachability into hrnSummary
 821     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
 822   }
 823
 824
 825   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
 826
 827     // clear references in and out of node i
 828     clearReferenceEdgesFrom(hrnB, null, true);
 829     clearReferenceEdgesTo(hrnB, null, true);
 830
 831     // copy each edge in and out of A to B
 832     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
 833     while( itrReferencee.hasNext() ) {
 834       ReferenceEdge edge          = itrReferencee.next();
 835       HeapRegionNode hrnReferencee = edge.getDst();
 836       ReferenceEdge edgeNew       = edge.copy();
 837       edgeNew.setSrc(hrnB);
 838
 839       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
 840     }
 841
 842     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
 843     while( itrReferencer.hasNext() ) {
 844       ReferenceEdge edge         = itrReferencer.next();
 845       OwnershipNode onReferencer = edge.getSrc();
 846       ReferenceEdge edgeNew      = edge.copy();
 847       edgeNew.setDst(hrnB);
 848
 849       addReferenceEdge(onReferencer, hrnB, edgeNew);
 850     }
 851
 852     // replace hrnB reachability with hrnA's
 853     hrnB.setAlpha(hrnA.getAlpha() );
 854   }
 855
 856
 857   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
 858     edge.setBeta(edge.getBeta().ageTokens(as) );
 859   }
 860
 861   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
 862     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
 863   }
 864
 865   protected void majorAgeTokens(AllocationSite as, ReferenceEdge edge) {
 866     //edge.setBeta( edge.getBeta().majorAgeTokens( as ) );
 867   }
 868
 869   protected void majorAgeTokens(AllocationSite as, HeapRegionNode hrn) {
 870     //hrn.setAlpha( hrn.getAlpha().majorAgeTokens( as ) );
 871   }
 872
 873
 874   public void resolveMethodCall(FlatCall fc,
 875                                 boolean isStatic,
 876                                 FlatMethod fm,
 877                                 OwnershipGraph ogCallee) {
 878
 879     // verify the existence of allocation sites and their
 880     // shadows from the callee in the context of this caller graph
 881     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
 882     while( asItr.hasNext() ) {
 883       AllocationSite allocSite        = asItr.next();
 884       HeapRegionNode hrnSummary       = getSummaryNode      ( allocSite );
 885
 886       // assert that the shadow nodes have no reference edges
 887       // because they're brand new to the graph, or last time
 888       // they were used they should have been cleared of edges
 889       HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
 890       assert hrnShadowSummary.getNumReferencers() == 0;
 891       assert hrnShadowSummary.getNumReferencees() == 0;
 892       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
 893         Integer idShadowIth = -(allocSite.getIthOldest(i));
 894         assert id2hrn.containsKey(idShadowIth);
 895         HeapRegionNode hrnShadowIth = id2hrn.get(idShadowIth);
 896         assert hrnShadowIth.getNumReferencers() == 0;
 897         assert hrnShadowIth.getNumReferencees() == 0;
 898       }
 899     }
 900
 901
 902     // define rewrite rules and other structures to organize
 903     // data by parameter/argument index
 904     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
 905       new Hashtable<Integer, ReachabilitySet>();
 906
 907     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
 908       new Hashtable<Integer, ReachabilitySet>();
 909
 910     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
 911       new Hashtable<Integer, ReachabilitySet>();
 912
 913     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
 914       new Hashtable<Integer, ReachabilitySet>();
 915
 916
 917     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
 918       new Hashtable<TokenTuple, Integer>();
 919
 920     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
 921       new Hashtable<Integer, TokenTuple>();
 922
 923     Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
 924       new Hashtable<TokenTuple, Integer>();
 925
 926     Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
 927       new Hashtable<Integer, TokenTuple>();
 928
 929
 930     Hashtable<Integer, LabelNode> paramIndex2ln =
 931       new Hashtable<Integer, LabelNode>();
 932
 933
 934     for( int i = 0; i < fm.numParameters(); ++i ) {
 935       Integer paramIndex = new Integer( i );
 936
 937       assert ogCallee.paramIndex2id.containsKey( paramIndex );
 938       Integer idParam = ogCallee.paramIndex2id.get( paramIndex );
 939
 940       assert ogCallee.id2hrn.containsKey( idParam );
 941       HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
 942       assert hrnParam != null;
 943       paramIndex2rewriteH.put( paramIndex, hrnParam.getAlpha() );
 944
 945       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo( hrnParam, null );
 946       assert edgeReflexive_i != null;
 947       paramIndex2rewriteJ.put( paramIndex, edgeReflexive_i.getBeta() );
 948
 949       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
 950       assert tdParamQ != null;
 951       LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
 952       assert lnParamQ != null;
 953       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnParam, null );
 954       assert edgeSpecialQ_i != null;
 955       paramIndex2rewriteK.put( paramIndex, edgeSpecialQ_i.getBeta() );
 956
 957       TokenTuple p_i = new TokenTuple( hrnParam.getID(),
 958                                        true,
 959                                        TokenTuple.ARITY_ONE ).makeCanonical();
 960       paramToken2paramIndex.put( p_i, paramIndex );
 961       paramIndex2paramToken.put( paramIndex, p_i );
 962
 963       TokenTuple p_i_star = new TokenTuple( hrnParam.getID(),
 964                                             true,
 965                                             TokenTuple.ARITY_MANY ).makeCanonical();
 966       paramTokenStar2paramIndex.put( p_i_star, paramIndex );
 967       paramIndex2paramTokenStar.put( paramIndex, p_i_star );
 968
 969       // now depending on whether the callee is static or not
 970       // we need to account for a "this" argument in order to
 971       // find the matching argument in the caller context
 972       TempDescriptor argTemp_i;
 973       if( isStatic ) {
 974         argTemp_i = fc.getArg( paramIndex );
 975       } else {
 976         if( paramIndex == 0 ) {
 977           argTemp_i = fc.getThis();
 978         } else {
 979           argTemp_i = fc.getArg( paramIndex - 1 );
 980         }
 981       }
 982
 983       // in non-static methods there is a "this" pointer
 984       // that should be taken into account
 985       if( isStatic ) {
 986         assert fc.numArgs()     == fm.numParameters();
 987       } else {
 988         assert fc.numArgs() + 1 == fm.numParameters();
 989       }
 990
 991       LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
 992       paramIndex2ln.put( paramIndex, argLabel_i );
 993
 994       ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
 995       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
 996       while( edgeItr.hasNext() ) {
 997         ReferenceEdge edge = edgeItr.next();
 998         D_i = D_i.union( edge.getBeta() );
 999       }
1000       paramIndex2rewriteD.put( paramIndex, D_i );
1001     }
1002
1003
1004     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1005     while( lnArgItr.hasNext() ) {
1006       Map.Entry me      = (Map.Entry) lnArgItr.next();
1007       Integer   index   = (Integer)   me.getKey();
1008       LabelNode lnArg_i = (LabelNode) me.getValue();
1009
1010       // rewrite alpha for the nodes reachable from argument label i
1011       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1012       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1013
1014       // to find all reachable nodes, start with label referencees
1015       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1016       while( edgeArgItr.hasNext() ) {
1017         ReferenceEdge edge = edgeArgItr.next();
1018         todoNodes.add( edge.getDst() );
1019       }
1020
1021       // then follow links until all reachable nodes have been found
1022       while( !todoNodes.isEmpty() ) {
1023         HeapRegionNode hrn = todoNodes.iterator().next();
1024         todoNodes.remove( hrn );
1025         reachableNodes.add( hrn );
1026
1027         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1028         while( edgeItr.hasNext() ) {
1029           ReferenceEdge edge = edgeItr.next();
1030
1031           if( !reachableNodes.contains( edge.getDst() ) ) {
1032             todoNodes.add( edge.getDst() );
1033           }
1034         }
1035       }
1036
1037       // now iterate over reachable nodes to update their alpha, and
1038       // classify edges found as "argument reachable" or "upstream"
1039       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1040       while( hrnItr.hasNext() ) {
1041         HeapRegionNode hrn = hrnItr.next();
1042
1043         rewriteCallerNodeAlpha( index,
1044                                 hrn,
1045                                 paramIndex2rewriteH,
1046                                 paramIndex2rewriteD,
1047                                 paramIndex2paramToken,
1048                                 paramTokenStar2paramIndex );
1049       }
1050     }
1051
1052
1053
1054
1055
1056     /*
1057     // make a change set to translate callee tokens into caller tokens
1058     ChangeTupleSet C = new ChangeTupleSet().makeCanonical();
1059
1060     for( int i = 0; i < fm.numParameters(); ++i ) {
1061
1062       Integer paramIndex = new Integer( i );
1063
1064       System.out.println( "In method "+fm+ " on param "+paramIndex );
1065
1066       assert ogCallee.paramIndex2id.containsKey( paramIndex );
1067       Integer idParam = ogCallee.paramIndex2id.get( paramIndex );
1068
1069       assert ogCallee.id2hrn.containsKey( idParam );
1070       HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
1071       assert hrnParam != null;
1072
1073       TokenTupleSet calleeTokenToMatch =
1074         new TokenTupleSet( new TokenTuple( hrnParam ) ).makeCanonical();
1075
1076
1077       // now depending on whether the callee is static or not
1078       // we need to account for a "this" argument in order to
1079       // find the matching argument in the caller context
1080       TempDescriptor argTemp;
1081       if( isStatic ) {
1082         argTemp = fc.getArg( paramIndex );
1083       } else {
1084         if( paramIndex == 0 ) {
1085           argTemp = fc.getThis();
1086         } else {
1087           argTemp = fc.getArg( paramIndex - 1 );
1088         }
1089       }
1090
1091       LabelNode argLabel = getLabelNodeFromTemp( argTemp );
1092       Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
1093       while( argHeapRegionsItr.hasNext() ) {
1094         Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
1095         HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
1096         ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
1097
1098         Iterator<TokenTupleSet> ttsItr = repArg.getBeta().iterator();
1099         while( ttsItr.hasNext() ) {
1100           TokenTupleSet callerTokensToReplace = ttsItr.next();
1101
1102           ChangeTuple ct = new ChangeTuple( calleeTokenToMatch,
1103                                             callerTokensToReplace ).makeCanonical();
1104
1105           C = C.union( ct );
1106         }
1107       }
1108     }
1109     */
1110
1111     /*
1112     System.out.println( "Applying method call "+fm );
1113     System.out.println( "  Change: "+C );
1114
1115
1116     // the heap regions represented by the arguments (caller graph)
1117     // and heap regions for the parameters (callee graph)
1118     // don't correspond to each other by heap region ID.  In fact,
1119     // an argument label node can be referencing several heap regions
1120     // so the parameter label always references a multiple-object
1121     // heap region in order to handle the range of possible contexts
1122     // for a method call.  This means we need to make a special mapping
1123     // of argument->parameter regions in order to update the caller graph
1124
1125     // for every heap region->heap region edge in the
1126     // callee graph, create the matching edge or edges
1127     // in the caller graph
1128     Set      sCallee = ogCallee.id2hrn.entrySet();
1129     Iterator iCallee = sCallee.iterator();
1130     while( iCallee.hasNext() ) {
1131       Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
1132       Integer        idCallee  = (Integer)        meCallee.getKey();
1133       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1134
1135       HeapRegionNode hrnChildCallee = null;
1136       Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
1137       while( heapRegionsItrCallee.hasNext() ) {
1138         Map.Entry me                 = (Map.Entry)               heapRegionsItrCallee.next();
1139         hrnChildCallee               = (HeapRegionNode)          me.getKey();
1140         ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
1141
1142         Integer idChildCallee = hrnChildCallee.getID();
1143
1144         // only address this edge if it is not a special reflexive edge
1145         if( !repC.isInitialParamReflexive() ) {
1146
1147           // now we know that in the callee method's ownership graph
1148           // there is a heap region->heap region reference edge given
1149           // by heap region pointers:
1150           // hrnCallee -> heapChildCallee
1151           //
1152           // or by the ownership-graph independent ID's:
1153           // idCallee -> idChildCallee
1154           //
1155           // So now make a set of possible source heaps in the caller graph
1156           // and a set of destination heaps in the caller graph, and make
1157           // a reference edge in the caller for every possible (src,dst) pair
1158           HashSet<HeapRegionNode> possibleCallerSrcs =
1159             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1160                                                  idCallee,
1161                                                  fc,
1162                                                  isStatic );
1163
1164           HashSet<HeapRegionNode> possibleCallerDsts =
1165             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1166                                                  idChildCallee,
1167                                                  fc,
1168                                                  isStatic );
1169
1170           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1171           Iterator srcItr = possibleCallerSrcs.iterator();
1172           while( srcItr.hasNext() ) {
1173             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1174
1175             Iterator dstItr = possibleCallerDsts.iterator();
1176             while( dstItr.hasNext() ) {
1177               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1178
1179               addReferenceEdge( src, dst, repC.copy() );
1180             }
1181           }
1182         }
1183       }
1184     }
1185     */
1186   }
1187
1188
1189   private void rewriteCallerNodeAlpha( Integer paramIndex,
1190                                        HeapRegionNode hrn,
1191                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1192                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1193                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1194                                        Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex ) {
1195
1196     ReachabilitySet rules = paramIndex2rewriteH.get( paramIndex );
1197     assert rules != null;
1198
1199     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1200     assert tokenToRewrite != null;
1201
1202     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1203
1204     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1205     while( ttsItr.hasNext() ) {
1206       TokenTupleSet tts = ttsItr.next();
1207       r0 = r0.union( tts.rewrite( tokenToRewrite, hrn.getAlpha() ) );
1208     }
1209
1210     //ReachabilitySet r1 = D( r0 );
1211
1212     hrn.setAlphaNew( r0 );
1213   }
1214
1215
1216
1217
1218   /*
1219      private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
1220                                                                        Integer        idCallee,
1221                                                                        FlatCall       fc,
1222                                                                        boolean        isStatic ) {
1223
1224       HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1225
1226       if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
1227           // the heap region that is part of this
1228           // reference edge won't have a matching ID in the
1229           // caller graph because it is specifically allocated
1230           // for a particular parameter.  Use that information
1231           // to find the corresponding argument label in the
1232           // caller in order to create the proper reference edge
1233           // or edges.
1234           assert !id2hrn.containsKey( idCallee );
1235
1236           Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
1237           TempDescriptor argTemp;
1238
1239           // now depending on whether the callee is static or not
1240           // we need to account for a "this" argument in order to
1241           // find the matching argument in the caller context
1242           if( isStatic ) {
1243               argTemp = fc.getArg( paramIndex );
1244           } else {
1245               if( paramIndex == 0 ) {
1246                   argTemp = fc.getThis();
1247               } else {
1248                   argTemp = fc.getArg( paramIndex - 1 );
1249               }
1250           }
1251
1252           LabelNode argLabel = getLabelNodeFromTemp( argTemp );
1253           Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
1254           while( argHeapRegionsItr.hasNext() ) {
1255               Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
1256               HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
1257               ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
1258
1259               possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
1260           }
1261
1262       } else {
1263           // this heap region is not a parameter, so it should
1264           // have a matching heap region in the caller graph
1265           assert id2hrn.containsKey( idCallee );
1266           possibleCallerHRNs.add( id2hrn.get( idCallee ) );
1267       }
1268
1269       return possibleCallerHRNs;
1270      }
1271    */
1272
1273
1274   ////////////////////////////////////////////////////
1275   // in merge() and equals() methods the suffix A
1276   // represents the passed in graph and the suffix
1277   // B refers to the graph in this object
1278   // Merging means to take the incoming graph A and
1279   // merge it into B, so after the operation graph B
1280   // is the final result.
1281   ////////////////////////////////////////////////////
1282   public void merge(OwnershipGraph og) {
1283
1284     if( og == null ) {
1285       return;
1286     }
1287
1288     mergeOwnershipNodes(og);
1289     mergeReferenceEdges(og);
1290     mergeId2paramIndex(og);
1291     mergeAllocationSites(og);
1292   }
1293
1294
1295   protected void mergeOwnershipNodes(OwnershipGraph og) {
1296     Set sA = og.id2hrn.entrySet();
1297     Iterator iA = sA.iterator();
1298     while( iA.hasNext() ) {
1299       Map.Entry meA  = (Map.Entry)iA.next();
1300       Integer idA  = (Integer)        meA.getKey();
1301       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1302
1303       // if this graph doesn't have a node the
1304       // incoming graph has, allocate it
1305       if( !id2hrn.containsKey(idA) ) {
1306         HeapRegionNode hrnB = hrnA.copy();
1307         id2hrn.put(idA, hrnB);
1308
1309       } else {
1310         // otherwise this is a node present in both graphs
1311         // so make the new reachability set a union of the
1312         // nodes' reachability sets
1313         HeapRegionNode hrnB = id2hrn.get(idA);
1314         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1315       }
1316     }
1317
1318     // now add any label nodes that are in graph B but
1319     // not in A
1320     sA = og.td2ln.entrySet();
1321     iA = sA.iterator();
1322     while( iA.hasNext() ) {
1323       Map.Entry meA = (Map.Entry)iA.next();
1324       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1325       LabelNode lnA = (LabelNode)      meA.getValue();
1326
1327       // if the label doesn't exist in B, allocate and add it
1328       LabelNode lnB = getLabelNodeFromTemp(tdA);
1329     }
1330   }
1331
1332   protected void mergeReferenceEdges(OwnershipGraph og) {
1333
1334     // heap regions
1335     Set sA = og.id2hrn.entrySet();
1336     Iterator iA = sA.iterator();
1337     while( iA.hasNext() ) {
1338       Map.Entry meA  = (Map.Entry)iA.next();
1339       Integer idA  = (Integer)        meA.getKey();
1340       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1341
1342       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1343       while( heapRegionsItrA.hasNext() ) {
1344         ReferenceEdge edgeA     = heapRegionsItrA.next();
1345         HeapRegionNode hrnChildA = edgeA.getDst();
1346         Integer idChildA  = hrnChildA.getID();
1347
1348         // at this point we know an edge in graph A exists
1349         // idA -> idChildA, does this exist in B?
1350         assert id2hrn.containsKey(idA);
1351         HeapRegionNode hrnB        = id2hrn.get(idA);
1352         ReferenceEdge edgeToMerge = null;
1353
1354         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1355         while( heapRegionsItrB.hasNext() &&
1356                edgeToMerge == null          ) {
1357
1358           ReferenceEdge edgeB     = heapRegionsItrB.next();
1359           HeapRegionNode hrnChildB = edgeB.getDst();
1360           Integer idChildB  = hrnChildB.getID();
1361
1362           // don't use the ReferenceEdge.equals() here because
1363           // we're talking about existence between graphs
1364           if( idChildB.equals(idChildA) &&
1365               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1366             edgeToMerge = edgeB;
1367           }
1368         }
1369
1370         // if the edge from A was not found in B,
1371         // add it to B.
1372         if( edgeToMerge == null ) {
1373           assert id2hrn.containsKey(idChildA);
1374           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1375           edgeToMerge = edgeA.copy();
1376           edgeToMerge.setSrc(hrnB);
1377           edgeToMerge.setDst(hrnChildB);
1378           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1379         }
1380         // otherwise, the edge already existed in both graphs
1381         // so merge their reachability sets
1382         else {
1383           // just replace this beta set with the union
1384           assert edgeToMerge != null;
1385           edgeToMerge.setBeta(
1386             edgeToMerge.getBeta().union(edgeA.getBeta() )
1387             );
1388           if( !edgeA.isInitialParamReflexive() ) {
1389             edgeToMerge.setIsInitialParamReflexive(false);
1390           }
1391         }
1392       }
1393     }
1394
1395     // and then again with label nodes
1396     sA = og.td2ln.entrySet();
1397     iA = sA.iterator();
1398     while( iA.hasNext() ) {
1399       Map.Entry meA = (Map.Entry)iA.next();
1400       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1401       LabelNode lnA = (LabelNode)      meA.getValue();
1402
1403       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1404       while( heapRegionsItrA.hasNext() ) {
1405         ReferenceEdge edgeA     = heapRegionsItrA.next();
1406         HeapRegionNode hrnChildA = edgeA.getDst();
1407         Integer idChildA  = hrnChildA.getID();
1408
1409         // at this point we know an edge in graph A exists
1410         // tdA -> idChildA, does this exist in B?
1411         assert td2ln.containsKey(tdA);
1412         LabelNode lnB         = td2ln.get(tdA);
1413         ReferenceEdge edgeToMerge = null;
1414
1415         // labels never have edges with a field
1416         //assert edgeA.getFieldDesc() == null;
1417
1418         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1419         while( heapRegionsItrB.hasNext() &&
1420                edgeToMerge == null          ) {
1421
1422           ReferenceEdge edgeB     = heapRegionsItrB.next();
1423           HeapRegionNode hrnChildB = edgeB.getDst();
1424           Integer idChildB  = hrnChildB.getID();
1425
1426           // labels never have edges with a field
1427           //assert edgeB.getFieldDesc() == null;
1428
1429           // don't use the ReferenceEdge.equals() here because
1430           // we're talking about existence between graphs
1431           if( idChildB.equals(idChildA) &&
1432               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1433             edgeToMerge = edgeB;
1434           }
1435         }
1436
1437         // if the edge from A was not found in B,
1438         // add it to B.
1439         if( edgeToMerge == null ) {
1440           assert id2hrn.containsKey(idChildA);
1441           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1442           edgeToMerge = edgeA.copy();
1443           edgeToMerge.setSrc(lnB);
1444           edgeToMerge.setDst(hrnChildB);
1445           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1446         }
1447         // otherwise, the edge already existed in both graphs
1448         // so merge their reachability sets
1449         else {
1450           // just replace this beta set with the union
1451           edgeToMerge.setBeta(
1452             edgeToMerge.getBeta().union(edgeA.getBeta() )
1453             );
1454           if( !edgeA.isInitialParamReflexive() ) {
1455             edgeToMerge.setIsInitialParamReflexive(false);
1456           }
1457         }
1458       }
1459     }
1460   }
1461
1462   // you should only merge ownership graphs that have the
1463   // same number of parameters, or if one or both parameter
1464   // index tables are empty
1465   protected void mergeId2paramIndex(OwnershipGraph og) {
1466     if( id2paramIndex.size() == 0 ) {
1467       id2paramIndex  = og.id2paramIndex;
1468       paramIndex2id  = og.paramIndex2id;
1469       paramIndex2tdQ = og.paramIndex2tdQ;
1470       return;
1471     }
1472
1473     if( og.id2paramIndex.size() == 0 ) {
1474       return;
1475     }
1476
1477     assert id2paramIndex.size() == og.id2paramIndex.size();
1478   }
1479
1480   protected void mergeAllocationSites(OwnershipGraph og) {
1481     allocationSites.addAll(og.allocationSites);
1482   }
1483
1484
1485
1486   // it is necessary in the equals() member functions
1487   // to "check both ways" when comparing the data
1488   // structures of two graphs.  For instance, if all
1489   // edges between heap region nodes in graph A are
1490   // present and equal in graph B it is not sufficient
1491   // to say the graphs are equal.  Consider that there
1492   // may be edges in graph B that are not in graph A.
1493   // the only way to know that all edges in both graphs
1494   // are equally present is to iterate over both data
1495   // structures and compare against the other graph.
1496   public boolean equals(OwnershipGraph og) {
1497
1498     if( og == null ) {
1499       return false;
1500     }
1501
1502     if( !areHeapRegionNodesEqual(og) ) {
1503       return false;
1504     }
1505
1506     if( !areLabelNodesEqual(og) ) {
1507       return false;
1508     }
1509
1510     if( !areReferenceEdgesEqual(og) ) {
1511       return false;
1512     }
1513
1514     if( !areId2paramIndexEqual(og) ) {
1515       return false;
1516     }
1517
1518     // if everything is equal up to this point,
1519     // assert that allocationSites is also equal--
1520     // this data is redundant and kept for efficiency
1521     assert allocationSites.equals(og.allocationSites);
1522
1523     return true;
1524   }
1525
1526   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
1527
1528     if( !areallHRNinAalsoinBandequal(this, og) ) {
1529       return false;
1530     }
1531
1532     if( !areallHRNinAalsoinBandequal(og, this) ) {
1533       return false;
1534     }
1535
1536     return true;
1537   }
1538
1539   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
1540                                                        OwnershipGraph ogB) {
1541     Set sA = ogA.id2hrn.entrySet();
1542     Iterator iA = sA.iterator();
1543     while( iA.hasNext() ) {
1544       Map.Entry meA  = (Map.Entry)iA.next();
1545       Integer idA  = (Integer)        meA.getKey();
1546       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1547
1548       if( !ogB.id2hrn.containsKey(idA) ) {
1549         return false;
1550       }
1551
1552       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1553       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
1554         return false;
1555       }
1556     }
1557
1558     return true;
1559   }
1560
1561
1562   protected boolean areLabelNodesEqual(OwnershipGraph og) {
1563
1564     if( !areallLNinAalsoinBandequal(this, og) ) {
1565       return false;
1566     }
1567
1568     if( !areallLNinAalsoinBandequal(og, this) ) {
1569       return false;
1570     }
1571
1572     return true;
1573   }
1574
1575   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
1576                                                       OwnershipGraph ogB) {
1577     Set sA = ogA.td2ln.entrySet();
1578     Iterator iA = sA.iterator();
1579     while( iA.hasNext() ) {
1580       Map.Entry meA = (Map.Entry)iA.next();
1581       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1582
1583       if( !ogB.td2ln.containsKey(tdA) ) {
1584         return false;
1585       }
1586     }
1587
1588     return true;
1589   }
1590
1591
1592   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
1593     if( !areallREinAandBequal(this, og) ) {
1594       return false;
1595     }
1596
1597     return true;
1598   }
1599
1600   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
1601                                                 OwnershipGraph ogB) {
1602
1603     // check all the heap region->heap region edges
1604     Set sA = ogA.id2hrn.entrySet();
1605     Iterator iA = sA.iterator();
1606     while( iA.hasNext() ) {
1607       Map.Entry meA  = (Map.Entry)iA.next();
1608       Integer idA  = (Integer)        meA.getKey();
1609       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1610
1611       // we should have already checked that the same
1612       // heap regions exist in both graphs
1613       assert ogB.id2hrn.containsKey(idA);
1614
1615       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
1616         return false;
1617       }
1618
1619       // then check every edge in B for presence in A, starting
1620       // from the same parent HeapRegionNode
1621       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1622
1623       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
1624         return false;
1625       }
1626     }
1627
1628     // then check all the label->heap region edges
1629     sA = ogA.td2ln.entrySet();
1630     iA = sA.iterator();
1631     while( iA.hasNext() ) {
1632       Map.Entry meA = (Map.Entry)iA.next();
1633       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1634       LabelNode lnA = (LabelNode)      meA.getValue();
1635
1636       // we should have already checked that the same
1637       // label nodes exist in both graphs
1638       assert ogB.td2ln.containsKey(tdA);
1639
1640       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
1641         return false;
1642       }
1643
1644       // then check every edge in B for presence in A, starting
1645       // from the same parent LabelNode
1646       LabelNode lnB = ogB.td2ln.get(tdA);
1647
1648       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
1649         return false;
1650       }
1651     }
1652
1653     return true;
1654   }
1655
1656
1657   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
1658                                                  OwnershipNode onA,
1659                                                  OwnershipGraph ogB) {
1660
1661     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
1662     while( itrA.hasNext() ) {
1663       ReferenceEdge edgeA     = itrA.next();
1664       HeapRegionNode hrnChildA = edgeA.getDst();
1665       Integer idChildA  = hrnChildA.getID();
1666
1667       assert ogB.id2hrn.containsKey(idChildA);
1668
1669       // at this point we know an edge in graph A exists
1670       // onA -> idChildA, does this exact edge exist in B?
1671       boolean edgeFound = false;
1672
1673       OwnershipNode onB = null;
1674       if( onA instanceof HeapRegionNode ) {
1675         HeapRegionNode hrnA = (HeapRegionNode) onA;
1676         onB = ogB.id2hrn.get(hrnA.getID() );
1677       } else {
1678         LabelNode lnA = (LabelNode) onA;
1679         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
1680       }
1681
1682       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
1683       while( itrB.hasNext() ) {
1684         ReferenceEdge edgeB     = itrB.next();
1685         HeapRegionNode hrnChildB = edgeB.getDst();
1686         Integer idChildB  = hrnChildB.getID();
1687
1688         if( idChildA.equals(idChildB) &&
1689             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
1690
1691           // there is an edge in the right place with the right field,
1692           // but do they have the same attributes?
1693           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
1694
1695             edgeFound = true;
1696             //} else {
1697             //return false;
1698           }
1699         }
1700       }
1701
1702       if( !edgeFound ) {
1703         return false;
1704       }
1705     }
1706
1707     return true;
1708   }
1709
1710
1711   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
1712     return id2paramIndex.size() == og.id2paramIndex.size();
1713   }
1714
1715
1716   /*
1717      // given a set B of heap region node ID's, return the set of heap
1718      // region node ID's that is reachable from B
1719      public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1720
1721       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1722       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1723
1724       // initial nodes to visit are from set B
1725       Iterator initialItr = idSetB.iterator();
1726       while( initialItr.hasNext() ) {
1727           Integer idInitial = (Integer) initialItr.next();
1728           assert id2hrn.contains( idInitial );
1729           HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1730           toVisit.add( hrnInitial );
1731       }
1732
1733       HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1734
1735       // do a heap traversal
1736       while( !toVisit.isEmpty() ) {
1737           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1738           toVisit.remove( hrnVisited );
1739           visited.add   ( hrnVisited );
1740
1741           // for every node visited, add it to the total
1742           // reachable set
1743           idSetReachableFromB.add( hrnVisited.getID() );
1744
1745           // find other reachable nodes
1746           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1747           while( referenceeItr.hasNext() ) {
1748               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1749               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1750               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1751
1752               if( !visited.contains( hrnReferencee ) ) {
1753                   toVisit.add( hrnReferencee );
1754               }
1755           }
1756       }
1757
1758       return idSetReachableFromB;
1759      }
1760
1761
1762      // used to find if a heap region can possibly have a reference to
1763      // any of the heap regions in the given set
1764      // if the id supplied is in the set, then a self-referencing edge
1765      // would return true, but that special case is specifically allowed
1766      // meaning that it isn't an external alias
1767      public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1768
1769       assert id2hrn.contains( id );
1770       HeapRegionNode hrn = id2hrn.get( id );
1771
1772
1773       //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1774
1775       //Iterator i = idSet.iterator();
1776       //while( i.hasNext() ) {
1777       //    Integer idFromSet = (Integer) i.next();
1778       //   assert id2hrn.contains( idFromSet );
1779       //    hrnSet.add( id2hrn.get( idFromSet ) );
1780       //}
1781
1782
1783       // do a traversal from hrn and see if any of the
1784       // heap regions from the set come up during that
1785       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1786       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1787
1788       toVisit.add( hrn );
1789       while( !toVisit.isEmpty() ) {
1790           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1791           toVisit.remove( hrnVisited );
1792           visited.add   ( hrnVisited );
1793
1794           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1795           while( referenceeItr.hasNext() ) {
1796               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1797               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1798               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1799
1800               if( idSet.contains( hrnReferencee.getID() ) ) {
1801                   if( !id.equals( hrnReferencee.getID() ) ) {
1802                       return true;
1803                   }
1804               }
1805
1806               if( !visited.contains( hrnReferencee ) ) {
1807                   toVisit.add( hrnReferencee );
1808               }
1809           }
1810       }
1811
1812       return false;
1813      }
1814    */
1815
1816
1817   // for writing ownership graphs to dot files
1818   public void writeGraph(Descriptor methodDesc,
1819                          FlatNode fn,
1820                          boolean writeLabels,
1821                          boolean labelSelect,
1822                          boolean pruneGarbage,
1823                          boolean writeReferencers
1824                          ) throws java.io.IOException {
1825     writeGraph(
1826       methodDesc.getSymbol() +
1827       methodDesc.getNum() +
1828       fn.toString(),
1829       writeLabels,
1830       labelSelect,
1831       pruneGarbage,
1832       writeReferencers
1833       );
1834   }
1835
1836   public void writeGraph(Descriptor methodDesc,
1837                          FlatNode fn,
1838                          boolean writeLabels,
1839                          boolean writeReferencers
1840                          ) throws java.io.IOException {
1841     writeGraph(
1842       methodDesc.getSymbol() +
1843       methodDesc.getNum() +
1844       fn.toString(),
1845       writeLabels,
1846       false,
1847       false,
1848       writeReferencers
1849       );
1850   }
1851
1852   public void writeGraph(Descriptor methodDesc,
1853                          boolean writeLabels,
1854                          boolean writeReferencers
1855                          ) throws java.io.IOException {
1856     writeGraph(
1857       methodDesc.getSymbol() +
1858       methodDesc.getNum() +
1859       "COMPLETE",
1860       writeLabels,
1861       false,
1862       false,
1863       writeReferencers
1864       );
1865   }
1866
1867   public void writeGraph(Descriptor methodDesc,
1868                          boolean writeLabels,
1869                          boolean labelSelect,
1870                          boolean pruneGarbage,
1871                          boolean writeReferencers
1872                          ) throws java.io.IOException {
1873     writeGraph(
1874       methodDesc.getSymbol() +
1875       methodDesc.getNum() +
1876       "COMPLETE",
1877       writeLabels,
1878       labelSelect,
1879       pruneGarbage,
1880       writeReferencers
1881       );
1882   }
1883
1884   public void writeGraph(String graphName,
1885                          boolean writeLabels,
1886                          boolean labelSelect,
1887                          boolean pruneGarbage,
1888                          boolean writeReferencers
1889                          ) throws java.io.IOException {
1890
1891     // remove all non-word characters from the graph name so
1892     // the filename and identifier in dot don't cause errors
1893     graphName = graphName.replaceAll("[\\W]", "");
1894
1895     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
1896     bw.write("digraph "+graphName+" {\n");
1897     //bw.write( "  size=\"7.5,10\";\n" );
1898
1899     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1900
1901     // then visit every heap region node
1902     if( !pruneGarbage ) {
1903       Set s = id2hrn.entrySet();
1904       Iterator i = s.iterator();
1905       while( i.hasNext() ) {
1906         Map.Entry me  = (Map.Entry)i.next();
1907         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1908         if( !visited.contains(hrn) ) {
1909           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
1910                                   hrn,
1911                                   bw,
1912                                   null,
1913                                   visited,
1914                                   writeReferencers);
1915         }
1916       }
1917     }
1918
1919     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
1920
1921
1922     // then visit every label node, useful for debugging
1923     if( writeLabels ) {
1924       Set s = td2ln.entrySet();
1925       Iterator i = s.iterator();
1926       while( i.hasNext() ) {
1927         Map.Entry me = (Map.Entry)i.next();
1928         LabelNode ln = (LabelNode) me.getValue();
1929
1930         if( labelSelect ) {
1931           String labelStr = ln.getTempDescriptorString();
1932           if( labelStr.startsWith("___temp") ||
1933               labelStr.startsWith("___dst") ||
1934               labelStr.startsWith("___srctmp") ||
1935               labelStr.startsWith("___neverused")   ) {
1936             continue;
1937           }
1938         }
1939
1940         bw.write(ln.toString() + ";\n");
1941
1942         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
1943         while( heapRegionsItr.hasNext() ) {
1944           ReferenceEdge edge = heapRegionsItr.next();
1945           HeapRegionNode hrn  = edge.getDst();
1946
1947           if( pruneGarbage && !visited.contains(hrn) ) {
1948             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
1949                                     hrn,
1950                                     bw,
1951                                     null,
1952                                     visited,
1953                                     writeReferencers);
1954           }
1955
1956           bw.write("  "        + ln.toString() +
1957                    " -> "      + hrn.toString() +
1958                    "[label=\"" + edge.toGraphEdgeString() +
1959                    "\",decorate];\n");
1960         }
1961       }
1962     }
1963
1964
1965     bw.write("}\n");
1966     bw.close();
1967   }
1968
1969   protected void traverseHeapRegionNodes(int mode,
1970                                          HeapRegionNode hrn,
1971                                          BufferedWriter bw,
1972                                          TempDescriptor td,
1973                                          HashSet<HeapRegionNode> visited,
1974                                          boolean writeReferencers
1975                                          ) throws java.io.IOException {
1976
1977     if( visited.contains(hrn) ) {
1978       return;
1979     }
1980     visited.add(hrn);
1981
1982     switch( mode ) {
1983     case VISIT_HRN_WRITE_FULL:
1984
1985       String attributes = "[";
1986
1987       if( hrn.isSingleObject() ) {
1988         attributes += "shape=box";
1989       } else {
1990         attributes += "shape=Msquare";
1991       }
1992
1993       if( hrn.isFlagged() ) {
1994         attributes += ",style=filled,fillcolor=lightgrey";
1995       }
1996
1997       attributes += ",label=\"ID"        +
1998                     hrn.getID()          +
1999                     "\\n"                +
2000                     hrn.getDescription() +
2001                     "\\n"                +
2002                     hrn.getAlphaString() +
2003                     "\"]";
2004
2005       bw.write("  " + hrn.toString() + attributes + ";\n");
2006       break;
2007     }
2008
2009
2010     // useful for debugging
2011     if( writeReferencers ) {
2012       OwnershipNode onRef  = null;
2013       Iterator refItr = hrn.iteratorToReferencers();
2014       while( refItr.hasNext() ) {
2015         onRef = (OwnershipNode) refItr.next();
2016
2017         switch( mode ) {
2018         case VISIT_HRN_WRITE_FULL:
2019           bw.write("  "                    + hrn.toString() +
2020                    " -> "                  + onRef.toString() +
2021                    "[color=lightgray];\n");
2022           break;
2023         }
2024       }
2025     }
2026
2027     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2028     while( childRegionsItr.hasNext() ) {
2029       ReferenceEdge edge     = childRegionsItr.next();
2030       HeapRegionNode hrnChild = edge.getDst();
2031
2032       switch( mode ) {
2033       case VISIT_HRN_WRITE_FULL:
2034         bw.write("  "        + hrn.toString() +
2035                  " -> "      + hrnChild.toString() +
2036                  "[label=\"" + edge.toGraphEdgeString() +
2037                  "\",decorate];\n");
2038         break;
2039       }
2040
2041       traverseHeapRegionNodes(mode,
2042                               hrnChild,
2043                               bw,
2044                               td,
2045                               visited,
2046                               writeReferencers);
2047     }
2048   }
2049 }