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