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
  25   public HashSet<AllocationSite> allocationSites;
  26
  27
  28   public OwnershipGraph(int allocationDepth) {
  29     this.allocationDepth = allocationDepth;
  30
  31     id2hrn        = new Hashtable<Integer,        HeapRegionNode>();
  32     td2ln         = new Hashtable<TempDescriptor, LabelNode     >();
  33     id2paramIndex = new Hashtable<Integer,        Integer       >();
  34     paramIndex2id = new Hashtable<Integer,        Integer       >();
  35
  36     allocationSites = new HashSet <AllocationSite>();
  37   }
  38
  39
  40   // label nodes are much easier to deal with than
  41   // heap region nodes.  Whenever there is a request
  42   // for the label node that is associated with a
  43   // temp descriptor we can either find it or make a
  44   // new one and return it.  This is because temp
  45   // descriptors are globally unique and every label
  46   // node is mapped to exactly one temp descriptor.
  47   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  48     assert td != null;
  49
  50     if( !td2ln.containsKey(td) ) {
  51       td2ln.put(td, new LabelNode(td) );
  52     }
  53
  54     return td2ln.get(td);
  55   }
  56
  57
  58   // the reason for this method is to have the option
  59   // creating new heap regions with specific IDs, or
  60   // duplicating heap regions with specific IDs (especially
  61   // in the merge() operation) or to create new heap
  62   // regions with a new unique ID.
  63   protected HeapRegionNode
  64   createNewHeapRegionNode(Integer id,
  65                           boolean isSingleObject,
  66                           boolean isFlagged,
  67                           boolean isNewSummary,
  68                           boolean isParameter,
  69                           AllocationSite allocSite,
  70                           ReachabilitySet alpha,
  71                           String description) {
  72
  73     if( id == null ) {
  74       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  75     }
  76
  77     if( alpha == null ) {
  78       if( isFlagged || isParameter ) {
  79         alpha = new ReachabilitySet(new TokenTuple(id,
  80                                                    !isSingleObject,
  81                                                    TokenTuple.ARITY_ONE)
  82                                     ).makeCanonical();
  83       } else {
  84         alpha = new ReachabilitySet(new TokenTupleSet()
  85                                     ).makeCanonical();
  86       }
  87     }
  88
  89     HeapRegionNode hrn = new HeapRegionNode(id,
  90                                             isSingleObject,
  91                                             isFlagged,
  92                                             isNewSummary,
  93                                             allocSite,
  94                                             alpha,
  95                                             description);
  96     id2hrn.put(id, hrn);
  97     return hrn;
  98   }
  99
 100
 101
 102   ////////////////////////////////////////////////
 103   //
 104   //  Low-level referencee and referencer methods
 105   //
 106   //  These methods provide the lowest level for
 107   //  creating references between ownership nodes
 108   //  and handling the details of maintaining both
 109   //  list of referencers and referencees.
 110   //
 111   ////////////////////////////////////////////////
 112   protected void addReferenceEdge(OwnershipNode referencer,
 113                                   HeapRegionNode referencee,
 114                                   ReferenceEdge edge) {
 115     assert referencer != null;
 116     assert referencee != null;
 117     assert edge       != null;
 118     assert edge.getSrc() == referencer;
 119     assert edge.getDst() == referencee;
 120
 121     referencer.addReferencee(edge);
 122     referencee.addReferencer(edge);
 123   }
 124
 125   protected void removeReferenceEdge(OwnershipNode referencer,
 126                                      HeapRegionNode referencee,
 127                                      FieldDescriptor fieldDesc) {
 128     assert referencer != null;
 129     assert referencee != null;
 130
 131     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 132                                                    fieldDesc);
 133     assert edge != null;
 134     assert edge == referencee.getReferenceFrom(referencer,
 135                                                fieldDesc);
 136
 137     referencer.removeReferencee(edge);
 138     referencee.removeReferencer(edge);
 139   }
 140
 141   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 142                                          FieldDescriptor fieldDesc,
 143                                          boolean removeAll) {
 144     assert referencer != null;
 145
 146     // get a copy of the set to iterate over, otherwise
 147     // we will be trying to take apart the set as we
 148     // are iterating over it, which won't work
 149     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 150     while( i.hasNext() ) {
 151       ReferenceEdge edge = i.next();
 152
 153       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 154         HeapRegionNode referencee = edge.getDst();
 155
 156         removeReferenceEdge(referencer,
 157                             referencee,
 158                             edge.getFieldDesc() );
 159       }
 160     }
 161   }
 162
 163   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 164                                        FieldDescriptor fieldDesc,
 165                                        boolean removeAll) {
 166     assert referencee != null;
 167
 168     // get a copy of the set to iterate over, otherwise
 169     // we will be trying to take apart the set as we
 170     // are iterating over it, which won't work
 171     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 172     while( i.hasNext() ) {
 173       ReferenceEdge edge = i.next();
 174
 175       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 176         OwnershipNode referencer = edge.getSrc();
 177         removeReferenceEdge(referencer,
 178                             referencee,
 179                             edge.getFieldDesc() );
 180       }
 181     }
 182   }
 183
 184
 185   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
 186                                           ChangeTupleSet c0,
 187                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
 188                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
 189
 190     HashSet<HeapRegionNode> todoNodes
 191     = new HashSet<HeapRegionNode>();
 192     todoNodes.add(nPrime);
 193
 194     HashSet<ReferenceEdge> todoEdges
 195     = new HashSet<ReferenceEdge>();
 196
 197     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 198     = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 199     nodePlannedChanges.put(nPrime, c0);
 200
 201     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
 202     = new Hashtable<ReferenceEdge, ChangeTupleSet>();
 203
 204
 205     while( !todoNodes.isEmpty() ) {
 206       HeapRegionNode n = todoNodes.iterator().next();
 207       ChangeTupleSet C = nodePlannedChanges.get(n);
 208
 209       Iterator itrC = C.iterator();
 210       while( itrC.hasNext() ) {
 211         ChangeTuple c = (ChangeTuple) itrC.next();
 212
 213         if( n.getAlpha().contains(c.getSetToMatch() ) ) {
 214           ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
 215           n.setAlphaNew(n.getAlphaNew().union(withChange) );
 216           nodesWithNewAlpha.add(n);
 217         }
 218       }
 219
 220       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 221       while( referItr.hasNext() ) {
 222         ReferenceEdge edge = referItr.next();
 223         todoEdges.add(edge);
 224
 225         if( !edgePlannedChanges.containsKey(edge) ) {
 226           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
 227         }
 228
 229         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 230       }
 231
 232       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
 233       while( refeeItr.hasNext() ) {
 234         ReferenceEdge edgeF = refeeItr.next();
 235         HeapRegionNode m     = edgeF.getDst();
 236
 237         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 238
 239         Iterator<ChangeTuple> itrCprime = C.iterator();
 240         while( itrCprime.hasNext() ) {
 241           ChangeTuple c = itrCprime.next();
 242           if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
 243             changesToPass = changesToPass.union(c);
 244           }
 245         }
 246
 247         if( !changesToPass.isEmpty() ) {
 248           if( !nodePlannedChanges.containsKey(m) ) {
 249             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
 250           }
 251
 252           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
 253
 254           if( !changesToPass.isSubset(currentChanges) ) {
 255
 256             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 257             todoNodes.add(m);
 258           }
 259         }
 260       }
 261
 262       todoNodes.remove(n);
 263     }
 264
 265     propagateTokensOverEdges(todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta);
 266   }
 267
 268
 269   protected void propagateTokensOverEdges(
 270     HashSet<ReferenceEdge>                   todoEdges,
 271     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
 272     HashSet<HeapRegionNode>                  nodesWithNewAlpha,
 273     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
 274
 275
 276     while( !todoEdges.isEmpty() ) {
 277       ReferenceEdge edgeE = todoEdges.iterator().next();
 278       todoEdges.remove(edgeE);
 279
 280       if( !edgePlannedChanges.containsKey(edgeE) ) {
 281         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
 282       }
 283
 284       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
 285
 286       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 287
 288       Iterator<ChangeTuple> itrC = C.iterator();
 289       while( itrC.hasNext() ) {
 290         ChangeTuple c = itrC.next();
 291         if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
 292           ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
 293           edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
 294           edgesWithNewBeta.add(edgeE);
 295           changesToPass = changesToPass.union(c);
 296         }
 297       }
 298
 299       OwnershipNode onSrc = edgeE.getSrc();
 300
 301       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 302         HeapRegionNode n = (HeapRegionNode) onSrc;
 303
 304         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 305         while( referItr.hasNext() ) {
 306           ReferenceEdge edgeF = referItr.next();
 307
 308           if( !edgePlannedChanges.containsKey(edgeF) ) {
 309             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
 310           }
 311
 312           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
 313
 314           if( !changesToPass.isSubset(currentChanges) ) {
 315             todoEdges.add(edgeF);
 316             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
 317           }
 318         }
 319       }
 320     }
 321   }
 322
 323
 324   ////////////////////////////////////////////////////
 325   //
 326   //  Assignment Operation Methods
 327   //
 328   //  These methods are high-level operations for
 329   //  modeling program assignment statements using
 330   //  the low-level reference create/remove methods
 331   //  above.
 332   //
 333   //  The destination in an assignment statement is
 334   //  going to have new references.  The method of
 335   //  determining the references depends on the type
 336   //  of the FlatNode assignment and the predicates
 337   //  of the nodes and edges involved.
 338   //
 339   ////////////////////////////////////////////////////
 340   public void assignTempYToTempX(TempDescriptor y,
 341                                  TempDescriptor x) {
 342
 343     LabelNode lnX = getLabelNodeFromTemp(x);
 344     LabelNode lnY = getLabelNodeFromTemp(y);
 345
 346     clearReferenceEdgesFrom(lnX, null, true);
 347
 348     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 349     while( itrYhrn.hasNext() ) {
 350       ReferenceEdge edgeY       = itrYhrn.next();
 351       HeapRegionNode referencee = edgeY.getDst();
 352       ReferenceEdge edgeNew    = edgeY.copy();
 353       edgeNew.setSrc(lnX);
 354
 355       addReferenceEdge(lnX, referencee, edgeNew);
 356     }
 357   }
 358
 359
 360   public void assignTempYFieldFToTempX(TempDescriptor y,
 361                                        FieldDescriptor f,
 362                                        TempDescriptor x) {
 363
 364     LabelNode lnX = getLabelNodeFromTemp(x);
 365     LabelNode lnY = getLabelNodeFromTemp(y);
 366
 367     clearReferenceEdgesFrom(lnX, null, true);
 368
 369     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 370     while( itrYhrn.hasNext() ) {
 371       ReferenceEdge edgeY = itrYhrn.next();
 372       HeapRegionNode hrnY  = edgeY.getDst();
 373       ReachabilitySet betaY = edgeY.getBeta();
 374
 375       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 376       while( itrHrnFhrn.hasNext() ) {
 377         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 378         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 379         ReachabilitySet betaHrn = edgeHrn.getBeta();
 380
 381         if( edgeHrn.getFieldDesc() == null ||
 382             edgeHrn.getFieldDesc() == f ) {
 383
 384           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 385                                                     hrnHrn,
 386                                                     f,
 387                                                     false,
 388                                                     betaY.intersection(betaHrn) );
 389
 390           addReferenceEdge(lnX, hrnHrn, edgeNew);
 391         }
 392       }
 393     }
 394   }
 395
 396
 397   public void assignTempYToTempXFieldF(TempDescriptor y,
 398                                        TempDescriptor x,
 399                                        FieldDescriptor f) {
 400
 401     LabelNode lnX = getLabelNodeFromTemp(x);
 402     LabelNode lnY = getLabelNodeFromTemp(y);
 403
 404     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 405     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 406
 407     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 408     while( itrXhrn.hasNext() ) {
 409       ReferenceEdge edgeX = itrXhrn.next();
 410       HeapRegionNode hrnX  = edgeX.getDst();
 411       ReachabilitySet betaX = edgeX.getBeta();
 412
 413       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 414
 415       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 416       while( itrYhrn.hasNext() ) {
 417         ReferenceEdge edgeY = itrYhrn.next();
 418         HeapRegionNode hrnY  = edgeY.getDst();
 419         ReachabilitySet O     = edgeY.getBeta();
 420
 421
 422         // propagate tokens over nodes starting from hrnSrc, and it will
 423         // take care of propagating back up edges from any touched nodes
 424         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 425         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 426
 427
 428         // then propagate back just up the edges from hrn
 429         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 430
 431         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 432
 433         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 434           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 435
 436         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 437         while( referItr.hasNext() ) {
 438           ReferenceEdge edgeUpstream = referItr.next();
 439           todoEdges.add(edgeUpstream);
 440           edgePlannedChanges.put(edgeUpstream, Cx);
 441         }
 442
 443         propagateTokensOverEdges(todoEdges,
 444                                  edgePlannedChanges,
 445                                  nodesWithNewAlpha,
 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     // keep track of heap regions that were created for
 524     // parameter labels, the index of the parameter they
 525     // are for is important when resolving method calls
 526     Integer newID = hrn.getID();
 527     assert !id2paramIndex.containsKey(newID);
 528     assert !id2paramIndex.containsValue(paramIndex);
 529     id2paramIndex.put(newID, paramIndex);
 530     paramIndex2id.put(paramIndex, newID);
 531
 532     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
 533                                                               true,
 534                                                               TokenTuple.ARITY_ONE) );
 535
 536     // heap regions for parameters are always multiple object (see above)
 537     // and have a reference to themselves, because we can't know the
 538     // structure of memory that is passed into the method.  We're assuming
 539     // the worst here.
 540
 541     ReferenceEdge edgeFromLabel =
 542       new ReferenceEdge(lnParam, hrn, null, false, beta);
 543
 544     ReferenceEdge edgeReflexive =
 545       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 546
 547     addReferenceEdge(lnParam, hrn, edgeFromLabel);
 548     addReferenceEdge(hrn,     hrn, edgeReflexive);
 549   }
 550
 551
 552   public void assignNewAllocationToTempX(TempDescriptor x,
 553                                          AllocationSite as) {
 554     assert x  != null;
 555     assert as != null;
 556
 557     age(as);
 558
 559     // after the age operation the newest (or zero-ith oldest)
 560     // node associated with the allocation site should have
 561     // no references to it as if it were a newly allocated
 562     // heap region, so make a reference to it to complete
 563     // this operation
 564
 565     Integer idNewest  = as.getIthOldest(0);
 566     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 567     assert hrnNewest != null;
 568
 569     LabelNode lnX = getLabelNodeFromTemp(x);
 570     clearReferenceEdgesFrom(lnX, null, true);
 571
 572     ReferenceEdge edgeNew =
 573       new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
 574
 575     addReferenceEdge(lnX, hrnNewest, edgeNew);
 576   }
 577
 578
 579   // use the allocation site (unique to entire analysis) to
 580   // locate the heap region nodes in this ownership graph
 581   // that should be aged.  The process models the allocation
 582   // of new objects and collects all the oldest allocations
 583   // in a summary node to allow for a finite analysis
 584   //
 585   // There is an additional property of this method.  After
 586   // running it on a particular ownership graph (many graphs
 587   // may have heap regions related to the same allocation site)
 588   // the heap region node objects in this ownership graph will be
 589   // allocated.  Therefore, after aging a graph for an allocation
 590   // site, attempts to retrieve the heap region nodes using the
 591   // integer id's contained in the allocation site should always
 592   // return non-null heap regions.
 593   public void age(AllocationSite as) {
 594
 595     // aging adds this allocation site to the graph's
 596     // list of sites that exist in the graph, or does
 597     // nothing if the site is already in the list
 598     allocationSites.add(as);
 599
 600     // get the summary node for the allocation site in the context
 601     // of this particular ownership graph
 602     HeapRegionNode hrnSummary = getSummaryNode(as);
 603
 604     // merge oldest node into summary
 605     Integer idK  = as.getOldest();
 606     HeapRegionNode hrnK = id2hrn.get(idK);
 607     mergeIntoSummary(hrnK, hrnSummary);
 608
 609     // move down the line of heap region nodes
 610     // clobbering the ith and transferring all references
 611     // to and from i-1 to node i.  Note that this clobbers
 612     // the oldest node (hrnK) that was just merged into
 613     // the summary
 614     for( int i = allocationDepth - 1; i > 0; --i ) {
 615
 616       // move references from the i-1 oldest to the ith oldest
 617       Integer idIth     = as.getIthOldest(i);
 618       HeapRegionNode hrnI      = id2hrn.get(idIth);
 619       Integer idImin1th = as.getIthOldest(i - 1);
 620       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 621
 622       transferOnto(hrnImin1, hrnI);
 623     }
 624
 625     // as stated above, the newest node should have had its
 626     // references moved over to the second oldest, so we wipe newest
 627     // in preparation for being the new object to assign something to
 628     Integer id0th = as.getIthOldest(0);
 629     HeapRegionNode hrn0  = id2hrn.get(id0th);
 630     assert hrn0 != null;
 631
 632     // clear all references in and out of newest node
 633     clearReferenceEdgesFrom(hrn0, null, true);
 634     clearReferenceEdgesTo(hrn0, null, true);
 635
 636
 637     // now tokens in reachability sets need to "age" also
 638     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 639     while( itrAllLabelNodes.hasNext() ) {
 640       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 641       LabelNode ln = (LabelNode) me.getValue();
 642
 643       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 644       while( itrEdges.hasNext() ) {
 645         ageTokens(as, itrEdges.next() );
 646       }
 647     }
 648
 649     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 650     while( itrAllHRNodes.hasNext() ) {
 651       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
 652       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 653
 654       ageTokens(as, hrnToAge);
 655
 656       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
 657       while( itrEdges.hasNext() ) {
 658         ageTokens(as, itrEdges.next() );
 659       }
 660     }
 661
 662
 663     // after tokens have been aged, reset newest node's reachability
 664     if( hrn0.isFlagged() ) {
 665       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
 666                                           new TokenTuple(hrn0)
 667                                           )
 668                                         ).makeCanonical()
 669                     );
 670     } else {
 671       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
 672                                         ).makeCanonical()
 673                     );
 674     }
 675   }
 676
 677
 678   protected HeapRegionNode getSummaryNode(AllocationSite as) {
 679
 680     Integer idSummary  = as.getSummary();
 681     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
 682
 683     // If this is null then we haven't touched this allocation site
 684     // in the context of the current ownership graph, so allocate
 685     // heap region nodes appropriate for the entire allocation site.
 686     // This should only happen once per ownership graph per allocation site,
 687     // and a particular integer id can be used to locate the heap region
 688     // in different ownership graphs that represents the same part of an
 689     // allocation site.
 690     if( hrnSummary == null ) {
 691
 692       boolean hasFlags = false;
 693       if( as.getType().isClass() ) {
 694         hasFlags = as.getType().getClassDesc().hasFlags();
 695       }
 696
 697       hrnSummary = createNewHeapRegionNode(idSummary,
 698                                            false,
 699                                            hasFlags,
 700                                            true,
 701                                            false,
 702                                            as,
 703                                            null,
 704                                            as + "\\n" + as.getType() + "\\nsummary");
 705
 706       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 707         Integer idIth = as.getIthOldest(i);
 708         assert !id2hrn.containsKey(idIth);
 709         createNewHeapRegionNode(idIth,
 710                                 true,
 711                                 hasFlags,
 712                                 false,
 713                                 false,
 714                                 as,
 715                                 null,
 716                                 as + "\\n" + as.getType() + "\\n" + i + " oldest");
 717       }
 718     }
 719
 720     return hrnSummary;
 721   }
 722
 723
 724   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
 725
 726     Integer idShadowSummary  = -(as.getSummary());
 727     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
 728
 729     if( hrnShadowSummary == null ) {
 730
 731       boolean hasFlags = false;
 732       if( as.getType().isClass() ) {
 733         hasFlags = as.getType().getClassDesc().hasFlags();
 734       }
 735
 736       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
 737                                                  false,
 738                                                  hasFlags,
 739                                                  true,
 740                                                  false,
 741                                                  as,
 742                                                  null,
 743                                                  as + "\\n" + as.getType() + "\\nshadowSum");
 744
 745       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 746         Integer idShadowIth = -(as.getIthOldest(i));
 747         assert !id2hrn.containsKey(idShadowIth);
 748         createNewHeapRegionNode(idShadowIth,
 749                                 true,
 750                                 hasFlags,
 751                                 false,
 752                                 false,
 753                                 as,
 754                                 null,
 755                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
 756       }
 757     }
 758
 759     return hrnShadowSummary;
 760   }
 761
 762
 763   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
 764     assert hrnSummary.isNewSummary();
 765
 766     // transfer references _from_ hrn over to hrnSummary
 767     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
 768     while( itrReferencee.hasNext() ) {
 769       ReferenceEdge edge       = itrReferencee.next();
 770       ReferenceEdge edgeMerged = edge.copy();
 771       edgeMerged.setSrc(hrnSummary);
 772
 773       HeapRegionNode hrnReferencee = edge.getDst();
 774       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
 775
 776       if( edgeSummary == null ) {
 777         // the merge is trivial, nothing to be done
 778       } else {
 779         // otherwise an edge from the referencer to hrnSummary exists already
 780         // and the edge referencer->hrn should be merged with it
 781         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 782       }
 783
 784       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
 785     }
 786
 787     // next transfer references _to_ hrn over to hrnSummary
 788     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
 789     while( itrReferencer.hasNext() ) {
 790       ReferenceEdge edge         = itrReferencer.next();
 791       ReferenceEdge edgeMerged   = edge.copy();
 792       edgeMerged.setDst(hrnSummary);
 793
 794       OwnershipNode onReferencer = edge.getSrc();
 795       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
 796
 797       if( edgeSummary == null ) {
 798         // the merge is trivial, nothing to be done
 799       } else {
 800         // otherwise an edge from the referencer to alpha_S exists already
 801         // and the edge referencer->alpha_K should be merged with it
 802         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 803       }
 804
 805       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
 806     }
 807
 808     // then merge hrn reachability into hrnSummary
 809     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
 810   }
 811
 812
 813   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
 814
 815     // clear references in and out of node i
 816     clearReferenceEdgesFrom(hrnB, null, true);
 817     clearReferenceEdgesTo(hrnB, null, true);
 818
 819     // copy each edge in and out of A to B
 820     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
 821     while( itrReferencee.hasNext() ) {
 822       ReferenceEdge edge          = itrReferencee.next();
 823       HeapRegionNode hrnReferencee = edge.getDst();
 824       ReferenceEdge edgeNew       = edge.copy();
 825       edgeNew.setSrc(hrnB);
 826
 827       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
 828     }
 829
 830     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
 831     while( itrReferencer.hasNext() ) {
 832       ReferenceEdge edge         = itrReferencer.next();
 833       OwnershipNode onReferencer = edge.getSrc();
 834       ReferenceEdge edgeNew      = edge.copy();
 835       edgeNew.setDst(hrnB);
 836
 837       addReferenceEdge(onReferencer, hrnB, edgeNew);
 838     }
 839
 840     // replace hrnB reachability with hrnA's
 841     hrnB.setAlpha(hrnA.getAlpha() );
 842   }
 843
 844
 845   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
 846     edge.setBeta(edge.getBeta().ageTokens(as) );
 847   }
 848
 849   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
 850     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
 851   }
 852
 853   protected void majorAgeTokens(AllocationSite as, ReferenceEdge edge) {
 854     //edge.setBeta( edge.getBeta().majorAgeTokens( as ) );
 855   }
 856
 857   protected void majorAgeTokens(AllocationSite as, HeapRegionNode hrn) {
 858     //hrn.setAlpha( hrn.getAlpha().majorAgeTokens( as ) );
 859   }
 860
 861
 862   public void resolveMethodCall(FlatCall fc,
 863                                 boolean isStatic,
 864                                 FlatMethod fm,
 865                                 OwnershipGraph ogCallee) {
 866
 867     /*
 868        // verify the existence of allocation sites and their
 869        // shadows from the callee in the context of this caller graph
 870        Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
 871        while( asItr.hasNext() ) {
 872         AllocationSite allocSite        = asItr.next();
 873         HeapRegionNode hrnSummary       = getSummaryNode      ( allocSite );
 874         HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
 875        }
 876
 877        // in non-static methods there is a "this" pointer
 878        // that should be taken into account
 879        if( isStatic ) {
 880         assert fc.numArgs()     == fm.numParameters();
 881        } else {
 882         assert fc.numArgs() + 1 == fm.numParameters();
 883        }
 884
 885        // make a change set to translate callee tokens into caller tokens
 886        ChangeTupleSet C = new ChangeTupleSet().makeCanonical();
 887
 888        for( int i = 0; i < fm.numParameters(); ++i ) {
 889
 890         Integer indexParam = new Integer( i );
 891
 892         System.out.println( "In method "+fm+ " on param "+indexParam );
 893
 894         assert ogCallee.paramIndex2id.containsKey( indexParam );
 895         Integer idParam = ogCallee.paramIndex2id.get( indexParam );
 896
 897         assert ogCallee.id2hrn.containsKey( idParam );
 898         HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
 899         assert hrnParam != null;
 900
 901         TokenTupleSet calleeTokenToMatch =
 902             new TokenTupleSet( new TokenTuple( hrnParam ) ).makeCanonical();
 903
 904
 905         // now depending on whether the callee is static or not
 906         // we need to account for a "this" argument in order to
 907         // find the matching argument in the caller context
 908         TempDescriptor argTemp;
 909         if( isStatic ) {
 910             argTemp = fc.getArg( indexParam );
 911         } else {
 912             if( indexParam == 0 ) {
 913                 argTemp = fc.getThis();
 914             } else {
 915                 argTemp = fc.getArg( indexParam - 1 );
 916             }
 917         }
 918
 919         LabelNode argLabel = getLabelNodeFromTemp( argTemp );
 920         Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
 921         while( argHeapRegionsItr.hasNext() ) {
 922             Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
 923             HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
 924             ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
 925
 926             Iterator<TokenTupleSet> ttsItr = repArg.getBeta().iterator();
 927             while( ttsItr.hasNext() ) {
 928                 TokenTupleSet callerTokensToReplace = ttsItr.next();
 929
 930                 ChangeTuple ct = new ChangeTuple( calleeTokenToMatch,
 931                                                   callerTokensToReplace ).makeCanonical();
 932
 933                 C = C.union( ct );
 934             }
 935         }
 936        }
 937
 938        System.out.println( "Applying method call "+fm );
 939        System.out.println( "  Change: "+C );
 940
 941
 942        // the heap regions represented by the arguments (caller graph)
 943        // and heap regions for the parameters (callee graph)
 944        // don't correspond to each other by heap region ID.  In fact,
 945        // an argument label node can be referencing several heap regions
 946        // so the parameter label always references a multiple-object
 947        // heap region in order to handle the range of possible contexts
 948        // for a method call.  This means we need to make a special mapping
 949        // of argument->parameter regions in order to update the caller graph
 950
 951        // for every heap region->heap region edge in the
 952        // callee graph, create the matching edge or edges
 953        // in the caller graph
 954        Set      sCallee = ogCallee.id2hrn.entrySet();
 955        Iterator iCallee = sCallee.iterator();
 956        while( iCallee.hasNext() ) {
 957         Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
 958         Integer        idCallee  = (Integer)        meCallee.getKey();
 959         HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
 960
 961         HeapRegionNode hrnChildCallee = null;
 962         Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
 963         while( heapRegionsItrCallee.hasNext() ) {
 964             Map.Entry me                 = (Map.Entry)               heapRegionsItrCallee.next();
 965             hrnChildCallee               = (HeapRegionNode)          me.getKey();
 966             ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
 967
 968             Integer idChildCallee = hrnChildCallee.getID();
 969
 970             // only address this edge if it is not a special reflexive edge
 971             if( !repC.isInitialParamReflexive() ) {
 972
 973                 // now we know that in the callee method's ownership graph
 974                 // there is a heap region->heap region reference edge given
 975                 // by heap region pointers:
 976                 // hrnCallee -> heapChildCallee
 977                 //
 978                 // or by the ownership-graph independent ID's:
 979                 // idCallee -> idChildCallee
 980                 //
 981                 // So now make a set of possible source heaps in the caller graph
 982                 // and a set of destination heaps in the caller graph, and make
 983                 // a reference edge in the caller for every possible (src,dst) pair
 984                 HashSet<HeapRegionNode> possibleCallerSrcs =
 985                     getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 986                                                          idCallee,
 987                                                          fc,
 988                                                          isStatic );
 989
 990                 HashSet<HeapRegionNode> possibleCallerDsts =
 991                     getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 992                                                          idChildCallee,
 993                                                          fc,
 994                                                          isStatic );
 995
 996                 // make every possible pair of {srcSet} -> {dstSet} edges in the caller
 997                 Iterator srcItr = possibleCallerSrcs.iterator();
 998                 while( srcItr.hasNext() ) {
 999                     HeapRegionNode src = (HeapRegionNode) srcItr.next();
1000
1001                     Iterator dstItr = possibleCallerDsts.iterator();
1002                     while( dstItr.hasNext() ) {
1003                         HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1004
1005                         addReferenceEdge( src, dst, repC.copy() );
1006                     }
1007                 }
1008             }
1009         }
1010        }
1011      */
1012   }
1013
1014   /*
1015      private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
1016                                                                        Integer        idCallee,
1017                                                                        FlatCall       fc,
1018                                                                        boolean        isStatic ) {
1019
1020       HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1021
1022       if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
1023           // the heap region that is part of this
1024           // reference edge won't have a matching ID in the
1025           // caller graph because it is specifically allocated
1026           // for a particular parameter.  Use that information
1027           // to find the corresponding argument label in the
1028           // caller in order to create the proper reference edge
1029           // or edges.
1030           assert !id2hrn.containsKey( idCallee );
1031
1032           Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
1033           TempDescriptor argTemp;
1034
1035           // now depending on whether the callee is static or not
1036           // we need to account for a "this" argument in order to
1037           // find the matching argument in the caller context
1038           if( isStatic ) {
1039               argTemp = fc.getArg( paramIndex );
1040           } else {
1041               if( paramIndex == 0 ) {
1042                   argTemp = fc.getThis();
1043               } else {
1044                   argTemp = fc.getArg( paramIndex - 1 );
1045               }
1046           }
1047
1048           LabelNode argLabel = getLabelNodeFromTemp( argTemp );
1049           Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
1050           while( argHeapRegionsItr.hasNext() ) {
1051               Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
1052               HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
1053               ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
1054
1055               possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
1056           }
1057
1058       } else {
1059           // this heap region is not a parameter, so it should
1060           // have a matching heap region in the caller graph
1061           assert id2hrn.containsKey( idCallee );
1062           possibleCallerHRNs.add( id2hrn.get( idCallee ) );
1063       }
1064
1065       return possibleCallerHRNs;
1066      }
1067    */
1068
1069
1070   ////////////////////////////////////////////////////
1071   // in merge() and equals() methods the suffix A
1072   // represents the passed in graph and the suffix
1073   // B refers to the graph in this object
1074   // Merging means to take the incoming graph A and
1075   // merge it into B, so after the operation graph B
1076   // is the final result.
1077   ////////////////////////////////////////////////////
1078   public void merge(OwnershipGraph og) {
1079
1080     if( og == null ) {
1081       return;
1082     }
1083
1084     mergeOwnershipNodes(og);
1085     mergeReferenceEdges(og);
1086     mergeId2paramIndex(og);
1087     mergeAllocationSites(og);
1088   }
1089
1090
1091   protected void mergeOwnershipNodes(OwnershipGraph og) {
1092     Set sA = og.id2hrn.entrySet();
1093     Iterator iA = sA.iterator();
1094     while( iA.hasNext() ) {
1095       Map.Entry meA  = (Map.Entry)iA.next();
1096       Integer idA  = (Integer)        meA.getKey();
1097       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1098
1099       // if this graph doesn't have a node the
1100       // incoming graph has, allocate it
1101       if( !id2hrn.containsKey(idA) ) {
1102         HeapRegionNode hrnB = hrnA.copy();
1103         id2hrn.put(idA, hrnB);
1104
1105       } else {
1106         // otherwise this is a node present in both graphs
1107         // so make the new reachability set a union of the
1108         // nodes' reachability sets
1109         HeapRegionNode hrnB = id2hrn.get(idA);
1110         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1111       }
1112     }
1113
1114     // now add any label nodes that are in graph B but
1115     // not in A
1116     sA = og.td2ln.entrySet();
1117     iA = sA.iterator();
1118     while( iA.hasNext() ) {
1119       Map.Entry meA = (Map.Entry)iA.next();
1120       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1121       LabelNode lnA = (LabelNode)      meA.getValue();
1122
1123       // if the label doesn't exist in B, allocate and add it
1124       LabelNode lnB = getLabelNodeFromTemp(tdA);
1125     }
1126   }
1127
1128   protected void mergeReferenceEdges(OwnershipGraph og) {
1129
1130     // heap regions
1131     Set sA = og.id2hrn.entrySet();
1132     Iterator iA = sA.iterator();
1133     while( iA.hasNext() ) {
1134       Map.Entry meA  = (Map.Entry)iA.next();
1135       Integer idA  = (Integer)        meA.getKey();
1136       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1137
1138       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1139       while( heapRegionsItrA.hasNext() ) {
1140         ReferenceEdge edgeA     = heapRegionsItrA.next();
1141         HeapRegionNode hrnChildA = edgeA.getDst();
1142         Integer idChildA  = hrnChildA.getID();
1143
1144         // at this point we know an edge in graph A exists
1145         // idA -> idChildA, does this exist in B?
1146         assert id2hrn.containsKey(idA);
1147         HeapRegionNode hrnB        = id2hrn.get(idA);
1148         ReferenceEdge edgeToMerge = null;
1149
1150         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1151         while( heapRegionsItrB.hasNext() &&
1152                edgeToMerge == null          ) {
1153
1154           ReferenceEdge edgeB     = heapRegionsItrB.next();
1155           HeapRegionNode hrnChildB = edgeB.getDst();
1156           Integer idChildB  = hrnChildB.getID();
1157
1158           // don't use the ReferenceEdge.equals() here because
1159           // we're talking about existence between graphs
1160           if( idChildB.equals(idChildA) &&
1161               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1162             edgeToMerge = edgeB;
1163           }
1164         }
1165
1166         // if the edge from A was not found in B,
1167         // add it to B.
1168         if( edgeToMerge == null ) {
1169           assert id2hrn.containsKey(idChildA);
1170           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1171           edgeToMerge = edgeA.copy();
1172           edgeToMerge.setSrc(hrnB);
1173           edgeToMerge.setDst(hrnChildB);
1174           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1175         }
1176         // otherwise, the edge already existed in both graphs
1177         // so merge their reachability sets
1178         else {
1179           // just replace this beta set with the union
1180           assert edgeToMerge != null;
1181           edgeToMerge.setBeta(
1182             edgeToMerge.getBeta().union(edgeA.getBeta() )
1183             );
1184           if( !edgeA.isInitialParamReflexive() ) {
1185             edgeToMerge.setIsInitialParamReflexive(false);
1186           }
1187         }
1188       }
1189     }
1190
1191     // and then again with label nodes
1192     sA = og.td2ln.entrySet();
1193     iA = sA.iterator();
1194     while( iA.hasNext() ) {
1195       Map.Entry meA = (Map.Entry)iA.next();
1196       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1197       LabelNode lnA = (LabelNode)      meA.getValue();
1198
1199       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1200       while( heapRegionsItrA.hasNext() ) {
1201         ReferenceEdge edgeA     = heapRegionsItrA.next();
1202         HeapRegionNode hrnChildA = edgeA.getDst();
1203         Integer idChildA  = hrnChildA.getID();
1204
1205         // at this point we know an edge in graph A exists
1206         // tdA -> idChildA, does this exist in B?
1207         assert td2ln.containsKey(tdA);
1208         LabelNode lnB         = td2ln.get(tdA);
1209         ReferenceEdge edgeToMerge = null;
1210
1211         // labels never have edges with a field
1212         //assert edgeA.getFieldDesc() == null;
1213
1214         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1215         while( heapRegionsItrB.hasNext() &&
1216                edgeToMerge == null          ) {
1217
1218           ReferenceEdge edgeB     = heapRegionsItrB.next();
1219           HeapRegionNode hrnChildB = edgeB.getDst();
1220           Integer idChildB  = hrnChildB.getID();
1221
1222           // labels never have edges with a field
1223           //assert edgeB.getFieldDesc() == null;
1224
1225           // don't use the ReferenceEdge.equals() here because
1226           // we're talking about existence between graphs
1227           if( idChildB.equals(idChildA) &&
1228               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1229             edgeToMerge = edgeB;
1230           }
1231         }
1232
1233         // if the edge from A was not found in B,
1234         // add it to B.
1235         if( edgeToMerge == null ) {
1236           assert id2hrn.containsKey(idChildA);
1237           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1238           edgeToMerge = edgeA.copy();
1239           edgeToMerge.setSrc(lnB);
1240           edgeToMerge.setDst(hrnChildB);
1241           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1242         }
1243         // otherwise, the edge already existed in both graphs
1244         // so merge their reachability sets
1245         else {
1246           // just replace this beta set with the union
1247           edgeToMerge.setBeta(
1248             edgeToMerge.getBeta().union(edgeA.getBeta() )
1249             );
1250           if( !edgeA.isInitialParamReflexive() ) {
1251             edgeToMerge.setIsInitialParamReflexive(false);
1252           }
1253         }
1254       }
1255     }
1256   }
1257
1258   // you should only merge ownership graphs that have the
1259   // same number of parameters, or if one or both parameter
1260   // index tables are empty
1261   protected void mergeId2paramIndex(OwnershipGraph og) {
1262     if( id2paramIndex.size() == 0 ) {
1263       id2paramIndex = og.id2paramIndex;
1264       paramIndex2id = og.paramIndex2id;
1265       return;
1266     }
1267
1268     if( og.id2paramIndex.size() == 0 ) {
1269       return;
1270     }
1271
1272     assert id2paramIndex.size() == og.id2paramIndex.size();
1273   }
1274
1275   protected void mergeAllocationSites(OwnershipGraph og) {
1276     allocationSites.addAll(og.allocationSites);
1277   }
1278
1279
1280
1281   // it is necessary in the equals() member functions
1282   // to "check both ways" when comparing the data
1283   // structures of two graphs.  For instance, if all
1284   // edges between heap region nodes in graph A are
1285   // present and equal in graph B it is not sufficient
1286   // to say the graphs are equal.  Consider that there
1287   // may be edges in graph B that are not in graph A.
1288   // the only way to know that all edges in both graphs
1289   // are equally present is to iterate over both data
1290   // structures and compare against the other graph.
1291   public boolean equals(OwnershipGraph og) {
1292
1293     if( og == null ) {
1294       return false;
1295     }
1296
1297     if( !areHeapRegionNodesEqual(og) ) {
1298       return false;
1299     }
1300
1301     if( !areLabelNodesEqual(og) ) {
1302       return false;
1303     }
1304
1305     if( !areReferenceEdgesEqual(og) ) {
1306       return false;
1307     }
1308
1309     if( !areId2paramIndexEqual(og) ) {
1310       return false;
1311     }
1312
1313     // if everything is equal up to this point,
1314     // assert that allocationSites is also equal--
1315     // this data is redundant and kept for efficiency
1316     assert allocationSites.equals(og.allocationSites);
1317
1318     return true;
1319   }
1320
1321   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
1322
1323     if( !areallHRNinAalsoinBandequal(this, og) ) {
1324       return false;
1325     }
1326
1327     if( !areallHRNinAalsoinBandequal(og, this) ) {
1328       return false;
1329     }
1330
1331     return true;
1332   }
1333
1334   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
1335                                                        OwnershipGraph ogB) {
1336     Set sA = ogA.id2hrn.entrySet();
1337     Iterator iA = sA.iterator();
1338     while( iA.hasNext() ) {
1339       Map.Entry meA  = (Map.Entry)iA.next();
1340       Integer idA  = (Integer)        meA.getKey();
1341       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1342
1343       if( !ogB.id2hrn.containsKey(idA) ) {
1344         return false;
1345       }
1346
1347       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1348       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
1349         return false;
1350       }
1351     }
1352
1353     return true;
1354   }
1355
1356
1357   protected boolean areLabelNodesEqual(OwnershipGraph og) {
1358
1359     if( !areallLNinAalsoinBandequal(this, og) ) {
1360       return false;
1361     }
1362
1363     if( !areallLNinAalsoinBandequal(og, this) ) {
1364       return false;
1365     }
1366
1367     return true;
1368   }
1369
1370   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
1371                                                       OwnershipGraph ogB) {
1372     Set sA = ogA.td2ln.entrySet();
1373     Iterator iA = sA.iterator();
1374     while( iA.hasNext() ) {
1375       Map.Entry meA = (Map.Entry)iA.next();
1376       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1377
1378       if( !ogB.td2ln.containsKey(tdA) ) {
1379         return false;
1380       }
1381     }
1382
1383     return true;
1384   }
1385
1386
1387   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
1388     if( !areallREinAandBequal(this, og) ) {
1389       return false;
1390     }
1391
1392     return true;
1393   }
1394
1395   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
1396                                                 OwnershipGraph ogB) {
1397
1398     // check all the heap region->heap region edges
1399     Set sA = ogA.id2hrn.entrySet();
1400     Iterator iA = sA.iterator();
1401     while( iA.hasNext() ) {
1402       Map.Entry meA  = (Map.Entry)iA.next();
1403       Integer idA  = (Integer)        meA.getKey();
1404       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1405
1406       // we should have already checked that the same
1407       // heap regions exist in both graphs
1408       assert ogB.id2hrn.containsKey(idA);
1409
1410       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
1411         return false;
1412       }
1413
1414       // then check every edge in B for presence in A, starting
1415       // from the same parent HeapRegionNode
1416       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
1417
1418       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
1419         return false;
1420       }
1421     }
1422
1423     // then check all the label->heap region edges
1424     sA = ogA.td2ln.entrySet();
1425     iA = sA.iterator();
1426     while( iA.hasNext() ) {
1427       Map.Entry meA = (Map.Entry)iA.next();
1428       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1429       LabelNode lnA = (LabelNode)      meA.getValue();
1430
1431       // we should have already checked that the same
1432       // label nodes exist in both graphs
1433       assert ogB.td2ln.containsKey(tdA);
1434
1435       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
1436         return false;
1437       }
1438
1439       // then check every edge in B for presence in A, starting
1440       // from the same parent LabelNode
1441       LabelNode lnB = ogB.td2ln.get(tdA);
1442
1443       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
1444         return false;
1445       }
1446     }
1447
1448     return true;
1449   }
1450
1451
1452   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
1453                                                  OwnershipNode onA,
1454                                                  OwnershipGraph ogB) {
1455
1456     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
1457     while( itrA.hasNext() ) {
1458       ReferenceEdge edgeA     = itrA.next();
1459       HeapRegionNode hrnChildA = edgeA.getDst();
1460       Integer idChildA  = hrnChildA.getID();
1461
1462       assert ogB.id2hrn.containsKey(idChildA);
1463
1464       // at this point we know an edge in graph A exists
1465       // onA -> idChildA, does this exact edge exist in B?
1466       boolean edgeFound = false;
1467
1468       OwnershipNode onB = null;
1469       if( onA instanceof HeapRegionNode ) {
1470         HeapRegionNode hrnA = (HeapRegionNode) onA;
1471         onB = ogB.id2hrn.get(hrnA.getID() );
1472       } else {
1473         LabelNode lnA = (LabelNode) onA;
1474         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
1475       }
1476
1477       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
1478       while( itrB.hasNext() ) {
1479         ReferenceEdge edgeB     = itrB.next();
1480         HeapRegionNode hrnChildB = edgeB.getDst();
1481         Integer idChildB  = hrnChildB.getID();
1482
1483         if( idChildA.equals(idChildB) &&
1484             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
1485
1486           // there is an edge in the right place with the right field,
1487           // but do they have the same attributes?
1488           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
1489
1490             edgeFound = true;
1491             //} else {
1492             //return false;
1493           }
1494         }
1495       }
1496
1497       if( !edgeFound ) {
1498         return false;
1499       }
1500     }
1501
1502     return true;
1503   }
1504
1505
1506   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
1507     return id2paramIndex.size() == og.id2paramIndex.size();
1508   }
1509
1510
1511   /*
1512      // given a set B of heap region node ID's, return the set of heap
1513      // region node ID's that is reachable from B
1514      public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1515
1516       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1517       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1518
1519       // initial nodes to visit are from set B
1520       Iterator initialItr = idSetB.iterator();
1521       while( initialItr.hasNext() ) {
1522           Integer idInitial = (Integer) initialItr.next();
1523           assert id2hrn.contains( idInitial );
1524           HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1525           toVisit.add( hrnInitial );
1526       }
1527
1528       HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1529
1530       // do a heap traversal
1531       while( !toVisit.isEmpty() ) {
1532           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1533           toVisit.remove( hrnVisited );
1534           visited.add   ( hrnVisited );
1535
1536           // for every node visited, add it to the total
1537           // reachable set
1538           idSetReachableFromB.add( hrnVisited.getID() );
1539
1540           // find other reachable nodes
1541           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1542           while( referenceeItr.hasNext() ) {
1543               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1544               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1545               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1546
1547               if( !visited.contains( hrnReferencee ) ) {
1548                   toVisit.add( hrnReferencee );
1549               }
1550           }
1551       }
1552
1553       return idSetReachableFromB;
1554      }
1555
1556
1557      // used to find if a heap region can possibly have a reference to
1558      // any of the heap regions in the given set
1559      // if the id supplied is in the set, then a self-referencing edge
1560      // would return true, but that special case is specifically allowed
1561      // meaning that it isn't an external alias
1562      public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1563
1564       assert id2hrn.contains( id );
1565       HeapRegionNode hrn = id2hrn.get( id );
1566
1567
1568       //HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1569
1570       //Iterator i = idSet.iterator();
1571       //while( i.hasNext() ) {
1572       //    Integer idFromSet = (Integer) i.next();
1573       //   assert id2hrn.contains( idFromSet );
1574       //    hrnSet.add( id2hrn.get( idFromSet ) );
1575       //}
1576
1577
1578       // do a traversal from hrn and see if any of the
1579       // heap regions from the set come up during that
1580       HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1581       HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1582
1583       toVisit.add( hrn );
1584       while( !toVisit.isEmpty() ) {
1585           HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1586           toVisit.remove( hrnVisited );
1587           visited.add   ( hrnVisited );
1588
1589           Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1590           while( referenceeItr.hasNext() ) {
1591               Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1592               HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1593               ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1594
1595               if( idSet.contains( hrnReferencee.getID() ) ) {
1596                   if( !id.equals( hrnReferencee.getID() ) ) {
1597                       return true;
1598                   }
1599               }
1600
1601               if( !visited.contains( hrnReferencee ) ) {
1602                   toVisit.add( hrnReferencee );
1603               }
1604           }
1605       }
1606
1607       return false;
1608      }
1609    */
1610
1611
1612   // for writing ownership graphs to dot files
1613   public void writeGraph(Descriptor methodDesc,
1614                          FlatNode fn,
1615                          boolean writeLabels,
1616                          boolean labelSelect,
1617                          boolean pruneGarbage,
1618                          boolean writeReferencers
1619                          ) throws java.io.IOException {
1620     writeGraph(
1621       methodDesc.getSymbol() +
1622       methodDesc.getNum() +
1623       fn.toString(),
1624       writeLabels,
1625       labelSelect,
1626       pruneGarbage,
1627       writeReferencers
1628       );
1629   }
1630
1631   public void writeGraph(Descriptor methodDesc,
1632                          FlatNode fn,
1633                          boolean writeLabels,
1634                          boolean writeReferencers
1635                          ) throws java.io.IOException {
1636     writeGraph(
1637       methodDesc.getSymbol() +
1638       methodDesc.getNum() +
1639       fn.toString(),
1640       writeLabels,
1641       false,
1642       false,
1643       writeReferencers
1644       );
1645   }
1646
1647   public void writeGraph(Descriptor methodDesc,
1648                          boolean writeLabels,
1649                          boolean writeReferencers
1650                          ) throws java.io.IOException {
1651     writeGraph(
1652       methodDesc.getSymbol() +
1653       methodDesc.getNum() +
1654       "COMPLETE",
1655       writeLabels,
1656       false,
1657       false,
1658       writeReferencers
1659       );
1660   }
1661
1662   public void writeGraph(Descriptor methodDesc,
1663                          boolean writeLabels,
1664                          boolean labelSelect,
1665                          boolean pruneGarbage,
1666                          boolean writeReferencers
1667                          ) throws java.io.IOException {
1668     writeGraph(
1669       methodDesc.getSymbol() +
1670       methodDesc.getNum() +
1671       "COMPLETE",
1672       writeLabels,
1673       labelSelect,
1674       pruneGarbage,
1675       writeReferencers
1676       );
1677   }
1678
1679   public void writeGraph(String graphName,
1680                          boolean writeLabels,
1681                          boolean labelSelect,
1682                          boolean pruneGarbage,
1683                          boolean writeReferencers
1684                          ) throws java.io.IOException {
1685
1686     // remove all non-word characters from the graph name so
1687     // the filename and identifier in dot don't cause errors
1688     graphName = graphName.replaceAll("[\\W]", "");
1689
1690     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
1691     bw.write("digraph "+graphName+" {\n");
1692     //bw.write( "  size=\"7.5,10\";\n" );
1693
1694     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1695
1696     // then visit every heap region node
1697     if( !pruneGarbage ) {
1698       Set s = id2hrn.entrySet();
1699       Iterator i = s.iterator();
1700       while( i.hasNext() ) {
1701         Map.Entry me  = (Map.Entry)i.next();
1702         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1703         if( !visited.contains(hrn) ) {
1704           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
1705                                   hrn,
1706                                   bw,
1707                                   null,
1708                                   visited,
1709                                   writeReferencers);
1710         }
1711       }
1712     }
1713
1714     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
1715
1716
1717     // then visit every label node, useful for debugging
1718     if( writeLabels ) {
1719       Set s = td2ln.entrySet();
1720       Iterator i = s.iterator();
1721       while( i.hasNext() ) {
1722         Map.Entry me = (Map.Entry)i.next();
1723         LabelNode ln = (LabelNode) me.getValue();
1724
1725         if( labelSelect ) {
1726           String labelStr = ln.getTempDescriptorString();
1727           if( labelStr.startsWith("___temp") ||
1728               labelStr.startsWith("___dst") ||
1729               labelStr.startsWith("___srctmp") ||
1730               labelStr.startsWith("___neverused")   ) {
1731             continue;
1732           }
1733         }
1734
1735         bw.write(ln.toString() + ";\n");
1736
1737         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
1738         while( heapRegionsItr.hasNext() ) {
1739           ReferenceEdge edge = heapRegionsItr.next();
1740           HeapRegionNode hrn  = edge.getDst();
1741
1742           if( pruneGarbage && !visited.contains(hrn) ) {
1743             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
1744                                     hrn,
1745                                     bw,
1746                                     null,
1747                                     visited,
1748                                     writeReferencers);
1749           }
1750
1751           bw.write("  "        + ln.toString() +
1752                    " -> "      + hrn.toString() +
1753                    "[label=\"" + edge.toGraphEdgeString() +
1754                    "\",decorate];\n");
1755         }
1756       }
1757     }
1758
1759
1760     bw.write("}\n");
1761     bw.close();
1762   }
1763
1764   protected void traverseHeapRegionNodes(int mode,
1765                                          HeapRegionNode hrn,
1766                                          BufferedWriter bw,
1767                                          TempDescriptor td,
1768                                          HashSet<HeapRegionNode> visited,
1769                                          boolean writeReferencers
1770                                          ) throws java.io.IOException {
1771
1772     if( visited.contains(hrn) ) {
1773       return;
1774     }
1775     visited.add(hrn);
1776
1777     switch( mode ) {
1778     case VISIT_HRN_WRITE_FULL:
1779
1780       String attributes = "[";
1781
1782       if( hrn.isSingleObject() ) {
1783         attributes += "shape=box";
1784       } else {
1785         attributes += "shape=Msquare";
1786       }
1787
1788       if( hrn.isFlagged() ) {
1789         attributes += ",style=filled,fillcolor=lightgrey";
1790       }
1791
1792       attributes += ",label=\"ID"        +
1793                     hrn.getID()          +
1794                     "\\n"                +
1795                     hrn.getDescription() +
1796                     "\\n"                +
1797                     hrn.getAlphaString() +
1798                     "\"]";
1799
1800       bw.write("  " + hrn.toString() + attributes + ";\n");
1801       break;
1802     }
1803
1804
1805     // useful for debugging
1806     if( writeReferencers ) {
1807       OwnershipNode onRef  = null;
1808       Iterator refItr = hrn.iteratorToReferencers();
1809       while( refItr.hasNext() ) {
1810         onRef = (OwnershipNode) refItr.next();
1811
1812         switch( mode ) {
1813         case VISIT_HRN_WRITE_FULL:
1814           bw.write("  "                    + hrn.toString() +
1815                    " -> "                  + onRef.toString() +
1816                    "[color=lightgray];\n");
1817           break;
1818         }
1819       }
1820     }
1821
1822     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
1823     while( childRegionsItr.hasNext() ) {
1824       ReferenceEdge edge     = childRegionsItr.next();
1825       HeapRegionNode hrnChild = edge.getDst();
1826
1827       switch( mode ) {
1828       case VISIT_HRN_WRITE_FULL:
1829         bw.write("  "        + hrn.toString() +
1830                  " -> "      + hrnChild.toString() +
1831                  "[label=\"" + edge.toGraphEdgeString() +
1832                  "\",decorate];\n");
1833         break;
1834       }
1835
1836       traverseHeapRegionNodes(mode,
1837                               hrnChild,
1838                               bw,
1839                               td,
1840                               visited,
1841                               writeReferencers);
1842     }
1843   }
1844 }