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   = false;
  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   // this suite of methods can be used to assert a
  67   // very important property of ReachGraph objects:
  68   // some element, HeapRegionNode, RefEdge etc.
  69   // should be referenced by at most ONE ReachGraph!!
  70   // If a heap region or edge or variable should be
  71   // in another graph, make a new object with
  72   // equivalent properties for a new graph
  73   public boolean belongsToThis( RefSrcNode rsn ) {
  74     if( rsn instanceof VariableNode ) {
  75       VariableNode vn = (VariableNode) rsn;
  76       return this.td2vn.get( vn.getTempDescriptor() ) == vn;
  77     }
  78     HeapRegionNode hrn = (HeapRegionNode) rsn;
  79     return this.id2hrn.get( hrn.getID() ) == hrn;
  80   }
  81
  82
  83
  84   // the reason for this method is to have the option
  85   // of creating new heap regions with specific IDs, or
  86   // duplicating heap regions with specific IDs (especially
  87   // in the merge() operation) or to create new heap
  88   // regions with a new unique ID
  89   protected HeapRegionNode
  90     createNewHeapRegionNode( Integer        id,
  91                              boolean        isSingleObject,
  92                              boolean        isNewSummary,
  93                              boolean        isFlagged,
  94                              boolean        isOutOfContext,
  95                              TypeDescriptor type,
  96                              AllocSite      allocSite,
  97                              ReachSet       inherent,
  98                              ReachSet       alpha,
  99                              ExistPredSet   preds,
 100                              String         description
 101                              ) {
 102
 103     boolean markForAnalysis = isFlagged;
 104
 105     TypeDescriptor typeToUse = null;
 106     if( allocSite != null ) {
 107       typeToUse = allocSite.getType();
 108       allocSites.add( allocSite );
 109     } else {
 110       typeToUse = type;
 111     }
 112
 113     if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
 114       markForAnalysis = true;
 115     }
 116
 117     if( id == null ) {
 118       id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
 119     }
 120
 121     if( inherent == null ) {
 122       if( markForAnalysis ) {
 123         inherent =
 124           ReachSet.factory(
 125                            ReachState.factory(
 126                                               ReachTuple.factory( id,
 127                                                                   !isSingleObject,
 128                                                                   ReachTuple.ARITY_ONE,
 129                                                                   false // out-of-context
 130                                                                   )
 131                                               )
 132                            );
 133       } else {
 134         inherent = rsetWithEmptyState;
 135       }
 136     }
 137
 138     if( alpha == null ) {
 139       alpha = inherent;
 140     }
 141
 142     assert preds != null;
 143
 144     HeapRegionNode hrn = new HeapRegionNode( id,
 145                                              isSingleObject,
 146                                              markForAnalysis,
 147                                              isNewSummary,
 148                                              isOutOfContext,
 149                                              typeToUse,
 150                                              allocSite,
 151                                              inherent,
 152                                              alpha,
 153                                              preds,
 154                                              description );
 155     id2hrn.put( id, hrn );
 156     return hrn;
 157   }
 158
 159
 160
 161   ////////////////////////////////////////////////
 162   //
 163   //  Low-level referencee and referencer methods
 164   //
 165   //  These methods provide the lowest level for
 166   //  creating references between reachability nodes
 167   //  and handling the details of maintaining both
 168   //  list of referencers and referencees.
 169   //
 170   ////////////////////////////////////////////////
 171   protected void addRefEdge( RefSrcNode     referencer,
 172                              HeapRegionNode referencee,
 173                              RefEdge        edge ) {
 174     assert referencer != null;
 175     assert referencee != null;
 176     assert edge       != null;
 177     assert edge.getSrc() == referencer;
 178     assert edge.getDst() == referencee;
 179     assert belongsToThis( referencer );
 180     assert belongsToThis( referencee );
 181
 182     // edges are getting added twice to graphs now, the
 183     // kind that should have abstract facts merged--use
 184     // this check to prevent that
 185     assert referencer.getReferenceTo( referencee,
 186                                       edge.getType(),
 187                                       edge.getField()
 188                                       ) == null;
 189
 190     referencer.addReferencee( edge );
 191     referencee.addReferencer( edge );
 192   }
 193
 194   protected void removeRefEdge( RefEdge e ) {
 195     removeRefEdge( e.getSrc(),
 196                    e.getDst(),
 197                    e.getType(),
 198                    e.getField() );
 199   }
 200
 201   protected void removeRefEdge( RefSrcNode     referencer,
 202                                 HeapRegionNode referencee,
 203                                 TypeDescriptor type,
 204                                 String         field ) {
 205     assert referencer != null;
 206     assert referencee != null;
 207
 208     RefEdge edge = referencer.getReferenceTo( referencee,
 209                                               type,
 210                                               field );
 211     assert edge != null;
 212     assert edge == referencee.getReferenceFrom( referencer,
 213                                                 type,
 214                                                 field );
 215
 216     referencer.removeReferencee( edge );
 217     referencee.removeReferencer( edge );
 218   }
 219
 220   protected void clearRefEdgesFrom( RefSrcNode     referencer,
 221                                     TypeDescriptor type,
 222                                     String         field,
 223                                     boolean        removeAll ) {
 224     assert referencer != null;
 225
 226     // get a copy of the set to iterate over, otherwise
 227     // we will be trying to take apart the set as we
 228     // are iterating over it, which won't work
 229     Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
 230     while( i.hasNext() ) {
 231       RefEdge edge = i.next();
 232
 233       if( removeAll                                          ||
 234           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 235         ){
 236
 237         HeapRegionNode referencee = edge.getDst();
 238
 239         removeRefEdge( referencer,
 240                        referencee,
 241                        edge.getType(),
 242                        edge.getField() );
 243       }
 244     }
 245   }
 246
 247   protected void clearRefEdgesTo( HeapRegionNode referencee,
 248                                   TypeDescriptor type,
 249                                   String         field,
 250                                   boolean        removeAll ) {
 251     assert referencee != null;
 252
 253     // get a copy of the set to iterate over, otherwise
 254     // we will be trying to take apart the set as we
 255     // are iterating over it, which won't work
 256     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 257     while( i.hasNext() ) {
 258       RefEdge edge = i.next();
 259
 260       if( removeAll                                          ||
 261           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 262         ){
 263
 264         RefSrcNode referencer = edge.getSrc();
 265
 266         removeRefEdge( referencer,
 267                        referencee,
 268                        edge.getType(),
 269                        edge.getField() );
 270       }
 271     }
 272   }
 273
 274   protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
 275     assert referencee != null;
 276
 277     // get a copy of the set to iterate over, otherwise
 278     // we will be trying to take apart the set as we
 279     // are iterating over it, which won't work
 280     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 281     while( i.hasNext() ) {
 282       RefEdge edge = i.next();
 283       RefSrcNode referencer = edge.getSrc();
 284       if( !(referencer instanceof VariableNode) ) {
 285         removeRefEdge( referencer,
 286                        referencee,
 287                        edge.getType(),
 288                        edge.getField() );
 289       }
 290     }
 291   }
 292
 293   // this is a common operation in many transfer functions: we want
 294   // to add an edge, but if there is already such an edge we should
 295   // merge the properties of the existing and the new edges
 296   protected void addEdgeOrMergeWithExisting( RefEdge edgeNew ) {
 297
 298     RefSrcNode src = edgeNew.getSrc();
 299     assert belongsToThis( src );
 300
 301     HeapRegionNode dst = edgeNew.getDst();
 302     assert belongsToThis( dst );
 303
 304     // look to see if an edge with same field exists
 305     // and merge with it, otherwise just add the edge
 306     RefEdge edgeExisting = src.getReferenceTo( dst,
 307                                                edgeNew.getType(),
 308                                                edgeNew.getField()
 309                                                );
 310
 311     if( edgeExisting != null ) {
 312       edgeExisting.setBeta(
 313                            Canonical.unionORpreds( edgeExisting.getBeta(),
 314                                                    edgeNew.getBeta()
 315                                                    )
 316                            );
 317       edgeExisting.setPreds(
 318                             Canonical.join( edgeExisting.getPreds(),
 319                                             edgeNew.getPreds()
 320                                             )
 321                             );
 322
 323     } else {
 324       addRefEdge( src, dst, edgeNew );
 325     }
 326   }
 327
 328
 329
 330   ////////////////////////////////////////////////////
 331   //
 332   //  Assignment Operation Methods
 333   //
 334   //  These methods are high-level operations for
 335   //  modeling program assignment statements using
 336   //  the low-level reference create/remove methods
 337   //  above.
 338   //
 339   ////////////////////////////////////////////////////
 340
 341   public void assignTempXEqualToTempY( TempDescriptor x,
 342                                        TempDescriptor y ) {
 343     assignTempXEqualToCastedTempY( x, y, null );
 344   }
 345
 346   public void assignTempXEqualToCastedTempY( TempDescriptor x,
 347                                              TempDescriptor y,
 348                                              TypeDescriptor tdCast ) {
 349
 350     VariableNode lnX = getVariableNodeFromTemp( x );
 351     VariableNode lnY = getVariableNodeFromTemp( y );
 352
 353     clearRefEdgesFrom( lnX, null, null, true );
 354
 355     // note it is possible that the types of temps in the
 356     // flat node to analyze will reveal that some typed
 357     // edges in the reachability graph are impossible
 358     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 359
 360     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 361     while( itrYhrn.hasNext() ) {
 362       RefEdge        edgeY      = itrYhrn.next();
 363       HeapRegionNode referencee = edgeY.getDst();
 364       RefEdge        edgeNew    = edgeY.copy();
 365
 366       if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
 367         impossibleEdges.add( edgeY );
 368         continue;
 369       }
 370
 371       edgeNew.setSrc( lnX );
 372
 373       if( tdCast == null ) {
 374         edgeNew.setType( mostSpecificType( y.getType(),
 375                                            edgeY.getType(),
 376                                            referencee.getType()
 377                                            )
 378                          );
 379       } else {
 380         edgeNew.setType( mostSpecificType( y.getType(),
 381                                            edgeY.getType(),
 382                                            referencee.getType(),
 383                                            tdCast
 384                                            )
 385                          );
 386       }
 387
 388       edgeNew.setField( null );
 389
 390       addRefEdge( lnX, referencee, edgeNew );
 391     }
 392
 393     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 394     while( itrImp.hasNext() ) {
 395       RefEdge edgeImp = itrImp.next();
 396       removeRefEdge( edgeImp );
 397     }
 398   }
 399
 400
 401   public void assignTempXEqualToTempYFieldF( TempDescriptor  x,
 402                                              TempDescriptor  y,
 403                                              FieldDescriptor f ) {
 404     VariableNode lnX = getVariableNodeFromTemp( x );
 405     VariableNode lnY = getVariableNodeFromTemp( y );
 406
 407     clearRefEdgesFrom( lnX, null, null, true );
 408
 409     // note it is possible that the types of temps in the
 410     // flat node to analyze will reveal that some typed
 411     // edges in the reachability graph are impossible
 412     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 413
 414     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 415     while( itrYhrn.hasNext() ) {
 416       RefEdge        edgeY = itrYhrn.next();
 417       HeapRegionNode hrnY  = edgeY.getDst();
 418       ReachSet       betaY = edgeY.getBeta();
 419
 420       Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 421       while( itrHrnFhrn.hasNext() ) {
 422         RefEdge        edgeHrn = itrHrnFhrn.next();
 423         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 424         ReachSet       betaHrn = edgeHrn.getBeta();
 425
 426         // prune edges that are not a matching field
 427         if( edgeHrn.getType() != null &&
 428             !edgeHrn.getField().equals( f.getSymbol() )
 429             ) {
 430           continue;
 431         }
 432
 433         // check for impossible edges
 434         if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
 435           impossibleEdges.add( edgeHrn );
 436           continue;
 437         }
 438
 439         TypeDescriptor tdNewEdge =
 440           mostSpecificType( edgeHrn.getType(),
 441                             hrnHrn.getType()
 442                             );
 443
 444         RefEdge edgeNew = new RefEdge( lnX,
 445                                        hrnHrn,
 446                                        tdNewEdge,
 447                                        null,
 448                                        Canonical.intersection( betaY, betaHrn ),
 449                                        predsTrue
 450                                        );
 451
 452         addEdgeOrMergeWithExisting( edgeNew );
 453       }
 454     }
 455
 456     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 457     while( itrImp.hasNext() ) {
 458       RefEdge edgeImp = itrImp.next();
 459       removeRefEdge( edgeImp );
 460     }
 461
 462     // anytime you might remove edges between heap regions
 463     // you must global sweep to clean up broken reachability
 464     if( !impossibleEdges.isEmpty() ) {
 465       if( !DISABLE_GLOBAL_SWEEP ) {
 466         globalSweep();
 467       }
 468     }
 469   }
 470
 471
 472   public void assignTempXFieldFEqualToTempY( TempDescriptor  x,
 473                                              FieldDescriptor f,
 474                                              TempDescriptor  y ) {
 475
 476     VariableNode lnX = getVariableNodeFromTemp( x );
 477     VariableNode lnY = getVariableNodeFromTemp( y );
 478
 479     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 480     HashSet<RefEdge>        edgesWithNewBeta  = new HashSet<RefEdge>();
 481
 482     // note it is possible that the types of temps in the
 483     // flat node to analyze will reveal that some typed
 484     // edges in the reachability graph are impossible
 485     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 486
 487     // first look for possible strong updates and remove those edges
 488     boolean strongUpdate = false;
 489
 490     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 491     while( itrXhrn.hasNext() ) {
 492       RefEdge        edgeX = itrXhrn.next();
 493       HeapRegionNode hrnX  = edgeX.getDst();
 494
 495       // we can do a strong update here if one of two cases holds
 496       if( f != null &&
 497           f != DisjointAnalysis.getArrayField( f.getType() ) &&
 498           (   (hrnX.getNumReferencers()                         == 1) || // case 1
 499               (hrnX.isSingleObject() && lnX.getNumReferencees() == 1)    // case 2
 500               )
 501           ) {
 502         if( !DISABLE_STRONG_UPDATES ) {
 503           strongUpdate = true;
 504           clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
 505         }
 506       }
 507     }
 508
 509     // then do all token propagation
 510     itrXhrn = lnX.iteratorToReferencees();
 511     while( itrXhrn.hasNext() ) {
 512       RefEdge        edgeX = itrXhrn.next();
 513       HeapRegionNode hrnX  = edgeX.getDst();
 514       ReachSet       betaX = edgeX.getBeta();
 515       ReachSet       R     = Canonical.intersection( hrnX.getAlpha(),
 516                                                      edgeX.getBeta()
 517                                                      );
 518
 519       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 520       while( itrYhrn.hasNext() ) {
 521         RefEdge        edgeY = itrYhrn.next();
 522         HeapRegionNode hrnY  = edgeY.getDst();
 523         ReachSet       O     = edgeY.getBeta();
 524
 525         // check for impossible edges
 526         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 527           impossibleEdges.add( edgeY );
 528           continue;
 529         }
 530
 531         // propagate tokens over nodes starting from hrnSrc, and it will
 532         // take care of propagating back up edges from any touched nodes
 533         ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
 534         propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
 535
 536         // then propagate back just up the edges from hrn
 537         ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
 538         HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
 539
 540         Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
 541           new Hashtable<RefEdge, ChangeSet>();
 542
 543         Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
 544         while( referItr.hasNext() ) {
 545           RefEdge edgeUpstream = referItr.next();
 546           todoEdges.add( edgeUpstream );
 547           edgePlannedChanges.put( edgeUpstream, Cx );
 548         }
 549
 550         propagateTokensOverEdges( todoEdges,
 551                                   edgePlannedChanges,
 552                                   edgesWithNewBeta );
 553       }
 554     }
 555
 556
 557     // apply the updates to reachability
 558     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 559     while( nodeItr.hasNext() ) {
 560       nodeItr.next().applyAlphaNew();
 561     }
 562
 563     Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
 564     while( edgeItr.hasNext() ) {
 565       edgeItr.next().applyBetaNew();
 566     }
 567
 568
 569     // then go back through and add the new edges
 570     itrXhrn = lnX.iteratorToReferencees();
 571     while( itrXhrn.hasNext() ) {
 572       RefEdge        edgeX = itrXhrn.next();
 573       HeapRegionNode hrnX  = edgeX.getDst();
 574
 575       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 576       while( itrYhrn.hasNext() ) {
 577         RefEdge        edgeY = itrYhrn.next();
 578         HeapRegionNode hrnY  = edgeY.getDst();
 579
 580         // skip impossible edges here, we already marked them
 581         // when computing reachability propagations above
 582         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 583           continue;
 584         }
 585
 586         // prepare the new reference edge hrnX.f -> hrnY
 587         TypeDescriptor tdNewEdge =
 588           mostSpecificType( y.getType(),
 589                             edgeY.getType(),
 590                             hrnY.getType()
 591                             );
 592
 593         RefEdge edgeNew = new RefEdge( hrnX,
 594                                        hrnY,
 595                                        tdNewEdge,
 596                                        f.getSymbol(),
 597                                        Canonical.pruneBy( edgeY.getBeta(),
 598                                                           hrnX.getAlpha()
 599                                                           ),
 600                                        predsTrue
 601                                        );
 602
 603         addEdgeOrMergeWithExisting( edgeNew );
 604       }
 605     }
 606
 607     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 608     while( itrImp.hasNext() ) {
 609       RefEdge edgeImp = itrImp.next();
 610       removeRefEdge( edgeImp );
 611     }
 612
 613     // if there was a strong update, make sure to improve
 614     // reachability with a global sweep
 615     if( strongUpdate || !impossibleEdges.isEmpty() ) {
 616       if( !DISABLE_GLOBAL_SWEEP ) {
 617         globalSweep();
 618       }
 619     }
 620   }
 621
 622
 623   public void assignReturnEqualToTemp( TempDescriptor x ) {
 624
 625     VariableNode lnR = getVariableNodeFromTemp( tdReturn );
 626     VariableNode lnX = getVariableNodeFromTemp( x );
 627
 628     clearRefEdgesFrom( lnR, null, null, true );
 629
 630     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 631     while( itrXhrn.hasNext() ) {
 632       RefEdge        edgeX      = itrXhrn.next();
 633       HeapRegionNode referencee = edgeX.getDst();
 634       RefEdge        edgeNew    = edgeX.copy();
 635       edgeNew.setSrc( lnR );
 636
 637       addRefEdge( lnR, referencee, edgeNew );
 638     }
 639   }
 640
 641
 642   public void assignTempEqualToNewAlloc( TempDescriptor x,
 643                                          AllocSite      as ) {
 644     assert x  != null;
 645     assert as != null;
 646
 647     age( as );
 648
 649     // after the age operation the newest (or zero-ith oldest)
 650     // node associated with the allocation site should have
 651     // no references to it as if it were a newly allocated
 652     // heap region
 653     Integer        idNewest   = as.getIthOldest( 0 );
 654     HeapRegionNode hrnNewest  = id2hrn.get( idNewest );
 655     assert         hrnNewest != null;
 656
 657     VariableNode lnX = getVariableNodeFromTemp( x );
 658     clearRefEdgesFrom( lnX, null, null, true );
 659
 660     // make a new reference to allocated node
 661     TypeDescriptor type = as.getType();
 662
 663     RefEdge edgeNew =
 664       new RefEdge( lnX,                  // source
 665                    hrnNewest,            // dest
 666                    type,                 // type
 667                    null,                 // field name
 668                    hrnNewest.getAlpha(), // beta
 669                    predsTrue             // predicates
 670                    );
 671
 672     addRefEdge( lnX, hrnNewest, edgeNew );
 673   }
 674
 675
 676   // use the allocation site (unique to entire analysis) to
 677   // locate the heap region nodes in this reachability graph
 678   // that should be aged.  The process models the allocation
 679   // of new objects and collects all the oldest allocations
 680   // in a summary node to allow for a finite analysis
 681   //
 682   // There is an additional property of this method.  After
 683   // running it on a particular reachability graph (many graphs
 684   // may have heap regions related to the same allocation site)
 685   // the heap region node objects in this reachability graph will be
 686   // allocated.  Therefore, after aging a graph for an allocation
 687   // site, attempts to retrieve the heap region nodes using the
 688   // integer id's contained in the allocation site should always
 689   // return non-null heap regions.
 690   public void age( AllocSite as ) {
 691
 692     // keep track of allocation sites that are represented
 693     // in this graph for efficiency with other operations
 694     allocSites.add( as );
 695
 696     // if there is a k-th oldest node, it merges into
 697     // the summary node
 698     Integer idK = as.getOldest();
 699     if( id2hrn.containsKey( idK ) ) {
 700       HeapRegionNode hrnK = id2hrn.get( idK );
 701
 702       // retrieve the summary node, or make it
 703       // from scratch
 704       HeapRegionNode hrnSummary = getSummaryNode( as, false );
 705
 706       mergeIntoSummary( hrnK, hrnSummary );
 707     }
 708
 709     // move down the line of heap region nodes
 710     // clobbering the ith and transferring all references
 711     // to and from i-1 to node i.
 712     for( int i = allocationDepth - 1; i > 0; --i ) {
 713
 714       // only do the transfer if the i-1 node exists
 715       Integer idImin1th = as.getIthOldest( i - 1 );
 716       if( id2hrn.containsKey( idImin1th ) ) {
 717         HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
 718         if( hrnImin1.isWiped() ) {
 719           // there is no info on this node, just skip
 720           continue;
 721         }
 722
 723         // either retrieve or make target of transfer
 724         HeapRegionNode hrnI = getIthNode( as, i, false );
 725
 726         transferOnto( hrnImin1, hrnI );
 727       }
 728
 729     }
 730
 731     // as stated above, the newest node should have had its
 732     // references moved over to the second oldest, so we wipe newest
 733     // in preparation for being the new object to assign something to
 734     HeapRegionNode hrn0 = getIthNode( as, 0, false );
 735     wipeOut( hrn0, true );
 736
 737     // now tokens in reachability sets need to "age" also
 738     Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
 739     while( itrAllVariableNodes.hasNext() ) {
 740       Map.Entry    me = (Map.Entry)    itrAllVariableNodes.next();
 741       VariableNode ln = (VariableNode) me.getValue();
 742
 743       Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
 744       while( itrEdges.hasNext() ) {
 745         ageTuplesFrom( as, itrEdges.next() );
 746       }
 747     }
 748
 749     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 750     while( itrAllHRNodes.hasNext() ) {
 751       Map.Entry      me       = (Map.Entry)      itrAllHRNodes.next();
 752       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 753
 754       ageTuplesFrom( as, hrnToAge );
 755
 756       Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
 757       while( itrEdges.hasNext() ) {
 758         ageTuplesFrom( as, itrEdges.next() );
 759       }
 760     }
 761
 762
 763     // after tokens have been aged, reset newest node's reachability
 764     // and a brand new node has a "true" predicate
 765     hrn0.setAlpha( hrn0.getInherent() );
 766     hrn0.setPreds( predsTrue );
 767   }
 768
 769
 770   // either retrieve or create the needed heap region node
 771   protected HeapRegionNode getSummaryNode( AllocSite as,
 772                                            boolean   shadow ) {
 773
 774     Integer idSummary;
 775     if( shadow ) {
 776       idSummary = as.getSummaryShadow();
 777     } else {
 778       idSummary = as.getSummary();
 779     }
 780
 781     HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 782
 783     if( hrnSummary == null ) {
 784
 785       boolean hasFlags = false;
 786       if( as.getType().isClass() ) {
 787         hasFlags = as.getType().getClassDesc().hasFlags();
 788       }
 789
 790       if( as.getFlag() ){
 791         hasFlags = as.getFlag();
 792       }
 793
 794       String strDesc = as.toStringForDOT()+"\\nsummary";
 795       if( shadow ) {
 796         strDesc += " shadow";
 797       }
 798
 799       hrnSummary =
 800         createNewHeapRegionNode( idSummary,    // id or null to generate a new one
 801                                  false,        // single object?
 802                                  true,         // summary?
 803                                  hasFlags,     // flagged?
 804                                  false,        // out-of-context?
 805                                  as.getType(), // type
 806                                  as,           // allocation site
 807                                  null,         // inherent reach
 808                                  null,         // current reach
 809                                  predsEmpty,   // predicates
 810                                  strDesc       // description
 811                                  );
 812     }
 813
 814     return hrnSummary;
 815   }
 816
 817   // either retrieve or create the needed heap region node
 818   protected HeapRegionNode getIthNode( AllocSite as,
 819                                        Integer   i,
 820                                        boolean   shadow ) {
 821
 822     Integer idIth;
 823     if( shadow ) {
 824       idIth = as.getIthOldestShadow( i );
 825     } else {
 826       idIth = as.getIthOldest( i );
 827     }
 828
 829     HeapRegionNode hrnIth = id2hrn.get( idIth );
 830
 831     if( hrnIth == null ) {
 832
 833       boolean hasFlags = false;
 834       if( as.getType().isClass() ) {
 835         hasFlags = as.getType().getClassDesc().hasFlags();
 836       }
 837
 838       if( as.getFlag() ){
 839         hasFlags = as.getFlag();
 840       }
 841
 842       String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
 843       if( shadow ) {
 844         strDesc += " shadow";
 845       }
 846
 847       hrnIth = createNewHeapRegionNode( idIth,        // id or null to generate a new one
 848                                         true,         // single object?
 849                                         false,        // summary?
 850                                         hasFlags,     // flagged?
 851                                         false,        // out-of-context?
 852                                         as.getType(), // type
 853                                         as,           // allocation site
 854                                         null,         // inherent reach
 855                                         null,         // current reach
 856                                         predsEmpty,   // predicates
 857                                         strDesc       // description
 858                                         );
 859     }
 860
 861     return hrnIth;
 862   }
 863
 864
 865   protected void mergeIntoSummary( HeapRegionNode hrn,
 866                                    HeapRegionNode hrnSummary ) {
 867     assert hrnSummary.isNewSummary();
 868
 869     // assert that these nodes belong to THIS graph
 870     assert belongsToThis( hrn );
 871     assert belongsToThis( hrnSummary );
 872
 873     assert hrn != hrnSummary;
 874
 875     // transfer references _from_ hrn over to hrnSummary
 876     Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
 877     while( itrReferencee.hasNext() ) {
 878       RefEdge edge       = itrReferencee.next();
 879       RefEdge edgeMerged = edge.copy();
 880       edgeMerged.setSrc( hrnSummary );
 881
 882       HeapRegionNode hrnReferencee = edge.getDst();
 883       RefEdge        edgeSummary   =
 884         hrnSummary.getReferenceTo( hrnReferencee,
 885                                    edge.getType(),
 886                                    edge.getField()
 887                                    );
 888
 889       if( edgeSummary == null ) {
 890         // the merge is trivial, nothing to be done
 891         addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
 892
 893       } else {
 894         // otherwise an edge from the referencer to hrnSummary exists already
 895         // and the edge referencer->hrn should be merged with it
 896         edgeSummary.setBeta(
 897                             Canonical.unionORpreds( edgeMerged.getBeta(),
 898                                              edgeSummary.getBeta()
 899                                              )
 900                              );
 901         edgeSummary.setPreds(
 902                              Canonical.join( edgeMerged.getPreds(),
 903                                              edgeSummary.getPreds()
 904                                              )
 905                               );
 906       }
 907     }
 908
 909     // next transfer references _to_ hrn over to hrnSummary
 910     Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
 911     while( itrReferencer.hasNext() ) {
 912       RefEdge edge         = itrReferencer.next();
 913       RefEdge edgeMerged   = edge.copy();
 914       edgeMerged.setDst( hrnSummary );
 915
 916       RefSrcNode onReferencer = edge.getSrc();
 917       RefEdge    edgeSummary  =
 918         onReferencer.getReferenceTo( hrnSummary,
 919                                      edge.getType(),
 920                                      edge.getField()
 921                                      );
 922
 923       if( edgeSummary == null ) {
 924         // the merge is trivial, nothing to be done
 925         addRefEdge( onReferencer, hrnSummary, edgeMerged );
 926
 927       } else {
 928         // otherwise an edge from the referencer to alpha_S exists already
 929         // and the edge referencer->alpha_K should be merged with it
 930         edgeSummary.setBeta(
 931                             Canonical.unionORpreds( edgeMerged.getBeta(),
 932                                              edgeSummary.getBeta()
 933                                              )
 934                              );
 935         edgeSummary.setPreds(
 936                              Canonical.join( edgeMerged.getPreds(),
 937                                              edgeSummary.getPreds()
 938                                              )
 939                               );
 940       }
 941     }
 942
 943     // then merge hrn reachability into hrnSummary
 944     hrnSummary.setAlpha(
 945                         Canonical.unionORpreds( hrnSummary.getAlpha(),
 946                                          hrn.getAlpha()
 947                                          )
 948                          );
 949
 950     hrnSummary.setPreds(
 951                         Canonical.join( hrnSummary.getPreds(),
 952                                         hrn.getPreds()
 953                                         )
 954                         );
 955
 956     // and afterward, this node is gone
 957     wipeOut( hrn, true );
 958   }
 959
 960
 961   protected void transferOnto( HeapRegionNode hrnA,
 962                                HeapRegionNode hrnB ) {
 963
 964     assert belongsToThis( hrnA );
 965     assert belongsToThis( hrnB );
 966     assert hrnA != hrnB;
 967
 968     // clear references in and out of node b?
 969     assert hrnB.isWiped();
 970
 971     // copy each: (edge in and out of A) to B
 972     Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
 973     while( itrReferencee.hasNext() ) {
 974       RefEdge        edge          = itrReferencee.next();
 975       HeapRegionNode hrnReferencee = edge.getDst();
 976       RefEdge        edgeNew       = edge.copy();
 977       edgeNew.setSrc( hrnB );
 978       edgeNew.setDst( hrnReferencee );
 979
 980       addRefEdge( hrnB, hrnReferencee, edgeNew );
 981     }
 982
 983     Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
 984     while( itrReferencer.hasNext() ) {
 985       RefEdge    edge          = itrReferencer.next();
 986       RefSrcNode rsnReferencer = edge.getSrc();
 987       RefEdge    edgeNew       = edge.copy();
 988       edgeNew.setSrc( rsnReferencer );
 989       edgeNew.setDst( hrnB );
 990
 991       addRefEdge( rsnReferencer, hrnB, edgeNew );
 992     }
 993
 994     // replace hrnB reachability and preds with hrnA's
 995     hrnB.setAlpha( hrnA.getAlpha() );
 996     hrnB.setPreds( hrnA.getPreds() );
 997
 998     // after transfer, wipe out source
 999     wipeOut( hrnA, true );
1000   }
1001
1002
1003   // the purpose of this method is to conceptually "wipe out"
1004   // a heap region from the graph--purposefully not called REMOVE
1005   // because the node is still hanging around in the graph, just
1006   // not mechanically connected or have any reach or predicate
1007   // information on it anymore--lots of ops can use this
1008   protected void wipeOut( HeapRegionNode hrn,
1009                           boolean        wipeVariableReferences ) {
1010
1011     assert belongsToThis( hrn );
1012
1013     clearRefEdgesFrom( hrn, null, null, true );
1014
1015     if( wipeVariableReferences ) {
1016       clearRefEdgesTo( hrn, null, null, true );
1017     } else {
1018       clearNonVarRefEdgesTo( hrn );
1019     }
1020
1021     hrn.setAlpha( rsetEmpty );
1022     hrn.setPreds( predsEmpty );
1023   }
1024
1025
1026   protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1027     edge.setBeta(
1028                  Canonical.ageTuplesFrom( edge.getBeta(),
1029                                           as
1030                                           )
1031                   );
1032   }
1033
1034   protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1035     hrn.setAlpha(
1036                  Canonical.ageTuplesFrom( hrn.getAlpha(),
1037                                           as
1038                                           )
1039                   );
1040   }
1041
1042
1043
1044   protected void propagateTokensOverNodes( HeapRegionNode          nPrime,
1045                                            ChangeSet               c0,
1046                                            HashSet<HeapRegionNode> nodesWithNewAlpha,
1047                                            HashSet<RefEdge>        edgesWithNewBeta ) {
1048
1049     HashSet<HeapRegionNode> todoNodes
1050       = new HashSet<HeapRegionNode>();
1051     todoNodes.add( nPrime );
1052
1053     HashSet<RefEdge> todoEdges
1054       = new HashSet<RefEdge>();
1055
1056     Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1057       = new Hashtable<HeapRegionNode, ChangeSet>();
1058     nodePlannedChanges.put( nPrime, c0 );
1059
1060     Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1061       = new Hashtable<RefEdge, ChangeSet>();
1062
1063     // first propagate change sets everywhere they can go
1064     while( !todoNodes.isEmpty() ) {
1065       HeapRegionNode n = todoNodes.iterator().next();
1066       ChangeSet      C = nodePlannedChanges.get( n );
1067
1068       Iterator<RefEdge> referItr = n.iteratorToReferencers();
1069       while( referItr.hasNext() ) {
1070         RefEdge edge = referItr.next();
1071         todoEdges.add( edge );
1072
1073         if( !edgePlannedChanges.containsKey( edge ) ) {
1074           edgePlannedChanges.put( edge,
1075                                   ChangeSet.factory()
1076                                   );
1077         }
1078
1079         edgePlannedChanges.put( edge,
1080                                 Canonical.union( edgePlannedChanges.get( edge ),
1081                                                  C
1082                                                  )
1083                                 );
1084       }
1085
1086       Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1087       while( refeeItr.hasNext() ) {
1088         RefEdge        edgeF = refeeItr.next();
1089         HeapRegionNode m     = edgeF.getDst();
1090
1091         ChangeSet changesToPass = ChangeSet.factory();
1092
1093         Iterator<ChangeTuple> itrCprime = C.iterator();
1094         while( itrCprime.hasNext() ) {
1095           ChangeTuple c = itrCprime.next();
1096           if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
1097               != null
1098               ) {
1099             changesToPass = Canonical.add( changesToPass, c );
1100           }
1101         }
1102
1103         if( !changesToPass.isEmpty() ) {
1104           if( !nodePlannedChanges.containsKey( m ) ) {
1105             nodePlannedChanges.put( m, ChangeSet.factory() );
1106           }
1107
1108           ChangeSet currentChanges = nodePlannedChanges.get( m );
1109
1110           if( !changesToPass.isSubset( currentChanges ) ) {
1111
1112             nodePlannedChanges.put( m,
1113                                     Canonical.union( currentChanges,
1114                                                      changesToPass
1115                                                      )
1116                                     );
1117             todoNodes.add( m );
1118           }
1119         }
1120       }
1121
1122       todoNodes.remove( n );
1123     }
1124
1125     // then apply all of the changes for each node at once
1126     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1127     while( itrMap.hasNext() ) {
1128       Map.Entry      me = (Map.Entry)      itrMap.next();
1129       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1130       ChangeSet      C  = (ChangeSet)      me.getValue();
1131
1132       // this propagation step is with respect to one change,
1133       // so we capture the full change from the old alpha:
1134       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1135                                                       C,
1136                                                       true
1137                                                       );
1138       // but this propagation may be only one of many concurrent
1139       // possible changes, so keep a running union with the node's
1140       // partially updated new alpha set
1141       n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1142                                       localDelta
1143                                       )
1144                      );
1145
1146       nodesWithNewAlpha.add( n );
1147     }
1148
1149     propagateTokensOverEdges( todoEdges,
1150                               edgePlannedChanges,
1151                               edgesWithNewBeta
1152                               );
1153   }
1154
1155
1156   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1157                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1158                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1159
1160     // first propagate all change tuples everywhere they can go
1161     while( !todoEdges.isEmpty() ) {
1162       RefEdge edgeE = todoEdges.iterator().next();
1163       todoEdges.remove( edgeE );
1164
1165       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1166         edgePlannedChanges.put( edgeE,
1167                                 ChangeSet.factory()
1168                                 );
1169       }
1170
1171       ChangeSet C = edgePlannedChanges.get( edgeE );
1172
1173       ChangeSet changesToPass = ChangeSet.factory();
1174
1175       Iterator<ChangeTuple> itrC = C.iterator();
1176       while( itrC.hasNext() ) {
1177         ChangeTuple c = itrC.next();
1178         if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1179             != null
1180             ) {
1181           changesToPass = Canonical.add( changesToPass, c );
1182         }
1183       }
1184
1185       RefSrcNode rsn = edgeE.getSrc();
1186
1187       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1188         HeapRegionNode n = (HeapRegionNode) rsn;
1189
1190         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1191         while( referItr.hasNext() ) {
1192           RefEdge edgeF = referItr.next();
1193
1194           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1195             edgePlannedChanges.put( edgeF,
1196                                     ChangeSet.factory()
1197                                     );
1198           }
1199
1200           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1201
1202           if( !changesToPass.isSubset( currentChanges ) ) {
1203             todoEdges.add( edgeF );
1204             edgePlannedChanges.put( edgeF,
1205                                     Canonical.union( currentChanges,
1206                                                      changesToPass
1207                                                      )
1208                                     );
1209           }
1210         }
1211       }
1212     }
1213
1214     // then apply all of the changes for each edge at once
1215     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1216     while( itrMap.hasNext() ) {
1217       Map.Entry me = (Map.Entry) itrMap.next();
1218       RefEdge   e  = (RefEdge)   me.getKey();
1219       ChangeSet C  = (ChangeSet) me.getValue();
1220
1221       // this propagation step is with respect to one change,
1222       // so we capture the full change from the old beta:
1223       ReachSet localDelta =
1224         Canonical.applyChangeSet( e.getBeta(),
1225                                   C,
1226                                   true
1227                                   );
1228
1229       // but this propagation may be only one of many concurrent
1230       // possible changes, so keep a running union with the edge's
1231       // partially updated new beta set
1232       e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1233                                      localDelta
1234                                      )
1235                     );
1236
1237       edgesWithNewBeta.add( e );
1238     }
1239   }
1240
1241
1242   // used in makeCalleeView below to decide if there is
1243   // already an appropriate out-of-context edge in a callee
1244   // view graph for merging, or null if a new one will be added
1245   protected RefEdge
1246     getOutOfContextReferenceTo( HeapRegionNode hrn,
1247                                 TypeDescriptor srcType,
1248                                 TypeDescriptor refType,
1249                                 String         refField ) {
1250     assert belongsToThis( hrn );
1251
1252     HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1253     if( hrnInContext == null ) {
1254       return null;
1255     }
1256
1257     Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1258     while( refItr.hasNext() ) {
1259       RefEdge re = refItr.next();
1260
1261       assert belongsToThis( re.getSrc() );
1262       assert belongsToThis( re.getDst() );
1263
1264       if( !(re.getSrc() instanceof HeapRegionNode) ) {
1265         continue;
1266       }
1267
1268       HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1269       if( !hrnSrc.isOutOfContext() ) {
1270         continue;
1271       }
1272
1273       if( srcType == null ) {
1274         if( hrnSrc.getType() != null ) {
1275           continue;
1276         }
1277       } else {
1278         if( !srcType.equals( hrnSrc.getType() ) ) {
1279           continue;
1280         }
1281       }
1282
1283       if( !re.typeEquals( refType ) ) {
1284         continue;
1285       }
1286
1287       if( !re.fieldEquals( refField ) ) {
1288         continue;
1289       }
1290
1291       // tada!  We found it!
1292       return re;
1293     }
1294
1295     return null;
1296   }
1297
1298   // used below to convert a ReachSet to its callee-context
1299   // equivalent with respect to allocation sites in this graph
1300   protected ReachSet toCalleeContext( ReachSet        rs,
1301                                       ExistPredSet    preds,
1302                                       Set<ReachTuple> oocTuples
1303                                       ) {
1304     ReachSet out = ReachSet.factory();
1305
1306     Iterator<ReachState> itr = rs.iterator();
1307     while( itr.hasNext() ) {
1308       ReachState stateCaller = itr.next();
1309
1310       ReachState stateCallee = stateCaller;
1311
1312       Iterator<AllocSite> asItr = allocSites.iterator();
1313       while( asItr.hasNext() ) {
1314         AllocSite as = asItr.next();
1315
1316         ReachState stateNew = ReachState.factory();
1317         Iterator<ReachTuple> rtItr = stateCallee.iterator();
1318         while( rtItr.hasNext() ) {
1319           ReachTuple rt = rtItr.next();
1320
1321           // only translate this tuple if it is
1322           // in the out-callee-context bag
1323           if( !oocTuples.contains( rt ) ) {
1324             stateNew = Canonical.add( stateNew, rt );
1325             continue;
1326           }
1327
1328           int age = as.getAgeCategory( rt.getHrnID() );
1329
1330           // this is the current mapping, where 0, 1, 2S were allocated
1331           // in the current context, 0?, 1? and 2S? were allocated in a
1332           // previous context, and we're translating to a future context
1333           //
1334           // 0    -> 0?
1335           // 1    -> 1?
1336           // 2S   -> 2S?
1337           // 2S*  -> 2S?*
1338           //
1339           // 0?   -> 2S?
1340           // 1?   -> 2S?
1341           // 2S?  -> 2S?
1342           // 2S?* -> 2S?*
1343
1344           if( age == AllocSite.AGE_notInThisSite ) {
1345             // things not from the site just go back in
1346             stateNew = Canonical.add( stateNew, rt );
1347
1348           } else if( age == AllocSite.AGE_summary ||
1349                      rt.isOutOfContext()
1350                      ) {
1351             // the in-context summary and all existing out-of-context
1352             // stuff all become
1353             stateNew = Canonical.add( stateNew,
1354                                       ReachTuple.factory( as.getSummary(),
1355                                                           true, // multi
1356                                                           rt.getArity(),
1357                                                           true  // out-of-context
1358                                                           )
1359                                       );
1360           } else {
1361             // otherwise everything else just goes to an out-of-context
1362             // version, everything else the same
1363             Integer I = as.getAge( rt.getHrnID() );
1364             assert I != null;
1365
1366             assert !rt.isMultiObject();
1367
1368             stateNew = Canonical.add( stateNew,
1369                                       ReachTuple.factory( rt.getHrnID(),
1370                                                           rt.isMultiObject(),
1371                                                           rt.getArity(),
1372                                                           true  // out-of-context
1373                                                           )
1374                                       );
1375           }
1376         }
1377
1378         stateCallee = stateNew;
1379       }
1380
1381       // attach the passed in preds
1382       stateCallee = Canonical.attach( stateCallee,
1383                                       preds );
1384
1385       out = Canonical.add( out,
1386                            stateCallee
1387                            );
1388
1389     }
1390     assert out.isCanonical();
1391     return out;
1392   }
1393
1394   // used below to convert a ReachSet to its caller-context
1395   // equivalent with respect to allocation sites in this graph
1396   protected ReachSet
1397     toCallerContext( ReachSet                            rs,
1398                      Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1399                      ) {
1400     ReachSet out = ReachSet.factory();
1401
1402     Iterator<ReachState> itr = rs.iterator();
1403     while( itr.hasNext() ) {
1404       ReachState stateCallee = itr.next();
1405
1406       if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1407
1408         // starting from one callee state...
1409         ReachSet rsCaller = ReachSet.factory( stateCallee );
1410
1411         // possibly branch it into many states, which any
1412         // allocation site might do, so lots of derived states
1413         Iterator<AllocSite> asItr = allocSites.iterator();
1414         while( asItr.hasNext() ) {
1415           AllocSite as = asItr.next();
1416           rsCaller = Canonical.toCallerContext( rsCaller, as );
1417         }
1418
1419         // then before adding each derived, now caller-context
1420         // states to the output, attach the appropriate pred
1421         // based on the source callee state
1422         Iterator<ReachState> stateItr = rsCaller.iterator();
1423         while( stateItr.hasNext() ) {
1424           ReachState stateCaller = stateItr.next();
1425           stateCaller = Canonical.attach( stateCaller,
1426                                           calleeStatesSatisfied.get( stateCallee )
1427                                           );
1428           out = Canonical.add( out,
1429                                stateCaller
1430                                );
1431         }
1432       }
1433     }
1434
1435     assert out.isCanonical();
1436     return out;
1437   }
1438
1439   // used below to convert a ReachSet to an equivalent
1440   // version with shadow IDs merged into unshadowed IDs
1441   protected ReachSet unshadow( ReachSet rs ) {
1442     ReachSet out = rs;
1443     Iterator<AllocSite> asItr = allocSites.iterator();
1444     while( asItr.hasNext() ) {
1445       AllocSite as = asItr.next();
1446       out = Canonical.unshadow( out, as );
1447     }
1448     assert out.isCanonical();
1449     return out;
1450   }
1451
1452
1453   // use this method to make a new reach graph that is
1454   // what heap the FlatMethod callee from the FlatCall
1455   // would start with reaching from its arguments in
1456   // this reach graph
1457   public ReachGraph
1458     makeCalleeView( FlatCall     fc,
1459                     FlatMethod   fmCallee,
1460                     Set<Integer> callerNodeIDsCopiedToCallee,
1461                     boolean      writeDebugDOTs
1462                     ) {
1463
1464
1465     // first traverse this context to find nodes and edges
1466     //  that will be callee-reachable
1467     Set<HeapRegionNode> reachableCallerNodes =
1468       new HashSet<HeapRegionNode>();
1469
1470     // caller edges between callee-reachable nodes
1471     Set<RefEdge> reachableCallerEdges =
1472       new HashSet<RefEdge>();
1473
1474     // caller edges from arg vars, and the matching param index
1475     // because these become a special edge in callee
1476     Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1477       new Hashtable<RefEdge, Integer>();
1478
1479     // caller edges from local vars or callee-unreachable nodes
1480     // (out-of-context sources) to callee-reachable nodes
1481     Set<RefEdge> oocCallerEdges =
1482       new HashSet<RefEdge>();
1483
1484
1485     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1486
1487       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1488       VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1489
1490       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1491       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1492
1493       toVisitInCaller.add( vnArgCaller );
1494
1495       while( !toVisitInCaller.isEmpty() ) {
1496         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1497         toVisitInCaller.remove( rsnCaller );
1498         visitedInCaller.add( rsnCaller );
1499
1500         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1501         while( itrRefEdges.hasNext() ) {
1502           RefEdge        reCaller  = itrRefEdges.next();
1503           HeapRegionNode hrnCaller = reCaller.getDst();
1504
1505           callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1506           reachableCallerNodes.add( hrnCaller );
1507
1508           if( reCaller.getSrc() instanceof HeapRegionNode ) {
1509             reachableCallerEdges.add( reCaller );
1510           } else {
1511             if( rsnCaller.equals( vnArgCaller ) ) {
1512               reachableCallerArgEdges2paramIndex.put( reCaller, i );
1513             } else {
1514               oocCallerEdges.add( reCaller );
1515             }
1516           }
1517
1518           if( !visitedInCaller.contains( hrnCaller ) ) {
1519             toVisitInCaller.add( hrnCaller );
1520           }
1521
1522         } // end edge iteration
1523       } // end visiting heap nodes in caller
1524     } // end iterating over parameters as starting points
1525
1526
1527     // now collect out-of-context reach tuples and
1528     // more out-of-context edges
1529     Set<ReachTuple> oocTuples = new HashSet<ReachTuple>();
1530
1531     Iterator<Integer> itrInContext =
1532       callerNodeIDsCopiedToCallee.iterator();
1533     while( itrInContext.hasNext() ) {
1534       Integer        hrnID                 = itrInContext.next();
1535       HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1536
1537       Iterator<RefEdge> itrMightCross =
1538         hrnCallerAndInContext.iteratorToReferencers();
1539       while( itrMightCross.hasNext() ) {
1540         RefEdge edgeMightCross = itrMightCross.next();
1541
1542         RefSrcNode rsnCallerAndOutContext =
1543           edgeMightCross.getSrc();
1544
1545         if( rsnCallerAndOutContext instanceof VariableNode ) {
1546           // variables do not have out-of-context reach states,
1547           // so jump out now
1548           oocCallerEdges.add( edgeMightCross );
1549           continue;
1550         }
1551
1552         HeapRegionNode hrnCallerAndOutContext =
1553           (HeapRegionNode) rsnCallerAndOutContext;
1554
1555         // is this source node out-of-context?
1556         if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1557           // no, skip this edge
1558           continue;
1559         }
1560
1561         // okay, we got one
1562         oocCallerEdges.add( edgeMightCross );
1563
1564         // add all reach tuples on the node to list
1565         // of things that are out-of-context: insight
1566         // if this node is reachable from someting that WAS
1567         // in-context, then this node should already be in-context
1568         Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1569         while( stateItr.hasNext() ) {
1570           ReachState state = stateItr.next();
1571
1572           Iterator<ReachTuple> rtItr = state.iterator();
1573           while( rtItr.hasNext() ) {
1574             ReachTuple rt = rtItr.next();
1575
1576             oocTuples.add( rt );
1577           }
1578         }
1579       }
1580     }
1581
1582
1583     // the callee view is a new graph: DON'T MODIFY *THIS* graph
1584     ReachGraph rg = new ReachGraph();
1585
1586     // add nodes to callee graph
1587     Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1588     while( hrnItr.hasNext() ) {
1589       HeapRegionNode hrnCaller = hrnItr.next();
1590
1591       assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1592       assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1593
1594       ExistPred    pred  = ExistPred.factory( hrnCaller.getID(), null );
1595       ExistPredSet preds = ExistPredSet.factory( pred );
1596
1597       rg.createNewHeapRegionNode( hrnCaller.getID(),
1598                                   hrnCaller.isSingleObject(),
1599                                   hrnCaller.isNewSummary(),
1600                                   hrnCaller.isFlagged(),
1601                                   false, // out-of-context?
1602                                   hrnCaller.getType(),
1603                                   hrnCaller.getAllocSite(),
1604                                   toCalleeContext( hrnCaller.getInherent(),
1605                                                    preds,
1606                                                    oocTuples
1607                                                    ),
1608                                   toCalleeContext( hrnCaller.getAlpha(),
1609                                                    preds,
1610                                                    oocTuples
1611                                                    ),
1612                                   preds,
1613                                   hrnCaller.getDescription()
1614                                   );
1615     }
1616
1617     // add param edges to callee graph
1618     Iterator argEdges =
1619       reachableCallerArgEdges2paramIndex.entrySet().iterator();
1620     while( argEdges.hasNext() ) {
1621       Map.Entry me    = (Map.Entry) argEdges.next();
1622       RefEdge   reArg = (RefEdge)   me.getKey();
1623       Integer   index = (Integer)   me.getValue();
1624
1625       TempDescriptor arg = fmCallee.getParameter( index );
1626
1627       VariableNode vnCallee =
1628         rg.getVariableNodeFromTemp( arg );
1629
1630       HeapRegionNode hrnDstCaller = reArg.getDst();
1631       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1632       assert hrnDstCallee != null;
1633
1634       ExistPred pred =
1635         ExistPred.factory( arg,
1636                            null,
1637                            hrnDstCallee.getID(),
1638                            reArg.getType(),
1639                            reArg.getField(),
1640                            null,
1641                            true,  // out-of-callee-context
1642                            false  // out-of-caller-context
1643                            );
1644
1645       ExistPredSet preds =
1646         ExistPredSet.factory( pred );
1647
1648       RefEdge reCallee =
1649         new RefEdge( vnCallee,
1650                      hrnDstCallee,
1651                      reArg.getType(),
1652                      reArg.getField(),
1653                      toCalleeContext( reArg.getBeta(),
1654                                       preds,
1655                                       oocTuples
1656                                       ),
1657                      preds
1658                      );
1659
1660       rg.addRefEdge( vnCallee,
1661                      hrnDstCallee,
1662                      reCallee
1663                      );
1664     }
1665
1666     // add in-context edges to callee graph
1667     Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1668     while( reItr.hasNext() ) {
1669       RefEdge    reCaller  = reItr.next();
1670       RefSrcNode rsnCaller = reCaller.getSrc();
1671       assert rsnCaller instanceof HeapRegionNode;
1672       HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1673       HeapRegionNode hrnDstCaller = reCaller.getDst();
1674
1675       HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1676       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1677       assert hrnSrcCallee != null;
1678       assert hrnDstCallee != null;
1679
1680       ExistPred pred =
1681         ExistPred.factory( null,
1682                            hrnSrcCallee.getID(),
1683                            hrnDstCallee.getID(),
1684                            reCaller.getType(),
1685                            reCaller.getField(),
1686                            null,
1687                            false, // out-of-callee-context
1688                            false  // out-of-caller-context
1689                            );
1690
1691       ExistPredSet preds =
1692         ExistPredSet.factory( pred );
1693
1694       RefEdge reCallee =
1695         new RefEdge( hrnSrcCallee,
1696                      hrnDstCallee,
1697                      reCaller.getType(),
1698                      reCaller.getField(),
1699                      toCalleeContext( reCaller.getBeta(),
1700                                       preds,
1701                                       oocTuples
1702                                       ),
1703                      preds
1704                      );
1705
1706       rg.addRefEdge( hrnSrcCallee,
1707                      hrnDstCallee,
1708                      reCallee
1709                      );
1710     }
1711
1712     // add out-of-context edges to callee graph
1713     reItr = oocCallerEdges.iterator();
1714     while( reItr.hasNext() ) {
1715       RefEdge        reCaller     = reItr.next();
1716       RefSrcNode     rsnCaller    = reCaller.getSrc();
1717       HeapRegionNode hrnDstCaller = reCaller.getDst();
1718       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1719       assert hrnDstCallee != null;
1720
1721       TypeDescriptor oocNodeType;
1722       ReachSet       oocReach;
1723       TempDescriptor oocPredSrcTemp = null;
1724       Integer        oocPredSrcID   = null;
1725       boolean        outOfCalleeContext;
1726       boolean        outOfCallerContext;
1727
1728       if( rsnCaller instanceof VariableNode ) {
1729         VariableNode vnCaller = (VariableNode) rsnCaller;
1730         oocNodeType    = null;
1731         oocReach       = rsetEmpty;
1732         oocPredSrcTemp = vnCaller.getTempDescriptor();
1733         outOfCalleeContext = true;
1734         outOfCallerContext = false;
1735
1736       } else {
1737         HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1738         assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1739         oocNodeType  = hrnSrcCaller.getType();
1740         oocReach     = hrnSrcCaller.getAlpha();
1741         oocPredSrcID = hrnSrcCaller.getID();
1742         if( hrnSrcCaller.isOutOfContext() ) {
1743           outOfCalleeContext = false;
1744           outOfCallerContext = true;
1745         } else {
1746           outOfCalleeContext = true;
1747           outOfCallerContext = false;
1748         }
1749       }
1750
1751       ExistPred pred =
1752         ExistPred.factory( oocPredSrcTemp,
1753                            oocPredSrcID,
1754                            hrnDstCallee.getID(),
1755                            reCaller.getType(),
1756                            reCaller.getField(),
1757                            null,
1758                            outOfCalleeContext,
1759                            outOfCallerContext
1760                            );
1761
1762       ExistPredSet preds =
1763         ExistPredSet.factory( pred );
1764
1765       RefEdge oocEdgeExisting =
1766         rg.getOutOfContextReferenceTo( hrnDstCallee,
1767                                        oocNodeType,
1768                                        reCaller.getType(),
1769                                        reCaller.getField()
1770                                        );
1771
1772       if( oocEdgeExisting == null ) {
1773           // for consistency, map one out-of-context "identifier"
1774           // to one heap region node id, otherwise no convergence
1775         String oocid = "oocid"+
1776           fmCallee+
1777           hrnDstCallee.getIDString()+
1778           oocNodeType+
1779           reCaller.getType()+
1780           reCaller.getField();
1781
1782         Integer oocHrnID = oocid2hrnid.get( oocid );
1783
1784         HeapRegionNode hrnCalleeAndOutContext;
1785
1786         if( oocHrnID == null ) {
1787
1788           hrnCalleeAndOutContext =
1789             rg.createNewHeapRegionNode( null,  // ID
1790                                         false, // single object?
1791                                         false, // new summary?
1792                                         false, // flagged?
1793                                         true,  // out-of-context?
1794                                         oocNodeType,
1795                                         null,  // alloc site, shouldn't be used
1796                                         toCalleeContext( oocReach,
1797                                                          preds,
1798                                                          oocTuples
1799                                                          ),
1800                                         toCalleeContext( oocReach,
1801                                                          preds,
1802                                                          oocTuples
1803                                                          ),
1804                                         preds,
1805                                         "out-of-context"
1806                                         );
1807
1808           oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1809
1810         } else {
1811
1812           // the mapping already exists, so see if node is there
1813           hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1814
1815           if( hrnCalleeAndOutContext == null ) {
1816             // nope, make it
1817             hrnCalleeAndOutContext =
1818               rg.createNewHeapRegionNode( oocHrnID,  // ID
1819                                           false, // single object?
1820                                           false, // new summary?
1821                                           false, // flagged?
1822                                           true,  // out-of-context?
1823                                           oocNodeType,
1824                                           null,  // alloc site, shouldn't be used
1825                                           toCalleeContext( oocReach,
1826                                                            preds,
1827                                                            oocTuples
1828                                                            ),
1829                                           toCalleeContext( oocReach,
1830                                                            preds,
1831                                                            oocTuples
1832                                                            ),
1833                                           preds,
1834                                           "out-of-context"
1835                                           );
1836           } else {
1837             // otherwise it is there, so merge reachability
1838             hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1839                                                                      toCalleeContext( oocReach,
1840                                                                                       preds,
1841                                                                                       oocTuples
1842                                                                                       )
1843                                                                      )
1844                                              );
1845           }
1846         }
1847
1848         rg.addRefEdge( hrnCalleeAndOutContext,
1849                        hrnDstCallee,
1850                        new RefEdge( hrnCalleeAndOutContext,
1851                                     hrnDstCallee,
1852                                     reCaller.getType(),
1853                                     reCaller.getField(),
1854                                     toCalleeContext( reCaller.getBeta(),
1855                                                      preds,
1856                                                      oocTuples
1857                                                      ),
1858                                     preds
1859                                     )
1860                        );
1861
1862         } else {
1863         // the out-of-context edge already exists
1864         oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1865                                                          toCalleeContext( reCaller.getBeta(),
1866                                                                           preds,
1867                                                                           oocTuples
1868                                                                           )
1869                                                   )
1870                                  );
1871
1872         oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1873                                                   reCaller.getPreds()
1874                                                   )
1875                                   );
1876
1877         HeapRegionNode hrnCalleeAndOutContext =
1878           (HeapRegionNode) oocEdgeExisting.getSrc();
1879         hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1880                                                                  toCalleeContext( oocReach,
1881                                                                                   preds,
1882                                                                                   oocTuples
1883                                                                                   )
1884                                                                  )
1885                                          );
1886
1887
1888       }
1889     }
1890
1891
1892     if( writeDebugDOTs ) {
1893       try {
1894         rg.writeGraph( "calleeview",
1895                        resolveMethodDebugDOTwriteLabels,
1896                        resolveMethodDebugDOTselectTemps,
1897                        resolveMethodDebugDOTpruneGarbage,
1898                        resolveMethodDebugDOThideSubsetReach,
1899                        resolveMethodDebugDOThideEdgeTaints );
1900       } catch( IOException e ) {}
1901     }
1902
1903     return rg;
1904   }
1905
1906   private static Hashtable<String, Integer> oocid2hrnid =
1907     new Hashtable<String, Integer>();
1908
1909
1910   // useful since many graphs writes in the method call debug code
1911   private static boolean resolveMethodDebugDOTwriteLabels     = true;
1912   private static boolean resolveMethodDebugDOTselectTemps     = true;
1913   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
1914   private static boolean resolveMethodDebugDOThideSubsetReach = false;
1915   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
1916
1917
1918
1919   public void
1920     resolveMethodCall( FlatCall     fc,
1921                        FlatMethod   fmCallee,
1922                        ReachGraph   rgCallee,
1923                        Set<Integer> callerNodeIDsCopiedToCallee,
1924                        boolean      writeDebugDOTs
1925                        ) {
1926
1927
1928     if( writeDebugDOTs ) {
1929       try {
1930         rgCallee.writeGraph( "callee",
1931                        resolveMethodDebugDOTwriteLabels,
1932                        resolveMethodDebugDOTselectTemps,
1933                        resolveMethodDebugDOTpruneGarbage,
1934                        resolveMethodDebugDOThideSubsetReach,
1935                        resolveMethodDebugDOThideEdgeTaints );
1936
1937         writeGraph( "caller00In",
1938                     resolveMethodDebugDOTwriteLabels,
1939                     resolveMethodDebugDOTselectTemps,
1940                     resolveMethodDebugDOTpruneGarbage,
1941                     resolveMethodDebugDOThideSubsetReach,
1942                     resolveMethodDebugDOThideEdgeTaints,
1943                     callerNodeIDsCopiedToCallee );
1944       } catch( IOException e ) {}
1945     }
1946
1947
1948     // method call transfer function steps:
1949     // 1. Use current callee-reachable heap (CRH) to test callee
1950     //    predicates and mark what will be coming in.
1951     // 2. Wipe CRH out of caller.
1952     // 3. Transplant marked callee parts in:
1953     //    a) bring in nodes
1954     //    b) bring in callee -> callee edges
1955     //    c) resolve out-of-context -> callee edges
1956     //    d) assign return value
1957     // 4. Collapse shadow nodes down
1958     // 5. Global sweep it.
1959
1960
1961
1962     // 1. mark what callee elements have satisfied predicates
1963     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1964       new Hashtable<HeapRegionNode, ExistPredSet>();
1965
1966     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1967       new Hashtable<RefEdge, ExistPredSet>();
1968
1969     Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1970       new Hashtable<ReachState, ExistPredSet>();
1971
1972     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1973       new Hashtable< RefEdge, Set<RefSrcNode> >();
1974
1975     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1976     while( meItr.hasNext() ) {
1977       Map.Entry      me        = (Map.Entry)      meItr.next();
1978       Integer        id        = (Integer)        me.getKey();
1979       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1980
1981       // if a callee element's predicates are satisfied then a set
1982       // of CALLER predicates is returned: they are the predicates
1983       // that the callee element moved into the caller context
1984       // should have, and it is inefficient to find this again later
1985       ExistPredSet predsIfSatis =
1986         hrnCallee.getPreds().isSatisfiedBy( this,
1987                                             callerNodeIDsCopiedToCallee
1988                                             );
1989       if( predsIfSatis != null ) {
1990         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1991       } else {
1992         // otherwise don't bother looking at edges to this node
1993         continue;
1994       }
1995
1996       // since the node is coming over, find out which reach
1997       // states on it should come over, too
1998       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
1999       while( stateItr.hasNext() ) {
2000         ReachState stateCallee = stateItr.next();
2001
2002         predsIfSatis =
2003           stateCallee.getPreds().isSatisfiedBy( this,
2004                                                 callerNodeIDsCopiedToCallee
2005                                                 );
2006         if( predsIfSatis != null ) {
2007           calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2008         }
2009       }
2010
2011       // then look at edges to the node
2012       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2013       while( reItr.hasNext() ) {
2014         RefEdge    reCallee  = reItr.next();
2015         RefSrcNode rsnCallee = reCallee.getSrc();
2016
2017         // (caller local variables to in-context heap regions)
2018         // have an (out-of-context heap region -> in-context heap region)
2019         // abstraction in the callEE, so its true we never need to
2020         // look at a (var node -> heap region) edge in callee to bring
2021         // those over for the call site transfer.  What about (param var->heap region)
2022         // edges in callee? They are dealt with below this loop.
2023         // So, yes, at this point skip (var->region) edges in callee
2024         if( rsnCallee instanceof VariableNode ) {
2025           continue;
2026         }
2027
2028         // first see if the source is out-of-context, and only
2029         // proceed with this edge if we find some caller-context
2030         // matches
2031         HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2032         boolean matchedOutOfContext = false;
2033
2034         if( hrnSrcCallee.isOutOfContext() ) {
2035
2036           assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2037           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2038
2039           HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2040           Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2041           while( reDstItr.hasNext() ) {
2042             // the edge and field (either possibly null) must match
2043             RefEdge reCaller = reDstItr.next();
2044
2045             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
2046                 !reCaller.fieldEquals( reCallee.getField() )
2047                 ) {
2048               continue;
2049             }
2050
2051             RefSrcNode rsnCaller = reCaller.getSrc();
2052             if( rsnCaller instanceof VariableNode ) {
2053               // a variable node matches an OOC region with null type
2054               if( hrnSrcCallee.getType() != null ) {
2055                 continue;
2056               }
2057
2058             } else {
2059               // otherwise types should match
2060               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2061               if( hrnSrcCallee.getType() == null ) {
2062                 if( hrnCallerSrc.getType() != null ) {
2063                   continue;
2064                 }
2065               } else {
2066                 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2067                   continue;
2068                 }
2069               }
2070             }
2071
2072             rsnCallers.add( rsnCaller );
2073             matchedOutOfContext = true;
2074           }
2075
2076           if( !rsnCallers.isEmpty() ) {
2077             calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2078           }
2079         }
2080
2081         if( hrnSrcCallee.isOutOfContext() &&
2082             !matchedOutOfContext ) {
2083           continue;
2084         }
2085
2086         predsIfSatis =
2087           reCallee.getPreds().isSatisfiedBy( this,
2088                                              callerNodeIDsCopiedToCallee
2089                                              );
2090         if( predsIfSatis != null ) {
2091           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2092
2093           // since the edge is coming over, find out which reach
2094           // states on it should come over, too
2095           stateItr = reCallee.getBeta().iterator();
2096           while( stateItr.hasNext() ) {
2097             ReachState stateCallee = stateItr.next();
2098
2099             predsIfSatis =
2100               stateCallee.getPreds().isSatisfiedBy( this,
2101                                                     callerNodeIDsCopiedToCallee
2102                                                     );
2103             if( predsIfSatis != null ) {
2104               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2105             }
2106           }
2107         }
2108       }
2109     }
2110
2111     // test param -> HRN edges, also
2112     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2113
2114       // parameter defined here is the symbol in the callee
2115       TempDescriptor tdParam  = fmCallee.getParameter( i );
2116       VariableNode   vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2117
2118       Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2119       while( reItr.hasNext() ) {
2120         RefEdge reCallee = reItr.next();
2121
2122         ExistPredSet ifDst =
2123           reCallee.getDst().getPreds().isSatisfiedBy( this,
2124                                                       callerNodeIDsCopiedToCallee
2125                                                       );
2126         if( ifDst == null ) {
2127           continue;
2128         }
2129
2130         ExistPredSet predsIfSatis =
2131           reCallee.getPreds().isSatisfiedBy( this,
2132                                              callerNodeIDsCopiedToCallee
2133                                              );
2134         if( predsIfSatis != null ) {
2135           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2136
2137           // since the edge is coming over, find out which reach
2138           // states on it should come over, too
2139           Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2140           while( stateItr.hasNext() ) {
2141             ReachState stateCallee = stateItr.next();
2142
2143             predsIfSatis =
2144               stateCallee.getPreds().isSatisfiedBy( this,
2145                                                     callerNodeIDsCopiedToCallee
2146                                                     );
2147             if( predsIfSatis != null ) {
2148               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2149             }
2150           }
2151
2152         }
2153       }
2154     }
2155
2156
2157
2158
2159     if( writeDebugDOTs ) {
2160       try {
2161         writeGraph( "caller20BeforeWipe",
2162                     resolveMethodDebugDOTwriteLabels,
2163                     resolveMethodDebugDOTselectTemps,
2164                     resolveMethodDebugDOTpruneGarbage,
2165                     resolveMethodDebugDOThideSubsetReach,
2166                     resolveMethodDebugDOThideEdgeTaints );
2167       } catch( IOException e ) {}
2168     }
2169
2170
2171     // 2. predicates tested, ok to wipe out caller part
2172     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2173     while( hrnItr.hasNext() ) {
2174       Integer        hrnID     = hrnItr.next();
2175       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2176       assert hrnCaller != null;
2177
2178       // when clearing off nodes, also eliminate variable
2179       // references
2180       wipeOut( hrnCaller, true );
2181     }
2182
2183
2184
2185     if( writeDebugDOTs ) {
2186       try {
2187         writeGraph( "caller30BeforeAddingNodes",
2188                     resolveMethodDebugDOTwriteLabels,
2189                     resolveMethodDebugDOTselectTemps,
2190                     resolveMethodDebugDOTpruneGarbage,
2191                     resolveMethodDebugDOThideSubsetReach,
2192                     resolveMethodDebugDOThideEdgeTaints );
2193       } catch( IOException e ) {}
2194     }
2195
2196
2197     // 3. callee elements with satisfied preds come in, note that
2198     //    the mapping of elements satisfied to preds is like this:
2199     //    A callee element EE has preds EEp that are satisfied by
2200     //    some caller element ER.  We bring EE into the caller
2201     //    context as ERee with the preds of ER, namely ERp, which
2202     //    in the following algorithm is the value in the mapping
2203
2204     // 3.a) nodes
2205     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2206     while( satisItr.hasNext() ) {
2207       Map.Entry      me        = (Map.Entry)      satisItr.next();
2208       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2209       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
2210
2211       // TODO: I think its true that the current implementation uses
2212       // the type of the OOC region and the predicates OF THE EDGE from
2213       // it to link everything up in caller context, so that's why we're
2214       // skipping this... maybe that's a sillier way to do it?
2215       if( hrnCallee.isOutOfContext() ) {
2216         continue;
2217       }
2218
2219       AllocSite as = hrnCallee.getAllocSite();
2220       allocSites.add( as );
2221
2222       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2223
2224       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2225       if( hrnCaller == null ) {
2226         hrnCaller =
2227           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
2228                                    hrnCallee.isSingleObject(), // single object?
2229                                    hrnCallee.isNewSummary(),   // summary?
2230                                    hrnCallee.isFlagged(),      // flagged?
2231                                    false,                      // out-of-context?
2232                                    hrnCallee.getType(),        // type
2233                                    hrnCallee.getAllocSite(),   // allocation site
2234                                    toCallerContext( hrnCallee.getInherent(),
2235                                                     calleeStatesSatisfied  ),    // inherent reach
2236                                    null,                       // current reach
2237                                    predsEmpty,                 // predicates
2238                                    hrnCallee.getDescription()  // description
2239                                    );
2240       } else {
2241         assert hrnCaller.isWiped();
2242       }
2243
2244       hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2245                                            calleeStatesSatisfied
2246                                            )
2247                           );
2248
2249       hrnCaller.setPreds( preds );
2250     }
2251
2252
2253
2254     if( writeDebugDOTs ) {
2255       try {
2256         writeGraph( "caller31BeforeAddingEdges",
2257                     resolveMethodDebugDOTwriteLabels,
2258                     resolveMethodDebugDOTselectTemps,
2259                     resolveMethodDebugDOTpruneGarbage,
2260                     resolveMethodDebugDOThideSubsetReach,
2261                     resolveMethodDebugDOThideEdgeTaints );
2262       } catch( IOException e ) {}
2263     }
2264
2265
2266     // set these up during the next procedure so after
2267     // the caller has all of its nodes and edges put
2268     // back together we can propagate the callee's
2269     // reach changes backwards into the caller graph
2270     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2271
2272     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2273       new Hashtable<RefEdge, ChangeSet>();
2274
2275
2276     // 3.b) callee -> callee edges AND out-of-context -> callee
2277     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2278     while( satisItr.hasNext() ) {
2279       Map.Entry    me       = (Map.Entry)    satisItr.next();
2280       RefEdge      reCallee = (RefEdge)      me.getKey();
2281       ExistPredSet preds    = (ExistPredSet) me.getValue();
2282
2283       HeapRegionNode hrnDstCallee = reCallee.getDst();
2284       AllocSite      asDst        = hrnDstCallee.getAllocSite();
2285       allocSites.add( asDst );
2286
2287       Integer hrnIDDstShadow =
2288         asDst.getShadowIDfromID( hrnDstCallee.getID() );
2289
2290       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2291       assert hrnDstCaller != null;
2292
2293
2294       RefSrcNode rsnCallee = reCallee.getSrc();
2295
2296       Set<RefSrcNode> rsnCallers =
2297         new HashSet<RefSrcNode>();
2298
2299       Set<RefSrcNode> oocCallers =
2300         calleeEdges2oocCallerSrcMatches.get( reCallee );
2301
2302       boolean oocEdges = false;
2303
2304       if( oocCallers == null ) {
2305         // there are no out-of-context matches, so it's
2306         // either a param/arg var or one in-context heap region
2307         if( rsnCallee instanceof VariableNode ) {
2308           // variable -> node in the callee should only
2309           // come into the caller if its from a param var
2310           VariableNode   vnCallee = (VariableNode) rsnCallee;
2311           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2312           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
2313                                                             tdParam );
2314           if( tdArg == null ) {
2315             // this means the variable isn't a parameter, its local
2316             // to the callee so we ignore it in call site transfer
2317             // shouldn't this NEVER HAPPEN?
2318             assert false;
2319           }
2320           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2321           oocEdges = true;
2322
2323         } else {
2324           // otherwise source is in context, one region
2325           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2326
2327           // translate an in-context node to shadow
2328           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2329           allocSites.add( asSrc );
2330
2331           Integer hrnIDSrcShadow =
2332             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2333
2334           HeapRegionNode hrnSrcCallerShadow =
2335             this.id2hrn.get( hrnIDSrcShadow );
2336
2337           if( hrnSrcCallerShadow == null ) {
2338             hrnSrcCallerShadow =
2339               createNewHeapRegionNode( hrnIDSrcShadow,                // id or null to generate a new one
2340                                        hrnSrcCallee.isSingleObject(), // single object?
2341                                        hrnSrcCallee.isNewSummary(),   // summary?
2342                                        hrnSrcCallee.isFlagged(),      // flagged?
2343                                        false,                         // out-of-context?
2344                                        hrnSrcCallee.getType(),        // type
2345                                        hrnSrcCallee.getAllocSite(),   // allocation site
2346                                        toCallerContext( hrnSrcCallee.getInherent(),
2347                                                         calleeStatesSatisfied ),    // inherent reach
2348                                        toCallerContext( hrnSrcCallee.getAlpha(),
2349                                                         calleeStatesSatisfied ),       // current reach
2350                                        predsEmpty,                    // predicates
2351                                        hrnSrcCallee.getDescription()  // description
2352                                        );
2353           }
2354
2355           rsnCallers.add( hrnSrcCallerShadow );
2356         }
2357
2358       } else {
2359         // otherwise we have a set of out-of-context srcs
2360         // that should NOT be translated to shadow nodes
2361         assert !oocCallers.isEmpty();
2362         rsnCallers.addAll( oocCallers );
2363         oocEdges = true;
2364       }
2365
2366       // now make all caller edges we've identified from
2367       // this callee edge with a satisfied predicate
2368       assert !rsnCallers.isEmpty();
2369       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2370       while( rsnItr.hasNext() ) {
2371         RefSrcNode rsnCaller = rsnItr.next();
2372
2373         RefEdge reCaller = new RefEdge( rsnCaller,
2374                                         hrnDstCaller,
2375                                         reCallee.getType(),
2376                                         reCallee.getField(),
2377                                         toCallerContext( reCallee.getBeta(),
2378                                                          calleeStatesSatisfied ),
2379                                         preds
2380                                         );
2381
2382         ChangeSet cs = ChangeSet.factory();
2383         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2384         while( rsItr.hasNext() ) {
2385           ReachState   state          = rsItr.next();
2386           ExistPredSet predsPreCallee = state.getPreds();
2387
2388           if( state.isEmpty() ) {
2389             continue;
2390           }
2391
2392           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2393           while( predItr.hasNext() ) {
2394             ExistPred pred = predItr.next();
2395             ReachState old = pred.ne_state;
2396
2397             if( old == null ) {
2398               old = rstateEmpty;
2399             }
2400
2401             cs = Canonical.add( cs,
2402                                 ChangeTuple.factory( old,
2403                                                      state
2404                                                      )
2405                                 );
2406           }
2407         }
2408
2409
2410         // look to see if an edge with same field exists
2411         // and merge with it, otherwise just add the edge
2412         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2413                                                          reCallee.getType(),
2414                                                          reCallee.getField()
2415                                                          );
2416         if( edgeExisting != null ) {
2417           edgeExisting.setBeta(
2418                                Canonical.unionORpreds( edgeExisting.getBeta(),
2419                                                 reCaller.getBeta()
2420                                                 )
2421                                );
2422           edgeExisting.setPreds(
2423                                 Canonical.join( edgeExisting.getPreds(),
2424                                                 reCaller.getPreds()
2425                                                 )
2426                                 );
2427
2428           // for reach propagation
2429           if( !cs.isEmpty() ) {
2430             edgePlannedChanges.put(
2431                                    edgeExisting,
2432                                    Canonical.union( edgePlannedChanges.get( edgeExisting ),
2433                                                     cs
2434                                                     )
2435                                     );
2436           }
2437
2438         } else {
2439           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2440
2441           // for reach propagation
2442           if( !cs.isEmpty() ) {
2443             edgesForPropagation.add( reCaller );
2444             assert !edgePlannedChanges.containsKey( reCaller );
2445             edgePlannedChanges.put( reCaller, cs );
2446           }
2447         }
2448       }
2449     }
2450
2451
2452
2453
2454
2455     if( writeDebugDOTs ) {
2456       try {
2457         writeGraph( "caller35BeforeAssignReturnValue",
2458                     resolveMethodDebugDOTwriteLabels,
2459                     resolveMethodDebugDOTselectTemps,
2460                     resolveMethodDebugDOTpruneGarbage,
2461                     resolveMethodDebugDOThideSubsetReach,
2462                     resolveMethodDebugDOThideEdgeTaints );
2463       } catch( IOException e ) {}
2464     }
2465
2466
2467
2468     // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2469     // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2470     // EDGES, JUST BRINGING THEM ALL!  It'll work for now, over approximation
2471
2472     // 3.d) handle return value assignment if needed
2473     TempDescriptor returnTemp = fc.getReturnTemp();
2474     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2475
2476       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2477       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2478
2479       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2480       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2481       while( reCalleeItr.hasNext() ) {
2482         RefEdge        reCallee     = reCalleeItr.next();
2483         HeapRegionNode hrnDstCallee = reCallee.getDst();
2484
2485         // some edge types are not possible return values when we can
2486         // see what type variable we are assigning it to
2487         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2488           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2489                               reCallee+" for return temp "+returnTemp );
2490           // prune
2491           continue;
2492         }
2493
2494         AllocSite asDst = hrnDstCallee.getAllocSite();
2495         allocSites.add( asDst );
2496
2497         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2498
2499         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2500         if( hrnDstCaller == null ) {
2501           hrnDstCaller =
2502             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
2503                                      hrnDstCallee.isSingleObject(), // single object?
2504                                      hrnDstCallee.isNewSummary(),   // summary?
2505                                      hrnDstCallee.isFlagged(),      // flagged?
2506                                      false,                         // out-of-context?
2507                                      hrnDstCallee.getType(),        // type
2508                                      hrnDstCallee.getAllocSite(),   // allocation site
2509                                      toCallerContext( hrnDstCallee.getInherent(),
2510                                                       calleeStatesSatisfied  ),    // inherent reach
2511                                      toCallerContext( hrnDstCallee.getAlpha(),
2512                                                       calleeStatesSatisfied  ),    // current reach
2513                                      predsTrue,                     // predicates
2514                                      hrnDstCallee.getDescription()  // description
2515                                      );
2516         }
2517
2518         TypeDescriptor tdNewEdge =
2519           mostSpecificType( reCallee.getType(),
2520                             hrnDstCallee.getType(),
2521                             hrnDstCaller.getType()
2522                             );
2523
2524         RefEdge reCaller = new RefEdge( vnLhsCaller,
2525                                         hrnDstCaller,
2526                                         tdNewEdge,
2527                                         null,
2528                                         toCallerContext( reCallee.getBeta(),
2529                                                          calleeStatesSatisfied ),
2530                                         predsTrue
2531                                         );
2532
2533         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2534       }
2535     }
2536
2537
2538
2539     if( writeDebugDOTs ) {
2540       try {
2541         writeGraph( "caller38propagateReach",
2542                     resolveMethodDebugDOTwriteLabels,
2543                     resolveMethodDebugDOTselectTemps,
2544                     resolveMethodDebugDOTpruneGarbage,
2545                     resolveMethodDebugDOThideSubsetReach,
2546                     resolveMethodDebugDOThideEdgeTaints );
2547       } catch( IOException e ) {}
2548     }
2549
2550     // propagate callee reachability changes to the rest
2551     // of the caller graph edges
2552     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2553
2554     propagateTokensOverEdges( edgesForPropagation, // source edges
2555                               edgePlannedChanges,  // map src edge to change set
2556                               edgesUpdated );      // list of updated edges
2557
2558     // commit beta' (beta<-betaNew)
2559     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2560     while( edgeItr.hasNext() ) {
2561       edgeItr.next().applyBetaNew();
2562     }
2563
2564
2565
2566
2567
2568
2569     if( writeDebugDOTs ) {
2570       try {
2571         writeGraph( "caller40BeforeShadowMerge",
2572                     resolveMethodDebugDOTwriteLabels,
2573                     resolveMethodDebugDOTselectTemps,
2574                     resolveMethodDebugDOTpruneGarbage,
2575                     resolveMethodDebugDOThideSubsetReach,
2576                     resolveMethodDebugDOThideEdgeTaints );
2577       } catch( IOException e ) {}
2578     }
2579
2580
2581     // 4) merge shadow nodes so alloc sites are back to k
2582     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2583     while( asItr.hasNext() ) {
2584       // for each allocation site do the following to merge
2585       // shadow nodes (newest from callee) with any existing
2586       // look for the newest normal and newest shadow "slot"
2587       // not being used, transfer normal to shadow.  Keep
2588       // doing this until there are no more normal nodes, or
2589       // no empty shadow slots: then merge all remaining normal
2590       // nodes into the shadow summary.  Finally, convert all
2591       // shadow to their normal versions.
2592       AllocSite as = asItr.next();
2593       int ageNorm = 0;
2594       int ageShad = 0;
2595       while( ageNorm < allocationDepth &&
2596              ageShad < allocationDepth ) {
2597
2598         // first, are there any normal nodes left?
2599         Integer        idNorm  = as.getIthOldest( ageNorm );
2600         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2601         if( hrnNorm == null ) {
2602           // no, this age of normal node not in the caller graph
2603           ageNorm++;
2604           continue;
2605         }
2606
2607         // yes, a normal node exists, is there an empty shadow
2608         // "slot" to transfer it onto?
2609         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2610         if( !hrnShad.isWiped() ) {
2611           // no, this age of shadow node is not empty
2612           ageShad++;
2613           continue;
2614         }
2615
2616         // yes, this shadow node is empty
2617         transferOnto( hrnNorm, hrnShad );
2618         ageNorm++;
2619         ageShad++;
2620       }
2621
2622       // now, while there are still normal nodes but no shadow
2623       // slots, merge normal nodes into the shadow summary
2624       while( ageNorm < allocationDepth ) {
2625
2626         // first, are there any normal nodes left?
2627         Integer        idNorm  = as.getIthOldest( ageNorm );
2628         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2629         if( hrnNorm == null ) {
2630           // no, this age of normal node not in the caller graph
2631           ageNorm++;
2632           continue;
2633         }
2634
2635         // yes, a normal node exists, so get the shadow summary
2636         HeapRegionNode summShad = getSummaryNode( as, true );
2637         mergeIntoSummary( hrnNorm, summShad );
2638         ageNorm++;
2639       }
2640
2641       // if there is a normal summary, merge it into shadow summary
2642       Integer        idNorm   = as.getSummary();
2643       HeapRegionNode summNorm = id2hrn.get( idNorm );
2644       if( summNorm != null ) {
2645         HeapRegionNode summShad = getSummaryNode( as, true );
2646         mergeIntoSummary( summNorm, summShad );
2647       }
2648
2649       // finally, flip all existing shadow nodes onto the normal
2650       for( int i = 0; i < allocationDepth; ++i ) {
2651         Integer        idShad  = as.getIthOldestShadow( i );
2652         HeapRegionNode hrnShad = id2hrn.get( idShad );
2653         if( hrnShad != null ) {
2654           // flip it
2655           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2656           assert hrnNorm.isWiped();
2657           transferOnto( hrnShad, hrnNorm );
2658         }
2659       }
2660
2661       Integer        idShad   = as.getSummaryShadow();
2662       HeapRegionNode summShad = id2hrn.get( idShad );
2663       if( summShad != null ) {
2664         summNorm = getSummaryNode( as, false );
2665         transferOnto( summShad, summNorm );
2666       }
2667     }
2668
2669
2670     if( writeDebugDOTs ) {
2671       try {
2672         writeGraph( "caller45BeforeUnshadow",
2673                     resolveMethodDebugDOTwriteLabels,
2674                     resolveMethodDebugDOTselectTemps,
2675                     resolveMethodDebugDOTpruneGarbage,
2676                     resolveMethodDebugDOThideSubsetReach,
2677                     resolveMethodDebugDOThideEdgeTaints );
2678       } catch( IOException e ) {}
2679     }
2680
2681
2682     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2683     while( itrAllHRNodes.hasNext() ) {
2684       Map.Entry      me  = (Map.Entry)      itrAllHRNodes.next();
2685       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2686
2687       hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2688
2689       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2690       while( itrEdges.hasNext() ) {
2691         RefEdge re = itrEdges.next();
2692         re.setBeta( unshadow( re.getBeta() ) );
2693       }
2694     }
2695
2696
2697
2698     if( writeDebugDOTs ) {
2699       try {
2700         writeGraph( "caller50BeforeGlobalSweep",
2701                     resolveMethodDebugDOTwriteLabels,
2702                     resolveMethodDebugDOTselectTemps,
2703                     resolveMethodDebugDOTpruneGarbage,
2704                     resolveMethodDebugDOThideSubsetReach,
2705                     resolveMethodDebugDOThideEdgeTaints );
2706       } catch( IOException e ) {}
2707     }
2708
2709
2710     // 5.
2711     if( !DISABLE_GLOBAL_SWEEP ) {
2712       globalSweep();
2713     }
2714
2715
2716
2717     if( writeDebugDOTs ) {
2718       try {
2719         writeGraph( "caller90AfterTransfer",
2720                     resolveMethodDebugDOTwriteLabels,
2721                     resolveMethodDebugDOTselectTemps,
2722                     resolveMethodDebugDOTpruneGarbage,
2723                     resolveMethodDebugDOThideSubsetReach,
2724                     resolveMethodDebugDOThideEdgeTaints );
2725       } catch( IOException e ) {}
2726     }
2727   }
2728
2729
2730
2731   ////////////////////////////////////////////////////
2732   //
2733   //  Abstract garbage collection simply removes
2734   //  heap region nodes that are not mechanically
2735   //  reachable from a root set.  This step is
2736   //  essential for testing node and edge existence
2737   //  predicates efficiently
2738   //
2739   ////////////////////////////////////////////////////
2740   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2741
2742     // calculate a root set, will be different for Java
2743     // version of analysis versus Bamboo version
2744     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2745
2746     // visit every variable in graph while building root
2747     // set, and do iterating on a copy, so we can remove
2748     // dead variables while we're at this
2749     Iterator makeCopyItr = td2vn.entrySet().iterator();
2750     Set      entrysCopy  = new HashSet();
2751     while( makeCopyItr.hasNext() ) {
2752       entrysCopy.add( makeCopyItr.next() );
2753     }
2754
2755     Iterator eItr = entrysCopy.iterator();
2756     while( eItr.hasNext() ) {
2757       Map.Entry      me = (Map.Entry)      eItr.next();
2758       TempDescriptor td = (TempDescriptor) me.getKey();
2759       VariableNode   vn = (VariableNode)   me.getValue();
2760
2761       if( liveSet.contains( td ) ) {
2762         toVisit.add( vn );
2763
2764       } else {
2765         // dead var, remove completely from graph
2766         td2vn.remove( td );
2767         clearRefEdgesFrom( vn, null, null, true );
2768       }
2769     }
2770
2771     // everything visited in a traversal is
2772     // considered abstractly live
2773     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2774
2775     while( !toVisit.isEmpty() ) {
2776       RefSrcNode rsn = toVisit.iterator().next();
2777       toVisit.remove( rsn );
2778       visited.add( rsn );
2779
2780       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2781       while( hrnItr.hasNext() ) {
2782         RefEdge        edge = hrnItr.next();
2783         HeapRegionNode hrn  = edge.getDst();
2784
2785         if( !visited.contains( hrn ) ) {
2786           toVisit.add( hrn );
2787         }
2788       }
2789     }
2790
2791     // get a copy of the set to iterate over because
2792     // we're going to monkey with the graph when we
2793     // identify a garbage node
2794     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2795     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2796     while( hrnItr.hasNext() ) {
2797       hrnAllPrior.add( hrnItr.next() );
2798     }
2799
2800     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2801     while( hrnAllItr.hasNext() ) {
2802       HeapRegionNode hrn = hrnAllItr.next();
2803
2804       if( !visited.contains( hrn ) ) {
2805
2806         // heap region nodes are compared across ReachGraph
2807         // objects by their integer ID, so when discarding
2808         // garbage nodes we must also discard entries in
2809         // the ID -> heap region hashtable.
2810         id2hrn.remove( hrn.getID() );
2811
2812         // RefEdge objects are two-way linked between
2813         // nodes, so when a node is identified as garbage,
2814         // actively clear references to and from it so
2815         // live nodes won't have dangling RefEdge's
2816         wipeOut( hrn, true );
2817
2818         // if we just removed the last node from an allocation
2819         // site, it should be taken out of the ReachGraph's list
2820         AllocSite as = hrn.getAllocSite();
2821         if( !hasNodesOf( as ) ) {
2822           allocSites.remove( as );
2823         }
2824       }
2825     }
2826   }
2827
2828   protected boolean hasNodesOf( AllocSite as ) {
2829     if( id2hrn.containsKey( as.getSummary() ) ) {
2830       return true;
2831     }
2832
2833     for( int i = 0; i < allocationDepth; ++i ) {
2834       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2835         return true;
2836       }
2837     }
2838     return false;
2839   }
2840
2841
2842   ////////////////////////////////////////////////////
2843   //
2844   //  This global sweep is an optional step to prune
2845   //  reachability sets that are not internally
2846   //  consistent with the global graph.  It should be
2847   //  invoked after strong updates or method calls.
2848   //
2849   ////////////////////////////////////////////////////
2850   public void globalSweep() {
2851
2852     // boldB is part of the phase 1 sweep
2853     // it has an in-context table and an out-of-context table
2854     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2855       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2856
2857     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2858       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2859
2860     // visit every heap region to initialize alphaNew and betaNew,
2861     // and make a map of every hrnID to the source nodes it should
2862     // propagate forward from.  In-context flagged hrnID's propagate
2863     // from only the in-context node they name, but out-of-context
2864     // ID's may propagate from several out-of-context nodes
2865     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2866       new Hashtable< Integer, Set<HeapRegionNode> >();
2867
2868     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2869       new Hashtable< Integer, Set<HeapRegionNode> >();
2870
2871
2872     Iterator itrHrns = id2hrn.entrySet().iterator();
2873     while( itrHrns.hasNext() ) {
2874       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2875       Integer        hrnID = (Integer)        me.getKey();
2876       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2877
2878       // assert that this node and incoming edges have clean alphaNew
2879       // and betaNew sets, respectively
2880       assert rsetEmpty.equals( hrn.getAlphaNew() );
2881
2882       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2883       while( itrRers.hasNext() ) {
2884         RefEdge edge = itrRers.next();
2885         assert rsetEmpty.equals( edge.getBetaNew() );
2886       }
2887
2888       // calculate boldB for this flagged node, or out-of-context node
2889       if( hrn.isFlagged() ) {
2890         assert !hrn.isOutOfContext();
2891         assert !icID2srcs.containsKey( hrn.getID() );
2892         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2893         srcs.add( hrn );
2894         icID2srcs.put( hrn.getID(), srcs );
2895       }
2896
2897       if( hrn.isOutOfContext() ) {
2898         assert !hrn.isFlagged();
2899
2900         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2901         while( stateItr.hasNext() ) {
2902           ReachState state = stateItr.next();
2903
2904           Iterator<ReachTuple> rtItr = state.iterator();
2905           while( rtItr.hasNext() ) {
2906             ReachTuple rt = rtItr.next();
2907             assert rt.isOutOfContext();
2908
2909             Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2910             if( srcs == null ) {
2911               srcs = new HashSet<HeapRegionNode>();
2912             }
2913             srcs.add( hrn );
2914             oocID2srcs.put( rt.getHrnID(), srcs );
2915           }
2916         }
2917       }
2918     }
2919
2920     // calculate boldB for all hrnIDs identified by the above
2921     // node traversal, propagating from every source
2922     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2923
2924       Integer             hrnID;
2925       Set<HeapRegionNode> srcs;
2926       boolean             inContext;
2927
2928       if( !icID2srcs.isEmpty() ) {
2929         Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2930         hrnID = (Integer)             me.getKey();
2931         srcs  = (Set<HeapRegionNode>) me.getValue();
2932         inContext = true;
2933         icID2srcs.remove( hrnID );
2934
2935       } else {
2936         assert !oocID2srcs.isEmpty();
2937
2938         Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2939         hrnID = (Integer)             me.getKey();
2940         srcs  = (Set<HeapRegionNode>) me.getValue();
2941         inContext = false;
2942         oocID2srcs.remove( hrnID );
2943       }
2944
2945
2946       Hashtable<RefEdge, ReachSet> boldB_f =
2947         new Hashtable<RefEdge, ReachSet>();
2948
2949       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2950
2951       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2952       while( hrnItr.hasNext() ) {
2953         HeapRegionNode hrn = hrnItr.next();
2954
2955         assert workSetEdges.isEmpty();
2956
2957         // initial boldB_f constraints
2958         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2959         while( itrRees.hasNext() ) {
2960           RefEdge edge = itrRees.next();
2961
2962           assert !boldB_f.containsKey( edge );
2963           boldB_f.put( edge, edge.getBeta() );
2964
2965           assert !workSetEdges.contains( edge );
2966           workSetEdges.add( edge );
2967         }
2968
2969         // enforce the boldB_f constraint at edges until we reach a fixed point
2970         while( !workSetEdges.isEmpty() ) {
2971           RefEdge edge = workSetEdges.iterator().next();
2972           workSetEdges.remove( edge );
2973
2974           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2975           while( itrPrime.hasNext() ) {
2976             RefEdge edgePrime = itrPrime.next();
2977
2978             ReachSet prevResult   = boldB_f.get( edgePrime );
2979             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2980                                                             edgePrime.getBeta()
2981                                                             );
2982
2983             if( prevResult == null ||
2984                 Canonical.unionORpreds( prevResult,
2985                                         intersection ).size()
2986                 > prevResult.size()
2987                 ) {
2988
2989               if( prevResult == null ) {
2990                 boldB_f.put( edgePrime,
2991                              Canonical.unionORpreds( edgePrime.getBeta(),
2992                                                      intersection
2993                                                      )
2994                              );
2995               } else {
2996                 boldB_f.put( edgePrime,
2997                              Canonical.unionORpreds( prevResult,
2998                                                      intersection
2999                                                      )
3000                              );
3001               }
3002               workSetEdges.add( edgePrime );
3003             }
3004           }
3005         }
3006       }
3007
3008       if( inContext ) {
3009         boldBic.put( hrnID, boldB_f );
3010       } else {
3011         boldBooc.put( hrnID, boldB_f );
3012       }
3013     }
3014
3015
3016     // use boldB to prune hrnIDs from alpha states that are impossible
3017     // and propagate the differences backwards across edges
3018     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3019
3020     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3021       new Hashtable<RefEdge, ChangeSet>();
3022
3023
3024     itrHrns = id2hrn.entrySet().iterator();
3025     while( itrHrns.hasNext() ) {
3026       Map.Entry      me    = (Map.Entry)      itrHrns.next();
3027       Integer        hrnID = (Integer)        me.getKey();
3028       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3029
3030       // out-of-context nodes don't participate in the
3031       // global sweep, they serve as sources for the pass
3032       // performed above
3033       if( hrn.isOutOfContext() ) {
3034         continue;
3035       }
3036
3037       // the inherent states of a region are the exception
3038       // to removal as the global sweep prunes
3039       ReachTuple rtException = ReachTuple.factory( hrnID,
3040                                                    !hrn.isSingleObject(),
3041                                                    ReachTuple.ARITY_ONE,
3042                                                    false // out-of-context
3043                                                    );
3044
3045       ChangeSet cts = ChangeSet.factory();
3046
3047       // mark hrnIDs for removal
3048       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3049       while( stateItr.hasNext() ) {
3050         ReachState stateOld = stateItr.next();
3051
3052         ReachState markedHrnIDs = ReachState.factory();
3053
3054         Iterator<ReachTuple> rtItr = stateOld.iterator();
3055         while( rtItr.hasNext() ) {
3056           ReachTuple rtOld = rtItr.next();
3057
3058           // never remove the inherent hrnID from a flagged region
3059           // because it is trivially satisfied
3060           if( hrn.isFlagged() ) {
3061             if( rtOld == rtException ) {
3062               continue;
3063             }
3064           }
3065
3066           // does boldB allow this hrnID?
3067           boolean foundState = false;
3068           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3069           while( incidentEdgeItr.hasNext() ) {
3070             RefEdge incidentEdge = incidentEdgeItr.next();
3071
3072             Hashtable<RefEdge, ReachSet> B;
3073             if( rtOld.isOutOfContext() ) {
3074               B = boldBooc.get( rtOld.getHrnID() );
3075             } else {
3076               assert id2hrn.containsKey( rtOld.getHrnID() );
3077               B = boldBic.get( rtOld.getHrnID() );
3078             }
3079
3080             if( B != null ) {
3081               ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3082               if( boldB_rtOld_incident != null &&
3083                   boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3084                   ) {
3085                 foundState = true;
3086               }
3087             }
3088           }
3089
3090           if( !foundState ) {
3091             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3092           }
3093         }
3094
3095         // if there is nothing marked, just move on
3096         if( markedHrnIDs.isEmpty() ) {
3097           hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3098                                           stateOld
3099                                           )
3100                            );
3101           continue;
3102         }
3103
3104         // remove all marked hrnIDs and establish a change set that should
3105         // propagate backwards over edges from this node
3106         ReachState statePruned = ReachState.factory();
3107         rtItr = stateOld.iterator();
3108         while( rtItr.hasNext() ) {
3109           ReachTuple rtOld = rtItr.next();
3110
3111           if( !markedHrnIDs.containsTuple( rtOld ) ) {
3112             statePruned = Canonical.add( statePruned, rtOld );
3113           }
3114         }
3115         assert !stateOld.equals( statePruned );
3116
3117         hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3118                                         statePruned
3119                                         )
3120                          );
3121         ChangeTuple ct = ChangeTuple.factory( stateOld,
3122                                               statePruned
3123                                               );
3124         cts = Canonical.add( cts, ct );
3125       }
3126
3127       // throw change tuple set on all incident edges
3128       if( !cts.isEmpty() ) {
3129         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3130         while( incidentEdgeItr.hasNext() ) {
3131           RefEdge incidentEdge = incidentEdgeItr.next();
3132
3133           edgesForPropagation.add( incidentEdge );
3134
3135           if( edgePlannedChanges.get( incidentEdge ) == null ) {
3136             edgePlannedChanges.put( incidentEdge, cts );
3137           } else {
3138             edgePlannedChanges.put(
3139                                    incidentEdge,
3140                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
3141                                                     cts
3142                                                     )
3143                                     );
3144           }
3145         }
3146       }
3147     }
3148
3149     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3150
3151     propagateTokensOverEdges( edgesForPropagation,
3152                               edgePlannedChanges,
3153                               edgesUpdated );
3154
3155     // at the end of the 1st phase reference edges have
3156     // beta, betaNew that correspond to beta and betaR
3157     //
3158     // commit beta<-betaNew, so beta=betaR and betaNew
3159     // will represent the beta' calculation in 2nd phase
3160     //
3161     // commit alpha<-alphaNew because it won't change
3162     HashSet<RefEdge> res = new HashSet<RefEdge>();
3163
3164     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3165     while( nodeItr.hasNext() ) {
3166       HeapRegionNode hrn = nodeItr.next();
3167
3168       // as mentioned above, out-of-context nodes only serve
3169       // as sources of reach states for the sweep, not part
3170       // of the changes
3171       if( hrn.isOutOfContext() ) {
3172         assert hrn.getAlphaNew().equals( rsetEmpty );
3173       } else {
3174         hrn.applyAlphaNew();
3175       }
3176
3177       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3178       while( itrRes.hasNext() ) {
3179         res.add( itrRes.next() );
3180       }
3181     }
3182
3183
3184     // 2nd phase
3185     Iterator<RefEdge> edgeItr = res.iterator();
3186     while( edgeItr.hasNext() ) {
3187       RefEdge        edge = edgeItr.next();
3188       HeapRegionNode hrn  = edge.getDst();
3189
3190       // commit results of last phase
3191       if( edgesUpdated.contains( edge ) ) {
3192         edge.applyBetaNew();
3193       }
3194
3195       // compute intial condition of 2nd phase
3196       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3197                                                hrn.getAlpha()
3198                                                )
3199                        );
3200     }
3201
3202     // every edge in the graph is the initial workset
3203     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3204     while( !edgeWorkSet.isEmpty() ) {
3205       RefEdge edgePrime = edgeWorkSet.iterator().next();
3206       edgeWorkSet.remove( edgePrime );
3207
3208       RefSrcNode rsn = edgePrime.getSrc();
3209       if( !(rsn instanceof HeapRegionNode) ) {
3210         continue;
3211       }
3212       HeapRegionNode hrn = (HeapRegionNode) rsn;
3213
3214       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3215       while( itrEdge.hasNext() ) {
3216         RefEdge edge = itrEdge.next();
3217
3218         ReachSet prevResult = edge.getBetaNew();
3219         assert prevResult != null;
3220
3221         ReachSet intersection =
3222           Canonical.intersection( edge.getBeta(),
3223                                   edgePrime.getBetaNew()
3224                                   );
3225
3226         if( Canonical.unionORpreds( prevResult,
3227                                     intersection
3228                                     ).size()
3229             > prevResult.size()
3230             ) {
3231
3232           edge.setBetaNew(
3233                           Canonical.unionORpreds( prevResult,
3234                                                   intersection
3235                                                   )
3236                            );
3237           edgeWorkSet.add( edge );
3238         }
3239       }
3240     }
3241
3242     // commit beta' (beta<-betaNew)
3243     edgeItr = res.iterator();
3244     while( edgeItr.hasNext() ) {
3245       edgeItr.next().applyBetaNew();
3246     }
3247   }
3248
3249
3250
3251   ////////////////////////////////////////////////////
3252   // high-level merge operations
3253   ////////////////////////////////////////////////////
3254   public void merge_sameMethodContext( ReachGraph rg ) {
3255     // when merging two graphs that abstract the heap
3256     // of the same method context, we just call the
3257     // basic merge operation
3258     merge( rg );
3259   }
3260
3261   public void merge_diffMethodContext( ReachGraph rg ) {
3262     // when merging graphs for abstract heaps in
3263     // different method contexts we should:
3264     // 1) age the allocation sites?
3265     merge( rg );
3266   }
3267
3268   ////////////////////////////////////////////////////
3269   // in merge() and equals() methods the suffix A
3270   // represents the passed in graph and the suffix
3271   // B refers to the graph in this object
3272   // Merging means to take the incoming graph A and
3273   // merge it into B, so after the operation graph B
3274   // is the final result.
3275   ////////////////////////////////////////////////////
3276   protected void merge( ReachGraph rg ) {
3277
3278     if( rg == null ) {
3279       return;
3280     }
3281
3282     mergeNodes     ( rg );
3283     mergeRefEdges  ( rg );
3284     mergeAllocSites( rg );
3285   }
3286
3287   protected void mergeNodes( ReachGraph rg ) {
3288
3289     // start with heap region nodes
3290     Set      sA = rg.id2hrn.entrySet();
3291     Iterator iA = sA.iterator();
3292     while( iA.hasNext() ) {
3293       Map.Entry      meA  = (Map.Entry)      iA.next();
3294       Integer        idA  = (Integer)        meA.getKey();
3295       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3296
3297       // if this graph doesn't have a node the
3298       // incoming graph has, allocate it
3299       if( !id2hrn.containsKey( idA ) ) {
3300         HeapRegionNode hrnB = hrnA.copy();
3301         id2hrn.put( idA, hrnB );
3302
3303       } else {
3304         // otherwise this is a node present in both graphs
3305         // so make the new reachability set a union of the
3306         // nodes' reachability sets
3307         HeapRegionNode hrnB = id2hrn.get( idA );
3308         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3309                                         hrnA.getAlpha()
3310                                         )
3311                        );
3312
3313         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3314                                        hrnA.getPreds()
3315                                        )
3316                        );
3317       }
3318     }
3319
3320     // now add any variable nodes that are in graph B but
3321     // not in A
3322     sA = rg.td2vn.entrySet();
3323     iA = sA.iterator();
3324     while( iA.hasNext() ) {
3325       Map.Entry      meA = (Map.Entry)      iA.next();
3326       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3327       VariableNode   lnA = (VariableNode)   meA.getValue();
3328
3329       // if the variable doesn't exist in B, allocate and add it
3330       VariableNode lnB = getVariableNodeFromTemp( tdA );
3331     }
3332   }
3333
3334   protected void mergeRefEdges( ReachGraph rg ) {
3335
3336     // between heap regions
3337     Set      sA = rg.id2hrn.entrySet();
3338     Iterator iA = sA.iterator();
3339     while( iA.hasNext() ) {
3340       Map.Entry      meA  = (Map.Entry)      iA.next();
3341       Integer        idA  = (Integer)        meA.getKey();
3342       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3343
3344       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3345       while( heapRegionsItrA.hasNext() ) {
3346         RefEdge        edgeA     = heapRegionsItrA.next();
3347         HeapRegionNode hrnChildA = edgeA.getDst();
3348         Integer        idChildA  = hrnChildA.getID();
3349
3350         // at this point we know an edge in graph A exists
3351         // idA -> idChildA, does this exist in B?
3352         assert id2hrn.containsKey( idA );
3353         HeapRegionNode hrnB        = id2hrn.get( idA );
3354         RefEdge        edgeToMerge = null;
3355
3356         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3357         while( heapRegionsItrB.hasNext() &&
3358                edgeToMerge == null          ) {
3359
3360           RefEdge        edgeB     = heapRegionsItrB.next();
3361           HeapRegionNode hrnChildB = edgeB.getDst();
3362           Integer        idChildB  = hrnChildB.getID();
3363
3364           // don't use the RefEdge.equals() here because
3365           // we're talking about existence between graphs,
3366           // not intragraph equal
3367           if( idChildB.equals( idChildA ) &&
3368               edgeB.typeAndFieldEquals( edgeA ) ) {
3369
3370             edgeToMerge = edgeB;
3371           }
3372         }
3373
3374         // if the edge from A was not found in B,
3375         // add it to B.
3376         if( edgeToMerge == null ) {
3377           assert id2hrn.containsKey( idChildA );
3378           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3379           edgeToMerge = edgeA.copy();
3380           edgeToMerge.setSrc( hrnB );
3381           edgeToMerge.setDst( hrnChildB );
3382           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3383         }
3384         // otherwise, the edge already existed in both graphs
3385         // so merge their reachability sets
3386         else {
3387           // just replace this beta set with the union
3388           assert edgeToMerge != null;
3389           edgeToMerge.setBeta(
3390                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3391                                                edgeA.getBeta()
3392                                                )
3393                               );
3394           edgeToMerge.setPreds(
3395                                Canonical.join( edgeToMerge.getPreds(),
3396                                                edgeA.getPreds()
3397                                                )
3398                                );
3399         }
3400       }
3401     }
3402
3403     // and then again from variable nodes
3404     sA = rg.td2vn.entrySet();
3405     iA = sA.iterator();
3406     while( iA.hasNext() ) {
3407       Map.Entry      meA = (Map.Entry)      iA.next();
3408       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3409       VariableNode   vnA = (VariableNode)   meA.getValue();
3410
3411       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3412       while( heapRegionsItrA.hasNext() ) {
3413         RefEdge        edgeA     = heapRegionsItrA.next();
3414         HeapRegionNode hrnChildA = edgeA.getDst();
3415         Integer        idChildA  = hrnChildA.getID();
3416
3417         // at this point we know an edge in graph A exists
3418         // tdA -> idChildA, does this exist in B?
3419         assert td2vn.containsKey( tdA );
3420         VariableNode vnB         = td2vn.get( tdA );
3421         RefEdge      edgeToMerge = null;
3422
3423         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3424         while( heapRegionsItrB.hasNext() &&
3425                edgeToMerge == null          ) {
3426
3427           RefEdge        edgeB     = heapRegionsItrB.next();
3428           HeapRegionNode hrnChildB = edgeB.getDst();
3429           Integer        idChildB  = hrnChildB.getID();
3430
3431           // don't use the RefEdge.equals() here because
3432           // we're talking about existence between graphs
3433           if( idChildB.equals( idChildA ) &&
3434               edgeB.typeAndFieldEquals( edgeA ) ) {
3435
3436             edgeToMerge = edgeB;
3437           }
3438         }
3439
3440         // if the edge from A was not found in B,
3441         // add it to B.
3442         if( edgeToMerge == null ) {
3443           assert id2hrn.containsKey( idChildA );
3444           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3445           edgeToMerge = edgeA.copy();
3446           edgeToMerge.setSrc( vnB );
3447           edgeToMerge.setDst( hrnChildB );
3448           addRefEdge( vnB, hrnChildB, edgeToMerge );
3449         }
3450         // otherwise, the edge already existed in both graphs
3451         // so merge their reachability sets
3452         else {
3453           // just replace this beta set with the union
3454           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3455                                                 edgeA.getBeta()
3456                                                 )
3457                                );
3458           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3459                                                 edgeA.getPreds()
3460                                                 )
3461                                 );
3462         }
3463       }
3464     }
3465   }
3466
3467   protected void mergeAllocSites( ReachGraph rg ) {
3468     allocSites.addAll( rg.allocSites );
3469   }
3470
3471
3472   // it is necessary in the equals() member functions
3473   // to "check both ways" when comparing the data
3474   // structures of two graphs.  For instance, if all
3475   // edges between heap region nodes in graph A are
3476   // present and equal in graph B it is not sufficient
3477   // to say the graphs are equal.  Consider that there
3478   // may be edges in graph B that are not in graph A.
3479   // the only way to know that all edges in both graphs
3480   // are equally present is to iterate over both data
3481   // structures and compare against the other graph.
3482   public boolean equals( ReachGraph rg ) {
3483
3484     if( rg == null ) {
3485       return false;
3486     }
3487
3488     if( !areHeapRegionNodesEqual( rg ) ) {
3489       return false;
3490     }
3491
3492     if( !areVariableNodesEqual( rg ) ) {
3493       return false;
3494     }
3495
3496     if( !areRefEdgesEqual( rg ) ) {
3497       return false;
3498     }
3499
3500     // if everything is equal up to this point,
3501     // assert that allocSites is also equal--
3502     // this data is redundant but kept for efficiency
3503     assert allocSites.equals( rg.allocSites );
3504
3505     return true;
3506   }
3507
3508
3509   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3510
3511     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3512       return false;
3513     }
3514
3515     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3516       return false;
3517     }
3518
3519     return true;
3520   }
3521
3522   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3523                                                         ReachGraph rgB ) {
3524     Set      sA = rgA.id2hrn.entrySet();
3525     Iterator iA = sA.iterator();
3526     while( iA.hasNext() ) {
3527       Map.Entry      meA  = (Map.Entry)      iA.next();
3528       Integer        idA  = (Integer)        meA.getKey();
3529       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3530
3531       if( !rgB.id2hrn.containsKey( idA ) ) {
3532         return false;
3533       }
3534
3535       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3536       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3537         return false;
3538       }
3539     }
3540
3541     return true;
3542   }
3543
3544
3545   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3546
3547     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3548       return false;
3549     }
3550
3551     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3552       return false;
3553     }
3554
3555     return true;
3556   }
3557
3558   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3559                                                        ReachGraph rgB ) {
3560     Set      sA = rgA.td2vn.entrySet();
3561     Iterator iA = sA.iterator();
3562     while( iA.hasNext() ) {
3563       Map.Entry      meA = (Map.Entry)      iA.next();
3564       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3565
3566       if( !rgB.td2vn.containsKey( tdA ) ) {
3567         return false;
3568       }
3569     }
3570
3571     return true;
3572   }
3573
3574
3575   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3576     if( !areallREinAandBequal( this, rg ) ) {
3577       return false;
3578     }
3579
3580     return true;
3581   }
3582
3583   static protected boolean areallREinAandBequal( ReachGraph rgA,
3584                                                  ReachGraph rgB ) {
3585
3586     // check all the heap region->heap region edges
3587     Set      sA = rgA.id2hrn.entrySet();
3588     Iterator iA = sA.iterator();
3589     while( iA.hasNext() ) {
3590       Map.Entry      meA  = (Map.Entry)      iA.next();
3591       Integer        idA  = (Integer)        meA.getKey();
3592       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3593
3594       // we should have already checked that the same
3595       // heap regions exist in both graphs
3596       assert rgB.id2hrn.containsKey( idA );
3597
3598       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3599         return false;
3600       }
3601
3602       // then check every edge in B for presence in A, starting
3603       // from the same parent HeapRegionNode
3604       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3605
3606       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3607         return false;
3608       }
3609     }
3610
3611     // then check all the variable->heap region edges
3612     sA = rgA.td2vn.entrySet();
3613     iA = sA.iterator();
3614     while( iA.hasNext() ) {
3615       Map.Entry      meA = (Map.Entry)      iA.next();
3616       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3617       VariableNode   vnA = (VariableNode)   meA.getValue();
3618
3619       // we should have already checked that the same
3620       // label nodes exist in both graphs
3621       assert rgB.td2vn.containsKey( tdA );
3622
3623       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3624         return false;
3625       }
3626
3627       // then check every edge in B for presence in A, starting
3628       // from the same parent VariableNode
3629       VariableNode vnB = rgB.td2vn.get( tdA );
3630
3631       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3632         return false;
3633       }
3634     }
3635
3636     return true;
3637   }
3638
3639
3640   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3641                                                   RefSrcNode rnA,
3642                                                   ReachGraph rgB ) {
3643
3644     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3645     while( itrA.hasNext() ) {
3646       RefEdge        edgeA     = itrA.next();
3647       HeapRegionNode hrnChildA = edgeA.getDst();
3648       Integer        idChildA  = hrnChildA.getID();
3649
3650       assert rgB.id2hrn.containsKey( idChildA );
3651
3652       // at this point we know an edge in graph A exists
3653       // rnA -> idChildA, does this exact edge exist in B?
3654       boolean edgeFound = false;
3655
3656       RefSrcNode rnB = null;
3657       if( rnA instanceof HeapRegionNode ) {
3658         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3659         rnB = rgB.id2hrn.get( hrnA.getID() );
3660       } else {
3661         VariableNode vnA = (VariableNode) rnA;
3662         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3663       }
3664
3665       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3666       while( itrB.hasNext() ) {
3667         RefEdge        edgeB     = itrB.next();
3668         HeapRegionNode hrnChildB = edgeB.getDst();
3669         Integer        idChildB  = hrnChildB.getID();
3670
3671         if( idChildA.equals( idChildB ) &&
3672             edgeA.typeAndFieldEquals( edgeB ) ) {
3673
3674           // there is an edge in the right place with the right field,
3675           // but do they have the same attributes?
3676           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3677               edgeA.equalsPreds( edgeB )
3678               ) {
3679             edgeFound = true;
3680           }
3681         }
3682       }
3683
3684       if( !edgeFound ) {
3685         return false;
3686       }
3687     }
3688
3689     return true;
3690   }
3691
3692
3693
3694   // this analysis no longer has the "match anything"
3695   // type which was represented by null
3696   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3697                                              TypeDescriptor td2 ) {
3698     assert td1 != null;
3699     assert td2 != null;
3700
3701     if( td1.isNull() ) {
3702       return td2;
3703     }
3704     if( td2.isNull() ) {
3705       return td1;
3706     }
3707     return typeUtil.mostSpecific( td1, td2 );
3708   }
3709
3710   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3711                                              TypeDescriptor td2,
3712                                              TypeDescriptor td3 ) {
3713
3714     return mostSpecificType( td1,
3715                              mostSpecificType( td2, td3 )
3716                              );
3717   }
3718
3719   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3720                                              TypeDescriptor td2,
3721                                              TypeDescriptor td3,
3722                                              TypeDescriptor td4 ) {
3723
3724     return mostSpecificType( mostSpecificType( td1, td2 ),
3725                              mostSpecificType( td3, td4 )
3726                              );
3727   }
3728
3729   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3730                                     TypeDescriptor possibleChild ) {
3731     assert possibleSuper != null;
3732     assert possibleChild != null;
3733
3734     if( possibleSuper.isNull() ||
3735         possibleChild.isNull() ) {
3736       return true;
3737     }
3738
3739     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3740   }
3741
3742
3743   protected boolean hasMatchingField( HeapRegionNode src,
3744                                       RefEdge        edge ) {
3745
3746     TypeDescriptor tdSrc = src.getType();
3747     assert tdSrc != null;
3748
3749     if( tdSrc.isArray() ) {
3750       TypeDescriptor td = edge.getType();
3751       assert td != null;
3752
3753       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3754       assert tdSrcDeref != null;
3755
3756       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3757         return false;
3758       }
3759
3760       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3761     }
3762
3763     // if it's not a class, it doesn't have any fields to match
3764     if( !tdSrc.isClass() ) {
3765       return false;
3766     }
3767
3768     ClassDescriptor cd = tdSrc.getClassDesc();
3769     while( cd != null ) {
3770       Iterator fieldItr = cd.getFields();
3771
3772       while( fieldItr.hasNext() ) {
3773         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3774
3775         if( fd.getType().equals( edge.getType() ) &&
3776             fd.getSymbol().equals( edge.getField() ) ) {
3777           return true;
3778         }
3779       }
3780
3781       cd = cd.getSuperDesc();
3782     }
3783
3784     // otherwise it is a class with fields
3785     // but we didn't find a match
3786     return false;
3787   }
3788
3789   protected boolean hasMatchingType( RefEdge        edge,
3790                                      HeapRegionNode dst  ) {
3791
3792     // if the region has no type, matches everything
3793     TypeDescriptor tdDst = dst.getType();
3794     assert tdDst != null;
3795
3796     // if the type is not a class or an array, don't
3797     // match because primitives are copied, no aliases
3798     ClassDescriptor cdDst = tdDst.getClassDesc();
3799     if( cdDst == null && !tdDst.isArray() ) {
3800       return false;
3801     }
3802
3803     // if the edge type is null, it matches everything
3804     TypeDescriptor tdEdge = edge.getType();
3805     assert tdEdge != null;
3806
3807     return typeUtil.isSuperorType( tdEdge, tdDst );
3808   }
3809
3810
3811
3812   public void writeGraph( String  graphName,
3813                           boolean writeLabels,
3814                           boolean labelSelect,
3815                           boolean pruneGarbage,
3816                           boolean hideSubsetReachability,
3817                           boolean hideEdgeTaints
3818                           ) throws java.io.IOException {
3819     writeGraph( graphName,
3820                 writeLabels,
3821                 labelSelect,
3822                 pruneGarbage,
3823                 hideSubsetReachability,
3824                 hideEdgeTaints,
3825                 null );
3826   }
3827
3828   public void writeGraph( String       graphName,
3829                           boolean      writeLabels,
3830                           boolean      labelSelect,
3831                           boolean      pruneGarbage,
3832                           boolean      hideSubsetReachability,
3833                           boolean      hideEdgeTaints,
3834                           Set<Integer> callerNodeIDsCopiedToCallee
3835                           ) throws java.io.IOException {
3836
3837     // remove all non-word characters from the graph name so
3838     // the filename and identifier in dot don't cause errors
3839     graphName = graphName.replaceAll( "[\\W]", "" );
3840
3841     BufferedWriter bw =
3842       new BufferedWriter( new FileWriter( graphName+".dot" ) );
3843
3844     bw.write( "digraph "+graphName+" {\n" );
3845
3846
3847     // this is an optional step to form the callee-reachable
3848     // "cut-out" into a DOT cluster for visualization
3849     if( callerNodeIDsCopiedToCallee != null ) {
3850
3851       bw.write( "  subgraph cluster0 {\n" );
3852       bw.write( "    color=blue;\n" );
3853
3854       Iterator i = id2hrn.entrySet().iterator();
3855       while( i.hasNext() ) {
3856         Map.Entry      me  = (Map.Entry)      i.next();
3857         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3858
3859         if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3860           bw.write( "    "+hrn.toString()+
3861                     hrn.toStringDOT( hideSubsetReachability )+
3862                     ";\n" );
3863
3864         }
3865       }
3866
3867       bw.write( "  }\n" );
3868     }
3869
3870
3871     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3872
3873     // then visit every heap region node
3874     Iterator i = id2hrn.entrySet().iterator();
3875     while( i.hasNext() ) {
3876       Map.Entry      me  = (Map.Entry)      i.next();
3877       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3878
3879       // only visit nodes worth writing out--for instance
3880       // not every node at an allocation is referenced
3881       // (think of it as garbage-collected), etc.
3882       if( !pruneGarbage        ||
3883           hrn.isOutOfContext()
3884           ) {
3885
3886         if( !visited.contains( hrn ) ) {
3887           traverseHeapRegionNodes( hrn,
3888                                    bw,
3889                                    null,
3890                                    visited,
3891                                    hideSubsetReachability,
3892                                    hideEdgeTaints,
3893                                    callerNodeIDsCopiedToCallee );
3894         }
3895       }
3896     }
3897
3898     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
3899
3900
3901     // then visit every label node, useful for debugging
3902     if( writeLabels ) {
3903       i = td2vn.entrySet().iterator();
3904       while( i.hasNext() ) {
3905         Map.Entry    me = (Map.Entry)    i.next();
3906         VariableNode vn = (VariableNode) me.getValue();
3907
3908         if( labelSelect ) {
3909           String labelStr = vn.getTempDescriptorString();
3910           if( labelStr.startsWith( "___temp" )     ||
3911               labelStr.startsWith( "___dst" )      ||
3912               labelStr.startsWith( "___srctmp" )   ||
3913               labelStr.startsWith( "___neverused" )
3914               ) {
3915             continue;
3916           }
3917         }
3918
3919         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3920         while( heapRegionsItr.hasNext() ) {
3921           RefEdge        edge = heapRegionsItr.next();
3922           HeapRegionNode hrn  = edge.getDst();
3923
3924           if( !visited.contains( hrn ) ) {
3925             traverseHeapRegionNodes( hrn,
3926                                      bw,
3927                                      null,
3928                                      visited,
3929                                      hideSubsetReachability,
3930                                      hideEdgeTaints,
3931                                      callerNodeIDsCopiedToCallee );
3932           }
3933
3934           bw.write( "  "+vn.toString()+
3935                     " -> "+hrn.toString()+
3936                     edge.toStringDOT( hideSubsetReachability, "" )+
3937                     ";\n" );
3938         }
3939       }
3940     }
3941
3942     bw.write( "}\n" );
3943     bw.close();
3944   }
3945
3946   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
3947                                           BufferedWriter      bw,
3948                                           TempDescriptor      td,
3949                                           Set<HeapRegionNode> visited,
3950                                           boolean             hideSubsetReachability,
3951                                           boolean             hideEdgeTaints,
3952                                           Set<Integer>        callerNodeIDsCopiedToCallee
3953                                           ) throws java.io.IOException {
3954
3955     if( visited.contains( hrn ) ) {
3956       return;
3957     }
3958     visited.add( hrn );
3959
3960     // if we're drawing the callee-view subgraph, only
3961     // write out the node info if it hasn't already been
3962     // written
3963     if( callerNodeIDsCopiedToCallee == null ||
3964         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3965         ) {
3966       bw.write( "  "+hrn.toString()+
3967                 hrn.toStringDOT( hideSubsetReachability )+
3968                 ";\n" );
3969     }
3970
3971     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3972     while( childRegionsItr.hasNext() ) {
3973       RefEdge        edge     = childRegionsItr.next();
3974       HeapRegionNode hrnChild = edge.getDst();
3975
3976       if( callerNodeIDsCopiedToCallee != null &&
3977           (edge.getSrc() instanceof HeapRegionNode) ) {
3978         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3979         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
3980             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3981             ) {
3982           bw.write( "  "+hrn.toString()+
3983                     " -> "+hrnChild.toString()+
3984                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3985                     ";\n");
3986         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
3987                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3988                    ) {
3989           bw.write( "  "+hrn.toString()+
3990                     " -> "+hrnChild.toString()+
3991                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3992                     ";\n");
3993         } else {
3994           bw.write( "  "+hrn.toString()+
3995                     " -> "+hrnChild.toString()+
3996                     edge.toStringDOT( hideSubsetReachability, "" )+
3997                     ";\n");
3998         }
3999       } else {
4000         bw.write( "  "+hrn.toString()+
4001                   " -> "+hrnChild.toString()+
4002                   edge.toStringDOT( hideSubsetReachability, "" )+
4003                   ";\n");
4004       }
4005
4006       traverseHeapRegionNodes( hrnChild,
4007                                bw,
4008                                td,
4009                                visited,
4010                                hideSubsetReachability,
4011                                hideEdgeTaints,
4012                                callerNodeIDsCopiedToCallee );
4013     }
4014   }
4015
4016         public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
4017                         HeapRegionNode hrn2) {
4018
4019                 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4020                 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4021
4022                 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4023                 todoNodes1.add(hrn1);
4024
4025                 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4026                 todoNodes2.add(hrn2);
4027
4028                 // follow links until all reachable nodes have been found
4029                 while (!todoNodes1.isEmpty()) {
4030                         HeapRegionNode hrn = todoNodes1.iterator().next();
4031                         todoNodes1.remove(hrn);
4032                         reachableNodes1.add(hrn);
4033
4034                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4035                         while (edgeItr.hasNext()) {
4036                                 RefEdge edge = edgeItr.next();
4037
4038                                 if (!reachableNodes1.contains(edge.getDst())) {
4039                                         todoNodes1.add(edge.getDst());
4040                                 }
4041                         }
4042                 }
4043
4044                 while (!todoNodes2.isEmpty()) {
4045                         HeapRegionNode hrn = todoNodes2.iterator().next();
4046                         todoNodes2.remove(hrn);
4047                         reachableNodes2.add(hrn);
4048
4049                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4050                         while (edgeItr.hasNext()) {
4051                                 RefEdge edge = edgeItr.next();
4052
4053                                 if (!reachableNodes2.contains(edge.getDst())) {
4054                                         todoNodes2.add(edge.getDst());
4055                                 }
4056                         }
4057                 }
4058
4059                 Set<HeapRegionNode> intersection =
4060                   new HashSet<HeapRegionNode>( reachableNodes1 );
4061
4062                 intersection.retainAll( reachableNodes2 );
4063
4064                 return intersection;
4065         }
4066
4067         public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4068                         HeapRegionNode hrn2) {
4069                 assert hrn1 != null;
4070                 assert hrn2 != null;
4071
4072                 // then get the various tokens for these heap regions
4073                 ReachTuple h1 = ReachTuple.factory(hrn1.getID(),
4074                                 !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false);
4075
4076                 int arity;
4077                 if(hrn1.isSingleObject){
4078                         arity=ReachTuple.ARITY_ONE;
4079                 }else{
4080                         arity=ReachTuple.ARITY_ZEROORMORE;
4081                 }
4082                 ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1
4083                                 .isSingleObject(), arity, false);
4084
4085                 ReachTuple h2 = ReachTuple.factory(hrn2.getID(),
4086                                 !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false);
4087
4088                 if(hrn2.isSingleObject){
4089                         arity=ReachTuple.ARITY_ONE;
4090                 }else{
4091                         arity=ReachTuple.ARITY_ZEROORMORE;
4092                 }
4093
4094                 ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2
4095                                 .isSingleObject(), arity, false);
4096
4097                 // then get the merged beta of all out-going edges from these heap
4098                 // regions
4099
4100                 ReachSet beta1 = ReachSet.factory();
4101                 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4102                 while (itrEdge.hasNext()) {
4103                         RefEdge edge = itrEdge.next();
4104                         beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4105                 }
4106
4107                 ReachSet beta2 = ReachSet.factory();
4108                 itrEdge = hrn2.iteratorToReferencees();
4109                 while (itrEdge.hasNext()) {
4110                         RefEdge edge = itrEdge.next();
4111                         beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4112                 }
4113
4114                 boolean aliasDetected = false;
4115
4116                 // only do this one if they are different tokens
4117                 if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) {
4118                         aliasDetected = true;
4119                 }
4120 //              if (beta1.containsStateWithBoth(h1plus, h2)) {
4121 //                      aliasDetected = true;
4122 //              }
4123                 if (beta1.containsStateWithBoth(h1star, h2)) {
4124                         aliasDetected = true;
4125                 }
4126 //              if (beta1.containsStateWithBoth(h1, h2plus)) {
4127 //                      aliasDetected = true;
4128 //              }
4129 //              if (beta1.containsStateWithBoth(h1plus, h2plus)) {
4130 //                      aliasDetected = true;
4131 //              }
4132 //              if (beta1.containsStateWithBoth(h1star, h2plus)) {
4133 //                      aliasDetected = true;
4134 //              }
4135                 if (beta1.containsStateWithBoth(h1, h2star)) {
4136                         aliasDetected = true;
4137                 }
4138 //              if (beta1.containsStateWithBoth(h1plus, h2star)) {
4139 //                      aliasDetected = true;
4140 //              }
4141                 if (beta1.containsStateWithBoth(h1star, h2star)) {
4142                         aliasDetected = true;
4143                 }
4144
4145                 if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) {
4146                         aliasDetected = true;
4147                 }
4148 //              if (beta2.containsStateWithBoth(h1plus, h2)) {
4149 //                      aliasDetected = true;
4150 //              }
4151                 if (beta2.containsStateWithBoth(h1star, h2)) {
4152                         aliasDetected = true;
4153                 }
4154 //              if (beta2.containsStateWithBoth(h1, h2plus)) {
4155 //                      aliasDetected = true;
4156 //              }
4157 //              if (beta2.containsStateWithBoth(h1plus, h2plus)) {
4158 //                      aliasDetected = true;
4159 //              }
4160 //              if (beta2.containsStateWithBoth(h1star, h2plus)) {
4161 //                      aliasDetected = true;
4162 //              }
4163                 if (beta2.containsStateWithBoth(h1, h2star)) {
4164                         aliasDetected = true;
4165                 }
4166 //              if (beta2.containsStateWithBoth(h1plus, h2star)) {
4167 //                      aliasDetected = true;
4168 //              }
4169                 if (beta2.containsStateWithBoth(h1star, h2star)) {
4170                         aliasDetected = true;
4171                 }
4172
4173                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4174                 if (aliasDetected) {
4175                         common = findCommonReachableNodes(hrn1, hrn2);
4176                         if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) {
4177                                 assert !common.isEmpty();
4178                         }
4179                 }
4180
4181                 return common;
4182         }
4183
4184         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4185                         Integer paramIndex1, Integer paramIndex2) {
4186
4187                 // get parameter's heap regions
4188                 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4189                 VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1);
4190                 RefEdge argEdge1 = argVar1.iteratorToReferencees().next();
4191                 HeapRegionNode hrnParam1 = argEdge1.getDst();
4192
4193                 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4194                 VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2);
4195                 RefEdge argEdge2 = argVar2.iteratorToReferencees().next();
4196                 HeapRegionNode hrnParam2 = argEdge2.getDst();
4197
4198                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4199                 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4200
4201                 return common;
4202         }
4203
4204         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4205                         Integer paramIndex, AllocSite as) {
4206
4207                 // get parameter's heap regions
4208                 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4209                 VariableNode argVar = getVariableNodeFromTemp(paramTemp);
4210                 RefEdge argEdge = argVar.iteratorToReferencees().next();
4211                 HeapRegionNode hrnParam = argEdge.getDst();
4212
4213                 // get summary node
4214                 HeapRegionNode hrnSummary=null;
4215                 if(id2hrn.containsKey(as.getSummary())){
4216                         // if summary node doesn't exist, ignore this case
4217                         hrnSummary = id2hrn.get(as.getSummary());
4218                         assert hrnSummary != null;
4219                 }
4220
4221                 Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
4222                 if(hrnSummary!=null){
4223                         common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4224                 }
4225
4226                 // check for other nodes
4227                 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4228
4229                         assert id2hrn.containsKey(as.getIthOldest(i));
4230                         HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4231                         assert hrnIthOldest != null;
4232
4233                         common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4234
4235                 }
4236
4237                 return common;
4238         }
4239
4240         public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4241                         AllocSite as2) {
4242
4243                 // get summary node 1's alpha
4244                 Integer idSum1 = as1.getSummary();
4245                 HeapRegionNode hrnSum1=null;
4246                 if(id2hrn.containsKey(idSum1)){
4247                         hrnSum1 = id2hrn.get(idSum1);
4248                 }
4249
4250                 // get summary node 2's alpha
4251                 Integer idSum2 = as2.getSummary();
4252                 HeapRegionNode hrnSum2=null;
4253                 if(id2hrn.containsKey(idSum2)){
4254                         hrnSum2 = id2hrn.get(idSum2);
4255                 }
4256
4257                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4258                 if(hrnSum1!=null && hrnSum2!=null){
4259                         common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4260                 }
4261
4262                 // check sum2 against alloc1 nodes
4263                 if(hrnSum2!=null){
4264                 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4265                         Integer idI1 = as1.getIthOldest(i);
4266                         assert id2hrn.containsKey(idI1);
4267                         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4268                         assert hrnI1 != null;
4269                         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4270                 }
4271                 }
4272
4273                 // check sum1 against alloc2 nodes
4274                 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4275                         Integer idI2 = as2.getIthOldest(i);
4276                         assert id2hrn.containsKey(idI2);
4277                         HeapRegionNode hrnI2 = id2hrn.get(idI2);
4278                         assert hrnI2 != null;
4279
4280                         if(hrnSum1!=null){
4281                                 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4282                         }
4283
4284                         // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4285                         for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4286                                 Integer idI1 = as1.getIthOldest(j);
4287
4288                                 // if these are the same site, don't look for the same token, no
4289                                 // alias.
4290                                 // different tokens of the same site could alias together though
4291                                 if (idI1.equals(idI2)) {
4292                                         continue;
4293                                 }
4294
4295                                 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4296
4297                                 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4298                         }
4299                 }
4300
4301                 return common;
4302         }
4303
4304 }