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