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