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     TempDescriptor returnTemp = fc.getReturnTemp();
1338     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1339
1340       LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1341       clearReferenceEdgesFrom(lnLhsCaller, null, true);
1342
1343       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1344       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1345       while( edgeCalleeItr.hasNext() ) {
1346         ReferenceEdge edgeCallee = edgeCalleeItr.next();
1347
1348         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1349                                                                   null,
1350                                                                   edgeCallee.getFieldDesc(),
1351                                                                   false,
1352                                                                   toShadowTokens(ogCallee, edgeCallee.getBeta() )
1353                                                                   );
1354         rewriteCallerEdgeBeta(fm.numParameters(),
1355                               bogusIndex,
1356                               edgeNewInCallerTemplate,
1357                               paramIndex2rewriteJ,
1358                               paramIndex2rewriteD,
1359                               paramIndex2paramToken,
1360                               paramIndex2paramTokenStar,
1361                               false,
1362                               null);
1363
1364         edgeNewInCallerTemplate.applyBetaNew();
1365
1366
1367         HashSet<HeapRegionNode> assignCallerRhs =
1368           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1369                                               edgeCallee.getDst(),
1370                                               paramIndex2reachableCallerNodes);
1371
1372         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1373         while( itrHrn.hasNext() ) {
1374           HeapRegionNode hrnCaller = itrHrn.next();
1375
1376           if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1377             // prune
1378             continue;
1379           }
1380
1381           // otherwise caller node can match callee edge, so make it
1382           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1383           edgeNewInCaller.setSrc(lnLhsCaller);
1384           edgeNewInCaller.setDst(hrnCaller);
1385
1386           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1387           if( edgeExisting == null ) {
1388
1389             // if this edge doesn't exist in the caller, create it
1390             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1391           } else {
1392             // if it already exists, merge with it
1393             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1394           }
1395         }
1396       }
1397     }
1398
1399
1400     // merge the shadow nodes of allocation sites back down to normal capacity
1401     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1402     while( allocItr.hasNext() ) {
1403       AllocationSite as = allocItr.next();
1404
1405       // first age each allocation site enough times to make room for the shadow nodes
1406       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1407         age(as);
1408       }
1409
1410       // then merge the shadow summary into the normal summary
1411       HeapRegionNode hrnSummary = getSummaryNode(as);
1412       assert hrnSummary != null;
1413
1414       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1415       assert hrnSummaryShadow != null;
1416
1417       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1418
1419       // then clear off after merge
1420       clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1421       clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1422       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1423
1424       // then transplant shadow nodes onto the now clean normal nodes
1425       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1426
1427         Integer idIth = as.getIthOldest(i);
1428         HeapRegionNode hrnIth = id2hrn.get(idIth);
1429
1430         Integer idIthShadow = as.getIthOldestShadow(i);
1431         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1432
1433         transferOnto(hrnIthShadow, hrnIth);
1434
1435         // clear off shadow nodes after transfer
1436         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1437         clearReferenceEdgesTo(hrnIthShadow, null, true);
1438         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1439       }
1440
1441       // finally, globally change shadow tokens into normal tokens
1442       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1443       while( itrAllLabelNodes.hasNext() ) {
1444         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1445         LabelNode ln = (LabelNode) me.getValue();
1446
1447         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1448         while( itrEdges.hasNext() ) {
1449           unshadowTokens(as, itrEdges.next() );
1450         }
1451       }
1452
1453       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1454       while( itrAllHRNodes.hasNext() ) {
1455         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1456         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1457
1458         unshadowTokens(as, hrnToAge);
1459
1460         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1461         while( itrEdges.hasNext() ) {
1462           unshadowTokens(as, itrEdges.next() );
1463         }
1464       }
1465     }
1466   }
1467
1468
1469   protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1470
1471     // if no allocation site, then it's a match-everything region
1472     AllocationSite asSrc = src.getAllocationSite();
1473     if( asSrc == null ) {
1474       return true;
1475     }
1476
1477     TypeDescriptor tdSrc = asSrc.getType();
1478     assert tdSrc != null;
1479
1480     // if it's not a class, it doesn't have any fields to match
1481     if( !tdSrc.isClass() ) {
1482       return false;
1483     }
1484
1485     Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1486     while( fieldsSrcItr.hasNext() ) {
1487       FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1488       if( fd == edge.getFieldDesc() ) {
1489         return true;
1490       }
1491     }
1492
1493     // otherwise it is a class with fields
1494     // but we didn't find a match
1495     return false;
1496   }
1497
1498
1499   protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1500
1501     // if the region has no type, matches everything
1502     AllocationSite asDst = dst.getAllocationSite();
1503     if( asDst == null ) {
1504       return true;
1505     }
1506
1507     TypeDescriptor tdDst = asDst.getType();
1508     assert tdDst != null;
1509
1510     // if the type is not a class don't match because
1511     // primitives are copied, no memory aliases
1512     ClassDescriptor cdDst = tdDst.getClassDesc();
1513     if( cdDst == null ) {
1514       return false;
1515     }
1516
1517     // if the field is null, it matches everything
1518     FieldDescriptor fd = edge.getFieldDesc();
1519     if( fd == null ) {
1520       return true;
1521     }
1522     TypeDescriptor tdFd = fd.getType();
1523     assert tdFd != null;
1524
1525     return typeUtil.isSuperorType(tdFd, tdDst);
1526   }
1527
1528
1529
1530   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1531     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1532   }
1533
1534   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1535     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1536   }
1537
1538
1539   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1540                                          ReachabilitySet rsIn) {
1541
1542     ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1543
1544     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1545     while( allocItr.hasNext() ) {
1546       AllocationSite as = allocItr.next();
1547
1548       rsOut = rsOut.toShadowTokens(as);
1549     }
1550
1551     return rsOut.makeCanonical();
1552   }
1553
1554
1555   private void rewriteCallerNodeAlpha(int numParameters,
1556                                       Integer paramIndex,
1557                                       HeapRegionNode hrn,
1558                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1559                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1560                                       Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1561                                       Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1562
1563     ReachabilitySet rules = paramIndex2rewriteH.get(paramIndex);
1564     assert rules != null;
1565
1566     TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1567     assert tokenToRewrite != null;
1568
1569     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1570     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1571     while( ttsItr.hasNext() ) {
1572       TokenTupleSet tts = ttsItr.next();
1573       r0 = r0.union(tts.rewriteToken(tokenToRewrite,
1574                                      hrn.getAlpha(),
1575                                      false,
1576                                      null) );
1577     }
1578
1579     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1580     ttsItr = r0.iterator();
1581     while( ttsItr.hasNext() ) {
1582       TokenTupleSet tts = ttsItr.next();
1583       r1 = r1.union(rewriteDpass(numParameters,
1584                                  paramIndex,
1585                                  tts,
1586                                  paramIndex2rewriteD,
1587                                  paramIndex2paramToken,
1588                                  paramIndex2paramTokenStar) );
1589     }
1590
1591     hrn.setAlphaNew(hrn.getAlphaNew().union(r1) );
1592   }
1593
1594
1595   private void rewriteCallerEdgeBeta(int numParameters,
1596                                      Integer paramIndex,
1597                                      ReferenceEdge edge,
1598                                      Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1599                                      Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1600                                      Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1601                                      Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1602                                      boolean makeChangeSet,
1603                                      Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1604
1605     ReachabilitySet rules = paramIndex2rewriteJorK.get(paramIndex);
1606     assert rules != null;
1607
1608     TokenTuple tokenToRewrite = paramIndex2paramToken.get(paramIndex);
1609     assert tokenToRewrite != null;
1610
1611     ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1612
1613     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1614     while( ttsItr.hasNext() ) {
1615       TokenTupleSet tts = ttsItr.next();
1616
1617       Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > forChangeSet =
1618         new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1619
1620       ReachabilitySet rTemp = tts.rewriteToken(tokenToRewrite,
1621                                                edge.getBeta(),
1622                                                true,
1623                                                forChangeSet);
1624
1625       Iterator fcsItr = forChangeSet.entrySet().iterator();
1626       while( fcsItr.hasNext() ) {
1627         Map.Entry me = (Map.Entry)fcsItr.next();
1628         TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1629         HashSet<TokenTupleSet> ttsAddSet = (HashSet<TokenTupleSet>) me.getValue();
1630         Iterator<TokenTupleSet> ttsAddItr = ttsAddSet.iterator();
1631         while( ttsAddItr.hasNext() ) {
1632           TokenTupleSet ttsAdd = ttsAddItr.next();
1633
1634           ChangeTuple ct = new ChangeTuple(ttsMatch,
1635                                            ttsAdd
1636                                            ).makeCanonical();
1637
1638           cts0 = cts0.union(ct);
1639         }
1640       }
1641     }
1642
1643
1644     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1645     ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1646
1647     Iterator<ChangeTuple> ctItr = cts0.iterator();
1648     while( ctItr.hasNext() ) {
1649       ChangeTuple ct = ctItr.next();
1650
1651       ReachabilitySet rTemp = rewriteDpass(numParameters,
1652                                            paramIndex,
1653                                            ct.getSetToAdd(),
1654                                            paramIndex2rewriteD,
1655                                            paramIndex2paramToken,
1656                                            paramIndex2paramTokenStar
1657                                            ).makeCanonical();
1658       r1 = r1.union(rTemp);
1659
1660       if( makeChangeSet ) {
1661         assert edgePlannedChanges != null;
1662
1663         Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1664         while( ttsTempItr.hasNext() ) {
1665           TokenTupleSet tts = ttsTempItr.next();
1666
1667           ChangeTuple ctFinal = new ChangeTuple(ct.getSetToMatch(),
1668                                                 tts
1669                                                 ).makeCanonical();
1670
1671           cts1 = cts1.union(ctFinal);
1672         }
1673       }
1674     }
1675
1676     if( makeChangeSet ) {
1677       edgePlannedChanges.put(edge, cts1);
1678     }
1679
1680     edge.setBetaNew(edge.getBetaNew().union(r1) );
1681   }
1682
1683
1684   private ReachabilitySet rewriteDpass(int numParameters,
1685                                        Integer paramIndex,
1686                                        TokenTupleSet ttsIn,
1687                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1688                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1689                                        Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar) {
1690
1691     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1692
1693     boolean rewritten = false;
1694
1695     for( int j = 0; j < numParameters; ++j ) {
1696       Integer paramIndexJ = new Integer(j);
1697       ReachabilitySet D_j = paramIndex2rewriteD.get(paramIndexJ);
1698       assert D_j != null;
1699
1700       if( paramIndexJ != paramIndex ) {
1701         TokenTuple tokenToRewriteJ = paramIndex2paramToken.get(paramIndexJ);
1702         assert tokenToRewriteJ != null;
1703         if( ttsIn.containsTuple(tokenToRewriteJ) ) {
1704           ReachabilitySet r = ttsIn.rewriteToken(tokenToRewriteJ,
1705                                                  D_j,
1706                                                  false,
1707                                                  null);
1708           Iterator<TokenTupleSet> ttsItr = r.iterator();
1709           while( ttsItr.hasNext() ) {
1710             TokenTupleSet tts = ttsItr.next();
1711             rsOut = rsOut.union(rewriteDpass(numParameters,
1712                                              paramIndex,
1713                                              tts,
1714                                              paramIndex2rewriteD,
1715                                              paramIndex2paramToken,
1716                                              paramIndex2paramTokenStar) );
1717             rewritten = true;
1718           }
1719         }
1720       }
1721
1722       TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get(paramIndexJ);
1723       assert tokenStarToRewriteJ != null;
1724       if( ttsIn.containsTuple(tokenStarToRewriteJ) ) {
1725         ReachabilitySet r = ttsIn.rewriteToken(tokenStarToRewriteJ,
1726                                                D_j,
1727                                                false,
1728                                                null);
1729         Iterator<TokenTupleSet> ttsItr = r.iterator();
1730         while( ttsItr.hasNext() ) {
1731           TokenTupleSet tts = ttsItr.next();
1732           rsOut = rsOut.union(rewriteDpass(numParameters,
1733                                            paramIndex,
1734                                            tts,
1735                                            paramIndex2rewriteD,
1736                                            paramIndex2paramToken,
1737                                            paramIndex2paramTokenStar) );
1738           rewritten = true;
1739         }
1740       }
1741     }
1742
1743     if( !rewritten ) {
1744       rsOut = rsOut.union(ttsIn);
1745     }
1746
1747     return rsOut;
1748   }
1749
1750
1751   private HashSet<HeapRegionNode>
1752   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1753                                       HeapRegionNode hrnCallee,
1754                                       Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1755                                       ) {
1756
1757     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1758
1759     Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1760
1761     if( paramIndexCallee == null ) {
1762       // this is a node allocated in the callee then and it has
1763       // exactly one shadow node in the caller to map to
1764       AllocationSite as = hrnCallee.getAllocationSite();
1765       assert as != null;
1766
1767       int age = as.getAgeCategory(hrnCallee.getID() );
1768       assert age != AllocationSite.AGE_notInThisSite;
1769
1770       Integer idCaller;
1771       if( age == AllocationSite.AGE_summary ) {
1772         idCaller = as.getSummaryShadow();
1773       } else if( age == AllocationSite.AGE_oldest ) {
1774         idCaller = as.getOldestShadow();
1775       } else {
1776         assert age == AllocationSite.AGE_in_I;
1777
1778         Integer I = as.getAge(hrnCallee.getID() );
1779         assert I != null;
1780
1781         idCaller = as.getIthOldestShadow(I);
1782       }
1783
1784       assert id2hrn.containsKey(idCaller);
1785       HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1786       possibleCallerHRNs.add(hrnCaller);
1787
1788     } else {
1789       // this is a node that was created to represent a parameter
1790       // so it maps to a whole mess of heap regions
1791       assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1792       possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1793     }
1794
1795     return possibleCallerHRNs;
1796   }
1797
1798
1799
1800   ////////////////////////////////////////////////////
1801   // in merge() and equals() methods the suffix A
1802   // represents the passed in graph and the suffix
1803   // B refers to the graph in this object
1804   // Merging means to take the incoming graph A and
1805   // merge it into B, so after the operation graph B
1806   // is the final result.
1807   ////////////////////////////////////////////////////
1808   public void merge(OwnershipGraph og) {
1809
1810     if( og == null ) {
1811       return;
1812     }
1813
1814     mergeOwnershipNodes(og);
1815     mergeReferenceEdges(og);
1816     mergeId2paramIndex(og);
1817     mergeAllocationSites(og);
1818   }
1819
1820
1821   protected void mergeOwnershipNodes(OwnershipGraph og) {
1822     Set sA = og.id2hrn.entrySet();
1823     Iterator iA = sA.iterator();
1824     while( iA.hasNext() ) {
1825       Map.Entry meA  = (Map.Entry)iA.next();
1826       Integer idA  = (Integer)        meA.getKey();
1827       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1828
1829       // if this graph doesn't have a node the
1830       // incoming graph has, allocate it
1831       if( !id2hrn.containsKey(idA) ) {
1832         HeapRegionNode hrnB = hrnA.copy();
1833         id2hrn.put(idA, hrnB);
1834
1835       } else {
1836         // otherwise this is a node present in both graphs
1837         // so make the new reachability set a union of the
1838         // nodes' reachability sets
1839         HeapRegionNode hrnB = id2hrn.get(idA);
1840         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1841       }
1842     }
1843
1844     // now add any label nodes that are in graph B but
1845     // not in A
1846     sA = og.td2ln.entrySet();
1847     iA = sA.iterator();
1848     while( iA.hasNext() ) {
1849       Map.Entry meA = (Map.Entry)iA.next();
1850       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1851       LabelNode lnA = (LabelNode)      meA.getValue();
1852
1853       // if the label doesn't exist in B, allocate and add it
1854       LabelNode lnB = getLabelNodeFromTemp(tdA);
1855     }
1856   }
1857
1858   protected void mergeReferenceEdges(OwnershipGraph og) {
1859
1860     // heap regions
1861     Set sA = og.id2hrn.entrySet();
1862     Iterator iA = sA.iterator();
1863     while( iA.hasNext() ) {
1864       Map.Entry meA  = (Map.Entry)iA.next();
1865       Integer idA  = (Integer)        meA.getKey();
1866       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1867
1868       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1869       while( heapRegionsItrA.hasNext() ) {
1870         ReferenceEdge edgeA     = heapRegionsItrA.next();
1871         HeapRegionNode hrnChildA = edgeA.getDst();
1872         Integer idChildA  = hrnChildA.getID();
1873
1874         // at this point we know an edge in graph A exists
1875         // idA -> idChildA, does this exist in B?
1876         assert id2hrn.containsKey(idA);
1877         HeapRegionNode hrnB        = id2hrn.get(idA);
1878         ReferenceEdge edgeToMerge = null;
1879
1880         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1881         while( heapRegionsItrB.hasNext() &&
1882                edgeToMerge == null          ) {
1883
1884           ReferenceEdge edgeB     = heapRegionsItrB.next();
1885           HeapRegionNode hrnChildB = edgeB.getDst();
1886           Integer idChildB  = hrnChildB.getID();
1887
1888           // don't use the ReferenceEdge.equals() here because
1889           // we're talking about existence between graphs
1890           if( idChildB.equals(idChildA) &&
1891               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1892             edgeToMerge = edgeB;
1893           }
1894         }
1895
1896         // if the edge from A was not found in B,
1897         // add it to B.
1898         if( edgeToMerge == null ) {
1899           assert id2hrn.containsKey(idChildA);
1900           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1901           edgeToMerge = edgeA.copy();
1902           edgeToMerge.setSrc(hrnB);
1903           edgeToMerge.setDst(hrnChildB);
1904           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1905         }
1906         // otherwise, the edge already existed in both graphs
1907         // so merge their reachability sets
1908         else {
1909           // just replace this beta set with the union
1910           assert edgeToMerge != null;
1911           edgeToMerge.setBeta(
1912             edgeToMerge.getBeta().union(edgeA.getBeta() )
1913             );
1914           if( !edgeA.isInitialParamReflexive() ) {
1915             edgeToMerge.setIsInitialParamReflexive(false);
1916           }
1917         }
1918       }
1919     }
1920
1921     // and then again with label nodes
1922     sA = og.td2ln.entrySet();
1923     iA = sA.iterator();
1924     while( iA.hasNext() ) {
1925       Map.Entry meA = (Map.Entry)iA.next();
1926       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1927       LabelNode lnA = (LabelNode)      meA.getValue();
1928
1929       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1930       while( heapRegionsItrA.hasNext() ) {
1931         ReferenceEdge edgeA     = heapRegionsItrA.next();
1932         HeapRegionNode hrnChildA = edgeA.getDst();
1933         Integer idChildA  = hrnChildA.getID();
1934
1935         // at this point we know an edge in graph A exists
1936         // tdA -> idChildA, does this exist in B?
1937         assert td2ln.containsKey(tdA);
1938         LabelNode lnB         = td2ln.get(tdA);
1939         ReferenceEdge edgeToMerge = null;
1940
1941         // labels never have edges with a field
1942         //assert edgeA.getFieldDesc() == null;
1943
1944         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1945         while( heapRegionsItrB.hasNext() &&
1946                edgeToMerge == null          ) {
1947
1948           ReferenceEdge edgeB     = heapRegionsItrB.next();
1949           HeapRegionNode hrnChildB = edgeB.getDst();
1950           Integer idChildB  = hrnChildB.getID();
1951
1952           // labels never have edges with a field
1953           //assert edgeB.getFieldDesc() == null;
1954
1955           // don't use the ReferenceEdge.equals() here because
1956           // we're talking about existence between graphs
1957           if( idChildB.equals(idChildA) &&
1958               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1959             edgeToMerge = edgeB;
1960           }
1961         }
1962
1963         // if the edge from A was not found in B,
1964         // add it to B.
1965         if( edgeToMerge == null ) {
1966           assert id2hrn.containsKey(idChildA);
1967           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1968           edgeToMerge = edgeA.copy();
1969           edgeToMerge.setSrc(lnB);
1970           edgeToMerge.setDst(hrnChildB);
1971           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1972         }
1973         // otherwise, the edge already existed in both graphs
1974         // so merge their reachability sets
1975         else {
1976           // just replace this beta set with the union
1977           edgeToMerge.setBeta(
1978             edgeToMerge.getBeta().union(edgeA.getBeta() )
1979             );
1980           if( !edgeA.isInitialParamReflexive() ) {
1981             edgeToMerge.setIsInitialParamReflexive(false);
1982           }
1983         }
1984       }
1985     }
1986   }
1987
1988   // you should only merge ownership graphs that have the
1989   // same number of parameters, or if one or both parameter
1990   // index tables are empty
1991   protected void mergeId2paramIndex(OwnershipGraph og) {
1992     if( id2paramIndex.size() == 0 ) {
1993       id2paramIndex  = og.id2paramIndex;
1994       paramIndex2id  = og.paramIndex2id;
1995       paramIndex2tdQ = og.paramIndex2tdQ;
1996       return;
1997     }
1998
1999     if( og.id2paramIndex.size() == 0 ) {
2000       return;
2001     }
2002
2003     assert id2paramIndex.size() == og.id2paramIndex.size();
2004   }
2005
2006   protected void mergeAllocationSites(OwnershipGraph og) {
2007     allocationSites.addAll(og.allocationSites);
2008   }
2009
2010
2011
2012   // it is necessary in the equals() member functions
2013   // to "check both ways" when comparing the data
2014   // structures of two graphs.  For instance, if all
2015   // edges between heap region nodes in graph A are
2016   // present and equal in graph B it is not sufficient
2017   // to say the graphs are equal.  Consider that there
2018   // may be edges in graph B that are not in graph A.
2019   // the only way to know that all edges in both graphs
2020   // are equally present is to iterate over both data
2021   // structures and compare against the other graph.
2022   public boolean equals(OwnershipGraph og) {
2023
2024     if( og == null ) {
2025       return false;
2026     }
2027
2028     if( !areHeapRegionNodesEqual(og) ) {
2029       return false;
2030     }
2031
2032     if( !areLabelNodesEqual(og) ) {
2033       return false;
2034     }
2035
2036     if( !areReferenceEdgesEqual(og) ) {
2037       return false;
2038     }
2039
2040     if( !areId2paramIndexEqual(og) ) {
2041       return false;
2042     }
2043
2044     // if everything is equal up to this point,
2045     // assert that allocationSites is also equal--
2046     // this data is redundant and kept for efficiency
2047     assert allocationSites.equals(og.allocationSites);
2048
2049     return true;
2050   }
2051
2052   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2053
2054     if( !areallHRNinAalsoinBandequal(this, og) ) {
2055       return false;
2056     }
2057
2058     if( !areallHRNinAalsoinBandequal(og, this) ) {
2059       return false;
2060     }
2061
2062     return true;
2063   }
2064
2065   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2066                                                        OwnershipGraph ogB) {
2067     Set sA = ogA.id2hrn.entrySet();
2068     Iterator iA = sA.iterator();
2069     while( iA.hasNext() ) {
2070       Map.Entry meA  = (Map.Entry)iA.next();
2071       Integer idA  = (Integer)        meA.getKey();
2072       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2073
2074       if( !ogB.id2hrn.containsKey(idA) ) {
2075         return false;
2076       }
2077
2078       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2079       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2080         return false;
2081       }
2082     }
2083
2084     return true;
2085   }
2086
2087
2088   protected boolean areLabelNodesEqual(OwnershipGraph og) {
2089
2090     if( !areallLNinAalsoinBandequal(this, og) ) {
2091       return false;
2092     }
2093
2094     if( !areallLNinAalsoinBandequal(og, this) ) {
2095       return false;
2096     }
2097
2098     return true;
2099   }
2100
2101   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2102                                                       OwnershipGraph ogB) {
2103     Set sA = ogA.td2ln.entrySet();
2104     Iterator iA = sA.iterator();
2105     while( iA.hasNext() ) {
2106       Map.Entry meA = (Map.Entry)iA.next();
2107       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2108
2109       if( !ogB.td2ln.containsKey(tdA) ) {
2110         return false;
2111       }
2112     }
2113
2114     return true;
2115   }
2116
2117
2118   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2119     if( !areallREinAandBequal(this, og) ) {
2120       return false;
2121     }
2122
2123     return true;
2124   }
2125
2126   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2127                                                 OwnershipGraph ogB) {
2128
2129     // check all the heap region->heap region edges
2130     Set sA = ogA.id2hrn.entrySet();
2131     Iterator iA = sA.iterator();
2132     while( iA.hasNext() ) {
2133       Map.Entry meA  = (Map.Entry)iA.next();
2134       Integer idA  = (Integer)        meA.getKey();
2135       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2136
2137       // we should have already checked that the same
2138       // heap regions exist in both graphs
2139       assert ogB.id2hrn.containsKey(idA);
2140
2141       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2142         return false;
2143       }
2144
2145       // then check every edge in B for presence in A, starting
2146       // from the same parent HeapRegionNode
2147       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2148
2149       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2150         return false;
2151       }
2152     }
2153
2154     // then check all the label->heap region edges
2155     sA = ogA.td2ln.entrySet();
2156     iA = sA.iterator();
2157     while( iA.hasNext() ) {
2158       Map.Entry meA = (Map.Entry)iA.next();
2159       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2160       LabelNode lnA = (LabelNode)      meA.getValue();
2161
2162       // we should have already checked that the same
2163       // label nodes exist in both graphs
2164       assert ogB.td2ln.containsKey(tdA);
2165
2166       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2167         return false;
2168       }
2169
2170       // then check every edge in B for presence in A, starting
2171       // from the same parent LabelNode
2172       LabelNode lnB = ogB.td2ln.get(tdA);
2173
2174       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2175         return false;
2176       }
2177     }
2178
2179     return true;
2180   }
2181
2182
2183   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2184                                                  OwnershipNode onA,
2185                                                  OwnershipGraph ogB) {
2186
2187     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2188     while( itrA.hasNext() ) {
2189       ReferenceEdge edgeA     = itrA.next();
2190       HeapRegionNode hrnChildA = edgeA.getDst();
2191       Integer idChildA  = hrnChildA.getID();
2192
2193       assert ogB.id2hrn.containsKey(idChildA);
2194
2195       // at this point we know an edge in graph A exists
2196       // onA -> idChildA, does this exact edge exist in B?
2197       boolean edgeFound = false;
2198
2199       OwnershipNode onB = null;
2200       if( onA instanceof HeapRegionNode ) {
2201         HeapRegionNode hrnA = (HeapRegionNode) onA;
2202         onB = ogB.id2hrn.get(hrnA.getID() );
2203       } else {
2204         LabelNode lnA = (LabelNode) onA;
2205         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2206       }
2207
2208       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2209       while( itrB.hasNext() ) {
2210         ReferenceEdge edgeB     = itrB.next();
2211         HeapRegionNode hrnChildB = edgeB.getDst();
2212         Integer idChildB  = hrnChildB.getID();
2213
2214         if( idChildA.equals(idChildB) &&
2215             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2216
2217           // there is an edge in the right place with the right field,
2218           // but do they have the same attributes?
2219           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2220
2221             edgeFound = true;
2222             //} else {
2223             //return false;
2224           }
2225         }
2226       }
2227
2228       if( !edgeFound ) {
2229         return false;
2230       }
2231     }
2232
2233     return true;
2234   }
2235
2236
2237   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2238     return id2paramIndex.size() == og.id2paramIndex.size();
2239   }
2240
2241
2242   public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2243
2244     // get parameter's heap region
2245     assert paramIndex2id.containsKey(paramIndex1);
2246     Integer idParam1 = paramIndex2id.get(paramIndex1);
2247
2248     assert id2hrn.containsKey(idParam1);
2249     HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2250     assert hrnParam1 != null;
2251
2252     // get tokens for this parameter
2253     TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2254                                    true,
2255                                    TokenTuple.ARITY_ONE).makeCanonical();
2256
2257     TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2258                                        true,
2259                                        TokenTuple.ARITY_MANY).makeCanonical();
2260
2261
2262     // get tokens for the other parameter
2263     assert paramIndex2id.containsKey(paramIndex2);
2264     Integer idParam2 = paramIndex2id.get(paramIndex2);
2265
2266     assert id2hrn.containsKey(idParam2);
2267     HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2268     assert hrnParam2 != null;
2269
2270     TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2271                                    true,
2272                                    TokenTuple.ARITY_ONE).makeCanonical();
2273
2274     TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2275                                        true,
2276                                        TokenTuple.ARITY_MANY).makeCanonical();
2277
2278
2279     // get special label p_q for first parameter
2280     TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2281     assert tdParamQ1 != null;
2282     LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2283     assert lnParamQ1 != null;
2284
2285     // then get the edge from label q to parameter's hrn
2286     ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2287     assert edgeSpecialQ1 != null;
2288
2289     // if the beta of this edge has tokens from both parameters in one
2290     // token tuple set, then there is a potential alias between them
2291     ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2292     assert beta1 != null;
2293
2294     if( beta1.containsTupleSetWithBoth(p1,     p2) ) {
2295       return true;
2296     }
2297     if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2298       return true;
2299     }
2300     if( beta1.containsTupleSetWithBoth(p1,     pStar2) ) {
2301       return true;
2302     }
2303     if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2304       return true;
2305     }
2306
2307     return false;
2308   }
2309
2310
2311   public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2312
2313     // get parameter's heap region
2314     assert paramIndex2id.containsKey(paramIndex);
2315     Integer idParam = paramIndex2id.get(paramIndex);
2316
2317     assert id2hrn.containsKey(idParam);
2318     HeapRegionNode hrnParam = id2hrn.get(idParam);
2319     assert hrnParam != null;
2320
2321     // get tokens for this parameter
2322     TokenTuple p = new TokenTuple(hrnParam.getID(),
2323                                   true,
2324                                   TokenTuple.ARITY_ONE).makeCanonical();
2325
2326     TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2327                                       true,
2328                                       TokenTuple.ARITY_MANY).makeCanonical();
2329
2330     // get special label p_q
2331     TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2332     assert tdParamQ != null;
2333     LabelNode lnParamQ = td2ln.get(tdParamQ);
2334     assert lnParamQ != null;
2335
2336     // then get the edge from label q to parameter's hrn
2337     ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2338     assert edgeSpecialQ != null;
2339
2340     // look through this beta set for potential aliases
2341     ReachabilitySet beta = edgeSpecialQ.getBeta();
2342     assert beta != null;
2343
2344
2345     // get tokens for summary node
2346     TokenTuple gs = new TokenTuple(as.getSummary(),
2347                                    true,
2348                                    TokenTuple.ARITY_ONE).makeCanonical();
2349
2350     TokenTuple gsStar = new TokenTuple(as.getSummary(),
2351                                        true,
2352                                        TokenTuple.ARITY_MANY).makeCanonical();
2353
2354     if( beta.containsTupleSetWithBoth(p,     gs) ) {
2355       return true;
2356     }
2357     if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2358       return true;
2359     }
2360     if( beta.containsTupleSetWithBoth(p,     gsStar) ) {
2361       return true;
2362     }
2363     if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2364       return true;
2365     }
2366
2367     // check for other nodes
2368     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2369
2370       // the other nodes of an allocation site are single, no stars
2371       TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2372                                      false,
2373                                      TokenTuple.ARITY_ONE).makeCanonical();
2374
2375       if( beta.containsTupleSetWithBoth(p,     gi) ) {
2376         return true;
2377       }
2378       if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2379         return true;
2380       }
2381     }
2382
2383     return false;
2384   }
2385
2386
2387   public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2388
2389     // get tokens for summary nodes
2390     TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2391                                     true,
2392                                     TokenTuple.ARITY_ONE).makeCanonical();
2393
2394     TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2395                                         true,
2396                                         TokenTuple.ARITY_MANY).makeCanonical();
2397
2398     // get summary node's alpha
2399     Integer idSum1 = as1.getSummary();
2400     assert id2hrn.containsKey(idSum1);
2401     HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2402     assert hrnSum1 != null;
2403     ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2404     assert alphaSum1 != null;
2405
2406
2407     // and for the other one
2408     TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2409                                     true,
2410                                     TokenTuple.ARITY_ONE).makeCanonical();
2411
2412     TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2413                                         true,
2414                                         TokenTuple.ARITY_MANY).makeCanonical();
2415
2416     // get summary node's alpha
2417     Integer idSum2 = as2.getSummary();
2418     assert id2hrn.containsKey(idSum2);
2419     HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2420     assert hrnSum2 != null;
2421     ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2422     assert alphaSum2 != null;
2423
2424     // does either one report reachability from the other tokens?
2425     if( alphaSum1.containsTuple(gsStar2) ) {
2426       return true;
2427     }
2428     if( alphaSum2.containsTuple(gsStar1) ) {
2429       return true;
2430     }
2431
2432     // only check non-star token if they are different sites
2433     if( as1 != as2 ) {
2434       if( alphaSum1.containsTuple(gs2) ) {
2435         return true;
2436       }
2437       if( alphaSum2.containsTuple(gs1) ) {
2438         return true;
2439       }
2440     }
2441
2442
2443     // check sum2 against alloc1 nodes
2444     for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2445       Integer idI1 = as1.getIthOldest(i);
2446       assert id2hrn.containsKey(idI1);
2447       HeapRegionNode hrnI1 = id2hrn.get(idI1);
2448       assert hrnI1 != null;
2449       ReachabilitySet alphaI1 = hrnI1.getAlpha();
2450       assert alphaI1 != null;
2451
2452       // the other nodes of an allocation site are single, no stars
2453       TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2454                                       false,
2455                                       TokenTuple.ARITY_ONE).makeCanonical();
2456
2457       if( alphaSum2.containsTuple(gi1) ) {
2458         return true;
2459       }
2460       if( alphaI1.containsTuple(gs2) ) {
2461         return true;
2462       }
2463       if( alphaI1.containsTuple(gsStar2) ) {
2464         return true;
2465       }
2466     }
2467
2468     // check sum1 against alloc2 nodes
2469     for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2470       Integer idI2 = as2.getIthOldest(i);
2471       assert id2hrn.containsKey(idI2);
2472       HeapRegionNode hrnI2 = id2hrn.get(idI2);
2473       assert hrnI2 != null;
2474       ReachabilitySet alphaI2 = hrnI2.getAlpha();
2475       assert alphaI2 != null;
2476
2477       TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2478                                       false,
2479                                       TokenTuple.ARITY_ONE).makeCanonical();
2480
2481       if( alphaSum1.containsTuple(gi2) ) {
2482         return true;
2483       }
2484       if( alphaI2.containsTuple(gs1) ) {
2485         return true;
2486       }
2487       if( alphaI2.containsTuple(gsStar1) ) {
2488         return true;
2489       }
2490
2491       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2492       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2493         Integer idI1 = as1.getIthOldest(j);
2494
2495         // if these are the same site, don't look for the same token, no alias
2496         // different tokens of the same site could alias together though
2497         if( idI1 == idI2 ) {
2498           continue;
2499         }
2500
2501         HeapRegionNode hrnI1 = id2hrn.get(idI1);
2502         ReachabilitySet alphaI1 = hrnI1.getAlpha();
2503         TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2504                                         false,
2505                                         TokenTuple.ARITY_ONE).makeCanonical();
2506         if( alphaI2.containsTuple(gi1) ) {
2507           return true;
2508         }
2509         if( alphaI1.containsTuple(gi2) ) {
2510           return true;
2511         }
2512       }
2513     }
2514
2515     return false;
2516   }
2517
2518
2519   // for writing ownership graphs to dot files
2520   public void writeGraph(Descriptor methodDesc,
2521                          FlatNode fn,
2522                          boolean writeLabels,
2523                          boolean labelSelect,
2524                          boolean pruneGarbage,
2525                          boolean writeReferencers,
2526                          boolean writeParamMappings
2527                          ) throws java.io.IOException {
2528     writeGraph(
2529       methodDesc.getSymbol() +
2530       methodDesc.getNum() +
2531       fn.toString(),
2532       writeLabels,
2533       labelSelect,
2534       pruneGarbage,
2535       writeReferencers,
2536       writeParamMappings
2537       );
2538   }
2539
2540   public void writeGraph(Descriptor methodDesc,
2541                          boolean writeLabels,
2542                          boolean labelSelect,
2543                          boolean pruneGarbage,
2544                          boolean writeReferencers,
2545                          boolean writeParamMappings
2546                          ) throws java.io.IOException {
2547
2548     writeGraph(methodDesc+"COMPLETE",
2549                writeLabels,
2550                labelSelect,
2551                pruneGarbage,
2552                writeReferencers,
2553                writeParamMappings
2554                );
2555   }
2556
2557   public void writeGraph(Descriptor methodDesc,
2558                          Integer numUpdate,
2559                          boolean writeLabels,
2560                          boolean labelSelect,
2561                          boolean pruneGarbage,
2562                          boolean writeReferencers,
2563                          boolean writeParamMappings
2564                          ) throws java.io.IOException {
2565
2566     writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2567                writeLabels,
2568                labelSelect,
2569                pruneGarbage,
2570                writeReferencers,
2571                writeParamMappings
2572                );
2573   }
2574
2575   public void writeGraph(String graphName,
2576                          boolean writeLabels,
2577                          boolean labelSelect,
2578                          boolean pruneGarbage,
2579                          boolean writeReferencers,
2580                          boolean writeParamMappings
2581                          ) throws java.io.IOException {
2582
2583     // remove all non-word characters from the graph name so
2584     // the filename and identifier in dot don't cause errors
2585     graphName = graphName.replaceAll("[\\W]", "");
2586
2587     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2588     bw.write("digraph "+graphName+" {\n");
2589
2590     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2591
2592     // then visit every heap region node
2593     if( !pruneGarbage ) {
2594       Set s = id2hrn.entrySet();
2595       Iterator i = s.iterator();
2596       while( i.hasNext() ) {
2597         Map.Entry me  = (Map.Entry)i.next();
2598         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2599         if( !visited.contains(hrn) ) {
2600           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2601                                   hrn,
2602                                   bw,
2603                                   null,
2604                                   visited,
2605                                   writeReferencers);
2606         }
2607       }
2608     }
2609
2610     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2611
2612     if( writeParamMappings ) {
2613       Set df = paramIndex2id.entrySet();
2614       Iterator ih = df.iterator();
2615       while( ih.hasNext() ) {
2616         Map.Entry meh = (Map.Entry)ih.next();
2617         Integer pi = (Integer) meh.getKey();
2618         Integer id = (Integer) meh.getValue();
2619         bw.write("  pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2620       }
2621     }
2622
2623     // then visit every label node, useful for debugging
2624     if( writeLabels ) {
2625       Set s = td2ln.entrySet();
2626       Iterator i = s.iterator();
2627       while( i.hasNext() ) {
2628         Map.Entry me = (Map.Entry)i.next();
2629         LabelNode ln = (LabelNode) me.getValue();
2630
2631         if( labelSelect ) {
2632           String labelStr = ln.getTempDescriptorString();
2633           if( labelStr.startsWith("___temp") ||
2634               labelStr.startsWith("___dst") ||
2635               labelStr.startsWith("___srctmp") ||
2636               labelStr.startsWith("___neverused")   ) {
2637             continue;
2638           }
2639         }
2640
2641         bw.write(ln.toString() + ";\n");
2642
2643         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2644         while( heapRegionsItr.hasNext() ) {
2645           ReferenceEdge edge = heapRegionsItr.next();
2646           HeapRegionNode hrn  = edge.getDst();
2647
2648           if( pruneGarbage && !visited.contains(hrn) ) {
2649             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2650                                     hrn,
2651                                     bw,
2652                                     null,
2653                                     visited,
2654                                     writeReferencers);
2655           }
2656
2657           bw.write("  "        + ln.toString() +
2658                    " -> "      + hrn.toString() +
2659                    "[label=\"" + edge.toGraphEdgeString() +
2660                    "\",decorate];\n");
2661         }
2662       }
2663     }
2664
2665
2666     bw.write("}\n");
2667     bw.close();
2668   }
2669
2670   protected void traverseHeapRegionNodes(int mode,
2671                                          HeapRegionNode hrn,
2672                                          BufferedWriter bw,
2673                                          TempDescriptor td,
2674                                          HashSet<HeapRegionNode> visited,
2675                                          boolean writeReferencers
2676                                          ) throws java.io.IOException {
2677
2678     if( visited.contains(hrn) ) {
2679       return;
2680     }
2681     visited.add(hrn);
2682
2683     switch( mode ) {
2684     case VISIT_HRN_WRITE_FULL:
2685
2686       String attributes = "[";
2687
2688       if( hrn.isSingleObject() ) {
2689         attributes += "shape=box";
2690       } else {
2691         attributes += "shape=Msquare";
2692       }
2693
2694       if( hrn.isFlagged() ) {
2695         attributes += ",style=filled,fillcolor=lightgrey";
2696       }
2697
2698       attributes += ",label=\"ID"        +
2699                     hrn.getID()          +
2700                     "\\n"                +
2701                     hrn.getDescription() +
2702                     "\\n"                +
2703                     hrn.getAlphaString() +
2704                     "\"]";
2705
2706       bw.write("  " + hrn.toString() + attributes + ";\n");
2707       break;
2708     }
2709
2710
2711     // useful for debugging
2712     if( writeReferencers ) {
2713       OwnershipNode onRef  = null;
2714       Iterator refItr = hrn.iteratorToReferencers();
2715       while( refItr.hasNext() ) {
2716         onRef = (OwnershipNode) refItr.next();
2717
2718         switch( mode ) {
2719         case VISIT_HRN_WRITE_FULL:
2720           bw.write("  "                    + hrn.toString() +
2721                    " -> "                  + onRef.toString() +
2722                    "[color=lightgray];\n");
2723           break;
2724         }
2725       }
2726     }
2727
2728     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2729     while( childRegionsItr.hasNext() ) {
2730       ReferenceEdge edge     = childRegionsItr.next();
2731       HeapRegionNode hrnChild = edge.getDst();
2732
2733       switch( mode ) {
2734       case VISIT_HRN_WRITE_FULL:
2735         bw.write("  "        + hrn.toString() +
2736                  " -> "      + hrnChild.toString() +
2737                  "[label=\"" + edge.toGraphEdgeString() +
2738                  "\",decorate];\n");
2739         break;
2740       }
2741
2742       traverseHeapRegionNodes(mode,
2743                               hrnChild,
2744                               bw,
2745                               td,
2746                               visited,
2747                               writeReferencers);
2748     }
2749   }
2750 }