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