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