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