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       = true;
2251   private static boolean resolveMethodDebugDOThideEdgeTaints  = false;
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     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2336     while( meItr.hasNext() ) {
2337       Map.Entry me        = (Map.Entry)meItr.next();
2338       Integer id        = (Integer)        me.getKey();
2339       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2340
2341       // if a callee element's predicates are satisfied then a set
2342       // of CALLER predicates is returned: they are the predicates
2343       // that the callee element moved into the caller context
2344       // should have, and it is inefficient to find this again later
2345       ExistPredSet predsIfSatis =
2346         hrnCallee.getPreds().isSatisfiedBy(this,
2347                                            callerNodeIDsCopiedToCallee
2348                                            );
2349
2350       if( predsIfSatis != null ) {
2351         calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2352       } else {
2353         // otherwise don't bother looking at edges to this node
2354         continue;
2355       }
2356
2357       // since the node is coming over, find out which reach
2358       // states on it should come over, too
2359       assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2360
2361       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2362       while( stateItr.hasNext() ) {
2363         ReachState stateCallee = stateItr.next();
2364
2365         predsIfSatis =
2366           stateCallee.getPreds().isSatisfiedBy(this,
2367                                                callerNodeIDsCopiedToCallee
2368                                                );
2369         if( predsIfSatis != null ) {
2370
2371           Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2372             calleeNode2calleeStatesSatisfied.get(hrnCallee);
2373
2374           if( calleeStatesSatisfied == null ) {
2375             calleeStatesSatisfied =
2376               new Hashtable<ReachState, ExistPredSet>();
2377
2378             calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2379           }
2380
2381           calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2382         }
2383       }
2384
2385       // then look at edges to the node
2386       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2387       while( reItr.hasNext() ) {
2388         RefEdge reCallee  = reItr.next();
2389         RefSrcNode rsnCallee = reCallee.getSrc();
2390
2391         // (caller local variables to in-context heap regions)
2392         // have an (out-of-context heap region -> in-context heap region)
2393         // abstraction in the callEE, so its true we never need to
2394         // look at a (var node -> heap region) edge in callee to bring
2395         // those over for the call site transfer, except for the special
2396         // case of *RETURN var* -> heap region edges.
2397         // What about (param var->heap region)
2398         // edges in callee? They are dealt with below this loop.
2399
2400         if( rsnCallee instanceof VariableNode ) {
2401
2402           // looking for the return-value variable only
2403           VariableNode vnCallee = (VariableNode) rsnCallee;
2404           if( vnCallee.getTempDescriptor() != tdReturn ) {
2405             continue;
2406           }
2407
2408           TempDescriptor returnTemp = fc.getReturnTemp();
2409           if( returnTemp == null ||
2410               !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2411               ) {
2412             continue;
2413           }
2414
2415           // note that the assignment of the return value is to a
2416           // variable in the caller which is out-of-context with
2417           // respect to the callee
2418           VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2419           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2420           rsnCallers.add(vnLhsCaller);
2421           calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2422
2423
2424         } else {
2425           // for HeapRegionNode callee sources...
2426
2427           // first see if the source is out-of-context, and only
2428           // proceed with this edge if we find some caller-context
2429           // matches
2430           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2431           boolean matchedOutOfContext = false;
2432
2433           if( !hrnSrcCallee.isOutOfContext() ) {
2434
2435             predsIfSatis =
2436               hrnSrcCallee.getPreds().isSatisfiedBy(this,
2437                                                     callerNodeIDsCopiedToCallee
2438                                                     );
2439             if( predsIfSatis != null ) {
2440               calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2441             } else {
2442               // otherwise forget this edge
2443               continue;
2444             }
2445
2446           } else {
2447             // hrnSrcCallee is out-of-context
2448
2449             assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2450
2451             Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2452
2453             // is the target node in the caller?
2454             HeapRegionNode hrnDstCaller = this.id2hrn.get(hrnCallee.getID() );
2455             if( hrnDstCaller == null ) {
2456               continue;
2457             }
2458
2459             Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2460             while( reDstItr.hasNext() ) {
2461               // the edge and field (either possibly null) must match
2462               RefEdge reCaller = reDstItr.next();
2463
2464               if( !reCaller.typeEquals(reCallee.getType()  ) ||
2465                   !reCaller.fieldEquals(reCallee.getField() )
2466                   ) {
2467                 continue;
2468               }
2469
2470               RefSrcNode rsnCaller = reCaller.getSrc();
2471               if( rsnCaller instanceof VariableNode ) {
2472
2473                 // a variable node matches an OOC region with null type
2474                 if( hrnSrcCallee.getType() != null ) {
2475                   continue;
2476                 }
2477
2478               } else {
2479                 // otherwise types should match
2480                 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2481                 if( hrnSrcCallee.getType() == null ) {
2482                   if( hrnCallerSrc.getType() != null ) {
2483                     continue;
2484                   }
2485                 } else {
2486                   if( !hrnSrcCallee.getType().equals(hrnCallerSrc.getType() ) ) {
2487                     continue;
2488                   }
2489                 }
2490               }
2491
2492               rsnCallers.add(rsnCaller);
2493               matchedOutOfContext = true;
2494             }
2495
2496             if( !rsnCallers.isEmpty() ) {
2497               calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2498             }
2499           }
2500
2501           if( hrnSrcCallee.isOutOfContext() &&
2502               !matchedOutOfContext ) {
2503             continue;
2504           }
2505         }
2506
2507
2508         predsIfSatis =
2509           reCallee.getPreds().isSatisfiedBy(this,
2510                                             callerNodeIDsCopiedToCallee
2511                                             );
2512
2513         if( predsIfSatis != null ) {
2514           calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2515
2516           // since the edge is coming over, find out which reach
2517           // states on it should come over, too
2518           assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2519
2520           stateItr = reCallee.getBeta().iterator();
2521           while( stateItr.hasNext() ) {
2522             ReachState stateCallee = stateItr.next();
2523
2524             predsIfSatis =
2525               stateCallee.getPreds().isSatisfiedBy(this,
2526                                                    callerNodeIDsCopiedToCallee
2527                                                    );
2528             if( predsIfSatis != null ) {
2529
2530               Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2531                 calleeEdge2calleeStatesSatisfied.get(reCallee);
2532
2533               if( calleeStatesSatisfied == null ) {
2534                 calleeStatesSatisfied =
2535                   new Hashtable<ReachState, ExistPredSet>();
2536
2537                 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2538               }
2539
2540               calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2541             }
2542           }
2543
2544           // since the edge is coming over, find out which taints
2545           // on it should come over, too
2546           assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2547
2548           Iterator<Taint> tItr = reCallee.getTaints().iterator();
2549           while( tItr.hasNext() ) {
2550             Taint tCallee = tItr.next();
2551
2552             predsIfSatis =
2553               tCallee.getPreds().isSatisfiedBy(this,
2554                                                callerNodeIDsCopiedToCallee
2555                                                );
2556             if( predsIfSatis != null ) {
2557
2558               Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2559                 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2560
2561               if( calleeTaintsSatisfied == null ) {
2562                 calleeTaintsSatisfied =
2563                   new Hashtable<Taint, ExistPredSet>();
2564
2565                 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2566               }
2567
2568               calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2569             }
2570           }
2571         }
2572       }
2573     }
2574
2575     if( writeDebugDOTs ) {
2576       writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2577                  resolveMethodDebugDOTwriteLabels,
2578                  resolveMethodDebugDOTselectTemps,
2579                  resolveMethodDebugDOTpruneGarbage,
2580                  resolveMethodDebugDOThideReach,
2581                  resolveMethodDebugDOThideSubsetReach,
2582                  resolveMethodDebugDOThidePreds,
2583                  resolveMethodDebugDOThideEdgeTaints);
2584     }
2585
2586
2587     // 2. predicates tested, ok to wipe out caller part
2588     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2589     while( hrnItr.hasNext() ) {
2590       Integer hrnID     = hrnItr.next();
2591       HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2592       assert hrnCaller != null;
2593
2594       // when clearing off nodes, also eliminate variable
2595       // references
2596       wipeOut(hrnCaller, true);
2597     }
2598
2599     // if we are assigning the return value to something, clobber now
2600     // as part of the wipe
2601     TempDescriptor returnTemp = fc.getReturnTemp();
2602     if( returnTemp != null &&
2603         DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2604         ) {
2605
2606       VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2607       clearRefEdgesFrom(vnLhsCaller, null, null, true);
2608     }
2609
2610
2611
2612
2613     if( writeDebugDOTs ) {
2614       writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2615                  resolveMethodDebugDOTwriteLabels,
2616                  resolveMethodDebugDOTselectTemps,
2617                  resolveMethodDebugDOTpruneGarbage,
2618                  resolveMethodDebugDOThideReach,
2619                  resolveMethodDebugDOThideSubsetReach,
2620                  resolveMethodDebugDOThidePreds,
2621                  resolveMethodDebugDOThideEdgeTaints);
2622     }
2623
2624
2625
2626
2627     // 3. callee elements with satisfied preds come in, note that
2628     //    the mapping of elements satisfied to preds is like this:
2629     //    A callee element EE has preds EEp that are satisfied by
2630     //    some caller element ER.  We bring EE into the caller
2631     //    context as ERee with the preds of ER, namely ERp, which
2632     //    in the following algorithm is the value in the mapping
2633
2634     // 3.a) nodes
2635     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2636     while( satisItr.hasNext() ) {
2637       Map.Entry me        = (Map.Entry)satisItr.next();
2638       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2639       ExistPredSet preds     = (ExistPredSet)   me.getValue();
2640
2641       // TODO: I think its true that the current implementation uses
2642       // the type of the OOC region and the predicates OF THE EDGE from
2643       // it to link everything up in caller context, so that's why we're
2644       // skipping this... maybe that's a sillier way to do it?
2645       if( hrnCallee.isOutOfContext() ) {
2646         continue;
2647       }
2648
2649       AllocSite as = hrnCallee.getAllocSite();
2650       allocSites.add(as);
2651
2652       Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2653
2654       HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2655       if( hrnCaller == null ) {
2656         hrnCaller =
2657           createNewHeapRegionNode(hrnIDshadow,                 // id or null to generate a new one
2658                                   hrnCallee.isSingleObject(),  // single object?
2659                                   hrnCallee.isNewSummary(),    // summary?
2660                                   false,                       // out-of-context?
2661                                   hrnCallee.getType(),         // type
2662                                   hrnCallee.getAllocSite(),    // allocation site
2663                                   toCallerContext(hrnCallee.getInherent(),
2664                                                   calleeNode2calleeStatesSatisfied.get(hrnCallee) ),     // inherent reach
2665                                   null,                        // current reach
2666                                   predsEmpty,                  // predicates
2667                                   hrnCallee.getDescription()   // description
2668                                   );
2669       } else {
2670         assert hrnCaller.isWiped();
2671       }
2672
2673       hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2674                                          calleeNode2calleeStatesSatisfied.get(hrnCallee)
2675                                          )
2676                          );
2677
2678       hrnCaller.setPreds(preds);
2679     }
2680
2681
2682
2683
2684
2685     if( writeDebugDOTs ) {
2686       writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2687                  resolveMethodDebugDOTwriteLabels,
2688                  resolveMethodDebugDOTselectTemps,
2689                  resolveMethodDebugDOTpruneGarbage,
2690                  resolveMethodDebugDOThideReach,
2691                  resolveMethodDebugDOThideSubsetReach,
2692                  resolveMethodDebugDOThidePreds,
2693                  resolveMethodDebugDOThideEdgeTaints);
2694     }
2695
2696
2697     // set these up during the next procedure so after
2698     // the caller has all of its nodes and edges put
2699     // back together we can propagate the callee's
2700     // reach changes backwards into the caller graph
2701     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2702
2703     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2704       new Hashtable<RefEdge, ChangeSet>();
2705
2706
2707     // 3.b) callee -> callee edges AND out-of-context -> callee
2708     //      which includes return temp -> callee edges now, too
2709     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2710     while( satisItr.hasNext() ) {
2711       Map.Entry me       = (Map.Entry)satisItr.next();
2712       RefEdge reCallee = (RefEdge)      me.getKey();
2713       ExistPredSet preds    = (ExistPredSet) me.getValue();
2714
2715       HeapRegionNode hrnDstCallee = reCallee.getDst();
2716       AllocSite asDst        = hrnDstCallee.getAllocSite();
2717       allocSites.add(asDst);
2718
2719       Integer hrnIDDstShadow =
2720         asDst.getShadowIDfromID(hrnDstCallee.getID() );
2721
2722       HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2723       assert hrnDstCaller != null;
2724
2725
2726       RefSrcNode rsnCallee = reCallee.getSrc();
2727
2728       Set<RefSrcNode> rsnCallers =
2729         new HashSet<RefSrcNode>();
2730
2731       Set<RefSrcNode> oocCallers =
2732         calleeEdges2oocCallerSrcMatches.get(reCallee);
2733
2734       if( rsnCallee instanceof HeapRegionNode ) {
2735         HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2736         if( hrnCalleeSrc.isOutOfContext() ) {
2737           assert oocCallers != null;
2738         }
2739       }
2740
2741
2742       if( oocCallers == null ) {
2743         // there are no out-of-context matches, so it's
2744         // either a param/arg var or one in-context heap region
2745         if( rsnCallee instanceof VariableNode ) {
2746           // variable -> node in the callee should only
2747           // come into the caller if its from a param var
2748           VariableNode vnCallee = (VariableNode) rsnCallee;
2749           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2750           TempDescriptor tdArg    = fc.getArgMatchingParam(fmCallee,
2751                                                            tdParam);
2752           if( tdArg == null ) {
2753             // this means the variable isn't a parameter, its local
2754             // to the callee so we ignore it in call site transfer
2755             // shouldn't this NEVER HAPPEN?
2756             assert false;
2757           }
2758
2759           rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2760
2761         } else {
2762           // otherwise source is in context, one region
2763
2764           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2765
2766           // translate an in-context node to shadow
2767           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2768           allocSites.add(asSrc);
2769
2770           Integer hrnIDSrcShadow =
2771             asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2772
2773           HeapRegionNode hrnSrcCallerShadow =
2774             this.id2hrn.get(hrnIDSrcShadow);
2775
2776           assert hrnSrcCallerShadow != null;
2777
2778           rsnCallers.add(hrnSrcCallerShadow);
2779         }
2780
2781       } else {
2782         // otherwise we have a set of out-of-context srcs
2783         // that should NOT be translated to shadow nodes
2784         assert !oocCallers.isEmpty();
2785         rsnCallers.addAll(oocCallers);
2786       }
2787
2788       // now make all caller edges we've identified from
2789       // this callee edge with a satisfied predicate
2790       assert !rsnCallers.isEmpty();
2791       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2792       while( rsnItr.hasNext() ) {
2793         RefSrcNode rsnCaller = rsnItr.next();
2794
2795         RefEdge reCaller = new RefEdge(rsnCaller,
2796                                        hrnDstCaller,
2797                                        reCallee.getType(),
2798                                        reCallee.getField(),
2799                                        toCallerContext(reCallee.getBeta(),
2800                                                        calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2801                                        preds,
2802                                        toCallerContext(reCallee.getTaints(),
2803                                                        calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2804                                        );
2805
2806         ChangeSet cs = ChangeSet.factory();
2807         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2808         while( rsItr.hasNext() ) {
2809           ReachState state          = rsItr.next();
2810           ExistPredSet predsPreCallee = state.getPreds();
2811
2812           if( state.isEmpty() ) {
2813             continue;
2814           }
2815
2816           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2817           while( predItr.hasNext() ) {
2818             ExistPred pred = predItr.next();
2819             ReachState old = pred.ne_state;
2820
2821             if( old == null ) {
2822               old = rstateEmpty;
2823             }
2824
2825             cs = Canonical.add(cs,
2826                                ChangeTuple.factory(old,
2827                                                    state
2828                                                    )
2829                                );
2830           }
2831         }
2832
2833         // we're just going to use the convenient "merge-if-exists"
2834         // edge call below, but still take a separate look if there
2835         // is an existing caller edge to build change sets properly
2836         if( !cs.isEmpty() ) {
2837           RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2838                                                           reCallee.getType(),
2839                                                           reCallee.getField()
2840                                                           );
2841           if( edgeExisting != null ) {
2842             ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2843             if( csExisting == null ) {
2844               csExisting = ChangeSet.factory();
2845             }
2846             edgePlannedChanges.put(edgeExisting,
2847                                    Canonical.union(csExisting,
2848                                                    cs
2849                                                    )
2850                                    );
2851           } else {
2852             edgesForPropagation.add(reCaller);
2853             assert !edgePlannedChanges.containsKey(reCaller);
2854             edgePlannedChanges.put(reCaller, cs);
2855           }
2856         }
2857
2858         // then add new caller edge or merge
2859         addEdgeOrMergeWithExisting(reCaller);
2860       }
2861     }
2862
2863
2864
2865
2866
2867     if( writeDebugDOTs ) {
2868       writeGraph(debugGraphPrefix+"caller38propagateReach",
2869                  resolveMethodDebugDOTwriteLabels,
2870                  resolveMethodDebugDOTselectTemps,
2871                  resolveMethodDebugDOTpruneGarbage,
2872                  resolveMethodDebugDOThideReach,
2873                  resolveMethodDebugDOThideSubsetReach,
2874                  resolveMethodDebugDOThidePreds,
2875                  resolveMethodDebugDOThideEdgeTaints);
2876     }
2877
2878     // propagate callee reachability changes to the rest
2879     // of the caller graph edges
2880     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2881
2882     propagateTokensOverEdges(edgesForPropagation,  // source edges
2883                              edgePlannedChanges,   // map src edge to change set
2884                              edgesUpdated);        // list of updated edges
2885
2886     // commit beta' (beta<-betaNew)
2887     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2888     while( edgeItr.hasNext() ) {
2889       edgeItr.next().applyBetaNew();
2890     }
2891
2892
2893
2894
2895
2896
2897
2898     if( writeDebugDOTs ) {
2899       writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
2900                  resolveMethodDebugDOTwriteLabels,
2901                  resolveMethodDebugDOTselectTemps,
2902                  resolveMethodDebugDOTpruneGarbage,
2903                  resolveMethodDebugDOThideReach,
2904                  resolveMethodDebugDOThideSubsetReach,
2905                  resolveMethodDebugDOThidePreds,
2906                  resolveMethodDebugDOThideEdgeTaints);
2907     }
2908
2909
2910     // 4) merge shadow nodes so alloc sites are back to k
2911     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2912     while( asItr.hasNext() ) {
2913       // for each allocation site do the following to merge
2914       // shadow nodes (newest from callee) with any existing
2915       // look for the newest normal and newest shadow "slot"
2916       // not being used, transfer normal to shadow.  Keep
2917       // doing this until there are no more normal nodes, or
2918       // no empty shadow slots: then merge all remaining normal
2919       // nodes into the shadow summary.  Finally, convert all
2920       // shadow to their normal versions.
2921       AllocSite as = asItr.next();
2922       int ageNorm = 0;
2923       int ageShad = 0;
2924
2925       while( ageNorm < allocationDepth &&
2926              ageShad < allocationDepth ) {
2927
2928         // first, are there any normal nodes left?
2929         Integer idNorm  = as.getIthOldest(ageNorm);
2930         HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2931         if( hrnNorm == null ) {
2932           // no, this age of normal node not in the caller graph
2933           ageNorm++;
2934           continue;
2935         }
2936
2937         // yes, a normal node exists, is there an empty shadow
2938         // "slot" to transfer it onto?
2939         HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
2940         if( !hrnShad.isWiped() ) {
2941           // no, this age of shadow node is not empty
2942           ageShad++;
2943           continue;
2944         }
2945
2946         // yes, this shadow node is empty
2947         transferOnto(hrnNorm, hrnShad);
2948         ageNorm++;
2949         ageShad++;
2950       }
2951
2952       // now, while there are still normal nodes but no shadow
2953       // slots, merge normal nodes into the shadow summary
2954       while( ageNorm < allocationDepth ) {
2955
2956         // first, are there any normal nodes left?
2957         Integer idNorm  = as.getIthOldest(ageNorm);
2958         HeapRegionNode hrnNorm = id2hrn.get(idNorm);
2959         if( hrnNorm == null ) {
2960           // no, this age of normal node not in the caller graph
2961           ageNorm++;
2962           continue;
2963         }
2964
2965         // yes, a normal node exists, so get the shadow summary
2966         HeapRegionNode summShad = getSummaryNode(as, true);
2967         mergeIntoSummary(hrnNorm, summShad);
2968
2969         // now tokens in reachability sets need to age also
2970         Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2971         while( itrAllHRNodes.hasNext() ) {
2972           Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
2973           HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2974
2975           ageTuplesFrom(as, hrnToAge);
2976
2977           Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
2978           while( itrEdges.hasNext() ) {
2979             ageTuplesFrom(as, itrEdges.next() );
2980           }
2981         }
2982
2983         ageNorm++;
2984       }
2985
2986       // if there is a normal summary, merge it into shadow summary
2987       Integer idNorm   = as.getSummary();
2988       HeapRegionNode summNorm = id2hrn.get(idNorm);
2989       if( summNorm != null ) {
2990         HeapRegionNode summShad = getSummaryNode(as, true);
2991         mergeIntoSummary(summNorm, summShad);
2992       }
2993
2994       // finally, flip all existing shadow nodes onto the normal
2995       for( int i = 0; i < allocationDepth; ++i ) {
2996         Integer idShad  = as.getIthOldestShadow(i);
2997         HeapRegionNode hrnShad = id2hrn.get(idShad);
2998         if( hrnShad != null ) {
2999           // flip it
3000           HeapRegionNode hrnNorm = getIthNode(as, i, false);
3001           assert hrnNorm.isWiped();
3002           transferOnto(hrnShad, hrnNorm);
3003         }
3004       }
3005
3006       Integer idShad   = as.getSummaryShadow();
3007       HeapRegionNode summShad = id2hrn.get(idShad);
3008       if( summShad != null ) {
3009         summNorm = getSummaryNode(as, false);
3010         transferOnto(summShad, summNorm);
3011       }
3012     }
3013
3014
3015
3016
3017
3018
3019     if( writeDebugDOTs ) {
3020       writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3021                  resolveMethodDebugDOTwriteLabels,
3022                  resolveMethodDebugDOTselectTemps,
3023                  resolveMethodDebugDOTpruneGarbage,
3024                  resolveMethodDebugDOThideReach,
3025                  resolveMethodDebugDOThideSubsetReach,
3026                  resolveMethodDebugDOThidePreds,
3027                  resolveMethodDebugDOThideEdgeTaints);
3028     }
3029
3030
3031     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3032     while( itrAllHRNodes.hasNext() ) {
3033       Map.Entry me  = (Map.Entry)itrAllHRNodes.next();
3034       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3035
3036       hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3037
3038       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3039       while( itrEdges.hasNext() ) {
3040         RefEdge re = itrEdges.next();
3041         re.setBeta(unshadow(re.getBeta() ) );
3042       }
3043     }
3044
3045
3046
3047
3048     if( writeDebugDOTs ) {
3049       writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3050                  resolveMethodDebugDOTwriteLabels,
3051                  resolveMethodDebugDOTselectTemps,
3052                  resolveMethodDebugDOTpruneGarbage,
3053                  resolveMethodDebugDOThideReach,
3054                  resolveMethodDebugDOThideSubsetReach,
3055                  resolveMethodDebugDOThidePreds,
3056                  resolveMethodDebugDOThideEdgeTaints);
3057     }
3058
3059
3060     // 5.
3061     if( !DISABLE_GLOBAL_SWEEP ) {
3062       globalSweep();
3063     }
3064
3065
3066     if( writeDebugDOTs ) {
3067       writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3068                  resolveMethodDebugDOTwriteLabels,
3069                  resolveMethodDebugDOTselectTemps,
3070                  resolveMethodDebugDOTpruneGarbage,
3071                  resolveMethodDebugDOThideReach,
3072                  resolveMethodDebugDOThideSubsetReach,
3073                  resolveMethodDebugDOThidePreds,
3074                  resolveMethodDebugDOThideEdgeTaints);
3075     }
3076   }
3077
3078
3079
3080   ////////////////////////////////////////////////////
3081   //
3082   //  Abstract garbage collection simply removes
3083   //  heap region nodes that are not mechanically
3084   //  reachable from a root set.  This step is
3085   //  essential for testing node and edge existence
3086   //  predicates efficiently
3087   //
3088   ////////////////////////////////////////////////////
3089   public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3090
3091     // calculate a root set, will be different for Java
3092     // version of analysis versus Bamboo version
3093     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3094
3095     // visit every variable in graph while building root
3096     // set, and do iterating on a copy, so we can remove
3097     // dead variables while we're at this
3098     Iterator makeCopyItr = td2vn.entrySet().iterator();
3099     Set entrysCopy  = new HashSet();
3100     while( makeCopyItr.hasNext() ) {
3101       entrysCopy.add(makeCopyItr.next() );
3102     }
3103
3104     Iterator eItr = entrysCopy.iterator();
3105     while( eItr.hasNext() ) {
3106       Map.Entry me = (Map.Entry)eItr.next();
3107       TempDescriptor td = (TempDescriptor) me.getKey();
3108       VariableNode vn = (VariableNode)   me.getValue();
3109
3110       if( liveSet.contains(td) ) {
3111         toVisit.add(vn);
3112
3113       } else {
3114         // dead var, remove completely from graph
3115         td2vn.remove(td);
3116         clearRefEdgesFrom(vn, null, null, true);
3117       }
3118     }
3119
3120     // everything visited in a traversal is
3121     // considered abstractly live
3122     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3123
3124     while( !toVisit.isEmpty() ) {
3125       RefSrcNode rsn = toVisit.iterator().next();
3126       toVisit.remove(rsn);
3127       visited.add(rsn);
3128
3129       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3130       while( hrnItr.hasNext() ) {
3131         RefEdge edge = hrnItr.next();
3132         HeapRegionNode hrn  = edge.getDst();
3133
3134         if( !visited.contains(hrn) ) {
3135           toVisit.add(hrn);
3136         }
3137       }
3138     }
3139
3140     // get a copy of the set to iterate over because
3141     // we're going to monkey with the graph when we
3142     // identify a garbage node
3143     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3144     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3145     while( hrnItr.hasNext() ) {
3146       hrnAllPrior.add(hrnItr.next() );
3147     }
3148
3149     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3150     while( hrnAllItr.hasNext() ) {
3151       HeapRegionNode hrn = hrnAllItr.next();
3152
3153       if( !visited.contains(hrn) ) {
3154
3155         // heap region nodes are compared across ReachGraph
3156         // objects by their integer ID, so when discarding
3157         // garbage nodes we must also discard entries in
3158         // the ID -> heap region hashtable.
3159         id2hrn.remove(hrn.getID() );
3160
3161         // RefEdge objects are two-way linked between
3162         // nodes, so when a node is identified as garbage,
3163         // actively clear references to and from it so
3164         // live nodes won't have dangling RefEdge's
3165         wipeOut(hrn, true);
3166
3167         // if we just removed the last node from an allocation
3168         // site, it should be taken out of the ReachGraph's list
3169         AllocSite as = hrn.getAllocSite();
3170         if( !hasNodesOf(as) ) {
3171           allocSites.remove(as);
3172         }
3173       }
3174     }
3175   }
3176
3177   protected boolean hasNodesOf(AllocSite as) {
3178     if( id2hrn.containsKey(as.getSummary() ) ) {
3179       return true;
3180     }
3181
3182     for( int i = 0; i < allocationDepth; ++i ) {
3183       if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3184         return true;
3185       }
3186     }
3187     return false;
3188   }
3189
3190
3191   ////////////////////////////////////////////////////
3192   //
3193   //  This global sweep is an optional step to prune
3194   //  reachability sets that are not internally
3195   //  consistent with the global graph.  It should be
3196   //  invoked after strong updates or method calls.
3197   //
3198   ////////////////////////////////////////////////////
3199   public void globalSweep() {
3200
3201     // boldB is part of the phase 1 sweep
3202     // it has an in-context table and an out-of-context table
3203     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3204       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3205
3206     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3207       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3208
3209     // visit every heap region to initialize alphaNew and betaNew,
3210     // and make a map of every hrnID to the source nodes it should
3211     // propagate forward from.  In-context flagged hrnID's propagate
3212     // from only the in-context node they name, but out-of-context
3213     // ID's may propagate from several out-of-context nodes
3214     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3215       new Hashtable< Integer, Set<HeapRegionNode> >();
3216
3217     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3218       new Hashtable< Integer, Set<HeapRegionNode> >();
3219
3220
3221     Iterator itrHrns = id2hrn.entrySet().iterator();
3222     while( itrHrns.hasNext() ) {
3223       Map.Entry me    = (Map.Entry)itrHrns.next();
3224       Integer hrnID = (Integer)        me.getKey();
3225       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3226
3227       // assert that this node and incoming edges have clean alphaNew
3228       // and betaNew sets, respectively
3229       assert rsetEmpty.equals(hrn.getAlphaNew() );
3230
3231       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3232       while( itrRers.hasNext() ) {
3233         RefEdge edge = itrRers.next();
3234         assert rsetEmpty.equals(edge.getBetaNew() );
3235       }
3236
3237       // make a mapping of IDs to heap regions they propagate from
3238       if( hrn.isFlagged() ) {
3239         assert !hrn.isOutOfContext();
3240         assert !icID2srcs.containsKey(hrn.getID() );
3241
3242         // in-context flagged node IDs simply propagate from the
3243         // node they name
3244         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3245         srcs.add(hrn);
3246         icID2srcs.put(hrn.getID(), srcs);
3247       }
3248
3249       if( hrn.isOutOfContext() ) {
3250         assert !hrn.isFlagged();
3251
3252         // the reachability states on an out-of-context
3253         // node are not really important (combinations of
3254         // IDs or arity)--what matters is that the states
3255         // specify which nodes this out-of-context node
3256         // stands in for.  For example, if the state [17?, 19*]
3257         // appears on the ooc node, it may serve as a source
3258         // for node 17? and a source for node 19.
3259         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3260         while( stateItr.hasNext() ) {
3261           ReachState state = stateItr.next();
3262
3263           Iterator<ReachTuple> rtItr = state.iterator();
3264           while( rtItr.hasNext() ) {
3265             ReachTuple rt = rtItr.next();
3266             assert rt.isOutOfContext();
3267
3268             Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3269             if( srcs == null ) {
3270               srcs = new HashSet<HeapRegionNode>();
3271             }
3272             srcs.add(hrn);
3273             oocID2srcs.put(rt.getHrnID(), srcs);
3274           }
3275         }
3276       }
3277     }
3278
3279     // calculate boldB for all hrnIDs identified by the above
3280     // node traversal, propagating from every source
3281     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3282
3283       Integer hrnID;
3284       Set<HeapRegionNode> srcs;
3285       boolean inContext;
3286
3287       if( !icID2srcs.isEmpty() ) {
3288         Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3289         hrnID = (Integer)             me.getKey();
3290         srcs  = (Set<HeapRegionNode>)me.getValue();
3291         inContext = true;
3292         icID2srcs.remove(hrnID);
3293
3294       } else {
3295         assert !oocID2srcs.isEmpty();
3296
3297         Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3298         hrnID = (Integer)             me.getKey();
3299         srcs  = (Set<HeapRegionNode>)me.getValue();
3300         inContext = false;
3301         oocID2srcs.remove(hrnID);
3302       }
3303
3304
3305       Hashtable<RefEdge, ReachSet> boldB_f =
3306         new Hashtable<RefEdge, ReachSet>();
3307
3308       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3309
3310       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3311       while( hrnItr.hasNext() ) {
3312         HeapRegionNode hrn = hrnItr.next();
3313
3314         assert workSetEdges.isEmpty();
3315
3316         // initial boldB_f constraints
3317         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3318         while( itrRees.hasNext() ) {
3319           RefEdge edge = itrRees.next();
3320
3321           assert !boldB_f.containsKey(edge);
3322           boldB_f.put(edge, edge.getBeta() );
3323
3324           assert !workSetEdges.contains(edge);
3325           workSetEdges.add(edge);
3326         }
3327
3328         // enforce the boldB_f constraint at edges until we reach a fixed point
3329         while( !workSetEdges.isEmpty() ) {
3330           RefEdge edge = workSetEdges.iterator().next();
3331           workSetEdges.remove(edge);
3332
3333           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3334           while( itrPrime.hasNext() ) {
3335             RefEdge edgePrime = itrPrime.next();
3336
3337             ReachSet prevResult   = boldB_f.get(edgePrime);
3338             ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3339                                                            edgePrime.getBeta()
3340                                                            );
3341
3342             if( prevResult == null ||
3343                 Canonical.unionORpreds(prevResult,
3344                                        intersection).size()
3345                 > prevResult.size()
3346                 ) {
3347
3348               if( prevResult == null ) {
3349                 boldB_f.put(edgePrime,
3350                             Canonical.unionORpreds(edgePrime.getBeta(),
3351                                                    intersection
3352                                                    )
3353                             );
3354               } else {
3355                 boldB_f.put(edgePrime,
3356                             Canonical.unionORpreds(prevResult,
3357                                                    intersection
3358                                                    )
3359                             );
3360               }
3361               workSetEdges.add(edgePrime);
3362             }
3363           }
3364         }
3365       }
3366
3367       if( inContext ) {
3368         boldBic.put(hrnID, boldB_f);
3369       } else {
3370         boldBooc.put(hrnID, boldB_f);
3371       }
3372     }
3373
3374
3375     // use boldB to prune hrnIDs from alpha states that are impossible
3376     // and propagate the differences backwards across edges
3377     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3378
3379     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3380       new Hashtable<RefEdge, ChangeSet>();
3381
3382
3383     itrHrns = id2hrn.entrySet().iterator();
3384     while( itrHrns.hasNext() ) {
3385       Map.Entry me    = (Map.Entry)itrHrns.next();
3386       Integer hrnID = (Integer)        me.getKey();
3387       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3388
3389       // out-of-context nodes don't participate in the
3390       // global sweep, they serve as sources for the pass
3391       // performed above
3392       if( hrn.isOutOfContext() ) {
3393         continue;
3394       }
3395
3396       // the inherent states of a region are the exception
3397       // to removal as the global sweep prunes
3398       ReachTuple rtException = ReachTuple.factory(hrnID,
3399                                                   !hrn.isSingleObject(),
3400                                                   ReachTuple.ARITY_ONE,
3401                                                   false  // out-of-context
3402                                                   );
3403
3404       ChangeSet cts = ChangeSet.factory();
3405
3406       // mark hrnIDs for removal
3407       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3408       while( stateItr.hasNext() ) {
3409         ReachState stateOld = stateItr.next();
3410
3411         ReachState markedHrnIDs = ReachState.factory();
3412
3413         Iterator<ReachTuple> rtItr = stateOld.iterator();
3414         while( rtItr.hasNext() ) {
3415           ReachTuple rtOld = rtItr.next();
3416
3417           // never remove the inherent hrnID from a flagged region
3418           // because it is trivially satisfied
3419           if( hrn.isFlagged() ) {
3420             if( rtOld == rtException ) {
3421               continue;
3422             }
3423           }
3424
3425           // does boldB allow this hrnID?
3426           boolean foundState = false;
3427           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3428           while( incidentEdgeItr.hasNext() ) {
3429             RefEdge incidentEdge = incidentEdgeItr.next();
3430
3431             Hashtable<RefEdge, ReachSet> B;
3432             if( rtOld.isOutOfContext() ) {
3433               B = boldBooc.get(rtOld.getHrnID() );
3434             } else {
3435
3436               if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3437                 // let symbols not in the graph get pruned
3438                 break;
3439               }
3440
3441               B = boldBic.get(rtOld.getHrnID() );
3442             }
3443
3444             if( B != null ) {
3445               ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3446               if( boldB_rtOld_incident != null &&
3447                   boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3448                   ) {
3449                 foundState = true;
3450               }
3451             }
3452           }
3453
3454           if( !foundState ) {
3455             markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3456           }
3457         }
3458
3459         // if there is nothing marked, just move on
3460         if( markedHrnIDs.isEmpty() ) {
3461           hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3462                                         stateOld
3463                                         )
3464                           );
3465           continue;
3466         }
3467
3468         // remove all marked hrnIDs and establish a change set that should
3469         // propagate backwards over edges from this node
3470         ReachState statePruned = ReachState.factory();
3471         rtItr = stateOld.iterator();
3472         while( rtItr.hasNext() ) {
3473           ReachTuple rtOld = rtItr.next();
3474
3475           if( !markedHrnIDs.containsTuple(rtOld) ) {
3476             statePruned = Canonical.addUpArity(statePruned, rtOld);
3477           }
3478         }
3479         assert !stateOld.equals(statePruned);
3480
3481         hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3482                                       statePruned
3483                                       )
3484                         );
3485         ChangeTuple ct = ChangeTuple.factory(stateOld,
3486                                              statePruned
3487                                              );
3488         cts = Canonical.add(cts, ct);
3489       }
3490
3491       // throw change tuple set on all incident edges
3492       if( !cts.isEmpty() ) {
3493         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3494         while( incidentEdgeItr.hasNext() ) {
3495           RefEdge incidentEdge = incidentEdgeItr.next();
3496
3497           edgesForPropagation.add(incidentEdge);
3498
3499           if( edgePlannedChanges.get(incidentEdge) == null ) {
3500             edgePlannedChanges.put(incidentEdge, cts);
3501           } else {
3502             edgePlannedChanges.put(
3503               incidentEdge,
3504               Canonical.union(edgePlannedChanges.get(incidentEdge),
3505                               cts
3506                               )
3507               );
3508           }
3509         }
3510       }
3511     }
3512
3513     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3514
3515     propagateTokensOverEdges(edgesForPropagation,
3516                              edgePlannedChanges,
3517                              edgesUpdated);
3518
3519     // at the end of the 1st phase reference edges have
3520     // beta, betaNew that correspond to beta and betaR
3521     //
3522     // commit beta<-betaNew, so beta=betaR and betaNew
3523     // will represent the beta' calculation in 2nd phase
3524     //
3525     // commit alpha<-alphaNew because it won't change
3526     HashSet<RefEdge> res = new HashSet<RefEdge>();
3527
3528     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3529     while( nodeItr.hasNext() ) {
3530       HeapRegionNode hrn = nodeItr.next();
3531
3532       // as mentioned above, out-of-context nodes only serve
3533       // as sources of reach states for the sweep, not part
3534       // of the changes
3535       if( hrn.isOutOfContext() ) {
3536         assert hrn.getAlphaNew().equals(rsetEmpty);
3537       } else {
3538         hrn.applyAlphaNew();
3539       }
3540
3541       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3542       while( itrRes.hasNext() ) {
3543         res.add(itrRes.next() );
3544       }
3545     }
3546
3547
3548     // 2nd phase
3549     Iterator<RefEdge> edgeItr = res.iterator();
3550     while( edgeItr.hasNext() ) {
3551       RefEdge edge = edgeItr.next();
3552       HeapRegionNode hrn  = edge.getDst();
3553
3554       // commit results of last phase
3555       if( edgesUpdated.contains(edge) ) {
3556         edge.applyBetaNew();
3557       }
3558
3559       // compute intial condition of 2nd phase
3560       edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3561                                              hrn.getAlpha()
3562                                              )
3563                       );
3564     }
3565
3566     // every edge in the graph is the initial workset
3567     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3568     while( !edgeWorkSet.isEmpty() ) {
3569       RefEdge edgePrime = edgeWorkSet.iterator().next();
3570       edgeWorkSet.remove(edgePrime);
3571
3572       RefSrcNode rsn = edgePrime.getSrc();
3573       if( !(rsn instanceof HeapRegionNode) ) {
3574         continue;
3575       }
3576       HeapRegionNode hrn = (HeapRegionNode) rsn;
3577
3578       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3579       while( itrEdge.hasNext() ) {
3580         RefEdge edge = itrEdge.next();
3581
3582         ReachSet prevResult = edge.getBetaNew();
3583         assert prevResult != null;
3584
3585         ReachSet intersection =
3586           Canonical.intersection(edge.getBeta(),
3587                                  edgePrime.getBetaNew()
3588                                  );
3589
3590         if( Canonical.unionORpreds(prevResult,
3591                                    intersection
3592                                    ).size()
3593             > prevResult.size()
3594             ) {
3595
3596           edge.setBetaNew(
3597             Canonical.unionORpreds(prevResult,
3598                                    intersection
3599                                    )
3600             );
3601           edgeWorkSet.add(edge);
3602         }
3603       }
3604     }
3605
3606     // commit beta' (beta<-betaNew)
3607     edgeItr = res.iterator();
3608     while( edgeItr.hasNext() ) {
3609       edgeItr.next().applyBetaNew();
3610     }
3611   }
3612
3613
3614   // a useful assertion for debugging:
3615   // every in-context tuple on any edge or
3616   // any node should name a node that is
3617   // part of the graph
3618   public boolean inContextTuplesInGraph() {
3619
3620     Iterator hrnItr = id2hrn.entrySet().iterator();
3621     while( hrnItr.hasNext() ) {
3622       Map.Entry me  = (Map.Entry)hrnItr.next();
3623       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3624
3625       {
3626         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3627         while( stateItr.hasNext() ) {
3628           ReachState state = stateItr.next();
3629
3630           Iterator<ReachTuple> rtItr = state.iterator();
3631           while( rtItr.hasNext() ) {
3632             ReachTuple rt = rtItr.next();
3633
3634             if( !rt.isOutOfContext() ) {
3635               if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3636                 System.out.println(rt.getHrnID()+" is missing");
3637                 return false;
3638               }
3639             }
3640           }
3641         }
3642       }
3643
3644       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3645       while( edgeItr.hasNext() ) {
3646         RefEdge edge = edgeItr.next();
3647
3648         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3649         while( stateItr.hasNext() ) {
3650           ReachState state = stateItr.next();
3651
3652           Iterator<ReachTuple> rtItr = state.iterator();
3653           while( rtItr.hasNext() ) {
3654             ReachTuple rt = rtItr.next();
3655
3656             if( !rt.isOutOfContext() ) {
3657               if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3658                 System.out.println(rt.getHrnID()+" is missing");
3659                 return false;
3660               }
3661             }
3662           }
3663         }
3664       }
3665     }
3666
3667     return true;
3668   }
3669
3670
3671   // another useful assertion for debugging
3672   public boolean noEmptyReachSetsInGraph() {
3673
3674     Iterator hrnItr = id2hrn.entrySet().iterator();
3675     while( hrnItr.hasNext() ) {
3676       Map.Entry me  = (Map.Entry)hrnItr.next();
3677       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3678
3679       if( !hrn.isOutOfContext() &&
3680           !hrn.isWiped()        &&
3681           hrn.getAlpha().isEmpty()
3682           ) {
3683         System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3684         return false;
3685       }
3686
3687       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3688       while( edgeItr.hasNext() ) {
3689         RefEdge edge = edgeItr.next();
3690
3691         if( edge.getBeta().isEmpty() ) {
3692           System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3693           return false;
3694         }
3695       }
3696     }
3697
3698     return true;
3699   }
3700
3701
3702   public boolean everyReachStateWTrue() {
3703
3704     Iterator hrnItr = id2hrn.entrySet().iterator();
3705     while( hrnItr.hasNext() ) {
3706       Map.Entry me  = (Map.Entry)hrnItr.next();
3707       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3708
3709       {
3710         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3711         while( stateItr.hasNext() ) {
3712           ReachState state = stateItr.next();
3713
3714           if( !state.getPreds().equals(predsTrue) ) {
3715             return false;
3716           }
3717         }
3718       }
3719
3720       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3721       while( edgeItr.hasNext() ) {
3722         RefEdge edge = edgeItr.next();
3723
3724         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3725         while( stateItr.hasNext() ) {
3726           ReachState state = stateItr.next();
3727
3728           if( !state.getPreds().equals(predsTrue) ) {
3729             return false;
3730           }
3731         }
3732       }
3733     }
3734
3735     return true;
3736   }
3737
3738
3739
3740
3741   ////////////////////////////////////////////////////
3742   // in merge() and equals() methods the suffix A
3743   // represents the passed in graph and the suffix
3744   // B refers to the graph in this object
3745   // Merging means to take the incoming graph A and
3746   // merge it into B, so after the operation graph B
3747   // is the final result.
3748   ////////////////////////////////////////////////////
3749   protected void merge(ReachGraph rg) {
3750
3751     if( rg == null ) {
3752       return;
3753     }
3754
3755     mergeNodes(rg);
3756     mergeRefEdges(rg);
3757     mergeAllocSites(rg);
3758     mergeInaccessibleVars(rg);
3759   }
3760
3761   protected void mergeNodes(ReachGraph rg) {
3762
3763     // start with heap region nodes
3764     Set sA = rg.id2hrn.entrySet();
3765     Iterator iA = sA.iterator();
3766     while( iA.hasNext() ) {
3767       Map.Entry meA  = (Map.Entry)iA.next();
3768       Integer idA  = (Integer)        meA.getKey();
3769       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3770
3771       // if this graph doesn't have a node the
3772       // incoming graph has, allocate it
3773       if( !id2hrn.containsKey(idA) ) {
3774         HeapRegionNode hrnB = hrnA.copy();
3775         id2hrn.put(idA, hrnB);
3776
3777       } else {
3778         // otherwise this is a node present in both graphs
3779         // so make the new reachability set a union of the
3780         // nodes' reachability sets
3781         HeapRegionNode hrnB = id2hrn.get(idA);
3782         hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3783                                              hrnA.getAlpha()
3784                                              )
3785                       );
3786
3787         hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3788                                      hrnA.getPreds()
3789                                      )
3790                       );
3791
3792
3793
3794         if( !hrnA.equals(hrnB) ) {
3795           rg.writeGraph("graphA");
3796           this.writeGraph("graphB");
3797           throw new Error("flagged not matching");
3798         }
3799
3800
3801
3802       }
3803     }
3804
3805     // now add any variable nodes that are in graph B but
3806     // not in A
3807     sA = rg.td2vn.entrySet();
3808     iA = sA.iterator();
3809     while( iA.hasNext() ) {
3810       Map.Entry meA = (Map.Entry)iA.next();
3811       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3812       VariableNode lnA = (VariableNode)   meA.getValue();
3813
3814       // if the variable doesn't exist in B, allocate and add it
3815       VariableNode lnB = getVariableNodeFromTemp(tdA);
3816     }
3817   }
3818
3819   protected void mergeRefEdges(ReachGraph rg) {
3820
3821     // between heap regions
3822     Set sA = rg.id2hrn.entrySet();
3823     Iterator iA = sA.iterator();
3824     while( iA.hasNext() ) {
3825       Map.Entry meA  = (Map.Entry)iA.next();
3826       Integer idA  = (Integer)        meA.getKey();
3827       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3828
3829       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3830       while( heapRegionsItrA.hasNext() ) {
3831         RefEdge edgeA     = heapRegionsItrA.next();
3832         HeapRegionNode hrnChildA = edgeA.getDst();
3833         Integer idChildA  = hrnChildA.getID();
3834
3835         // at this point we know an edge in graph A exists
3836         // idA -> idChildA, does this exist in B?
3837         assert id2hrn.containsKey(idA);
3838         HeapRegionNode hrnB        = id2hrn.get(idA);
3839         RefEdge edgeToMerge = null;
3840
3841         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3842         while( heapRegionsItrB.hasNext() &&
3843                edgeToMerge == null          ) {
3844
3845           RefEdge edgeB     = heapRegionsItrB.next();
3846           HeapRegionNode hrnChildB = edgeB.getDst();
3847           Integer idChildB  = hrnChildB.getID();
3848
3849           // don't use the RefEdge.equals() here because
3850           // we're talking about existence between graphs,
3851           // not intragraph equal
3852           if( idChildB.equals(idChildA) &&
3853               edgeB.typeAndFieldEquals(edgeA) ) {
3854
3855             edgeToMerge = edgeB;
3856           }
3857         }
3858
3859         // if the edge from A was not found in B,
3860         // add it to B.
3861         if( edgeToMerge == null ) {
3862           assert id2hrn.containsKey(idChildA);
3863           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3864           edgeToMerge = edgeA.copy();
3865           edgeToMerge.setSrc(hrnB);
3866           edgeToMerge.setDst(hrnChildB);
3867           addRefEdge(hrnB, hrnChildB, edgeToMerge);
3868         }
3869         // otherwise, the edge already existed in both graphs
3870         // so merge their reachability sets
3871         else {
3872           // just replace this beta set with the union
3873           assert edgeToMerge != null;
3874           edgeToMerge.setBeta(
3875             Canonical.unionORpreds(edgeToMerge.getBeta(),
3876                                    edgeA.getBeta()
3877                                    )
3878             );
3879           edgeToMerge.setPreds(
3880             Canonical.join(edgeToMerge.getPreds(),
3881                            edgeA.getPreds()
3882                            )
3883             );
3884           edgeToMerge.setTaints(
3885             Canonical.union(edgeToMerge.getTaints(),
3886                             edgeA.getTaints()
3887                             )
3888             );
3889         }
3890       }
3891     }
3892
3893     // and then again from variable nodes
3894     sA = rg.td2vn.entrySet();
3895     iA = sA.iterator();
3896     while( iA.hasNext() ) {
3897       Map.Entry meA = (Map.Entry)iA.next();
3898       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3899       VariableNode vnA = (VariableNode)   meA.getValue();
3900
3901       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3902       while( heapRegionsItrA.hasNext() ) {
3903         RefEdge edgeA     = heapRegionsItrA.next();
3904         HeapRegionNode hrnChildA = edgeA.getDst();
3905         Integer idChildA  = hrnChildA.getID();
3906
3907         // at this point we know an edge in graph A exists
3908         // tdA -> idChildA, does this exist in B?
3909         assert td2vn.containsKey(tdA);
3910         VariableNode vnB         = td2vn.get(tdA);
3911         RefEdge edgeToMerge = null;
3912
3913         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3914         while( heapRegionsItrB.hasNext() &&
3915                edgeToMerge == null          ) {
3916
3917           RefEdge edgeB     = heapRegionsItrB.next();
3918           HeapRegionNode hrnChildB = edgeB.getDst();
3919           Integer idChildB  = hrnChildB.getID();
3920
3921           // don't use the RefEdge.equals() here because
3922           // we're talking about existence between graphs
3923           if( idChildB.equals(idChildA) &&
3924               edgeB.typeAndFieldEquals(edgeA) ) {
3925
3926             edgeToMerge = edgeB;
3927           }
3928         }
3929
3930         // if the edge from A was not found in B,
3931         // add it to B.
3932         if( edgeToMerge == null ) {
3933           assert id2hrn.containsKey(idChildA);
3934           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3935           edgeToMerge = edgeA.copy();
3936           edgeToMerge.setSrc(vnB);
3937           edgeToMerge.setDst(hrnChildB);
3938           addRefEdge(vnB, hrnChildB, edgeToMerge);
3939         }
3940         // otherwise, the edge already existed in both graphs
3941         // so merge their reachability sets
3942         else {
3943           // just replace this beta set with the union
3944           edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
3945                                                      edgeA.getBeta()
3946                                                      )
3947                               );
3948           edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
3949                                               edgeA.getPreds()
3950                                               )
3951                                );
3952           edgeToMerge.setTaints(
3953             Canonical.union(edgeToMerge.getTaints(),
3954                             edgeA.getTaints()
3955                             )
3956             );
3957         }
3958       }
3959     }
3960   }
3961
3962   protected void mergeAllocSites(ReachGraph rg) {
3963     allocSites.addAll(rg.allocSites);
3964   }
3965
3966   protected void mergeInaccessibleVars(ReachGraph rg) {
3967     inaccessibleVars.addAll(rg.inaccessibleVars);
3968   }
3969
3970
3971
3972   static boolean dbgEquals = false;
3973
3974
3975   // it is necessary in the equals() member functions
3976   // to "check both ways" when comparing the data
3977   // structures of two graphs.  For instance, if all
3978   // edges between heap region nodes in graph A are
3979   // present and equal in graph B it is not sufficient
3980   // to say the graphs are equal.  Consider that there
3981   // may be edges in graph B that are not in graph A.
3982   // the only way to know that all edges in both graphs
3983   // are equally present is to iterate over both data
3984   // structures and compare against the other graph.
3985   public boolean equals(ReachGraph rg) {
3986
3987     if( rg == null ) {
3988       if( dbgEquals ) {
3989         System.out.println("rg is null");
3990       }
3991       return false;
3992     }
3993
3994     if( !areHeapRegionNodesEqual(rg) ) {
3995       if( dbgEquals ) {
3996         System.out.println("hrn not equal");
3997       }
3998       return false;
3999     }
4000
4001     if( !areVariableNodesEqual(rg) ) {
4002       if( dbgEquals ) {
4003         System.out.println("vars not equal");
4004       }
4005       return false;
4006     }
4007
4008     if( !areRefEdgesEqual(rg) ) {
4009       if( dbgEquals ) {
4010         System.out.println("edges not equal");
4011       }
4012       return false;
4013     }
4014
4015     if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4016       return false;
4017     }
4018
4019     // if everything is equal up to this point,
4020     // assert that allocSites is also equal--
4021     // this data is redundant but kept for efficiency
4022     assert allocSites.equals(rg.allocSites);
4023
4024     return true;
4025   }
4026
4027
4028   protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4029
4030     if( !areallHRNinAalsoinBandequal(this, rg) ) {
4031       return false;
4032     }
4033
4034     if( !areallHRNinAalsoinBandequal(rg, this) ) {
4035       return false;
4036     }
4037
4038     return true;
4039   }
4040
4041   static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4042                                                        ReachGraph rgB) {
4043     Set sA = rgA.id2hrn.entrySet();
4044     Iterator iA = sA.iterator();
4045     while( iA.hasNext() ) {
4046       Map.Entry meA  = (Map.Entry)iA.next();
4047       Integer idA  = (Integer)        meA.getKey();
4048       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4049
4050       if( !rgB.id2hrn.containsKey(idA) ) {
4051         return false;
4052       }
4053
4054       HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4055       if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4056         return false;
4057       }
4058     }
4059
4060     return true;
4061   }
4062
4063   protected boolean areVariableNodesEqual(ReachGraph rg) {
4064
4065     if( !areallVNinAalsoinBandequal(this, rg) ) {
4066       return false;
4067     }
4068
4069     if( !areallVNinAalsoinBandequal(rg, this) ) {
4070       return false;
4071     }
4072
4073     return true;
4074   }
4075
4076   static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4077                                                       ReachGraph rgB) {
4078     Set sA = rgA.td2vn.entrySet();
4079     Iterator iA = sA.iterator();
4080     while( iA.hasNext() ) {
4081       Map.Entry meA = (Map.Entry)iA.next();
4082       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4083
4084       if( !rgB.td2vn.containsKey(tdA) ) {
4085         return false;
4086       }
4087     }
4088
4089     return true;
4090   }
4091
4092
4093   protected boolean areRefEdgesEqual(ReachGraph rg) {
4094     if( !areallREinAandBequal(this, rg) ) {
4095       return false;
4096     }
4097
4098     if( !areallREinAandBequal(rg, this) ) {
4099       return false;
4100     }
4101
4102     return true;
4103   }
4104
4105   static protected boolean areallREinAandBequal(ReachGraph rgA,
4106                                                 ReachGraph rgB) {
4107
4108     // check all the heap region->heap region edges
4109     Set sA = rgA.id2hrn.entrySet();
4110     Iterator iA = sA.iterator();
4111     while( iA.hasNext() ) {
4112       Map.Entry meA  = (Map.Entry)iA.next();
4113       Integer idA  = (Integer)        meA.getKey();
4114       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4115
4116       // we should have already checked that the same
4117       // heap regions exist in both graphs
4118       assert rgB.id2hrn.containsKey(idA);
4119
4120       if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4121         return false;
4122       }
4123
4124       // then check every edge in B for presence in A, starting
4125       // from the same parent HeapRegionNode
4126       HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4127
4128       if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4129         return false;
4130       }
4131     }
4132
4133     // then check all the variable->heap region edges
4134     sA = rgA.td2vn.entrySet();
4135     iA = sA.iterator();
4136     while( iA.hasNext() ) {
4137       Map.Entry meA = (Map.Entry)iA.next();
4138       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4139       VariableNode vnA = (VariableNode)   meA.getValue();
4140
4141       // we should have already checked that the same
4142       // label nodes exist in both graphs
4143       assert rgB.td2vn.containsKey(tdA);
4144
4145       if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4146         return false;
4147       }
4148
4149       // then check every edge in B for presence in A, starting
4150       // from the same parent VariableNode
4151       VariableNode vnB = rgB.td2vn.get(tdA);
4152
4153       if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4154         return false;
4155       }
4156     }
4157
4158     return true;
4159   }
4160
4161
4162   static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4163                                                  RefSrcNode rnA,
4164                                                  ReachGraph rgB) {
4165
4166     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4167     while( itrA.hasNext() ) {
4168       RefEdge edgeA     = itrA.next();
4169       HeapRegionNode hrnChildA = edgeA.getDst();
4170       Integer idChildA  = hrnChildA.getID();
4171
4172       assert rgB.id2hrn.containsKey(idChildA);
4173
4174       // at this point we know an edge in graph A exists
4175       // rnA -> idChildA, does this exact edge exist in B?
4176       boolean edgeFound = false;
4177
4178       RefSrcNode rnB = null;
4179       if( rnA instanceof HeapRegionNode ) {
4180         HeapRegionNode hrnA = (HeapRegionNode) rnA;
4181         rnB = rgB.id2hrn.get(hrnA.getID() );
4182       } else {
4183         VariableNode vnA = (VariableNode) rnA;
4184         rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4185       }
4186
4187       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4188       while( itrB.hasNext() ) {
4189         RefEdge edgeB     = itrB.next();
4190         HeapRegionNode hrnChildB = edgeB.getDst();
4191         Integer idChildB  = hrnChildB.getID();
4192
4193         if( idChildA.equals(idChildB) &&
4194             edgeA.typeAndFieldEquals(edgeB) ) {
4195
4196           // there is an edge in the right place with the right field,
4197           // but do they have the same attributes?
4198           if( edgeA.getBeta().equals(edgeB.getBeta() ) &&
4199               edgeA.equalsPreds(edgeB)
4200               ) {
4201             edgeFound = true;
4202           }
4203         }
4204       }
4205
4206       if( !edgeFound ) {
4207         return false;
4208       }
4209     }
4210
4211     return true;
4212   }
4213
4214
4215   // can be used to assert monotonicity
4216   static public boolean isNoSmallerThan(ReachGraph rgA,
4217                                         ReachGraph rgB) {
4218
4219     //System.out.println( "*** Asking if A is no smaller than B ***" );
4220
4221
4222     Iterator iA = rgA.id2hrn.entrySet().iterator();
4223     while( iA.hasNext() ) {
4224       Map.Entry meA  = (Map.Entry)iA.next();
4225       Integer idA  = (Integer)        meA.getKey();
4226       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4227
4228       if( !rgB.id2hrn.containsKey(idA) ) {
4229         System.out.println("  regions smaller");
4230         return false;
4231       }
4232
4233       //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
4234       /* NOT EQUALS, NO SMALLER THAN!
4235          if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
4236          System.out.println( "  regions smaller" );
4237          return false;
4238          }
4239        */
4240     }
4241
4242     // this works just fine, no smaller than
4243     if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4244       System.out.println("  vars smaller:");
4245       System.out.println("    A:"+rgA.td2vn.keySet() );
4246       System.out.println("    B:"+rgB.td2vn.keySet() );
4247       return false;
4248     }
4249
4250
4251     iA = rgA.id2hrn.entrySet().iterator();
4252     while( iA.hasNext() ) {
4253       Map.Entry meA  = (Map.Entry)iA.next();
4254       Integer idA  = (Integer)        meA.getKey();
4255       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4256
4257       Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4258       while( reItr.hasNext() ) {
4259         RefEdge edgeA = reItr.next();
4260         RefSrcNode rsnA  = edgeA.getSrc();
4261
4262         // we already checked that nodes were present
4263         HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4264         assert hrnB != null;
4265
4266         RefSrcNode rsnB;
4267         if( rsnA instanceof VariableNode ) {
4268           VariableNode vnA = (VariableNode) rsnA;
4269           rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4270
4271         } else {
4272           HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4273           rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4274         }
4275         assert rsnB != null;
4276
4277         RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4278                                             edgeA.getType(),
4279                                             edgeA.getField()
4280                                             );
4281         if( edgeB == null ) {
4282           System.out.println("  edges smaller:");
4283           return false;
4284         }
4285
4286         // REMEMBER, IS NO SMALLER THAN
4287         /*
4288            System.out.println( "  edges smaller" );
4289            return false;
4290            }
4291          */
4292
4293       }
4294     }
4295
4296
4297     return true;
4298   }
4299
4300
4301
4302
4303
4304   // this analysis no longer has the "match anything"
4305   // type which was represented by null
4306   protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4307                                             TypeDescriptor td2) {
4308     assert td1 != null;
4309     assert td2 != null;
4310
4311     if( td1.isNull() ) {
4312       return td2;
4313     }
4314     if( td2.isNull() ) {
4315       return td1;
4316     }
4317     return typeUtil.mostSpecific(td1, td2);
4318   }
4319
4320   protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4321                                             TypeDescriptor td2,
4322                                             TypeDescriptor td3) {
4323
4324     return mostSpecificType(td1,
4325                             mostSpecificType(td2, td3)
4326                             );
4327   }
4328
4329   protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4330                                             TypeDescriptor td2,
4331                                             TypeDescriptor td3,
4332                                             TypeDescriptor td4) {
4333
4334     return mostSpecificType(mostSpecificType(td1, td2),
4335                             mostSpecificType(td3, td4)
4336                             );
4337   }
4338
4339   protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4340                                    TypeDescriptor possibleChild) {
4341     assert possibleSuper != null;
4342     assert possibleChild != null;
4343
4344     if( possibleSuper.isNull() ||
4345         possibleChild.isNull() ) {
4346       return true;
4347     }
4348
4349     return typeUtil.isSuperorType(possibleSuper, possibleChild);
4350   }
4351
4352
4353   protected boolean hasMatchingField(HeapRegionNode src,
4354                                      RefEdge edge) {
4355
4356     TypeDescriptor tdSrc = src.getType();
4357     assert tdSrc != null;
4358
4359     if( tdSrc.isArray() ) {
4360       TypeDescriptor td = edge.getType();
4361       assert td != null;
4362
4363       TypeDescriptor tdSrcDeref = tdSrc.dereference();
4364       assert tdSrcDeref != null;
4365
4366       if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4367         return false;
4368       }
4369
4370       return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4371     }
4372
4373     // if it's not a class, it doesn't have any fields to match
4374     if( !tdSrc.isClass() ) {
4375       return false;
4376     }
4377
4378     ClassDescriptor cd = tdSrc.getClassDesc();
4379     while( cd != null ) {
4380       Iterator fieldItr = cd.getFields();
4381
4382       while( fieldItr.hasNext() ) {
4383         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4384
4385         if( fd.getType().equals(edge.getType() ) &&
4386             fd.getSymbol().equals(edge.getField() ) ) {
4387           return true;
4388         }
4389       }
4390
4391       cd = cd.getSuperDesc();
4392     }
4393
4394     // otherwise it is a class with fields
4395     // but we didn't find a match
4396     return false;
4397   }
4398
4399   protected boolean hasMatchingType(RefEdge edge,
4400                                     HeapRegionNode dst) {
4401
4402     // if the region has no type, matches everything
4403     TypeDescriptor tdDst = dst.getType();
4404     assert tdDst != null;
4405
4406     // if the type is not a class or an array, don't
4407     // match because primitives are copied, no aliases
4408     ClassDescriptor cdDst = tdDst.getClassDesc();
4409     if( cdDst == null && !tdDst.isArray() ) {
4410       return false;
4411     }
4412
4413     // if the edge type is null, it matches everything
4414     TypeDescriptor tdEdge = edge.getType();
4415     assert tdEdge != null;
4416
4417     return typeUtil.isSuperorType(tdEdge, tdDst);
4418   }
4419
4420
4421
4422   // the default signature for quick-and-dirty debugging
4423   public void writeGraph(String graphName) {
4424     writeGraph(graphName,
4425                true,   // write labels
4426                true,   // label select
4427                true,   // prune garbage
4428                false,  // hide reachability
4429                true,   // hide subset reachability
4430                true,   // hide predicates
4431                false,   // hide edge taints
4432                null    // in-context boundary
4433                );
4434   }
4435
4436   public void writeGraph(String graphName,
4437                          boolean writeLabels,
4438                          boolean labelSelect,
4439                          boolean pruneGarbage,
4440                          boolean hideReachability,
4441                          boolean hideSubsetReachability,
4442                          boolean hidePredicates,
4443                          boolean hideEdgeTaints
4444                          ) {
4445     writeGraph(graphName,
4446                writeLabels,
4447                labelSelect,
4448                pruneGarbage,
4449                hideReachability,
4450                hideSubsetReachability,
4451                hidePredicates,
4452                hideEdgeTaints,
4453                null);
4454   }
4455
4456   public void writeGraph(String graphName,
4457                          boolean writeLabels,
4458                          boolean labelSelect,
4459                          boolean pruneGarbage,
4460                          boolean hideReachability,
4461                          boolean hideSubsetReachability,
4462                          boolean hidePredicates,
4463                          boolean hideEdgeTaints,
4464                          Set<Integer> callerNodeIDsCopiedToCallee
4465                          ) {
4466     try {
4467       // remove all non-word characters from the graph name so
4468       // the filename and identifier in dot don't cause errors
4469       graphName = graphName.replaceAll("[\\W]", "");
4470
4471       BufferedWriter bw =
4472         new BufferedWriter(new FileWriter(graphName+".dot") );
4473
4474       bw.write("digraph "+graphName+" {\n");
4475
4476
4477       // this is an optional step to form the callee-reachable
4478       // "cut-out" into a DOT cluster for visualization
4479       if( callerNodeIDsCopiedToCallee != null ) {
4480
4481         bw.write("  subgraph cluster0 {\n");
4482         bw.write("    color=blue;\n");
4483
4484         Iterator i = id2hrn.entrySet().iterator();
4485         while( i.hasNext() ) {
4486           Map.Entry me  = (Map.Entry)i.next();
4487           HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4488
4489           if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4490             bw.write("    "+
4491                      hrn.toString()+
4492                      hrn.toStringDOT(hideReachability,
4493                                      hideSubsetReachability,
4494                                      hidePredicates)+
4495                      ";\n");
4496           }
4497         }
4498
4499         bw.write("  }\n");
4500       }
4501
4502
4503       Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4504
4505       // then visit every heap region node
4506       Iterator i = id2hrn.entrySet().iterator();
4507       while( i.hasNext() ) {
4508         Map.Entry me  = (Map.Entry)i.next();
4509         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4510
4511         // only visit nodes worth writing out--for instance
4512         // not every node at an allocation is referenced
4513         // (think of it as garbage-collected), etc.
4514         if( !pruneGarbage        ||
4515             hrn.isOutOfContext() ||
4516             (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4517             ) {
4518
4519           if( !visited.contains(hrn) ) {
4520             traverseHeapRegionNodes(hrn,
4521                                     bw,
4522                                     null,
4523                                     visited,
4524                                     hideReachability,
4525                                     hideSubsetReachability,
4526                                     hidePredicates,
4527                                     hideEdgeTaints,
4528                                     callerNodeIDsCopiedToCallee);
4529           }
4530         }
4531       }
4532
4533       bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
4534
4535
4536       // then visit every label node, useful for debugging
4537       if( writeLabels ) {
4538         i = td2vn.entrySet().iterator();
4539         while( i.hasNext() ) {
4540           Map.Entry me = (Map.Entry)i.next();
4541           VariableNode vn = (VariableNode) me.getValue();
4542
4543           if( labelSelect ) {
4544             String labelStr = vn.getTempDescriptorString();
4545             if( labelStr.startsWith("___temp")     ||
4546                 labelStr.startsWith("___dst")      ||
4547                 labelStr.startsWith("___srctmp")   ||
4548                 labelStr.startsWith("___neverused")
4549                 ) {
4550               continue;
4551             }
4552           }
4553
4554           Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4555           while( heapRegionsItr.hasNext() ) {
4556             RefEdge edge = heapRegionsItr.next();
4557             HeapRegionNode hrn  = edge.getDst();
4558
4559             if( !visited.contains(hrn) ) {
4560               traverseHeapRegionNodes(hrn,
4561                                       bw,
4562                                       null,
4563                                       visited,
4564                                       hideReachability,
4565                                       hideSubsetReachability,
4566                                       hidePredicates,
4567                                       hideEdgeTaints,
4568                                       callerNodeIDsCopiedToCallee);
4569             }
4570
4571             bw.write("  "+vn.toString()+
4572                      " -> "+hrn.toString()+
4573                      edge.toStringDOT(hideReachability,
4574                                       hideSubsetReachability,
4575                                       hidePredicates,
4576                                       hideEdgeTaints,
4577                                       "")+
4578                      ";\n");
4579           }
4580         }
4581       }
4582
4583       bw.write("}\n");
4584       bw.close();
4585
4586     } catch( IOException e ) {
4587       throw new Error("Error writing out DOT graph "+graphName);
4588     }
4589   }
4590
4591   protected void
4592   traverseHeapRegionNodes(HeapRegionNode hrn,
4593                           BufferedWriter bw,
4594                           TempDescriptor td,
4595                           Set<HeapRegionNode> visited,
4596                           boolean hideReachability,
4597                           boolean hideSubsetReachability,
4598                           boolean hidePredicates,
4599                           boolean hideEdgeTaints,
4600                           Set<Integer>        callerNodeIDsCopiedToCallee
4601                           ) throws java.io.IOException {
4602
4603     if( visited.contains(hrn) ) {
4604       return;
4605     }
4606     visited.add(hrn);
4607
4608     // if we're drawing the callee-view subgraph, only
4609     // write out the node info if it hasn't already been
4610     // written
4611     if( callerNodeIDsCopiedToCallee == null ||
4612         !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4613         ) {
4614       bw.write("  "+
4615                hrn.toString()+
4616                hrn.toStringDOT(hideReachability,
4617                                hideSubsetReachability,
4618                                hidePredicates)+
4619                ";\n");
4620     }
4621
4622     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4623     while( childRegionsItr.hasNext() ) {
4624       RefEdge edge     = childRegionsItr.next();
4625       HeapRegionNode hrnChild = edge.getDst();
4626
4627       if( callerNodeIDsCopiedToCallee != null &&
4628           (edge.getSrc() instanceof HeapRegionNode) ) {
4629         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4630         if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID()        ) &&
4631             callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4632             ) {
4633           bw.write("  "+hrn.toString()+
4634                    " -> "+hrnChild.toString()+
4635                    edge.toStringDOT(hideReachability,
4636                                     hideSubsetReachability,
4637                                     hidePredicates,
4638                                     hideEdgeTaints,
4639                                     ",color=blue")+
4640                    ";\n");
4641         } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID()       ) &&
4642                    callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4643                    ) {
4644           bw.write("  "+hrn.toString()+
4645                    " -> "+hrnChild.toString()+
4646                    edge.toStringDOT(hideReachability,
4647                                     hideSubsetReachability,
4648                                     hidePredicates,
4649                                     hideEdgeTaints,
4650                                     ",color=blue,style=dashed")+
4651                    ";\n");
4652         } else {
4653           bw.write("  "+hrn.toString()+
4654                    " -> "+hrnChild.toString()+
4655                    edge.toStringDOT(hideReachability,
4656                                     hideSubsetReachability,
4657                                     hidePredicates,
4658                                     hideEdgeTaints,
4659                                     "")+
4660                    ";\n");
4661         }
4662       } else {
4663         bw.write("  "+hrn.toString()+
4664                  " -> "+hrnChild.toString()+
4665                  edge.toStringDOT(hideReachability,
4666                                   hideSubsetReachability,
4667                                   hidePredicates,
4668                                   hideEdgeTaints,
4669                                   "")+
4670                  ";\n");
4671       }
4672
4673       traverseHeapRegionNodes(hrnChild,
4674                               bw,
4675                               td,
4676                               visited,
4677                               hideReachability,
4678                               hideSubsetReachability,
4679                               hidePredicates,
4680                               hideEdgeTaints,
4681                               callerNodeIDsCopiedToCallee);
4682     }
4683   }
4684
4685
4686
4687
4688
4689
4690   // return the set of heap regions from the given allocation
4691   // site, if any, that exist in this graph
4692   protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4693
4694     Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4695
4696     Integer idSum = as.getSummary();
4697     if( id2hrn.containsKey(idSum) ) {
4698       out.add(id2hrn.get(idSum) );
4699     }
4700
4701     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4702       Integer idI = as.getIthOldest(i);
4703       if( id2hrn.containsKey(idI) ) {
4704         out.add(id2hrn.get(idI) );
4705       }
4706     }
4707
4708     return out;
4709   }
4710
4711   // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4712   // from the given allocation site, if any, from regions for that
4713   // site that exist in this graph
4714   protected Set<ReachTuple> getAnyExisting(AllocSite as,
4715                                            boolean includeARITY_ZEROORMORE,
4716                                            boolean includeARITY_ONE) {
4717
4718     Set<ReachTuple> out = new HashSet<ReachTuple>();
4719
4720     Integer idSum = as.getSummary();
4721     if( id2hrn.containsKey(idSum) ) {
4722
4723       HeapRegionNode hrn = id2hrn.get(idSum);
4724       assert !hrn.isOutOfContext();
4725
4726       if( !includeARITY_ZEROORMORE ) {
4727         out.add(ReachTuple.factory(hrn.getID(),
4728                                    true,     // multi-obj region
4729                                    ReachTuple.ARITY_ZEROORMORE,
4730                                    false)    // ooc?
4731                 );
4732       }
4733
4734       if( includeARITY_ONE ) {
4735         out.add(ReachTuple.factory(hrn.getID(),
4736                                    true,     // multi-object region
4737                                    ReachTuple.ARITY_ONE,
4738                                    false)    // ooc?
4739                 );
4740       }
4741     }
4742
4743     if( !includeARITY_ONE ) {
4744       // no need to do the single-object regions that
4745       // only have an ARITY ONE possible
4746       return out;
4747     }
4748
4749     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4750
4751       Integer idI = as.getIthOldest(i);
4752       if( id2hrn.containsKey(idI) ) {
4753
4754         HeapRegionNode hrn = id2hrn.get(idI);
4755         assert !hrn.isOutOfContext();
4756
4757         out.add(ReachTuple.factory(hrn.getID(),
4758                                    false,    // multi-object region
4759                                    ReachTuple.ARITY_ONE,
4760                                    false)    // ooc?
4761                 );
4762       }
4763     }
4764
4765     return out;
4766   }
4767
4768
4769   // if an object allocated at the target site may be
4770   // reachable from both an object from root1 and an
4771   // object allocated at root2, return TRUE
4772   public boolean mayBothReachTarget(AllocSite asRoot1,
4773                                     AllocSite asRoot2,
4774                                     AllocSite asTarget) {
4775
4776     // consider all heap regions of the target and look
4777     // for a reach state that indicates regions of root1
4778     // and root2 might be able to reach same object
4779     Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4780
4781     // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4782     Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4783     Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4784
4785     Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4786     while( hrnItr.hasNext() ) {
4787       HeapRegionNode hrn = hrnItr.next();
4788
4789       Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4790       while( rtItr1.hasNext() ) {
4791         ReachTuple rt1 = rtItr1.next();
4792
4793         Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4794         while( rtItr2.hasNext() ) {
4795           ReachTuple rt2 = rtItr2.next();
4796
4797           if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4798             return true;
4799           }
4800         }
4801       }
4802     }
4803
4804     return false;
4805   }
4806
4807   // similar to the method above, return TRUE if ever
4808   // more than one object from the root allocation site
4809   // may reach an object from the target site
4810   public boolean mayManyReachTarget(AllocSite asRoot,
4811                                     AllocSite asTarget) {
4812
4813     // consider all heap regions of the target and look
4814     // for a reach state that multiple objects of root
4815     // might be able to reach the same object
4816     Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4817
4818     // get relevant reach tuples
4819     Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true,  false);
4820     Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4821
4822     Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4823     while( hrnItr.hasNext() ) {
4824       HeapRegionNode hrn = hrnItr.next();
4825
4826       // if any ZERORMORE tuples are here, TRUE
4827       Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4828       while( rtItr.hasNext() ) {
4829         ReachTuple rtZOM = rtItr.next();
4830
4831         if( hrn.getAlpha().containsTuple(rtZOM) ) {
4832           return true;
4833         }
4834       }
4835
4836       // otherwise, look for any pair of ONE tuples
4837       Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4838       while( rtItr1.hasNext() ) {
4839         ReachTuple rt1 = rtItr1.next();
4840
4841         Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4842         while( rtItr2.hasNext() ) {
4843           ReachTuple rt2 = rtItr2.next();
4844
4845           if( rt1 == rt2 ) {
4846             continue;
4847           }
4848
4849           if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4850             return true;
4851           }
4852         }
4853       }
4854     }
4855
4856     return false;
4857   }
4858
4859
4860
4861
4862
4863   public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4864
4865     Set<HeapRegionNode> exhibitProofState =
4866       new HashSet<HeapRegionNode>();
4867
4868     Iterator hrnItr = id2hrn.entrySet().iterator();
4869     while( hrnItr.hasNext() ) {
4870       Map.Entry me  = (Map.Entry)hrnItr.next();
4871       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4872
4873       ReachSet intersection =
4874         Canonical.intersection(proofOfSharing,
4875                                hrn.getAlpha()
4876                                );
4877       if( !intersection.isEmpty() ) {
4878         assert !hrn.isOutOfContext();
4879         exhibitProofState.add(hrn);
4880       }
4881     }
4882
4883     return exhibitProofState;
4884   }
4885
4886
4887   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4888                                                    HeapRegionNode hrn2) {
4889     assert hrn1 != null;
4890     assert hrn2 != null;
4891
4892     assert !hrn1.isOutOfContext();
4893     assert !hrn2.isOutOfContext();
4894
4895     assert belongsToThis(hrn1);
4896     assert belongsToThis(hrn2);
4897
4898     assert !hrn1.getID().equals(hrn2.getID() );
4899
4900
4901     // then get the various tokens for these heap regions
4902     ReachTuple h1 =
4903       ReachTuple.factory(hrn1.getID(),
4904                          !hrn1.isSingleObject(),  // multi?
4905                          ReachTuple.ARITY_ONE,
4906                          false);                  // ooc?
4907
4908     ReachTuple h1star = null;
4909     if( !hrn1.isSingleObject() ) {
4910       h1star =
4911         ReachTuple.factory(hrn1.getID(),
4912                            !hrn1.isSingleObject(),
4913                            ReachTuple.ARITY_ZEROORMORE,
4914                            false);
4915     }
4916
4917     ReachTuple h2 =
4918       ReachTuple.factory(hrn2.getID(),
4919                          !hrn2.isSingleObject(),
4920                          ReachTuple.ARITY_ONE,
4921                          false);
4922
4923     ReachTuple h2star = null;
4924     if( !hrn2.isSingleObject() ) {
4925       h2star =
4926         ReachTuple.factory(hrn2.getID(),
4927                            !hrn2.isSingleObject(),
4928                            ReachTuple.ARITY_ZEROORMORE,
4929                            false);
4930     }
4931
4932     // then get the merged beta of all out-going edges from these heap
4933     // regions
4934
4935     ReachSet beta1 = ReachSet.factory();
4936     Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4937     while (itrEdge.hasNext()) {
4938       RefEdge edge = itrEdge.next();
4939       beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4940     }
4941
4942     ReachSet beta2 = ReachSet.factory();
4943     itrEdge = hrn2.iteratorToReferencees();
4944     while (itrEdge.hasNext()) {
4945       RefEdge edge = itrEdge.next();
4946       beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4947     }
4948
4949     ReachSet proofOfSharing = ReachSet.factory();
4950
4951     proofOfSharing =
4952       Canonical.unionORpreds(proofOfSharing,
4953                              beta1.getStatesWithBoth(h1, h2)
4954                              );
4955     proofOfSharing =
4956       Canonical.unionORpreds(proofOfSharing,
4957                              beta2.getStatesWithBoth(h1, h2)
4958                              );
4959
4960     if( !hrn1.isSingleObject() ) {
4961       proofOfSharing =
4962         Canonical.unionORpreds(proofOfSharing,
4963                                beta1.getStatesWithBoth(h1star, h2)
4964                                );
4965       proofOfSharing =
4966         Canonical.unionORpreds(proofOfSharing,
4967                                beta2.getStatesWithBoth(h1star, h2)
4968                                );
4969     }
4970
4971     if( !hrn2.isSingleObject() ) {
4972       proofOfSharing =
4973         Canonical.unionORpreds(proofOfSharing,
4974                                beta1.getStatesWithBoth(h1, h2star)
4975                                );
4976       proofOfSharing =
4977         Canonical.unionORpreds(proofOfSharing,
4978                                beta2.getStatesWithBoth(h1, h2star)
4979                                );
4980     }
4981
4982     if( !hrn1.isSingleObject() &&
4983         !hrn2.isSingleObject()
4984         ) {
4985       proofOfSharing =
4986         Canonical.unionORpreds(proofOfSharing,
4987                                beta1.getStatesWithBoth(h1star, h2star)
4988                                );
4989       proofOfSharing =
4990         Canonical.unionORpreds(proofOfSharing,
4991                                beta2.getStatesWithBoth(h1star, h2star)
4992                                );
4993     }
4994
4995     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4996     if( !proofOfSharing.isEmpty() ) {
4997       common = findCommonReachableNodes(proofOfSharing);
4998       if( !DISABLE_STRONG_UPDATES &&
4999           !DISABLE_GLOBAL_SWEEP
5000           ) {
5001         assert !common.isEmpty();
5002       }
5003     }
5004
5005     return common;
5006   }
5007
5008   // this version of the above method checks whether there is sharing
5009   // among the objects in a summary node
5010   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5011     assert hrn != null;
5012     assert hrn.isNewSummary();
5013     assert !hrn.isOutOfContext();
5014     assert belongsToThis(hrn);
5015
5016     ReachTuple hstar =
5017       ReachTuple.factory(hrn.getID(),
5018                          true,     // multi
5019                          ReachTuple.ARITY_ZEROORMORE,
5020                          false);   // ooc
5021
5022     // then get the merged beta of all out-going edges from
5023     // this heap region
5024
5025     ReachSet beta = ReachSet.factory();
5026     Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5027     while (itrEdge.hasNext()) {
5028       RefEdge edge = itrEdge.next();
5029       beta = Canonical.unionORpreds(beta, edge.getBeta());
5030     }
5031
5032     ReachSet proofOfSharing = ReachSet.factory();
5033
5034     proofOfSharing =
5035       Canonical.unionORpreds(proofOfSharing,
5036                              beta.getStatesWithBoth(hstar, hstar)
5037                              );
5038
5039     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5040     if( !proofOfSharing.isEmpty() ) {
5041       common = findCommonReachableNodes(proofOfSharing);
5042       if( !DISABLE_STRONG_UPDATES &&
5043           !DISABLE_GLOBAL_SWEEP
5044           ) {
5045         assert !common.isEmpty();
5046       }
5047     }
5048
5049     return common;
5050   }
5051
5052
5053   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5054                                                    Integer paramIndex1,
5055                                                    Integer paramIndex2) {
5056
5057     // get parameter's heap regions
5058     TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5059     assert this.hasVariable(paramTemp1);
5060     VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5061
5062
5063     if( !(paramVar1.getNumReferencees() == 1) ) {
5064       System.out.println("\n  fm="+fm+"\n  param="+paramTemp1);
5065       writeGraph("whatup");
5066     }
5067
5068
5069     assert paramVar1.getNumReferencees() == 1;
5070     RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5071     HeapRegionNode hrnParam1 = paramEdge1.getDst();
5072
5073     TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5074     assert this.hasVariable(paramTemp2);
5075     VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5076
5077     if( !(paramVar2.getNumReferencees() == 1) ) {
5078       System.out.println("\n  fm="+fm+"\n  param="+paramTemp2);
5079       writeGraph("whatup");
5080     }
5081
5082     assert paramVar2.getNumReferencees() == 1;
5083     RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5084     HeapRegionNode hrnParam2 = paramEdge2.getDst();
5085
5086     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5087     common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5088
5089     return common;
5090   }
5091
5092   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5093                                                    Integer paramIndex,
5094                                                    AllocSite as) {
5095
5096     // get parameter's heap regions
5097     TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5098     assert this.hasVariable(paramTemp);
5099     VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5100     assert paramVar.getNumReferencees() == 1;
5101     RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5102     HeapRegionNode hrnParam = paramEdge.getDst();
5103
5104     // get summary node
5105     HeapRegionNode hrnSummary=null;
5106     if(id2hrn.containsKey(as.getSummary())) {
5107       // if summary node doesn't exist, ignore this case
5108       hrnSummary = id2hrn.get(as.getSummary());
5109       assert hrnSummary != null;
5110     }
5111
5112     Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
5113     if(hrnSummary!=null) {
5114       common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5115     }
5116
5117     // check for other nodes
5118     for (int i = 0; i < as.getAllocationDepth(); ++i) {
5119
5120       assert id2hrn.containsKey(as.getIthOldest(i));
5121       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5122       assert hrnIthOldest != null;
5123
5124       common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5125
5126     }
5127
5128     return common;
5129   }
5130
5131   public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5132                                                    AllocSite as2) {
5133
5134     // get summary node 1's alpha
5135     Integer idSum1 = as1.getSummary();
5136     HeapRegionNode hrnSum1=null;
5137     if(id2hrn.containsKey(idSum1)) {
5138       hrnSum1 = id2hrn.get(idSum1);
5139     }
5140
5141     // get summary node 2's alpha
5142     Integer idSum2 = as2.getSummary();
5143     HeapRegionNode hrnSum2=null;
5144     if(id2hrn.containsKey(idSum2)) {
5145       hrnSum2 = id2hrn.get(idSum2);
5146     }
5147
5148     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5149     if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5150       common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5151     }
5152
5153     if(hrnSum1!=null) {
5154       // ask if objects from this summary share among each other
5155       common.addAll(mayReachSharedObjects(hrnSum1));
5156     }
5157
5158     // check sum2 against alloc1 nodes
5159     if(hrnSum2!=null) {
5160       for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5161         Integer idI1 = as1.getIthOldest(i);
5162         assert id2hrn.containsKey(idI1);
5163         HeapRegionNode hrnI1 = id2hrn.get(idI1);
5164         assert hrnI1 != null;
5165         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5166       }
5167
5168       // also ask if objects from this summary share among each other
5169       common.addAll(mayReachSharedObjects(hrnSum2));
5170     }
5171
5172     // check sum1 against alloc2 nodes
5173     for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5174       Integer idI2 = as2.getIthOldest(i);
5175       assert id2hrn.containsKey(idI2);
5176       HeapRegionNode hrnI2 = id2hrn.get(idI2);
5177       assert hrnI2 != null;
5178
5179       if(hrnSum1!=null) {
5180         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5181       }
5182
5183       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5184       for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5185         Integer idI1 = as1.getIthOldest(j);
5186
5187         // if these are the same site, don't look for the same token, no
5188         // alias.
5189         // different tokens of the same site could alias together though
5190         if (idI1.equals(idI2)) {
5191           continue;
5192         }
5193
5194         HeapRegionNode hrnI1 = id2hrn.get(idI1);
5195
5196         common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5197       }
5198     }
5199
5200     return common;
5201   }
5202
5203   public void makeInaccessible(Set<TempDescriptor> vars) {
5204     inaccessibleVars.addAll(vars);
5205   }
5206
5207   public void makeInaccessible(TempDescriptor td) {
5208     inaccessibleVars.add(td);
5209   }
5210
5211   public void makeAccessible(TempDescriptor td) {
5212     inaccessibleVars.remove(td);
5213   }
5214
5215   public boolean isAccessible(TempDescriptor td) {
5216     return !inaccessibleVars.contains(td);
5217   }
5218
5219   public Set<TempDescriptor> getInaccessibleVars() {
5220     return inaccessibleVars;
5221   }
5222
5223
5224
5225
5226   public Set<Alloc> canPointTo( TempDescriptor x ) {
5227
5228     if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5229       // if we don't care to track it, return null which means
5230       // "a client of this result shouldn't care either"
5231       return HeapAnalysis.DONTCARE_PTR;
5232     }
5233
5234     Set<Alloc> out = new HashSet<Alloc>();
5235
5236     VariableNode vn = getVariableNodeNoMutation( x );
5237     if( vn == null ) {
5238       // the empty set means "can't point to anything"
5239       return out;
5240     }
5241
5242     Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5243     while( edgeItr.hasNext() ) {
5244       HeapRegionNode hrn = edgeItr.next().getDst();
5245       out.add( hrn.getAllocSite() );
5246     }
5247
5248     return out;
5249   }
5250
5251
5252
5253   public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5254                                                     String         field,
5255                                                     TypeDescriptor fieldType ) {
5256
5257     if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5258       // if we don't care to track it, return null which means
5259       // "a client of this result shouldn't care either"
5260       return HeapAnalysis.DONTCARE_DREF;
5261     }
5262
5263     Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5264
5265     VariableNode vn = getVariableNodeNoMutation( x );
5266     if( vn == null ) {
5267       // the empty table means "x can't point to anything"
5268       return out;
5269     }
5270
5271     Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5272     while( edgeItr.hasNext() ) {
5273       HeapRegionNode hrn = edgeItr.next().getDst();
5274       Alloc          key = hrn.getAllocSite();
5275
5276       if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5277         // if we don't care to track it, put no entry which means
5278         // "a client of this result shouldn't care either"
5279         out.put( key, HeapAnalysis.DONTCARE_PTR );
5280         continue;
5281       }
5282
5283       Set<Alloc> moreValues = new HashSet<Alloc>();
5284       Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5285       while( edgeItr2.hasNext() ) {
5286         RefEdge edge = edgeItr2.next();
5287
5288         if( field.equals( edge.getField() ) ) {
5289           moreValues.add( edge.getDst().getAllocSite() );
5290         }
5291       }
5292
5293       if( out.containsKey( key ) ) {
5294         out.get( key ).addAll( moreValues );
5295       } else {
5296         out.put( key, moreValues );
5297       }
5298     }
5299
5300     return out;
5301   }
5302
5303
5304
5305   // for debugging
5306   public TempDescriptor findVariableByName( String name ) {
5307
5308     for( TempDescriptor td: td2vn.keySet() ) {
5309       if( td.getSymbol().contains( name ) ) {
5310         return td;
5311       }
5312     }
5313
5314     return null;
5315   }
5316 }