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