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