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