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