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( null,
 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( fd,
 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( null, false, beta ) );
 491         addReferenceEdge( hrn,     hrn, new ReferenceEdgeProperties( null, 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( null, 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         // in non-static methods there is a "this" pointer
 834         // that should be taken into account
 835         if( isStatic ) {
 836             assert fc.numArgs()     == fm.numParameters();
 837         } else {
 838             assert fc.numArgs() + 1 == fm.numParameters();
 839         }
 840
 841         // the heap regions represented by the arguments (caller graph)
 842         // and heap regions for the parameters (callee graph)
 843         // don't correspond to each other by heap region ID.  In fact,
 844         // an argument label node can be referencing several heap regions
 845         // so the parameter label always references a multiple-object
 846         // heap region in order to handle the range of possible contexts
 847         // for a method call.  This means we need to make a special mapping
 848         // of argument->parameter regions in order to update the caller graph
 849
 850         // for every heap region->heap region edge in the
 851         // callee graph, create the matching edge or edges
 852         // in the caller graph
 853         Set      sCallee = ogCallee.id2hrn.entrySet();
 854         Iterator iCallee = sCallee.iterator();
 855         while( iCallee.hasNext() ) {
 856             Map.Entry      meCallee  = (Map.Entry)      iCallee.next();
 857             Integer        idCallee  = (Integer)        meCallee.getKey();
 858             HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
 859
 860             HeapRegionNode hrnChildCallee = null;
 861             Iterator heapRegionsItrCallee = hrnCallee.setIteratorToReferencedRegions();
 862             while( heapRegionsItrCallee.hasNext() ) {
 863                 Map.Entry me                 = (Map.Entry)               heapRegionsItrCallee.next();
 864                 hrnChildCallee               = (HeapRegionNode)          me.getKey();
 865                 ReferenceEdgeProperties repC = (ReferenceEdgeProperties) me.getValue();
 866
 867                 Integer idChildCallee = hrnChildCallee.getID();
 868
 869                 // only address this edge if it is not a special reflexive edge
 870                 if( !repC.isInitialParamReflexive() ) {
 871
 872                     // now we know that in the callee method's ownership graph
 873                     // there is a heap region->heap region reference edge given
 874                     // by heap region pointers:
 875                     // hrnCallee -> heapChildCallee
 876                     //
 877                     // or by the ownership-graph independent ID's:
 878                     // idCallee -> idChildCallee
 879                     //
 880                     // So now make a set of possible source heaps in the caller graph
 881                     // and a set of destination heaps in the caller graph, and make
 882                     // a reference edge in the caller for every possible (src,dst) pair
 883                     if( !ogCallee.id2hrn.contains( idChildCallee ) ) {
 884                         System.out.println( "Houston, we got a problem." );
 885                         System.out.println( "idCallee is "+idCallee );
 886                         System.out.println( "idChildCallee is "+idChildCallee );
 887
 888                         try {
 889                             writeGraph         ( "caller", false, false, false, false );
 890                             ogCallee.writeGraph( "callee", false, false, false, false );
 891                         } catch( IOException e ) {}
 892                     }
 893
 894                     HashSet<HeapRegionNode> possibleCallerSrcs =
 895                         getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 896                                                              idCallee,
 897                                                              fc,
 898                                                              isStatic );
 899
 900                     HashSet<HeapRegionNode> possibleCallerDsts =
 901                         getHRNSetThatPossiblyMapToCalleeHRN( ogCallee,
 902                                                              idChildCallee,
 903                                                              fc,
 904                                                              isStatic );
 905
 906                     // make every possible pair of {srcSet} -> {dstSet} edges in the caller
 907                     Iterator srcItr = possibleCallerSrcs.iterator();
 908                     while( srcItr.hasNext() ) {
 909                         HeapRegionNode src = (HeapRegionNode) srcItr.next();
 910
 911                         Iterator dstItr = possibleCallerDsts.iterator();
 912                         while( dstItr.hasNext() ) {
 913                             HeapRegionNode dst = (HeapRegionNode) dstItr.next();
 914
 915                             addReferenceEdge( src, dst, repC.copy() );
 916                         }
 917                     }
 918                 }
 919             }
 920         }
 921     }
 922
 923
 924     private HashSet<HeapRegionNode> getHRNSetThatPossiblyMapToCalleeHRN( OwnershipGraph ogCallee,
 925                                                                          Integer        idCallee,
 926                                                                          FlatCall       fc,
 927                                                                          boolean        isStatic ) {
 928
 929         HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
 930
 931         if( ogCallee.id2paramIndex.containsKey( idCallee ) ) {
 932             // the heap region that is part of this
 933             // reference edge won't have a matching ID in the
 934             // caller graph because it is specifically allocated
 935             // for a particular parameter.  Use that information
 936             // to find the corresponding argument label in the
 937             // caller in order to create the proper reference edge
 938             // or edges.
 939             assert !id2hrn.containsKey( idCallee );
 940
 941             Integer paramIndex = ogCallee.id2paramIndex.get( idCallee );
 942             TempDescriptor argTemp;
 943
 944             // now depending on whether the callee is static or not
 945             // we need to account for a "this" argument in order to
 946             // find the matching argument in the caller context
 947             if( isStatic ) {
 948                 argTemp = fc.getArg( paramIndex );
 949             } else {
 950                 if( paramIndex == 0 ) {
 951                     argTemp = fc.getThis();
 952                 } else {
 953                     argTemp = fc.getArg( paramIndex - 1 );
 954                 }
 955             }
 956
 957             LabelNode argLabel = getLabelNodeFromTemp( argTemp );
 958             Iterator argHeapRegionsItr = argLabel.setIteratorToReferencedRegions();
 959             while( argHeapRegionsItr.hasNext() ) {
 960                 Map.Entry meArg                = (Map.Entry)               argHeapRegionsItr.next();
 961                 HeapRegionNode argHeapRegion   = (HeapRegionNode)          meArg.getKey();
 962                 ReferenceEdgeProperties repArg = (ReferenceEdgeProperties) meArg.getValue();
 963
 964                 possibleCallerHRNs.add( (HeapRegionNode) argHeapRegion );
 965             }
 966
 967         } else {
 968             // this heap region is not a parameter, so it should
 969             // have a matching heap region in the caller graph
 970             assert id2hrn.containsKey( idCallee );
 971             possibleCallerHRNs.add( id2hrn.get( idCallee ) );
 972         }
 973
 974         return possibleCallerHRNs;
 975     }
 976
 977
 978
 979     ////////////////////////////////////////////////////
 980     // in merge() and equals() methods the suffix A
 981     // represents the passed in graph and the suffix
 982     // B refers to the graph in this object
 983     // Merging means to take the incoming graph A and
 984     // merge it into B, so after the operation graph B
 985     // is the final result.
 986     ////////////////////////////////////////////////////
 987     public void merge( OwnershipGraph og ) {
 988
 989         if( og == null ) {
 990           return;
 991         }
 992
 993         mergeOwnershipNodes ( og );
 994         mergeReferenceEdges ( og );
 995         mergeId2paramIndex  ( og );
 996         mergeAllocationSites( og );
 997     }
 998
 999
1000     protected void mergeOwnershipNodes( OwnershipGraph og ) {
1001         Set      sA = og.id2hrn.entrySet();
1002         Iterator iA = sA.iterator();
1003         while( iA.hasNext() ) {
1004             Map.Entry      meA  = (Map.Entry)      iA.next();
1005             Integer        idA  = (Integer)        meA.getKey();
1006             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1007
1008             // if this graph doesn't have a node the
1009             // incoming graph has, allocate it
1010             if( !id2hrn.containsKey( idA ) ) {
1011                 HeapRegionNode hrnB = hrnA.copy();
1012                 id2hrn.put( idA, hrnB );
1013
1014             } else {
1015                 // otherwise this is a node present in both graphs
1016                 // so make the new reachability set a union of the
1017                 // nodes' reachability sets
1018                 HeapRegionNode hrnB = id2hrn.get( idA );
1019                 hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
1020             }
1021         }
1022
1023         // now add any label nodes that are in graph B but
1024         // not in A
1025         sA = og.td2ln.entrySet();
1026         iA = sA.iterator();
1027         while( iA.hasNext() ) {
1028             Map.Entry      meA = (Map.Entry)      iA.next();
1029             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1030             LabelNode      lnA = (LabelNode)      meA.getValue();
1031
1032             // if the label doesn't exist in B, allocate and add it
1033             LabelNode lnB = getLabelNodeFromTemp( tdA );
1034         }
1035     }
1036
1037     protected void mergeReferenceEdges( OwnershipGraph og ) {
1038         // there is a data structure for storing label nodes
1039         // retireved by temp descriptors, and a data structure
1040         // for stroing heap region nodes retrieved by integer
1041         // ids.  Because finding edges requires interacting
1042         // with these disparate data structures frequently the
1043         // process is nearly duplicated, one for each structure
1044         // that stores edges
1045
1046         // heap regions
1047         Set      sA = og.id2hrn.entrySet();
1048         Iterator iA = sA.iterator();
1049         while( iA.hasNext() ) {
1050             Map.Entry      meA  = (Map.Entry)      iA.next();
1051             Integer        idA  = (Integer)        meA.getKey();
1052             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1053
1054             HeapRegionNode hrnChildA = null;
1055             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1056             while( heapRegionsItrA.hasNext() ) {
1057                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1058                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1059                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1060
1061                 Integer idChildA = hrnChildA.getID();
1062
1063                 // at this point we know an edge in graph A exists
1064                 // idA -> idChildA, does this exist in B?
1065                 boolean edgeFound = false;
1066                 assert id2hrn.containsKey( idA );
1067                 HeapRegionNode hrnB = id2hrn.get( idA );
1068
1069                 HeapRegionNode          hrnChildB = null;
1070                 ReferenceEdgeProperties repB      = null;
1071                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1072                 while( heapRegionsItrB.hasNext() ) {
1073                     Map.Entry meC               = (Map.Entry)               heapRegionsItrB.next();
1074                     hrnChildB                   = (HeapRegionNode)          meC.getKey();
1075                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
1076
1077                     if( hrnChildB.equals( idChildA ) ) {
1078                         edgeFound = true;
1079                         repB      = rep;
1080                     }
1081                 }
1082
1083                 // if the edge from A was not found in B,
1084                 // add it to B.
1085                 if( !edgeFound ) {
1086                     assert id2hrn.containsKey( idChildA );
1087                     hrnChildB = id2hrn.get( idChildA );
1088                     repB = repA.copy();
1089                     addReferenceEdge( hrnB, hrnChildB, repB );
1090                 }
1091                 // otherwise, the edge already existed in both graphs
1092                 // so merge their reachability sets
1093                 else {
1094                     // just replace this beta set with the union
1095                     assert repB != null;
1096                     repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
1097                 }
1098             }
1099         }
1100
1101         // and then again with label nodes
1102         sA = og.td2ln.entrySet();
1103         iA = sA.iterator();
1104         while( iA.hasNext() ) {
1105             Map.Entry      meA = (Map.Entry)      iA.next();
1106             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1107             LabelNode      lnA = (LabelNode)      meA.getValue();
1108
1109             HeapRegionNode hrnChildA = null;
1110             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1111             while( heapRegionsItrA.hasNext() ) {
1112                 Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1113                 hrnChildA                    = (HeapRegionNode)          meH.getKey();
1114                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1115
1116                 Integer idChildA = hrnChildA.getID();
1117
1118                 // at this point we know an edge in graph A exists
1119                 // tdA -> idChildA, does this exist in B?
1120                 boolean edgeFound = false;
1121                 assert td2ln.containsKey( tdA );
1122                 LabelNode lnB = td2ln.get( tdA );
1123
1124                 HeapRegionNode          hrnChildB = null;
1125                 ReferenceEdgeProperties repB      = null;
1126                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1127                 while( heapRegionsItrB.hasNext() ) {
1128                     Map.Entry meC               = (Map.Entry)               heapRegionsItrB.next();
1129                     hrnChildB                   = (HeapRegionNode)          meC.getKey();
1130                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meC.getValue();
1131
1132                     if( hrnChildB.equals( idChildA ) ) {
1133                         edgeFound = true;
1134                         repB      = rep;
1135                     }
1136                 }
1137
1138                 // if the edge from A was not found in B,
1139                 // add it to B.
1140                 if( !edgeFound ) {
1141                     assert id2hrn.containsKey( idChildA );
1142                     hrnChildB = id2hrn.get( idChildA );
1143                     repB = repA.copy();
1144                     addReferenceEdge( lnB, hrnChildB, repB );
1145                 }
1146                 // otherwise, the edge already existed in both graphs
1147                 // so merge the reachability sets
1148                 else {
1149                     // just replace this beta set with the union
1150                     assert repB != null;
1151                     repB.setBeta( repB.getBeta().union( repA.getBeta() ) );
1152                 }
1153             }
1154         }
1155     }
1156
1157     // you should only merge ownership graphs that have the
1158     // same number of parameters, or if one or both parameter
1159     // index tables are empty
1160     protected void mergeId2paramIndex( OwnershipGraph og ) {
1161         if( id2paramIndex.size() == 0 ) {
1162             id2paramIndex = og.id2paramIndex;
1163             paramIndex2id = og.paramIndex2id;
1164             return;
1165         }
1166
1167         if( og.id2paramIndex.size() == 0 ) {
1168             return;
1169         }
1170
1171         assert id2paramIndex.size() == og.id2paramIndex.size();
1172     }
1173
1174     protected void mergeAllocationSites( OwnershipGraph og ) {
1175         allocationSites.addAll( og.allocationSites );
1176     }
1177
1178
1179
1180     // it is necessary in the equals() member functions
1181     // to "check both ways" when comparing the data
1182     // structures of two graphs.  For instance, if all
1183     // edges between heap region nodes in graph A are
1184     // present and equal in graph B it is not sufficient
1185     // to say the graphs are equal.  Consider that there
1186     // may be edges in graph B that are not in graph A.
1187     // the only way to know that all edges in both graphs
1188     // are equally present is to iterate over both data
1189     // structures and compare against the other graph.
1190     public boolean equals( OwnershipGraph og ) {
1191
1192         if( og == null ) {
1193           return false;
1194         }
1195
1196         if( !areHeapRegionNodesEqual( og ) ) {
1197             return false;
1198         }
1199
1200         if( !areHeapRegionToHeapRegionEdgesEqual( og ) ) {
1201             return false;
1202         }
1203
1204         if( !areLabelNodesEqual( og ) ) {
1205             return false;
1206         }
1207
1208         if( !areLabelToHeapRegionEdgesEqual( og ) ) {
1209             return false;
1210         }
1211
1212         if( !areId2paramIndexEqual( og ) ) {
1213             return false;
1214         }
1215
1216         // if everything is equal up to this point,
1217         // assert that allocationSites is also equal--
1218         // this data is redundant and kept for efficiency
1219         assert allocationSites.equals( og.allocationSites );
1220
1221         return true;
1222     }
1223
1224     protected boolean areHeapRegionNodesEqual( OwnershipGraph og ) {
1225         // check all nodes in A for presence in graph B
1226         Set      sA = og.id2hrn.entrySet();
1227         Iterator iA = sA.iterator();
1228         while( iA.hasNext() ) {
1229             Map.Entry      meA  = (Map.Entry)      iA.next();
1230             Integer        idA  = (Integer)        meA.getKey();
1231             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1232
1233             if( !id2hrn.containsKey( idA ) ) {
1234                 return false;
1235             }
1236
1237             //HeapRegionNode hrnB = og.id2hrn.get( idA );
1238             HeapRegionNode hrnB = id2hrn.get( idA );
1239             if( !hrnA.equals( hrnB ) ) {
1240                 return false;
1241             }
1242         }
1243
1244         // then check all nodes in B verses graph A
1245         Set      sB = id2hrn.entrySet();
1246         Iterator iB = sB.iterator();
1247         while( iB.hasNext() ) {
1248             Map.Entry      meB  = (Map.Entry)      iB.next();
1249             Integer        idB  = (Integer)        meB.getKey();
1250             HeapRegionNode hrnB = (HeapRegionNode) meB.getValue();
1251
1252             if( !og.id2hrn.containsKey( idB ) ) {
1253                 return false;
1254             }
1255
1256             // we should have already checked the equality
1257             // of this pairing in the last pass if they both
1258             // exist so assert that they are equal now
1259             HeapRegionNode hrnA = og.id2hrn.get( idB );
1260             assert hrnB.equals( hrnA );
1261         }
1262
1263         return true;
1264     }
1265
1266     protected boolean areHeapRegionToHeapRegionEdgesEqual( OwnershipGraph og ) {
1267         Set      sA = og.id2hrn.entrySet();
1268         Iterator iA = sA.iterator();
1269         while( iA.hasNext() ) {
1270             Map.Entry      meA  = (Map.Entry)      iA.next();
1271             Integer        idA  = (Integer)        meA.getKey();
1272             HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1273
1274             // we should have already checked that the same
1275             // heap regions exist in both graphs
1276             assert id2hrn.containsKey( idA );
1277
1278             // and are their edges the same?  first check every
1279             // edge in A for presence and equality in B
1280             HeapRegionNode hrnChildA = null;
1281             Iterator heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1282             while( heapRegionsItrA.hasNext() ) {
1283                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1284                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1285                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1286
1287                 Integer idChildA = hrnChildA.getID();
1288                 assert id2hrn.containsKey( idChildA );
1289
1290                 // at this point we know an edge in graph A exists
1291                 // idA -> idChildA, does this edge exist in B?
1292                 boolean edgeFound = false;
1293                 HeapRegionNode hrnB = id2hrn.get( idA );
1294
1295                 HeapRegionNode hrnChildB = null;
1296                 Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1297                 while( heapRegionsItrB.hasNext() ) {
1298                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
1299                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
1300                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1301
1302                     if( idChildA.equals( hrnChildB.getID() ) ) {
1303                         if( !repA.equals( repB ) ) {
1304                             return false;
1305                         }
1306                         edgeFound = true;
1307                     }
1308                 }
1309
1310                 if( !edgeFound ) {
1311                     return false;
1312                 }
1313             }
1314
1315             // then check every edge in B for presence in A, starting
1316             // from the same parent HeapRegionNode
1317             HeapRegionNode hrnB = id2hrn.get( idA );
1318
1319             HeapRegionNode hrnChildB = null;
1320             Iterator heapRegionsItrB = hrnB.setIteratorToReferencedRegions();
1321             while( heapRegionsItrB.hasNext() ) {
1322                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
1323                 hrnChildB                    = (HeapRegionNode)          me.getKey();
1324                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1325
1326                 Integer idChildB = hrnChildB.getID();
1327
1328                 // at this point we know an edge in graph B exists
1329                 // idB -> idChildB, does this edge exist in A?
1330                 boolean edgeFound = false;
1331
1332                 hrnChildA       = null;
1333                 heapRegionsItrA = hrnA.setIteratorToReferencedRegions();
1334                 while( heapRegionsItrA.hasNext() ) {
1335                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1336                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
1337                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1338
1339                     if( idChildB.equals( hrnChildA.getID() ) ) {
1340                         assert repB.equals( repA );
1341                         edgeFound = true;
1342                     }
1343                 }
1344
1345                 if( !edgeFound ) {
1346                     return false;
1347                 }
1348             }
1349         }
1350
1351         return true;
1352     }
1353
1354     protected boolean areLabelNodesEqual( OwnershipGraph og ) {
1355         // are all label nodes in A also in graph B?
1356         Set      sA = og.td2ln.entrySet();
1357         Iterator iA = sA.iterator();
1358         while( iA.hasNext() ) {
1359             Map.Entry      meA = (Map.Entry)      iA.next();
1360             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1361
1362             if( !td2ln.containsKey( tdA ) ) {
1363                 return false;
1364             }
1365         }
1366
1367         // are all label nodes in B also in A?
1368         Set      sB = td2ln.entrySet();
1369         Iterator iB = sB.iterator();
1370         while( iB.hasNext() ) {
1371             Map.Entry      meB = (Map.Entry)      iB.next();
1372             TempDescriptor tdB = (TempDescriptor) meB.getKey();
1373
1374             if( !og.td2ln.containsKey( tdB ) ) {
1375                 return false;
1376             }
1377         }
1378
1379         return true;
1380     }
1381
1382     protected boolean areLabelToHeapRegionEdgesEqual( OwnershipGraph og ) {
1383         Set      sA = og.td2ln.entrySet();
1384         Iterator iA = sA.iterator();
1385         while( iA.hasNext() ) {
1386             Map.Entry      meA = (Map.Entry)      iA.next();
1387             TempDescriptor tdA = (TempDescriptor) meA.getKey();
1388             LabelNode      lnA = (LabelNode)      meA.getValue();
1389
1390             // we should have already checked that the same
1391             // label nodes exist in both graphs
1392             assert td2ln.containsKey( tdA );
1393
1394             // and are their edges the same?  first check every
1395             // edge in A for presence and equality in B
1396             HeapRegionNode hrnChildA = null;
1397             Iterator heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1398             while( heapRegionsItrA.hasNext() ) {
1399                 Map.Entry me                 = (Map.Entry)               heapRegionsItrA.next();
1400                 hrnChildA                    = (HeapRegionNode)          me.getKey();
1401                 ReferenceEdgeProperties repA = (ReferenceEdgeProperties) me.getValue();
1402
1403                 Integer idChildA = hrnChildA.getID();
1404                 assert id2hrn.containsKey( idChildA );
1405
1406                 // at this point we know an edge in graph A exists
1407                 // tdA -> idChildA, does this edge exist in B?
1408                 boolean edgeFound = false;
1409                 LabelNode lnB = td2ln.get( tdA );
1410
1411                 HeapRegionNode hrnChildB = null;
1412                 Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1413                 while( heapRegionsItrB.hasNext() ) {
1414                     Map.Entry meH                = (Map.Entry)               heapRegionsItrB.next();
1415                     hrnChildB                    = (HeapRegionNode)          meH.getKey();
1416                     ReferenceEdgeProperties repB = (ReferenceEdgeProperties) meH.getValue();
1417
1418                     if( idChildA.equals( hrnChildB.getID() ) ) {
1419                         if( !repA.equals( repB ) ) {
1420                             return false;
1421                         }
1422                         edgeFound = true;
1423                     }
1424                 }
1425
1426                 if( !edgeFound ) {
1427                     return false;
1428                 }
1429             }
1430
1431             // then check every edge in B for presence in A, starting
1432             // from the same parent LabelNode
1433             LabelNode lnB = td2ln.get( tdA );
1434
1435             HeapRegionNode hrnChildB = null;
1436             Iterator heapRegionsItrB = lnB.setIteratorToReferencedRegions();
1437             while( heapRegionsItrB.hasNext() ) {
1438                 Map.Entry me                 = (Map.Entry)               heapRegionsItrB.next();
1439                 hrnChildB                    = (HeapRegionNode)          me.getKey();
1440                 ReferenceEdgeProperties repB = (ReferenceEdgeProperties) me.getValue();
1441
1442                 Integer idChildB = hrnChildB.getID();
1443
1444                 // at this point we know an edge in graph B exists
1445                 // tdB -> idChildB, does this edge exist in A?
1446                 boolean edgeFound = false;
1447
1448                 hrnChildA       = null;
1449                 heapRegionsItrA = lnA.setIteratorToReferencedRegions();
1450                 while( heapRegionsItrA.hasNext() ) {
1451                     Map.Entry meH                = (Map.Entry)               heapRegionsItrA.next();
1452                     hrnChildA                    = (HeapRegionNode)          meH.getKey();
1453                     ReferenceEdgeProperties repA = (ReferenceEdgeProperties) meH.getValue();
1454
1455                     if( idChildB.equals( hrnChildA.getID() ) ) {
1456                         assert repB.equals( repA );
1457                         edgeFound = true;
1458                     }
1459                 }
1460
1461                 if( !edgeFound ) {
1462                     return false;
1463                 }
1464             }
1465         }
1466
1467         return true;
1468     }
1469
1470
1471     protected boolean areId2paramIndexEqual( OwnershipGraph og ) {
1472         return id2paramIndex.size() == og.id2paramIndex.size();
1473     }
1474
1475
1476
1477     // given a set B of heap region node ID's, return the set of heap
1478     // region node ID's that is reachable from B
1479     public HashSet<Integer> getReachableSet( HashSet<Integer> idSetB ) {
1480
1481         HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1482         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1483
1484         // initial nodes to visit are from set B
1485         Iterator initialItr = idSetB.iterator();
1486         while( initialItr.hasNext() ) {
1487             Integer idInitial = (Integer) initialItr.next();
1488             assert id2hrn.contains( idInitial );
1489             HeapRegionNode hrnInitial = id2hrn.get( idInitial );
1490             toVisit.add( hrnInitial );
1491         }
1492
1493         HashSet<Integer> idSetReachableFromB = new HashSet<Integer>();
1494
1495         // do a heap traversal
1496         while( !toVisit.isEmpty() ) {
1497             HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1498             toVisit.remove( hrnVisited );
1499             visited.add   ( hrnVisited );
1500
1501             // for every node visited, add it to the total
1502             // reachable set
1503             idSetReachableFromB.add( hrnVisited.getID() );
1504
1505             // find other reachable nodes
1506             Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1507             while( referenceeItr.hasNext() ) {
1508                 Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1509                 HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1510                 ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1511
1512                 if( !visited.contains( hrnReferencee ) ) {
1513                     toVisit.add( hrnReferencee );
1514                 }
1515             }
1516         }
1517
1518         return idSetReachableFromB;
1519     }
1520
1521
1522     // used to find if a heap region can possibly have a reference to
1523     // any of the heap regions in the given set
1524     // if the id supplied is in the set, then a self-referencing edge
1525     // would return true, but that special case is specifically allowed
1526     // meaning that it isn't an external alias
1527     public boolean canIdReachSet( Integer id, HashSet<Integer> idSet ) {
1528
1529         assert id2hrn.contains( id );
1530         HeapRegionNode hrn = id2hrn.get( id );
1531
1532         /*
1533         HashSet<HeapRegionNode> hrnSet = new HashSet<HeapRegionNode>();
1534
1535         Iterator i = idSet.iterator();
1536         while( i.hasNext() ) {
1537             Integer idFromSet = (Integer) i.next();
1538             assert id2hrn.contains( idFromSet );
1539             hrnSet.add( id2hrn.get( idFromSet ) );
1540         }
1541         */
1542
1543         // do a traversal from hrn and see if any of the
1544         // heap regions from the set come up during that
1545         HashSet<HeapRegionNode> toVisit = new HashSet<HeapRegionNode>();
1546         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1547
1548         toVisit.add( hrn );
1549         while( !toVisit.isEmpty() ) {
1550             HeapRegionNode hrnVisited = (HeapRegionNode) toVisit.iterator().next();
1551             toVisit.remove( hrnVisited );
1552             visited.add   ( hrnVisited );
1553
1554             Iterator referenceeItr = hrnVisited.setIteratorToReferencedRegions();
1555             while( referenceeItr.hasNext() ) {
1556                 Map.Entry me                 = (Map.Entry)               referenceeItr.next();
1557                 HeapRegionNode hrnReferencee = (HeapRegionNode)          me.getKey();
1558                 ReferenceEdgeProperties rep  = (ReferenceEdgeProperties) me.getValue();
1559
1560                 if( idSet.contains( hrnReferencee.getID() ) ) {
1561                     if( !id.equals( hrnReferencee.getID() ) ) {
1562                         return true;
1563                     }
1564                 }
1565
1566                 if( !visited.contains( hrnReferencee ) ) {
1567                     toVisit.add( hrnReferencee );
1568                 }
1569             }
1570         }
1571
1572         return false;
1573     }
1574
1575
1576
1577     // for writing ownership graphs to dot files
1578     public void writeGraph( Descriptor methodDesc,
1579                             FlatNode   fn,
1580                             boolean    writeLabels,
1581                             boolean    labelSelect,
1582                             boolean    pruneGarbage,
1583                             boolean    writeReferencers
1584                             ) throws java.io.IOException {
1585         writeGraph(
1586                    methodDesc.getSymbol() +
1587                    methodDesc.getNum() +
1588                    fn.toString(),
1589                    writeLabels,
1590                    labelSelect,
1591                    pruneGarbage,
1592                    writeReferencers
1593                    );
1594     }
1595
1596     public void writeGraph( Descriptor methodDesc,
1597                             FlatNode   fn,
1598                             boolean    writeLabels,
1599                             boolean    writeReferencers
1600                             ) throws java.io.IOException {
1601         writeGraph(
1602                    methodDesc.getSymbol() +
1603                    methodDesc.getNum() +
1604                    fn.toString(),
1605                    writeLabels,
1606                    false,
1607                    false,
1608                    writeReferencers
1609                    );
1610     }
1611
1612     public void writeGraph( Descriptor methodDesc,
1613                             boolean    writeLabels,
1614                             boolean    writeReferencers
1615                             ) throws java.io.IOException {
1616         writeGraph(
1617                    methodDesc.getSymbol() +
1618                    methodDesc.getNum() +
1619                    "COMPLETE",
1620                    writeLabels,
1621                    false,
1622                    false,
1623                    writeReferencers
1624                     );
1625     }
1626
1627     public void writeGraph( Descriptor methodDesc,
1628                             boolean    writeLabels,
1629                             boolean    labelSelect,
1630                             boolean    pruneGarbage,
1631                             boolean    writeReferencers
1632                             ) throws java.io.IOException {
1633         writeGraph(
1634                    methodDesc.getSymbol() +
1635                    methodDesc.getNum() +
1636                    "COMPLETE",
1637                    writeLabels,
1638                    labelSelect,
1639                    pruneGarbage,
1640                    writeReferencers
1641                     );
1642     }
1643
1644     public void writeGraph( String graphName,
1645                             boolean writeLabels,
1646                             boolean labelSelect,
1647                             boolean pruneGarbage,
1648                             boolean writeReferencers
1649                             ) throws java.io.IOException {
1650
1651         // remove all non-word characters from the graph name so
1652         // the filename and identifier in dot don't cause errors
1653         graphName = graphName.replaceAll( "[\\W]", "" );
1654
1655         BufferedWriter bw = new BufferedWriter( new FileWriter( graphName+".dot" ) );
1656         bw.write( "digraph "+graphName+" {\n" );
1657         //bw.write( "  size=\"7.5,10\";\n" );
1658
1659         HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
1660
1661         // then visit every heap region node
1662         if( !pruneGarbage ) {
1663             Set      s = id2hrn.entrySet();
1664             Iterator i = s.iterator();
1665             while( i.hasNext() ) {
1666                 Map.Entry      me  = (Map.Entry)      i.next();
1667                 HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1668                 if( !visited.contains( hrn ) ) {
1669                     traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1670                                              hrn,
1671                                              bw,
1672                                              null,
1673                                              visited,
1674                                              writeReferencers );
1675                 }
1676             }
1677         }
1678
1679         bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
1680
1681
1682         // then visit every label node, useful for debugging
1683         if( writeLabels ) {
1684             Set      s = td2ln.entrySet();
1685             Iterator i = s.iterator();
1686             while( i.hasNext() ) {
1687                 Map.Entry me = (Map.Entry) i.next();
1688                 LabelNode ln = (LabelNode) me.getValue();
1689
1690                 if( labelSelect ) {
1691                     String labelStr = ln.getTempDescriptorString();
1692                     if( labelStr.startsWith( "___temp"      ) ||
1693                         labelStr.startsWith( "___dst"       ) ||
1694                         labelStr.startsWith( "___srctmp"   ) ||
1695                         labelStr.startsWith( "___neverused" )   ) {
1696                         continue;
1697                     }
1698                 }
1699
1700                 HeapRegionNode hrn = null;
1701                 Iterator heapRegionsItr = ln.setIteratorToReferencedRegions();
1702                 while( heapRegionsItr.hasNext() ) {
1703                     Map.Entry meH               = (Map.Entry)               heapRegionsItr.next();
1704                     hrn                         = (HeapRegionNode)          meH.getKey();
1705                     ReferenceEdgeProperties rep = (ReferenceEdgeProperties) meH.getValue();
1706
1707                     if( pruneGarbage && !visited.contains( hrn ) ) {
1708                         traverseHeapRegionNodes( VISIT_HRN_WRITE_FULL,
1709                                                  hrn,
1710                                                  bw,
1711                                                  null,
1712                                                  visited,
1713                                                  writeReferencers );
1714                     }
1715
1716                     bw.write( "  "        + ln.toString() +
1717                               " -> "      + hrn.toString() +
1718                               "[label=\"" + rep.toEdgeLabelString() +
1719                               "\",decorate];\n" );
1720                 }
1721             }
1722         }
1723
1724
1725         bw.write( "}\n" );
1726         bw.close();
1727     }
1728
1729     protected void traverseHeapRegionNodes( int mode,
1730                                             HeapRegionNode hrn,
1731                                             BufferedWriter bw,
1732                                             TempDescriptor td,
1733                                             HashSet<HeapRegionNode> visited,
1734                                             boolean writeReferencers
1735                                             ) throws java.io.IOException {
1736
1737         if( visited.contains( hrn ) ) {
1738             return;
1739         }
1740         visited.add( hrn );
1741
1742         switch( mode ) {
1743         case VISIT_HRN_WRITE_FULL:
1744
1745             String attributes = "[";
1746
1747             if( hrn.isSingleObject() ) {
1748                 attributes += "shape=box";
1749             } else {
1750                 attributes += "shape=Msquare";
1751             }
1752
1753             if( hrn.isFlagged() ) {
1754                 attributes += ",style=filled,fillcolor=lightgrey";
1755             }
1756
1757             attributes += ",label=\"ID"        +
1758                           hrn.getID()          +
1759                           "\\n"                +
1760                           hrn.getDescription() +
1761                           "\\n"                +
1762                           hrn.getAlphaString() +
1763                           "\"]";
1764
1765             bw.write( "  " + hrn.toString() + attributes + ";\n" );
1766             break;
1767         }
1768
1769
1770         // useful for debugging
1771         if( writeReferencers ) {
1772             OwnershipNode onRef  = null;
1773             Iterator      refItr = hrn.iteratorToReferencers();
1774             while( refItr.hasNext() ) {
1775                 onRef = (OwnershipNode) refItr.next();
1776
1777                 switch( mode ) {
1778                 case VISIT_HRN_WRITE_FULL:
1779                     bw.write( "  "                    + hrn.toString() +
1780                               " -> "                  + onRef.toString() +
1781                               "[color=lightgray];\n" );
1782                     break;
1783                 }
1784             }
1785         }
1786
1787
1788         HeapRegionNode hrnChild = null;
1789         Iterator childRegionsItr = hrn.setIteratorToReferencedRegions();
1790         while( childRegionsItr.hasNext() ) {
1791             Map.Entry me                = (Map.Entry)               childRegionsItr.next();
1792             hrnChild                    = (HeapRegionNode)          me.getKey();
1793             ReferenceEdgeProperties rep = (ReferenceEdgeProperties) me.getValue();
1794
1795             switch( mode ) {
1796             case VISIT_HRN_WRITE_FULL:
1797                 bw.write( "  "        + hrn.toString() +
1798                           " -> "      + hrnChild.toString() +
1799                           "[label=\"" + rep.toEdgeLabelString() +
1800                           "\",decorate];\n" );
1801                 break;
1802             }
1803
1804             traverseHeapRegionNodes( mode,
1805                                      hrnChild,
1806                                      bw,
1807                                      td,
1808                                      visited,
1809                                      writeReferencers );
1810         }
1811     }
1812 }