Robust/src/Analysis/Disjoint/ReachGraph.java

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