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