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
  23
  24     public OwnershipGraph( int allocationDepth ) {
  25         this.allocationDepth = allocationDepth;
  26
  27         id2hrn = new Hashtable<Integer,        HeapRegionNode>();
  28         td2ln  = new Hashtable<TempDescriptor, LabelNode     >();
  29     }
  30
  31
  32     // label nodes are much easier to deal with than
  33     // heap region nodes.  Whenever there is a request
  34     // for the label node that is associated with a
  35     // temp descriptor we can either find it or make a
  36     // new one and return it.  This is because temp
  37     // descriptors are globally unique and every label
  38     // node is mapped to exactly one temp descriptor.
  39     protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) {
  40         assert td != null;
  41
  42         if( !td2ln.containsKey( td ) ) {
  43             td2ln.put( td, new LabelNode( td ) );
  44         }
  45
  46         return td2ln.get( td );
  47     }
  48
  49
  50     // the reason for this method is to have the option
  51     // creating new heap regions with specific IDs, or
  52     // duplicating heap regions with specific IDs (especially
  53     // in the merge() operation) or to create new heap
  54     // regions with a new unique ID.
  55     protected HeapRegionNode
  56         createNewHeapRegionNode( Integer id,
  57                                  boolean isSingleObject,
  58                                  boolean isFlagged,
  59                                  boolean isNewSummary,
  60                                  String  description ) {
  61
  62         if( id == null ) {
  63             id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  64         }
  65
  66         HeapRegionNode hrn = new HeapRegionNode( id,
  67                                                  isSingleObject,
  68                                                  isFlagged,
  69                                                  isNewSummary,
  70                                                  description );
  71         id2hrn.put( id, hrn );
  72         return hrn;
  73     }
  74
  75
  76
  77     ////////////////////////////////////////////////
  78     //
  79     //  Low-level referencee and referencer methods
  80     //
  81     //  These methods provide the lowest level for
  82     //  creating references between ownership nodes
  83     //  and handling the details of maintaining both
  84     //  list of referencers and referencees.
  85     //
  86     ////////////////////////////////////////////////
  87     protected void addReferenceEdge( OwnershipNode  referencer,
  88                                      HeapRegionNode referencee,
  89                                      ReferenceEdgeProperties rep ) {
  90         assert referencer != null;
  91         assert referencee != null;
  92         referencer.addReferencedRegion( referencee, rep );
  93         referencee.addReferencer( referencer );
  94     }
  95
  96     protected void removeReferenceEdge( OwnershipNode  referencer,
  97                                         HeapRegionNode referencee ) {
  98         assert referencer != null;
  99         assert referencee != null;
 100         assert referencer.getReferenceTo( referencee ) != null;
 101         assert referencee.isReferencedBy( referencer );
 102
 103         referencer.removeReferencedRegion( referencee );
 104         referencee.removeReferencer( referencer );
 105     }
 106
 107     protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
 108         assert referencer != null;
 109
 110         // get a copy of the table to iterate over, otherwise
 111         // we will be trying to take apart the table as we
 112         // are iterating over it, which won't work
 113         Iterator i = referencer.setIteratorToReferencedRegionsClone();
 114         while( i.hasNext() ) {
 115             Map.Entry me = (Map.Entry) i.next();
 116             HeapRegionNode referencee = (HeapRegionNode) me.getKey();
 117             removeReferenceEdge( referencer, referencee );
 118         }
 119     }
 120
 121     protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
 122         assert referencee != null;
 123
 124         // get a copy of the table to iterate over, otherwise
 125         // we will be trying to take apart the table as we
 126         // are iterating over it, which won't work
 127         Iterator i = referencee.iteratorToReferencersClone();
 128         while( i.hasNext() ) {
 129             OwnershipNode referencer = (OwnershipNode) i.next();
 130             removeReferenceEdge( referencer, referencee );
 131         }
 132     }
 133
 134
 135     ////////////////////////////////////////////////////
 136     //
 137     //  Assignment Operation Methods
 138     //
 139     //  These methods are high-level operations for
 140     //  modeling program assignment statements using
 141     //  the low-level reference create/remove methods
 142     //  above.
 143     //
 144     //  The destination in an assignment statement is
 145     //  going to have new references.  The method of
 146     //  determining the references depends on the type
 147     //  of the FlatNode assignment and the predicates
 148     //  of the nodes and edges involved.
 149     //
 150     ////////////////////////////////////////////////////
 151     public void assignTempToTemp( TempDescriptor src,
 152                                   TempDescriptor dst ) {
 153         LabelNode srcln = getLabelNodeFromTemp( src );
 154         LabelNode dstln = getLabelNodeFromTemp( dst );
 155
 156         clearReferenceEdgesFrom( dstln );
 157         HeapRegionNode newReferencee = null;
 158         Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
 159         while( srcRegionsItr.hasNext() ) {
 160             Map.Entry               me  = (Map.Entry)               srcRegionsItr.next();
 161             newReferencee               = (HeapRegionNode)          me.getKey();
 162             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 163
 164             addReferenceEdge( dstln, newReferencee, rep.copy() );
 165         }
 166     }
 167
 168     public void assignTempToField( TempDescriptor src,
 169                                    TempDescriptor dst,
 170                                    FieldDescriptor fd ) {
 171         LabelNode srcln = getLabelNodeFromTemp( src );
 172         LabelNode dstln = getLabelNodeFromTemp( dst );
 173
 174         clearReferenceEdgesFrom( dstln );
 175
 176         HeapRegionNode hrn = null;
 177         Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
 178         while( srcRegionsItr.hasNext() ) {
 179             Map.Entry me = (Map.Entry)      srcRegionsItr.next();
 180             hrn          = (HeapRegionNode) me.getKey();
 181
 182             HeapRegionNode hrnOneHop = null;
 183             Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
 184             while( hrnRegionsItr.hasNext() ) {
 185                 Map.Entry               meH = (Map.Entry)               hrnRegionsItr.next();
 186                 hrnOneHop                   = (HeapRegionNode)          meH.getKey();
 187                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
 188
 189                 addReferenceEdge( dstln, hrnOneHop, rep.copy() );
 190             }
 191         }
 192     }
 193
 194     public void assignFieldToTemp( TempDescriptor src,
 195                                    TempDescriptor dst,
 196                                    FieldDescriptor fd ) {
 197         LabelNode srcln = getLabelNodeFromTemp( src );
 198         LabelNode dstln = getLabelNodeFromTemp( dst );
 199
 200         HeapRegionNode hrn = null;
 201         Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
 202         while( dstRegionsItr.hasNext() ) {
 203             Map.Entry me = (Map.Entry)      dstRegionsItr.next();
 204             hrn          = (HeapRegionNode) me.getKey();
 205
 206             HeapRegionNode hrnSrc = null;
 207             Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
 208             while( srcRegionsItr.hasNext() ) {
 209                 Map.Entry               meS = (Map.Entry)               srcRegionsItr.next();
 210                 hrnSrc                      = (HeapRegionNode)          meS.getKey();
 211                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meS.getValue();
 212
 213                 addReferenceEdge( hrn, hrnSrc, rep.copy() );
 214             }
 215         }
 216     }
 217
 218     public void assignTempToParameterAllocation( boolean isTask,
 219                                                  TempDescriptor td ) {
 220         assert td != null;
 221
 222         LabelNode      lnParam = getLabelNodeFromTemp( td );
 223         HeapRegionNode hrn     = createNewHeapRegionNode( null,
 224                                                           false,
 225                                                           isTask,
 226                                                           false,
 227                                                           "param" );
 228
 229         addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false ) );
 230         addReferenceEdge( hrn,     hrn, new ReferenceEdgeProperties( false ) );
 231     }
 232
 233     public void assignTempToNewAllocation( TempDescriptor td,
 234                                            AllocationSite as ) {
 235         assert td != null;
 236         assert as != null;
 237
 238         age( as );
 239
 240         // after the age operation the newest (or zero-ith oldest)
 241         // node associated with the allocation site should have
 242         // no references to it as if it were a newly allocated
 243         // heap region, so make a reference to it to complete
 244         // this operation
 245         Integer        id        = as.getIthOldest( 0 );
 246         HeapRegionNode hrnNewest = id2hrn.get( id );
 247         assert hrnNewest != null;
 248
 249         LabelNode dst = getLabelNodeFromTemp( td );
 250
 251         addReferenceEdge( dst, hrnNewest, new ReferenceEdgeProperties( false ) );
 252     }
 253
 254
 255     // use the allocation site (unique to entire analysis) to
 256     // locate the heap region nodes in this ownership graph
 257     // that should be aged.  The process models the allocation
 258     // of new objects and collects all the oldest allocations
 259     // in a summary node to allow for a finite analysis
 260     //
 261     // There is an additional property of this method.  After
 262     // running it on a particular ownership graph (many graphs
 263     // may have heap regions related to the same allocation site)
 264     // the heap region node objects in this ownership graph will be
 265     // allocated.  Therefore, after aging a graph for an allocation
 266     // site, attempts to retrieve the heap region nodes using the
 267     // integer id's contained in the allocation site should always
 268     // return non-null heap regions.
 269     public void age( AllocationSite as ) {
 270
 271         //////////////////////////////////////////////////////////////////
 272         //
 273         //  move existing references down the line toward
 274         //  the oldest element, starting with the oldest
 275         //
 276         //  An illustration:
 277         //    TempDescriptor = the td passed into this function, left side of new statement
 278         //    AllocationSite = { alpha0, alpha1, alpha2, alphaSummary }
 279         //
 280         //  1. Specially merge refs in/out at alpha2 into alphaSummary
 281         //  2. Move refs in/out at alpha1 over to alpha2 (alpha1 becomes alpha2)
 282         //  3. Move refs in/out at alpha0 over to alpha1
 283         //  4. Assign reference from td to alpha0, which now represents a freshly allocated object
 284         //
 285         //////////////////////////////////////////////////////////////////
 286
 287
 288         // first specially merge the references from the oldest
 289         // node into the summary node, keeping track of 1-to-1 edges
 290         Integer        idSummary  = as.getSummary();
 291         HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 292
 293         // if this is null then we haven't touched this allocation site
 294         // in the context of the current ownership graph, so simply
 295         // allocate an appropriate heap region node
 296         // this should only happen once per ownership per allocation site,
 297         // and a particular integer id can be used to locate the heap region
 298         // in different ownership graphs that represents the same part of an
 299         // allocation site
 300         if( hrnSummary == null ) {
 301             hrnSummary = createNewHeapRegionNode( idSummary,
 302                                                   false,
 303                                                   false,
 304                                                   true,
 305                                                   as + "\\nsummary" );
 306         }
 307
 308         // first transfer the references out of alpha_k to alpha_s
 309         Integer        idK  = as.getOldest();
 310         HeapRegionNode hrnK = id2hrn.get( idK );
 311
 312         // see comment above about needing to allocate a heap region
 313         // for the context of this ownership graph
 314         if( hrnK == null ) {
 315             hrnK = createNewHeapRegionNode( idK,
 316                                             true,
 317                                             false,
 318                                             false,
 319                                             as + "\\noldest" );
 320         }
 321
 322         HeapRegionNode hrnReferencee = null;
 323         Iterator       itrReferencee = hrnK.setIteratorToReferencedRegions();
 324         while( itrReferencee.hasNext() ) {
 325             Map.Entry               me  = (Map.Entry)               itrReferencee.next();
 326             hrnReferencee               = (HeapRegionNode)          me.getKey();
 327             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 328
 329             // determine if another summary node is already referencing this referencee
 330             boolean       hasSummaryReferencer = false;
 331             OwnershipNode onReferencer         = null;
 332             Iterator      itrReferencer        = hrnReferencee.iteratorToReferencers();
 333             while( itrReferencer.hasNext() ) {
 334                 onReferencer = (OwnershipNode) itrReferencer.next();
 335                 if( onReferencer instanceof HeapRegionNode ) {
 336                     HeapRegionNode hrnPossibleSummary = (HeapRegionNode) onReferencer;
 337                     if( hrnPossibleSummary.isNewSummary() ) {
 338                         hasSummaryReferencer = true;
 339                     }
 340                 }
 341             }
 342
 343             addReferenceEdge( hrnSummary,
 344                               hrnReferencee,
 345                               new ReferenceEdgeProperties( !hasSummaryReferencer ) );
 346         }
 347
 348         // next transfer references to alpha_k over to alpha_s
 349         OwnershipNode onReferencer  = null;
 350         Iterator      itrReferencer = hrnK.iteratorToReferencers();
 351         while( itrReferencer.hasNext() ) {
 352             onReferencer = (OwnershipNode) itrReferencer.next();
 353
 354             ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnK );
 355             assert rep != null;
 356
 357             addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
 358         }
 359
 360
 361         // then move down the line of heap region nodes
 362         // clobbering the ith and transferring all references
 363         // to and from i-1 to node i.  Note that this clobbers
 364         // the oldest node (alpha_k) that was just merged into
 365         // the summary above and should move everything from
 366         // alpha_0 to alpha_1 before we finish
 367         for( int i = allocationDepth - 1; i > 0; --i ) {
 368
 369             // move references from the ith oldest to the i+1 oldest
 370             Integer        idIth     = as.getIthOldest( i );
 371             HeapRegionNode hrnI      = id2hrn.get( idIth );
 372             Integer        idImin1th = as.getIthOldest( i - 1 );
 373             HeapRegionNode hrnImin1  = id2hrn.get( idImin1th );
 374
 375             // see comment above about needing to allocate a heap region
 376             // for the context of this ownership graph
 377             if( hrnI == null ) {
 378                 hrnI = createNewHeapRegionNode( idIth,
 379                                                 true,
 380                                                 false,
 381                                                 false,
 382                                                 as + "\\n" + Integer.toString( i ) + "th" );
 383             }
 384             if( hrnImin1 == null ) {
 385                 hrnImin1 = createNewHeapRegionNode( idImin1th,
 386                                                     true,
 387                                                     false,
 388                                                     false,
 389                                                     as + "\\n" + Integer.toString( i-1 ) + "th" );
 390             }
 391
 392             // clear references in and out of node i
 393             clearReferenceEdgesFrom( hrnI );
 394             clearReferenceEdgesTo  ( hrnI );
 395
 396             // copy each edge in and out of i-1 to i
 397             hrnReferencee = null;
 398             itrReferencee = hrnImin1.setIteratorToReferencedRegions();
 399             while( itrReferencee.hasNext() ) {
 400                 Map.Entry               me  = (Map.Entry)               itrReferencee.next();
 401                 hrnReferencee               = (HeapRegionNode)          me.getKey();
 402                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 403
 404                 addReferenceEdge( hrnI, hrnReferencee, rep.copy() );
 405             }
 406
 407             onReferencer  = null;
 408             itrReferencer = hrnImin1.iteratorToReferencers();
 409             while( itrReferencer.hasNext() ) {
 410                 onReferencer = (OwnershipNode) itrReferencer.next();
 411
 412                 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 );
 413                 assert rep != null;
 414
 415                 addReferenceEdge( onReferencer, hrnI, rep.copy() );
 416             }
 417         }
 418
 419         // as stated above, the newest node alpha_0 should have had its
 420         // references moved over to alpha_1, so we can wipe alpha_0 clean
 421         // in preparation for operations that want to reference a freshly
 422         // allocated object from this allocation site
 423         Integer        id0th = as.getIthOldest( 0 );
 424         HeapRegionNode hrn0  = id2hrn.get( id0th );
 425
 426         // the loop to move references from i-1 to i should
 427         // have touched this node, therefore assert it is non-null
 428         assert hrn0 != null;
 429
 430         // clear all references in and out of newest node
 431         clearReferenceEdgesFrom( hrn0 );
 432         clearReferenceEdgesTo  ( hrn0 );
 433     }
 434
 435
 436
 437     ////////////////////////////////////////////////////
 438     // in merge() and equals() methods the suffix A
 439     // represents the passed in graph and the suffix
 440     // B refers to the graph in this object
 441     ////////////////////////////////////////////////////
 442
 443     public void merge( OwnershipGraph og ) {
 444
 445         if( og == null ) {
 446           return;
 447         }
 448
 449         mergeOwnershipNodes ( og );
 450         mergeReferenceEdges ( og );
 451     }
 452
 453     protected void mergeOwnershipNodes( OwnershipGraph og ) {
 454         Set      sA = og.id2hrn.entrySet();
 455         Iterator iA = sA.iterator();
 456         while( iA.hasNext() ) {
 457             Map.Entry      meA  = (Map.Entry)      iA.next();
 458             Integer        idA  = (Integer)        meA.getKey();
 459             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 460
 461             // if this graph doesn't have a node the
 462             // incoming graph has, allocate it
 463             if( !id2hrn.containsKey( idA ) ) {
 464                 HeapRegionNode hrnB = hrnA.copy();
 465                 id2hrn.put( idA, hrnB );
 466             }
 467         }
 468
 469         // now add any label nodes that are in graph B but
 470         // not in A
 471         sA = og.td2ln.entrySet();
 472         iA = sA.iterator();
 473         while( iA.hasNext() ) {
 474             Map.Entry      meA = (Map.Entry)      iA.next();
 475             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 476             LabelNode      lnA = (LabelNode)      meA.getValue();
 477
 478             // if the label doesn't exist in B, allocate and add it
 479             LabelNode lnB = getLabelNodeFromTemp( tdA );
 480         }
 481     }
 482
 483     protected void mergeReferenceEdges( OwnershipGraph og ) {
 484         // there is a data structure for storing label nodes
 485         // retireved by temp descriptors, and a data structure
 486         // for stroing heap region nodes retrieved by integer
 487         // ids.  Because finding edges requires interacting
 488         // with these disparate data structures frequently the
 489         // process is nearly duplicated, one for each
 490
 491         // heap regions
 492         Set      sA = og.id2hrn.entrySet();
 493         Iterator iA = sA.iterator();
 494         while( iA.hasNext() ) {
 495             Map.Entry      meA  = (Map.Entry)      iA.next();
 496             Integer        idA  = (Integer)        meA.getKey();
 497             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 498
 499             HeapRegionNode hrnChildA = null;
 500             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
 501             while( heapRegionsItrA.hasNext() ) {
 502                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
 503                 hrnChildA                    = (HeapRegionNode)          me.getKey();
 504                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
 505
 506                 Integer idChildA = hrnChildA.getID();
 507
 508                 // at this point we know an edge in graph A exists
 509                 // idA -> idChildA, does this exist in B?
 510                 boolean edgeFound = false;
 511                 assert id2hrn.containsKey( idA );
 512                 HeapRegionNode hrnB = id2hrn.get( idA );
 513
 514                 HeapRegionNode hrnChildB = null;
 515                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
 516                 while( heapRegionsItrB.hasNext() ) {
 517                     Map.Entry meC = (Map.Entry)      heapRegionsItrB.next();
 518                     hrnChildB     = (HeapRegionNode) meC.getKey();
 519
 520                     if( hrnChildB.equals( idChildA ) ) {
 521                         edgeFound = true;
 522                     }
 523                 }
 524
 525                 // if the edge from A was not found in B,
 526                 // add it to B.
 527                 if( !edgeFound ) {
 528                     assert id2hrn.containsKey( idChildA );
 529                     hrnChildB = id2hrn.get( idChildA );
 530                     ReferenceEdgeProperties repB = repA.copy();
 531                     addReferenceEdge( hrnB, hrnChildB, repB );
 532                 }
 533                 // otherwise, the edge already existed in both graphs.
 534                 // if this is the case, check to see whether the isUnique
 535                 // predicate of the edges might change
 536                 else
 537                 {
 538
 539                 }
 540             }
 541         }
 542
 543         // and then again with label nodes
 544         sA = og.td2ln.entrySet();
 545         iA = sA.iterator();
 546         while( iA.hasNext() ) {
 547             Map.Entry      meA = (Map.Entry)      iA.next();
 548             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 549             LabelNode      lnA = (LabelNode)      meA.getValue();
 550
 551             HeapRegionNode hrnChildA = null;
 552             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
 553             while( heapRegionsItrA.hasNext() ) {
 554                 Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
 555                 hrnChildA                    = (HeapRegionNode)          meH.getKey();
 556                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
 557
 558                 Integer idChildA = hrnChildA.getID();
 559
 560                 // at this point we know an edge in graph A exists
 561                 // tdA -> idChildA, does this exist in B?
 562                 boolean edgeFound = false;
 563                 assert td2ln.containsKey( tdA );
 564                 LabelNode lnB = td2ln.get( tdA );
 565
 566                 HeapRegionNode hrnChildB = null;
 567                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
 568                 while( heapRegionsItrB.hasNext() ) {
 569                     Map.Entry meC = (Map.Entry)      heapRegionsItrB.next();
 570                     hrnChildB     = (HeapRegionNode) meC.getKey();
 571
 572                     if( hrnChildB.equals( idChildA ) ) {
 573                         edgeFound = true;
 574                     }
 575                 }
 576
 577                 // if the edge from A was not found in B,
 578                 // add it to B.
 579                 if( !edgeFound ) {
 580                     assert id2hrn.containsKey( idChildA );
 581                     hrnChildB = id2hrn.get( idChildA );
 582                     ReferenceEdgeProperties repB = repA.copy();
 583                     addReferenceEdge( lnB, hrnChildB, repB );
 584                 }
 585                 // otherwise, the edge already existed in both graphs.
 586                 // if this is the case, check to see whether the isUnique
 587                 // predicate of the edges might change
 588                 else
 589                 {
 590
 591                 }
 592             }
 593         }
 594     }
 595
 596
 597     // it is necessary in the equals() member functions
 598     // to "check both ways" when comparing the data
 599     // structures of two graphs.  For instance, if all
 600     // edges between heap region nodes in graph A are
 601     // present and equal in graph B it is not sufficient
 602     // to say the graphs are equal.  Consider that there
 603     // may be edges in graph B that are not in graph A.
 604     // the only way to know that all edges in both graphs
 605     // are equally present is to iterate over both data
 606     // structures and compare against the other graph.
 607     public boolean equals( OwnershipGraph og ) {
 608
 609         if( og == null ) {
 610           return false;
 611         }
 612
 613         if( !areHeapRegionNodesEqual( og ) ) {
 614             return false;
 615         }
 616
 617         if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
 618             return false;
 619         }
 620
 621         if( !areLabelNodesEqual( og ) ) {
 622             return false;
 623         }
 624
 625         if( !areLabelToHeapRegionEdgesEqual( og ) ) {
 626             return false;
 627         }
 628
 629         return true;
 630     }
 631
 632     protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
 633         // check all nodes in A for presence in graph B
 634         Set      sA = og.id2hrn.entrySet();
 635         Iterator iA = sA.iterator();
 636         while( iA.hasNext() ) {
 637             Map.Entry      meA  = (Map.Entry)      iA.next();
 638             Integer        idA  = (Integer)        meA.getKey();
 639             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 640
 641             if( !id2hrn.containsKey( idA ) ) {
 642                 return false;
 643             }
 644
 645             HeapRegionNode hrnB = og.id2hrn.get( idA );
 646             if( !hrnA.equals( hrnB ) ) {
 647                 return false;
 648             }
 649         }
 650
 651         // then check all nodes in B verses graph A
 652         Set      sB = id2hrn.entrySet();
 653         Iterator iB = sB.iterator();
 654         while( iB.hasNext() ) {
 655             Map.Entry      meB  = (Map.Entry)      iB.next();
 656             Integer        idB  = (Integer)        meB.getKey();
 657             HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
 658
 659             if( !og.id2hrn.containsKey( idB ) ) {
 660                 return false;
 661             }
 662
 663             // we should have already checked the equality
 664             // of this pairing in the last pass if they both
 665             // exist so assert that they are equal now
 666             HeapRegionNode hrnA = og.id2hrn.get( idB );
 667             assert hrnB.equals( hrnA );
 668         }
 669
 670         return true;
 671     }
 672
 673     protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
 674         Set      sA = og.id2hrn.entrySet();
 675         Iterator iA = sA.iterator();
 676         while( iA.hasNext() ) {
 677             Map.Entry      meA  = (Map.Entry)      iA.next();
 678             Integer        idA  = (Integer)        meA.getKey();
 679             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 680
 681             // we should have already checked that the same
 682             // heap regions exist in both graphs
 683             assert id2hrn.containsKey( idA );
 684
 685             // and are their edges the same?  first check every
 686             // edge in A for presence and equality in B
 687             HeapRegionNode hrnChildA = null;
 688             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
 689             while( heapRegionsItrA.hasNext() ) {
 690                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
 691                 hrnChildA                    = (HeapRegionNode)          me.getKey();
 692                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
 693
 694                 Integer idChildA = hrnChildA.getID();
 695                 assert id2hrn.containsKey( idChildA );
 696
 697                 // at this point we know an edge in graph A exists
 698                 // idA -> idChildA, does this edge exist in B?
 699                 boolean edgeFound = false;
 700                 HeapRegionNode hrnB = id2hrn.get( idA );
 701
 702                 HeapRegionNode hrnChildB = null;
 703                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
 704                 while( heapRegionsItrB.hasNext() ) {
 705                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
 706                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
 707                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
 708
 709                     if( idChildA.equals( hrnChildB.getID() ) ) {
 710                         if( !repA.equals( repB ) ) {
 711                             return false;
 712                         }
 713                         edgeFound = true;
 714                     }
 715                 }
 716
 717                 if( !edgeFound ) {
 718                     return false;
 719                 }
 720             }
 721
 722             // then check every edge in B for presence in A, starting
 723             // from the same parent HeapRegionNode
 724             HeapRegionNode hrnB = id2hrn.get( idA );
 725
 726             HeapRegionNode hrnChildB = null;
 727             Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
 728             while( heapRegionsItrB.hasNext() ) {
 729                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
 730                 hrnChildB                    = (HeapRegionNode)          me.getKey();
 731                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
 732
 733                 Integer idChildB = hrnChildB.getID();
 734
 735                 // at this point we know an edge in graph B exists
 736                 // idB -> idChildB, does this edge exist in A?
 737                 boolean edgeFound = false;
 738
 739                 hrnChildA       = null;
 740                 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
 741                 while( heapRegionsItrA.hasNext() ) {
 742                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
 743                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
 744                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
 745
 746                     if( idChildB.equals( hrnChildA.getID() ) ) {
 747                         assert repB.equals( repA );
 748                         edgeFound = true;
 749                     }
 750                 }
 751
 752                 if( !edgeFound ) {
 753                     return false;
 754                 }
 755             }
 756         }
 757
 758         return true;
 759     }
 760
 761     protected boolean areLabelNodesEqual( OwnershipGraph og ) {
 762         // are all label nodes in A also in graph B?
 763         Set      sA = og.td2ln.entrySet();
 764         Iterator iA = sA.iterator();
 765         while( iA.hasNext() ) {
 766             Map.Entry      meA = (Map.Entry)      iA.next();
 767             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 768
 769             if( !td2ln.containsKey( tdA ) ) {
 770                 return false;
 771             }
 772         }
 773
 774         // are all label nodes in B also in A?
 775         Set      sB = td2ln.entrySet();
 776         Iterator iB = sB.iterator();
 777         while( iB.hasNext() ) {
 778             Map.Entry      meB = (Map.Entry)      iB.next();
 779             TempDescriptor tdB = (TempDescriptor) meB.getKey();
 780
 781             if( !og.td2ln.containsKey( tdB ) ) {
 782                 return false;
 783             }
 784         }
 785
 786         return true;
 787     }
 788
 789     protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
 790         Set      sA = og.td2ln.entrySet();
 791         Iterator iA = sA.iterator();
 792         while( iA.hasNext() ) {
 793             Map.Entry      meA = (Map.Entry)      iA.next();
 794             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 795             LabelNode      lnA = (LabelNode)      meA.getValue();
 796
 797             // we should have already checked that the same
 798             // label nodes exist in both graphs
 799             assert td2ln.containsKey( tdA );
 800
 801             // and are their edges the same?  first check every
 802             // edge in A for presence and equality in B
 803             HeapRegionNode hrnChildA = null;
 804             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
 805             while( heapRegionsItrA.hasNext() ) {
 806                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
 807                 hrnChildA                    = (HeapRegionNode)          me.getKey();
 808                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
 809
 810                 Integer idChildA = hrnChildA.getID();
 811                 assert id2hrn.containsKey( idChildA );
 812
 813                 // at this point we know an edge in graph A exists
 814                 // tdA -> idChildA, does this edge exist in B?
 815                 boolean edgeFound = false;
 816                 LabelNode lnB = td2ln.get( tdA );
 817
 818                 HeapRegionNode hrnChildB = null;
 819                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
 820                 while( heapRegionsItrB.hasNext() ) {
 821                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
 822                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
 823                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
 824
 825                     if( idChildA.equals( hrnChildB.getID() ) ) {
 826                         if( !repA.equals( repB ) ) {
 827                             return false;
 828                         }
 829                         edgeFound = true;
 830                     }
 831                 }
 832
 833                 if( !edgeFound ) {
 834                     return false;
 835                 }
 836             }
 837
 838             // then check every edge in B for presence in A, starting
 839             // from the same parent LabelNode
 840             LabelNode lnB = td2ln.get( tdA );
 841
 842             HeapRegionNode hrnChildB = null;
 843             Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
 844             while( heapRegionsItrB.hasNext() ) {
 845                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
 846                 hrnChildB                    = (HeapRegionNode)          me.getKey();
 847                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
 848
 849                 Integer idChildB = hrnChildB.getID();
 850
 851                 // at this point we know an edge in graph B exists
 852                 // tdB -> idChildB, does this edge exist in A?
 853                 boolean edgeFound = false;
 854
 855                 hrnChildA       = null;
 856                 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
 857                 while( heapRegionsItrA.hasNext() ) {
 858                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
 859                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
 860                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
 861
 862                     if( idChildB.equals( hrnChildA.getID() ) ) {
 863                         assert repB.equals( repA );
 864                         edgeFound = true;
 865                     }
 866                 }
 867
 868                 if( !edgeFound ) {
 869                     return false;
 870                 }
 871             }
 872         }
 873
 874         return true;
 875     }
 876
 877
 878     // for writing ownership graphs to dot files
 879     public void writeGraph( Descriptor methodDesc,
 880                             FlatNode   fn ) throws java.io.IOException {
 881
 882         String graphName =
 883             methodDesc.getSymbol() +
 884             methodDesc.getNum() +
 885             fn.toString();
 886
 887         // remove all non-word characters from the graph name so
 888         // the filename and identifier in dot don't cause errors
 889         graphName = graphName.replaceAll( "[\\W]", "" );
 890
 891         BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
 892         bw.write( "digraph "+graphName+" {\n" );
 893
 894         // then visit every heap region node
 895         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
 896
 897         Set      s = id2hrn.entrySet();
 898         Iterator i = s.iterator();
 899         while( i.hasNext() ) {
 900             Map.Entry      me  = (Map.Entry)      i.next();
 901             HeapRegionNode hrn = (HeapRegionNode) me.getValue();
 902             if( !visited.contains( hrn ) ) {
 903                 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL, hrn, bw, null, visited );
 904             }
 905         }
 906
 907         // then visit every label node
 908         s = td2ln.entrySet();
 909         i = s.iterator();
 910         while( i.hasNext() ) {
 911             Map.Entry me = (Map.Entry) i.next();
 912             LabelNode ln = (LabelNode) me.getValue();
 913
 914             HeapRegionNode hrn = null;
 915             Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
 916             while( heapRegionsItr.hasNext() ) {
 917                 Map.Entry meH               = (Map.Entry)               heapRegionsItr.next();
 918                 hrn                         = (HeapRegionNode)          meH.getKey();
 919                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
 920
 921                 String edgeLabel = "";
 922                 if( rep.isUnique() ) {
 923                     edgeLabel = "Unique";
 924                 }
 925                 bw.write( "  "        + ln.toString() +
 926                           " -> "      + hrn.toString() +
 927                           "[label=\"" + edgeLabel +
 928                           "\"];\n" );
 929             }
 930         }
 931
 932         bw.write( "}\n" );
 933         bw.close();
 934     }
 935
 936     protected void traverseHeapRegionNodes( int mode,
 937                                             HeapRegionNode hrn,
 938                                             BufferedWriter bw,
 939                                             TempDescriptor td,
 940                                             HashSet<HeapRegionNode> visited
 941                                             ) throws java.io.IOException {
 942
 943         if( visited.contains( hrn ) ) {
 944             return;
 945         }
 946         visited.add( hrn );
 947
 948         switch( mode ) {
 949         case VISIT_HRN_WRITE_FULL:
 950
 951             String attributes = "[";
 952
 953             if( hrn.isSingleObject() ) {
 954                 attributes += "shape=box";
 955             } else {
 956                 attributes += "shape=Msquare";
 957             }
 958
 959             if( hrn.isFlagged() ) {
 960                 attributes += ",style=filled,fillcolor=lightgrey";
 961             }
 962
 963             attributes += ",label=\""           +
 964                           hrn.getDescription()  +
 965                           "\"]";
 966
 967             bw.write( "  " + hrn.toString() + attributes + ";\n" );
 968             break;
 969         }
 970
 971
 972         // go back and let a compile flag control whether the light
 973         // gray "referencer" edges are written to dot files.  It makes
 974         // the graph cluttered but can be useful for debugging.
 975         /*
 976         OwnershipNode onRef  = null;
 977         Iterator      refItr = hrn.iteratorToReferencers();
 978         while( refItr.hasNext() ) {
 979             onRef = (OwnershipNode) refItr.next();
 980
 981             switch( mode ) {
 982             case VISIT_HRN_WRITE_FULL:
 983                 bw.write( "  "                    + hrn.toString() +
 984                           " -> "                  + onRef.toString() +
 985                           "[color=lightgray];\n" );
 986                 break;
 987             }
 988         }
 989         */
 990
 991         HeapRegionNode hrnChild = null;
 992         Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
 993         while( childRegionsItr.hasNext() ) {
 994             Map.Entry me                = (Map.Entry)               childRegionsItr.next();
 995             hrnChild                    = (HeapRegionNode)          me.getKey();
 996             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 997
 998             switch( mode ) {
 999             case VISIT_HRN_WRITE_FULL:
1000                 String edgeLabel = "";
1001                 if( rep.isUnique() ) {
1002                     edgeLabel = "Unique";
1003                 }
1004                 bw.write( "  "        + hrn.toString() +
1005                           " -> "      + hrnChild.toString() +
1006                           "[label=\"" + edgeLabel +
1007                           "\"];\n" );
1008                 break;
1009             }
1010
1011             traverseHeapRegionNodes( mode, hrnChild, bw, td, visited );
1012         }
1013     }
1014 }