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     /*
  11     protected static final int VISIT_HRN_WRITE_FULL      = 0;
  12     protected static final int VISIT_HRN_WRITE_CONDENSED = 1;
  13     */
  14
  15     private int allocationDepth;
  16
  17     //protected static int heapRegionNodeIDs = 0;
  18     public Hashtable<Integer, HeapRegionNode> id2hrn;
  19     public Hashtable<Integer, HeapRegionNode> heapRoots;
  20
  21     //protected static int labelNodeIDs = 0;
  22     public Hashtable<TempDescriptor, LabelNode> td2ln;
  23
  24     //public HashSet<TempDescriptor> analysisRegionLabels;
  25     //protected Hashtable<TempDescriptor, TempDescriptor> linkedRegions;
  26
  27
  28     //public Hashtable<FlatNew, NewCluster> fn2nc;
  29
  30
  31     public OwnershipGraph( int allocationDepth ) {
  32         this.allocationDepth = allocationDepth;
  33
  34         id2hrn    = new Hashtable<Integer,        HeapRegionNode>();
  35         heapRoots = new Hashtable<Integer,        HeapRegionNode>();
  36         td2ln     = new Hashtable<TempDescriptor, LabelNode>();
  37
  38         //analysisRegionLabels = new HashSet<TempDescriptor>();
  39         //linkedRegions = new Hashtable<TempDescriptor, TempDescriptor>();
  40         //fn2nc          = new Hashtable<FlatNew, NewCluster>();
  41     }
  42
  43     protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) {
  44         assert td != null;
  45
  46         if( !td2ln.containsKey( td ) ) {
  47             td2ln.put( td, new LabelNode( td ) );
  48         }
  49
  50         return td2ln.get( td );
  51     }
  52
  53     protected void addReferenceEdge( OwnershipNode  referencer,
  54                                      HeapRegionNode referencee,
  55                                      ReferenceEdgeProperties rep ) {
  56         assert referencer != null;
  57         assert referencee != null;
  58         referencer.addReferencedRegion( referencee, rep );
  59         referencee.addReferencer( referencer );
  60     }
  61
  62     protected void removeReferenceEdge( OwnershipNode  referencer,
  63                                         HeapRegionNode referencee ) {
  64         assert referencer != null;
  65         assert referencee != null;
  66         assert referencer.getReferenceTo( referencee ) != null;
  67         assert referencee.isReferencedBy( referencer );
  68
  69         referencer.removeReferencedRegion( referencee );
  70         referencee.removeReferencer( referencer );
  71     }
  72
  73     protected void clearReferenceEdgesFrom( OwnershipNode referencer ) {
  74         assert referencer != null;
  75
  76         // get a copy of the table to iterate over, otherwise
  77         // we will be trying to take apart the table as we
  78         // are iterating over it, which won't work
  79         Iterator i = referencer.setIteratorToReferencedRegionsClone();
  80         while( i.hasNext() ) {
  81             Map.Entry me = (Map.Entry) i.next();
  82             HeapRegionNode referencee = (HeapRegionNode) me.getKey();
  83             removeReferenceEdge( referencer, referencee );
  84         }
  85     }
  86
  87     protected void clearReferenceEdgesTo( HeapRegionNode referencee ) {
  88         assert referencee != null;
  89
  90         // get a copy of the table to iterate over, otherwise
  91         // we will be trying to take apart the table as we
  92         // are iterating over it, which won't work
  93         Iterator i = referencee.iteratorToReferencersClone();
  94         while( i.hasNext() ) {
  95             OwnershipNode referencer = (OwnershipNode) i.next();
  96             removeReferenceEdge( referencer, referencee );
  97         }
  98     }
  99
 100
 101     /*
 102     ////////////////////////////////////////////////////
 103     //
 104     //  New Reference Methods
 105     //
 106     //  The destination in an assignment statement is
 107     //  going to have new references.  The method of
 108     //  determining the references depends on the type
 109     //  of the FlatNode assignment and the predicates
 110     //  of the nodes and edges involved.
 111     //
 112     ////////////////////////////////////////////////////
 113     public void assignTempToTemp( TempDescriptor src,
 114                                   TempDescriptor dst ) {
 115         LabelNode srcln = getLabelNodeFromTemp( src );
 116         LabelNode dstln = getLabelNodeFromTemp( dst );
 117
 118         clearReferenceEdgesFrom( dstln );
 119         HeapRegionNode newReferencee = null;
 120         Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
 121         while( srcRegionsItr.hasNext() ) {
 122             Map.Entry               me  = (Map.Entry)               srcRegionsItr.next();
 123             newReferencee               = (HeapRegionNode)          me.getKey();
 124             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 125
 126             addReferenceEdge( dstln, newReferencee, rep.copy() );
 127         }
 128     }
 129
 130     public void assignTempToField( TempDescriptor src,
 131                                    TempDescriptor dst,
 132                                    FieldDescriptor fd ) {
 133         LabelNode srcln = getLabelNodeFromTemp( src );
 134         LabelNode dstln = getLabelNodeFromTemp( dst );
 135
 136         clearReferenceEdgesFrom( dstln );
 137
 138         HeapRegionNode hrn = null;
 139         Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
 140         while( srcRegionsItr.hasNext() ) {
 141             Map.Entry me = (Map.Entry)      srcRegionsItr.next();
 142             hrn          = (HeapRegionNode) me.getKey();
 143
 144             HeapRegionNode hrnOneHop = null;
 145             Iterator hrnRegionsItr = hrn.setIteratorToReferencedRegions();
 146             while( hrnRegionsItr.hasNext() ) {
 147                 Map.Entry               meH = (Map.Entry)               hrnRegionsItr.next();
 148                 hrnOneHop                   = (HeapRegionNode)          meH.getKey();
 149                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
 150
 151                 addReferenceEdge( dstln, hrnOneHop, rep.copy() );
 152             }
 153         }
 154     }
 155
 156     public void assignFieldToTemp( TempDescriptor src,
 157                                    TempDescriptor dst,
 158                                    FieldDescriptor fd ) {
 159         LabelNode srcln = getLabelNodeFromTemp( src );
 160         LabelNode dstln = getLabelNodeFromTemp( dst );
 161
 162         HeapRegionNode hrn = null;
 163         Iterator dstRegionsItr = dstln.setIteratorToReferencedRegions();
 164         while( dstRegionsItr.hasNext() ) {
 165             Map.Entry me = (Map.Entry)      dstRegionsItr.next();
 166             hrn          = (HeapRegionNode) me.getKey();
 167
 168             HeapRegionNode hrnSrc = null;
 169             Iterator srcRegionsItr = srcln.setIteratorToReferencedRegions();
 170             while( srcRegionsItr.hasNext() ) {
 171                 Map.Entry               meS = (Map.Entry)               srcRegionsItr.next();
 172                 hrnSrc                      = (HeapRegionNode)          meS.getKey();
 173                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meS.getValue();
 174
 175                 addReferenceEdge( hrn, hrnSrc, rep.copy() );
 176             }
 177         }
 178     }
 179     ////////////////////////////////////////////////////
 180     // end new reference methods
 181     ////////////////////////////////////////////////////
 182
 183     */
 184
 185     protected HeapRegionNode
 186         createNewHeapRegionNode( Integer id,
 187                                  boolean isSingleObject,
 188                                  boolean isFlagged,
 189                                  boolean isNewSummary ) {
 190
 191         if( id == null ) {
 192             //id = new Integer( heapRegionNodeIDs );
 193             //++heapRegionNodeIDs;
 194             id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
 195         }
 196
 197         HeapRegionNode hrn = new HeapRegionNode( id,
 198                                                  isSingleObject,
 199                                                  isFlagged,
 200                                                  isNewSummary );
 201         id2hrn.put( id, hrn );
 202         return hrn;
 203     }
 204
 205     public void parameterAllocation( boolean isTask, TempDescriptor td ) {
 206         assert td != null;
 207
 208         LabelNode      lnParam = getLabelNodeFromTemp( td );
 209         HeapRegionNode hrn     = createNewHeapRegionNode( null, false, isTask, false );
 210         heapRoots.put( hrn.getID(), hrn );
 211
 212         addReferenceEdge( lnParam, hrn, new ReferenceEdgeProperties( false ) );
 213         addReferenceEdge( hrn,     hrn, new ReferenceEdgeProperties( false ) );
 214     }
 215
 216     /*
 217     public void assignTempToNewAllocation( TempDescriptor td, FlatNew fn ) {
 218         assert td != null;
 219         assert fn != null;
 220
 221         NewCluster nc = getNewClusterFromFlatNew( fn );
 222
 223         // move existing references down the line toward
 224         // the oldest element
 225         for( int i = newDepthK - 2; i >= 0; --i ) {
 226             // move references from the ith oldest to the i+1 oldest
 227             HeapRegionNode hrnIthOld = nc.getIthOldest( i );
 228             HeapRegionNode hrnIp1Old = nc.getIthOldest( i + 1 );
 229
 230             // clear i + 1 references in and out, unless it is the
 231             // oldest node which keeps everything
 232             if( !(i + 1 == newDepthK - 1) ) {
 233                 clearReferenceEdgesFrom( hrnIp1Old );
 234                 clearReferenceEdgesTo  ( hrnIp1Old );
 235             }
 236
 237             // copy each edge in and out of i to i + 1
 238             HeapRegionNode hrnReferencee = null;
 239             Iterator       itrReferencee = hrnIthOld.setIteratorToReferencedRegions();
 240             while( itrReferencee.hasNext() ) {
 241                 Map.Entry               me  = (Map.Entry)               itrReferencee.next();
 242                 hrnReferencee               = (HeapRegionNode)          me.getKey();
 243                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 244
 245                 addReferenceEdge( hrnIp1Old, hrnReferencee, rep.copy() );
 246             }
 247
 248             OwnershipNode onReferencer  = null;
 249             Iterator      itrReferencer = hrnIthOld.iteratorToReferencers();
 250             while( itrReferencer.hasNext() ) {
 251                 onReferencer = (OwnershipNode) itrReferencer.next();
 252
 253                 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnIthOld );
 254                 assert rep != null;
 255
 256                 addReferenceEdge( onReferencer, hrnIp1Old, rep.copy() );
 257             }
 258         }
 259
 260         HeapRegionNode hrnNewest    = nc.getIthOldest( 0 );
 261         ReferenceEdgeProperties rep = new ReferenceEdgeProperties( true );
 262         LabelNode dst               = getLabelNodeFromTemp( td );
 263
 264         // clear all references in and out of newest node
 265         clearReferenceEdgesFrom( hrnNewest );
 266         clearReferenceEdgesTo  ( hrnNewest );
 267
 268         // finally assign the temp descriptor to the newest
 269         // node in the new cluster
 270         addReferenceEdge( dst, hrnNewest, rep );
 271     }
 272
 273
 274
 275
 276     public void addAnalysisRegion( TempDescriptor td ) {
 277         assert td != null;
 278         analysisRegionLabels.add( td );
 279     }
 280
 281     // This method gives an existing label node for a temp
 282     // descriptor or creates one if it has not been requested
 283     // yet.  The system is simple because temp descriptors and
 284     // label nodes have a one-to-one mapping and no special
 285     // predicates
 286     protected LabelNode getLabelNodeFromTemp( TempDescriptor td ) {
 287         assert td != null;
 288
 289         if( !td2ln.containsKey( td ) ) {
 290             Integer id = new Integer( labelNodeIDs );
 291             td2ln.put( td, new LabelNode( td ) );
 292             ++labelNodeIDs;
 293         }
 294
 295         return td2ln.get( td );
 296     }
 297     */
 298
 299
 300     // use the allocation site (unique to entire analysis) to
 301     // locate the heap region nodes in this ownership graph
 302     // that should be aged.  The process models the allocation
 303     // of new objects and collects all the oldest allocations
 304     // in a summary node to allow for a finite analysis
 305     public void age( AllocationSite as ) {
 306
 307     }
 308
 309
 310
 311     ////////////////////////////////////////////////////
 312     // in merge() and equals() methods the suffix A
 313     // represents the passed in graph and the suffix
 314     // B refers to the graph in this object
 315     ////////////////////////////////////////////////////
 316
 317     public void merge( OwnershipGraph og ) {
 318
 319         if( og == null ) {
 320           return;
 321         }
 322
 323         mergeOwnershipNodes ( og );
 324         mergeReferenceEdges ( og );
 325         mergeHeapRoots      ( og );
 326         //mergeAnalysisRegions( og );
 327         //mergeNewClusters    ( og );
 328     }
 329
 330     protected void mergeOwnershipNodes( OwnershipGraph og ) {
 331         Set      sA = og.id2hrn.entrySet();
 332         Iterator iA = sA.iterator();
 333         while( iA.hasNext() ) {
 334             Map.Entry      meA  = (Map.Entry)      iA.next();
 335             Integer        idA  = (Integer)        meA.getKey();
 336             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 337
 338             // if this graph doesn't have a node the
 339             // incoming graph has, allocate it
 340             if( !id2hrn.containsKey( idA ) ) {
 341                 HeapRegionNode hrnB = hrnA.copy();
 342                 id2hrn.put( idA, hrnB );
 343             }
 344         }
 345
 346         // now add any label nodes that are in graph B but
 347         // not in A
 348         sA = og.td2ln.entrySet();
 349         iA = sA.iterator();
 350         while( iA.hasNext() ) {
 351             Map.Entry      meA = (Map.Entry)      iA.next();
 352             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 353             LabelNode      lnA = (LabelNode)      meA.getValue();
 354
 355             // if the label doesn't exist in B, allocate and add it
 356             LabelNode lnB = getLabelNodeFromTemp( tdA );
 357         }
 358     }
 359
 360     protected void mergeReferenceEdges( OwnershipGraph og ) {
 361         // there is a data structure for storing label nodes
 362         // retireved by temp descriptors, and a data structure
 363         // for stroing heap region nodes retrieved by integer
 364         // ids.  Because finding edges requires interacting
 365         // with these disparate data structures frequently the
 366         // process is nearly duplicated, one for each
 367
 368         // heap regions
 369         Set      sA = og.id2hrn.entrySet();
 370         Iterator iA = sA.iterator();
 371         while( iA.hasNext() ) {
 372             Map.Entry      meA  = (Map.Entry)      iA.next();
 373             Integer        idA  = (Integer)        meA.getKey();
 374             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 375
 376             HeapRegionNode hrnChildA = null;
 377             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
 378             while( heapRegionsItrA.hasNext() ) {
 379                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
 380                 hrnChildA                    = (HeapRegionNode)          me.getKey();
 381                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
 382
 383                 Integer idChildA = hrnChildA.getID();
 384
 385                 // at this point we know an edge in graph A exists
 386                 // idA -> idChildA, does this exist in B?
 387                 boolean edgeFound = false;
 388                 assert id2hrn.containsKey( idA );
 389                 HeapRegionNode hrnB = id2hrn.get( idA );
 390
 391                 HeapRegionNode hrnChildB = null;
 392                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
 393                 while( heapRegionsItrB.hasNext() ) {
 394                     Map.Entry meC = (Map.Entry)      heapRegionsItrB.next();
 395                     hrnChildB     = (HeapRegionNode) meC.getKey();
 396
 397                     if( hrnChildB.equals( idChildA ) ) {
 398                         edgeFound = true;
 399                     }
 400                 }
 401
 402                 // if the edge from A was not found in B,
 403                 // add it to B.
 404                 if( !edgeFound ) {
 405                     assert id2hrn.containsKey( idChildA );
 406                     hrnChildB = id2hrn.get( idChildA );
 407                     ReferenceEdgeProperties repB = repA.copy();
 408                     addReferenceEdge( hrnB, hrnChildB, repB );
 409                 }
 410                 // otherwise, the edge already existed in both graphs.
 411                 // if this is the case, check to see whether the isUnique
 412                 // predicate of the edges might change
 413                 else
 414                 {
 415
 416                 }
 417             }
 418         }
 419
 420         // and then again with label nodes
 421         sA = og.td2ln.entrySet();
 422         iA = sA.iterator();
 423         while( iA.hasNext() ) {
 424             Map.Entry      meA = (Map.Entry)      iA.next();
 425             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 426             LabelNode      lnA = (LabelNode)      meA.getValue();
 427
 428             HeapRegionNode hrnChildA = null;
 429             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
 430             while( heapRegionsItrA.hasNext() ) {
 431                 Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
 432                 hrnChildA                    = (HeapRegionNode)          meH.getKey();
 433                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
 434
 435                 Integer idChildA = hrnChildA.getID();
 436
 437                 // at this point we know an edge in graph A exists
 438                 // tdA -> idChildA, does this exist in B?
 439                 boolean edgeFound = false;
 440                 assert td2ln.containsKey( tdA );
 441                 LabelNode lnB = td2ln.get( tdA );
 442
 443                 HeapRegionNode hrnChildB = null;
 444                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
 445                 while( heapRegionsItrB.hasNext() ) {
 446                     Map.Entry meC = (Map.Entry)      heapRegionsItrB.next();
 447                     hrnChildB     = (HeapRegionNode) meC.getKey();
 448
 449                     if( hrnChildB.equals( idChildA ) ) {
 450                         edgeFound = true;
 451                     }
 452                 }
 453
 454                 // if the edge from A was not found in B,
 455                 // add it to B.
 456                 if( !edgeFound ) {
 457                     assert id2hrn.containsKey( idChildA );
 458                     hrnChildB = id2hrn.get( idChildA );
 459                     ReferenceEdgeProperties repB = repA.copy();
 460                     addReferenceEdge( lnB, hrnChildB, repB );
 461                 }
 462                 // otherwise, the edge already existed in both graphs.
 463                 // if this is the case, check to see whether the isUnique
 464                 // predicate of the edges might change
 465                 else
 466                 {
 467
 468                 }
 469             }
 470         }
 471     }
 472
 473     protected void mergeHeapRoots( OwnershipGraph og ) {
 474         Set      sA = og.heapRoots.entrySet();
 475         Iterator iA = sA.iterator();
 476         while( iA.hasNext() ) {
 477             Map.Entry      meA  = (Map.Entry)      iA.next();
 478             Integer        idA  = (Integer)        meA.getKey();
 479             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 480
 481             if( !heapRoots.containsKey( idA ) ) {
 482                 assert id2hrn.containsKey( idA );
 483                 HeapRegionNode hrnB = id2hrn.get( idA );
 484                 heapRoots.put( idA, hrnB );
 485             }
 486         }
 487     }
 488
 489     /*
 490     protected void mergeAnalysisRegions( OwnershipGraph og ) {
 491         Iterator iA = og.analysisRegionLabels.iterator();
 492         while( iA.hasNext() ) {
 493             TempDescriptor tdA = (TempDescriptor) iA.next();
 494             if( !analysisRegionLabels.contains( tdA ) ) {
 495                 analysisRegionLabels.add( tdA );
 496             }
 497         }
 498     }
 499
 500     protected void mergeNewClusters( OwnershipGraph og ) {
 501         Set      sA = og.fn2nc.entrySet();
 502         Iterator iA = sA.iterator();
 503         while( iA.hasNext() ) {
 504             Map.Entry  meA = (Map.Entry)  iA.next();
 505             FlatNew    fnA = (FlatNew)    meA.getKey();
 506             NewCluster ncA = (NewCluster) meA.getValue();
 507
 508             // if the A cluster doesn't exist in B we have to construct
 509             // it carefully because the nodes and their edges have already
 510             // been merged above.  Just find the equivalent heap regions
 511             // in the B graph by matching IDs
 512
 513             // if the cluster already exists the edges of its elements
 514             // should already have been merged by the above code that
 515             // does not care whether the regions are part of clusters
 516             NewCluster ncB = null;
 517             if( !fn2nc.containsKey( fnA ) ) {
 518                 ncB = new NewCluster( newDepthK );
 519
 520                 for( int i = 0; i < newDepthK; ++i ) {
 521                     HeapRegionNode hrnA = ncA.getIthOldest( i );
 522
 523                     // this node shouldn't exist in graph B if the
 524                     // corresponding new cluster didn't exist in B
 525                     //assert !id2hrn.containsKey( hrnA.getID() );
 526
 527                     HeapRegionNode hrnB = createNewHeapRegionNode( hrnA.getID(),
 528                                                                    hrnA.isSingleObject(),
 529                                                                    hrnA.isFlagged(),
 530                                                                    hrnA.isNewSummary() );
 531                     ncB.setIthOldest( i, hrnB );
 532                 }
 533
 534                 fn2nc.put( fnA, ncB );
 535             }
 536         }
 537     }
 538     */
 539
 540
 541     // it is necessary in the equals() member functions
 542     // to "check both ways" when comparing the data
 543     // structures of two graphs.  For instance, if all
 544     // edges between heap region nodes in graph A are
 545     // present and equal in graph B it is not sufficient
 546     // to say the graphs are equal.  Consider that there
 547     // may be edges in graph B that are not in graph A.
 548     // the only way to know that all edges in both graphs
 549     // are equally present is to iterate over both data
 550     // structures and compare against the other graph.
 551     public boolean equals( OwnershipGraph og ) {
 552
 553         if( og == null ) {
 554           return false;
 555         }
 556
 557         if( !areHeapRegionNodesEqual( og ) ) {
 558             return false;
 559         }
 560
 561         if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
 562             return false;
 563         }
 564
 565         if( !areLabelNodesEqual( og ) ) {
 566             return false;
 567         }
 568
 569         if( !areLabelToHeapRegionEdgesEqual( og ) ) {
 570             return false;
 571         }
 572
 573         if( !areHeapRootsEqual( og ) ) {
 574             return false;
 575         }
 576
 577         /*
 578         if( !areAnalysisRegionLabelsEqual( og ) ) {
 579             return false;
 580         }
 581
 582         if( !areNewClustersEqual( og ) ) {
 583             return false;
 584         }
 585         */
 586
 587         return true;
 588     }
 589
 590     protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
 591         // check all nodes in A for presence in graph B
 592         Set      sA = og.id2hrn.entrySet();
 593         Iterator iA = sA.iterator();
 594         while( iA.hasNext() ) {
 595             Map.Entry      meA  = (Map.Entry)      iA.next();
 596             Integer        idA  = (Integer)        meA.getKey();
 597             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 598
 599             if( !id2hrn.containsKey( idA ) ) {
 600                 return false;
 601             }
 602
 603             HeapRegionNode hrnB = og.id2hrn.get( idA );
 604             if( !hrnA.equals( hrnB ) ) {
 605                 return false;
 606             }
 607         }
 608
 609         // then check all nodes in B verses graph A
 610         Set      sB = id2hrn.entrySet();
 611         Iterator iB = sB.iterator();
 612         while( iB.hasNext() ) {
 613             Map.Entry      meB  = (Map.Entry)      iB.next();
 614             Integer        idB  = (Integer)        meB.getKey();
 615             HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
 616
 617             if( !og.id2hrn.containsKey( idB ) ) {
 618                 return false;
 619             }
 620
 621             // we should have already checked the equality
 622             // of this pairing in the last pass if they both
 623             // exist so assert that they are equal now
 624             HeapRegionNode hrnA = og.id2hrn.get( idB );
 625             assert hrnB.equals( hrnA );
 626         }
 627
 628         return true;
 629     }
 630
 631     protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
 632         Set      sA = og.id2hrn.entrySet();
 633         Iterator iA = sA.iterator();
 634         while( iA.hasNext() ) {
 635             Map.Entry      meA  = (Map.Entry)      iA.next();
 636             Integer        idA  = (Integer)        meA.getKey();
 637             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 638
 639             // we should have already checked that the same
 640             // heap regions exist in both graphs
 641             assert id2hrn.containsKey( idA );
 642
 643             // and are their edges the same?  first check every
 644             // edge in A for presence and equality in B
 645             HeapRegionNode hrnChildA = null;
 646             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
 647             while( heapRegionsItrA.hasNext() ) {
 648                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
 649                 hrnChildA                    = (HeapRegionNode)          me.getKey();
 650                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
 651
 652                 Integer idChildA = hrnChildA.getID();
 653                 assert id2hrn.containsKey( idChildA );
 654
 655                 // at this point we know an edge in graph A exists
 656                 // idA -> idChildA, does this edge exist in B?
 657                 boolean edgeFound = false;
 658                 HeapRegionNode hrnB = id2hrn.get( idA );
 659
 660                 HeapRegionNode hrnChildB = null;
 661                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
 662                 while( heapRegionsItrB.hasNext() ) {
 663                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
 664                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
 665                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
 666
 667                     if( idChildA.equals( hrnChildB.getID() ) ) {
 668                         if( !repA.equals( repB ) ) {
 669                             return false;
 670                         }
 671                         edgeFound = true;
 672                     }
 673                 }
 674
 675                 if( !edgeFound ) {
 676                     return false;
 677                 }
 678             }
 679
 680             // then check every edge in B for presence in A, starting
 681             // from the same parent HeapRegionNode
 682             HeapRegionNode hrnB = id2hrn.get( idA );
 683
 684             HeapRegionNode hrnChildB = null;
 685             Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
 686             while( heapRegionsItrB.hasNext() ) {
 687                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
 688                 hrnChildB                    = (HeapRegionNode)          me.getKey();
 689                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
 690
 691                 Integer idChildB = hrnChildB.getID();
 692
 693                 // at this point we know an edge in graph B exists
 694                 // idB -> idChildB, does this edge exist in A?
 695                 boolean edgeFound = false;
 696
 697                 hrnChildA       = null;
 698                 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
 699                 while( heapRegionsItrA.hasNext() ) {
 700                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
 701                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
 702                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
 703
 704                     if( idChildB.equals( hrnChildA.getID() ) ) {
 705                         assert repB.equals( repA );
 706                         edgeFound = true;
 707                     }
 708                 }
 709
 710                 if( !edgeFound ) {
 711                     return false;
 712                 }
 713             }
 714         }
 715
 716         return true;
 717     }
 718
 719     protected boolean areLabelNodesEqual( OwnershipGraph og ) {
 720         // are all label nodes in A also in graph B?
 721         Set      sA = og.td2ln.entrySet();
 722         Iterator iA = sA.iterator();
 723         while( iA.hasNext() ) {
 724             Map.Entry      meA = (Map.Entry)      iA.next();
 725             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 726
 727             if( !td2ln.containsKey( tdA ) ) {
 728                 return false;
 729             }
 730         }
 731
 732         // are all label nodes in B also in A?
 733         Set      sB = td2ln.entrySet();
 734         Iterator iB = sB.iterator();
 735         while( iB.hasNext() ) {
 736             Map.Entry      meB = (Map.Entry)      iB.next();
 737             TempDescriptor tdB = (TempDescriptor) meB.getKey();
 738
 739             if( !og.td2ln.containsKey( tdB ) ) {
 740                 return false;
 741             }
 742         }
 743
 744         return true;
 745     }
 746
 747     protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
 748         Set      sA = og.td2ln.entrySet();
 749         Iterator iA = sA.iterator();
 750         while( iA.hasNext() ) {
 751             Map.Entry      meA = (Map.Entry)      iA.next();
 752             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 753             LabelNode      lnA = (LabelNode)      meA.getValue();
 754
 755             // we should have already checked that the same
 756             // label nodes exist in both graphs
 757             assert td2ln.containsKey( tdA );
 758
 759             // and are their edges the same?  first check every
 760             // edge in A for presence and equality in B
 761             HeapRegionNode hrnChildA = null;
 762             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
 763             while( heapRegionsItrA.hasNext() ) {
 764                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
 765                 hrnChildA                    = (HeapRegionNode)          me.getKey();
 766                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
 767
 768                 Integer idChildA = hrnChildA.getID();
 769                 assert id2hrn.containsKey( idChildA );
 770
 771                 // at this point we know an edge in graph A exists
 772                 // tdA -> idChildA, does this edge exist in B?
 773                 boolean edgeFound = false;
 774                 LabelNode lnB = td2ln.get( tdA );
 775
 776                 HeapRegionNode hrnChildB = null;
 777                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
 778                 while( heapRegionsItrB.hasNext() ) {
 779                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
 780                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
 781                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
 782
 783                     if( idChildA.equals( hrnChildB.getID() ) ) {
 784                         if( !repA.equals( repB ) ) {
 785                             return false;
 786                         }
 787                         edgeFound = true;
 788                     }
 789                 }
 790
 791                 if( !edgeFound ) {
 792                     return false;
 793                 }
 794             }
 795
 796             // then check every edge in B for presence in A, starting
 797             // from the same parent LabelNode
 798             LabelNode lnB = td2ln.get( tdA );
 799
 800             HeapRegionNode hrnChildB = null;
 801             Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
 802             while( heapRegionsItrB.hasNext() ) {
 803                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
 804                 hrnChildB                    = (HeapRegionNode)          me.getKey();
 805                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
 806
 807                 Integer idChildB = hrnChildB.getID();
 808
 809                 // at this point we know an edge in graph B exists
 810                 // tdB -> idChildB, does this edge exist in A?
 811                 boolean edgeFound = false;
 812
 813                 hrnChildA       = null;
 814                 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
 815                 while( heapRegionsItrA.hasNext() ) {
 816                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
 817                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
 818                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
 819
 820                     if( idChildB.equals( hrnChildA.getID() ) ) {
 821                         assert repB.equals( repA );
 822                         edgeFound = true;
 823                     }
 824                 }
 825
 826                 if( !edgeFound ) {
 827                     return false;
 828                 }
 829             }
 830         }
 831
 832         return true;
 833     }
 834
 835     protected boolean areHeapRootsEqual( OwnershipGraph og ) {
 836         if( og.heapRoots.size() != heapRoots.size() ) {
 837             return false;
 838         }
 839
 840         Set      sA = og.heapRoots.entrySet();
 841         Iterator iA = sA.iterator();
 842         while( iA.hasNext() ) {
 843             Map.Entry meA = (Map.Entry) iA.next();
 844             Integer   idA = (Integer)   meA.getKey();
 845
 846             if( !heapRoots.containsKey( idA ) ) {
 847                 return false;
 848             }
 849         }
 850
 851         Set      sB = heapRoots.entrySet();
 852         Iterator iB = sB.iterator();
 853         while( iB.hasNext() ) {
 854             Map.Entry meB = (Map.Entry) iB.next();
 855             Integer   idB = (Integer)   meB.getKey();
 856
 857             if( !heapRoots.containsKey( idB ) ) {
 858                 return false;
 859             }
 860         }
 861
 862         return true;
 863     }
 864
 865     /*
 866     protected boolean areAnalysisRegionLabelsEqual( OwnershipGraph og ) {
 867         if( og.analysisRegionLabels.size() != analysisRegionLabels.size() ) {
 868             return false;
 869         }
 870
 871         Iterator iA = og.analysisRegionLabels.iterator();
 872         while( iA.hasNext() ) {
 873             TempDescriptor tdA = (TempDescriptor) iA.next();
 874             if( !analysisRegionLabels.contains( tdA ) ) {
 875                 return false;
 876             }
 877         }
 878
 879         Iterator iB = analysisRegionLabels.iterator();
 880         while( iB.hasNext() ) {
 881             TempDescriptor tdB = (TempDescriptor) iB.next();
 882             if( !og.analysisRegionLabels.contains( tdB ) ) {
 883                 return false;
 884             }
 885         }
 886
 887         return true;
 888     }
 889
 890     protected boolean areNewClustersEqual( OwnershipGraph og ) {
 891         if( og.fn2nc.size() != fn2nc.size() ) {
 892             return false;
 893         }
 894
 895         Set      sA = og.fn2nc.entrySet();
 896         Iterator iA = sA.iterator();
 897         while( iA.hasNext() ) {
 898             Map.Entry meA = (Map.Entry) iA.next();
 899             FlatNew   fnA = (FlatNew)   meA.getKey();
 900
 901             if( !fn2nc.containsKey( fnA ) ) {
 902                 return false;
 903             }
 904         }
 905
 906         Set      sB = fn2nc.entrySet();
 907         Iterator iB = sB.iterator();
 908         while( iB.hasNext() ) {
 909             Map.Entry meB = (Map.Entry) iB.next();
 910             FlatNew   fnB = (FlatNew)   meB.getKey();
 911
 912             if( !fn2nc.containsKey( fnB ) ) {
 913                 return false;
 914             }
 915         }
 916
 917         return true;
 918     }
 919     */
 920
 921     public void writeGraph( String graphName ) throws java.io.IOException {
 922
 923         BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
 924         bw.write( "digraph "+graphName+" {\n" );
 925
 926         /*
 927         // first write out new clusters
 928         Integer newClusterNum = new Integer( 100 );
 929         Set      s = fn2nc.entrySet();
 930         Iterator i = s.iterator();
 931         while( i.hasNext() ) {
 932             Map.Entry  me = (Map.Entry)  i.next();
 933             FlatNew    fn = (FlatNew)    me.getKey();
 934             NewCluster nc = (NewCluster) me.getValue();
 935
 936             bw.write( "  subgraph cluster" + newClusterNum + " {\n"     );
 937             bw.write( "    color=blue;\n"                      );
 938             bw.write( "    rankdir=LR;\n"                      );
 939             bw.write( "    label=\"" + fn.toString() + "\";\n" );
 940
 941             for( int j = 0; j < newDepthK; ++j ) {
 942                 HeapRegionNode hrn = nc.getIthOldest( j );
 943                 bw.write( "    " + hrn.toString() + ";\n" );
 944             }
 945
 946             bw.write( "  }\n" );
 947         }
 948
 949         // then visit every heap region node
 950         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
 951
 952         s = heapRoots.entrySet();
 953         i = s.iterator();
 954         while( i.hasNext() ) {
 955             Map.Entry      me  = (Map.Entry)      i.next();
 956             HeapRegionNode hrn = (HeapRegionNode) me.getValue();
 957             traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL, hrn, bw, null, visited );
 958         }
 959
 960         // then visit every label node
 961         s = td2ln.entrySet();
 962         i = s.iterator();
 963         while( i.hasNext() ) {
 964             Map.Entry me = (Map.Entry) i.next();
 965             LabelNode ln = (LabelNode) me.getValue();
 966
 967             HeapRegionNode hrn = null;
 968             Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
 969             while( heapRegionsItr.hasNext() ) {
 970                 Map.Entry meH               = (Map.Entry)               heapRegionsItr.next();
 971                 hrn                         = (HeapRegionNode)          meH.getKey();
 972                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
 973
 974                 String edgeLabel = "";
 975                 if( rep.isUnique() ) {
 976                     edgeLabel = "Unique";
 977                 }
 978                 bw.write( "  "        + ln.toString() +
 979                           " -> "      + hrn.toString() +
 980                           "[label=\"" + edgeLabel +
 981                           "\"];\n" );
 982             }
 983         }
 984         */
 985
 986         bw.write( "}\n" );
 987         bw.close();
 988     }
 989
 990     /*
 991     public void writeCondensedAnalysis( String graphName ) throws java.io.IOException {
 992         BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
 993         bw.write( "graph "+graphName+" {\n" );
 994
 995         // find linked regions
 996         Iterator i = analysisRegionLabels.iterator();
 997         while( i.hasNext() ) {
 998             TempDescriptor td = (TempDescriptor) i.next();
 999             bw.write( "  "+td.getSymbol()+";\n" );
1000             LabelNode ln = getLabelNodeFromTemp( td );
1001
1002             HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1003
1004             HeapRegionNode hrn = null;
1005             Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1006             while( heapRegionsItr.hasNext() ) {
1007                 Map.Entry me                = (Map.Entry)               heapRegionsItr.next();
1008                 hrn                         = (HeapRegionNode)          me.getKey();
1009                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1010
1011                 traverseHeapRegionNodes( VISIT_HRN_WRITE_CONDENSED, hrn, bw, td, visited );
1012             }
1013         }
1014
1015         // write out linked regions
1016         Set      s   = linkedRegions.entrySet();
1017         Iterator lri = s.iterator();
1018         while( lri.hasNext() ) {
1019             Map.Entry      me = (Map.Entry)      lri.next();
1020             TempDescriptor t1 = (TempDescriptor) me.getKey();
1021             TempDescriptor t2 = (TempDescriptor) me.getValue();
1022             bw.write( "  "+t1.getSymbol()+" -- "+t2.getSymbol()+";\n" );
1023         }
1024
1025         bw.write( "}\n" );
1026         bw.close();
1027     }
1028
1029     protected void traverseHeapRegionNodes( int mode,
1030                                             HeapRegionNode hrn,
1031                                             BufferedWriter bw,
1032                                             TempDescriptor td,
1033                                             HashSet<HeapRegionNode> visited
1034                                             ) throws java.io.IOException {
1035
1036         if( visited.contains( hrn ) ) {
1037             return;
1038         }
1039         visited.add( hrn );
1040
1041         switch( mode ) {
1042         case VISIT_HRN_WRITE_FULL:
1043
1044             String isSingleObjectStr = "isSingleObject";
1045             if( !hrn.isSingleObject() ) {
1046                 isSingleObjectStr = "!isSingleObject";
1047             }
1048
1049             String isFlaggedStr = "isFlagged";
1050             if( !hrn.isFlagged() ) {
1051                 isFlaggedStr = "!isFlagged";
1052             }
1053
1054             String isNewSummaryStr = "isNewSummary";
1055             if( !hrn.isNewSummary() ) {
1056                 isNewSummaryStr = "!isNewSummary";
1057             }
1058
1059             bw.write( "  "                  + hrn.toString() +
1060                       "[shape=box,label=\"" + isFlaggedStr +
1061                       "\\n"                 + isSingleObjectStr +
1062                       "\\n"                 + isNewSummaryStr +
1063                       "\"];\n" );
1064             break;
1065
1066         case VISIT_HRN_WRITE_CONDENSED:
1067
1068             Iterator i = hrn.iteratorToAnalysisRegionAliases();
1069             while( i.hasNext() ) {
1070                 TempDescriptor tdn = (TempDescriptor) i.next();
1071
1072                 // only add a linked region if the td passed in and
1073                 // the td's aliased to this node haven't already been
1074                 // added as linked regions
1075                 TempDescriptor tdAlias = null;
1076                 if( linkedRegions.containsKey( td ) ) {
1077                     tdAlias = linkedRegions.get( td );
1078                 }
1079
1080                 TempDescriptor tdnAlias = null;
1081                 if( linkedRegions.containsKey( tdn ) ) {
1082                     tdnAlias = linkedRegions.get( tdn );
1083                 }
1084
1085                 if( tdn != tdAlias && td != tdnAlias ) {
1086                     linkedRegions.put( td, tdn );
1087                 }
1088             }
1089
1090             hrn.addAnalysisRegionAlias( td );
1091             break;
1092         }
1093
1094
1095         OwnershipNode onRef = null;
1096         Iterator refItr = hrn.iteratorToReferencers();
1097         while( refItr.hasNext() ) {
1098             onRef = (OwnershipNode) refItr.next();
1099
1100             switch( mode ) {
1101             case VISIT_HRN_WRITE_FULL:
1102                 bw.write( "  "                    + hrn.toString() +
1103                           " -> "                  + onRef.toString() +
1104                           "[color=lightgray];\n" );
1105                 break;
1106             }
1107         }
1108
1109
1110         HeapRegionNode hrnChild = null;
1111         Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1112         while( childRegionsItr.hasNext() ) {
1113             Map.Entry me                = (Map.Entry)               childRegionsItr.next();
1114             hrnChild                    = (HeapRegionNode)          me.getKey();
1115             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1116
1117             switch( mode ) {
1118             case VISIT_HRN_WRITE_FULL:
1119                 String edgeLabel = "";
1120                 if( rep.isUnique() ) {
1121                     edgeLabel = "Unique";
1122                 }
1123                 bw.write( "  "        + hrn.toString() +
1124                           " -> "      + hrnChild.toString() +
1125                           "[label=\"" + edgeLabel +
1126                           "\"];\n" );
1127                 break;
1128             }
1129
1130             traverseHeapRegionNodes( mode, hrnChild, bw, td, visited );
1131         }
1132     }
1133     */
1134
1135 }