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