Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8 public class OwnershipGraph {
   9
  10     private int allocationDepth;
  11
  12     // there was already one other very similar reason
  13     // for traversing heap nodes that is no longer needed
  14     // instead of writing a new heap region visitor, use
  15     // the existing method with a new mode to describe what
  16     // actions to take during the traversal
  17     protected static final int VISIT_HRN_WRITE_FULL = 0;
  18
  19
  20     public Hashtable<Integer,        HeapRegionNode> id2hrn;
  21     public Hashtable<TempDescriptor, LabelNode     > td2ln;
  22     public Hashtable<Integer,        Integer       > id2paramIndex;
  23     public Hashtable<Integer,        Integer       > paramIndex2id;
  24
  25     public HashSet<AllocationSite> allocationSites;
  26
  27
  28     public OwnershipGraph( int allocationDepth ) {
  29         this.allocationDepth = allocationDepth;
  30
  31         id2hrn        = new Hashtable<Integer,        HeapRegionNode>();
  32         td2ln         = new Hashtable<TempDescriptor, LabelNode     >();
  33         id2paramIndex = new Hashtable<Integer,        Integer       >();
  34         paramIndex2id = new Hashtable<Integer,        Integer       >();
  35
  36         allocationSites = new HashSet <AllocationSite>();
  37     }
  38
  39
  40     // label nodes are much easier to deal with than
  41     // heap region nodes.  Whenever there is a request
  42     // for the label node that is associated with a
  43     // temp descriptor we can either find it or make a
  44     // new one and return it.  This is because temp
  45     // descriptors are globally unique and every label
  46     // node is mapped to exactly one temp descriptor.
  47     protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) {
  48         assert td != null;
  49
  50         if( !td2ln.containsKey( td ) ) {
  51             td2ln.put( td, new LabelNode( td ) );
  52         }
  53
  54         return td2ln.get( td );
  55     }
  56
  57
  58     // the reason for this method is to have the option
  59     // creating new heap regions with specific IDs, or
  60     // duplicating heap regions with specific IDs (especially
  61     // in the merge() operation) or to create new heap
  62     // regions with a new unique ID.
  63     protected HeapRegionNode
  64         createNewHeapRegionNode( Integer         id,
  65                                  boolean         isSingleObject,
  66                                  boolean         isFlagged,
  67                                  boolean         isNewSummary,
  68                                  boolean         isParameter,
  69                                  AllocationSite  allocSite,
  70                                  ReachabilitySet alpha,
  71                                  String          description ) {
  72
  73         if( id == null ) {
  74             id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  75         }
  76
  77         if( alpha == null ) {
  78             if( isFlagged || isParameter ) {
  79                 alpha = new ReachabilitySet( new TokenTuple( id,
  80                                                              isNewSummary,
  81                                                              TokenTuple.ARITY_ONE ) );
  82             } else {
  83                 alpha = new ReachabilitySet();
  84             }
  85         }
  86
  87         HeapRegionNode hrn = new HeapRegionNode( id,
  88                                                  isSingleObject,
  89                                                  isFlagged,
  90                                                  isNewSummary,
  91                                                  allocSite,
  92                                                  alpha,
  93                                                  description );
  94         id2hrn.put( id, hrn );
  95         return hrn;
  96     }
  97
  98
  99
 100     ////////////////////////////////////////////////
 101     //
 102     //  Low-level referencee and referencer methods
 103     //
 104     //  These methods provide the lowest level for
 105     //  creating references between ownership nodes
 106     //  and handling the details of maintaining both
 107     //  list of referencers and referencees.
 108     //
 109     ////////////////////////////////////////////////
 110     protected void addReferenceEdge( OwnershipNode  referencer,
 111                                      HeapRegionNode referencee,
 112                                      ReferenceEdgeProperties rep ) {
 113         assert referencer != null;
 114         assert referencee != null;
 115         assert rep        != null;
 116         referencer.addReferencedRegion( referencee, rep );
 117         referencee.addReferencer( referencer );
 118         rep.setSrc( referencer );
 119         rep.setDst( referencee );
 120     }
 121
 122     protected void removeReferenceEdge( OwnershipNode  referencer,
 123                                         HeapRegionNode referencee ) {
 124         assert referencer != null;
 125         assert referencee != null;
 126         assert referencer.getReferenceTo( referencee ) != null;
 127         assert referencee.isReferencedBy( referencer );
 128
 129         referencer.removeReferencedRegion( referencee );
 130         referencee.removeReferencer( referencer );
 131     }
 132
 133     protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
 134         assert referencer != null;
 135
 136         // get a copy of the table to iterate over, otherwise
 137         // we will be trying to take apart the table as we
 138         // are iterating over it, which won't work
 139         Iterator i = referencer.setIteratorToReferencedRegionsClone();
 140         while( i.hasNext() ) {
 141             Map.Entry me = (Map.Entry) i.next();
 142             HeapRegionNode referencee = (HeapRegionNode) me.getKey();
 143             removeReferenceEdge( referencer, referencee );
 144         }
 145     }
 146
 147     protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
 148         assert referencee != null;
 149
 150         // get a copy of the table to iterate over, otherwise
 151         // we will be trying to take apart the table as we
 152         // are iterating over it, which won't work
 153         Iterator i = referencee.iteratorToReferencersClone();
 154         while( i.hasNext() ) {
 155             OwnershipNode referencer = (OwnershipNode) i.next();
 156             removeReferenceEdge( referencer, referencee );
 157         }
 158     }
 159
 160
 161     protected void propagateTokensOverNodes( HeapRegionNode                   nPrime,
 162                                              ChangeTupleSet                   c0,
 163                                              HashSet<HeapRegionNode>          nodesWithNewAlpha,
 164                                              HashSet<ReferenceEdgeProperties> edgesWithNewBeta ) {
 165
 166         HashSet<HeapRegionNode> todoNodes
 167             = new HashSet<HeapRegionNode>();
 168         todoNodes.add( nPrime );
 169
 170         HashSet<ReferenceEdgeProperties> todoEdges
 171             = new HashSet<ReferenceEdgeProperties>();
 172
 173         Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 174             = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 175         nodePlannedChanges.put( nPrime, c0 );
 176
 177         Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges
 178             = new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
 179
 180
 181         while( !todoNodes.isEmpty() ) {
 182             HeapRegionNode n = todoNodes.iterator().next();
 183             ChangeTupleSet C = nodePlannedChanges.get( n );
 184
 185             Iterator itrC = C.iterator();
 186             while( itrC.hasNext() ) {
 187                 ChangeTuple c = (ChangeTuple) itrC.next();
 188
 189                 if( n.getAlpha().contains( c.getSetToMatch() ) ) {
 190                     ReachabilitySet withChange = n.getAlpha().union( c.getSetToAdd() );
 191                     n.setAlphaNew( n.getAlphaNew().union( withChange ) );
 192                     nodesWithNewAlpha.add( n );
 193                 }
 194             }
 195
 196             Iterator referItr = n.iteratorToReferencers();
 197             while( referItr.hasNext() ) {
 198                 OwnershipNode           on  = (OwnershipNode) referItr.next();
 199                 ReferenceEdgeProperties rep = on.getReferenceTo( n );
 200                 todoEdges.add( rep );
 201
 202                 if( !edgePlannedChanges.containsKey( rep ) ) {
 203                     edgePlannedChanges.put( rep, new ChangeTupleSet().makeCanonical() );
 204                 }
 205
 206                 edgePlannedChanges.put( rep, edgePlannedChanges.get( rep ).union( C ) );
 207             }
 208
 209             HeapRegionNode          m = null;
 210             ReferenceEdgeProperties f = null;
 211             Iterator refeeItr = n.setIteratorToReferencedRegions();
 212             while( refeeItr.hasNext() ) {
 213                 Map.Entry me = (Map.Entry)               refeeItr.next();
 214                 m            = (HeapRegionNode)          me.getKey();
 215                 f            = (ReferenceEdgeProperties) me.getValue();
 216
 217                 ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 218
 219                 Iterator itrCprime = C.iterator();
 220                 while( itrCprime.hasNext() ) {
 221                     ChangeTuple c = (ChangeTuple) itrCprime.next();
 222                     if( f.getBeta().contains( c.getSetToMatch() ) ) {
 223                         changesToPass = changesToPass.union( c );
 224                     }
 225                 }
 226
 227                 if( !changesToPass.isEmpty() ) {
 228                     if( !nodePlannedChanges.containsKey( m ) ) {
 229                         nodePlannedChanges.put( m, new ChangeTupleSet().makeCanonical() );
 230                     }
 231
 232                     ChangeTupleSet currentChanges = nodePlannedChanges.get( m );
 233
 234                     if( !changesToPass.isSubset( currentChanges ) ) {
 235
 236                         nodePlannedChanges.put( m, currentChanges.union( changesToPass ) );
 237                         todoNodes.add( m );
 238                     }
 239                 }
 240             }
 241
 242             todoNodes.remove( n );
 243         }
 244
 245         propagateTokensOverEdges( todoEdges, edgePlannedChanges, nodesWithNewAlpha, edgesWithNewBeta );
 246     }
 247
 248
 249     protected void propagateTokensOverEdges(
 250          HashSet<ReferenceEdgeProperties>                   todoEdges,
 251          Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges,
 252          HashSet<HeapRegionNode>                            nodesWithNewAlpha,
 253          HashSet<ReferenceEdgeProperties>                   edgesWithNewBeta ) {
 254
 255
 256         while( !todoEdges.isEmpty() ) {
 257             ReferenceEdgeProperties e = todoEdges.iterator().next();
 258             todoEdges.remove( e );
 259
 260             if( !edgePlannedChanges.containsKey( e ) ) {
 261                 edgePlannedChanges.put( e, new ChangeTupleSet().makeCanonical() );
 262             }
 263
 264             ChangeTupleSet C = edgePlannedChanges.get( e );
 265
 266             ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 267
 268             Iterator itrC = C.iterator();
 269             while( itrC.hasNext() ) {
 270                 ChangeTuple c = (ChangeTuple) itrC.next();
 271                 if( e.getBeta().contains( c.getSetToMatch() ) ) {
 272                     ReachabilitySet withChange = e.getBeta().union( c.getSetToAdd() );
 273                     e.setBetaNew( e.getBetaNew().union( withChange ) );
 274                     edgesWithNewBeta.add( e );
 275                     changesToPass = changesToPass.union( c );
 276                 }
 277             }
 278
 279             OwnershipNode onSrc = e.getSrc();
 280
 281             if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 282                 HeapRegionNode n = (HeapRegionNode) onSrc;
 283                 Iterator referItr = n.iteratorToReferencers();
 284
 285                 while( referItr.hasNext() ) {
 286                     OwnershipNode onRef = (OwnershipNode) referItr.next();
 287                     ReferenceEdgeProperties f = onRef.getReferenceTo( n );
 288
 289                     if( !edgePlannedChanges.containsKey( f ) ) {
 290                         edgePlannedChanges.put( f, new ChangeTupleSet().makeCanonical() );
 291                     }
 292
 293                     ChangeTupleSet currentChanges = edgePlannedChanges.get( f );
 294
 295                     if( !changesToPass.isSubset( currentChanges ) ) {
 296                         todoEdges.add( f );
 297                         edgePlannedChanges.put( f, currentChanges.union( changesToPass ) );
 298                     }
 299                 }
 300             }
 301         }
 302     }
 303
 304
 305     ////////////////////////////////////////////////////
 306     //
 307     //  Assignment Operation Methods
 308     //
 309     //  These methods are high-level operations for
 310     //  modeling program assignment statements using
 311     //  the low-level reference create/remove methods
 312     //  above.
 313     //
 314     //  The destination in an assignment statement is
 315     //  going to have new references.  The method of
 316     //  determining the references depends on the type
 317     //  of the FlatNode assignment and the predicates
 318     //  of the nodes and edges involved.
 319     //
 320     ////////////////////////////////////////////////////
 321     public void assignTempToTemp( TempDescriptor src,
 322                                   TempDescriptor dst ) {
 323         LabelNode srcln = getLabelNodeFromTemp( src );
 324         LabelNode dstln = getLabelNodeFromTemp( dst );
 325
 326         clearReferenceEdgesFrom( dstln );
 327
 328         HeapRegionNode newReferencee = null;
 329         Iterator       srcRegionsItr = srcln.setIteratorToReferencedRegions();
 330         while( srcRegionsItr.hasNext() ) {
 331             Map.Entry me                = (Map.Entry)               srcRegionsItr.next();
 332             newReferencee               = (HeapRegionNode)          me.getKey();
 333             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 334
 335             addReferenceEdge( dstln, newReferencee, rep.copy() );
 336         }
 337     }
 338
 339     public void assignTempToField( TempDescriptor  src,
 340                                    TempDescriptor  dst,
 341                                    FieldDescriptor fd ) {
 342         LabelNode srcln = getLabelNodeFromTemp( src );
 343         LabelNode dstln = getLabelNodeFromTemp( dst );
 344
 345         clearReferenceEdgesFrom( dstln );
 346
 347         HeapRegionNode hrn           = null;
 348         Iterator       srcRegionsItr = srcln.setIteratorToReferencedRegions();
 349         while( srcRegionsItr.hasNext() ) {
 350             Map.Entry me                 = (Map.Entry)               srcRegionsItr.next();
 351             hrn                          = (HeapRegionNode)          me.getKey();
 352             ReferenceEdgeProperties rep1 = (ReferenceEdgeProperties) me.getValue();
 353             ReachabilitySet beta1        = rep1.getBeta();
 354
 355             HeapRegionNode hrnOneHop = null;
 356             Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
 357             while( hrnRegionsItr.hasNext() ) {
 358                 Map.Entry meH                = (Map.Entry)               hrnRegionsItr.next();
 359                 hrnOneHop                    = (HeapRegionNode)          meH.getKey();
 360                 ReferenceEdgeProperties rep2 = (ReferenceEdgeProperties) meH.getValue();
 361                 ReachabilitySet beta2        = rep2.getBeta();
 362
 363                 ReferenceEdgeProperties rep =
 364                     new ReferenceEdgeProperties( null,
 365                                                  false,
 366                                                  beta1.intersection( beta2 ) );
 367
 368                 addReferenceEdge( dstln, hrnOneHop, rep );
 369             }
 370         }
 371     }
 372
 373     public void assignFieldToTemp( TempDescriptor  src,
 374                                    TempDescriptor  dst,
 375                                    FieldDescriptor fd ) {
 376
 377         // I think my use of src and dst are actually backwards in this method!
 378         // acccording to the Reachability Notes, think of dst at N and src as N prime
 379
 380         LabelNode srcln = getLabelNodeFromTemp( src );
 381         LabelNode dstln = getLabelNodeFromTemp( dst );
 382
 383         HashSet<HeapRegionNode>          nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 384         HashSet<ReferenceEdgeProperties> edgesWithNewBeta  = new HashSet<ReferenceEdgeProperties>();
 385
 386         HeapRegionNode          hrn = null;
 387         ReferenceEdgeProperties rep = null;
 388         Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
 389         while( dstRegionsItr.hasNext() ) {
 390             Map.Entry me = (Map.Entry)               dstRegionsItr.next();
 391             hrn          = (HeapRegionNode)          me.getKey();
 392             rep          = (ReferenceEdgeProperties) me.getValue();
 393
 394             ReachabilitySet R = hrn.getAlpha().intersection( rep.getBeta() );
 395
 396             HeapRegionNode          hrnSrc = null;
 397             ReferenceEdgeProperties repSrc = null;
 398             Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
 399             while( srcRegionsItr.hasNext() ) {
 400                 Map.Entry meS = (Map.Entry)               srcRegionsItr.next();
 401                 hrnSrc        = (HeapRegionNode)          meS.getKey();
 402                 repSrc        = (ReferenceEdgeProperties) meS.getValue();
 403
 404                 ReachabilitySet O = srcln.getReferenceTo( hrnSrc ).getBeta();
 405
 406
 407                 // propagate tokens over nodes starting from hrnSrc, and it will
 408                 // take care of propagating back up edges from any touched nodes
 409                 ChangeTupleSet Cy = O.unionUpArityToChangeSet( R );
 410                 propagateTokensOverNodes( hrnSrc, Cy, nodesWithNewAlpha, edgesWithNewBeta );
 411
 412
 413                 // then propagate back just up the edges from hrn
 414                 ChangeTupleSet Cx = R.unionUpArityToChangeSet( O );
 415
 416                 HashSet<ReferenceEdgeProperties> todoEdges =
 417                     new HashSet<ReferenceEdgeProperties>();
 418
 419                 Hashtable<ReferenceEdgeProperties, ChangeTupleSet> edgePlannedChanges =
 420                     new Hashtable<ReferenceEdgeProperties, ChangeTupleSet>();
 421
 422                 Iterator referItr = hrn.iteratorToReferencers();
 423                 while( referItr.hasNext() ) {
 424                     OwnershipNode onRef = (OwnershipNode) referItr.next();
 425                     ReferenceEdgeProperties repUpstream = onRef.getReferenceTo( hrn );
 426
 427                     todoEdges.add( repUpstream );
 428                     edgePlannedChanges.put( repUpstream, Cx );
 429                 }
 430
 431                 propagateTokensOverEdges( todoEdges,
 432                                           edgePlannedChanges,
 433                                           nodesWithNewAlpha,
 434                                           edgesWithNewBeta );
 435
 436                 // finally, create the actual reference edge hrn->hrnSrc
 437                 ReferenceEdgeProperties repNew
 438                     = new ReferenceEdgeProperties( fd,
 439                                                    false,
 440                                                    repSrc.getBetaNew().pruneBy( hrn.getAlpha() )
 441                                                  );
 442
 443                 addReferenceEdge( hrn, hrnSrc, repNew );
 444             }
 445         }
 446
 447         Iterator nodeItr = nodesWithNewAlpha.iterator();
 448         while( nodeItr.hasNext() ) {
 449             ((HeapRegionNode) nodeItr.next()).applyAlphaNew();
 450         }
 451
 452         Iterator edgeItr = edgesWithNewBeta.iterator();
 453         while( edgeItr.hasNext() ) {
 454             ((ReferenceEdgeProperties) edgeItr.next()).applyBetaNew();
 455         }
 456     }
 457
 458     public void assignTempToParameterAllocation( boolean        isTask,
 459                                                  TempDescriptor td,
 460                                                  Integer        paramIndex ) {
 461         assert td != null;
 462
 463         LabelNode      lnParam = getLabelNodeFromTemp( td );
 464         HeapRegionNode hrn     = createNewHeapRegionNode( null,
 465                                                           false,
 466                                                           isTask,
 467                                                           false,
 468                                                           true,
 469                                                           null,
 470                                                           null,
 471                                                           "param" + paramIndex );
 472
 473         // keep track of heap regions that were created for
 474         // parameter labels, the index of the parameter they
 475         // are for is important when resolving method calls
 476         Integer newID = hrn.getID();
 477         assert !id2paramIndex.containsKey  ( newID );
 478         assert !id2paramIndex.containsValue( paramIndex );
 479         id2paramIndex.put( newID, paramIndex );
 480         paramIndex2id.put( paramIndex, newID );
 481
 482         ReachabilitySet beta = new ReachabilitySet( new TokenTuple( newID,
 483                                                                     false,
 484                                                                     TokenTuple.ARITY_ONE ) );
 485
 486         // heap regions for parameters are always multiple object (see above)
 487         // and have a reference to themselves, because we can't know the
 488         // structure of memory that is passed into the method.  We're assuming
 489         // the worst here.
 490         addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( null, false, beta ) );
 491         addReferenceEdge( hrn,     hrn, new ReferenceEdgeProperties( null, true,  beta ) );
 492     }
 493
 494     public void assignTempToNewAllocation( TempDescriptor td,
 495                                            AllocationSite as ) {
 496         assert td != null;
 497         assert as != null;
 498
 499         age( as );
 500
 501
 502         // after the age operation the newest (or zero-ith oldest)
 503         // node associated with the allocation site should have
 504         // no references to it as if it were a newly allocated
 505         // heap region, so make a reference to it to complete
 506         // this operation
 507         Integer        idNewest  = as.getIthOldest( 0 );
 508         HeapRegionNode hrnNewest = id2hrn.get( idNewest );
 509         assert hrnNewest != null;
 510
 511         LabelNode dst = getLabelNodeFromTemp( td );
 512
 513         clearReferenceEdgesFrom( dst );
 514
 515         addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( null, false, hrnNewest.getAlpha() ) );
 516     }
 517
 518
 519     // use the allocation site (unique to entire analysis) to
 520     // locate the heap region nodes in this ownership graph
 521     // that should be aged.  The process models the allocation
 522     // of new objects and collects all the oldest allocations
 523     // in a summary node to allow for a finite analysis
 524     //
 525     // There is an additional property of this method.  After
 526     // running it on a particular ownership graph (many graphs
 527     // may have heap regions related to the same allocation site)
 528     // the heap region node objects in this ownership graph will be
 529     // allocated.  Therefore, after aging a graph for an allocation
 530     // site, attempts to retrieve the heap region nodes using the
 531     // integer id's contained in the allocation site should always
 532     // return non-null heap regions.
 533     public void age( AllocationSite as ) {
 534
 535         // aging adds this allocation site to the graph's
 536         // list of sites that exist in the graph, or does
 537         // nothing if the site is already in the list
 538         allocationSites.add( as );
 539
 540         // get the summary node for the allocation site in the context
 541         // of this particular ownership graph
 542         HeapRegionNode hrnSummary = getSummaryNode( as );
 543
 544         // merge oldest node into summary
 545         Integer        idK  = as.getOldest();
 546         HeapRegionNode hrnK = id2hrn.get( idK );
 547         mergeIntoSummary( hrnK, hrnSummary );
 548
 549         // move down the line of heap region nodes
 550         // clobbering the ith and transferring all references
 551         // to and from i-1 to node i.  Note that this clobbers
 552         // the oldest node (hrnK) that was just merged into
 553         // the summary
 554         for( int i = allocationDepth - 1; i > 0; --i ) {
 555
 556             // move references from the i-1 oldest to the ith oldest
 557             Integer        idIth     = as.getIthOldest( i );
 558             HeapRegionNode hrnI      = id2hrn.get( idIth );
 559             Integer        idImin1th = as.getIthOldest( i - 1 );
 560             HeapRegionNode hrnImin1  = id2hrn.get( idImin1th );
 561
 562             transferOnto( hrnImin1, hrnI );
 563         }
 564
 565         // as stated above, the newest node should have had its
 566         // references moved over to the second oldest, so we wipe newest
 567         // in preparation for being the new object to assign something to
 568         Integer        id0th = as.getIthOldest( 0 );
 569         HeapRegionNode hrn0  = id2hrn.get( id0th );
 570         assert hrn0 != null;
 571
 572         // clear all references in and out of newest node
 573         clearReferenceEdgesFrom( hrn0 );
 574         clearReferenceEdgesTo  ( hrn0 );
 575
 576
 577         // now tokens in reachability sets need to "age" also
 578         ReferenceEdgeProperties repToAge = null;
 579         Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 580         while( itrAllLabelNodes.hasNext() ) {
 581             Map.Entry me = (Map.Entry) itrAllLabelNodes.next();
 582             LabelNode ln = (LabelNode) me.getValue();
 583
 584             Iterator itrEdges = ln.setIteratorToReferencedRegions();
 585             while( itrEdges.hasNext() ) {
 586                 Map.Entry meE = (Map.Entry)               itrEdges.next();
 587                 repToAge      = (ReferenceEdgeProperties) meE.getValue();
 588
 589                 ageTokens( as, repToAge );
 590             }
 591         }
 592         HeapRegionNode hrnToAge = null;
 593         Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 594         while( itrAllHRNodes.hasNext() ) {
 595             Map.Entry me = (Map.Entry)               itrAllHRNodes.next();
 596             hrnToAge     = (HeapRegionNode)          me.getValue();
 597
 598             ageTokens( as, hrnToAge );
 599
 600             Iterator itrEdges = hrnToAge.setIteratorToReferencedRegions();
 601             while( itrEdges.hasNext() ) {
 602                 Map.Entry meE = (Map.Entry)               itrEdges.next();
 603                 repToAge      = (ReferenceEdgeProperties) meE.getValue();
 604
 605                 ageTokens( as, repToAge );
 606             }
 607         }
 608
 609
 610         // after tokens have been aged, reset newest node's reachability
 611         hrn0.setAlpha( new ReachabilitySet(
 612                            new TokenTupleSet(
 613                                new TokenTuple( hrn0 )
 614                                             )
 615                                           ).makeCanonical()
 616                        );
 617     }
 618
 619
 620     protected HeapRegionNode getSummaryNode( AllocationSite as ) {
 621
 622         Integer        idSummary  = as.getSummary();
 623         HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 624
 625         // If this is null then we haven't touched this allocation site
 626         // in the context of the current ownership graph, so allocate
 627         // heap region nodes appropriate for the entire allocation site.
 628         // This should only happen once per ownership graph per allocation site,
 629         // and a particular integer id can be used to locate the heap region
 630         // in different ownership graphs that represents the same part of an
 631         // allocation site.
 632         if( hrnSummary == null ) {
 633
 634             boolean hasFlags = false;
 635             if( as.getType().isClass() ) {
 636                 hasFlags = as.getType().getClassDesc().hasFlags();
 637             }
 638
 639             hrnSummary = createNewHeapRegionNode( idSummary,
 640                                                   false,
 641                                                   hasFlags,
 642                                                   true,
 643                                                   false,
 644                                                   as,
 645                                                   null,
 646                                                   as + "\\n" + as.getType() + "\\nsummary" );
 647
 648             for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 649                 Integer idIth = as.getIthOldest( i );
 650                 assert !id2hrn.containsKey( idIth );
 651                 createNewHeapRegionNode( idIth,
 652                                          true,
 653                                          hasFlags,
 654                                          false,
 655                                          false,
 656                                          as,
 657                                          null,
 658                                          as + "\\n" + as.getType() + "\\n" + i + " oldest" );
 659             }
 660         }
 661
 662         return hrnSummary;
 663     }
 664
 665
 666     protected HeapRegionNode getShadowSummaryNode( AllocationSite as ) {
 667
 668         Integer        idShadowSummary  = -(as.getSummary());
 669         HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
 670
 671         if( hrnShadowSummary == null ) {
 672
 673             boolean hasFlags = false;
 674             if( as.getType().isClass() ) {
 675                 hasFlags = as.getType().getClassDesc().hasFlags();
 676             }
 677
 678             hrnShadowSummary = createNewHeapRegionNode( idShadowSummary,
 679                                                         false,
 680                                                         hasFlags,
 681                                                         true,
 682                                                         false,
 683                                                         as,
 684                                                         null,
 685                                                         as + "\\n" + as.getType() + "\\nshadowSum" );
 686
 687             for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 688                 Integer idShadowIth = -(as.getIthOldest( i ));
 689                 assert !id2hrn.containsKey( idShadowIth );
 690                 createNewHeapRegionNode( idShadowIth,
 691                                          true,
 692                                          hasFlags,
 693                                          false,
 694                                          false,
 695                                          as,
 696                                          null,
 697                                          as + "\\n" + as.getType() + "\\n" + i + " shadow" );
 698             }
 699         }
 700
 701         return hrnShadowSummary;
 702     }
 703
 704
 705     protected void mergeIntoSummary( HeapRegionNode hrn, HeapRegionNode hrnSummary ) {
 706         assert hrnSummary.isNewSummary();
 707
 708         // transfer references _from_ hrn over to hrnSummary
 709         HeapRegionNode hrnReferencee = null;
 710         Iterator       itrReferencee = hrn.setIteratorToReferencedRegions();
 711         while( itrReferencee.hasNext() ) {
 712             Map.Entry               me  = (Map.Entry)               itrReferencee.next();
 713             hrnReferencee               = (HeapRegionNode)          me.getKey();
 714             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 715
 716             ReferenceEdgeProperties repSummary = hrnSummary.getReferenceTo( hrnReferencee );
 717             ReferenceEdgeProperties repMerged = rep.copy();
 718
 719             if( repSummary == null ) {
 720                 // the merge is trivial, nothing to be done
 721             } else {
 722                 // otherwise an edge from the referencer to hrnSummary exists already
 723                 // and the edge referencer->hrn should be merged with it
 724                 repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
 725             }
 726
 727             addReferenceEdge( hrnSummary, hrnReferencee, repMerged );
 728         }
 729
 730         // next transfer references _to_ hrn over to hrnSummary
 731         OwnershipNode onReferencer  = null;
 732         Iterator      itrReferencer = hrn.iteratorToReferencers();
 733         while( itrReferencer.hasNext() ) {
 734             onReferencer = (OwnershipNode) itrReferencer.next();
 735
 736             ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrn );
 737             assert rep != null;
 738             ReferenceEdgeProperties repSummary = onReferencer.getReferenceTo( hrnSummary );
 739             ReferenceEdgeProperties repMerged = rep.copy();
 740
 741             if( repSummary == null ) {
 742                 // the merge is trivial, nothing to be done
 743             } else {
 744                 // otherwise an edge from the referencer to alpha_S exists already
 745                 // and the edge referencer->alpha_K should be merged with it
 746                 repMerged.setBeta( repMerged.getBeta().union( repSummary.getBeta() ) );
 747             }
 748
 749             addReferenceEdge( onReferencer, hrnSummary, repMerged );
 750         }
 751
 752         // then merge hrn reachability into hrnSummary
 753         hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrn.getAlpha() ) );
 754     }
 755
 756
 757     protected void transferOnto( HeapRegionNode hrnA, HeapRegionNode hrnB ) {
 758
 759         // clear references in and out of node i
 760         clearReferenceEdgesFrom( hrnB );
 761         clearReferenceEdgesTo  ( hrnB );
 762
 763         // copy each edge in and out of A to B
 764         HeapRegionNode hrnReferencee = null;
 765         Iterator       itrReferencee = hrnA.setIteratorToReferencedRegions();
 766         while( itrReferencee.hasNext() ) {
 767             Map.Entry               me  = (Map.Entry)               itrReferencee.next();
 768             hrnReferencee               = (HeapRegionNode)          me.getKey();
 769             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 770
 771             addReferenceEdge( hrnB, hrnReferencee, rep.copy() );
 772         }
 773
 774         OwnershipNode onReferencer  = null;
 775         Iterator      itrReferencer = hrnA.iteratorToReferencers();
 776         while( itrReferencer.hasNext() ) {
 777             onReferencer = (OwnershipNode) itrReferencer.next();
 778
 779             ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnA );
 780             assert rep != null;
 781
 782             addReferenceEdge( onReferencer, hrnB, rep.copy() );
 783         }
 784
 785         // replace hrnB reachability with hrnA's
 786         hrnB.setAlpha( hrnA.getAlpha() );
 787     }
 788
 789
 790     protected void ageTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
 791         rep.setBeta( rep.getBeta().ageTokens( as ) );
 792     }
 793
 794     protected void ageTokens( AllocationSite as, HeapRegionNode hrn ) {
 795         hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
 796     }
 797
 798     protected void majorAgeTokens( AllocationSite as, ReferenceEdgeProperties rep ) {
 799         //rep.setBeta( rep.getBeta().majorAgeTokens( as ) );
 800     }
 801
 802     protected void majorAgeTokens( AllocationSite as, HeapRegionNode hrn ) {
 803         //hrn.setAlpha( hrn.getAlpha().majorAgeTokens( as ) );
 804     }
 805
 806
 807     // some notes:
 808     // the heap regions that are specially allocated as multiple-object
 809     // regions for method parameters need to be remembered in order to
 810     // resolve a function call.  So actually, we need a mapping from
 811     // caller argument descriptors to the callee parameter heap regions
 812     // to apply reference edges in the callee to the caller graph.
 813     //
 814     // also, Constructors and virtual dispatch methods have a "this"
 815     // argument that make the mapping of arguments to parameters a little
 816     // tricky.  What happens to that this region?
 817
 818
 819     public void resolveMethodCall( FlatCall                fc,
 820                                    boolean                 isStatic,
 821                                    FlatMethod              fm,
 822                                    OwnershipGraph          ogCallee ) {
 823
 824         // verify the existence of allocation sites and their
 825         // shadows from the callee in the context of this caller graph
 826         Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
 827         while( asItr.hasNext() ) {
 828             AllocationSite allocSite        = asItr.next();
 829             HeapRegionNode hrnSummary       = getSummaryNode      ( allocSite );
 830             HeapRegionNode hrnShadowSummary = getShadowSummaryNode( allocSite );
 831         }
 832
 833         // in non-static methods there is a "this" pointer
 834         // that should be taken into account
 835         if( isStatic ) {
 836             assert fc.numArgs()     == fm.numParameters();
 837         } else {
 838             assert fc.numArgs() + 1 == fm.numParameters();
 839         }
 840
 841         // make a change set to translate callee tokens into caller tokens
 842         ChangeTupleSet C = new ChangeTupleSet().makeCanonical();
 843
 844         for( int i = 0; i < fm.numParameters(); ++i ) {
 845
 846             Integer indexParam = new Integer( i );
 847
 848             System.out.println( "In method "+fm+ " on param "+indexParam );
 849
 850             assert ogCallee.paramIndex2id.containsKey( indexParam );
 851             Integer idParam = ogCallee.paramIndex2id.get( indexParam );
 852
 853             assert ogCallee.id2hrn.containsKey( idParam );
 854             HeapRegionNode hrnParam = ogCallee.id2hrn.get( idParam );
 855             assert hrnParam != null;
 856
 857             TokenTupleSet calleeTokenToMatch =
 858                 new TokenTupleSet( new TokenTuple( hrnParam ) ).makeCanonical();
 859
 860
 861             // now depending on whether the callee is static or not
 862             // we need to account for a "this" argument in order to
 863             // find the matching argument in the caller context
 864             TempDescriptor argTemp;
 865             if( isStatic ) {
 866                 argTemp = fc.getArg( indexParam );
 867             } else {
 868                 if( indexParam == 0 ) {
 869                     argTemp = fc.getThis();
 870                 } else {
 871                     argTemp = fc.getArg( indexParam - 1 );
 872                 }
 873             }
 874
 875             LabelNode argLabel = getLabelNodeFromTemp( argTemp );
 876             Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
 877             while( argHeapRegionsItr.hasNext() ) {
 878                 Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
 879                 HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
 880                 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
 881
 882                 Iterator<TokenTupleSet> ttsItr = repArg.getBeta().iterator();
 883                 while( ttsItr.hasNext() ) {
 884                     TokenTupleSet callerTokensToReplace = ttsItr.next();
 885
 886                     ChangeTuple ct = new ChangeTuple( calleeTokenToMatch,
 887                                                       callerTokensToReplace ).makeCanonical();
 888
 889                     C = C.union( ct );
 890                 }
 891             }
 892         }
 893
 894         System.out.println( "Applying method call "+fm );
 895         System.out.println( "  Change: "+C );
 896
 897
 898         // the heap regions represented by the arguments (caller graph)
 899         // and heap regions for the parameters (callee graph)
 900         // don't correspond to each other by heap region ID.  In fact,
 901         // an argument label node can be referencing several heap regions
 902         // so the parameter label always references a multiple-object
 903         // heap region in order to handle the range of possible contexts
 904         // for a method call.  This means we need to make a special mapping
 905         // of argument->parameter regions in order to update the caller graph
 906
 907         // for every heap region->heap region edge in the
 908         // callee graph, create the matching edge or edges
 909         // in the caller graph
 910         Set      sCallee = ogCallee.id2hrn.entrySet();
 911         Iterator iCallee = sCallee.iterator();
 912         while( iCallee.hasNext() ) {
 913             Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
 914             Integer        idCallee  = (Integer)        meCallee.getKey();
 915             HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
 916
 917             HeapRegionNode hrnChildCallee = null;
 918             Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
 919             while( heapRegionsItrCallee.hasNext() ) {
 920                 Map.Entry me                 = (Map.Entry)               heapRegionsItrCallee.next();
 921                 hrnChildCallee               = (HeapRegionNode)          me.getKey();
 922                 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
 923
 924                 Integer idChildCallee = hrnChildCallee.getID();
 925
 926                 // only address this edge if it is not a special reflexive edge
 927                 if( !repC.isInitialParamReflexive() ) {
 928
 929                     // now we know that in the callee method's ownership graph
 930                     // there is a heap region->heap region reference edge given
 931                     // by heap region pointers:
 932                     // hrnCallee -> heapChildCallee
 933                     //
 934                     // or by the ownership-graph independent ID's:
 935                     // idCallee -> idChildCallee
 936                     //
 937                     // So now make a set of possible source heaps in the caller graph
 938                     // and a set of destination heaps in the caller graph, and make
 939                     // a reference edge in the caller for every possible (src,dst) pair
 940                     if( !ogCallee.id2hrn.contains( idChildCallee ) ) {
 941                         System.out.println( "Houston, we got a problem." );
 942                         System.out.println( "idCallee is "+idCallee );
 943                         System.out.println( "idChildCallee is "+idChildCallee );
 944
 945                         try {
 946                             writeGraph         ( "caller", false, false, false, false );
 947                             ogCallee.writeGraph( "callee", false, false, false, false );
 948                         } catch( IOException e ) {}
 949                     }
 950
 951                     HashSet<HeapRegionNode> possibleCallerSrcs =
 952                         getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 953                                                              idCallee,
 954                                                              fc,
 955                                                              isStatic );
 956
 957                     HashSet<HeapRegionNode> possibleCallerDsts =
 958                         getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 959                                                              idChildCallee,
 960                                                              fc,
 961                                                              isStatic );
 962
 963                     // make every possible pair of {srcSet} -> {dstSet} edges in the caller
 964                     Iterator srcItr = possibleCallerSrcs.iterator();
 965                     while( srcItr.hasNext() ) {
 966                         HeapRegionNode src = (HeapRegionNode) srcItr.next();
 967
 968                         Iterator dstItr = possibleCallerDsts.iterator();
 969                         while( dstItr.hasNext() ) {
 970                             HeapRegionNode dst = (HeapRegionNode) dstItr.next();
 971
 972                             addReferenceEdge( src, dst, repC.copy() );
 973                         }
 974                     }
 975                 }
 976             }
 977         }
 978     }
 979
 980
 981     private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
 982                                                                          Integer        idCallee,
 983                                                                          FlatCall       fc,
 984                                                                          boolean        isStatic ) {
 985
 986         HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
 987
 988         if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
 989             // the heap region that is part of this
 990             // reference edge won't have a matching ID in the
 991             // caller graph because it is specifically allocated
 992             // for a particular parameter.  Use that information
 993             // to find the corresponding argument label in the
 994             // caller in order to create the proper reference edge
 995             // or edges.
 996             assert !id2hrn.containsKey( idCallee );
 997
 998             Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
 999             TempDescriptor argTemp;
1000
1001             // now depending on whether the callee is static or not
1002             // we need to account for a "this" argument in order to
1003             // find the matching argument in the caller context
1004             if( isStatic ) {
1005                 argTemp = fc.getArg( paramIndex );
1006             } else {
1007                 if( paramIndex == 0 ) {
1008                     argTemp = fc.getThis();
1009                 } else {
1010                     argTemp = fc.getArg( paramIndex - 1 );
1011                 }
1012             }
1013
1014             LabelNode argLabel = getLabelNodeFromTemp( argTemp );
1015             Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
1016             while( argHeapRegionsItr.hasNext() ) {
1017                 Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
1018                 HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
1019                 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
1020
1021                 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
1022             }
1023
1024         } else {
1025             // this heap region is not a parameter, so it should
1026             // have a matching heap region in the caller graph
1027             assert id2hrn.containsKey( idCallee );
1028             possibleCallerHRNs.add( id2hrn.get( idCallee ) );
1029         }
1030
1031         return possibleCallerHRNs;
1032     }
1033
1034
1035
1036     ////////////////////////////////////////////////////
1037     // in merge() and equals() methods the suffix A
1038     // represents the passed in graph and the suffix
1039     // B refers to the graph in this object
1040     // Merging means to take the incoming graph A and
1041     // merge it into B, so after the operation graph B
1042     // is the final result.
1043     ////////////////////////////////////////////////////
1044     public void merge( OwnershipGraph og ) {
1045
1046         if( og == null ) {
1047           return;
1048         }
1049
1050         mergeOwnershipNodes ( og );
1051         mergeReferenceEdges ( og );
1052         mergeId2paramIndex  ( og );
1053         mergeAllocationSites( og );
1054     }
1055
1056
1057     protected void mergeOwnershipNodes( OwnershipGraph og ) {
1058         Set      sA = og.id2hrn.entrySet();
1059         Iterator iA = sA.iterator();
1060         while( iA.hasNext() ) {
1061             Map.Entry      meA  = (Map.Entry)      iA.next();
1062             Integer        idA  = (Integer)        meA.getKey();
1063             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1064
1065             // if this graph doesn't have a node the
1066             // incoming graph has, allocate it
1067             if( !id2hrn.containsKey( idA ) ) {
1068                 HeapRegionNode hrnB = hrnA.copy();
1069                 id2hrn.put( idA, hrnB );
1070
1071             } else {
1072                 // otherwise this is a node present in both graphs
1073                 // so make the new reachability set a union of the
1074                 // nodes' reachability sets
1075                 HeapRegionNode hrnB = id2hrn.get( idA );
1076                 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
1077             }
1078         }
1079
1080         // now add any label nodes that are in graph B but
1081         // not in A
1082         sA = og.td2ln.entrySet();
1083         iA = sA.iterator();
1084         while( iA.hasNext() ) {
1085             Map.Entry      meA = (Map.Entry)      iA.next();
1086             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1087             LabelNode      lnA = (LabelNode)      meA.getValue();
1088
1089             // if the label doesn't exist in B, allocate and add it
1090             LabelNode lnB = getLabelNodeFromTemp( tdA );
1091         }
1092     }
1093
1094     protected void mergeReferenceEdges( OwnershipGraph og ) {
1095         // there is a data structure for storing label nodes
1096         // retireved by temp descriptors, and a data structure
1097         // for stroing heap region nodes retrieved by integer
1098         // ids.  Because finding edges requires interacting
1099         // with these disparate data structures frequently the
1100         // process is nearly duplicated, one for each structure
1101         // that stores edges
1102
1103         // heap regions
1104         Set      sA = og.id2hrn.entrySet();
1105         Iterator iA = sA.iterator();
1106         while( iA.hasNext() ) {
1107             Map.Entry      meA  = (Map.Entry)      iA.next();
1108             Integer        idA  = (Integer)        meA.getKey();
1109             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1110
1111             HeapRegionNode hrnChildA = null;
1112             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1113             while( heapRegionsItrA.hasNext() ) {
1114                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1115                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1116                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1117
1118                 Integer idChildA = hrnChildA.getID();
1119
1120                 // at this point we know an edge in graph A exists
1121                 // idA -> idChildA, does this exist in B?
1122                 boolean edgeFound = false;
1123                 assert id2hrn.containsKey( idA );
1124                 HeapRegionNode hrnB = id2hrn.get( idA );
1125
1126                 HeapRegionNode          hrnChildB = null;
1127                 ReferenceEdgeProperties repB      = null;
1128                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1129                 while( heapRegionsItrB.hasNext() ) {
1130                     Map.Entry meC               = (Map.Entry)               heapRegionsItrB.next();
1131                     hrnChildB                   = (HeapRegionNode)          meC.getKey();
1132                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
1133
1134                     if( hrnChildB.equals( idChildA ) ) {
1135                         edgeFound = true;
1136                         repB      = rep;
1137                     }
1138                 }
1139
1140                 // if the edge from A was not found in B,
1141                 // add it to B.
1142                 if( !edgeFound ) {
1143                     assert id2hrn.containsKey( idChildA );
1144                     hrnChildB = id2hrn.get( idChildA );
1145                     repB = repA.copy();
1146                     addReferenceEdge( hrnB, hrnChildB, repB );
1147                 }
1148                 // otherwise, the edge already existed in both graphs
1149                 // so merge their reachability sets
1150                 else {
1151                     // just replace this beta set with the union
1152                     assert repB != null;
1153                     repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
1154                 }
1155             }
1156         }
1157
1158         // and then again with label nodes
1159         sA = og.td2ln.entrySet();
1160         iA = sA.iterator();
1161         while( iA.hasNext() ) {
1162             Map.Entry      meA = (Map.Entry)      iA.next();
1163             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1164             LabelNode      lnA = (LabelNode)      meA.getValue();
1165
1166             HeapRegionNode hrnChildA = null;
1167             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1168             while( heapRegionsItrA.hasNext() ) {
1169                 Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1170                 hrnChildA                    = (HeapRegionNode)          meH.getKey();
1171                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1172
1173                 Integer idChildA = hrnChildA.getID();
1174
1175                 // at this point we know an edge in graph A exists
1176                 // tdA -> idChildA, does this exist in B?
1177                 boolean edgeFound = false;
1178                 assert td2ln.containsKey( tdA );
1179                 LabelNode lnB = td2ln.get( tdA );
1180
1181                 HeapRegionNode          hrnChildB = null;
1182                 ReferenceEdgeProperties repB      = null;
1183                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1184                 while( heapRegionsItrB.hasNext() ) {
1185                     Map.Entry meC               = (Map.Entry)               heapRegionsItrB.next();
1186                     hrnChildB                   = (HeapRegionNode)          meC.getKey();
1187                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
1188
1189                     if( hrnChildB.equals( idChildA ) ) {
1190                         edgeFound = true;
1191                         repB      = rep;
1192                     }
1193                 }
1194
1195                 // if the edge from A was not found in B,
1196                 // add it to B.
1197                 if( !edgeFound ) {
1198                     assert id2hrn.containsKey( idChildA );
1199                     hrnChildB = id2hrn.get( idChildA );
1200                     repB = repA.copy();
1201                     addReferenceEdge( lnB, hrnChildB, repB );
1202                 }
1203                 // otherwise, the edge already existed in both graphs
1204                 // so merge the reachability sets
1205                 else {
1206                     // just replace this beta set with the union
1207                     assert repB != null;
1208                     repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
1209                 }
1210             }
1211         }
1212     }
1213
1214     // you should only merge ownership graphs that have the
1215     // same number of parameters, or if one or both parameter
1216     // index tables are empty
1217     protected void mergeId2paramIndex( OwnershipGraph og ) {
1218         if( id2paramIndex.size() == 0 ) {
1219             id2paramIndex = og.id2paramIndex;
1220             paramIndex2id = og.paramIndex2id;
1221             return;
1222         }
1223
1224         if( og.id2paramIndex.size() == 0 ) {
1225             return;
1226         }
1227
1228         assert id2paramIndex.size() == og.id2paramIndex.size();
1229     }
1230
1231     protected void mergeAllocationSites( OwnershipGraph og ) {
1232         allocationSites.addAll( og.allocationSites );
1233     }
1234
1235
1236
1237     // it is necessary in the equals() member functions
1238     // to "check both ways" when comparing the data
1239     // structures of two graphs.  For instance, if all
1240     // edges between heap region nodes in graph A are
1241     // present and equal in graph B it is not sufficient
1242     // to say the graphs are equal.  Consider that there
1243     // may be edges in graph B that are not in graph A.
1244     // the only way to know that all edges in both graphs
1245     // are equally present is to iterate over both data
1246     // structures and compare against the other graph.
1247     public boolean equals( OwnershipGraph og ) {
1248
1249         if( og == null ) {
1250           return false;
1251         }
1252
1253         if( !areHeapRegionNodesEqual( og ) ) {
1254             return false;
1255         }
1256
1257         if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
1258             return false;
1259         }
1260
1261         if( !areLabelNodesEqual( og ) ) {
1262             return false;
1263         }
1264
1265         if( !areLabelToHeapRegionEdgesEqual( og ) ) {
1266             return false;
1267         }
1268
1269         if( !areId2paramIndexEqual( og ) ) {
1270             return false;
1271         }
1272
1273         // if everything is equal up to this point,
1274         // assert that allocationSites is also equal--
1275         // this data is redundant and kept for efficiency
1276         assert allocationSites.equals( og.allocationSites );
1277
1278         return true;
1279     }
1280
1281     protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1282         // check all nodes in A for presence in graph B
1283         Set      sA = og.id2hrn.entrySet();
1284         Iterator iA = sA.iterator();
1285         while( iA.hasNext() ) {
1286             Map.Entry      meA  = (Map.Entry)      iA.next();
1287             Integer        idA  = (Integer)        meA.getKey();
1288             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1289
1290             if( !id2hrn.containsKey( idA ) ) {
1291                 return false;
1292             }
1293
1294             //HeapRegionNode hrnB = og.id2hrn.get( idA );
1295             HeapRegionNode hrnB = id2hrn.get( idA );
1296             if( !hrnA.equals( hrnB ) ) {
1297                 return false;
1298             }
1299         }
1300
1301         // then check all nodes in B verses graph A
1302         Set      sB = id2hrn.entrySet();
1303         Iterator iB = sB.iterator();
1304         while( iB.hasNext() ) {
1305             Map.Entry      meB  = (Map.Entry)      iB.next();
1306             Integer        idB  = (Integer)        meB.getKey();
1307             HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
1308
1309             if( !og.id2hrn.containsKey( idB ) ) {
1310                 return false;
1311             }
1312
1313             // we should have already checked the equality
1314             // of this pairing in the last pass if they both
1315             // exist so assert that they are equal now
1316             HeapRegionNode hrnA = og.id2hrn.get( idB );
1317             assert hrnB.equals( hrnA );
1318         }
1319
1320         return true;
1321     }
1322
1323     protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
1324         Set      sA = og.id2hrn.entrySet();
1325         Iterator iA = sA.iterator();
1326         while( iA.hasNext() ) {
1327             Map.Entry      meA  = (Map.Entry)      iA.next();
1328             Integer        idA  = (Integer)        meA.getKey();
1329             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1330
1331             // we should have already checked that the same
1332             // heap regions exist in both graphs
1333             assert id2hrn.containsKey( idA );
1334
1335             // and are their edges the same?  first check every
1336             // edge in A for presence and equality in B
1337             HeapRegionNode hrnChildA = null;
1338             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1339             while( heapRegionsItrA.hasNext() ) {
1340                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1341                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1342                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1343
1344                 Integer idChildA = hrnChildA.getID();
1345                 assert id2hrn.containsKey( idChildA );
1346
1347                 // at this point we know an edge in graph A exists
1348                 // idA -> idChildA, does this edge exist in B?
1349                 boolean edgeFound = false;
1350                 HeapRegionNode hrnB = id2hrn.get( idA );
1351
1352                 HeapRegionNode hrnChildB = null;
1353                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1354                 while( heapRegionsItrB.hasNext() ) {
1355                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
1356                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
1357                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1358
1359                     if( idChildA.equals( hrnChildB.getID() ) ) {
1360                         if( !repA.equals( repB ) ) {
1361                             return false;
1362                         }
1363                         edgeFound = true;
1364                     }
1365                 }
1366
1367                 if( !edgeFound ) {
1368                     return false;
1369                 }
1370             }
1371
1372             // then check every edge in B for presence in A, starting
1373             // from the same parent HeapRegionNode
1374             HeapRegionNode hrnB = id2hrn.get( idA );
1375
1376             HeapRegionNode hrnChildB = null;
1377             Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1378             while( heapRegionsItrB.hasNext() ) {
1379                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
1380                 hrnChildB                    = (HeapRegionNode)          me.getKey();
1381                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1382
1383                 Integer idChildB = hrnChildB.getID();
1384
1385                 // at this point we know an edge in graph B exists
1386                 // idB -> idChildB, does this edge exist in A?
1387                 boolean edgeFound = false;
1388
1389                 hrnChildA       = null;
1390                 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1391                 while( heapRegionsItrA.hasNext() ) {
1392                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1393                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
1394                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1395
1396                     if( idChildB.equals( hrnChildA.getID() ) ) {
1397                         assert repB.equals( repA );
1398                         edgeFound = true;
1399                     }
1400                 }
1401
1402                 if( !edgeFound ) {
1403                     return false;
1404                 }
1405             }
1406         }
1407
1408         return true;
1409     }
1410
1411     protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1412         // are all label nodes in A also in graph B?
1413         Set      sA = og.td2ln.entrySet();
1414         Iterator iA = sA.iterator();
1415         while( iA.hasNext() ) {
1416             Map.Entry      meA = (Map.Entry)      iA.next();
1417             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1418
1419             if( !td2ln.containsKey( tdA ) ) {
1420                 return false;
1421             }
1422         }
1423
1424         // are all label nodes in B also in A?
1425         Set      sB = td2ln.entrySet();
1426         Iterator iB = sB.iterator();
1427         while( iB.hasNext() ) {
1428             Map.Entry      meB = (Map.Entry)      iB.next();
1429             TempDescriptor tdB = (TempDescriptor) meB.getKey();
1430
1431             if( !og.td2ln.containsKey( tdB ) ) {
1432                 return false;
1433             }
1434         }
1435
1436         return true;
1437     }
1438
1439     protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
1440         Set      sA = og.td2ln.entrySet();
1441         Iterator iA = sA.iterator();
1442         while( iA.hasNext() ) {
1443             Map.Entry      meA = (Map.Entry)      iA.next();
1444             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1445             LabelNode      lnA = (LabelNode)      meA.getValue();
1446
1447             // we should have already checked that the same
1448             // label nodes exist in both graphs
1449             assert td2ln.containsKey( tdA );
1450
1451             // and are their edges the same?  first check every
1452             // edge in A for presence and equality in B
1453             HeapRegionNode hrnChildA = null;
1454             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1455             while( heapRegionsItrA.hasNext() ) {
1456                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1457                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1458                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1459
1460                 Integer idChildA = hrnChildA.getID();
1461                 assert id2hrn.containsKey( idChildA );
1462
1463                 // at this point we know an edge in graph A exists
1464                 // tdA -> idChildA, does this edge exist in B?
1465                 boolean edgeFound = false;
1466                 LabelNode lnB = td2ln.get( tdA );
1467
1468                 HeapRegionNode hrnChildB = null;
1469                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1470                 while( heapRegionsItrB.hasNext() ) {
1471                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
1472                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
1473                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1474
1475                     if( idChildA.equals( hrnChildB.getID() ) ) {
1476                         if( !repA.equals( repB ) ) {
1477                             return false;
1478                         }
1479                         edgeFound = true;
1480                     }
1481                 }
1482
1483                 if( !edgeFound ) {
1484                     return false;
1485                 }
1486             }
1487
1488             // then check every edge in B for presence in A, starting
1489             // from the same parent LabelNode
1490             LabelNode lnB = td2ln.get( tdA );
1491
1492             HeapRegionNode hrnChildB = null;
1493             Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1494             while( heapRegionsItrB.hasNext() ) {
1495                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
1496                 hrnChildB                    = (HeapRegionNode)          me.getKey();
1497                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1498
1499                 Integer idChildB = hrnChildB.getID();
1500
1501                 // at this point we know an edge in graph B exists
1502                 // tdB -> idChildB, does this edge exist in A?
1503                 boolean edgeFound = false;
1504
1505                 hrnChildA       = null;
1506                 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1507                 while( heapRegionsItrA.hasNext() ) {
1508                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1509                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
1510                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1511
1512                     if( idChildB.equals( hrnChildA.getID() ) ) {
1513                         assert repB.equals( repA );
1514                         edgeFound = true;
1515                     }
1516                 }
1517
1518                 if( !edgeFound ) {
1519                     return false;
1520                 }
1521             }
1522         }
1523
1524         return true;
1525     }
1526
1527
1528     protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1529         return id2paramIndex.size() == og.id2paramIndex.size();
1530     }
1531
1532
1533
1534     // given a set B of heap region node ID's, return the set of heap
1535     // region node ID's that is reachable from B
1536     public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1537
1538         HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1539         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1540
1541         // initial nodes to visit are from set B
1542         Iterator initialItr = idSetB.iterator();
1543         while( initialItr.hasNext() ) {
1544             Integer idInitial = (Integer) initialItr.next();
1545             assert id2hrn.contains( idInitial );
1546             HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1547             toVisit.add( hrnInitial );
1548         }
1549
1550         HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1551
1552         // do a heap traversal
1553         while( !toVisit.isEmpty() ) {
1554             HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1555             toVisit.remove( hrnVisited );
1556             visited.add   ( hrnVisited );
1557
1558             // for every node visited, add it to the total
1559             // reachable set
1560             idSetReachableFromB.add( hrnVisited.getID() );
1561
1562             // find other reachable nodes
1563             Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1564             while( referenceeItr.hasNext() ) {
1565                 Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1566                 HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1567                 ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1568
1569                 if( !visited.contains( hrnReferencee ) ) {
1570                     toVisit.add( hrnReferencee );
1571                 }
1572             }
1573         }
1574
1575         return idSetReachableFromB;
1576     }
1577
1578
1579     // used to find if a heap region can possibly have a reference to
1580     // any of the heap regions in the given set
1581     // if the id supplied is in the set, then a self-referencing edge
1582     // would return true, but that special case is specifically allowed
1583     // meaning that it isn't an external alias
1584     public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1585
1586         assert id2hrn.contains( id );
1587         HeapRegionNode hrn = id2hrn.get( id );
1588
1589         /*
1590         HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1591
1592         Iterator i = idSet.iterator();
1593         while( i.hasNext() ) {
1594             Integer idFromSet = (Integer) i.next();
1595             assert id2hrn.contains( idFromSet );
1596             hrnSet.add( id2hrn.get( idFromSet ) );
1597         }
1598         */
1599
1600         // do a traversal from hrn and see if any of the
1601         // heap regions from the set come up during that
1602         HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1603         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1604
1605         toVisit.add( hrn );
1606         while( !toVisit.isEmpty() ) {
1607             HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1608             toVisit.remove( hrnVisited );
1609             visited.add   ( hrnVisited );
1610
1611             Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1612             while( referenceeItr.hasNext() ) {
1613                 Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1614                 HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1615                 ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1616
1617                 if( idSet.contains( hrnReferencee.getID() ) ) {
1618                     if( !id.equals( hrnReferencee.getID() ) ) {
1619                         return true;
1620                     }
1621                 }
1622
1623                 if( !visited.contains( hrnReferencee ) ) {
1624                     toVisit.add( hrnReferencee );
1625                 }
1626             }
1627         }
1628
1629         return false;
1630     }
1631
1632
1633
1634     // for writing ownership graphs to dot files
1635     public void writeGraph( Descriptor methodDesc,
1636                             FlatNode   fn,
1637                             boolean    writeLabels,
1638                             boolean    labelSelect,
1639                             boolean    pruneGarbage,
1640                             boolean    writeReferencers
1641                             ) throws java.io.IOException {
1642         writeGraph(
1643                    methodDesc.getSymbol() +
1644                    methodDesc.getNum() +
1645                    fn.toString(),
1646                    writeLabels,
1647                    labelSelect,
1648                    pruneGarbage,
1649                    writeReferencers
1650                    );
1651     }
1652
1653     public void writeGraph( Descriptor methodDesc,
1654                             FlatNode   fn,
1655                             boolean    writeLabels,
1656                             boolean    writeReferencers
1657                             ) throws java.io.IOException {
1658         writeGraph(
1659                    methodDesc.getSymbol() +
1660                    methodDesc.getNum() +
1661                    fn.toString(),
1662                    writeLabels,
1663                    false,
1664                    false,
1665                    writeReferencers
1666                    );
1667     }
1668
1669     public void writeGraph( Descriptor methodDesc,
1670                             boolean    writeLabels,
1671                             boolean    writeReferencers
1672                             ) throws java.io.IOException {
1673         writeGraph(
1674                    methodDesc.getSymbol() +
1675                    methodDesc.getNum() +
1676                    "COMPLETE",
1677                    writeLabels,
1678                    false,
1679                    false,
1680                    writeReferencers
1681                     );
1682     }
1683
1684     public void writeGraph( Descriptor methodDesc,
1685                             boolean    writeLabels,
1686                             boolean    labelSelect,
1687                             boolean    pruneGarbage,
1688                             boolean    writeReferencers
1689                             ) throws java.io.IOException {
1690         writeGraph(
1691                    methodDesc.getSymbol() +
1692                    methodDesc.getNum() +
1693                    "COMPLETE",
1694                    writeLabels,
1695                    labelSelect,
1696                    pruneGarbage,
1697                    writeReferencers
1698                     );
1699     }
1700
1701     public void writeGraph( String graphName,
1702                             boolean writeLabels,
1703                             boolean labelSelect,
1704                             boolean pruneGarbage,
1705                             boolean writeReferencers
1706                             ) throws java.io.IOException {
1707
1708         // remove all non-word characters from the graph name so
1709         // the filename and identifier in dot don't cause errors
1710         graphName = graphName.replaceAll( "[\\W]", "" );
1711
1712         BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1713         bw.write( "digraph "+graphName+" {\n" );
1714         //bw.write( "  size=\"7.5,10\";\n" );
1715
1716         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1717
1718         // then visit every heap region node
1719         if( !pruneGarbage ) {
1720             Set      s = id2hrn.entrySet();
1721             Iterator i = s.iterator();
1722             while( i.hasNext() ) {
1723                 Map.Entry      me  = (Map.Entry)      i.next();
1724                 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1725                 if( !visited.contains( hrn ) ) {
1726                     traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1727                                              hrn,
1728                                              bw,
1729                                              null,
1730                                              visited,
1731                                              writeReferencers );
1732                 }
1733             }
1734         }
1735
1736         bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
1737
1738
1739         // then visit every label node, useful for debugging
1740         if( writeLabels ) {
1741             Set      s = td2ln.entrySet();
1742             Iterator i = s.iterator();
1743             while( i.hasNext() ) {
1744                 Map.Entry me = (Map.Entry) i.next();
1745                 LabelNode ln = (LabelNode) me.getValue();
1746
1747                 if( labelSelect ) {
1748                     String labelStr = ln.getTempDescriptorString();
1749                     if( labelStr.startsWith( "___temp"      ) ||
1750                         labelStr.startsWith( "___dst"       ) ||
1751                         labelStr.startsWith( "___srctmp"   ) ||
1752                         labelStr.startsWith( "___neverused" )   ) {
1753                         continue;
1754                     }
1755                 }
1756
1757                 HeapRegionNode hrn = null;
1758                 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1759                 while( heapRegionsItr.hasNext() ) {
1760                     Map.Entry meH               = (Map.Entry)               heapRegionsItr.next();
1761                     hrn                         = (HeapRegionNode)          meH.getKey();
1762                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
1763
1764                     if( pruneGarbage && !visited.contains( hrn ) ) {
1765                         traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1766                                                  hrn,
1767                                                  bw,
1768                                                  null,
1769                                                  visited,
1770                                                  writeReferencers );
1771                     }
1772
1773                     bw.write( "  "        + ln.toString() +
1774                               " -> "      + hrn.toString() +
1775                               "[label=\"" + rep.toEdgeLabelString() +
1776                               "\",decorate];\n" );
1777                 }
1778             }
1779         }
1780
1781
1782         bw.write( "}\n" );
1783         bw.close();
1784     }
1785
1786     protected void traverseHeapRegionNodes( int mode,
1787                                             HeapRegionNode hrn,
1788                                             BufferedWriter bw,
1789                                             TempDescriptor td,
1790                                             HashSet<HeapRegionNode> visited,
1791                                             boolean writeReferencers
1792                                             ) throws java.io.IOException {
1793
1794         if( visited.contains( hrn ) ) {
1795             return;
1796         }
1797         visited.add( hrn );
1798
1799         switch( mode ) {
1800         case VISIT_HRN_WRITE_FULL:
1801
1802             String attributes = "[";
1803
1804             if( hrn.isSingleObject() ) {
1805                 attributes += "shape=box";
1806             } else {
1807                 attributes += "shape=Msquare";
1808             }
1809
1810             if( hrn.isFlagged() ) {
1811                 attributes += ",style=filled,fillcolor=lightgrey";
1812             }
1813
1814             attributes += ",label=\"ID"        +
1815                           hrn.getID()          +
1816                           "\\n"                +
1817                           hrn.getDescription() +
1818                           "\\n"                +
1819                           hrn.getAlphaString() +
1820                           "\"]";
1821
1822             bw.write( "  " + hrn.toString() + attributes + ";\n" );
1823             break;
1824         }
1825
1826
1827         // useful for debugging
1828         if( writeReferencers ) {
1829             OwnershipNode onRef  = null;
1830             Iterator      refItr = hrn.iteratorToReferencers();
1831             while( refItr.hasNext() ) {
1832                 onRef = (OwnershipNode) refItr.next();
1833
1834                 switch( mode ) {
1835                 case VISIT_HRN_WRITE_FULL:
1836                     bw.write( "  "                    + hrn.toString() +
1837                               " -> "                  + onRef.toString() +
1838                               "[color=lightgray];\n" );
1839                     break;
1840                 }
1841             }
1842         }
1843
1844
1845         HeapRegionNode hrnChild = null;
1846         Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1847         while( childRegionsItr.hasNext() ) {
1848             Map.Entry me                = (Map.Entry)               childRegionsItr.next();
1849             hrnChild                    = (HeapRegionNode)          me.getKey();
1850             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1851
1852             switch( mode ) {
1853             case VISIT_HRN_WRITE_FULL:
1854                 bw.write( "  "        + hrn.toString() +
1855                           " -> "      + hrnChild.toString() +
1856                           "[label=\"" + rep.toEdgeLabelString() +
1857                           "\",decorate];\n" );
1858                 break;
1859             }
1860
1861             traverseHeapRegionNodes( mode,
1862                                      hrnChild,
1863                                      bw,
1864                                      td,
1865                                      visited,
1866                                      writeReferencers );
1867         }
1868     }
1869 }