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