Robust/src/Analysis/Disjoint/ReachGraph.java

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