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