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