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     // define rewrite rules and other structures to organize
 891     // data by parameter/argument index
 892     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
 893       new Hashtable<Integer, ReachabilitySet>();
 894
 895     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
 896       new Hashtable<Integer, ReachabilitySet>();
 897
 898     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
 899       new Hashtable<Integer, ReachabilitySet>();
 900
 901     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
 902       new Hashtable<Integer, ReachabilitySet>();
 903
 904     // helpful structures
 905     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
 906       new Hashtable<TokenTuple, Integer>();
 907
 908     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
 909       new Hashtable<Integer, TokenTuple>();
 910
 911     Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
 912       new Hashtable<TokenTuple, Integer>();
 913
 914     Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
 915       new Hashtable<Integer, TokenTuple>();
 916
 917     Hashtable<Integer, LabelNode> paramIndex2ln =
 918       new Hashtable<Integer, LabelNode>();
 919
 920     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
 921       new Hashtable<Integer, HashSet<HeapRegionNode> >();
 922
 923
 924     // add a bogus entry with the identity rule for easy rewrite
 925     // of new callee nodes and edges, doesn't belong to any parameter
 926     Integer bogusID = new Integer(-1);
 927     Integer bogusIndex = new Integer(-1);
 928     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
 929     TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
 930     ReachabilitySet rsIdentity =
 931       new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
 932
 933     paramIndex2rewriteH.put(bogusIndex, rsIdentity);
 934     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
 935     paramToken2paramIndex.put(bogusToken, bogusIndex);
 936     paramIndex2paramToken.put(bogusIndex, bogusToken);
 937     paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
 938     paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
 939
 940
 941     for( int i = 0; i < fm.numParameters(); ++i ) {
 942       Integer paramIndex = new Integer(i);
 943
 944       assert ogCallee.paramIndex2id.containsKey(paramIndex);
 945       Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
 946
 947       assert ogCallee.id2hrn.containsKey(idParam);
 948       HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
 949       assert hrnParam != null;
 950       paramIndex2rewriteH.put(paramIndex,
 951
 952                               toShadowTokens(ogCallee, hrnParam.getAlpha() )
 953                               );
 954
 955       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
 956       assert edgeReflexive_i != null;
 957       paramIndex2rewriteJ.put(paramIndex,
 958                               toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
 959                               );
 960
 961       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
 962       assert tdParamQ != null;
 963       LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
 964       assert lnParamQ != null;
 965       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
 966       assert edgeSpecialQ_i != null;
 967       paramIndex2rewriteK.put(paramIndex,
 968                               toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
 969                               );
 970
 971       TokenTuple p_i = new TokenTuple(hrnParam.getID(),
 972                                       true,
 973                                       TokenTuple.ARITY_ONE).makeCanonical();
 974       paramToken2paramIndex.put(p_i, paramIndex);
 975       paramIndex2paramToken.put(paramIndex, p_i);
 976
 977       TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
 978                                            true,
 979                                            TokenTuple.ARITY_MANY).makeCanonical();
 980       paramTokenStar2paramIndex.put(p_i_star, paramIndex);
 981       paramIndex2paramTokenStar.put(paramIndex, p_i_star);
 982
 983       // now depending on whether the callee is static or not
 984       // we need to account for a "this" argument in order to
 985       // find the matching argument in the caller context
 986       TempDescriptor argTemp_i;
 987       if( isStatic ) {
 988         argTemp_i = fc.getArg(paramIndex);
 989       } else {
 990         if( paramIndex == 0 ) {
 991           argTemp_i = fc.getThis();
 992         } else {
 993           argTemp_i = fc.getArg(paramIndex - 1);
 994         }
 995       }
 996
 997       // in non-static methods there is a "this" pointer
 998       // that should be taken into account
 999       if( isStatic ) {
1000         assert fc.numArgs()     == fm.numParameters();
1001       } else {
1002         assert fc.numArgs() + 1 == fm.numParameters();
1003       }
1004
1005       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1006       paramIndex2ln.put(paramIndex, argLabel_i);
1007
1008       ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
1009       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1010       while( edgeItr.hasNext() ) {
1011         ReferenceEdge edge = edgeItr.next();
1012         D_i = D_i.union(edge.getBeta() );
1013       }
1014       D_i = D_i.exhaustiveArityCombinations();
1015       paramIndex2rewriteD.put(paramIndex, D_i);
1016     }
1017
1018
1019     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1020     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1021
1022     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1023     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1024
1025     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1026     while( lnArgItr.hasNext() ) {
1027       Map.Entry me      = (Map.Entry)lnArgItr.next();
1028       Integer index   = (Integer)   me.getKey();
1029       LabelNode lnArg_i = (LabelNode) me.getValue();
1030
1031       // rewrite alpha for the nodes reachable from argument label i
1032       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1033       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1034
1035       // to find all reachable nodes, start with label referencees
1036       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1037       while( edgeArgItr.hasNext() ) {
1038         ReferenceEdge edge = edgeArgItr.next();
1039         todoNodes.add(edge.getDst() );
1040       }
1041
1042       // then follow links until all reachable nodes have been found
1043       while( !todoNodes.isEmpty() ) {
1044         HeapRegionNode hrn = todoNodes.iterator().next();
1045         todoNodes.remove(hrn);
1046         reachableNodes.add(hrn);
1047
1048         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1049         while( edgeItr.hasNext() ) {
1050           ReferenceEdge edge = edgeItr.next();
1051
1052           if( !reachableNodes.contains(edge.getDst() ) ) {
1053             todoNodes.add(edge.getDst() );
1054           }
1055         }
1056       }
1057
1058       // save for later
1059       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1060
1061       // now iterate over reachable nodes to update their alpha, and
1062       // classify edges found as "argument reachable" or "upstream"
1063       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1064       while( hrnItr.hasNext() ) {
1065         HeapRegionNode hrn = hrnItr.next();
1066
1067         rewriteCallerNodeAlpha(fm.numParameters(),
1068                                index,
1069                                hrn,
1070                                paramIndex2rewriteH,
1071                                paramIndex2rewriteD,
1072                                paramIndex2paramToken,
1073                                paramIndex2paramTokenStar);
1074
1075         nodesWithNewAlpha.add(hrn);
1076
1077         // look at all incoming edges to the reachable nodes
1078         // and sort them as edges reachable from the argument
1079         // label node, or upstream edges
1080         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1081         while( edgeItr.hasNext() ) {
1082           ReferenceEdge edge = edgeItr.next();
1083
1084           OwnershipNode on = edge.getSrc();
1085
1086           if( on instanceof LabelNode ) {
1087
1088             LabelNode ln0 = (LabelNode) on;
1089             if( ln0.equals(lnArg_i) ) {
1090               edgesReachable.add(edge);
1091             } else {
1092               edgesUpstream.add(edge);
1093             }
1094
1095           } else {
1096
1097             HeapRegionNode hrn0 = (HeapRegionNode) on;
1098             if( reachableNodes.contains(hrn0) ) {
1099               edgesReachable.add(edge);
1100             } else {
1101               edgesUpstream.add(edge);
1102             }
1103           }
1104         }
1105       }
1106
1107
1108       // update reachable edges
1109       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1110       while( edgeReachableItr.hasNext() ) {
1111         ReferenceEdge edgeReachable = edgeReachableItr.next();
1112
1113         rewriteCallerEdgeBeta(fm.numParameters(),
1114                               index,
1115                               edgeReachable,
1116                               paramIndex2rewriteJ,
1117                               paramIndex2rewriteD,
1118                               paramIndex2paramToken,
1119                               paramIndex2paramTokenStar,
1120                               false,
1121                               null);
1122
1123         edgesWithNewBeta.add(edgeReachable);
1124       }
1125
1126
1127       // update upstream edges
1128       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
1129       = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1130
1131       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1132       while( edgeUpstreamItr.hasNext() ) {
1133         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1134
1135         rewriteCallerEdgeBeta(fm.numParameters(),
1136                               index,
1137                               edgeUpstream,
1138                               paramIndex2rewriteK,
1139                               paramIndex2rewriteD,
1140                               paramIndex2paramToken,
1141                               paramIndex2paramTokenStar,
1142                               true,
1143                               edgeUpstreamPlannedChanges);
1144
1145         edgesWithNewBeta.add(edgeUpstream);
1146       }
1147
1148       propagateTokensOverEdges(edgesUpstream,
1149                                edgeUpstreamPlannedChanges,
1150                                edgesWithNewBeta);
1151     }
1152
1153
1154     // commit changes to alpha and beta
1155     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1156     while( nodeItr.hasNext() ) {
1157       nodeItr.next().applyAlphaNew();
1158     }
1159
1160     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1161     while( edgeItr.hasNext() ) {
1162       edgeItr.next().applyBetaNew();
1163     }
1164
1165
1166
1167     // verify the existence of allocation sites and their
1168     // shadows from the callee in the context of this caller graph
1169     // then map allocated nodes of callee onto the caller shadows
1170     // of them
1171     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1172     while( asItr.hasNext() ) {
1173       AllocationSite allocSite  = asItr.next();
1174       HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1175
1176       // assert that the shadow nodes have no reference edges
1177       // because they're brand new to the graph, or last time
1178       // they were used they should have been cleared of edges
1179       HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1180       assert hrnShadowSummary.getNumReferencers() == 0;
1181       assert hrnShadowSummary.getNumReferencees() == 0;
1182
1183       // then bring g_ij onto g'_ij and rewrite
1184       transferOnto(hrnSummary, hrnShadowSummary);
1185
1186       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1187       hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1188
1189       // shadow nodes only are touched by a rewrite one time,
1190       // so rewrite and immediately commit--and they don't belong
1191       // to a particular parameter, so use a bogus param index
1192       // that pulls a self-rewrite out of H
1193       rewriteCallerNodeAlpha(fm.numParameters(),
1194                              bogusIndex,
1195                              hrnShadowSummary,
1196                              paramIndex2rewriteH,
1197                              paramIndex2rewriteD,
1198                              paramIndex2paramToken,
1199                              paramIndex2paramTokenStar);
1200
1201       hrnShadowSummary.applyAlphaNew();
1202
1203
1204       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1205         Integer idIth = allocSite.getIthOldest(i);
1206         assert id2hrn.containsKey(idIth);
1207         HeapRegionNode hrnIth = id2hrn.get(idIth);
1208
1209         Integer idShadowIth = -(allocSite.getIthOldest(i));
1210         assert id2hrn.containsKey(idShadowIth);
1211         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1212         assert hrnIthShadow.getNumReferencers() == 0;
1213         assert hrnIthShadow.getNumReferencees() == 0;
1214
1215         transferOnto(hrnIth, hrnIthShadow);
1216
1217         assert ogCallee.id2hrn.containsKey(idIth);
1218         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1219         hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1220
1221         rewriteCallerNodeAlpha(fm.numParameters(),
1222                                bogusIndex,
1223                                hrnIthShadow,
1224                                paramIndex2rewriteH,
1225                                paramIndex2rewriteD,
1226                                paramIndex2paramToken,
1227                                paramIndex2paramTokenStar);
1228
1229         hrnIthShadow.applyAlphaNew();
1230       }
1231     }
1232
1233
1234     // for every heap region->heap region edge in the
1235     // callee graph, create the matching edge or edges
1236     // in the caller graph
1237     Set sCallee = ogCallee.id2hrn.entrySet();
1238     Iterator iCallee = sCallee.iterator();
1239     while( iCallee.hasNext() ) {
1240       Map.Entry meCallee  = (Map.Entry)iCallee.next();
1241       Integer idCallee  = (Integer)        meCallee.getKey();
1242       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1243
1244       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1245       while( heapRegionsItrCallee.hasNext() ) {
1246         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1247         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1248         Integer idChildCallee         = hrnChildCallee.getID();
1249
1250         // only address this edge if it is not a special reflexive edge
1251         if( !edgeCallee.isInitialParamReflexive() ) {
1252
1253           // now we know that in the callee method's ownership graph
1254           // there is a heap region->heap region reference edge given
1255           // by heap region pointers:
1256           // hrnCallee -> heapChildCallee
1257           //
1258           // or by the ownership-graph independent ID's:
1259           // idCallee -> idChildCallee
1260
1261           // make the edge with src and dst so beta info is
1262           // calculated once, then copy it for each new edge in caller
1263           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1264                                                                     null,
1265                                                                     edgeCallee.getFieldDesc(),
1266                                                                     false,
1267                                                                     toShadowTokens(ogCallee, edgeCallee.getBeta() )
1268                                                                     );
1269           rewriteCallerEdgeBeta(fm.numParameters(),
1270                                 bogusIndex,
1271                                 edgeNewInCallerTemplate,
1272                                 paramIndex2rewriteJ,
1273                                 paramIndex2rewriteD,
1274                                 paramIndex2paramToken,
1275                                 paramIndex2paramTokenStar,
1276                                 false,
1277                                 null);
1278
1279           edgeNewInCallerTemplate.applyBetaNew();
1280
1281
1282           // So now make a set of possible source heaps in the caller graph
1283           // and a set of destination heaps in the caller graph, and make
1284           // a reference edge in the caller for every possible (src,dst) pair
1285           HashSet<HeapRegionNode> possibleCallerSrcs =
1286             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1287                                                 (HeapRegionNode) edgeCallee.getSrc(),
1288                                                 paramIndex2reachableCallerNodes);
1289
1290           HashSet<HeapRegionNode> possibleCallerDsts =
1291             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1292                                                 edgeCallee.getDst(),
1293                                                 paramIndex2reachableCallerNodes);
1294
1295
1296           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1297           Iterator srcItr = possibleCallerSrcs.iterator();
1298           while( srcItr.hasNext() ) {
1299             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1300
1301             // check that if this source node has a definite type that
1302             // it also has the appropriate field, otherwise prune this
1303             AllocationSite asSrc = src.getAllocationSite();
1304             if( asSrc != null ) {
1305               boolean foundField = false;
1306               TypeDescriptor tdSrc = asSrc.getType();
1307               if( tdSrc != null && tdSrc.isClass() ) {
1308                 Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1309                 while( fieldsSrcItr.hasNext() ) {
1310                   FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1311                   if( fd == edgeCallee.getFieldDesc() ) {
1312                     foundField = true;
1313                     break;
1314                   }
1315                 }
1316                 if( !foundField ) {
1317                   // prune this source node possibility
1318                   continue;
1319                 }
1320               }
1321             }
1322
1323             Iterator dstItr = possibleCallerDsts.iterator();
1324             while( dstItr.hasNext() ) {
1325               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1326
1327               // check if this dst node has a definite type and
1328               // if it matches the callee edge
1329               AllocationSite asDst = dst.getAllocationSite();
1330               if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1331                 if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
1332                   continue;
1333                 }
1334                 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
1335                   continue;
1336                 }
1337                 if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1338                   if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
1339                     continue;
1340                   }
1341                 }
1342               }
1343
1344               // otherwise the caller src and dst pair can match the edge, so make it
1345               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1346               edgeNewInCaller.setSrc(src);
1347               edgeNewInCaller.setDst(dst);
1348
1349               ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1350               if( edgeExisting == null ) {
1351                 // if this edge doesn't exist in the caller, create it
1352                 addReferenceEdge(src, dst, edgeNewInCaller);
1353               } else {
1354                 // if it already exists, merge with it
1355                 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1356               }
1357             }
1358           }
1359         }
1360       }
1361     }
1362
1363
1364
1365     // return value may need to be assigned in caller
1366     if( fc.getReturnTemp() != null ) {
1367
1368       LabelNode lnLhsCaller = getLabelNodeFromTemp(fc.getReturnTemp() );
1369       clearReferenceEdgesFrom(lnLhsCaller, null, true);
1370
1371       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1372       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1373       while( edgeCalleeItr.hasNext() ) {
1374         ReferenceEdge edgeCallee = edgeCalleeItr.next();
1375
1376         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1377                                                                   null,
1378                                                                   edgeCallee.getFieldDesc(),
1379                                                                   false,
1380                                                                   toShadowTokens(ogCallee, edgeCallee.getBeta() )
1381                                                                   );
1382         rewriteCallerEdgeBeta(fm.numParameters(),
1383                               bogusIndex,
1384                               edgeNewInCallerTemplate,
1385                               paramIndex2rewriteJ,
1386                               paramIndex2rewriteD,
1387                               paramIndex2paramToken,
1388                               paramIndex2paramTokenStar,
1389                               false,
1390                               null);
1391
1392         edgeNewInCallerTemplate.applyBetaNew();
1393
1394
1395         HashSet<HeapRegionNode> assignCallerRhs =
1396           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1397                                               edgeCallee.getDst(),
1398                                               paramIndex2reachableCallerNodes);
1399
1400         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1401         while( itrHrn.hasNext() ) {
1402           HeapRegionNode hrnCaller = itrHrn.next();
1403
1404           // check if this dst node has a definite type and
1405           // if it matches the callee edge
1406           // check if this dst node has a definite type and
1407           // if it matches the callee edge
1408           AllocationSite asDst = hrnCaller.getAllocationSite();
1409           if( asDst != null && edgeCallee.getFieldDesc() != null ) {
1410             if( asDst.getType() == null && edgeCallee.getFieldDesc().getType() != null ) {
1411               continue;
1412             }
1413             if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() == null ) {
1414               continue;
1415             }
1416             if( asDst.getType() != null && edgeCallee.getFieldDesc().getType() != null ) {
1417               if( !asDst.getType().equals(edgeCallee.getFieldDesc().getType() ) ) {
1418                 continue;
1419               }
1420             }
1421           }
1422
1423           // otherwise caller node can match callee edge, so make it
1424           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1425           edgeNewInCaller.setSrc(lnLhsCaller);
1426           edgeNewInCaller.setDst(hrnCaller);
1427
1428           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1429           if( edgeExisting == null ) {
1430             // if this edge doesn't exist in the caller, create it
1431             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1432           } else {
1433             // if it already exists, merge with it
1434             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1435           }
1436         }
1437       }
1438     }
1439
1440
1441
1442     // merge the shadow nodes of allocation sites back down to normal capacity
1443     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1444     while( allocItr.hasNext() ) {
1445       AllocationSite as = allocItr.next();
1446
1447       // first age each allocation site enough times to make room for the shadow nodes
1448       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1449         age(as);
1450       }
1451
1452       // then merge the shadow summary into the normal summary
1453       HeapRegionNode hrnSummary = getSummaryNode(as);
1454       assert hrnSummary != null;
1455
1456       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1457       assert hrnSummaryShadow != null;
1458
1459       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1460
1461       // then clear off after merge
1462       clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1463       clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1464       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1465
1466       // then transplant shadow nodes onto the now clean normal nodes
1467       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1468
1469         Integer idIth = as.getIthOldest(i);
1470         HeapRegionNode hrnIth = id2hrn.get(idIth);
1471
1472         Integer idIthShadow = as.getIthOldestShadow(i);
1473         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1474
1475         transferOnto(hrnIthShadow, hrnIth);
1476
1477         // clear off shadow nodes after transfer
1478         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1479         clearReferenceEdgesTo(hrnIthShadow, null, true);
1480         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1481       }
1482
1483       // finally, globally change shadow tokens into normal tokens
1484       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1485       while( itrAllLabelNodes.hasNext() ) {
1486         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1487         LabelNode ln = (LabelNode) me.getValue();
1488
1489         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1490         while( itrEdges.hasNext() ) {
1491           unshadowTokens(as, itrEdges.next() );
1492         }
1493       }
1494
1495       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1496       while( itrAllHRNodes.hasNext() ) {
1497         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1498         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1499
1500         unshadowTokens(as, hrnToAge);
1501
1502         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1503         while( itrEdges.hasNext() ) {
1504           unshadowTokens(as, itrEdges.next() );
1505         }
1506       }
1507     }
1508   }
1509
1510
1511   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1512     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1513   }
1514
1515   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1516     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1517   }
1518
1519
1520   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1521                                          ReachabilitySet rsIn) {
1522
1523     ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1524
1525     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1526     while( allocItr.hasNext() ) {
1527       AllocationSite as = allocItr.next();
1528
1529       rsOut = rsOut.toShadowTokens(as);
1530     }
1531
1532     return rsOut.makeCanonical();
1533   }
1534
1535
1536   private void rewriteCallerNodeAlpha(int numParameters,
1537                                       Integer paramIndex,
1538                                       HeapRegionNode hrn,
1539                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1540                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1541                                       Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1542                                       Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1543
1544     ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
1545     assert rules != null;
1546
1547     TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1548     assert tokenToRewrite != null;
1549
1550     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1551     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1552     while( ttsItr.hasNext() ) {
1553       TokenTupleSet tts = ttsItr.next();
1554       r0 = r0.union(tts.rewriteToken(tokenToRewrite,
1555                                      hrn.getAlpha(),
1556                                      false,
1557                                      null) );
1558     }
1559
1560     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1561     ttsItr = r0.iterator();
1562     while( ttsItr.hasNext() ) {
1563       TokenTupleSet tts = ttsItr.next();
1564       r1 = r1.union(rewriteDpass(numParameters,
1565                                  paramIndex,
1566                                  tts,
1567                                  paramIndex2rewriteD,
1568                                  paramIndex2paramToken,
1569                                  paramIndex2paramTokenStar) );
1570     }
1571
1572     hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
1573   }
1574
1575
1576   private void rewriteCallerEdgeBeta(int numParameters,
1577                                      Integer paramIndex,
1578                                      ReferenceEdge edge,
1579                                      Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1580                                      Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1581                                      Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1582                                      Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1583                                      boolean makeChangeSet,
1584                                      Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1585
1586     ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
1587     assert rules != null;
1588
1589     TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1590     assert tokenToRewrite != null;
1591
1592     ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1593
1594     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1595     while( ttsItr.hasNext() ) {
1596       TokenTupleSet tts = ttsItr.next();
1597
1598       Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1599         new Hashtable<TokenTupleSet, TokenTupleSet>();
1600
1601       ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
1602                                                edge.getBeta(),
1603                                                true,
1604                                                forChangeSet);
1605
1606       Iterator fcsItr = forChangeSet.entrySet().iterator();
1607       while( fcsItr.hasNext() ) {
1608         Map.Entry me = (Map.Entry)fcsItr.next();
1609         TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1610         TokenTupleSet ttsAdd   = (TokenTupleSet) me.getValue();
1611
1612         ChangeTuple ct = new ChangeTuple(ttsMatch,
1613                                          ttsAdd
1614                                          ).makeCanonical();
1615
1616         cts0 = cts0.union(ct);
1617       }
1618     }
1619
1620
1621     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1622     ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1623
1624     Iterator<ChangeTuple> ctItr = cts0.iterator();
1625     while( ctItr.hasNext() ) {
1626       ChangeTuple ct = ctItr.next();
1627
1628       ReachabilitySet rTemp = rewriteDpass(numParameters,
1629                                            paramIndex,
1630                                            ct.getSetToAdd(),
1631                                            paramIndex2rewriteD,
1632                                            paramIndex2paramToken,
1633                                            paramIndex2paramTokenStar
1634                                            ).makeCanonical();
1635       r1 = r1.union(rTemp);
1636
1637       if( makeChangeSet ) {
1638         assert edgePlannedChanges != null;
1639
1640         Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1641         while( ttsTempItr.hasNext() ) {
1642           TokenTupleSet tts = ttsTempItr.next();
1643
1644           ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
1645                                                 tts
1646                                                 ).makeCanonical();
1647
1648           cts1 = cts1.union(ctFinal);
1649         }
1650       }
1651     }
1652
1653     if( makeChangeSet ) {
1654       edgePlannedChanges.put(edge, cts1);
1655     }
1656
1657     edge.setBetaNew(edge.getBetaNew().union(r1) );
1658   }
1659
1660
1661   private ReachabilitySet rewriteDpass(int numParameters,
1662                                        Integer paramIndex,
1663                                        TokenTupleSet ttsIn,
1664                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1665                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1666                                        Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1667
1668     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1669
1670     boolean rewritten = false;
1671
1672     for( int j = 0; j < numParameters; ++j ) {
1673       Integer paramIndexJ = new Integer(j);
1674       ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ);
1675       assert D_j != null;
1676
1677       if( paramIndexJ != paramIndex ) {
1678         TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ);
1679         assert tokenToRewriteJ != null;
1680         if( ttsIn.containsTuple(tokenToRewriteJ) ) {
1681           ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ,
1682                                                  D_j,
1683                                                  false,
1684                                                  null);
1685           Iterator<TokenTupleSet> ttsItr = r.iterator();
1686           while( ttsItr.hasNext() ) {
1687             TokenTupleSet tts = ttsItr.next();
1688             rsOut = rsOut.union(rewriteDpass(numParameters,
1689                                              paramIndex,
1690                                              tts,
1691                                              paramIndex2rewriteD,
1692                                              paramIndex2paramToken,
1693                                              paramIndex2paramTokenStar) );
1694             rewritten = true;
1695           }
1696         }
1697       }
1698
1699       TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ);
1700       assert tokenStarToRewriteJ != null;
1701       if( ttsIn.containsTuple(tokenStarToRewriteJ) ) {
1702         ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ,
1703                                                D_j,
1704                                                false,
1705                                                null);
1706         Iterator<TokenTupleSet> ttsItr = r.iterator();
1707         while( ttsItr.hasNext() ) {
1708           TokenTupleSet tts = ttsItr.next();
1709           rsOut = rsOut.union(rewriteDpass(numParameters,
1710                                            paramIndex,
1711                                            tts,
1712                                            paramIndex2rewriteD,
1713                                            paramIndex2paramToken,
1714                                            paramIndex2paramTokenStar) );
1715           rewritten = true;
1716         }
1717       }
1718     }
1719
1720     if( !rewritten ) {
1721       rsOut = rsOut.union(ttsIn);
1722     }
1723
1724     return rsOut;
1725   }
1726
1727
1728   private HashSet<HeapRegionNode>
1729   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1730                                       HeapRegionNode hrnCallee,
1731                                       Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1732                                       ) {
1733
1734     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1735
1736     Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1737
1738     if( paramIndexCallee == null ) {
1739       // this is a node allocated in the callee then and it has
1740       // exactly one shadow node in the caller to map to
1741       AllocationSite as = hrnCallee.getAllocationSite();
1742       assert as != null;
1743
1744       int age = as.getAgeCategory(hrnCallee.getID() );
1745       assert age != AllocationSite.AGE_notInThisSite;
1746
1747       Integer idCaller;
1748       if( age == AllocationSite.AGE_summary ) {
1749         idCaller = as.getSummaryShadow();
1750       } else if( age == AllocationSite.AGE_oldest ) {
1751         idCaller = as.getOldestShadow();
1752       } else {
1753         assert age == AllocationSite.AGE_in_I;
1754
1755         Integer I = as.getAge(hrnCallee.getID() );
1756         assert I != null;
1757
1758         idCaller = as.getIthOldestShadow(I);
1759       }
1760
1761       assert id2hrn.containsKey(idCaller);
1762       HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1763       possibleCallerHRNs.add(hrnCaller);
1764
1765     } else {
1766       // this is a node that was created to represent a parameter
1767       // so it maps to a whole mess of heap regions
1768       assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1769       possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1770     }
1771
1772     return possibleCallerHRNs;
1773   }
1774
1775
1776
1777   ////////////////////////////////////////////////////
1778   // in merge() and equals() methods the suffix A
1779   // represents the passed in graph and the suffix
1780   // B refers to the graph in this object
1781   // Merging means to take the incoming graph A and
1782   // merge it into B, so after the operation graph B
1783   // is the final result.
1784   ////////////////////////////////////////////////////
1785   public void merge(OwnershipGraph og) {
1786
1787     if( og == null ) {
1788       return;
1789     }
1790
1791     mergeOwnershipNodes(og);
1792     mergeReferenceEdges(og);
1793     mergeId2paramIndex(og);
1794     mergeAllocationSites(og);
1795   }
1796
1797
1798   protected void mergeOwnershipNodes(OwnershipGraph og) {
1799     Set sA = og.id2hrn.entrySet();
1800     Iterator iA = sA.iterator();
1801     while( iA.hasNext() ) {
1802       Map.Entry meA  = (Map.Entry)iA.next();
1803       Integer idA  = (Integer)        meA.getKey();
1804       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1805
1806       // if this graph doesn't have a node the
1807       // incoming graph has, allocate it
1808       if( !id2hrn.containsKey(idA) ) {
1809         HeapRegionNode hrnB = hrnA.copy();
1810         id2hrn.put(idA, hrnB);
1811
1812       } else {
1813         // otherwise this is a node present in both graphs
1814         // so make the new reachability set a union of the
1815         // nodes' reachability sets
1816         HeapRegionNode hrnB = id2hrn.get(idA);
1817         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1818       }
1819     }
1820
1821     // now add any label nodes that are in graph B but
1822     // not in A
1823     sA = og.td2ln.entrySet();
1824     iA = sA.iterator();
1825     while( iA.hasNext() ) {
1826       Map.Entry meA = (Map.Entry)iA.next();
1827       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1828       LabelNode lnA = (LabelNode)      meA.getValue();
1829
1830       // if the label doesn't exist in B, allocate and add it
1831       LabelNode lnB = getLabelNodeFromTemp(tdA);
1832     }
1833   }
1834
1835   protected void mergeReferenceEdges(OwnershipGraph og) {
1836
1837     // heap regions
1838     Set sA = og.id2hrn.entrySet();
1839     Iterator iA = sA.iterator();
1840     while( iA.hasNext() ) {
1841       Map.Entry meA  = (Map.Entry)iA.next();
1842       Integer idA  = (Integer)        meA.getKey();
1843       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1844
1845       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1846       while( heapRegionsItrA.hasNext() ) {
1847         ReferenceEdge edgeA     = heapRegionsItrA.next();
1848         HeapRegionNode hrnChildA = edgeA.getDst();
1849         Integer idChildA  = hrnChildA.getID();
1850
1851         // at this point we know an edge in graph A exists
1852         // idA -> idChildA, does this exist in B?
1853         assert id2hrn.containsKey(idA);
1854         HeapRegionNode hrnB        = id2hrn.get(idA);
1855         ReferenceEdge edgeToMerge = null;
1856
1857         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1858         while( heapRegionsItrB.hasNext() &&
1859                edgeToMerge == null          ) {
1860
1861           ReferenceEdge edgeB     = heapRegionsItrB.next();
1862           HeapRegionNode hrnChildB = edgeB.getDst();
1863           Integer idChildB  = hrnChildB.getID();
1864
1865           // don't use the ReferenceEdge.equals() here because
1866           // we're talking about existence between graphs
1867           if( idChildB.equals(idChildA) &&
1868               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1869             edgeToMerge = edgeB;
1870           }
1871         }
1872
1873         // if the edge from A was not found in B,
1874         // add it to B.
1875         if( edgeToMerge == null ) {
1876           assert id2hrn.containsKey(idChildA);
1877           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1878           edgeToMerge = edgeA.copy();
1879           edgeToMerge.setSrc(hrnB);
1880           edgeToMerge.setDst(hrnChildB);
1881           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1882         }
1883         // otherwise, the edge already existed in both graphs
1884         // so merge their reachability sets
1885         else {
1886           // just replace this beta set with the union
1887           assert edgeToMerge != null;
1888           edgeToMerge.setBeta(
1889             edgeToMerge.getBeta().union(edgeA.getBeta() )
1890             );
1891           if( !edgeA.isInitialParamReflexive() ) {
1892             edgeToMerge.setIsInitialParamReflexive(false);
1893           }
1894         }
1895       }
1896     }
1897
1898     // and then again with label nodes
1899     sA = og.td2ln.entrySet();
1900     iA = sA.iterator();
1901     while( iA.hasNext() ) {
1902       Map.Entry meA = (Map.Entry)iA.next();
1903       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1904       LabelNode lnA = (LabelNode)      meA.getValue();
1905
1906       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1907       while( heapRegionsItrA.hasNext() ) {
1908         ReferenceEdge edgeA     = heapRegionsItrA.next();
1909         HeapRegionNode hrnChildA = edgeA.getDst();
1910         Integer idChildA  = hrnChildA.getID();
1911
1912         // at this point we know an edge in graph A exists
1913         // tdA -> idChildA, does this exist in B?
1914         assert td2ln.containsKey(tdA);
1915         LabelNode lnB         = td2ln.get(tdA);
1916         ReferenceEdge edgeToMerge = null;
1917
1918         // labels never have edges with a field
1919         //assert edgeA.getFieldDesc() == null;
1920
1921         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1922         while( heapRegionsItrB.hasNext() &&
1923                edgeToMerge == null          ) {
1924
1925           ReferenceEdge edgeB     = heapRegionsItrB.next();
1926           HeapRegionNode hrnChildB = edgeB.getDst();
1927           Integer idChildB  = hrnChildB.getID();
1928
1929           // labels never have edges with a field
1930           //assert edgeB.getFieldDesc() == null;
1931
1932           // don't use the ReferenceEdge.equals() here because
1933           // we're talking about existence between graphs
1934           if( idChildB.equals(idChildA) &&
1935               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1936             edgeToMerge = edgeB;
1937           }
1938         }
1939
1940         // if the edge from A was not found in B,
1941         // add it to B.
1942         if( edgeToMerge == null ) {
1943           assert id2hrn.containsKey(idChildA);
1944           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1945           edgeToMerge = edgeA.copy();
1946           edgeToMerge.setSrc(lnB);
1947           edgeToMerge.setDst(hrnChildB);
1948           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1949         }
1950         // otherwise, the edge already existed in both graphs
1951         // so merge their reachability sets
1952         else {
1953           // just replace this beta set with the union
1954           edgeToMerge.setBeta(
1955             edgeToMerge.getBeta().union(edgeA.getBeta() )
1956             );
1957           if( !edgeA.isInitialParamReflexive() ) {
1958             edgeToMerge.setIsInitialParamReflexive(false);
1959           }
1960         }
1961       }
1962     }
1963   }
1964
1965   // you should only merge ownership graphs that have the
1966   // same number of parameters, or if one or both parameter
1967   // index tables are empty
1968   protected void mergeId2paramIndex(OwnershipGraph og) {
1969     if( id2paramIndex.size() == 0 ) {
1970       id2paramIndex  = og.id2paramIndex;
1971       paramIndex2id  = og.paramIndex2id;
1972       paramIndex2tdQ = og.paramIndex2tdQ;
1973       return;
1974     }
1975
1976     if( og.id2paramIndex.size() == 0 ) {
1977       return;
1978     }
1979
1980     assert id2paramIndex.size() == og.id2paramIndex.size();
1981   }
1982
1983   protected void mergeAllocationSites(OwnershipGraph og) {
1984     allocationSites.addAll(og.allocationSites);
1985   }
1986
1987
1988
1989   // it is necessary in the equals() member functions
1990   // to "check both ways" when comparing the data
1991   // structures of two graphs.  For instance, if all
1992   // edges between heap region nodes in graph A are
1993   // present and equal in graph B it is not sufficient
1994   // to say the graphs are equal.  Consider that there
1995   // may be edges in graph B that are not in graph A.
1996   // the only way to know that all edges in both graphs
1997   // are equally present is to iterate over both data
1998   // structures and compare against the other graph.
1999   public boolean equals(OwnershipGraph og) {
2000
2001     if( og == null ) {
2002       return false;
2003     }
2004
2005     if( !areHeapRegionNodesEqual(og) ) {
2006       return false;
2007     }
2008
2009     if( !areLabelNodesEqual(og) ) {
2010       return false;
2011     }
2012
2013     if( !areReferenceEdgesEqual(og) ) {
2014       return false;
2015     }
2016
2017     if( !areId2paramIndexEqual(og) ) {
2018       return false;
2019     }
2020
2021     // if everything is equal up to this point,
2022     // assert that allocationSites is also equal--
2023     // this data is redundant and kept for efficiency
2024     assert allocationSites.equals(og.allocationSites);
2025
2026     return true;
2027   }
2028
2029   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2030
2031     if( !areallHRNinAalsoinBandequal(this, og) ) {
2032       return false;
2033     }
2034
2035     if( !areallHRNinAalsoinBandequal(og, this) ) {
2036       return false;
2037     }
2038
2039     return true;
2040   }
2041
2042   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2043                                                        OwnershipGraph ogB) {
2044     Set sA = ogA.id2hrn.entrySet();
2045     Iterator iA = sA.iterator();
2046     while( iA.hasNext() ) {
2047       Map.Entry meA  = (Map.Entry)iA.next();
2048       Integer idA  = (Integer)        meA.getKey();
2049       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2050
2051       if( !ogB.id2hrn.containsKey(idA) ) {
2052         return false;
2053       }
2054
2055       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2056       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2057         return false;
2058       }
2059     }
2060
2061     return true;
2062   }
2063
2064
2065   protected boolean areLabelNodesEqual(OwnershipGraph og) {
2066
2067     if( !areallLNinAalsoinBandequal(this, og) ) {
2068       return false;
2069     }
2070
2071     if( !areallLNinAalsoinBandequal(og, this) ) {
2072       return false;
2073     }
2074
2075     return true;
2076   }
2077
2078   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2079                                                       OwnershipGraph ogB) {
2080     Set sA = ogA.td2ln.entrySet();
2081     Iterator iA = sA.iterator();
2082     while( iA.hasNext() ) {
2083       Map.Entry meA = (Map.Entry)iA.next();
2084       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2085
2086       if( !ogB.td2ln.containsKey(tdA) ) {
2087         return false;
2088       }
2089     }
2090
2091     return true;
2092   }
2093
2094
2095   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2096     if( !areallREinAandBequal(this, og) ) {
2097       return false;
2098     }
2099
2100     return true;
2101   }
2102
2103   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2104                                                 OwnershipGraph ogB) {
2105
2106     // check all the heap region->heap region edges
2107     Set sA = ogA.id2hrn.entrySet();
2108     Iterator iA = sA.iterator();
2109     while( iA.hasNext() ) {
2110       Map.Entry meA  = (Map.Entry)iA.next();
2111       Integer idA  = (Integer)        meA.getKey();
2112       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2113
2114       // we should have already checked that the same
2115       // heap regions exist in both graphs
2116       assert ogB.id2hrn.containsKey(idA);
2117
2118       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2119         return false;
2120       }
2121
2122       // then check every edge in B for presence in A, starting
2123       // from the same parent HeapRegionNode
2124       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2125
2126       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2127         return false;
2128       }
2129     }
2130
2131     // then check all the label->heap region edges
2132     sA = ogA.td2ln.entrySet();
2133     iA = sA.iterator();
2134     while( iA.hasNext() ) {
2135       Map.Entry meA = (Map.Entry)iA.next();
2136       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2137       LabelNode lnA = (LabelNode)      meA.getValue();
2138
2139       // we should have already checked that the same
2140       // label nodes exist in both graphs
2141       assert ogB.td2ln.containsKey(tdA);
2142
2143       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2144         return false;
2145       }
2146
2147       // then check every edge in B for presence in A, starting
2148       // from the same parent LabelNode
2149       LabelNode lnB = ogB.td2ln.get(tdA);
2150
2151       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2152         return false;
2153       }
2154     }
2155
2156     return true;
2157   }
2158
2159
2160   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2161                                                  OwnershipNode onA,
2162                                                  OwnershipGraph ogB) {
2163
2164     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2165     while( itrA.hasNext() ) {
2166       ReferenceEdge edgeA     = itrA.next();
2167       HeapRegionNode hrnChildA = edgeA.getDst();
2168       Integer idChildA  = hrnChildA.getID();
2169
2170       assert ogB.id2hrn.containsKey(idChildA);
2171
2172       // at this point we know an edge in graph A exists
2173       // onA -> idChildA, does this exact edge exist in B?
2174       boolean edgeFound = false;
2175
2176       OwnershipNode onB = null;
2177       if( onA instanceof HeapRegionNode ) {
2178         HeapRegionNode hrnA = (HeapRegionNode) onA;
2179         onB = ogB.id2hrn.get(hrnA.getID() );
2180       } else {
2181         LabelNode lnA = (LabelNode) onA;
2182         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2183       }
2184
2185       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2186       while( itrB.hasNext() ) {
2187         ReferenceEdge edgeB     = itrB.next();
2188         HeapRegionNode hrnChildB = edgeB.getDst();
2189         Integer idChildB  = hrnChildB.getID();
2190
2191         if( idChildA.equals(idChildB) &&
2192             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2193
2194           // there is an edge in the right place with the right field,
2195           // but do they have the same attributes?
2196           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2197
2198             edgeFound = true;
2199             //} else {
2200             //return false;
2201           }
2202         }
2203       }
2204
2205       if( !edgeFound ) {
2206         return false;
2207       }
2208     }
2209
2210     return true;
2211   }
2212
2213
2214   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2215     return id2paramIndex.size() == og.id2paramIndex.size();
2216   }
2217
2218
2219   public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2220
2221     // get parameter's heap region
2222     assert paramIndex2id.containsKey(paramIndex1);
2223     Integer idParam1 = paramIndex2id.get(paramIndex1);
2224
2225     assert id2hrn.containsKey(idParam1);
2226     HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2227     assert hrnParam1 != null;
2228
2229     // get tokens for this parameter
2230     TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2231                                    true,
2232                                    TokenTuple.ARITY_ONE).makeCanonical();
2233
2234     TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2235                                        true,
2236                                        TokenTuple.ARITY_MANY).makeCanonical();
2237
2238
2239     // get tokens for the other parameter
2240     assert paramIndex2id.containsKey(paramIndex2);
2241     Integer idParam2 = paramIndex2id.get(paramIndex2);
2242
2243     assert id2hrn.containsKey(idParam2);
2244     HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2245     assert hrnParam2 != null;
2246
2247     TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2248                                    true,
2249                                    TokenTuple.ARITY_ONE).makeCanonical();
2250
2251     TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2252                                        true,
2253                                        TokenTuple.ARITY_MANY).makeCanonical();
2254
2255
2256     // get special label p_q for first parameter
2257     TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2258     assert tdParamQ1 != null;
2259     LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2260     assert lnParamQ1 != null;
2261
2262     // then get the edge from label q to parameter's hrn
2263     ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2264     assert edgeSpecialQ1 != null;
2265
2266     // if the beta of this edge has tokens from both parameters in one
2267     // token tuple set, then there is a potential alias between them
2268     ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2269     assert beta1 != null;
2270
2271     if( beta1.containsTupleSetWithBoth(p1,     p2) ) {
2272       return true;
2273     }
2274     if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2275       return true;
2276     }
2277     if( beta1.containsTupleSetWithBoth(p1,     pStar2) ) {
2278       return true;
2279     }
2280     if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2281       return true;
2282     }
2283
2284     return false;
2285   }
2286
2287
2288   public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2289
2290     // get parameter's heap region
2291     assert paramIndex2id.containsKey(paramIndex);
2292     Integer idParam = paramIndex2id.get(paramIndex);
2293
2294     assert id2hrn.containsKey(idParam);
2295     HeapRegionNode hrnParam = id2hrn.get(idParam);
2296     assert hrnParam != null;
2297
2298     // get tokens for this parameter
2299     TokenTuple p = new TokenTuple(hrnParam.getID(),
2300                                   true,
2301                                   TokenTuple.ARITY_ONE).makeCanonical();
2302
2303     TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2304                                       true,
2305                                       TokenTuple.ARITY_MANY).makeCanonical();
2306
2307     // get special label p_q
2308     TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2309     assert tdParamQ != null;
2310     LabelNode lnParamQ = td2ln.get(tdParamQ);
2311     assert lnParamQ != null;
2312
2313     // then get the edge from label q to parameter's hrn
2314     ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2315     assert edgeSpecialQ != null;
2316
2317     // look through this beta set for potential aliases
2318     ReachabilitySet beta = edgeSpecialQ.getBeta();
2319     assert beta != null;
2320
2321
2322     // get tokens for summary node
2323     TokenTuple gs = new TokenTuple(as.getSummary(),
2324                                    true,
2325                                    TokenTuple.ARITY_ONE).makeCanonical();
2326
2327     TokenTuple gsStar = new TokenTuple(as.getSummary(),
2328                                        true,
2329                                        TokenTuple.ARITY_MANY).makeCanonical();
2330
2331     if( beta.containsTupleSetWithBoth(p,     gs) ) {
2332       return true;
2333     }
2334     if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2335       return true;
2336     }
2337     if( beta.containsTupleSetWithBoth(p,     gsStar) ) {
2338       return true;
2339     }
2340     if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2341       return true;
2342     }
2343
2344     // check for other nodes
2345     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2346
2347       // the other nodes of an allocation site are single, no stars
2348       TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2349                                      false,
2350                                      TokenTuple.ARITY_ONE).makeCanonical();
2351
2352       if( beta.containsTupleSetWithBoth(p,     gi) ) {
2353         return true;
2354       }
2355       if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2356         return true;
2357       }
2358     }
2359
2360     return false;
2361   }
2362
2363
2364   public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2365
2366     // get tokens for summary nodes
2367     TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2368                                     true,
2369                                     TokenTuple.ARITY_ONE).makeCanonical();
2370
2371     TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2372                                         true,
2373                                         TokenTuple.ARITY_MANY).makeCanonical();
2374
2375     // get summary node's alpha
2376     Integer idSum1 = as1.getSummary();
2377     assert id2hrn.containsKey(idSum1);
2378     HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2379     assert hrnSum1 != null;
2380     ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2381     assert alphaSum1 != null;
2382
2383
2384     // and for the other one
2385     TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2386                                     true,
2387                                     TokenTuple.ARITY_ONE).makeCanonical();
2388
2389     TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2390                                         true,
2391                                         TokenTuple.ARITY_MANY).makeCanonical();
2392
2393     // get summary node's alpha
2394     Integer idSum2 = as2.getSummary();
2395     assert id2hrn.containsKey(idSum2);
2396     HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2397     assert hrnSum2 != null;
2398     ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2399     assert alphaSum2 != null;
2400
2401     // does either one report reachability from the other tokens?
2402     if( alphaSum1.containsTuple(gsStar2) ) {
2403       return true;
2404     }
2405     if( alphaSum2.containsTuple(gsStar1) ) {
2406       return true;
2407     }
2408
2409     // only check non-star token if they are different sites
2410     if( as1 != as2 ) {
2411       if( alphaSum1.containsTuple(gs2) ) {
2412         return true;
2413       }
2414       if( alphaSum2.containsTuple(gs1) ) {
2415         return true;
2416       }
2417     }
2418
2419
2420     // check sum2 against alloc1 nodes
2421     for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2422       Integer idI1 = as1.getIthOldest(i);
2423       assert id2hrn.containsKey(idI1);
2424       HeapRegionNode hrnI1 = id2hrn.get(idI1);
2425       assert hrnI1 != null;
2426       ReachabilitySet alphaI1 = hrnI1.getAlpha();
2427       assert alphaI1 != null;
2428
2429       // the other nodes of an allocation site are single, no stars
2430       TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2431                                       false,
2432                                       TokenTuple.ARITY_ONE).makeCanonical();
2433
2434       if( alphaSum2.containsTuple(gi1) ) {
2435         return true;
2436       }
2437       if( alphaI1.containsTuple(gs2) ) {
2438         return true;
2439       }
2440       if( alphaI1.containsTuple(gsStar2) ) {
2441         return true;
2442       }
2443     }
2444
2445     // check sum1 against alloc2 nodes
2446     for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2447       Integer idI2 = as2.getIthOldest(i);
2448       assert id2hrn.containsKey(idI2);
2449       HeapRegionNode hrnI2 = id2hrn.get(idI2);
2450       assert hrnI2 != null;
2451       ReachabilitySet alphaI2 = hrnI2.getAlpha();
2452       assert alphaI2 != null;
2453
2454       TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2455                                       false,
2456                                       TokenTuple.ARITY_ONE).makeCanonical();
2457
2458       if( alphaSum1.containsTuple(gi2) ) {
2459         return true;
2460       }
2461       if( alphaI2.containsTuple(gs1) ) {
2462         return true;
2463       }
2464       if( alphaI2.containsTuple(gsStar1) ) {
2465         return true;
2466       }
2467
2468       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2469       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2470         Integer idI1 = as1.getIthOldest(j);
2471
2472         // if these are the same site, don't look for the same token, no alias
2473         // different tokens of the same site could alias together though
2474         if( idI1 == idI2 ) {
2475           continue;
2476         }
2477
2478         HeapRegionNode hrnI1 = id2hrn.get(idI1);
2479         ReachabilitySet alphaI1 = hrnI1.getAlpha();
2480         TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2481                                         false,
2482                                         TokenTuple.ARITY_ONE).makeCanonical();
2483         if( alphaI2.containsTuple(gi1) ) {
2484           return true;
2485         }
2486         if( alphaI1.containsTuple(gi2) ) {
2487           return true;
2488         }
2489       }
2490     }
2491
2492     return false;
2493   }
2494
2495
2496   // for writing ownership graphs to dot files
2497   public void writeGraph(Descriptor methodDesc,
2498                          FlatNode fn,
2499                          boolean writeLabels,
2500                          boolean labelSelect,
2501                          boolean pruneGarbage,
2502                          boolean writeReferencers
2503                          ) throws java.io.IOException {
2504     writeGraph(
2505       methodDesc.getSymbol() +
2506       methodDesc.getNum() +
2507       fn.toString(),
2508       writeLabels,
2509       labelSelect,
2510       pruneGarbage,
2511       writeReferencers
2512       );
2513   }
2514
2515   public void writeGraph(Descriptor methodDesc,
2516                          boolean writeLabels,
2517                          boolean labelSelect,
2518                          boolean pruneGarbage,
2519                          boolean writeReferencers
2520                          ) throws java.io.IOException {
2521
2522     writeGraph(methodDesc+"COMPLETE",
2523                writeLabels,
2524                labelSelect,
2525                pruneGarbage,
2526                writeReferencers
2527                );
2528   }
2529
2530   public void writeGraph(Descriptor methodDesc,
2531                          Integer numUpdate,
2532                          boolean writeLabels,
2533                          boolean labelSelect,
2534                          boolean pruneGarbage,
2535                          boolean writeReferencers
2536                          ) throws java.io.IOException {
2537
2538     writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2539                writeLabels,
2540                labelSelect,
2541                pruneGarbage,
2542                writeReferencers
2543                );
2544   }
2545
2546   public void writeGraph(String graphName,
2547                          boolean writeLabels,
2548                          boolean labelSelect,
2549                          boolean pruneGarbage,
2550                          boolean writeReferencers
2551                          ) throws java.io.IOException {
2552
2553     // remove all non-word characters from the graph name so
2554     // the filename and identifier in dot don't cause errors
2555     graphName = graphName.replaceAll("[\\W]", "");
2556
2557     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2558     bw.write("digraph "+graphName+" {\n");
2559     //bw.write( "  size=\"7.5,10\";\n" );
2560
2561     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2562
2563     // then visit every heap region node
2564     if( !pruneGarbage ) {
2565       Set s = id2hrn.entrySet();
2566       Iterator i = s.iterator();
2567       while( i.hasNext() ) {
2568         Map.Entry me  = (Map.Entry)i.next();
2569         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2570         if( !visited.contains(hrn) ) {
2571           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2572                                   hrn,
2573                                   bw,
2574                                   null,
2575                                   visited,
2576                                   writeReferencers);
2577         }
2578       }
2579     }
2580
2581     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2582
2583     Set df = paramIndex2id.entrySet();
2584     Iterator ih = df.iterator();
2585     while( ih.hasNext() ) {
2586       Map.Entry meh = (Map.Entry)ih.next();
2587       Integer pi = (Integer) meh.getKey();
2588       Integer id = (Integer) meh.getValue();
2589       bw.write("  pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2590     }
2591
2592     // then visit every label node, useful for debugging
2593     if( writeLabels ) {
2594       Set s = td2ln.entrySet();
2595       Iterator i = s.iterator();
2596       while( i.hasNext() ) {
2597         Map.Entry me = (Map.Entry)i.next();
2598         LabelNode ln = (LabelNode) me.getValue();
2599
2600         if( labelSelect ) {
2601           String labelStr = ln.getTempDescriptorString();
2602           if( labelStr.startsWith("___temp") ||
2603               labelStr.startsWith("___dst") ||
2604               labelStr.startsWith("___srctmp") ||
2605               labelStr.startsWith("___neverused")   ) {
2606             continue;
2607           }
2608         }
2609
2610         bw.write(ln.toString() + ";\n");
2611
2612         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2613         while( heapRegionsItr.hasNext() ) {
2614           ReferenceEdge edge = heapRegionsItr.next();
2615           HeapRegionNode hrn  = edge.getDst();
2616
2617           if( pruneGarbage && !visited.contains(hrn) ) {
2618             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2619                                     hrn,
2620                                     bw,
2621                                     null,
2622                                     visited,
2623                                     writeReferencers);
2624           }
2625
2626           bw.write("  "        + ln.toString() +
2627                    " -> "      + hrn.toString() +
2628                    "[label=\"" + edge.toGraphEdgeString() +
2629                    "\",decorate];\n");
2630         }
2631       }
2632     }
2633
2634
2635     bw.write("}\n");
2636     bw.close();
2637   }
2638
2639   protected void traverseHeapRegionNodes(int mode,
2640                                          HeapRegionNode hrn,
2641                                          BufferedWriter bw,
2642                                          TempDescriptor td,
2643                                          HashSet<HeapRegionNode> visited,
2644                                          boolean writeReferencers
2645                                          ) throws java.io.IOException {
2646
2647     if( visited.contains(hrn) ) {
2648       return;
2649     }
2650     visited.add(hrn);
2651
2652     switch( mode ) {
2653     case VISIT_HRN_WRITE_FULL:
2654
2655       String attributes = "[";
2656
2657       if( hrn.isSingleObject() ) {
2658         attributes += "shape=box";
2659       } else {
2660         attributes += "shape=Msquare";
2661       }
2662
2663       if( hrn.isFlagged() ) {
2664         attributes += ",style=filled,fillcolor=lightgrey";
2665       }
2666
2667       attributes += ",label=\"ID"        +
2668                     hrn.getID()          +
2669                     "\\n"                +
2670                     hrn.getDescription() +
2671                     "\\n"                +
2672                     hrn.getAlphaString() +
2673                     "\"]";
2674
2675       bw.write("  " + hrn.toString() + attributes + ";\n");
2676       break;
2677     }
2678
2679
2680     // useful for debugging
2681     if( writeReferencers ) {
2682       OwnershipNode onRef  = null;
2683       Iterator refItr = hrn.iteratorToReferencers();
2684       while( refItr.hasNext() ) {
2685         onRef = (OwnershipNode) refItr.next();
2686
2687         switch( mode ) {
2688         case VISIT_HRN_WRITE_FULL:
2689           bw.write("  "                    + hrn.toString() +
2690                    " -> "                  + onRef.toString() +
2691                    "[color=lightgray];\n");
2692           break;
2693         }
2694       }
2695     }
2696
2697     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2698     while( childRegionsItr.hasNext() ) {
2699       ReferenceEdge edge     = childRegionsItr.next();
2700       HeapRegionNode hrnChild = edge.getDst();
2701
2702       switch( mode ) {
2703       case VISIT_HRN_WRITE_FULL:
2704         bw.write("  "        + hrn.toString() +
2705                  " -> "      + hrnChild.toString() +
2706                  "[label=\"" + edge.toGraphEdgeString() +
2707                  "\",decorate];\n");
2708         break;
2709       }
2710
2711       traverseHeapRegionNodes(mode,
2712                               hrnChild,
2713                               bw,
2714                               td,
2715                               visited,
2716                               writeReferencers);
2717     }
2718   }
2719 }