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