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
  12   // there was already one other very similar reason
  13   // for traversing heap nodes that is no longer needed
  14   // instead of writing a new heap region visitor, use
  15   // the existing method with a new mode to describe what
  16   // actions to take during the traversal
  17   protected static final int VISIT_HRN_WRITE_FULL = 0;
  18
  19
  20   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  21   public Hashtable<TempDescriptor, LabelNode     > td2ln;
  22   public Hashtable<Integer,        Integer       > id2paramIndex;
  23   public Hashtable<Integer,        Integer       > paramIndex2id;
  24   public Hashtable<Integer,        TempDescriptor> paramIndex2tdQ;
  25
  26   public HashSet<AllocationSite> allocationSites;
  27
  28
  29   public OwnershipGraph(int allocationDepth) {
  30     this.allocationDepth = allocationDepth;
  31
  32     id2hrn         = new Hashtable<Integer,        HeapRegionNode>();
  33     td2ln          = new Hashtable<TempDescriptor, LabelNode     >();
  34     id2paramIndex  = new Hashtable<Integer,        Integer       >();
  35     paramIndex2id  = new Hashtable<Integer,        Integer       >();
  36     paramIndex2tdQ = new Hashtable<Integer,        TempDescriptor>();
  37
  38     allocationSites = new HashSet <AllocationSite>();
  39   }
  40
  41
  42   // label nodes are much easier to deal with than
  43   // heap region nodes.  Whenever there is a request
  44   // for the label node that is associated with a
  45   // temp descriptor we can either find it or make a
  46   // new one and return it.  This is because temp
  47   // descriptors are globally unique and every label
  48   // node is mapped to exactly one temp descriptor.
  49   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  50     assert td != null;
  51
  52     if( !td2ln.containsKey(td) ) {
  53       td2ln.put(td, new LabelNode(td) );
  54     }
  55
  56     return td2ln.get(td);
  57   }
  58
  59
  60   // the reason for this method is to have the option
  61   // creating new heap regions with specific IDs, or
  62   // duplicating heap regions with specific IDs (especially
  63   // in the merge() operation) or to create new heap
  64   // regions with a new unique ID.
  65   protected HeapRegionNode
  66   createNewHeapRegionNode(Integer id,
  67                           boolean isSingleObject,
  68                           boolean isFlagged,
  69                           boolean isNewSummary,
  70                           boolean isParameter,
  71                           AllocationSite allocSite,
  72                           ReachabilitySet alpha,
  73                           String description) {
  74
  75     if( id == null ) {
  76       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  77     }
  78
  79     if( alpha == null ) {
  80       if( isFlagged || isParameter ) {
  81         alpha = new ReachabilitySet(new TokenTuple(id,
  82                                                    !isSingleObject,
  83                                                    TokenTuple.ARITY_ONE)
  84                                     ).makeCanonical();
  85       } else {
  86         alpha = new ReachabilitySet(new TokenTupleSet()
  87                                     ).makeCanonical();
  88       }
  89     }
  90
  91     HeapRegionNode hrn = new HeapRegionNode(id,
  92                                             isSingleObject,
  93                                             isFlagged,
  94                                             isNewSummary,
  95                                             allocSite,
  96                                             alpha,
  97                                             description);
  98     id2hrn.put(id, hrn);
  99     return hrn;
 100   }
 101
 102
 103
 104   ////////////////////////////////////////////////
 105   //
 106   //  Low-level referencee and referencer methods
 107   //
 108   //  These methods provide the lowest level for
 109   //  creating references between ownership nodes
 110   //  and handling the details of maintaining both
 111   //  list of referencers and referencees.
 112   //
 113   ////////////////////////////////////////////////
 114   protected void addReferenceEdge(OwnershipNode referencer,
 115                                   HeapRegionNode referencee,
 116                                   ReferenceEdge edge) {
 117     assert referencer != null;
 118     assert referencee != null;
 119     assert edge       != null;
 120     assert edge.getSrc() == referencer;
 121     assert edge.getDst() == referencee;
 122
 123     referencer.addReferencee(edge);
 124     referencee.addReferencer(edge);
 125   }
 126
 127   protected void removeReferenceEdge(OwnershipNode referencer,
 128                                      HeapRegionNode referencee,
 129                                      FieldDescriptor fieldDesc) {
 130     assert referencer != null;
 131     assert referencee != null;
 132
 133     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 134                                                    fieldDesc);
 135     assert edge != null;
 136     assert edge == referencee.getReferenceFrom(referencer,
 137                                                fieldDesc);
 138
 139     referencer.removeReferencee(edge);
 140     referencee.removeReferencer(edge);
 141   }
 142
 143   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 144                                          FieldDescriptor fieldDesc,
 145                                          boolean removeAll) {
 146     assert referencer != null;
 147
 148     // get a copy of the set to iterate over, otherwise
 149     // we will be trying to take apart the set as we
 150     // are iterating over it, which won't work
 151     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 152     while( i.hasNext() ) {
 153       ReferenceEdge edge = i.next();
 154
 155       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 156         HeapRegionNode referencee = edge.getDst();
 157
 158         removeReferenceEdge(referencer,
 159                             referencee,
 160                             edge.getFieldDesc() );
 161       }
 162     }
 163   }
 164
 165   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 166                                        FieldDescriptor fieldDesc,
 167                                        boolean removeAll) {
 168     assert referencee != null;
 169
 170     // get a copy of the set to iterate over, otherwise
 171     // we will be trying to take apart the set as we
 172     // are iterating over it, which won't work
 173     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 174     while( i.hasNext() ) {
 175       ReferenceEdge edge = i.next();
 176
 177       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 178         OwnershipNode referencer = edge.getSrc();
 179         removeReferenceEdge(referencer,
 180                             referencee,
 181                             edge.getFieldDesc() );
 182       }
 183     }
 184   }
 185
 186
 187   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
 188                                           ChangeTupleSet c0,
 189                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
 190                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
 191
 192     HashSet<HeapRegionNode> todoNodes
 193     = new HashSet<HeapRegionNode>();
 194     todoNodes.add(nPrime);
 195
 196     HashSet<ReferenceEdge> todoEdges
 197     = new HashSet<ReferenceEdge>();
 198
 199     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 200     = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 201     nodePlannedChanges.put(nPrime, c0);
 202
 203     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
 204     = new Hashtable<ReferenceEdge, ChangeTupleSet>();
 205
 206
 207     while( !todoNodes.isEmpty() ) {
 208       HeapRegionNode n = todoNodes.iterator().next();
 209       ChangeTupleSet C = nodePlannedChanges.get(n);
 210
 211       Iterator itrC = C.iterator();
 212       while( itrC.hasNext() ) {
 213         ChangeTuple c = (ChangeTuple) itrC.next();
 214
 215         if( n.getAlpha().contains(c.getSetToMatch() ) ) {
 216           ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
 217           n.setAlphaNew(n.getAlphaNew().union(withChange) );
 218           nodesWithNewAlpha.add(n);
 219         }
 220       }
 221
 222       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 223       while( referItr.hasNext() ) {
 224         ReferenceEdge edge = referItr.next();
 225         todoEdges.add(edge);
 226
 227         if( !edgePlannedChanges.containsKey(edge) ) {
 228           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
 229         }
 230
 231         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 232       }
 233
 234       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
 235       while( refeeItr.hasNext() ) {
 236         ReferenceEdge edgeF = refeeItr.next();
 237         HeapRegionNode m     = edgeF.getDst();
 238
 239         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 240
 241         Iterator<ChangeTuple> itrCprime = C.iterator();
 242         while( itrCprime.hasNext() ) {
 243           ChangeTuple c = itrCprime.next();
 244           if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
 245             changesToPass = changesToPass.union(c);
 246           }
 247         }
 248
 249         if( !changesToPass.isEmpty() ) {
 250           if( !nodePlannedChanges.containsKey(m) ) {
 251             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
 252           }
 253
 254           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
 255
 256           if( !changesToPass.isSubset(currentChanges) ) {
 257
 258             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 259             todoNodes.add(m);
 260           }
 261         }
 262       }
 263
 264       todoNodes.remove(n);
 265     }
 266
 267     propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
 268   }
 269
 270
 271   protected void propagateTokensOverEdges(
 272     HashSet<ReferenceEdge>                   todoEdges,
 273     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
 274     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
 275
 276
 277     while( !todoEdges.isEmpty() ) {
 278       ReferenceEdge edgeE = todoEdges.iterator().next();
 279       todoEdges.remove(edgeE);
 280
 281       if( !edgePlannedChanges.containsKey(edgeE) ) {
 282         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
 283       }
 284
 285       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
 286
 287       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 288
 289       Iterator<ChangeTuple> itrC = C.iterator();
 290       while( itrC.hasNext() ) {
 291         ChangeTuple c = itrC.next();
 292         if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
 293           ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
 294           edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
 295           edgesWithNewBeta.add(edgeE);
 296           changesToPass = changesToPass.union(c);
 297         }
 298       }
 299
 300       OwnershipNode onSrc = edgeE.getSrc();
 301
 302       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 303         HeapRegionNode n = (HeapRegionNode) onSrc;
 304
 305         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 306         while( referItr.hasNext() ) {
 307           ReferenceEdge edgeF = referItr.next();
 308
 309           if( !edgePlannedChanges.containsKey(edgeF) ) {
 310             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
 311           }
 312
 313           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
 314
 315           if( !changesToPass.isSubset(currentChanges) ) {
 316             todoEdges.add(edgeF);
 317             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
 318           }
 319         }
 320       }
 321     }
 322   }
 323
 324
 325   ////////////////////////////////////////////////////
 326   //
 327   //  Assignment Operation Methods
 328   //
 329   //  These methods are high-level operations for
 330   //  modeling program assignment statements using
 331   //  the low-level reference create/remove methods
 332   //  above.
 333   //
 334   //  The destination in an assignment statement is
 335   //  going to have new references.  The method of
 336   //  determining the references depends on the type
 337   //  of the FlatNode assignment and the predicates
 338   //  of the nodes and edges involved.
 339   //
 340   ////////////////////////////////////////////////////
 341   public void assignTempYToTempX(TempDescriptor y,
 342                                  TempDescriptor x) {
 343
 344     LabelNode lnX = getLabelNodeFromTemp(x);
 345     LabelNode lnY = getLabelNodeFromTemp(y);
 346
 347     clearReferenceEdgesFrom(lnX, null, true);
 348
 349     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 350     while( itrYhrn.hasNext() ) {
 351       ReferenceEdge edgeY       = itrYhrn.next();
 352       HeapRegionNode referencee = edgeY.getDst();
 353       ReferenceEdge edgeNew    = edgeY.copy();
 354       edgeNew.setSrc(lnX);
 355
 356       addReferenceEdge(lnX, referencee, edgeNew);
 357     }
 358   }
 359
 360
 361   public void assignTempYFieldFToTempX(TempDescriptor y,
 362                                        FieldDescriptor f,
 363                                        TempDescriptor x) {
 364
 365     LabelNode lnX = getLabelNodeFromTemp(x);
 366     LabelNode lnY = getLabelNodeFromTemp(y);
 367
 368     clearReferenceEdgesFrom(lnX, null, true);
 369
 370     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 371     while( itrYhrn.hasNext() ) {
 372       ReferenceEdge edgeY = itrYhrn.next();
 373       HeapRegionNode hrnY  = edgeY.getDst();
 374       ReachabilitySet betaY = edgeY.getBeta();
 375
 376       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 377       while( itrHrnFhrn.hasNext() ) {
 378         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 379         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 380         ReachabilitySet betaHrn = edgeHrn.getBeta();
 381
 382         if( edgeHrn.getFieldDesc() == null ||
 383             edgeHrn.getFieldDesc() == f ) {
 384
 385           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 386                                                     hrnHrn,
 387                                                     f,
 388                                                     false,
 389                                                     betaY.intersection(betaHrn) );
 390
 391           addReferenceEdge(lnX, hrnHrn, edgeNew);
 392         }
 393       }
 394     }
 395   }
 396
 397
 398   public void assignTempYToTempXFieldF(TempDescriptor y,
 399                                        TempDescriptor x,
 400                                        FieldDescriptor f) {
 401
 402     LabelNode lnX = getLabelNodeFromTemp(x);
 403     LabelNode lnY = getLabelNodeFromTemp(y);
 404
 405     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 406     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 407
 408     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 409     while( itrXhrn.hasNext() ) {
 410       ReferenceEdge edgeX = itrXhrn.next();
 411       HeapRegionNode hrnX  = edgeX.getDst();
 412       ReachabilitySet betaX = edgeX.getBeta();
 413
 414       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 415
 416       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 417       while( itrYhrn.hasNext() ) {
 418         ReferenceEdge edgeY = itrYhrn.next();
 419         HeapRegionNode hrnY  = edgeY.getDst();
 420         ReachabilitySet O     = edgeY.getBeta();
 421
 422
 423         // propagate tokens over nodes starting from hrnSrc, and it will
 424         // take care of propagating back up edges from any touched nodes
 425         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 426         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 427
 428
 429         // then propagate back just up the edges from hrn
 430         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 431
 432         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 433
 434         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 435           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 436
 437         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 438         while( referItr.hasNext() ) {
 439           ReferenceEdge edgeUpstream = referItr.next();
 440           todoEdges.add(edgeUpstream);
 441           edgePlannedChanges.put(edgeUpstream, Cx);
 442         }
 443
 444         propagateTokensOverEdges(todoEdges,
 445                                  edgePlannedChanges,
 446                                  edgesWithNewBeta);
 447
 448
 449
 450         //System.out.println( edgeY.getBetaNew() + "\nbeing pruned by\n" + hrnX.getAlpha() );
 451
 452         // create the actual reference edge hrnX.f -> hrnY
 453         ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
 454                                                   hrnY,
 455                                                   f,
 456                                                   false,
 457                                                   edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
 458                                                   //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
 459                                                   );
 460         addReferenceEdge(hrnX, hrnY, edgeNew);
 461
 462         /*
 463            if( f != null ) {
 464             // we can do a strong update here if one of two cases holds
 465             // SAVE FOR LATER, WITHOUT STILL CORRECT
 466             if( (hrnX.getNumReferencers() == 1)                           ||
 467                 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
 468               ) {
 469                 clearReferenceEdgesFrom( hrnX, f, false );
 470             }
 471
 472             addReferenceEdge( hrnX, hrnY, edgeNew );
 473
 474            } else {
 475             // if the field is null, or "any" field, then
 476             // look to see if an any field already exists
 477             // and merge with it, otherwise just add the edge
 478             ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
 479
 480             if( edgeExisting != null ) {
 481                 edgeExisting.setBetaNew(
 482                   edgeExisting.getBetaNew().union( edgeNew.getBeta() )
 483                                        );
 484                 // a new edge here cannot be reflexive, so existing will
 485                 // always be also not reflexive anymore
 486                 edgeExisting.setIsInitialParamReflexive( false );
 487
 488             } else {
 489                 addReferenceEdge( hrnX, hrnY, edgeNew );
 490             }
 491            }
 492          */
 493       }
 494     }
 495
 496     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 497     while( nodeItr.hasNext() ) {
 498       nodeItr.next().applyAlphaNew();
 499     }
 500
 501     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
 502     while( edgeItr.hasNext() ) {
 503       edgeItr.next().applyBetaNew();
 504     }
 505   }
 506
 507
 508   public void assignParameterAllocationToTemp(boolean isTask,
 509                                               TempDescriptor td,
 510                                               Integer paramIndex) {
 511     assert td != null;
 512
 513     LabelNode lnParam = getLabelNodeFromTemp(td);
 514     HeapRegionNode hrn = createNewHeapRegionNode(null,
 515                                                  false,
 516                                                  isTask,
 517                                                  false,
 518                                                  true,
 519                                                  null,
 520                                                  null,
 521                                                  "param" + paramIndex);
 522
 523     // this is a non-program-accessible label that picks up beta
 524     // info to be used for fixing a caller of this method
 525     TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
 526     LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
 527
 528     // keep track of heap regions that were created for
 529     // parameter labels, the index of the parameter they
 530     // are for is important when resolving method calls
 531     Integer newID = hrn.getID();
 532     assert !id2paramIndex.containsKey(newID);
 533     assert !id2paramIndex.containsValue(paramIndex);
 534     id2paramIndex.put(newID, paramIndex);
 535     paramIndex2id.put(paramIndex, newID);
 536     paramIndex2tdQ.put(paramIndex, tdParamQ);
 537
 538     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
 539                                                               true,
 540                                                               TokenTuple.ARITY_ONE) );
 541
 542     // heap regions for parameters are always multiple object (see above)
 543     // and have a reference to themselves, because we can't know the
 544     // structure of memory that is passed into the method.  We're assuming
 545     // the worst here.
 546
 547     ReferenceEdge edgeFromLabel =
 548       new ReferenceEdge(lnParam, hrn, null, false, beta);
 549
 550     ReferenceEdge edgeFromLabelQ =
 551       new ReferenceEdge(lnParamQ, hrn, null, false, beta);
 552
 553     ReferenceEdge edgeReflexive =
 554       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 555
 556     addReferenceEdge(lnParam,  hrn, edgeFromLabel);
 557     addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
 558     addReferenceEdge(hrn,      hrn, edgeReflexive);
 559   }
 560
 561
 562   public void assignNewAllocationToTempX(TempDescriptor x,
 563                                          AllocationSite as) {
 564     assert x  != null;
 565     assert as != null;
 566
 567     age(as);
 568
 569     // after the age operation the newest (or zero-ith oldest)
 570     // node associated with the allocation site should have
 571     // no references to it as if it were a newly allocated
 572     // heap region, so make a reference to it to complete
 573     // this operation
 574
 575     Integer idNewest  = as.getIthOldest(0);
 576     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 577     assert hrnNewest != null;
 578
 579     LabelNode lnX = getLabelNodeFromTemp(x);
 580     clearReferenceEdgesFrom(lnX, null, true);
 581
 582     ReferenceEdge edgeNew =
 583       new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
 584
 585     addReferenceEdge(lnX, hrnNewest, edgeNew);
 586   }
 587
 588
 589   // use the allocation site (unique to entire analysis) to
 590   // locate the heap region nodes in this ownership graph
 591   // that should be aged.  The process models the allocation
 592   // of new objects and collects all the oldest allocations
 593   // in a summary node to allow for a finite analysis
 594   //
 595   // There is an additional property of this method.  After
 596   // running it on a particular ownership graph (many graphs
 597   // may have heap regions related to the same allocation site)
 598   // the heap region node objects in this ownership graph will be
 599   // allocated.  Therefore, after aging a graph for an allocation
 600   // site, attempts to retrieve the heap region nodes using the
 601   // integer id's contained in the allocation site should always
 602   // return non-null heap regions.
 603   public void age(AllocationSite as) {
 604
 605     // aging adds this allocation site to the graph's
 606     // list of sites that exist in the graph, or does
 607     // nothing if the site is already in the list
 608     allocationSites.add(as);
 609
 610     // get the summary node for the allocation site in the context
 611     // of this particular ownership graph
 612     HeapRegionNode hrnSummary = getSummaryNode(as);
 613
 614     // merge oldest node into summary
 615     Integer idK  = as.getOldest();
 616     HeapRegionNode hrnK = id2hrn.get(idK);
 617     mergeIntoSummary(hrnK, hrnSummary);
 618
 619     // move down the line of heap region nodes
 620     // clobbering the ith and transferring all references
 621     // to and from i-1 to node i.  Note that this clobbers
 622     // the oldest node (hrnK) that was just merged into
 623     // the summary
 624     for( int i = allocationDepth - 1; i > 0; --i ) {
 625
 626       // move references from the i-1 oldest to the ith oldest
 627       Integer idIth     = as.getIthOldest(i);
 628       HeapRegionNode hrnI      = id2hrn.get(idIth);
 629       Integer idImin1th = as.getIthOldest(i - 1);
 630       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 631
 632       transferOnto(hrnImin1, hrnI);
 633     }
 634
 635     // as stated above, the newest node should have had its
 636     // references moved over to the second oldest, so we wipe newest
 637     // in preparation for being the new object to assign something to
 638     Integer id0th = as.getIthOldest(0);
 639     HeapRegionNode hrn0  = id2hrn.get(id0th);
 640     assert hrn0 != null;
 641
 642     // clear all references in and out of newest node
 643     clearReferenceEdgesFrom(hrn0, null, true);
 644     clearReferenceEdgesTo(hrn0, null, true);
 645
 646
 647     // now tokens in reachability sets need to "age" also
 648     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 649     while( itrAllLabelNodes.hasNext() ) {
 650       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 651       LabelNode ln = (LabelNode) me.getValue();
 652
 653       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 654       while( itrEdges.hasNext() ) {
 655         ageTokens(as, itrEdges.next() );
 656       }
 657     }
 658
 659     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 660     while( itrAllHRNodes.hasNext() ) {
 661       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
 662       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 663
 664       ageTokens(as, hrnToAge);
 665
 666       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
 667       while( itrEdges.hasNext() ) {
 668         ageTokens(as, itrEdges.next() );
 669       }
 670     }
 671
 672
 673     // after tokens have been aged, reset newest node's reachability
 674     if( hrn0.isFlagged() ) {
 675       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
 676                                           new TokenTuple(hrn0)
 677                                           )
 678                                         ).makeCanonical()
 679                     );
 680     } else {
 681       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
 682                                         ).makeCanonical()
 683                     );
 684     }
 685   }
 686
 687
 688   protected HeapRegionNode getSummaryNode(AllocationSite as) {
 689
 690     Integer idSummary  = as.getSummary();
 691     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
 692
 693     // If this is null then we haven't touched this allocation site
 694     // in the context of the current ownership graph, so allocate
 695     // heap region nodes appropriate for the entire allocation site.
 696     // This should only happen once per ownership graph per allocation site,
 697     // and a particular integer id can be used to locate the heap region
 698     // in different ownership graphs that represents the same part of an
 699     // allocation site.
 700     if( hrnSummary == null ) {
 701
 702       boolean hasFlags = false;
 703       if( as.getType().isClass() ) {
 704         hasFlags = as.getType().getClassDesc().hasFlags();
 705       }
 706
 707       hrnSummary = createNewHeapRegionNode(idSummary,
 708                                            false,
 709                                            hasFlags,
 710                                            true,
 711                                            false,
 712                                            as,
 713                                            null,
 714                                            as + "\\n" + as.getType() + "\\nsummary");
 715
 716       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 717         Integer idIth = as.getIthOldest(i);
 718         assert !id2hrn.containsKey(idIth);
 719         createNewHeapRegionNode(idIth,
 720                                 true,
 721                                 hasFlags,
 722                                 false,
 723                                 false,
 724                                 as,
 725                                 null,
 726                                 as + "\\n" + as.getType() + "\\n" + i + " oldest");
 727       }
 728     }
 729
 730     return hrnSummary;
 731   }
 732
 733
 734   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
 735
 736     Integer idShadowSummary  = as.getSummaryShadow();
 737     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
 738
 739     if( hrnShadowSummary == null ) {
 740
 741       boolean hasFlags = false;
 742       if( as.getType().isClass() ) {
 743         hasFlags = as.getType().getClassDesc().hasFlags();
 744       }
 745
 746       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
 747                                                  false,
 748                                                  hasFlags,
 749                                                  true,
 750                                                  false,
 751                                                  as,
 752                                                  null,
 753                                                  as + "\\n" + as.getType() + "\\nshadowSum");
 754
 755       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 756         Integer idShadowIth = as.getIthOldestShadow(i);
 757         assert !id2hrn.containsKey(idShadowIth);
 758         createNewHeapRegionNode(idShadowIth,
 759                                 true,
 760                                 hasFlags,
 761                                 false,
 762                                 false,
 763                                 as,
 764                                 null,
 765                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
 766       }
 767     }
 768
 769     return hrnShadowSummary;
 770   }
 771
 772
 773   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
 774     assert hrnSummary.isNewSummary();
 775
 776     // transfer references _from_ hrn over to hrnSummary
 777     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
 778     while( itrReferencee.hasNext() ) {
 779       ReferenceEdge edge       = itrReferencee.next();
 780       ReferenceEdge edgeMerged = edge.copy();
 781       edgeMerged.setSrc(hrnSummary);
 782
 783       HeapRegionNode hrnReferencee = edge.getDst();
 784       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
 785
 786       if( edgeSummary == null ) {
 787         // the merge is trivial, nothing to be done
 788       } else {
 789         // otherwise an edge from the referencer to hrnSummary exists already
 790         // and the edge referencer->hrn should be merged with it
 791         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 792       }
 793
 794       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
 795     }
 796
 797     // next transfer references _to_ hrn over to hrnSummary
 798     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
 799     while( itrReferencer.hasNext() ) {
 800       ReferenceEdge edge         = itrReferencer.next();
 801       ReferenceEdge edgeMerged   = edge.copy();
 802       edgeMerged.setDst(hrnSummary);
 803
 804       OwnershipNode onReferencer = edge.getSrc();
 805       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
 806
 807       if( edgeSummary == null ) {
 808         // the merge is trivial, nothing to be done
 809       } else {
 810         // otherwise an edge from the referencer to alpha_S exists already
 811         // and the edge referencer->alpha_K should be merged with it
 812         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 813       }
 814
 815       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
 816     }
 817
 818     // then merge hrn reachability into hrnSummary
 819     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
 820   }
 821
 822
 823   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
 824
 825     // clear references in and out of node i
 826     clearReferenceEdgesFrom(hrnB, null, true);
 827     clearReferenceEdgesTo(hrnB, null, true);
 828
 829     // copy each edge in and out of A to B
 830     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
 831     while( itrReferencee.hasNext() ) {
 832       ReferenceEdge edge          = itrReferencee.next();
 833       HeapRegionNode hrnReferencee = edge.getDst();
 834       ReferenceEdge edgeNew       = edge.copy();
 835       edgeNew.setSrc(hrnB);
 836
 837       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
 838     }
 839
 840     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
 841     while( itrReferencer.hasNext() ) {
 842       ReferenceEdge edge         = itrReferencer.next();
 843       OwnershipNode onReferencer = edge.getSrc();
 844       ReferenceEdge edgeNew      = edge.copy();
 845       edgeNew.setDst(hrnB);
 846
 847       addReferenceEdge(onReferencer, hrnB, edgeNew);
 848     }
 849
 850     // replace hrnB reachability with hrnA's
 851     hrnB.setAlpha(hrnA.getAlpha() );
 852   }
 853
 854
 855   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
 856     edge.setBeta(edge.getBeta().ageTokens(as) );
 857   }
 858
 859   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
 860     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
 861   }
 862
 863
 864   public void resolveMethodCall(FlatCall fc,
 865                                 boolean isStatic,
 866                                 FlatMethod fm,
 867                                 OwnershipGraph ogCallee) {
 868
 869
 870     // define rewrite rules and other structures to organize
 871     // data by parameter/argument index
 872     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
 873       new Hashtable<Integer, ReachabilitySet>();
 874
 875     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
 876       new Hashtable<Integer, ReachabilitySet>();
 877
 878     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
 879       new Hashtable<Integer, ReachabilitySet>();
 880
 881     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
 882       new Hashtable<Integer, ReachabilitySet>();
 883
 884     // helpful structures
 885     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
 886       new Hashtable<TokenTuple, Integer>();
 887
 888     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
 889       new Hashtable<Integer, TokenTuple>();
 890
 891     Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
 892       new Hashtable<TokenTuple, Integer>();
 893
 894     Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
 895       new Hashtable<Integer, TokenTuple>();
 896
 897     Hashtable<Integer, LabelNode> paramIndex2ln =
 898       new Hashtable<Integer, LabelNode>();
 899
 900     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
 901       new Hashtable<Integer, HashSet<HeapRegionNode> >();
 902
 903
 904     // add a bogus entry with the identity rule for easy rewrite
 905     // of new callee nodes and edges, doesn't belong to any parameter
 906     Integer bogusID = new Integer( -1 );
 907     Integer bogusIndex = new Integer( -1 );
 908     TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE );
 909     TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_MANY );
 910     ReachabilitySet rsIdentity =
 911       new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical();
 912
 913     paramIndex2rewriteH.put( bogusIndex, rsIdentity );
 914     paramIndex2rewriteJ.put( bogusIndex, rsIdentity );
 915     paramToken2paramIndex.put( bogusToken, bogusIndex );
 916     paramIndex2paramToken.put( bogusIndex, bogusToken );
 917     paramTokenStar2paramIndex.put( bogusTokenStar, bogusIndex );
 918     paramIndex2paramTokenStar.put( bogusIndex, bogusTokenStar );
 919
 920
 921     for( int i = 0; i < fm.numParameters(); ++i ) {
 922       Integer paramIndex = new Integer( i );
 923
 924       assert ogCallee.paramIndex2id.containsKey( paramIndex );
 925       Integer idParam = ogCallee.paramIndex2id.get( paramIndex );
 926
 927       assert ogCallee.id2hrn.containsKey( idParam );
 928       HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
 929       assert hrnParam != null;
 930       paramIndex2rewriteH.put( paramIndex,
 931                                toShadowTokens( ogCallee, hrnParam.getAlpha() )
 932                                );
 933
 934       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo( hrnParam, null );
 935       assert edgeReflexive_i != null;
 936       paramIndex2rewriteJ.put( paramIndex,
 937                                toShadowTokens( ogCallee, edgeReflexive_i.getBeta() )
 938                                );
 939
 940       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
 941       assert tdParamQ != null;
 942       LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
 943       assert lnParamQ != null;
 944       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnParam, null );
 945       assert edgeSpecialQ_i != null;
 946       paramIndex2rewriteK.put( paramIndex,
 947                                toShadowTokens( ogCallee, edgeSpecialQ_i.getBeta() )
 948                                );
 949
 950       TokenTuple p_i = new TokenTuple( hrnParam.getID(),
 951                                        true,
 952                                        TokenTuple.ARITY_ONE ).makeCanonical();
 953       paramToken2paramIndex.put( p_i, paramIndex );
 954       paramIndex2paramToken.put( paramIndex, p_i );
 955
 956       TokenTuple p_i_star = new TokenTuple( hrnParam.getID(),
 957                                             true,
 958                                             TokenTuple.ARITY_MANY ).makeCanonical();
 959       paramTokenStar2paramIndex.put( p_i_star, paramIndex );
 960       paramIndex2paramTokenStar.put( paramIndex, p_i_star );
 961
 962       // now depending on whether the callee is static or not
 963       // we need to account for a "this" argument in order to
 964       // find the matching argument in the caller context
 965       TempDescriptor argTemp_i;
 966       if( isStatic ) {
 967         argTemp_i = fc.getArg( paramIndex );
 968       } else {
 969         if( paramIndex == 0 ) {
 970           argTemp_i = fc.getThis();
 971         } else {
 972           argTemp_i = fc.getArg( paramIndex - 1 );
 973         }
 974       }
 975
 976       // in non-static methods there is a "this" pointer
 977       // that should be taken into account
 978       if( isStatic ) {
 979         assert fc.numArgs()     == fm.numParameters();
 980       } else {
 981         assert fc.numArgs() + 1 == fm.numParameters();
 982       }
 983
 984       LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
 985       paramIndex2ln.put( paramIndex, argLabel_i );
 986
 987       ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
 988       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
 989       while( edgeItr.hasNext() ) {
 990         ReferenceEdge edge = edgeItr.next();
 991         D_i = D_i.union( edge.getBeta() );
 992       }
 993       D_i = D_i.exhaustiveArityCombinations();
 994       paramIndex2rewriteD.put( paramIndex, D_i );
 995     }
 996
 997
 998     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 999     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1000
