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