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