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