Robust/src/Analysis/Disjoint/ReachGraph.java

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