Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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