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