Robust/src/Analysis/Disjoint/ReachGraph.java

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