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                                                   preds
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       rg.writeGraph( "calleeview",
1897                      resolveMethodDebugDOTwriteLabels,
1898                      resolveMethodDebugDOTselectTemps,
1899                      resolveMethodDebugDOTpruneGarbage,
1900                      resolveMethodDebugDOThideSubsetReach,
1901                      resolveMethodDebugDOThideEdgeTaints );
1902     }
1903
1904     return rg;
1905   }
1906
1907   private static Hashtable<String, Integer> oocid2hrnid =
1908     new Hashtable<String, Integer>();
1909
1910
1911   // useful since many graphs writes in the method call debug code
1912   private static boolean resolveMethodDebugDOTwriteLabels     = true;
1913   private static boolean resolveMethodDebugDOTselectTemps     = true;
1914   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
1915   private static boolean resolveMethodDebugDOThideSubsetReach = false;
1916   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
1917
1918
1919
1920   public void
1921     resolveMethodCall( FlatCall     fc,
1922                        FlatMethod   fmCallee,
1923                        ReachGraph   rgCallee,
1924                        Set<Integer> callerNodeIDsCopiedToCallee,
1925                        boolean      writeDebugDOTs
1926                        ) {
1927
1928     if( writeDebugDOTs ) {
1929       rgCallee.writeGraph( "callee",
1930                            resolveMethodDebugDOTwriteLabels,
1931                            resolveMethodDebugDOTselectTemps,
1932                            resolveMethodDebugDOTpruneGarbage,
1933                            resolveMethodDebugDOThideSubsetReach,
1934                            resolveMethodDebugDOThideEdgeTaints );
1935
1936       writeGraph( "caller00In",
1937                   resolveMethodDebugDOTwriteLabels,
1938                   resolveMethodDebugDOTselectTemps,
1939                   resolveMethodDebugDOTpruneGarbage,
1940                   resolveMethodDebugDOThideSubsetReach,
1941                   resolveMethodDebugDOThideEdgeTaints,
1942                   callerNodeIDsCopiedToCallee );
1943     }
1944
1945
1946     // method call transfer function steps:
1947     // 1. Use current callee-reachable heap (CRH) to test callee
1948     //    predicates and mark what will be coming in.
1949     // 2. Wipe CRH out of caller.
1950     // 3. Transplant marked callee parts in:
1951     //    a) bring in nodes
1952     //    b) bring in callee -> callee edges
1953     //    c) resolve out-of-context -> callee edges
1954     //    d) assign return value
1955     // 4. Collapse shadow nodes down
1956     // 5. Global sweep it.
1957
1958
1959     // 1. mark what callee elements have satisfied predicates
1960     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1961       new Hashtable<HeapRegionNode, ExistPredSet>();
1962
1963     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1964       new Hashtable<RefEdge, ExistPredSet>();
1965
1966     Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1967       new Hashtable<ReachState, ExistPredSet>();
1968
1969     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1970       new Hashtable< RefEdge, Set<RefSrcNode> >();
1971
1972     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1973     while( meItr.hasNext() ) {
1974       Map.Entry      me        = (Map.Entry)      meItr.next();
1975       Integer        id        = (Integer)        me.getKey();
1976       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1977
1978       // if a callee element's predicates are satisfied then a set
1979       // of CALLER predicates is returned: they are the predicates
1980       // that the callee element moved into the caller context
1981       // should have, and it is inefficient to find this again later
1982       ExistPredSet predsIfSatis =
1983         hrnCallee.getPreds().isSatisfiedBy( this,
1984                                             callerNodeIDsCopiedToCallee
1985                                             );
1986
1987       if( predsIfSatis != null ) {
1988         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1989       } else {
1990         // otherwise don't bother looking at edges to this node
1991         continue;
1992       }
1993
1994       // since the node is coming over, find out which reach
1995       // states on it should come over, too
1996       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
1997       while( stateItr.hasNext() ) {
1998         ReachState stateCallee = stateItr.next();
1999
2000         predsIfSatis =
2001           stateCallee.getPreds().isSatisfiedBy( this,
2002                                                 callerNodeIDsCopiedToCallee
2003                                                 );
2004         if( predsIfSatis != null ) {
2005           calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2006         }
2007       }
2008
2009       // then look at edges to the node
2010       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2011       while( reItr.hasNext() ) {
2012         RefEdge    reCallee  = reItr.next();
2013         RefSrcNode rsnCallee = reCallee.getSrc();
2014
2015         // (caller local variables to in-context heap regions)
2016         // have an (out-of-context heap region -> in-context heap region)
2017         // abstraction in the callEE, so its true we never need to
2018         // look at a (var node -> heap region) edge in callee to bring
2019         // those over for the call site transfer.  What about (param var->heap region)
2020         // edges in callee? They are dealt with below this loop.
2021         // So, yes, at this point skip (var->region) edges in callee
2022         if( rsnCallee instanceof VariableNode ) {
2023           continue;
2024         }
2025
2026         // first see if the source is out-of-context, and only
2027         // proceed with this edge if we find some caller-context
2028         // matches
2029         HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2030         boolean matchedOutOfContext = false;
2031
2032         if( hrnSrcCallee.isOutOfContext() ) {
2033
2034           assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2035
2036           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2037
2038           // is the target node in the caller?
2039           HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2040           if( hrnDstCaller == null ) {
2041             continue;
2042           }
2043
2044           Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2045           while( reDstItr.hasNext() ) {
2046             // the edge and field (either possibly null) must match
2047             RefEdge reCaller = reDstItr.next();
2048
2049             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
2050                 !reCaller.fieldEquals( reCallee.getField() )
2051                 ) {
2052               continue;
2053             }
2054
2055             RefSrcNode rsnCaller = reCaller.getSrc();
2056             if( rsnCaller instanceof VariableNode ) {
2057
2058               // a variable node matches an OOC region with null type
2059               if( hrnSrcCallee.getType() != null ) {
2060                 continue;
2061               }
2062
2063             } else {
2064               // otherwise types should match
2065               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2066               if( hrnSrcCallee.getType() == null ) {
2067                 if( hrnCallerSrc.getType() != null ) {
2068                   continue;
2069                 }
2070               } else {
2071                 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2072                   continue;
2073                 }
2074               }
2075             }
2076
2077             rsnCallers.add( rsnCaller );
2078             matchedOutOfContext = true;
2079           }
2080
2081           if( !rsnCallers.isEmpty() ) {
2082             calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2083           }
2084         }
2085
2086         if( hrnSrcCallee.isOutOfContext() &&
2087             !matchedOutOfContext ) {
2088           continue;
2089         }
2090
2091         predsIfSatis =
2092           reCallee.getPreds().isSatisfiedBy( this,
2093                                              callerNodeIDsCopiedToCallee
2094                                              );
2095
2096         if( predsIfSatis != null ) {
2097           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2098
2099           // since the edge is coming over, find out which reach
2100           // states on it should come over, too
2101           stateItr = reCallee.getBeta().iterator();
2102           while( stateItr.hasNext() ) {
2103             ReachState stateCallee = stateItr.next();
2104
2105             predsIfSatis =
2106               stateCallee.getPreds().isSatisfiedBy( this,
2107                                                     callerNodeIDsCopiedToCallee
2108                                                     );
2109             if( predsIfSatis != null ) {
2110               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2111             }
2112           }
2113         }
2114       }
2115     }
2116
2117     // test param -> HRN edges, also
2118     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2119
2120       // parameter defined here is the symbol in the callee
2121       TempDescriptor tdParam = fmCallee.getParameter( i );
2122
2123       if( !DisjointAnalysis.shouldAnalysisTrack( tdParam.getType() ) ) {
2124         // skip primitive/immutable parameters
2125         continue;
2126       }
2127
2128       VariableNode vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2129
2130       Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2131       while( reItr.hasNext() ) {
2132         RefEdge reCallee = reItr.next();
2133
2134         ExistPredSet ifDst =
2135           reCallee.getDst().getPreds().isSatisfiedBy( this,
2136                                                       callerNodeIDsCopiedToCallee
2137                                                       );
2138         if( ifDst == null ) {
2139           continue;
2140         }
2141
2142         ExistPredSet predsIfSatis =
2143           reCallee.getPreds().isSatisfiedBy( this,
2144                                              callerNodeIDsCopiedToCallee
2145                                              );
2146         if( predsIfSatis != null ) {
2147           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2148
2149           // since the edge is coming over, find out which reach
2150           // states on it should come over, too
2151           Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2152           while( stateItr.hasNext() ) {
2153             ReachState stateCallee = stateItr.next();
2154
2155             predsIfSatis =
2156               stateCallee.getPreds().isSatisfiedBy( this,
2157                                                     callerNodeIDsCopiedToCallee
2158                                                     );
2159             if( predsIfSatis != null ) {
2160               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2161             }
2162           }
2163
2164         }
2165       }
2166     }
2167
2168
2169
2170
2171     if( writeDebugDOTs ) {
2172       writeGraph( "caller20BeforeWipe",
2173                   resolveMethodDebugDOTwriteLabels,
2174                   resolveMethodDebugDOTselectTemps,
2175                   resolveMethodDebugDOTpruneGarbage,
2176                   resolveMethodDebugDOThideSubsetReach,
2177                   resolveMethodDebugDOThideEdgeTaints );
2178     }
2179
2180
2181     // 2. predicates tested, ok to wipe out caller part
2182     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2183     while( hrnItr.hasNext() ) {
2184       Integer        hrnID     = hrnItr.next();
2185       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2186       assert hrnCaller != null;
2187
2188       // when clearing off nodes, also eliminate variable
2189       // references
2190       wipeOut( hrnCaller, true );
2191     }
2192
2193
2194
2195     if( writeDebugDOTs ) {
2196       writeGraph( "caller30BeforeAddingNodes",
2197                   resolveMethodDebugDOTwriteLabels,
2198                   resolveMethodDebugDOTselectTemps,
2199                   resolveMethodDebugDOTpruneGarbage,
2200                   resolveMethodDebugDOThideSubsetReach,
2201                   resolveMethodDebugDOThideEdgeTaints );
2202     }
2203
2204
2205     // 3. callee elements with satisfied preds come in, note that
2206     //    the mapping of elements satisfied to preds is like this:
2207     //    A callee element EE has preds EEp that are satisfied by
2208     //    some caller element ER.  We bring EE into the caller
2209     //    context as ERee with the preds of ER, namely ERp, which
2210     //    in the following algorithm is the value in the mapping
2211
2212     // 3.a) nodes
2213     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2214     while( satisItr.hasNext() ) {
2215       Map.Entry      me        = (Map.Entry)      satisItr.next();
2216       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2217       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
2218
2219       // TODO: I think its true that the current implementation uses
2220       // the type of the OOC region and the predicates OF THE EDGE from
2221       // it to link everything up in caller context, so that's why we're
2222       // skipping this... maybe that's a sillier way to do it?
2223       if( hrnCallee.isOutOfContext() ) {
2224         continue;
2225       }
2226
2227       AllocSite as = hrnCallee.getAllocSite();
2228       allocSites.add( as );
2229
2230       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2231
2232       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2233       if( hrnCaller == null ) {
2234         hrnCaller =
2235           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
2236                                    hrnCallee.isSingleObject(), // single object?
2237                                    hrnCallee.isNewSummary(),   // summary?
2238                                    hrnCallee.isFlagged(),      // flagged?
2239                                    false,                      // out-of-context?
2240                                    hrnCallee.getType(),        // type
2241                                    hrnCallee.getAllocSite(),   // allocation site
2242                                    toCallerContext( hrnCallee.getInherent(),
2243                                                     calleeStatesSatisfied  ),    // inherent reach
2244                                    null,                       // current reach
2245                                    predsEmpty,                 // predicates
2246                                    hrnCallee.getDescription()  // description
2247                                    );
2248       } else {
2249         assert hrnCaller.isWiped();
2250       }
2251
2252       hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2253                                            calleeStatesSatisfied
2254                                            )
2255                           );
2256
2257       hrnCaller.setPreds( preds );
2258     }
2259
2260
2261
2262     if( writeDebugDOTs ) {
2263       writeGraph( "caller31BeforeAddingEdges",
2264                   resolveMethodDebugDOTwriteLabels,
2265                   resolveMethodDebugDOTselectTemps,
2266                   resolveMethodDebugDOTpruneGarbage,
2267                   resolveMethodDebugDOThideSubsetReach,
2268                   resolveMethodDebugDOThideEdgeTaints );
2269     }
2270
2271
2272     // set these up during the next procedure so after
2273     // the caller has all of its nodes and edges put
2274     // back together we can propagate the callee's
2275     // reach changes backwards into the caller graph
2276     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2277
2278     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2279       new Hashtable<RefEdge, ChangeSet>();
2280
2281
2282     // 3.b) callee -> callee edges AND out-of-context -> callee
2283     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2284     while( satisItr.hasNext() ) {
2285       Map.Entry    me       = (Map.Entry)    satisItr.next();
2286       RefEdge      reCallee = (RefEdge)      me.getKey();
2287       ExistPredSet preds    = (ExistPredSet) me.getValue();
2288
2289       HeapRegionNode hrnDstCallee = reCallee.getDst();
2290       AllocSite      asDst        = hrnDstCallee.getAllocSite();
2291       allocSites.add( asDst );
2292
2293       Integer hrnIDDstShadow =
2294         asDst.getShadowIDfromID( hrnDstCallee.getID() );
2295
2296       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2297       assert hrnDstCaller != null;
2298
2299
2300       RefSrcNode rsnCallee = reCallee.getSrc();
2301
2302       Set<RefSrcNode> rsnCallers =
2303         new HashSet<RefSrcNode>();
2304
2305       Set<RefSrcNode> oocCallers =
2306         calleeEdges2oocCallerSrcMatches.get( reCallee );
2307
2308
2309       if( oocCallers == null ) {
2310         // there are no out-of-context matches, so it's
2311         // either a param/arg var or one in-context heap region
2312         if( rsnCallee instanceof VariableNode ) {
2313           // variable -> node in the callee should only
2314           // come into the caller if its from a param var
2315           VariableNode   vnCallee = (VariableNode) rsnCallee;
2316           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2317           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
2318                                                             tdParam );
2319           if( tdArg == null ) {
2320             // this means the variable isn't a parameter, its local
2321             // to the callee so we ignore it in call site transfer
2322             // shouldn't this NEVER HAPPEN?
2323             assert false;
2324           }
2325
2326           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2327
2328         } else {
2329           // otherwise source is in context, one region
2330           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2331
2332           // translate an in-context node to shadow
2333           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2334           allocSites.add( asSrc );
2335
2336           Integer hrnIDSrcShadow =
2337             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2338
2339           HeapRegionNode hrnSrcCallerShadow =
2340             this.id2hrn.get( hrnIDSrcShadow );
2341
2342           if( hrnSrcCallerShadow == null ) {
2343             hrnSrcCallerShadow =
2344               createNewHeapRegionNode( hrnIDSrcShadow,                // id or null to generate a new one
2345                                        hrnSrcCallee.isSingleObject(), // single object?
2346                                        hrnSrcCallee.isNewSummary(),   // summary?
2347                                        hrnSrcCallee.isFlagged(),      // flagged?
2348                                        false,                         // out-of-context?
2349                                        hrnSrcCallee.getType(),        // type
2350                                        hrnSrcCallee.getAllocSite(),   // allocation site
2351                                        toCallerContext( hrnSrcCallee.getInherent(),
2352                                                         calleeStatesSatisfied ),    // inherent reach
2353                                        toCallerContext( hrnSrcCallee.getAlpha(),
2354                                                         calleeStatesSatisfied ),       // current reach
2355                                        predsEmpty,                    // predicates
2356                                        hrnSrcCallee.getDescription()  // description
2357                                        );
2358           }
2359
2360           rsnCallers.add( hrnSrcCallerShadow );
2361         }
2362
2363       } else {
2364         // otherwise we have a set of out-of-context srcs
2365         // that should NOT be translated to shadow nodes
2366         assert !oocCallers.isEmpty();
2367         rsnCallers.addAll( oocCallers );
2368       }
2369
2370       // now make all caller edges we've identified from
2371       // this callee edge with a satisfied predicate
2372       assert !rsnCallers.isEmpty();
2373       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2374       while( rsnItr.hasNext() ) {
2375         RefSrcNode rsnCaller = rsnItr.next();
2376
2377         RefEdge reCaller = new RefEdge( rsnCaller,
2378                                         hrnDstCaller,
2379                                         reCallee.getType(),
2380                                         reCallee.getField(),
2381                                         toCallerContext( reCallee.getBeta(),
2382                                                          calleeStatesSatisfied ),
2383                                         preds
2384                                         );
2385
2386         ChangeSet cs = ChangeSet.factory();
2387         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2388         while( rsItr.hasNext() ) {
2389           ReachState   state          = rsItr.next();
2390           ExistPredSet predsPreCallee = state.getPreds();
2391
2392           if( state.isEmpty() ) {
2393             continue;
2394           }
2395
2396           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2397           while( predItr.hasNext() ) {
2398             ExistPred pred = predItr.next();
2399             ReachState old = pred.ne_state;
2400
2401             if( old == null ) {
2402               old = rstateEmpty;
2403             }
2404
2405             cs = Canonical.add( cs,
2406                                 ChangeTuple.factory( old,
2407                                                      state
2408                                                      )
2409                                 );
2410           }
2411         }
2412
2413
2414         // look to see if an edge with same field exists
2415         // and merge with it, otherwise just add the edge
2416         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2417                                                          reCallee.getType(),
2418                                                          reCallee.getField()
2419                                                          );
2420         if( edgeExisting != null ) {
2421           edgeExisting.setBeta(
2422                                Canonical.unionORpreds( edgeExisting.getBeta(),
2423                                                 reCaller.getBeta()
2424                                                 )
2425                                );
2426           edgeExisting.setPreds(
2427                                 Canonical.join( edgeExisting.getPreds(),
2428                                                 reCaller.getPreds()
2429                                                 )
2430                                 );
2431
2432           // for reach propagation
2433           if( !cs.isEmpty() ) {
2434             ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
2435             if( csExisting == null ) {
2436               csExisting = ChangeSet.factory();
2437             }
2438             edgePlannedChanges.put( edgeExisting,
2439                                     Canonical.union( csExisting,
2440                                                      cs
2441                                                      )
2442                                     );
2443           }
2444
2445         } else {
2446           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2447
2448           // for reach propagation
2449           if( !cs.isEmpty() ) {
2450             edgesForPropagation.add( reCaller );
2451             assert !edgePlannedChanges.containsKey( reCaller );
2452             edgePlannedChanges.put( reCaller, cs );
2453           }
2454         }
2455       }
2456     }
2457
2458
2459
2460
2461
2462     if( writeDebugDOTs ) {
2463       writeGraph( "caller35BeforeAssignReturnValue",
2464                   resolveMethodDebugDOTwriteLabels,
2465                   resolveMethodDebugDOTselectTemps,
2466                   resolveMethodDebugDOTpruneGarbage,
2467                   resolveMethodDebugDOThideSubsetReach,
2468                   resolveMethodDebugDOThideEdgeTaints );
2469     }
2470
2471
2472
2473     // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2474     // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2475     // EDGES, JUST BRINGING THEM ALL!  It'll work for now, over approximation
2476
2477     // 3.d) handle return value assignment if needed
2478     TempDescriptor returnTemp = fc.getReturnTemp();
2479     if( returnTemp != null &&
2480         DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2481         ) {
2482
2483       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2484       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2485
2486       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2487       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2488       while( reCalleeItr.hasNext() ) {
2489         RefEdge        reCallee     = reCalleeItr.next();
2490         HeapRegionNode hrnDstCallee = reCallee.getDst();
2491
2492         // some edge types are not possible return values when we can
2493         // see what type variable we are assigning it to
2494         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2495           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2496                               reCallee+" for return temp "+returnTemp );
2497           // prune
2498           continue;
2499         }
2500
2501         AllocSite asDst = hrnDstCallee.getAllocSite();
2502         allocSites.add( asDst );
2503
2504         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2505
2506         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2507         if( hrnDstCaller == null ) {
2508           hrnDstCaller =
2509             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
2510                                      hrnDstCallee.isSingleObject(), // single object?
2511                                      hrnDstCallee.isNewSummary(),   // summary?
2512                                      hrnDstCallee.isFlagged(),      // flagged?
2513                                      false,                         // out-of-context?
2514                                      hrnDstCallee.getType(),        // type
2515                                      hrnDstCallee.getAllocSite(),   // allocation site
2516                                      toCallerContext( hrnDstCallee.getInherent(),
2517                                                       calleeStatesSatisfied  ),    // inherent reach
2518                                      toCallerContext( hrnDstCallee.getAlpha(),
2519                                                       calleeStatesSatisfied  ),    // current reach
2520                                      predsTrue,                     // predicates
2521                                      hrnDstCallee.getDescription()  // description
2522                                      );
2523         }
2524
2525         TypeDescriptor tdNewEdge =
2526           mostSpecificType( reCallee.getType(),
2527                             hrnDstCallee.getType(),
2528                             hrnDstCaller.getType()
2529                             );
2530
2531         RefEdge reCaller = new RefEdge( vnLhsCaller,
2532                                         hrnDstCaller,
2533                                         tdNewEdge,
2534                                         null,
2535                                         toCallerContext( reCallee.getBeta(),
2536                                                          calleeStatesSatisfied ),
2537                                         predsTrue
2538                                         );
2539
2540         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2541       }
2542     }
2543
2544
2545
2546     if( writeDebugDOTs ) {
2547       writeGraph( "caller38propagateReach",
2548                   resolveMethodDebugDOTwriteLabels,
2549                   resolveMethodDebugDOTselectTemps,
2550                   resolveMethodDebugDOTpruneGarbage,
2551                   resolveMethodDebugDOThideSubsetReach,
2552                   resolveMethodDebugDOThideEdgeTaints );
2553     }
2554
2555     // propagate callee reachability changes to the rest
2556     // of the caller graph edges
2557     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2558
2559     propagateTokensOverEdges( edgesForPropagation, // source edges
2560                               edgePlannedChanges,  // map src edge to change set
2561                               edgesUpdated );      // list of updated edges
2562
2563     // commit beta' (beta<-betaNew)
2564     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2565     while( edgeItr.hasNext() ) {
2566       edgeItr.next().applyBetaNew();
2567     }
2568
2569
2570
2571
2572
2573
2574     if( writeDebugDOTs ) {
2575       writeGraph( "caller40BeforeShadowMerge",
2576                   resolveMethodDebugDOTwriteLabels,
2577                   resolveMethodDebugDOTselectTemps,
2578                   resolveMethodDebugDOTpruneGarbage,
2579                   resolveMethodDebugDOThideSubsetReach,
2580                   resolveMethodDebugDOThideEdgeTaints );
2581     }
2582
2583
2584     // 4) merge shadow nodes so alloc sites are back to k
2585     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2586     while( asItr.hasNext() ) {
2587       // for each allocation site do the following to merge
2588       // shadow nodes (newest from callee) with any existing
2589       // look for the newest normal and newest shadow "slot"
2590       // not being used, transfer normal to shadow.  Keep
2591       // doing this until there are no more normal nodes, or
2592       // no empty shadow slots: then merge all remaining normal
2593       // nodes into the shadow summary.  Finally, convert all
2594       // shadow to their normal versions.
2595       AllocSite as = asItr.next();
2596       int ageNorm = 0;
2597       int ageShad = 0;
2598       while( ageNorm < allocationDepth &&
2599              ageShad < allocationDepth ) {
2600
2601         // first, are there any normal nodes left?
2602         Integer        idNorm  = as.getIthOldest( ageNorm );
2603         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2604         if( hrnNorm == null ) {
2605           // no, this age of normal node not in the caller graph
2606           ageNorm++;
2607           continue;
2608         }
2609
2610         // yes, a normal node exists, is there an empty shadow
2611         // "slot" to transfer it onto?
2612         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2613         if( !hrnShad.isWiped() ) {
2614           // no, this age of shadow node is not empty
2615           ageShad++;
2616           continue;
2617         }
2618
2619         // yes, this shadow node is empty
2620         transferOnto( hrnNorm, hrnShad );
2621         ageNorm++;
2622         ageShad++;
2623       }
2624
2625       // now, while there are still normal nodes but no shadow
2626       // slots, merge normal nodes into the shadow summary
2627       while( ageNorm < allocationDepth ) {
2628
2629         // first, are there any normal nodes left?
2630         Integer        idNorm  = as.getIthOldest( ageNorm );
2631         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2632         if( hrnNorm == null ) {
2633           // no, this age of normal node not in the caller graph
2634           ageNorm++;
2635           continue;
2636         }
2637
2638         // yes, a normal node exists, so get the shadow summary
2639         HeapRegionNode summShad = getSummaryNode( as, true );
2640         mergeIntoSummary( hrnNorm, summShad );
2641         ageNorm++;
2642       }
2643
2644       // if there is a normal summary, merge it into shadow summary
2645       Integer        idNorm   = as.getSummary();
2646       HeapRegionNode summNorm = id2hrn.get( idNorm );
2647       if( summNorm != null ) {
2648         HeapRegionNode summShad = getSummaryNode( as, true );
2649         mergeIntoSummary( summNorm, summShad );
2650       }
2651
2652       // finally, flip all existing shadow nodes onto the normal
2653       for( int i = 0; i < allocationDepth; ++i ) {
2654         Integer        idShad  = as.getIthOldestShadow( i );
2655         HeapRegionNode hrnShad = id2hrn.get( idShad );
2656         if( hrnShad != null ) {
2657           // flip it
2658           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2659           assert hrnNorm.isWiped();
2660           transferOnto( hrnShad, hrnNorm );
2661         }
2662       }
2663
2664       Integer        idShad   = as.getSummaryShadow();
2665       HeapRegionNode summShad = id2hrn.get( idShad );
2666       if( summShad != null ) {
2667         summNorm = getSummaryNode( as, false );
2668         transferOnto( summShad, summNorm );
2669       }
2670     }
2671
2672
2673     if( writeDebugDOTs ) {
2674       writeGraph( "caller45BeforeUnshadow",
2675                   resolveMethodDebugDOTwriteLabels,
2676                   resolveMethodDebugDOTselectTemps,
2677                   resolveMethodDebugDOTpruneGarbage,
2678                   resolveMethodDebugDOThideSubsetReach,
2679                   resolveMethodDebugDOThideEdgeTaints );
2680     }
2681
2682
2683     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2684     while( itrAllHRNodes.hasNext() ) {
2685       Map.Entry      me  = (Map.Entry)      itrAllHRNodes.next();
2686       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2687
2688       hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2689
2690       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2691       while( itrEdges.hasNext() ) {
2692         RefEdge re = itrEdges.next();
2693         re.setBeta( unshadow( re.getBeta() ) );
2694       }
2695     }
2696
2697
2698
2699     if( writeDebugDOTs ) {
2700       writeGraph( "caller50BeforeGlobalSweep",
2701                   resolveMethodDebugDOTwriteLabels,
2702                   resolveMethodDebugDOTselectTemps,
2703                   resolveMethodDebugDOTpruneGarbage,
2704                   resolveMethodDebugDOThideSubsetReach,
2705                   resolveMethodDebugDOThideEdgeTaints );
2706     }
2707
2708
2709     // 5.
2710     if( !DISABLE_GLOBAL_SWEEP ) {
2711       globalSweep();
2712     }
2713
2714
2715
2716     if( writeDebugDOTs ) {
2717       writeGraph( "caller90AfterTransfer",
2718                   resolveMethodDebugDOTwriteLabels,
2719                   resolveMethodDebugDOTselectTemps,
2720                   resolveMethodDebugDOTpruneGarbage,
2721                   resolveMethodDebugDOThideSubsetReach,
2722                   resolveMethodDebugDOThideEdgeTaints );
2723     }
2724   }
2725
2726
2727
2728   ////////////////////////////////////////////////////
2729   //
2730   //  Abstract garbage collection simply removes
2731   //  heap region nodes that are not mechanically
2732   //  reachable from a root set.  This step is
2733   //  essential for testing node and edge existence
2734   //  predicates efficiently
2735   //
2736   ////////////////////////////////////////////////////
2737   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2738
2739     // calculate a root set, will be different for Java
2740     // version of analysis versus Bamboo version
2741     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2742
2743     // visit every variable in graph while building root
2744     // set, and do iterating on a copy, so we can remove
2745     // dead variables while we're at this
2746     Iterator makeCopyItr = td2vn.entrySet().iterator();
2747     Set      entrysCopy  = new HashSet();
2748     while( makeCopyItr.hasNext() ) {
2749       entrysCopy.add( makeCopyItr.next() );
2750     }
2751
2752     Iterator eItr = entrysCopy.iterator();
2753     while( eItr.hasNext() ) {
2754       Map.Entry      me = (Map.Entry)      eItr.next();
2755       TempDescriptor td = (TempDescriptor) me.getKey();
2756       VariableNode   vn = (VariableNode)   me.getValue();
2757
2758       if( liveSet.contains( td ) ) {
2759         toVisit.add( vn );
2760
2761       } else {
2762         // dead var, remove completely from graph
2763         td2vn.remove( td );
2764         clearRefEdgesFrom( vn, null, null, true );
2765       }
2766     }
2767
2768     // everything visited in a traversal is
2769     // considered abstractly live
2770     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2771
2772     while( !toVisit.isEmpty() ) {
2773       RefSrcNode rsn = toVisit.iterator().next();
2774       toVisit.remove( rsn );
2775       visited.add( rsn );
2776
2777       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2778       while( hrnItr.hasNext() ) {
2779         RefEdge        edge = hrnItr.next();
2780         HeapRegionNode hrn  = edge.getDst();
2781
2782         if( !visited.contains( hrn ) ) {
2783           toVisit.add( hrn );
2784         }
2785       }
2786     }
2787
2788     // get a copy of the set to iterate over because
2789     // we're going to monkey with the graph when we
2790     // identify a garbage node
2791     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2792     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2793     while( hrnItr.hasNext() ) {
2794       hrnAllPrior.add( hrnItr.next() );
2795     }
2796
2797     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2798     while( hrnAllItr.hasNext() ) {
2799       HeapRegionNode hrn = hrnAllItr.next();
2800
2801       if( !visited.contains( hrn ) ) {
2802
2803         // heap region nodes are compared across ReachGraph
2804         // objects by their integer ID, so when discarding
2805         // garbage nodes we must also discard entries in
2806         // the ID -> heap region hashtable.
2807         id2hrn.remove( hrn.getID() );
2808
2809         // RefEdge objects are two-way linked between
2810         // nodes, so when a node is identified as garbage,
2811         // actively clear references to and from it so
2812         // live nodes won't have dangling RefEdge's
2813         wipeOut( hrn, true );
2814
2815         // if we just removed the last node from an allocation
2816         // site, it should be taken out of the ReachGraph's list
2817         AllocSite as = hrn.getAllocSite();
2818         if( !hasNodesOf( as ) ) {
2819           allocSites.remove( as );
2820         }
2821       }
2822     }
2823   }
2824
2825   protected boolean hasNodesOf( AllocSite as ) {
2826     if( id2hrn.containsKey( as.getSummary() ) ) {
2827       return true;
2828     }
2829
2830     for( int i = 0; i < allocationDepth; ++i ) {
2831       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2832         return true;
2833       }
2834     }
2835     return false;
2836   }
2837
2838
2839   ////////////////////////////////////////////////////
2840   //
2841   //  This global sweep is an optional step to prune
2842   //  reachability sets that are not internally
2843   //  consistent with the global graph.  It should be
2844   //  invoked after strong updates or method calls.
2845   //
2846   ////////////////////////////////////////////////////
2847   public void globalSweep() {
2848
2849     // boldB is part of the phase 1 sweep
2850     // it has an in-context table and an out-of-context table
2851     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2852       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2853
2854     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2855       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2856
2857     // visit every heap region to initialize alphaNew and betaNew,
2858     // and make a map of every hrnID to the source nodes it should
2859     // propagate forward from.  In-context flagged hrnID's propagate
2860     // from only the in-context node they name, but out-of-context
2861     // ID's may propagate from several out-of-context nodes
2862     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2863       new Hashtable< Integer, Set<HeapRegionNode> >();
2864
2865     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2866       new Hashtable< Integer, Set<HeapRegionNode> >();
2867
2868
2869     Iterator itrHrns = id2hrn.entrySet().iterator();
2870     while( itrHrns.hasNext() ) {
2871       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2872       Integer        hrnID = (Integer)        me.getKey();
2873       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2874
2875       // assert that this node and incoming edges have clean alphaNew
2876       // and betaNew sets, respectively
2877       assert rsetEmpty.equals( hrn.getAlphaNew() );
2878
2879       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2880       while( itrRers.hasNext() ) {
2881         RefEdge edge = itrRers.next();
2882         assert rsetEmpty.equals( edge.getBetaNew() );
2883       }
2884
2885       // make a mapping of IDs to heap regions they propagate from
2886       if( hrn.isFlagged() ) {
2887         assert !hrn.isOutOfContext();
2888         assert !icID2srcs.containsKey( hrn.getID() );
2889
2890         // in-context flagged node IDs simply propagate from the
2891         // node they name
2892         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2893         srcs.add( hrn );
2894         icID2srcs.put( hrn.getID(), srcs );
2895       }
2896
2897       if( hrn.isOutOfContext() ) {
2898         assert !hrn.isFlagged();
2899
2900         // the reachability states on an out-of-context
2901         // node are not really important (combinations of
2902         // IDs or arity)--what matters is that the states
2903         // specify which nodes this out-of-context node
2904         // stands in for.  For example, if the state [17?, 19*]
2905         // appears on the ooc node, it may serve as a source
2906         // for node 17? and a source for node 19.
2907         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2908         while( stateItr.hasNext() ) {
2909           ReachState state = stateItr.next();
2910
2911           Iterator<ReachTuple> rtItr = state.iterator();
2912           while( rtItr.hasNext() ) {
2913             ReachTuple rt = rtItr.next();
2914             assert rt.isOutOfContext();
2915
2916             Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2917             if( srcs == null ) {
2918               srcs = new HashSet<HeapRegionNode>();
2919             }
2920             srcs.add( hrn );
2921             oocID2srcs.put( rt.getHrnID(), srcs );
2922           }
2923         }
2924       }
2925     }
2926
2927     // calculate boldB for all hrnIDs identified by the above
2928     // node traversal, propagating from every source
2929     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2930
2931       Integer             hrnID;
2932       Set<HeapRegionNode> srcs;
2933       boolean             inContext;
2934
2935       if( !icID2srcs.isEmpty() ) {
2936         Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2937         hrnID = (Integer)             me.getKey();
2938         srcs  = (Set<HeapRegionNode>) me.getValue();
2939         inContext = true;
2940         icID2srcs.remove( hrnID );
2941
2942       } else {
2943         assert !oocID2srcs.isEmpty();
2944
2945         Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2946         hrnID = (Integer)             me.getKey();
2947         srcs  = (Set<HeapRegionNode>) me.getValue();
2948         inContext = false;
2949         oocID2srcs.remove( hrnID );
2950       }
2951
2952
2953       Hashtable<RefEdge, ReachSet> boldB_f =
2954         new Hashtable<RefEdge, ReachSet>();
2955
2956       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2957
2958       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2959       while( hrnItr.hasNext() ) {
2960         HeapRegionNode hrn = hrnItr.next();
2961
2962         assert workSetEdges.isEmpty();
2963
2964         // initial boldB_f constraints
2965         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2966         while( itrRees.hasNext() ) {
2967           RefEdge edge = itrRees.next();
2968
2969           assert !boldB_f.containsKey( edge );
2970           boldB_f.put( edge, edge.getBeta() );
2971
2972           assert !workSetEdges.contains( edge );
2973           workSetEdges.add( edge );
2974         }
2975
2976         // enforce the boldB_f constraint at edges until we reach a fixed point
2977         while( !workSetEdges.isEmpty() ) {
2978           RefEdge edge = workSetEdges.iterator().next();
2979           workSetEdges.remove( edge );
2980
2981           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2982           while( itrPrime.hasNext() ) {
2983             RefEdge edgePrime = itrPrime.next();
2984
2985             ReachSet prevResult   = boldB_f.get( edgePrime );
2986             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2987                                                             edgePrime.getBeta()
2988                                                             );
2989
2990             if( prevResult == null ||
2991                 Canonical.unionORpreds( prevResult,
2992                                         intersection ).size()
2993                 > prevResult.size()
2994                 ) {
2995
2996               if( prevResult == null ) {
2997                 boldB_f.put( edgePrime,
2998                              Canonical.unionORpreds( edgePrime.getBeta(),
2999                                                      intersection
3000                                                      )
3001                              );
3002               } else {
3003                 boldB_f.put( edgePrime,
3004                              Canonical.unionORpreds( prevResult,
3005                                                      intersection
3006                                                      )
3007                              );
3008               }
3009               workSetEdges.add( edgePrime );
3010             }
3011           }
3012         }
3013       }
3014
3015       if( inContext ) {
3016         boldBic.put( hrnID, boldB_f );
3017       } else {
3018         boldBooc.put( hrnID, boldB_f );
3019       }
3020     }
3021
3022
3023     // use boldB to prune hrnIDs from alpha states that are impossible
3024     // and propagate the differences backwards across edges
3025     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3026
3027     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3028       new Hashtable<RefEdge, ChangeSet>();
3029
3030
3031     itrHrns = id2hrn.entrySet().iterator();
3032     while( itrHrns.hasNext() ) {
3033       Map.Entry      me    = (Map.Entry)      itrHrns.next();
3034       Integer        hrnID = (Integer)        me.getKey();
3035       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3036
3037       // out-of-context nodes don't participate in the
3038       // global sweep, they serve as sources for the pass
3039       // performed above
3040       if( hrn.isOutOfContext() ) {
3041         continue;
3042       }
3043
3044       // the inherent states of a region are the exception
3045       // to removal as the global sweep prunes
3046       ReachTuple rtException = ReachTuple.factory( hrnID,
3047                                                    !hrn.isSingleObject(),
3048                                                    ReachTuple.ARITY_ONE,
3049                                                    false // out-of-context
3050                                                    );
3051
3052       ChangeSet cts = ChangeSet.factory();
3053
3054       // mark hrnIDs for removal
3055       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3056       while( stateItr.hasNext() ) {
3057         ReachState stateOld = stateItr.next();
3058
3059         ReachState markedHrnIDs = ReachState.factory();
3060
3061         Iterator<ReachTuple> rtItr = stateOld.iterator();
3062         while( rtItr.hasNext() ) {
3063           ReachTuple rtOld = rtItr.next();
3064
3065           // never remove the inherent hrnID from a flagged region
3066           // because it is trivially satisfied
3067           if( hrn.isFlagged() ) {
3068             if( rtOld == rtException ) {
3069               continue;
3070             }
3071           }
3072
3073           // does boldB allow this hrnID?
3074           boolean foundState = false;
3075           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3076           while( incidentEdgeItr.hasNext() ) {
3077             RefEdge incidentEdge = incidentEdgeItr.next();
3078
3079             Hashtable<RefEdge, ReachSet> B;
3080             if( rtOld.isOutOfContext() ) {
3081               B = boldBooc.get( rtOld.getHrnID() );
3082             } else {
3083
3084
3085               if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
3086                 System.out.println( "\nLooking for "+rtOld );
3087                 writeGraph( "dbgz" );
3088               }
3089
3090
3091               assert id2hrn.containsKey( rtOld.getHrnID() );
3092               B = boldBic.get( rtOld.getHrnID() );
3093             }
3094
3095             if( B != null ) {
3096               ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3097               if( boldB_rtOld_incident != null &&
3098                   boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3099                   ) {
3100                 foundState = true;
3101               }
3102             }
3103           }
3104
3105           if( !foundState ) {
3106             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3107           }
3108         }
3109
3110         // if there is nothing marked, just move on
3111         if( markedHrnIDs.isEmpty() ) {
3112           hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3113                                           stateOld
3114                                           )
3115                            );
3116           continue;
3117         }
3118
3119         // remove all marked hrnIDs and establish a change set that should
3120         // propagate backwards over edges from this node
3121         ReachState statePruned = ReachState.factory();
3122         rtItr = stateOld.iterator();
3123         while( rtItr.hasNext() ) {
3124           ReachTuple rtOld = rtItr.next();
3125
3126           if( !markedHrnIDs.containsTuple( rtOld ) ) {
3127             statePruned = Canonical.add( statePruned, rtOld );
3128           }
3129         }
3130         assert !stateOld.equals( statePruned );
3131
3132         hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3133                                         statePruned
3134                                         )
3135                          );
3136         ChangeTuple ct = ChangeTuple.factory( stateOld,
3137                                               statePruned
3138                                               );
3139         cts = Canonical.add( cts, ct );
3140       }
3141
3142       // throw change tuple set on all incident edges
3143       if( !cts.isEmpty() ) {
3144         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3145         while( incidentEdgeItr.hasNext() ) {
3146           RefEdge incidentEdge = incidentEdgeItr.next();
3147
3148           edgesForPropagation.add( incidentEdge );
3149
3150           if( edgePlannedChanges.get( incidentEdge ) == null ) {
3151             edgePlannedChanges.put( incidentEdge, cts );
3152           } else {
3153             edgePlannedChanges.put(
3154                                    incidentEdge,
3155                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
3156                                                     cts
3157                                                     )
3158                                     );
3159           }
3160         }
3161       }
3162     }
3163
3164     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3165
3166     propagateTokensOverEdges( edgesForPropagation,
3167                               edgePlannedChanges,
3168                               edgesUpdated );
3169
3170     // at the end of the 1st phase reference edges have
3171     // beta, betaNew that correspond to beta and betaR
3172     //
3173     // commit beta<-betaNew, so beta=betaR and betaNew
3174     // will represent the beta' calculation in 2nd phase
3175     //
3176     // commit alpha<-alphaNew because it won't change
3177     HashSet<RefEdge> res = new HashSet<RefEdge>();
3178
3179     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3180     while( nodeItr.hasNext() ) {
3181       HeapRegionNode hrn = nodeItr.next();
3182
3183       // as mentioned above, out-of-context nodes only serve
3184       // as sources of reach states for the sweep, not part
3185       // of the changes
3186       if( hrn.isOutOfContext() ) {
3187         assert hrn.getAlphaNew().equals( rsetEmpty );
3188       } else {
3189         hrn.applyAlphaNew();
3190       }
3191
3192       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3193       while( itrRes.hasNext() ) {
3194         res.add( itrRes.next() );
3195       }
3196     }
3197
3198
3199     // 2nd phase
3200     Iterator<RefEdge> edgeItr = res.iterator();
3201     while( edgeItr.hasNext() ) {
3202       RefEdge        edge = edgeItr.next();
3203       HeapRegionNode hrn  = edge.getDst();
3204
3205       // commit results of last phase
3206       if( edgesUpdated.contains( edge ) ) {
3207         edge.applyBetaNew();
3208       }
3209
3210       // compute intial condition of 2nd phase
3211       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3212                                                hrn.getAlpha()
3213                                                )
3214                        );
3215     }
3216
3217     // every edge in the graph is the initial workset
3218     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3219     while( !edgeWorkSet.isEmpty() ) {
3220       RefEdge edgePrime = edgeWorkSet.iterator().next();
3221       edgeWorkSet.remove( edgePrime );
3222
3223       RefSrcNode rsn = edgePrime.getSrc();
3224       if( !(rsn instanceof HeapRegionNode) ) {
3225         continue;
3226       }
3227       HeapRegionNode hrn = (HeapRegionNode) rsn;
3228
3229       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3230       while( itrEdge.hasNext() ) {
3231         RefEdge edge = itrEdge.next();
3232
3233         ReachSet prevResult = edge.getBetaNew();
3234         assert prevResult != null;
3235
3236         ReachSet intersection =
3237           Canonical.intersection( edge.getBeta(),
3238                                   edgePrime.getBetaNew()
3239                                   );
3240
3241         if( Canonical.unionORpreds( prevResult,
3242                                     intersection
3243                                     ).size()
3244             > prevResult.size()
3245             ) {
3246
3247           edge.setBetaNew(
3248                           Canonical.unionORpreds( prevResult,
3249                                                   intersection
3250                                                   )
3251                            );
3252           edgeWorkSet.add( edge );
3253         }
3254       }
3255     }
3256
3257     // commit beta' (beta<-betaNew)
3258     edgeItr = res.iterator();
3259     while( edgeItr.hasNext() ) {
3260       edgeItr.next().applyBetaNew();
3261     }
3262   }
3263
3264
3265
3266   ////////////////////////////////////////////////////
3267   // high-level merge operations
3268   ////////////////////////////////////////////////////
3269   public void merge_sameMethodContext( ReachGraph rg ) {
3270     // when merging two graphs that abstract the heap
3271     // of the same method context, we just call the
3272     // basic merge operation
3273     merge( rg );
3274   }
3275
3276   public void merge_diffMethodContext( ReachGraph rg ) {
3277     // when merging graphs for abstract heaps in
3278     // different method contexts we should:
3279     // 1) age the allocation sites?
3280     merge( rg );
3281   }
3282
3283   ////////////////////////////////////////////////////
3284   // in merge() and equals() methods the suffix A
3285   // represents the passed in graph and the suffix
3286   // B refers to the graph in this object
3287   // Merging means to take the incoming graph A and
3288   // merge it into B, so after the operation graph B
3289   // is the final result.
3290   ////////////////////////////////////////////////////
3291   protected void merge( ReachGraph rg ) {
3292
3293     if( rg == null ) {
3294       return;
3295     }
3296
3297     mergeNodes     ( rg );
3298     mergeRefEdges  ( rg );
3299     mergeAllocSites( rg );
3300   }
3301
3302   protected void mergeNodes( ReachGraph rg ) {
3303
3304     // start with heap region nodes
3305     Set      sA = rg.id2hrn.entrySet();
3306     Iterator iA = sA.iterator();
3307     while( iA.hasNext() ) {
3308       Map.Entry      meA  = (Map.Entry)      iA.next();
3309       Integer        idA  = (Integer)        meA.getKey();
3310       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3311
3312       // if this graph doesn't have a node the
3313       // incoming graph has, allocate it
3314       if( !id2hrn.containsKey( idA ) ) {
3315         HeapRegionNode hrnB = hrnA.copy();
3316         id2hrn.put( idA, hrnB );
3317
3318       } else {
3319         // otherwise this is a node present in both graphs
3320         // so make the new reachability set a union of the
3321         // nodes' reachability sets
3322         HeapRegionNode hrnB = id2hrn.get( idA );
3323         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3324                                         hrnA.getAlpha()
3325                                         )
3326                        );
3327
3328         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3329                                        hrnA.getPreds()
3330                                        )
3331                        );
3332       }
3333     }
3334
3335     // now add any variable nodes that are in graph B but
3336     // not in A
3337     sA = rg.td2vn.entrySet();
3338     iA = sA.iterator();
3339     while( iA.hasNext() ) {
3340       Map.Entry      meA = (Map.Entry)      iA.next();
3341       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3342       VariableNode   lnA = (VariableNode)   meA.getValue();
3343
3344       // if the variable doesn't exist in B, allocate and add it
3345       VariableNode lnB = getVariableNodeFromTemp( tdA );
3346     }
3347   }
3348
3349   protected void mergeRefEdges( ReachGraph rg ) {
3350
3351     // between heap regions
3352     Set      sA = rg.id2hrn.entrySet();
3353     Iterator iA = sA.iterator();
3354     while( iA.hasNext() ) {
3355       Map.Entry      meA  = (Map.Entry)      iA.next();
3356       Integer        idA  = (Integer)        meA.getKey();
3357       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3358
3359       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3360       while( heapRegionsItrA.hasNext() ) {
3361         RefEdge        edgeA     = heapRegionsItrA.next();
3362         HeapRegionNode hrnChildA = edgeA.getDst();
3363         Integer        idChildA  = hrnChildA.getID();
3364
3365         // at this point we know an edge in graph A exists
3366         // idA -> idChildA, does this exist in B?
3367         assert id2hrn.containsKey( idA );
3368         HeapRegionNode hrnB        = id2hrn.get( idA );
3369         RefEdge        edgeToMerge = null;
3370
3371         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3372         while( heapRegionsItrB.hasNext() &&
3373                edgeToMerge == null          ) {
3374
3375           RefEdge        edgeB     = heapRegionsItrB.next();
3376           HeapRegionNode hrnChildB = edgeB.getDst();
3377           Integer        idChildB  = hrnChildB.getID();
3378
3379           // don't use the RefEdge.equals() here because
3380           // we're talking about existence between graphs,
3381           // not intragraph equal
3382           if( idChildB.equals( idChildA ) &&
3383               edgeB.typeAndFieldEquals( edgeA ) ) {
3384
3385             edgeToMerge = edgeB;
3386           }
3387         }
3388
3389         // if the edge from A was not found in B,
3390         // add it to B.
3391         if( edgeToMerge == null ) {
3392           assert id2hrn.containsKey( idChildA );
3393           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3394           edgeToMerge = edgeA.copy();
3395           edgeToMerge.setSrc( hrnB );
3396           edgeToMerge.setDst( hrnChildB );
3397           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3398         }
3399         // otherwise, the edge already existed in both graphs
3400         // so merge their reachability sets
3401         else {
3402           // just replace this beta set with the union
3403           assert edgeToMerge != null;
3404           edgeToMerge.setBeta(
3405                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3406                                                edgeA.getBeta()
3407                                                )
3408                               );
3409           edgeToMerge.setPreds(
3410                                Canonical.join( edgeToMerge.getPreds(),
3411                                                edgeA.getPreds()
3412                                                )
3413                                );
3414         }
3415       }
3416     }
3417
3418     // and then again from variable nodes
3419     sA = rg.td2vn.entrySet();
3420     iA = sA.iterator();
3421     while( iA.hasNext() ) {
3422       Map.Entry      meA = (Map.Entry)      iA.next();
3423       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3424       VariableNode   vnA = (VariableNode)   meA.getValue();
3425
3426       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3427       while( heapRegionsItrA.hasNext() ) {
3428         RefEdge        edgeA     = heapRegionsItrA.next();
3429         HeapRegionNode hrnChildA = edgeA.getDst();
3430         Integer        idChildA  = hrnChildA.getID();
3431
3432         // at this point we know an edge in graph A exists
3433         // tdA -> idChildA, does this exist in B?
3434         assert td2vn.containsKey( tdA );
3435         VariableNode vnB         = td2vn.get( tdA );
3436         RefEdge      edgeToMerge = null;
3437
3438         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3439         while( heapRegionsItrB.hasNext() &&
3440                edgeToMerge == null          ) {
3441
3442           RefEdge        edgeB     = heapRegionsItrB.next();
3443           HeapRegionNode hrnChildB = edgeB.getDst();
3444           Integer        idChildB  = hrnChildB.getID();
3445
3446           // don't use the RefEdge.equals() here because
3447           // we're talking about existence between graphs
3448           if( idChildB.equals( idChildA ) &&
3449               edgeB.typeAndFieldEquals( edgeA ) ) {
3450
3451             edgeToMerge = edgeB;
3452           }
3453         }
3454
3455         // if the edge from A was not found in B,
3456         // add it to B.
3457         if( edgeToMerge == null ) {
3458           assert id2hrn.containsKey( idChildA );
3459           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3460           edgeToMerge = edgeA.copy();
3461           edgeToMerge.setSrc( vnB );
3462           edgeToMerge.setDst( hrnChildB );
3463           addRefEdge( vnB, hrnChildB, edgeToMerge );
3464         }
3465         // otherwise, the edge already existed in both graphs
3466         // so merge their reachability sets
3467         else {
3468           // just replace this beta set with the union
3469           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3470                                                 edgeA.getBeta()
3471                                                 )
3472                                );
3473           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3474                                                 edgeA.getPreds()
3475                                                 )
3476                                 );
3477         }
3478       }
3479     }
3480   }
3481
3482   protected void mergeAllocSites( ReachGraph rg ) {
3483     allocSites.addAll( rg.allocSites );
3484   }
3485
3486
3487
3488   static boolean dbgEquals = false;
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       if( dbgEquals ) {
3505         System.out.println( "rg is null" );
3506       }
3507       return false;
3508     }
3509
3510     if( !areHeapRegionNodesEqual( rg ) ) {
3511       if( dbgEquals ) {
3512         System.out.println( "hrn not equal" );
3513       }
3514       return false;
3515     }
3516
3517     if( !areVariableNodesEqual( rg ) ) {
3518       if( dbgEquals ) {
3519         System.out.println( "vars not equal" );
3520       }
3521       return false;
3522     }
3523
3524     if( !areRefEdgesEqual( rg ) ) {
3525       if( dbgEquals ) {
3526         System.out.println( "edges not equal" );
3527       }
3528       return false;
3529     }
3530
3531     // if everything is equal up to this point,
3532     // assert that allocSites is also equal--
3533     // this data is redundant but kept for efficiency
3534     assert allocSites.equals( rg.allocSites );
3535
3536     return true;
3537   }
3538
3539
3540   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3541
3542     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3543       return false;
3544     }
3545
3546     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3547       return false;
3548     }
3549
3550     return true;
3551   }
3552
3553   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3554                                                         ReachGraph rgB ) {
3555     Set      sA = rgA.id2hrn.entrySet();
3556     Iterator iA = sA.iterator();
3557     while( iA.hasNext() ) {
3558       Map.Entry      meA  = (Map.Entry)      iA.next();
3559       Integer        idA  = (Integer)        meA.getKey();
3560       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3561
3562       if( !rgB.id2hrn.containsKey( idA ) ) {
3563         return false;
3564       }
3565
3566       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3567       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3568         return false;
3569       }
3570     }
3571
3572     return true;
3573   }
3574
3575   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3576
3577     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3578       return false;
3579     }
3580
3581     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3582       return false;
3583     }
3584
3585     return true;
3586   }
3587
3588   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3589                                                        ReachGraph rgB ) {
3590     Set      sA = rgA.td2vn.entrySet();
3591     Iterator iA = sA.iterator();
3592     while( iA.hasNext() ) {
3593       Map.Entry      meA = (Map.Entry)      iA.next();
3594       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3595
3596       if( !rgB.td2vn.containsKey( tdA ) ) {
3597         return false;
3598       }
3599     }
3600
3601     return true;
3602   }
3603
3604
3605   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3606     if( !areallREinAandBequal( this, rg ) ) {
3607       return false;
3608     }
3609
3610     return true;
3611   }
3612
3613   static protected boolean areallREinAandBequal( ReachGraph rgA,
3614                                                  ReachGraph rgB ) {
3615
3616     // check all the heap region->heap region edges
3617     Set      sA = rgA.id2hrn.entrySet();
3618     Iterator iA = sA.iterator();
3619     while( iA.hasNext() ) {
3620       Map.Entry      meA  = (Map.Entry)      iA.next();
3621       Integer        idA  = (Integer)        meA.getKey();
3622       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3623
3624       // we should have already checked that the same
3625       // heap regions exist in both graphs
3626       assert rgB.id2hrn.containsKey( idA );
3627
3628       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3629         return false;
3630       }
3631
3632       // then check every edge in B for presence in A, starting
3633       // from the same parent HeapRegionNode
3634       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3635
3636       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3637         return false;
3638       }
3639     }
3640
3641     // then check all the variable->heap region edges
3642     sA = rgA.td2vn.entrySet();
3643     iA = sA.iterator();
3644     while( iA.hasNext() ) {
3645       Map.Entry      meA = (Map.Entry)      iA.next();
3646       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3647       VariableNode   vnA = (VariableNode)   meA.getValue();
3648
3649       // we should have already checked that the same
3650       // label nodes exist in both graphs
3651       assert rgB.td2vn.containsKey( tdA );
3652
3653       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3654         return false;
3655       }
3656
3657       // then check every edge in B for presence in A, starting
3658       // from the same parent VariableNode
3659       VariableNode vnB = rgB.td2vn.get( tdA );
3660
3661       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3662         return false;
3663       }
3664     }
3665
3666     return true;
3667   }
3668
3669
3670   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3671                                                   RefSrcNode rnA,
3672                                                   ReachGraph rgB ) {
3673
3674     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3675     while( itrA.hasNext() ) {
3676       RefEdge        edgeA     = itrA.next();
3677       HeapRegionNode hrnChildA = edgeA.getDst();
3678       Integer        idChildA  = hrnChildA.getID();
3679
3680       assert rgB.id2hrn.containsKey( idChildA );
3681
3682       // at this point we know an edge in graph A exists
3683       // rnA -> idChildA, does this exact edge exist in B?
3684       boolean edgeFound = false;
3685
3686       RefSrcNode rnB = null;
3687       if( rnA instanceof HeapRegionNode ) {
3688         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3689         rnB = rgB.id2hrn.get( hrnA.getID() );
3690       } else {
3691         VariableNode vnA = (VariableNode) rnA;
3692         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3693       }
3694
3695       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3696       while( itrB.hasNext() ) {
3697         RefEdge        edgeB     = itrB.next();
3698         HeapRegionNode hrnChildB = edgeB.getDst();
3699         Integer        idChildB  = hrnChildB.getID();
3700
3701         if( idChildA.equals( idChildB ) &&
3702             edgeA.typeAndFieldEquals( edgeB ) ) {
3703
3704           // there is an edge in the right place with the right field,
3705           // but do they have the same attributes?
3706           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3707               edgeA.equalsPreds( edgeB )
3708               ) {
3709             edgeFound = true;
3710           }
3711         }
3712       }
3713
3714       if( !edgeFound ) {
3715         return false;
3716       }
3717     }
3718
3719     return true;
3720   }
3721
3722
3723
3724   // this analysis no longer has the "match anything"
3725   // type which was represented by null
3726   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3727                                              TypeDescriptor td2 ) {
3728     assert td1 != null;
3729     assert td2 != null;
3730
3731     if( td1.isNull() ) {
3732       return td2;
3733     }
3734     if( td2.isNull() ) {
3735       return td1;
3736     }
3737     return typeUtil.mostSpecific( td1, td2 );
3738   }
3739
3740   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3741                                              TypeDescriptor td2,
3742                                              TypeDescriptor td3 ) {
3743
3744     return mostSpecificType( td1,
3745                              mostSpecificType( td2, td3 )
3746                              );
3747   }
3748
3749   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3750                                              TypeDescriptor td2,
3751                                              TypeDescriptor td3,
3752                                              TypeDescriptor td4 ) {
3753
3754     return mostSpecificType( mostSpecificType( td1, td2 ),
3755                              mostSpecificType( td3, td4 )
3756                              );
3757   }
3758
3759   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3760                                     TypeDescriptor possibleChild ) {
3761     assert possibleSuper != null;
3762     assert possibleChild != null;
3763
3764     if( possibleSuper.isNull() ||
3765         possibleChild.isNull() ) {
3766       return true;
3767     }
3768
3769     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3770   }
3771
3772
3773   protected boolean hasMatchingField( HeapRegionNode src,
3774                                       RefEdge        edge ) {
3775
3776     TypeDescriptor tdSrc = src.getType();
3777     assert tdSrc != null;
3778
3779     if( tdSrc.isArray() ) {
3780       TypeDescriptor td = edge.getType();
3781       assert td != null;
3782
3783       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3784       assert tdSrcDeref != null;
3785
3786       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3787         return false;
3788       }
3789
3790       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3791     }
3792
3793     // if it's not a class, it doesn't have any fields to match
3794     if( !tdSrc.isClass() ) {
3795       return false;
3796     }
3797
3798     ClassDescriptor cd = tdSrc.getClassDesc();
3799     while( cd != null ) {
3800       Iterator fieldItr = cd.getFields();
3801
3802       while( fieldItr.hasNext() ) {
3803         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3804
3805         if( fd.getType().equals( edge.getType() ) &&
3806             fd.getSymbol().equals( edge.getField() ) ) {
3807           return true;
3808         }
3809       }
3810
3811       cd = cd.getSuperDesc();
3812     }
3813
3814     // otherwise it is a class with fields
3815     // but we didn't find a match
3816     return false;
3817   }
3818
3819   protected boolean hasMatchingType( RefEdge        edge,
3820                                      HeapRegionNode dst  ) {
3821
3822     // if the region has no type, matches everything
3823     TypeDescriptor tdDst = dst.getType();
3824     assert tdDst != null;
3825
3826     // if the type is not a class or an array, don't
3827     // match because primitives are copied, no aliases
3828     ClassDescriptor cdDst = tdDst.getClassDesc();
3829     if( cdDst == null && !tdDst.isArray() ) {
3830       return false;
3831     }
3832
3833     // if the edge type is null, it matches everything
3834     TypeDescriptor tdEdge = edge.getType();
3835     assert tdEdge != null;
3836
3837     return typeUtil.isSuperorType( tdEdge, tdDst );
3838   }
3839
3840
3841
3842   // the default signature for quick-and-dirty debugging
3843   public void writeGraph( String graphName ) {
3844     writeGraph( graphName,
3845                 true, // write labels
3846                 true, // label select
3847                 true, // prune garbage
3848                 true, // hide subset reachability
3849                 true, // hide edge taints
3850                 null  // in-context boundary
3851                 );
3852   }
3853
3854   public void writeGraph( String  graphName,
3855                           boolean writeLabels,
3856                           boolean labelSelect,
3857                           boolean pruneGarbage,
3858                           boolean hideSubsetReachability,
3859                           boolean hideEdgeTaints
3860                           ) {
3861     writeGraph( graphName,
3862                 writeLabels,
3863                 labelSelect,
3864                 pruneGarbage,
3865                 hideSubsetReachability,
3866                 hideEdgeTaints,
3867                 null );
3868   }
3869
3870   public void writeGraph( String       graphName,
3871                           boolean      writeLabels,
3872                           boolean      labelSelect,
3873                           boolean      pruneGarbage,
3874                           boolean      hideSubsetReachability,
3875                           boolean      hideEdgeTaints,
3876                           Set<Integer> callerNodeIDsCopiedToCallee
3877                           ) {
3878
3879     try {
3880       // remove all non-word characters from the graph name so
3881       // the filename and identifier in dot don't cause errors
3882       graphName = graphName.replaceAll( "[\\W]", "" );
3883
3884       BufferedWriter bw =
3885         new BufferedWriter( new FileWriter( graphName+".dot" ) );
3886
3887       bw.write( "digraph "+graphName+" {\n" );
3888
3889
3890       // this is an optional step to form the callee-reachable
3891       // "cut-out" into a DOT cluster for visualization
3892       if( callerNodeIDsCopiedToCallee != null ) {
3893
3894         bw.write( "  subgraph cluster0 {\n" );
3895         bw.write( "    color=blue;\n" );
3896
3897         Iterator i = id2hrn.entrySet().iterator();
3898         while( i.hasNext() ) {
3899           Map.Entry      me  = (Map.Entry)      i.next();
3900           HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3901
3902           if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3903             bw.write( "    "+hrn.toString()+
3904                       hrn.toStringDOT( hideSubsetReachability )+
3905                       ";\n" );
3906
3907           }
3908         }
3909
3910         bw.write( "  }\n" );
3911       }
3912
3913
3914       Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3915
3916       // then visit every heap region node
3917       Iterator i = id2hrn.entrySet().iterator();
3918       while( i.hasNext() ) {
3919         Map.Entry      me  = (Map.Entry)      i.next();
3920         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3921
3922         // only visit nodes worth writing out--for instance
3923         // not every node at an allocation is referenced
3924         // (think of it as garbage-collected), etc.
3925         if( !pruneGarbage        ||
3926             hrn.isOutOfContext()
3927             ) {
3928
3929           if( !visited.contains( hrn ) ) {
3930             traverseHeapRegionNodes( hrn,
3931                                      bw,
3932                                      null,
3933                                      visited,
3934                                      hideSubsetReachability,
3935                                      hideEdgeTaints,
3936                                      callerNodeIDsCopiedToCallee );
3937           }
3938         }
3939       }
3940
3941       bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
3942
3943
3944       // then visit every label node, useful for debugging
3945       if( writeLabels ) {
3946         i = td2vn.entrySet().iterator();
3947         while( i.hasNext() ) {
3948           Map.Entry    me = (Map.Entry)    i.next();
3949           VariableNode vn = (VariableNode) me.getValue();
3950
3951           if( labelSelect ) {
3952             String labelStr = vn.getTempDescriptorString();
3953             if( labelStr.startsWith( "___temp" )     ||
3954                 labelStr.startsWith( "___dst" )      ||
3955                 labelStr.startsWith( "___srctmp" )   ||
3956                 labelStr.startsWith( "___neverused" )
3957                 ) {
3958               continue;
3959             }
3960           }
3961
3962           Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3963           while( heapRegionsItr.hasNext() ) {
3964             RefEdge        edge = heapRegionsItr.next();
3965             HeapRegionNode hrn  = edge.getDst();
3966
3967             if( !visited.contains( hrn ) ) {
3968               traverseHeapRegionNodes( hrn,
3969                                        bw,
3970                                        null,
3971                                        visited,
3972                                        hideSubsetReachability,
3973                                        hideEdgeTaints,
3974                                        callerNodeIDsCopiedToCallee );
3975             }
3976
3977             bw.write( "  "+vn.toString()+
3978                       " -> "+hrn.toString()+
3979                       edge.toStringDOT( hideSubsetReachability, "" )+
3980                       ";\n" );
3981           }
3982         }
3983       }
3984
3985       bw.write( "}\n" );
3986       bw.close();
3987
3988     } catch( IOException e ) {
3989       throw new Error( "Error writing out DOT graph "+graphName );
3990     }
3991   }
3992
3993   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
3994                                           BufferedWriter      bw,
3995                                           TempDescriptor      td,
3996                                           Set<HeapRegionNode> visited,
3997                                           boolean             hideSubsetReachability,
3998                                           boolean             hideEdgeTaints,
3999                                           Set<Integer>        callerNodeIDsCopiedToCallee
4000                                           ) throws java.io.IOException {
4001
4002     if( visited.contains( hrn ) ) {
4003       return;
4004     }
4005     visited.add( hrn );
4006
4007     // if we're drawing the callee-view subgraph, only
4008     // write out the node info if it hasn't already been
4009     // written
4010     if( callerNodeIDsCopiedToCallee == null ||
4011         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4012         ) {
4013       bw.write( "  "+hrn.toString()+
4014                 hrn.toStringDOT( hideSubsetReachability )+
4015                 ";\n" );
4016     }
4017
4018     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4019     while( childRegionsItr.hasNext() ) {
4020       RefEdge        edge     = childRegionsItr.next();
4021       HeapRegionNode hrnChild = edge.getDst();
4022
4023       if( callerNodeIDsCopiedToCallee != null &&
4024           (edge.getSrc() instanceof HeapRegionNode) ) {
4025         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4026         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
4027             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4028             ) {
4029           bw.write( "  "+hrn.toString()+
4030                     " -> "+hrnChild.toString()+
4031                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4032                     ";\n");
4033         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
4034                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4035                    ) {
4036           bw.write( "  "+hrn.toString()+
4037                     " -> "+hrnChild.toString()+
4038                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4039                     ";\n");
4040         } else {
4041           bw.write( "  "+hrn.toString()+
4042                     " -> "+hrnChild.toString()+
4043                     edge.toStringDOT( hideSubsetReachability, "" )+
4044                     ";\n");
4045         }
4046       } else {
4047         bw.write( "  "+hrn.toString()+
4048                   " -> "+hrnChild.toString()+
4049                   edge.toStringDOT( hideSubsetReachability, "" )+
4050                   ";\n");
4051       }
4052
4053       traverseHeapRegionNodes( hrnChild,
4054                                bw,
4055                                td,
4056                                visited,
4057                                hideSubsetReachability,
4058                                hideEdgeTaints,
4059                                callerNodeIDsCopiedToCallee );
4060     }
4061   }
4062
4063
4064
4065
4066
4067   public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4068
4069     Set<HeapRegionNode> exhibitProofState =
4070       new HashSet<HeapRegionNode>();
4071
4072     Iterator hrnItr = id2hrn.entrySet().iterator();
4073     while( hrnItr.hasNext() ) {
4074       Map.Entry      me  = (Map.Entry) hrnItr.next();
4075       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4076
4077       ReachSet intersection =
4078         Canonical.intersection( proofOfSharing,
4079                                 hrn.getAlpha()
4080                                 );
4081       if( !intersection.isEmpty() ) {
4082         assert !hrn.isOutOfContext();
4083         exhibitProofState.add( hrn );
4084       }
4085     }
4086
4087     return exhibitProofState;
4088   }
4089
4090
4091   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4092                                                    HeapRegionNode hrn2) {
4093     assert hrn1 != null;
4094     assert hrn2 != null;
4095
4096     assert !hrn1.isOutOfContext();
4097     assert !hrn2.isOutOfContext();
4098
4099     assert belongsToThis( hrn1 );
4100     assert belongsToThis( hrn2 );
4101
4102     assert !hrn1.getID().equals( hrn2.getID() );
4103
4104
4105     // then get the various tokens for these heap regions
4106     ReachTuple h1 =
4107       ReachTuple.factory( hrn1.getID(),
4108                           !hrn1.isSingleObject(), // multi?
4109                           ReachTuple.ARITY_ONE,
4110                           false );                // ooc?
4111
4112     ReachTuple h1star = null;
4113     if( !hrn1.isSingleObject() ) {
4114       h1star =
4115         ReachTuple.factory( hrn1.getID(),
4116                             !hrn1.isSingleObject(),
4117                             ReachTuple.ARITY_ZEROORMORE,
4118                             false );
4119     }
4120
4121     ReachTuple h2 =
4122       ReachTuple.factory( hrn2.getID(),
4123                           !hrn2.isSingleObject(),
4124                           ReachTuple.ARITY_ONE,
4125                           false );
4126
4127     ReachTuple h2star = null;
4128     if( !hrn2.isSingleObject() ) {
4129       h2star =
4130         ReachTuple.factory( hrn2.getID(),
4131                             !hrn2.isSingleObject(),
4132                             ReachTuple.ARITY_ZEROORMORE,
4133                             false );
4134     }
4135
4136     // then get the merged beta of all out-going edges from these heap
4137     // regions
4138
4139     ReachSet beta1 = ReachSet.factory();
4140     Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4141     while (itrEdge.hasNext()) {
4142       RefEdge edge = itrEdge.next();
4143       beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4144     }
4145
4146     ReachSet beta2 = ReachSet.factory();
4147     itrEdge = hrn2.iteratorToReferencees();
4148     while (itrEdge.hasNext()) {
4149       RefEdge edge = itrEdge.next();
4150       beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4151     }
4152
4153     ReachSet proofOfSharing = ReachSet.factory();
4154
4155     proofOfSharing =
4156       Canonical.unionORpreds( proofOfSharing,
4157                               beta1.getStatesWithBoth( h1, h2 )
4158                               );
4159     proofOfSharing =
4160       Canonical.unionORpreds( proofOfSharing,
4161                               beta2.getStatesWithBoth( h1, h2 )
4162                               );
4163
4164     if( !hrn1.isSingleObject() ) {
4165       proofOfSharing =
4166         Canonical.unionORpreds( proofOfSharing,
4167                                 beta1.getStatesWithBoth( h1star, h2 )
4168                                 );
4169       proofOfSharing =
4170         Canonical.unionORpreds( proofOfSharing,
4171                                 beta2.getStatesWithBoth( h1star, h2 )
4172                                 );
4173     }
4174
4175     if( !hrn2.isSingleObject() ) {
4176       proofOfSharing =
4177         Canonical.unionORpreds( proofOfSharing,
4178                                 beta1.getStatesWithBoth( h1, h2star )
4179                                 );
4180       proofOfSharing =
4181         Canonical.unionORpreds( proofOfSharing,
4182                                 beta2.getStatesWithBoth( h1, h2star )
4183                                 );
4184     }
4185
4186     if( !hrn1.isSingleObject() &&
4187         !hrn2.isSingleObject()
4188         ) {
4189       proofOfSharing =
4190         Canonical.unionORpreds( proofOfSharing,
4191                                 beta1.getStatesWithBoth( h1star, h2star )
4192                                 );
4193       proofOfSharing =
4194         Canonical.unionORpreds( proofOfSharing,
4195                                 beta2.getStatesWithBoth( h1star, h2star )
4196                                 );
4197     }
4198
4199     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4200     if( !proofOfSharing.isEmpty() ) {
4201       common = findCommonReachableNodes( proofOfSharing );
4202       if( !DISABLE_STRONG_UPDATES &&
4203           !DISABLE_GLOBAL_SWEEP
4204           ) {
4205         assert !common.isEmpty();
4206       }
4207     }
4208
4209     return common;
4210   }
4211
4212   // this version of the above method checks whether there is sharing
4213   // among the objects in a summary node
4214   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4215     assert hrn != null;
4216     assert hrn.isNewSummary();
4217     assert !hrn.isOutOfContext();
4218     assert belongsToThis( hrn );
4219
4220     ReachTuple hstar =
4221       ReachTuple.factory( hrn.getID(),
4222                           true,    // multi
4223                           ReachTuple.ARITY_ZEROORMORE,
4224                           false ); // ooc
4225
4226     // then get the merged beta of all out-going edges from
4227     // this heap region
4228
4229     ReachSet beta = ReachSet.factory();
4230     Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4231     while (itrEdge.hasNext()) {
4232       RefEdge edge = itrEdge.next();
4233       beta = Canonical.unionORpreds(beta, edge.getBeta());
4234     }
4235
4236     ReachSet proofOfSharing = ReachSet.factory();
4237
4238     proofOfSharing =
4239       Canonical.unionORpreds( proofOfSharing,
4240                               beta.getStatesWithBoth( hstar, hstar )
4241                               );
4242
4243     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4244     if( !proofOfSharing.isEmpty() ) {
4245       common = findCommonReachableNodes( proofOfSharing );
4246       if( !DISABLE_STRONG_UPDATES &&
4247           !DISABLE_GLOBAL_SWEEP
4248           ) {
4249         assert !common.isEmpty();
4250       }
4251     }
4252
4253     return common;
4254   }
4255
4256
4257   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4258                                                    Integer paramIndex1,
4259                                                    Integer paramIndex2) {
4260
4261     // get parameter's heap regions
4262     TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4263     assert this.hasVariable( paramTemp1 );
4264     VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4265
4266
4267     if( !(paramVar1.getNumReferencees() == 1) ) {
4268       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp1 );
4269       writeGraph( "whatup" );
4270     }
4271
4272
4273     assert paramVar1.getNumReferencees() == 1;
4274     RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4275     HeapRegionNode hrnParam1 = paramEdge1.getDst();
4276
4277     TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4278     assert this.hasVariable( paramTemp2 );
4279     VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4280
4281     if( !(paramVar2.getNumReferencees() == 1) ) {
4282       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp2 );
4283       writeGraph( "whatup" );
4284     }
4285
4286     assert paramVar2.getNumReferencees() == 1;
4287     RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4288     HeapRegionNode hrnParam2 = paramEdge2.getDst();
4289
4290     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4291     common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4292
4293     return common;
4294   }
4295
4296   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4297                                                    Integer paramIndex,
4298                                                    AllocSite as) {
4299
4300     // get parameter's heap regions
4301     TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4302     assert this.hasVariable( paramTemp );
4303     VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4304     assert paramVar.getNumReferencees() == 1;
4305     RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4306     HeapRegionNode hrnParam = paramEdge.getDst();
4307
4308     // get summary node
4309     HeapRegionNode hrnSummary=null;
4310     if(id2hrn.containsKey(as.getSummary())){
4311       // if summary node doesn't exist, ignore this case
4312       hrnSummary = id2hrn.get(as.getSummary());
4313       assert hrnSummary != null;
4314     }
4315
4316     Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
4317     if(hrnSummary!=null){
4318       common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4319     }
4320
4321     // check for other nodes
4322     for (int i = 0; i < as.getAllocationDepth(); ++i) {
4323
4324       assert id2hrn.containsKey(as.getIthOldest(i));
4325       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4326       assert hrnIthOldest != null;
4327
4328       common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4329
4330     }
4331
4332     return common;
4333   }
4334
4335   public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4336                                                    AllocSite as2) {
4337
4338     // get summary node 1's alpha
4339     Integer idSum1 = as1.getSummary();
4340     HeapRegionNode hrnSum1=null;
4341     if(id2hrn.containsKey(idSum1)){
4342       hrnSum1 = id2hrn.get(idSum1);
4343     }
4344
4345     // get summary node 2's alpha
4346     Integer idSum2 = as2.getSummary();
4347     HeapRegionNode hrnSum2=null;
4348     if(id2hrn.containsKey(idSum2)){
4349       hrnSum2 = id2hrn.get(idSum2);
4350     }
4351
4352     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4353     if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4354       common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4355     }
4356
4357     if(hrnSum1!=null){
4358       // ask if objects from this summary share among each other
4359       common.addAll(mayReachSharedObjects(hrnSum1));
4360     }
4361
4362     // check sum2 against alloc1 nodes
4363     if(hrnSum2!=null){
4364       for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4365         Integer idI1 = as1.getIthOldest(i);
4366         assert id2hrn.containsKey(idI1);
4367         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4368         assert hrnI1 != null;
4369         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4370       }
4371
4372       // also ask if objects from this summary share among each other
4373       common.addAll(mayReachSharedObjects(hrnSum2));
4374     }
4375
4376     // check sum1 against alloc2 nodes
4377     for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4378       Integer idI2 = as2.getIthOldest(i);
4379       assert id2hrn.containsKey(idI2);
4380       HeapRegionNode hrnI2 = id2hrn.get(idI2);
4381       assert hrnI2 != null;
4382
4383       if(hrnSum1!=null){
4384         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4385       }
4386
4387       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4388       for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4389         Integer idI1 = as1.getIthOldest(j);
4390
4391         // if these are the same site, don't look for the same token, no
4392         // alias.
4393         // different tokens of the same site could alias together though
4394         if (idI1.equals(idI2)) {
4395           continue;
4396         }
4397
4398         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4399
4400         common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4401       }
4402     }
4403
4404     return common;
4405   }
4406 }