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