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