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