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