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