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