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