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