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