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