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