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       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode( allocSite );
1166       hrnShadowSummary.setAlpha( toShadowTokens( ogCallee, hrnSummaryCallee.getAlpha() ) );
1167
1168       // shadow nodes only are touched by a rewrite one time,
1169       // so rewrite and immediately commit--and they don't belong
1170       // to a particular parameter, so use a bogus param index
1171       // that pulls a self-rewrite out of H
1172       rewriteCallerNodeAlpha( fm.numParameters(),
1173                               bogusIndex,
1174                               hrnShadowSummary,
1175                               paramIndex2rewriteH,
1176                               paramIndex2rewriteD,
1177                               paramIndex2paramToken,
1178                               paramIndex2paramTokenStar );
1179
1180       hrnShadowSummary.applyAlphaNew();
1181
1182
1183       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1184         Integer idIth = allocSite.getIthOldest(i);
1185         assert id2hrn.containsKey(idIth);
1186         HeapRegionNode hrnIth = id2hrn.get(idIth);
1187
1188         Integer idShadowIth = -(allocSite.getIthOldest(i));
1189         assert id2hrn.containsKey(idShadowIth);
1190         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1191         assert hrnIthShadow.getNumReferencers() == 0;
1192         assert hrnIthShadow.getNumReferencees() == 0;
1193
1194         transferOnto( hrnIth, hrnIthShadow );
1195
1196         assert ogCallee.id2hrn.containsKey(idIth);
1197         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1198         hrnIthShadow.setAlpha( toShadowTokens( ogCallee, hrnIthCallee.getAlpha() ) );
1199
1200         rewriteCallerNodeAlpha( fm.numParameters(),
1201                                 bogusIndex,
1202                                 hrnIthShadow,
1203                                 paramIndex2rewriteH,
1204                                 paramIndex2rewriteD,
1205                                 paramIndex2paramToken,
1206                                 paramIndex2paramTokenStar );
1207
1208         hrnIthShadow.applyAlphaNew();
1209       }
1210     }
1211
1212
1213     try{
1214       writeGraph("test",true,true,true,false);
1215     } catch(Exception e){}
1216
1217
1218     // for every heap region->heap region edge in the
1219     // callee graph, create the matching edge or edges
1220     // in the caller graph
1221     Set      sCallee = ogCallee.id2hrn.entrySet();
1222     Iterator iCallee = sCallee.iterator();
1223     while( iCallee.hasNext() ) {
1224       Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
1225       Integer        idCallee  = (Integer)        meCallee.getKey();
1226       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1227
1228       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1229       while( heapRegionsItrCallee.hasNext() ) {
1230         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1231         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1232         Integer idChildCallee         = hrnChildCallee.getID();
1233
1234         // only address this edge if it is not a special reflexive edge
1235         if( !edgeCallee.isInitialParamReflexive() ) {
1236
1237           // now we know that in the callee method's ownership graph
1238           // there is a heap region->heap region reference edge given
1239           // by heap region pointers:
1240           // hrnCallee -> heapChildCallee
1241           //
1242           // or by the ownership-graph independent ID's:
1243           // idCallee -> idChildCallee
1244
1245           // make the edge with src and dst so beta info is
1246           // calculated once, then copy it for each new edge in caller
1247           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
1248                                                                      null,
1249                                                                      edgeCallee.getFieldDesc(),
1250                                                                      false,
1251                                                                      toShadowTokens( ogCallee, edgeCallee.getBeta() )
1252                                                                      );
1253           rewriteCallerEdgeBeta( fm.numParameters(),
1254                                  bogusIndex,
1255                                  edgeNewInCallerTemplate,
1256                                  paramIndex2rewriteJ,
1257                                  paramIndex2rewriteD,
1258                                  paramIndex2paramToken,
1259                                  paramIndex2paramTokenStar,
1260                                  false,
1261                                  null );
1262
1263           edgeNewInCallerTemplate.applyBetaNew();
1264
1265
1266
1267           // So now make a set of possible source heaps in the caller graph
1268           // and a set of destination heaps in the caller graph, and make
1269           // a reference edge in the caller for every possible (src,dst) pair
1270           HashSet<HeapRegionNode> possibleCallerSrcs =
1271             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1272                                                  edgeCallee,
1273                                                  true,
1274                                                  paramIndex2reachableCallerNodes );
1275
1276           HashSet<HeapRegionNode> possibleCallerDsts =
1277             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1278                                                  edgeCallee,
1279                                                  false,
1280                                                  paramIndex2reachableCallerNodes );
1281
1282           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1283           Iterator srcItr = possibleCallerSrcs.iterator();
1284           while( srcItr.hasNext() ) {
1285             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1286
1287             Iterator dstItr = possibleCallerDsts.iterator();
1288             while( dstItr.hasNext() ) {
1289               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1290
1291               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1292               edgeNewInCaller.setSrc( src );
1293               edgeNewInCaller.setDst( dst );
1294
1295               ReferenceEdge edgeExisting = src.getReferenceTo( dst, edgeNewInCaller.getFieldDesc() );
1296               if( edgeExisting == null ) {
1297                 // if this edge doesn't exist in the caller, create it
1298                 addReferenceEdge( src, dst, edgeNewInCaller );
1299               } else {
1300                 // if it already exists, merge with it
1301                 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
1302               }
1303             }
1304           }
1305         }
1306       }
1307     }
1308
1309
1310     // merge the shadow nodes of allocation sites back down to normal capacity
1311     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1312     while( allocItr.hasNext() ) {
1313       AllocationSite as = allocItr.next();
1314
1315       // first age each allocation site enough times to make room for the shadow nodes
1316       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1317         age( as );
1318       }
1319
1320       // then merge the shadow summary into the normal summary
1321       HeapRegionNode hrnSummary = getSummaryNode( as );
1322       assert hrnSummary != null;
1323
1324       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode( as );
1325       assert hrnSummaryShadow != null;
1326
1327       mergeIntoSummary( hrnSummaryShadow, hrnSummary );
1328
1329       // then transplant shadow nodes onto the now clean normal nodes
1330       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1331
1332         Integer idIth = as.getIthOldest(i);
1333         HeapRegionNode hrnIth = id2hrn.get(idIth);
1334
1335         Integer idIthShadow = as.getIthOldestShadow(i);
1336         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1337
1338         transferOnto(hrnIthShadow, hrnIth);
1339
1340         // clear off shadow nodes after transfer
1341         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1342         clearReferenceEdgesTo(hrnIthShadow, null, true);
1343         hrnIthShadow.setAlpha( new ReachabilitySet().makeCanonical() );
1344       }
1345
1346       // finally, globally change shadow tokens into normal tokens
1347       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1348       while( itrAllLabelNodes.hasNext() ) {
1349         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1350         LabelNode ln = (LabelNode) me.getValue();
1351
1352         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1353         while( itrEdges.hasNext() ) {
1354           unshadowTokens(as, itrEdges.next() );
1355         }
1356       }
1357
1358       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1359       while( itrAllHRNodes.hasNext() ) {
1360         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1361         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1362
1363         unshadowTokens(as, hrnToAge);
1364
1365         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1366         while( itrEdges.hasNext() ) {
1367           unshadowTokens(as, itrEdges.next() );
1368         }
1369       }
1370     }
1371   }
1372
1373
1374   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1375     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1376   }
1377
1378   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1379     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1380   }
1381
1382
1383   private ReachabilitySet toShadowTokens( OwnershipGraph ogCallee,
1384                                           ReachabilitySet rsIn ) {
1385
1386     ReachabilitySet rsOut = new ReachabilitySet( rsIn );
1387
1388     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1389     while( allocItr.hasNext() ) {
1390       AllocationSite as = allocItr.next();
1391
1392       rsOut = rsOut.toShadowTokens( as );
1393     }
1394
1395     return rsOut.makeCanonical();
1396   }
1397
1398
1399   private void rewriteCallerNodeAlpha( int numParameters,
1400                                        Integer paramIndex,
1401                                        HeapRegionNode hrn,
1402                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1403                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1404                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1405                                        Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1406
1407     ReachabilitySet rules = paramIndex2rewriteH.get( paramIndex );
1408     assert rules != null;
1409
1410     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1411     assert tokenToRewrite != null;
1412
1413     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1414     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1415     while( ttsItr.hasNext() ) {
1416       TokenTupleSet tts = ttsItr.next();
1417       r0 = r0.union( tts.rewriteToken( tokenToRewrite,
1418                                        hrn.getAlpha(),
1419                                        false,
1420                                        null ) );
1421     }
1422
1423     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1424     ttsItr = r0.iterator();
1425     while( ttsItr.hasNext() ) {
1426       TokenTupleSet tts = ttsItr.next();
1427       r1 = r1.union( rewriteDpass( numParameters,
1428                                    paramIndex,
1429                                    tts,
1430                                    paramIndex2rewriteD,
1431                                    paramIndex2paramToken,
1432                                    paramIndex2paramTokenStar ) );
1433     }
1434
1435     hrn.setAlphaNew( hrn.getAlphaNew().union( r1 ) );
1436   }
1437
1438
1439   private void rewriteCallerEdgeBeta( int numParameters,
1440                                       Integer paramIndex,
1441                                       ReferenceEdge edge,
1442                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1443                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1444                                       Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1445                                       Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1446                                       boolean makeChangeSet,
1447                                       Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1448
1449     ReachabilitySet rules = paramIndex2rewriteJorK.get( paramIndex );
1450     assert rules != null;
1451
1452     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1453     assert tokenToRewrite != null;
1454
1455     ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1456
1457     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1458     while( ttsItr.hasNext() ) {
1459       TokenTupleSet tts = ttsItr.next();
1460
1461       Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1462         new Hashtable<TokenTupleSet, TokenTupleSet>();
1463
1464       ReachabilitySet rTemp = tts.rewriteToken( tokenToRewrite,
1465                                                 edge.getBeta(),
1466                                                 true,
1467                                                 forChangeSet );
1468
1469       Iterator fcsItr = forChangeSet.entrySet().iterator();
1470       while( fcsItr.hasNext() ) {
1471         Map.Entry me = (Map.Entry) fcsItr.next();
1472         TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1473         TokenTupleSet ttsAdd   = (TokenTupleSet) me.getValue();
1474
1475         ChangeTuple ct = new ChangeTuple( ttsMatch,
1476                                           ttsAdd
1477                                           ).makeCanonical();
1478
1479         cts0 = cts0.union( ct );
1480       }
1481     }
1482
1483
1484     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1485     ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1486
1487     Iterator<ChangeTuple> ctItr = cts0.iterator();
1488     while( ctItr.hasNext() ) {
1489       ChangeTuple ct = ctItr.next();
1490
1491       ReachabilitySet rTemp = rewriteDpass( numParameters,
1492                                             paramIndex,
1493                                             ct.getSetToAdd(),
1494                                             paramIndex2rewriteD,
1495                                             paramIndex2paramToken,
1496                                             paramIndex2paramTokenStar
1497                                             ).makeCanonical();
1498       r1 = r1.union( rTemp );
1499
1500       if( makeChangeSet ) {
1501         assert edgePlannedChanges != null;
1502
1503         Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1504         while( ttsTempItr.hasNext() ) {
1505           TokenTupleSet tts = ttsTempItr.next();
1506
1507           ChangeTuple ctFinal = new ChangeTuple( ct.getSetToMatch(),
1508                                                  tts
1509                                                  ).makeCanonical();
1510
1511           cts1 = cts1.union( ctFinal );
1512         }
1513       }
1514     }
1515
1516     if( makeChangeSet ) {
1517       edgePlannedChanges.put( edge, cts1 );
1518     }
1519
1520     edge.setBetaNew( edge.getBetaNew().union( r1 ) );
1521   }
1522
1523
1524   private ReachabilitySet rewriteDpass( int numParameters,
1525                                         Integer paramIndex,
1526                                         TokenTupleSet ttsIn,
1527                                         Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1528                                         Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1529                                         Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1530
1531     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1532
1533     boolean rewritten = false;
1534
1535     for( int j = 0; j < numParameters; ++j ) {
1536       Integer paramIndexJ = new Integer( j );
1537       ReachabilitySet D_j = paramIndex2rewriteD.get( paramIndexJ );
1538       assert D_j != null;
1539
1540       if( paramIndexJ != paramIndex ) {
1541         TokenTuple tokenToRewriteJ = paramIndex2paramToken.get( paramIndexJ );
1542         assert tokenToRewriteJ != null;
1543         if( ttsIn.containsTuple( tokenToRewriteJ ) ) {
1544           ReachabilitySet r = ttsIn.rewriteToken( tokenToRewriteJ,
1545                                                   D_j,
1546                                                   false,
1547                                                   null );
1548           Iterator<TokenTupleSet> ttsItr = r.iterator();
1549           while( ttsItr.hasNext() ) {
1550             TokenTupleSet tts = ttsItr.next();
1551             rsOut = rsOut.union( rewriteDpass( numParameters,
1552                                                paramIndex,
1553                                                tts,
1554                                                paramIndex2rewriteD,
1555                                                paramIndex2paramToken,
1556                                                paramIndex2paramTokenStar ) );
1557             rewritten = true;
1558           }
1559         }
1560       }
1561
1562       TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get( paramIndexJ );
1563       assert tokenStarToRewriteJ != null;
1564       if( ttsIn.containsTuple( tokenStarToRewriteJ ) ) {
1565         ReachabilitySet r = ttsIn.rewriteToken( tokenStarToRewriteJ,
1566                                                 D_j,
1567                                                 false,
1568                                                 null );
1569         Iterator<TokenTupleSet> ttsItr = r.iterator();
1570         while( ttsItr.hasNext() ) {
1571           TokenTupleSet tts = ttsItr.next();
1572           rsOut = rsOut.union( rewriteDpass( numParameters,
1573                                              paramIndex,
1574                                              tts,
1575                                              paramIndex2rewriteD,
1576                                              paramIndex2paramToken,
1577                                              paramIndex2paramTokenStar ) );
1578           rewritten = true;
1579         }
1580       }
1581     }
1582
1583     if( !rewritten ) {
1584       rsOut = rsOut.union( ttsIn );
1585     }
1586
1587     return rsOut;
1588   }
1589
1590
1591   private HashSet<HeapRegionNode>
1592     getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
1593                                          ReferenceEdge edgeCallee,
1594                                          boolean mapFromSrc,
1595                                          Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1596                                          ) {
1597
1598     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1599
1600     HeapRegionNode hrnCallee;
1601     if( mapFromSrc ) {
1602       OwnershipNode on = edgeCallee.getSrc();
1603       assert on instanceof HeapRegionNode;
1604       hrnCallee = (HeapRegionNode) on;
1605     } else {
1606       hrnCallee = edgeCallee.getDst();
1607     }
1608
1609     Integer paramIndexCallee = ogCallee.id2paramIndex.get( hrnCallee.getID() );
1610
1611     if( paramIndexCallee == null ) {
1612       // this is a node allocated in the callee then and it has
1613       // exactly one shadow node in the caller to map to
1614       AllocationSite as = hrnCallee.getAllocationSite();
1615       assert as != null;
1616
1617       int age = as.getAgeCategory( hrnCallee.getID() );
1618       assert age != AllocationSite.AGE_notInThisSite;
1619
1620       Integer idCaller;
1621       if( age == AllocationSite.AGE_summary ) {
1622         idCaller = as.getSummaryShadow();
1623       } else if( age == AllocationSite.AGE_oldest ) {
1624         idCaller = as.getOldestShadow();
1625       } else {
1626         assert age == AllocationSite.AGE_in_I;
1627
1628         Integer I = as.getAge( hrnCallee.getID() );
1629         assert I != null;
1630
1631         idCaller = as.getIthOldestShadow( I );
1632       }
1633
1634       assert id2hrn.containsKey( idCaller );
1635       HeapRegionNode hrnCaller = id2hrn.get( idCaller );
1636       possibleCallerHRNs.add( hrnCaller );
1637
1638     } else {
1639       // this is a node that was created to represent a parameter
1640       // so it maps to a whole mess of heap regions
1641       assert paramIndex2reachableCallerNodes.containsKey( paramIndexCallee );
1642       possibleCallerHRNs = paramIndex2reachableCallerNodes.get( paramIndexCallee );
1643
1644       // TODO PRUNE BY TYPE/FIELD NAME!!
1645     }
1646
1647     return possibleCallerHRNs;
1648   }
1649
1650
1651
1652   ////////////////////////////////////////////////////
1653   // in merge() and equals() methods the suffix A
1654   // represents the passed in graph and the suffix
1655   // B refers to the graph in this object
1656   // Merging means to take the incoming graph A and
1657   // merge it into B, so after the operation graph B
1658   // is the final result.
1659   ////////////////////////////////////////////////////
1660   public void merge(OwnershipGraph og) {
1661
1662     if( og == null ) {
1663       return;
1664     }
1665
1666     mergeOwnershipNodes(og);
1667     mergeReferenceEdges(og);
1668     mergeId2paramIndex(og);
1669     mergeAllocationSites(og);
1670   }
1671
1672
1673   protected void mergeOwnershipNodes(OwnershipGraph og) {
1674     Set sA = og.id2hrn.entrySet();
1675     Iterator iA = sA.iterator();
1676     while( iA.hasNext() ) {
1677       Map.Entry meA  = (Map.Entry)iA.next();
1678       Integer idA  = (Integer)        meA.getKey();
1679       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1680
1681       // if this graph doesn't have a node the
1682       // incoming graph has, allocate it
1683       if( !id2hrn.containsKey(idA) ) {
1684         HeapRegionNode hrnB = hrnA.copy();
1685         id2hrn.put(idA, hrnB);
1686
1687       } else {
1688         // otherwise this is a node present in both graphs
1689         // so make the new reachability set a union of the
1690         // nodes' reachability sets
1691         HeapRegionNode hrnB = id2hrn.get(idA);
1692         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1693       }
1694     }
1695
1696     // now add any label nodes that are in graph B but
1697     // not in A
1698     sA = og.td2ln.entrySet();
1699     iA = sA.iterator();
1700     while( iA.hasNext() ) {
1701       Map.Entry meA = (Map.Entry)iA.next();
1702       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1703       LabelNode lnA = (LabelNode)      meA.getValue();
1704
1705       // if the label doesn't exist in B, allocate and add it
1706       LabelNode lnB = getLabelNodeFromTemp(tdA);
1707     }
1708   }
1709
1710   protected void mergeReferenceEdges(OwnershipGraph og) {
1711
1712     // heap regions
1713     Set sA = og.id2hrn.entrySet();
1714     Iterator iA = sA.iterator();
1715     while( iA.hasNext() ) {
1716       Map.Entry meA  = (Map.Entry)iA.next();
1717       Integer idA  = (Integer)        meA.getKey();
1718       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1719
1720       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1721       while( heapRegionsItrA.hasNext() ) {
1722         ReferenceEdge edgeA     = heapRegionsItrA.next();
1723         HeapRegionNode hrnChildA = edgeA.getDst();
1724         Integer idChildA  = hrnChildA.getID();
1725
1726         // at this point we know an edge in graph A exists
1727         // idA -> idChildA, does this exist in B?
1728         assert id2hrn.containsKey(idA);
1729         HeapRegionNode hrnB        = id2hrn.get(idA);
1730         ReferenceEdge edgeToMerge = null;
1731
1732         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1733         while( heapRegionsItrB.hasNext() &&
1734                edgeToMerge == null          ) {
1735
1736           ReferenceEdge edgeB     = heapRegionsItrB.next();
1737           HeapRegionNode hrnChildB = edgeB.getDst();
1738           Integer idChildB  = hrnChildB.getID();
1739
1740           // don't use the ReferenceEdge.equals() here because
1741           // we're talking about existence between graphs
1742           if( idChildB.equals(idChildA) &&
1743               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1744             edgeToMerge = edgeB;
1745           }
1746         }
1747
1748         // if the edge from A was not found in B,
1749         // add it to B.
1750         if( edgeToMerge == null ) {
1751           assert id2hrn.containsKey(idChildA);
1752           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1753           edgeToMerge = edgeA.copy();
1754           edgeToMerge.setSrc(hrnB);
1755           edgeToMerge.setDst(hrnChildB);
1756           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1757         }
1758         // otherwise, the edge already existed in both graphs
1759         // so merge their reachability sets
1760         else {
1761           // just replace this beta set with the union
1762           assert edgeToMerge != null;
1763           edgeToMerge.setBeta(
1764             edgeToMerge.getBeta().union(edgeA.getBeta() )
1765             );
1766           if( !edgeA.isInitialParamReflexive() ) {
1767             edgeToMerge.setIsInitialParamReflexive(false);
1768           }
1769         }
1770       }
1771     }
1772
1773     // and then again with label nodes
1774     sA = og.td2ln.entrySet();
1775     iA = sA.iterator();
1776     while( iA.hasNext() ) {
1777       Map.Entry meA = (Map.Entry)iA.next();
1778       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1779       LabelNode lnA = (LabelNode)      meA.getValue();
1780
1781       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1782       while( heapRegionsItrA.hasNext() ) {
1783         ReferenceEdge edgeA     = heapRegionsItrA.next();
1784         HeapRegionNode hrnChildA = edgeA.getDst();
1785         Integer idChildA  = hrnChildA.getID();
1786
1787         // at this point we know an edge in graph A exists
1788         // tdA -> idChildA, does this exist in B?
1789         assert td2ln.containsKey(tdA);
1790         LabelNode lnB         = td2ln.get(tdA);
1791         ReferenceEdge edgeToMerge = null;
1792
1793         // labels never have edges with a field
1794         //assert edgeA.getFieldDesc() == null;
1795
1796         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1797         while( heapRegionsItrB.hasNext() &&
1798                edgeToMerge == null          ) {
1799
1800           ReferenceEdge edgeB     = heapRegionsItrB.next();
1801           HeapRegionNode hrnChildB = edgeB.getDst();
1802           Integer idChildB  = hrnChildB.getID();
1803
1804           // labels never have edges with a field
1805           //assert edgeB.getFieldDesc() == null;
1806
1807           // don't use the ReferenceEdge.equals() here because
1808           // we're talking about existence between graphs
1809           if( idChildB.equals(idChildA) &&
1810               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1811             edgeToMerge = edgeB;
1812           }
1813         }
1814
1815         // if the edge from A was not found in B,
1816         // add it to B.
1817         if( edgeToMerge == null ) {
1818           assert id2hrn.containsKey(idChildA);
1819           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1820           edgeToMerge = edgeA.copy();
1821           edgeToMerge.setSrc(lnB);
1822           edgeToMerge.setDst(hrnChildB);
1823           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1824         }
1825         // otherwise, the edge already existed in both graphs
1826         // so merge their reachability sets
1827         else {
1828           // just replace this beta set with the union
1829           edgeToMerge.setBeta(
1830             edgeToMerge.getBeta().union(edgeA.getBeta() )
1831             );
1832           if( !edgeA.isInitialParamReflexive() ) {
1833             edgeToMerge.setIsInitialParamReflexive(false);
1834           }
1835         }
1836       }
1837     }
1838   }
1839
1840   // you should only merge ownership graphs that have the
1841   // same number of parameters, or if one or both parameter
1842   // index tables are empty
1843   protected void mergeId2paramIndex(OwnershipGraph og) {
1844     if( id2paramIndex.size() == 0 ) {
1845       id2paramIndex  = og.id2paramIndex;
1846       paramIndex2id  = og.paramIndex2id;
1847       paramIndex2tdQ = og.paramIndex2tdQ;
1848       return;
1849     }
1850
1851     if( og.id2paramIndex.size() == 0 ) {
1852       return;
1853     }
1854
1855     assert id2paramIndex.size() == og.id2paramIndex.size();
1856   }
1857
1858   protected void mergeAllocationSites(OwnershipGraph og) {
1859     allocationSites.addAll(og.allocationSites);
1860   }
1861
1862
1863
1864   // it is necessary in the equals() member functions
1865   // to "check both ways" when comparing the data
1866   // structures of two graphs.  For instance, if all
1867   // edges between heap region nodes in graph A are
1868   // present and equal in graph B it is not sufficient
1869   // to say the graphs are equal.  Consider that there
1870   // may be edges in graph B that are not in graph A.
1871   // the only way to know that all edges in both graphs
1872   // are equally present is to iterate over both data
1873   // structures and compare against the other graph.
1874   public boolean equals(OwnershipGraph og) {
1875
1876     if( og == null ) {
1877       return false;
1878     }
1879
1880     if( !areHeapRegionNodesEqual(og) ) {
1881       return false;
1882     }
1883
1884     if( !areLabelNodesEqual(og) ) {
1885       return false;
1886     }
1887
1888     if( !areReferenceEdgesEqual(og) ) {
1889       return false;
1890     }
1891
1892     if( !areId2paramIndexEqual(og) ) {
1893       return false;
1894     }
1895
1896     // if everything is equal up to this point,
1897     // assert that allocationSites is also equal--
1898     // this data is redundant and kept for efficiency
1899     assert allocationSites.equals(og.allocationSites);
1900
1901     return true;
1902   }
1903
1904   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
1905
1906     if( !areallHRNinAalsoinBandequal(this, og) ) {
1907       return false;
1908     }
1909
1910     if( !areallHRNinAalsoinBandequal(og, this) ) {
1911       return false;
1912     }
1913
1914     return true;
1915   }
1916
1917   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
1918                                                        OwnershipGraph ogB) {
1919     Set sA = ogA.id2hrn.entrySet();
1920     Iterator iA = sA.iterator();
1921     while( iA.hasNext() ) {
1922       Map.Entry meA  = (Map.Entry)iA.next();
1923       Integer idA  = (Integer)        meA.getKey();
1924       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1925
1926       if( !ogB.id2hrn.containsKey(idA) ) {
1927         return false;
1928       }
1929
1930       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1931       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
1932         return false;
1933       }
1934     }
1935
1936     return true;
1937   }
1938
1939
1940   protected boolean areLabelNodesEqual(OwnershipGraph og) {
1941
1942     if( !areallLNinAalsoinBandequal(this, og) ) {
1943       return false;
1944     }
1945
1946     if( !areallLNinAalsoinBandequal(og, this) ) {
1947       return false;
1948     }
1949
1950     return true;
1951   }
1952
1953   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
1954                                                       OwnershipGraph ogB) {
1955     Set sA = ogA.td2ln.entrySet();
1956     Iterator iA = sA.iterator();
1957     while( iA.hasNext() ) {
1958       Map.Entry meA = (Map.Entry)iA.next();
1959       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1960
1961       if( !ogB.td2ln.containsKey(tdA) ) {
1962         return false;
1963       }
1964     }
1965
1966     return true;
1967   }
1968
1969
1970   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
1971     if( !areallREinAandBequal(this, og) ) {
1972       return false;
1973     }
1974
1975     return true;
1976   }
1977
1978   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
1979                                                 OwnershipGraph ogB) {
1980
1981     // check all the heap region->heap region edges
1982     Set sA = ogA.id2hrn.entrySet();
1983     Iterator iA = sA.iterator();
1984     while( iA.hasNext() ) {
1985       Map.Entry meA  = (Map.Entry)iA.next();
1986       Integer idA  = (Integer)        meA.getKey();
1987       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1988
1989       // we should have already checked that the same
1990       // heap regions exist in both graphs
1991       assert ogB.id2hrn.containsKey(idA);
1992
1993       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
1994         return false;
1995       }
1996
1997       // then check every edge in B for presence in A, starting
1998       // from the same parent HeapRegionNode
1999       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2000
2001       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2002         return false;
2003       }
2004     }
2005
2006     // then check all the label->heap region edges
2007     sA = ogA.td2ln.entrySet();
2008     iA = sA.iterator();
2009     while( iA.hasNext() ) {
2010       Map.Entry meA = (Map.Entry)iA.next();
2011       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2012       LabelNode lnA = (LabelNode)      meA.getValue();
2013
2014       // we should have already checked that the same
2015       // label nodes exist in both graphs
2016       assert ogB.td2ln.containsKey(tdA);
2017
2018       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2019         return false;
2020       }
2021
2022       // then check every edge in B for presence in A, starting
2023       // from the same parent LabelNode
2024       LabelNode lnB = ogB.td2ln.get(tdA);
2025
2026       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2027         return false;
2028       }
2029     }
2030
2031     return true;
2032   }
2033
2034
2035   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2036                                                  OwnershipNode onA,
2037                                                  OwnershipGraph ogB) {
2038
2039     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2040     while( itrA.hasNext() ) {
2041       ReferenceEdge edgeA     = itrA.next();
2042       HeapRegionNode hrnChildA = edgeA.getDst();
2043       Integer idChildA  = hrnChildA.getID();
2044
2045       assert ogB.id2hrn.containsKey(idChildA);
2046
2047       // at this point we know an edge in graph A exists
2048       // onA -> idChildA, does this exact edge exist in B?
2049       boolean edgeFound = false;
2050
2051       OwnershipNode onB = null;
2052       if( onA instanceof HeapRegionNode ) {
2053         HeapRegionNode hrnA = (HeapRegionNode) onA;
2054         onB = ogB.id2hrn.get(hrnA.getID() );
2055       } else {
2056         LabelNode lnA = (LabelNode) onA;
2057         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2058       }
2059
2060       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2061       while( itrB.hasNext() ) {
2062         ReferenceEdge edgeB     = itrB.next();
2063         HeapRegionNode hrnChildB = edgeB.getDst();
2064         Integer idChildB  = hrnChildB.getID();
2065
2066         if( idChildA.equals(idChildB) &&
2067             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2068
2069           // there is an edge in the right place with the right field,
2070           // but do they have the same attributes?
2071           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2072
2073             edgeFound = true;
2074             //} else {
2075             //return false;
2076           }
2077         }
2078       }
2079
2080       if( !edgeFound ) {
2081         return false;
2082       }
2083     }
2084
2085     return true;
2086   }
2087
2088
2089   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2090     return id2paramIndex.size() == og.id2paramIndex.size();
2091   }
2092
2093
2094   /*
2095      // given a set B of heap region node ID's, return the set of heap
2096      // region node ID's that is reachable from B
2097      public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
2098
2099       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
2100       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2101
2102       // initial nodes to visit are from set B
2103       Iterator initialItr = idSetB.iterator();
2104       while( initialItr.hasNext() ) {
2105           Integer idInitial = (Integer) initialItr.next();
2106           assert id2hrn.contains( idInitial );
2107           HeapRegionNode hrnInitial = id2hrn.get( idInitial );
2108           toVisit.add( hrnInitial );
2109       }
2110
2111       HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
2112
2113       // do a heap traversal
2114       while( !toVisit.isEmpty() ) {
2115           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2116           toVisit.remove( hrnVisited );
2117           visited.add   ( hrnVisited );
2118
2119           // for every node visited, add it to the total
2120           // reachable set
2121           idSetReachableFromB.add( hrnVisited.getID() );
2122
2123           // find other reachable nodes
2124           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2125           while( referenceeItr.hasNext() ) {
2126               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2127               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2128               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2129
2130               if( !visited.contains( hrnReferencee ) ) {
2131                   toVisit.add( hrnReferencee );
2132               }
2133           }
2134       }
2135
2136       return idSetReachableFromB;
2137      }
2138
2139
2140      // used to find if a heap region can possibly have a reference to
2141      // any of the heap regions in the given set
2142      // if the id supplied is in the set, then a self-referencing edge
2143      // would return true, but that special case is specifically allowed
2144      // meaning that it isn't an external alias
2145      public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
2146
2147       assert id2hrn.contains( id );
2148       HeapRegionNode hrn = id2hrn.get( id );
2149
2150
2151       //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
2152
2153       //Iterator i = idSet.iterator();
2154       //while( i.hasNext() ) {
2155       //    Integer idFromSet = (Integer) i.next();
2156       //   assert id2hrn.contains( idFromSet );
2157       //    hrnSet.add( id2hrn.get( idFromSet ) );
2158       //}
2159
2160
2161       // do a traversal from hrn and see if any of the
2162       // heap regions from the set come up during that
2163       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
2164       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2165
2166       toVisit.add( hrn );
2167       while( !toVisit.isEmpty() ) {
2168           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2169           toVisit.remove( hrnVisited );
2170           visited.add   ( hrnVisited );
2171
2172           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2173           while( referenceeItr.hasNext() ) {
2174               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2175               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2176               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2177
2178               if( idSet.contains( hrnReferencee.getID() ) ) {
2179                   if( !id.equals( hrnReferencee.getID() ) ) {
2180                       return true;
2181                   }
2182               }
2183
2184               if( !visited.contains( hrnReferencee ) ) {
2185                   toVisit.add( hrnReferencee );
2186               }
2187           }
2188       }
2189
2190       return false;
2191      }
2192    */
2193
2194
2195   // for writing ownership graphs to dot files
2196   public void writeGraph(Descriptor methodDesc,
2197                          FlatNode fn,
2198                          boolean writeLabels,
2199                          boolean labelSelect,
2200                          boolean pruneGarbage,
2201                          boolean writeReferencers
2202                          ) throws java.io.IOException {
2203     writeGraph(
2204       methodDesc.getSymbol() +
2205       methodDesc.getNum() +
2206       fn.toString(),
2207       writeLabels,
2208       labelSelect,
2209       pruneGarbage,
2210       writeReferencers
2211       );
2212   }
2213
2214   public void writeGraph(Descriptor methodDesc,
2215                          FlatNode fn,
2216                          boolean writeLabels,
2217                          boolean writeReferencers
2218                          ) throws java.io.IOException {
2219     writeGraph(
2220       methodDesc.getSymbol() +
2221       methodDesc.getNum() +
2222       fn.toString(),
2223       writeLabels,
2224       false,
2225       false,
2226       writeReferencers
2227       );
2228   }
2229
2230   public void writeGraph(Descriptor methodDesc,
2231                          boolean writeLabels,
2232                          boolean writeReferencers
2233                          ) throws java.io.IOException {
2234     writeGraph(
2235       methodDesc.getSymbol() +
2236       methodDesc.getNum() +
2237       "COMPLETE",
2238       writeLabels,
2239       false,
2240       false,
2241       writeReferencers
2242       );
2243   }
2244
2245   public void writeGraph(Descriptor methodDesc,
2246                          boolean writeLabels,
2247                          boolean labelSelect,
2248                          boolean pruneGarbage,
2249                          boolean writeReferencers
2250                          ) throws java.io.IOException {
2251     writeGraph(
2252       methodDesc.getSymbol() +
2253       methodDesc.getNum() +
2254       "COMPLETE",
2255       writeLabels,
2256       labelSelect,
2257       pruneGarbage,
2258       writeReferencers
2259       );
2260   }
2261
2262   public void writeGraph(String graphName,
2263                          boolean writeLabels,
2264                          boolean labelSelect,
2265                          boolean pruneGarbage,
2266                          boolean writeReferencers
2267                          ) throws java.io.IOException {
2268
2269     // remove all non-word characters from the graph name so
2270     // the filename and identifier in dot don't cause errors
2271     graphName = graphName.replaceAll("[\\W]", "");
2272
2273     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2274     bw.write("digraph "+graphName+" {\n");
2275     //bw.write( "  size=\"7.5,10\";\n" );
2276
2277     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2278
2279     // then visit every heap region node
2280     if( !pruneGarbage ) {
2281       Set s = id2hrn.entrySet();
2282       Iterator i = s.iterator();
2283       while( i.hasNext() ) {
2284         Map.Entry me  = (Map.Entry)i.next();
2285         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2286         if( !visited.contains(hrn) ) {
2287           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2288                                   hrn,
2289                                   bw,
2290                                   null,
2291                                   visited,
2292                                   writeReferencers);
2293         }
2294       }
2295     }
2296
2297     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2298
2299
2300     // then visit every label node, useful for debugging
2301     if( writeLabels ) {
2302       Set s = td2ln.entrySet();
2303       Iterator i = s.iterator();
2304       while( i.hasNext() ) {
2305         Map.Entry me = (Map.Entry)i.next();
2306         LabelNode ln = (LabelNode) me.getValue();
2307
2308         if( labelSelect ) {
2309           String labelStr = ln.getTempDescriptorString();
2310           if( labelStr.startsWith("___temp") ||
2311               labelStr.startsWith("___dst") ||
2312               labelStr.startsWith("___srctmp") ||
2313               labelStr.startsWith("___neverused")   ) {
2314             continue;
2315           }
2316         }
2317
2318         bw.write(ln.toString() + ";\n");
2319
2320         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2321         while( heapRegionsItr.hasNext() ) {
2322           ReferenceEdge edge = heapRegionsItr.next();
2323           HeapRegionNode hrn  = edge.getDst();
2324
2325           if( pruneGarbage && !visited.contains(hrn) ) {
2326             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2327                                     hrn,
2328                                     bw,
2329                                     null,
2330                                     visited,
2331                                     writeReferencers);
2332           }
2333
2334           bw.write("  "        + ln.toString() +
2335                    " -> "      + hrn.toString() +
2336                    "[label=\"" + edge.toGraphEdgeString() +
2337                    "\",decorate];\n");
2338         }
2339       }
2340     }
2341
2342
2343     bw.write("}\n");
2344     bw.close();
2345   }
2346
2347   protected void traverseHeapRegionNodes(int mode,
2348                                          HeapRegionNode hrn,
2349                                          BufferedWriter bw,
2350                                          TempDescriptor td,
2351                                          HashSet<HeapRegionNode> visited,
2352                                          boolean writeReferencers
2353                                          ) throws java.io.IOException {
2354
2355     if( visited.contains(hrn) ) {
2356       return;
2357     }
2358     visited.add(hrn);
2359
2360     switch( mode ) {
2361     case VISIT_HRN_WRITE_FULL:
2362
2363       String attributes = "[";
2364
2365       if( hrn.isSingleObject() ) {
2366         attributes += "shape=box";
2367       } else {
2368         attributes += "shape=Msquare";
2369       }
2370
2371       if( hrn.isFlagged() ) {
2372         attributes += ",style=filled,fillcolor=lightgrey";
2373       }
2374
2375       attributes += ",label=\"ID"        +
2376                     hrn.getID()          +
2377                     "\\n"                +
2378                     hrn.getDescription() +
2379                     "\\n"                +
2380                     hrn.getAlphaString() +
2381                     "\"]";
2382
2383       bw.write("  " + hrn.toString() + attributes + ";\n");
2384       break;
2385     }
2386
2387
2388     // useful for debugging
2389     if( writeReferencers ) {
2390       OwnershipNode onRef  = null;
2391       Iterator refItr = hrn.iteratorToReferencers();
2392       while( refItr.hasNext() ) {
2393         onRef = (OwnershipNode) refItr.next();
2394
2395         switch( mode ) {
2396         case VISIT_HRN_WRITE_FULL:
2397           bw.write("  "                    + hrn.toString() +
2398                    " -> "                  + onRef.toString() +
2399                    "[color=lightgray];\n");
2400           break;
2401         }
2402       }
2403     }
2404
2405     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2406     while( childRegionsItr.hasNext() ) {
2407       ReferenceEdge edge     = childRegionsItr.next();
2408       HeapRegionNode hrnChild = edge.getDst();
2409
2410       switch( mode ) {
2411       case VISIT_HRN_WRITE_FULL:
2412         bw.write("  "        + hrn.toString() +
2413                  " -> "      + hrnChild.toString() +
2414                  "[label=\"" + edge.toGraphEdgeString() +
2415                  "\",decorate];\n");
2416         break;
2417       }
2418
2419       traverseHeapRegionNodes(mode,
2420                               hrnChild,
2421                               bw,
2422                               td,
2423                               visited,
2424                               writeReferencers);
2425     }
2426   }
2427 }