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                     boolean             writeDebugDOTs
1138                     ) {
1139
1140     // the callee view is a new graph: DON'T MODIFY
1141     // *THIS* graph
1142     ReachGraph rg = new ReachGraph();
1143
1144     // track what parts of this graph have already been
1145     // added to callee view, variables not needed.
1146     // Note that we need this because when we traverse
1147     // this caller graph for each parameter we may find
1148     // nodes and edges more than once (which the per-param
1149     // "visit" sets won't show) and we only want to create
1150     // an element in the new callee view one time
1151     //Set callerNodesCopiedToCallee = new HashSet<HeapRegionNode>();
1152     //Set callerEdgesCopiedToCallee = new HashSet<RefEdge>();
1153
1154
1155     // a conservative starting point is to take the
1156     // mechanically-reachable-from-arguments graph
1157     // as opposed to using reachability information
1158     // to prune the graph further
1159     for( int i = 0; i < fm.numParameters(); ++i ) {
1160
1161       // for each parameter index, get the symbol in the
1162       // caller view and callee view
1163
1164       // argument defined here is the symbol in the caller
1165       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
1166
1167       // parameter defined here is the symbol in the callee
1168       TempDescriptor tdParam = fm.getParameter( i );
1169
1170       // use these two VariableNode objects to translate
1171       // between caller and callee--its easy to compare
1172       // a HeapRegionNode across callee and caller because
1173       // they will have the same heap region ID
1174       VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1175       VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1176
1177       // now traverse the calleR view using the argument to
1178       // build the calleE view which has the parameter symbol
1179       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1180       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1181       toVisitInCaller.add( vnCaller );
1182
1183       while( !toVisitInCaller.isEmpty() ) {
1184         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1185         RefSrcNode rsnCallee;
1186
1187         toVisitInCaller.remove( rsnCaller );
1188         visitedInCaller.add( rsnCaller );
1189
1190         // FIRST - setup the source end of an edge, and
1191         // remember the identifying info of the source
1192         // to build predicates
1193         TempDescriptor tdSrc    = null;
1194         Integer        hrnSrcID = null;
1195
1196         if( rsnCaller == vnCaller ) {
1197           // if the caller node is the param symbol, we
1198           // have to do this translation for the callee
1199           rsnCallee = vnCallee;
1200           tdSrc     = tdArg;
1201
1202         } else {
1203           // otherwise the callee-view node is a heap
1204           // region with the same ID, that may or may
1205           // not have been created already
1206           assert rsnCaller instanceof HeapRegionNode;
1207
1208           HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1209           hrnSrcID = hrnSrcCaller.getID();
1210
1211           if( !callerNodesCopiedToCallee.contains( rsnCaller ) ) {
1212
1213             ExistPred pred =
1214               ExistPred.factory( hrnSrcID, null );
1215
1216             ExistPredSet preds =
1217               ExistPredSet.factory( pred );
1218
1219             rsnCallee =
1220               rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1221                                           hrnSrcCaller.isSingleObject(),
1222                                           hrnSrcCaller.isNewSummary(),
1223                                           hrnSrcCaller.isFlagged(),
1224                                           false, // out-of-context?
1225                                           hrnSrcCaller.getType(),
1226                                           hrnSrcCaller.getAllocSite(),
1227                                           /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/,
1228                                           /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/,
1229                                           preds,
1230                                           hrnSrcCaller.getDescription()
1231                                           );
1232             callerNodesCopiedToCallee.add( (HeapRegionNode) rsnCaller );
1233
1234           } else {
1235             rsnCallee = rg.id2hrn.get( hrnSrcID );
1236           }
1237         }
1238
1239         // SECOND - go over all edges from that source
1240
1241         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1242         while( itrRefEdges.hasNext() ) {
1243           RefEdge        reCaller  = itrRefEdges.next();
1244           HeapRegionNode hrnCaller = reCaller.getDst();
1245           HeapRegionNode hrnCallee;
1246
1247           // THIRD - setup destination ends of edges
1248           Integer hrnDstID = hrnCaller.getID();
1249
1250           if( !callerNodesCopiedToCallee.contains( hrnCaller ) ) {
1251
1252             ExistPred pred =
1253               ExistPred.factory( hrnDstID, null );
1254
1255             ExistPredSet preds =
1256               ExistPredSet.factory( pred );
1257
1258             hrnCallee =
1259               rg.createNewHeapRegionNode( hrnCaller.getID(),
1260                                           hrnCaller.isSingleObject(),
1261                                           hrnCaller.isNewSummary(),
1262                                           hrnCaller.isFlagged(),
1263                                           false, // out-of-context?
1264                                           hrnCaller.getType(),
1265                                           hrnCaller.getAllocSite(),
1266                                           /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/,
1267                                           /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/,
1268                                           preds,
1269                                           hrnCaller.getDescription()
1270                                           );
1271             callerNodesCopiedToCallee.add( hrnCaller );
1272           } else {
1273             hrnCallee = rg.id2hrn.get( hrnDstID );
1274           }
1275
1276           // FOURTH - copy edge over if needed
1277           if( !callerEdgesCopiedToCallee.contains( reCaller ) ) {
1278
1279             ExistPred pred =
1280               ExistPred.factory( tdSrc,
1281                                  hrnSrcID,
1282                                  hrnDstID,
1283                                  reCaller.getType(),
1284                                  reCaller.getField(),
1285                                  null );
1286
1287             ExistPredSet preds =
1288               ExistPredSet.factory( pred );
1289
1290             rg.addRefEdge( rsnCallee,
1291                            hrnCallee,
1292                            new RefEdge( rsnCallee,
1293                                         hrnCallee,
1294                                         reCaller.getType(),
1295                                         reCaller.getField(),
1296                                         /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/,
1297                                         preds
1298                                         )
1299                            );
1300             callerEdgesCopiedToCallee.add( reCaller );
1301           }
1302
1303           // keep traversing nodes reachable from param i
1304           // that we haven't visited yet
1305           if( !visitedInCaller.contains( hrnCaller ) ) {
1306             toVisitInCaller.add( hrnCaller );
1307           }
1308
1309         } // end edge iteration
1310       } // end visiting heap nodes in caller
1311     } // end iterating over parameters as starting points
1312
1313
1314     // find the set of edges in this graph with source
1315     // out-of-context (not in nodes copied) and have a
1316     // destination in context (one of nodes copied) as
1317     // a starting point for building out-of-context nodes
1318     Iterator<HeapRegionNode> itrInContext =
1319       callerNodesCopiedToCallee.iterator();
1320     while( itrInContext.hasNext() ) {
1321       HeapRegionNode hrnCallerAndInContext = itrInContext.next();
1322
1323       Iterator<RefEdge> itrMightCross =
1324         hrnCallerAndInContext.iteratorToReferencers();
1325       while( itrMightCross.hasNext() ) {
1326         RefEdge edgeMightCross = itrMightCross.next();
1327
1328         // we're only interested in edges with a source
1329         // 1) out-of-context and 2) is a heap region
1330         if( callerNodesCopiedToCallee.contains( edgeMightCross.getSrc() ) ||
1331             !(edgeMightCross.getSrc() instanceof HeapRegionNode)
1332             ) {
1333           // then just skip
1334           continue;
1335         }
1336
1337         HeapRegionNode hrnCallerAndOutContext =
1338           (HeapRegionNode) edgeMightCross.getSrc();
1339
1340         // we found a reference that crosses from out-of-context
1341         // to in-context, so build a special out-of-context node
1342         // for the callee IHM and its reference edge
1343         HeapRegionNode hrnCalleeAndOutContext =
1344           rg.createNewHeapRegionNode( null,  // ID
1345                                       false, // single object?
1346                                       false, // new summary?
1347                                       false, // flagged?
1348                                       true,  // out-of-context?
1349                                       hrnCallerAndOutContext.getType(),
1350                                       null,  // alloc site, shouldn't be used
1351                                       /*toShadowTokens( this,*/ hrnCallerAndOutContext.getAlpha() /*)*/, // inherent
1352                                       /*toShadowTokens( this,*/ hrnCallerAndOutContext.getAlpha() /*)*/, // alpha
1353                                       predsEmpty,
1354                                       "out-of-context"
1355                                       );
1356
1357         HeapRegionNode hrnCalleeAndInContext =
1358           rg.id2hrn.get( hrnCallerAndInContext.getID() );
1359
1360         rg.addRefEdge( hrnCalleeAndOutContext,
1361                        hrnCalleeAndInContext,
1362                        new RefEdge( hrnCalleeAndOutContext,
1363                                     hrnCalleeAndInContext,
1364                                     edgeMightCross.getType(),
1365                                     edgeMightCross.getField(),
1366                                     /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/,
1367                                     predsEmpty
1368                                     )
1369                        );
1370       }
1371     }
1372
1373
1374     if( writeDebugDOTs ) {
1375       try {
1376         rg.writeGraph( "calleeview", true, false, false, false, true, true );
1377       } catch( IOException e ) {}
1378     }
1379
1380
1381     return rg;
1382   }
1383
1384   public void
1385     resolveMethodCall( FlatCall            fc,
1386                        FlatMethod          fm,
1387                        ReachGraph          rgCallee,
1388                        Set<HeapRegionNode> callerNodesCopiedToCallee,
1389                        Set<RefEdge>        callerEdgesCopiedToCallee,
1390                        boolean             writeDebugDOTs
1391                        ) {
1392
1393
1394     if( writeDebugDOTs ) {
1395       try {
1396         this.writeGraph( "caller", true, false, false, false, true, true,
1397                          callerNodesCopiedToCallee, callerEdgesCopiedToCallee );
1398         rgCallee.writeGraph( "callee", true, false, false, false, true, true );
1399       } catch( IOException e ) {}
1400     }
1401
1402
1403     // method call transfer function steps:
1404     // 1. Use current callee-reachable heap (CRH) to test callee
1405     //    predicates and mark what will be coming in.
1406     // 2. Wipe CRH out of caller.
1407     // 3. Transplant marked callee parts in:
1408     //    a) bring in nodes
1409     //    b) bring in callee -> callee edges
1410     //    c) resolve out-of-context -> callee edges
1411     // 4. Global sweep it.
1412
1413
1414     System.out.println( );
1415
1416
1417
1418     // 1. mark what callee elements have satisfied predicates
1419     Set<HeapRegionNode> calleeNodesSatisfied =
1420       new HashSet<HeapRegionNode>();
1421
1422     Set<RefEdge>        calleeEdgesSatisfied =
1423       new HashSet<RefEdge>();
1424
1425     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1426     while( meItr.hasNext() ) {
1427       Map.Entry      me        = (Map.Entry)      meItr.next();
1428       Integer        id        = (Integer)        me.getKey();
1429       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1430
1431       if( hrnCallee.getPreds().isSatisfiedBy( this,
1432                                               callerNodesCopiedToCallee,
1433                                               callerEdgesCopiedToCallee
1434                                               )
1435           ) {
1436         calleeNodesSatisfied.add( hrnCallee );
1437
1438
1439
1440
1441
1442       }
1443
1444       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencees();
1445       while( reItr.hasNext() ) {
1446         RefEdge reCallee = reItr.next();
1447
1448         if( reCallee.getPreds().isSatisfiedBy( this,
1449                                                callerNodesCopiedToCallee,
1450                                                callerEdgesCopiedToCallee
1451                                                )
1452             ) {
1453           calleeEdgesSatisfied.add( reCallee );
1454         }
1455       }
1456     }
1457
1458
1459     // 2. predicates tested, ok to wipe out caller part
1460     Iterator<HeapRegionNode> hrnItr = callerNodesCopiedToCallee.iterator();
1461     while( hrnItr.hasNext() ) {
1462       HeapRegionNode hrnCaller = hrnItr.next();
1463       wipeOut( hrnCaller );
1464     }
1465
1466
1467     // 3. callee elements with satisfied preds come in
1468
1469     // 3.a) nodes
1470     hrnItr = calleeNodesSatisfied.iterator();
1471     while( hrnItr.hasNext() ) {
1472       HeapRegionNode hrnCallee = hrnItr.next();
1473
1474       if( hrnCallee.isOutOfContext() ) {
1475         continue;
1476       }
1477
1478       HeapRegionNode hrnCaller = id2hrn.get( hrnCallee.getID() );
1479       if( hrnCaller == null ) {
1480         hrnCaller =
1481           createNewHeapRegionNode( hrnCallee.getID(),          // id or null to generate a new one
1482                                    hrnCallee.isSingleObject(), // single object?
1483                                    hrnCallee.isNewSummary(),   // summary?
1484                                    hrnCallee.isFlagged(),      // flagged?
1485                                    false,                      // out-of-context?
1486                                    hrnCallee.getType(),        // type
1487                                    hrnCallee.getAllocSite(),   // allocation site
1488                                    hrnCallee.getInherent(),    // inherent reach
1489                                    null,                       // current reach
1490                                    predsEmpty,                 // predicates
1491                                    hrnCallee.getDescription()  // description
1492                                    );
1493       }
1494
1495       transferOnto( hrnCallee, hrnCaller );
1496     }
1497
1498     // 3.b) callee -> callee edges
1499     Iterator<RefEdge> reItr = calleeEdgesSatisfied.iterator();
1500     while( reItr.hasNext() ) {
1501       RefEdge reCallee = reItr.next();
1502
1503       RefSrcNode rsnCallee = reCallee.getSrc();
1504       RefSrcNode rsnCaller;
1505
1506       if( rsnCallee instanceof VariableNode ) {
1507         VariableNode   vnCallee = (VariableNode) rsnCallee;
1508         TempDescriptor tdParam  = vnCallee.getTempDescriptor();
1509         TempDescriptor tdArg    = fc.getArgMatchingParam( fm,
1510                                                           tdParam );
1511         if( tdArg == null ) {
1512           // this means the variable isn't a parameter, its local
1513           // to the callee so we ignore it in call site transfer
1514           continue;
1515         }
1516
1517         rsnCaller = this.getVariableNodeFromTemp( tdArg );
1518
1519       } else {
1520         HeapRegionNode hrnSrcCallee = (HeapRegionNode) reCallee.getSrc();
1521         rsnCaller = id2hrn.get( hrnSrcCallee.getID() );
1522       }
1523
1524       assert rsnCaller != null;
1525
1526       HeapRegionNode hrnDstCallee = reCallee.getDst();
1527       HeapRegionNode hrnDstCaller = id2hrn.get( hrnDstCallee.getID() );
1528       assert hrnDstCaller != null;
1529
1530       RefEdge reCaller = new RefEdge( rsnCaller,
1531                                       hrnDstCaller,
1532                                       reCallee.getType(),
1533                                       reCallee.getField(),
1534                                       reCallee.getBeta(),
1535                                       reCallee.getPreds()
1536                                       );
1537       addRefEdge( rsnCaller, hrnDstCaller, reCaller );
1538     }
1539
1540     // 3.c) resolve out-of-context -> callee edges
1541
1542
1543
1544     // 4.
1545     /*
1546     globalSweep();
1547     */
1548
1549     if( writeDebugDOTs ) {
1550       try {
1551         writeGraph( "callerAfter",
1552                     true, false, false, false, true, true,
1553                     null, null );
1554       } catch( IOException e ) {}
1555     }
1556
1557   }
1558
1559
1560
1561   ////////////////////////////////////////////////////
1562   //
1563   //  Abstract garbage collection simply removes
1564   //  heap region nodes that are not mechanically
1565   //  reachable from a root set.  This step is
1566   //  essential for testing node and edge existence
1567   //  predicates efficiently
1568   //
1569   ////////////////////////////////////////////////////
1570   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
1571
1572     // calculate a root set, will be different for Java
1573     // version of analysis versus Bamboo version
1574     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
1575
1576     // visit every variable in graph while building root
1577     // set, and do iterating on a copy, so we can remove
1578     // dead variables while we're at this
1579     Iterator makeCopyItr = td2vn.entrySet().iterator();
1580     Set      entrysCopy  = new HashSet();
1581     while( makeCopyItr.hasNext() ) {
1582       entrysCopy.add( makeCopyItr.next() );
1583     }
1584
1585     Iterator eItr = entrysCopy.iterator();
1586     while( eItr.hasNext() ) {
1587       Map.Entry      me = (Map.Entry)      eItr.next();
1588       TempDescriptor td = (TempDescriptor) me.getKey();
1589       VariableNode   vn = (VariableNode)   me.getValue();
1590
1591       if( liveSet.contains( td ) ) {
1592         toVisit.add( vn );
1593
1594       } else {
1595         // dead var, remove completely from graph
1596         td2vn.remove( td );
1597         clearRefEdgesFrom( vn, null, null, true );
1598       }
1599     }
1600
1601     // everything visited in a traversal is
1602     // considered abstractly live
1603     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
1604
1605     while( !toVisit.isEmpty() ) {
1606       RefSrcNode rsn = toVisit.iterator().next();
1607       toVisit.remove( rsn );
1608       visited.add( rsn );
1609
1610       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
1611       while( hrnItr.hasNext() ) {
1612         RefEdge        edge = hrnItr.next();
1613         HeapRegionNode hrn  = edge.getDst();
1614
1615         if( !visited.contains( hrn ) ) {
1616           toVisit.add( hrn );
1617         }
1618       }
1619     }
1620
1621     // get a copy of the set to iterate over because
1622     // we're going to monkey with the graph when we
1623     // identify a garbage node
1624     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
1625     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
1626     while( hrnItr.hasNext() ) {
1627       hrnAllPrior.add( hrnItr.next() );
1628     }
1629
1630     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
1631     while( hrnAllItr.hasNext() ) {
1632       HeapRegionNode hrn = hrnAllItr.next();
1633
1634       if( !visited.contains( hrn ) ) {
1635
1636         // heap region nodes are compared across ReachGraph
1637         // objects by their integer ID, so when discarding
1638         // garbage nodes we must also discard entries in
1639         // the ID -> heap region hashtable.
1640         id2hrn.remove( hrn.getID() );
1641
1642         // RefEdge objects are two-way linked between
1643         // nodes, so when a node is identified as garbage,
1644         // actively clear references to and from it so
1645         // live nodes won't have dangling RefEdge's
1646         wipeOut( hrn );
1647
1648         // if we just removed the last node from an allocation
1649         // site, it should be taken out of the ReachGraph's list
1650         AllocSite as = hrn.getAllocSite();
1651         if( !hasNodesOf( as ) ) {
1652           allocSites.remove( as );
1653         }
1654       }
1655     }
1656   }
1657
1658   protected boolean hasNodesOf( AllocSite as ) {
1659     if( id2hrn.containsKey( as.getSummary() ) ) {
1660       return true;
1661     }
1662
1663     for( int i = 0; i < allocationDepth; ++i ) {
1664       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
1665         return true;
1666       }
1667     }
1668     return false;
1669   }
1670
1671
1672   ////////////////////////////////////////////////////
1673   //
1674   //  This global sweep is an optional step to prune
1675   //  reachability sets that are not internally
1676   //  consistent with the global graph.  It should be
1677   //  invoked after strong updates or method calls.
1678   //
1679   ////////////////////////////////////////////////////
1680   public void globalSweep() {
1681
1682     // boldB is part of the phase 1 sweep
1683     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
1684       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
1685
1686     // visit every heap region to initialize alphaNew and calculate boldB
1687     Iterator itrHrns = id2hrn.entrySet().iterator();
1688     while( itrHrns.hasNext() ) {
1689       Map.Entry      me    = (Map.Entry)      itrHrns.next();
1690       Integer        hrnID = (Integer)        me.getKey();
1691       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
1692
1693       // assert that this node and incoming edges have clean alphaNew
1694       // and betaNew sets, respectively
1695       assert rsetEmpty.equals( hrn.getAlphaNew() );
1696
1697       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
1698       while( itrRers.hasNext() ) {
1699         RefEdge edge = itrRers.next();
1700         assert rsetEmpty.equals( edge.getBetaNew() );
1701       }
1702
1703       // calculate boldB for this flagged node
1704       if( hrn.isFlagged() ) {
1705
1706         Hashtable<RefEdge, ReachSet> boldB_f =
1707           new Hashtable<RefEdge, ReachSet>();
1708
1709         Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
1710
1711         // initial boldB_f constraints
1712         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
1713         while( itrRees.hasNext() ) {
1714           RefEdge edge = itrRees.next();
1715
1716           assert !boldB.containsKey( edge );
1717           boldB_f.put( edge, edge.getBeta() );
1718
1719           assert !workSetEdges.contains( edge );
1720           workSetEdges.add( edge );
1721         }
1722
1723         // enforce the boldB_f constraint at edges until we reach a fixed point
1724         while( !workSetEdges.isEmpty() ) {
1725           RefEdge edge = workSetEdges.iterator().next();
1726           workSetEdges.remove( edge );
1727
1728           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
1729           while( itrPrime.hasNext() ) {
1730             RefEdge edgePrime = itrPrime.next();
1731
1732             ReachSet prevResult   = boldB_f.get( edgePrime );
1733             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
1734                                                             edgePrime.getBeta()
1735                                                             );
1736
1737             if( prevResult == null ||
1738                 Canonical.union( prevResult,
1739                                  intersection ).size() > prevResult.size() ) {
1740
1741               if( prevResult == null ) {
1742                 boldB_f.put( edgePrime,
1743                              Canonical.union( edgePrime.getBeta(),
1744                                               intersection
1745                                               )
1746                              );
1747               } else {
1748                 boldB_f.put( edgePrime,
1749                              Canonical.union( prevResult,
1750                                               intersection
1751                                               )
1752                              );
1753               }
1754               workSetEdges.add( edgePrime );
1755             }
1756           }
1757         }
1758
1759         boldB.put( hrnID, boldB_f );
1760       }
1761     }
1762
1763
1764     // use boldB to prune hrnIDs from alpha states that are impossible
1765     // and propagate the differences backwards across edges
1766     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
1767
1768     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
1769       new Hashtable<RefEdge, ChangeSet>();
1770
1771
1772     itrHrns = id2hrn.entrySet().iterator();
1773     while( itrHrns.hasNext() ) {
1774       Map.Entry      me    = (Map.Entry)      itrHrns.next();
1775       Integer        hrnID = (Integer)        me.getKey();
1776       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
1777
1778       // create the inherent hrnID from a flagged region
1779       // as an exception to removal below
1780       ReachTuple rtException =
1781         ReachTuple.factory( hrnID,
1782                             !hrn.isSingleObject(),
1783                             ReachTuple.ARITY_ONE
1784                             );
1785
1786       ChangeSet cts = ChangeSet.factory();
1787
1788       // mark hrnIDs for removal
1789       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
1790       while( stateItr.hasNext() ) {
1791         ReachState stateOld = stateItr.next();
1792
1793         ReachState markedHrnIDs = ReachState.factory();
1794
1795         Iterator<ReachTuple> rtItr = stateOld.iterator();
1796         while( rtItr.hasNext() ) {
1797           ReachTuple rtOld = rtItr.next();
1798
1799           // never remove the inherent hrnID from a flagged region
1800           // because it is trivially satisfied
1801           if( hrn.isFlagged() ) {
1802             if( rtOld == rtException ) {
1803               continue;
1804             }
1805           }
1806
1807           // does boldB_ttOld allow this hrnID?
1808           boolean foundState = false;
1809           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1810           while( incidentEdgeItr.hasNext() ) {
1811             RefEdge incidentEdge = incidentEdgeItr.next();
1812
1813             // if it isn't allowed, mark for removal
1814             Integer idOld = rtOld.getHrnID();
1815             assert id2hrn.containsKey( idOld );
1816             Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
1817             ReachSet boldB_ttOld_incident = B.get( incidentEdge );
1818             if( boldB_ttOld_incident != null &&
1819                 boldB_ttOld_incident.contains( stateOld ) ) {
1820               foundState = true;
1821             }
1822           }
1823
1824           if( !foundState ) {
1825             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
1826           }
1827         }
1828
1829         // if there is nothing marked, just move on
1830         if( markedHrnIDs.isEmpty() ) {
1831           hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
1832                                             stateOld
1833                                             )
1834                            );
1835           continue;
1836         }
1837
1838         // remove all marked hrnIDs and establish a change set that should
1839         // propagate backwards over edges from this node
1840         ReachState statePruned = ReachState.factory();
1841         rtItr = stateOld.iterator();
1842         while( rtItr.hasNext() ) {
1843           ReachTuple rtOld = rtItr.next();
1844
1845           if( !markedHrnIDs.containsTuple( rtOld ) ) {
1846             statePruned = Canonical.union( statePruned, rtOld );
1847           }
1848         }
1849         assert !stateOld.equals( statePruned );
1850
1851         hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
1852                                           statePruned
1853                                           )
1854                          );
1855         ChangeTuple ct = ChangeTuple.factory( stateOld,
1856                                               statePruned
1857                                               );
1858         cts = Canonical.union( cts, ct );
1859       }
1860
1861       // throw change tuple set on all incident edges
1862       if( !cts.isEmpty() ) {
1863         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1864         while( incidentEdgeItr.hasNext() ) {
1865           RefEdge incidentEdge = incidentEdgeItr.next();
1866
1867           edgesForPropagation.add( incidentEdge );
1868
1869           if( edgePlannedChanges.get( incidentEdge ) == null ) {
1870             edgePlannedChanges.put( incidentEdge, cts );
1871           } else {
1872             edgePlannedChanges.put(
1873                                    incidentEdge,
1874                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
1875                                                     cts
1876                                                     )
1877                                     );
1878           }
1879         }
1880       }
1881     }
1882
1883     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
1884
1885     propagateTokensOverEdges( edgesForPropagation,
1886                               edgePlannedChanges,
1887                               edgesUpdated );
1888
1889     // at the end of the 1st phase reference edges have
1890     // beta, betaNew that correspond to beta and betaR
1891     //
1892     // commit beta<-betaNew, so beta=betaR and betaNew
1893     // will represent the beta' calculation in 2nd phase
1894     //
1895     // commit alpha<-alphaNew because it won't change
1896     HashSet<RefEdge> res = new HashSet<RefEdge>();
1897
1898     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
1899     while( nodeItr.hasNext() ) {
1900       HeapRegionNode hrn = nodeItr.next();
1901       hrn.applyAlphaNew();
1902       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
1903       while( itrRes.hasNext() ) {
1904         res.add( itrRes.next() );
1905       }
1906     }
1907
1908
1909     // 2nd phase
1910     Iterator<RefEdge> edgeItr = res.iterator();
1911     while( edgeItr.hasNext() ) {
1912       RefEdge        edge = edgeItr.next();
1913       HeapRegionNode hrn  = edge.getDst();
1914
1915       // commit results of last phase
1916       if( edgesUpdated.contains( edge ) ) {
1917         edge.applyBetaNew();
1918       }
1919
1920       // compute intial condition of 2nd phase
1921       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
1922                                                hrn.getAlpha()
1923                                                )
1924                        );
1925     }
1926
1927     // every edge in the graph is the initial workset
1928     Set<RefEdge> edgeWorkSet = (Set) res.clone();
1929     while( !edgeWorkSet.isEmpty() ) {
1930       RefEdge edgePrime = edgeWorkSet.iterator().next();
1931       edgeWorkSet.remove( edgePrime );
1932
1933       RefSrcNode rsn = edgePrime.getSrc();
1934       if( !(rsn instanceof HeapRegionNode) ) {
1935         continue;
1936       }
1937       HeapRegionNode hrn = (HeapRegionNode) rsn;
1938
1939       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
1940       while( itrEdge.hasNext() ) {
1941         RefEdge edge = itrEdge.next();
1942
1943         ReachSet prevResult = edge.getBetaNew();
1944         assert prevResult != null;
1945
1946         ReachSet intersection =
1947           Canonical.intersection( edge.getBeta(),
1948                                   edgePrime.getBetaNew()
1949                                   );
1950
1951         if( Canonical.union( prevResult,
1952                              intersection
1953                              ).size() > prevResult.size() ) {
1954           edge.setBetaNew(
1955                           Canonical.union( prevResult,
1956                                            intersection
1957                                            )
1958                            );
1959           edgeWorkSet.add( edge );
1960         }
1961       }
1962     }
1963
1964     // commit beta' (beta<-betaNew)
1965     edgeItr = res.iterator();
1966     while( edgeItr.hasNext() ) {
1967       edgeItr.next().applyBetaNew();
1968     }
1969   }
1970
1971
1972
1973   ////////////////////////////////////////////////////
1974   // high-level merge operations
1975   ////////////////////////////////////////////////////
1976   public void merge_sameMethodContext( ReachGraph rg ) {
1977     // when merging two graphs that abstract the heap
1978     // of the same method context, we just call the
1979     // basic merge operation
1980     merge( rg );
1981   }
1982
1983   public void merge_diffMethodContext( ReachGraph rg ) {
1984     // when merging graphs for abstract heaps in
1985     // different method contexts we should:
1986     // 1) age the allocation sites?
1987     merge( rg );
1988   }
1989
1990   ////////////////////////////////////////////////////
1991   // in merge() and equals() methods the suffix A
1992   // represents the passed in graph and the suffix
1993   // B refers to the graph in this object
1994   // Merging means to take the incoming graph A and
1995   // merge it into B, so after the operation graph B
1996   // is the final result.
1997   ////////////////////////////////////////////////////
1998   protected void merge( ReachGraph rg ) {
1999
2000     if( rg == null ) {
2001       return;
2002     }
2003
2004     mergeNodes     ( rg );
2005     mergeRefEdges  ( rg );
2006     mergeAllocSites( rg );
2007   }
2008
2009   protected void mergeNodes( ReachGraph rg ) {
2010
2011     // start with heap region nodes
2012     Set      sA = rg.id2hrn.entrySet();
2013     Iterator iA = sA.iterator();
2014     while( iA.hasNext() ) {
2015       Map.Entry      meA  = (Map.Entry)      iA.next();
2016       Integer        idA  = (Integer)        meA.getKey();
2017       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2018
2019       // if this graph doesn't have a node the
2020       // incoming graph has, allocate it
2021       if( !id2hrn.containsKey( idA ) ) {
2022         HeapRegionNode hrnB = hrnA.copy();
2023         id2hrn.put( idA, hrnB );
2024
2025       } else {
2026         // otherwise this is a node present in both graphs
2027         // so make the new reachability set a union of the
2028         // nodes' reachability sets
2029         HeapRegionNode hrnB = id2hrn.get( idA );
2030         hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
2031                                         hrnA.getAlpha()
2032                                         )
2033                        );
2034
2035         // if hrnB is already dirty or hrnA is dirty,
2036         // the hrnB should end up dirty: TODO
2037         /*
2038         if( !hrnA.isClean() ) {
2039           hrnB.setIsClean( false );
2040         }
2041         */
2042       }
2043     }
2044
2045     // now add any variable nodes that are in graph B but
2046     // not in A
2047     sA = rg.td2vn.entrySet();
2048     iA = sA.iterator();
2049     while( iA.hasNext() ) {
2050       Map.Entry      meA = (Map.Entry)      iA.next();
2051       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2052       VariableNode   lnA = (VariableNode)   meA.getValue();
2053
2054       // if the variable doesn't exist in B, allocate and add it
2055       VariableNode lnB = getVariableNodeFromTemp( tdA );
2056     }
2057   }
2058
2059   protected void mergeRefEdges( ReachGraph rg ) {
2060
2061     // between heap regions
2062     Set      sA = rg.id2hrn.entrySet();
2063     Iterator iA = sA.iterator();
2064     while( iA.hasNext() ) {
2065       Map.Entry      meA  = (Map.Entry)      iA.next();
2066       Integer        idA  = (Integer)        meA.getKey();
2067       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2068
2069       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2070       while( heapRegionsItrA.hasNext() ) {
2071         RefEdge        edgeA     = heapRegionsItrA.next();
2072         HeapRegionNode hrnChildA = edgeA.getDst();
2073         Integer        idChildA  = hrnChildA.getID();
2074
2075         // at this point we know an edge in graph A exists
2076         // idA -> idChildA, does this exist in B?
2077         assert id2hrn.containsKey( idA );
2078         HeapRegionNode hrnB        = id2hrn.get( idA );
2079         RefEdge        edgeToMerge = null;
2080
2081         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2082         while( heapRegionsItrB.hasNext() &&
2083                edgeToMerge == null          ) {
2084
2085           RefEdge        edgeB     = heapRegionsItrB.next();
2086           HeapRegionNode hrnChildB = edgeB.getDst();
2087           Integer        idChildB  = hrnChildB.getID();
2088
2089           // don't use the RefEdge.equals() here because
2090           // we're talking about existence between graphs,
2091           // not intragraph equal
2092           if( idChildB.equals( idChildA ) &&
2093               edgeB.typeAndFieldEquals( edgeA ) ) {
2094
2095             edgeToMerge = edgeB;
2096           }
2097         }
2098
2099         // if the edge from A was not found in B,
2100         // add it to B.
2101         if( edgeToMerge == null ) {
2102           assert id2hrn.containsKey( idChildA );
2103           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2104           edgeToMerge = edgeA.copy();
2105           edgeToMerge.setSrc( hrnB );
2106           edgeToMerge.setDst( hrnChildB );
2107           addRefEdge( hrnB, hrnChildB, edgeToMerge );
2108         }
2109         // otherwise, the edge already existed in both graphs
2110         // so merge their reachability sets
2111         else {
2112           // just replace this beta set with the union
2113           assert edgeToMerge != null;
2114           edgeToMerge.setBeta(
2115                               Canonical.union( edgeToMerge.getBeta(),
2116                                                edgeA.getBeta()
2117                                                )
2118                               );
2119           // TODO: what?
2120           /*
2121           if( !edgeA.isClean() ) {
2122             edgeToMerge.setIsClean( false );
2123           }
2124           */
2125         }
2126       }
2127     }
2128
2129     // and then again from variable nodes
2130     sA = rg.td2vn.entrySet();
2131     iA = sA.iterator();
2132     while( iA.hasNext() ) {
2133       Map.Entry      meA = (Map.Entry)      iA.next();
2134       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2135       VariableNode   vnA = (VariableNode)   meA.getValue();
2136
2137       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
2138       while( heapRegionsItrA.hasNext() ) {
2139         RefEdge        edgeA     = heapRegionsItrA.next();
2140         HeapRegionNode hrnChildA = edgeA.getDst();
2141         Integer        idChildA  = hrnChildA.getID();
2142
2143         // at this point we know an edge in graph A exists
2144         // tdA -> idChildA, does this exist in B?
2145         assert td2vn.containsKey( tdA );
2146         VariableNode vnB         = td2vn.get( tdA );
2147         RefEdge      edgeToMerge = null;
2148
2149         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
2150         while( heapRegionsItrB.hasNext() &&
2151                edgeToMerge == null          ) {
2152
2153           RefEdge        edgeB     = heapRegionsItrB.next();
2154           HeapRegionNode hrnChildB = edgeB.getDst();
2155           Integer        idChildB  = hrnChildB.getID();
2156
2157           // don't use the RefEdge.equals() here because
2158           // we're talking about existence between graphs
2159           if( idChildB.equals( idChildA ) &&
2160               edgeB.typeAndFieldEquals( edgeA ) ) {
2161
2162             edgeToMerge = edgeB;
2163           }
2164         }
2165
2166         // if the edge from A was not found in B,
2167         // add it to B.
2168         if( edgeToMerge == null ) {
2169           assert id2hrn.containsKey( idChildA );
2170           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2171           edgeToMerge = edgeA.copy();
2172           edgeToMerge.setSrc( vnB );
2173           edgeToMerge.setDst( hrnChildB );
2174           addRefEdge( vnB, hrnChildB, edgeToMerge );
2175         }
2176         // otherwise, the edge already existed in both graphs
2177         // so merge their reachability sets
2178         else {
2179           // just replace this beta set with the union
2180           edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
2181                                                 edgeA.getBeta()
2182                                                 )
2183                                );
2184           // TODO: what?
2185           /*
2186           if( !edgeA.isClean() ) {
2187             edgeToMerge.setIsClean( false );
2188           }
2189           */
2190         }
2191       }
2192     }
2193   }
2194
2195   protected void mergeAllocSites( ReachGraph rg ) {
2196     allocSites.addAll( rg.allocSites );
2197   }
2198
2199
2200   // it is necessary in the equals() member functions
2201   // to "check both ways" when comparing the data
2202   // structures of two graphs.  For instance, if all
2203   // edges between heap region nodes in graph A are
2204   // present and equal in graph B it is not sufficient
2205   // to say the graphs are equal.  Consider that there
2206   // may be edges in graph B that are not in graph A.
2207   // the only way to know that all edges in both graphs
2208   // are equally present is to iterate over both data
2209   // structures and compare against the other graph.
2210   public boolean equals( ReachGraph rg ) {
2211
2212     if( rg == null ) {
2213       return false;
2214     }
2215
2216     if( !areHeapRegionNodesEqual( rg ) ) {
2217       return false;
2218     }
2219
2220     if( !areVariableNodesEqual( rg ) ) {
2221       return false;
2222     }
2223
2224     if( !areRefEdgesEqual( rg ) ) {
2225       return false;
2226     }
2227
2228     // if everything is equal up to this point,
2229     // assert that allocSites is also equal--
2230     // this data is redundant but kept for efficiency
2231     assert allocSites.equals( rg.allocSites );
2232
2233     return true;
2234   }
2235
2236
2237   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
2238
2239     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
2240       return false;
2241     }
2242
2243     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
2244       return false;
2245     }
2246
2247     return true;
2248   }
2249
2250   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
2251                                                         ReachGraph rgB ) {
2252     Set      sA = rgA.id2hrn.entrySet();
2253     Iterator iA = sA.iterator();
2254     while( iA.hasNext() ) {
2255       Map.Entry      meA  = (Map.Entry)      iA.next();
2256       Integer        idA  = (Integer)        meA.getKey();
2257       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2258
2259       if( !rgB.id2hrn.containsKey( idA ) ) {
2260         return false;
2261       }
2262
2263       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2264       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
2265         return false;
2266       }
2267     }
2268
2269     return true;
2270   }
2271
2272
2273   protected boolean areVariableNodesEqual( ReachGraph rg ) {
2274
2275     if( !areallVNinAalsoinBandequal( this, rg ) ) {
2276       return false;
2277     }
2278
2279     if( !areallVNinAalsoinBandequal( rg, this ) ) {
2280       return false;
2281     }
2282
2283     return true;
2284   }
2285
2286   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2287                                                        ReachGraph rgB ) {
2288     Set      sA = rgA.td2vn.entrySet();
2289     Iterator iA = sA.iterator();
2290     while( iA.hasNext() ) {
2291       Map.Entry      meA = (Map.Entry)      iA.next();
2292       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2293
2294       if( !rgB.td2vn.containsKey( tdA ) ) {
2295         return false;
2296       }
2297     }
2298
2299     return true;
2300   }
2301
2302
2303   protected boolean areRefEdgesEqual( ReachGraph rg ) {
2304     if( !areallREinAandBequal( this, rg ) ) {
2305       return false;
2306     }
2307
2308     return true;
2309   }
2310
2311   static protected boolean areallREinAandBequal( ReachGraph rgA,
2312                                                  ReachGraph rgB ) {
2313
2314     // check all the heap region->heap region edges
2315     Set      sA = rgA.id2hrn.entrySet();
2316     Iterator iA = sA.iterator();
2317     while( iA.hasNext() ) {
2318       Map.Entry      meA  = (Map.Entry)      iA.next();
2319       Integer        idA  = (Integer)        meA.getKey();
2320       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2321
2322       // we should have already checked that the same
2323       // heap regions exist in both graphs
2324       assert rgB.id2hrn.containsKey( idA );
2325
2326       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
2327         return false;
2328       }
2329
2330       // then check every edge in B for presence in A, starting
2331       // from the same parent HeapRegionNode
2332       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2333
2334       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
2335         return false;
2336       }
2337     }
2338
2339     // then check all the variable->heap region edges
2340     sA = rgA.td2vn.entrySet();
2341     iA = sA.iterator();
2342     while( iA.hasNext() ) {
2343       Map.Entry      meA = (Map.Entry)      iA.next();
2344       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2345       VariableNode   vnA = (VariableNode)   meA.getValue();
2346
2347       // we should have already checked that the same
2348       // label nodes exist in both graphs
2349       assert rgB.td2vn.containsKey( tdA );
2350
2351       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
2352         return false;
2353       }
2354
2355       // then check every edge in B for presence in A, starting
2356       // from the same parent VariableNode
2357       VariableNode vnB = rgB.td2vn.get( tdA );
2358
2359       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
2360         return false;
2361       }
2362     }
2363
2364     return true;
2365   }
2366
2367
2368   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
2369                                                   RefSrcNode rnA,
2370                                                   ReachGraph rgB ) {
2371
2372     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
2373     while( itrA.hasNext() ) {
2374       RefEdge        edgeA     = itrA.next();
2375       HeapRegionNode hrnChildA = edgeA.getDst();
2376       Integer        idChildA  = hrnChildA.getID();
2377
2378       assert rgB.id2hrn.containsKey( idChildA );
2379
2380       // at this point we know an edge in graph A exists
2381       // rnA -> idChildA, does this exact edge exist in B?
2382       boolean edgeFound = false;
2383
2384       RefSrcNode rnB = null;
2385       if( rnA instanceof HeapRegionNode ) {
2386         HeapRegionNode hrnA = (HeapRegionNode) rnA;
2387         rnB = rgB.id2hrn.get( hrnA.getID() );
2388       } else {
2389         VariableNode vnA = (VariableNode) rnA;
2390         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
2391       }
2392
2393       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
2394       while( itrB.hasNext() ) {
2395         RefEdge        edgeB     = itrB.next();
2396         HeapRegionNode hrnChildB = edgeB.getDst();
2397         Integer        idChildB  = hrnChildB.getID();
2398
2399         if( idChildA.equals( idChildB ) &&
2400             edgeA.typeAndFieldEquals( edgeB ) ) {
2401
2402           // there is an edge in the right place with the right field,
2403           // but do they have the same attributes?
2404           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
2405               edgeA.equalsPreds( edgeB )
2406               ) {
2407             edgeFound = true;
2408           }
2409         }
2410       }
2411
2412       if( !edgeFound ) {
2413         return false;
2414       }
2415     }
2416
2417     return true;
2418   }
2419
2420
2421
2422   // this analysis no longer has the "match anything"
2423   // type which was represented by null
2424   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2425                                              TypeDescriptor td2 ) {
2426     assert td1 != null;
2427     assert td2 != null;
2428
2429     if( td1.isNull() ) {
2430       return td2;
2431     }
2432     if( td2.isNull() ) {
2433       return td1;
2434     }
2435     return typeUtil.mostSpecific( td1, td2 );
2436   }
2437
2438   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2439                                              TypeDescriptor td2,
2440                                              TypeDescriptor td3 ) {
2441
2442     return mostSpecificType( td1,
2443                              mostSpecificType( td2, td3 )
2444                              );
2445   }
2446
2447   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2448                                              TypeDescriptor td2,
2449                                              TypeDescriptor td3,
2450                                              TypeDescriptor td4 ) {
2451
2452     return mostSpecificType( mostSpecificType( td1, td2 ),
2453                              mostSpecificType( td3, td4 )
2454                              );
2455   }
2456
2457   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
2458                                     TypeDescriptor possibleChild ) {
2459     assert possibleSuper != null;
2460     assert possibleChild != null;
2461
2462     if( possibleSuper.isNull() ||
2463         possibleChild.isNull() ) {
2464       return true;
2465     }
2466
2467     return typeUtil.isSuperorType( possibleSuper, possibleChild );
2468   }
2469
2470
2471   protected boolean hasMatchingField( HeapRegionNode src,
2472                                       RefEdge        edge ) {
2473
2474     TypeDescriptor tdSrc = src.getType();
2475     assert tdSrc != null;
2476
2477     if( tdSrc.isArray() ) {
2478       TypeDescriptor td = edge.getType();
2479       assert td != null;
2480
2481       TypeDescriptor tdSrcDeref = tdSrc.dereference();
2482       assert tdSrcDeref != null;
2483
2484       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2485         return false;
2486       }
2487
2488       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
2489     }
2490
2491     // if it's not a class, it doesn't have any fields to match
2492     if( !tdSrc.isClass() ) {
2493       return false;
2494     }
2495
2496     ClassDescriptor cd = tdSrc.getClassDesc();
2497     while( cd != null ) {
2498       Iterator fieldItr = cd.getFields();
2499
2500       while( fieldItr.hasNext() ) {
2501         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
2502
2503         if( fd.getType().equals( edge.getType() ) &&
2504             fd.getSymbol().equals( edge.getField() ) ) {
2505           return true;
2506         }
2507       }
2508
2509       cd = cd.getSuperDesc();
2510     }
2511
2512     // otherwise it is a class with fields
2513     // but we didn't find a match
2514     return false;
2515   }
2516
2517   protected boolean hasMatchingType( RefEdge        edge,
2518                                      HeapRegionNode dst  ) {
2519
2520     // if the region has no type, matches everything
2521     TypeDescriptor tdDst = dst.getType();
2522     assert tdDst != null;
2523
2524     // if the type is not a class or an array, don't
2525     // match because primitives are copied, no aliases
2526     ClassDescriptor cdDst = tdDst.getClassDesc();
2527     if( cdDst == null && !tdDst.isArray() ) {
2528       return false;
2529     }
2530
2531     // if the edge type is null, it matches everything
2532     TypeDescriptor tdEdge = edge.getType();
2533     assert tdEdge != null;
2534
2535     return typeUtil.isSuperorType( tdEdge, tdDst );
2536   }
2537
2538
2539
2540   public void writeGraph( String  graphName,
2541                           boolean writeLabels,
2542                           boolean labelSelect,
2543                           boolean pruneGarbage,
2544                           boolean writeReferencers,
2545                           boolean hideSubsetReachability,
2546                           boolean hideEdgeTaints
2547                           ) throws java.io.IOException {
2548     writeGraph( graphName,
2549                 writeLabels,
2550                 labelSelect,
2551                 pruneGarbage,
2552                 writeReferencers,
2553                 hideSubsetReachability,
2554                 hideEdgeTaints,
2555                 null,
2556                 null );
2557   }
2558
2559   public void writeGraph( String              graphName,
2560                           boolean             writeLabels,
2561                           boolean             labelSelect,
2562                           boolean             pruneGarbage,
2563                           boolean             writeReferencers,
2564                           boolean             hideSubsetReachability,
2565                           boolean             hideEdgeTaints,
2566                           Set<HeapRegionNode> callerNodesCopiedToCallee,
2567                           Set<RefEdge>        callerEdgesCopiedToCallee
2568                           ) throws java.io.IOException {
2569
2570     // remove all non-word characters from the graph name so
2571     // the filename and identifier in dot don't cause errors
2572     graphName = graphName.replaceAll( "[\\W]", "" );
2573
2574     BufferedWriter bw =
2575       new BufferedWriter( new FileWriter( graphName+".dot" ) );
2576
2577     bw.write( "digraph "+graphName+" {\n" );
2578
2579
2580     // this is an optional step to form the callee-reachable
2581     // "cut-out" into a DOT cluster for visualization
2582     if( callerNodesCopiedToCallee != null ) {
2583
2584       bw.write( "  subgraph cluster0 {\n" );
2585       bw.write( "    color=blue;\n" );
2586
2587       Iterator i = id2hrn.entrySet().iterator();
2588       while( i.hasNext() ) {
2589         Map.Entry      me  = (Map.Entry)      i.next();
2590         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2591
2592         if( callerNodesCopiedToCallee.contains( hrn ) ) {
2593           bw.write( "    "+hrn.toString()+
2594                     hrn.toStringDOT( hideSubsetReachability )+
2595                     ";\n" );
2596
2597         }
2598       }
2599
2600       bw.write( "  }\n" );
2601     }
2602
2603
2604     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2605
2606     // then visit every heap region node
2607     Iterator i = id2hrn.entrySet().iterator();
2608     while( i.hasNext() ) {
2609       Map.Entry      me  = (Map.Entry)      i.next();
2610       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2611
2612       // only visit nodes worth writing out--for instance
2613       // not every node at an allocation is referenced
2614       // (think of it as garbage-collected), etc.
2615       if( !pruneGarbage                              ||
2616           (hrn.isFlagged() && hrn.getID() > 0)       ||
2617           hrn.getDescription().startsWith( "param" ) ||
2618           hrn.isOutOfContext()
2619           ) {
2620
2621         if( !visited.contains( hrn ) ) {
2622           traverseHeapRegionNodes( hrn,
2623                                    bw,
2624                                    null,
2625                                    visited,
2626                                    writeReferencers,
2627                                    hideSubsetReachability,
2628                                    hideEdgeTaints,
2629                                    callerNodesCopiedToCallee,
2630                                    callerEdgesCopiedToCallee );
2631         }
2632       }
2633     }
2634
2635     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
2636
2637
2638     // then visit every label node, useful for debugging
2639     if( writeLabels ) {
2640       i = td2vn.entrySet().iterator();
2641       while( i.hasNext() ) {
2642         Map.Entry    me = (Map.Entry)    i.next();
2643         VariableNode vn = (VariableNode) me.getValue();
2644
2645         if( labelSelect ) {
2646           String labelStr = vn.getTempDescriptorString();
2647           if( labelStr.startsWith("___temp") ||
2648               labelStr.startsWith("___dst") ||
2649               labelStr.startsWith("___srctmp") ||
2650               labelStr.startsWith("___neverused")
2651               ) {
2652             continue;
2653           }
2654         }
2655
2656         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
2657         while( heapRegionsItr.hasNext() ) {
2658           RefEdge        edge = heapRegionsItr.next();
2659           HeapRegionNode hrn  = edge.getDst();
2660
2661           if( pruneGarbage && !visited.contains( hrn ) ) {
2662             traverseHeapRegionNodes( hrn,
2663                                      bw,
2664                                      null,
2665                                      visited,
2666                                      writeReferencers,
2667                                      hideSubsetReachability,
2668                                      hideEdgeTaints,
2669                                      callerNodesCopiedToCallee,
2670                                      callerEdgesCopiedToCallee );
2671           }
2672
2673           bw.write( "  "+vn.toString()+
2674                     " -> "+hrn.toString()+
2675                     edge.toStringDOT( hideSubsetReachability, "" )+
2676                     ";\n" );
2677         }
2678       }
2679     }
2680
2681     bw.write( "}\n" );
2682     bw.close();
2683   }
2684
2685   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
2686                                           BufferedWriter      bw,
2687                                           TempDescriptor      td,
2688                                           Set<HeapRegionNode> visited,
2689                                           boolean             writeReferencers,
2690                                           boolean             hideSubsetReachability,
2691                                           boolean             hideEdgeTaints,
2692                                           Set<HeapRegionNode> callerNodesCopiedToCallee,
2693                                           Set<RefEdge>        callerEdgesCopiedToCallee
2694                                           ) throws java.io.IOException {
2695
2696     if( visited.contains( hrn ) ) {
2697       return;
2698     }
2699     visited.add( hrn );
2700
2701     // if we're drawing the callee-view subgraph, only
2702     // write out the node info if it hasn't already been
2703     // written
2704     if( callerNodesCopiedToCallee == null ||
2705         !callerNodesCopiedToCallee.contains( hrn )
2706         ) {
2707       bw.write( "  "+hrn.toString()+
2708                 hrn.toStringDOT( hideSubsetReachability )+
2709                 ";\n" );
2710     }
2711
2712     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
2713     while( childRegionsItr.hasNext() ) {
2714       RefEdge        edge     = childRegionsItr.next();
2715       HeapRegionNode hrnChild = edge.getDst();
2716
2717       if( callerEdgesCopiedToCallee != null &&
2718           callerEdgesCopiedToCallee.contains( hrn )
2719           ) {
2720         bw.write( "  "+hrn.toString()+
2721                   " -> "+hrnChild.toString()+
2722                   edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
2723                   ";\n");
2724       } else {
2725         bw.write( "  "+hrn.toString()+
2726                   " -> "+hrnChild.toString()+
2727                   edge.toStringDOT( hideSubsetReachability, "" )+
2728                   ";\n");
2729       }
2730
2731       traverseHeapRegionNodes( hrnChild,
2732                                bw,
2733                                td,
2734                                visited,
2735                                writeReferencers,
2736                                hideSubsetReachability,
2737                                hideEdgeTaints,
2738                                callerNodesCopiedToCallee,
2739                                callerEdgesCopiedToCallee );
2740     }
2741   }
2742
2743 }