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