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     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1005
1006     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1007     while( lnArgItr.hasNext() ) {
1008       Map.Entry me      = (Map.Entry) lnArgItr.next();
1009       Integer   index   = (Integer)   me.getKey();
1010       LabelNode lnArg_i = (LabelNode) me.getValue();
1011
1012       // rewrite alpha for the nodes reachable from argument label i
1013       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1014       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1015
1016       // to find all reachable nodes, start with label referencees
1017       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1018       while( edgeArgItr.hasNext() ) {
1019         ReferenceEdge edge = edgeArgItr.next();
1020         todoNodes.add( edge.getDst() );
1021       }
1022
1023       // then follow links until all reachable nodes have been found
1024       while( !todoNodes.isEmpty() ) {
1025         HeapRegionNode hrn = todoNodes.iterator().next();
1026         todoNodes.remove( hrn );
1027         reachableNodes.add( hrn );
1028
1029         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1030         while( edgeItr.hasNext() ) {
1031           ReferenceEdge edge = edgeItr.next();
1032
1033           if( !reachableNodes.contains( edge.getDst() ) ) {
1034             todoNodes.add( edge.getDst() );
1035           }
1036         }
1037       }
1038
1039       // now iterate over reachable nodes to update their alpha, and
1040       // classify edges found as "argument reachable" or "upstream"
1041       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1042       while( hrnItr.hasNext() ) {
1043         HeapRegionNode hrn = hrnItr.next();
1044
1045         rewriteCallerNodeAlpha( fm.numParameters(),
1046                                 index,
1047                                 hrn,
1048                                 paramIndex2rewriteH,
1049                                 paramIndex2rewriteD,
1050                                 paramIndex2paramToken,
1051                                 paramIndex2paramTokenStar );
1052
1053         nodesWithNewAlpha.add( hrn );
1054       }
1055     }
1056
1057
1058     // commit changes to alpha
1059     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1060     while( nodeItr.hasNext() ) {
1061       nodeItr.next().applyAlphaNew();
1062     }
1063
1064
1065
1066     /*
1067     System.out.println( "Applying method call "+fm );
1068     System.out.println( "  Change: "+C );
1069
1070
1071     // the heap regions represented by the arguments (caller graph)
1072     // and heap regions for the parameters (callee graph)
1073     // don't correspond to each other by heap region ID.  In fact,
1074     // an argument label node can be referencing several heap regions
1075     // so the parameter label always references a multiple-object
1076     // heap region in order to handle the range of possible contexts
1077     // for a method call.  This means we need to make a special mapping
1078     // of argument->parameter regions in order to update the caller graph
1079
1080     // for every heap region->heap region edge in the
1081     // callee graph, create the matching edge or edges
1082     // in the caller graph
1083     Set      sCallee = ogCallee.id2hrn.entrySet();
1084     Iterator iCallee = sCallee.iterator();
1085     while( iCallee.hasNext() ) {
1086       Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
1087       Integer        idCallee  = (Integer)        meCallee.getKey();
1088       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1089
1090       HeapRegionNode hrnChildCallee = null;
1091       Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
1092       while( heapRegionsItrCallee.hasNext() ) {
1093         Map.Entry me                 = (Map.Entry)               heapRegionsItrCallee.next();
1094         hrnChildCallee               = (HeapRegionNode)          me.getKey();
1095         ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
1096
1097         Integer idChildCallee = hrnChildCallee.getID();
1098
1099         // only address this edge if it is not a special reflexive edge
1100         if( !repC.isInitialParamReflexive() ) {
1101
1102           // now we know that in the callee method's ownership graph
1103           // there is a heap region->heap region reference edge given
1104           // by heap region pointers:
1105           // hrnCallee -> heapChildCallee
1106           //
1107           // or by the ownership-graph independent ID's:
1108           // idCallee -> idChildCallee
1109           //
1110           // So now make a set of possible source heaps in the caller graph
1111           // and a set of destination heaps in the caller graph, and make
1112           // a reference edge in the caller for every possible (src,dst) pair
1113           HashSet<HeapRegionNode> possibleCallerSrcs =
1114             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1115                                                  idCallee,
1116                                                  fc,
1117                                                  isStatic );
1118
1119           HashSet<HeapRegionNode> possibleCallerDsts =
1120             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1121                                                  idChildCallee,
1122                                                  fc,
1123                                                  isStatic );
1124
1125           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1126           Iterator srcItr = possibleCallerSrcs.iterator();
1127           while( srcItr.hasNext() ) {
1128             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1129
1130             Iterator dstItr = possibleCallerDsts.iterator();
1131             while( dstItr.hasNext() ) {
1132               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1133
1134               addReferenceEdge( src, dst, repC.copy() );
1135             }
1136           }
1137         }
1138       }
1139     }
1140     */
1141   }
1142
1143
1144   private void rewriteCallerNodeAlpha( int numParameters,
1145                                        Integer paramIndex,
1146                                        HeapRegionNode hrn,
1147                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1148                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1149                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1150                                        Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1151
1152     ReachabilitySet rules = paramIndex2rewriteH.get( paramIndex );
1153     assert rules != null;
1154
1155     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1156     assert tokenToRewrite != null;
1157
1158     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1159     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1160     while( ttsItr.hasNext() ) {
1161       TokenTupleSet tts = ttsItr.next();
1162       r0 = r0.union( tts.simpleRewriteToken( tokenToRewrite, hrn.getAlpha() ) );
1163     }
1164
1165     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1166     ttsItr = r0.iterator();
1167     while( ttsItr.hasNext() ) {
1168       TokenTupleSet tts = ttsItr.next();
1169       r1 = r1.union( rewriteDpass( numParameters,
1170                                    paramIndex,
1171                                    tts,
1172                                    paramIndex2rewriteD,
1173                                    paramIndex2paramToken,
1174                                    paramIndex2paramTokenStar ) );
1175     }
1176
1177     hrn.setAlphaNew( r1 );
1178   }
1179
1180
1181   private ReachabilitySet rewriteDpass( int numParameters,
1182                                         Integer paramIndex,
1183                                         TokenTupleSet ttsIn,
1184                                         Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1185                                         Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1186                                         Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1187
1188     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1189
1190     boolean rewritten = false;
1191
1192     for( int j = 0; j < numParameters; ++j ) {
1193       Integer paramIndexJ = new Integer( j );
1194       ReachabilitySet D_j = paramIndex2rewriteD.get( paramIndexJ );
1195       assert D_j != null;
1196
1197       if( paramIndexJ != paramIndex ) {
1198         TokenTuple tokenToRewriteJ = paramIndex2paramToken.get( paramIndexJ );
1199         assert tokenToRewriteJ != null;
1200         if( ttsIn.containsTuple( tokenToRewriteJ ) ) {
1201           ReachabilitySet r = ttsIn.exhaustiveRewriteToken( tokenToRewriteJ, D_j );
1202           Iterator<TokenTupleSet> ttsItr = r.iterator();
1203           while( ttsItr.hasNext() ) {
1204             TokenTupleSet tts = ttsItr.next();
1205             rsOut = rsOut.union( rewriteDpass( numParameters,
1206                                                paramIndex,
1207                                                tts,
1208                                                paramIndex2rewriteD,
1209                                                paramIndex2paramToken,
1210                                                paramIndex2paramTokenStar ) );
1211             rewritten = true;
1212           }
1213         }
1214       }
1215
1216       TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get( paramIndexJ );
1217       assert tokenStarToRewriteJ != null;
1218       if( ttsIn.containsTuple( tokenStarToRewriteJ ) ) {
1219         ReachabilitySet r = ttsIn.exhaustiveRewriteToken( tokenStarToRewriteJ, D_j );
1220         Iterator<TokenTupleSet> ttsItr = r.iterator();
1221         while( ttsItr.hasNext() ) {
1222           TokenTupleSet tts = ttsItr.next();
1223           rsOut = rsOut.union( rewriteDpass( numParameters,
1224                                              paramIndex,
1225                                              tts,
1226                                              paramIndex2rewriteD,
1227                                              paramIndex2paramToken,
1228                                              paramIndex2paramTokenStar ) );
1229           rewritten = true;
1230         }
1231       }
1232     }
1233
1234     if( !rewritten ) {
1235       rsOut = rsOut.union( ttsIn );
1236     }
1237
1238     return rsOut;
1239   }
1240
1241
1242   /*
1243      private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
1244                                                                        Integer        idCallee,
1245                                                                        FlatCall       fc,
1246                                                                        boolean        isStatic ) {
1247
1248       HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1249
1250       if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
1251           // the heap region that is part of this
1252           // reference edge won't have a matching ID in the
1253           // caller graph because it is specifically allocated
1254           // for a particular parameter.  Use that information
1255           // to find the corresponding argument label in the
1256           // caller in order to create the proper reference edge
1257           // or edges.
1258           assert !id2hrn.containsKey( idCallee );
1259
1260           Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
1261           TempDescriptor argTemp;
1262
1263           // now depending on whether the callee is static or not
1264           // we need to account for a "this" argument in order to
1265           // find the matching argument in the caller context
1266           if( isStatic ) {
1267               argTemp = fc.getArg( paramIndex );
1268           } else {
1269               if( paramIndex == 0 ) {
1270                   argTemp = fc.getThis();
1271               } else {
1272                   argTemp = fc.getArg( paramIndex - 1 );
1273               }
1274           }
1275
1276           LabelNode argLabel = getLabelNodeFromTemp( argTemp );
1277           Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
1278           while( argHeapRegionsItr.hasNext() ) {
1279               Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
1280               HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
1281               ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
1282
1283               possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
1284           }
1285
1286       } else {
1287           // this heap region is not a parameter, so it should
1288           // have a matching heap region in the caller graph
1289           assert id2hrn.containsKey( idCallee );
1290           possibleCallerHRNs.add( id2hrn.get( idCallee ) );
1291       }
1292
1293       return possibleCallerHRNs;
1294      }
1295    */
1296
1297
1298   ////////////////////////////////////////////////////
1299   // in merge() and equals() methods the suffix A
1300   // represents the passed in graph and the suffix
1301   // B refers to the graph in this object
1302   // Merging means to take the incoming graph A and
1303   // merge it into B, so after the operation graph B
1304   // is the final result.
1305   ////////////////////////////////////////////////////
1306   public void merge(OwnershipGraph og) {
1307
1308     if( og == null ) {
1309       return;
1310     }
1311
1312     mergeOwnershipNodes(og);
1313     mergeReferenceEdges(og);
1314     mergeId2paramIndex(og);
1315     mergeAllocationSites(og);
1316   }
1317
1318
1319   protected void mergeOwnershipNodes(OwnershipGraph og) {
1320     Set sA = og.id2hrn.entrySet();
1321     Iterator iA = sA.iterator();
1322     while( iA.hasNext() ) {
1323       Map.Entry meA  = (Map.Entry)iA.next();
1324       Integer idA  = (Integer)        meA.getKey();
1325       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1326
1327       // if this graph doesn't have a node the
1328       // incoming graph has, allocate it
1329       if( !id2hrn.containsKey(idA) ) {
1330         HeapRegionNode hrnB = hrnA.copy();
1331         id2hrn.put(idA, hrnB);
1332
1333       } else {
1334         // otherwise this is a node present in both graphs
1335         // so make the new reachability set a union of the
1336         // nodes' reachability sets
1337         HeapRegionNode hrnB = id2hrn.get(idA);
1338         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1339       }
1340     }
1341
1342     // now add any label nodes that are in graph B but
1343     // not in A
1344     sA = og.td2ln.entrySet();
1345     iA = sA.iterator();
1346     while( iA.hasNext() ) {
1347       Map.Entry meA = (Map.Entry)iA.next();
1348       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1349       LabelNode lnA = (LabelNode)      meA.getValue();
1350
1351       // if the label doesn't exist in B, allocate and add it
1352       LabelNode lnB = getLabelNodeFromTemp(tdA);
1353     }
1354   }
1355
1356   protected void mergeReferenceEdges(OwnershipGraph og) {
1357
1358     // heap regions
1359     Set sA = og.id2hrn.entrySet();
1360     Iterator iA = sA.iterator();
1361     while( iA.hasNext() ) {
1362       Map.Entry meA  = (Map.Entry)iA.next();
1363       Integer idA  = (Integer)        meA.getKey();
1364       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1365
1366       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1367       while( heapRegionsItrA.hasNext() ) {
1368         ReferenceEdge edgeA     = heapRegionsItrA.next();
1369         HeapRegionNode hrnChildA = edgeA.getDst();
1370         Integer idChildA  = hrnChildA.getID();
1371
1372         // at this point we know an edge in graph A exists
1373         // idA -> idChildA, does this exist in B?
1374         assert id2hrn.containsKey(idA);
1375         HeapRegionNode hrnB        = id2hrn.get(idA);
1376         ReferenceEdge edgeToMerge = null;
1377
1378         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1379         while( heapRegionsItrB.hasNext() &&
1380                edgeToMerge == null          ) {
1381
1382           ReferenceEdge edgeB     = heapRegionsItrB.next();
1383           HeapRegionNode hrnChildB = edgeB.getDst();
1384           Integer idChildB  = hrnChildB.getID();
1385
1386           // don't use the ReferenceEdge.equals() here because
1387           // we're talking about existence between graphs
1388           if( idChildB.equals(idChildA) &&
1389               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1390             edgeToMerge = edgeB;
1391           }
1392         }
1393
1394         // if the edge from A was not found in B,
1395         // add it to B.
1396         if( edgeToMerge == null ) {
1397           assert id2hrn.containsKey(idChildA);
1398           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1399           edgeToMerge = edgeA.copy();
1400           edgeToMerge.setSrc(hrnB);
1401           edgeToMerge.setDst(hrnChildB);
1402           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1403         }
1404         // otherwise, the edge already existed in both graphs
1405         // so merge their reachability sets
1406         else {
1407           // just replace this beta set with the union
1408           assert edgeToMerge != null;
1409           edgeToMerge.setBeta(
1410             edgeToMerge.getBeta().union(edgeA.getBeta() )
1411             );
1412           if( !edgeA.isInitialParamReflexive() ) {
1413             edgeToMerge.setIsInitialParamReflexive(false);
1414           }
1415         }
1416       }
1417     }
1418
1419     // and then again with label nodes
1420     sA = og.td2ln.entrySet();
1421     iA = sA.iterator();
1422     while( iA.hasNext() ) {
1423       Map.Entry meA = (Map.Entry)iA.next();
1424       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1425       LabelNode lnA = (LabelNode)      meA.getValue();
1426
1427       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1428       while( heapRegionsItrA.hasNext() ) {
1429         ReferenceEdge edgeA     = heapRegionsItrA.next();
1430         HeapRegionNode hrnChildA = edgeA.getDst();
1431         Integer idChildA  = hrnChildA.getID();
1432
1433         // at this point we know an edge in graph A exists
1434         // tdA -> idChildA, does this exist in B?
1435         assert td2ln.containsKey(tdA);
1436         LabelNode lnB         = td2ln.get(tdA);
1437         ReferenceEdge edgeToMerge = null;
1438
1439         // labels never have edges with a field
1440         //assert edgeA.getFieldDesc() == null;
1441
1442         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1443         while( heapRegionsItrB.hasNext() &&
1444                edgeToMerge == null          ) {
1445
1446           ReferenceEdge edgeB     = heapRegionsItrB.next();
1447           HeapRegionNode hrnChildB = edgeB.getDst();
1448           Integer idChildB  = hrnChildB.getID();
1449
1450           // labels never have edges with a field
1451           //assert edgeB.getFieldDesc() == null;
1452
1453           // don't use the ReferenceEdge.equals() here because
1454           // we're talking about existence between graphs
1455           if( idChildB.equals(idChildA) &&
1456               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1457             edgeToMerge = edgeB;
1458           }
1459         }
1460
1461         // if the edge from A was not found in B,
1462         // add it to B.
1463         if( edgeToMerge == null ) {
1464           assert id2hrn.containsKey(idChildA);
1465           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1466           edgeToMerge = edgeA.copy();
1467           edgeToMerge.setSrc(lnB);
1468           edgeToMerge.setDst(hrnChildB);
1469           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1470         }
1471         // otherwise, the edge already existed in both graphs
1472         // so merge their reachability sets
1473         else {
1474           // just replace this beta set with the union
1475           edgeToMerge.setBeta(
1476             edgeToMerge.getBeta().union(edgeA.getBeta() )
1477             );
1478           if( !edgeA.isInitialParamReflexive() ) {
1479             edgeToMerge.setIsInitialParamReflexive(false);
1480           }
1481         }
1482       }
1483     }
1484   }
1485
1486   // you should only merge ownership graphs that have the
1487   // same number of parameters, or if one or both parameter
1488   // index tables are empty
1489   protected void mergeId2paramIndex(OwnershipGraph og) {
1490     if( id2paramIndex.size() == 0 ) {
1491       id2paramIndex  = og.id2paramIndex;
1492       paramIndex2id  = og.paramIndex2id;
1493       paramIndex2tdQ = og.paramIndex2tdQ;
1494       return;
1495     }
1496
1497     if( og.id2paramIndex.size() == 0 ) {
1498       return;
1499     }
1500
1501     assert id2paramIndex.size() == og.id2paramIndex.size();
1502   }
1503
1504   protected void mergeAllocationSites(OwnershipGraph og) {
1505     allocationSites.addAll(og.allocationSites);
1506   }
1507
1508
1509
1510   // it is necessary in the equals() member functions
1511   // to "check both ways" when comparing the data
1512   // structures of two graphs.  For instance, if all
1513   // edges between heap region nodes in graph A are
1514   // present and equal in graph B it is not sufficient
1515   // to say the graphs are equal.  Consider that there
1516   // may be edges in graph B that are not in graph A.
1517   // the only way to know that all edges in both graphs
1518   // are equally present is to iterate over both data
1519   // structures and compare against the other graph.
1520   public boolean equals(OwnershipGraph og) {
1521
1522     if( og == null ) {
1523       return false;
1524     }
1525
1526     if( !areHeapRegionNodesEqual(og) ) {
1527       return false;
1528     }
1529
1530     if( !areLabelNodesEqual(og) ) {
1531       return false;
1532     }
1533
1534     if( !areReferenceEdgesEqual(og) ) {
1535       return false;
1536     }
1537
1538     if( !areId2paramIndexEqual(og) ) {
1539       return false;
1540     }
1541
1542     // if everything is equal up to this point,
1543     // assert that allocationSites is also equal--
1544     // this data is redundant and kept for efficiency
1545     assert allocationSites.equals(og.allocationSites);
1546
1547     return true;
1548   }
1549
1550   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
1551
1552     if( !areallHRNinAalsoinBandequal(this, og) ) {
1553       return false;
1554     }
1555
1556     if( !areallHRNinAalsoinBandequal(og, this) ) {
1557       return false;
1558     }
1559
1560     return true;
1561   }
1562
1563   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
1564                                                        OwnershipGraph ogB) {
1565     Set sA = ogA.id2hrn.entrySet();
1566     Iterator iA = sA.iterator();
1567     while( iA.hasNext() ) {
1568       Map.Entry meA  = (Map.Entry)iA.next();
1569       Integer idA  = (Integer)        meA.getKey();
1570       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1571
1572       if( !ogB.id2hrn.containsKey(idA) ) {
1573         return false;
1574       }
1575
1576       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1577       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
1578         return false;
1579       }
1580     }
1581
1582     return true;
1583   }
1584
1585
1586   protected boolean areLabelNodesEqual(OwnershipGraph og) {
1587
1588     if( !areallLNinAalsoinBandequal(this, og) ) {
1589       return false;
1590     }
1591
1592     if( !areallLNinAalsoinBandequal(og, this) ) {
1593       return false;
1594     }
1595
1596     return true;
1597   }
1598
1599   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
1600                                                       OwnershipGraph ogB) {
1601     Set sA = ogA.td2ln.entrySet();
1602     Iterator iA = sA.iterator();
1603     while( iA.hasNext() ) {
1604       Map.Entry meA = (Map.Entry)iA.next();
1605       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1606
1607       if( !ogB.td2ln.containsKey(tdA) ) {
1608         return false;
1609       }
1610     }
1611
1612     return true;
1613   }
1614
1615
1616   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
1617     if( !areallREinAandBequal(this, og) ) {
1618       return false;
1619     }
1620
1621     return true;
1622   }
1623
1624   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
1625                                                 OwnershipGraph ogB) {
1626
1627     // check all the heap region->heap region edges
1628     Set sA = ogA.id2hrn.entrySet();
1629     Iterator iA = sA.iterator();
1630     while( iA.hasNext() ) {
1631       Map.Entry meA  = (Map.Entry)iA.next();
1632       Integer idA  = (Integer)        meA.getKey();
1633       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1634
1635       // we should have already checked that the same
1636       // heap regions exist in both graphs
1637       assert ogB.id2hrn.containsKey(idA);
1638
1639       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
1640         return false;
1641       }
1642
1643       // then check every edge in B for presence in A, starting
1644       // from the same parent HeapRegionNode
1645       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1646
1647       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
1648         return false;
1649       }
1650     }
1651
1652     // then check all the label->heap region edges
1653     sA = ogA.td2ln.entrySet();
1654     iA = sA.iterator();
1655     while( iA.hasNext() ) {
1656       Map.Entry meA = (Map.Entry)iA.next();
1657       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1658       LabelNode lnA = (LabelNode)      meA.getValue();
1659
1660       // we should have already checked that the same
1661       // label nodes exist in both graphs
1662       assert ogB.td2ln.containsKey(tdA);
1663
1664       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
1665         return false;
1666       }
1667
1668       // then check every edge in B for presence in A, starting
1669       // from the same parent LabelNode
1670       LabelNode lnB = ogB.td2ln.get(tdA);
1671
1672       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
1673         return false;
1674       }
1675     }
1676
1677     return true;
1678   }
1679
1680
1681   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
1682                                                  OwnershipNode onA,
1683                                                  OwnershipGraph ogB) {
1684
1685     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
1686     while( itrA.hasNext() ) {
1687       ReferenceEdge edgeA     = itrA.next();
1688       HeapRegionNode hrnChildA = edgeA.getDst();
1689       Integer idChildA  = hrnChildA.getID();
1690
1691       assert ogB.id2hrn.containsKey(idChildA);
1692
1693       // at this point we know an edge in graph A exists
1694       // onA -> idChildA, does this exact edge exist in B?
1695       boolean edgeFound = false;
1696
1697       OwnershipNode onB = null;
1698       if( onA instanceof HeapRegionNode ) {
1699         HeapRegionNode hrnA = (HeapRegionNode) onA;
1700         onB = ogB.id2hrn.get(hrnA.getID() );
1701       } else {
1702         LabelNode lnA = (LabelNode) onA;
1703         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
1704       }
1705
1706       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
1707       while( itrB.hasNext() ) {
1708         ReferenceEdge edgeB     = itrB.next();
1709         HeapRegionNode hrnChildB = edgeB.getDst();
1710         Integer idChildB  = hrnChildB.getID();
1711
1712         if( idChildA.equals(idChildB) &&
1713             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
1714
1715           // there is an edge in the right place with the right field,
1716           // but do they have the same attributes?
1717           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
1718
1719             edgeFound = true;
1720             //} else {
1721             //return false;
1722           }
1723         }
1724       }
1725
1726       if( !edgeFound ) {
1727         return false;
1728       }
1729     }
1730
1731     return true;
1732   }
1733
1734
1735   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
1736     return id2paramIndex.size() == og.id2paramIndex.size();
1737   }
1738
1739
1740   /*
1741      // given a set B of heap region node ID's, return the set of heap
1742      // region node ID's that is reachable from B
1743      public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1744
1745       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1746       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1747
1748       // initial nodes to visit are from set B
1749       Iterator initialItr = idSetB.iterator();
1750       while( initialItr.hasNext() ) {
1751           Integer idInitial = (Integer) initialItr.next();
1752           assert id2hrn.contains( idInitial );
1753           HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1754           toVisit.add( hrnInitial );
1755       }
1756
1757       HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1758
1759       // do a heap traversal
1760       while( !toVisit.isEmpty() ) {
1761           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1762           toVisit.remove( hrnVisited );
1763           visited.add   ( hrnVisited );
1764
1765           // for every node visited, add it to the total
1766           // reachable set
1767           idSetReachableFromB.add( hrnVisited.getID() );
1768
1769           // find other reachable nodes
1770           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1771           while( referenceeItr.hasNext() ) {
1772               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1773               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1774               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1775
1776               if( !visited.contains( hrnReferencee ) ) {
1777                   toVisit.add( hrnReferencee );
1778               }
1779           }
1780       }
1781
1782       return idSetReachableFromB;
1783      }
1784
1785
1786      // used to find if a heap region can possibly have a reference to
1787      // any of the heap regions in the given set
1788      // if the id supplied is in the set, then a self-referencing edge
1789      // would return true, but that special case is specifically allowed
1790      // meaning that it isn't an external alias
1791      public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1792
1793       assert id2hrn.contains( id );
1794       HeapRegionNode hrn = id2hrn.get( id );
1795
1796
1797       //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1798
1799       //Iterator i = idSet.iterator();
1800       //while( i.hasNext() ) {
1801       //    Integer idFromSet = (Integer) i.next();
1802       //   assert id2hrn.contains( idFromSet );
1803       //    hrnSet.add( id2hrn.get( idFromSet ) );
1804       //}
1805
1806
1807       // do a traversal from hrn and see if any of the
1808       // heap regions from the set come up during that
1809       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1810       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1811
1812       toVisit.add( hrn );
1813       while( !toVisit.isEmpty() ) {
1814           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1815           toVisit.remove( hrnVisited );
1816           visited.add   ( hrnVisited );
1817
1818           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1819           while( referenceeItr.hasNext() ) {
1820               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1821               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1822               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1823
1824               if( idSet.contains( hrnReferencee.getID() ) ) {
1825                   if( !id.equals( hrnReferencee.getID() ) ) {
1826                       return true;
1827                   }
1828               }
1829
1830               if( !visited.contains( hrnReferencee ) ) {
1831                   toVisit.add( hrnReferencee );
1832               }
1833           }
1834       }
1835
1836       return false;
1837      }
1838    */
1839
1840
1841   // for writing ownership graphs to dot files
1842   public void writeGraph(Descriptor methodDesc,
1843                          FlatNode fn,
1844                          boolean writeLabels,
1845                          boolean labelSelect,
1846                          boolean pruneGarbage,
1847                          boolean writeReferencers
1848                          ) throws java.io.IOException {
1849     writeGraph(
1850       methodDesc.getSymbol() +
1851       methodDesc.getNum() +
1852       fn.toString(),
1853       writeLabels,
1854       labelSelect,
1855       pruneGarbage,
1856       writeReferencers
1857       );
1858   }
1859
1860   public void writeGraph(Descriptor methodDesc,
1861                          FlatNode fn,
1862                          boolean writeLabels,
1863                          boolean writeReferencers
1864                          ) throws java.io.IOException {
1865     writeGraph(
1866       methodDesc.getSymbol() +
1867       methodDesc.getNum() +
1868       fn.toString(),
1869       writeLabels,
1870       false,
1871       false,
1872       writeReferencers
1873       );
1874   }
1875
1876   public void writeGraph(Descriptor methodDesc,
1877                          boolean writeLabels,
1878                          boolean writeReferencers
1879                          ) throws java.io.IOException {
1880     writeGraph(
1881       methodDesc.getSymbol() +
1882       methodDesc.getNum() +
1883       "COMPLETE",
1884       writeLabels,
1885       false,
1886       false,
1887       writeReferencers
1888       );
1889   }
1890
1891   public void writeGraph(Descriptor methodDesc,
1892                          boolean writeLabels,
1893                          boolean labelSelect,
1894                          boolean pruneGarbage,
1895                          boolean writeReferencers
1896                          ) throws java.io.IOException {
1897     writeGraph(
1898       methodDesc.getSymbol() +
1899       methodDesc.getNum() +
1900       "COMPLETE",
1901       writeLabels,
1902       labelSelect,
1903       pruneGarbage,
1904       writeReferencers
1905       );
1906   }
1907
1908   public void writeGraph(String graphName,
1909                          boolean writeLabels,
1910                          boolean labelSelect,
1911                          boolean pruneGarbage,
1912                          boolean writeReferencers
1913                          ) throws java.io.IOException {
1914
1915     // remove all non-word characters from the graph name so
1916     // the filename and identifier in dot don't cause errors
1917     graphName = graphName.replaceAll("[\\W]", "");
1918
1919     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
1920     bw.write("digraph "+graphName+" {\n");
1921     //bw.write( "  size=\"7.5,10\";\n" );
1922
1923     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1924
1925     // then visit every heap region node
1926     if( !pruneGarbage ) {
1927       Set s = id2hrn.entrySet();
1928       Iterator i = s.iterator();
1929       while( i.hasNext() ) {
1930         Map.Entry me  = (Map.Entry)i.next();
1931         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1932         if( !visited.contains(hrn) ) {
1933           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
1934                                   hrn,
1935                                   bw,
1936                                   null,
1937                                   visited,
1938                                   writeReferencers);
1939         }
1940       }
1941     }
1942
1943     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
1944
1945
1946     // then visit every label node, useful for debugging
1947     if( writeLabels ) {
1948       Set s = td2ln.entrySet();
1949       Iterator i = s.iterator();
1950       while( i.hasNext() ) {
1951         Map.Entry me = (Map.Entry)i.next();
1952         LabelNode ln = (LabelNode) me.getValue();
1953
1954         if( labelSelect ) {
1955           String labelStr = ln.getTempDescriptorString();
1956           if( labelStr.startsWith("___temp") ||
1957               labelStr.startsWith("___dst") ||
1958               labelStr.startsWith("___srctmp") ||
1959               labelStr.startsWith("___neverused")   ) {
1960             continue;
1961           }
1962         }
1963
1964         bw.write(ln.toString() + ";\n");
1965
1966         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
1967         while( heapRegionsItr.hasNext() ) {
1968           ReferenceEdge edge = heapRegionsItr.next();
1969           HeapRegionNode hrn  = edge.getDst();
1970
1971           if( pruneGarbage && !visited.contains(hrn) ) {
1972             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
1973                                     hrn,
1974                                     bw,
1975                                     null,
1976                                     visited,
1977                                     writeReferencers);
1978           }
1979
1980           bw.write("  "        + ln.toString() +
1981                    " -> "      + hrn.toString() +
1982                    "[label=\"" + edge.toGraphEdgeString() +
1983                    "\",decorate];\n");
1984         }
1985       }
1986     }
1987
1988
1989     bw.write("}\n");
1990     bw.close();
1991   }
1992
1993   protected void traverseHeapRegionNodes(int mode,
1994                                          HeapRegionNode hrn,
1995                                          BufferedWriter bw,
1996                                          TempDescriptor td,
1997                                          HashSet<HeapRegionNode> visited,
1998                                          boolean writeReferencers
1999                                          ) throws java.io.IOException {
2000
2001     if( visited.contains(hrn) ) {
2002       return;
2003     }
2004     visited.add(hrn);
2005
2006     switch( mode ) {
2007     case VISIT_HRN_WRITE_FULL:
2008
2009       String attributes = "[";
2010
2011       if( hrn.isSingleObject() ) {
2012         attributes += "shape=box";
2013       } else {
2014         attributes += "shape=Msquare";
2015       }
2016
2017       if( hrn.isFlagged() ) {
2018         attributes += ",style=filled,fillcolor=lightgrey";
2019       }
2020
2021       attributes += ",label=\"ID"        +
2022                     hrn.getID()          +
2023                     "\\n"                +
2024                     hrn.getDescription() +
2025                     "\\n"                +
2026                     hrn.getAlphaString() +
2027                     "\"]";
2028
2029       bw.write("  " + hrn.toString() + attributes + ";\n");
2030       break;
2031     }
2032
2033
2034     // useful for debugging
2035     if( writeReferencers ) {
2036       OwnershipNode onRef  = null;
2037       Iterator refItr = hrn.iteratorToReferencers();
2038       while( refItr.hasNext() ) {
2039         onRef = (OwnershipNode) refItr.next();
2040
2041         switch( mode ) {
2042         case VISIT_HRN_WRITE_FULL:
2043           bw.write("  "                    + hrn.toString() +
2044                    " -> "                  + onRef.toString() +
2045                    "[color=lightgray];\n");
2046           break;
2047         }
2048       }
2049     }
2050
2051     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2052     while( childRegionsItr.hasNext() ) {
2053       ReferenceEdge edge     = childRegionsItr.next();
2054       HeapRegionNode hrnChild = edge.getDst();
2055
2056       switch( mode ) {
2057       case VISIT_HRN_WRITE_FULL:
2058         bw.write("  "        + hrn.toString() +
2059                  " -> "      + hrnChild.toString() +
2060                  "[label=\"" + edge.toGraphEdgeString() +
2061                  "\",decorate];\n");
2062         break;
2063       }
2064
2065       traverseHeapRegionNodes(mode,
2066                               hrnChild,
2067                               bw,
2068                               td,
2069                               visited,
2070                               writeReferencers);
2071     }
2072   }
2073 }