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
 796       hrnSummary =
 797         createNewHeapRegionNode( idSummary,    // id or null to generate a new one
 798                                  false,        // single object?
 799                                  true,         // summary?
 800                                  hasFlags,     // flagged?
 801                                  false,        // out-of-context?
 802                                  as.getType(), // type
 803                                  as,           // allocation site
 804                                  null,         // inherent reach
 805                                  null,         // current reach
 806                                  predsEmpty,   // predicates
 807                                  strDesc       // description
 808                                  );
 809     }
 810
 811     return hrnSummary;
 812   }
 813
 814   // either retrieve or create the needed heap region node
 815   protected HeapRegionNode getIthNode( AllocSite as,
 816                                        Integer   i,
 817                                        boolean   shadow ) {
 818
 819     Integer idIth;
 820     if( shadow ) {
 821       idIth = as.getIthOldestShadow( i );
 822     } else {
 823       idIth = as.getIthOldest( i );
 824     }
 825
 826     HeapRegionNode hrnIth = id2hrn.get( idIth );
 827
 828     if( hrnIth == null ) {
 829
 830       boolean hasFlags = false;
 831       if( as.getType().isClass() ) {
 832         hasFlags = as.getType().getClassDesc().hasFlags();
 833       }
 834
 835       if( as.getFlag() ){
 836         hasFlags = as.getFlag();
 837       }
 838
 839       String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
 840
 841       hrnIth = createNewHeapRegionNode( idIth,        // id or null to generate a new one
 842                                         true,         // single object?
 843                                         false,        // summary?
 844                                         hasFlags,     // flagged?
 845                                         false,        // out-of-context?
 846                                         as.getType(), // type
 847                                         as,           // allocation site
 848                                         null,         // inherent reach
 849                                         null,         // current reach
 850                                         predsEmpty,   // predicates
 851                                         strDesc       // description
 852                                         );
 853     }
 854
 855     return hrnIth;
 856   }
 857
 858
 859   protected void mergeIntoSummary( HeapRegionNode hrn,
 860                                    HeapRegionNode hrnSummary ) {
 861     assert hrnSummary.isNewSummary();
 862
 863     // assert that these nodes belong to THIS graph
 864     assert belongsToThis( hrn );
 865     assert belongsToThis( hrnSummary );
 866
 867     assert hrn != hrnSummary;
 868
 869     // transfer references _from_ hrn over to hrnSummary
 870     Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
 871     while( itrReferencee.hasNext() ) {
 872       RefEdge edge       = itrReferencee.next();
 873       RefEdge edgeMerged = edge.copy();
 874       edgeMerged.setSrc( hrnSummary );
 875
 876       HeapRegionNode hrnReferencee = edge.getDst();
 877       RefEdge        edgeSummary   =
 878         hrnSummary.getReferenceTo( hrnReferencee,
 879                                    edge.getType(),
 880                                    edge.getField()
 881                                    );
 882
 883       if( edgeSummary == null ) {
 884         // the merge is trivial, nothing to be done
 885         addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
 886
 887       } else {
 888         // otherwise an edge from the referencer to hrnSummary exists already
 889         // and the edge referencer->hrn should be merged with it
 890         edgeSummary.setBeta(
 891                             Canonical.unionORpreds( edgeMerged.getBeta(),
 892                                              edgeSummary.getBeta()
 893                                              )
 894                              );
 895         edgeSummary.setPreds(
 896                              Canonical.join( edgeMerged.getPreds(),
 897                                              edgeSummary.getPreds()
 898                                              )
 899                               );
 900       }
 901     }
 902
 903     // next transfer references _to_ hrn over to hrnSummary
 904     Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
 905     while( itrReferencer.hasNext() ) {
 906       RefEdge edge         = itrReferencer.next();
 907       RefEdge edgeMerged   = edge.copy();
 908       edgeMerged.setDst( hrnSummary );
 909
 910       RefSrcNode onReferencer = edge.getSrc();
 911       RefEdge    edgeSummary  =
 912         onReferencer.getReferenceTo( hrnSummary,
 913                                      edge.getType(),
 914                                      edge.getField()
 915                                      );
 916
 917       if( edgeSummary == null ) {
 918         // the merge is trivial, nothing to be done
 919         addRefEdge( onReferencer, hrnSummary, edgeMerged );
 920
 921       } else {
 922         // otherwise an edge from the referencer to alpha_S exists already
 923         // and the edge referencer->alpha_K should be merged with it
 924         edgeSummary.setBeta(
 925                             Canonical.unionORpreds( edgeMerged.getBeta(),
 926                                              edgeSummary.getBeta()
 927                                              )
 928                              );
 929         edgeSummary.setPreds(
 930                              Canonical.join( edgeMerged.getPreds(),
 931                                              edgeSummary.getPreds()
 932                                              )
 933                               );
 934       }
 935     }
 936
 937     // then merge hrn reachability into hrnSummary
 938     hrnSummary.setAlpha(
 939                         Canonical.unionORpreds( hrnSummary.getAlpha(),
 940                                          hrn.getAlpha()
 941                                          )
 942                          );
 943
 944     hrnSummary.setPreds(
 945                         Canonical.join( hrnSummary.getPreds(),
 946                                         hrn.getPreds()
 947                                         )
 948                         );
 949
 950     // and afterward, this node is gone
 951     wipeOut( hrn, true );
 952   }
 953
 954
 955   protected void transferOnto( HeapRegionNode hrnA,
 956                                HeapRegionNode hrnB ) {
 957
 958     assert belongsToThis( hrnA );
 959     assert belongsToThis( hrnB );
 960     assert hrnA != hrnB;
 961
 962     // clear references in and out of node b?
 963     assert hrnB.isWiped();
 964
 965     // copy each: (edge in and out of A) to B
 966     Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
 967     while( itrReferencee.hasNext() ) {
 968       RefEdge        edge          = itrReferencee.next();
 969       HeapRegionNode hrnReferencee = edge.getDst();
 970       RefEdge        edgeNew       = edge.copy();
 971       edgeNew.setSrc( hrnB );
 972       edgeNew.setDst( hrnReferencee );
 973
 974       addRefEdge( hrnB, hrnReferencee, edgeNew );
 975     }
 976
 977     Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
 978     while( itrReferencer.hasNext() ) {
 979       RefEdge    edge          = itrReferencer.next();
 980       RefSrcNode rsnReferencer = edge.getSrc();
 981       RefEdge    edgeNew       = edge.copy();
 982       edgeNew.setSrc( rsnReferencer );
 983       edgeNew.setDst( hrnB );
 984
 985       addRefEdge( rsnReferencer, hrnB, edgeNew );
 986     }
 987
 988     // replace hrnB reachability and preds with hrnA's
 989     hrnB.setAlpha( hrnA.getAlpha() );
 990     hrnB.setPreds( hrnA.getPreds() );
 991
 992     // after transfer, wipe out source
 993     wipeOut( hrnA, true );
 994   }
 995
 996
 997   // the purpose of this method is to conceptually "wipe out"
 998   // a heap region from the graph--purposefully not called REMOVE
 999   // because the node is still hanging around in the graph, just
