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   private TypeUtil typeUtil;
  12
  13   // there was already one other very similar reason
  14   // for traversing heap nodes that is no longer needed
  15   // instead of writing a new heap region visitor, use
  16   // the existing method with a new mode to describe what
  17   // actions to take during the traversal
  18   protected static final int VISIT_HRN_WRITE_FULL = 0;
  19
  20   protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
  21
  22
  23   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  24   public Hashtable<TempDescriptor, LabelNode     > td2ln;
  25   public Hashtable<Integer,        Integer       > id2paramIndex;
  26   public Hashtable<Integer,        Integer       > paramIndex2id;
  27   public Hashtable<Integer,        TempDescriptor> paramIndex2tdQ;
  28
  29   public HashSet<AllocationSite> allocationSites;
  30
  31
  32
  33
  34   public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
  35     this.allocationDepth = allocationDepth;
  36     this.typeUtil        = typeUtil;
  37
  38     id2hrn         = new Hashtable<Integer,        HeapRegionNode>();
  39     td2ln          = new Hashtable<TempDescriptor, LabelNode     >();
  40     id2paramIndex  = new Hashtable<Integer,        Integer       >();
  41     paramIndex2id  = new Hashtable<Integer,        Integer       >();
  42     paramIndex2tdQ = new Hashtable<Integer,        TempDescriptor>();
  43
  44     allocationSites = new HashSet <AllocationSite>();
  45   }
  46
  47
  48   // label nodes are much easier to deal with than
  49   // heap region nodes.  Whenever there is a request
  50   // for the label node that is associated with a
  51   // temp descriptor we can either find it or make a
  52   // new one and return it.  This is because temp
  53   // descriptors are globally unique and every label
  54   // node is mapped to exactly one temp descriptor.
  55   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  56     assert td != null;
  57
  58     if( !td2ln.containsKey(td) ) {
  59       td2ln.put(td, new LabelNode(td) );
  60     }
  61
  62     return td2ln.get(td);
  63   }
  64
  65
  66   // the reason for this method is to have the option
  67   // creating new heap regions with specific IDs, or
  68   // duplicating heap regions with specific IDs (especially
  69   // in the merge() operation) or to create new heap
  70   // regions with a new unique ID.
  71   protected HeapRegionNode
  72   createNewHeapRegionNode(Integer id,
  73                           boolean isSingleObject,
  74                           boolean isFlagged,
  75                           boolean isNewSummary,
  76                           boolean isParameter,
  77                           AllocationSite allocSite,
  78                           ReachabilitySet alpha,
  79                           String description) {
  80
  81     if( id == null ) {
  82       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  83     }
  84
  85     if( alpha == null ) {
  86       if( isFlagged || isParameter ) {
  87         alpha = new ReachabilitySet(
  88           new TokenTuple(id,
  89                          !isSingleObject,
  90                          TokenTuple.ARITY_ONE
  91                          ).makeCanonical()
  92           ).makeCanonical();
  93       } else {
  94         alpha = new ReachabilitySet(
  95           new TokenTupleSet().makeCanonical()
  96           ).makeCanonical();
  97       }
  98     }
  99
 100     HeapRegionNode hrn = new HeapRegionNode(id,
 101                                             isSingleObject,
 102                                             isFlagged,
 103                                             isNewSummary,
 104                                             allocSite,
 105                                             alpha,
 106                                             description);
 107     id2hrn.put(id, hrn);
 108     return hrn;
 109   }
 110
 111
 112
 113   ////////////////////////////////////////////////
 114   //
 115   //  Low-level referencee and referencer methods
 116   //
 117   //  These methods provide the lowest level for
 118   //  creating references between ownership nodes
 119   //  and handling the details of maintaining both
 120   //  list of referencers and referencees.
 121   //
 122   ////////////////////////////////////////////////
 123   protected void addReferenceEdge(OwnershipNode referencer,
 124                                   HeapRegionNode referencee,
 125                                   ReferenceEdge edge) {
 126     assert referencer != null;
 127     assert referencee != null;
 128     assert edge       != null;
 129     assert edge.getSrc() == referencer;
 130     assert edge.getDst() == referencee;
 131
 132     referencer.addReferencee(edge);
 133     referencee.addReferencer(edge);
 134   }
 135
 136   protected void removeReferenceEdge(OwnershipNode referencer,
 137                                      HeapRegionNode referencee,
 138                                      FieldDescriptor fieldDesc) {
 139     assert referencer != null;
 140     assert referencee != null;
 141
 142     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 143                                                    fieldDesc);
 144     assert edge != null;
 145     assert edge == referencee.getReferenceFrom(referencer,
 146                                                fieldDesc);
 147
 148     referencer.removeReferencee(edge);
 149     referencee.removeReferencer(edge);
 150   }
 151
 152   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 153                                          FieldDescriptor fieldDesc,
 154                                          boolean removeAll) {
 155     assert referencer != null;
 156
 157     // get a copy of the set to iterate over, otherwise
 158     // we will be trying to take apart the set as we
 159     // are iterating over it, which won't work
 160     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 161     while( i.hasNext() ) {
 162       ReferenceEdge edge = i.next();
 163
 164       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 165         HeapRegionNode referencee = edge.getDst();
 166
 167         removeReferenceEdge(referencer,
 168                             referencee,
 169                             edge.getFieldDesc() );
 170       }
 171     }
 172   }
 173
 174   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 175                                        FieldDescriptor fieldDesc,
 176                                        boolean removeAll) {
 177     assert referencee != null;
 178
 179     // get a copy of the set to iterate over, otherwise
 180     // we will be trying to take apart the set as we
 181     // are iterating over it, which won't work
 182     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 183     while( i.hasNext() ) {
 184       ReferenceEdge edge = i.next();
 185
 186       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 187         OwnershipNode referencer = edge.getSrc();
 188         removeReferenceEdge(referencer,
 189                             referencee,
 190                             edge.getFieldDesc() );
 191       }
 192     }
 193   }
 194
 195
 196   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
 197                                           ChangeTupleSet c0,
 198                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
 199                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
 200
 201     HashSet<HeapRegionNode> todoNodes
 202     = new HashSet<HeapRegionNode>();
 203     todoNodes.add(nPrime);
 204
 205     HashSet<ReferenceEdge> todoEdges
 206     = new HashSet<ReferenceEdge>();
 207
 208     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 209     = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 210     nodePlannedChanges.put(nPrime, c0);
 211
 212     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
 213     = new Hashtable<ReferenceEdge, ChangeTupleSet>();
 214
 215
 216     while( !todoNodes.isEmpty() ) {
 217       HeapRegionNode n = todoNodes.iterator().next();
 218       ChangeTupleSet C = nodePlannedChanges.get(n);
 219
 220       Iterator itrC = C.iterator();
 221       while( itrC.hasNext() ) {
 222         ChangeTuple c = (ChangeTuple) itrC.next();
 223
 224         if( n.getAlpha().contains(c.getSetToMatch() ) ) {
 225           ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
 226           n.setAlphaNew(n.getAlphaNew().union(withChange) );
 227           nodesWithNewAlpha.add(n);
 228         }
 229       }
 230
 231       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 232       while( referItr.hasNext() ) {
 233         ReferenceEdge edge = referItr.next();
 234         todoEdges.add(edge);
 235
 236         if( !edgePlannedChanges.containsKey(edge) ) {
 237           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
 238         }
 239
 240         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 241       }
 242
 243       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
 244       while( refeeItr.hasNext() ) {
 245         ReferenceEdge edgeF = refeeItr.next();
 246         HeapRegionNode m     = edgeF.getDst();
 247
 248         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 249
 250         Iterator<ChangeTuple> itrCprime = C.iterator();
 251         while( itrCprime.hasNext() ) {
 252           ChangeTuple c = itrCprime.next();
 253           if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
 254             changesToPass = changesToPass.union(c);
 255           }
 256         }
 257
 258         if( !changesToPass.isEmpty() ) {
 259           if( !nodePlannedChanges.containsKey(m) ) {
 260             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
 261           }
 262
 263           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
 264
 265           if( !changesToPass.isSubset(currentChanges) ) {
 266
 267             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 268             todoNodes.add(m);
 269           }
 270         }
 271       }
 272
 273       todoNodes.remove(n);
 274     }
 275
 276     propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
 277   }
 278
 279
 280   protected void propagateTokensOverEdges(
 281     HashSet<ReferenceEdge>                   todoEdges,
 282     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
 283     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
 284
 285
 286     while( !todoEdges.isEmpty() ) {
 287       ReferenceEdge edgeE = todoEdges.iterator().next();
 288       todoEdges.remove(edgeE);
 289
 290       if( !edgePlannedChanges.containsKey(edgeE) ) {
 291         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
 292       }
 293
 294       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
 295
 296       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 297
 298       Iterator<ChangeTuple> itrC = C.iterator();
 299       while( itrC.hasNext() ) {
 300         ChangeTuple c = itrC.next();
 301         if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
 302           ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
 303           edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
 304           edgesWithNewBeta.add(edgeE);
 305           changesToPass = changesToPass.union(c);
 306         }
 307       }
 308
 309       OwnershipNode onSrc = edgeE.getSrc();
 310
 311       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 312         HeapRegionNode n = (HeapRegionNode) onSrc;
 313
 314         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 315         while( referItr.hasNext() ) {
 316           ReferenceEdge edgeF = referItr.next();
 317
 318           if( !edgePlannedChanges.containsKey(edgeF) ) {
 319             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
 320           }
 321
 322           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
 323
 324           if( !changesToPass.isSubset(currentChanges) ) {
 325             todoEdges.add(edgeF);
 326             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
 327           }
 328         }
 329       }
 330     }
 331   }
 332
 333
 334   ////////////////////////////////////////////////////
 335   //
 336   //  Assignment Operation Methods
 337   //
 338   //  These methods are high-level operations for
 339   //  modeling program assignment statements using
 340   //  the low-level reference create/remove methods
 341   //  above.
 342   //
 343   //  The destination in an assignment statement is
 344   //  going to have new references.  The method of
 345   //  determining the references depends on the type
 346   //  of the FlatNode assignment and the predicates
 347   //  of the nodes and edges involved.
 348   //
 349   ////////////////////////////////////////////////////
 350   public void assignTempXEqualToTempY(TempDescriptor x,
 351                                       TempDescriptor y) {
 352
 353     LabelNode lnX = getLabelNodeFromTemp(x);
 354     LabelNode lnY = getLabelNodeFromTemp(y);
 355
 356     clearReferenceEdgesFrom(lnX, null, true);
 357
 358     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 359     while( itrYhrn.hasNext() ) {
 360       ReferenceEdge edgeY       = itrYhrn.next();
 361       HeapRegionNode referencee = edgeY.getDst();
 362       ReferenceEdge edgeNew    = edgeY.copy();
 363       edgeNew.setSrc(lnX);
 364
 365       addReferenceEdge(lnX, referencee, edgeNew);
 366     }
 367   }
 368
 369
 370   public void assignTempXEqualToTempYFieldF(TempDescriptor x,
 371                                             TempDescriptor y,
 372                                             FieldDescriptor f) {
 373     LabelNode lnX = getLabelNodeFromTemp(x);
 374     LabelNode lnY = getLabelNodeFromTemp(y);
 375
 376     clearReferenceEdgesFrom(lnX, null, true);
 377
 378     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 379     while( itrYhrn.hasNext() ) {
 380       ReferenceEdge edgeY = itrYhrn.next();
 381       HeapRegionNode hrnY  = edgeY.getDst();
 382       ReachabilitySet betaY = edgeY.getBeta();
 383
 384       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 385       while( itrHrnFhrn.hasNext() ) {
 386         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 387         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 388         ReachabilitySet betaHrn = edgeHrn.getBeta();
 389
 390         if( edgeHrn.getFieldDesc() == null ||
 391             edgeHrn.getFieldDesc() == f ) {
 392
 393           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 394                                                     hrnHrn,
 395                                                     f,
 396                                                     false,
 397                                                     betaY.intersection(betaHrn) );
 398
 399           addReferenceEdge(lnX, hrnHrn, edgeNew);
 400         }
 401       }
 402     }
 403   }
 404
 405
 406   public void assignTempXFieldFEqualToTempY(TempDescriptor x,
 407                                             FieldDescriptor f,
 408                                             TempDescriptor y) {
 409     LabelNode lnX = getLabelNodeFromTemp(x);
 410     LabelNode lnY = getLabelNodeFromTemp(y);
 411
 412     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 413     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 414
 415     boolean strongUpdate = false;
 416
 417     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 418     while( itrXhrn.hasNext() ) {
 419       ReferenceEdge edgeX = itrXhrn.next();
 420       HeapRegionNode hrnX  = edgeX.getDst();
 421       ReachabilitySet betaX = edgeX.getBeta();
 422
 423       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 424
 425       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 426       while( itrYhrn.hasNext() ) {
 427         ReferenceEdge edgeY = itrYhrn.next();
 428         HeapRegionNode hrnY  = edgeY.getDst();
 429         ReachabilitySet O     = edgeY.getBeta();
 430
 431
 432         // propagate tokens over nodes starting from hrnSrc, and it will
 433         // take care of propagating back up edges from any touched nodes
 434         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 435         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 436
 437
 438         // then propagate back just up the edges from hrn
 439         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 440
 441
 442         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 443
 444         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 445           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 446
 447         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 448         while( referItr.hasNext() ) {
 449           ReferenceEdge edgeUpstream = referItr.next();
 450           todoEdges.add(edgeUpstream);
 451           edgePlannedChanges.put(edgeUpstream, Cx);
 452         }
 453
 454         propagateTokensOverEdges(todoEdges,
 455                                  edgePlannedChanges,
 456                                  edgesWithNewBeta);
 457
 458         // if edgeY's beta was updated, use that to calculate beta for new edge
 459         // otherwise the edgeY didn't change and it is the source for the calc
 460         ReachabilitySet sourceBetaForNewEdge;
 461         //if( edgesWithNewBeta.contains( edgeY ) ) {
 462         if( !edgeY.getBetaNew().equals( new ReachabilitySet().makeCanonical() ) ) {
 463           sourceBetaForNewEdge = edgeY.getBetaNew();
 464         } else {
 465           sourceBetaForNewEdge = edgeY.getBeta();
 466         }
 467
 468         ReachabilitySet sourceAlphaForPrune;
 469         if( !hrnX.getAlphaNew().equals( new ReachabilitySet().makeCanonical() ) ) {
 470           sourceAlphaForPrune = hrnX.getAlphaNew();
 471         } else {
 472           sourceAlphaForPrune = hrnX.getAlpha();
 473         }
 474
 475         // prepare the new reference edge hrnX.f -> hrnY
 476         ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
 477                                                   hrnY,
 478                                                   f,
 479                                                   false,
 480                                                   sourceBetaForNewEdge.pruneBy( sourceAlphaForPrune )
 481                                                   );
 482
 483         // we can do a strong update here if one of two cases holds
 484         if( f != null &&
 485             (   (hrnX.getNumReferencers() == 1)                           ||
 486                 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
 487             )
 488           ) {
 489           strongUpdate = true;
 490           clearReferenceEdgesFrom( hrnX, f, false );
 491         }
 492
 493         // look to see if an edge with same field exists
 494         // and merge with it, otherwise just add the edge
 495         ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
 496
 497         if( edgeExisting != null ) {
 498           edgeExisting.setBetaNew(
 499                                   edgeExisting.getBetaNew().union( edgeNew.getBeta() )
 500                                   );
 501           // a new edge here cannot be reflexive, so existing will
 502           // always be also not reflexive anymore
 503           edgeExisting.setIsInitialParamReflexive( false );
 504         } else {
 505           addReferenceEdge( hrnX, hrnY, edgeNew );
 506         }
 507       }
 508     }
 509
 510     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 511     while( nodeItr.hasNext() ) {
 512       nodeItr.next().applyAlphaNew();
 513     }
 514
 515     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
 516     while( edgeItr.hasNext() ) {
 517       edgeItr.next().applyBetaNew();
 518     }
 519
 520     // if it was a strong update, make sure to improve
 521     // reachability with a global sweep
 522     if( strongUpdate ) {
 523       //try {
 524       //writeGraph( "testBefore", true, true, true, false, false );
 525         globalSweep();
 526         //writeGraph( "testPost", true, true, true, false, false );
 527         //} catch( Exception e ) {}
 528     }
 529   }
 530
 531
 532   public void assignTempEqualToParamAlloc(TempDescriptor td,
 533                                           boolean isTask,
 534                                           Integer paramIndex) {
 535     assert td != null;
 536
 537     LabelNode lnParam = getLabelNodeFromTemp(td);
 538     HeapRegionNode hrn = createNewHeapRegionNode(null,
 539                                                  false,
 540                                                  isTask,
 541                                                  false,
 542                                                  true,
 543                                                  null,
 544                                                  null,
 545                                                  "param" + paramIndex);
 546
 547     // this is a non-program-accessible label that picks up beta
 548     // info to be used for fixing a caller of this method
 549     TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
 550     LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
 551
 552     // keep track of heap regions that were created for
 553     // parameter labels, the index of the parameter they
 554     // are for is important when resolving method calls
 555     Integer newID = hrn.getID();
 556     assert !id2paramIndex.containsKey(newID);
 557     assert !id2paramIndex.containsValue(paramIndex);
 558     id2paramIndex.put(newID, paramIndex);
 559     paramIndex2id.put(paramIndex, newID);
 560     paramIndex2tdQ.put(paramIndex, tdParamQ);
 561
 562     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
 563                                                               true,
 564                                                               TokenTuple.ARITY_ONE).makeCanonical()
 565                                                ).makeCanonical();
 566
 567     // heap regions for parameters are always multiple object (see above)
 568     // and have a reference to themselves, because we can't know the
 569     // structure of memory that is passed into the method.  We're assuming
 570     // the worst here.
 571
 572     ReferenceEdge edgeFromLabel =
 573       new ReferenceEdge(lnParam, hrn, null, false, beta);
 574
 575     ReferenceEdge edgeFromLabelQ =
 576       new ReferenceEdge(lnParamQ, hrn, null, false, beta);
 577
 578     ReferenceEdge edgeReflexive =
 579       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 580
 581     addReferenceEdge(lnParam,  hrn, edgeFromLabel);
 582     addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
 583     addReferenceEdge(hrn,      hrn, edgeReflexive);
 584   }
 585
 586
 587   public void assignReturnEqualToTemp(TempDescriptor x) {
 588
 589     LabelNode lnR = getLabelNodeFromTemp(tdReturn);
 590     LabelNode lnX = getLabelNodeFromTemp(x);
 591
 592     clearReferenceEdgesFrom(lnR, null, true);
 593
 594     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 595     while( itrXhrn.hasNext() ) {
 596       ReferenceEdge edgeX       = itrXhrn.next();
 597       HeapRegionNode referencee = edgeX.getDst();
 598       ReferenceEdge edgeNew    = edgeX.copy();
 599       edgeNew.setSrc(lnR);
 600
 601       addReferenceEdge(lnR, referencee, edgeNew);
 602     }
 603   }
 604
 605
 606   public void assignTempEqualToNewAlloc(TempDescriptor x,
 607                                         AllocationSite as) {
 608     assert x  != null;
 609     assert as != null;
 610
 611     age(as);
 612
 613     // after the age operation the newest (or zero-ith oldest)
 614     // node associated with the allocation site should have
 615     // no references to it as if it were a newly allocated
 616     // heap region, so make a reference to it to complete
 617     // this operation
 618
 619     Integer idNewest  = as.getIthOldest(0);
 620     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 621     assert hrnNewest != null;
 622
 623     LabelNode lnX = getLabelNodeFromTemp(x);
 624     clearReferenceEdgesFrom(lnX, null, true);
 625
 626     ReferenceEdge edgeNew =
 627       new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
 628
 629     addReferenceEdge(lnX, hrnNewest, edgeNew);
 630   }
 631
 632
 633   // use the allocation site (unique to entire analysis) to
 634   // locate the heap region nodes in this ownership graph
 635   // that should be aged.  The process models the allocation
 636   // of new objects and collects all the oldest allocations
 637   // in a summary node to allow for a finite analysis
 638   //
 639   // There is an additional property of this method.  After
 640   // running it on a particular ownership graph (many graphs
 641   // may have heap regions related to the same allocation site)
 642   // the heap region node objects in this ownership graph will be
 643   // allocated.  Therefore, after aging a graph for an allocation
 644   // site, attempts to retrieve the heap region nodes using the
 645   // integer id's contained in the allocation site should always
 646   // return non-null heap regions.
 647   public void age(AllocationSite as) {
 648
 649     // aging adds this allocation site to the graph's
 650     // list of sites that exist in the graph, or does
 651     // nothing if the site is already in the list
 652     allocationSites.add(as);
 653
 654     // get the summary node for the allocation site in the context
 655     // of this particular ownership graph
 656     HeapRegionNode hrnSummary = getSummaryNode(as);
 657
 658     // merge oldest node into summary
 659     Integer idK  = as.getOldest();
 660     HeapRegionNode hrnK = id2hrn.get(idK);
 661     mergeIntoSummary(hrnK, hrnSummary);
 662
 663     // move down the line of heap region nodes
 664     // clobbering the ith and transferring all references
 665     // to and from i-1 to node i.  Note that this clobbers
 666     // the oldest node (hrnK) that was just merged into
 667     // the summary
 668     for( int i = allocationDepth - 1; i > 0; --i ) {
 669
 670       // move references from the i-1 oldest to the ith oldest
 671       Integer idIth     = as.getIthOldest(i);
 672       HeapRegionNode hrnI      = id2hrn.get(idIth);
 673       Integer idImin1th = as.getIthOldest(i - 1);
 674       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 675
 676       transferOnto(hrnImin1, hrnI);
 677     }
 678
 679     // as stated above, the newest node should have had its
 680     // references moved over to the second oldest, so we wipe newest
 681     // in preparation for being the new object to assign something to
 682     Integer id0th = as.getIthOldest(0);
 683     HeapRegionNode hrn0  = id2hrn.get(id0th);
 684     assert hrn0 != null;
 685
 686     // clear all references in and out of newest node
 687     clearReferenceEdgesFrom(hrn0, null, true);
 688     clearReferenceEdgesTo(hrn0, null, true);
 689
 690
 691     // now tokens in reachability sets need to "age" also
 692     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 693     while( itrAllLabelNodes.hasNext() ) {
 694       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 695       LabelNode ln = (LabelNode) me.getValue();
 696
 697       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 698       while( itrEdges.hasNext() ) {
 699         ageTokens(as, itrEdges.next() );
 700       }
 701     }
 702
 703     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 704     while( itrAllHRNodes.hasNext() ) {
 705       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
 706       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 707
 708       ageTokens(as, hrnToAge);
 709
 710       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
 711       while( itrEdges.hasNext() ) {
 712         ageTokens(as, itrEdges.next() );
 713       }
 714     }
 715
 716
 717     // after tokens have been aged, reset newest node's reachability
 718     if( hrn0.isFlagged() ) {
 719       hrn0.setAlpha(new ReachabilitySet(
 720                       new TokenTupleSet(
 721                         new TokenTuple(hrn0).makeCanonical()
 722                         ).makeCanonical()
 723                       ).makeCanonical()
 724                     );
 725     } else {
 726       hrn0.setAlpha(new ReachabilitySet(
 727                       new TokenTupleSet().makeCanonical()
 728                       ).makeCanonical()
 729                     );
 730     }
 731   }
 732
 733
 734   protected HeapRegionNode getSummaryNode(AllocationSite as) {
 735
 736     Integer idSummary  = as.getSummary();
 737     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
 738
 739     // If this is null then we haven't touched this allocation site
 740     // in the context of the current ownership graph, so allocate
 741     // heap region nodes appropriate for the entire allocation site.
 742     // This should only happen once per ownership graph per allocation site,
 743     // and a particular integer id can be used to locate the heap region
 744     // in different ownership graphs that represents the same part of an
 745     // allocation site.
 746     if( hrnSummary == null ) {
 747
 748       boolean hasFlags = false;
 749       if( as.getType().isClass() ) {
 750         hasFlags = as.getType().getClassDesc().hasFlags();
 751       }
 752
 753       hrnSummary = createNewHeapRegionNode(idSummary,
 754                                            false,
 755                                            hasFlags,
 756                                            true,
 757                                            false,
 758                                            as,
 759                                            null,
 760                                            as + "\\n" + as.getType() + "\\nsummary");
 761
 762       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 763         Integer idIth = as.getIthOldest(i);
 764         assert !id2hrn.containsKey(idIth);
 765         createNewHeapRegionNode(idIth,
 766                                 true,
 767                                 hasFlags,
 768                                 false,
 769                                 false,
 770                                 as,
 771                                 null,
 772                                 as + "\\n" + as.getType() + "\\n" + i + " oldest");
 773       }
 774     }
 775
 776     return hrnSummary;
 777   }
 778
 779
 780   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
 781
 782     Integer idShadowSummary  = as.getSummaryShadow();
 783     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
 784
 785     if( hrnShadowSummary == null ) {
 786
 787       boolean hasFlags = false;
 788       if( as.getType().isClass() ) {
 789         hasFlags = as.getType().getClassDesc().hasFlags();
 790       }
 791
 792       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
 793                                                  false,
 794                                                  hasFlags,
 795                                                  true,
 796                                                  false,
 797                                                  as,
 798                                                  null,
 799                                                  as + "\\n" + as.getType() + "\\nshadowSum");
 800
 801       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 802         Integer idShadowIth = as.getIthOldestShadow(i);
 803         assert !id2hrn.containsKey(idShadowIth);
 804         createNewHeapRegionNode(idShadowIth,
 805                                 true,
 806                                 hasFlags,
 807                                 false,
 808                                 false,
 809                                 as,
 810                                 null,
 811                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
 812       }
 813     }
 814
 815     return hrnShadowSummary;
 816   }
 817
 818
 819   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
 820     assert hrnSummary.isNewSummary();
 821
 822     // transfer references _from_ hrn over to hrnSummary
 823     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
 824     while( itrReferencee.hasNext() ) {
 825       ReferenceEdge edge       = itrReferencee.next();
 826       ReferenceEdge edgeMerged = edge.copy();
 827       edgeMerged.setSrc(hrnSummary);
 828
 829       HeapRegionNode hrnReferencee = edge.getDst();
 830       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
 831
 832       if( edgeSummary == null ) {
 833         // the merge is trivial, nothing to be done
 834       } else {
 835         // otherwise an edge from the referencer to hrnSummary exists already
 836         // and the edge referencer->hrn should be merged with it
 837         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 838       }
 839
 840       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
 841     }
 842
 843     // next transfer references _to_ hrn over to hrnSummary
 844     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
 845     while( itrReferencer.hasNext() ) {
 846       ReferenceEdge edge         = itrReferencer.next();
 847       ReferenceEdge edgeMerged   = edge.copy();
 848       edgeMerged.setDst(hrnSummary);
 849
 850       OwnershipNode onReferencer = edge.getSrc();
 851       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
 852
 853       if( edgeSummary == null ) {
 854         // the merge is trivial, nothing to be done
 855       } else {
 856         // otherwise an edge from the referencer to alpha_S exists already
 857         // and the edge referencer->alpha_K should be merged with it
 858         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 859       }
 860
 861       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
 862     }
 863
 864     // then merge hrn reachability into hrnSummary
 865     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
 866   }
 867
 868
 869   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
 870
 871     // clear references in and out of node i
 872     clearReferenceEdgesFrom(hrnB, null, true);
 873     clearReferenceEdgesTo(hrnB, null, true);
 874
 875     // copy each edge in and out of A to B
 876     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
 877     while( itrReferencee.hasNext() ) {
 878       ReferenceEdge edge          = itrReferencee.next();
 879       HeapRegionNode hrnReferencee = edge.getDst();
 880       ReferenceEdge edgeNew       = edge.copy();
 881       edgeNew.setSrc(hrnB);
 882
 883       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
 884     }
 885
 886     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
 887     while( itrReferencer.hasNext() ) {
 888       ReferenceEdge edge         = itrReferencer.next();
 889       OwnershipNode onReferencer = edge.getSrc();
 890       ReferenceEdge edgeNew      = edge.copy();
 891       edgeNew.setDst(hrnB);
 892
 893       addReferenceEdge(onReferencer, hrnB, edgeNew);
 894     }
 895
 896     // replace hrnB reachability with hrnA's
 897     hrnB.setAlpha(hrnA.getAlpha() );
 898   }
 899
 900
 901   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
 902     edge.setBeta(edge.getBeta().ageTokens(as) );
 903   }
 904
 905   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
 906     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
 907   }
 908
 909
 910   public void resolveMethodCall(FlatCall fc,
 911                                 boolean isStatic,
 912                                 FlatMethod fm,
 913                                 OwnershipGraph ogCallee) {
 914
 915     // define rewrite rules and other structures to organize
 916     // data by parameter/argument index
 917     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
 918       new Hashtable<Integer, ReachabilitySet>();
 919
 920     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
 921       new Hashtable<Integer, ReachabilitySet>();
 922
 923     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
 924       new Hashtable<Integer, ReachabilitySet>();
 925
 926     Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d =
 927       new Hashtable<Integer, ReachabilitySet>();
 928
 929     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
 930       new Hashtable<Integer, ReachabilitySet>();
 931
 932     // helpful structures
 933     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
 934       new Hashtable<TokenTuple, Integer>();
 935
 936     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
 937       new Hashtable<Integer, TokenTuple>();
 938
 939     Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
 940       new Hashtable<TokenTuple, Integer>();
 941
 942     Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
 943       new Hashtable<Integer, TokenTuple>();
 944
 945     Hashtable<Integer, LabelNode> paramIndex2ln =
 946       new Hashtable<Integer, LabelNode>();
 947
 948     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
 949       new Hashtable<Integer, HashSet<HeapRegionNode> >();
 950
 951
 952     // add a bogus entry with the identity rule for easy rewrite
 953     // of new callee nodes and edges, doesn't belong to any parameter
 954     Integer bogusID = new Integer(-1);
 955     Integer bogusIndex = new Integer(-1);
 956     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE).makeCanonical();
 957     TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE).makeCanonical();
 958     ReachabilitySet rsIdentity =
 959       new ReachabilitySet(
 960         new TokenTupleSet(bogusToken).makeCanonical()
 961         ).makeCanonical();
 962
 963     paramIndex2rewriteH.put(bogusIndex, rsIdentity);
 964     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
 965     paramToken2paramIndex.put(bogusToken, bogusIndex);
 966     paramIndex2paramToken.put(bogusIndex, bogusToken);
 967     paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
 968     paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
 969
 970
 971     for( int i = 0; i < fm.numParameters(); ++i ) {
 972       Integer paramIndex = new Integer(i);
 973
 974       assert ogCallee.paramIndex2id.containsKey(paramIndex);
 975       Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
 976
 977       assert ogCallee.id2hrn.containsKey(idParam);
 978       HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
 979       assert hrnParam != null;
 980       paramIndex2rewriteH.put(paramIndex,
 981
 982                               toShadowTokens(ogCallee, hrnParam.getAlpha() )
 983                               );
 984
 985       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
 986       assert edgeReflexive_i != null;
 987       paramIndex2rewriteJ.put(paramIndex,
 988                               toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
 989                               );
 990
 991       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
 992       assert tdParamQ != null;
 993       LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
 994       assert lnParamQ != null;
 995       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
 996       assert edgeSpecialQ_i != null;
 997       paramIndex2rewriteK.put(paramIndex,
 998                               toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
 999                               );
1000
1001       TokenTuple p_i = new TokenTuple(hrnParam.getID(),
1002                                       true,
1003                                       TokenTuple.ARITY_ONE).makeCanonical();
1004       paramToken2paramIndex.put(p_i, paramIndex);
1005       paramIndex2paramToken.put(paramIndex, p_i);
1006
1007       TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
1008                                            true,
1009                                            TokenTuple.ARITY_ONEORMORE).makeCanonical();
1010       paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
1011       paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
1012
1013       // now depending on whether the callee is static or not
1014       // we need to account for a "this" argument in order to
1015       // find the matching argument in the caller context
1016       TempDescriptor argTemp_i;
1017       if( isStatic ) {
1018         argTemp_i = fc.getArg(paramIndex);
1019       } else {
1020         if( paramIndex.equals(0) ) {
1021           argTemp_i = fc.getThis();
1022         } else {
1023           argTemp_i = fc.getArg(paramIndex - 1);
1024         }
1025       }
1026
1027       // in non-static methods there is a "this" pointer
1028       // that should be taken into account
1029       if( isStatic ) {
1030         assert fc.numArgs()     == fm.numParameters();
1031       } else {
1032         assert fc.numArgs() + 1 == fm.numParameters();
1033       }
1034
1035       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1036       paramIndex2ln.put(paramIndex, argLabel_i);
1037
1038       ReachabilitySet d_i = new ReachabilitySet().makeCanonical();
1039       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1040       while( edgeItr.hasNext() ) {
1041         ReferenceEdge edge = edgeItr.next();
1042         d_i = d_i.union(edge.getBeta());
1043       }
1044       paramIndex2rewrite_d.put(paramIndex, d_i);
1045
1046       ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
1047       paramIndex2rewriteD.put(paramIndex, D_i);
1048     }
1049
1050
1051     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1052     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1053
1054     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1055     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1056
1057     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1058     while( lnArgItr.hasNext() ) {
1059       Map.Entry me      = (Map.Entry)lnArgItr.next();
1060       Integer index   = (Integer)   me.getKey();
1061       LabelNode lnArg_i = (LabelNode) me.getValue();
1062
1063       // rewrite alpha for the nodes reachable from argument label i
1064       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1065       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1066
1067       // to find all reachable nodes, start with label referencees
1068       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1069       while( edgeArgItr.hasNext() ) {
1070         ReferenceEdge edge = edgeArgItr.next();
1071         todoNodes.add(edge.getDst() );
1072       }
1073
1074       // then follow links until all reachable nodes have been found
1075       while( !todoNodes.isEmpty() ) {
1076         HeapRegionNode hrn = todoNodes.iterator().next();
1077         todoNodes.remove(hrn);
1078         reachableNodes.add(hrn);
1079
1080         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1081         while( edgeItr.hasNext() ) {
1082           ReferenceEdge edge = edgeItr.next();
1083
1084           if( !reachableNodes.contains(edge.getDst() ) ) {
1085             todoNodes.add(edge.getDst() );
1086           }
1087         }
1088       }
1089
1090       // save for later
1091       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1092
1093       // now iterate over reachable nodes to update their alpha, and
1094       // classify edges found as "argument reachable" or "upstream"
1095       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1096       while( hrnItr.hasNext() ) {
1097         HeapRegionNode hrn = hrnItr.next();
1098
1099         rewriteCallerReachability(index,
1100                                   hrn,
1101                                   null,
1102                                   paramIndex2rewriteH.get(index),
1103                                   paramIndex2rewrite_d,
1104                                   paramIndex2rewriteD,
1105                                   paramIndex2paramToken.get(index),
1106                                   paramToken2paramIndex,
1107                                   paramTokenPlus2paramIndex,
1108                                   false,
1109                                   null);
1110
1111         nodesWithNewAlpha.add(hrn);
1112
1113         // look at all incoming edges to the reachable nodes
1114         // and sort them as edges reachable from the argument
1115         // label node, or upstream edges
1116         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1117         while( edgeItr.hasNext() ) {
1118           ReferenceEdge edge = edgeItr.next();
1119
1120           OwnershipNode on = edge.getSrc();
1121
1122           if( on instanceof LabelNode ) {
1123
1124             LabelNode ln0 = (LabelNode) on;
1125             if( ln0.equals(lnArg_i) ) {
1126               edgesReachable.add(edge);
1127             } else {
1128               edgesUpstream.add(edge);
1129             }
1130
1131           } else {
1132
1133             HeapRegionNode hrn0 = (HeapRegionNode) on;
1134             if( reachableNodes.contains(hrn0) ) {
1135               edgesReachable.add(edge);
1136             } else {
1137               edgesUpstream.add(edge);
1138             }
1139           }
1140         }
1141       }
1142
1143       // update reachable edges
1144       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1145       while( edgeReachableItr.hasNext() ) {
1146         ReferenceEdge edgeReachable = edgeReachableItr.next();
1147
1148         rewriteCallerReachability(index,
1149                                   null,
1150                                   edgeReachable,
1151                                   paramIndex2rewriteJ.get(index),
1152                                   paramIndex2rewrite_d,
1153                                   paramIndex2rewriteD,
1154                                   paramIndex2paramToken.get(index),
1155                                   paramToken2paramIndex,
1156                                   paramTokenPlus2paramIndex,
1157                                   false,
1158                                   null);
1159
1160         edgesWithNewBeta.add(edgeReachable);
1161       }
1162
1163       // update upstream edges
1164       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1165         new Hashtable<ReferenceEdge, ChangeTupleSet>();
1166
1167       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1168       while( edgeUpstreamItr.hasNext() ) {
1169         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1170
1171         rewriteCallerReachability(index,
1172                                   null,
1173                                   edgeUpstream,
1174                                   paramIndex2rewriteK.get(index),
1175                                   paramIndex2rewrite_d,
1176                                   paramIndex2rewriteD,
1177                                   paramIndex2paramToken.get(index),
1178                                   paramToken2paramIndex,
1179                                   paramTokenPlus2paramIndex,
1180                                   true,
1181                                   edgeUpstreamPlannedChanges);
1182
1183         edgesWithNewBeta.add(edgeUpstream);
1184       }
1185
1186       propagateTokensOverEdges(edgesUpstream,
1187                                edgeUpstreamPlannedChanges,
1188                                edgesWithNewBeta);
1189     }
1190
1191
1192     // commit changes to alpha and beta
1193     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1194     while( nodeItr.hasNext() ) {
1195       nodeItr.next().applyAlphaNew();
1196     }
1197
1198     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1199     while( edgeItr.hasNext() ) {
1200       edgeItr.next().applyBetaNew();
1201     }
1202
1203
1204     // verify the existence of allocation sites and their
1205     // shadows from the callee in the context of this caller graph
1206     // then map allocated nodes of callee onto the caller shadows
1207     // of them
1208     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1209     while( asItr.hasNext() ) {
1210       AllocationSite allocSite  = asItr.next();
1211       HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1212
1213       // assert that the shadow nodes have no reference edges
1214       // because they're brand new to the graph, or last time
1215       // they were used they should have been cleared of edges
1216       HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1217       assert hrnShadowSummary.getNumReferencers() == 0;
1218       assert hrnShadowSummary.getNumReferencees() == 0;
1219
1220       // then bring g_ij onto g'_ij and rewrite
1221       transferOnto(hrnSummary, hrnShadowSummary);
1222
1223       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1224       hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1225
1226       // shadow nodes only are touched by a rewrite one time,
1227       // so rewrite and immediately commit--and they don't belong
1228       // to a particular parameter, so use a bogus param index
1229       // that pulls a self-rewrite out of H
1230       rewriteCallerReachability(bogusIndex,
1231                                 hrnShadowSummary,
1232                                 null,
1233                                 hrnShadowSummary.getAlpha(),
1234                                 paramIndex2rewrite_d,
1235                                 paramIndex2rewriteD,
1236                                 bogusToken,
1237                                 paramToken2paramIndex,
1238                                 paramTokenPlus2paramIndex,
1239                                 false,
1240                                 null);
1241
1242       hrnShadowSummary.applyAlphaNew();
1243
1244
1245       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1246         Integer idIth = allocSite.getIthOldest(i);
1247         assert id2hrn.containsKey(idIth);
1248         HeapRegionNode hrnIth = id2hrn.get(idIth);
1249
1250         Integer idShadowIth = -(allocSite.getIthOldest(i));
1251         assert id2hrn.containsKey(idShadowIth);
1252         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1253         assert hrnIthShadow.getNumReferencers() == 0;
1254         assert hrnIthShadow.getNumReferencees() == 0;
1255
1256         transferOnto(hrnIth, hrnIthShadow);
1257
1258         assert ogCallee.id2hrn.containsKey(idIth);
1259         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1260         hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1261
1262         rewriteCallerReachability(bogusIndex,
1263                                   hrnIthShadow,
1264                                   null,
1265                                   hrnIthShadow.getAlpha(),
1266                                   paramIndex2rewrite_d,
1267                                   paramIndex2rewriteD,
1268                                   bogusToken,
1269                                   paramToken2paramIndex,
1270                                   paramTokenPlus2paramIndex,
1271                                   false,
1272                                   null);
1273
1274         hrnIthShadow.applyAlphaNew();
1275       }
1276     }
1277
1278
1279     // for every heap region->heap region edge in the
1280     // callee graph, create the matching edge or edges
1281     // in the caller graph
1282     Set sCallee = ogCallee.id2hrn.entrySet();
1283     Iterator iCallee = sCallee.iterator();
1284     while( iCallee.hasNext() ) {
1285       Map.Entry meCallee  = (Map.Entry)iCallee.next();
1286       Integer idCallee  = (Integer)        meCallee.getKey();
1287       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1288
1289       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1290       while( heapRegionsItrCallee.hasNext() ) {
1291         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1292         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1293         Integer idChildCallee         = hrnChildCallee.getID();
1294
1295         // only address this edge if it is not a special reflexive edge
1296         if( !edgeCallee.isInitialParamReflexive() ) {
1297
1298           // now we know that in the callee method's ownership graph
1299           // there is a heap region->heap region reference edge given
1300           // by heap region pointers:
1301           // hrnCallee -> heapChildCallee
1302           //
1303           // or by the ownership-graph independent ID's:
1304           // idCallee -> idChildCallee
1305
1306           // make the edge with src and dst so beta info is
1307           // calculated once, then copy it for each new edge in caller
1308           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1309                                                                     null,
1310                                                                     edgeCallee.getFieldDesc(),
1311                                                                     false,
1312                                                                     toShadowTokens(ogCallee,
1313                                                                                    edgeCallee.getBeta() )
1314                                                                     );
1315           rewriteCallerReachability(bogusIndex,
1316                                     null,
1317                                     edgeNewInCallerTemplate,
1318                                     edgeNewInCallerTemplate.getBeta(),
1319                                     paramIndex2rewrite_d,
1320                                     paramIndex2rewriteD,
1321                                     bogusToken,
1322                                     paramToken2paramIndex,
1323                                     paramTokenPlus2paramIndex,
1324                                     false,
1325                                     null);
1326
1327           edgeNewInCallerTemplate.applyBetaNew();
1328
1329
1330           // So now make a set of possible source heaps in the caller graph
1331           // and a set of destination heaps in the caller graph, and make
1332           // a reference edge in the caller for every possible (src,dst) pair
1333           HashSet<HeapRegionNode> possibleCallerSrcs =
1334             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1335                                                 (HeapRegionNode) edgeCallee.getSrc(),
1336                                                 paramIndex2reachableCallerNodes);
1337
1338           HashSet<HeapRegionNode> possibleCallerDsts =
1339             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1340                                                 edgeCallee.getDst(),
1341                                                 paramIndex2reachableCallerNodes);
1342
1343
1344           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1345           Iterator srcItr = possibleCallerSrcs.iterator();
1346           while( srcItr.hasNext() ) {
1347             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1348
1349             if( !hasMatchingField(src, edgeCallee) ) {
1350               // prune this source node possibility
1351               continue;
1352             }
1353
1354             Iterator dstItr = possibleCallerDsts.iterator();
1355             while( dstItr.hasNext() ) {
1356               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1357
1358               if( !hasMatchingType(edgeCallee, dst) ) {
1359                 // prune
1360                 continue;
1361               }
1362
1363               // otherwise the caller src and dst pair can match the edge, so make it
1364               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1365               edgeNewInCaller.setSrc(src);
1366               edgeNewInCaller.setDst(dst);
1367
1368               ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1369               if( edgeExisting == null ) {
1370                 // if this edge doesn't exist in the caller, create it
1371                 addReferenceEdge(src, dst, edgeNewInCaller);
1372               } else {
1373                 // if it already exists, merge with it
1374                 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1375               }
1376             }
1377           }
1378         }
1379       }
1380     }
1381
1382
1383     // return value may need to be assigned in caller
1384     TempDescriptor returnTemp = fc.getReturnTemp();
1385     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1386
1387       LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1388       clearReferenceEdgesFrom(lnLhsCaller, null, true);
1389
1390       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1391       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1392       while( edgeCalleeItr.hasNext() ) {
1393         ReferenceEdge edgeCallee = edgeCalleeItr.next();
1394
1395         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1396                                                                   null,
1397                                                                   edgeCallee.getFieldDesc(),
1398                                                                   false,
1399                                                                   toShadowTokens(ogCallee,
1400                                                                                  edgeCallee.getBeta() )
1401                                                                   );
1402         rewriteCallerReachability(bogusIndex,
1403                                   null,
1404                                   edgeNewInCallerTemplate,
1405                                   edgeNewInCallerTemplate.getBeta(),
1406                                   paramIndex2rewrite_d,
1407                                   paramIndex2rewriteD,
1408                                   bogusToken,
1409                                   paramToken2paramIndex,
1410                                   paramTokenPlus2paramIndex,
1411                                   false,
1412                                   null);
1413
1414         edgeNewInCallerTemplate.applyBetaNew();
1415
1416
1417         HashSet<HeapRegionNode> assignCallerRhs =
1418           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1419                                               edgeCallee.getDst(),
1420                                               paramIndex2reachableCallerNodes);
1421
1422         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1423         while( itrHrn.hasNext() ) {
1424           HeapRegionNode hrnCaller = itrHrn.next();
1425
1426           if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1427             // prune
1428             continue;
1429           }
1430
1431           // otherwise caller node can match callee edge, so make it
1432           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1433           edgeNewInCaller.setSrc(lnLhsCaller);
1434           edgeNewInCaller.setDst(hrnCaller);
1435
1436           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1437           if( edgeExisting == null ) {
1438
1439             // if this edge doesn't exist in the caller, create it
1440             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1441           } else {
1442             // if it already exists, merge with it
1443             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1444           }
1445         }
1446       }
1447     }
1448
1449
1450     // merge the shadow nodes of allocation sites back down to normal capacity
1451     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1452     while( allocItr.hasNext() ) {
1453       AllocationSite as = allocItr.next();
1454
1455       // first age each allocation site enough times to make room for the shadow nodes
1456       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1457         age(as);
1458       }
1459
1460       // then merge the shadow summary into the normal summary
1461       HeapRegionNode hrnSummary = getSummaryNode(as);
1462       assert hrnSummary != null;
1463
1464       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1465       assert hrnSummaryShadow != null;
1466
1467       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1468
1469       // then clear off after merge
1470       clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1471       clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1472       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1473
1474       // then transplant shadow nodes onto the now clean normal nodes
1475       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1476
1477         Integer idIth = as.getIthOldest(i);
1478         HeapRegionNode hrnIth = id2hrn.get(idIth);
1479
1480         Integer idIthShadow = as.getIthOldestShadow(i);
1481         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1482
1483         transferOnto(hrnIthShadow, hrnIth);
1484
1485         // clear off shadow nodes after transfer
1486         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1487         clearReferenceEdgesTo(hrnIthShadow, null, true);
1488         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1489       }
1490
1491       // finally, globally change shadow tokens into normal tokens
1492       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1493       while( itrAllLabelNodes.hasNext() ) {
1494         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1495         LabelNode ln = (LabelNode) me.getValue();
1496
1497         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1498         while( itrEdges.hasNext() ) {
1499           unshadowTokens(as, itrEdges.next() );
1500         }
1501       }
1502
1503       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1504       while( itrAllHRNodes.hasNext() ) {
1505         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1506         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1507
1508         unshadowTokens(as, hrnToAge);
1509
1510         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1511         while( itrEdges.hasNext() ) {
1512           unshadowTokens(as, itrEdges.next() );
1513         }
1514       }
1515     }
1516
1517     // last thing in the entire method call is to do a global sweep
1518     // and try to clean up a little bit
1519     globalSweep();
1520   }
1521
1522
1523   protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1524
1525     // if no allocation site, then it's a match-everything region
1526     AllocationSite asSrc = src.getAllocationSite();
1527     if( asSrc == null ) {
1528       return true;
1529     }
1530
1531     TypeDescriptor tdSrc = asSrc.getType();
1532     assert tdSrc != null;
1533
1534     // if it's not a class, it doesn't have any fields to match
1535     if( !tdSrc.isClass() ) {
1536       return false;
1537     }
1538
1539     Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1540     while( fieldsSrcItr.hasNext() ) {
1541       FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1542       if( fd == edge.getFieldDesc() ) {
1543         return true;
1544       }
1545     }
1546
1547     // otherwise it is a class with fields
1548     // but we didn't find a match
1549     return false;
1550   }
1551
1552
1553   protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1554
1555     // if the region has no type, matches everything
1556     AllocationSite asDst = dst.getAllocationSite();
1557     if( asDst == null ) {
1558       return true;
1559     }
1560
1561     TypeDescriptor tdDst = asDst.getType();
1562     assert tdDst != null;
1563
1564     // if the type is not a class don't match because
1565     // primitives are copied, no memory aliases
1566     ClassDescriptor cdDst = tdDst.getClassDesc();
1567     if( cdDst == null ) {
1568       return false;
1569     }
1570
1571     // if the field is null, it matches everything
1572     FieldDescriptor fd = edge.getFieldDesc();
1573     if( fd == null ) {
1574       return true;
1575     }
1576     TypeDescriptor tdFd = fd.getType();
1577     assert tdFd != null;
1578
1579     return typeUtil.isSuperorType(tdFd, tdDst);
1580   }
1581
1582
1583
1584   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1585     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1586   }
1587
1588   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1589     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1590   }
1591
1592
1593   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1594                                          ReachabilitySet rsIn) {
1595
1596     ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
1597
1598     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1599     while( allocItr.hasNext() ) {
1600       AllocationSite as = allocItr.next();
1601
1602       rsOut = rsOut.toShadowTokens(as);
1603     }
1604
1605     return rsOut.makeCanonical();
1606   }
1607
1608
1609   private void rewriteCallerReachability(Integer paramIndex,
1610                                          HeapRegionNode hrn,
1611                                          ReferenceEdge edge,
1612                                          ReachabilitySet rules,
1613                                          Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d,
1614                                          Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1615                                          TokenTuple p_i,
1616                                          Hashtable<TokenTuple, Integer> paramToken2paramIndex,
1617                                          Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
1618                                          boolean makeChangeSet,
1619                                          Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1620     assert(hrn == null && edge != null) ||
1621     (hrn != null && edge == null);
1622
1623     assert rules != null;
1624     assert p_i != null;
1625
1626     ReachabilitySet callerReachabilityCurrent;
1627     if( hrn == null ) {
1628       callerReachabilityCurrent = edge.getBeta();
1629     } else {
1630       callerReachabilityCurrent = hrn.getAlpha();
1631     }
1632
1633     ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
1634
1635     // for initializing structures in this method
1636     TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
1637
1638     // use this to construct a change set if required; the idea is to
1639     // map every partially rewritten token tuple set to the set of
1640     // caller-context token tuple sets that were used to generate it
1641     Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
1642       new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1643     rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
1644
1645
1646     Iterator<TokenTupleSet> rulesItr = rules.iterator();
1647     while(rulesItr.hasNext()) {
1648       TokenTupleSet rule = rulesItr.next();
1649
1650       ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
1651
1652       Iterator<TokenTuple> ruleItr = rule.iterator();
1653       while(ruleItr.hasNext()) {
1654         TokenTuple ttCallee = ruleItr.next();
1655
1656         // compute the possibilities for rewriting this callee token
1657         ReachabilitySet ttCalleeRewrites = null;
1658         boolean callerSourceUsed = false;
1659
1660         if( ttCallee.equals(p_i) ) {
1661           // replace the arity-one token of the current parameter with the reachability
1662           // information from the caller edge
1663           ttCalleeRewrites = callerReachabilityCurrent;
1664           callerSourceUsed = true;
1665
1666         } else if( paramToken2paramIndex.containsKey(ttCallee) ) {
1667           // use little d
1668           Integer paramIndex_j = paramToken2paramIndex.get(ttCallee);
1669           assert paramIndex_j != null;
1670           ttCalleeRewrites = paramIndex2rewrite_d.get(paramIndex_j);
1671           assert ttCalleeRewrites != null;
1672
1673         } else if( paramTokenPlus2paramIndex.containsKey(ttCallee) ) {
1674           // worse, use big D
1675           Integer paramIndex_j = paramTokenPlus2paramIndex.get(ttCallee);
1676           assert paramIndex_j != null;
1677           ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
1678           assert ttCalleeRewrites != null;
1679
1680         } else {
1681           // otherwise there's no need for a rewrite, just pass this one on
1682           TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
1683           ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
1684         }
1685
1686         // branch every version of the working rewritten rule with
1687         // the possibilities for rewriting the current callee token
1688         ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
1689
1690         Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
1691         while( rewrittenRuleItr.hasNext() ) {
1692           TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
1693
1694           Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
1695           while( ttCalleeRewritesItr.hasNext() ) {
1696             TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
1697
1698             TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity(ttsBranch);
1699
1700             if( makeChangeSet ) {
1701               // in order to keep the list of source token tuple sets
1702               // start with the sets used to make the partially rewritten
1703               // rule up to this point
1704               HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewritten);
1705               assert sourceSets != null;
1706
1707               // make a shallow copy for possible modification
1708               sourceSets = (HashSet<TokenTupleSet>)sourceSets.clone();
1709
1710               // if we used something from the caller to rewrite it, remember
1711               if( callerSourceUsed ) {
1712                 sourceSets.add(ttsBranch);
1713               }
1714
1715               // set mapping for the further rewritten rule
1716               rewritten2source.put(ttsRewrittenNext, sourceSets);
1717             }
1718
1719             rewrittenRuleWithTTCallee =
1720               rewrittenRuleWithTTCallee.union(ttsRewrittenNext);
1721           }
1722         }
1723
1724         // now the rewritten rule's possibilities have been extended by
1725         // rewriting the current callee token, remember result
1726         rewrittenRule = rewrittenRuleWithTTCallee;
1727       }
1728
1729       // the rule has been entirely rewritten into the caller context
1730       // now, so add it to the new reachability information
1731       callerReachabilityNew =
1732         callerReachabilityNew.union(rewrittenRule);
1733     }
1734
1735     if( makeChangeSet ) {
1736       ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
1737
1738       // each possibility for the final reachability should have a set of
1739       // caller sources mapped to it, use to create the change set
1740       Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
1741       while( callerReachabilityItr.hasNext() ) {
1742         TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
1743         HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewrittenFinal);
1744         assert sourceSets != null;
1745
1746         Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
1747         while( sourceSetsItr.hasNext() ) {
1748           TokenTupleSet ttsSource = sourceSetsItr.next();
1749
1750           callerChangeSet =
1751             callerChangeSet.union(new ChangeTuple(ttsSource, ttsRewrittenFinal) );
1752         }
1753       }
1754
1755       assert edgePlannedChanges != null;
1756       edgePlannedChanges.put(edge, callerChangeSet);
1757     }
1758
1759     if( hrn == null ) {
1760       edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
1761     } else {
1762       hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
1763     }
1764   }
1765
1766
1767
1768   private HashSet<HeapRegionNode>
1769   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1770                                       HeapRegionNode hrnCallee,
1771                                       Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1772                                       ) {
1773
1774     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1775
1776     Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1777
1778     if( paramIndexCallee == null ) {
1779       // this is a node allocated in the callee then and it has
1780       // exactly one shadow node in the caller to map to
1781       AllocationSite as = hrnCallee.getAllocationSite();
1782       assert as != null;
1783
1784       int age = as.getAgeCategory(hrnCallee.getID() );
1785       assert age != AllocationSite.AGE_notInThisSite;
1786
1787       Integer idCaller;
1788       if( age == AllocationSite.AGE_summary ) {
1789         idCaller = as.getSummaryShadow();
1790       } else if( age == AllocationSite.AGE_oldest ) {
1791         idCaller = as.getOldestShadow();
1792       } else {
1793         assert age == AllocationSite.AGE_in_I;
1794
1795         Integer I = as.getAge(hrnCallee.getID() );
1796         assert I != null;
1797
1798         idCaller = as.getIthOldestShadow(I);
1799       }
1800
1801       assert id2hrn.containsKey(idCaller);
1802       HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1803       possibleCallerHRNs.add(hrnCaller);
1804
1805     } else {
1806       // this is a node that was created to represent a parameter
1807       // so it maps to a whole mess of heap regions
1808       assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1809       possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1810     }
1811
1812     return possibleCallerHRNs;
1813   }
1814
1815
1816
1817   ////////////////////////////////////////////////////
1818   //
1819   //  This global sweep is an optional step to prune
1820   //  reachability sets that are not internally
1821   //  consistent with the global graph.  It should be
1822   //  invoked after strong updates or method calls.
1823   //
1824   ////////////////////////////////////////////////////
1825   protected void globalSweep() {
1826
1827     // a work set for performing the sweep
1828     Hashtable<HeapRegionNode, HashSet<TokenTupleSet> > workSet =
1829       new Hashtable<HeapRegionNode, HashSet<TokenTupleSet> >();
1830
1831     // first initialize every alphaNew for a flagged region to
1832     // a set with just that token
1833     Set hrns = id2hrn.entrySet();
1834     Iterator itrHrns = hrns.iterator();
1835     while( itrHrns.hasNext() ) {
1836       Map.Entry me = (Map.Entry)itrHrns.next();
1837       Integer token = (Integer) me.getKey();
1838       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1839
1840       // assert that this node and incoming edges have clean alphaNew
1841       // and betaNew sets, respectively
1842       ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
1843       //System.out.println( "hrn="+hrn );
1844       //System.out.println( "alphaNew="+hrn.getAlphaNew() );
1845       assert rsEmpty.equals( hrn.getAlphaNew() );
1846
1847       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
1848       while( itrRes.hasNext() ) {
1849         ReferenceEdge edge = itrRes.next();
1850         assert rsEmpty.equals( edge.getBetaNew() );
1851       }
1852
1853       TokenTuple tt     = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE        ).makeCanonical();
1854       TokenTuple ttPlus = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONEORMORE  ).makeCanonical();
1855       TokenTuple ttStar = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
1856
1857       TokenTupleSet tts      = new TokenTupleSet( tt     ).makeCanonical();
1858       TokenTupleSet ttsPlus  = new TokenTupleSet( ttPlus ).makeCanonical();
1859       TokenTupleSet ttsStar  = new TokenTupleSet( ttStar ).makeCanonical();
1860       TokenTupleSet ttsEmpty = new TokenTupleSet(        ).makeCanonical();
1861
1862       if( hrn.isFlagged() ) {
1863         HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
1864         subWorkSet.add( tts     );
1865         subWorkSet.add( ttsPlus );
1866         subWorkSet.add( ttsStar );
1867         workSet.put( hrn, subWorkSet );
1868
1869         hrn.setAlphaNew( new ReachabilitySet( tts ).makeCanonical() );
1870       } else {
1871         hrn.setAlphaNew( new ReachabilitySet( ttsEmpty ).makeCanonical() );
1872       }
1873     }
1874
1875     // then propagate tokens forward one step at a time
1876     while( !workSet.isEmpty() ) {
1877       HeapRegionNode hrn = workSet.keySet().iterator().next();
1878
1879       HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
1880       assert subWorkSet != null;
1881
1882       if( subWorkSet.isEmpty() ) {
1883         // we're currently done with sub work at this heap region, although
1884         // more work may get queued up later, but remove it for now and continue
1885         workSet.remove( hrn );
1886         continue;
1887       }
1888
1889       TokenTupleSet tts = subWorkSet.iterator().next();
1890       subWorkSet.remove( tts );
1891
1892       // try to push this TokenTupleSet over all outgoing edges
1893       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencees();
1894       while( itrRes.hasNext() ) {
1895         ReferenceEdge edge = itrRes.next();
1896         if( edge.getBeta().containsSuperSet( tts ) ) {
1897           HeapRegionNode dst = edge.getDst();
1898
1899           // make a set of possible contributions this token
1900           // might have on the alpha set here
1901           HashSet<TokenTupleSet> ttsNewSet = new HashSet<TokenTupleSet>();
1902           //ttsNewSet.add( tts );
1903
1904           Iterator<TokenTupleSet> itrDstAlphaNew = dst.getAlphaNew().iterator();
1905           while( itrDstAlphaNew.hasNext() ) {
1906             TokenTupleSet ttsDstAlphaNew = itrDstAlphaNew.next();
1907             ttsNewSet.add( tts.unionUpArity( ttsDstAlphaNew ) );
1908           }
1909
1910           // only add this to the dst alpha new if it is in the beta of
1911           // the edge we crossed to get here, and then only continue the
1912           // propagation if it isn't already in the dst alpha new
1913           Iterator<TokenTupleSet> itrNewSet = ttsNewSet.iterator();
1914           while( itrNewSet.hasNext() ) {
1915             TokenTupleSet ttsNew = itrNewSet.next();
1916
1917             if( edge.getBeta().containsSuperSet( ttsNew ) &&
1918                 !dst.getAlphaNew().contains( ttsNew ) ) {
1919
1920               // okay, this is a valid propagation, and add to the
1921               // work set to further propagate it
1922               dst.setAlphaNew( dst.getAlphaNew().union( ttsNew ) );
1923
1924               HashSet<TokenTupleSet> subWorkSetDst = workSet.get( dst );
1925               if( subWorkSetDst == null ) {
1926                 subWorkSetDst = new HashSet<TokenTupleSet>();
1927               }
1928
1929               subWorkSetDst.add( ttsNew );
1930               workSet.put( dst, subWorkSetDst );
1931             }
1932           }
1933         }
1934       }
1935     }
1936
1937     // now prepare work sets to propagate token sets backwards
1938     // from heap regions across all edges
1939     assert workSet.isEmpty();
1940     hrns = id2hrn.entrySet();
1941     itrHrns = hrns.iterator();
1942     while( itrHrns.hasNext() ) {
1943       Map.Entry me = (Map.Entry)itrHrns.next();
1944       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1945
1946       HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
1947
1948       Iterator<TokenTupleSet> itrAlphaNewSets = hrn.getAlphaNew().iterator();
1949       while( itrAlphaNewSets.hasNext() ) {
1950         TokenTupleSet tts = itrAlphaNewSets.next();
1951         subWorkSet.add( tts );
1952       }
1953
1954       workSet.put( hrn, subWorkSet );
1955     }
1956
1957     // propagate token sets backwards across edges one step at a time
1958     while( !workSet.isEmpty() ) {
1959       HeapRegionNode hrn = workSet.keySet().iterator().next();
1960
1961       HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
1962       assert subWorkSet != null;
1963
1964       if( subWorkSet.isEmpty() ) {
1965         // we're currently done with sub work at this heap region, although
1966         // more work may get queued up later, but remove it for now and continue
1967         workSet.remove( hrn );
1968         continue;
1969       }
1970
1971       TokenTupleSet tts = subWorkSet.iterator().next();
1972       subWorkSet.remove( tts );
1973
1974       // try to push this TokenTupleSet back up incoming edges
1975       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
1976       while( itrRes.hasNext() ) {
1977         ReferenceEdge edge = itrRes.next();
1978         if( edge.getBeta().containsWithZeroes( tts ) &&
1979             !edge.getBetaNew().contains( tts ) ) {
1980           // okay, this is a valid propagation, and add to the
1981           // work set to further propagate it
1982           edge.setBetaNew( edge.getBetaNew().union( tts ) );
1983
1984           OwnershipNode src = edge.getSrc();
1985           if( src instanceof HeapRegionNode ) {
1986
1987             HashSet<TokenTupleSet> subWorkSetSrc = workSet.get( (HeapRegionNode) src );
1988             if( subWorkSetSrc == null ) {
1989               subWorkSetSrc = new HashSet<TokenTupleSet>();
1990             }
1991
1992             subWorkSetSrc.add( tts );
1993             workSet.put( (HeapRegionNode) src, subWorkSetSrc );
1994           }
1995         }
1996       }
1997     }
1998
1999     // apply alphaNew and betaNew to all nodes and edges
2000     HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
2001
2002     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2003     while( nodeItr.hasNext() ) {
2004       HeapRegionNode hrn = nodeItr.next();
2005       hrn.applyAlphaNew();
2006       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2007       while( itrRes.hasNext() ) {
2008         res.add( itrRes.next() );
2009       }
2010     }
2011
2012     Iterator<ReferenceEdge> edgeItr = res.iterator();
2013     while( edgeItr.hasNext() ) {
2014       edgeItr.next().applyBetaNew();
2015     }
2016   }
2017
2018
2019
2020   ////////////////////////////////////////////////////
2021   // in merge() and equals() methods the suffix A
2022   // represents the passed in graph and the suffix
2023   // B refers to the graph in this object
2024   // Merging means to take the incoming graph A and
2025   // merge it into B, so after the operation graph B
2026   // is the final result.
2027   ////////////////////////////////////////////////////
2028   public void merge(OwnershipGraph og) {
2029
2030     if( og == null ) {
2031       return;
2032     }
2033
2034     mergeOwnershipNodes(og);
2035     mergeReferenceEdges(og);
2036     mergeId2paramIndex(og);
2037     mergeAllocationSites(og);
2038   }
2039
2040
2041   protected void mergeOwnershipNodes(OwnershipGraph og) {
2042     Set sA = og.id2hrn.entrySet();
2043     Iterator iA = sA.iterator();
2044     while( iA.hasNext() ) {
2045       Map.Entry meA  = (Map.Entry)iA.next();
2046       Integer idA  = (Integer)        meA.getKey();
2047       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2048
2049       // if this graph doesn't have a node the
2050       // incoming graph has, allocate it
2051       if( !id2hrn.containsKey(idA) ) {
2052         HeapRegionNode hrnB = hrnA.copy();
2053         id2hrn.put(idA, hrnB);
2054
2055       } else {
2056         // otherwise this is a node present in both graphs
2057         // so make the new reachability set a union of the
2058         // nodes' reachability sets
2059         HeapRegionNode hrnB = id2hrn.get(idA);
2060         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
2061       }
2062     }
2063
2064     // now add any label nodes that are in graph B but
2065     // not in A
2066     sA = og.td2ln.entrySet();
2067     iA = sA.iterator();
2068     while( iA.hasNext() ) {
2069       Map.Entry meA = (Map.Entry)iA.next();
2070       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2071       LabelNode lnA = (LabelNode)      meA.getValue();
2072
2073       // if the label doesn't exist in B, allocate and add it
2074       LabelNode lnB = getLabelNodeFromTemp(tdA);
2075     }
2076   }
2077
2078   protected void mergeReferenceEdges(OwnershipGraph og) {
2079
2080     // heap regions
2081     Set sA = og.id2hrn.entrySet();
2082     Iterator iA = sA.iterator();
2083     while( iA.hasNext() ) {
2084       Map.Entry meA  = (Map.Entry)iA.next();
2085       Integer idA  = (Integer)        meA.getKey();
2086       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2087
2088       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2089       while( heapRegionsItrA.hasNext() ) {
2090         ReferenceEdge edgeA     = heapRegionsItrA.next();
2091         HeapRegionNode hrnChildA = edgeA.getDst();
2092         Integer idChildA  = hrnChildA.getID();
2093
2094         // at this point we know an edge in graph A exists
2095         // idA -> idChildA, does this exist in B?
2096         assert id2hrn.containsKey(idA);
2097         HeapRegionNode hrnB        = id2hrn.get(idA);
2098         ReferenceEdge edgeToMerge = null;
2099
2100         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2101         while( heapRegionsItrB.hasNext() &&
2102                edgeToMerge == null          ) {
2103
2104           ReferenceEdge edgeB     = heapRegionsItrB.next();
2105           HeapRegionNode hrnChildB = edgeB.getDst();
2106           Integer idChildB  = hrnChildB.getID();
2107
2108           // don't use the ReferenceEdge.equals() here because
2109           // we're talking about existence between graphs
2110           if( idChildB.equals(idChildA) &&
2111               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2112             edgeToMerge = edgeB;
2113           }
2114         }
2115
2116         // if the edge from A was not found in B,
2117         // add it to B.
2118         if( edgeToMerge == null ) {
2119           assert id2hrn.containsKey(idChildA);
2120           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2121           edgeToMerge = edgeA.copy();
2122           edgeToMerge.setSrc(hrnB);
2123           edgeToMerge.setDst(hrnChildB);
2124           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
2125         }
2126         // otherwise, the edge already existed in both graphs
2127         // so merge their reachability sets
2128         else {
2129           // just replace this beta set with the union
2130           assert edgeToMerge != null;
2131           edgeToMerge.setBeta(
2132             edgeToMerge.getBeta().union(edgeA.getBeta() )
2133             );
2134           if( !edgeA.isInitialParamReflexive() ) {
2135             edgeToMerge.setIsInitialParamReflexive(false);
2136           }
2137         }
2138       }
2139     }
2140
2141     // and then again with label nodes
2142     sA = og.td2ln.entrySet();
2143     iA = sA.iterator();
2144     while( iA.hasNext() ) {
2145       Map.Entry meA = (Map.Entry)iA.next();
2146       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2147       LabelNode lnA = (LabelNode)      meA.getValue();
2148
2149       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
2150       while( heapRegionsItrA.hasNext() ) {
2151         ReferenceEdge edgeA     = heapRegionsItrA.next();
2152         HeapRegionNode hrnChildA = edgeA.getDst();
2153         Integer idChildA  = hrnChildA.getID();
2154
2155         // at this point we know an edge in graph A exists
2156         // tdA -> idChildA, does this exist in B?
2157         assert td2ln.containsKey(tdA);
2158         LabelNode lnB         = td2ln.get(tdA);
2159         ReferenceEdge edgeToMerge = null;
2160
2161         // labels never have edges with a field
2162         //assert edgeA.getFieldDesc() == null;
2163
2164         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
2165         while( heapRegionsItrB.hasNext() &&
2166                edgeToMerge == null          ) {
2167
2168           ReferenceEdge edgeB     = heapRegionsItrB.next();
2169           HeapRegionNode hrnChildB = edgeB.getDst();
2170           Integer idChildB  = hrnChildB.getID();
2171
2172           // labels never have edges with a field
2173           //assert edgeB.getFieldDesc() == null;
2174
2175           // don't use the ReferenceEdge.equals() here because
2176           // we're talking about existence between graphs
2177           if( idChildB.equals(idChildA) &&
2178               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2179             edgeToMerge = edgeB;
2180           }
2181         }
2182
2183         // if the edge from A was not found in B,
2184         // add it to B.
2185         if( edgeToMerge == null ) {
2186           assert id2hrn.containsKey(idChildA);
2187           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2188           edgeToMerge = edgeA.copy();
2189           edgeToMerge.setSrc(lnB);
2190           edgeToMerge.setDst(hrnChildB);
2191           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
2192         }
2193         // otherwise, the edge already existed in both graphs
2194         // so merge their reachability sets
2195         else {
2196           // just replace this beta set with the union
2197           edgeToMerge.setBeta(
2198             edgeToMerge.getBeta().union(edgeA.getBeta() )
2199             );
2200           if( !edgeA.isInitialParamReflexive() ) {
2201             edgeToMerge.setIsInitialParamReflexive(false);
2202           }
2203         }
2204       }
2205     }
2206   }
2207
2208   // you should only merge ownership graphs that have the
2209   // same number of parameters, or if one or both parameter
2210   // index tables are empty
2211   protected void mergeId2paramIndex(OwnershipGraph og) {
2212     if( id2paramIndex.size() == 0 ) {
2213       id2paramIndex  = og.id2paramIndex;
2214       paramIndex2id  = og.paramIndex2id;
2215       paramIndex2tdQ = og.paramIndex2tdQ;
2216       return;
2217     }
2218
2219     if( og.id2paramIndex.size() == 0 ) {
2220       return;
2221     }
2222
2223     assert id2paramIndex.size() == og.id2paramIndex.size();
2224   }
2225
2226   protected void mergeAllocationSites(OwnershipGraph og) {
2227     allocationSites.addAll(og.allocationSites);
2228   }
2229
2230
2231
2232   // it is necessary in the equals() member functions
2233   // to "check both ways" when comparing the data
2234   // structures of two graphs.  For instance, if all
2235   // edges between heap region nodes in graph A are
2236   // present and equal in graph B it is not sufficient
2237   // to say the graphs are equal.  Consider that there
2238   // may be edges in graph B that are not in graph A.
2239   // the only way to know that all edges in both graphs
2240   // are equally present is to iterate over both data
2241   // structures and compare against the other graph.
2242   public boolean equals(OwnershipGraph og) {
2243
2244     if( og == null ) {
2245       return false;
2246     }
2247
2248     if( !areHeapRegionNodesEqual(og) ) {
2249       return false;
2250     }
2251
2252     if( !areLabelNodesEqual(og) ) {
2253       return false;
2254     }
2255
2256     if( !areReferenceEdgesEqual(og) ) {
2257       return false;
2258     }
2259
2260     if( !areId2paramIndexEqual(og) ) {
2261       return false;
2262     }
2263
2264     // if everything is equal up to this point,
2265     // assert that allocationSites is also equal--
2266     // this data is redundant and kept for efficiency
2267     assert allocationSites.equals(og.allocationSites);
2268
2269     return true;
2270   }
2271
2272   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2273
2274     if( !areallHRNinAalsoinBandequal(this, og) ) {
2275       return false;
2276     }
2277
2278     if( !areallHRNinAalsoinBandequal(og, this) ) {
2279       return false;
2280     }
2281
2282     return true;
2283   }
2284
2285   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2286                                                        OwnershipGraph ogB) {
2287     Set sA = ogA.id2hrn.entrySet();
2288     Iterator iA = sA.iterator();
2289     while( iA.hasNext() ) {
2290       Map.Entry meA  = (Map.Entry)iA.next();
2291       Integer idA  = (Integer)        meA.getKey();
2292       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2293
2294       if( !ogB.id2hrn.containsKey(idA) ) {
2295         return false;
2296       }
2297
2298       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2299       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2300         return false;
2301       }
2302     }
2303
2304     return true;
2305   }
2306
2307
2308   protected boolean areLabelNodesEqual(OwnershipGraph og) {
2309
2310     if( !areallLNinAalsoinBandequal(this, og) ) {
2311       return false;
2312     }
2313
2314     if( !areallLNinAalsoinBandequal(og, this) ) {
2315       return false;
2316     }
2317
2318     return true;
2319   }
2320
2321   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2322                                                       OwnershipGraph ogB) {
2323     Set sA = ogA.td2ln.entrySet();
2324     Iterator iA = sA.iterator();
2325     while( iA.hasNext() ) {
2326       Map.Entry meA = (Map.Entry)iA.next();
2327       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2328
2329       if( !ogB.td2ln.containsKey(tdA) ) {
2330         return false;
2331       }
2332     }
2333
2334     return true;
2335   }
2336
2337
2338   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2339     if( !areallREinAandBequal(this, og) ) {
2340       return false;
2341     }
2342
2343     return true;
2344   }
2345
2346   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2347                                                 OwnershipGraph ogB) {
2348
2349     // check all the heap region->heap region edges
2350     Set sA = ogA.id2hrn.entrySet();
2351     Iterator iA = sA.iterator();
2352     while( iA.hasNext() ) {
2353       Map.Entry meA  = (Map.Entry)iA.next();
2354       Integer idA  = (Integer)        meA.getKey();
2355       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2356
2357       // we should have already checked that the same
2358       // heap regions exist in both graphs
2359       assert ogB.id2hrn.containsKey(idA);
2360
2361       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2362         return false;
2363       }
2364
2365       // then check every edge in B for presence in A, starting
2366       // from the same parent HeapRegionNode
2367       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2368
2369       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2370         return false;
2371       }
2372     }
2373
2374     // then check all the label->heap region edges
2375     sA = ogA.td2ln.entrySet();
2376     iA = sA.iterator();
2377     while( iA.hasNext() ) {
2378       Map.Entry meA = (Map.Entry)iA.next();
2379       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2380       LabelNode lnA = (LabelNode)      meA.getValue();
2381
2382       // we should have already checked that the same
2383       // label nodes exist in both graphs
2384       assert ogB.td2ln.containsKey(tdA);
2385
2386       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2387         return false;
2388       }
2389
2390       // then check every edge in B for presence in A, starting
2391       // from the same parent LabelNode
2392       LabelNode lnB = ogB.td2ln.get(tdA);
2393
2394       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2395         return false;
2396       }
2397     }
2398
2399     return true;
2400   }
2401
2402
2403   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2404                                                  OwnershipNode onA,
2405                                                  OwnershipGraph ogB) {
2406
2407     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2408     while( itrA.hasNext() ) {
2409       ReferenceEdge edgeA     = itrA.next();
2410       HeapRegionNode hrnChildA = edgeA.getDst();
2411       Integer idChildA  = hrnChildA.getID();
2412
2413       assert ogB.id2hrn.containsKey(idChildA);
2414
2415       // at this point we know an edge in graph A exists
2416       // onA -> idChildA, does this exact edge exist in B?
2417       boolean edgeFound = false;
2418
2419       OwnershipNode onB = null;
2420       if( onA instanceof HeapRegionNode ) {
2421         HeapRegionNode hrnA = (HeapRegionNode) onA;
2422         onB = ogB.id2hrn.get(hrnA.getID() );
2423       } else {
2424         LabelNode lnA = (LabelNode) onA;
2425         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2426       }
2427
2428       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2429       while( itrB.hasNext() ) {
2430         ReferenceEdge edgeB     = itrB.next();
2431         HeapRegionNode hrnChildB = edgeB.getDst();
2432         Integer idChildB  = hrnChildB.getID();
2433
2434         if( idChildA.equals(idChildB) &&
2435             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2436
2437           // there is an edge in the right place with the right field,
2438           // but do they have the same attributes?
2439           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2440
2441             edgeFound = true;
2442             //} else {
2443             //return false;
2444           }
2445         }
2446       }
2447
2448       if( !edgeFound ) {
2449         return false;
2450       }
2451     }
2452
2453     return true;
2454   }
2455
2456
2457   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2458     return id2paramIndex.size() == og.id2paramIndex.size();
2459   }
2460
2461   public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2462
2463     // get parameter's heap region
2464     assert paramIndex2id.containsKey(paramIndex1);
2465     Integer idParam1 = paramIndex2id.get(paramIndex1);
2466
2467     assert id2hrn.containsKey(idParam1);
2468     HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2469     assert hrnParam1 != null;
2470
2471     // get tokens for this parameter
2472     TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2473                                    true,
2474                                    TokenTuple.ARITY_ONE).makeCanonical();
2475
2476     TokenTuple pPlus1 = new TokenTuple(hrnParam1.getID(),
2477                                        true,
2478                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
2479
2480     TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2481                                        true,
2482                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2483
2484
2485     // get tokens for the other parameter
2486     assert paramIndex2id.containsKey(paramIndex2);
2487     Integer idParam2 = paramIndex2id.get(paramIndex2);
2488
2489     assert id2hrn.containsKey(idParam2);
2490     HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2491     assert hrnParam2 != null;
2492
2493     TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2494                                    true,
2495                                    TokenTuple.ARITY_ONE).makeCanonical();
2496
2497     TokenTuple pPlus2 = new TokenTuple(hrnParam2.getID(),
2498                                        true,
2499                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
2500
2501     TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2502                                        true,
2503                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2504
2505
2506     // get special label p_q for first parameter
2507     TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2508     assert tdParamQ1 != null;
2509     LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2510     assert lnParamQ1 != null;
2511
2512     // then get the edge from label q to parameter's hrn
2513     ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2514     assert edgeSpecialQ1 != null;
2515
2516     // if the beta of this edge has tokens from both parameters in one
2517     // token tuple set, then there is a potential alias between them
2518     ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2519     assert beta1 != null;
2520
2521     if( beta1.containsTupleSetWithBoth(p1,     p2) ) {
2522       return true;
2523     }
2524     if( beta1.containsTupleSetWithBoth(pPlus1, p2) ) {
2525       return true;
2526     }
2527     if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2528       return true;
2529     }
2530     if( beta1.containsTupleSetWithBoth(p1,     pPlus2) ) {
2531       return true;
2532     }
2533     if( beta1.containsTupleSetWithBoth(pPlus1, pPlus2) ) {
2534       return true;
2535     }
2536     if( beta1.containsTupleSetWithBoth(pStar1, pPlus2) ) {
2537       return true;
2538     }
2539     if( beta1.containsTupleSetWithBoth(p1,     pStar2) ) {
2540       return true;
2541     }
2542     if( beta1.containsTupleSetWithBoth(pPlus1, pStar2) ) {
2543       return true;
2544     }
2545     if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2546       return true;
2547     }
2548
2549     return false;
2550   }
2551
2552
2553   public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2554
2555     // get parameter's heap region
2556     assert paramIndex2id.containsKey(paramIndex);
2557     Integer idParam = paramIndex2id.get(paramIndex);
2558
2559     assert id2hrn.containsKey(idParam);
2560     HeapRegionNode hrnParam = id2hrn.get(idParam);
2561     assert hrnParam != null;
2562
2563     // get tokens for this parameter
2564     TokenTuple p = new TokenTuple(hrnParam.getID(),
2565                                   true,
2566                                   TokenTuple.ARITY_ONE).makeCanonical();
2567
2568     TokenTuple pPlus = new TokenTuple(hrnParam.getID(),
2569                                       true,
2570                                       TokenTuple.ARITY_ONEORMORE).makeCanonical();
2571
2572     TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2573                                       true,
2574                                       TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2575
2576     // get special label p_q
2577     TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2578     assert tdParamQ != null;
2579     LabelNode lnParamQ = td2ln.get(tdParamQ);
2580     assert lnParamQ != null;
2581
2582     // then get the edge from label q to parameter's hrn
2583     ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2584     assert edgeSpecialQ != null;
2585
2586     // look through this beta set for potential aliases
2587     ReachabilitySet beta = edgeSpecialQ.getBeta();
2588     assert beta != null;
2589
2590
2591     // get tokens for summary node
2592     TokenTuple gs = new TokenTuple(as.getSummary(),
2593                                    true,
2594                                    TokenTuple.ARITY_ONE).makeCanonical();
2595
2596     TokenTuple gsPlus = new TokenTuple(as.getSummary(),
2597                                        true,
2598                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
2599
2600     TokenTuple gsStar = new TokenTuple(as.getSummary(),
2601                                        true,
2602                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2603
2604
2605     if( beta.containsTupleSetWithBoth(p,     gs) ) {
2606       return true;
2607     }
2608     if( beta.containsTupleSetWithBoth(pPlus, gs) ) {
2609       return true;
2610     }
2611     if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2612       return true;
2613     }
2614     if( beta.containsTupleSetWithBoth(p,     gsPlus) ) {
2615       return true;
2616     }
2617     if( beta.containsTupleSetWithBoth(pPlus, gsPlus) ) {
2618       return true;
2619     }
2620     if( beta.containsTupleSetWithBoth(pStar, gsPlus) ) {
2621       return true;
2622     }
2623     if( beta.containsTupleSetWithBoth(p,     gsStar) ) {
2624       return true;
2625     }
2626     if( beta.containsTupleSetWithBoth(pPlus, gsStar) ) {
2627       return true;
2628     }
2629     if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2630       return true;
2631     }
2632
2633     // check for other nodes
2634     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2635
2636       // the other nodes of an allocation site are single, no plus
2637       TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2638                                      false,
2639                                      TokenTuple.ARITY_ONE).makeCanonical();
2640
2641       TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
2642                                          false,
2643                                          TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2644
2645       if( beta.containsTupleSetWithBoth(p,     gi) ) {
2646         return true;
2647       }
2648       if( beta.containsTupleSetWithBoth(pPlus, gi) ) {
2649         return true;
2650       }
2651       if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2652         return true;
2653       }
2654       if( beta.containsTupleSetWithBoth(p,     giStar) ) {
2655         return true;
2656       }
2657       if( beta.containsTupleSetWithBoth(pPlus, giStar) ) {
2658         return true;
2659       }
2660       if( beta.containsTupleSetWithBoth(pStar, giStar) ) {
2661         return true;
2662       }
2663     }
2664
2665     return false;
2666   }
2667
2668
2669   public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2670
2671     // get tokens for summary nodes
2672     TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2673                                     true,
2674                                     TokenTuple.ARITY_ONE).makeCanonical();
2675
2676     TokenTuple gsPlus1 = new TokenTuple(as1.getSummary(),
2677                                         true,
2678                                         TokenTuple.ARITY_ONEORMORE).makeCanonical();
2679
2680     TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2681                                         true,
2682                                         TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2683
2684     // get summary node's alpha
2685     Integer idSum1 = as1.getSummary();
2686     assert id2hrn.containsKey(idSum1);
2687     HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2688     assert hrnSum1 != null;
2689     ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2690     assert alphaSum1 != null;
2691
2692
2693     // and for the other one
2694     TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2695                                     true,
2696                                     TokenTuple.ARITY_ONE).makeCanonical();
2697
2698     TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
2699                                         true,
2700                                         TokenTuple.ARITY_ONEORMORE).makeCanonical();
2701
2702     TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2703                                         true,
2704                                         TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2705
2706     // get summary node's alpha
2707     Integer idSum2 = as2.getSummary();
2708     assert id2hrn.containsKey(idSum2);
2709     HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2710     assert hrnSum2 != null;
2711     ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2712     assert alphaSum2 != null;
2713
2714     // does either one report reachability from the other tokens?
2715     if( alphaSum1.containsTuple(gsPlus2) ) {
2716       return true;
2717     }
2718     if( alphaSum1.containsTuple(gsStar2) ) {
2719       return true;
2720     }
2721     if( alphaSum2.containsTuple(gsPlus1) ) {
2722       return true;
2723     }
2724     if( alphaSum2.containsTuple(gsStar1) ) {
2725       return true;
2726     }
2727
2728     // only check ONE token if they are different sites
2729     if( as1 != as2 ) {
2730       if( alphaSum1.containsTuple(gs2) ) {
2731         return true;
2732       }
2733       if( alphaSum2.containsTuple(gs1) ) {
2734         return true;
2735       }
2736     }
2737
2738
2739     // check sum2 against alloc1 nodes
2740     for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2741       Integer idI1 = as1.getIthOldest(i);
2742       assert id2hrn.containsKey(idI1);
2743       HeapRegionNode hrnI1 = id2hrn.get(idI1);
2744       assert hrnI1 != null;
2745       ReachabilitySet alphaI1 = hrnI1.getAlpha();
2746       assert alphaI1 != null;
2747
2748       // the other nodes of an allocation site are single, no stars
2749       TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2750                                       false,
2751                                       TokenTuple.ARITY_ONE).makeCanonical();
2752
2753       TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(i),
2754                                           false,
2755                                           TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2756
2757       if( alphaSum2.containsTuple(gi1) ) {
2758         return true;
2759       }
2760       if( alphaSum2.containsTuple(giStar1) ) {
2761         return true;
2762       }
2763       if(   alphaI1.containsTuple(gs2) ) {
2764         return true;
2765       }
2766       if(   alphaI1.containsTuple(gsPlus2) ) {
2767         return true;
2768       }
2769       if(   alphaI1.containsTuple(gsStar2) ) {
2770         return true;
2771       }
2772     }
2773
2774     // check sum1 against alloc2 nodes
2775     for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2776       Integer idI2 = as2.getIthOldest(i);
2777       assert id2hrn.containsKey(idI2);
2778       HeapRegionNode hrnI2 = id2hrn.get(idI2);
2779       assert hrnI2 != null;
2780       ReachabilitySet alphaI2 = hrnI2.getAlpha();
2781       assert alphaI2 != null;
2782
2783       TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2784                                       false,
2785                                       TokenTuple.ARITY_ONE).makeCanonical();
2786
2787       TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
2788                                           false,
2789                                           TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2790
2791       if( alphaSum1.containsTuple(gi2) ) {
2792         return true;
2793       }
2794       if( alphaSum1.containsTuple(giStar2) ) {
2795         return true;
2796       }
2797       if(   alphaI2.containsTuple(gs1) ) {
2798         return true;
2799       }
2800       if(   alphaI2.containsTuple(gsPlus1) ) {
2801         return true;
2802       }
2803       if(   alphaI2.containsTuple(gsStar1) ) {
2804         return true;
2805       }
2806
2807       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2808       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2809         Integer idI1 = as1.getIthOldest(j);
2810
2811         // if these are the same site, don't look for the same token, no alias.
2812         // different tokens of the same site could alias together though
2813         if( idI1 == idI2 ) {
2814           continue;
2815         }
2816
2817         HeapRegionNode hrnI1 = id2hrn.get(idI1);
2818         ReachabilitySet alphaI1 = hrnI1.getAlpha();
2819         TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2820                                         false,
2821                                         TokenTuple.ARITY_ONE).makeCanonical();
2822
2823         TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
2824                                             false,
2825                                             TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2826
2827         if( alphaI2.containsTuple(gi1) ) {
2828           return true;
2829         }
2830         if( alphaI2.containsTuple(giStar1) ) {
2831           return true;
2832         }
2833         if( alphaI1.containsTuple(gi2) ) {
2834           return true;
2835         }
2836         if( alphaI1.containsTuple(giStar2) ) {
2837           return true;
2838         }
2839       }
2840     }
2841
2842     return false;
2843   }
2844
2845
2846   // for writing ownership graphs to dot files
2847   public void writeGraph(Descriptor methodDesc,
2848                          FlatNode fn,
2849                          boolean writeLabels,
2850                          boolean labelSelect,
2851                          boolean pruneGarbage,
2852                          boolean writeReferencers,
2853                          boolean writeParamMappings
2854                          ) throws java.io.IOException {
2855     writeGraph(
2856       methodDesc.getSymbol() +
2857       methodDesc.getNum() +
2858       fn.toString(),
2859       writeLabels,
2860       labelSelect,
2861       pruneGarbage,
2862       writeReferencers,
2863       writeParamMappings
2864       );
2865   }
2866
2867   public void writeGraph(Descriptor methodDesc,
2868                          boolean writeLabels,
2869                          boolean labelSelect,
2870                          boolean pruneGarbage,
2871                          boolean writeReferencers,
2872                          boolean writeParamMappings
2873                          ) throws java.io.IOException {
2874
2875     writeGraph(methodDesc+"COMPLETE",
2876                writeLabels,
2877                labelSelect,
2878                pruneGarbage,
2879                writeReferencers,
2880                writeParamMappings
2881                );
2882   }
2883
2884   public void writeGraph(Descriptor methodDesc,
2885                          Integer numUpdate,
2886                          boolean writeLabels,
2887                          boolean labelSelect,
2888                          boolean pruneGarbage,
2889                          boolean writeReferencers,
2890                          boolean writeParamMappings
2891                          ) throws java.io.IOException {
2892
2893     writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2894                writeLabels,
2895                labelSelect,
2896                pruneGarbage,
2897                writeReferencers,
2898                writeParamMappings
2899                );
2900   }
2901
2902   public void writeGraph(String graphName,
2903                          boolean writeLabels,
2904                          boolean labelSelect,
2905                          boolean pruneGarbage,
2906                          boolean writeReferencers,
2907                          boolean writeParamMappings
2908                          ) throws java.io.IOException {
2909
2910     // remove all non-word characters from the graph name so
2911     // the filename and identifier in dot don't cause errors
2912     graphName = graphName.replaceAll("[\\W]", "");
2913
2914     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2915     bw.write("digraph "+graphName+" {\n");
2916
2917     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2918
2919     // then visit every heap region node
2920     Set s = id2hrn.entrySet();
2921     Iterator i = s.iterator();
2922     while( i.hasNext() ) {
2923       Map.Entry me  = (Map.Entry)i.next();
2924       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2925       if( !pruneGarbage ||
2926           hrn.isFlagged() ||
2927           hrn.getDescription().startsWith("param")
2928           ) {
2929
2930         if( !visited.contains(hrn) ) {
2931           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2932                                   hrn,
2933                                   bw,
2934                                   null,
2935                                   visited,
2936                                   writeReferencers);
2937         }
2938       }
2939     }
2940
2941     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2942
2943     if( writeParamMappings ) {
2944       Set df = paramIndex2id.entrySet();
2945       Iterator ih = df.iterator();
2946       while( ih.hasNext() ) {
2947         Map.Entry meh = (Map.Entry)ih.next();
2948         Integer pi = (Integer) meh.getKey();
2949         Integer id = (Integer) meh.getValue();
2950         bw.write("  pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2951       }
2952     }
2953
2954     // then visit every label node, useful for debugging
2955     if( writeLabels ) {
2956       s = td2ln.entrySet();
2957       i = s.iterator();
2958       while( i.hasNext() ) {
2959         Map.Entry me = (Map.Entry)i.next();
2960         LabelNode ln = (LabelNode) me.getValue();
2961
2962         if( labelSelect ) {
2963           String labelStr = ln.getTempDescriptorString();
2964           if( labelStr.startsWith("___temp") ||
2965               labelStr.startsWith("___dst") ||
2966               labelStr.startsWith("___srctmp") ||
2967               labelStr.startsWith("___neverused")   ) {
2968             continue;
2969           }
2970         }
2971
2972         //bw.write("  "+ln.toString() + ";\n");
2973
2974         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2975         while( heapRegionsItr.hasNext() ) {
2976           ReferenceEdge edge = heapRegionsItr.next();
2977           HeapRegionNode hrn  = edge.getDst();
2978
2979           if( pruneGarbage && !visited.contains(hrn) ) {
2980             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2981                                     hrn,
2982                                     bw,
2983                                     null,
2984                                     visited,
2985                                     writeReferencers);
2986           }
2987
2988           bw.write("  "        + ln.toString() +
2989                    " -> "      + hrn.toString() +
2990                    "[label=\"" + edge.toGraphEdgeString() +
2991                    "\",decorate];\n");
2992         }
2993       }
2994     }
2995
2996
2997     bw.write("}\n");
2998     bw.close();
2999   }
3000
3001   protected void traverseHeapRegionNodes(int mode,
3002                                          HeapRegionNode hrn,
3003                                          BufferedWriter bw,
3004                                          TempDescriptor td,
3005                                          HashSet<HeapRegionNode> visited,
3006                                          boolean writeReferencers
3007                                          ) throws java.io.IOException {
3008
3009     if( visited.contains(hrn) ) {
3010       return;
3011     }
3012     visited.add(hrn);
3013
3014     switch( mode ) {
3015     case VISIT_HRN_WRITE_FULL:
3016
3017       String attributes = "[";
3018
3019       if( hrn.isSingleObject() ) {
3020         attributes += "shape=box";
3021       } else {
3022         attributes += "shape=Msquare";
3023       }
3024
3025       if( hrn.isFlagged() ) {
3026         attributes += ",style=filled,fillcolor=lightgrey";
3027       }
3028
3029       attributes += ",label=\"ID"        +
3030                     hrn.getID()          +
3031                     "\\n"                +
3032                     hrn.getDescription() +
3033                     "\\n"                +
3034                     hrn.getAlphaString() +
3035                     "\"]";
3036
3037       bw.write("  " + hrn.toString() + attributes + ";\n");
3038       break;
3039     }
3040
3041
3042     // useful for debugging
3043     if( writeReferencers ) {
3044       OwnershipNode onRef  = null;
3045       Iterator refItr = hrn.iteratorToReferencers();
3046       while( refItr.hasNext() ) {
3047         onRef = (OwnershipNode) refItr.next();
3048
3049         switch( mode ) {
3050         case VISIT_HRN_WRITE_FULL:
3051           bw.write("  "                    + hrn.toString() +
3052                    " -> "                  + onRef.toString() +
3053                    "[color=lightgray];\n");
3054           break;
3055         }
3056       }
3057     }
3058
3059     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
3060     while( childRegionsItr.hasNext() ) {
3061       ReferenceEdge edge     = childRegionsItr.next();
3062       HeapRegionNode hrnChild = edge.getDst();
3063
3064       switch( mode ) {
3065       case VISIT_HRN_WRITE_FULL:
3066         bw.write("  "        + hrn.toString() +
3067                  " -> "      + hrnChild.toString() +
3068                  "[label=\"" + edge.toGraphEdgeString() +
3069                  "\",decorate];\n");
3070         break;
3071       }
3072
3073       traverseHeapRegionNodes(mode,
3074                               hrnChild,
3075                               bw,
3076                               td,
3077                               visited,
3078                               writeReferencers);
3079     }
3080   }
3081 }