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