Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8 public class OwnershipGraph {
   9
  10   private int allocationDepth;
  11
  12   // there was already one other very similar reason
  13   // for traversing heap nodes that is no longer needed
  14   // instead of writing a new heap region visitor, use
  15   // the existing method with a new mode to describe what
  16   // actions to take during the traversal
  17   protected static final int VISIT_HRN_WRITE_FULL = 0;
  18
  19   protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
  20
  21
  22   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  23   public Hashtable<TempDescriptor, LabelNode     > td2ln;
  24   public Hashtable<Integer,        Integer       > id2paramIndex;
  25   public Hashtable<Integer,        Integer       > paramIndex2id;
  26   public Hashtable<Integer,        TempDescriptor> paramIndex2tdQ;
  27
  28   public HashSet<AllocationSite> allocationSites;
  29
  30
  31
  32
  33   public OwnershipGraph(int allocationDepth) {
  34     this.allocationDepth = allocationDepth;
  35
  36     id2hrn         = new Hashtable<Integer,        HeapRegionNode>();
  37     td2ln          = new Hashtable<TempDescriptor, LabelNode     >();
  38     id2paramIndex  = new Hashtable<Integer,        Integer       >();
  39     paramIndex2id  = new Hashtable<Integer,        Integer       >();
  40     paramIndex2tdQ = new Hashtable<Integer,        TempDescriptor>();
  41
  42     allocationSites = new HashSet <AllocationSite>();
  43   }
  44
  45
  46   // label nodes are much easier to deal with than
  47   // heap region nodes.  Whenever there is a request
  48   // for the label node that is associated with a
  49   // temp descriptor we can either find it or make a
  50   // new one and return it.  This is because temp
  51   // descriptors are globally unique and every label
  52   // node is mapped to exactly one temp descriptor.
  53   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  54     assert td != null;
  55
  56     if( !td2ln.containsKey(td) ) {
  57       td2ln.put(td, new LabelNode(td) );
  58     }
  59
  60     return td2ln.get(td);
  61   }
  62
  63
  64   // the reason for this method is to have the option
  65   // creating new heap regions with specific IDs, or
  66   // duplicating heap regions with specific IDs (especially
  67   // in the merge() operation) or to create new heap
  68   // regions with a new unique ID.
  69   protected HeapRegionNode
  70   createNewHeapRegionNode(Integer id,
  71                           boolean isSingleObject,
  72                           boolean isFlagged,
  73                           boolean isNewSummary,
  74                           boolean isParameter,
  75                           AllocationSite allocSite,
  76                           ReachabilitySet alpha,
  77                           String description) {
  78
  79     if( id == null ) {
  80       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  81     }
  82
  83     if( alpha == null ) {
  84       if( isFlagged || isParameter ) {
  85         alpha = new ReachabilitySet(new TokenTuple(id,
  86                                                    !isSingleObject,
  87                                                    TokenTuple.ARITY_ONE)
  88                                     ).makeCanonical();
  89       } else {
  90         alpha = new ReachabilitySet(new TokenTupleSet()
  91                                     ).makeCanonical();
  92       }
  93     }
  94
  95     HeapRegionNode hrn = new HeapRegionNode(id,
  96                                             isSingleObject,
  97                                             isFlagged,
  98                                             isNewSummary,
  99                                             allocSite,
 100                                             alpha,
 101                                             description);
 102     id2hrn.put(id, hrn);
 103     return hrn;
 104   }
 105
 106
 107
 108   ////////////////////////////////////////////////
 109   //
 110   //  Low-level referencee and referencer methods
 111   //
 112   //  These methods provide the lowest level for
 113   //  creating references between ownership nodes
 114   //  and handling the details of maintaining both
 115   //  list of referencers and referencees.
 116   //
 117   ////////////////////////////////////////////////
 118   protected void addReferenceEdge(OwnershipNode referencer,
 119                                   HeapRegionNode referencee,
 120                                   ReferenceEdge edge) {
 121     assert referencer != null;
 122     assert referencee != null;
 123     assert edge       != null;
 124     assert edge.getSrc() == referencer;
 125     assert edge.getDst() == referencee;
 126
 127     referencer.addReferencee(edge);
 128     referencee.addReferencer(edge);
 129   }
 130
 131   protected void removeReferenceEdge(OwnershipNode referencer,
 132                                      HeapRegionNode referencee,
 133                                      FieldDescriptor fieldDesc) {
 134     assert referencer != null;
 135     assert referencee != null;
 136
 137     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 138                                                    fieldDesc);
 139     assert edge != null;
 140     assert edge == referencee.getReferenceFrom(referencer,
 141                                                fieldDesc);
 142
 143     referencer.removeReferencee(edge);
 144     referencee.removeReferencer(edge);
 145   }
 146
 147   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 148                                          FieldDescriptor fieldDesc,
 149                                          boolean removeAll) {
 150     assert referencer != null;
 151
 152     // get a copy of the set to iterate over, otherwise
 153     // we will be trying to take apart the set as we
 154     // are iterating over it, which won't work
 155     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 156     while( i.hasNext() ) {
 157       ReferenceEdge edge = i.next();
 158
 159       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 160         HeapRegionNode referencee = edge.getDst();
 161
 162         removeReferenceEdge(referencer,
 163                             referencee,
 164                             edge.getFieldDesc() );
 165       }
 166     }
 167   }
 168
 169   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 170                                        FieldDescriptor fieldDesc,
 171                                        boolean removeAll) {
 172     assert referencee != null;
 173
 174     // get a copy of the set to iterate over, otherwise
 175     // we will be trying to take apart the set as we
 176     // are iterating over it, which won't work
 177     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 178     while( i.hasNext() ) {
 179       ReferenceEdge edge = i.next();
 180
 181       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 182         OwnershipNode referencer = edge.getSrc();
 183         removeReferenceEdge(referencer,
 184                             referencee,
 185                             edge.getFieldDesc() );
 186       }
 187     }
 188   }
 189
 190
 191   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
 192                                           ChangeTupleSet c0,
 193                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
 194                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
 195
 196     HashSet<HeapRegionNode> todoNodes
 197     = new HashSet<HeapRegionNode>();
 198     todoNodes.add(nPrime);
 199
 200     HashSet<ReferenceEdge> todoEdges
 201     = new HashSet<ReferenceEdge>();
 202
 203     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 204     = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 205     nodePlannedChanges.put(nPrime, c0);
 206
 207     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
 208     = new Hashtable<ReferenceEdge, ChangeTupleSet>();
 209
 210
 211     while( !todoNodes.isEmpty() ) {
 212       HeapRegionNode n = todoNodes.iterator().next();
 213       ChangeTupleSet C = nodePlannedChanges.get(n);
 214
 215       Iterator itrC = C.iterator();
 216       while( itrC.hasNext() ) {
 217         ChangeTuple c = (ChangeTuple) itrC.next();
 218
 219         if( n.getAlpha().contains(c.getSetToMatch() ) ) {
 220           ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
 221           n.setAlphaNew(n.getAlphaNew().union(withChange) );
 222           nodesWithNewAlpha.add(n);
 223         }
 224       }
 225
 226       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 227       while( referItr.hasNext() ) {
 228         ReferenceEdge edge = referItr.next();
 229         todoEdges.add(edge);
 230
 231         if( !edgePlannedChanges.containsKey(edge) ) {
 232           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
 233         }
 234
 235         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 236       }
 237
 238       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
 239       while( refeeItr.hasNext() ) {
 240         ReferenceEdge edgeF = refeeItr.next();
 241         HeapRegionNode m     = edgeF.getDst();
 242
 243         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 244
 245         Iterator<ChangeTuple> itrCprime = C.iterator();
 246         while( itrCprime.hasNext() ) {
 247           ChangeTuple c = itrCprime.next();
 248           if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
 249             changesToPass = changesToPass.union(c);
 250           }
 251         }
 252
 253         if( !changesToPass.isEmpty() ) {
 254           if( !nodePlannedChanges.containsKey(m) ) {
 255             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
 256           }
 257
 258           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
 259
 260           if( !changesToPass.isSubset(currentChanges) ) {
 261
 262             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 263             todoNodes.add(m);
 264           }
 265         }
 266       }
 267
 268       todoNodes.remove(n);
 269     }
 270
 271     propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
 272   }
 273
 274
 275   protected void propagateTokensOverEdges(
 276     HashSet<ReferenceEdge>                   todoEdges,
 277     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
 278     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
 279
 280
 281     while( !todoEdges.isEmpty() ) {
 282       ReferenceEdge edgeE = todoEdges.iterator().next();
 283       todoEdges.remove(edgeE);
 284
 285       if( !edgePlannedChanges.containsKey(edgeE) ) {
 286         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
 287       }
 288
 289       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
 290
 291       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 292
 293       Iterator<ChangeTuple> itrC = C.iterator();
 294       while( itrC.hasNext() ) {
 295         ChangeTuple c = itrC.next();
 296         if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
 297           ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
 298           edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
 299           edgesWithNewBeta.add(edgeE);
 300           changesToPass = changesToPass.union(c);
 301         }
 302       }
 303
 304       OwnershipNode onSrc = edgeE.getSrc();
 305
 306       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 307         HeapRegionNode n = (HeapRegionNode) onSrc;
 308
 309         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 310         while( referItr.hasNext() ) {
 311           ReferenceEdge edgeF = referItr.next();
 312
 313           if( !edgePlannedChanges.containsKey(edgeF) ) {
 314             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
 315           }
 316
 317           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
 318
 319           if( !changesToPass.isSubset(currentChanges) ) {
 320             todoEdges.add(edgeF);
 321             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
 322           }
 323         }
 324       }
 325     }
 326   }
 327
 328
 329   ////////////////////////////////////////////////////
 330   //
 331   //  Assignment Operation Methods
 332   //
 333   //  These methods are high-level operations for
 334   //  modeling program assignment statements using
 335   //  the low-level reference create/remove methods
 336   //  above.
 337   //
 338   //  The destination in an assignment statement is
 339   //  going to have new references.  The method of
 340   //  determining the references depends on the type
 341   //  of the FlatNode assignment and the predicates
 342   //  of the nodes and edges involved.
 343   //
 344   ////////////////////////////////////////////////////
 345   public void assignTempXEqualToTempY(TempDescriptor x,
 346                                       TempDescriptor y) {
 347
 348     LabelNode lnX = getLabelNodeFromTemp(x);
 349     LabelNode lnY = getLabelNodeFromTemp(y);
 350
 351     clearReferenceEdgesFrom(lnX, null, true);
 352
 353     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 354     while( itrYhrn.hasNext() ) {
 355       ReferenceEdge edgeY       = itrYhrn.next();
 356       HeapRegionNode referencee = edgeY.getDst();
 357       ReferenceEdge edgeNew    = edgeY.copy();
 358       edgeNew.setSrc(lnX);
 359
 360       addReferenceEdge(lnX, referencee, edgeNew);
 361     }
 362   }
 363
 364
 365   public void assignTempXEqualToTempYFieldF(TempDescriptor x,
 366                                             TempDescriptor y,
 367                                             FieldDescriptor f) {
 368     LabelNode lnX = getLabelNodeFromTemp(x);
 369     LabelNode lnY = getLabelNodeFromTemp(y);
 370
 371     clearReferenceEdgesFrom(lnX, null, true);
 372
 373     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 374     while( itrYhrn.hasNext() ) {
 375       ReferenceEdge edgeY = itrYhrn.next();
 376       HeapRegionNode hrnY  = edgeY.getDst();
 377       ReachabilitySet betaY = edgeY.getBeta();
 378
 379       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 380       while( itrHrnFhrn.hasNext() ) {
 381         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 382         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 383         ReachabilitySet betaHrn = edgeHrn.getBeta();
 384
 385         if( edgeHrn.getFieldDesc() == null ||
 386             edgeHrn.getFieldDesc() == f ) {
 387
 388           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 389                                                     hrnHrn,
 390                                                     f,
 391                                                     false,
 392                                                     betaY.intersection(betaHrn) );
 393
 394           addReferenceEdge(lnX, hrnHrn, edgeNew);
 395         }
 396       }
 397     }
 398   }
 399
 400
 401   public void assignTempXFieldFEqualToTempY(TempDescriptor x,
 402                                             FieldDescriptor f,
 403                                             TempDescriptor y) {
 404     LabelNode lnX = getLabelNodeFromTemp(x);
 405     LabelNode lnY = getLabelNodeFromTemp(y);
 406
 407     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 408     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 409
 410     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 411     while( itrXhrn.hasNext() ) {
 412       ReferenceEdge edgeX = itrXhrn.next();
 413       HeapRegionNode hrnX  = edgeX.getDst();
 414       ReachabilitySet betaX = edgeX.getBeta();
 415
 416       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 417
 418       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 419       while( itrYhrn.hasNext() ) {
 420         ReferenceEdge edgeY = itrYhrn.next();
 421         HeapRegionNode hrnY  = edgeY.getDst();
 422         ReachabilitySet O     = edgeY.getBeta();
 423
 424
 425         // propagate tokens over nodes starting from hrnSrc, and it will
 426         // take care of propagating back up edges from any touched nodes
 427         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 428         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 429
 430
 431         // then propagate back just up the edges from hrn
 432         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 433
 434         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 435
 436         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 437           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 438
 439         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 440         while( referItr.hasNext() ) {
 441           ReferenceEdge edgeUpstream = referItr.next();
 442           todoEdges.add(edgeUpstream);
 443           edgePlannedChanges.put(edgeUpstream, Cx);
 444         }
 445
 446         propagateTokensOverEdges(todoEdges,
 447                                  edgePlannedChanges,
 448                                  edgesWithNewBeta);
 449
 450
 451
 452         //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
 453
 454         // create the actual reference edge hrnX.f -> hrnY
 455         ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
 456                                                   hrnY,
 457                                                   f,
 458                                                   false,
 459                                                   edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
 460                                                   //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
 461                                                   );
 462         addReferenceEdge(hrnX, hrnY, edgeNew);
 463
 464         /*
 465            if( f != null ) {
 466             // we can do a strong update here if one of two cases holds
 467             // SAVE FOR LATER, WITHOUT STILL CORRECT
 468             if( (hrnX.getNumReferencers() == 1)                           ||
 469                 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
 470               ) {
 471                 clearReferenceEdgesFrom( hrnX, f, false );
 472             }
 473
 474             addReferenceEdge( hrnX, hrnY, edgeNew );
 475
 476            } else {
 477             // if the field is null, or "any" field, then
 478             // look to see if an any field already exists
 479             // and merge with it, otherwise just add the edge
 480             ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
 481
 482             if( edgeExisting != null ) {
 483                 edgeExisting.setBetaNew(
 484                   edgeExisting.getBetaNew().union( edgeNew.getBeta() )
 485                                        );
 486                 // a new edge here cannot be reflexive, so existing will
 487                 // always be also not reflexive anymore
 488                 edgeExisting.setIsInitialParamReflexive( false );
 489
 490             } else {
 491                 addReferenceEdge( hrnX, hrnY, edgeNew );
 492             }
 493            }
 494          */
 495       }
 496     }
 497
 498     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 499     while( nodeItr.hasNext() ) {
 500       nodeItr.next().applyAlphaNew();
 501     }
 502
 503     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
 504     while( edgeItr.hasNext() ) {
 505       edgeItr.next().applyBetaNew();
 506     }
 507   }
 508
 509
 510   public void assignTempEqualToParamAlloc(TempDescriptor td,
 511                                           boolean isTask,
 512                                           Integer paramIndex) {
 513     assert td != null;
 514
 515     LabelNode lnParam = getLabelNodeFromTemp(td);
 516     HeapRegionNode hrn = createNewHeapRegionNode(null,
 517                                                  false,
 518                                                  isTask,
 519                                                  false,
 520                                                  true,
 521                                                  null,
 522                                                  null,
 523                                                  "param" + paramIndex);
 524
 525     // this is a non-program-accessible label that picks up beta
 526     // info to be used for fixing a caller of this method
 527     TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
 528     LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
 529
 530     // keep track of heap regions that were created for
 531     // parameter labels, the index of the parameter they
 532     // are for is important when resolving method calls
 533     Integer newID = hrn.getID();
 534     assert !id2paramIndex.containsKey(newID);
 535     assert !id2paramIndex.containsValue(paramIndex);
 536     id2paramIndex.put(newID, paramIndex);
 537     paramIndex2id.put(paramIndex, newID);
 538     paramIndex2tdQ.put(paramIndex, tdParamQ);
 539
 540     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
 541                                                               true,
 542                                                               TokenTuple.ARITY_ONE) );
 543
 544     // heap regions for parameters are always multiple object (see above)
 545     // and have a reference to themselves, because we can't know the
 546     // structure of memory that is passed into the method.  We're assuming
 547     // the worst here.
 548
 549     ReferenceEdge edgeFromLabel =
 550       new ReferenceEdge(lnParam, hrn, null, false, beta);
 551
 552     ReferenceEdge edgeFromLabelQ =
 553       new ReferenceEdge(lnParamQ, hrn, null, false, beta);
 554
 555     ReferenceEdge edgeReflexive =
 556       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 557
 558     addReferenceEdge(lnParam,  hrn, edgeFromLabel);
 559     addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
 560     addReferenceEdge(hrn,      hrn, edgeReflexive);
 561   }
 562
 563
 564   public void assignReturnEqualToTemp(TempDescriptor x) {
 565
 566     LabelNode lnR = getLabelNodeFromTemp(tdReturn);
 567     LabelNode lnX = getLabelNodeFromTemp(x);
 568
 569     clearReferenceEdgesFrom(lnR, null, true);
 570
 571     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 572     while( itrXhrn.hasNext() ) {
 573       ReferenceEdge edgeX       = itrXhrn.next();
 574       HeapRegionNode referencee = edgeX.getDst();
 575       ReferenceEdge edgeNew    = edgeX.copy();
 576       edgeNew.setSrc(lnR);
 577
 578       addReferenceEdge(lnR, referencee, edgeNew);
 579     }
 580   }
 581
 582
 583   public void assignTempEqualToNewAlloc(TempDescriptor x,
 584                                         AllocationSite as) {
 585     assert x  != null;
 586     assert as != null;
 587
 588     age(as);
 589
 590     // after the age operation the newest (or zero-ith oldest)
 591     // node associated with the allocation site should have
 592     // no references to it as if it were a newly allocated
 593     // heap region, so make a reference to it to complete
 594     // this operation
 595
 596     Integer idNewest  = as.getIthOldest(0);
 597     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 598     assert hrnNewest != null;
 599
 600     LabelNode lnX = getLabelNodeFromTemp(x);
 601     clearReferenceEdgesFrom(lnX, null, true);
 602
 603     ReferenceEdge edgeNew =
 604       new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
 605
 606     addReferenceEdge(lnX, hrnNewest, edgeNew);
 607   }
 608
 609
 610   // use the allocation site (unique to entire analysis) to
 611   // locate the heap region nodes in this ownership graph
 612   // that should be aged.  The process models the allocation
 613   // of new objects and collects all the oldest allocations
 614   // in a summary node to allow for a finite analysis
 615   //
 616   // There is an additional property of this method.  After
 617   // running it on a particular ownership graph (many graphs
 618   // may have heap regions related to the same allocation site)
 619   // the heap region node objects in this ownership graph will be
 620   // allocated.  Therefore, after aging a graph for an allocation
 621   // site, attempts to retrieve the heap region nodes using the
 622   // integer id's contained in the allocation site should always
 623   // return non-null heap regions.
 624   public void age(AllocationSite as) {
 625
 626     // aging adds this allocation site to the graph's
 627     // list of sites that exist in the graph, or does
 628     // nothing if the site is already in the list
 629     allocationSites.add(as);
 630
 631     // get the summary node for the allocation site in the context
 632     // of this particular ownership graph
 633     HeapRegionNode hrnSummary = getSummaryNode(as);
 634
 635     // merge oldest node into summary
 636     Integer idK  = as.getOldest();
 637     HeapRegionNode hrnK = id2hrn.get(idK);
 638     mergeIntoSummary(hrnK, hrnSummary);
 639
 640     // move down the line of heap region nodes
 641     // clobbering the ith and transferring all references
 642     // to and from i-1 to node i.  Note that this clobbers
 643     // the oldest node (hrnK) that was just merged into
 644     // the summary
 645     for( int i = allocationDepth - 1; i > 0; --i ) {
 646
 647       // move references from the i-1 oldest to the ith oldest
 648       Integer idIth     = as.getIthOldest(i);
 649       HeapRegionNode hrnI      = id2hrn.get(idIth);
 650       Integer idImin1th = as.getIthOldest(i - 1);
 651       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 652
 653       transferOnto(hrnImin1, hrnI);
 654     }
 655
 656     // as stated above, the newest node should have had its
 657     // references moved over to the second oldest, so we wipe newest
 658     // in preparation for being the new object to assign something to
 659     Integer id0th = as.getIthOldest(0);
 660     HeapRegionNode hrn0  = id2hrn.get(id0th);
 661     assert hrn0 != null;
 662
 663     // clear all references in and out of newest node
 664     clearReferenceEdgesFrom(hrn0, null, true);
 665     clearReferenceEdgesTo(hrn0, null, true);
 666
 667
 668     // now tokens in reachability sets need to "age" also
 669     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 670     while( itrAllLabelNodes.hasNext() ) {
 671       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 672       LabelNode ln = (LabelNode) me.getValue();
 673
 674       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 675       while( itrEdges.hasNext() ) {
 676         ageTokens(as, itrEdges.next() );
 677       }
 678     }
 679
 680     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 681     while( itrAllHRNodes.hasNext() ) {
 682       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
 683       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 684
 685       ageTokens(as, hrnToAge);
 686
 687       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
 688       while( itrEdges.hasNext() ) {
 689         ageTokens(as, itrEdges.next() );
 690       }
 691     }
 692
 693
 694     // after tokens have been aged, reset newest node's reachability
 695     if( hrn0.isFlagged() ) {
 696       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
 697                                           new TokenTuple(hrn0)
 698                                           )
 699                                         ).makeCanonical()
 700                     );
 701     } else {
 702       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
 703                                         ).makeCanonical()
 704                     );
 705     }
 706   }
 707
 708
 709   protected HeapRegionNode getSummaryNode(AllocationSite as) {
 710
 711     Integer idSummary  = as.getSummary();
 712     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
 713
 714     // If this is null then we haven't touched this allocation site
 715     // in the context of the current ownership graph, so allocate
 716     // heap region nodes appropriate for the entire allocation site.
 717     // This should only happen once per ownership graph per allocation site,
 718     // and a particular integer id can be used to locate the heap region
 719     // in different ownership graphs that represents the same part of an
 720     // allocation site.
 721     if( hrnSummary == null ) {
 722
 723       boolean hasFlags = false;
 724       if( as.getType().isClass() ) {
 725         hasFlags = as.getType().getClassDesc().hasFlags();
 726       }
 727
 728       hrnSummary = createNewHeapRegionNode(idSummary,
 729                                            false,
 730                                            hasFlags,
 731                                            true,
 732                                            false,
 733                                            as,
 734                                            null,
 735                                            as + "\\n" + as.getType() + "\\nsummary");
 736
 737       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 738         Integer idIth = as.getIthOldest(i);
 739         assert !id2hrn.containsKey(idIth);
 740         createNewHeapRegionNode(idIth,
 741                                 true,
 742                                 hasFlags,
 743                                 false,
 744                                 false,
 745                                 as,
 746                                 null,
 747                                 as + "\\n" + as.getType() + "\\n" + i + " oldest");
 748       }
 749     }
 750
 751     return hrnSummary;
 752   }
 753
 754
 755   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
 756
 757     Integer idShadowSummary  = as.getSummaryShadow();
 758     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
 759
 760     if( hrnShadowSummary == null ) {
 761
 762       boolean hasFlags = false;
 763       if( as.getType().isClass() ) {
 764         hasFlags = as.getType().getClassDesc().hasFlags();
 765       }
 766
 767       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
 768                                                  false,
 769                                                  hasFlags,
 770                                                  true,
 771                                                  false,
 772                                                  as,
 773                                                  null,
 774                                                  as + "\\n" + as.getType() + "\\nshadowSum");
 775
 776       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 777         Integer idShadowIth = as.getIthOldestShadow(i);
 778         assert !id2hrn.containsKey(idShadowIth);
 779         createNewHeapRegionNode(idShadowIth,
 780                                 true,
 781                                 hasFlags,
 782                                 false,
 783                                 false,
 784                                 as,
 785                                 null,
 786                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
 787       }
 788     }
 789
 790     return hrnShadowSummary;
 791   }
 792
 793
 794   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
 795     assert hrnSummary.isNewSummary();
 796
 797     // transfer references _from_ hrn over to hrnSummary
 798     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
 799     while( itrReferencee.hasNext() ) {
 800       ReferenceEdge edge       = itrReferencee.next();
 801       ReferenceEdge edgeMerged = edge.copy();
 802       edgeMerged.setSrc(hrnSummary);
 803
 804       HeapRegionNode hrnReferencee = edge.getDst();
 805       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
 806
 807       if( edgeSummary == null ) {
 808         // the merge is trivial, nothing to be done
 809       } else {
 810         // otherwise an edge from the referencer to hrnSummary exists already
 811         // and the edge referencer->hrn should be merged with it
 812         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 813       }
 814
 815       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
 816     }
 817
 818     // next transfer references _to_ hrn over to hrnSummary
 819     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
 820     while( itrReferencer.hasNext() ) {
 821       ReferenceEdge edge         = itrReferencer.next();
 822       ReferenceEdge edgeMerged   = edge.copy();
 823       edgeMerged.setDst(hrnSummary);
 824
 825       OwnershipNode onReferencer = edge.getSrc();
 826       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
 827
 828       if( edgeSummary == null ) {
 829         // the merge is trivial, nothing to be done
 830       } else {
 831         // otherwise an edge from the referencer to alpha_S exists already
 832         // and the edge referencer->alpha_K should be merged with it
 833         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 834       }
 835
 836       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
 837     }
 838
 839     // then merge hrn reachability into hrnSummary
 840     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
 841   }
 842
 843
 844   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
 845
 846     // clear references in and out of node i
 847     clearReferenceEdgesFrom(hrnB, null, true);
 848     clearReferenceEdgesTo(hrnB, null, true);
 849
 850     // copy each edge in and out of A to B
 851     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
 852     while( itrReferencee.hasNext() ) {
 853       ReferenceEdge edge          = itrReferencee.next();
 854       HeapRegionNode hrnReferencee = edge.getDst();
 855       ReferenceEdge edgeNew       = edge.copy();
 856       edgeNew.setSrc(hrnB);
 857
 858       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
 859     }
 860
 861     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
 862     while( itrReferencer.hasNext() ) {
 863       ReferenceEdge edge         = itrReferencer.next();
 864       OwnershipNode onReferencer = edge.getSrc();
 865       ReferenceEdge edgeNew      = edge.copy();
 866       edgeNew.setDst(hrnB);
 867
 868       addReferenceEdge(onReferencer, hrnB, edgeNew);
 869     }
 870
 871     // replace hrnB reachability with hrnA's
 872     hrnB.setAlpha(hrnA.getAlpha() );
 873   }
 874
 875
 876   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
 877     edge.setBeta(edge.getBeta().ageTokens(as) );
 878   }
 879
 880   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
 881     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
 882   }
 883
 884
 885   public void resolveMethodCall(FlatCall fc,
 886                                 boolean isStatic,
 887                                 FlatMethod fm,
 888                                 OwnershipGraph ogCallee) {
 889
 890
 891     // define rewrite rules and other structures to organize
 892     // data by parameter/argument index
 893     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
 894       new Hashtable<Integer, ReachabilitySet>();
 895
 896     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
 897       new Hashtable<Integer, ReachabilitySet>();
 898
 899     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
 900       new Hashtable<Integer, ReachabilitySet>();
 901
 902     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
 903       new Hashtable<Integer, ReachabilitySet>();
 904
 905     // helpful structures
 906     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
 907       new Hashtable<TokenTuple, Integer>();
 908
 909     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
 910       new Hashtable<Integer, TokenTuple>();
 911
 912     Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
 913       new Hashtable<TokenTuple, Integer>();
 914
 915     Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
 916       new Hashtable<Integer, TokenTuple>();
 917
 918     Hashtable<Integer, LabelNode> paramIndex2ln =
 919       new Hashtable<Integer, LabelNode>();
 920
 921     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
 922       new Hashtable<Integer, HashSet<HeapRegionNode> >();
 923
 924
 925     // add a bogus entry with the identity rule for easy rewrite
 926     // of new callee nodes and edges, doesn't belong to any parameter
 927     Integer bogusID = new Integer(-1);
 928     Integer bogusIndex = new Integer(-1);
 929     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
 930     TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
 931     ReachabilitySet rsIdentity =
 932       new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
 933
 934     paramIndex2rewriteH.put(bogusIndex, rsIdentity);
 935     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
 936     paramToken2paramIndex.put(bogusToken, bogusIndex);
 937     paramIndex2paramToken.put(bogusIndex, bogusToken);
 938     paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
 939     paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
 940
 941
 942     for( int i = 0; i < fm.numParameters(); ++i ) {
 943       Integer paramIndex = new Integer(i);
 944
 945       assert ogCallee.paramIndex2id.containsKey(paramIndex);
 946       Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
 947
 948       assert ogCallee.id2hrn.containsKey(idParam);
 949       HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
 950       assert hrnParam != null;
 951       paramIndex2rewriteH.put(paramIndex,
 952
 953                               toShadowTokens(ogCallee, hrnParam.getAlpha() )
 954                               );
 955
 956       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
 957       assert edgeReflexive_i != null;
 958       paramIndex2rewriteJ.put(paramIndex,
 959                               toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
 960                               );
 961
 962       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
 963       assert tdParamQ != null;
 964       LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
 965       assert lnParamQ != null;
 966       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
 967       assert edgeSpecialQ_i != null;
 968       paramIndex2rewriteK.put(paramIndex,
 969                               toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
 970                               );
 971
 972       TokenTuple p_i = new TokenTuple(hrnParam.getID(),
 973                                       true,
 974                                       TokenTuple.ARITY_ONE).makeCanonical();
 975       paramToken2paramIndex.put(p_i, paramIndex);
 976       paramIndex2paramToken.put(paramIndex, p_i);
 977
 978       TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
 979                                            true,
 980                                            TokenTuple.ARITY_MANY).makeCanonical();
 981       paramTokenStar2paramIndex.put(p_i_star, paramIndex);
 982       paramIndex2paramTokenStar.put(paramIndex, p_i_star);
 983
 984       // now depending on whether the callee is static or not
 985       // we need to account for a "this" argument in order to
 986       // find the matching argument in the caller context
 987       TempDescriptor argTemp_i;
 988       if( isStatic ) {
 989         argTemp_i = fc.getArg(paramIndex);
 990       } else {
 991         if( paramIndex == 0 ) {
 992           argTemp_i = fc.getThis();
 993         } else {
 994           argTemp_i = fc.getArg(paramIndex - 1);
 995         }
 996       }
 997
 998       // in non-static methods there is a "this" pointer
 999       // that should be taken into account
1000       if( isStatic ) {
1001         assert fc.numArgs()     == fm.numParameters();
1002       } else {
1003         assert fc.numArgs() + 1 == fm.numParameters();
1004       }
1005
1006       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1007       paramIndex2ln.put(paramIndex, argLabel_i);
1008
1009       ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
1010       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1011       while( edgeItr.hasNext() ) {
1012         ReferenceEdge edge = edgeItr.next();
1013         D_i = D_i.union(edge.getBeta() );
1014       }
1015       D_i = D_i.exhaustiveArityCombinations();
1016       paramIndex2rewriteD.put(paramIndex, D_i);
1017     }
1018
1019
1020     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1021     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1022
1023     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1024     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1025
1026     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1027     while( lnArgItr.hasNext() ) {
1028       Map.Entry me      = (Map.Entry)lnArgItr.next();
1029       Integer index   = (Integer)   me.getKey();
1030       LabelNode lnArg_i = (LabelNode) me.getValue();
1031
1032       // rewrite alpha for the nodes reachable from argument label i
1033       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1034       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1035
1036       // to find all reachable nodes, start with label referencees
1037       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1038       while( edgeArgItr.hasNext() ) {
1039         ReferenceEdge edge = edgeArgItr.next();
1040         todoNodes.add(edge.getDst() );
1041       }
1042
1043       // then follow links until all reachable nodes have been found
1044       while( !todoNodes.isEmpty() ) {
1045         HeapRegionNode hrn = todoNodes.iterator().next();
1046         todoNodes.remove(hrn);
1047         reachableNodes.add(hrn);
1048
1049         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1050         while( edgeItr.hasNext() ) {
1051           ReferenceEdge edge = edgeItr.next();
1052
1053           if( !reachableNodes.contains(edge.getDst() ) ) {
1054             todoNodes.add(edge.getDst() );
1055           }
1056         }
1057       }
1058
1059       // save for later
1060       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1061
1062       // now iterate over reachable nodes to update their alpha, and
1063       // classify edges found as "argument reachable" or "upstream"
1064       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1065       while( hrnItr.hasNext() ) {
1066         HeapRegionNode hrn = hrnItr.next();
1067
1068         rewriteCallerNodeAlpha(fm.numParameters(),
1069                                index,
1070                                hrn,
1071                                paramIndex2rewriteH,
1072                                paramIndex2rewriteD,
1073                                paramIndex2paramToken,
1074                                paramIndex2paramTokenStar);
1075
1076         nodesWithNewAlpha.add(hrn);
1077
1078         // look at all incoming edges to the reachable nodes
1079         // and sort them as edges reachable from the argument
1080         // label node, or upstream edges
1081         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1082         while( edgeItr.hasNext() ) {
1083           ReferenceEdge edge = edgeItr.next();
1084
1085           OwnershipNode on = edge.getSrc();
1086
1087           if( on instanceof LabelNode ) {
1088
1089             LabelNode ln0 = (LabelNode) on;
1090             if( ln0.equals(lnArg_i) ) {
1091               edgesReachable.add(edge);
1092             } else {
1093               edgesUpstream.add(edge);
1094             }
1095
1096           } else {
1097
1098             HeapRegionNode hrn0 = (HeapRegionNode) on;
1099             if( reachableNodes.contains(hrn0) ) {
1100               edgesReachable.add(edge);
1101             } else {
1102               edgesUpstream.add(edge);
1103             }
1104           }
1105         }
1106       }
1107
1108
1109       // update reachable edges
1110       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1111       while( edgeReachableItr.hasNext() ) {
1112         ReferenceEdge edgeReachable = edgeReachableItr.next();
1113
1114         rewriteCallerEdgeBeta(fm.numParameters(),
1115                               index,
1116                               edgeReachable,
1117                               paramIndex2rewriteJ,
1118                               paramIndex2rewriteD,
1119                               paramIndex2paramToken,
1120                               paramIndex2paramTokenStar,
1121                               false,
1122                               null);
1123
1124         edgesWithNewBeta.add(edgeReachable);
1125       }
1126
1127
1128       // update upstream edges
1129       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
1130       = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1131
1132       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1133       while( edgeUpstreamItr.hasNext() ) {
1134         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1135
1136         rewriteCallerEdgeBeta(fm.numParameters(),
1137                               index,
1138                               edgeUpstream,
1139                               paramIndex2rewriteK,
1140                               paramIndex2rewriteD,
1141                               paramIndex2paramToken,
1142                               paramIndex2paramTokenStar,
1143                               true,
1144                               edgeUpstreamPlannedChanges);
1145
1146         edgesWithNewBeta.add(edgeUpstream);
1147       }
1148
1149       propagateTokensOverEdges(edgesUpstream,
1150                                edgeUpstreamPlannedChanges,
1151                                edgesWithNewBeta);
1152     }
1153
1154
1155     // commit changes to alpha and beta
1156     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1157     while( nodeItr.hasNext() ) {
1158       nodeItr.next().applyAlphaNew();
1159     }
1160
1161     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1162     while( edgeItr.hasNext() ) {
1163       edgeItr.next().applyBetaNew();
1164     }
1165
1166
1167
1168     // verify the existence of allocation sites and their
1169     // shadows from the callee in the context of this caller graph
1170     // then map allocated nodes of callee onto the caller shadows
1171     // of them
1172     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1173     while( asItr.hasNext() ) {
1174       AllocationSite allocSite  = asItr.next();
1175       HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1176
1177       // assert that the shadow nodes have no reference edges
1178       // because they're brand new to the graph, or last time
1179       // they were used they should have been cleared of edges
1180       HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1181       assert hrnShadowSummary.getNumReferencers() == 0;
1182       assert hrnShadowSummary.getNumReferencees() == 0;
1183
1184       // then bring g_ij onto g'_ij and rewrite
1185       transferOnto(hrnSummary, hrnShadowSummary);
1186
1187       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1188       hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1189
1190       // shadow nodes only are touched by a rewrite one time,
1191       // so rewrite and immediately commit--and they don't belong
1192       // to a particular parameter, so use a bogus param index
1193       // that pulls a self-rewrite out of H
1194       rewriteCallerNodeAlpha(fm.numParameters(),
1195                              bogusIndex,
1196                              hrnShadowSummary,
1197                              paramIndex2rewriteH,
1198                              paramIndex2rewriteD,
1199                              paramIndex2paramToken,
1200                              paramIndex2paramTokenStar);
1201
1202       hrnShadowSummary.applyAlphaNew();
1203
1204
1205       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1206         Integer idIth = allocSite.getIthOldest(i);
1207         assert id2hrn.containsKey(idIth);
1208         HeapRegionNode hrnIth = id2hrn.get(idIth);
1209
1210         Integer idShadowIth = -(allocSite.getIthOldest(i));
1211         assert id2hrn.containsKey(idShadowIth);
1212         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1213         assert hrnIthShadow.getNumReferencers() == 0;
1214         assert hrnIthShadow.getNumReferencees() == 0;
1215
1216         transferOnto(hrnIth, hrnIthShadow);
1217
1218         assert ogCallee.id2hrn.containsKey(idIth);
1219         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1220         hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1221
1222         rewriteCallerNodeAlpha(fm.numParameters(),
1223                                bogusIndex,
1224                                hrnIthShadow,
1225                                paramIndex2rewriteH,
1226                                paramIndex2rewriteD,
1227                                paramIndex2paramToken,
1228                                paramIndex2paramTokenStar);
1229
1230         hrnIthShadow.applyAlphaNew();
1231       }
1232     }
1233
1234
1235     // for every heap region->heap region edge in the
1236     // callee graph, create the matching edge or edges
1237     // in the caller graph
1238     Set sCallee = ogCallee.id2hrn.entrySet();
1239     Iterator iCallee = sCallee.iterator();
1240     while( iCallee.hasNext() ) {
1241       Map.Entry meCallee  = (Map.Entry)iCallee.next();
1242       Integer idCallee  = (Integer)        meCallee.getKey();
1243       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1244
1245       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1246       while( heapRegionsItrCallee.hasNext() ) {
1247         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1248         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1249         Integer idChildCallee         = hrnChildCallee.getID();
1250
1251         // only address this edge if it is not a special reflexive edge
1252         if( !edgeCallee.isInitialParamReflexive() ) {
1253
1254           // now we know that in the callee method's ownership graph
1255           // there is a heap region->heap region reference edge given
1256           // by heap region pointers:
1257           // hrnCallee -> heapChildCallee
1258           //
1259           // or by the ownership-graph independent ID's:
1260           // idCallee -> idChildCallee
1261
1262           // make the edge with src and dst so beta info is
1263           // calculated once, then copy it for each new edge in caller
1264           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1265                                                                     null,
1266                                                                     edgeCallee.getFieldDesc(),
1267                                                                     false,
1268                                                                     toShadowTokens(ogCallee, edgeCallee.getBeta() )
1269                                                                     );
1270           rewriteCallerEdgeBeta(fm.numParameters(),
1271                                 bogusIndex,
1272                                 edgeNewInCallerTemplate,
1273                                 paramIndex2rewriteJ,
1274                                 paramIndex2rewriteD,
1275                                 paramIndex2paramToken,
1276                                 paramIndex2paramTokenStar,
1277                                 false,
1278                                 null);
1279
1280           edgeNewInCallerTemplate.applyBetaNew();
1281
1282
1283           // So now make a set of possible source heaps in the caller graph
1284           // and a set of destination heaps in the caller graph, and make
1285           // a reference edge in the caller for every possible (src,dst) pair
1286           HashSet<HeapRegionNode> possibleCallerSrcs =
1287             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1288                                                 (HeapRegionNode) edgeCallee.getSrc(),
1289                                                 paramIndex2reachableCallerNodes);
1290
1291           HashSet<HeapRegionNode> possibleCallerDsts =
1292             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1293                                                 edgeCallee.getDst(),
1294                                                 paramIndex2reachableCallerNodes);
1295
1296
1297           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1298           Iterator srcItr = possibleCallerSrcs.iterator();
1299           while( srcItr.hasNext() ) {
1300             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1301
1302             // check that if this source node has a definite type that
1303             // it also has the appropriate field, otherwise prune this
1304             AllocationSite asSrc = src.getAllocationSite();
1305             if( asSrc != null ) {
1306               boolean foundField = false;
1307               Iterator fieldsSrcItr = asSrc.getType().getClassDesc().getFields();
1308               while( fieldsSrcItr.hasNext() ) {
1309                 FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1310                 if( fd == edgeCallee.getFieldDesc() ) {
1311                   foundField = true;
1312                   break;
1313                 }
1314               }
1315               if( !foundField ) {
1316                 // prune this source node possibility
1317                 continue;
1318               }
1319             }
1320
1321             Iterator dstItr = possibleCallerDsts.iterator();
1322             while( dstItr.hasNext() ) {
1323               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1324
1325               // check if this dst node has a definite type and
1326               // if it matches the callee edge
1327               AllocationSite asDst = dst.getAllocationSite();
1328               if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1329                 if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) { continue; }
1330                 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) { continue; }
1331                 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1332                   if( !asDst.getType().equals( edgeCallee.getFieldDesc().getType() ) ) { continue; }
1333                 }
1334               }
1335
1336               // otherwise the caller src and dst pair can match the edge, so make it
1337               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1338               edgeNewInCaller.setSrc(src);
1339               edgeNewInCaller.setDst(dst);
1340
1341               ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1342               if( edgeExisting == null ) {
1343                 // if this edge doesn't exist in the caller, create it
1344                 addReferenceEdge(src, dst, edgeNewInCaller);
1345               } else {
1346                 // if it already exists, merge with it
1347                 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1348               }
1349             }
1350           }
1351         }
1352       }
1353     }
1354
1355
1356
1357     // return value may need to be assigned in caller
1358     if( fc.getReturnTemp() != null ) {
1359
1360       LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() );
1361       clearReferenceEdgesFrom(lnLhsCaller, null, true);
1362
1363       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1364       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1365       while( edgeCalleeItr.hasNext() ) {
1366         ReferenceEdge edgeCallee = edgeCalleeItr.next();
1367
1368         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1369                                                                   null,
1370                                                                   edgeCallee.getFieldDesc(),
1371                                                                   false,
1372                                                                   toShadowTokens(ogCallee, edgeCallee.getBeta() )
1373                                                                   );
1374         rewriteCallerEdgeBeta(fm.numParameters(),
1375                               bogusIndex,
1376                               edgeNewInCallerTemplate,
1377                               paramIndex2rewriteJ,
1378                               paramIndex2rewriteD,
1379                               paramIndex2paramToken,
1380                               paramIndex2paramTokenStar,
1381                               false,
1382                               null);
1383
1384         edgeNewInCallerTemplate.applyBetaNew();
1385
1386
1387         HashSet<HeapRegionNode> assignCallerRhs =
1388           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1389                                               edgeCallee.getDst(),
1390                                               paramIndex2reachableCallerNodes);
1391
1392         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1393         while( itrHrn.hasNext() ) {
1394           HeapRegionNode hrnCaller = itrHrn.next();
1395
1396           // check if this dst node has a definite type and
1397           // if it matches the callee edge
1398           // check if this dst node has a definite type and
1399           // if it matches the callee edge
1400           AllocationSite asDst = hrnCaller.getAllocationSite();
1401           if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1402             if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) { continue; }
1403             if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) { continue; }
1404             if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1405               if( !asDst.getType().equals( edgeCallee.getFieldDesc().getType() ) ) { continue; }
1406             }
1407           }
1408
1409           // otherwise caller node can match callee edge, so make it
1410           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1411           edgeNewInCaller.setSrc(lnLhsCaller);
1412           edgeNewInCaller.setDst(hrnCaller);
1413
1414           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1415           if( edgeExisting == null ) {
1416             // if this edge doesn't exist in the caller, create it
1417             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1418           } else {
1419             // if it already exists, merge with it
1420             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1421           }
1422         }
1423       }
1424     }
1425
1426
1427
1428     // merge the shadow nodes of allocation sites back down to normal capacity
1429     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1430     while( allocItr.hasNext() ) {
1431       AllocationSite as = allocItr.next();
1432
1433       // first age each allocation site enough times to make room for the shadow nodes
1434       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1435         age(as);
1436       }
1437
1438       // then merge the shadow summary into the normal summary
1439       HeapRegionNode hrnSummary = getSummaryNode(as);
1440       assert hrnSummary != null;
1441
1442       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1443       assert hrnSummaryShadow != null;
1444
1445       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1446
1447       // then clear off after merge
1448       clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1449       clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1450       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1451
1452       // then transplant shadow nodes onto the now clean normal nodes
1453       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1454
1455         Integer idIth = as.getIthOldest(i);
1456         HeapRegionNode hrnIth = id2hrn.get(idIth);
1457
1458         Integer idIthShadow = as.getIthOldestShadow(i);
1459         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1460
1461         transferOnto(hrnIthShadow, hrnIth);
1462
1463         // clear off shadow nodes after transfer
1464         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1465         clearReferenceEdgesTo(hrnIthShadow, null, true);
1466         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1467       }
1468
1469       // finally, globally change shadow tokens into normal tokens
1470       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1471       while( itrAllLabelNodes.hasNext() ) {
1472         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1473         LabelNode ln = (LabelNode) me.getValue();
1474
1475         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1476         while( itrEdges.hasNext() ) {
1477           unshadowTokens(as, itrEdges.next() );
1478         }
1479       }
1480
1481       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1482       while( itrAllHRNodes.hasNext() ) {
1483         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1484         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1485
1486         unshadowTokens(as, hrnToAge);
1487
1488         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1489         while( itrEdges.hasNext() ) {
1490           unshadowTokens(as, itrEdges.next() );
1491         }
1492       }
1493     }
1494   }
1495
1496
1497   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1498     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1499   }
1500
1501   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1502     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1503   }
1504
1505
1506   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1507                                          ReachabilitySet rsIn) {
1508
1509     ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1510
1511     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1512     while( allocItr.hasNext() ) {
1513       AllocationSite as = allocItr.next();
1514
1515       rsOut = rsOut.toShadowTokens(as);
1516     }
1517
1518     return rsOut.makeCanonical();
1519   }
1520
1521
1522   private void rewriteCallerNodeAlpha(int numParameters,
1523                                       Integer paramIndex,
1524                                       HeapRegionNode hrn,
1525                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1526                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1527                                       Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1528                                       Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1529
1530     ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
1531     assert rules != null;
1532
1533     TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1534     assert tokenToRewrite != null;
1535
1536     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1537     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1538     while( ttsItr.hasNext() ) {
1539       TokenTupleSet tts = ttsItr.next();
1540       r0 = r0.union(tts.rewriteToken(tokenToRewrite,
1541                                      hrn.getAlpha(),
1542                                      false,
1543                                      null) );
1544     }
1545
1546     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1547     ttsItr = r0.iterator();
1548     while( ttsItr.hasNext() ) {
1549       TokenTupleSet tts = ttsItr.next();
1550       r1 = r1.union(rewriteDpass(numParameters,
1551                                  paramIndex,
1552                                  tts,
1553                                  paramIndex2rewriteD,
1554                                  paramIndex2paramToken,
1555                                  paramIndex2paramTokenStar) );
1556     }
1557
1558     hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
1559   }
1560
1561
1562   private void rewriteCallerEdgeBeta(int numParameters,
1563                                      Integer paramIndex,
1564                                      ReferenceEdge edge,
1565                                      Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1566                                      Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1567                                      Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1568                                      Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1569                                      boolean makeChangeSet,
1570                                      Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1571
1572     ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
1573     assert rules != null;
1574
1575     TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1576     assert tokenToRewrite != null;
1577
1578     ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1579
1580     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1581     while( ttsItr.hasNext() ) {
1582       TokenTupleSet tts = ttsItr.next();
1583
1584       Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1585         new Hashtable<TokenTupleSet, TokenTupleSet>();
1586
1587       ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
1588                                                edge.getBeta(),
1589                                                true,
1590                                                forChangeSet);
1591
1592       Iterator fcsItr = forChangeSet.entrySet().iterator();
1593       while( fcsItr.hasNext() ) {
1594         Map.Entry me = (Map.Entry)fcsItr.next();
1595         TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1596         TokenTupleSet ttsAdd   = (TokenTupleSet) me.getValue();
1597
1598         ChangeTuple ct = new ChangeTuple(ttsMatch,
1599                                          ttsAdd
1600                                          ).makeCanonical();
1601
1602         cts0 = cts0.union(ct);
1603       }
1604     }
1605
1606
1607     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1608     ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1609
1610     Iterator<ChangeTuple> ctItr = cts0.iterator();
1611     while( ctItr.hasNext() ) {
1612       ChangeTuple ct = ctItr.next();
1613
1614       ReachabilitySet rTemp = rewriteDpass(numParameters,
1615                                            paramIndex,
1616                                            ct.getSetToAdd(),
1617                                            paramIndex2rewriteD,
1618                                            paramIndex2paramToken,
1619                                            paramIndex2paramTokenStar
1620                                            ).makeCanonical();
1621       r1 = r1.union(rTemp);
1622
1623       if( makeChangeSet ) {
1624         assert edgePlannedChanges != null;
1625
1626         Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1627         while( ttsTempItr.hasNext() ) {
1628           TokenTupleSet tts = ttsTempItr.next();
1629
1630           ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
1631                                                 tts
1632                                                 ).makeCanonical();
1633
1634           cts1 = cts1.union(ctFinal);
1635         }
1636       }
1637     }
1638
1639     if( makeChangeSet ) {
1640       edgePlannedChanges.put(edge, cts1);
1641     }
1642
1643     edge.setBetaNew(edge.getBetaNew().union(r1) );
1644   }
1645
1646
1647   private ReachabilitySet rewriteDpass(int numParameters,
1648                                        Integer paramIndex,
1649                                        TokenTupleSet ttsIn,
1650                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1651                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1652                                        Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1653
1654     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1655
1656     boolean rewritten = false;
1657
1658     for( int j = 0; j < numParameters; ++j ) {
1659       Integer paramIndexJ = new Integer(j);
1660       ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ);
1661       assert D_j != null;
1662
1663       if( paramIndexJ != paramIndex ) {
1664         TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ);
1665         assert tokenToRewriteJ != null;
1666         if( ttsIn.containsTuple(tokenToRewriteJ) ) {
1667           ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ,
1668                                                  D_j,
1669                                                  false,
1670                                                  null);
1671           Iterator<TokenTupleSet> ttsItr = r.iterator();
1672           while( ttsItr.hasNext() ) {
1673             TokenTupleSet tts = ttsItr.next();
1674             rsOut = rsOut.union(rewriteDpass(numParameters,
1675                                              paramIndex,
1676                                              tts,
1677                                              paramIndex2rewriteD,
1678                                              paramIndex2paramToken,
1679                                              paramIndex2paramTokenStar) );
1680             rewritten = true;
1681           }
1682         }
1683       }
1684
1685       TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ);
1686       assert tokenStarToRewriteJ != null;
1687       if( ttsIn.containsTuple(tokenStarToRewriteJ) ) {
1688         ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ,
1689                                                D_j,
1690                                                false,
1691                                                null);
1692         Iterator<TokenTupleSet> ttsItr = r.iterator();
1693         while( ttsItr.hasNext() ) {
1694           TokenTupleSet tts = ttsItr.next();
1695           rsOut = rsOut.union(rewriteDpass(numParameters,
1696                                            paramIndex,
1697                                            tts,
1698                                            paramIndex2rewriteD,
1699                                            paramIndex2paramToken,
1700                                            paramIndex2paramTokenStar) );
1701           rewritten = true;
1702         }
1703       }
1704     }
1705
1706     if( !rewritten ) {
1707       rsOut = rsOut.union(ttsIn);
1708     }
1709
1710     return rsOut;
1711   }
1712
1713
1714   private HashSet<HeapRegionNode>
1715   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1716                                       HeapRegionNode hrnCallee,
1717                                       Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1718                                       ) {
1719
1720     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1721
1722     Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1723
1724     if( paramIndexCallee == null ) {
1725       // this is a node allocated in the callee then and it has
1726       // exactly one shadow node in the caller to map to
1727       AllocationSite as = hrnCallee.getAllocationSite();
1728       assert as != null;
1729
1730       int age = as.getAgeCategory(hrnCallee.getID() );
1731       assert age != AllocationSite.AGE_notInThisSite;
1732
1733       Integer idCaller;
1734       if( age == AllocationSite.AGE_summary ) {
1735         idCaller = as.getSummaryShadow();
1736       } else if( age == AllocationSite.AGE_oldest ) {
1737         idCaller = as.getOldestShadow();
1738       } else {
1739         assert age == AllocationSite.AGE_in_I;
1740
1741         Integer I = as.getAge(hrnCallee.getID() );
1742         assert I != null;
1743
1744         idCaller = as.getIthOldestShadow(I);
1745       }
1746
1747       assert id2hrn.containsKey(idCaller);
1748       HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1749       possibleCallerHRNs.add(hrnCaller);
1750
1751     } else {
1752       // this is a node that was created to represent a parameter
1753       // so it maps to a whole mess of heap regions
1754       assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1755       possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1756     }
1757
1758     return possibleCallerHRNs;
1759   }
1760
1761
1762
1763   ////////////////////////////////////////////////////
1764   // in merge() and equals() methods the suffix A
1765   // represents the passed in graph and the suffix
1766   // B refers to the graph in this object
1767   // Merging means to take the incoming graph A and
1768   // merge it into B, so after the operation graph B
1769   // is the final result.
1770   ////////////////////////////////////////////////////
1771   public void merge(OwnershipGraph og) {
1772
1773     if( og == null ) {
1774       return;
1775     }
1776
1777     mergeOwnershipNodes(og);
1778     mergeReferenceEdges(og);
1779     mergeId2paramIndex(og);
1780     mergeAllocationSites(og);
1781   }
1782
1783
1784   protected void mergeOwnershipNodes(OwnershipGraph og) {
1785     Set sA = og.id2hrn.entrySet();
1786     Iterator iA = sA.iterator();
1787     while( iA.hasNext() ) {
1788       Map.Entry meA  = (Map.Entry)iA.next();
1789       Integer idA  = (Integer)        meA.getKey();
1790       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1791
1792       // if this graph doesn't have a node the
1793       // incoming graph has, allocate it
1794       if( !id2hrn.containsKey(idA) ) {
1795         HeapRegionNode hrnB = hrnA.copy();
1796         id2hrn.put(idA, hrnB);
1797
1798       } else {
1799         // otherwise this is a node present in both graphs
1800         // so make the new reachability set a union of the
1801         // nodes' reachability sets
1802         HeapRegionNode hrnB = id2hrn.get(idA);
1803         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1804       }
1805     }
1806
1807     // now add any label nodes that are in graph B but
1808     // not in A
1809     sA = og.td2ln.entrySet();
1810     iA = sA.iterator();
1811     while( iA.hasNext() ) {
1812       Map.Entry meA = (Map.Entry)iA.next();
1813       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1814       LabelNode lnA = (LabelNode)      meA.getValue();
1815
1816       // if the label doesn't exist in B, allocate and add it
1817       LabelNode lnB = getLabelNodeFromTemp(tdA);
1818     }
1819   }
1820
1821   protected void mergeReferenceEdges(OwnershipGraph og) {
1822
1823     // heap regions
1824     Set sA = og.id2hrn.entrySet();
1825     Iterator iA = sA.iterator();
1826     while( iA.hasNext() ) {
1827       Map.Entry meA  = (Map.Entry)iA.next();
1828       Integer idA  = (Integer)        meA.getKey();
1829       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1830
1831       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1832       while( heapRegionsItrA.hasNext() ) {
1833         ReferenceEdge edgeA     = heapRegionsItrA.next();
1834         HeapRegionNode hrnChildA = edgeA.getDst();
1835         Integer idChildA  = hrnChildA.getID();
1836
1837         // at this point we know an edge in graph A exists
1838         // idA -> idChildA, does this exist in B?
1839         assert id2hrn.containsKey(idA);
1840         HeapRegionNode hrnB        = id2hrn.get(idA);
1841         ReferenceEdge edgeToMerge = null;
1842
1843         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1844         while( heapRegionsItrB.hasNext() &&
1845                edgeToMerge == null          ) {
1846
1847           ReferenceEdge edgeB     = heapRegionsItrB.next();
1848           HeapRegionNode hrnChildB = edgeB.getDst();
1849           Integer idChildB  = hrnChildB.getID();
1850
1851           // don't use the ReferenceEdge.equals() here because
1852           // we're talking about existence between graphs
1853           if( idChildB.equals(idChildA) &&
1854               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1855             edgeToMerge = edgeB;
1856           }
1857         }
1858
1859         // if the edge from A was not found in B,
1860         // add it to B.
1861         if( edgeToMerge == null ) {
1862           assert id2hrn.containsKey(idChildA);
1863           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1864           edgeToMerge = edgeA.copy();
1865           edgeToMerge.setSrc(hrnB);
1866           edgeToMerge.setDst(hrnChildB);
1867           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1868         }
1869         // otherwise, the edge already existed in both graphs
1870         // so merge their reachability sets
1871         else {
1872           // just replace this beta set with the union
1873           assert edgeToMerge != null;
1874           edgeToMerge.setBeta(
1875             edgeToMerge.getBeta().union(edgeA.getBeta() )
1876             );
1877           if( !edgeA.isInitialParamReflexive() ) {
1878             edgeToMerge.setIsInitialParamReflexive(false);
1879           }
1880         }
1881       }
1882     }
1883
1884     // and then again with label nodes
1885     sA = og.td2ln.entrySet();
1886     iA = sA.iterator();
1887     while( iA.hasNext() ) {
1888       Map.Entry meA = (Map.Entry)iA.next();
1889       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1890       LabelNode lnA = (LabelNode)      meA.getValue();
1891
1892       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1893       while( heapRegionsItrA.hasNext() ) {
1894         ReferenceEdge edgeA     = heapRegionsItrA.next();
1895         HeapRegionNode hrnChildA = edgeA.getDst();
1896         Integer idChildA  = hrnChildA.getID();
1897
1898         // at this point we know an edge in graph A exists
1899         // tdA -> idChildA, does this exist in B?
1900         assert td2ln.containsKey(tdA);
1901         LabelNode lnB         = td2ln.get(tdA);
1902         ReferenceEdge edgeToMerge = null;
1903
1904         // labels never have edges with a field
1905         //assert edgeA.getFieldDesc() == null;
1906
1907         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1908         while( heapRegionsItrB.hasNext() &&
1909                edgeToMerge == null          ) {
1910
1911           ReferenceEdge edgeB     = heapRegionsItrB.next();
1912           HeapRegionNode hrnChildB = edgeB.getDst();
1913           Integer idChildB  = hrnChildB.getID();
1914
1915           // labels never have edges with a field
1916           //assert edgeB.getFieldDesc() == null;
1917
1918           // don't use the ReferenceEdge.equals() here because
1919           // we're talking about existence between graphs
1920           if( idChildB.equals(idChildA) &&
1921               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1922             edgeToMerge = edgeB;
1923           }
1924         }
1925
1926         // if the edge from A was not found in B,
1927         // add it to B.
1928         if( edgeToMerge == null ) {
1929           assert id2hrn.containsKey(idChildA);
1930           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1931           edgeToMerge = edgeA.copy();
1932           edgeToMerge.setSrc(lnB);
1933           edgeToMerge.setDst(hrnChildB);
1934           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1935         }
1936         // otherwise, the edge already existed in both graphs
1937         // so merge their reachability sets
1938         else {
1939           // just replace this beta set with the union
1940           edgeToMerge.setBeta(
1941             edgeToMerge.getBeta().union(edgeA.getBeta() )
1942             );
1943           if( !edgeA.isInitialParamReflexive() ) {
1944             edgeToMerge.setIsInitialParamReflexive(false);
1945           }
1946         }
1947       }
1948     }
1949   }
1950
1951   // you should only merge ownership graphs that have the
1952   // same number of parameters, or if one or both parameter
1953   // index tables are empty
1954   protected void mergeId2paramIndex(OwnershipGraph og) {
1955     if( id2paramIndex.size() == 0 ) {
1956       id2paramIndex  = og.id2paramIndex;
1957       paramIndex2id  = og.paramIndex2id;
1958       paramIndex2tdQ = og.paramIndex2tdQ;
1959       return;
1960     }
1961
1962     if( og.id2paramIndex.size() == 0 ) {
1963       return;
1964     }
1965
1966     assert id2paramIndex.size() == og.id2paramIndex.size();
1967   }
1968
1969   protected void mergeAllocationSites(OwnershipGraph og) {
1970     allocationSites.addAll(og.allocationSites);
1971   }
1972
1973
1974
1975   // it is necessary in the equals() member functions
1976   // to "check both ways" when comparing the data
1977   // structures of two graphs.  For instance, if all
1978   // edges between heap region nodes in graph A are
1979   // present and equal in graph B it is not sufficient
1980   // to say the graphs are equal.  Consider that there
1981   // may be edges in graph B that are not in graph A.
1982   // the only way to know that all edges in both graphs
1983   // are equally present is to iterate over both data
1984   // structures and compare against the other graph.
1985   public boolean equals(OwnershipGraph og) {
1986
1987     if( og == null ) {
1988       return false;
1989     }
1990
1991     if( !areHeapRegionNodesEqual(og) ) {
1992       return false;
1993     }
1994
1995     if( !areLabelNodesEqual(og) ) {
1996       return false;
1997     }
1998
1999     if( !areReferenceEdgesEqual(og) ) {
2000       return false;
2001     }
2002
2003     if( !areId2paramIndexEqual(og) ) {
2004       return false;
2005     }
2006
2007     // if everything is equal up to this point,
2008     // assert that allocationSites is also equal--
2009     // this data is redundant and kept for efficiency
2010     assert allocationSites.equals(og.allocationSites);
2011
2012     return true;
2013   }
2014
2015   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2016
2017     if( !areallHRNinAalsoinBandequal(this, og) ) {
2018       return false;
2019     }
2020
2021     if( !areallHRNinAalsoinBandequal(og, this) ) {
2022       return false;
2023     }
2024
2025     return true;
2026   }
2027
2028   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2029                                                        OwnershipGraph ogB) {
2030     Set sA = ogA.id2hrn.entrySet();
2031     Iterator iA = sA.iterator();
2032     while( iA.hasNext() ) {
2033       Map.Entry meA  = (Map.Entry)iA.next();
2034       Integer idA  = (Integer)        meA.getKey();
2035       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2036
2037       if( !ogB.id2hrn.containsKey(idA) ) {
2038         return false;
2039       }
2040
2041       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2042       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2043         return false;
2044       }
2045     }
2046
2047     return true;
2048   }
2049
2050
2051   protected boolean areLabelNodesEqual(OwnershipGraph og) {
2052
2053     if( !areallLNinAalsoinBandequal(this, og) ) {
2054       return false;
2055     }
2056
2057     if( !areallLNinAalsoinBandequal(og, this) ) {
2058       return false;
2059     }
2060
2061     return true;
2062   }
2063
2064   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2065                                                       OwnershipGraph ogB) {
2066     Set sA = ogA.td2ln.entrySet();
2067     Iterator iA = sA.iterator();
2068     while( iA.hasNext() ) {
2069       Map.Entry meA = (Map.Entry)iA.next();
2070       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2071
2072       if( !ogB.td2ln.containsKey(tdA) ) {
2073         return false;
2074       }
2075     }
2076
2077     return true;
2078   }
2079
2080
2081   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2082     if( !areallREinAandBequal(this, og) ) {
2083       return false;
2084     }
2085
2086     return true;
2087   }
2088
2089   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2090                                                 OwnershipGraph ogB) {
2091
2092     // check all the heap region->heap region edges
2093     Set sA = ogA.id2hrn.entrySet();
2094     Iterator iA = sA.iterator();
2095     while( iA.hasNext() ) {
2096       Map.Entry meA  = (Map.Entry)iA.next();
2097       Integer idA  = (Integer)        meA.getKey();
2098       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2099
2100       // we should have already checked that the same
2101       // heap regions exist in both graphs
2102       assert ogB.id2hrn.containsKey(idA);
2103
2104       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2105         return false;
2106       }
2107
2108       // then check every edge in B for presence in A, starting
2109       // from the same parent HeapRegionNode
2110       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2111
2112       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2113         return false;
2114       }
2115     }
2116
2117     // then check all the label->heap region edges
2118     sA = ogA.td2ln.entrySet();
2119     iA = sA.iterator();
2120     while( iA.hasNext() ) {
2121       Map.Entry meA = (Map.Entry)iA.next();
2122       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2123       LabelNode lnA = (LabelNode)      meA.getValue();
2124
2125       // we should have already checked that the same
2126       // label nodes exist in both graphs
2127       assert ogB.td2ln.containsKey(tdA);
2128
2129       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2130         return false;
2131       }
2132
2133       // then check every edge in B for presence in A, starting
2134       // from the same parent LabelNode
2135       LabelNode lnB = ogB.td2ln.get(tdA);
2136
2137       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2138         return false;
2139       }
2140     }
2141
2142     return true;
2143   }
2144
2145
2146   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2147                                                  OwnershipNode onA,
2148                                                  OwnershipGraph ogB) {
2149
2150     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2151     while( itrA.hasNext() ) {
2152       ReferenceEdge edgeA     = itrA.next();
2153       HeapRegionNode hrnChildA = edgeA.getDst();
2154       Integer idChildA  = hrnChildA.getID();
2155
2156       assert ogB.id2hrn.containsKey(idChildA);
2157
2158       // at this point we know an edge in graph A exists
2159       // onA -> idChildA, does this exact edge exist in B?
2160       boolean edgeFound = false;
2161
2162       OwnershipNode onB = null;
2163       if( onA instanceof HeapRegionNode ) {
2164         HeapRegionNode hrnA = (HeapRegionNode) onA;
2165         onB = ogB.id2hrn.get(hrnA.getID() );
2166       } else {
2167         LabelNode lnA = (LabelNode) onA;
2168         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2169       }
2170
2171       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2172       while( itrB.hasNext() ) {
2173         ReferenceEdge edgeB     = itrB.next();
2174         HeapRegionNode hrnChildB = edgeB.getDst();
2175         Integer idChildB  = hrnChildB.getID();
2176
2177         if( idChildA.equals(idChildB) &&
2178             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2179
2180           // there is an edge in the right place with the right field,
2181           // but do they have the same attributes?
2182           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2183
2184             edgeFound = true;
2185             //} else {
2186             //return false;
2187           }
2188         }
2189       }
2190
2191       if( !edgeFound ) {
2192         return false;
2193       }
2194     }
2195
2196     return true;
2197   }
2198
2199
2200   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2201     return id2paramIndex.size() == og.id2paramIndex.size();
2202   }
2203
2204
2205   /*
2206      // given a set B of heap region node ID's, return the set of heap
2207      // region node ID's that is reachable from B
2208      public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
2209
2210       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
2211       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2212
2213       // initial nodes to visit are from set B
2214       Iterator initialItr = idSetB.iterator();
2215       while( initialItr.hasNext() ) {
2216           Integer idInitial = (Integer) initialItr.next();
2217           assert id2hrn.contains( idInitial );
2218           HeapRegionNode hrnInitial = id2hrn.get( idInitial );
2219           toVisit.add( hrnInitial );
2220       }
2221
2222       HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
2223
2224       // do a heap traversal
2225       while( !toVisit.isEmpty() ) {
2226           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2227           toVisit.remove( hrnVisited );
2228           visited.add   ( hrnVisited );
2229
2230           // for every node visited, add it to the total
2231           // reachable set
2232           idSetReachableFromB.add( hrnVisited.getID() );
2233
2234           // find other reachable nodes
2235           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2236           while( referenceeItr.hasNext() ) {
2237               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2238               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2239               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2240
2241               if( !visited.contains( hrnReferencee ) ) {
2242                   toVisit.add( hrnReferencee );
2243               }
2244           }
2245       }
2246
2247       return idSetReachableFromB;
2248      }
2249
2250
2251      // used to find if a heap region can possibly have a reference to
2252      // any of the heap regions in the given set
2253      // if the id supplied is in the set, then a self-referencing edge
2254      // would return true, but that special case is specifically allowed
2255      // meaning that it isn't an external alias
2256      public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
2257
2258       assert id2hrn.contains( id );
2259       HeapRegionNode hrn = id2hrn.get( id );
2260
2261
2262       //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
2263
2264       //Iterator i = idSet.iterator();
2265       //while( i.hasNext() ) {
2266       //    Integer idFromSet = (Integer) i.next();
2267       //   assert id2hrn.contains( idFromSet );
2268       //    hrnSet.add( id2hrn.get( idFromSet ) );
2269       //}
2270
2271
2272       // do a traversal from hrn and see if any of the
2273       // heap regions from the set come up during that
2274       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
2275       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2276
2277       toVisit.add( hrn );
2278       while( !toVisit.isEmpty() ) {
2279           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2280           toVisit.remove( hrnVisited );
2281           visited.add   ( hrnVisited );
2282
2283           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2284           while( referenceeItr.hasNext() ) {
2285               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2286               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2287               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2288
2289               if( idSet.contains( hrnReferencee.getID() ) ) {
2290                   if( !id.equals( hrnReferencee.getID() ) ) {
2291                       return true;
2292                   }
2293               }
2294
2295               if( !visited.contains( hrnReferencee ) ) {
2296                   toVisit.add( hrnReferencee );
2297               }
2298           }
2299       }
2300
2301       return false;
2302      }
2303    */
2304
2305
2306   // for writing ownership graphs to dot files
2307   public void writeGraph(Descriptor methodDesc,
2308                          FlatNode fn,
2309                          boolean writeLabels,
2310                          boolean labelSelect,
2311                          boolean pruneGarbage,
2312                          boolean writeReferencers
2313                          ) throws java.io.IOException {
2314     writeGraph(
2315       methodDesc.getSymbol() +
2316       methodDesc.getNum() +
2317       fn.toString(),
2318       writeLabels,
2319       labelSelect,
2320       pruneGarbage,
2321       writeReferencers
2322       );
2323   }
2324
2325   /*
2326      public void writeGraph(Descriptor methodDesc,
2327                          FlatNode fn,
2328                          boolean writeLabels,
2329                          boolean writeReferencers
2330                          ) throws java.io.IOException {
2331      writeGraph(
2332       methodDesc.getSymbol() +
2333       methodDesc.getNum() +
2334       fn.toString(),
2335       writeLabels,
2336       false,
2337       false,
2338       writeReferencers
2339       );
2340      }
2341
2342      public void writeGraph(Descriptor methodDesc,
2343                          boolean writeLabels,
2344                          boolean writeReferencers
2345                          ) throws java.io.IOException {
2346      writeGraph(
2347       methodDesc.getSymbol() +
2348       methodDesc.getNum() +
2349       "COMPLETE",
2350       writeLabels,
2351       false,
2352       false,
2353       writeReferencers
2354       );
2355      }
2356    */
2357
2358   public void writeGraph(Descriptor methodDesc,
2359                          boolean writeLabels,
2360                          boolean labelSelect,
2361                          boolean pruneGarbage,
2362                          boolean writeReferencers
2363                          ) throws java.io.IOException {
2364
2365     writeGraph(methodDesc+"COMPLETE",
2366                writeLabels,
2367                labelSelect,
2368                pruneGarbage,
2369                writeReferencers
2370                );
2371   }
2372
2373   public void writeGraph(String graphName,
2374                          boolean writeLabels,
2375                          boolean labelSelect,
2376                          boolean pruneGarbage,
2377                          boolean writeReferencers
2378                          ) throws java.io.IOException {
2379
2380     // remove all non-word characters from the graph name so
2381     // the filename and identifier in dot don't cause errors
2382     graphName = graphName.replaceAll("[\\W]", "");
2383
2384     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2385     bw.write("digraph "+graphName+" {\n");
2386     //bw.write( "  size=\"7.5,10\";\n" );
2387
2388     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2389
2390     // then visit every heap region node
2391     if( !pruneGarbage ) {
2392       Set s = id2hrn.entrySet();
2393       Iterator i = s.iterator();
2394       while( i.hasNext() ) {
2395         Map.Entry me  = (Map.Entry)i.next();
2396         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2397         if( !visited.contains(hrn) ) {
2398           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2399                                   hrn,
2400                                   bw,
2401                                   null,
2402                                   visited,
2403                                   writeReferencers);
2404         }
2405       }
2406     }
2407
2408     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2409
2410
2411     // then visit every label node, useful for debugging
2412     if( writeLabels ) {
2413       Set s = td2ln.entrySet();
2414       Iterator i = s.iterator();
2415       while( i.hasNext() ) {
2416         Map.Entry me = (Map.Entry)i.next();
2417         LabelNode ln = (LabelNode) me.getValue();
2418
2419         if( labelSelect ) {
2420           String labelStr = ln.getTempDescriptorString();
2421           if( labelStr.startsWith("___temp") ||
2422               labelStr.startsWith("___dst") ||
2423               labelStr.startsWith("___srctmp") ||
2424               labelStr.startsWith("___neverused")   ) {
2425             continue;
2426           }
2427         }
2428
2429         bw.write(ln.toString() + ";\n");
2430
2431         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2432         while( heapRegionsItr.hasNext() ) {
2433           ReferenceEdge edge = heapRegionsItr.next();
2434           HeapRegionNode hrn  = edge.getDst();
2435
2436           if( pruneGarbage && !visited.contains(hrn) ) {
2437             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2438                                     hrn,
2439                                     bw,
2440                                     null,
2441                                     visited,
2442                                     writeReferencers);
2443           }
2444
2445           bw.write("  "        + ln.toString() +
2446                    " -> "      + hrn.toString() +
2447                    "[label=\"" + edge.toGraphEdgeString() +
2448                    "\",decorate];\n");
2449         }
2450       }
2451     }
2452
2453
2454     bw.write("}\n");
2455     bw.close();
2456   }
2457
2458   protected void traverseHeapRegionNodes(int mode,
2459                                          HeapRegionNode hrn,
2460                                          BufferedWriter bw,
2461                                          TempDescriptor td,
2462                                          HashSet<HeapRegionNode> visited,
2463                                          boolean writeReferencers
2464                                          ) throws java.io.IOException {
2465
2466     if( visited.contains(hrn) ) {
2467       return;
2468     }
2469     visited.add(hrn);
2470
2471     switch( mode ) {
2472     case VISIT_HRN_WRITE_FULL:
2473
2474       String attributes = "[";
2475
2476       if( hrn.isSingleObject() ) {
2477         attributes += "shape=box";
2478       } else {
2479         attributes += "shape=Msquare";
2480       }
2481
2482       if( hrn.isFlagged() ) {
2483         attributes += ",style=filled,fillcolor=lightgrey";
2484       }
2485
2486       attributes += ",label=\"ID"        +
2487                     hrn.getID()          +
2488                     "\\n"                +
2489                     hrn.getDescription() +
2490                     "\\n"                +
2491                     hrn.getAlphaString() +
2492                     "\"]";
2493
2494       bw.write("  " + hrn.toString() + attributes + ";\n");
2495       break;
2496     }
2497
2498
2499     // useful for debugging
2500     if( writeReferencers ) {
2501       OwnershipNode onRef  = null;
2502       Iterator refItr = hrn.iteratorToReferencers();
2503       while( refItr.hasNext() ) {
2504         onRef = (OwnershipNode) refItr.next();
2505
2506         switch( mode ) {
2507         case VISIT_HRN_WRITE_FULL:
2508           bw.write("  "                    + hrn.toString() +
2509                    " -> "                  + onRef.toString() +
2510                    "[color=lightgray];\n");
2511           break;
2512         }
2513       }
2514     }
2515
2516     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2517     while( childRegionsItr.hasNext() ) {
2518       ReferenceEdge edge     = childRegionsItr.next();
2519       HeapRegionNode hrnChild = edge.getDst();
2520
2521       switch( mode ) {
2522       case VISIT_HRN_WRITE_FULL:
2523         bw.write("  "        + hrn.toString() +
2524                  " -> "      + hrnChild.toString() +
2525                  "[label=\"" + edge.toGraphEdgeString() +
2526                  "\",decorate];\n");
2527         break;
2528       }
2529
2530       traverseHeapRegionNodes(mode,
2531                               hrnChild,
2532                               bw,
2533                               td,
2534                               visited,
2535                               writeReferencers);
2536     }
2537   }
2538 }