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