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   protected void majorAgeTokens(AllocationSite as, ReferenceEdge edge) {
 864     //edge.setBeta( edge.getBeta().majorAgeTokens( as ) );
 865   }
 866
 867   protected void majorAgeTokens(AllocationSite as, HeapRegionNode hrn) {
 868     //hrn.setAlpha( hrn.getAlpha().majorAgeTokens( as ) );
 869   }
 870
 871
 872   public void resolveMethodCall(FlatCall fc,
 873                                 boolean isStatic,
 874                                 FlatMethod fm,
 875                                 OwnershipGraph ogCallee) {
 876
 877
 878     // define rewrite rules and other structures to organize
 879     // data by parameter/argument index
 880     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
 881       new Hashtable<Integer, ReachabilitySet>();
 882
 883     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
 884       new Hashtable<Integer, ReachabilitySet>();
 885
 886     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
 887       new Hashtable<Integer, ReachabilitySet>();
 888
 889     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
 890       new Hashtable<Integer, ReachabilitySet>();
 891
 892     // helpful structures
 893     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
 894       new Hashtable<TokenTuple, Integer>();
 895
 896     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
 897       new Hashtable<Integer, TokenTuple>();
 898
 899     Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
 900       new Hashtable<TokenTuple, Integer>();
 901
 902     Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
 903       new Hashtable<Integer, TokenTuple>();
 904
 905     Hashtable<Integer, LabelNode> paramIndex2ln =
 906       new Hashtable<Integer, LabelNode>();
 907
 908     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
 909       new Hashtable<Integer, HashSet<HeapRegionNode> >();
 910
 911
 912     // add a bogus entry with the identity rule for easy rewrite
 913     // of new callee nodes and edges, doesn't belong to any parameter
 914     Integer bogusID = new Integer( -1 );
 915     Integer bogusIndex = new Integer( -1 );
 916     TokenTuple bogusToken = new TokenTuple( bogusID, true, TokenTuple.ARITY_ONE );
 917     TokenTuple bogusTokenStar = new TokenTuple( bogusID, true, TokenTuple.ARITY_MANY );
 918     ReachabilitySet rsIdentity =
 919       new ReachabilitySet( new TokenTupleSet( bogusToken ).makeCanonical() ).makeCanonical();
 920
 921     paramIndex2rewriteH.put( bogusIndex, rsIdentity );
 922     paramIndex2rewriteJ.put( bogusIndex, rsIdentity );
 923     paramToken2paramIndex.put( bogusToken, bogusIndex );
 924     paramIndex2paramToken.put( bogusIndex, bogusToken );
 925     paramTokenStar2paramIndex.put( bogusTokenStar, bogusIndex );
 926     paramIndex2paramTokenStar.put( bogusIndex, bogusTokenStar );
 927
 928
 929     for( int i = 0; i < fm.numParameters(); ++i ) {
 930       Integer paramIndex = new Integer( i );
 931
 932       assert ogCallee.paramIndex2id.containsKey( paramIndex );
 933       Integer idParam = ogCallee.paramIndex2id.get( paramIndex );
 934
 935       assert ogCallee.id2hrn.containsKey( idParam );
 936       HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
 937       assert hrnParam != null;
 938       paramIndex2rewriteH.put( paramIndex, hrnParam.getAlpha() );
 939
 940       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo( hrnParam, null );
 941       assert edgeReflexive_i != null;
 942       paramIndex2rewriteJ.put( paramIndex, edgeReflexive_i.getBeta() );
 943
 944       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get( paramIndex );
 945       assert tdParamQ != null;
 946       LabelNode lnParamQ = ogCallee.td2ln.get( tdParamQ );
 947       assert lnParamQ != null;
 948       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo( hrnParam, null );
 949       assert edgeSpecialQ_i != null;
 950       paramIndex2rewriteK.put( paramIndex, edgeSpecialQ_i.getBeta() );
 951
 952       TokenTuple p_i = new TokenTuple( hrnParam.getID(),
 953                                        true,
 954                                        TokenTuple.ARITY_ONE ).makeCanonical();
 955       paramToken2paramIndex.put( p_i, paramIndex );
 956       paramIndex2paramToken.put( paramIndex, p_i );
 957
 958       TokenTuple p_i_star = new TokenTuple( hrnParam.getID(),
 959                                             true,
 960                                             TokenTuple.ARITY_MANY ).makeCanonical();
 961       paramTokenStar2paramIndex.put( p_i_star, paramIndex );
 962       paramIndex2paramTokenStar.put( paramIndex, p_i_star );
 963
 964       // now depending on whether the callee is static or not
 965       // we need to account for a "this" argument in order to
 966       // find the matching argument in the caller context
 967       TempDescriptor argTemp_i;
 968       if( isStatic ) {
 969         argTemp_i = fc.getArg( paramIndex );
 970       } else {
 971         if( paramIndex == 0 ) {
 972           argTemp_i = fc.getThis();
 973         } else {
 974           argTemp_i = fc.getArg( paramIndex - 1 );
 975         }
 976       }
 977
 978       // in non-static methods there is a "this" pointer
 979       // that should be taken into account
 980       if( isStatic ) {
 981         assert fc.numArgs()     == fm.numParameters();
 982       } else {
 983         assert fc.numArgs() + 1 == fm.numParameters();
 984       }
 985
 986       LabelNode argLabel_i = getLabelNodeFromTemp( argTemp_i );
 987       paramIndex2ln.put( paramIndex, argLabel_i );
 988
 989       ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
 990       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
 991       while( edgeItr.hasNext() ) {
 992         ReferenceEdge edge = edgeItr.next();
 993         D_i = D_i.union( edge.getBeta() );
 994       }
 995       D_i = D_i.exhaustiveArityCombinations();
 996       paramIndex2rewriteD.put( paramIndex, D_i );
 997     }
 998
 999
1000     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1001     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1002
1003     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1004     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1005
1006     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1007     while( lnArgItr.hasNext() ) {
1008       Map.Entry me      = (Map.Entry) lnArgItr.next();
1009       Integer   index   = (Integer)   me.getKey();
1010       LabelNode lnArg_i = (LabelNode) me.getValue();
1011
1012       // rewrite alpha for the nodes reachable from argument label i
1013       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1014       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1015
1016       // to find all reachable nodes, start with label referencees
1017       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1018       while( edgeArgItr.hasNext() ) {
1019         ReferenceEdge edge = edgeArgItr.next();
1020         todoNodes.add( edge.getDst() );
1021       }
1022
1023       // then follow links until all reachable nodes have been found
1024       while( !todoNodes.isEmpty() ) {
1025         HeapRegionNode hrn = todoNodes.iterator().next();
1026         todoNodes.remove( hrn );
1027         reachableNodes.add( hrn );
1028
1029         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1030         while( edgeItr.hasNext() ) {
1031           ReferenceEdge edge = edgeItr.next();
1032
1033           if( !reachableNodes.contains( edge.getDst() ) ) {
1034             todoNodes.add( edge.getDst() );
1035           }
1036         }
1037       }
1038
1039       // save for later
1040       paramIndex2reachableCallerNodes.put( index, reachableNodes );
1041
1042       // now iterate over reachable nodes to update their alpha, and
1043       // classify edges found as "argument reachable" or "upstream"
1044       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1045       while( hrnItr.hasNext() ) {
1046         HeapRegionNode hrn = hrnItr.next();
1047
1048         rewriteCallerNodeAlpha( fm.numParameters(),
1049                                 index,
1050                                 hrn,
1051                                 paramIndex2rewriteH,
1052                                 paramIndex2rewriteD,
1053                                 paramIndex2paramToken,
1054                                 paramIndex2paramTokenStar );
1055
1056         nodesWithNewAlpha.add( hrn );
1057
1058         // look at all incoming edges to the reachable nodes
1059         // and sort them as edges reachable from the argument
1060         // label node, or upstream edges
1061         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1062         while( edgeItr.hasNext() ) {
1063           ReferenceEdge edge = edgeItr.next();
1064
1065           OwnershipNode on = edge.getSrc();
1066
1067           if( on instanceof LabelNode ) {
1068
1069             LabelNode ln0 = (LabelNode) on;
1070             if( ln0.equals( lnArg_i ) ) {
1071               edgesReachable.add( edge );
1072             } else {
1073               edgesUpstream.add( edge );
1074             }
1075
1076           } else {
1077
1078             HeapRegionNode hrn0 = (HeapRegionNode) on;
1079             if( reachableNodes.contains( hrn0 ) ) {
1080               edgesReachable.add( edge );
1081             } else {
1082               edgesUpstream.add( edge );
1083             }
1084           }
1085         }
1086       }
1087
1088
1089       // update reachable edges
1090       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1091       while( edgeReachableItr.hasNext() ) {
1092         ReferenceEdge edgeReachable = edgeReachableItr.next();
1093
1094         rewriteCallerEdgeBeta( fm.numParameters(),
1095                                index,
1096                                edgeReachable,
1097                                paramIndex2rewriteJ,
1098                                paramIndex2rewriteD,
1099                                paramIndex2paramToken,
1100                                paramIndex2paramTokenStar,
1101                                false,
1102                                null );
1103
1104         edgesWithNewBeta.add( edgeReachable );
1105       }
1106
1107
1108       // update upstream edges
1109       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges
1110         = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1111
1112       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1113       while( edgeUpstreamItr.hasNext() ) {
1114         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1115
1116         rewriteCallerEdgeBeta( fm.numParameters(),
1117                                index,
1118                                edgeUpstream,
1119                                paramIndex2rewriteK,
1120                                paramIndex2rewriteD,
1121                                paramIndex2paramToken,
1122                                paramIndex2paramTokenStar,
1123                                true,
1124                                edgeUpstreamPlannedChanges );
1125
1126         edgesWithNewBeta.add( edgeUpstream );
1127       }
1128
1129       propagateTokensOverEdges( edgesUpstream,
1130                                 edgeUpstreamPlannedChanges,
1131                                 edgesWithNewBeta );
1132     }
1133
1134
1135     // commit changes to alpha and beta
1136     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1137     while( nodeItr.hasNext() ) {
1138       nodeItr.next().applyAlphaNew();
1139     }
1140
1141     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1142     while( edgeItr.hasNext() ) {
1143       edgeItr.next().applyBetaNew();
1144     }
1145
1146
1147
1148     // verify the existence of allocation sites and their
1149     // shadows from the callee in the context of this caller graph
1150     // then map allocated nodes of callee onto the caller shadows
1151     // of them
1152     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1153     while( asItr.hasNext() ) {
1154       AllocationSite allocSite  = asItr.next();
1155       HeapRegionNode hrnSummary = getSummaryNode( allocSite );
1156
1157       // assert that the shadow nodes have no reference edges
1158       // because they're brand new to the graph, or last time
1159       // they were used they should have been cleared of edges
1160       HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
1161       assert hrnShadowSummary.getNumReferencers() == 0;
1162       assert hrnShadowSummary.getNumReferencees() == 0;
1163
1164       // then bring g_ij onto g'_ij and rewrite
1165       transferOnto( hrnSummary, hrnShadowSummary );
1166
1167       // TODO REPLACE NORMAL TOKEN WITH SHADOW TOKEN BEFORE PROCEEDING!!
1168
1169       // shadow nodes only are touched by a rewrite one time,
1170       // so rewrite and immediately commit--and they don't belong
1171       // to a particular parameter, so use a bogus param index
1172       // that pulls a self-rewrite out of H
1173       rewriteCallerNodeAlpha( fm.numParameters(),
1174                               bogusIndex,
1175                               hrnShadowSummary,
1176                               paramIndex2rewriteH,
1177                               paramIndex2rewriteD,
1178                               paramIndex2paramToken,
1179                               paramIndex2paramTokenStar );
1180
1181
1182       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1183         Integer idIth = allocSite.getIthOldest(i);
1184         assert id2hrn.containsKey(idIth);
1185         HeapRegionNode hrnIth = id2hrn.get(idIth);
1186
1187         Integer idShadowIth = -(allocSite.getIthOldest(i));
1188         assert id2hrn.containsKey(idShadowIth);
1189         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1190         assert hrnIthShadow.getNumReferencers() == 0;
1191         assert hrnIthShadow.getNumReferencees() == 0;
1192
1193         transferOnto( hrnIth, hrnIthShadow );
1194
1195         rewriteCallerNodeAlpha( fm.numParameters(),
1196                                 bogusIndex,
1197                                 hrnIthShadow,
1198                                 paramIndex2rewriteH,
1199                                 paramIndex2rewriteD,
1200                                 paramIndex2paramToken,
1201                                 paramIndex2paramTokenStar );
1202       }
1203     }
1204
1205     // for every heap region->heap region edge in the
1206     // callee graph, create the matching edge or edges
1207     // in the caller graph
1208     Set      sCallee = ogCallee.id2hrn.entrySet();
1209     Iterator iCallee = sCallee.iterator();
1210     while( iCallee.hasNext() ) {
1211       Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
1212       Integer        idCallee  = (Integer)        meCallee.getKey();
1213       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1214
1215       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1216       while( heapRegionsItrCallee.hasNext() ) {
1217         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1218         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1219         Integer idChildCallee         = hrnChildCallee.getID();
1220
1221         // only address this edge if it is not a special reflexive edge
1222         if( !edgeCallee.isInitialParamReflexive() ) {
1223
1224           // now we know that in the callee method's ownership graph
1225           // there is a heap region->heap region reference edge given
1226           // by heap region pointers:
1227           // hrnCallee -> heapChildCallee
1228           //
1229           // or by the ownership-graph independent ID's:
1230           // idCallee -> idChildCallee
1231
1232           // make the edge with src and dst so beta info is
1233           // calculated once, then copy it for each new edge in caller
1234           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge( null,
1235                                                                      null,
1236                                                                      edgeCallee.getFieldDesc(),
1237                                                                      false,
1238                                                                      edgeCallee.getBeta() );
1239           rewriteCallerEdgeBeta( fm.numParameters(),
1240                                  bogusIndex,
1241                                  edgeNewInCallerTemplate,
1242                                  paramIndex2rewriteJ,
1243                                  paramIndex2rewriteD,
1244                                  paramIndex2paramToken,
1245                                  paramIndex2paramTokenStar,
1246                                  false,
1247                                  null );
1248
1249
1250
1251
1252           // So now make a set of possible source heaps in the caller graph
1253           // and a set of destination heaps in the caller graph, and make
1254           // a reference edge in the caller for every possible (src,dst) pair
1255           HashSet<HeapRegionNode> possibleCallerSrcs =
1256             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1257                                                  edgeCallee,
1258                                                  true,
1259                                                  paramIndex2reachableCallerNodes );
1260
1261           HashSet<HeapRegionNode> possibleCallerDsts =
1262             getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
1263                                                  edgeCallee,
1264                                                  false,
1265                                                  paramIndex2reachableCallerNodes );
1266
1267           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1268           Iterator srcItr = possibleCallerSrcs.iterator();
1269           while( srcItr.hasNext() ) {
1270             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1271
1272             Iterator dstItr = possibleCallerDsts.iterator();
1273             while( dstItr.hasNext() ) {
1274               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1275
1276               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1277               edgeNewInCaller.setSrc( src );
1278               edgeNewInCaller.setDst( dst );
1279
1280               ReferenceEdge edgeExisting = src.getReferenceTo( dst, edgeNewInCaller.getFieldDesc() );
1281               if( edgeExisting == null ) {
1282                 // if this edge doesn't exist in the caller, create it
1283                 addReferenceEdge( src, dst, edgeNewInCaller );
1284               } else {
1285                 // if it already exists, merge with it
1286                 edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNewInCaller.getBeta() ) );
1287               }
1288             }
1289           }
1290         }
1291       }
1292     }
1293
1294   }
1295
1296
1297   private void rewriteCallerNodeAlpha( int numParameters,
1298                                        Integer paramIndex,
1299                                        HeapRegionNode hrn,
1300                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH,
1301                                        Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1302                                        Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1303                                        Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1304
1305     ReachabilitySet rules = paramIndex2rewriteH.get( paramIndex );
1306     assert rules != null;
1307
1308     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1309     assert tokenToRewrite != null;
1310
1311     ReachabilitySet r0 = new ReachabilitySet().makeCanonical();
1312     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1313     while( ttsItr.hasNext() ) {
1314       TokenTupleSet tts = ttsItr.next();
1315       r0 = r0.union( tts.rewriteToken( tokenToRewrite,
1316                                        hrn.getAlpha(),
1317                                        false,
1318                                        null ) );
1319     }
1320
1321     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1322     ttsItr = r0.iterator();
1323     while( ttsItr.hasNext() ) {
1324       TokenTupleSet tts = ttsItr.next();
1325       r1 = r1.union( rewriteDpass( numParameters,
1326                                    paramIndex,
1327                                    tts,
1328                                    paramIndex2rewriteD,
1329                                    paramIndex2paramToken,
1330                                    paramIndex2paramTokenStar ) );
1331     }
1332
1333     hrn.setAlphaNew( hrn.getAlphaNew().union( r1 ) );
1334   }
1335
1336
1337   private void rewriteCallerEdgeBeta( int numParameters,
1338                                       Integer paramIndex,
1339                                       ReferenceEdge edge,
1340                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJorK,
1341                                       Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1342                                       Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1343                                       Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar,
1344                                       boolean makeChangeSet,
1345                                       Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1346
1347     ReachabilitySet rules = paramIndex2rewriteJorK.get( paramIndex );
1348     assert rules != null;
1349
1350     TokenTuple tokenToRewrite = paramIndex2paramToken.get( paramIndex );
1351     assert tokenToRewrite != null;
1352
1353     ChangeTupleSet cts0 = new ChangeTupleSet().makeCanonical();
1354
1355     Iterator<TokenTupleSet> ttsItr = rules.iterator();
1356     while( ttsItr.hasNext() ) {
1357       TokenTupleSet tts = ttsItr.next();
1358
1359       Hashtable<TokenTupleSet, TokenTupleSet> forChangeSet =
1360         new Hashtable<TokenTupleSet, TokenTupleSet>();
1361
1362       ReachabilitySet rTemp = tts.rewriteToken( tokenToRewrite,
1363                                                 edge.getBeta(),
1364                                                 true,
1365                                                 forChangeSet );
1366
1367       Iterator fcsItr = forChangeSet.entrySet().iterator();
1368       while( fcsItr.hasNext() ) {
1369         Map.Entry me = (Map.Entry) fcsItr.next();
1370         TokenTupleSet ttsMatch = (TokenTupleSet) me.getKey();
1371         TokenTupleSet ttsAdd   = (TokenTupleSet) me.getValue();
1372
1373         ChangeTuple ct = new ChangeTuple( ttsMatch,
1374                                           ttsAdd
1375                                           ).makeCanonical();
1376
1377         cts0 = cts0.union( ct );
1378       }
1379     }
1380
1381
1382     ReachabilitySet r1 = new ReachabilitySet().makeCanonical();
1383     ChangeTupleSet cts1 = new ChangeTupleSet().makeCanonical();
1384
1385     Iterator<ChangeTuple> ctItr = cts0.iterator();
1386     while( ctItr.hasNext() ) {
1387       ChangeTuple ct = ctItr.next();
1388
1389       ReachabilitySet rTemp = rewriteDpass( numParameters,
1390                                             paramIndex,
1391                                             ct.getSetToAdd(),
1392                                             paramIndex2rewriteD,
1393                                             paramIndex2paramToken,
1394                                             paramIndex2paramTokenStar
1395                                             ).makeCanonical();
1396       r1 = r1.union( rTemp );
1397
1398       if( makeChangeSet ) {
1399         assert edgePlannedChanges != null;
1400
1401         Iterator<TokenTupleSet> ttsTempItr = rTemp.iterator();
1402         while( ttsTempItr.hasNext() ) {
1403           TokenTupleSet tts = ttsTempItr.next();
1404
1405           ChangeTuple ctFinal = new ChangeTuple( ct.getSetToMatch(),
1406                                                  tts
1407                                                  ).makeCanonical();
1408
1409           cts1 = cts1.union( ctFinal );
1410         }
1411       }
1412     }
1413
1414     if( makeChangeSet ) {
1415       edgePlannedChanges.put( edge, cts1 );
1416     }
1417
1418     edge.setBetaNew( edge.getBetaNew().union( r1 ) );
1419   }
1420
1421
1422   private ReachabilitySet rewriteDpass( int numParameters,
1423                                         Integer paramIndex,
1424                                         TokenTupleSet ttsIn,
1425                                         Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1426                                         Hashtable<Integer, TokenTuple> paramIndex2paramToken,
1427                                         Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar ) {
1428
1429     ReachabilitySet rsOut = new ReachabilitySet().makeCanonical();
1430
1431     boolean rewritten = false;
1432
1433     for( int j = 0; j < numParameters; ++j ) {
1434       Integer paramIndexJ = new Integer( j );
1435       ReachabilitySet D_j = paramIndex2rewriteD.get( paramIndexJ );
1436       assert D_j != null;
1437
1438       if( paramIndexJ != paramIndex ) {
1439         TokenTuple tokenToRewriteJ = paramIndex2paramToken.get( paramIndexJ );
1440         assert tokenToRewriteJ != null;
1441         if( ttsIn.containsTuple( tokenToRewriteJ ) ) {
1442           ReachabilitySet r = ttsIn.rewriteToken( tokenToRewriteJ,
1443                                                   D_j,
1444                                                   false,
1445                                                   null );
1446           Iterator<TokenTupleSet> ttsItr = r.iterator();
1447           while( ttsItr.hasNext() ) {
1448             TokenTupleSet tts = ttsItr.next();
1449             rsOut = rsOut.union( rewriteDpass( numParameters,
1450                                                paramIndex,
1451                                                tts,
1452                                                paramIndex2rewriteD,
1453                                                paramIndex2paramToken,
1454                                                paramIndex2paramTokenStar ) );
1455             rewritten = true;
1456           }
1457         }
1458       }
1459
1460       TokenTuple tokenStarToRewriteJ = paramIndex2paramTokenStar.get( paramIndexJ );
1461       assert tokenStarToRewriteJ != null;
1462       if( ttsIn.containsTuple( tokenStarToRewriteJ ) ) {
1463         ReachabilitySet r = ttsIn.rewriteToken( tokenStarToRewriteJ,
1464                                                 D_j,
1465                                                 false,
1466                                                 null );
1467         Iterator<TokenTupleSet> ttsItr = r.iterator();
1468         while( ttsItr.hasNext() ) {
1469           TokenTupleSet tts = ttsItr.next();
1470           rsOut = rsOut.union( rewriteDpass( numParameters,
1471                                              paramIndex,
1472                                              tts,
1473                                              paramIndex2rewriteD,
1474                                              paramIndex2paramToken,
1475                                              paramIndex2paramTokenStar ) );
1476           rewritten = true;
1477         }
1478       }
1479     }
1480
1481     if( !rewritten ) {
1482       rsOut = rsOut.union( ttsIn );
1483     }
1484
1485     return rsOut;
1486   }
1487
1488
1489   private HashSet<HeapRegionNode>
1490     getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
1491                                          ReferenceEdge edgeCallee,
1492                                          boolean mapFromSrc,
1493                                          Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1494                                          ) {
1495
1496     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1497
1498     HeapRegionNode hrnCallee;
1499     if( mapFromSrc ) {
1500       OwnershipNode on = edgeCallee.getSrc();
1501       assert on instanceof HeapRegionNode;
1502       hrnCallee = (HeapRegionNode) on;
1503     } else {
1504       hrnCallee = edgeCallee.getDst();
1505     }
1506
1507     Integer paramIndexCallee = ogCallee.id2paramIndex.get( hrnCallee.getID() );
1508
1509     if( paramIndexCallee == null ) {
1510       // this is a node allocated in the callee then and it has
1511       // exactly one shadow node in the caller to map to
1512       AllocationSite as = hrnCallee.getAllocationSite();
1513       assert as != null;
1514
1515       int age = as.getAge( hrnCallee.getID() );
1516       assert age != AllocationSite.AGE_notInThisSite;
1517
1518       Integer idCaller;
1519       if( age == AllocationSite.AGE_summary ) {
1520         idCaller = as.getSummaryShadow();
1521       } else if( age == AllocationSite.AGE_oldest ) {
1522         idCaller = as.getOldestShadow();
1523       } else {
1524         idCaller = as.getIthOldestShadow( age );
1525       }
1526
1527       assert id2hrn.containsKey( idCaller );
1528       HeapRegionNode hrnCaller = id2hrn.get( idCaller );
1529       possibleCallerHRNs.add( hrnCaller );
1530
1531     } else {
1532       // this is a node that was created to represent a parameter
1533       // so it maps to a whole mess of heap regions
1534       assert paramIndex2reachableCallerNodes.containsKey( paramIndexCallee );
1535       possibleCallerHRNs = paramIndex2reachableCallerNodes.get( paramIndexCallee );
1536
1537       // TODO PRUNE BY TYPE/FIELD NAME!!
1538     }
1539
1540     return possibleCallerHRNs;
1541   }
1542
1543
1544
1545   ////////////////////////////////////////////////////
1546   // in merge() and equals() methods the suffix A
1547   // represents the passed in graph and the suffix
1548   // B refers to the graph in this object
1549   // Merging means to take the incoming graph A and
1550   // merge it into B, so after the operation graph B
1551   // is the final result.
1552   ////////////////////////////////////////////////////
1553   public void merge(OwnershipGraph og) {
1554
1555     if( og == null ) {
1556       return;
1557     }
1558
1559     mergeOwnershipNodes(og);
1560     mergeReferenceEdges(og);
1561     mergeId2paramIndex(og);
1562     mergeAllocationSites(og);
1563   }
1564
1565
1566   protected void mergeOwnershipNodes(OwnershipGraph og) {
1567     Set sA = og.id2hrn.entrySet();
1568     Iterator iA = sA.iterator();
1569     while( iA.hasNext() ) {
1570       Map.Entry meA  = (Map.Entry)iA.next();
1571       Integer idA  = (Integer)        meA.getKey();
1572       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1573
1574       // if this graph doesn't have a node the
1575       // incoming graph has, allocate it
1576       if( !id2hrn.containsKey(idA) ) {
1577         HeapRegionNode hrnB = hrnA.copy();
1578         id2hrn.put(idA, hrnB);
1579
1580       } else {
1581         // otherwise this is a node present in both graphs
1582         // so make the new reachability set a union of the
1583         // nodes' reachability sets
1584         HeapRegionNode hrnB = id2hrn.get(idA);
1585         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1586       }
1587     }
1588
1589     // now add any label nodes that are in graph B but
1590     // not in A
1591     sA = og.td2ln.entrySet();
1592     iA = sA.iterator();
1593     while( iA.hasNext() ) {
1594       Map.Entry meA = (Map.Entry)iA.next();
1595       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1596       LabelNode lnA = (LabelNode)      meA.getValue();
1597
1598       // if the label doesn't exist in B, allocate and add it
1599       LabelNode lnB = getLabelNodeFromTemp(tdA);
1600     }
1601   }
1602
1603   protected void mergeReferenceEdges(OwnershipGraph og) {
1604
1605     // heap regions
1606     Set sA = og.id2hrn.entrySet();
1607     Iterator iA = sA.iterator();
1608     while( iA.hasNext() ) {
1609       Map.Entry meA  = (Map.Entry)iA.next();
1610       Integer idA  = (Integer)        meA.getKey();
1611       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1612
1613       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1614       while( heapRegionsItrA.hasNext() ) {
1615         ReferenceEdge edgeA     = heapRegionsItrA.next();
1616         HeapRegionNode hrnChildA = edgeA.getDst();
1617         Integer idChildA  = hrnChildA.getID();
1618
1619         // at this point we know an edge in graph A exists
1620         // idA -> idChildA, does this exist in B?
1621         assert id2hrn.containsKey(idA);
1622         HeapRegionNode hrnB        = id2hrn.get(idA);
1623         ReferenceEdge edgeToMerge = null;
1624
1625         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1626         while( heapRegionsItrB.hasNext() &&
1627                edgeToMerge == null          ) {
1628
1629           ReferenceEdge edgeB     = heapRegionsItrB.next();
1630           HeapRegionNode hrnChildB = edgeB.getDst();
1631           Integer idChildB  = hrnChildB.getID();
1632
1633           // don't use the ReferenceEdge.equals() here because
1634           // we're talking about existence between graphs
1635           if( idChildB.equals(idChildA) &&
1636               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1637             edgeToMerge = edgeB;
1638           }
1639         }
1640
1641         // if the edge from A was not found in B,
1642         // add it to B.
1643         if( edgeToMerge == null ) {
1644           assert id2hrn.containsKey(idChildA);
1645           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1646           edgeToMerge = edgeA.copy();
1647           edgeToMerge.setSrc(hrnB);
1648           edgeToMerge.setDst(hrnChildB);
1649           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1650         }
1651         // otherwise, the edge already existed in both graphs
1652         // so merge their reachability sets
1653         else {
1654           // just replace this beta set with the union
1655           assert edgeToMerge != null;
1656           edgeToMerge.setBeta(
1657             edgeToMerge.getBeta().union(edgeA.getBeta() )
1658             );
1659           if( !edgeA.isInitialParamReflexive() ) {
1660             edgeToMerge.setIsInitialParamReflexive(false);
1661           }
1662         }
1663       }
1664     }
1665
1666     // and then again with label nodes
1667     sA = og.td2ln.entrySet();
1668     iA = sA.iterator();
1669     while( iA.hasNext() ) {
1670       Map.Entry meA = (Map.Entry)iA.next();
1671       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1672       LabelNode lnA = (LabelNode)      meA.getValue();
1673
1674       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1675       while( heapRegionsItrA.hasNext() ) {
1676         ReferenceEdge edgeA     = heapRegionsItrA.next();
1677         HeapRegionNode hrnChildA = edgeA.getDst();
1678         Integer idChildA  = hrnChildA.getID();
1679
1680         // at this point we know an edge in graph A exists
1681         // tdA -> idChildA, does this exist in B?
1682         assert td2ln.containsKey(tdA);
1683         LabelNode lnB         = td2ln.get(tdA);
1684         ReferenceEdge edgeToMerge = null;
1685
1686         // labels never have edges with a field
1687         //assert edgeA.getFieldDesc() == null;
1688
1689         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1690         while( heapRegionsItrB.hasNext() &&
1691                edgeToMerge == null          ) {
1692
1693           ReferenceEdge edgeB     = heapRegionsItrB.next();
1694           HeapRegionNode hrnChildB = edgeB.getDst();
1695           Integer idChildB  = hrnChildB.getID();
1696
1697           // labels never have edges with a field
1698           //assert edgeB.getFieldDesc() == null;
1699
1700           // don't use the ReferenceEdge.equals() here because
1701           // we're talking about existence between graphs
1702           if( idChildB.equals(idChildA) &&
1703               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1704             edgeToMerge = edgeB;
1705           }
1706         }
1707
1708         // if the edge from A was not found in B,
1709         // add it to B.
1710         if( edgeToMerge == null ) {
1711           assert id2hrn.containsKey(idChildA);
1712           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1713           edgeToMerge = edgeA.copy();
1714           edgeToMerge.setSrc(lnB);
1715           edgeToMerge.setDst(hrnChildB);
1716           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1717         }
1718         // otherwise, the edge already existed in both graphs
1719         // so merge their reachability sets
1720         else {
1721           // just replace this beta set with the union
1722           edgeToMerge.setBeta(
1723             edgeToMerge.getBeta().union(edgeA.getBeta() )
1724             );
1725           if( !edgeA.isInitialParamReflexive() ) {
1726             edgeToMerge.setIsInitialParamReflexive(false);
1727           }
1728         }
1729       }
1730     }
1731   }
1732
1733   // you should only merge ownership graphs that have the
1734   // same number of parameters, or if one or both parameter
1735   // index tables are empty
1736   protected void mergeId2paramIndex(OwnershipGraph og) {
1737     if( id2paramIndex.size() == 0 ) {
1738       id2paramIndex  = og.id2paramIndex;
1739       paramIndex2id  = og.paramIndex2id;
1740       paramIndex2tdQ = og.paramIndex2tdQ;
1741       return;
1742     }
1743
1744     if( og.id2paramIndex.size() == 0 ) {
1745       return;
1746     }
1747
1748     assert id2paramIndex.size() == og.id2paramIndex.size();
1749   }
1750
1751   protected void mergeAllocationSites(OwnershipGraph og) {
1752     allocationSites.addAll(og.allocationSites);
1753   }
1754
1755
1756
1757   // it is necessary in the equals() member functions
1758   // to "check both ways" when comparing the data
1759   // structures of two graphs.  For instance, if all
1760   // edges between heap region nodes in graph A are
1761   // present and equal in graph B it is not sufficient
1762   // to say the graphs are equal.  Consider that there
1763   // may be edges in graph B that are not in graph A.
1764   // the only way to know that all edges in both graphs
1765   // are equally present is to iterate over both data
1766   // structures and compare against the other graph.
1767   public boolean equals(OwnershipGraph og) {
1768
1769     if( og == null ) {
1770       return false;
1771     }
1772
1773     if( !areHeapRegionNodesEqual(og) ) {
1774       return false;
1775     }
1776
1777     if( !areLabelNodesEqual(og) ) {
1778       return false;
1779     }
1780
1781     if( !areReferenceEdgesEqual(og) ) {
1782       return false;
1783     }
1784
1785     if( !areId2paramIndexEqual(og) ) {
1786       return false;
1787     }
1788
1789     // if everything is equal up to this point,
1790     // assert that allocationSites is also equal--
1791     // this data is redundant and kept for efficiency
1792     assert allocationSites.equals(og.allocationSites);
1793
1794     return true;
1795   }
1796
1797   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
1798
1799     if( !areallHRNinAalsoinBandequal(this, og) ) {
1800       return false;
1801     }
1802
1803     if( !areallHRNinAalsoinBandequal(og, this) ) {
1804       return false;
1805     }
1806
1807     return true;
1808   }
1809
1810   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
1811                                                        OwnershipGraph ogB) {
1812     Set sA = ogA.id2hrn.entrySet();
1813     Iterator iA = sA.iterator();
1814     while( iA.hasNext() ) {
1815       Map.Entry meA  = (Map.Entry)iA.next();
1816       Integer idA  = (Integer)        meA.getKey();
1817       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1818
1819       if( !ogB.id2hrn.containsKey(idA) ) {
1820         return false;
1821       }
1822
1823       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1824       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
1825         return false;
1826       }
1827     }
1828
1829     return true;
1830   }
1831
1832
1833   protected boolean areLabelNodesEqual(OwnershipGraph og) {
1834
1835     if( !areallLNinAalsoinBandequal(this, og) ) {
1836       return false;
1837     }
1838
1839     if( !areallLNinAalsoinBandequal(og, this) ) {
1840       return false;
1841     }
1842
1843     return true;
1844   }
1845
1846   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
1847                                                       OwnershipGraph ogB) {
1848     Set sA = ogA.td2ln.entrySet();
1849     Iterator iA = sA.iterator();
1850     while( iA.hasNext() ) {
1851       Map.Entry meA = (Map.Entry)iA.next();
1852       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1853
1854       if( !ogB.td2ln.containsKey(tdA) ) {
1855         return false;
1856       }
1857     }
1858
1859     return true;
1860   }
1861
1862
1863   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
1864     if( !areallREinAandBequal(this, og) ) {
1865       return false;
1866     }
1867
1868     return true;
1869   }
1870
1871   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
1872                                                 OwnershipGraph ogB) {
1873
1874     // check all the heap region->heap region edges
1875     Set sA = ogA.id2hrn.entrySet();
1876     Iterator iA = sA.iterator();
1877     while( iA.hasNext() ) {
1878       Map.Entry meA  = (Map.Entry)iA.next();
1879       Integer idA  = (Integer)        meA.getKey();
1880       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1881
1882       // we should have already checked that the same
1883       // heap regions exist in both graphs
1884       assert ogB.id2hrn.containsKey(idA);
1885
1886       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
1887         return false;
1888       }
1889
1890       // then check every edge in B for presence in A, starting
1891       // from the same parent HeapRegionNode
1892       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1893
1894       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
1895         return false;
1896       }
1897     }
1898
1899     // then check all the label->heap region edges
1900     sA = ogA.td2ln.entrySet();
1901     iA = sA.iterator();
1902     while( iA.hasNext() ) {
1903       Map.Entry meA = (Map.Entry)iA.next();
1904       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1905       LabelNode lnA = (LabelNode)      meA.getValue();
1906
1907       // we should have already checked that the same
1908       // label nodes exist in both graphs
1909       assert ogB.td2ln.containsKey(tdA);
1910
1911       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
1912         return false;
1913       }
1914
1915       // then check every edge in B for presence in A, starting
1916       // from the same parent LabelNode
1917       LabelNode lnB = ogB.td2ln.get(tdA);
1918
1919       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
1920         return false;
1921       }
1922     }
1923
1924     return true;
1925   }
1926
1927
1928   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
1929                                                  OwnershipNode onA,
1930                                                  OwnershipGraph ogB) {
1931
1932     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
1933     while( itrA.hasNext() ) {
1934       ReferenceEdge edgeA     = itrA.next();
1935       HeapRegionNode hrnChildA = edgeA.getDst();
1936       Integer idChildA  = hrnChildA.getID();
1937
1938       assert ogB.id2hrn.containsKey(idChildA);
1939
1940       // at this point we know an edge in graph A exists
1941       // onA -> idChildA, does this exact edge exist in B?
1942       boolean edgeFound = false;
1943
1944       OwnershipNode onB = null;
1945       if( onA instanceof HeapRegionNode ) {
1946         HeapRegionNode hrnA = (HeapRegionNode) onA;
1947         onB = ogB.id2hrn.get(hrnA.getID() );
1948       } else {
1949         LabelNode lnA = (LabelNode) onA;
1950         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
1951       }
1952
1953       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
1954       while( itrB.hasNext() ) {
1955         ReferenceEdge edgeB     = itrB.next();
1956         HeapRegionNode hrnChildB = edgeB.getDst();
1957         Integer idChildB  = hrnChildB.getID();
1958
1959         if( idChildA.equals(idChildB) &&
1960             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
1961
1962           // there is an edge in the right place with the right field,
1963           // but do they have the same attributes?
1964           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
1965
1966             edgeFound = true;
1967             //} else {
1968             //return false;
1969           }
1970         }
1971       }
1972
1973       if( !edgeFound ) {
1974         return false;
1975       }
1976     }
1977
1978     return true;
1979   }
1980
1981
1982   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
1983     return id2paramIndex.size() == og.id2paramIndex.size();
1984   }
1985
1986
1987   /*
1988      // given a set B of heap region node ID's, return the set of heap
1989      // region node ID's that is reachable from B
1990      public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1991
1992       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1993       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1994
1995       // initial nodes to visit are from set B
1996       Iterator initialItr = idSetB.iterator();
1997       while( initialItr.hasNext() ) {
1998           Integer idInitial = (Integer) initialItr.next();
1999           assert id2hrn.contains( idInitial );
2000           HeapRegionNode hrnInitial = id2hrn.get( idInitial );
2001           toVisit.add( hrnInitial );
2002       }
2003
2004       HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
2005
2006       // do a heap traversal
2007       while( !toVisit.isEmpty() ) {
2008           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2009           toVisit.remove( hrnVisited );
2010           visited.add   ( hrnVisited );
2011
2012           // for every node visited, add it to the total
2013           // reachable set
2014           idSetReachableFromB.add( hrnVisited.getID() );
2015
2016           // find other reachable nodes
2017           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2018           while( referenceeItr.hasNext() ) {
2019               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2020               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2021               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2022
2023               if( !visited.contains( hrnReferencee ) ) {
2024                   toVisit.add( hrnReferencee );
2025               }
2026           }
2027       }
2028
2029       return idSetReachableFromB;
2030      }
2031
2032
2033      // used to find if a heap region can possibly have a reference to
2034      // any of the heap regions in the given set
2035      // if the id supplied is in the set, then a self-referencing edge
2036      // would return true, but that special case is specifically allowed
2037      // meaning that it isn't an external alias
2038      public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
2039
2040       assert id2hrn.contains( id );
2041       HeapRegionNode hrn = id2hrn.get( id );
2042
2043
2044       //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
2045
2046       //Iterator i = idSet.iterator();
2047       //while( i.hasNext() ) {
2048       //    Integer idFromSet = (Integer) i.next();
2049       //   assert id2hrn.contains( idFromSet );
2050       //    hrnSet.add( id2hrn.get( idFromSet ) );
2051       //}
2052
2053
2054       // do a traversal from hrn and see if any of the
2055       // heap regions from the set come up during that
2056       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
2057       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2058
2059       toVisit.add( hrn );
2060       while( !toVisit.isEmpty() ) {
2061           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
2062           toVisit.remove( hrnVisited );
2063           visited.add   ( hrnVisited );
2064
2065           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
2066           while( referenceeItr.hasNext() ) {
2067               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
2068               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
2069               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
2070
2071               if( idSet.contains( hrnReferencee.getID() ) ) {
2072                   if( !id.equals( hrnReferencee.getID() ) ) {
2073                       return true;
2074                   }
2075               }
2076
2077               if( !visited.contains( hrnReferencee ) ) {
2078                   toVisit.add( hrnReferencee );
2079               }
2080           }
2081       }
2082
2083       return false;
2084      }
2085    */
2086
2087
2088   // for writing ownership graphs to dot files
2089   public void writeGraph(Descriptor methodDesc,
2090                          FlatNode fn,
2091                          boolean writeLabels,
2092                          boolean labelSelect,
2093                          boolean pruneGarbage,
2094                          boolean writeReferencers
2095                          ) throws java.io.IOException {
2096     writeGraph(
2097       methodDesc.getSymbol() +
2098       methodDesc.getNum() +
2099       fn.toString(),
2100       writeLabels,
2101       labelSelect,
2102       pruneGarbage,
2103       writeReferencers
2104       );
2105   }
2106
2107   public void writeGraph(Descriptor methodDesc,
2108                          FlatNode fn,
2109                          boolean writeLabels,
2110                          boolean writeReferencers
2111                          ) throws java.io.IOException {
2112     writeGraph(
2113       methodDesc.getSymbol() +
2114       methodDesc.getNum() +
2115       fn.toString(),
2116       writeLabels,
2117       false,
2118       false,
2119       writeReferencers
2120       );
2121   }
2122
2123   public void writeGraph(Descriptor methodDesc,
2124                          boolean writeLabels,
2125                          boolean writeReferencers
2126                          ) throws java.io.IOException {
2127     writeGraph(
2128       methodDesc.getSymbol() +
2129       methodDesc.getNum() +
2130       "COMPLETE",
2131       writeLabels,
2132       false,
2133       false,
2134       writeReferencers
2135       );
2136   }
2137
2138   public void writeGraph(Descriptor methodDesc,
2139                          boolean writeLabels,
2140                          boolean labelSelect,
2141                          boolean pruneGarbage,
2142                          boolean writeReferencers
2143                          ) throws java.io.IOException {
2144     writeGraph(
2145       methodDesc.getSymbol() +
2146       methodDesc.getNum() +
2147       "COMPLETE",
2148       writeLabels,
2149       labelSelect,
2150       pruneGarbage,
2151       writeReferencers
2152       );
2153   }
2154
2155   public void writeGraph(String graphName,
2156                          boolean writeLabels,
2157                          boolean labelSelect,
2158                          boolean pruneGarbage,
2159                          boolean writeReferencers
2160                          ) throws java.io.IOException {
2161
2162     // remove all non-word characters from the graph name so
2163     // the filename and identifier in dot don't cause errors
2164     graphName = graphName.replaceAll("[\\W]", "");
2165
2166     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2167     bw.write("digraph "+graphName+" {\n");
2168     //bw.write( "  size=\"7.5,10\";\n" );
2169
2170     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2171
2172     // then visit every heap region node
2173     if( !pruneGarbage ) {
2174       Set s = id2hrn.entrySet();
2175       Iterator i = s.iterator();
2176       while( i.hasNext() ) {
2177         Map.Entry me  = (Map.Entry)i.next();
2178         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2179         if( !visited.contains(hrn) ) {
2180           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2181                                   hrn,
2182                                   bw,
2183                                   null,
2184                                   visited,
2185                                   writeReferencers);
2186         }
2187       }
2188     }
2189
2190     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2191
2192
2193     // then visit every label node, useful for debugging
2194     if( writeLabels ) {
2195       Set s = td2ln.entrySet();
2196       Iterator i = s.iterator();
2197       while( i.hasNext() ) {
2198         Map.Entry me = (Map.Entry)i.next();
2199         LabelNode ln = (LabelNode) me.getValue();
2200
2201         if( labelSelect ) {
2202           String labelStr = ln.getTempDescriptorString();
2203           if( labelStr.startsWith("___temp") ||
2204               labelStr.startsWith("___dst") ||
2205               labelStr.startsWith("___srctmp") ||
2206               labelStr.startsWith("___neverused")   ) {
2207             continue;
2208           }
2209         }
2210
2211         bw.write(ln.toString() + ";\n");
2212
2213         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2214         while( heapRegionsItr.hasNext() ) {
2215           ReferenceEdge edge = heapRegionsItr.next();
2216           HeapRegionNode hrn  = edge.getDst();
2217
2218           if( pruneGarbage && !visited.contains(hrn) ) {
2219             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2220                                     hrn,
2221                                     bw,
2222                                     null,
2223                                     visited,
2224                                     writeReferencers);
2225           }
2226
2227           bw.write("  "        + ln.toString() +
2228                    " -> "      + hrn.toString() +
2229                    "[label=\"" + edge.toGraphEdgeString() +
2230                    "\",decorate];\n");
2231         }
2232       }
2233     }
2234
2235
2236     bw.write("}\n");
2237     bw.close();
2238   }
2239
2240   protected void traverseHeapRegionNodes(int mode,
2241                                          HeapRegionNode hrn,
2242                                          BufferedWriter bw,
2243                                          TempDescriptor td,
2244                                          HashSet<HeapRegionNode> visited,
2245                                          boolean writeReferencers
2246                                          ) throws java.io.IOException {
2247
2248     if( visited.contains(hrn) ) {
2249       return;
2250     }
2251     visited.add(hrn);
2252
2253     switch( mode ) {
2254     case VISIT_HRN_WRITE_FULL:
2255
2256       String attributes = "[";
2257
2258       if( hrn.isSingleObject() ) {
2259         attributes += "shape=box";
2260       } else {
2261         attributes += "shape=Msquare";
2262       }
2263
2264       if( hrn.isFlagged() ) {
2265         attributes += ",style=filled,fillcolor=lightgrey";
2266       }
2267
2268       attributes += ",label=\"ID"        +
2269                     hrn.getID()          +
2270                     "\\n"                +
2271                     hrn.getDescription() +
2272                     "\\n"                +
2273                     hrn.getAlphaString() +
2274                     "\"]";
2275
2276       bw.write("  " + hrn.toString() + attributes + ";\n");
2277       break;
2278     }
2279
2280
2281     // useful for debugging
2282     if( writeReferencers ) {
2283       OwnershipNode onRef  = null;
2284       Iterator refItr = hrn.iteratorToReferencers();
2285       while( refItr.hasNext() ) {
2286         onRef = (OwnershipNode) refItr.next();
2287
2288         switch( mode ) {
2289         case VISIT_HRN_WRITE_FULL:
2290           bw.write("  "                    + hrn.toString() +
2291                    " -> "                  + onRef.toString() +
2292                    "[color=lightgray];\n");
2293           break;
2294         }
2295       }
2296     }
2297
2298     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2299     while( childRegionsItr.hasNext() ) {
2300       ReferenceEdge edge     = childRegionsItr.next();
2301       HeapRegionNode hrnChild = edge.getDst();
2302
2303       switch( mode ) {
2304       case VISIT_HRN_WRITE_FULL:
2305         bw.write("  "        + hrn.toString() +
2306                  " -> "      + hrnChild.toString() +
2307                  "[label=\"" + edge.toGraphEdgeString() +
2308                  "\",decorate];\n");
2309         break;
2310       }
2311
2312       traverseHeapRegionNodes(mode,
2313                               hrnChild,
2314                               bw,
2315                               td,
2316                               visited,
2317                               writeReferencers);
2318     }
2319   }
2320 }