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