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