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