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