1000   // not mechanically connected or have any reach or predicate
1001   // information on it anymore--lots of ops can use this
1002   protected void wipeOut( HeapRegionNode hrn,
1003                           boolean        wipeVariableReferences ) {
1004
1005     assert belongsToThis( hrn );
1006
1007     clearRefEdgesFrom( hrn, null, null, true );
1008
1009     if( wipeVariableReferences ) {
1010       clearRefEdgesTo( hrn, null, null, true );
1011     } else {
1012       clearNonVarRefEdgesTo( hrn );
1013     }
1014
1015     hrn.setAlpha( rsetEmpty );
1016     hrn.setPreds( predsEmpty );
1017   }
1018
1019
1020   protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1021     edge.setBeta(
1022                  Canonical.ageTuplesFrom( edge.getBeta(),
1023                                           as
1024                                           )
1025                   );
1026   }
1027
1028   protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1029     hrn.setAlpha(
1030                  Canonical.ageTuplesFrom( hrn.getAlpha(),
1031                                           as
1032                                           )
1033                   );
1034   }
1035
1036
1037
1038   protected void propagateTokensOverNodes( HeapRegionNode          nPrime,
1039                                            ChangeSet               c0,
1040                                            HashSet<HeapRegionNode> nodesWithNewAlpha,
1041                                            HashSet<RefEdge>        edgesWithNewBeta ) {
1042
1043     HashSet<HeapRegionNode> todoNodes
1044       = new HashSet<HeapRegionNode>();
1045     todoNodes.add( nPrime );
1046
1047     HashSet<RefEdge> todoEdges
1048       = new HashSet<RefEdge>();
1049
1050     Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1051       = new Hashtable<HeapRegionNode, ChangeSet>();
1052     nodePlannedChanges.put( nPrime, c0 );
1053
1054     Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1055       = new Hashtable<RefEdge, ChangeSet>();
1056
1057     // first propagate change sets everywhere they can go
1058     while( !todoNodes.isEmpty() ) {
1059       HeapRegionNode n = todoNodes.iterator().next();
1060       ChangeSet      C = nodePlannedChanges.get( n );
1061
1062       Iterator<RefEdge> referItr = n.iteratorToReferencers();
1063       while( referItr.hasNext() ) {
1064         RefEdge edge = referItr.next();
1065         todoEdges.add( edge );
1066
1067         if( !edgePlannedChanges.containsKey( edge ) ) {
1068           edgePlannedChanges.put( edge,
1069                                   ChangeSet.factory()
1070                                   );
1071         }
1072
1073         edgePlannedChanges.put( edge,
1074                                 Canonical.union( edgePlannedChanges.get( edge ),
1075                                                  C
1076                                                  )
1077                                 );
1078       }
1079
1080       Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1081       while( refeeItr.hasNext() ) {
1082         RefEdge        edgeF = refeeItr.next();
1083         HeapRegionNode m     = edgeF.getDst();
1084
1085         ChangeSet changesToPass = ChangeSet.factory();
1086
1087         Iterator<ChangeTuple> itrCprime = C.iterator();
1088         while( itrCprime.hasNext() ) {
1089           ChangeTuple c = itrCprime.next();
1090           if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
1091               != null
1092               ) {
1093             changesToPass = Canonical.add( changesToPass, c );
1094           }
1095         }
1096
1097         if( !changesToPass.isEmpty() ) {
1098           if( !nodePlannedChanges.containsKey( m ) ) {
1099             nodePlannedChanges.put( m, ChangeSet.factory() );
1100           }
1101
1102           ChangeSet currentChanges = nodePlannedChanges.get( m );
1103
1104           if( !changesToPass.isSubset( currentChanges ) ) {
1105
1106             nodePlannedChanges.put( m,
1107                                     Canonical.union( currentChanges,
1108                                                      changesToPass
1109                                                      )
1110                                     );
1111             todoNodes.add( m );
1112           }
1113         }
1114       }
1115
1116       todoNodes.remove( n );
1117     }
1118
1119     // then apply all of the changes for each node at once
1120     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1121     while( itrMap.hasNext() ) {
1122       Map.Entry      me = (Map.Entry)      itrMap.next();
1123       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1124       ChangeSet      C  = (ChangeSet)      me.getValue();
1125
1126       // this propagation step is with respect to one change,
1127       // so we capture the full change from the old alpha:
1128       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1129                                                       C,
1130                                                       true
1131                                                       );
1132       // but this propagation may be only one of many concurrent
1133       // possible changes, so keep a running union with the node's
1134       // partially updated new alpha set
1135       n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1136                                       localDelta
1137                                       )
1138                      );
1139
1140       nodesWithNewAlpha.add( n );
1141     }
1142
1143     propagateTokensOverEdges( todoEdges,
1144                               edgePlannedChanges,
1145                               edgesWithNewBeta
1146                               );
1147   }
1148
1149
1150   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1151                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1152                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1153
1154     // first propagate all change tuples everywhere they can go
1155     while( !todoEdges.isEmpty() ) {
1156       RefEdge edgeE = todoEdges.iterator().next();
1157       todoEdges.remove( edgeE );
1158
1159       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1160         edgePlannedChanges.put( edgeE,
1161                                 ChangeSet.factory()
1162                                 );
1163       }
1164
1165       ChangeSet C = edgePlannedChanges.get( edgeE );
1166
1167       ChangeSet changesToPass = ChangeSet.factory();
1168
1169       Iterator<ChangeTuple> itrC = C.iterator();
1170       while( itrC.hasNext() ) {
1171         ChangeTuple c = itrC.next();
1172         if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1173             != null
1174             ) {
1175           changesToPass = Canonical.add( changesToPass, c );
1176         }
1177       }
1178
1179       RefSrcNode rsn = edgeE.getSrc();
1180
1181       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1182         HeapRegionNode n = (HeapRegionNode) rsn;
1183
1184         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1185         while( referItr.hasNext() ) {
1186           RefEdge edgeF = referItr.next();
1187
1188           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1189             edgePlannedChanges.put( edgeF,
1190                                     ChangeSet.factory()
1191                                     );
1192           }
1193
1194           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1195
1196           if( !changesToPass.isSubset( currentChanges ) ) {
1197             todoEdges.add( edgeF );
1198             edgePlannedChanges.put( edgeF,
1199                                     Canonical.union( currentChanges,
1200                                                      changesToPass
1201                                                      )
1202                                     );
1203           }
1204         }
1205       }
1206     }
1207
1208     // then apply all of the changes for each edge at once
1209     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1210     while( itrMap.hasNext() ) {
1211       Map.Entry me = (Map.Entry) itrMap.next();
1212       RefEdge   e  = (RefEdge)   me.getKey();
1213       ChangeSet C  = (ChangeSet) me.getValue();
1214
1215       // this propagation step is with respect to one change,
1216       // so we capture the full change from the old beta:
1217       ReachSet localDelta =
1218         Canonical.applyChangeSet( e.getBeta(),
1219                                   C,
1220                                   true
1221                                   );
1222
1223       // but this propagation may be only one of many concurrent
1224       // possible changes, so keep a running union with the edge's
1225       // partially updated new beta set
1226       e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1227                                      localDelta
1228                                      )
1229                     );
1230
1231       edgesWithNewBeta.add( e );
1232     }
1233   }
1234
1235
1236   // used in makeCalleeView below to decide if there is
1237   // already an appropriate out-of-context edge in a callee
1238   // view graph for merging, or null if a new one will be added
1239   protected RefEdge
1240     getOutOfContextReferenceTo( HeapRegionNode hrn,
1241                                 TypeDescriptor srcType,
1242                                 TypeDescriptor refType,
1243                                 String         refField ) {
1244     assert belongsToThis( hrn );
1245
1246     HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1247     if( hrnInContext == null ) {
1248       return null;
1249     }
1250
1251     Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1252     while( refItr.hasNext() ) {
1253       RefEdge re = refItr.next();
1254
1255       assert belongsToThis( re.getSrc() );
1256       assert belongsToThis( re.getDst() );
1257
1258       if( !(re.getSrc() instanceof HeapRegionNode) ) {
1259         continue;
1260       }
1261
1262       HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1263       if( !hrnSrc.isOutOfContext() ) {
1264         continue;
1265       }
1266
1267       if( srcType == null ) {
1268         if( hrnSrc.getType() != null ) {
1269           continue;
1270         }
1271       } else {
1272         if( !srcType.equals( hrnSrc.getType() ) ) {
1273           continue;
1274         }
1275       }
1276
1277       if( !re.typeEquals( refType ) ) {
1278         continue;
1279       }
1280
1281       if( !re.fieldEquals( refField ) ) {
1282         continue;
1283       }
1284
1285       // tada!  We found it!
1286       return re;
1287     }
1288
1289     return null;
1290   }
1291
1292   // used below to convert a ReachSet to its callee-context
1293   // equivalent with respect to allocation sites in this graph
1294   protected ReachSet toCalleeContext( ReachSet      rs,
1295                                       ExistPredSet  preds,
1296                                       Set<HrnIdOoc> oocHrnIdOoc2callee
1297                                       ) {
1298     ReachSet out = ReachSet.factory();
1299
1300     Iterator<ReachState> itr = rs.iterator();
1301     while( itr.hasNext() ) {
1302       ReachState stateCaller = itr.next();
1303
1304       ReachState stateCallee = stateCaller;
1305
1306       Iterator<AllocSite> asItr = allocSites.iterator();
1307       while( asItr.hasNext() ) {
1308         AllocSite as = asItr.next();
1309
1310         ReachState stateNew = ReachState.factory();
1311         Iterator<ReachTuple> rtItr = stateCallee.iterator();
1312         while( rtItr.hasNext() ) {
1313           ReachTuple rt = rtItr.next();
1314
1315           // only translate this tuple if it is
1316           // in the out-callee-context bag
1317           HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(),
1318                                        rt.isOutOfContext()
1319                                        );
1320           if( !oocHrnIdOoc2callee.contains( hio ) ) {
1321             stateNew = Canonical.add( stateNew, rt );
1322             continue;
1323           }
1324
1325           int age = as.getAgeCategory( rt.getHrnID() );
1326
1327           // this is the current mapping, where 0, 1, 2S were allocated
1328           // in the current context, 0?, 1? and 2S? were allocated in a
1329           // previous context, and we're translating to a future context
1330           //
1331           // 0    -> 0?
1332           // 1    -> 1?
1333           // 2S   -> 2S?
1334           // 2S*  -> 2S?*
1335           //
1336           // 0?   -> 2S?
1337           // 1?   -> 2S?
1338           // 2S?  -> 2S?
1339           // 2S?* -> 2S?*
1340
1341           if( age == AllocSite.AGE_notInThisSite ) {
1342             // things not from the site just go back in
1343             stateNew = Canonical.add( stateNew, rt );
1344
1345           } else if( age == AllocSite.AGE_summary ||
1346                      rt.isOutOfContext()
1347                      ) {
1348             // the in-context summary and all existing out-of-context
1349             // stuff all become
1350             stateNew = Canonical.add( stateNew,
1351                                       ReachTuple.factory( as.getSummary(),
1352                                                           true, // multi
1353                                                           rt.getArity(),
1354                                                           true  // out-of-context
1355                                                           )
1356                                       );
1357           } else {
1358             // otherwise everything else just goes to an out-of-context
1359             // version, everything else the same
1360             Integer I = as.getAge( rt.getHrnID() );
1361             assert I != null;
1362
1363             assert !rt.isMultiObject();
1364
1365             stateNew = Canonical.add( stateNew,
1366                                       ReachTuple.factory( rt.getHrnID(),
1367                                                           rt.isMultiObject(),
1368                                                           rt.getArity(),
1369                                                           true  // out-of-context
1370                                                           )
1371                                       );
1372           }
1373         }
1374
1375         stateCallee = stateNew;
1376       }
1377
1378       // attach the passed in preds
1379       stateCallee = Canonical.attach( stateCallee,
1380                                       preds );
1381
1382       out = Canonical.add( out,
1383                            stateCallee
1384                            );
1385
1386     }
1387     assert out.isCanonical();
1388     return out;
1389   }
1390
1391   // used below to convert a ReachSet to its caller-context
1392   // equivalent with respect to allocation sites in this graph
1393   protected ReachSet
1394     toCallerContext( ReachSet                            rs,
1395                      Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1396                      ) {
1397     ReachSet out = ReachSet.factory();
1398
1399     Iterator<ReachState> itr = rs.iterator();
1400     while( itr.hasNext() ) {
1401       ReachState stateCallee = itr.next();
1402
1403       if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1404
1405         // starting from one callee state...
1406         ReachSet rsCaller = ReachSet.factory( stateCallee );
1407
1408         // possibly branch it into many states, which any
1409         // allocation site might do, so lots of derived states
1410         Iterator<AllocSite> asItr = allocSites.iterator();
1411         while( asItr.hasNext() ) {
1412           AllocSite as = asItr.next();
1413           rsCaller = Canonical.toCallerContext( rsCaller, as );
1414         }
1415
1416         // then before adding each derived, now caller-context
1417         // states to the output, attach the appropriate pred
1418         // based on the source callee state
1419         Iterator<ReachState> stateItr = rsCaller.iterator();
1420         while( stateItr.hasNext() ) {
1421           ReachState stateCaller = stateItr.next();
1422           stateCaller = Canonical.attach( stateCaller,
1423                                           calleeStatesSatisfied.get( stateCallee )
1424                                           );
1425           out = Canonical.add( out,
1426                                stateCaller
1427                                );
1428         }
1429       }
1430     }
1431
1432     assert out.isCanonical();
1433     return out;
1434   }
1435
1436   // used below to convert a ReachSet to an equivalent
1437   // version with shadow IDs merged into unshadowed IDs
1438   protected ReachSet unshadow( ReachSet rs ) {
1439     ReachSet out = rs;
1440     Iterator<AllocSite> asItr = allocSites.iterator();
1441     while( asItr.hasNext() ) {
1442       AllocSite as = asItr.next();
1443       out = Canonical.unshadow( out, as );
1444     }
1445     assert out.isCanonical();
1446     return out;
1447   }
1448
1449
1450   // use this method to make a new reach graph that is
1451   // what heap the FlatMethod callee from the FlatCall
1452   // would start with reaching from its arguments in
1453   // this reach graph
1454   public ReachGraph
1455     makeCalleeView( FlatCall     fc,
1456                     FlatMethod   fmCallee,
1457                     Set<Integer> callerNodeIDsCopiedToCallee,
1458                     boolean      writeDebugDOTs
1459                     ) {
1460
1461
1462     // first traverse this context to find nodes and edges
1463     //  that will be callee-reachable
1464     Set<HeapRegionNode> reachableCallerNodes =
1465       new HashSet<HeapRegionNode>();
1466
1467     // caller edges between callee-reachable nodes
1468     Set<RefEdge> reachableCallerEdges =
1469       new HashSet<RefEdge>();
1470
1471     // caller edges from arg vars, and the matching param index
1472     // because these become a special edge in callee
1473     Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1474       new Hashtable<RefEdge, Integer>();
1475
1476     // caller edges from local vars or callee-unreachable nodes
1477     // (out-of-context sources) to callee-reachable nodes
1478     Set<RefEdge> oocCallerEdges =
1479       new HashSet<RefEdge>();
1480
1481
1482     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1483
1484       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1485       VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1486
1487       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1488       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1489
1490       toVisitInCaller.add( vnArgCaller );
1491
1492       while( !toVisitInCaller.isEmpty() ) {
1493         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1494         toVisitInCaller.remove( rsnCaller );
1495         visitedInCaller.add( rsnCaller );
1496
1497         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1498         while( itrRefEdges.hasNext() ) {
1499           RefEdge        reCaller  = itrRefEdges.next();
1500           HeapRegionNode hrnCaller = reCaller.getDst();
1501
1502           callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1503           reachableCallerNodes.add( hrnCaller );
1504
1505           if( reCaller.getSrc() instanceof HeapRegionNode ) {
1506             reachableCallerEdges.add( reCaller );
1507           } else {
1508             if( rsnCaller.equals( vnArgCaller ) ) {
1509               reachableCallerArgEdges2paramIndex.put( reCaller, i );
1510             } else {
1511               oocCallerEdges.add( reCaller );
1512             }
1513           }
1514
1515           if( !visitedInCaller.contains( hrnCaller ) ) {
1516             toVisitInCaller.add( hrnCaller );
1517           }
1518
1519         } // end edge iteration
1520       } // end visiting heap nodes in caller
1521     } // end iterating over parameters as starting points
1522
1523
1524     // now collect out-of-callee-context IDs and
1525     // map them to whether the ID is out of the caller
1526     // context as well
1527     Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1528
1529     Iterator<Integer> itrInContext =
1530       callerNodeIDsCopiedToCallee.iterator();
1531     while( itrInContext.hasNext() ) {
1532       Integer        hrnID                 = itrInContext.next();
1533       HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1534
1535       Iterator<RefEdge> itrMightCross =
1536         hrnCallerAndInContext.iteratorToReferencers();
1537       while( itrMightCross.hasNext() ) {
1538         RefEdge edgeMightCross = itrMightCross.next();
1539
1540         RefSrcNode rsnCallerAndOutContext =
1541           edgeMightCross.getSrc();
1542
1543         if( rsnCallerAndOutContext instanceof VariableNode ) {
1544           // variables do not have out-of-context reach states,
1545           // so jump out now
1546           oocCallerEdges.add( edgeMightCross );
1547           continue;
1548         }
1549
1550         HeapRegionNode hrnCallerAndOutContext =
1551           (HeapRegionNode) rsnCallerAndOutContext;
1552
1553         // is this source node out-of-context?
1554         if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1555           // no, skip this edge
1556           continue;
1557         }
1558
1559         // okay, we got one
1560         oocCallerEdges.add( edgeMightCross );
1561
1562         // add all reach tuples on the node to list
1563         // of things that are out-of-context: insight
1564         // if this node is reachable from someting that WAS
1565         // in-context, then this node should already be in-context
1566         Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1567         while( stateItr.hasNext() ) {
1568           ReachState state = stateItr.next();
1569
1570           Iterator<ReachTuple> rtItr = state.iterator();
1571           while( rtItr.hasNext() ) {
1572             ReachTuple rt = rtItr.next();
1573
1574             oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(),
1575                                                   rt.isOutOfContext()
1576                                                   )
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                                                    oocHrnIdOoc2callee
1607                                                    ),
1608                                   toCalleeContext( hrnCaller.getAlpha(),
1609                                                    preds,
1610                                                    oocHrnIdOoc2callee
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                                       oocHrnIdOoc2callee
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                                       oocHrnIdOoc2callee
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                                                          oocHrnIdOoc2callee
1799                                                          ),
1800                                         toCalleeContext( oocReach,
1801                                                          preds,
1802                                                          oocHrnIdOoc2callee
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                                                            oocHrnIdOoc2callee
1828                                                            ),
1829                                           toCalleeContext( oocReach,
1830                                                            preds,
1831                                                            oocHrnIdOoc2callee
1832                                                            ),
1833                                           preds,
1834                                           "out-of-context"
1835                                           );
1836
1837           } else {
1838             // otherwise it is there, so merge reachability
1839             hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1840                                                                      toCalleeContext( oocReach,
1841                                                                                       preds,
1842                                                                                       oocHrnIdOoc2callee
1843                                                                                       )
1844                                                                      )
1845                                              );
1846           }
1847         }
1848
1849         assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1850
1851         rg.addRefEdge( hrnCalleeAndOutContext,
1852                        hrnDstCallee,
1853                        new RefEdge( hrnCalleeAndOutContext,
1854                                     hrnDstCallee,
1855                                     reCaller.getType(),
1856                                     reCaller.getField(),
1857                                     toCalleeContext( reCaller.getBeta(),
1858                                                      preds,
1859                                                      oocHrnIdOoc2callee
1860                                                      ),
1861                                     preds
1862                                     )
1863                        );
1864
1865         } else {
1866         // the out-of-context edge already exists
1867         oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1868                                                          toCalleeContext( reCaller.getBeta(),
1869                                                                           preds,
1870                                                                           oocHrnIdOoc2callee
1871                                                                           )
1872                                                   )
1873                                  );
1874
1875         oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1876                                                   reCaller.getPreds()
1877                                                   )
1878                                   );
1879
1880         HeapRegionNode hrnCalleeAndOutContext =
1881           (HeapRegionNode) oocEdgeExisting.getSrc();
1882         hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1883                                                                  toCalleeContext( oocReach,
1884                                                                                   preds,
1885                                                                                   oocHrnIdOoc2callee
1886                                                                                   )
1887                                                                  )
1888                                          );
1889
1890         assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1891       }
1892     }
1893
1894
1895     if( writeDebugDOTs ) {
1896       try {
1897         rg.writeGraph( "calleeview",
1898                        resolveMethodDebugDOTwriteLabels,
1899                        resolveMethodDebugDOTselectTemps,
1900                        resolveMethodDebugDOTpruneGarbage,
1901                        resolveMethodDebugDOThideSubsetReach,
1902                        resolveMethodDebugDOThideEdgeTaints );
1903       } catch( IOException e ) {}
1904     }
1905
1906     return rg;
1907   }
1908
1909   private static Hashtable<String, Integer> oocid2hrnid =
1910     new Hashtable<String, Integer>();
1911
1912
1913   // useful since many graphs writes in the method call debug code
1914   private static boolean resolveMethodDebugDOTwriteLabels     = true;
1915   private static boolean resolveMethodDebugDOTselectTemps     = true;
1916   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
1917   private static boolean resolveMethodDebugDOThideSubsetReach = false;
1918   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
1919
1920
1921
1922   public void
1923     resolveMethodCall( FlatCall     fc,
1924                        FlatMethod   fmCallee,
1925                        ReachGraph   rgCallee,
1926                        Set<Integer> callerNodeIDsCopiedToCallee,
1927                        boolean      writeDebugDOTs
1928                        ) {
1929
1930
1931     if( writeDebugDOTs ) {
1932       try {
1933         rgCallee.writeGraph( "callee",
1934                        resolveMethodDebugDOTwriteLabels,
1935                        resolveMethodDebugDOTselectTemps,
1936                        resolveMethodDebugDOTpruneGarbage,
1937                        resolveMethodDebugDOThideSubsetReach,
1938                        resolveMethodDebugDOThideEdgeTaints );
1939
1940         writeGraph( "caller00In",
1941                     resolveMethodDebugDOTwriteLabels,
1942                     resolveMethodDebugDOTselectTemps,
1943                     resolveMethodDebugDOTpruneGarbage,
1944                     resolveMethodDebugDOThideSubsetReach,
1945                     resolveMethodDebugDOThideEdgeTaints,
1946                     callerNodeIDsCopiedToCallee );
1947       } catch( IOException e ) {}
1948     }
1949
1950
1951     // method call transfer function steps:
1952     // 1. Use current callee-reachable heap (CRH) to test callee
1953     //    predicates and mark what will be coming in.
1954     // 2. Wipe CRH out of caller.
1955     // 3. Transplant marked callee parts in:
1956     //    a) bring in nodes
1957     //    b) bring in callee -> callee edges
1958     //    c) resolve out-of-context -> callee edges
1959     //    d) assign return value
1960     // 4. Collapse shadow nodes down
1961     // 5. Global sweep it.
1962
1963
1964
1965     // 1. mark what callee elements have satisfied predicates
1966     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1967       new Hashtable<HeapRegionNode, ExistPredSet>();
1968
1969     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1970       new Hashtable<RefEdge, ExistPredSet>();
1971
1972     Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1973       new Hashtable<ReachState, ExistPredSet>();
1974
1975     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1976       new Hashtable< RefEdge, Set<RefSrcNode> >();
1977
1978     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1979     while( meItr.hasNext() ) {
1980       Map.Entry      me        = (Map.Entry)      meItr.next();
1981       Integer        id        = (Integer)        me.getKey();
1982       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1983
1984       // if a callee element's predicates are satisfied then a set
1985       // of CALLER predicates is returned: they are the predicates
1986       // that the callee element moved into the caller context
1987       // should have, and it is inefficient to find this again later
1988       ExistPredSet predsIfSatis =
1989         hrnCallee.getPreds().isSatisfiedBy( this,
1990                                             callerNodeIDsCopiedToCallee
1991                                             );
1992       if( predsIfSatis != null ) {
1993         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1994       } else {
1995         // otherwise don't bother looking at edges to this node
1996         continue;
1997       }
1998
1999       // since the node is coming over, find out which reach
2000       // states on it should come over, too
2001       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2002       while( stateItr.hasNext() ) {
2003         ReachState stateCallee = stateItr.next();
2004
2005         predsIfSatis =
2006           stateCallee.getPreds().isSatisfiedBy( this,
2007                                                 callerNodeIDsCopiedToCallee
2008                                                 );
2009         if( predsIfSatis != null ) {
2010           calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2011         }
2012       }
2013
2014       // then look at edges to the node
2015       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2016       while( reItr.hasNext() ) {
2017         RefEdge    reCallee  = reItr.next();
2018         RefSrcNode rsnCallee = reCallee.getSrc();
2019
2020         // (caller local variables to in-context heap regions)
2021         // have an (out-of-context heap region -> in-context heap region)
2022         // abstraction in the callEE, so its true we never need to
2023         // look at a (var node -> heap region) edge in callee to bring
2024         // those over for the call site transfer.  What about (param var->heap region)
2025         // edges in callee? They are dealt with below this loop.
2026         // So, yes, at this point skip (var->region) edges in callee
2027         if( rsnCallee instanceof VariableNode ) {
2028           continue;
2029         }
2030
2031         // first see if the source is out-of-context, and only
2032         // proceed with this edge if we find some caller-context
2033         // matches
2034         HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2035         boolean matchedOutOfContext = false;
2036
2037         if( hrnSrcCallee.isOutOfContext() ) {
2038
2039           assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2040
2041           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2042
2043           // is the target node in the caller?
2044           HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2045           if( hrnDstCaller == null ) {
2046             continue;
2047           }
2048
2049           Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2050           while( reDstItr.hasNext() ) {
2051             // the edge and field (either possibly null) must match
2052             RefEdge reCaller = reDstItr.next();
2053
2054             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
2055                 !reCaller.fieldEquals( reCallee.getField() )
2056                 ) {
2057               continue;
2058             }
2059
2060             RefSrcNode rsnCaller = reCaller.getSrc();
2061             if( rsnCaller instanceof VariableNode ) {
2062               // a variable node matches an OOC region with null type
2063               if( hrnSrcCallee.getType() != null ) {
2064                 continue;
2065               }
2066
2067             } else {
2068               // otherwise types should match
2069               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2070               if( hrnSrcCallee.getType() == null ) {
2071                 if( hrnCallerSrc.getType() != null ) {
2072                   continue;
2073                 }
2074               } else {
2075                 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2076                   continue;
2077                 }
2078               }
2079             }
2080
2081             rsnCallers.add( rsnCaller );
2082             matchedOutOfContext = true;
2083           }
2084
2085           if( !rsnCallers.isEmpty() ) {
2086             calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2087           }
2088         }
2089
2090         if( hrnSrcCallee.isOutOfContext() &&
2091             !matchedOutOfContext ) {
2092           continue;
2093         }
2094
2095         predsIfSatis =
2096           reCallee.getPreds().isSatisfiedBy( this,
2097                                              callerNodeIDsCopiedToCallee
2098                                              );
2099         if( predsIfSatis != null ) {
2100           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2101
2102           // since the edge is coming over, find out which reach
2103           // states on it should come over, too
2104           stateItr = reCallee.getBeta().iterator();
2105           while( stateItr.hasNext() ) {
2106             ReachState stateCallee = stateItr.next();
2107
2108             predsIfSatis =
2109               stateCallee.getPreds().isSatisfiedBy( this,
2110                                                     callerNodeIDsCopiedToCallee
2111                                                     );
2112             if( predsIfSatis != null ) {
2113               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2114             }
2115           }
2116         }
2117       }
2118     }
2119
2120     // test param -> HRN edges, also
2121     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2122
2123       // parameter defined here is the symbol in the callee
2124       TempDescriptor tdParam  = fmCallee.getParameter( i );
2125       VariableNode   vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2126
2127       Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2128       while( reItr.hasNext() ) {
2129         RefEdge reCallee = reItr.next();
2130
2131         ExistPredSet ifDst =
2132           reCallee.getDst().getPreds().isSatisfiedBy( this,
2133                                                       callerNodeIDsCopiedToCallee
2134                                                       );
2135         if( ifDst == null ) {
2136           continue;
2137         }
2138
2139         ExistPredSet predsIfSatis =
2140           reCallee.getPreds().isSatisfiedBy( this,
2141                                              callerNodeIDsCopiedToCallee
2142                                              );
2143         if( predsIfSatis != null ) {
2144           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2145
2146           // since the edge is coming over, find out which reach
2147           // states on it should come over, too
2148           Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2149           while( stateItr.hasNext() ) {
2150             ReachState stateCallee = stateItr.next();
2151
2152             predsIfSatis =
2153               stateCallee.getPreds().isSatisfiedBy( this,
2154                                                     callerNodeIDsCopiedToCallee
2155                                                     );
2156             if( predsIfSatis != null ) {
2157               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2158             }
2159           }
2160
2161         }
2162       }
2163     }
2164
2165
2166
2167
2168     if( writeDebugDOTs ) {
2169       try {
2170         writeGraph( "caller20BeforeWipe",
2171                     resolveMethodDebugDOTwriteLabels,
2172                     resolveMethodDebugDOTselectTemps,
2173                     resolveMethodDebugDOTpruneGarbage,
2174                     resolveMethodDebugDOThideSubsetReach,
2175                     resolveMethodDebugDOThideEdgeTaints );
2176       } catch( IOException e ) {}
2177     }
2178
2179
2180     // 2. predicates tested, ok to wipe out caller part
2181     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2182     while( hrnItr.hasNext() ) {
2183       Integer        hrnID     = hrnItr.next();
2184       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2185       assert hrnCaller != null;
2186
2187       // when clearing off nodes, also eliminate variable
2188       // references
2189       wipeOut( hrnCaller, true );
2190     }
2191
2192
2193
2194     if( writeDebugDOTs ) {
2195       try {
2196         writeGraph( "caller30BeforeAddingNodes",
2197                     resolveMethodDebugDOTwriteLabels,
2198                     resolveMethodDebugDOTselectTemps,
2199                     resolveMethodDebugDOTpruneGarbage,
2200                     resolveMethodDebugDOThideSubsetReach,
2201                     resolveMethodDebugDOThideEdgeTaints );
2202       } catch( IOException e ) {}
2203     }
2204
2205
2206     // 3. callee elements with satisfied preds come in, note that
2207     //    the mapping of elements satisfied to preds is like this:
2208     //    A callee element EE has preds EEp that are satisfied by
2209     //    some caller element ER.  We bring EE into the caller
2210     //    context as ERee with the preds of ER, namely ERp, which
2211     //    in the following algorithm is the value in the mapping
2212
2213     // 3.a) nodes
2214     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2215     while( satisItr.hasNext() ) {
2216       Map.Entry      me        = (Map.Entry)      satisItr.next();
2217       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2218       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
2219
2220       // TODO: I think its true that the current implementation uses
2221       // the type of the OOC region and the predicates OF THE EDGE from
2222       // it to link everything up in caller context, so that's why we're
2223       // skipping this... maybe that's a sillier way to do it?
2224       if( hrnCallee.isOutOfContext() ) {
2225         continue;
2226       }
2227
2228       AllocSite as = hrnCallee.getAllocSite();
2229       allocSites.add( as );
2230
2231       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2232
2233       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2234       if( hrnCaller == null ) {
2235         hrnCaller =
2236           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
2237                                    hrnCallee.isSingleObject(), // single object?
2238                                    hrnCallee.isNewSummary(),   // summary?
2239                                    hrnCallee.isFlagged(),      // flagged?
2240                                    false,                      // out-of-context?
2241                                    hrnCallee.getType(),        // type
2242                                    hrnCallee.getAllocSite(),   // allocation site
2243                                    toCallerContext( hrnCallee.getInherent(),
2244                                                     calleeStatesSatisfied  ),    // inherent reach
2245                                    null,                       // current reach
2246                                    predsEmpty,                 // predicates
2247                                    hrnCallee.getDescription()  // description
2248                                    );
2249       } else {
2250         assert hrnCaller.isWiped();
2251       }
2252
2253       hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2254                                            calleeStatesSatisfied
2255                                            )
2256                           );
2257
2258       hrnCaller.setPreds( preds );
2259     }
2260
2261
2262
2263     if( writeDebugDOTs ) {
2264       try {
2265         writeGraph( "caller31BeforeAddingEdges",
2266                     resolveMethodDebugDOTwriteLabels,
2267                     resolveMethodDebugDOTselectTemps,
2268                     resolveMethodDebugDOTpruneGarbage,
2269                     resolveMethodDebugDOThideSubsetReach,
2270                     resolveMethodDebugDOThideEdgeTaints );
2271       } catch( IOException e ) {}
2272     }
2273
2274
2275     // set these up during the next procedure so after
2276     // the caller has all of its nodes and edges put
2277     // back together we can propagate the callee's
2278     // reach changes backwards into the caller graph
2279     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2280
2281     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2282       new Hashtable<RefEdge, ChangeSet>();
2283
2284
2285     // 3.b) callee -> callee edges AND out-of-context -> callee
2286     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2287     while( satisItr.hasNext() ) {
2288       Map.Entry    me       = (Map.Entry)    satisItr.next();
2289       RefEdge      reCallee = (RefEdge)      me.getKey();
2290       ExistPredSet preds    = (ExistPredSet) me.getValue();
2291
2292       HeapRegionNode hrnDstCallee = reCallee.getDst();
2293       AllocSite      asDst        = hrnDstCallee.getAllocSite();
2294       allocSites.add( asDst );
2295
2296       Integer hrnIDDstShadow =
2297         asDst.getShadowIDfromID( hrnDstCallee.getID() );
2298
2299       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2300       assert hrnDstCaller != null;
2301
2302
2303       RefSrcNode rsnCallee = reCallee.getSrc();
2304
2305       Set<RefSrcNode> rsnCallers =
2306         new HashSet<RefSrcNode>();
2307
2308       Set<RefSrcNode> oocCallers =
2309         calleeEdges2oocCallerSrcMatches.get( reCallee );
2310
2311       boolean oocEdges = false;
2312
2313       if( oocCallers == null ) {
2314         // there are no out-of-context matches, so it's
2315         // either a param/arg var or one in-context heap region
2316         if( rsnCallee instanceof VariableNode ) {
2317           // variable -> node in the callee should only
2318           // come into the caller if its from a param var
2319           VariableNode   vnCallee = (VariableNode) rsnCallee;
2320           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2321           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
2322                                                             tdParam );
2323           if( tdArg == null ) {
2324             // this means the variable isn't a parameter, its local
2325             // to the callee so we ignore it in call site transfer
2326             // shouldn't this NEVER HAPPEN?
2327             assert false;
2328           }
2329           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2330           oocEdges = true;
2331
2332         } else {
2333           // otherwise source is in context, one region
2334           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2335
2336           // translate an in-context node to shadow
2337           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2338           allocSites.add( asSrc );
2339
2340           Integer hrnIDSrcShadow =
2341             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2342
2343           HeapRegionNode hrnSrcCallerShadow =
2344             this.id2hrn.get( hrnIDSrcShadow );
2345
2346           if( hrnSrcCallerShadow == null ) {
2347             hrnSrcCallerShadow =
2348               createNewHeapRegionNode( hrnIDSrcShadow,                // id or null to generate a new one
2349                                        hrnSrcCallee.isSingleObject(), // single object?
2350                                        hrnSrcCallee.isNewSummary(),   // summary?
2351                                        hrnSrcCallee.isFlagged(),      // flagged?
2352                                        false,                         // out-of-context?
2353                                        hrnSrcCallee.getType(),        // type
2354                                        hrnSrcCallee.getAllocSite(),   // allocation site
2355                                        toCallerContext( hrnSrcCallee.getInherent(),
2356                                                         calleeStatesSatisfied ),    // inherent reach
2357                                        toCallerContext( hrnSrcCallee.getAlpha(),
2358                                                         calleeStatesSatisfied ),       // current reach
2359                                        predsEmpty,                    // predicates
2360                                        hrnSrcCallee.getDescription()  // description
2361                                        );
2362           }
2363
2364           rsnCallers.add( hrnSrcCallerShadow );
2365         }
2366
2367       } else {
2368         // otherwise we have a set of out-of-context srcs
2369         // that should NOT be translated to shadow nodes
2370         assert !oocCallers.isEmpty();
2371         rsnCallers.addAll( oocCallers );
2372         oocEdges = true;
2373       }
2374
2375       // now make all caller edges we've identified from
2376       // this callee edge with a satisfied predicate
2377       assert !rsnCallers.isEmpty();
2378       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2379       while( rsnItr.hasNext() ) {
2380         RefSrcNode rsnCaller = rsnItr.next();
2381
2382         RefEdge reCaller = new RefEdge( rsnCaller,
2383                                         hrnDstCaller,
2384                                         reCallee.getType(),
2385                                         reCallee.getField(),
2386                                         toCallerContext( reCallee.getBeta(),
2387                                                          calleeStatesSatisfied ),
2388                                         preds
2389                                         );
2390
2391         ChangeSet cs = ChangeSet.factory();
2392         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2393         while( rsItr.hasNext() ) {
2394           ReachState   state          = rsItr.next();
2395           ExistPredSet predsPreCallee = state.getPreds();
2396
2397           if( state.isEmpty() ) {
2398             continue;
2399           }
2400
2401           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2402           while( predItr.hasNext() ) {
2403             ExistPred pred = predItr.next();
2404             ReachState old = pred.ne_state;
2405
2406             if( old == null ) {
2407               old = rstateEmpty;
2408             }
2409
2410             cs = Canonical.add( cs,
2411                                 ChangeTuple.factory( old,
2412                                                      state
2413                                                      )
2414                                 );
2415           }
2416         }
2417
2418
2419         // look to see if an edge with same field exists
2420         // and merge with it, otherwise just add the edge
2421         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2422                                                          reCallee.getType(),
2423                                                          reCallee.getField()
2424                                                          );
2425         if( edgeExisting != null ) {
2426           edgeExisting.setBeta(
2427                                Canonical.unionORpreds( edgeExisting.getBeta(),
2428                                                 reCaller.getBeta()
2429                                                 )
2430                                );
2431           edgeExisting.setPreds(
2432                                 Canonical.join( edgeExisting.getPreds(),
2433                                                 reCaller.getPreds()
2434                                                 )
2435                                 );
2436
2437           // for reach propagation
2438           if( !cs.isEmpty() ) {
2439             edgePlannedChanges.put(
2440                                    edgeExisting,
2441                                    Canonical.union( edgePlannedChanges.get( edgeExisting ),
2442                                                     cs
2443                                                     )
2444                                     );
2445           }
2446
2447         } else {
2448           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2449
2450           // for reach propagation
2451           if( !cs.isEmpty() ) {
2452             edgesForPropagation.add( reCaller );
2453             assert !edgePlannedChanges.containsKey( reCaller );
2454             edgePlannedChanges.put( reCaller, cs );
2455           }
2456         }
2457       }
2458     }
2459
2460
2461
2462
2463
2464     if( writeDebugDOTs ) {
2465       try {
2466         writeGraph( "caller35BeforeAssignReturnValue",
2467                     resolveMethodDebugDOTwriteLabels,
2468                     resolveMethodDebugDOTselectTemps,
2469                     resolveMethodDebugDOTpruneGarbage,
2470                     resolveMethodDebugDOThideSubsetReach,
2471                     resolveMethodDebugDOThideEdgeTaints );
2472       } catch( IOException e ) {}
2473     }
2474
2475
2476
2477     // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2478     // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2479     // EDGES, JUST BRINGING THEM ALL!  It'll work for now, over approximation
2480
2481     // 3.d) handle return value assignment if needed
2482     TempDescriptor returnTemp = fc.getReturnTemp();
2483     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2484
2485       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2486       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2487
2488       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2489       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2490       while( reCalleeItr.hasNext() ) {
2491         RefEdge        reCallee     = reCalleeItr.next();
2492         HeapRegionNode hrnDstCallee = reCallee.getDst();
2493
2494         // some edge types are not possible return values when we can
2495         // see what type variable we are assigning it to
2496         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2497           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2498                               reCallee+" for return temp "+returnTemp );
2499           // prune
2500           continue;
2501         }
2502
2503         AllocSite asDst = hrnDstCallee.getAllocSite();
2504         allocSites.add( asDst );
2505
2506         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2507
2508         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2509         if( hrnDstCaller == null ) {
2510           hrnDstCaller =
2511             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
2512                                      hrnDstCallee.isSingleObject(), // single object?
2513                                      hrnDstCallee.isNewSummary(),   // summary?
2514                                      hrnDstCallee.isFlagged(),      // flagged?
2515                                      false,                         // out-of-context?
2516                                      hrnDstCallee.getType(),        // type
2517                                      hrnDstCallee.getAllocSite(),   // allocation site
2518                                      toCallerContext( hrnDstCallee.getInherent(),
2519                                                       calleeStatesSatisfied  ),    // inherent reach
2520                                      toCallerContext( hrnDstCallee.getAlpha(),
2521                                                       calleeStatesSatisfied  ),    // current reach
2522                                      predsTrue,                     // predicates
2523                                      hrnDstCallee.getDescription()  // description
2524                                      );
2525         }
2526
2527         TypeDescriptor tdNewEdge =
2528           mostSpecificType( reCallee.getType(),
2529                             hrnDstCallee.getType(),
2530                             hrnDstCaller.getType()
2531                             );
2532
2533         RefEdge reCaller = new RefEdge( vnLhsCaller,
2534                                         hrnDstCaller,
2535                                         tdNewEdge,
2536                                         null,
2537                                         toCallerContext( reCallee.getBeta(),
2538                                                          calleeStatesSatisfied ),
2539                                         predsTrue
2540                                         );
2541
2542         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2543       }
2544     }
2545
2546
2547
2548     if( writeDebugDOTs ) {
2549       try {
2550         writeGraph( "caller38propagateReach",
2551                     resolveMethodDebugDOTwriteLabels,
2552                     resolveMethodDebugDOTselectTemps,
2553                     resolveMethodDebugDOTpruneGarbage,
2554                     resolveMethodDebugDOThideSubsetReach,
2555                     resolveMethodDebugDOThideEdgeTaints );
2556       } catch( IOException e ) {}
2557     }
2558
2559     // propagate callee reachability changes to the rest
2560     // of the caller graph edges
2561     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2562
2563     propagateTokensOverEdges( edgesForPropagation, // source edges
2564                               edgePlannedChanges,  // map src edge to change set
2565                               edgesUpdated );      // list of updated edges
2566
2567     // commit beta' (beta<-betaNew)
2568     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2569     while( edgeItr.hasNext() ) {
2570       edgeItr.next().applyBetaNew();
2571     }
2572
2573
2574
2575
2576
2577
2578     if( writeDebugDOTs ) {
2579       try {
2580         writeGraph( "caller40BeforeShadowMerge",
2581                     resolveMethodDebugDOTwriteLabels,
2582                     resolveMethodDebugDOTselectTemps,
2583                     resolveMethodDebugDOTpruneGarbage,
2584                     resolveMethodDebugDOThideSubsetReach,
2585                     resolveMethodDebugDOThideEdgeTaints );
2586       } catch( IOException e ) {}
2587     }
2588
2589
2590     // 4) merge shadow nodes so alloc sites are back to k
2591     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2592     while( asItr.hasNext() ) {
2593       // for each allocation site do the following to merge
2594       // shadow nodes (newest from callee) with any existing
2595       // look for the newest normal and newest shadow "slot"
2596       // not being used, transfer normal to shadow.  Keep
2597       // doing this until there are no more normal nodes, or
2598       // no empty shadow slots: then merge all remaining normal
2599       // nodes into the shadow summary.  Finally, convert all
2600       // shadow to their normal versions.
2601       AllocSite as = asItr.next();
2602       int ageNorm = 0;
2603       int ageShad = 0;
2604       while( ageNorm < allocationDepth &&
2605              ageShad < allocationDepth ) {
2606
2607         // first, are there any normal nodes left?
2608         Integer        idNorm  = as.getIthOldest( ageNorm );
2609         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2610         if( hrnNorm == null ) {
2611           // no, this age of normal node not in the caller graph
2612           ageNorm++;
2613           continue;
2614         }
2615
2616         // yes, a normal node exists, is there an empty shadow
2617         // "slot" to transfer it onto?
2618         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2619         if( !hrnShad.isWiped() ) {
2620           // no, this age of shadow node is not empty
2621           ageShad++;
2622           continue;
2623         }
2624
2625         // yes, this shadow node is empty
2626         transferOnto( hrnNorm, hrnShad );
2627         ageNorm++;
2628         ageShad++;
2629       }
2630
2631       // now, while there are still normal nodes but no shadow
2632       // slots, merge normal nodes into the shadow summary
2633       while( ageNorm < allocationDepth ) {
2634
2635         // first, are there any normal nodes left?
2636         Integer        idNorm  = as.getIthOldest( ageNorm );
2637         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2638         if( hrnNorm == null ) {
2639           // no, this age of normal node not in the caller graph
2640           ageNorm++;
2641           continue;
2642         }
2643
2644         // yes, a normal node exists, so get the shadow summary
2645         HeapRegionNode summShad = getSummaryNode( as, true );
2646         mergeIntoSummary( hrnNorm, summShad );
2647         ageNorm++;
2648       }
2649
2650       // if there is a normal summary, merge it into shadow summary
2651       Integer        idNorm   = as.getSummary();
2652       HeapRegionNode summNorm = id2hrn.get( idNorm );
2653       if( summNorm != null ) {
2654         HeapRegionNode summShad = getSummaryNode( as, true );
2655         mergeIntoSummary( summNorm, summShad );
2656       }
2657
2658       // finally, flip all existing shadow nodes onto the normal
2659       for( int i = 0; i < allocationDepth; ++i ) {
2660         Integer        idShad  = as.getIthOldestShadow( i );
2661         HeapRegionNode hrnShad = id2hrn.get( idShad );
2662         if( hrnShad != null ) {
2663           // flip it
2664           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2665           assert hrnNorm.isWiped();
2666           transferOnto( hrnShad, hrnNorm );
2667         }
2668       }
2669
2670       Integer        idShad   = as.getSummaryShadow();
2671       HeapRegionNode summShad = id2hrn.get( idShad );
2672       if( summShad != null ) {
2673         summNorm = getSummaryNode( as, false );
2674         transferOnto( summShad, summNorm );
2675       }
2676     }
2677
2678
2679     if( writeDebugDOTs ) {
2680       try {
2681         writeGraph( "caller45BeforeUnshadow",
2682                     resolveMethodDebugDOTwriteLabels,
2683                     resolveMethodDebugDOTselectTemps,
2684                     resolveMethodDebugDOTpruneGarbage,
2685                     resolveMethodDebugDOThideSubsetReach,
2686                     resolveMethodDebugDOThideEdgeTaints );
2687       } catch( IOException e ) {}
2688     }
2689
2690
2691     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2692     while( itrAllHRNodes.hasNext() ) {
2693       Map.Entry      me  = (Map.Entry)      itrAllHRNodes.next();
2694       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2695
2696       hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2697
2698       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2699       while( itrEdges.hasNext() ) {
2700         RefEdge re = itrEdges.next();
2701         re.setBeta( unshadow( re.getBeta() ) );
2702       }
2703     }
2704
2705
2706
2707     if( writeDebugDOTs ) {
2708       try {
2709         writeGraph( "caller50BeforeGlobalSweep",
2710                     resolveMethodDebugDOTwriteLabels,
2711                     resolveMethodDebugDOTselectTemps,
2712                     resolveMethodDebugDOTpruneGarbage,
2713                     resolveMethodDebugDOThideSubsetReach,
2714                     resolveMethodDebugDOThideEdgeTaints );
2715       } catch( IOException e ) {}
2716     }
2717
2718
2719     // 5.
2720     if( !DISABLE_GLOBAL_SWEEP ) {
2721       globalSweep();
2722     }
2723
2724
2725
2726     if( writeDebugDOTs ) {
2727       try {
2728         writeGraph( "caller90AfterTransfer",
2729                     resolveMethodDebugDOTwriteLabels,
2730                     resolveMethodDebugDOTselectTemps,
2731                     resolveMethodDebugDOTpruneGarbage,
2732                     resolveMethodDebugDOThideSubsetReach,
2733                     resolveMethodDebugDOThideEdgeTaints );
2734       } catch( IOException e ) {}
2735     }
2736   }
2737
2738
2739
2740   ////////////////////////////////////////////////////
2741   //
2742   //  Abstract garbage collection simply removes
2743   //  heap region nodes that are not mechanically
2744   //  reachable from a root set.  This step is
2745   //  essential for testing node and edge existence
2746   //  predicates efficiently
2747   //
2748   ////////////////////////////////////////////////////
2749   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2750
2751     // calculate a root set, will be different for Java
2752     // version of analysis versus Bamboo version
2753     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2754
2755     // visit every variable in graph while building root
2756     // set, and do iterating on a copy, so we can remove
2757     // dead variables while we're at this
2758     Iterator makeCopyItr = td2vn.entrySet().iterator();
2759     Set      entrysCopy  = new HashSet();
2760     while( makeCopyItr.hasNext() ) {
2761       entrysCopy.add( makeCopyItr.next() );
2762     }
2763
2764     Iterator eItr = entrysCopy.iterator();
2765     while( eItr.hasNext() ) {
2766       Map.Entry      me = (Map.Entry)      eItr.next();
2767       TempDescriptor td = (TempDescriptor) me.getKey();
2768       VariableNode   vn = (VariableNode)   me.getValue();
2769
2770       if( liveSet.contains( td ) ) {
2771         toVisit.add( vn );
2772
2773       } else {
2774         // dead var, remove completely from graph
2775         td2vn.remove( td );
2776         clearRefEdgesFrom( vn, null, null, true );
2777       }
2778     }
2779
2780     // everything visited in a traversal is
2781     // considered abstractly live
2782     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2783
2784     while( !toVisit.isEmpty() ) {
2785       RefSrcNode rsn = toVisit.iterator().next();
2786       toVisit.remove( rsn );
2787       visited.add( rsn );
2788
2789       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2790       while( hrnItr.hasNext() ) {
2791         RefEdge        edge = hrnItr.next();
2792         HeapRegionNode hrn  = edge.getDst();
2793
2794         if( !visited.contains( hrn ) ) {
2795           toVisit.add( hrn );
2796         }
2797       }
2798     }
2799
2800     // get a copy of the set to iterate over because
2801     // we're going to monkey with the graph when we
2802     // identify a garbage node
2803     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2804     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2805     while( hrnItr.hasNext() ) {
2806       hrnAllPrior.add( hrnItr.next() );
2807     }
2808
2809     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2810     while( hrnAllItr.hasNext() ) {
2811       HeapRegionNode hrn = hrnAllItr.next();
2812
2813       if( !visited.contains( hrn ) ) {
2814
2815         // heap region nodes are compared across ReachGraph
2816         // objects by their integer ID, so when discarding
2817         // garbage nodes we must also discard entries in
2818         // the ID -> heap region hashtable.
2819         id2hrn.remove( hrn.getID() );
2820
2821         // RefEdge objects are two-way linked between
2822         // nodes, so when a node is identified as garbage,
2823         // actively clear references to and from it so
2824         // live nodes won't have dangling RefEdge's
2825         wipeOut( hrn, true );
2826
2827         // if we just removed the last node from an allocation
2828         // site, it should be taken out of the ReachGraph's list
2829         AllocSite as = hrn.getAllocSite();
2830         if( !hasNodesOf( as ) ) {
2831           allocSites.remove( as );
2832         }
2833       }
2834     }
2835   }
2836
2837   protected boolean hasNodesOf( AllocSite as ) {
2838     if( id2hrn.containsKey( as.getSummary() ) ) {
2839       return true;
2840     }
2841
2842     for( int i = 0; i < allocationDepth; ++i ) {
2843       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2844         return true;
2845       }
2846     }
2847     return false;
2848   }
2849
2850
2851   ////////////////////////////////////////////////////
2852   //
2853   //  This global sweep is an optional step to prune
2854   //  reachability sets that are not internally
2855   //  consistent with the global graph.  It should be
2856   //  invoked after strong updates or method calls.
2857   //
2858   ////////////////////////////////////////////////////
2859   public void globalSweep() {
2860
2861     // boldB is part of the phase 1 sweep
2862     // it has an in-context table and an out-of-context table
2863     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2864       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2865
2866     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2867       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2868
2869     // visit every heap region to initialize alphaNew and betaNew,
2870     // and make a map of every hrnID to the source nodes it should
2871     // propagate forward from.  In-context flagged hrnID's propagate
2872     // from only the in-context node they name, but out-of-context
2873     // ID's may propagate from several out-of-context nodes
2874     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2875       new Hashtable< Integer, Set<HeapRegionNode> >();
2876
2877     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2878       new Hashtable< Integer, Set<HeapRegionNode> >();
2879
2880
2881     Iterator itrHrns = id2hrn.entrySet().iterator();
2882     while( itrHrns.hasNext() ) {
2883       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2884       Integer        hrnID = (Integer)        me.getKey();
2885       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2886
2887       // assert that this node and incoming edges have clean alphaNew
2888       // and betaNew sets, respectively
2889       assert rsetEmpty.equals( hrn.getAlphaNew() );
2890
2891       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2892       while( itrRers.hasNext() ) {
2893         RefEdge edge = itrRers.next();
2894         assert rsetEmpty.equals( edge.getBetaNew() );
2895       }
2896
2897       // make a mapping of IDs to heap regions they propagate from
2898       if( hrn.isFlagged() ) {
2899         assert !hrn.isOutOfContext();
2900         assert !icID2srcs.containsKey( hrn.getID() );
2901
2902         // in-context flagged node IDs simply propagate from the
2903         // node they name
2904         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2905         srcs.add( hrn );
2906         icID2srcs.put( hrn.getID(), srcs );
2907       }
2908
2909       if( hrn.isOutOfContext() ) {
2910         assert !hrn.isFlagged();
2911
2912         // the reachability states on an out-of-context
2913         // node are not really important (combinations of
2914         // IDs or arity)--what matters is that the states
2915         // specify which nodes this out-of-context node
2916         // stands in for.  For example, if the state [17?, 19*]
2917         // appears on the ooc node, it may serve as a source
2918         // for node 17? and a source for node 19.
2919         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2920         while( stateItr.hasNext() ) {
2921           ReachState state = stateItr.next();
2922
2923           Iterator<ReachTuple> rtItr = state.iterator();
2924           while( rtItr.hasNext() ) {
2925             ReachTuple rt = rtItr.next();
2926             assert rt.isOutOfContext();
2927
2928             Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2929             if( srcs == null ) {
2930               srcs = new HashSet<HeapRegionNode>();
2931             }
2932             srcs.add( hrn );
2933             oocID2srcs.put( rt.getHrnID(), srcs );
2934           }
2935         }
2936       }
2937     }
2938
2939     // calculate boldB for all hrnIDs identified by the above
2940     // node traversal, propagating from every source
2941     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2942
2943       Integer             hrnID;
2944       Set<HeapRegionNode> srcs;
2945       boolean             inContext;
2946
2947       if( !icID2srcs.isEmpty() ) {
2948         Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2949         hrnID = (Integer)             me.getKey();
2950         srcs  = (Set<HeapRegionNode>) me.getValue();
2951         inContext = true;
2952         icID2srcs.remove( hrnID );
2953
2954       } else {
2955         assert !oocID2srcs.isEmpty();
2956
2957         Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2958         hrnID = (Integer)             me.getKey();
2959         srcs  = (Set<HeapRegionNode>) me.getValue();
2960         inContext = false;
2961         oocID2srcs.remove( hrnID );
2962       }
2963
2964
2965       Hashtable<RefEdge, ReachSet> boldB_f =
2966         new Hashtable<RefEdge, ReachSet>();
2967
2968       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2969
2970       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2971       while( hrnItr.hasNext() ) {
2972         HeapRegionNode hrn = hrnItr.next();
2973
2974         assert workSetEdges.isEmpty();
2975
2976         // initial boldB_f constraints
2977         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2978         while( itrRees.hasNext() ) {
2979           RefEdge edge = itrRees.next();
2980
2981           assert !boldB_f.containsKey( edge );
2982           boldB_f.put( edge, edge.getBeta() );
2983
2984           assert !workSetEdges.contains( edge );
2985           workSetEdges.add( edge );
2986         }
2987
2988         // enforce the boldB_f constraint at edges until we reach a fixed point
2989         while( !workSetEdges.isEmpty() ) {
2990           RefEdge edge = workSetEdges.iterator().next();
2991           workSetEdges.remove( edge );
2992
2993           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2994           while( itrPrime.hasNext() ) {
2995             RefEdge edgePrime = itrPrime.next();
2996
2997             ReachSet prevResult   = boldB_f.get( edgePrime );
2998             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2999                                                             edgePrime.getBeta()
3000                                                             );
3001
3002             if( prevResult == null ||
3003                 Canonical.unionORpreds( prevResult,
3004                                         intersection ).size()
3005                 > prevResult.size()
3006                 ) {
3007
3008               if( prevResult == null ) {
3009                 boldB_f.put( edgePrime,
3010                              Canonical.unionORpreds( edgePrime.getBeta(),
3011                                                      intersection
3012                                                      )
3013                              );
3014               } else {
3015                 boldB_f.put( edgePrime,
3016                              Canonical.unionORpreds( prevResult,
3017                                                      intersection
3018                                                      )
3019                              );
3020               }
3021               workSetEdges.add( edgePrime );
3022             }
3023           }
3024         }
3025       }
3026
3027       if( inContext ) {
3028         boldBic.put( hrnID, boldB_f );
3029       } else {
3030         boldBooc.put( hrnID, boldB_f );
3031       }
3032     }
3033
3034
3035     // use boldB to prune hrnIDs from alpha states that are impossible
3036     // and propagate the differences backwards across edges
3037     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3038
3039     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3040       new Hashtable<RefEdge, ChangeSet>();
3041
3042
3043     itrHrns = id2hrn.entrySet().iterator();
3044     while( itrHrns.hasNext() ) {
3045       Map.Entry      me    = (Map.Entry)      itrHrns.next();
3046       Integer        hrnID = (Integer)        me.getKey();
3047       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3048
3049       // out-of-context nodes don't participate in the
3050       // global sweep, they serve as sources for the pass
3051       // performed above
3052       if( hrn.isOutOfContext() ) {
3053         continue;
3054       }
3055
3056       // the inherent states of a region are the exception
3057       // to removal as the global sweep prunes
3058       ReachTuple rtException = ReachTuple.factory( hrnID,
3059                                                    !hrn.isSingleObject(),
3060                                                    ReachTuple.ARITY_ONE,
3061                                                    false // out-of-context
3062                                                    );
3063
3064       ChangeSet cts = ChangeSet.factory();
3065
3066       // mark hrnIDs for removal
3067       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3068       while( stateItr.hasNext() ) {
3069         ReachState stateOld = stateItr.next();
3070
3071         ReachState markedHrnIDs = ReachState.factory();
3072
3073         Iterator<ReachTuple> rtItr = stateOld.iterator();
3074         while( rtItr.hasNext() ) {
3075           ReachTuple rtOld = rtItr.next();
3076
3077           // never remove the inherent hrnID from a flagged region
3078           // because it is trivially satisfied
3079           if( hrn.isFlagged() ) {
3080             if( rtOld == rtException ) {
3081               continue;
3082             }
3083           }
3084
3085           // does boldB allow this hrnID?
3086           boolean foundState = false;
3087           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3088           while( incidentEdgeItr.hasNext() ) {
3089             RefEdge incidentEdge = incidentEdgeItr.next();
3090
3091             Hashtable<RefEdge, ReachSet> B;
3092             if( rtOld.isOutOfContext() ) {
3093               B = boldBooc.get( rtOld.getHrnID() );
3094             } else {
3095               assert id2hrn.containsKey( rtOld.getHrnID() );
3096               B = boldBic.get( rtOld.getHrnID() );
3097             }
3098
3099             if( B != null ) {
3100               ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3101               if( boldB_rtOld_incident != null &&
3102                   boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3103                   ) {
3104                 foundState = true;
3105               }
3106             }
3107           }
3108
3109           if( !foundState ) {
3110             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3111           }
3112         }
3113
3114         // if there is nothing marked, just move on
3115         if( markedHrnIDs.isEmpty() ) {
3116           hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3117                                           stateOld
3118                                           )
3119                            );
3120           continue;
3121         }
3122
3123         // remove all marked hrnIDs and establish a change set that should
3124         // propagate backwards over edges from this node
3125         ReachState statePruned = ReachState.factory();
3126         rtItr = stateOld.iterator();
3127         while( rtItr.hasNext() ) {
3128           ReachTuple rtOld = rtItr.next();
3129
3130           if( !markedHrnIDs.containsTuple( rtOld ) ) {
3131             statePruned = Canonical.add( statePruned, rtOld );
3132           }
3133         }
3134         assert !stateOld.equals( statePruned );
3135
3136         hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3137                                         statePruned
3138                                         )
3139                          );
3140         ChangeTuple ct = ChangeTuple.factory( stateOld,
3141                                               statePruned
3142                                               );
3143         cts = Canonical.add( cts, ct );
3144       }
3145
3146       // throw change tuple set on all incident edges
3147       if( !cts.isEmpty() ) {
3148         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3149         while( incidentEdgeItr.hasNext() ) {
3150           RefEdge incidentEdge = incidentEdgeItr.next();
3151
3152           edgesForPropagation.add( incidentEdge );
3153
3154           if( edgePlannedChanges.get( incidentEdge ) == null ) {
3155             edgePlannedChanges.put( incidentEdge, cts );
3156           } else {
3157             edgePlannedChanges.put(
3158                                    incidentEdge,
3159                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
3160                                                     cts
3161                                                     )
3162                                     );
3163           }
3164         }
3165       }
3166     }
3167
3168     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3169
3170     propagateTokensOverEdges( edgesForPropagation,
3171                               edgePlannedChanges,
3172                               edgesUpdated );
3173
3174     // at the end of the 1st phase reference edges have
3175     // beta, betaNew that correspond to beta and betaR
3176     //
3177     // commit beta<-betaNew, so beta=betaR and betaNew
3178     // will represent the beta' calculation in 2nd phase
3179     //
3180     // commit alpha<-alphaNew because it won't change
3181     HashSet<RefEdge> res = new HashSet<RefEdge>();
3182
3183     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3184     while( nodeItr.hasNext() ) {
3185       HeapRegionNode hrn = nodeItr.next();
3186
3187       // as mentioned above, out-of-context nodes only serve
3188       // as sources of reach states for the sweep, not part
3189       // of the changes
3190       if( hrn.isOutOfContext() ) {
3191         assert hrn.getAlphaNew().equals( rsetEmpty );
3192       } else {
3193         hrn.applyAlphaNew();
3194       }
3195
3196       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3197       while( itrRes.hasNext() ) {
3198         res.add( itrRes.next() );
3199       }
3200     }
3201
3202
3203     // 2nd phase
3204     Iterator<RefEdge> edgeItr = res.iterator();
3205     while( edgeItr.hasNext() ) {
3206       RefEdge        edge = edgeItr.next();
3207       HeapRegionNode hrn  = edge.getDst();
3208
3209       // commit results of last phase
3210       if( edgesUpdated.contains( edge ) ) {
3211         edge.applyBetaNew();
3212       }
3213
3214       // compute intial condition of 2nd phase
3215       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3216                                                hrn.getAlpha()
3217                                                )
3218                        );
3219     }
3220
3221     // every edge in the graph is the initial workset
3222     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3223     while( !edgeWorkSet.isEmpty() ) {
3224       RefEdge edgePrime = edgeWorkSet.iterator().next();
3225       edgeWorkSet.remove( edgePrime );
3226
3227       RefSrcNode rsn = edgePrime.getSrc();
3228       if( !(rsn instanceof HeapRegionNode) ) {
3229         continue;
3230       }
3231       HeapRegionNode hrn = (HeapRegionNode) rsn;
3232
3233       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3234       while( itrEdge.hasNext() ) {
3235         RefEdge edge = itrEdge.next();
3236
3237         ReachSet prevResult = edge.getBetaNew();
3238         assert prevResult != null;
3239
3240         ReachSet intersection =
3241           Canonical.intersection( edge.getBeta(),
3242                                   edgePrime.getBetaNew()
3243                                   );
3244
3245         if( Canonical.unionORpreds( prevResult,
3246                                     intersection
3247                                     ).size()
3248             > prevResult.size()
3249             ) {
3250
3251           edge.setBetaNew(
3252                           Canonical.unionORpreds( prevResult,
3253                                                   intersection
3254                                                   )
3255                            );
3256           edgeWorkSet.add( edge );
3257         }
3258       }
3259     }
3260
3261     // commit beta' (beta<-betaNew)
3262     edgeItr = res.iterator();
3263     while( edgeItr.hasNext() ) {
3264       edgeItr.next().applyBetaNew();
3265     }
3266   }
3267
3268
3269
3270   ////////////////////////////////////////////////////
3271   // high-level merge operations
3272   ////////////////////////////////////////////////////
3273   public void merge_sameMethodContext( ReachGraph rg ) {
3274     // when merging two graphs that abstract the heap
3275     // of the same method context, we just call the
3276     // basic merge operation
3277     merge( rg );
3278   }
3279
3280   public void merge_diffMethodContext( ReachGraph rg ) {
3281     // when merging graphs for abstract heaps in
3282     // different method contexts we should:
3283     // 1) age the allocation sites?
3284     merge( rg );
3285   }
3286
3287   ////////////////////////////////////////////////////
3288   // in merge() and equals() methods the suffix A
3289   // represents the passed in graph and the suffix
3290   // B refers to the graph in this object
3291   // Merging means to take the incoming graph A and
3292   // merge it into B, so after the operation graph B
3293   // is the final result.
3294   ////////////////////////////////////////////////////
3295   protected void merge( ReachGraph rg ) {
3296
3297     if( rg == null ) {
3298       return;
3299     }
3300
3301     mergeNodes     ( rg );
3302     mergeRefEdges  ( rg );
3303     mergeAllocSites( rg );
3304   }
3305
3306   protected void mergeNodes( ReachGraph rg ) {
3307
3308     // start with heap region nodes
3309     Set      sA = rg.id2hrn.entrySet();
3310     Iterator iA = sA.iterator();
3311     while( iA.hasNext() ) {
3312       Map.Entry      meA  = (Map.Entry)      iA.next();
3313       Integer        idA  = (Integer)        meA.getKey();
3314       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3315
3316       // if this graph doesn't have a node the
3317       // incoming graph has, allocate it
3318       if( !id2hrn.containsKey( idA ) ) {
3319         HeapRegionNode hrnB = hrnA.copy();
3320         id2hrn.put( idA, hrnB );
3321
3322       } else {
3323         // otherwise this is a node present in both graphs
3324         // so make the new reachability set a union of the
3325         // nodes' reachability sets
3326         HeapRegionNode hrnB = id2hrn.get( idA );
3327         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3328                                         hrnA.getAlpha()
3329                                         )
3330                        );
3331
3332         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3333                                        hrnA.getPreds()
3334                                        )
3335                        );
3336       }
3337     }
3338
3339     // now add any variable nodes that are in graph B but
3340     // not in A
3341     sA = rg.td2vn.entrySet();
3342     iA = sA.iterator();
3343     while( iA.hasNext() ) {
3344       Map.Entry      meA = (Map.Entry)      iA.next();
3345       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3346       VariableNode   lnA = (VariableNode)   meA.getValue();
3347
3348       // if the variable doesn't exist in B, allocate and add it
3349       VariableNode lnB = getVariableNodeFromTemp( tdA );
3350     }
3351   }
3352
3353   protected void mergeRefEdges( ReachGraph rg ) {
3354
3355     // between heap regions
3356     Set      sA = rg.id2hrn.entrySet();
3357     Iterator iA = sA.iterator();
3358     while( iA.hasNext() ) {
3359       Map.Entry      meA  = (Map.Entry)      iA.next();
3360       Integer        idA  = (Integer)        meA.getKey();
3361       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3362
3363       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3364       while( heapRegionsItrA.hasNext() ) {
3365         RefEdge        edgeA     = heapRegionsItrA.next();
3366         HeapRegionNode hrnChildA = edgeA.getDst();
3367         Integer        idChildA  = hrnChildA.getID();
3368
3369         // at this point we know an edge in graph A exists
3370         // idA -> idChildA, does this exist in B?
3371         assert id2hrn.containsKey( idA );
3372         HeapRegionNode hrnB        = id2hrn.get( idA );
3373         RefEdge        edgeToMerge = null;
3374
3375         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3376         while( heapRegionsItrB.hasNext() &&
3377                edgeToMerge == null          ) {
3378
3379           RefEdge        edgeB     = heapRegionsItrB.next();
3380           HeapRegionNode hrnChildB = edgeB.getDst();
3381           Integer        idChildB  = hrnChildB.getID();
3382
3383           // don't use the RefEdge.equals() here because
3384           // we're talking about existence between graphs,
3385           // not intragraph equal
3386           if( idChildB.equals( idChildA ) &&
3387               edgeB.typeAndFieldEquals( edgeA ) ) {
3388
3389             edgeToMerge = edgeB;
3390           }
3391         }
3392
3393         // if the edge from A was not found in B,
3394         // add it to B.
3395         if( edgeToMerge == null ) {
3396           assert id2hrn.containsKey( idChildA );
3397           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3398           edgeToMerge = edgeA.copy();
3399           edgeToMerge.setSrc( hrnB );
3400           edgeToMerge.setDst( hrnChildB );
3401           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3402         }
3403         // otherwise, the edge already existed in both graphs
3404         // so merge their reachability sets
3405         else {
3406           // just replace this beta set with the union
3407           assert edgeToMerge != null;
3408           edgeToMerge.setBeta(
3409                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3410                                                edgeA.getBeta()
3411                                                )
3412                               );
3413           edgeToMerge.setPreds(
3414                                Canonical.join( edgeToMerge.getPreds(),
3415                                                edgeA.getPreds()
3416                                                )
3417                                );
3418         }
3419       }
3420     }
3421
3422     // and then again from variable nodes
3423     sA = rg.td2vn.entrySet();
3424     iA = sA.iterator();
3425     while( iA.hasNext() ) {
3426       Map.Entry      meA = (Map.Entry)      iA.next();
3427       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3428       VariableNode   vnA = (VariableNode)   meA.getValue();
3429
3430       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3431       while( heapRegionsItrA.hasNext() ) {
3432         RefEdge        edgeA     = heapRegionsItrA.next();
3433         HeapRegionNode hrnChildA = edgeA.getDst();
3434         Integer        idChildA  = hrnChildA.getID();
3435
3436         // at this point we know an edge in graph A exists
3437         // tdA -> idChildA, does this exist in B?
3438         assert td2vn.containsKey( tdA );
3439         VariableNode vnB         = td2vn.get( tdA );
3440         RefEdge      edgeToMerge = null;
3441
3442         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3443         while( heapRegionsItrB.hasNext() &&
3444                edgeToMerge == null          ) {
3445
3446           RefEdge        edgeB     = heapRegionsItrB.next();
3447           HeapRegionNode hrnChildB = edgeB.getDst();
3448           Integer        idChildB  = hrnChildB.getID();
3449
3450           // don't use the RefEdge.equals() here because
3451           // we're talking about existence between graphs
3452           if( idChildB.equals( idChildA ) &&
3453               edgeB.typeAndFieldEquals( edgeA ) ) {
3454
3455             edgeToMerge = edgeB;
3456           }
3457         }
3458
3459         // if the edge from A was not found in B,
3460         // add it to B.
3461         if( edgeToMerge == null ) {
3462           assert id2hrn.containsKey( idChildA );
3463           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3464           edgeToMerge = edgeA.copy();
3465           edgeToMerge.setSrc( vnB );
3466           edgeToMerge.setDst( hrnChildB );
3467           addRefEdge( vnB, hrnChildB, edgeToMerge );
3468         }
3469         // otherwise, the edge already existed in both graphs
3470         // so merge their reachability sets
3471         else {
3472           // just replace this beta set with the union
3473           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3474                                                 edgeA.getBeta()
3475                                                 )
3476                                );
3477           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3478                                                 edgeA.getPreds()
3479                                                 )
3480                                 );
3481         }
3482       }
3483     }
3484   }
3485
3486   protected void mergeAllocSites( ReachGraph rg ) {
3487     allocSites.addAll( rg.allocSites );
3488   }
3489
3490
3491   // it is necessary in the equals() member functions
3492   // to "check both ways" when comparing the data
3493   // structures of two graphs.  For instance, if all
3494   // edges between heap region nodes in graph A are
3495   // present and equal in graph B it is not sufficient
3496   // to say the graphs are equal.  Consider that there
3497   // may be edges in graph B that are not in graph A.
3498   // the only way to know that all edges in both graphs
3499   // are equally present is to iterate over both data
3500   // structures and compare against the other graph.
3501   public boolean equals( ReachGraph rg ) {
3502
3503     if( rg == null ) {
3504       return false;
3505     }
3506
3507     if( !areHeapRegionNodesEqual( rg ) ) {
3508       return false;
3509     }
3510
3511     if( !areVariableNodesEqual( rg ) ) {
3512       return false;
3513     }
3514
3515     if( !areRefEdgesEqual( rg ) ) {
3516       return false;
3517     }
3518
3519     // if everything is equal up to this point,
3520     // assert that allocSites is also equal--
3521     // this data is redundant but kept for efficiency
3522     assert allocSites.equals( rg.allocSites );
3523
3524     return true;
3525   }
3526
3527
3528   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3529
3530     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3531       return false;
3532     }
3533
3534     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3535       return false;
3536     }
3537
3538     return true;
3539   }
3540
3541   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3542                                                         ReachGraph rgB ) {
3543     Set      sA = rgA.id2hrn.entrySet();
3544     Iterator iA = sA.iterator();
3545     while( iA.hasNext() ) {
3546       Map.Entry      meA  = (Map.Entry)      iA.next();
3547       Integer        idA  = (Integer)        meA.getKey();
3548       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3549
3550       if( !rgB.id2hrn.containsKey( idA ) ) {
3551         return false;
3552       }
3553
3554       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3555       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3556         return false;
3557       }
3558     }
3559
3560     return true;
3561   }
3562
3563   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3564
3565     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3566       return false;
3567     }
3568
3569     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3570       return false;
3571     }
3572
3573     return true;
3574   }
3575
3576   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3577                                                        ReachGraph rgB ) {
3578     Set      sA = rgA.td2vn.entrySet();
3579     Iterator iA = sA.iterator();
3580     while( iA.hasNext() ) {
3581       Map.Entry      meA = (Map.Entry)      iA.next();
3582       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3583
3584       if( !rgB.td2vn.containsKey( tdA ) ) {
3585         return false;
3586       }
3587     }
3588
3589     return true;
3590   }
3591
3592
3593   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3594     if( !areallREinAandBequal( this, rg ) ) {
3595       return false;
3596     }
3597
3598     return true;
3599   }
3600
3601   static protected boolean areallREinAandBequal( ReachGraph rgA,
3602                                                  ReachGraph rgB ) {
3603
3604     // check all the heap region->heap region edges
3605     Set      sA = rgA.id2hrn.entrySet();
3606     Iterator iA = sA.iterator();
3607     while( iA.hasNext() ) {
3608       Map.Entry      meA  = (Map.Entry)      iA.next();
3609       Integer        idA  = (Integer)        meA.getKey();
3610       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3611
3612       // we should have already checked that the same
3613       // heap regions exist in both graphs
3614       assert rgB.id2hrn.containsKey( idA );
3615
3616       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3617         return false;
3618       }
3619
3620       // then check every edge in B for presence in A, starting
3621       // from the same parent HeapRegionNode
3622       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3623
3624       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3625         return false;
3626       }
3627     }
3628
3629     // then check all the variable->heap region edges
3630     sA = rgA.td2vn.entrySet();
3631     iA = sA.iterator();
3632     while( iA.hasNext() ) {
3633       Map.Entry      meA = (Map.Entry)      iA.next();
3634       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3635       VariableNode   vnA = (VariableNode)   meA.getValue();
3636
3637       // we should have already checked that the same
3638       // label nodes exist in both graphs
3639       assert rgB.td2vn.containsKey( tdA );
3640
3641       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3642         return false;
3643       }
3644
3645       // then check every edge in B for presence in A, starting
3646       // from the same parent VariableNode
3647       VariableNode vnB = rgB.td2vn.get( tdA );
3648
3649       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3650         return false;
3651       }
3652     }
3653
3654     return true;
3655   }
3656
3657
3658   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3659                                                   RefSrcNode rnA,
3660                                                   ReachGraph rgB ) {
3661
3662     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3663     while( itrA.hasNext() ) {
3664       RefEdge        edgeA     = itrA.next();
3665       HeapRegionNode hrnChildA = edgeA.getDst();
3666       Integer        idChildA  = hrnChildA.getID();
3667
3668       assert rgB.id2hrn.containsKey( idChildA );
3669
3670       // at this point we know an edge in graph A exists
3671       // rnA -> idChildA, does this exact edge exist in B?
3672       boolean edgeFound = false;
3673
3674       RefSrcNode rnB = null;
3675       if( rnA instanceof HeapRegionNode ) {
3676         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3677         rnB = rgB.id2hrn.get( hrnA.getID() );
3678       } else {
3679         VariableNode vnA = (VariableNode) rnA;
3680         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3681       }
3682
3683       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3684       while( itrB.hasNext() ) {
3685         RefEdge        edgeB     = itrB.next();
3686         HeapRegionNode hrnChildB = edgeB.getDst();
3687         Integer        idChildB  = hrnChildB.getID();
3688
3689         if( idChildA.equals( idChildB ) &&
3690             edgeA.typeAndFieldEquals( edgeB ) ) {
3691
3692           // there is an edge in the right place with the right field,
3693           // but do they have the same attributes?
3694           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3695               edgeA.equalsPreds( edgeB )
3696               ) {
3697             edgeFound = true;
3698           }
3699         }
3700       }
3701
3702       if( !edgeFound ) {
3703         return false;
3704       }
3705     }
3706
3707     return true;
3708   }
3709
3710
3711
3712   // this analysis no longer has the "match anything"
3713   // type which was represented by null
3714   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3715                                              TypeDescriptor td2 ) {
3716     assert td1 != null;
3717     assert td2 != null;
3718
3719     if( td1.isNull() ) {
3720       return td2;
3721     }
3722     if( td2.isNull() ) {
3723       return td1;
3724     }
3725     return typeUtil.mostSpecific( td1, td2 );
3726   }
3727
3728   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3729                                              TypeDescriptor td2,
3730                                              TypeDescriptor td3 ) {
3731
3732     return mostSpecificType( td1,
3733                              mostSpecificType( td2, td3 )
3734                              );
3735   }
3736
3737   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3738                                              TypeDescriptor td2,
3739                                              TypeDescriptor td3,
3740                                              TypeDescriptor td4 ) {
3741
3742     return mostSpecificType( mostSpecificType( td1, td2 ),
3743                              mostSpecificType( td3, td4 )
3744                              );
3745   }
3746
3747   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3748                                     TypeDescriptor possibleChild ) {
3749     assert possibleSuper != null;
3750     assert possibleChild != null;
3751
3752     if( possibleSuper.isNull() ||
3753         possibleChild.isNull() ) {
3754       return true;
3755     }
3756
3757     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3758   }
3759
3760
3761   protected boolean hasMatchingField( HeapRegionNode src,
3762                                       RefEdge        edge ) {
3763
3764     TypeDescriptor tdSrc = src.getType();
3765     assert tdSrc != null;
3766
3767     if( tdSrc.isArray() ) {
3768       TypeDescriptor td = edge.getType();
3769       assert td != null;
3770
3771       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3772       assert tdSrcDeref != null;
3773
3774       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3775         return false;
3776       }
3777
3778       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3779     }
3780
3781     // if it's not a class, it doesn't have any fields to match
3782     if( !tdSrc.isClass() ) {
3783       return false;
3784     }
3785
3786     ClassDescriptor cd = tdSrc.getClassDesc();
3787     while( cd != null ) {
3788       Iterator fieldItr = cd.getFields();
3789
3790       while( fieldItr.hasNext() ) {
3791         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3792
3793         if( fd.getType().equals( edge.getType() ) &&
3794             fd.getSymbol().equals( edge.getField() ) ) {
3795           return true;
3796         }
3797       }
3798
3799       cd = cd.getSuperDesc();
3800     }
3801
3802     // otherwise it is a class with fields
3803     // but we didn't find a match
3804     return false;
3805   }
3806
3807   protected boolean hasMatchingType( RefEdge        edge,
3808                                      HeapRegionNode dst  ) {
3809
3810     // if the region has no type, matches everything
3811     TypeDescriptor tdDst = dst.getType();
3812     assert tdDst != null;
3813
3814     // if the type is not a class or an array, don't
3815     // match because primitives are copied, no aliases
3816     ClassDescriptor cdDst = tdDst.getClassDesc();
3817     if( cdDst == null && !tdDst.isArray() ) {
3818       return false;
3819     }
3820
3821     // if the edge type is null, it matches everything
3822     TypeDescriptor tdEdge = edge.getType();
3823     assert tdEdge != null;
3824
3825     return typeUtil.isSuperorType( tdEdge, tdDst );
3826   }
3827
3828
3829
3830   public void writeGraph( String  graphName,
3831                           boolean writeLabels,
3832                           boolean labelSelect,
3833                           boolean pruneGarbage,
3834                           boolean hideSubsetReachability,
3835                           boolean hideEdgeTaints
3836                           ) throws java.io.IOException {
3837     writeGraph( graphName,
3838                 writeLabels,
3839                 labelSelect,
3840                 pruneGarbage,
3841                 hideSubsetReachability,
3842                 hideEdgeTaints,
3843                 null );
3844   }
3845
3846   public void writeGraph( String       graphName,
3847                           boolean      writeLabels,
3848                           boolean      labelSelect,
3849                           boolean      pruneGarbage,
3850                           boolean      hideSubsetReachability,
3851                           boolean      hideEdgeTaints,
3852                           Set<Integer> callerNodeIDsCopiedToCallee
3853                           ) throws java.io.IOException {
3854
3855     // remove all non-word characters from the graph name so
3856     // the filename and identifier in dot don't cause errors
3857     graphName = graphName.replaceAll( "[\\W]", "" );
3858
3859     BufferedWriter bw =
3860       new BufferedWriter( new FileWriter( graphName+".dot" ) );
3861
3862     bw.write( "digraph "+graphName+" {\n" );
3863
3864
3865     // this is an optional step to form the callee-reachable
3866     // "cut-out" into a DOT cluster for visualization
3867     if( callerNodeIDsCopiedToCallee != null ) {
3868
3869       bw.write( "  subgraph cluster0 {\n" );
3870       bw.write( "    color=blue;\n" );
3871
3872       Iterator i = id2hrn.entrySet().iterator();
3873       while( i.hasNext() ) {
3874         Map.Entry      me  = (Map.Entry)      i.next();
3875         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3876
3877         if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3878           bw.write( "    "+hrn.toString()+
3879                     hrn.toStringDOT( hideSubsetReachability )+
3880                     ";\n" );
3881
3882         }
3883       }
3884
3885       bw.write( "  }\n" );
3886     }
3887
3888
3889     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3890
3891     // then visit every heap region node
3892     Iterator i = id2hrn.entrySet().iterator();
3893     while( i.hasNext() ) {
3894       Map.Entry      me  = (Map.Entry)      i.next();
3895       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3896
3897       // only visit nodes worth writing out--for instance
3898       // not every node at an allocation is referenced
3899       // (think of it as garbage-collected), etc.
3900       if( !pruneGarbage        ||
3901           hrn.isOutOfContext()
3902           ) {
3903
3904         if( !visited.contains( hrn ) ) {
3905           traverseHeapRegionNodes( hrn,
3906                                    bw,
3907                                    null,
3908                                    visited,
3909                                    hideSubsetReachability,
3910                                    hideEdgeTaints,
3911                                    callerNodeIDsCopiedToCallee );
3912         }
3913       }
3914     }
3915
3916     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
3917
3918
3919     // then visit every label node, useful for debugging
3920     if( writeLabels ) {
3921       i = td2vn.entrySet().iterator();
3922       while( i.hasNext() ) {
3923         Map.Entry    me = (Map.Entry)    i.next();
3924         VariableNode vn = (VariableNode) me.getValue();
3925
3926         if( labelSelect ) {
3927           String labelStr = vn.getTempDescriptorString();
3928           if( labelStr.startsWith( "___temp" )     ||
3929               labelStr.startsWith( "___dst" )      ||
3930               labelStr.startsWith( "___srctmp" )   ||
3931               labelStr.startsWith( "___neverused" )
3932               ) {
3933             continue;
3934           }
3935         }
3936
3937         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3938         while( heapRegionsItr.hasNext() ) {
3939           RefEdge        edge = heapRegionsItr.next();
3940           HeapRegionNode hrn  = edge.getDst();
3941
3942           if( !visited.contains( hrn ) ) {
3943             traverseHeapRegionNodes( hrn,
3944                                      bw,
3945                                      null,
3946                                      visited,
3947                                      hideSubsetReachability,
3948                                      hideEdgeTaints,
3949                                      callerNodeIDsCopiedToCallee );
3950           }
3951
3952           bw.write( "  "+vn.toString()+
3953                     " -> "+hrn.toString()+
3954                     edge.toStringDOT( hideSubsetReachability, "" )+
3955                     ";\n" );
3956         }
3957       }
3958     }
3959
3960     bw.write( "}\n" );
3961     bw.close();
3962   }
3963
3964   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
3965                                           BufferedWriter      bw,
3966                                           TempDescriptor      td,
3967                                           Set<HeapRegionNode> visited,
3968                                           boolean             hideSubsetReachability,
3969                                           boolean             hideEdgeTaints,
3970                                           Set<Integer>        callerNodeIDsCopiedToCallee
3971                                           ) throws java.io.IOException {
3972
3973     if( visited.contains( hrn ) ) {
3974       return;
3975     }
3976     visited.add( hrn );
3977
3978     // if we're drawing the callee-view subgraph, only
3979     // write out the node info if it hasn't already been
3980     // written
3981     if( callerNodeIDsCopiedToCallee == null ||
3982         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3983         ) {
3984       bw.write( "  "+hrn.toString()+
3985                 hrn.toStringDOT( hideSubsetReachability )+
3986                 ";\n" );
3987     }
3988
3989     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3990     while( childRegionsItr.hasNext() ) {
3991       RefEdge        edge     = childRegionsItr.next();
3992       HeapRegionNode hrnChild = edge.getDst();
3993
3994       if( callerNodeIDsCopiedToCallee != null &&
3995           (edge.getSrc() instanceof HeapRegionNode) ) {
3996         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3997         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
3998             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3999             ) {
4000           bw.write( "  "+hrn.toString()+
4001                     " -> "+hrnChild.toString()+
4002                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4003                     ";\n");
4004         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
4005                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4006                    ) {
4007           bw.write( "  "+hrn.toString()+
4008                     " -> "+hrnChild.toString()+
4009                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4010                     ";\n");
4011         } else {
4012           bw.write( "  "+hrn.toString()+
4013                     " -> "+hrnChild.toString()+
4014                     edge.toStringDOT( hideSubsetReachability, "" )+
4015                     ";\n");
4016         }
4017       } else {
4018         bw.write( "  "+hrn.toString()+
4019                   " -> "+hrnChild.toString()+
4020                   edge.toStringDOT( hideSubsetReachability, "" )+
4021                   ";\n");
4022       }
4023
4024       traverseHeapRegionNodes( hrnChild,
4025                                bw,
4026                                td,
4027                                visited,
4028                                hideSubsetReachability,
4029                                hideEdgeTaints,
4030                                callerNodeIDsCopiedToCallee );
4031     }
4032   }
4033
4034         public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
4035                         HeapRegionNode hrn2) {
4036
4037                 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4038                 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4039
4040                 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4041                 todoNodes1.add(hrn1);
4042
4043                 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4044                 todoNodes2.add(hrn2);
4045
4046                 // follow links until all reachable nodes have been found
4047                 while (!todoNodes1.isEmpty()) {
4048                         HeapRegionNode hrn = todoNodes1.iterator().next();
4049                         todoNodes1.remove(hrn);
4050                         reachableNodes1.add(hrn);
4051
4052                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4053                         while (edgeItr.hasNext()) {
4054                                 RefEdge edge = edgeItr.next();
4055
4056                                 if (!reachableNodes1.contains(edge.getDst())) {
4057                                         todoNodes1.add(edge.getDst());
4058                                 }
4059                         }
4060                 }
4061
4062                 while (!todoNodes2.isEmpty()) {
4063                         HeapRegionNode hrn = todoNodes2.iterator().next();
4064                         todoNodes2.remove(hrn);
4065                         reachableNodes2.add(hrn);
4066
4067                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4068                         while (edgeItr.hasNext()) {
4069                                 RefEdge edge = edgeItr.next();
4070
4071                                 if (!reachableNodes2.contains(edge.getDst())) {
4072                                         todoNodes2.add(edge.getDst());
4073                                 }
4074                         }
4075                 }
4076
4077                 Set<HeapRegionNode> intersection =
4078                   new HashSet<HeapRegionNode>( reachableNodes1 );
4079
4080                 intersection.retainAll( reachableNodes2 );
4081
4082                 return intersection;
4083         }
4084
4085         public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4086                         HeapRegionNode hrn2) {
4087                 assert hrn1 != null;
4088                 assert hrn2 != null;
4089
4090                 // then get the various tokens for these heap regions
4091                 ReachTuple h1 = ReachTuple.factory(hrn1.getID(),
4092                                 !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false);
4093
4094                 int arity;
4095                 if(hrn1.isSingleObject){
4096                         arity=ReachTuple.ARITY_ONE;
4097                 }else{
4098                         arity=ReachTuple.ARITY_ZEROORMORE;
4099                 }
4100                 ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1
4101                                 .isSingleObject(), arity, false);
4102
4103                 ReachTuple h2 = ReachTuple.factory(hrn2.getID(),
4104                                 !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false);
4105
4106                 if(hrn2.isSingleObject){
4107                         arity=ReachTuple.ARITY_ONE;
4108                 }else{
4109                         arity=ReachTuple.ARITY_ZEROORMORE;
4110                 }
4111
4112                 ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2
4113                                 .isSingleObject(), arity, false);
4114
4115                 // then get the merged beta of all out-going edges from these heap
4116                 // regions
4117
4118                 ReachSet beta1 = ReachSet.factory();
4119                 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4120                 while (itrEdge.hasNext()) {
4121                         RefEdge edge = itrEdge.next();
4122                         beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4123                 }
4124
4125                 ReachSet beta2 = ReachSet.factory();
4126                 itrEdge = hrn2.iteratorToReferencees();
4127                 while (itrEdge.hasNext()) {
4128                         RefEdge edge = itrEdge.next();
4129                         beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4130                 }
4131
4132                 boolean aliasDetected = false;
4133
4134                 // only do this one if they are different tokens
4135                 if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) {
4136                         aliasDetected = true;
4137                 }
4138 //              if (beta1.containsStateWithBoth(h1plus, h2)) {
4139 //                      aliasDetected = true;
4140 //              }
4141                 if (beta1.containsStateWithBoth(h1star, h2)) {
4142                         aliasDetected = true;
4143                 }
4144 //              if (beta1.containsStateWithBoth(h1, h2plus)) {
4145 //                      aliasDetected = true;
4146 //              }
4147 //              if (beta1.containsStateWithBoth(h1plus, h2plus)) {
4148 //                      aliasDetected = true;
4149 //              }
4150 //              if (beta1.containsStateWithBoth(h1star, h2plus)) {
4151 //                      aliasDetected = true;
4152 //              }
4153                 if (beta1.containsStateWithBoth(h1, h2star)) {
4154                         aliasDetected = true;
4155                 }
4156 //              if (beta1.containsStateWithBoth(h1plus, h2star)) {
4157 //                      aliasDetected = true;
4158 //              }
4159                 if (beta1.containsStateWithBoth(h1star, h2star)) {
4160                         aliasDetected = true;
4161                 }
4162
4163                 if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) {
4164                         aliasDetected = true;
4165                 }
4166 //              if (beta2.containsStateWithBoth(h1plus, h2)) {
4167 //                      aliasDetected = true;
4168 //              }
4169                 if (beta2.containsStateWithBoth(h1star, h2)) {
4170                         aliasDetected = true;
4171                 }
4172 //              if (beta2.containsStateWithBoth(h1, h2plus)) {
4173 //                      aliasDetected = true;
4174 //              }
4175 //              if (beta2.containsStateWithBoth(h1plus, h2plus)) {
4176 //                      aliasDetected = true;
4177 //              }
4178 //              if (beta2.containsStateWithBoth(h1star, h2plus)) {
4179 //                      aliasDetected = true;
4180 //              }
4181                 if (beta2.containsStateWithBoth(h1, h2star)) {
4182                         aliasDetected = true;
4183                 }
4184 //              if (beta2.containsStateWithBoth(h1plus, h2star)) {
4185 //                      aliasDetected = true;
4186 //              }
4187                 if (beta2.containsStateWithBoth(h1star, h2star)) {
4188                         aliasDetected = true;
4189                 }
4190
4191                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4192                 if (aliasDetected) {
4193                         common = findCommonReachableNodes(hrn1, hrn2);
4194                         if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) {
4195                                 assert !common.isEmpty();
4196                         }
4197                 }
4198
4199                 return common;
4200         }
4201
4202         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4203                         Integer paramIndex1, Integer paramIndex2) {
4204
4205                 // get parameter's heap regions
4206                 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4207                 VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1);
4208                 RefEdge argEdge1 = argVar1.iteratorToReferencees().next();
4209                 HeapRegionNode hrnParam1 = argEdge1.getDst();
4210
4211                 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4212                 VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2);
4213                 RefEdge argEdge2 = argVar2.iteratorToReferencees().next();
4214                 HeapRegionNode hrnParam2 = argEdge2.getDst();
4215
4216                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4217                 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4218
4219                 return common;
4220         }
4221
4222         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4223                         Integer paramIndex, AllocSite as) {
4224
4225                 // get parameter's heap regions
4226                 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4227                 VariableNode argVar = getVariableNodeFromTemp(paramTemp);
4228                 RefEdge argEdge = argVar.iteratorToReferencees().next();
4229                 HeapRegionNode hrnParam = argEdge.getDst();
4230
4231                 // get summary node
4232                 HeapRegionNode hrnSummary=null;
4233                 if(id2hrn.containsKey(as.getSummary())){
4234                         // if summary node doesn't exist, ignore this case
4235                         hrnSummary = id2hrn.get(as.getSummary());
4236                         assert hrnSummary != null;
4237                 }
4238
4239                 Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
4240                 if(hrnSummary!=null){
4241                         common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4242                 }
4243
4244                 // check for other nodes
4245                 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4246
4247                         assert id2hrn.containsKey(as.getIthOldest(i));
4248                         HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4249                         assert hrnIthOldest != null;
4250
4251                         common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4252
4253                 }
4254
4255                 return common;
4256         }
4257
4258         public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4259                         AllocSite as2) {
4260
4261                 // get summary node 1's alpha
4262                 Integer idSum1 = as1.getSummary();
4263                 HeapRegionNode hrnSum1=null;
4264                 if(id2hrn.containsKey(idSum1)){
4265                         hrnSum1 = id2hrn.get(idSum1);
4266                 }
4267
4268                 // get summary node 2's alpha
4269                 Integer idSum2 = as2.getSummary();
4270                 HeapRegionNode hrnSum2=null;
4271                 if(id2hrn.containsKey(idSum2)){
4272                         hrnSum2 = id2hrn.get(idSum2);
4273                 }
4274
4275                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4276                 if(hrnSum1!=null && hrnSum2!=null){
4277                         common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4278                 }
4279
4280                 // check sum2 against alloc1 nodes
4281                 if(hrnSum2!=null){
4282                 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4283                         Integer idI1 = as1.getIthOldest(i);
4284                         assert id2hrn.containsKey(idI1);
4285                         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4286                         assert hrnI1 != null;
4287                         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4288                 }
4289                 }
4290
4291                 // check sum1 against alloc2 nodes
4292                 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4293                         Integer idI2 = as2.getIthOldest(i);
4294                         assert id2hrn.containsKey(idI2);
4295                         HeapRegionNode hrnI2 = id2hrn.get(idI2);
4296                         assert hrnI2 != null;
4297
4298                         if(hrnSum1!=null){
4299                                 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4300                         }
4301
4302                         // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4303                         for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4304                                 Integer idI1 = as1.getIthOldest(j);
4305
4306                                 // if these are the same site, don't look for the same token, no
4307                                 // alias.
4308                                 // different tokens of the same site could alias together though
4309                                 if (idI1.equals(idI2)) {
4310                                         continue;
4311                                 }
4312
4313                                 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4314
4315                                 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4316                         }
4317                 }
4318
4319                 return common;
4320         }
4321
4322 }