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