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