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   protected static final int bogusParamIndexInt = -2;
  23
  24
  25   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  26   public Hashtable<TempDescriptor, LabelNode     > td2ln;
  27   public Hashtable<Integer,        Set<Integer>  > id2paramIndexSet;
  28   public Hashtable<Integer,        Integer       > paramIndex2id;
  29   public Hashtable<Integer,        TempDescriptor> paramIndex2tdQ;
  30
  31   public HashSet<AllocationSite> allocationSites;
  32
  33
  34
  35
  36   public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
  37     this.allocationDepth = allocationDepth;
  38     this.typeUtil        = typeUtil;
  39
  40     id2hrn           = new Hashtable<Integer,        HeapRegionNode>();
  41     td2ln            = new Hashtable<TempDescriptor, LabelNode     >();
  42     id2paramIndexSet = new Hashtable<Integer,        Set<Integer>  >();
  43     paramIndex2id    = new Hashtable<Integer,        Integer       >();
  44     paramIndex2tdQ   = new Hashtable<Integer,        TempDescriptor>();
  45
  46     allocationSites = new HashSet <AllocationSite>();
  47   }
  48
  49
  50   // label nodes are much easier to deal with than
  51   // heap region nodes.  Whenever there is a request
  52   // for the label node that is associated with a
  53   // temp descriptor we can either find it or make a
  54   // new one and return it.  This is because temp
  55   // descriptors are globally unique and every label
  56   // node is mapped to exactly one temp descriptor.
  57   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  58     assert td != null;
  59
  60     if( !td2ln.containsKey(td) ) {
  61       td2ln.put(td, new LabelNode(td) );
  62     }
  63
  64     return td2ln.get(td);
  65   }
  66
  67
  68   // the reason for this method is to have the option
  69   // creating new heap regions with specific IDs, or
  70   // duplicating heap regions with specific IDs (especially
  71   // in the merge() operation) or to create new heap
  72   // regions with a new unique ID.
  73   protected HeapRegionNode
  74   createNewHeapRegionNode(Integer id,
  75                           boolean isSingleObject,
  76                           boolean isFlagged,
  77                           boolean isNewSummary,
  78                           boolean isParameter,
  79                           AllocationSite allocSite,
  80                           ReachabilitySet alpha,
  81                           String description) {
  82
  83     if( id == null ) {
  84       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  85     }
  86
  87     if( alpha == null ) {
  88       if( isFlagged || isParameter ) {
  89         alpha = new ReachabilitySet(
  90           new TokenTuple(id,
  91                          !isSingleObject,
  92                          TokenTuple.ARITY_ONE
  93                          ).makeCanonical()
  94           ).makeCanonical();
  95       } else {
  96         alpha = new ReachabilitySet(
  97           new TokenTupleSet().makeCanonical()
  98           ).makeCanonical();
  99       }
 100     }
 101
 102     HeapRegionNode hrn = new HeapRegionNode(id,
 103                                             isSingleObject,
 104                                             isFlagged,
 105                                             isParameter,
 106                                             isNewSummary,
 107                                             allocSite,
 108                                             alpha,
 109                                             description);
 110     id2hrn.put(id, hrn);
 111     return hrn;
 112   }
 113
 114
 115
 116   ////////////////////////////////////////////////
 117   //
 118   //  Low-level referencee and referencer methods
 119   //
 120   //  These methods provide the lowest level for
 121   //  creating references between ownership nodes
 122   //  and handling the details of maintaining both
 123   //  list of referencers and referencees.
 124   //
 125   ////////////////////////////////////////////////
 126   protected void addReferenceEdge(OwnershipNode referencer,
 127                                   HeapRegionNode referencee,
 128                                   ReferenceEdge edge) {
 129     assert referencer != null;
 130     assert referencee != null;
 131     assert edge       != null;
 132     assert edge.getSrc() == referencer;
 133     assert edge.getDst() == referencee;
 134
 135     referencer.addReferencee(edge);
 136     referencee.addReferencer(edge);
 137   }
 138
 139   protected void removeReferenceEdge(OwnershipNode referencer,
 140                                      HeapRegionNode referencee,
 141                                      FieldDescriptor fieldDesc) {
 142     assert referencer != null;
 143     assert referencee != null;
 144
 145     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 146                                                    fieldDesc);
 147     assert edge != null;
 148     assert edge == referencee.getReferenceFrom(referencer,
 149                                                fieldDesc);
 150
 151     referencer.removeReferencee(edge);
 152     referencee.removeReferencer(edge);
 153   }
 154
 155   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 156                                          FieldDescriptor fieldDesc,
 157                                          boolean removeAll) {
 158     assert referencer != null;
 159
 160     // get a copy of the set to iterate over, otherwise
 161     // we will be trying to take apart the set as we
 162     // are iterating over it, which won't work
 163     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 164     while( i.hasNext() ) {
 165       ReferenceEdge edge = i.next();
 166
 167       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 168         HeapRegionNode referencee = edge.getDst();
 169
 170         removeReferenceEdge(referencer,
 171                             referencee,
 172                             edge.getFieldDesc() );
 173       }
 174     }
 175   }
 176
 177   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 178                                        FieldDescriptor fieldDesc,
 179                                        boolean removeAll) {
 180     assert referencee != null;
 181
 182     // get a copy of the set to iterate over, otherwise
 183     // we will be trying to take apart the set as we
 184     // are iterating over it, which won't work
 185     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 186     while( i.hasNext() ) {
 187       ReferenceEdge edge = i.next();
 188
 189       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 190         OwnershipNode referencer = edge.getSrc();
 191         removeReferenceEdge(referencer,
 192                             referencee,
 193                             edge.getFieldDesc() );
 194       }
 195     }
 196   }
 197
 198
 199   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
 200                                           ChangeTupleSet c0,
 201                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
 202                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
 203
 204     HashSet<HeapRegionNode> todoNodes
 205     = new HashSet<HeapRegionNode>();
 206     todoNodes.add(nPrime);
 207
 208     HashSet<ReferenceEdge> todoEdges
 209     = new HashSet<ReferenceEdge>();
 210
 211     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 212     = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 213     nodePlannedChanges.put(nPrime, c0);
 214
 215     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
 216     = new Hashtable<ReferenceEdge, ChangeTupleSet>();
 217
 218
 219     while( !todoNodes.isEmpty() ) {
 220       HeapRegionNode n = todoNodes.iterator().next();
 221       ChangeTupleSet C = nodePlannedChanges.get(n);
 222
 223       Iterator itrC = C.iterator();
 224       while( itrC.hasNext() ) {
 225         ChangeTuple c = (ChangeTuple) itrC.next();
 226
 227         if( n.getAlpha().contains(c.getSetToMatch() ) ) {
 228           ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
 229           n.setAlphaNew(n.getAlphaNew().union(withChange) );
 230           nodesWithNewAlpha.add(n);
 231         }
 232       }
 233
 234       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 235       while( referItr.hasNext() ) {
 236         ReferenceEdge edge = referItr.next();
 237         todoEdges.add(edge);
 238
 239         if( !edgePlannedChanges.containsKey(edge) ) {
 240           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
 241         }
 242
 243         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 244       }
 245
 246       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
 247       while( refeeItr.hasNext() ) {
 248         ReferenceEdge edgeF = refeeItr.next();
 249         HeapRegionNode m     = edgeF.getDst();
 250
 251         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 252
 253         Iterator<ChangeTuple> itrCprime = C.iterator();
 254         while( itrCprime.hasNext() ) {
 255           ChangeTuple c = itrCprime.next();
 256           if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
 257             changesToPass = changesToPass.union(c);
 258           }
 259         }
 260
 261         if( !changesToPass.isEmpty() ) {
 262           if( !nodePlannedChanges.containsKey(m) ) {
 263             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
 264           }
 265
 266           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
 267
 268           if( !changesToPass.isSubset(currentChanges) ) {
 269
 270             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 271             todoNodes.add(m);
 272           }
 273         }
 274       }
 275
 276       todoNodes.remove(n);
 277     }
 278
 279     propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
 280   }
 281
 282
 283   protected void propagateTokensOverEdges(
 284     HashSet<ReferenceEdge>                   todoEdges,
 285     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
 286     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
 287
 288
 289     while( !todoEdges.isEmpty() ) {
 290       ReferenceEdge edgeE = todoEdges.iterator().next();
 291       todoEdges.remove(edgeE);
 292
 293       if( !edgePlannedChanges.containsKey(edgeE) ) {
 294         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
 295       }
 296
 297       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
 298
 299       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 300
 301       Iterator<ChangeTuple> itrC = C.iterator();
 302       while( itrC.hasNext() ) {
 303         ChangeTuple c = itrC.next();
 304         if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
 305           ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
 306           edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
 307           edgesWithNewBeta.add(edgeE);
 308           changesToPass = changesToPass.union(c);
 309         }
 310       }
 311
 312       OwnershipNode onSrc = edgeE.getSrc();
 313
 314       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 315         HeapRegionNode n = (HeapRegionNode) onSrc;
 316
 317         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 318         while( referItr.hasNext() ) {
 319           ReferenceEdge edgeF = referItr.next();
 320
 321           if( !edgePlannedChanges.containsKey(edgeF) ) {
 322             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
 323           }
 324
 325           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
 326
 327           if( !changesToPass.isSubset(currentChanges) ) {
 328             todoEdges.add(edgeF);
 329             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
 330           }
 331         }
 332       }
 333     }
 334   }
 335
 336
 337   ////////////////////////////////////////////////////
 338   //
 339   //  Assignment Operation Methods
 340   //
 341   //  These methods are high-level operations for
 342   //  modeling program assignment statements using
 343   //  the low-level reference create/remove methods
 344   //  above.
 345   //
 346   //  The destination in an assignment statement is
 347   //  going to have new references.  The method of
 348   //  determining the references depends on the type
 349   //  of the FlatNode assignment and the predicates
 350   //  of the nodes and edges involved.
 351   //
 352   ////////////////////////////////////////////////////
 353   public void assignTempXEqualToTempY(TempDescriptor x,
 354                                       TempDescriptor y) {
 355
 356     LabelNode lnX = getLabelNodeFromTemp(x);
 357     LabelNode lnY = getLabelNodeFromTemp(y);
 358
 359     clearReferenceEdgesFrom(lnX, null, true);
 360
 361     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 362     while( itrYhrn.hasNext() ) {
 363       ReferenceEdge edgeY       = itrYhrn.next();
 364       HeapRegionNode referencee = edgeY.getDst();
 365       ReferenceEdge edgeNew    = edgeY.copy();
 366       edgeNew.setSrc(lnX);
 367
 368       addReferenceEdge(lnX, referencee, edgeNew);
 369     }
 370   }
 371
 372
 373   public void assignTempXEqualToTempYFieldF(TempDescriptor x,
 374                                             TempDescriptor y,
 375                                             FieldDescriptor f) {
 376     LabelNode lnX = getLabelNodeFromTemp(x);
 377     LabelNode lnY = getLabelNodeFromTemp(y);
 378
 379     clearReferenceEdgesFrom(lnX, null, true);
 380
 381     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 382     while( itrYhrn.hasNext() ) {
 383       ReferenceEdge edgeY = itrYhrn.next();
 384       HeapRegionNode hrnY  = edgeY.getDst();
 385       ReachabilitySet betaY = edgeY.getBeta();
 386
 387       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 388       while( itrHrnFhrn.hasNext() ) {
 389         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 390         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 391         ReachabilitySet betaHrn = edgeHrn.getBeta();
 392
 393         if( edgeHrn.getFieldDesc() == null ||
 394             edgeHrn.getFieldDesc() == f ) {
 395
 396           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 397                                                     hrnHrn,
 398                                                     f,
 399                                                     false,
 400                                                     betaY.intersection(betaHrn) );
 401
 402           addReferenceEdge(lnX, hrnHrn, edgeNew);
 403         }
 404       }
 405     }
 406   }
 407
 408
 409   public void assignTempXFieldFEqualToTempY(TempDescriptor x,
 410                                             FieldDescriptor f,
 411                                             TempDescriptor y) {
 412     LabelNode lnX = getLabelNodeFromTemp(x);
 413     LabelNode lnY = getLabelNodeFromTemp(y);
 414
 415     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 416     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 417
 418
 419     // first look for possible strong updates and remove those edges
 420     boolean strongUpdate = false;
 421
 422     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 423     while( itrXhrn.hasNext() ) {
 424       ReferenceEdge edgeX = itrXhrn.next();
 425       HeapRegionNode hrnX = edgeX.getDst();
 426
 427       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 428       while( itrYhrn.hasNext() ) {
 429         ReferenceEdge edgeY = itrYhrn.next();
 430         HeapRegionNode hrnY = edgeY.getDst();
 431
 432         // we can do a strong update here if one of two cases holds
 433         if( f != null &&
 434             hrnX.isSingleObject() &&
 435             (   (hrnX.getNumReferencers() == 1)                           ||
 436                 ( lnX.getNumReferencees() == 1)
 437             )
 438           ) {
 439           strongUpdate = true;
 440           clearReferenceEdgesFrom( hrnX, f, false );
 441         }
 442       }
 443     }
 444
 445
 446     // then do all token propagation
 447     itrXhrn = lnX.iteratorToReferencees();
 448     while( itrXhrn.hasNext() ) {
 449       ReferenceEdge edgeX = itrXhrn.next();
 450       HeapRegionNode hrnX = edgeX.getDst();
 451       ReachabilitySet betaX = edgeX.getBeta();
 452
 453       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 454
 455       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 456       while( itrYhrn.hasNext() ) {
 457         ReferenceEdge edgeY = itrYhrn.next();
 458         HeapRegionNode hrnY = edgeY.getDst();
 459         ReachabilitySet O = edgeY.getBeta();
 460
 461
 462         // propagate tokens over nodes starting from hrnSrc, and it will
 463         // take care of propagating back up edges from any touched nodes
 464         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 465         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 466
 467
 468         // then propagate back just up the edges from hrn
 469         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 470
 471
 472         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 473
 474         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 475           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 476
 477         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 478         while( referItr.hasNext() ) {
 479           ReferenceEdge edgeUpstream = referItr.next();
 480           todoEdges.add(edgeUpstream);
 481           edgePlannedChanges.put(edgeUpstream, Cx);
 482         }
 483
 484         propagateTokensOverEdges(todoEdges,
 485                                  edgePlannedChanges,
 486                                  edgesWithNewBeta);
 487       }
 488     }
 489
 490
 491     // apply the updates to reachability
 492     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 493     while( nodeItr.hasNext() ) {
 494       nodeItr.next().applyAlphaNew();
 495     }
 496
 497     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
 498     while( edgeItr.hasNext() ) {
 499       edgeItr.next().applyBetaNew();
 500     }
 501
 502
 503     // then go back through and add the new edges
 504     itrXhrn = lnX.iteratorToReferencees();
 505     while( itrXhrn.hasNext() ) {
 506       ReferenceEdge edgeX = itrXhrn.next();
 507       HeapRegionNode hrnX = edgeX.getDst();
 508
 509       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 510       while( itrYhrn.hasNext() ) {
 511         ReferenceEdge edgeY = itrYhrn.next();
 512         HeapRegionNode hrnY = edgeY.getDst();
 513
 514         // prepare the new reference edge hrnX.f -> hrnY
 515         ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
 516                                                   hrnY,
 517                                                   f,
 518                                                   false,
 519                                                   edgeY.getBeta().pruneBy( hrnX.getAlpha() )
 520                                                   );
 521
 522         // look to see if an edge with same field exists
 523         // and merge with it, otherwise just add the edge
 524         ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
 525
 526         if( edgeExisting != null ) {
 527           edgeExisting.setBeta(
 528                                edgeExisting.getBeta().union( edgeNew.getBeta() )
 529                               );
 530           // a new edge here cannot be reflexive, so existing will
 531           // always be also not reflexive anymore
 532           edgeExisting.setIsInitialParamReflexive( false );
 533         } else {
 534           addReferenceEdge( hrnX, hrnY, edgeNew );
 535         }
 536       }
 537     }
 538
 539
 540     // if there was a strong update, make sure to improve
 541     // reachability with a global sweep
 542     if( strongUpdate ) {
 543       globalSweep();
 544     }
 545   }
 546
 547
 548   public void assignTempEqualToParamAlloc(TempDescriptor td,
 549                                           boolean isTask,
 550                                           Integer paramIndex) {
 551     assert td != null;
 552
 553     LabelNode lnParam = getLabelNodeFromTemp(td);
 554     HeapRegionNode hrn = createNewHeapRegionNode(null,
 555                                                  false,
 556                                                  isTask,
 557                                                  false,
 558                                                  true,
 559                                                  null,
 560                                                  null,
 561                                                  "param" + paramIndex);
 562
 563     // this is a non-program-accessible label that picks up beta
 564     // info to be used for fixing a caller of this method
 565     TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
 566     LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
 567
 568     // keep track of heap regions that were created for
 569     // parameter labels, the index of the parameter they
 570     // are for is important when resolving method calls
 571     Integer newID = hrn.getID();
 572     assert !id2paramIndexSet.containsKey(newID);
 573     Set s = new HashSet<Integer>();
 574     s.add( paramIndex );
 575     id2paramIndexSet.put(newID, s);
 576     paramIndex2id.put(paramIndex, newID);
 577     paramIndex2tdQ.put(paramIndex, tdParamQ);
 578
 579     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
 580                                                               true,
 581                                                               TokenTuple.ARITY_ONE).makeCanonical()
 582                                                ).makeCanonical();
 583
 584     // heap regions for parameters are always multiple object (see above)
 585     // and have a reference to themselves, because we can't know the
 586     // structure of memory that is passed into the method.  We're assuming
 587     // the worst here.
 588
 589     ReferenceEdge edgeFromLabel =
 590       new ReferenceEdge(lnParam, hrn, null, false, beta);
 591
 592     ReferenceEdge edgeFromLabelQ =
 593       new ReferenceEdge(lnParamQ, hrn, null, false, beta);
 594
 595     ReferenceEdge edgeReflexive =
 596       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 597
 598     addReferenceEdge(lnParam,  hrn, edgeFromLabel);
 599     addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
 600     addReferenceEdge(hrn,      hrn, edgeReflexive);
 601   }
 602
 603   public void makeAliasedParamHeapRegionNode(TempDescriptor td) {
 604     assert td != null;
 605
 606     LabelNode lnParam = getLabelNodeFromTemp(td);
 607     HeapRegionNode hrn = createNewHeapRegionNode(null,
 608                                                  false,
 609                                                  false,
 610                                                  false,
 611                                                  true,
 612                                                  null,
 613                                                  null,
 614                                                  "aliasedParams");
 615
 616
 617     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(hrn.getID(),
 618                                                               true,
 619                                                               TokenTuple.ARITY_ONE).makeCanonical()
 620                                                ).makeCanonical();
 621
 622     // heap regions for parameters are always multiple object (see above)
 623     // and have a reference to themselves, because we can't know the
 624     // structure of memory that is passed into the method.  We're assuming
 625     // the worst here.
 626
 627     ReferenceEdge edgeFromLabel =
 628       new ReferenceEdge(lnParam, hrn, null, false, beta);
 629
 630     ReferenceEdge edgeReflexive =
 631       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 632
 633     addReferenceEdge(lnParam, hrn, edgeFromLabel);
 634     addReferenceEdge(hrn,     hrn, edgeReflexive);
 635   }
 636
 637   public void assignTempEqualToAliasedParam(TempDescriptor tdParam,
 638                                             TempDescriptor tdAliased,
 639                                             Integer paramIndex ) {
 640
 641     assert tdParam   != null;
 642     assert tdAliased != null;
 643
 644     LabelNode lnParam   = getLabelNodeFromTemp(tdParam);
 645     LabelNode lnAliased = getLabelNodeFromTemp(tdAliased);
 646
 647     // this is a non-program-accessible label that picks up beta
 648     // info to be used for fixing a caller of this method
 649     TempDescriptor tdParamQ = new TempDescriptor(tdParam+"specialQ");
 650     LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
 651
 652     // the lnAliased should always only reference one node, and that
 653     // heap region node is the aliased param blob
 654     assert lnAliased.getNumReferencees() == 1;
 655     HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
 656
 657     // keep track of heap regions that were created for
 658     // parameter labels, the index of the parameter they
 659     // are for is important when resolving method calls
 660     Integer idAliased = hrnAliasBlob.getID();
 661     Set s = id2paramIndexSet.get( idAliased );
 662     if( s == null ) {
 663       s = new HashSet<Integer>();
 664     }
 665     s.add( paramIndex );
 666     id2paramIndexSet.put(idAliased, s);
 667     paramIndex2id.put(paramIndex, idAliased);
 668     paramIndex2tdQ.put(paramIndex, tdParamQ);
 669
 670     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(idAliased,
 671                                                               true,
 672                                                               TokenTuple.ARITY_ONE).makeCanonical()
 673                                                ).makeCanonical();
 674
 675     // heap regions for parameters are always multiple object (see above)
 676     // and have a reference to themselves, because we can't know the
 677     // structure of memory that is passed into the method.  We're assuming
 678     // the worst here.
 679
 680     ReferenceEdge edgeFromLabel =
 681       new ReferenceEdge(lnParam, hrnAliasBlob, null, false, beta);
 682
 683     ReferenceEdge edgeFromLabelQ =
 684       new ReferenceEdge(lnParamQ, hrnAliasBlob, null, false, beta);
 685
 686     addReferenceEdge(lnParam,  hrnAliasBlob, edgeFromLabel);
 687     addReferenceEdge(lnParamQ, hrnAliasBlob, edgeFromLabelQ);
 688   }
 689
 690
 691
 692   public void assignReturnEqualToTemp(TempDescriptor x) {
 693
 694     LabelNode lnR = getLabelNodeFromTemp(tdReturn);
 695     LabelNode lnX = getLabelNodeFromTemp(x);
 696
 697     clearReferenceEdgesFrom(lnR, null, true);
 698
 699     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 700     while( itrXhrn.hasNext() ) {
 701       ReferenceEdge edgeX       = itrXhrn.next();
 702       HeapRegionNode referencee = edgeX.getDst();
 703       ReferenceEdge edgeNew    = edgeX.copy();
 704       edgeNew.setSrc(lnR);
 705
 706       addReferenceEdge(lnR, referencee, edgeNew);
 707     }
 708   }
 709
 710
 711   public void assignTempEqualToNewAlloc(TempDescriptor x,
 712                                         AllocationSite as) {
 713     assert x  != null;
 714     assert as != null;
 715
 716     age(as);
 717
 718     // after the age operation the newest (or zero-ith oldest)
 719     // node associated with the allocation site should have
 720     // no references to it as if it were a newly allocated
 721     // heap region, so make a reference to it to complete
 722     // this operation
 723
 724     Integer idNewest  = as.getIthOldest(0);
 725     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 726     assert hrnNewest != null;
 727
 728     LabelNode lnX = getLabelNodeFromTemp(x);
 729     clearReferenceEdgesFrom(lnX, null, true);
 730
 731     ReferenceEdge edgeNew =
 732       new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
 733
 734     addReferenceEdge(lnX, hrnNewest, edgeNew);
 735   }
 736
 737
 738   // use the allocation site (unique to entire analysis) to
 739   // locate the heap region nodes in this ownership graph
 740   // that should be aged.  The process models the allocation
 741   // of new objects and collects all the oldest allocations
 742   // in a summary node to allow for a finite analysis
 743   //
 744   // There is an additional property of this method.  After
 745   // running it on a particular ownership graph (many graphs
 746   // may have heap regions related to the same allocation site)
 747   // the heap region node objects in this ownership graph will be
 748   // allocated.  Therefore, after aging a graph for an allocation
 749   // site, attempts to retrieve the heap region nodes using the
 750   // integer id's contained in the allocation site should always
 751   // return non-null heap regions.
 752   public void age(AllocationSite as) {
 753
 754     // aging adds this allocation site to the graph's
 755     // list of sites that exist in the graph, or does
 756     // nothing if the site is already in the list
 757     allocationSites.add(as);
 758
 759     // get the summary node for the allocation site in the context
 760     // of this particular ownership graph
 761     HeapRegionNode hrnSummary = getSummaryNode(as);
 762
 763     // merge oldest node into summary
 764     Integer idK  = as.getOldest();
 765     HeapRegionNode hrnK = id2hrn.get(idK);
 766     mergeIntoSummary(hrnK, hrnSummary);
 767
 768     // move down the line of heap region nodes
 769     // clobbering the ith and transferring all references
 770     // to and from i-1 to node i.  Note that this clobbers
 771     // the oldest node (hrnK) that was just merged into
 772     // the summary
 773     for( int i = allocationDepth - 1; i > 0; --i ) {
 774
 775       // move references from the i-1 oldest to the ith oldest
 776       Integer idIth     = as.getIthOldest(i);
 777       HeapRegionNode hrnI      = id2hrn.get(idIth);
 778       Integer idImin1th = as.getIthOldest(i - 1);
 779       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 780
 781       transferOnto(hrnImin1, hrnI);
 782     }
 783
 784     // as stated above, the newest node should have had its
 785     // references moved over to the second oldest, so we wipe newest
 786     // in preparation for being the new object to assign something to
 787     Integer id0th = as.getIthOldest(0);
 788     HeapRegionNode hrn0  = id2hrn.get(id0th);
 789     assert hrn0 != null;
 790
 791     // clear all references in and out of newest node
 792     clearReferenceEdgesFrom(hrn0, null, true);
 793     clearReferenceEdgesTo(hrn0, null, true);
 794
 795
 796     // now tokens in reachability sets need to "age" also
 797     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 798     while( itrAllLabelNodes.hasNext() ) {
 799       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 800       LabelNode ln = (LabelNode) me.getValue();
 801
 802       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 803       while( itrEdges.hasNext() ) {
 804         ageTokens(as, itrEdges.next() );
 805       }
 806     }
 807
 808     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 809     while( itrAllHRNodes.hasNext() ) {
 810       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
 811       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 812
 813       ageTokens(as, hrnToAge);
 814
 815       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
 816       while( itrEdges.hasNext() ) {
 817         ageTokens(as, itrEdges.next() );
 818       }
 819     }
 820
 821
 822     // after tokens have been aged, reset newest node's reachability
 823     if( hrn0.isFlagged() ) {
 824       hrn0.setAlpha(new ReachabilitySet(
 825                       new TokenTupleSet(
 826                         new TokenTuple(hrn0).makeCanonical()
 827                         ).makeCanonical()
 828                       ).makeCanonical()
 829                     );
 830     } else {
 831       hrn0.setAlpha(new ReachabilitySet(
 832                       new TokenTupleSet().makeCanonical()
 833                       ).makeCanonical()
 834                     );
 835     }
 836   }
 837
 838
 839   protected HeapRegionNode getSummaryNode(AllocationSite as) {
 840
 841     Integer idSummary  = as.getSummary();
 842     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
 843
 844     // If this is null then we haven't touched this allocation site
 845     // in the context of the current ownership graph, so allocate
 846     // heap region nodes appropriate for the entire allocation site.
 847     // This should only happen once per ownership graph per allocation site,
 848     // and a particular integer id can be used to locate the heap region
 849     // in different ownership graphs that represents the same part of an
 850     // allocation site.
 851     if( hrnSummary == null ) {
 852
 853       boolean hasFlags = false;
 854       if( as.getType().isClass() ) {
 855         hasFlags = as.getType().getClassDesc().hasFlags();
 856       }
 857
 858       hrnSummary = createNewHeapRegionNode(idSummary,
 859                                            false,
 860                                            hasFlags,
 861                                            true,
 862                                            false,
 863                                            as,
 864                                            null,
 865                                            as + "\\n" + as.getType() + "\\nsummary");
 866
 867       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 868         Integer idIth = as.getIthOldest(i);
 869         assert !id2hrn.containsKey(idIth);
 870         createNewHeapRegionNode(idIth,
 871                                 true,
 872                                 hasFlags,
 873                                 false,
 874                                 false,
 875                                 as,
 876                                 null,
 877                                 as + "\\n" + as.getType() + "\\n" + i + " oldest");
 878       }
 879     }
 880
 881     return hrnSummary;
 882   }
 883
 884
 885   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
 886
 887     Integer idShadowSummary  = as.getSummaryShadow();
 888     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
 889
 890     if( hrnShadowSummary == null ) {
 891
 892       boolean hasFlags = false;
 893       if( as.getType().isClass() ) {
 894         hasFlags = as.getType().getClassDesc().hasFlags();
 895       }
 896
 897       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
 898                                                  false,
 899                                                  hasFlags,
 900                                                  true,
 901                                                  false,
 902                                                  as,
 903                                                  null,
 904                                                  as + "\\n" + as.getType() + "\\nshadowSum");
 905
 906       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 907         Integer idShadowIth = as.getIthOldestShadow(i);
 908         assert !id2hrn.containsKey(idShadowIth);
 909         createNewHeapRegionNode(idShadowIth,
 910                                 true,
 911                                 hasFlags,
 912                                 false,
 913                                 false,
 914                                 as,
 915                                 null,
 916                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
 917       }
 918     }
 919
 920     return hrnShadowSummary;
 921   }
 922
 923
 924   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
 925     assert hrnSummary.isNewSummary();
 926
 927     // transfer references _from_ hrn over to hrnSummary
 928     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
 929     while( itrReferencee.hasNext() ) {
 930       ReferenceEdge edge       = itrReferencee.next();
 931       ReferenceEdge edgeMerged = edge.copy();
 932       edgeMerged.setSrc(hrnSummary);
 933
 934       HeapRegionNode hrnReferencee = edge.getDst();
 935       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
 936
 937       if( edgeSummary == null ) {
 938         // the merge is trivial, nothing to be done
 939       } else {
 940         // otherwise an edge from the referencer to hrnSummary exists already
 941         // and the edge referencer->hrn should be merged with it
 942         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 943       }
 944
 945       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
 946     }
 947
 948     // next transfer references _to_ hrn over to hrnSummary
 949     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
 950     while( itrReferencer.hasNext() ) {
 951       ReferenceEdge edge         = itrReferencer.next();
 952       ReferenceEdge edgeMerged   = edge.copy();
 953       edgeMerged.setDst(hrnSummary);
 954
 955       OwnershipNode onReferencer = edge.getSrc();
 956       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
 957
 958       if( edgeSummary == null ) {
 959         // the merge is trivial, nothing to be done
 960       } else {
 961         // otherwise an edge from the referencer to alpha_S exists already
 962         // and the edge referencer->alpha_K should be merged with it
 963         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 964       }
 965
 966       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
 967     }
 968
 969     // then merge hrn reachability into hrnSummary
 970     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
 971   }
 972
 973
 974   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
 975
 976     // clear references in and out of node b
 977     clearReferenceEdgesFrom(hrnB, null, true);
 978     clearReferenceEdgesTo(hrnB, null, true);
 979
 980     // copy each edge in and out of A to B
 981     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
 982     while( itrReferencee.hasNext() ) {
 983       ReferenceEdge edge          = itrReferencee.next();
 984       HeapRegionNode hrnReferencee = edge.getDst();
 985       ReferenceEdge edgeNew       = edge.copy();
 986       edgeNew.setSrc(hrnB);
 987
 988       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
 989     }
 990
 991     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
 992     while( itrReferencer.hasNext() ) {
 993       ReferenceEdge edge         = itrReferencer.next();
 994       OwnershipNode onReferencer = edge.getSrc();
 995       ReferenceEdge edgeNew      = edge.copy();
 996       edgeNew.setDst(hrnB);
 997
 998       addReferenceEdge(onReferencer, hrnB, edgeNew);
 999     }
