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