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