1000
1001     // replace hrnB reachability with hrnA's
1002     hrnB.setAlpha(hrnA.getAlpha() );
1003   }
1004
1005
1006   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
1007     edge.setBeta(edge.getBeta().ageTokens(as) );
1008   }
1009
1010   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
1011     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1012   }
1013
1014
1015   public Set<Integer> calculateAliasedParamSet(FlatCall fc,
1016                                                boolean isStatic,
1017                                                FlatMethod fm) {
1018
1019     Hashtable<Integer, LabelNode> paramIndex2ln =
1020       new Hashtable<Integer, LabelNode>();
1021
1022     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1023       new Hashtable<Integer, HashSet<HeapRegionNode> >();
1024
1025     for( int i = 0; i < fm.numParameters(); ++i ) {
1026       Integer paramIndex = new Integer(i);
1027
1028       // now depending on whether the callee is static or not
1029       // we need to account for a "this" argument in order to
1030       // find the matching argument in the caller context
1031       TempDescriptor argTemp_i;
1032       if( isStatic ) {
1033         argTemp_i = fc.getArg(paramIndex);
1034       } else {
1035         if( paramIndex.equals(0) ) {
1036           argTemp_i = fc.getThis();
1037         } else {
1038           argTemp_i = fc.getArg(paramIndex - 1);
1039         }
1040       }
1041
1042       // in non-static methods there is a "this" pointer
1043       // that should be taken into account
1044       if( isStatic ) {
1045         assert fc.numArgs()     == fm.numParameters();
1046       } else {
1047         assert fc.numArgs() + 1 == fm.numParameters();
1048       }
1049
1050       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1051       paramIndex2ln.put(paramIndex, argLabel_i);
1052     }
1053
1054     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1055     while( lnArgItr.hasNext() ) {
1056       Map.Entry me      = (Map.Entry)lnArgItr.next();
1057       Integer index   = (Integer)   me.getKey();
1058       LabelNode lnArg_i = (LabelNode) me.getValue();
1059
1060       // rewrite alpha for the nodes reachable from argument label i
1061       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1062       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1063
1064       // to find all reachable nodes, start with label referencees
1065       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1066       while( edgeArgItr.hasNext() ) {
1067         ReferenceEdge edge = edgeArgItr.next();
1068         todoNodes.add(edge.getDst() );
1069       }
1070
1071       // then follow links until all reachable nodes have been found
1072       while( !todoNodes.isEmpty() ) {
1073         HeapRegionNode hrn = todoNodes.iterator().next();
1074         todoNodes.remove(hrn);
1075         reachableNodes.add(hrn);
1076
1077         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1078         while( edgeItr.hasNext() ) {
1079           ReferenceEdge edge = edgeItr.next();
1080
1081           if( !reachableNodes.contains(edge.getDst() ) ) {
1082             todoNodes.add(edge.getDst() );
1083           }
1084         }
1085       }
1086
1087       // save for later
1088       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1089     }
1090
1091     Set<Integer> aliasedIndices = new HashSet<Integer>();
1092
1093     // check for arguments that are aliased
1094     for( int i = 0; i < fm.numParameters(); ++i ) {
1095       for( int j = 0; j < i; ++j ) {
1096         HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1097         HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1098
1099         Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1100         intersection.retainAll(s2);
1101
1102         if( !intersection.isEmpty() ) {
1103           aliasedIndices.add( new Integer( i ) );
1104           aliasedIndices.add( new Integer( j ) );
1105         }
1106       }
1107     }
1108
1109     return aliasedIndices;
1110   }
1111
1112
1113   public void resolveMethodCall(FlatCall fc,
1114                                 boolean isStatic,
1115                                 FlatMethod fm,
1116                                 OwnershipGraph ogCallee) {
1117
1118     // define rewrite rules and other structures to organize
1119     // data by parameter/argument index
1120     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
1121       new Hashtable<Integer, ReachabilitySet>();
1122
1123     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
1124       new Hashtable<Integer, ReachabilitySet>();
1125
1126     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
1127       new Hashtable<Integer, ReachabilitySet>();
1128
1129     Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d =
1130       new Hashtable<Integer, ReachabilitySet>();
1131
1132     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
1133       new Hashtable<Integer, ReachabilitySet>();
1134
1135     // helpful structures
1136     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
1137       new Hashtable<TokenTuple, Integer>();
1138
1139     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
1140       new Hashtable<Integer, TokenTuple>();
1141
1142     Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
1143       new Hashtable<TokenTuple, Integer>();
1144
1145     Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
1146       new Hashtable<Integer, TokenTuple>();
1147
1148     Hashtable<Integer, LabelNode> paramIndex2ln =
1149       new Hashtable<Integer, LabelNode>();
1150
1151     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1152       new Hashtable<Integer, HashSet<HeapRegionNode> >();
1153
1154
1155     // add a bogus entry with the identity rule for easy rewrite
1156     // of new callee nodes and edges, doesn't belong to any parameter
1157     Integer bogusID = new Integer(bogusParamIndexInt);
1158     Integer bogusIndex = new Integer(bogusParamIndexInt);
1159     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE).makeCanonical();
1160     TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE).makeCanonical();
1161     ReachabilitySet rsIdentity =
1162       new ReachabilitySet(
1163         new TokenTupleSet(bogusToken).makeCanonical()
1164         ).makeCanonical();
1165
1166     paramIndex2rewriteH.put(bogusIndex, rsIdentity);
1167     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
1168     paramToken2paramIndex.put(bogusToken, bogusIndex);
1169     paramIndex2paramToken.put(bogusIndex, bogusToken);
1170     paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
1171     paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
1172
1173
1174     for( int i = 0; i < fm.numParameters(); ++i ) {
1175       Integer paramIndex = new Integer(i);
1176
1177       assert ogCallee.paramIndex2id.containsKey(paramIndex);
1178       Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
1179
1180       assert ogCallee.id2hrn.containsKey(idParam);
1181       HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
1182       assert hrnParam != null;
1183       paramIndex2rewriteH.put(paramIndex,
1184
1185                               toShadowTokens(ogCallee, hrnParam.getAlpha() )
1186                               );
1187
1188       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
1189       assert edgeReflexive_i != null;
1190       paramIndex2rewriteJ.put(paramIndex,
1191                               toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
1192                               );
1193
1194       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
1195       assert tdParamQ != null;
1196       LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
1197       assert lnParamQ != null;
1198       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
1199       assert edgeSpecialQ_i != null;
1200       paramIndex2rewriteK.put(paramIndex,
1201                               toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
1202                               );
1203
1204       TokenTuple p_i = new TokenTuple(hrnParam.getID(),
1205                                       true,
1206                                       TokenTuple.ARITY_ONE).makeCanonical();
1207       paramToken2paramIndex.put(p_i, paramIndex);
1208       paramIndex2paramToken.put(paramIndex, p_i);
1209
1210       TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
1211                                            true,
1212                                            TokenTuple.ARITY_ONEORMORE).makeCanonical();
1213       paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
1214       paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
1215
1216       // now depending on whether the callee is static or not
1217       // we need to account for a "this" argument in order to
1218       // find the matching argument in the caller context
1219       TempDescriptor argTemp_i;
1220       if( isStatic ) {
1221         argTemp_i = fc.getArg(paramIndex);
1222       } else {
1223         if( paramIndex.equals(0) ) {
1224           argTemp_i = fc.getThis();
1225         } else {
1226           argTemp_i = fc.getArg(paramIndex - 1);
1227         }
1228       }
1229
1230       // in non-static methods there is a "this" pointer
1231       // that should be taken into account
1232       if( isStatic ) {
1233         assert fc.numArgs()     == fm.numParameters();
1234       } else {
1235         assert fc.numArgs() + 1 == fm.numParameters();
1236       }
1237
1238       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1239       paramIndex2ln.put(paramIndex, argLabel_i);
1240
1241       ReachabilitySet d_i = new ReachabilitySet().makeCanonical();
1242       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1243       while( edgeItr.hasNext() ) {
1244         ReferenceEdge edge = edgeItr.next();
1245         d_i = d_i.union(edge.getBeta());
1246       }
1247       paramIndex2rewrite_d.put(paramIndex, d_i);
1248
1249       ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
1250       paramIndex2rewriteD.put(paramIndex, D_i);
1251     }
1252
1253
1254     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1255     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1256
1257     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1258     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1259
1260     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1261     while( lnArgItr.hasNext() ) {
1262       Map.Entry me      = (Map.Entry)lnArgItr.next();
1263       Integer index   = (Integer)   me.getKey();
1264       LabelNode lnArg_i = (LabelNode) me.getValue();
1265
1266       // rewrite alpha for the nodes reachable from argument label i
1267       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1268       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1269
1270       // to find all reachable nodes, start with label referencees
1271       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1272       while( edgeArgItr.hasNext() ) {
1273         ReferenceEdge edge = edgeArgItr.next();
1274         todoNodes.add(edge.getDst() );
1275       }
1276
1277       // then follow links until all reachable nodes have been found
1278       while( !todoNodes.isEmpty() ) {
1279         HeapRegionNode hrn = todoNodes.iterator().next();
1280         todoNodes.remove(hrn);
1281         reachableNodes.add(hrn);
1282
1283         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1284         while( edgeItr.hasNext() ) {
1285           ReferenceEdge edge = edgeItr.next();
1286
1287           if( !reachableNodes.contains(edge.getDst() ) ) {
1288             todoNodes.add(edge.getDst() );
1289           }
1290         }
1291       }
1292
1293       // save for later
1294       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1295
1296       // now iterate over reachable nodes to update their alpha, and
1297       // classify edges found as "argument reachable" or "upstream"
1298       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1299       while( hrnItr.hasNext() ) {
1300         HeapRegionNode hrn = hrnItr.next();
1301
1302         rewriteCallerReachability(index,
1303                                   hrn,
1304                                   null,
1305                                   paramIndex2rewriteH.get(index),
1306                                   paramIndex2rewrite_d,
1307                                   paramIndex2rewriteD,
1308                                   paramIndex2paramToken.get(index),
1309                                   paramToken2paramIndex,
1310                                   paramTokenPlus2paramIndex,
1311                                   false,
1312                                   null);
1313
1314         nodesWithNewAlpha.add(hrn);
1315
1316         // look at all incoming edges to the reachable nodes
1317         // and sort them as edges reachable from the argument
1318         // label node, or upstream edges
1319         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1320         while( edgeItr.hasNext() ) {
1321           ReferenceEdge edge = edgeItr.next();
1322
1323           OwnershipNode on = edge.getSrc();
1324
1325           if( on instanceof LabelNode ) {
1326
1327             LabelNode ln0 = (LabelNode) on;
1328             if( ln0.equals(lnArg_i) ) {
1329               edgesReachable.add(edge);
1330             } else {
1331               edgesUpstream.add(edge);
1332             }
1333
1334           } else {
1335
1336             HeapRegionNode hrn0 = (HeapRegionNode) on;
1337             if( reachableNodes.contains(hrn0) ) {
1338               edgesReachable.add(edge);
1339             } else {
1340               edgesUpstream.add(edge);
1341             }
1342           }
1343         }
1344       }
1345
1346       // update reachable edges
1347       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1348       while( edgeReachableItr.hasNext() ) {
1349         ReferenceEdge edgeReachable = edgeReachableItr.next();
1350
1351         rewriteCallerReachability(index,
1352                                   null,
1353                                   edgeReachable,
1354                                   paramIndex2rewriteJ.get(index),
1355                                   paramIndex2rewrite_d,
1356                                   paramIndex2rewriteD,
1357                                   paramIndex2paramToken.get(index),
1358                                   paramToken2paramIndex,
1359                                   paramTokenPlus2paramIndex,
1360                                   false,
1361                                   null);
1362
1363         edgesWithNewBeta.add(edgeReachable);
1364       }
1365
1366       // update upstream edges
1367       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1368         new Hashtable<ReferenceEdge, ChangeTupleSet>();
1369
1370       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1371       while( edgeUpstreamItr.hasNext() ) {
1372         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1373
1374         rewriteCallerReachability(index,
1375                                   null,
1376                                   edgeUpstream,
1377                                   paramIndex2rewriteK.get(index),
1378                                   paramIndex2rewrite_d,
1379                                   paramIndex2rewriteD,
1380                                   paramIndex2paramToken.get(index),
1381                                   paramToken2paramIndex,
1382                                   paramTokenPlus2paramIndex,
1383                                   true,
1384                                   edgeUpstreamPlannedChanges);
1385
1386         edgesWithNewBeta.add(edgeUpstream);
1387       }
1388
1389       propagateTokensOverEdges(edgesUpstream,
1390                                edgeUpstreamPlannedChanges,
1391                                edgesWithNewBeta);
1392     }
1393
1394
1395     // commit changes to alpha and beta
1396     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1397     while( nodeItr.hasNext() ) {
1398       nodeItr.next().applyAlphaNew();
1399     }
1400
1401     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1402     while( edgeItr.hasNext() ) {
1403       edgeItr.next().applyBetaNew();
1404     }
1405
1406
1407     // verify the existence of allocation sites and their
1408     // shadows from the callee in the context of this caller graph
1409     // then map allocated nodes of callee onto the caller shadows
1410     // of them
1411     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1412     while( asItr.hasNext() ) {
1413       AllocationSite allocSite  = asItr.next();
1414
1415       // grab the summary in the caller just to make sure
1416       // the allocation site has nodes in the caller
1417       HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1418
1419       // assert that the shadow nodes have no reference edges
1420       // because they're brand new to the graph, or last time
1421       // they were used they should have been cleared of edges
1422       HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1423       assert hrnShadowSummary.getNumReferencers() == 0;
1424       assert hrnShadowSummary.getNumReferencees() == 0;
1425
1426       // then bring g_ij onto g'_ij and rewrite
1427       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1428       hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1429
1430       // shadow nodes only are touched by a rewrite one time,
1431       // so rewrite and immediately commit--and they don't belong
1432       // to a particular parameter, so use a bogus param index
1433       // that pulls a self-rewrite out of H
1434       rewriteCallerReachability(bogusIndex,
1435                                 hrnShadowSummary,
1436                                 null,
1437                                 hrnShadowSummary.getAlpha(),
1438                                 paramIndex2rewrite_d,
1439                                 paramIndex2rewriteD,
1440                                 bogusToken,
1441                                 paramToken2paramIndex,
1442                                 paramTokenPlus2paramIndex,
1443                                 false,
1444                                 null);
1445
1446       hrnShadowSummary.applyAlphaNew();
1447
1448
1449       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1450         Integer idIth = allocSite.getIthOldest(i);
1451         assert id2hrn.containsKey(idIth);
1452         HeapRegionNode hrnIth = id2hrn.get(idIth);
1453
1454         Integer idShadowIth = -(allocSite.getIthOldest(i));
1455         assert id2hrn.containsKey(idShadowIth);
1456         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1457         assert hrnIthShadow.getNumReferencers() == 0;
1458         assert hrnIthShadow.getNumReferencees() == 0;
1459
1460         assert ogCallee.id2hrn.containsKey(idIth);
1461         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1462         hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1463
1464         rewriteCallerReachability(bogusIndex,
1465                                   hrnIthShadow,
1466                                   null,
1467                                   hrnIthShadow.getAlpha(),
1468                                   paramIndex2rewrite_d,
1469                                   paramIndex2rewriteD,
1470                                   bogusToken,
1471                                   paramToken2paramIndex,
1472                                   paramTokenPlus2paramIndex,
1473                                   false,
1474                                   null);
1475
1476         hrnIthShadow.applyAlphaNew();
1477       }
1478     }
1479
1480
1481     // for every heap region->heap region edge in the
1482     // callee graph, create the matching edge or edges
1483     // in the caller graph
1484     Set sCallee = ogCallee.id2hrn.entrySet();
1485     Iterator iCallee = sCallee.iterator();
1486     while( iCallee.hasNext() ) {
1487       Map.Entry meCallee  = (Map.Entry)iCallee.next();
1488       Integer idCallee  = (Integer)        meCallee.getKey();
1489       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1490
1491       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1492       while( heapRegionsItrCallee.hasNext() ) {
1493         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1494         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1495         Integer idChildCallee         = hrnChildCallee.getID();
1496
1497         // only address this edge if it is not a special reflexive edge
1498         if( !edgeCallee.isInitialParamReflexive() ) {
1499
1500           // now we know that in the callee method's ownership graph
1501           // there is a heap region->heap region reference edge given
1502           // by heap region pointers:
1503           // hrnCallee -> heapChildCallee
1504           //
1505           // or by the ownership-graph independent ID's:
1506           // idCallee -> idChildCallee
1507
1508           // make the edge with src and dst so beta info is
1509           // calculated once, then copy it for each new edge in caller
1510           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1511                                                                     null,
1512                                                                     edgeCallee.getFieldDesc(),
1513                                                                     false,
1514                                                                     toShadowTokens(ogCallee,
1515                                                                                    edgeCallee.getBeta() )
1516                                                                     );
1517           rewriteCallerReachability(bogusIndex,
1518                                     null,
1519                                     edgeNewInCallerTemplate,
1520                                     edgeNewInCallerTemplate.getBeta(),
1521                                     paramIndex2rewrite_d,
1522                                     paramIndex2rewriteD,
1523                                     bogusToken,
1524                                     paramToken2paramIndex,
1525                                     paramTokenPlus2paramIndex,
1526                                     false,
1527                                     null);
1528
1529           edgeNewInCallerTemplate.applyBetaNew();
1530
1531
1532           // So now make a set of possible source heaps in the caller graph
1533           // and a set of destination heaps in the caller graph, and make
1534           // a reference edge in the caller for every possible (src,dst) pair
1535           HashSet<HeapRegionNode> possibleCallerSrcs =
1536             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1537                                                 (HeapRegionNode) edgeCallee.getSrc(),
1538                                                 paramIndex2reachableCallerNodes);
1539
1540           HashSet<HeapRegionNode> possibleCallerDsts =
1541             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1542                                                 edgeCallee.getDst(),
1543                                                 paramIndex2reachableCallerNodes);
1544
1545
1546           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1547           Iterator srcItr = possibleCallerSrcs.iterator();
1548           while( srcItr.hasNext() ) {
1549             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1550
1551             if( !hasMatchingField(src, edgeCallee) ) {
1552               // prune this source node possibility
1553               continue;
1554             }
1555
1556             Iterator dstItr = possibleCallerDsts.iterator();
1557             while( dstItr.hasNext() ) {
1558               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1559
1560               if( !hasMatchingType(edgeCallee, dst) ) {
1561                 // prune
1562                 continue;
1563               }
1564
1565               // otherwise the caller src and dst pair can match the edge, so make it
1566               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1567               edgeNewInCaller.setSrc(src);
1568               edgeNewInCaller.setDst(dst);
1569
1570               ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1571               if( edgeExisting == null ) {
1572                 // if this edge doesn't exist in the caller, create it
1573                 addReferenceEdge(src, dst, edgeNewInCaller);
1574               } else {
1575                 // if it already exists, merge with it
1576                 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1577               }
1578             }
1579           }
1580         }
1581       }
1582     }
1583
1584
1585     // return value may need to be assigned in caller
1586     TempDescriptor returnTemp = fc.getReturnTemp();
1587     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1588
1589       LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1590       clearReferenceEdgesFrom(lnLhsCaller, null, true);
1591
1592       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1593       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1594       while( edgeCalleeItr.hasNext() ) {
1595         ReferenceEdge edgeCallee = edgeCalleeItr.next();
1596
1597         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1598                                                                   null,
1599                                                                   edgeCallee.getFieldDesc(),
1600                                                                   false,
1601                                                                   toShadowTokens(ogCallee,
1602                                                                                  edgeCallee.getBeta() )
1603                                                                   );
1604         rewriteCallerReachability(bogusIndex,
1605                                   null,
1606                                   edgeNewInCallerTemplate,
1607                                   edgeNewInCallerTemplate.getBeta(),
1608                                   paramIndex2rewrite_d,
1609                                   paramIndex2rewriteD,
1610                                   bogusToken,
1611                                   paramToken2paramIndex,
1612                                   paramTokenPlus2paramIndex,
1613                                   false,
1614                                   null);
1615
1616         edgeNewInCallerTemplate.applyBetaNew();
1617
1618
1619         HashSet<HeapRegionNode> assignCallerRhs =
1620           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1621                                               edgeCallee.getDst(),
1622                                               paramIndex2reachableCallerNodes);
1623
1624         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1625         while( itrHrn.hasNext() ) {
1626           HeapRegionNode hrnCaller = itrHrn.next();
1627
1628           if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1629             // prune
1630             continue;
1631           }
1632
1633           // otherwise caller node can match callee edge, so make it
1634           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1635           edgeNewInCaller.setSrc(lnLhsCaller);
1636           edgeNewInCaller.setDst(hrnCaller);
1637
1638           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1639           if( edgeExisting == null ) {
1640
1641             // if this edge doesn't exist in the caller, create it
1642             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1643           } else {
1644             // if it already exists, merge with it
1645             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1646           }
1647         }
1648       }
1649     }
1650
1651
1652     // merge the shadow nodes of allocation sites back down to normal capacity
1653     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1654     while( allocItr.hasNext() ) {
1655       AllocationSite as = allocItr.next();
1656
1657       // first age each allocation site enough times to make room for the shadow nodes
1658       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1659         age(as);
1660       }
1661
1662       // then merge the shadow summary into the normal summary
1663       HeapRegionNode hrnSummary = getSummaryNode(as);
1664       assert hrnSummary != null;
1665
1666       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1667       assert hrnSummaryShadow != null;
1668
1669       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1670
1671       // then clear off after merge
1672       clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1673       clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1674       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1675
1676       // then transplant shadow nodes onto the now clean normal nodes
1677       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1678
1679         Integer idIth = as.getIthOldest(i);
1680         HeapRegionNode hrnIth = id2hrn.get(idIth);
1681
1682         Integer idIthShadow = as.getIthOldestShadow(i);
1683         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1684
1685         transferOnto(hrnIthShadow, hrnIth);
1686
1687         // clear off shadow nodes after transfer
1688         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1689         clearReferenceEdgesTo(hrnIthShadow, null, true);
1690         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1691       }
1692
1693       // finally, globally change shadow tokens into normal tokens
1694       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1695       while( itrAllLabelNodes.hasNext() ) {
1696         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1697         LabelNode ln = (LabelNode) me.getValue();
1698
1699         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1700         while( itrEdges.hasNext() ) {
1701           unshadowTokens(as, itrEdges.next() );
1702         }
1703       }
1704
1705       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1706       while( itrAllHRNodes.hasNext() ) {
1707         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1708         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1709
1710         unshadowTokens(as, hrnToAge);
1711
1712         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1713         while( itrEdges.hasNext() ) {
1714           unshadowTokens(as, itrEdges.next() );
1715         }
1716       }
1717     }
1718
1719     // improve reachability as much as possible
1720     globalSweep();
1721   }
1722
1723
1724   protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1725
1726     // if no allocation site, then it's a match-everything region
1727     AllocationSite asSrc = src.getAllocationSite();
1728     if( asSrc == null ) {
1729       return true;
1730     }
1731
1732     TypeDescriptor tdSrc = asSrc.getType();
1733     assert tdSrc != null;
1734
1735     // if it's not a class, it doesn't have any fields to match
1736     if( !tdSrc.isClass() ) {
1737       return false;
1738     }
1739
1740     Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1741     while( fieldsSrcItr.hasNext() ) {
1742       FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1743       if( fd == edge.getFieldDesc() ) {
1744         return true;
1745       }
1746     }
1747
1748     // otherwise it is a class with fields
1749     // but we didn't find a match
1750     return false;
1751   }
1752
1753
1754   protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1755
1756     // if the region has no type, matches everything
1757     AllocationSite asDst = dst.getAllocationSite();
1758     if( asDst == null ) {
1759       return true;
1760     }
1761
1762     TypeDescriptor tdDst = asDst.getType();
1763     assert tdDst != null;
1764
1765     // if the type is not a class don't match because
1766     // primitives are copied, no memory aliases
1767     ClassDescriptor cdDst = tdDst.getClassDesc();
1768     if( cdDst == null ) {
1769       return false;
1770     }
1771
1772     // if the field is null, it matches everything
1773     FieldDescriptor fd = edge.getFieldDesc();
1774     if( fd == null ) {
1775       return true;
1776     }
1777     TypeDescriptor tdFd = fd.getType();
1778     assert tdFd != null;
1779
1780     return typeUtil.isSuperorType(tdFd, tdDst);
1781   }
1782
1783
1784
1785   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1786     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1787   }
1788
1789   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1790     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1791   }
1792
1793
1794   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1795                                          ReachabilitySet rsIn) {
1796
1797     ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
1798
1799     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1800     while( allocItr.hasNext() ) {
1801       AllocationSite as = allocItr.next();
1802
1803       rsOut = rsOut.toShadowTokens(as);
1804     }
1805
1806     return rsOut.makeCanonical();
1807   }
1808
1809
1810   private void rewriteCallerReachability(Integer paramIndex,
1811                                          HeapRegionNode hrn,
1812                                          ReferenceEdge edge,
1813                                          ReachabilitySet rules,
1814                                          Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d,
1815                                          Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1816                                          TokenTuple p_i,
1817                                          Hashtable<TokenTuple, Integer> paramToken2paramIndex,
1818                                          Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
1819                                          boolean makeChangeSet,
1820                                          Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1821     assert(hrn == null && edge != null) ||
1822     (hrn != null && edge == null);
1823
1824     assert rules != null;
1825     assert p_i != null;
1826
1827     ReachabilitySet callerReachabilityCurrent;
1828     if( hrn == null ) {
1829       callerReachabilityCurrent = edge.getBeta();
1830     } else {
1831       callerReachabilityCurrent = hrn.getAlpha();
1832     }
1833
1834     ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
1835
1836     // for initializing structures in this method
1837     TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
1838
1839     // use this to construct a change set if required; the idea is to
1840     // map every partially rewritten token tuple set to the set of
1841     // caller-context token tuple sets that were used to generate it
1842     Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
1843       new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1844     rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
1845
1846
1847     Iterator<TokenTupleSet> rulesItr = rules.iterator();
1848     while(rulesItr.hasNext()) {
1849       TokenTupleSet rule = rulesItr.next();
1850
1851       ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
1852
1853       Iterator<TokenTuple> ruleItr = rule.iterator();
1854       while(ruleItr.hasNext()) {
1855         TokenTuple ttCallee = ruleItr.next();
1856
1857         // compute the possibilities for rewriting this callee token
1858         ReachabilitySet ttCalleeRewrites = null;
1859         boolean callerSourceUsed = false;
1860
1861         if( ttCallee.equals(p_i) ) {
1862           // replace the arity-one token of the current parameter with the reachability
1863           // information from the caller edge
1864           ttCalleeRewrites = callerReachabilityCurrent;
1865           callerSourceUsed = true;
1866
1867         } else if( paramToken2paramIndex.containsKey(ttCallee) ) {
1868           // use little d
1869           Integer paramIndex_j = paramToken2paramIndex.get(ttCallee);
1870           assert paramIndex_j != null;
1871           ttCalleeRewrites = paramIndex2rewrite_d.get(paramIndex_j);
1872           assert ttCalleeRewrites != null;
1873
1874         } else if( paramTokenPlus2paramIndex.containsKey(ttCallee) ) {
1875           // worse, use big D
1876           Integer paramIndex_j = paramTokenPlus2paramIndex.get(ttCallee);
1877           assert paramIndex_j != null;
1878           ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
1879           assert ttCalleeRewrites != null;
1880
1881         } else {
1882           // otherwise there's no need for a rewrite, just pass this one on
1883           TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
1884           ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
1885         }
1886
1887         // branch every version of the working rewritten rule with
1888         // the possibilities for rewriting the current callee token
1889         ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
1890
1891         Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
1892         while( rewrittenRuleItr.hasNext() ) {
1893           TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
1894
1895           Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
1896           while( ttCalleeRewritesItr.hasNext() ) {
1897             TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
1898
1899             TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity(ttsBranch);
1900
1901             if( makeChangeSet ) {
1902               // in order to keep the list of source token tuple sets
1903               // start with the sets used to make the partially rewritten
1904               // rule up to this point
1905               HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewritten);
1906               assert sourceSets != null;
1907
1908               // make a shallow copy for possible modification
1909               sourceSets = (HashSet<TokenTupleSet>)sourceSets.clone();
1910
1911               // if we used something from the caller to rewrite it, remember
1912               if( callerSourceUsed ) {
1913                 sourceSets.add(ttsBranch);
1914               }
1915
1916               // set mapping for the further rewritten rule
1917               rewritten2source.put(ttsRewrittenNext, sourceSets);
1918             }
1919
1920             rewrittenRuleWithTTCallee =
1921               rewrittenRuleWithTTCallee.union(ttsRewrittenNext);
1922           }
1923         }
1924
1925         // now the rewritten rule's possibilities have been extended by
1926         // rewriting the current callee token, remember result
1927         rewrittenRule = rewrittenRuleWithTTCallee;
1928       }
1929
1930       // the rule has been entirely rewritten into the caller context
1931       // now, so add it to the new reachability information
1932       callerReachabilityNew =
1933         callerReachabilityNew.union(rewrittenRule);
1934     }
1935
1936     if( makeChangeSet ) {
1937       ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
1938
1939       // each possibility for the final reachability should have a set of
1940       // caller sources mapped to it, use to create the change set
1941       Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
1942       while( callerReachabilityItr.hasNext() ) {
1943         TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
1944         HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewrittenFinal);
1945         assert sourceSets != null;
1946
1947         Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
1948         while( sourceSetsItr.hasNext() ) {
1949           TokenTupleSet ttsSource = sourceSetsItr.next();
1950
1951           callerChangeSet =
1952             callerChangeSet.union(new ChangeTuple(ttsSource, ttsRewrittenFinal) );
1953         }
1954       }
1955
1956       assert edgePlannedChanges != null;
1957       edgePlannedChanges.put(edge, callerChangeSet);
1958     }
1959
1960     if( hrn == null ) {
1961       edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
1962     } else {
1963       hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
1964     }
1965   }
1966
1967
1968
1969   private HashSet<HeapRegionNode>
1970   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1971                                       HeapRegionNode hrnCallee,
1972                                       Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1973                                       ) {
1974
1975     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1976
1977     Set<Integer> paramIndicesCallee = ogCallee.id2paramIndexSet.get( hrnCallee.getID() );
1978
1979     if( paramIndicesCallee == null ) {
1980       // this is a node allocated in the callee then and it has
1981       // exactly one shadow node in the caller to map to
1982       AllocationSite as = hrnCallee.getAllocationSite();
1983       assert as != null;
1984
1985       int age = as.getAgeCategory(hrnCallee.getID() );
1986       assert age != AllocationSite.AGE_notInThisSite;
1987
1988       Integer idCaller;
1989       if( age == AllocationSite.AGE_summary ) {
1990         idCaller = as.getSummaryShadow();
1991       } else if( age == AllocationSite.AGE_oldest ) {
1992         idCaller = as.getOldestShadow();
1993       } else {
1994         assert age == AllocationSite.AGE_in_I;
1995
1996         Integer I = as.getAge(hrnCallee.getID() );
1997         assert I != null;
1998
1999         idCaller = as.getIthOldestShadow(I);
2000       }
2001
2002       assert id2hrn.containsKey(idCaller);
2003       HeapRegionNode hrnCaller = id2hrn.get(idCaller);
2004       possibleCallerHRNs.add(hrnCaller);
2005
2006     } else {
2007       // this is a node that was created to represent a parameter
2008       // so it maps to a whole mess of heap regions
2009       Iterator<Integer> itrIndex = paramIndicesCallee.iterator();
2010       while( itrIndex.hasNext() ) {
2011         Integer paramIndexCallee = itrIndex.next();
2012         assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
2013         possibleCallerHRNs.addAll( paramIndex2reachableCallerNodes.get(paramIndexCallee) );
2014       }
2015     }
2016
2017     return possibleCallerHRNs;
2018   }
2019
2020
2021
2022   ////////////////////////////////////////////////////
2023   //
2024   //  This global sweep is an optional step to prune
2025   //  reachability sets that are not internally
2026   //  consistent with the global graph.  It should be
2027   //  invoked after strong updates or method calls.
2028   //
2029   ////////////////////////////////////////////////////
2030   protected void globalSweep() {
2031
2032     // a work set for performing the sweep
2033     Hashtable<HeapRegionNode, HashSet<TokenTupleSet> > workSet =
2034       new Hashtable<HeapRegionNode, HashSet<TokenTupleSet> >();
2035
2036     // first initialize every alphaNew for a flagged region
2037     // (or parameter region) to a set with just that token
2038     Set hrns = id2hrn.entrySet();
2039     Iterator itrHrns = hrns.iterator();
2040     while( itrHrns.hasNext() ) {
2041       Map.Entry me = (Map.Entry)itrHrns.next();
2042       Integer token = (Integer) me.getKey();
2043       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2044
2045       // assert that this node and incoming edges have clean alphaNew
2046       // and betaNew sets, respectively
2047       ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
2048       assert rsEmpty.equals( hrn.getAlphaNew() );
2049
2050       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2051       while( itrRes.hasNext() ) {
2052         ReferenceEdge edge = itrRes.next();
2053         assert rsEmpty.equals( edge.getBetaNew() );
2054       }
2055
2056       TokenTuple tt     = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE        ).makeCanonical();
2057       TokenTuple ttPlus = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONEORMORE  ).makeCanonical();
2058       TokenTuple ttStar = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ZEROORMORE ).makeCanonical();
2059
2060       TokenTupleSet tts      = new TokenTupleSet( tt     ).makeCanonical();
2061       TokenTupleSet ttsPlus  = new TokenTupleSet( ttPlus ).makeCanonical();
2062       TokenTupleSet ttsStar  = new TokenTupleSet( ttStar ).makeCanonical();
2063       TokenTupleSet ttsEmpty = new TokenTupleSet(        ).makeCanonical();
2064
2065       if( hrn.isFlagged() || hrn.isParameter() ) {
2066         HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
2067         subWorkSet.add( tts     );
2068         subWorkSet.add( ttsPlus );
2069         subWorkSet.add( ttsStar );
2070         workSet.put( hrn, subWorkSet );
2071
2072         hrn.setAlphaNew( new ReachabilitySet( tts ).makeCanonical() );
2073       } else {
2074         hrn.setAlphaNew( new ReachabilitySet( ttsEmpty ).makeCanonical() );
2075       }
2076     }
2077
2078     // then propagate tokens forward one step at a time
2079     while( !workSet.isEmpty() ) {
2080       HeapRegionNode hrn = workSet.keySet().iterator().next();
2081
2082       HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
2083       assert subWorkSet != null;
2084
2085       if( subWorkSet.isEmpty() ) {
2086         // we're currently done with sub work at this heap region, although
2087         // more work may get queued up later, but remove it for now and continue
2088         workSet.remove( hrn );
2089         continue;
2090       }
2091
2092       TokenTupleSet tts = subWorkSet.iterator().next();
2093       subWorkSet.remove( tts );
2094
2095       // try to push this TokenTupleSet over all outgoing edges
2096       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencees();
2097       while( itrRes.hasNext() ) {
2098         ReferenceEdge edge = itrRes.next();
2099
2100         if( edge.getBeta().containsSuperSet( tts ) ) {
2101           HeapRegionNode dst = edge.getDst();
2102
2103           // make a set of possible contributions this token
2104           // might have on the alpha set here
2105           HashSet<TokenTupleSet> ttsNewSet = new HashSet<TokenTupleSet>();
2106
2107           Iterator<TokenTupleSet> itrDstAlphaNew = dst.getAlphaNew().iterator();
2108           while( itrDstAlphaNew.hasNext() ) {
2109             TokenTupleSet ttsDstAlphaNew = itrDstAlphaNew.next();
2110             ttsNewSet.add( tts.unionUpArity( ttsDstAlphaNew ) );
2111           }
2112
2113           // only add this to the dst alpha new if it is in the beta of
2114           // the edge we crossed to get here, and then only continue the
2115           // propagation if it isn't already in the dst alpha new
2116           Iterator<TokenTupleSet> itrNewSet = ttsNewSet.iterator();
2117           while( itrNewSet.hasNext() ) {
2118             TokenTupleSet ttsNew = itrNewSet.next();
2119
2120             if( edge.getBeta().containsSuperSet( ttsNew ) &&
2121                 !dst.getAlphaNew().contains( ttsNew ) ) {
2122
2123               // okay, this is a valid propagation, and add to the
2124               // work set to further propagate it
2125               dst.setAlphaNew( dst.getAlphaNew().union( ttsNew ) );
2126
2127               HashSet<TokenTupleSet> subWorkSetDst = workSet.get( dst );
2128               if( subWorkSetDst == null ) {
2129                 subWorkSetDst = new HashSet<TokenTupleSet>();
2130               }
2131
2132               subWorkSetDst.add( ttsNew );
2133               workSet.put( dst, subWorkSetDst );
2134             }
2135           }
2136         }
2137       }
2138     }
2139
2140     // now prepare work sets to propagate token sets backwards
2141     // from heap regions across all edges
2142     assert workSet.isEmpty();
2143     hrns = id2hrn.entrySet();
2144     itrHrns = hrns.iterator();
2145     while( itrHrns.hasNext() ) {
2146       Map.Entry me = (Map.Entry)itrHrns.next();
2147       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2148
2149       HashSet<TokenTupleSet> subWorkSet = new HashSet<TokenTupleSet>();
2150
2151       Iterator<TokenTupleSet> itrAlphaNewSets = hrn.getAlphaNew().iterator();
2152       while( itrAlphaNewSets.hasNext() ) {
2153         TokenTupleSet tts = itrAlphaNewSets.next();
2154         subWorkSet.add( tts );
2155       }
2156
2157       workSet.put( hrn, subWorkSet );
2158     }
2159
2160     // propagate token sets backwards across edges one step at a time
2161     while( !workSet.isEmpty() ) {
2162       HeapRegionNode hrn = workSet.keySet().iterator().next();
2163
2164       HashSet<TokenTupleSet> subWorkSet = workSet.get( hrn );
2165       assert subWorkSet != null;
2166
2167       if( subWorkSet.isEmpty() ) {
2168         // we're currently done with sub work at this heap region, although
2169         // more work may get queued up later, but remove it for now and continue
2170         workSet.remove( hrn );
2171         continue;
2172       }
2173
2174       TokenTupleSet tts = subWorkSet.iterator().next();
2175       subWorkSet.remove( tts );
2176
2177       // try to push this TokenTupleSet back up incoming edges
2178       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2179       while( itrRes.hasNext() ) {
2180         ReferenceEdge edge = itrRes.next();
2181         if( edge.getBeta().containsWithZeroes( tts ) &&
2182             !edge.getBetaNew().contains( tts ) ) {
2183           // okay, this is a valid propagation, and add to the
2184           // work set to further propagate it
2185           edge.setBetaNew( edge.getBetaNew().union( tts ) );
2186
2187           OwnershipNode src = edge.getSrc();
2188           if( src instanceof HeapRegionNode ) {
2189
2190             HashSet<TokenTupleSet> subWorkSetSrc = workSet.get( (HeapRegionNode) src );
2191             if( subWorkSetSrc == null ) {
2192               subWorkSetSrc = new HashSet<TokenTupleSet>();
2193             }
2194
2195             subWorkSetSrc.add( tts );
2196             workSet.put( (HeapRegionNode) src, subWorkSetSrc );
2197           }
2198         }
2199       }
2200     }
2201
2202     // apply alphaNew and betaNew to all nodes and edges
2203     HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
2204
2205     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2206     while( nodeItr.hasNext() ) {
2207       HeapRegionNode hrn = nodeItr.next();
2208       hrn.applyAlphaNew();
2209       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2210       while( itrRes.hasNext() ) {
2211         res.add( itrRes.next() );
2212       }
2213     }
2214
2215     Iterator<ReferenceEdge> edgeItr = res.iterator();
2216     while( edgeItr.hasNext() ) {
2217       edgeItr.next().applyBetaNew();
2218     }
2219   }
2220
2221
2222
2223   ////////////////////////////////////////////////////
2224   // in merge() and equals() methods the suffix A
2225   // represents the passed in graph and the suffix
2226   // B refers to the graph in this object
2227   // Merging means to take the incoming graph A and
2228   // merge it into B, so after the operation graph B
2229   // is the final result.
2230   ////////////////////////////////////////////////////
2231   public void merge(OwnershipGraph og) {
2232
2233     if( og == null ) {
2234       return;
2235     }
2236
2237     mergeOwnershipNodes(og);
2238     mergeReferenceEdges(og);
2239     mergeId2paramIndex(og);
2240     mergeAllocationSites(og);
2241   }
2242
2243
2244   protected void mergeOwnershipNodes(OwnershipGraph og) {
2245     Set sA = og.id2hrn.entrySet();
2246     Iterator iA = sA.iterator();
2247     while( iA.hasNext() ) {
2248       Map.Entry meA  = (Map.Entry)iA.next();
2249       Integer idA  = (Integer)        meA.getKey();
2250       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2251
2252       // if this graph doesn't have a node the
2253       // incoming graph has, allocate it
2254       if( !id2hrn.containsKey(idA) ) {
2255         HeapRegionNode hrnB = hrnA.copy();
2256         id2hrn.put(idA, hrnB);
2257
2258       } else {
2259         // otherwise this is a node present in both graphs
2260         // so make the new reachability set a union of the
2261         // nodes' reachability sets
2262         HeapRegionNode hrnB = id2hrn.get(idA);
2263         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
2264       }
2265     }
2266
2267     // now add any label nodes that are in graph B but
2268     // not in A
2269     sA = og.td2ln.entrySet();
2270     iA = sA.iterator();
2271     while( iA.hasNext() ) {
2272       Map.Entry meA = (Map.Entry)iA.next();
2273       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2274       LabelNode lnA = (LabelNode)      meA.getValue();
2275
2276       // if the label doesn't exist in B, allocate and add it
2277       LabelNode lnB = getLabelNodeFromTemp(tdA);
2278     }
2279   }
2280
2281   protected void mergeReferenceEdges(OwnershipGraph og) {
2282
2283     // heap regions
2284     Set sA = og.id2hrn.entrySet();
2285     Iterator iA = sA.iterator();
2286     while( iA.hasNext() ) {
2287       Map.Entry meA  = (Map.Entry)iA.next();
2288       Integer idA  = (Integer)        meA.getKey();
2289       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2290
2291       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2292       while( heapRegionsItrA.hasNext() ) {
2293         ReferenceEdge edgeA     = heapRegionsItrA.next();
2294         HeapRegionNode hrnChildA = edgeA.getDst();
2295         Integer idChildA  = hrnChildA.getID();
2296
2297         // at this point we know an edge in graph A exists
2298         // idA -> idChildA, does this exist in B?
2299         assert id2hrn.containsKey(idA);
2300         HeapRegionNode hrnB        = id2hrn.get(idA);
2301         ReferenceEdge edgeToMerge = null;
2302
2303         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2304         while( heapRegionsItrB.hasNext() &&
2305                edgeToMerge == null          ) {
2306
2307           ReferenceEdge edgeB     = heapRegionsItrB.next();
2308           HeapRegionNode hrnChildB = edgeB.getDst();
2309           Integer idChildB  = hrnChildB.getID();
2310
2311           // don't use the ReferenceEdge.equals() here because
2312           // we're talking about existence between graphs
2313           if( idChildB.equals(idChildA) &&
2314               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2315             edgeToMerge = edgeB;
2316           }
2317         }
2318
2319         // if the edge from A was not found in B,
2320         // add it to B.
2321         if( edgeToMerge == null ) {
2322           assert id2hrn.containsKey(idChildA);
2323           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2324           edgeToMerge = edgeA.copy();
2325           edgeToMerge.setSrc(hrnB);
2326           edgeToMerge.setDst(hrnChildB);
2327           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
2328         }
2329         // otherwise, the edge already existed in both graphs
2330         // so merge their reachability sets
2331         else {
2332           // just replace this beta set with the union
2333           assert edgeToMerge != null;
2334           edgeToMerge.setBeta(
2335             edgeToMerge.getBeta().union(edgeA.getBeta() )
2336             );
2337           if( !edgeA.isInitialParamReflexive() ) {
2338             edgeToMerge.setIsInitialParamReflexive(false);
2339           }
2340         }
2341       }
2342     }
2343
2344     // and then again with label nodes
2345     sA = og.td2ln.entrySet();
2346     iA = sA.iterator();
2347     while( iA.hasNext() ) {
2348       Map.Entry meA = (Map.Entry)iA.next();
2349       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2350       LabelNode lnA = (LabelNode)      meA.getValue();
2351
2352       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
2353       while( heapRegionsItrA.hasNext() ) {
2354         ReferenceEdge edgeA     = heapRegionsItrA.next();
2355         HeapRegionNode hrnChildA = edgeA.getDst();
2356         Integer idChildA  = hrnChildA.getID();
2357
2358         // at this point we know an edge in graph A exists
2359         // tdA -> idChildA, does this exist in B?
2360         assert td2ln.containsKey(tdA);
2361         LabelNode lnB         = td2ln.get(tdA);
2362         ReferenceEdge edgeToMerge = null;
2363
2364         // labels never have edges with a field
2365         //assert edgeA.getFieldDesc() == null;
2366
2367         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
2368         while( heapRegionsItrB.hasNext() &&
2369                edgeToMerge == null          ) {
2370
2371           ReferenceEdge edgeB     = heapRegionsItrB.next();
2372           HeapRegionNode hrnChildB = edgeB.getDst();
2373           Integer idChildB  = hrnChildB.getID();
2374
2375           // labels never have edges with a field
2376           //assert edgeB.getFieldDesc() == null;
2377
2378           // don't use the ReferenceEdge.equals() here because
2379           // we're talking about existence between graphs
2380           if( idChildB.equals(idChildA) &&
2381               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
2382             edgeToMerge = edgeB;
2383           }
2384         }
2385
2386         // if the edge from A was not found in B,
2387         // add it to B.
2388         if( edgeToMerge == null ) {
2389           assert id2hrn.containsKey(idChildA);
2390           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2391           edgeToMerge = edgeA.copy();
2392           edgeToMerge.setSrc(lnB);
2393           edgeToMerge.setDst(hrnChildB);
2394           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
2395         }
2396         // otherwise, the edge already existed in both graphs
2397         // so merge their reachability sets
2398         else {
2399           // just replace this beta set with the union
2400           edgeToMerge.setBeta(
2401             edgeToMerge.getBeta().union(edgeA.getBeta() )
2402             );
2403           if( !edgeA.isInitialParamReflexive() ) {
2404             edgeToMerge.setIsInitialParamReflexive(false);
2405           }
2406         }
2407       }
2408     }
2409   }
2410
2411   // you should only merge ownership graphs that have the
2412   // same number of parameters, or if one or both parameter
2413   // index tables are empty
2414   protected void mergeId2paramIndex(OwnershipGraph og) {
2415     if( id2paramIndexSet.size() == 0 ) {
2416       id2paramIndexSet = og.id2paramIndexSet;
2417       paramIndex2id    = og.paramIndex2id;
2418       paramIndex2tdQ   = og.paramIndex2tdQ;
2419       return;
2420     }
2421
2422     if( og.id2paramIndexSet.size() == 0 ) {
2423       return;
2424     }
2425
2426     assert id2paramIndexSet.size() == og.id2paramIndexSet.size();
2427   }
2428
2429   protected void mergeAllocationSites(OwnershipGraph og) {
2430     allocationSites.addAll(og.allocationSites);
2431   }
2432
2433
2434
2435   // it is necessary in the equals() member functions
2436   // to "check both ways" when comparing the data
2437   // structures of two graphs.  For instance, if all
2438   // edges between heap region nodes in graph A are
2439   // present and equal in graph B it is not sufficient
2440   // to say the graphs are equal.  Consider that there
2441   // may be edges in graph B that are not in graph A.
2442   // the only way to know that all edges in both graphs
2443   // are equally present is to iterate over both data
2444   // structures and compare against the other graph.
2445   public boolean equals(OwnershipGraph og) {
2446
2447     if( og == null ) {
2448       return false;
2449     }
2450
2451     if( !areHeapRegionNodesEqual(og) ) {
2452       return false;
2453     }
2454
2455     if( !areLabelNodesEqual(og) ) {
2456       return false;
2457     }
2458
2459     if( !areReferenceEdgesEqual(og) ) {
2460       return false;
2461     }
2462
2463     if( !areId2paramIndexEqual(og) ) {
2464       return false;
2465     }
2466
2467     // if everything is equal up to this point,
2468     // assert that allocationSites is also equal--
2469     // this data is redundant and kept for efficiency
2470     assert allocationSites.equals(og.allocationSites);
2471
2472     return true;
2473   }
2474
2475   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2476
2477     if( !areallHRNinAalsoinBandequal(this, og) ) {
2478       return false;
2479     }
2480
2481     if( !areallHRNinAalsoinBandequal(og, this) ) {
2482       return false;
2483     }
2484
2485     return true;
2486   }
2487
2488   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2489                                                        OwnershipGraph ogB) {
2490     Set sA = ogA.id2hrn.entrySet();
2491     Iterator iA = sA.iterator();
2492     while( iA.hasNext() ) {
2493       Map.Entry meA  = (Map.Entry)iA.next();
2494       Integer idA  = (Integer)        meA.getKey();
2495       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2496
2497       if( !ogB.id2hrn.containsKey(idA) ) {
2498         return false;
2499       }
2500
2501       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2502       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2503         return false;
2504       }
2505     }
2506
2507     return true;
2508   }
2509
2510
2511   protected boolean areLabelNodesEqual(OwnershipGraph og) {
2512
2513     if( !areallLNinAalsoinBandequal(this, og) ) {
2514       return false;
2515     }
2516
2517     if( !areallLNinAalsoinBandequal(og, this) ) {
2518       return false;
2519     }
2520
2521     return true;
2522   }
2523
2524   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2525                                                       OwnershipGraph ogB) {
2526     Set sA = ogA.td2ln.entrySet();
2527     Iterator iA = sA.iterator();
2528     while( iA.hasNext() ) {
2529       Map.Entry meA = (Map.Entry)iA.next();
2530       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2531
2532       if( !ogB.td2ln.containsKey(tdA) ) {
2533         return false;
2534       }
2535     }
2536
2537     return true;
2538   }
2539
2540
2541   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2542     if( !areallREinAandBequal(this, og) ) {
2543       return false;
2544     }
2545
2546     return true;
2547   }
2548
2549   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2550                                                 OwnershipGraph ogB) {
2551
2552     // check all the heap region->heap region edges
2553     Set sA = ogA.id2hrn.entrySet();
2554     Iterator iA = sA.iterator();
2555     while( iA.hasNext() ) {
2556       Map.Entry meA  = (Map.Entry)iA.next();
2557       Integer idA  = (Integer)        meA.getKey();
2558       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2559
2560       // we should have already checked that the same
2561       // heap regions exist in both graphs
2562       assert ogB.id2hrn.containsKey(idA);
2563
2564       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2565         return false;
2566       }
2567
2568       // then check every edge in B for presence in A, starting
2569       // from the same parent HeapRegionNode
2570       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2571
2572       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2573         return false;
2574       }
2575     }
2576
2577     // then check all the label->heap region edges
2578     sA = ogA.td2ln.entrySet();
2579     iA = sA.iterator();
2580     while( iA.hasNext() ) {
2581       Map.Entry meA = (Map.Entry)iA.next();
2582       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2583       LabelNode lnA = (LabelNode)      meA.getValue();
2584
2585       // we should have already checked that the same
2586       // label nodes exist in both graphs
2587       assert ogB.td2ln.containsKey(tdA);
2588
2589       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2590         return false;
2591       }
2592
2593       // then check every edge in B for presence in A, starting
2594       // from the same parent LabelNode
2595       LabelNode lnB = ogB.td2ln.get(tdA);
2596
2597       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2598         return false;
2599       }
2600     }
2601
2602     return true;
2603   }
2604
2605
2606   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2607                                                  OwnershipNode onA,
2608                                                  OwnershipGraph ogB) {
2609
2610     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2611     while( itrA.hasNext() ) {
2612       ReferenceEdge edgeA     = itrA.next();
2613       HeapRegionNode hrnChildA = edgeA.getDst();
2614       Integer idChildA  = hrnChildA.getID();
2615
2616       assert ogB.id2hrn.containsKey(idChildA);
2617
2618       // at this point we know an edge in graph A exists
2619       // onA -> idChildA, does this exact edge exist in B?
2620       boolean edgeFound = false;
2621
2622       OwnershipNode onB = null;
2623       if( onA instanceof HeapRegionNode ) {
2624         HeapRegionNode hrnA = (HeapRegionNode) onA;
2625         onB = ogB.id2hrn.get(hrnA.getID() );
2626       } else {
2627         LabelNode lnA = (LabelNode) onA;
2628         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2629       }
2630
2631       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2632       while( itrB.hasNext() ) {
2633         ReferenceEdge edgeB     = itrB.next();
2634         HeapRegionNode hrnChildB = edgeB.getDst();
2635         Integer idChildB  = hrnChildB.getID();
2636
2637         if( idChildA.equals(idChildB) &&
2638             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2639
2640           // there is an edge in the right place with the right field,
2641           // but do they have the same attributes?
2642           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2643
2644             edgeFound = true;
2645             //} else {
2646             //return false;
2647           }
2648         }
2649       }
2650
2651       if( !edgeFound ) {
2652         return false;
2653       }
2654     }
2655
2656     return true;
2657   }
2658
2659
2660   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2661     return id2paramIndexSet.size() == og.id2paramIndexSet.size();
2662   }
2663
2664   public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2665
2666     // get parameter's heap region
2667     assert paramIndex2id.containsKey(paramIndex1);
2668     Integer idParam1 = paramIndex2id.get(paramIndex1);
2669
2670     assert id2hrn.containsKey(idParam1);
2671     HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2672     assert hrnParam1 != null;
2673
2674     // get tokens for this parameter
2675     TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2676                                    true,
2677                                    TokenTuple.ARITY_ONE).makeCanonical();
2678
2679     TokenTuple pPlus1 = new TokenTuple(hrnParam1.getID(),
2680                                        true,
2681                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
2682
2683     TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2684                                        true,
2685                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2686
2687
2688     // get tokens for the other parameter
2689     assert paramIndex2id.containsKey(paramIndex2);
2690     Integer idParam2 = paramIndex2id.get(paramIndex2);
2691
2692     assert id2hrn.containsKey(idParam2);
2693     HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2694     assert hrnParam2 != null;
2695
2696     TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2697                                    true,
2698                                    TokenTuple.ARITY_ONE).makeCanonical();
2699
2700     TokenTuple pPlus2 = new TokenTuple(hrnParam2.getID(),
2701                                        true,
2702                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
2703
2704     TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2705                                        true,
2706                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2707
2708
2709     // get special label p_q for first parameter
2710     TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2711     assert tdParamQ1 != null;
2712     LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2713     assert lnParamQ1 != null;
2714
2715     // then get the edge from label q to parameter's hrn
2716     ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2717     assert edgeSpecialQ1 != null;
2718
2719     // if the beta of this edge has tokens from both parameters in one
2720     // token tuple set, then there is a potential alias between them
2721     ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2722     assert beta1 != null;
2723
2724     if( beta1.containsTupleSetWithBoth(p1,     p2) ) {
2725       return true;
2726     }
2727     if( beta1.containsTupleSetWithBoth(pPlus1, p2) ) {
2728       return true;
2729     }
2730     if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2731       return true;
2732     }
2733     if( beta1.containsTupleSetWithBoth(p1,     pPlus2) ) {
2734       return true;
2735     }
2736     if( beta1.containsTupleSetWithBoth(pPlus1, pPlus2) ) {
2737       return true;
2738     }
2739     if( beta1.containsTupleSetWithBoth(pStar1, pPlus2) ) {
2740       return true;
2741     }
2742     if( beta1.containsTupleSetWithBoth(p1,     pStar2) ) {
2743       return true;
2744     }
2745     if( beta1.containsTupleSetWithBoth(pPlus1, pStar2) ) {
2746       return true;
2747     }
2748     if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2749       return true;
2750     }
2751
2752     return false;
2753   }
2754
2755
2756   public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2757
2758     // get parameter's heap region
2759     assert paramIndex2id.containsKey(paramIndex);
2760     Integer idParam = paramIndex2id.get(paramIndex);
2761
2762     assert id2hrn.containsKey(idParam);
2763     HeapRegionNode hrnParam = id2hrn.get(idParam);
2764     assert hrnParam != null;
2765
2766     // get tokens for this parameter
2767     TokenTuple p = new TokenTuple(hrnParam.getID(),
2768                                   true,
2769                                   TokenTuple.ARITY_ONE).makeCanonical();
2770
2771     TokenTuple pPlus = new TokenTuple(hrnParam.getID(),
2772                                       true,
2773                                       TokenTuple.ARITY_ONEORMORE).makeCanonical();
2774
2775     TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2776                                       true,
2777                                       TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2778
2779     // get special label p_q
2780     TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2781     assert tdParamQ != null;
2782     LabelNode lnParamQ = td2ln.get(tdParamQ);
2783     assert lnParamQ != null;
2784
2785     // then get the edge from label q to parameter's hrn
2786     ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2787     assert edgeSpecialQ != null;
2788
2789     // look through this beta set for potential aliases
2790     ReachabilitySet beta = edgeSpecialQ.getBeta();
2791     assert beta != null;
2792
2793
2794     // get tokens for summary node
2795     TokenTuple gs = new TokenTuple(as.getSummary(),
2796                                    true,
2797                                    TokenTuple.ARITY_ONE).makeCanonical();
2798
2799     TokenTuple gsPlus = new TokenTuple(as.getSummary(),
2800                                        true,
2801                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
2802
2803     TokenTuple gsStar = new TokenTuple(as.getSummary(),
2804                                        true,
2805                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2806
2807
2808     if( beta.containsTupleSetWithBoth(p,     gs) ) {
2809       return true;
2810     }
2811     if( beta.containsTupleSetWithBoth(pPlus, gs) ) {
2812       return true;
2813     }
2814     if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2815       return true;
2816     }
2817     if( beta.containsTupleSetWithBoth(p,     gsPlus) ) {
2818       return true;
2819     }
2820     if( beta.containsTupleSetWithBoth(pPlus, gsPlus) ) {
2821       return true;
2822     }
2823     if( beta.containsTupleSetWithBoth(pStar, gsPlus) ) {
2824       return true;
2825     }
2826     if( beta.containsTupleSetWithBoth(p,     gsStar) ) {
2827       return true;
2828     }
2829     if( beta.containsTupleSetWithBoth(pPlus, gsStar) ) {
2830       return true;
2831     }
2832     if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2833       return true;
2834     }
2835
2836     // check for other nodes
2837     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2838
2839       // the other nodes of an allocation site are single, no plus
2840       TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2841                                      false,
2842                                      TokenTuple.ARITY_ONE).makeCanonical();
2843
2844       TokenTuple giStar = new TokenTuple(as.getIthOldest(i),
2845                                          false,
2846                                          TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2847
2848       if( beta.containsTupleSetWithBoth(p,     gi) ) {
2849         return true;
2850       }
2851       if( beta.containsTupleSetWithBoth(pPlus, gi) ) {
2852         return true;
2853       }
2854       if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2855         return true;
2856       }
2857       if( beta.containsTupleSetWithBoth(p,     giStar) ) {
2858         return true;
2859       }
2860       if( beta.containsTupleSetWithBoth(pPlus, giStar) ) {
2861         return true;
2862       }
2863       if( beta.containsTupleSetWithBoth(pStar, giStar) ) {
2864         return true;
2865       }
2866     }
2867
2868     return false;
2869   }
2870
2871
2872   public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2873
2874     // get tokens for summary nodes
2875     TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2876                                     true,
2877                                     TokenTuple.ARITY_ONE).makeCanonical();
2878
2879     TokenTuple gsPlus1 = new TokenTuple(as1.getSummary(),
2880                                         true,
2881                                         TokenTuple.ARITY_ONEORMORE).makeCanonical();
2882
2883     TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2884                                         true,
2885                                         TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2886
2887     // get summary node's alpha
2888     Integer idSum1 = as1.getSummary();
2889     assert id2hrn.containsKey(idSum1);
2890     HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2891     assert hrnSum1 != null;
2892     ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2893     assert alphaSum1 != null;
2894
2895
2896     // and for the other one
2897     TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2898                                     true,
2899                                     TokenTuple.ARITY_ONE).makeCanonical();
2900
2901     TokenTuple gsPlus2 = new TokenTuple(as2.getSummary(),
2902                                         true,
2903                                         TokenTuple.ARITY_ONEORMORE).makeCanonical();
2904
2905     TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2906                                         true,
2907                                         TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2908
2909     // get summary node's alpha
2910     Integer idSum2 = as2.getSummary();
2911     assert id2hrn.containsKey(idSum2);
2912     HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2913     assert hrnSum2 != null;
2914     ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2915     assert alphaSum2 != null;
2916
2917     // does either one report reachability from the other tokens?
2918     if( alphaSum1.containsTuple(gsPlus2) ) {
2919       return true;
2920     }
2921     if( alphaSum1.containsTuple(gsStar2) ) {
2922       return true;
2923     }
2924     if( alphaSum2.containsTuple(gsPlus1) ) {
2925       return true;
2926     }
2927     if( alphaSum2.containsTuple(gsStar1) ) {
2928       return true;
2929     }
2930
2931     // only check ONE token if they are different sites
2932     if( as1 != as2 ) {
2933       if( alphaSum1.containsTuple(gs2) ) {
2934         return true;
2935       }
2936       if( alphaSum2.containsTuple(gs1) ) {
2937         return true;
2938       }
2939     }
2940
2941
2942     // check sum2 against alloc1 nodes
2943     for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2944       Integer idI1 = as1.getIthOldest(i);
2945       assert id2hrn.containsKey(idI1);
2946       HeapRegionNode hrnI1 = id2hrn.get(idI1);
2947       assert hrnI1 != null;
2948       ReachabilitySet alphaI1 = hrnI1.getAlpha();
2949       assert alphaI1 != null;
2950
2951       // the other nodes of an allocation site are single, no stars
2952       TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2953                                       false,
2954                                       TokenTuple.ARITY_ONE).makeCanonical();
2955
2956       TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(i),
2957                                           false,
2958                                           TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2959
2960       if( alphaSum2.containsTuple(gi1) ) {
2961         return true;
2962       }
2963       if( alphaSum2.containsTuple(giStar1) ) {
2964         return true;
2965       }
2966       if(   alphaI1.containsTuple(gs2) ) {
2967         return true;
2968       }
2969       if(   alphaI1.containsTuple(gsPlus2) ) {
2970         return true;
2971       }
2972       if(   alphaI1.containsTuple(gsStar2) ) {
2973         return true;
2974       }
2975     }
2976
2977     // check sum1 against alloc2 nodes
2978     for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2979       Integer idI2 = as2.getIthOldest(i);
2980       assert id2hrn.containsKey(idI2);
2981       HeapRegionNode hrnI2 = id2hrn.get(idI2);
2982       assert hrnI2 != null;
2983       ReachabilitySet alphaI2 = hrnI2.getAlpha();
2984       assert alphaI2 != null;
2985
2986       TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2987                                       false,
2988                                       TokenTuple.ARITY_ONE).makeCanonical();
2989
2990       TokenTuple giStar2 = new TokenTuple(as2.getIthOldest(i),
2991                                           false,
2992                                           TokenTuple.ARITY_ZEROORMORE).makeCanonical();
2993
2994       if( alphaSum1.containsTuple(gi2) ) {
2995         return true;
2996       }
2997       if( alphaSum1.containsTuple(giStar2) ) {
2998         return true;
2999       }
3000       if(   alphaI2.containsTuple(gs1) ) {
3001         return true;
3002       }
3003       if(   alphaI2.containsTuple(gsPlus1) ) {
3004         return true;
3005       }
3006       if(   alphaI2.containsTuple(gsStar1) ) {
3007         return true;
3008       }
3009
3010       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
3011       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
3012         Integer idI1 = as1.getIthOldest(j);
3013
3014         // if these are the same site, don't look for the same token, no alias.
3015         // different tokens of the same site could alias together though
3016         if( idI1 == idI2 ) {
3017           continue;
3018         }
3019
3020         HeapRegionNode hrnI1 = id2hrn.get(idI1);
3021         ReachabilitySet alphaI1 = hrnI1.getAlpha();
3022         TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
3023                                         false,
3024                                         TokenTuple.ARITY_ONE).makeCanonical();
3025
3026         TokenTuple giStar1 = new TokenTuple(as1.getIthOldest(j),
3027                                             false,
3028                                             TokenTuple.ARITY_ZEROORMORE).makeCanonical();
3029
3030         if( alphaI2.containsTuple(gi1) ) {
3031           return true;
3032         }
3033         if( alphaI2.containsTuple(giStar1) ) {
3034           return true;
3035         }
3036         if( alphaI1.containsTuple(gi2) ) {
3037           return true;
3038         }
3039         if( alphaI1.containsTuple(giStar2) ) {
3040           return true;
3041         }
3042       }
3043     }
3044
3045     return false;
3046   }
3047
3048
3049   // for writing ownership graphs to dot files
3050   public void writeGraph(MethodContext mc,
3051                          FlatNode fn,
3052                          boolean writeLabels,
3053                          boolean labelSelect,
3054                          boolean pruneGarbage,
3055                          boolean writeReferencers,
3056                          boolean writeParamMappings
3057                          ) throws java.io.IOException {
3058     writeGraph(
3059       mc.toString() +
3060       fn.toString(),
3061       writeLabels,
3062       labelSelect,
3063       pruneGarbage,
3064       writeReferencers,
3065       writeParamMappings
3066       );
3067   }
3068
3069   public void writeGraph(MethodContext mc,
3070                          boolean writeLabels,
3071                          boolean labelSelect,
3072                          boolean pruneGarbage,
3073                          boolean writeReferencers,
3074                          boolean writeParamMappings
3075                          ) throws java.io.IOException {
3076
3077     writeGraph(mc+"COMPLETE",
3078                writeLabels,
3079                labelSelect,
3080                pruneGarbage,
3081                writeReferencers,
3082                writeParamMappings
3083                );
3084   }
3085
3086   public void writeGraph(MethodContext mc,
3087                          Integer numUpdate,
3088                          boolean writeLabels,
3089                          boolean labelSelect,
3090                          boolean pruneGarbage,
3091                          boolean writeReferencers,
3092                          boolean writeParamMappings
3093                          ) throws java.io.IOException {
3094
3095     writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
3096                writeLabels,
3097                labelSelect,
3098                pruneGarbage,
3099                writeReferencers,
3100                writeParamMappings
3101                );
3102   }
3103
3104   public void writeGraph(String graphName,
3105                          boolean writeLabels,
3106                          boolean labelSelect,
3107                          boolean pruneGarbage,
3108                          boolean writeReferencers,
3109                          boolean writeParamMappings
3110                          ) throws java.io.IOException {
3111
3112     // remove all non-word characters from the graph name so
3113     // the filename and identifier in dot don't cause errors
3114     graphName = graphName.replaceAll("[\\W]", "");
3115
3116     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
3117     bw.write("digraph "+graphName+" {\n");
3118
3119     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3120
3121     // then visit every heap region node
3122     Set s = id2hrn.entrySet();
3123     Iterator i = s.iterator();
3124     while( i.hasNext() ) {
3125       Map.Entry me  = (Map.Entry)i.next();
3126       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3127       if( !pruneGarbage ||
3128           hrn.isFlagged() ||
3129           hrn.getDescription().startsWith("param")
3130           ) {
3131
3132         if( !visited.contains(hrn) ) {
3133           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
3134                                   hrn,
3135                                   bw,
3136                                   null,
3137                                   visited,
3138                                   writeReferencers);
3139         }
3140       }
3141     }
3142
3143     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
3144
3145     if( writeParamMappings ) {
3146       Set df = paramIndex2id.entrySet();
3147       Iterator ih = df.iterator();
3148       while( ih.hasNext() ) {
3149         Map.Entry meh = (Map.Entry)ih.next();
3150         Integer pi = (Integer) meh.getKey();
3151         Integer id = (Integer) meh.getValue();
3152         bw.write("  pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
3153       }
3154     }
3155
3156     // then visit every label node, useful for debugging
3157     if( writeLabels ) {
3158       s = td2ln.entrySet();
3159       i = s.iterator();
3160       while( i.hasNext() ) {
3161         Map.Entry me = (Map.Entry)i.next();
3162         LabelNode ln = (LabelNode) me.getValue();
3163
3164         if( labelSelect ) {
3165           String labelStr = ln.getTempDescriptorString();
3166           if( labelStr.startsWith("___temp") ||
3167               labelStr.startsWith("___dst") ||
3168               labelStr.startsWith("___srctmp") ||
3169               labelStr.startsWith("___neverused")   ) {
3170             continue;
3171           }
3172         }
3173
3174         //bw.write("  "+ln.toString() + ";\n");
3175
3176         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
3177         while( heapRegionsItr.hasNext() ) {
3178           ReferenceEdge edge = heapRegionsItr.next();
3179           HeapRegionNode hrn  = edge.getDst();
3180
3181           if( pruneGarbage && !visited.contains(hrn) ) {
3182             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
3183                                     hrn,
3184                                     bw,
3185                                     null,
3186                                     visited,
3187                                     writeReferencers);
3188           }
3189
3190           bw.write("  "        + ln.toString() +
3191                    " -> "      + hrn.toString() +
3192                    "[label=\"" + edge.toGraphEdgeString() +
3193                    "\",decorate];\n");
3194         }
3195       }
3196     }
3197
3198
3199     bw.write("}\n");
3200     bw.close();
3201   }
3202
3203   protected void traverseHeapRegionNodes(int mode,
3204                                          HeapRegionNode hrn,
3205                                          BufferedWriter bw,
3206                                          TempDescriptor td,
3207                                          HashSet<HeapRegionNode> visited,
3208                                          boolean writeReferencers
3209                                          ) throws java.io.IOException {
3210
3211     if( visited.contains(hrn) ) {
3212       return;
3213     }
3214     visited.add(hrn);
3215
3216     switch( mode ) {
3217     case VISIT_HRN_WRITE_FULL:
3218
3219       String attributes = "[";
3220
3221       if( hrn.isSingleObject() ) {
3222         attributes += "shape=box";
3223       } else {
3224         attributes += "shape=Msquare";
3225       }
3226
3227       if( hrn.isFlagged() ) {
3228         attributes += ",style=filled,fillcolor=lightgrey";
3229       }
3230
3231       attributes += ",label=\"ID"        +
3232                     hrn.getID()          +
3233                     "\\n"                +
3234                     hrn.getDescription() +
3235                     "\\n"                +
3236                     hrn.getAlphaString() +
3237                     "\"]";
3238
3239       bw.write("  " + hrn.toString() + attributes + ";\n");
3240       break;
3241     }
3242
3243
3244     // useful for debugging
3245     if( writeReferencers ) {
3246       OwnershipNode onRef  = null;
3247       Iterator refItr = hrn.iteratorToReferencers();
3248       while( refItr.hasNext() ) {
3249         onRef = (OwnershipNode) refItr.next();
3250
3251         switch( mode ) {
3252         case VISIT_HRN_WRITE_FULL:
3253           bw.write("  "                    + hrn.toString() +
3254                    " -> "                  + onRef.toString() +
3255                    "[color=lightgray];\n");
3256           break;
3257         }
3258       }
3259     }
3260
3261     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
3262     while( childRegionsItr.hasNext() ) {
3263       ReferenceEdge edge     = childRegionsItr.next();
3264       HeapRegionNode hrnChild = edge.getDst();
3265
3266       switch( mode ) {
3267       case VISIT_HRN_WRITE_FULL:
3268         bw.write("  "        + hrn.toString() +
3269                  " -> "      + hrnChild.toString() +
3270                  "[label=\"" + edge.toGraphEdgeString() +
3271                  "\",decorate];\n");
3272         break;
3273       }
3274
3275       traverseHeapRegionNodes(mode,
3276                               hrnChild,
3277                               bw,
3278                               td,
3279                               visited,
3280                               writeReferencers);
3281     }
3282   }
3283 }