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