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