1001     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1002     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1003
1004     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1005     while( lnArgItr.hasNext() ) {
1006       Map.Entry me      = (Map.Entry) lnArgItr.next();
1007       Integer   index   = (Integer)   me.getKey();
1008       LabelNode lnArg_i = (LabelNode) me.getValue();
1009
1010       // rewrite alpha for the nodes reachable from argument label i
1011       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1012       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1013
1014       // to find all reachable nodes, start with label referencees
1015       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1016       while( edgeArgItr.hasNext() ) {
1017         ReferenceEdge edge = edgeArgItr.next();
1018         todoNodes.add( edge.getDst() );
1019       }
1020
1021       // then follow links until all reachable nodes have been found
1022       while( !todoNodes.isEmpty() ) {
1023         HeapRegionNode hrn = todoNodes.iterator().next();
1024         todoNodes.remove( hrn );
1025         reachableNodes.add( hrn );
1026
1027         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1028         while( edgeItr.hasNext() ) {
1029           ReferenceEdge edge = edgeItr.next();
1030
1031           if( !reachableNodes.contains( edge.getDst() ) ) {
1032             todoNodes.add( edge.getDst() );
1033           }
1034         }
1035       }
1036
1037       // save for later
1038       paramIndex2reachableCallerNodes.put( index, reachableNodes );
1039
1040       // now iterate over reachable nodes to update their alpha, and
1041       // classify edges found as "argument reachable" or "upstream"
1042       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1043       while( hrnItr.hasNext() ) {
1044         HeapRegionNode hrn = hrnItr.next();
1045
1046         rewriteCallerNodeAlpha( fm.numParameters(),
1047                                 index,
1048                                 hrn,
1049                                 paramIndex2rewriteH,
1050                                 paramIndex2rewriteD,
1051                                 paramIndex2paramToken,
1052                                 paramIndex2paramTokenStar );
1053
1054         nodesWithNewAlpha.add( hrn );
1055
1056         // look at all incoming edges to the reachable nodes
1057         // and sort them as edges reachable from the argument
1058         // label node, or upstream edges
1059         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1060         while( edgeItr.hasNext() ) {
1061           ReferenceEdge edge = edgeItr.next();
1062
1063           OwnershipNode on = edge.getSrc();
1064
1065           if( on instanceof LabelNode ) {
1066
1067             LabelNode ln0 = (LabelNode) on;
1068             if( ln0.equals( lnArg_i ) ) {
1069               edgesReachable.add( edge );
1070             } else {
1071               edgesUpstream.add( edge );
1072             }
1073
1074           } else {
1075
1076             HeapRegionNode hrn0 = (HeapRegionNode) on;
1077             if( reachableNodes.contains( hrn0 ) ) {
1078               edgesReachable.add( edge );
1079             } else {
1080               edgesUpstream.add( edge );
1081             }
1082           }
1083         }
1084       }
1085
1086
1087       // update reachable edges
1088       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1089       while( edgeReachableItr.hasNext() ) {
1090         ReferenceEdge edgeReachable = edgeReachableItr.next();
1091
1092         rewriteCallerEdgeBeta( fm.numParameters(),
1093                                index,
1094                                edgeReachable,
1095                                paramIndex2rewriteJ,
1096                                paramIndex2rewriteD,
1097                                paramIndex2paramToken,
1098                                paramIndex2paramTokenStar,
1099                                false,
1100                                null );
1101
1102         edgesWithNewBeta.add( edgeReachable );
1103       }
1104
1105
1106       // update upstream edges
1107       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
1108         = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1109
1110       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1111       while( edgeUpstreamItr.hasNext() ) {
1112         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1113
1114         rewriteCallerEdgeBeta( fm.numParameters(),
1115                                index,
1116                                edgeUpstream,
1117                                paramIndex2rewriteK,
1118                                paramIndex2rewriteD,
1119                                paramIndex2paramToken,
1120                                paramIndex2paramTokenStar,
1121                                true,
1122                                edgeUpstreamPlannedChanges );
1123
1124         edgesWithNewBeta.add( edgeUpstream );
1125       }
1126
1127       propagateTokensOverEdges( edgesUpstream,
1128                                 edgeUpstreamPlannedChanges,
1129                                 edgesWithNewBeta );
1130     }
1131
1132
1133     // commit changes to alpha and beta
1134     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1135     while( nodeItr.hasNext() ) {
1136       nodeItr.next().applyAlphaNew();
1137     }
1138
1139     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1140     while( edgeItr.hasNext() ) {
1141       edgeItr.next().applyBetaNew();
1142     }
1143
1144
1145
1146     // verify the existence of allocation sites and their
1147     // shadows from the callee in the context of this caller graph
1148     // then map allocated nodes of callee onto the caller shadows
1149     // of them
1150     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1151     while( asItr.hasNext() ) {
1152       AllocationSite allocSite  = asItr.next();
1153       HeapRegionNode hrnSummary = getSummaryNode( allocSite );
1154
1155       // assert that the shadow nodes have no reference edges
1156       // because they're brand new to the graph, or last time
1157       // they were used they should have been cleared of edges
1158       HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
1159       assert hrnShadowSummary.getNumReferencers() == 0;
1160       assert hrnShadowSummary.getNumReferencees() == 0;
1161
1162       // then bring g_ij onto g'_ij and rewrite
1163       transferOnto( hrnSummary, hrnShadowSummary );
1164
1165       hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnShadowSummary.getAlpha() ) );
1166
1167       // shadow nodes only are touched by a rewrite one time,
1168       // so rewrite and immediately commit--and they don't belong
1169       // to a particular parameter, so use a bogus param index
1170       // that pulls a self-rewrite out of H
1171       rewriteCallerNodeAlpha( fm.numParameters(),
1172                               bogusIndex,
1173                               hrnShadowSummary,
1174                               paramIndex2rewriteH,
1175                               paramIndex2rewriteD,
1176                               paramIndex2paramToken,
1177                               paramIndex2paramTokenStar );
1178
1179
1180       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1181         Integer idIth = allocSite.getIthOldest(i);
1182         assert id2hrn.containsKey(idIth);
1183         HeapRegionNode hrnIth = id2hrn.get(idIth);
1184
1185         Integer idShadowIth = -(allocSite.getIthOldest(i));
1186         assert id2hrn.containsKey(idShadowIth);
1187         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1188         assert hrnIthShadow.getNumReferencers() == 0;
1189         assert hrnIthShadow.getNumReferencees() == 0;
1190
1191         transferOnto( hrnIth, hrnIthShadow );
1192
1193         hrnIthShadow.setAlpha( toShadowTokens( ogCallee, hrnIthShadow.getAlpha() ) );
1194
1195         rewriteCallerNodeAlpha( fm.numParameters(),
1196                                 bogusIndex,
1197                                 hrnIthShadow,
1198                                 paramIndex2rewriteH,
1199                                 paramIndex2rewriteD,
1200                                 paramIndex2paramToken,
1201                                 paramIndex2paramTokenStar );
1202       }
1203     }
1204
1205     // for every heap region->heap region edge in the
1206     // callee graph, create the matching edge or edges
1207     // in the caller graph
1208     Set      sCallee = ogCallee.id2hrn.entrySet();
1209     Iterator iCallee = sCallee.iterator();
1210     while( iCallee.hasNext() ) {
1211       Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
1212       Integer        idCallee  = (Integer)        meCallee.getKey();
1213       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1214
1215       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1216       while( heapRegionsItrCallee.hasNext() ) {
1217         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1218         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1219         Integer idChildCallee         = hrnChildCallee.getID();
1220
1221         // only address this edge if it is not a special reflexive edge
1222         if( !edgeCallee.isInitialParamReflexive() ) {
1223
1224           // now we know that in the callee method's ownership graph
1225           // there is a heap region->heap region reference edge given
1226           // by heap region pointers:
1227           // hrnCallee -> heapChildCallee
1228           //
1229           // or by the ownership-graph independent ID's:
1230           // idCallee -> idChildCallee
1231
1232           // make the edge with src and dst so beta info is
1233           // calculated once, then copy it for each new edge in caller
1234           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
1235                                                                      null,
1236                                                                      edgeCallee.getFieldDesc(),
1237                                                                      false,
1238                                                                      toShadowTokens( ogCallee, edgeCallee.getBeta() )
1239                                                                      );
1240           rewriteCallerEdgeBeta( fm.numParameters(),
1241                                  bogusIndex,
1242                                  edgeNewInCallerTemplate,
1243                                  paramIndex2rewriteJ,
1244                                  paramIndex2rewriteD,
1245                                  paramIndex2paramToken,
1246                                  paramIndex2paramTokenStar,
1247                                  false,
1248                                  null );
1249
1250
1251
1252
1253           // So now make a set of possible source heaps in the caller graph
1254           // and a set of destination heaps in the caller graph, and make
1255           // a reference edge in the caller for every possible (src,dst) pair
1256           HashSet<HeapRegionNode> possibleCallerSrcs =
1257             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1258                                                  edgeCallee,
1259                                                  true,
1260                                                  paramIndex2reachableCallerNodes );
1261
1262           HashSet<HeapRegionNode> possibleCallerDsts =
1263             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1264                                                  edgeCallee,
1265                                                  false,
1266                                                  paramIndex2reachableCallerNodes );
1267
1268           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1269           Iterator srcItr = possibleCallerSrcs.iterator();
1270           while( srcItr.hasNext() ) {
1271             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1272
1273             Iterator dstItr = possibleCallerDsts.iterator();
1274             while( dstItr.hasNext() ) {
1275               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1276
1277               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1278               edgeNewInCaller.setSrc( src );
1279               edgeNewInCaller.setDst( dst );
1280
1281               ReferenceEdge edgeExisting = src.getReferenceTo( dst, edgeNewInCaller.getFieldDesc() );
1282               if( edgeExisting == null ) {
1283                 // if this edge doesn't exist in the caller, create it
1284                 addReferenceEdge( src, dst, edgeNewInCaller );
1285               } else {
1286                 // if it already exists, merge with it
1287                 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
1288               }
1289             }
1290           }
1291         }
1292       }
1293     }
1294
1295
1296     // merge the shadow nodes of allocation sites back down to normal capacity
1297     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1298     while( allocItr.hasNext() ) {
1299       AllocationSite as = allocItr.next();
1300
1301       // first age each allocation site enough times to make room for the shadow nodes
1302       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1303         age( as );
1304       }
1305
1306       // then merge the shadow summary into the normal summary
1307       HeapRegionNode hrnSummary = getSummaryNode( as );
1308       assert hrnSummary != null;
1309
1310       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
1311       assert hrnSummaryShadow != null;
1312
1313       mergeIntoSummary( hrnSummaryShadow, hrnSummary );
1314
1315       // then transplant shadow nodes onto the now clean normal nodes
1316       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1317
1318         Integer idIth = as.getIthOldest(i);
1319         HeapRegionNode hrnIth = id2hrn.get(idIth);
1320
1321         Integer idIthShadow = as.getIthOldestShadow(i);
1322         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1323
1324         transferOnto(hrnIthShadow, hrnIth);
1325
1326         // clear off shadow nodes after transfer
1327         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1328         clearReferenceEdgesTo(hrnIthShadow, null, true);
1329         hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
1330       }
1331
1332       // finally, globally change shadow tokens into normal tokens
1333       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1334       while( itrAllLabelNodes.hasNext() ) {
1335         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1336         LabelNode ln = (LabelNode) me.getValue();
1337
1338         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1339         while( itrEdges.hasNext() ) {
1340           unshadowTokens(as, itrEdges.next() );
1341         }
1342       }
1343
1344       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1345       while( itrAllHRNodes.hasNext() ) {
1346         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1347         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1348
1349         unshadowTokens(as, hrnToAge);
1350
1351         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1352         while( itrEdges.hasNext() ) {
1353           unshadowTokens(as, itrEdges.next() );
1354         }
1355       }
1356     }
1357   }
1358
1359
1360   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1361     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1362   }
1363
1364   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1365     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1366   }
1367
1368
1369   private ReachabilitySet toShadowTokens( OwnershipGraph ogCallee,
1370                                           ReachabilitySet rsIn ) {
1371
1372     ReachabilitySet rsOut = new ReachabilitySet( rsIn );
1373
1374     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1375     while( allocItr.hasNext() ) {
1376       AllocationSite as = allocItr.next();
1377
1378       rsOut = rsOut.toShadowTokens( as );
1379     }
1380
1381     return rsOut.makeCanonical();
1382   }
1383
1384
1385   private void rewriteCallerNodeAlpha( int numParameters,
1386                                        Integer paramIndex,
1387                                        HeapRegionNode hrn,
1388                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1389                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1390                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1391                                        Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1392
1393     ReachabilitySet rules = paramIndex2rewriteH.get( paramIndex );
1394     assert rules != null;
1395
1396     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1397     assert tokenToRewrite != null;
1398
1399     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1400     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1401     while( ttsItr.hasNext() ) {
1402       TokenTupleSet tts = ttsItr.next();
1403       r0 = r0.union( tts.rewriteToken( tokenToRewrite,
1404                                        hrn.getAlpha(),
1405                                        false,
1406                                        null ) );
1407     }
1408
1409     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1410     ttsItr = r0.iterator();
1411     while( ttsItr.hasNext() ) {
1412       TokenTupleSet tts = ttsItr.next();
1413       r1 = r1.union( rewriteDpass( numParameters,
1414                                    paramIndex,
1415                                    tts,
1416                                    paramIndex2rewriteD,
1417                                    paramIndex2paramToken,
1418                                    paramIndex2paramTokenStar ) );
1419     }
1420
1421     hrn.setAlphaNew( hrn.getAlphaNew().union( r1 ) );
1422   }
1423
1424
1425   private void rewriteCallerEdgeBeta( int numParameters,
1426                                       Integer paramIndex,
1427                                       ReferenceEdge edge,
1428                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1429                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1430                                       Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1431                                       Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1432                                       boolean makeChangeSet,
1433                                       Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1434
1435     ReachabilitySet rules = paramIndex2rewriteJorK.get( paramIndex );
1436     assert rules != null;
1437
1438     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1439     assert tokenToRewrite != null;
1440
1441     ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1442
1443     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1444     while( ttsItr.hasNext() ) {
1445       TokenTupleSet tts = ttsItr.next();
1446
1447       Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1448         new Hashtable<TokenTupleSet, TokenTupleSet>();
1449
1450       ReachabilitySet rTemp = tts.rewriteToken( tokenToRewrite,
1451                                                 edge.getBeta(),
1452                                                 true,
1453                                                 forChangeSet );
1454
1455       Iterator fcsItr = forChangeSet.entrySet().iterator();
1456       while( fcsItr.hasNext() ) {
1457         Map.Entry me = (Map.Entry) fcsItr.next();
1458         TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1459         TokenTupleSet ttsAdd   = (TokenTupleSet) me.getValue();
1460
1461         ChangeTuple ct = new ChangeTuple( ttsMatch,
1462                                           ttsAdd
1463                                           ).makeCanonical();
1464
1465         cts0 = cts0.union( ct );
1466       }
1467     }
1468
1469
1470     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1471     ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1472
1473     Iterator<ChangeTuple> ctItr = cts0.iterator();
1474     while( ctItr.hasNext() ) {
1475       ChangeTuple ct = ctItr.next();
1476
1477       ReachabilitySet rTemp = rewriteDpass( numParameters,
1478                                             paramIndex,
1479                                             ct.getSetToAdd(),
1480                                             paramIndex2rewriteD,
1481                                             paramIndex2paramToken,
1482                                             paramIndex2paramTokenStar
1483                                             ).makeCanonical();
1484       r1 = r1.union( rTemp );
1485
1486       if( makeChangeSet ) {
1487         assert edgePlannedChanges != null;
1488
1489         Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1490         while( ttsTempItr.hasNext() ) {
1491           TokenTupleSet tts = ttsTempItr.next();
1492
1493           ChangeTuple ctFinal = new ChangeTuple( ct.getSetToMatch(),
1494                                                  tts
1495                                                  ).makeCanonical();
1496
1497           cts1 = cts1.union( ctFinal );
1498         }
1499       }
1500     }
1501
1502     if( makeChangeSet ) {
1503       edgePlannedChanges.put( edge, cts1 );
1504     }
1505
1506     edge.setBetaNew( edge.getBetaNew().union( r1 ) );
1507   }
1508
1509
1510   private ReachabilitySet rewriteDpass( int numParameters,
1511                                         Integer paramIndex,
1512                                         TokenTupleSet ttsIn,
1513                                         Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1514                                         Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1515                                         Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1516
1517     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1518
1519     boolean rewritten = false;
1520
1521     for( int j = 0; j < numParameters; ++j ) {
1522       Integer paramIndexJ = new Integer( j );
1523       ReachabilitySet D_j = paramIndex2rewriteD.get( paramIndexJ );
1524       assert D_j != null;
1525
1526       if( paramIndexJ != paramIndex ) {
1527         TokenTuple tokenToRewriteJ = paramIndex2paramToken.get( paramIndexJ );
1528         assert tokenToRewriteJ != null;
1529         if( ttsIn.containsTuple( tokenToRewriteJ ) ) {
1530           ReachabilitySet r = ttsIn.rewriteToken( tokenToRewriteJ,
1531                                                   D_j,
1532                                                   false,
1533                                                   null );
1534           Iterator<TokenTupleSet> ttsItr = r.iterator();
1535           while( ttsItr.hasNext() ) {
1536             TokenTupleSet tts = ttsItr.next();
1537             rsOut = rsOut.union( rewriteDpass( numParameters,
1538                                                paramIndex,
1539                                                tts,
1540                                                paramIndex2rewriteD,
1541                                                paramIndex2paramToken,
1542                                                paramIndex2paramTokenStar ) );
1543             rewritten = true;
1544           }
1545         }
1546       }
1547
1548       TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get( paramIndexJ );
1549       assert tokenStarToRewriteJ != null;
1550       if( ttsIn.containsTuple( tokenStarToRewriteJ ) ) {
1551         ReachabilitySet r = ttsIn.rewriteToken( tokenStarToRewriteJ,
1552                                                 D_j,
1553                                                 false,
1554                                                 null );
1555         Iterator<TokenTupleSet> ttsItr = r.iterator();
1556         while( ttsItr.hasNext() ) {
1557           TokenTupleSet tts = ttsItr.next();
1558           rsOut = rsOut.union( rewriteDpass( numParameters,
1559                                              paramIndex,
1560                                              tts,
1561                                              paramIndex2rewriteD,
1562                                              paramIndex2paramToken,
1563                                              paramIndex2paramTokenStar ) );
1564           rewritten = true;
1565         }
1566       }
1567     }
1568
1569     if( !rewritten ) {
1570       rsOut = rsOut.union( ttsIn );
1571     }
1572
1573     return rsOut;
1574   }
1575
1576
1577   private HashSet<HeapRegionNode>
1578     getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
1579                                          ReferenceEdge edgeCallee,
1580                                          boolean mapFromSrc,
1581                                          Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1582                                          ) {
1583
1584     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1585
1586     HeapRegionNode hrnCallee;
1587     if( mapFromSrc ) {
1588       OwnershipNode on = edgeCallee.getSrc();
1589       assert on instanceof HeapRegionNode;
1590       hrnCallee = (HeapRegionNode) on;
1591     } else {
1592       hrnCallee = edgeCallee.getDst();
1593     }
1594
1595     Integer paramIndexCallee = ogCallee.id2paramIndex.get( hrnCallee.getID() );
1596
1597     if( paramIndexCallee == null ) {
1598       // this is a node allocated in the callee then and it has
1599       // exactly one shadow node in the caller to map to
1600       AllocationSite as = hrnCallee.getAllocationSite();
1601       assert as != null;
1602
1603       int age = as.getAgeCategory( hrnCallee.getID() );
1604       assert age != AllocationSite.AGE_notInThisSite;
1605
1606       Integer idCaller;
1607       if( age == AllocationSite.AGE_summary ) {
1608         idCaller = as.getSummaryShadow();
1609       } else if( age == AllocationSite.AGE_oldest ) {
1610         idCaller = as.getOldestShadow();
1611       } else {
1612         assert age == AllocationSite.AGE_in_I;
1613
1614         Integer I = as.getAge( hrnCallee.getID() );
1615         assert I != null;
1616
1617         idCaller = as.getIthOldestShadow( I );
1618       }
1619
1620       assert id2hrn.containsKey( idCaller );
1621       HeapRegionNode hrnCaller = id2hrn.get( idCaller );
1622       possibleCallerHRNs.add( hrnCaller );
1623
1624     } else {
1625       // this is a node that was created to represent a parameter
1626       // so it maps to a whole mess of heap regions
1627       assert paramIndex2reachableCallerNodes.containsKey( paramIndexCallee );
1628       possibleCallerHRNs = paramIndex2reachableCallerNodes.get( paramIndexCallee );
1629
1630       // TODO PRUNE BY TYPE/FIELD NAME!!
1631     }
1632
1633     return possibleCallerHRNs;
1634   }
1635
1636
1637
1638   ////////////////////////////////////////////////////
1639   // in merge() and equals() methods the suffix A
1640   // represents the passed in graph and the suffix
1641   // B refers to the graph in this object
1642   // Merging means to take the incoming graph A and
1643   // merge it into B, so after the operation graph B
1644   // is the final result.
1645   ////////////////////////////////////////////////////
1646   public void merge(OwnershipGraph og) {
1647
1648     if( og == null ) {
1649       return;
1650     }
1651
1652     mergeOwnershipNodes(og);
1653     mergeReferenceEdges(og);
1654     mergeId2paramIndex(og);
1655     mergeAllocationSites(og);
1656   }
1657
1658
1659   protected void mergeOwnershipNodes(OwnershipGraph og) {
1660     Set sA = og.id2hrn.entrySet();
1661     Iterator iA = sA.iterator();
1662     while( iA.hasNext() ) {
1663       Map.Entry meA  = (Map.Entry)iA.next();
1664       Integer idA  = (Integer)        meA.getKey();
1665       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1666
1667       // if this graph doesn't have a node the
1668       // incoming graph has, allocate it
1669       if( !id2hrn.containsKey(idA) ) {
1670         HeapRegionNode hrnB = hrnA.copy();
1671         id2hrn.put(idA, hrnB);
1672
1673       } else {
1674         // otherwise this is a node present in both graphs
1675         // so make the new reachability set a union of the
1676         // nodes' reachability sets
1677         HeapRegionNode hrnB = id2hrn.get(idA);
1678         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1679       }
1680     }
1681
1682     // now add any label nodes that are in graph B but
1683     // not in A
1684     sA = og.td2ln.entrySet();
1685     iA = sA.iterator();
1686     while( iA.hasNext() ) {
1687       Map.Entry meA = (Map.Entry)iA.next();
1688       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1689       LabelNode lnA = (LabelNode)      meA.getValue();
1690
1691       // if the label doesn't exist in B, allocate and add it
1692       LabelNode lnB = getLabelNodeFromTemp(tdA);
1693     }
1694   }
1695
1696   protected void mergeReferenceEdges(OwnershipGraph og) {
1697
1698     // heap regions
1699     Set sA = og.id2hrn.entrySet();
1700     Iterator iA = sA.iterator();
1701     while( iA.hasNext() ) {
1702       Map.Entry meA  = (Map.Entry)iA.next();
1703       Integer idA  = (Integer)        meA.getKey();
1704       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1705
1706       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1707       while( heapRegionsItrA.hasNext() ) {
1708         ReferenceEdge edgeA     = heapRegionsItrA.next();
1709         HeapRegionNode hrnChildA = edgeA.getDst();
1710         Integer idChildA  = hrnChildA.getID();
1711
1712         // at this point we know an edge in graph A exists
1713         // idA -> idChildA, does this exist in B?
1714         assert id2hrn.containsKey(idA);
1715         HeapRegionNode hrnB        = id2hrn.get(idA);
1716         ReferenceEdge edgeToMerge = null;
1717
1718         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1719         while( heapRegionsItrB.hasNext() &&
1720                edgeToMerge == null          ) {
1721
1722           ReferenceEdge edgeB     = heapRegionsItrB.next();
1723           HeapRegionNode hrnChildB = edgeB.getDst();
1724           Integer idChildB  = hrnChildB.getID();
1725
1726           // don't use the ReferenceEdge.equals() here because
1727           // we're talking about existence between graphs
1728           if( idChildB.equals(idChildA) &&
1729               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1730             edgeToMerge = edgeB;
1731           }
1732         }
1733
1734         // if the edge from A was not found in B,
1735         // add it to B.
1736         if( edgeToMerge == null ) {
1737           assert id2hrn.containsKey(idChildA);
1738           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1739           edgeToMerge = edgeA.copy();
1740           edgeToMerge.setSrc(hrnB);
1741           edgeToMerge.setDst(hrnChildB);
1742           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1743         }
1744         // otherwise, the edge already existed in both graphs
1745         // so merge their reachability sets
1746         else {
1747           // just replace this beta set with the union
1748           assert edgeToMerge != null;
1749           edgeToMerge.setBeta(
1750             edgeToMerge.getBeta().union(edgeA.getBeta() )
1751             );
1752           if( !edgeA.isInitialParamReflexive() ) {
1753             edgeToMerge.setIsInitialParamReflexive(false);
1754           }
1755         }
1756       }
1757     }
1758
1759     // and then again with label nodes
1760     sA = og.td2ln.entrySet();
1761     iA = sA.iterator();
1762     while( iA.hasNext() ) {
1763       Map.Entry meA = (Map.Entry)iA.next();
1764       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1765       LabelNode lnA = (LabelNode)      meA.getValue();
1766
1767       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1768       while( heapRegionsItrA.hasNext() ) {
1769         ReferenceEdge edgeA     = heapRegionsItrA.next();
1770         HeapRegionNode hrnChildA = edgeA.getDst();
1771         Integer idChildA  = hrnChildA.getID();
1772
1773         // at this point we know an edge in graph A exists
1774         // tdA -> idChildA, does this exist in B?
1775         assert td2ln.containsKey(tdA);
1776         LabelNode lnB         = td2ln.get(tdA);
1777         ReferenceEdge edgeToMerge = null;
1778
1779         // labels never have edges with a field
1780         //assert edgeA.getFieldDesc() == null;
1781
1782         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1783         while( heapRegionsItrB.hasNext() &&
1784                edgeToMerge == null          ) {
1785
1786           ReferenceEdge edgeB     = heapRegionsItrB.next();
1787           HeapRegionNode hrnChildB = edgeB.getDst();
1788           Integer idChildB  = hrnChildB.getID();
1789
1790           // labels never have edges with a field
1791           //assert edgeB.getFieldDesc() == null;
1792
1793           // don't use the ReferenceEdge.equals() here because
1794           // we're talking about existence between graphs
1795           if( idChildB.equals(idChildA) &&
1796               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1797             edgeToMerge = edgeB;
1798           }
1799         }
1800
1801         // if the edge from A was not found in B,
1802         // add it to B.
1803         if( edgeToMerge == null ) {
1804           assert id2hrn.containsKey(idChildA);
1805           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1806           edgeToMerge = edgeA.copy();
1807           edgeToMerge.setSrc(lnB);
1808           edgeToMerge.setDst(hrnChildB);
1809           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1810         }
1811         // otherwise, the edge already existed in both graphs
1812         // so merge their reachability sets
1813         else {
1814           // just replace this beta set with the union
1815           edgeToMerge.setBeta(
1816             edgeToMerge.getBeta().union(edgeA.getBeta() )
1817             );
1818           if( !edgeA.isInitialParamReflexive() ) {
1819             edgeToMerge.setIsInitialParamReflexive(false);
1820           }
1821         }
1822       }
1823     }
1824   }
1825
1826   // you should only merge ownership graphs that have the
1827   // same number of parameters, or if one or both parameter
1828   // index tables are empty
1829   protected void mergeId2paramIndex(OwnershipGraph og) {
1830     if( id2paramIndex.size() == 0 ) {
1831       id2paramIndex  = og.id2paramIndex;
1832       paramIndex2id  = og.paramIndex2id;
1833       paramIndex2tdQ = og.paramIndex2tdQ;
1834       return;
1835     }
1836
1837     if( og.id2paramIndex.size() == 0 ) {
1838       return;
1839     }
1840
1841     assert id2paramIndex.size() == og.id2paramIndex.size();
1842   }
1843
1844   protected void mergeAllocationSites(OwnershipGraph og) {
1845     allocationSites.addAll(og.allocationSites);
1846   }
1847
1848
1849
1850   // it is necessary in the equals() member functions
1851   // to "check both ways" when comparing the data
1852   // structures of two graphs.  For instance, if all
1853   // edges between heap region nodes in graph A are
1854   // present and equal in graph B it is not sufficient
1855   // to say the graphs are equal.  Consider that there
1856   // may be edges in graph B that are not in graph A.
1857   // the only way to know that all edges in both graphs
1858   // are equally present is to iterate over both data
1859   // structures and compare against the other graph.
1860   public boolean equals(OwnershipGraph og) {
1861
1862     if( og == null ) {
1863       return false;
1864     }
1865
1866     if( !areHeapRegionNodesEqual(og) ) {
1867       return false;
1868     }
1869
1870     if( !areLabelNodesEqual(og) ) {
1871       return false;
1872     }
1873
1874     if( !areReferenceEdgesEqual(og) ) {
1875       return false;
1876     }
1877
1878     if( !areId2paramIndexEqual(og) ) {
1879       return false;
1880     }
1881
1882     // if everything is equal up to this point,
1883     // assert that allocationSites is also equal--
1884     // this data is redundant and kept for efficiency
1885     assert allocationSites.equals(og.allocationSites);
1886
1887     return true;
1888   }
1889
1890   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
1891
1892     if( !areallHRNinAalsoinBandequal(this, og) ) {
1893       return false;
1894     }
1895
1896     if( !areallHRNinAalsoinBandequal(og, this) ) {
1897       return false;
1898     }
1899
1900     return true;
1901   }
1902
1903   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
1904                                                        OwnershipGraph ogB) {
1905     Set sA = ogA.id2hrn.entrySet();
1906     Iterator iA = sA.iterator();
1907     while( iA.hasNext() ) {
1908       Map.Entry meA  = (Map.Entry)iA.next();
1909       Integer idA  = (Integer)        meA.getKey();
1910       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1911
1912       if( !ogB.id2hrn.containsKey(idA) ) {
1913         return false;
1914       }
1915
1916       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1917       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
1918         return false;
1919       }
1920     }
1921
1922     return true;
1923   }
1924
1925
1926   protected boolean areLabelNodesEqual(OwnershipGraph og) {
1927
1928     if( !areallLNinAalsoinBandequal(this, og) ) {
1929       return false;
1930     }
1931
1932     if( !areallLNinAalsoinBandequal(og, this) ) {
1933       return false;
1934     }
1935
1936     return true;
1937   }
1938
1939   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
1940                                                       OwnershipGraph ogB) {
1941     Set sA = ogA.td2ln.entrySet();
1942     Iterator iA = sA.iterator();
1943     while( iA.hasNext() ) {
1944       Map.Entry meA = (Map.Entry)iA.next();
1945       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1946
1947       if( !ogB.td2ln.containsKey(tdA) ) {
1948         return false;
1949       }
1950     }
1951
1952     return true;
1953   }
1954
1955
1956   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
1957     if( !areallREinAandBequal(this, og) ) {
1958       return false;
1959     }
1960
1961     return true;
1962   }
1963
1964   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
1965                                                 OwnershipGraph ogB) {
1966
1967     // check all the heap region->heap region edges
1968     Set sA = ogA.id2hrn.entrySet();
1969     Iterator iA = sA.iterator();
1970     while( iA.hasNext() ) {
1971       Map.Entry meA  = (Map.Entry)iA.next();
1972       Integer idA  = (Integer)        meA.getKey();
1973       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1974
1975       // we should have already checked that the same
1976       // heap regions exist in both graphs
1977       assert ogB.id2hrn.containsKey(idA);
1978
1979       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
1980         return false;
1981       }
1982
1983       // then check every edge in B for presence in A, starting
1984       // from the same parent HeapRegionNode
1985       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1986
1987       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
1988         return false;
1989       }
1990     }
1991
1992     // then check all the label->heap region edges
1993     sA = ogA.td2ln.entrySet();
1994     iA = sA.iterator();
1995     while( iA.hasNext() ) {
1996       Map.Entry meA = (Map.Entry)iA.next();
1997       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1998       LabelNode lnA = (LabelNode)      meA.getValue();
1999
2000       // we should have already checked that the same
2001       // label nodes exist in both graphs
2002       assert ogB.td2ln.containsKey(tdA);
2003
2004       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2005         return false;
2006       }
2007
2008       // then check every edge in B for presence in A, starting
2009       // from the same parent LabelNode
2010       LabelNode lnB = ogB.td2ln.get(tdA);
2011
2012       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2013         return false;
2014       }
2015     }
2016
2017     return true;
2018   }
2019
2020
2021   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2022                                                  OwnershipNode onA,
2023                                                  OwnershipGraph ogB) {
2024
2025     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2026     while( itrA.hasNext() ) {
2027       ReferenceEdge edgeA     = itrA.next();
2028       HeapRegionNode hrnChildA = edgeA.getDst();
2029       Integer idChildA  = hrnChildA.getID();
2030
2031       assert ogB.id2hrn.containsKey(idChildA);
2032
2033       // at this point we know an edge in graph A exists
2034       // onA -> idChildA, does this exact edge exist in B?
2035       boolean edgeFound = false;
2036
2037       OwnershipNode onB = null;
2038       if( onA instanceof HeapRegionNode ) {
2039         HeapRegionNode hrnA = (HeapRegionNode) onA;
2040         onB = ogB.id2hrn.get(hrnA.getID() );
2041       } else {
2042         LabelNode lnA = (LabelNode) onA;
2043         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2044       }
2045
2046       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2047       while( itrB.hasNext() ) {
2048         ReferenceEdge edgeB     = itrB.next();
2049         HeapRegionNode hrnChildB = edgeB.getDst();
2050         Integer idChildB  = hrnChildB.getID();
2051
2052         if( idChildA.equals(idChildB) &&
2053             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2054
2055           // there is an edge in the right place with the right field,
2056           // but do they have the same attributes?
2057           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2058
2059             edgeFound = true;
2060             //} else {
2061             //return false;
2062           }
2063         }
2064       }
2065
2066       if( !edgeFound ) {
2067         return false;
2068       }
2069     }
2070
2071     return true;
2072   }
2073
2074
2075   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2076     return id2paramIndex.size() == og.id2paramIndex.size();
2077   }
2078
2079
2080   /*
2081      // given a set B of heap region node ID's, return the set of heap
2082      // region node ID's that is reachable from B
2083      public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
2084
2085       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
2086       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2087
2088       // initial nodes to visit are from set B
2089       Iterator initialItr = idSetB.iterator();
2090       while( initialItr.hasNext() ) {
2091           Integer idInitial = (Integer) initialItr.next();
2092           assert id2hrn.contains( idInitial );
2093           HeapRegionNode hrnInitial = id2hrn.get( idInitial );
2094           toVisit.add( hrnInitial );
2095       }
2096
2097       HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
2098
2099       // do a heap traversal
2100       while( !toVisit.isEmpty() ) {
2101           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2102           toVisit.remove( hrnVisited );
2103           visited.add   ( hrnVisited );
2104
2105           // for every node visited, add it to the total
2106           // reachable set
2107           idSetReachableFromB.add( hrnVisited.getID() );
2108
2109           // find other reachable nodes
2110           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2111           while( referenceeItr.hasNext() ) {
2112               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2113               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2114               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2115
2116               if( !visited.contains( hrnReferencee ) ) {
2117                   toVisit.add( hrnReferencee );
2118               }
2119           }
2120       }
2121
2122       return idSetReachableFromB;
2123      }
2124
2125
2126      // used to find if a heap region can possibly have a reference to
2127      // any of the heap regions in the given set
2128      // if the id supplied is in the set, then a self-referencing edge
2129      // would return true, but that special case is specifically allowed
2130      // meaning that it isn't an external alias
2131      public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
2132
2133       assert id2hrn.contains( id );
2134       HeapRegionNode hrn = id2hrn.get( id );
2135
2136
2137       //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
2138
2139       //Iterator i = idSet.iterator();
2140       //while( i.hasNext() ) {
2141       //    Integer idFromSet = (Integer) i.next();
2142       //   assert id2hrn.contains( idFromSet );
2143       //    hrnSet.add( id2hrn.get( idFromSet ) );
2144       //}
2145
2146
2147       // do a traversal from hrn and see if any of the
2148       // heap regions from the set come up during that
2149       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
2150       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2151
2152       toVisit.add( hrn );
2153       while( !toVisit.isEmpty() ) {
2154           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2155           toVisit.remove( hrnVisited );
2156           visited.add   ( hrnVisited );
2157
2158           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2159           while( referenceeItr.hasNext() ) {
2160               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2161               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2162               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2163
2164               if( idSet.contains( hrnReferencee.getID() ) ) {
2165                   if( !id.equals( hrnReferencee.getID() ) ) {
2166                       return true;
2167                   }
2168               }
2169
2170               if( !visited.contains( hrnReferencee ) ) {
2171                   toVisit.add( hrnReferencee );
2172               }
2173           }
2174       }
2175
2176       return false;
2177      }
2178    */
2179
2180
2181   // for writing ownership graphs to dot files
2182   public void writeGraph(Descriptor methodDesc,
2183                          FlatNode fn,
2184                          boolean writeLabels,
2185                          boolean labelSelect,
2186                          boolean pruneGarbage,
2187                          boolean writeReferencers
2188                          ) throws java.io.IOException {
2189     writeGraph(
2190       methodDesc.getSymbol() +
2191       methodDesc.getNum() +
2192       fn.toString(),
2193       writeLabels,
2194       labelSelect,
2195       pruneGarbage,
2196       writeReferencers
2197       );
2198   }
2199
2200   public void writeGraph(Descriptor methodDesc,
2201                          FlatNode fn,
2202                          boolean writeLabels,
2203                          boolean writeReferencers
2204                          ) throws java.io.IOException {
2205     writeGraph(
2206       methodDesc.getSymbol() +
2207       methodDesc.getNum() +
2208       fn.toString(),
2209       writeLabels,
2210       false,
2211       false,
2212       writeReferencers
2213       );
2214   }
2215
2216   public void writeGraph(Descriptor methodDesc,
2217                          boolean writeLabels,
2218                          boolean writeReferencers
2219                          ) throws java.io.IOException {
2220     writeGraph(
2221       methodDesc.getSymbol() +
2222       methodDesc.getNum() +
2223       "COMPLETE",
2224       writeLabels,
2225       false,
2226       false,
2227       writeReferencers
2228       );
2229   }
2230
2231   public void writeGraph(Descriptor methodDesc,
2232                          boolean writeLabels,
2233                          boolean labelSelect,
2234                          boolean pruneGarbage,
2235                          boolean writeReferencers
2236                          ) throws java.io.IOException {
2237     writeGraph(
2238       methodDesc.getSymbol() +
2239       methodDesc.getNum() +
2240       "COMPLETE",
2241       writeLabels,
2242       labelSelect,
2243       pruneGarbage,
2244       writeReferencers
2245       );
2246   }
2247
2248   public void writeGraph(String graphName,
2249                          boolean writeLabels,
2250                          boolean labelSelect,
2251                          boolean pruneGarbage,
2252                          boolean writeReferencers
2253                          ) throws java.io.IOException {
2254
2255     // remove all non-word characters from the graph name so
2256     // the filename and identifier in dot don't cause errors
2257     graphName = graphName.replaceAll("[\\W]", "");
2258
2259     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2260     bw.write("digraph "+graphName+" {\n");
2261     //bw.write( "  size=\"7.5,10\";\n" );
2262
2263     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2264
2265     // then visit every heap region node
2266     if( !pruneGarbage ) {
2267       Set s = id2hrn.entrySet();
2268       Iterator i = s.iterator();
2269       while( i.hasNext() ) {
2270         Map.Entry me  = (Map.Entry)i.next();
2271         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2272         if( !visited.contains(hrn) ) {
2273           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2274                                   hrn,
2275                                   bw,
2276                                   null,
2277                                   visited,
2278                                   writeReferencers);
2279         }
2280       }
2281     }
2282
2283     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2284
2285
2286     // then visit every label node, useful for debugging
2287     if( writeLabels ) {
2288       Set s = td2ln.entrySet();
2289       Iterator i = s.iterator();
2290       while( i.hasNext() ) {
2291         Map.Entry me = (Map.Entry)i.next();
2292         LabelNode ln = (LabelNode) me.getValue();
2293
2294         if( labelSelect ) {
2295           String labelStr = ln.getTempDescriptorString();
2296           if( labelStr.startsWith("___temp") ||
2297               labelStr.startsWith("___dst") ||
2298               labelStr.startsWith("___srctmp") ||
2299               labelStr.startsWith("___neverused")   ) {
2300             continue;
2301           }
2302         }
2303
2304         bw.write(ln.toString() + ";\n");
2305
2306         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2307         while( heapRegionsItr.hasNext() ) {
2308           ReferenceEdge edge = heapRegionsItr.next();
2309           HeapRegionNode hrn  = edge.getDst();
2310
2311           if( pruneGarbage && !visited.contains(hrn) ) {
2312             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2313                                     hrn,
2314                                     bw,
2315                                     null,
2316                                     visited,
2317                                     writeReferencers);
2318           }
2319
2320           bw.write("  "        + ln.toString() +
2321                    " -> "      + hrn.toString() +
2322                    "[label=\"" + edge.toGraphEdgeString() +
2323                    "\",decorate];\n");
2324         }
2325       }
2326     }
2327
2328
2329     bw.write("}\n");
2330     bw.close();
2331   }
2332
2333   protected void traverseHeapRegionNodes(int mode,
2334                                          HeapRegionNode hrn,
2335                                          BufferedWriter bw,
2336                                          TempDescriptor td,
2337                                          HashSet<HeapRegionNode> visited,
2338                                          boolean writeReferencers
2339                                          ) throws java.io.IOException {
2340
2341     if( visited.contains(hrn) ) {
2342       return;
2343     }
2344     visited.add(hrn);
2345
2346     switch( mode ) {
2347     case VISIT_HRN_WRITE_FULL:
2348
2349       String attributes = "[";
2350
2351       if( hrn.isSingleObject() ) {
2352         attributes += "shape=box";
2353       } else {
2354         attributes += "shape=Msquare";
2355       }
2356
2357       if( hrn.isFlagged() ) {
2358         attributes += ",style=filled,fillcolor=lightgrey";
2359       }
2360
2361       attributes += ",label=\"ID"        +
2362                     hrn.getID()          +
2363                     "\\n"                +
2364                     hrn.getDescription() +
2365                     "\\n"                +
2366                     hrn.getAlphaString() +
2367                     "\"]";
2368
2369       bw.write("  " + hrn.toString() + attributes + ";\n");
2370       break;
2371     }
2372
2373
2374     // useful for debugging
2375     if( writeReferencers ) {
2376       OwnershipNode onRef  = null;
2377       Iterator refItr = hrn.iteratorToReferencers();
2378       while( refItr.hasNext() ) {
2379         onRef = (OwnershipNode) refItr.next();
2380
2381         switch( mode ) {
2382         case VISIT_HRN_WRITE_FULL:
2383           bw.write("  "                    + hrn.toString() +
2384                    " -> "                  + onRef.toString() +
2385                    "[color=lightgray];\n");
2386           break;
2387         }
2388       }
2389     }
2390
2391     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2392     while( childRegionsItr.hasNext() ) {
2393       ReferenceEdge edge     = childRegionsItr.next();
2394       HeapRegionNode hrnChild = edge.getDst();
2395
2396       switch( mode ) {
2397       case VISIT_HRN_WRITE_FULL:
2398         bw.write("  "        + hrn.toString() +
2399                  " -> "      + hrnChild.toString() +
2400                  "[label=\"" + edge.toGraphEdgeString() +
2401                  "\",decorate];\n");
2402         break;
2403       }
2404
2405       traverseHeapRegionNodes(mode,
2406                               hrnChild,
2407                               bw,
2408                               td,
2409                               visited,
2410                               writeReferencers);
2411     }
2412   }
2413 }