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.unionUpArity( R );
 403                 ChangeTupleSet Cx = R.unionUpArity( 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
 609             addReferenceEdge( onReferencer, hrnSummary, rep.copy() );
 610         }
 611
 612
 613         // then move down the line of heap region nodes
 614         // clobbering the ith and transferring all references
 615         // to and from i-1 to node i.  Note that this clobbers
 616         // the oldest node (alpha_k) that was just merged into
 617         // the summary above and should move everything from
 618         // alpha_0 to alpha_1 before we finish
 619         for( int i = allocationDepth - 1; i > 0; --i ) {
 620
 621             // move references from the i-1 oldest to the ith oldest
 622             Integer        idIth     = as.getIthOldest( i );
 623             HeapRegionNode hrnI      = id2hrn.get( idIth );
 624             Integer        idImin1th = as.getIthOldest( i - 1 );
 625             HeapRegionNode hrnImin1  = id2hrn.get( idImin1th );
 626
 627             // clear references in and out of node i
 628             clearReferenceEdgesFrom( hrnI );
 629             clearReferenceEdgesTo  ( hrnI );
 630
 631             // copy each edge in and out of i-1 to i
 632             hrnReferencee = null;
 633             itrReferencee = hrnImin1.setIteratorToReferencedRegions();
 634             while( itrReferencee.hasNext() ) {
 635                 Map.Entry               me  = (Map.Entry)               itrReferencee.next();
 636                 hrnReferencee               = (HeapRegionNode)          me.getKey();
 637                 ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
 638
 639                 addReferenceEdge( hrnI, hrnReferencee, rep.copy() );
 640             }
 641
 642             onReferencer  = null;
 643             itrReferencer = hrnImin1.iteratorToReferencers();
 644             while( itrReferencer.hasNext() ) {
 645                 onReferencer = (OwnershipNode) itrReferencer.next();
 646
 647                 ReferenceEdgeProperties rep = onReferencer.getReferenceTo( hrnImin1 );
 648                 assert rep != null;
 649
 650                 addReferenceEdge( onReferencer, hrnI, rep.copy() );
 651             }
 652         }
 653
 654         // as stated above, the newest node alpha_0 should have had its
 655         // references moved over to alpha_1, so we can wipe alpha_0 clean
 656         // in preparation for operations that want to reference a freshly
 657         // allocated object from this allocation site
 658         Integer        id0th = as.getIthOldest( 0 );
 659         HeapRegionNode hrn0  = id2hrn.get( id0th );
 660
 661         // the loop to move references from i-1 to i should
 662         // have touched this node, therefore assert it is non-null
 663         assert hrn0 != null;
 664
 665         // clear all references in and out of newest node
 666         clearReferenceEdgesFrom( hrn0 );
 667         clearReferenceEdgesTo  ( hrn0 );
 668     }
 669
 670
 671     // some notes:
 672     // the heap regions that are specially allocated as multiple-object
 673     // regions for method parameters need to be remembered in order to
 674     // resolve a function call.  So actually, we need a mapping from
 675     // caller argument descriptors to the callee parameter heap regions
 676     // to apply reference edges in the callee to the caller graph.
 677     //
 678     // also, Constructors and virtual dispatch methods have a "this"
 679     // argument that make the mapping of arguments to parameters a little
 680     // tricky.  What happens to that this region?
 681
 682
 683     public void resolveMethodCall( FlatCall                fc,
 684                                    boolean                 isStatic,
 685                                    FlatMethod              fm,
 686                                    OwnershipGraph          ogCallee ) { //,
 687         //HashSet<AllocationSite> allocSiteSet ) {
 688
 689         // first age all of the allocation sites from
 690         // the callee graph in this graph
 691         Iterator i = ogCallee.allocationSites.iterator();
 692         while( i.hasNext() ) {
 693             AllocationSite allocSite = (AllocationSite) i.next();
 694             this.age( allocSite );
 695         }
 696
 697         // in non-static methods there is a "this" pointer
 698         // that should be taken into account
 699         if( isStatic ) {
 700             assert fc.numArgs()     == fm.numParameters();
 701         } else {
 702             assert fc.numArgs() + 1 == fm.numParameters();
 703         }
 704
 705         // the heap regions represented by the arguments (caller graph)
 706         // and heap regions for the parameters (callee graph)
 707         // don't correspond to each other by heap region ID.  In fact,
 708         // an argument label node can be referencing several heap regions
 709         // so the parameter label always references a multiple-object
 710         // heap region in order to handle the range of possible contexts
 711         // for a method call.  This means we need to make a special mapping
 712         // of argument->parameter regions in order to update the caller graph
 713
 714         // for every heap region->heap region edge in the
 715         // callee graph, create the matching edge or edges
 716         // in the caller graph
 717         Set      sCallee = ogCallee.id2hrn.entrySet();
 718         Iterator iCallee = sCallee.iterator();
 719         while( iCallee.hasNext() ) {
 720             Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
 721             Integer        idCallee  = (Integer)        meCallee.getKey();
 722             HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
 723
 724             HeapRegionNode hrnChildCallee = null;
 725             Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
 726             while( heapRegionsItrCallee.hasNext() ) {
 727                 Map.Entry me                 = (Map.Entry)               heapRegionsItrCallee.next();
 728                 hrnChildCallee               = (HeapRegionNode)          me.getKey();
 729                 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
 730
 731                 Integer idChildCallee = hrnChildCallee.getID();
 732
 733                 // only address this edge if it is not a special reflexive edge
 734                 if( !repC.isInitialParamReflexive() ) {
 735
 736                     // now we know that in the callee method's ownership graph
 737                     // there is a heap region->heap region reference edge given
 738                     // by heap region pointers:
 739                     // hrnCallee -> heapChildCallee
 740                     //
 741                     // or by the ownership-graph independent ID's:
 742                     // idCallee -> idChildCallee
 743                     //
 744                     // So now make a set of possible source heaps in the caller graph
 745                     // and a set of destination heaps in the caller graph, and make
 746                     // a reference edge in the caller for every possible (src,dst) pair
 747                     if( !ogCallee.id2hrn.contains( idChildCallee ) ) {
 748                         //System.out.println( "Houston, we got a problem." );
 749                         //System.out.println( "idCallee is "+idCallee );
 750                         //System.out.println( "idChildCallee is "+idChildCallee );
 751
 752                         try {
 753                             writeGraph( "caller", false, false );
 754                             ogCallee.writeGraph( "callee", false, false );
 755                         } catch( IOException e ) {}
 756                     }
 757
 758                     HashSet<HeapRegionNode> possibleCallerSrcs =
 759                         getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 760                                                              idCallee,
 761                                                              fc,
 762                                                              isStatic );
 763
 764                     HashSet<HeapRegionNode> possibleCallerDsts =
 765                         getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 766                                                              idChildCallee,
 767                                                              fc,
 768                                                              isStatic );
 769
 770                     // make every possible pair of {srcSet} -> {dstSet} edges in the caller
 771                     Iterator srcItr = possibleCallerSrcs.iterator();
 772                     while( srcItr.hasNext() ) {
 773                         HeapRegionNode src = (HeapRegionNode) srcItr.next();
 774
 775                         Iterator dstItr = possibleCallerDsts.iterator();
 776                         while( dstItr.hasNext() ) {
 777                             HeapRegionNode dst = (HeapRegionNode) dstItr.next();
 778
 779                             addReferenceEdge( src, dst, repC.copy() );
 780                         }
 781                     }
 782                 }
 783             }
 784         }
 785     }
 786
 787     private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
 788                                                                          Integer        idCallee,
 789                                                                          FlatCall       fc,
 790                                                                          boolean        isStatic ) {
 791
 792         HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
 793
 794         if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
 795             // the heap region that is part of this
 796             // reference edge won't have a matching ID in the
 797             // caller graph because it is specifically allocated
 798             // for a particular parameter.  Use that information
 799             // to find the corresponding argument label in the
 800             // caller in order to create the proper reference edge
 801             // or edges.
 802             assert !id2hrn.containsKey( idCallee );
 803
 804             Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
 805             TempDescriptor argTemp;
 806
 807             // now depending on whether the callee is static or not
 808             // we need to account for a "this" argument in order to
 809             // find the matching argument in the caller context
 810             if( isStatic ) {
 811                 argTemp = fc.getArg( paramIndex );
 812             } else {
 813                 if( paramIndex == 0 ) {
 814                     argTemp = fc.getThis();
 815                 } else {
 816                     argTemp = fc.getArg( paramIndex - 1 );
 817                 }
 818             }
 819
 820             LabelNode argLabel = getLabelNodeFromTemp( argTemp );
 821             Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
 822             while( argHeapRegionsItr.hasNext() ) {
 823                 Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
 824                 HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
 825                 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
 826
 827                 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
 828             }
 829
 830         } else {
 831             // this heap region is not a parameter, so it should
 832             // have a matching heap region in the caller graph
 833             assert id2hrn.containsKey( idCallee );
 834             possibleCallerHRNs.add( id2hrn.get( idCallee ) );
 835         }
 836
 837         return possibleCallerHRNs;
 838     }
 839
 840
 841
 842     ////////////////////////////////////////////////////
 843     // in merge() and equals() methods the suffix A
 844     // represents the passed in graph and the suffix
 845     // B refers to the graph in this object
 846     // Merging means to take the incoming graph A and
 847     // merge it into B, so after the operation graph B
 848     // is the final result.
 849     ////////////////////////////////////////////////////
 850     public void merge( OwnershipGraph og ) {
 851
 852         if( og == null ) {
 853           return;
 854         }
 855
 856         mergeOwnershipNodes ( og );
 857         mergeReferenceEdges ( og );
 858         mergeId2paramIndex  ( og );
 859         mergeAllocationSites( og );
 860     }
 861
 862
 863     protected void mergeOwnershipNodes( OwnershipGraph og ) {
 864         Set      sA = og.id2hrn.entrySet();
 865         Iterator iA = sA.iterator();
 866         while( iA.hasNext() ) {
 867             Map.Entry      meA  = (Map.Entry)      iA.next();
 868             Integer        idA  = (Integer)        meA.getKey();
 869             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 870
 871             // if this graph doesn't have a node the
 872             // incoming graph has, allocate it
 873             if( !id2hrn.containsKey( idA ) ) {
 874                 HeapRegionNode hrnB = hrnA.copy();
 875                 id2hrn.put( idA, hrnB );
 876
 877             } else {
 878                 // otherwise this is a node present in both graphs
 879                 // so make the new reachability set a union of the
 880                 // nodes' reachability sets
 881                 HeapRegionNode hrnB = id2hrn.get( idA );
 882                 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
 883             }
 884         }
 885
 886         // now add any label nodes that are in graph B but
 887         // not in A
 888         sA = og.td2ln.entrySet();
 889         iA = sA.iterator();
 890         while( iA.hasNext() ) {
 891             Map.Entry      meA = (Map.Entry)      iA.next();
 892             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 893             LabelNode      lnA = (LabelNode)      meA.getValue();
 894
 895             // if the label doesn't exist in B, allocate and add it
 896             LabelNode lnB = getLabelNodeFromTemp( tdA );
 897         }
 898     }
 899
 900     protected void mergeReferenceEdges( OwnershipGraph og ) {
 901         // there is a data structure for storing label nodes
 902         // retireved by temp descriptors, and a data structure
 903         // for stroing heap region nodes retrieved by integer
 904         // ids.  Because finding edges requires interacting
 905         // with these disparate data structures frequently the
 906         // process is nearly duplicated, one for each structure
 907         // that stores edges
 908
 909         // heap regions
 910         Set      sA = og.id2hrn.entrySet();
 911         Iterator iA = sA.iterator();
 912         while( iA.hasNext() ) {
 913             Map.Entry      meA  = (Map.Entry)      iA.next();
 914             Integer        idA  = (Integer)        meA.getKey();
 915             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
 916
 917             HeapRegionNode hrnChildA = null;
 918             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
 919             while( heapRegionsItrA.hasNext() ) {
 920                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
 921                 hrnChildA                    = (HeapRegionNode)          me.getKey();
 922                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
 923
 924                 Integer idChildA = hrnChildA.getID();
 925
 926                 // at this point we know an edge in graph A exists
 927                 // idA -> idChildA, does this exist in B?
 928                 boolean edgeFound = false;
 929                 assert id2hrn.containsKey( idA );
 930                 HeapRegionNode hrnB = id2hrn.get( idA );
 931
 932                 HeapRegionNode          hrnChildB = null;
 933                 ReferenceEdgeProperties repB      = null;
 934                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
 935                 while( heapRegionsItrB.hasNext() ) {
 936                     Map.Entry meC               = (Map.Entry)               heapRegionsItrB.next();
 937                     hrnChildB                   = (HeapRegionNode)          meC.getKey();
 938                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
 939
 940                     if( hrnChildB.equals( idChildA ) ) {
 941                         edgeFound = true;
 942                         repB      = rep;
 943                     }
 944                 }
 945
 946                 // if the edge from A was not found in B,
 947                 // add it to B.
 948                 if( !edgeFound ) {
 949                     assert id2hrn.containsKey( idChildA );
 950                     hrnChildB = id2hrn.get( idChildA );
 951                     repB = repA.copy();
 952                     addReferenceEdge( hrnB, hrnChildB, repB );
 953                 }
 954                 // otherwise, the edge already existed in both graphs
 955                 // so merge their reachability sets
 956                 else {
 957                     // just replace this beta set with the union
 958                     assert repB != null;
 959                     repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
 960                 }
 961             }
 962         }
 963
 964         // and then again with label nodes
 965         sA = og.td2ln.entrySet();
 966         iA = sA.iterator();
 967         while( iA.hasNext() ) {
 968             Map.Entry      meA = (Map.Entry)      iA.next();
 969             TempDescriptor tdA = (TempDescriptor) meA.getKey();
 970             LabelNode      lnA = (LabelNode)      meA.getValue();
 971
 972             HeapRegionNode hrnChildA = null;
 973             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
 974             while( heapRegionsItrA.hasNext() ) {
 975                 Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
 976                 hrnChildA                    = (HeapRegionNode)          meH.getKey();
 977                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
 978
 979                 Integer idChildA = hrnChildA.getID();
 980
 981                 // at this point we know an edge in graph A exists
 982                 // tdA -> idChildA, does this exist in B?
 983                 boolean edgeFound = false;
 984                 assert td2ln.containsKey( tdA );
 985                 LabelNode lnB = td2ln.get( tdA );
 986
 987                 HeapRegionNode          hrnChildB = null;
 988                 ReferenceEdgeProperties repB      = null;
 989                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
 990                 while( heapRegionsItrB.hasNext() ) {
 991                     Map.Entry meC               = (Map.Entry)               heapRegionsItrB.next();
 992                     hrnChildB                   = (HeapRegionNode)          meC.getKey();
 993                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
 994
 995                     if( hrnChildB.equals( idChildA ) ) {
 996                         edgeFound = true;
 997                         repB      = rep;
 998                     }
 999                 }
1000
1001                 // if the edge from A was not found in B,
1002                 // add it to B.
1003                 if( !edgeFound ) {
1004                     assert id2hrn.containsKey( idChildA );
1005                     hrnChildB = id2hrn.get( idChildA );
1006                     repB = repA.copy();
1007                     addReferenceEdge( lnB, hrnChildB, repB );
1008                 }
1009                 // otherwise, the edge already existed in both graphs
1010                 // so merge the reachability sets
1011                 else {
1012                     // just replace this beta set with the union
1013                     assert repB != null;
1014                     repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
1015                 }
1016             }
1017         }
1018     }
1019
1020     // you should only merge ownership graphs that have the
1021     // same number of parameters, or if one or both parameter
1022     // index tables are empty
1023     protected void mergeId2paramIndex( OwnershipGraph og ) {
1024         if( id2paramIndex.size() == 0 ) {
1025             id2paramIndex = og.id2paramIndex;
1026             paramIndex2id = og.paramIndex2id;
1027             return;
1028         }
1029
1030         if( og.id2paramIndex.size() == 0 ) {
1031             return;
1032         }
1033
1034         assert id2paramIndex.size() == og.id2paramIndex.size();
1035     }
1036
1037     protected void mergeAllocationSites( OwnershipGraph og ) {
1038         allocationSites.addAll( og.allocationSites );
1039     }
1040
1041
1042
1043     // it is necessary in the equals() member functions
1044     // to "check both ways" when comparing the data
1045     // structures of two graphs.  For instance, if all
1046     // edges between heap region nodes in graph A are
1047     // present and equal in graph B it is not sufficient
1048     // to say the graphs are equal.  Consider that there
1049     // may be edges in graph B that are not in graph A.
1050     // the only way to know that all edges in both graphs
1051     // are equally present is to iterate over both data
1052     // structures and compare against the other graph.
1053     public boolean equals( OwnershipGraph og ) {
1054
1055         if( og == null ) {
1056           return false;
1057         }
1058
1059         if( !areHeapRegionNodesEqual( og ) ) {
1060             return false;
1061         }
1062
1063         if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
1064             return false;
1065         }
1066
1067         if( !areLabelNodesEqual( og ) ) {
1068             return false;
1069         }
1070
1071         if( !areLabelToHeapRegionEdgesEqual( og ) ) {
1072             return false;
1073         }
1074
1075         if( !areId2paramIndexEqual( og ) ) {
1076             return false;
1077         }
1078
1079         // if everything is equal up to this point,
1080         // assert that allocationSites is also equal--
1081         // this data is redundant and kept for efficiency
1082         assert allocationSites.equals( og.allocationSites );
1083
1084         return true;
1085     }
1086
1087     protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1088         // check all nodes in A for presence in graph B
1089         Set      sA = og.id2hrn.entrySet();
1090         Iterator iA = sA.iterator();
1091         while( iA.hasNext() ) {
1092             Map.Entry      meA  = (Map.Entry)      iA.next();
1093             Integer        idA  = (Integer)        meA.getKey();
1094             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1095
1096             if( !id2hrn.containsKey( idA ) ) {
1097                 return false;
1098             }
1099
1100             //HeapRegionNode hrnB = og.id2hrn.get( idA );
1101             HeapRegionNode hrnB = id2hrn.get( idA );
1102             if( !hrnA.equals( hrnB ) ) {
1103                 return false;
1104             }
1105         }
1106
1107         // then check all nodes in B verses graph A
1108         Set      sB = id2hrn.entrySet();
1109         Iterator iB = sB.iterator();
1110         while( iB.hasNext() ) {
1111             Map.Entry      meB  = (Map.Entry)      iB.next();
1112             Integer        idB  = (Integer)        meB.getKey();
1113             HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
1114
1115             if( !og.id2hrn.containsKey( idB ) ) {
1116                 return false;
1117             }
1118
1119             // we should have already checked the equality
1120             // of this pairing in the last pass if they both
1121             // exist so assert that they are equal now
1122             HeapRegionNode hrnA = og.id2hrn.get( idB );
1123             assert hrnB.equals( hrnA );
1124         }
1125
1126         return true;
1127     }
1128
1129     protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
1130         Set      sA = og.id2hrn.entrySet();
1131         Iterator iA = sA.iterator();
1132         while( iA.hasNext() ) {
1133             Map.Entry      meA  = (Map.Entry)      iA.next();
1134             Integer        idA  = (Integer)        meA.getKey();
1135             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1136
1137             // we should have already checked that the same
1138             // heap regions exist in both graphs
1139             assert id2hrn.containsKey( idA );
1140
1141             // and are their edges the same?  first check every
1142             // edge in A for presence and equality in B
1143             HeapRegionNode hrnChildA = null;
1144             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1145             while( heapRegionsItrA.hasNext() ) {
1146                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1147                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1148                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1149
1150                 Integer idChildA = hrnChildA.getID();
1151                 assert id2hrn.containsKey( idChildA );
1152
1153                 // at this point we know an edge in graph A exists
1154                 // idA -> idChildA, does this edge exist in B?
1155                 boolean edgeFound = false;
1156                 HeapRegionNode hrnB = id2hrn.get( idA );
1157
1158                 HeapRegionNode hrnChildB = null;
1159                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1160                 while( heapRegionsItrB.hasNext() ) {
1161                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
1162                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
1163                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1164
1165                     if( idChildA.equals( hrnChildB.getID() ) ) {
1166                         if( !repA.equals( repB ) ) {
1167                             return false;
1168                         }
1169                         edgeFound = true;
1170                     }
1171                 }
1172
1173                 if( !edgeFound ) {
1174                     return false;
1175                 }
1176             }
1177
1178             // then check every edge in B for presence in A, starting
1179             // from the same parent HeapRegionNode
1180             HeapRegionNode hrnB = id2hrn.get( idA );
1181
1182             HeapRegionNode hrnChildB = null;
1183             Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1184             while( heapRegionsItrB.hasNext() ) {
1185                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
1186                 hrnChildB                    = (HeapRegionNode)          me.getKey();
1187                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1188
1189                 Integer idChildB = hrnChildB.getID();
1190
1191                 // at this point we know an edge in graph B exists
1192                 // idB -> idChildB, does this edge exist in A?
1193                 boolean edgeFound = false;
1194
1195                 hrnChildA       = null;
1196                 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1197                 while( heapRegionsItrA.hasNext() ) {
1198                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1199                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
1200                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1201
1202                     if( idChildB.equals( hrnChildA.getID() ) ) {
1203                         assert repB.equals( repA );
1204                         edgeFound = true;
1205                     }
1206                 }
1207
1208                 if( !edgeFound ) {
1209                     return false;
1210                 }
1211             }
1212         }
1213
1214         return true;
1215     }
1216
1217     protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1218         // are all label nodes in A also in graph B?
1219         Set      sA = og.td2ln.entrySet();
1220         Iterator iA = sA.iterator();
1221         while( iA.hasNext() ) {
1222             Map.Entry      meA = (Map.Entry)      iA.next();
1223             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1224
1225             if( !td2ln.containsKey( tdA ) ) {
1226                 return false;
1227             }
1228         }
1229
1230         // are all label nodes in B also in A?
1231         Set      sB = td2ln.entrySet();
1232         Iterator iB = sB.iterator();
1233         while( iB.hasNext() ) {
1234             Map.Entry      meB = (Map.Entry)      iB.next();
1235             TempDescriptor tdB = (TempDescriptor) meB.getKey();
1236
1237             if( !og.td2ln.containsKey( tdB ) ) {
1238                 return false;
1239             }
1240         }
1241
1242         return true;
1243     }
1244
1245     protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
1246         Set      sA = og.td2ln.entrySet();
1247         Iterator iA = sA.iterator();
1248         while( iA.hasNext() ) {
1249             Map.Entry      meA = (Map.Entry)      iA.next();
1250             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1251             LabelNode      lnA = (LabelNode)      meA.getValue();
1252
1253             // we should have already checked that the same
1254             // label nodes exist in both graphs
1255             assert td2ln.containsKey( tdA );
1256
1257             // and are their edges the same?  first check every
1258             // edge in A for presence and equality in B
1259             HeapRegionNode hrnChildA = null;
1260             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1261             while( heapRegionsItrA.hasNext() ) {
1262                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1263                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1264                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1265
1266                 Integer idChildA = hrnChildA.getID();
1267                 assert id2hrn.containsKey( idChildA );
1268
1269                 // at this point we know an edge in graph A exists
1270                 // tdA -> idChildA, does this edge exist in B?
1271                 boolean edgeFound = false;
1272                 LabelNode lnB = td2ln.get( tdA );
1273
1274                 HeapRegionNode hrnChildB = null;
1275                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1276                 while( heapRegionsItrB.hasNext() ) {
1277                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
1278                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
1279                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1280
1281                     if( idChildA.equals( hrnChildB.getID() ) ) {
1282                         if( !repA.equals( repB ) ) {
1283                             return false;
1284                         }
1285                         edgeFound = true;
1286                     }
1287                 }
1288
1289                 if( !edgeFound ) {
1290                     return false;
1291                 }
1292             }
1293
1294             // then check every edge in B for presence in A, starting
1295             // from the same parent LabelNode
1296             LabelNode lnB = td2ln.get( tdA );
1297
1298             HeapRegionNode hrnChildB = null;
1299             Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1300             while( heapRegionsItrB.hasNext() ) {
1301                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
1302                 hrnChildB                    = (HeapRegionNode)          me.getKey();
1303                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1304
1305                 Integer idChildB = hrnChildB.getID();
1306
1307                 // at this point we know an edge in graph B exists
1308                 // tdB -> idChildB, does this edge exist in A?
1309                 boolean edgeFound = false;
1310
1311                 hrnChildA       = null;
1312                 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1313                 while( heapRegionsItrA.hasNext() ) {
1314                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1315                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
1316                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1317
1318                     if( idChildB.equals( hrnChildA.getID() ) ) {
1319                         assert repB.equals( repA );
1320                         edgeFound = true;
1321                     }
1322                 }
1323
1324                 if( !edgeFound ) {
1325                     return false;
1326                 }
1327             }
1328         }
1329
1330         return true;
1331     }
1332
1333
1334     protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1335         return id2paramIndex.size() == og.id2paramIndex.size();
1336     }
1337
1338
1339
1340     // given a set B of heap region node ID's, return the set of heap
1341     // region node ID's that is reachable from B
1342     public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1343
1344         HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1345         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1346
1347         // initial nodes to visit are from set B
1348         Iterator initialItr = idSetB.iterator();
1349         while( initialItr.hasNext() ) {
1350             Integer idInitial = (Integer) initialItr.next();
1351             assert id2hrn.contains( idInitial );
1352             HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1353             toVisit.add( hrnInitial );
1354         }
1355
1356         HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1357
1358         // do a heap traversal
1359         while( !toVisit.isEmpty() ) {
1360             HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1361             toVisit.remove( hrnVisited );
1362             visited.add   ( hrnVisited );
1363
1364             // for every node visited, add it to the total
1365             // reachable set
1366             idSetReachableFromB.add( hrnVisited.getID() );
1367
1368             // find other reachable nodes
1369             Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1370             while( referenceeItr.hasNext() ) {
1371                 Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1372                 HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1373                 ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1374
1375                 if( !visited.contains( hrnReferencee ) ) {
1376                     toVisit.add( hrnReferencee );
1377                 }
1378             }
1379         }
1380
1381         return idSetReachableFromB;
1382     }
1383
1384
1385     // used to find if a heap region can possibly have a reference to
1386     // any of the heap regions in the given set
1387     // if the id supplied is in the set, then a self-referencing edge
1388     // would return true, but that special case is specifically allowed
1389     // meaning that it isn't an external alias
1390     public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1391
1392         assert id2hrn.contains( id );
1393         HeapRegionNode hrn = id2hrn.get( id );
1394
1395         /*
1396         HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1397
1398         Iterator i = idSet.iterator();
1399         while( i.hasNext() ) {
1400             Integer idFromSet = (Integer) i.next();
1401             assert id2hrn.contains( idFromSet );
1402             hrnSet.add( id2hrn.get( idFromSet ) );
1403         }
1404         */
1405
1406         // do a traversal from hrn and see if any of the
1407         // heap regions from the set come up during that
1408         HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1409         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1410
1411         toVisit.add( hrn );
1412         while( !toVisit.isEmpty() ) {
1413             HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1414             toVisit.remove( hrnVisited );
1415             visited.add   ( hrnVisited );
1416
1417             Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1418             while( referenceeItr.hasNext() ) {
1419                 Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1420                 HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1421                 ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1422
1423                 if( idSet.contains( hrnReferencee.getID() ) ) {
1424                     if( !id.equals( hrnReferencee.getID() ) ) {
1425                         return true;
1426                     }
1427                 }
1428
1429                 if( !visited.contains( hrnReferencee ) ) {
1430                     toVisit.add( hrnReferencee );
1431                 }
1432             }
1433         }
1434
1435         return false;
1436     }
1437
1438
1439
1440     // for writing ownership graphs to dot files
1441     public void writeGraph( Descriptor methodDesc,
1442                             FlatNode   fn,
1443                             boolean    writeLabels,
1444                             boolean    writeReferencers
1445                             ) throws java.io.IOException {
1446         writeGraph(
1447                    methodDesc.getSymbol() +
1448                    methodDesc.getNum() +
1449                    fn.toString(),
1450                    writeLabels,
1451                    writeReferencers
1452                    );
1453     }
1454
1455     public void writeGraph( Descriptor methodDesc,
1456                             boolean    writeLabels,
1457                             boolean    writeReferencers
1458                             ) throws java.io.IOException {
1459         writeGraph(
1460                    methodDesc.getSymbol() +
1461                    methodDesc.getNum() +
1462                    "COMPLETE",
1463                    writeLabels,
1464                    writeReferencers
1465                     );
1466     }
1467
1468     public void writeGraph( String graphName,
1469                             boolean writeLabels,
1470                             boolean writeReferencers
1471                             ) throws java.io.IOException {
1472
1473         // remove all non-word characters from the graph name so
1474         // the filename and identifier in dot don't cause errors
1475         graphName = graphName.replaceAll( "[\\W]", "" );
1476
1477         BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1478         bw.write( "digraph "+graphName+" {\n" );
1479         //bw.write( "  size=\"7.5,10\";\n" );
1480
1481
1482         // then visit every heap region node
1483         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1484
1485         Set      s = id2hrn.entrySet();
1486         Iterator i = s.iterator();
1487         while( i.hasNext() ) {
1488             Map.Entry      me  = (Map.Entry)      i.next();
1489             HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1490             if( !visited.contains( hrn ) ) {
1491                 traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1492                                          hrn,
1493                                          bw,
1494                                          null,
1495                                          visited,
1496                                          writeReferencers );
1497             }
1498         }
1499
1500         bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
1501
1502
1503         // then visit every label node, useful for debugging
1504         if( writeLabels ) {
1505             s = td2ln.entrySet();
1506             i = s.iterator();
1507             while( i.hasNext() ) {
1508                 Map.Entry me = (Map.Entry) i.next();
1509                 LabelNode ln = (LabelNode) me.getValue();
1510
1511                 HeapRegionNode hrn = null;
1512                 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1513                 while( heapRegionsItr.hasNext() ) {
1514                     Map.Entry meH               = (Map.Entry)               heapRegionsItr.next();
1515                     hrn                         = (HeapRegionNode)          meH.getKey();
1516                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
1517
1518                     bw.write( "  "        + ln.toString() +
1519                               " -> "      + hrn.toString() +
1520                               "[label=\"" + rep.toEdgeLabelString() +
1521                               "\",decorate];\n" );
1522                 }
1523             }
1524         }
1525
1526
1527         bw.write( "}\n" );
1528         bw.close();
1529     }
1530
1531     protected void traverseHeapRegionNodes( int mode,
1532                                             HeapRegionNode hrn,
1533                                             BufferedWriter bw,
1534                                             TempDescriptor td,
1535                                             HashSet<HeapRegionNode> visited,
1536                                             boolean writeReferencers
1537                                             ) throws java.io.IOException {
1538
1539         if( visited.contains( hrn ) ) {
1540             return;
1541         }
1542         visited.add( hrn );
1543
1544         switch( mode ) {
1545         case VISIT_HRN_WRITE_FULL:
1546
1547             String attributes = "[";
1548
1549             if( hrn.isSingleObject() ) {
1550                 attributes += "shape=box";
1551             } else {
1552                 attributes += "shape=Msquare";
1553             }
1554
1555             if( hrn.isFlagged() ) {
1556                 attributes += ",style=filled,fillcolor=lightgrey";
1557             }
1558
1559             attributes += ",label=\"ID"        +
1560                           hrn.getID()          +
1561                           "\\n"                +
1562                           hrn.getDescription() +
1563                           "\\n"                +
1564                           hrn.getAlphaString() +
1565                           "\"]";
1566
1567             bw.write( "  " + hrn.toString() + attributes + ";\n" );
1568             break;
1569         }
1570
1571
1572         // useful for debugging
1573         if( writeReferencers ) {
1574             OwnershipNode onRef  = null;
1575             Iterator      refItr = hrn.iteratorToReferencers();
1576             while( refItr.hasNext() ) {
1577                 onRef = (OwnershipNode) refItr.next();
1578
1579                 switch( mode ) {
1580                 case VISIT_HRN_WRITE_FULL:
1581                     bw.write( "  "                    + hrn.toString() +
1582                               " -> "                  + onRef.toString() +
1583                               "[color=lightgray];\n" );
1584                     break;
1585                 }
1586             }
1587         }
1588
1589
1590         HeapRegionNode hrnChild = null;
1591         Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1592         while( childRegionsItr.hasNext() ) {
1593             Map.Entry me                = (Map.Entry)               childRegionsItr.next();
1594             hrnChild                    = (HeapRegionNode)          me.getKey();
1595             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1596
1597             switch( mode ) {
1598             case VISIT_HRN_WRITE_FULL:
1599                 bw.write( "  "        + hrn.toString() +
1600                           " -> "      + hrnChild.toString() +
1601                           "[label=\"" + rep.toEdgeLabelString() +
1602                           "\",decorate];\n" );
1603                 break;
1604             }
1605
1606             traverseHeapRegionNodes( mode,
1607                                      hrnChild,
1608                                      bw,
1609                                      td,
1610                                      visited,
1611                                      writeReferencers );
1612         }
1613     }
1614 }