Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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