Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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