Robust/src/Analysis/Disjoint/ReachGraph.java

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