Robust/src/Analysis/Disjoint/ReachGraph.java

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