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