Robust/src/Analysis/Disjoint/ReachGraph.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import Util.UtilAlgorithms;
   6 import java.util.*;
   7 import java.io.*;
   8
   9 public class ReachGraph {
  10
  11   // use to disable improvements for comparison
  12   protected static final boolean DISABLE_STRONG_UPDATES = false;
  13   protected static final boolean DISABLE_GLOBAL_SWEEP   = true;
  14
  15   // a special out-of-scope temp
  16   protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
  17
  18   // some frequently used reachability constants
  19   protected static final ReachState rstateEmpty        = ReachState.factory();
  20   protected static final ReachSet   rsetEmpty          = ReachSet.factory();
  21   protected static final ReachSet   rsetWithEmptyState = ReachSet.factory( rstateEmpty );
  22
  23   // predicate constants
  24   protected static final ExistPred    predTrue   = ExistPred.factory(); // if no args, true
  25   protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
  26   protected static final ExistPredSet predsTrue  = ExistPredSet.factory( predTrue );
  27
  28
  29   // from DisjointAnalysis for convenience
  30   protected static int      allocationDepth   = -1;
  31   protected static TypeUtil typeUtil          = null;
  32
  33
  34   // variable and heap region nodes indexed by unique ID
  35   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  36   public Hashtable<TempDescriptor, VariableNode  > td2vn;
  37
  38   // convenient set of alloc sites for all heap regions
  39   // present in the graph without having to search
  40   public HashSet<AllocSite> allocSites;
  41
  42   public ReachGraph() {
  43     id2hrn     = new Hashtable<Integer,        HeapRegionNode>();
  44     td2vn      = new Hashtable<TempDescriptor, VariableNode  >();
  45     allocSites = new HashSet<AllocSite>();
  46   }
  47
  48
  49   // temp descriptors are globally unique and map to
  50   // exactly one variable node, easy
  51   protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
  52     assert td != null;
  53
  54     if( !td2vn.containsKey( td ) ) {
  55       td2vn.put( td, new VariableNode( td ) );
  56     }
  57
  58     return td2vn.get( td );
  59   }
  60
  61   public boolean hasVariable( TempDescriptor td ) {
  62     return td2vn.containsKey( td );
  63   }
  64
  65
  66   // the reason for this method is to have the option
  67   // of creating new heap regions with specific IDs, or
  68   // duplicating heap regions with specific IDs (especially
  69   // in the merge() operation) or to create new heap
  70   // regions with a new unique ID
  71   protected HeapRegionNode
  72     createNewHeapRegionNode( Integer        id,
  73                              boolean        isSingleObject,
  74                              boolean        isNewSummary,
  75                              boolean        isFlagged,
  76                              boolean        isOutOfContext,
  77                              TypeDescriptor type,
  78                              AllocSite      allocSite,
  79                              ReachSet       inherent,
  80                              ReachSet       alpha,
  81                              ExistPredSet   preds,
  82                              String         description
  83                              ) {
  84
  85     boolean markForAnalysis = isFlagged;
  86
  87     TypeDescriptor typeToUse = null;
  88     if( allocSite != null ) {
  89       typeToUse = allocSite.getType();
  90       allocSites.add( allocSite );
  91     } else {
  92       typeToUse = type;
  93     }
  94
  95     if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
  96       markForAnalysis = true;
  97     }
  98
  99     if( id == null ) {
 100       id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
 101     }
 102
 103     if( inherent == null ) {
 104       if( markForAnalysis ) {
 105         inherent =
 106           ReachSet.factory(
 107                            ReachState.factory(
 108                                               ReachTuple.factory( id,
 109                                                                   !isSingleObject,
 110                                                                   ReachTuple.ARITY_ONE
 111                                                                   )
 112                                               )
 113                            );
 114       } else {
 115         inherent = rsetWithEmptyState;
 116       }
 117     }
 118
 119     if( alpha == null ) {
 120       alpha = inherent;
 121     }
 122
 123     if( preds == null ) {
 124       // TODO: do this right?  For out-of-context nodes?
 125       preds = ExistPredSet.factory();
 126     }
 127
 128     HeapRegionNode hrn = new HeapRegionNode( id,
 129                                              isSingleObject,
 130                                              markForAnalysis,
 131                                              isNewSummary,
 132                                              isOutOfContext,
 133                                              typeToUse,
 134                                              allocSite,
 135                                              inherent,
 136                                              alpha,
 137                                              preds,
 138                                              description );
 139     id2hrn.put( id, hrn );
 140     return hrn;
 141   }
 142
 143
 144
 145   ////////////////////////////////////////////////
 146   //
 147   //  Low-level referencee and referencer methods
 148   //
 149   //  These methods provide the lowest level for
 150   //  creating references between reachability nodes
 151   //  and handling the details of maintaining both
 152   //  list of referencers and referencees.
 153   //
 154   ////////////////////////////////////////////////
 155   protected void addRefEdge( RefSrcNode     referencer,
 156                              HeapRegionNode referencee,
 157                              RefEdge        edge ) {
 158     assert referencer != null;
 159     assert referencee != null;
 160     assert edge       != null;
 161     assert edge.getSrc() == referencer;
 162     assert edge.getDst() == referencee;
 163
 164     referencer.addReferencee( edge );
 165     referencee.addReferencer( edge );
 166   }
 167
 168   protected void removeRefEdge( RefEdge e ) {
 169     removeRefEdge( e.getSrc(),
 170                    e.getDst(),
 171                    e.getType(),
 172                    e.getField() );
 173   }
 174
 175   protected void removeRefEdge( RefSrcNode     referencer,
 176                                 HeapRegionNode referencee,
 177                                 TypeDescriptor type,
 178                                 String         field ) {
 179     assert referencer != null;
 180     assert referencee != null;
 181
 182     RefEdge edge = referencer.getReferenceTo( referencee,
 183                                               type,
 184                                               field );
 185     assert edge != null;
 186     assert edge == referencee.getReferenceFrom( referencer,
 187                                                 type,
 188                                                 field );
 189
 190     referencer.removeReferencee( edge );
 191     referencee.removeReferencer( edge );
 192   }
 193
 194   protected void clearRefEdgesFrom( RefSrcNode     referencer,
 195                                     TypeDescriptor type,
 196                                     String         field,
 197                                     boolean        removeAll ) {
 198     assert referencer != null;
 199
 200     // get a copy of the set to iterate over, otherwise
 201     // we will be trying to take apart the set as we
 202     // are iterating over it, which won't work
 203     Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
 204     while( i.hasNext() ) {
 205       RefEdge edge = i.next();
 206
 207       if( removeAll                                          ||
 208           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 209         ){
 210
 211         HeapRegionNode referencee = edge.getDst();
 212
 213         removeRefEdge( referencer,
 214                        referencee,
 215                        edge.getType(),
 216                        edge.getField() );
 217       }
 218     }
 219   }
 220
 221   protected void clearRefEdgesTo( HeapRegionNode referencee,
 222                                   TypeDescriptor type,
 223                                   String         field,
 224                                   boolean        removeAll ) {
 225     assert referencee != null;
 226
 227     // get a copy of the set to iterate over, otherwise
 228     // we will be trying to take apart the set as we
 229     // are iterating over it, which won't work
 230     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 231     while( i.hasNext() ) {
 232       RefEdge edge = i.next();
 233
 234       if( removeAll                                          ||
 235           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 236         ){
 237
 238         RefSrcNode referencer = edge.getSrc();
 239
 240         removeRefEdge( referencer,
 241                        referencee,
 242                        edge.getType(),
 243                        edge.getField() );
 244       }
 245     }
 246   }
 247
 248
 249   ////////////////////////////////////////////////////
 250   //
 251   //  Assignment Operation Methods
 252   //
 253   //  These methods are high-level operations for
 254   //  modeling program assignment statements using
 255   //  the low-level reference create/remove methods
 256   //  above.
 257   //
 258   ////////////////////////////////////////////////////
 259
 260   public void assignTempXEqualToTempY( TempDescriptor x,
 261                                        TempDescriptor y ) {
 262     assignTempXEqualToCastedTempY( x, y, null );
 263   }
 264
 265   public void assignTempXEqualToCastedTempY( TempDescriptor x,
 266                                              TempDescriptor y,
 267                                              TypeDescriptor tdCast ) {
 268
 269     VariableNode lnX = getVariableNodeFromTemp( x );
 270     VariableNode lnY = getVariableNodeFromTemp( y );
 271
 272     clearRefEdgesFrom( lnX, null, null, true );
 273
 274     // note it is possible that the types of temps in the
 275     // flat node to analyze will reveal that some typed
 276     // edges in the reachability graph are impossible
 277     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 278
 279     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 280     while( itrYhrn.hasNext() ) {
 281       RefEdge        edgeY      = itrYhrn.next();
 282       HeapRegionNode referencee = edgeY.getDst();
 283       RefEdge        edgeNew    = edgeY.copy();
 284
 285       if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
 286         impossibleEdges.add( edgeY );
 287         continue;
 288       }
 289
 290       edgeNew.setSrc( lnX );
 291
 292       if( tdCast == null ) {
 293         edgeNew.setType( mostSpecificType( y.getType(),
 294                                            edgeY.getType(),
 295                                            referencee.getType()
 296                                            )
 297                          );
 298       } else {
 299         edgeNew.setType( mostSpecificType( y.getType(),
 300                                            edgeY.getType(),
 301                                            referencee.getType(),
 302                                            tdCast
 303                                            )
 304                          );
 305       }
 306
 307       edgeNew.setField( null );
 308
 309       addRefEdge( lnX, referencee, edgeNew );
 310     }
 311
 312     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 313     while( itrImp.hasNext() ) {
 314       RefEdge edgeImp = itrImp.next();
 315       removeRefEdge( edgeImp );
 316     }
 317   }
 318
 319
 320   public void assignTempXEqualToTempYFieldF( TempDescriptor  x,
 321                                              TempDescriptor  y,
 322                                              FieldDescriptor f ) {
 323     VariableNode lnX = getVariableNodeFromTemp( x );
 324     VariableNode lnY = getVariableNodeFromTemp( y );
 325
 326     clearRefEdgesFrom( lnX, null, null, true );
 327
 328     // note it is possible that the types of temps in the
 329     // flat node to analyze will reveal that some typed
 330     // edges in the reachability graph are impossible
 331     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 332
 333     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 334     while( itrYhrn.hasNext() ) {
 335       RefEdge        edgeY = itrYhrn.next();
 336       HeapRegionNode hrnY  = edgeY.getDst();
 337       ReachSet       betaY = edgeY.getBeta();
 338
 339       Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 340       while( itrHrnFhrn.hasNext() ) {
 341         RefEdge        edgeHrn = itrHrnFhrn.next();
 342         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 343         ReachSet       betaHrn = edgeHrn.getBeta();
 344
 345         // prune edges that are not a matching field
 346         if( edgeHrn.getType() != null &&
 347             !edgeHrn.getField().equals( f.getSymbol() )
 348             ) {
 349           continue;
 350         }
 351
 352         // check for impossible edges
 353         if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
 354           impossibleEdges.add( edgeHrn );
 355           continue;
 356         }
 357
 358         TypeDescriptor tdNewEdge =
 359           mostSpecificType( edgeHrn.getType(),
 360                             hrnHrn.getType()
 361                             );
 362
 363         RefEdge edgeNew = new RefEdge( lnX,
 364                                        hrnHrn,
 365                                        tdNewEdge,
 366                                        null,
 367                                        Canonical.intersection( betaY, betaHrn ),
 368                                        predsTrue
 369                                        );
 370
 371         addRefEdge( lnX, hrnHrn, edgeNew );
 372       }
 373     }
 374
 375     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 376     while( itrImp.hasNext() ) {
 377       RefEdge edgeImp = itrImp.next();
 378       removeRefEdge( edgeImp );
 379     }
 380
 381     // anytime you might remove edges between heap regions
 382     // you must global sweep to clean up broken reachability
 383     if( !impossibleEdges.isEmpty() ) {
 384       if( !DISABLE_GLOBAL_SWEEP ) {
 385         globalSweep();
 386       }
 387     }
 388   }
 389
 390
 391   public void assignTempXFieldFEqualToTempY( TempDescriptor  x,
 392                                              FieldDescriptor f,
 393                                              TempDescriptor  y ) {
 394
 395     VariableNode lnX = getVariableNodeFromTemp( x );
 396     VariableNode lnY = getVariableNodeFromTemp( y );
 397
 398     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 399     HashSet<RefEdge>        edgesWithNewBeta  = new HashSet<RefEdge>();
 400
 401     // note it is possible that the types of temps in the
 402     // flat node to analyze will reveal that some typed
 403     // edges in the reachability graph are impossible
 404     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 405
 406     // first look for possible strong updates and remove those edges
 407     boolean strongUpdate = false;
 408
 409     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 410     while( itrXhrn.hasNext() ) {
 411       RefEdge        edgeX = itrXhrn.next();
 412       HeapRegionNode hrnX  = edgeX.getDst();
 413
 414       // we can do a strong update here if one of two cases holds
 415       if( f != null &&
 416           f != DisjointAnalysis.getArrayField( f.getType() ) &&
 417           (   (hrnX.getNumReferencers()                         == 1) || // case 1
 418               (hrnX.isSingleObject() && lnX.getNumReferencees() == 1)    // case 2
 419               )
 420           ) {
 421         if( !DISABLE_STRONG_UPDATES ) {
 422           strongUpdate = true;
 423           clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
 424         }
 425       }
 426     }
 427
 428     // then do all token propagation
 429     itrXhrn = lnX.iteratorToReferencees();
 430     while( itrXhrn.hasNext() ) {
 431       RefEdge        edgeX = itrXhrn.next();
 432       HeapRegionNode hrnX  = edgeX.getDst();
 433       ReachSet       betaX = edgeX.getBeta();
 434       ReachSet       R     = Canonical.intersection( hrnX.getAlpha(),
 435                                                      edgeX.getBeta()
 436                                                      );
 437
 438       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 439       while( itrYhrn.hasNext() ) {
 440         RefEdge        edgeY = itrYhrn.next();
 441         HeapRegionNode hrnY  = edgeY.getDst();
 442         ReachSet       O     = edgeY.getBeta();
 443
 444         // check for impossible edges
 445         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 446           impossibleEdges.add( edgeY );
 447           continue;
 448         }
 449
 450         // propagate tokens over nodes starting from hrnSrc, and it will
 451         // take care of propagating back up edges from any touched nodes
 452         ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
 453         propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
 454
 455         // then propagate back just up the edges from hrn
 456         ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
 457         HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
 458
 459         Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
 460           new Hashtable<RefEdge, ChangeSet>();
 461
 462         Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
 463         while( referItr.hasNext() ) {
 464           RefEdge edgeUpstream = referItr.next();
 465           todoEdges.add( edgeUpstream );
 466           edgePlannedChanges.put( edgeUpstream, Cx );
 467         }
 468
 469         propagateTokensOverEdges( todoEdges,
 470                                   edgePlannedChanges,
 471                                   edgesWithNewBeta );
 472       }
 473     }
 474
 475
 476     // apply the updates to reachability
 477     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 478     while( nodeItr.hasNext() ) {
 479       nodeItr.next().applyAlphaNew();
 480     }
 481
 482     Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
 483     while( edgeItr.hasNext() ) {
 484       edgeItr.next().applyBetaNew();
 485     }
 486
 487
 488     // then go back through and add the new edges
 489     itrXhrn = lnX.iteratorToReferencees();
 490     while( itrXhrn.hasNext() ) {
 491       RefEdge        edgeX = itrXhrn.next();
 492       HeapRegionNode hrnX  = edgeX.getDst();
 493
 494       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 495       while( itrYhrn.hasNext() ) {
 496         RefEdge        edgeY = itrYhrn.next();
 497         HeapRegionNode hrnY  = edgeY.getDst();
 498
 499         // skip impossible edges here, we already marked them
 500         // when computing reachability propagations above
 501         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 502           continue;
 503         }
 504
 505         // prepare the new reference edge hrnX.f -> hrnY
 506         TypeDescriptor tdNewEdge =
 507           mostSpecificType( y.getType(),
 508                             edgeY.getType(),
 509                             hrnY.getType()
 510                             );
 511
 512         RefEdge edgeNew = new RefEdge( hrnX,
 513                                        hrnY,
 514                                        tdNewEdge,
 515                                        f.getSymbol(),
 516                                        Canonical.pruneBy( edgeY.getBeta(),
 517                                                           hrnX.getAlpha()
 518                                                           ),
 519                                        predsTrue
 520                                        );
 521
 522         // look to see if an edge with same field exists
 523         // and merge with it, otherwise just add the edge
 524         RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
 525                                                     tdNewEdge,
 526                                                     f.getSymbol() );
 527
 528         if( edgeExisting != null ) {
 529           edgeExisting.setBeta(
 530                                Canonical.union( edgeExisting.getBeta(),
 531                                                 edgeNew.getBeta()
 532                                                 )
 533                                );
 534           edgeExisting.setPreds(
 535                                 Canonical.join( edgeExisting.getPreds(),
 536                                                 edgeNew.getPreds()
 537                                                 )
 538                                 );
 539
 540         } else {
 541           addRefEdge( hrnX, hrnY, edgeNew );
 542         }
 543       }
 544     }
 545
 546     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 547     while( itrImp.hasNext() ) {
 548       RefEdge edgeImp = itrImp.next();
 549       removeRefEdge( edgeImp );
 550     }
 551
 552     // if there was a strong update, make sure to improve
 553     // reachability with a global sweep
 554     if( strongUpdate || !impossibleEdges.isEmpty() ) {
 555       if( !DISABLE_GLOBAL_SWEEP ) {
 556         globalSweep();
 557       }
 558     }
 559   }
 560
 561
 562   public void assignReturnEqualToTemp( TempDescriptor x ) {
 563
 564     VariableNode lnR = getVariableNodeFromTemp( tdReturn );
 565     VariableNode lnX = getVariableNodeFromTemp( x );
 566
 567     clearRefEdgesFrom( lnR, null, null, true );
 568
 569     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 570     while( itrXhrn.hasNext() ) {
 571       RefEdge        edgeX      = itrXhrn.next();
 572       HeapRegionNode referencee = edgeX.getDst();
 573       RefEdge        edgeNew    = edgeX.copy();
 574       edgeNew.setSrc( lnR );
 575
 576       addRefEdge( lnR, referencee, edgeNew );
 577     }
 578   }
 579
 580
 581   public void assignTempEqualToNewAlloc( TempDescriptor x,
 582                                          AllocSite      as ) {
 583     assert x  != null;
 584     assert as != null;
 585
 586     age( as );
 587
 588     // after the age operation the newest (or zero-ith oldest)
 589     // node associated with the allocation site should have
 590     // no references to it as if it were a newly allocated
 591     // heap region
 592     Integer        idNewest   = as.getIthOldest( 0 );
 593     HeapRegionNode hrnNewest  = id2hrn.get( idNewest );
 594     assert         hrnNewest != null;
 595
 596     VariableNode lnX = getVariableNodeFromTemp( x );
 597     clearRefEdgesFrom( lnX, null, null, true );
 598
 599     // make a new reference to allocated node
 600     TypeDescriptor type = as.getType();
 601
 602     RefEdge edgeNew =
 603       new RefEdge( lnX,                  // source
 604                    hrnNewest,            // dest
 605                    type,                 // type
 606                    null,                 // field name
 607                    hrnNewest.getAlpha(), // beta
 608                    predsTrue             // predicates
 609                    );
 610
 611     addRefEdge( lnX, hrnNewest, edgeNew );
 612   }
 613
 614
 615   // use the allocation site (unique to entire analysis) to
 616   // locate the heap region nodes in this reachability graph
 617   // that should be aged.  The process models the allocation
 618   // of new objects and collects all the oldest allocations
 619   // in a summary node to allow for a finite analysis
 620   //
 621   // There is an additional property of this method.  After
 622   // running it on a particular reachability graph (many graphs
 623   // may have heap regions related to the same allocation site)
 624   // the heap region node objects in this reachability graph will be
 625   // allocated.  Therefore, after aging a graph for an allocation
 626   // site, attempts to retrieve the heap region nodes using the
 627   // integer id's contained in the allocation site should always
 628   // return non-null heap regions.
 629   public void age( AllocSite as ) {
 630
 631     // keep track of allocation sites that are represented
 632     // in this graph for efficiency with other operations
 633     allocSites.add( as );
 634
 635     // if there is a k-th oldest node, it merges into
 636     // the summary node
 637     Integer idK = as.getOldest();
 638     if( id2hrn.containsKey( idK ) ) {
 639       HeapRegionNode hrnK = id2hrn.get( idK );
 640
 641       // retrieve the summary node, or make it
 642       // from scratch
 643       HeapRegionNode hrnSummary = getSummaryNode( as );
 644
 645       mergeIntoSummary( hrnK, hrnSummary );
 646     }
 647
 648     // move down the line of heap region nodes
 649     // clobbering the ith and transferring all references
 650     // to and from i-1 to node i.
 651     for( int i = allocationDepth - 1; i > 0; --i ) {
 652
 653       // if the target (ith) node exists, clobber it
 654       // whether the i-1 node exists or not
 655       Integer idIth = as.getIthOldest( i );
 656       if( id2hrn.containsKey( idIth ) ) {
 657         HeapRegionNode hrnI = id2hrn.get( idIth );
 658
 659         // clear all references in and out
 660         wipeOut( hrnI );
 661       }
 662
 663       // only do the transfer if the i-1 node exists
 664       Integer idImin1th = as.getIthOldest( i - 1 );
 665       if( id2hrn.containsKey( idImin1th ) ) {
 666         HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
 667
 668         // either retrieve or make target of transfer
 669         HeapRegionNode hrnI = getIthNode( as, i );
 670
 671         transferOnto( hrnImin1, hrnI );
 672       }
 673
 674     }
 675
 676     // as stated above, the newest node should have had its
 677     // references moved over to the second oldest, so we wipe newest
 678     // in preparation for being the new object to assign something to
 679     HeapRegionNode hrn0 = getIthNode( as, 0 );
 680     wipeOut( hrn0 );
 681
 682     // now tokens in reachability sets need to "age" also
 683     Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
 684     while( itrAllVariableNodes.hasNext() ) {
 685       Map.Entry    me = (Map.Entry)    itrAllVariableNodes.next();
 686       VariableNode ln = (VariableNode) me.getValue();
 687
 688       Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
 689       while( itrEdges.hasNext() ) {
 690         ageTuplesFrom( as, itrEdges.next() );
 691       }
 692     }
 693
 694     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 695     while( itrAllHRNodes.hasNext() ) {
 696       Map.Entry      me       = (Map.Entry)      itrAllHRNodes.next();
 697       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 698
 699       ageTuplesFrom( as, hrnToAge );
 700
 701       Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
 702       while( itrEdges.hasNext() ) {
 703         ageTuplesFrom( as, itrEdges.next() );
 704       }
 705     }
 706
 707
 708     // after tokens have been aged, reset newest node's reachability
 709     // and a brand new node has a "true" predicate
 710     hrn0.setAlpha( hrn0.getInherent() );
 711     hrn0.setPreds( predsTrue );
 712   }
 713
 714
 715   // either retrieve or create the needed heap region node
 716   protected HeapRegionNode getSummaryNode( AllocSite as ) {
 717
 718     Integer        idSummary  = as.getSummary();
 719     HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 720
 721     if( hrnSummary == null ) {
 722
 723       boolean hasFlags = false;
 724       if( as.getType().isClass() ) {
 725         hasFlags = as.getType().getClassDesc().hasFlags();
 726       }
 727
 728       if( as.getFlag() ){
 729         hasFlags = as.getFlag();
 730       }
 731
 732       String strDesc = as.toStringForDOT()+"\\nsummary";
 733       hrnSummary =
 734         createNewHeapRegionNode( idSummary,    // id or null to generate a new one
 735                                  false,        // single object?
 736                                  true,         // summary?
 737                                  hasFlags,     // flagged?
 738                                  false,        // out-of-context?
 739                                  as.getType(), // type
 740                                  as,           // allocation site
 741                                  null,         // inherent reach
 742                                  null,         // current reach
 743                                  predsEmpty,   // predicates
 744                                  strDesc       // description
 745                                  );
 746     }
 747
 748     return hrnSummary;
 749   }
 750
 751   // either retrieve or create the needed heap region node
 752   protected HeapRegionNode getIthNode( AllocSite as, Integer i ) {
 753
 754     Integer        idIth  = as.getIthOldest( i );
 755     HeapRegionNode hrnIth = id2hrn.get( idIth );
 756
 757     if( hrnIth == null ) {
 758
 759       boolean hasFlags = false;
 760       if( as.getType().isClass() ) {
 761         hasFlags = as.getType().getClassDesc().hasFlags();
 762       }
 763
 764       if( as.getFlag() ){
 765         hasFlags = as.getFlag();
 766       }
 767
 768       String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
 769       hrnIth = createNewHeapRegionNode( idIth,        // id or null to generate a new one
 770                                         true,         // single object?
 771                                         false,        // summary?
 772                                         hasFlags,     // flagged?
 773                                         false,        // out-of-context?
 774                                         as.getType(), // type
 775                                         as,           // allocation site
 776                                         null,         // inherent reach
 777                                         null,         // current reach
 778                                         predsEmpty,   // predicates
 779                                         strDesc       // description
 780                                         );
 781     }
 782
 783     return hrnIth;
 784   }
 785
 786
 787
 788   protected void mergeIntoSummary( HeapRegionNode hrn,
 789                                    HeapRegionNode hrnSummary ) {
 790     assert hrnSummary.isNewSummary();
 791
 792     // transfer references _from_ hrn over to hrnSummary
 793     Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
 794     while( itrReferencee.hasNext() ) {
 795       RefEdge edge       = itrReferencee.next();
 796       RefEdge edgeMerged = edge.copy();
 797       edgeMerged.setSrc( hrnSummary );
 798
 799       HeapRegionNode hrnReferencee = edge.getDst();
 800       RefEdge        edgeSummary   =
 801         hrnSummary.getReferenceTo( hrnReferencee,
 802                                    edge.getType(),
 803                                    edge.getField()
 804                                    );
 805
 806       if( edgeSummary == null ) {
 807         // the merge is trivial, nothing to be done
 808       } else {
 809         // otherwise an edge from the referencer to hrnSummary exists already
 810         // and the edge referencer->hrn should be merged with it
 811         edgeMerged.setBeta(
 812                            Canonical.union( edgeMerged.getBeta(),
 813                                             edgeSummary.getBeta()
 814                                             )
 815                             );
 816         edgeMerged.setPreds(
 817                             Canonical.join( edgeMerged.getPreds(),
 818                                             edgeSummary.getPreds()
 819                                             )
 820                              );
 821       }
 822
 823       addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
 824     }
 825
 826     // next transfer references _to_ hrn over to hrnSummary
 827     Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
 828     while( itrReferencer.hasNext() ) {
 829       RefEdge edge         = itrReferencer.next();
 830       RefEdge edgeMerged   = edge.copy();
 831       edgeMerged.setDst( hrnSummary );
 832
 833       RefSrcNode onReferencer = edge.getSrc();
 834       RefEdge    edgeSummary  =
 835         onReferencer.getReferenceTo( hrnSummary,
 836                                      edge.getType(),
 837                                      edge.getField()
 838                                      );
 839
 840       if( edgeSummary == null ) {
 841         // the merge is trivial, nothing to be done
 842       } else {
 843         // otherwise an edge from the referencer to alpha_S exists already
 844         // and the edge referencer->alpha_K should be merged with it
 845         edgeMerged.setBeta(
 846                            Canonical.union( edgeMerged.getBeta(),
 847                                             edgeSummary.getBeta()
 848                                             )
 849                             );
 850         edgeMerged.setPreds(
 851                             Canonical.join( edgeMerged.getPreds(),
 852                                             edgeSummary.getPreds()
 853                                             )
 854                              );
 855       }
 856
 857       addRefEdge( onReferencer, hrnSummary, edgeMerged );
 858     }
 859
 860     // then merge hrn reachability into hrnSummary
 861     hrnSummary.setAlpha(
 862                         Canonical.union( hrnSummary.getAlpha(),
 863                                          hrn.getAlpha()
 864                                          )
 865                          );
 866   }
 867
 868
 869   protected void transferOnto( HeapRegionNode hrnA,
 870                                HeapRegionNode hrnB ) {
 871
 872     // clear references in and out of node b
 873     wipeOut( hrnB );
 874
 875     // copy each edge in and out of A to B
 876     Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
 877     while( itrReferencee.hasNext() ) {
 878       RefEdge        edge          = itrReferencee.next();
 879       HeapRegionNode hrnReferencee = edge.getDst();
 880       RefEdge        edgeNew       = edge.copy();
 881       edgeNew.setSrc( hrnB );
 882
 883       addRefEdge( hrnB, hrnReferencee, edgeNew );
 884     }
 885
 886     Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
 887     while( itrReferencer.hasNext() ) {
 888       RefEdge    edge         = itrReferencer.next();
 889       RefSrcNode onReferencer = edge.getSrc();
 890       RefEdge    edgeNew      = edge.copy();
 891       edgeNew.setDst( hrnB );
 892
 893       addRefEdge( onReferencer, hrnB, edgeNew );
 894     }
 895
 896     // replace hrnB reachability and preds with hrnA's
 897     hrnB.setAlpha( hrnA.getAlpha() );
 898     hrnB.setPreds( hrnA.getPreds() );
 899   }
 900
 901
 902   // the purpose of this method is to conceptually "wipe out"
 903   // a heap region from the graph--purposefully not called REMOVE
 904   // because the node is still hanging around in the graph, just
 905   // not mechanically connected or have any reach or predicate
 906   // information on it anymore--lots of ops can use this
 907   protected void wipeOut( HeapRegionNode hrn ) {
 908     clearRefEdgesFrom( hrn, null, null, true );
 909     clearRefEdgesTo  ( hrn, null, null, true );
 910     hrn.setAlpha( rsetEmpty );
 911     hrn.setPreds( predsEmpty );
 912   }
 913
 914
 915   protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
 916     edge.setBeta(
 917                  Canonical.ageTuplesFrom( edge.getBeta(),
 918                                           as
 919                                           )
 920                   );
 921   }
 922
 923   protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
 924     hrn.setAlpha(
 925                  Canonical.ageTuplesFrom( hrn.getAlpha(),
 926                                           as
 927                                           )
 928                   );
 929   }
 930
 931
 932
 933   protected void propagateTokensOverNodes( HeapRegionNode          nPrime,
 934                                            ChangeSet               c0,
 935                                            HashSet<HeapRegionNode> nodesWithNewAlpha,
 936                                            HashSet<RefEdge>        edgesWithNewBeta ) {
 937
 938     HashSet<HeapRegionNode> todoNodes
 939       = new HashSet<HeapRegionNode>();
 940     todoNodes.add( nPrime );
 941
 942     HashSet<RefEdge> todoEdges
 943       = new HashSet<RefEdge>();
 944
 945     Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
 946       = new Hashtable<HeapRegionNode, ChangeSet>();
 947     nodePlannedChanges.put( nPrime, c0 );
 948
 949     Hashtable<RefEdge, ChangeSet> edgePlannedChanges
 950       = new Hashtable<RefEdge, ChangeSet>();
 951
 952     // first propagate change sets everywhere they can go
 953     while( !todoNodes.isEmpty() ) {
 954       HeapRegionNode n = todoNodes.iterator().next();
 955       ChangeSet      C = nodePlannedChanges.get( n );
 956
 957       Iterator<RefEdge> referItr = n.iteratorToReferencers();
 958       while( referItr.hasNext() ) {
 959         RefEdge edge = referItr.next();
 960         todoEdges.add( edge );
 961
 962         if( !edgePlannedChanges.containsKey( edge ) ) {
 963           edgePlannedChanges.put( edge,
 964                                   ChangeSet.factory()
 965                                   );
 966         }
 967
 968         edgePlannedChanges.put( edge,
 969                                 Canonical.union( edgePlannedChanges.get( edge ),
 970                                                  C
 971                                                  )
 972                                 );
 973       }
 974
 975       Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
 976       while( refeeItr.hasNext() ) {
 977         RefEdge        edgeF = refeeItr.next();
 978         HeapRegionNode m     = edgeF.getDst();
 979
 980         ChangeSet changesToPass = ChangeSet.factory();
 981
 982         Iterator<ChangeTuple> itrCprime = C.iterator();
 983         while( itrCprime.hasNext() ) {
 984           ChangeTuple c = itrCprime.next();
 985           if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
 986             changesToPass = Canonical.union( changesToPass, c );
 987           }
 988         }
 989
 990         if( !changesToPass.isEmpty() ) {
 991           if( !nodePlannedChanges.containsKey( m ) ) {
 992             nodePlannedChanges.put( m, ChangeSet.factory() );
 993           }
 994
 995           ChangeSet currentChanges = nodePlannedChanges.get( m );
 996
 997           if( !changesToPass.isSubset( currentChanges ) ) {
 998
 999             nodePlannedChanges.put( m,
1000                                     Canonical.union( currentChanges,
1001                                                      changesToPass
1002                                                      )
1003                                     );
1004             todoNodes.add( m );
1005           }
1006         }
1007       }
1008
1009       todoNodes.remove( n );
1010     }
1011
1012     // then apply all of the changes for each node at once
1013     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1014     while( itrMap.hasNext() ) {
1015       Map.Entry      me = (Map.Entry)      itrMap.next();
1016       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1017       ChangeSet      C  = (ChangeSet)      me.getValue();
1018
1019       // this propagation step is with respect to one change,
1020       // so we capture the full change from the old alpha:
1021       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1022                                                       C,
1023                                                       true
1024                                                       );
1025       // but this propagation may be only one of many concurrent
1026       // possible changes, so keep a running union with the node's
1027       // partially updated new alpha set
1028       n.setAlphaNew( Canonical.union( n.getAlphaNew(),
1029                                       localDelta
1030                                       )
1031                      );
1032
1033       nodesWithNewAlpha.add( n );
1034     }
1035
1036     propagateTokensOverEdges( todoEdges,
1037                               edgePlannedChanges,
1038                               edgesWithNewBeta
1039                               );
1040   }
1041
1042
1043   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1044                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1045                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1046
1047     // first propagate all change tuples everywhere they can go
1048     while( !todoEdges.isEmpty() ) {
1049       RefEdge edgeE = todoEdges.iterator().next();
1050       todoEdges.remove( edgeE );
1051
1052       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1053         edgePlannedChanges.put( edgeE,
1054                                 ChangeSet.factory()
1055                                 );
1056       }
1057
1058       ChangeSet C = edgePlannedChanges.get( edgeE );
1059
1060       ChangeSet changesToPass = ChangeSet.factory();
1061
1062       Iterator<ChangeTuple> itrC = C.iterator();
1063       while( itrC.hasNext() ) {
1064         ChangeTuple c = itrC.next();
1065         if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1066           changesToPass = Canonical.union( changesToPass, c );
1067         }
1068       }
1069
1070       RefSrcNode rsn = edgeE.getSrc();
1071
1072       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1073         HeapRegionNode n = (HeapRegionNode) rsn;
1074
1075         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1076         while( referItr.hasNext() ) {
1077           RefEdge edgeF = referItr.next();
1078
1079           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1080             edgePlannedChanges.put( edgeF,
1081                                     ChangeSet.factory()
1082                                     );
1083           }
1084
1085           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1086
1087           if( !changesToPass.isSubset( currentChanges ) ) {
1088             todoEdges.add( edgeF );
1089             edgePlannedChanges.put( edgeF,
1090                                     Canonical.union( currentChanges,
1091                                                      changesToPass
1092                                                      )
1093                                     );
1094           }
1095         }
1096       }
1097     }
1098
1099     // then apply all of the changes for each edge at once
1100     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1101     while( itrMap.hasNext() ) {
1102       Map.Entry me = (Map.Entry) itrMap.next();
1103       RefEdge   e  = (RefEdge)   me.getKey();
1104       ChangeSet C  = (ChangeSet) me.getValue();
1105
1106       // this propagation step is with respect to one change,
1107       // so we capture the full change from the old beta:
1108       ReachSet localDelta =
1109         Canonical.applyChangeSet( e.getBeta(),
1110                                   C,
1111                                   true
1112                                   );
1113
1114       // but this propagation may be only one of many concurrent
1115       // possible changes, so keep a running union with the edge's
1116       // partially updated new beta set
1117       e.setBetaNew( Canonical.union( e.getBetaNew(),
1118                                      localDelta
1119                                      )
1120                     );
1121
1122       edgesWithNewBeta.add( e );
1123     }
1124   }
1125
1126
1127
1128   // use this method to make a new reach graph that is
1129   // what heap the FlatMethod callee from the FlatCall
1130   // would start with reaching from its arguments in
1131   // this reach graph
1132   public ReachGraph
1133     makeCalleeView( FlatCall            fc,
1134                     FlatMethod          fm,
1135                     Set<HeapRegionNode> callerNodesCopiedToCallee,
1136                     Set<RefEdge>        callerEdgesCopiedToCallee
1137                     ) {
1138
1139     // the callee view is a new graph: DON'T MODIFY
1140     // *THIS* graph
1141     ReachGraph rg = new ReachGraph();
1142
1143     // track what parts of this graph have already been
1144     // added to callee view, variables not needed.
1145     // Note that we need this because when we traverse
1146     // this caller graph for each parameter we may find
1147     // nodes and edges more than once (which the per-param
1148     // "visit" sets won't show) and we only want to create
1149     // an element in the new callee view one time
1150     //Set callerNodesCopiedToCallee = new HashSet<HeapRegionNode>();
1151     //Set callerEdgesCopiedToCallee = new HashSet<RefEdge>();
1152
1153
1154     // a conservative starting point is to take the
1155     // mechanically-reachable-from-arguments graph
1156     // as opposed to using reachability information
1157     // to prune the graph further
1158     for( int i = 0; i < fm.numParameters(); ++i ) {
1159
1160       // for each parameter index, get the symbol in the
1161       // caller view and callee view
1162
1163       // argument defined here is the symbol in the caller
1164       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
1165
1166       // parameter defined here is the symbol in the callee
1167       TempDescriptor tdParam = fm.getParameter( i );
1168
1169       // use these two VariableNode objects to translate
1170       // between caller and callee--its easy to compare
1171       // a HeapRegionNode across callee and caller because
1172       // they will have the same heap region ID
1173       VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1174       VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1175
1176       // now traverse the calleR view using the argument to
1177       // build the calleE view which has the parameter symbol
1178       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1179       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1180       toVisitInCaller.add( vnCaller );
1181
1182       while( !toVisitInCaller.isEmpty() ) {
1183         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1184         RefSrcNode rsnCallee;
1185
1186         toVisitInCaller.remove( rsnCaller );
1187         visitedInCaller.add( rsnCaller );
1188
1189         // FIRST - setup the source end of an edge, and
1190         // remember the identifying info of the source
1191         // to build predicates
1192         TempDescriptor tdSrc    = null;
1193         Integer        hrnSrcID = null;
1194
1195         if( rsnCaller == vnCaller ) {
1196           // if the caller node is the param symbol, we
1197           // have to do this translation for the callee
1198           rsnCallee = vnCallee;
1199           tdSrc     = tdArg;
1200
1201         } else {
1202           // otherwise the callee-view node is a heap
1203           // region with the same ID, that may or may
1204           // not have been created already
1205           assert rsnCaller instanceof HeapRegionNode;
1206
1207           HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1208           hrnSrcID = hrnSrcCaller.getID();
1209
1210           if( !callerNodesCopiedToCallee.contains( rsnCaller ) ) {
1211
1212             ExistPred pred =
1213               ExistPred.factory( hrnSrcID, null );
1214
1215             ExistPredSet preds =
1216               ExistPredSet.factory( pred );
1217
1218             rsnCallee =
1219               rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1220                                           hrnSrcCaller.isSingleObject(),
1221                                           hrnSrcCaller.isNewSummary(),
1222                                           hrnSrcCaller.isFlagged(),
1223                                           false, // out-of-context?
1224                                           hrnSrcCaller.getType(),
1225                                           hrnSrcCaller.getAllocSite(),
1226                                           /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/,
1227                                           /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/,
1228                                           preds,
1229                                           hrnSrcCaller.getDescription()
1230                                           );
1231             callerNodesCopiedToCallee.add( (HeapRegionNode) rsnCaller );
1232
1233           } else {
1234             rsnCallee = rg.id2hrn.get( hrnSrcID );
1235           }
1236         }
1237
1238         // SECOND - go over all edges from that source
1239
1240         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1241         while( itrRefEdges.hasNext() ) {
1242           RefEdge        reCaller  = itrRefEdges.next();
1243           HeapRegionNode hrnCaller = reCaller.getDst();
1244           HeapRegionNode hrnCallee;
1245
1246           // THIRD - setup destination ends of edges
1247           Integer hrnDstID = hrnCaller.getID();
1248
1249           if( !callerNodesCopiedToCallee.contains( hrnCaller ) ) {
1250
1251             ExistPred pred =
1252               ExistPred.factory( hrnDstID, null );
1253
1254             ExistPredSet preds =
1255               ExistPredSet.factory( pred );
1256
1257             hrnCallee =
1258               rg.createNewHeapRegionNode( hrnCaller.getID(),
1259                                           hrnCaller.isSingleObject(),
1260                                           hrnCaller.isNewSummary(),
1261                                           hrnCaller.isFlagged(),
1262                                           false, // out-of-context?
1263                                           hrnCaller.getType(),
1264                                           hrnCaller.getAllocSite(),
1265                                           /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/,
1266                                           /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/,
1267                                           preds,
1268                                           hrnCaller.getDescription()
1269                                           );
1270             callerNodesCopiedToCallee.add( hrnCaller );
1271           } else {
1272             hrnCallee = rg.id2hrn.get( hrnDstID );
1273           }
1274
1275           // FOURTH - copy edge over if needed
1276           if( !callerEdgesCopiedToCallee.contains( reCaller ) ) {
1277
1278             ExistPred pred =
1279               ExistPred.factory( tdSrc,
1280                                  hrnSrcID,
1281                                  hrnDstID,
1282                                  reCaller.getType(),
1283                                  reCaller.getField(),
1284                                  null );
1285
1286             ExistPredSet preds =
1287               ExistPredSet.factory( pred );
1288
1289             rg.addRefEdge( rsnCallee,
1290                            hrnCallee,
1291                            new RefEdge( rsnCallee,
1292                                         hrnCallee,
1293                                         reCaller.getType(),
1294                                         reCaller.getField(),
1295                                         /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/,
1296                                         preds
1297                                         )
1298                            );
1299             callerEdgesCopiedToCallee.add( reCaller );
1300           }
1301
1302           // keep traversing nodes reachable from param i
1303           // that we haven't visited yet
1304           if( !visitedInCaller.contains( hrnCaller ) ) {
1305             toVisitInCaller.add( hrnCaller );
1306           }
1307
1308         } // end edge iteration
1309       } // end visiting heap nodes in caller
1310     } // end iterating over parameters as starting points
1311
1312
1313     // find the set of edges in this graph with source
1314     // out-of-context (not in nodes copied) and have a
1315     // destination in context (one of nodes copied) as
1316     // a starting point for building out-of-context nodes
1317     Iterator<HeapRegionNode> itrInContext =
1318       callerNodesCopiedToCallee.iterator();
1319     while( itrInContext.hasNext() ) {
1320       HeapRegionNode hrnCallerAndInContext = itrInContext.next();
1321
1322       Iterator<RefEdge> itrMightCross =
1323         hrnCallerAndInContext.iteratorToReferencers();
1324       while( itrMightCross.hasNext() ) {
1325         RefEdge edgeMightCross = itrMightCross.next();
1326
1327         // we're only interested in edges with a source
1328         // 1) out-of-context and 2) is a heap region
1329         if( callerNodesCopiedToCallee.contains( edgeMightCross.getSrc() ) ||
1330             !(edgeMightCross.getSrc() instanceof HeapRegionNode)
1331             ) {
1332           // then just skip
1333           continue;
1334         }
1335
1336         HeapRegionNode hrnCallerAndOutContext =
1337           (HeapRegionNode) edgeMightCross.getSrc();
1338
1339         // we found a reference that crosses from out-of-context
1340         // to in-context, so build a special out-of-context node
1341         // for the callee IHM and its reference edge
1342         HeapRegionNode hrnCalleeAndOutContext =
1343           rg.createNewHeapRegionNode( null,  // ID
1344                                       false, // single object?
1345                                       false, // new summary?
1346                                       false, // flagged?
1347                                       true,  // out-of-context?
1348                                       hrnCallerAndOutContext.getType(),
1349                                       null,  // alloc site, shouldn't be used
1350                                       /*toShadowTokens( this,*/ hrnCallerAndOutContext.getAlpha() /*)*/, // inherent
1351                                       /*toShadowTokens( this,*/ hrnCallerAndOutContext.getAlpha() /*)*/, // alpha
1352                                       predsEmpty,
1353                                       "out-of-context"
1354                                       );
1355
1356         HeapRegionNode hrnCalleeAndInContext =
1357           rg.id2hrn.get( hrnCallerAndInContext.getID() );
1358
1359         rg.addRefEdge( hrnCalleeAndOutContext,
1360                        hrnCalleeAndInContext,
1361                        new RefEdge( hrnCalleeAndOutContext,
1362                                     hrnCalleeAndInContext,
1363                                     edgeMightCross.getType(),
1364                                     edgeMightCross.getField(),
1365                                     /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/,
1366                                     predsEmpty
1367                                     )
1368                        );
1369       }
1370     }
1371
1372
1373     /*
1374     try {
1375       rg.writeGraph( "calleeview", true, false, false, false, true, true );
1376     } catch( IOException e ) {}
1377
1378
1379     if( fc.getMethod().getSymbol().equals( "addSomething" ) ) {
1380       System.exit( 0 );
1381     }
1382     */
1383
1384     return rg;
1385   }
1386
1387   public void
1388     resolveMethodCall( FlatCall            fc,
1389                        FlatMethod          fm,
1390                        ReachGraph          rgCallee,
1391                        Set<HeapRegionNode> callerNodesCopiedToCallee,
1392                        Set<RefEdge>        callerEdgesCopiedToCallee
1393                        ) {
1394
1395
1396     if( fc.getMethod().getSymbol().equals( "addBar" ) ) {
1397
1398       try {
1399         writeGraph( "caller", true, false, false, false, true, true, callerNodesCopiedToCallee, callerEdgesCopiedToCallee );
1400         rgCallee.writeGraph( "callee", true, false, false, false, true, true );
1401       } catch( IOException e ) {}
1402
1403       //System.exit( 0 );
1404     }
1405
1406
1407     // method call transfer function steps:
1408     // 1. Use current callee-reachable heap (CRH) to test callee
1409     //    predicates and mark what will be coming in.
1410     // 2. Wipe CRH out of caller.
1411     // 3. Transplant marked callee parts in:
1412     //    a) bring in nodes
1413     //    b) bring in callee -> callee edges
1414     //    c) resolve out-of-context -> callee edges
1415     // 4. Global sweep it.
1416
1417
1418
1419     // 1. mark what callee elements have satisfied predicates
1420     Set<HeapRegionNode> calleeNodesSatisfied =
1421       new HashSet<HeapRegionNode>();
1422
1423     Set<RefEdge>        calleeEdgesSatisfied =
1424       new HashSet<RefEdge>();
1425
1426     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1427     while( meItr.hasNext() ) {
1428       Map.Entry      me        = (Map.Entry)      meItr.next();
1429       Integer        id        = (Integer)        me.getKey();
1430       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1431
1432       if( hrnCallee.getPreds().isSatisfiedBy( this,
1433                                               callerNodesCopiedToCallee,
1434                                               callerEdgesCopiedToCallee
1435                                               )
1436           ) {
1437         calleeNodesSatisfied.add( hrnCallee );
1438       }
1439
1440       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencees();
1441       while( reItr.hasNext() ) {
1442         RefEdge reCallee = reItr.next();
1443
1444         if( reCallee.getPreds().isSatisfiedBy( this,
1445                                                callerNodesCopiedToCallee,
1446                                                callerEdgesCopiedToCallee
1447                                                )
1448             ) {
1449           calleeEdgesSatisfied.add( reCallee );
1450         }
1451       }
1452     }
1453
1454
1455     // 2. predicates tested, ok to wipe out caller part
1456     Iterator<HeapRegionNode> hrnItr = callerNodesCopiedToCallee.iterator();
1457     while( hrnItr.hasNext() ) {
1458       HeapRegionNode hrnCaller = hrnItr.next();
1459       wipeOut( hrnCaller );
1460     }
1461
1462
1463     /*
1464     // 3. callee elements with satisfied preds come in
1465
1466     // 3.a) nodes
1467     hrnItr = calleeNodesSatisfied.iterator();
1468     while( hrnItr.hasNext() ) {
1469       HeapRegionNode hrnCallee = hrnItr.next();
1470
1471       if( hrnCallee.isOutOfContext() ) {
1472         continue;
1473       }
1474
1475       HeapRegionNode hrnCaller = id2hrn.get( hrnCallee.getID() );
1476       if( hrnCaller == null ) {
1477         hrnCaller =
1478           createNewHeapRegionNode( hrnCallee.getID(),          // id or null to generate a new one
1479                                    hrnCallee.isSingleObject(), // single object?
1480                                    hrnCallee.isNewSummary(),   // summary?
1481                                    hrnCallee.isFlagged(),      // flagged?
1482                                    false,                      // out-of-context?
1483                                    hrnCallee.getType(),        // type
1484                                    hrnCallee.getAllocSite(),   // allocation site
1485                                    hrnCallee.getInherent(),    // inherent reach
1486                                    null,                       // current reach
1487                                    predsEmpty,                 // predicates
1488                                    hrnCallee.getDescription()  // description
1489                                    );
1490       }
1491
1492       transferOnto( hrnCallee, hrnCaller );
1493     }
1494
1495     // 3.b) callee -> callee edges
1496     Iterator<RefEdge> reItr = calleeEdgesSatisfied.iterator();
1497     while( reItr.hasNext() ) {
1498       RefEdge reCallee = reItr.next();
1499
1500       RefSrcNode rsnCallee = reCallee.getSrc();
1501       RefSrcNode rsnCaller;
1502
1503       if( rsnCallee instanceof VariableNode ) {
1504         VariableNode   vnCallee = (VariableNode) rsnCallee;
1505         TempDescriptor tdParam  = vnCallee.getTempDescriptor();
1506         TempDescriptor tdArg    = fc.getArgMatchingParam( fm,
1507                                                           tdParam );
1508         if( tdArg == null ) {
1509           // this means the variable isn't a parameter, its local
1510           // to the callee so we ignore it in call site transfer
1511           continue;
1512         }
1513
1514         rsnCaller = this.getVariableNodeFromTemp( tdArg );
1515
1516       } else {
1517         HeapRegionNode hrnSrcCallee = (HeapRegionNode) reCallee.getSrc();
1518         rsnCaller = id2hrn.get( hrnSrcCallee.getID() );
1519       }
1520
1521       assert rsnCaller != null;
1522
1523       HeapRegionNode hrnDstCallee = reCallee.getDst();
1524       HeapRegionNode hrnDstCaller = id2hrn.get( hrnDstCallee.getID() );
1525       assert hrnDstCaller != null;
1526
1527       RefEdge reCaller = new RefEdge( rsnCaller,
1528                                       hrnDstCaller,
1529                                       reCallee.getType(),
1530                                       reCallee.getField(),
1531                                       reCallee.getBeta(),
1532                                       reCallee.getPreds()
1533                                       );
1534       addRefEdge( rsnCaller, hrnDstCaller, reCaller );
1535     }
1536
1537     // 3.c) resolve out-of-context -> callee edges
1538     */
1539
1540
1541     // 4.
1542     /*
1543     globalSweep();
1544     */
1545
1546     if( fc.getMethod().getSymbol().equals( "addBar" ) ) {
1547
1548       try {
1549         writeGraph( "callerAfter", true, false, false, false, true, true, null, null );
1550       } catch( IOException e ) {}
1551
1552       //System.exit( 0 );
1553     }
1554
1555   }
1556
1557
1558
1559   ////////////////////////////////////////////////////
1560   //
1561   //  Abstract garbage collection simply removes
1562   //  heap region nodes that are not mechanically
1563   //  reachable from a root set.  This step is
1564   //  essential for testing node and edge existence
1565   //  predicates efficiently
1566   //
1567   ////////////////////////////////////////////////////
1568   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
1569
1570     // calculate a root set, will be different for Java
1571     // version of analysis versus Bamboo version
1572     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
1573
1574     // visit every variable in graph while building root
1575     // set, and do iterating on a copy, so we can remove
1576     // dead variables while we're at this
1577     Iterator makeCopyItr = td2vn.entrySet().iterator();
1578     Set      entrysCopy  = new HashSet();
1579     while( makeCopyItr.hasNext() ) {
1580       entrysCopy.add( makeCopyItr.next() );
1581     }
1582
1583     Iterator eItr = entrysCopy.iterator();
1584     while( eItr.hasNext() ) {
1585       Map.Entry      me = (Map.Entry)      eItr.next();
1586       TempDescriptor td = (TempDescriptor) me.getKey();
1587       VariableNode   vn = (VariableNode)   me.getValue();
1588
1589       if( liveSet.contains( td ) ) {
1590         toVisit.add( vn );
1591
1592       } else {
1593         // dead var, remove completely from graph
1594         td2vn.remove( td );
1595         clearRefEdgesFrom( vn, null, null, true );
1596       }
1597     }
1598
1599     // everything visited in a traversal is
1600     // considered abstractly live
1601     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
1602
1603     while( !toVisit.isEmpty() ) {
1604       RefSrcNode rsn = toVisit.iterator().next();
1605       toVisit.remove( rsn );
1606       visited.add( rsn );
1607
1608       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
1609       while( hrnItr.hasNext() ) {
1610         RefEdge        edge = hrnItr.next();
1611         HeapRegionNode hrn  = edge.getDst();
1612
1613         if( !visited.contains( hrn ) ) {
1614           toVisit.add( hrn );
1615         }
1616       }
1617     }
1618
1619     // get a copy of the set to iterate over because
1620     // we're going to monkey with the graph when we
1621     // identify a garbage node
1622     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
1623     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
1624     while( hrnItr.hasNext() ) {
1625       hrnAllPrior.add( hrnItr.next() );
1626     }
1627
1628     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
1629     while( hrnAllItr.hasNext() ) {
1630       HeapRegionNode hrn = hrnAllItr.next();
1631
1632       if( !visited.contains( hrn ) ) {
1633
1634         // heap region nodes are compared across ReachGraph
1635         // objects by their integer ID, so when discarding
1636         // garbage nodes we must also discard entries in
1637         // the ID -> heap region hashtable.
1638         id2hrn.remove( hrn.getID() );
1639
1640         // RefEdge objects are two-way linked between
1641         // nodes, so when a node is identified as garbage,
1642         // actively clear references to and from it so
1643         // live nodes won't have dangling RefEdge's
1644         wipeOut( hrn );
1645
1646         // if we just removed the last node from an allocation
1647         // site, it should be taken out of the ReachGraph's list
1648         AllocSite as = hrn.getAllocSite();
1649         if( !hasNodesOf( as ) ) {
1650           allocSites.remove( as );
1651         }
1652       }
1653     }
1654   }
1655
1656   protected boolean hasNodesOf( AllocSite as ) {
1657     if( id2hrn.containsKey( as.getSummary() ) ) {
1658       return true;
1659     }
1660
1661     for( int i = 0; i < allocationDepth; ++i ) {
1662       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
1663         return true;
1664       }
1665     }
1666     return false;
1667   }
1668
1669
1670   ////////////////////////////////////////////////////
1671   //
1672   //  This global sweep is an optional step to prune
1673   //  reachability sets that are not internally
1674   //  consistent with the global graph.  It should be
1675   //  invoked after strong updates or method calls.
1676   //
1677   ////////////////////////////////////////////////////
1678   public void globalSweep() {
1679
1680     // boldB is part of the phase 1 sweep
1681     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
1682       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
1683
1684     // visit every heap region to initialize alphaNew and calculate boldB
1685     Iterator itrHrns = id2hrn.entrySet().iterator();
1686     while( itrHrns.hasNext() ) {
1687       Map.Entry      me    = (Map.Entry)      itrHrns.next();
1688       Integer        hrnID = (Integer)        me.getKey();
1689       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
1690
1691       // assert that this node and incoming edges have clean alphaNew
1692       // and betaNew sets, respectively
1693       assert rsetEmpty.equals( hrn.getAlphaNew() );
1694
1695       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
1696       while( itrRers.hasNext() ) {
1697         RefEdge edge = itrRers.next();
1698         assert rsetEmpty.equals( edge.getBetaNew() );
1699       }
1700
1701       // calculate boldB for this flagged node
1702       if( hrn.isFlagged() ) {
1703
1704         Hashtable<RefEdge, ReachSet> boldB_f =
1705           new Hashtable<RefEdge, ReachSet>();
1706
1707         Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
1708
1709         // initial boldB_f constraints
1710         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
1711         while( itrRees.hasNext() ) {
1712           RefEdge edge = itrRees.next();
1713
1714           assert !boldB.containsKey( edge );
1715           boldB_f.put( edge, edge.getBeta() );
1716
1717           assert !workSetEdges.contains( edge );
1718           workSetEdges.add( edge );
1719         }
1720
1721         // enforce the boldB_f constraint at edges until we reach a fixed point
1722         while( !workSetEdges.isEmpty() ) {
1723           RefEdge edge = workSetEdges.iterator().next();
1724           workSetEdges.remove( edge );
1725
1726           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
1727           while( itrPrime.hasNext() ) {
1728             RefEdge edgePrime = itrPrime.next();
1729
1730             ReachSet prevResult   = boldB_f.get( edgePrime );
1731             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
1732                                                             edgePrime.getBeta()
1733                                                             );
1734
1735             if( prevResult == null ||
1736                 Canonical.union( prevResult,
1737                                  intersection ).size() > prevResult.size() ) {
1738
1739               if( prevResult == null ) {
1740                 boldB_f.put( edgePrime,
1741                              Canonical.union( edgePrime.getBeta(),
1742                                               intersection
1743                                               )
1744                              );
1745               } else {
1746                 boldB_f.put( edgePrime,
1747                              Canonical.union( prevResult,
1748                                               intersection
1749                                               )
1750                              );
1751               }
1752               workSetEdges.add( edgePrime );
1753             }
1754           }
1755         }
1756
1757         boldB.put( hrnID, boldB_f );
1758       }
1759     }
1760
1761
1762     // use boldB to prune hrnIDs from alpha states that are impossible
1763     // and propagate the differences backwards across edges
1764     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
1765
1766     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
1767       new Hashtable<RefEdge, ChangeSet>();
1768
1769
1770     itrHrns = id2hrn.entrySet().iterator();
1771     while( itrHrns.hasNext() ) {
1772       Map.Entry      me    = (Map.Entry)      itrHrns.next();
1773       Integer        hrnID = (Integer)        me.getKey();
1774       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
1775
1776       // create the inherent hrnID from a flagged region
1777       // as an exception to removal below
1778       ReachTuple rtException =
1779         ReachTuple.factory( hrnID,
1780                             !hrn.isSingleObject(),
1781                             ReachTuple.ARITY_ONE
1782                             );
1783
1784       ChangeSet cts = ChangeSet.factory();
1785
1786       // mark hrnIDs for removal
1787       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
1788       while( stateItr.hasNext() ) {
1789         ReachState stateOld = stateItr.next();
1790
1791         ReachState markedHrnIDs = ReachState.factory();
1792
1793         Iterator<ReachTuple> rtItr = stateOld.iterator();
1794         while( rtItr.hasNext() ) {
1795           ReachTuple rtOld = rtItr.next();
1796
1797           // never remove the inherent hrnID from a flagged region
1798           // because it is trivially satisfied
1799           if( hrn.isFlagged() ) {
1800             if( rtOld == rtException ) {
1801               continue;
1802             }
1803           }
1804
1805           // does boldB_ttOld allow this hrnID?
1806           boolean foundState = false;
1807           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1808           while( incidentEdgeItr.hasNext() ) {
1809             RefEdge incidentEdge = incidentEdgeItr.next();
1810
1811             // if it isn't allowed, mark for removal
1812             Integer idOld = rtOld.getHrnID();
1813             assert id2hrn.containsKey( idOld );
1814             Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
1815             ReachSet boldB_ttOld_incident = B.get( incidentEdge );
1816             if( boldB_ttOld_incident != null &&
1817                 boldB_ttOld_incident.contains( stateOld ) ) {
1818               foundState = true;
1819             }
1820           }
1821
1822           if( !foundState ) {
1823             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
1824           }
1825         }
1826
1827         // if there is nothing marked, just move on
1828         if( markedHrnIDs.isEmpty() ) {
1829           hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
1830                                             stateOld
1831                                             )
1832                            );
1833           continue;
1834         }
1835
1836         // remove all marked hrnIDs and establish a change set that should
1837         // propagate backwards over edges from this node
1838         ReachState statePruned = ReachState.factory();
1839         rtItr = stateOld.iterator();
1840         while( rtItr.hasNext() ) {
1841           ReachTuple rtOld = rtItr.next();
1842
1843           if( !markedHrnIDs.containsTuple( rtOld ) ) {
1844             statePruned = Canonical.union( statePruned, rtOld );
1845           }
1846         }
1847         assert !stateOld.equals( statePruned );
1848
1849         hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
1850                                           statePruned
1851                                           )
1852                          );
1853         ChangeTuple ct = ChangeTuple.factory( stateOld,
1854                                               statePruned
1855                                               );
1856         cts = Canonical.union( cts, ct );
1857       }
1858
1859       // throw change tuple set on all incident edges
1860       if( !cts.isEmpty() ) {
1861         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1862         while( incidentEdgeItr.hasNext() ) {
1863           RefEdge incidentEdge = incidentEdgeItr.next();
1864
1865           edgesForPropagation.add( incidentEdge );
1866
1867           if( edgePlannedChanges.get( incidentEdge ) == null ) {
1868             edgePlannedChanges.put( incidentEdge, cts );
1869           } else {
1870             edgePlannedChanges.put(
1871                                    incidentEdge,
1872                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
1873                                                     cts
1874                                                     )
1875                                     );
1876           }
1877         }
1878       }
1879     }
1880
1881     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
1882
1883     propagateTokensOverEdges( edgesForPropagation,
1884                               edgePlannedChanges,
1885                               edgesUpdated );
1886
1887     // at the end of the 1st phase reference edges have
1888     // beta, betaNew that correspond to beta and betaR
1889     //
1890     // commit beta<-betaNew, so beta=betaR and betaNew
1891     // will represent the beta' calculation in 2nd phase
1892     //
1893     // commit alpha<-alphaNew because it won't change
1894     HashSet<RefEdge> res = new HashSet<RefEdge>();
1895
1896     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
1897     while( nodeItr.hasNext() ) {
1898       HeapRegionNode hrn = nodeItr.next();
1899       hrn.applyAlphaNew();
1900       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
1901       while( itrRes.hasNext() ) {
1902         res.add( itrRes.next() );
1903       }
1904     }
1905
1906
1907     // 2nd phase
1908     Iterator<RefEdge> edgeItr = res.iterator();
1909     while( edgeItr.hasNext() ) {
1910       RefEdge        edge = edgeItr.next();
1911       HeapRegionNode hrn  = edge.getDst();
1912
1913       // commit results of last phase
1914       if( edgesUpdated.contains( edge ) ) {
1915         edge.applyBetaNew();
1916       }
1917
1918       // compute intial condition of 2nd phase
1919       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
1920                                                hrn.getAlpha()
1921                                                )
1922                        );
1923     }
1924
1925     // every edge in the graph is the initial workset
1926     Set<RefEdge> edgeWorkSet = (Set) res.clone();
1927     while( !edgeWorkSet.isEmpty() ) {
1928       RefEdge edgePrime = edgeWorkSet.iterator().next();
1929       edgeWorkSet.remove( edgePrime );
1930
1931       RefSrcNode rsn = edgePrime.getSrc();
1932       if( !(rsn instanceof HeapRegionNode) ) {
1933         continue;
1934       }
1935       HeapRegionNode hrn = (HeapRegionNode) rsn;
1936
1937       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
1938       while( itrEdge.hasNext() ) {
1939         RefEdge edge = itrEdge.next();
1940
1941         ReachSet prevResult = edge.getBetaNew();
1942         assert prevResult != null;
1943
1944         ReachSet intersection =
1945           Canonical.intersection( edge.getBeta(),
1946                                   edgePrime.getBetaNew()
1947                                   );
1948
1949         if( Canonical.union( prevResult,
1950                              intersection
1951                              ).size() > prevResult.size() ) {
1952           edge.setBetaNew(
1953                           Canonical.union( prevResult,
1954                                            intersection
1955                                            )
1956                            );
1957           edgeWorkSet.add( edge );
1958         }
1959       }
1960     }
1961
1962     // commit beta' (beta<-betaNew)
1963     edgeItr = res.iterator();
1964     while( edgeItr.hasNext() ) {
1965       edgeItr.next().applyBetaNew();
1966     }
1967   }
1968
1969
1970
1971   ////////////////////////////////////////////////////
1972   // high-level merge operations
1973   ////////////////////////////////////////////////////
1974   public void merge_sameMethodContext( ReachGraph rg ) {
1975     // when merging two graphs that abstract the heap
1976     // of the same method context, we just call the
1977     // basic merge operation
1978     merge( rg );
1979   }
1980
1981   public void merge_diffMethodContext( ReachGraph rg ) {
1982     // when merging graphs for abstract heaps in
1983     // different method contexts we should:
1984     // 1) age the allocation sites?
1985     merge( rg );
1986   }
1987
1988   ////////////////////////////////////////////////////
1989   // in merge() and equals() methods the suffix A
1990   // represents the passed in graph and the suffix
1991   // B refers to the graph in this object
1992   // Merging means to take the incoming graph A and
1993   // merge it into B, so after the operation graph B
1994   // is the final result.
1995   ////////////////////////////////////////////////////
1996   protected void merge( ReachGraph rg ) {
1997
1998     if( rg == null ) {
1999       return;
2000     }
2001
2002     mergeNodes     ( rg );
2003     mergeRefEdges  ( rg );
2004     mergeAllocSites( rg );
2005   }
2006
2007   protected void mergeNodes( ReachGraph rg ) {
2008
2009     // start with heap region nodes
2010     Set      sA = rg.id2hrn.entrySet();
2011     Iterator iA = sA.iterator();
2012     while( iA.hasNext() ) {
2013       Map.Entry      meA  = (Map.Entry)      iA.next();
2014       Integer        idA  = (Integer)        meA.getKey();
2015       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2016
2017       // if this graph doesn't have a node the
2018       // incoming graph has, allocate it
2019       if( !id2hrn.containsKey( idA ) ) {
2020         HeapRegionNode hrnB = hrnA.copy();
2021         id2hrn.put( idA, hrnB );
2022
2023       } else {
2024         // otherwise this is a node present in both graphs
2025         // so make the new reachability set a union of the
2026         // nodes' reachability sets
2027         HeapRegionNode hrnB = id2hrn.get( idA );
2028         hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
2029                                         hrnA.getAlpha()
2030                                         )
2031                        );
2032
2033         // if hrnB is already dirty or hrnA is dirty,
2034         // the hrnB should end up dirty: TODO
2035         /*
2036         if( !hrnA.isClean() ) {
2037           hrnB.setIsClean( false );
2038         }
2039         */
2040       }
2041     }
2042
2043     // now add any variable nodes that are in graph B but
2044     // not in A
2045     sA = rg.td2vn.entrySet();
2046     iA = sA.iterator();
2047     while( iA.hasNext() ) {
2048       Map.Entry      meA = (Map.Entry)      iA.next();
2049       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2050       VariableNode   lnA = (VariableNode)   meA.getValue();
2051
2052       // if the variable doesn't exist in B, allocate and add it
2053       VariableNode lnB = getVariableNodeFromTemp( tdA );
2054     }
2055   }
2056
2057   protected void mergeRefEdges( ReachGraph rg ) {
2058
2059     // between heap regions
2060     Set      sA = rg.id2hrn.entrySet();
2061     Iterator iA = sA.iterator();
2062     while( iA.hasNext() ) {
2063       Map.Entry      meA  = (Map.Entry)      iA.next();
2064       Integer        idA  = (Integer)        meA.getKey();
2065       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2066
2067       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2068       while( heapRegionsItrA.hasNext() ) {
2069         RefEdge        edgeA     = heapRegionsItrA.next();
2070         HeapRegionNode hrnChildA = edgeA.getDst();
2071         Integer        idChildA  = hrnChildA.getID();
2072
2073         // at this point we know an edge in graph A exists
2074         // idA -> idChildA, does this exist in B?
2075         assert id2hrn.containsKey( idA );
2076         HeapRegionNode hrnB        = id2hrn.get( idA );
2077         RefEdge        edgeToMerge = null;
2078
2079         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2080         while( heapRegionsItrB.hasNext() &&
2081                edgeToMerge == null          ) {
2082
2083           RefEdge        edgeB     = heapRegionsItrB.next();
2084           HeapRegionNode hrnChildB = edgeB.getDst();
2085           Integer        idChildB  = hrnChildB.getID();
2086
2087           // don't use the RefEdge.equals() here because
2088           // we're talking about existence between graphs,
2089           // not intragraph equal
2090           if( idChildB.equals( idChildA ) &&
2091               edgeB.typeAndFieldEquals( edgeA ) ) {
2092
2093             edgeToMerge = edgeB;
2094           }
2095         }
2096
2097         // if the edge from A was not found in B,
2098         // add it to B.
2099         if( edgeToMerge == null ) {
2100           assert id2hrn.containsKey( idChildA );
2101           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2102           edgeToMerge = edgeA.copy();
2103           edgeToMerge.setSrc( hrnB );
2104           edgeToMerge.setDst( hrnChildB );
2105           addRefEdge( hrnB, hrnChildB, edgeToMerge );
2106         }
2107         // otherwise, the edge already existed in both graphs
2108         // so merge their reachability sets
2109         else {
2110           // just replace this beta set with the union
2111           assert edgeToMerge != null;
2112           edgeToMerge.setBeta(
2113                               Canonical.union( edgeToMerge.getBeta(),
2114                                                edgeA.getBeta()
2115                                                )
2116                               );
2117           // TODO: what?
2118           /*
2119           if( !edgeA.isClean() ) {
2120             edgeToMerge.setIsClean( false );
2121           }
2122           */
2123         }
2124       }
2125     }
2126
2127     // and then again from variable nodes
2128     sA = rg.td2vn.entrySet();
2129     iA = sA.iterator();
2130     while( iA.hasNext() ) {
2131       Map.Entry      meA = (Map.Entry)      iA.next();
2132       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2133       VariableNode   vnA = (VariableNode)   meA.getValue();
2134
2135       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
2136       while( heapRegionsItrA.hasNext() ) {
2137         RefEdge        edgeA     = heapRegionsItrA.next();
2138         HeapRegionNode hrnChildA = edgeA.getDst();
2139         Integer        idChildA  = hrnChildA.getID();
2140
2141         // at this point we know an edge in graph A exists
2142         // tdA -> idChildA, does this exist in B?
2143         assert td2vn.containsKey( tdA );
2144         VariableNode vnB         = td2vn.get( tdA );
2145         RefEdge      edgeToMerge = null;
2146
2147         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
2148         while( heapRegionsItrB.hasNext() &&
2149                edgeToMerge == null          ) {
2150
2151           RefEdge        edgeB     = heapRegionsItrB.next();
2152           HeapRegionNode hrnChildB = edgeB.getDst();
2153           Integer        idChildB  = hrnChildB.getID();
2154
2155           // don't use the RefEdge.equals() here because
2156           // we're talking about existence between graphs
2157           if( idChildB.equals( idChildA ) &&
2158               edgeB.typeAndFieldEquals( edgeA ) ) {
2159
2160             edgeToMerge = edgeB;
2161           }
2162         }
2163
2164         // if the edge from A was not found in B,
2165         // add it to B.
2166         if( edgeToMerge == null ) {
2167           assert id2hrn.containsKey( idChildA );
2168           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2169           edgeToMerge = edgeA.copy();
2170           edgeToMerge.setSrc( vnB );
2171           edgeToMerge.setDst( hrnChildB );
2172           addRefEdge( vnB, hrnChildB, edgeToMerge );
2173         }
2174         // otherwise, the edge already existed in both graphs
2175         // so merge their reachability sets
2176         else {
2177           // just replace this beta set with the union
2178           edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
2179                                                 edgeA.getBeta()
2180                                                 )
2181                                );
2182           // TODO: what?
2183           /*
2184           if( !edgeA.isClean() ) {
2185             edgeToMerge.setIsClean( false );
2186           }
2187           */
2188         }
2189       }
2190     }
2191   }
2192
2193   protected void mergeAllocSites( ReachGraph rg ) {
2194     allocSites.addAll( rg.allocSites );
2195   }
2196
2197
2198   // it is necessary in the equals() member functions
2199   // to "check both ways" when comparing the data
2200   // structures of two graphs.  For instance, if all
2201   // edges between heap region nodes in graph A are
2202   // present and equal in graph B it is not sufficient
2203   // to say the graphs are equal.  Consider that there
2204   // may be edges in graph B that are not in graph A.
2205   // the only way to know that all edges in both graphs
2206   // are equally present is to iterate over both data
2207   // structures and compare against the other graph.
2208   public boolean equals( ReachGraph rg ) {
2209
2210     if( rg == null ) {
2211       return false;
2212     }
2213
2214     if( !areHeapRegionNodesEqual( rg ) ) {
2215       return false;
2216     }
2217
2218     if( !areVariableNodesEqual( rg ) ) {
2219       return false;
2220     }
2221
2222     if( !areRefEdgesEqual( rg ) ) {
2223       return false;
2224     }
2225
2226     // if everything is equal up to this point,
2227     // assert that allocSites is also equal--
2228     // this data is redundant but kept for efficiency
2229     assert allocSites.equals( rg.allocSites );
2230
2231     return true;
2232   }
2233
2234
2235   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
2236
2237     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
2238       return false;
2239     }
2240
2241     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
2242       return false;
2243     }
2244
2245     return true;
2246   }
2247
2248   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
2249                                                         ReachGraph rgB ) {
2250     Set      sA = rgA.id2hrn.entrySet();
2251     Iterator iA = sA.iterator();
2252     while( iA.hasNext() ) {
2253       Map.Entry      meA  = (Map.Entry)      iA.next();
2254       Integer        idA  = (Integer)        meA.getKey();
2255       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2256
2257       if( !rgB.id2hrn.containsKey( idA ) ) {
2258         return false;
2259       }
2260
2261       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2262       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
2263         return false;
2264       }
2265     }
2266
2267     return true;
2268   }
2269
2270
2271   protected boolean areVariableNodesEqual( ReachGraph rg ) {
2272
2273     if( !areallVNinAalsoinBandequal( this, rg ) ) {
2274       return false;
2275     }
2276
2277     if( !areallVNinAalsoinBandequal( rg, this ) ) {
2278       return false;
2279     }
2280
2281     return true;
2282   }
2283
2284   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2285                                                        ReachGraph rgB ) {
2286     Set      sA = rgA.td2vn.entrySet();
2287     Iterator iA = sA.iterator();
2288     while( iA.hasNext() ) {
2289       Map.Entry      meA = (Map.Entry)      iA.next();
2290       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2291
2292       if( !rgB.td2vn.containsKey( tdA ) ) {
2293         return false;
2294       }
2295     }
2296
2297     return true;
2298   }
2299
2300
2301   protected boolean areRefEdgesEqual( ReachGraph rg ) {
2302     if( !areallREinAandBequal( this, rg ) ) {
2303       return false;
2304     }
2305
2306     return true;
2307   }
2308
2309   static protected boolean areallREinAandBequal( ReachGraph rgA,
2310                                                  ReachGraph rgB ) {
2311
2312     // check all the heap region->heap region edges
2313     Set      sA = rgA.id2hrn.entrySet();
2314     Iterator iA = sA.iterator();
2315     while( iA.hasNext() ) {
2316       Map.Entry      meA  = (Map.Entry)      iA.next();
2317       Integer        idA  = (Integer)        meA.getKey();
2318       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2319
2320       // we should have already checked that the same
2321       // heap regions exist in both graphs
2322       assert rgB.id2hrn.containsKey( idA );
2323
2324       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
2325         return false;
2326       }
2327
2328       // then check every edge in B for presence in A, starting
2329       // from the same parent HeapRegionNode
2330       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2331
2332       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
2333         return false;
2334       }
2335     }
2336
2337     // then check all the variable->heap region edges
2338     sA = rgA.td2vn.entrySet();
2339     iA = sA.iterator();
2340     while( iA.hasNext() ) {
2341       Map.Entry      meA = (Map.Entry)      iA.next();
2342       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2343       VariableNode   vnA = (VariableNode)   meA.getValue();
2344
2345       // we should have already checked that the same
2346       // label nodes exist in both graphs
2347       assert rgB.td2vn.containsKey( tdA );
2348
2349       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
2350         return false;
2351       }
2352
2353       // then check every edge in B for presence in A, starting
2354       // from the same parent VariableNode
2355       VariableNode vnB = rgB.td2vn.get( tdA );
2356
2357       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
2358         return false;
2359       }
2360     }
2361
2362     return true;
2363   }
2364
2365
2366   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
2367                                                   RefSrcNode rnA,
2368                                                   ReachGraph rgB ) {
2369
2370     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
2371     while( itrA.hasNext() ) {
2372       RefEdge        edgeA     = itrA.next();
2373       HeapRegionNode hrnChildA = edgeA.getDst();
2374       Integer        idChildA  = hrnChildA.getID();
2375
2376       assert rgB.id2hrn.containsKey( idChildA );
2377
2378       // at this point we know an edge in graph A exists
2379       // rnA -> idChildA, does this exact edge exist in B?
2380       boolean edgeFound = false;
2381
2382       RefSrcNode rnB = null;
2383       if( rnA instanceof HeapRegionNode ) {
2384         HeapRegionNode hrnA = (HeapRegionNode) rnA;
2385         rnB = rgB.id2hrn.get( hrnA.getID() );
2386       } else {
2387         VariableNode vnA = (VariableNode) rnA;
2388         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
2389       }
2390
2391       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
2392       while( itrB.hasNext() ) {
2393         RefEdge        edgeB     = itrB.next();
2394         HeapRegionNode hrnChildB = edgeB.getDst();
2395         Integer        idChildB  = hrnChildB.getID();
2396
2397         if( idChildA.equals( idChildB ) &&
2398             edgeA.typeAndFieldEquals( edgeB ) ) {
2399
2400           // there is an edge in the right place with the right field,
2401           // but do they have the same attributes?
2402           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
2403               edgeA.equalsPreds( edgeB )
2404               ) {
2405             edgeFound = true;
2406           }
2407         }
2408       }
2409
2410       if( !edgeFound ) {
2411         return false;
2412       }
2413     }
2414
2415     return true;
2416   }
2417
2418
2419
2420   // this analysis no longer has the "match anything"
2421   // type which was represented by null
2422   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2423                                              TypeDescriptor td2 ) {
2424     assert td1 != null;
2425     assert td2 != null;
2426
2427     if( td1.isNull() ) {
2428       return td2;
2429     }
2430     if( td2.isNull() ) {
2431       return td1;
2432     }
2433     return typeUtil.mostSpecific( td1, td2 );
2434   }
2435
2436   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2437                                              TypeDescriptor td2,
2438                                              TypeDescriptor td3 ) {
2439
2440     return mostSpecificType( td1,
2441                              mostSpecificType( td2, td3 )
2442                              );
2443   }
2444
2445   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2446                                              TypeDescriptor td2,
2447                                              TypeDescriptor td3,
2448                                              TypeDescriptor td4 ) {
2449
2450     return mostSpecificType( mostSpecificType( td1, td2 ),
2451                              mostSpecificType( td3, td4 )
2452                              );
2453   }
2454
2455   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
2456                                     TypeDescriptor possibleChild ) {
2457     assert possibleSuper != null;
2458     assert possibleChild != null;
2459
2460     if( possibleSuper.isNull() ||
2461         possibleChild.isNull() ) {
2462       return true;
2463     }
2464
2465     return typeUtil.isSuperorType( possibleSuper, possibleChild );
2466   }
2467
2468
2469   protected boolean hasMatchingField( HeapRegionNode src,
2470                                       RefEdge        edge ) {
2471
2472     TypeDescriptor tdSrc = src.getType();
2473     assert tdSrc != null;
2474
2475     if( tdSrc.isArray() ) {
2476       TypeDescriptor td = edge.getType();
2477       assert td != null;
2478
2479       TypeDescriptor tdSrcDeref = tdSrc.dereference();
2480       assert tdSrcDeref != null;
2481
2482       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2483         return false;
2484       }
2485
2486       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
2487     }
2488
2489     // if it's not a class, it doesn't have any fields to match
2490     if( !tdSrc.isClass() ) {
2491       return false;
2492     }
2493
2494     ClassDescriptor cd = tdSrc.getClassDesc();
2495     while( cd != null ) {
2496       Iterator fieldItr = cd.getFields();
2497
2498       while( fieldItr.hasNext() ) {
2499         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
2500
2501         if( fd.getType().equals( edge.getType() ) &&
2502             fd.getSymbol().equals( edge.getField() ) ) {
2503           return true;
2504         }
2505       }
2506
2507       cd = cd.getSuperDesc();
2508     }
2509
2510     // otherwise it is a class with fields
2511     // but we didn't find a match
2512     return false;
2513   }
2514
2515   protected boolean hasMatchingType( RefEdge        edge,
2516                                      HeapRegionNode dst  ) {
2517
2518     // if the region has no type, matches everything
2519     TypeDescriptor tdDst = dst.getType();
2520     assert tdDst != null;
2521
2522     // if the type is not a class or an array, don't
2523     // match because primitives are copied, no aliases
2524     ClassDescriptor cdDst = tdDst.getClassDesc();
2525     if( cdDst == null && !tdDst.isArray() ) {
2526       return false;
2527     }
2528
2529     // if the edge type is null, it matches everything
2530     TypeDescriptor tdEdge = edge.getType();
2531     assert tdEdge != null;
2532
2533     return typeUtil.isSuperorType( tdEdge, tdDst );
2534   }
2535
2536
2537
2538   public void writeGraph( String  graphName,
2539                           boolean writeLabels,
2540                           boolean labelSelect,
2541                           boolean pruneGarbage,
2542                           boolean writeReferencers,
2543                           boolean hideSubsetReachability,
2544                           boolean hideEdgeTaints
2545                           ) throws java.io.IOException {
2546     writeGraph( graphName,
2547                 writeLabels,
2548                 labelSelect,
2549                 pruneGarbage,
2550                 writeReferencers,
2551                 hideSubsetReachability,
2552                 hideEdgeTaints,
2553                 null,
2554                 null );
2555   }
2556
2557   public void writeGraph( String              graphName,
2558                           boolean             writeLabels,
2559                           boolean             labelSelect,
2560                           boolean             pruneGarbage,
2561                           boolean             writeReferencers,
2562                           boolean             hideSubsetReachability,
2563                           boolean             hideEdgeTaints,
2564                           Set<HeapRegionNode> callerNodesCopiedToCallee,
2565                           Set<RefEdge>        callerEdgesCopiedToCallee
2566                           ) throws java.io.IOException {
2567
2568     // remove all non-word characters from the graph name so
2569     // the filename and identifier in dot don't cause errors
2570     graphName = graphName.replaceAll( "[\\W]", "" );
2571
2572     BufferedWriter bw =
2573       new BufferedWriter( new FileWriter( graphName+".dot" ) );
2574
2575     bw.write( "digraph "+graphName+" {\n" );
2576
2577
2578     // this is an optional step to form the callee-reachable
2579     // "cut-out" into a DOT cluster for visualization
2580     if( callerNodesCopiedToCallee != null ) {
2581
2582       bw.write( "  subgraph cluster0 {\n" );
2583       bw.write( "    color=blue;\n" );
2584
2585       Iterator i = id2hrn.entrySet().iterator();
2586       while( i.hasNext() ) {
2587         Map.Entry      me  = (Map.Entry)      i.next();
2588         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2589
2590         if( callerNodesCopiedToCallee.contains( hrn ) ) {
2591           bw.write( "    "+hrn.toString()+
2592                     hrn.toStringDOT( hideSubsetReachability )+
2593                     ";\n" );
2594
2595         }
2596       }
2597
2598       bw.write( "  }\n" );
2599     }
2600
2601
2602     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2603
2604     // then visit every heap region node
2605     Iterator i = id2hrn.entrySet().iterator();
2606     while( i.hasNext() ) {
2607       Map.Entry      me  = (Map.Entry)      i.next();
2608       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2609
2610       // only visit nodes worth writing out--for instance
2611       // not every node at an allocation is referenced
2612       // (think of it as garbage-collected), etc.
2613       if( !pruneGarbage                              ||
2614           (hrn.isFlagged() && hrn.getID() > 0)       ||
2615           hrn.getDescription().startsWith( "param" ) ||
2616           hrn.isOutOfContext()
2617           ) {
2618
2619         if( !visited.contains( hrn ) ) {
2620           traverseHeapRegionNodes( hrn,
2621                                    bw,
2622                                    null,
2623                                    visited,
2624                                    writeReferencers,
2625                                    hideSubsetReachability,
2626                                    hideEdgeTaints,
2627                                    callerNodesCopiedToCallee,
2628                                    callerEdgesCopiedToCallee );
2629         }
2630       }
2631     }
2632
2633     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
2634
2635
2636     // then visit every label node, useful for debugging
2637     if( writeLabels ) {
2638       i = td2vn.entrySet().iterator();
2639       while( i.hasNext() ) {
2640         Map.Entry    me = (Map.Entry)    i.next();
2641         VariableNode vn = (VariableNode) me.getValue();
2642
2643         if( labelSelect ) {
2644           String labelStr = vn.getTempDescriptorString();
2645           if( labelStr.startsWith("___temp") ||
2646               labelStr.startsWith("___dst") ||
2647               labelStr.startsWith("___srctmp") ||
2648               labelStr.startsWith("___neverused")
2649               ) {
2650             continue;
2651           }
2652         }
2653
2654         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
2655         while( heapRegionsItr.hasNext() ) {
2656           RefEdge        edge = heapRegionsItr.next();
2657           HeapRegionNode hrn  = edge.getDst();
2658
2659           if( pruneGarbage && !visited.contains( hrn ) ) {
2660             traverseHeapRegionNodes( hrn,
2661                                      bw,
2662                                      null,
2663                                      visited,
2664                                      writeReferencers,
2665                                      hideSubsetReachability,
2666                                      hideEdgeTaints,
2667                                      callerNodesCopiedToCallee,
2668                                      callerEdgesCopiedToCallee );
2669           }
2670
2671           bw.write( "  "+vn.toString()+
2672                     " -> "+hrn.toString()+
2673                     edge.toStringDOT( hideSubsetReachability, "" )+
2674                     ";\n" );
2675         }
2676       }
2677     }
2678
2679     bw.write( "}\n" );
2680     bw.close();
2681   }
2682
2683   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
2684                                           BufferedWriter      bw,
2685                                           TempDescriptor      td,
2686                                           Set<HeapRegionNode> visited,
2687                                           boolean             writeReferencers,
2688                                           boolean             hideSubsetReachability,
2689                                           boolean             hideEdgeTaints,
2690                                           Set<HeapRegionNode> callerNodesCopiedToCallee,
2691                                           Set<RefEdge>        callerEdgesCopiedToCallee
2692                                           ) throws java.io.IOException {
2693
2694     if( visited.contains( hrn ) ) {
2695       return;
2696     }
2697     visited.add( hrn );
2698
2699     // if we're drawing the callee-view subgraph, only
2700     // write out the node info if it hasn't already been
2701     // written
2702     if( callerNodesCopiedToCallee == null ||
2703         !callerNodesCopiedToCallee.contains( hrn )
2704         ) {
2705       bw.write( "  "+hrn.toString()+
2706                 hrn.toStringDOT( hideSubsetReachability )+
2707                 ";\n" );
2708     }
2709
2710     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
2711     while( childRegionsItr.hasNext() ) {
2712       RefEdge        edge     = childRegionsItr.next();
2713       HeapRegionNode hrnChild = edge.getDst();
2714
2715       if( callerEdgesCopiedToCallee != null &&
2716           callerEdgesCopiedToCallee.contains( hrn )
2717           ) {
2718         bw.write( "  "+hrn.toString()+
2719                   " -> "+hrnChild.toString()+
2720                   edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
2721                   ";\n");
2722       } else {
2723         bw.write( "  "+hrn.toString()+
2724                   " -> "+hrnChild.toString()+
2725                   edge.toStringDOT( hideSubsetReachability, "" )+
2726                   ";\n");
2727       }
2728
2729       traverseHeapRegionNodes( hrnChild,
2730                                bw,
2731                                td,
2732                                visited,
2733                                writeReferencers,
2734                                hideSubsetReachability,
2735                                hideEdgeTaints,
2736                                callerNodesCopiedToCallee,
2737                                callerEdgesCopiedToCallee );
2738     }
2739   }
2740
2741 }