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         if( !DISABLE_GLOBAL_SWEEP ) {
2314           assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2315         }
2316
2317         rg.addRefEdge(hrnCalleeAndOutContext,
2318                       hrnDstCallee,
2319                       new RefEdge(hrnCalleeAndOutContext,
2320                                   hrnDstCallee,
2321                                   reCaller.getType(),
2322                                   reCaller.getField(),
2323                                   toCalleeContext(reCaller.getBeta(),
2324                                                   preds,
2325                                                   oocHrnIdOoc2callee
2326                                                   ),
2327                                   preds,
2328                                   toCalleeContext(reCaller.getTaints(),
2329                                                   preds)
2330                                   )
2331                       );
2332
2333       } else {
2334         // the out-of-context edge already exists
2335         oocEdgeExisting.setBeta(Canonical.unionORpreds(oocEdgeExisting.getBeta(),
2336                                                        toCalleeContext(reCaller.getBeta(),
2337                                                                        preds,
2338                                                                        oocHrnIdOoc2callee
2339                                                                        )
2340                                                        )
2341                                 );
2342
2343         oocEdgeExisting.setPreds(Canonical.join(oocEdgeExisting.getPreds(),
2344                                                 preds
2345                                                 )
2346                                  );
2347
2348         oocEdgeExisting.setTaints(Canonical.unionORpreds(oocEdgeExisting.getTaints(),
2349                                                          toCalleeContext(reCaller.getTaints(),
2350                                                                          preds
2351                                                                          )
2352                                                          )
2353                                   );
2354
2355         HeapRegionNode hrnCalleeAndOutContext =
2356           (HeapRegionNode) oocEdgeExisting.getSrc();
2357         hrnCalleeAndOutContext.setAlpha(Canonical.unionORpreds(hrnCalleeAndOutContext.getAlpha(),
2358                                                                toCalleeContext(oocReach,
2359                                                                                preds,
2360                                                                                oocHrnIdOoc2callee
2361                                                                                )
2362                                                                )
2363                                         );
2364
2365         assert hrnCalleeAndOutContext.reachHasOnlyOOC();
2366       }
2367     }
2368
2369
2370     if( writeDebugDOTs ) {
2371       debugGraphPrefix = String.format("call%03d", debugCallSiteVisitCounter);
2372       rg.writeGraph(debugGraphPrefix+"calleeview",
2373                     resolveMethodDebugDOTwriteLabels,
2374                     resolveMethodDebugDOTselectTemps,
2375                     resolveMethodDebugDOTpruneGarbage,
2376                     resolveMethodDebugDOThideReach,
2377                     resolveMethodDebugDOThideSubsetReach,
2378                     resolveMethodDebugDOThidePreds,
2379                     resolveMethodDebugDOThideEdgeTaints);
2380     }
2381
2382     return rg;
2383   }
2384
2385   private static Hashtable<String, Integer> oocid2hrnid =
2386     new Hashtable<String, Integer>();
2387
2388
2389   private static boolean resolveMethodDebugDOTwriteLabels     = true;
2390   private static boolean resolveMethodDebugDOTselectTemps     = true;
2391   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
2392   private static boolean resolveMethodDebugDOThideReach       = false;
2393   private static boolean resolveMethodDebugDOThideSubsetReach = true;
2394   private static boolean resolveMethodDebugDOThidePreds       = false;
2395   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
2396
2397   static String debugGraphPrefix;
2398   static int debugCallSiteVisitCounter;
2399   static int debugCallSiteVisitStartCapture;
2400   static int debugCallSiteNumVisitsToCapture;
2401   static boolean debugCallSiteStopAfter;
2402
2403
2404   public void
2405   resolveMethodCall(FlatCall fc,
2406                     FlatMethod fmCallee,
2407                     ReachGraph rgCallee,
2408                     Set<Integer> callerNodeIDsCopiedToCallee,
2409                     boolean writeDebugDOTs
2410                     ) {
2411
2412     if( writeDebugDOTs ) {
2413
2414       System.out.println("  Writing out visit "+
2415                          debugCallSiteVisitCounter+
2416                          " to debug call site");
2417
2418       debugGraphPrefix = String.format("call%03d",
2419                                        debugCallSiteVisitCounter);
2420
2421       rgCallee.writeGraph(debugGraphPrefix+"callee",
2422                           resolveMethodDebugDOTwriteLabels,
2423                           resolveMethodDebugDOTselectTemps,
2424                           resolveMethodDebugDOTpruneGarbage,
2425                           resolveMethodDebugDOThideReach,
2426                           resolveMethodDebugDOThideSubsetReach,
2427                           resolveMethodDebugDOThidePreds,
2428                           resolveMethodDebugDOThideEdgeTaints);
2429
2430       writeGraph(debugGraphPrefix+"caller00In",
2431                  resolveMethodDebugDOTwriteLabels,
2432                  resolveMethodDebugDOTselectTemps,
2433                  resolveMethodDebugDOTpruneGarbage,
2434                  resolveMethodDebugDOThideReach,
2435                  resolveMethodDebugDOThideSubsetReach,
2436                  resolveMethodDebugDOThidePreds,
2437                  resolveMethodDebugDOThideEdgeTaints,
2438                  callerNodeIDsCopiedToCallee);
2439     }
2440
2441
2442
2443     // method call transfer function steps:
2444     // 1. Use current callee-reachable heap (CRH) to test callee
2445     //    predicates and mark what will be coming in.
2446     // 2. Wipe CRH out of caller.
2447     // 3. Transplant marked callee parts in:
2448     //    a) bring in nodes
2449     //    b) bring in callee -> callee edges
2450     //    c) resolve out-of-context -> callee edges
2451     //    d) assign return value
2452     // 4. Collapse shadow nodes down
2453     // 5. Global sweep it.
2454
2455
2456     // 1. mark what callee elements have satisfied predicates
2457     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
2458       new Hashtable<HeapRegionNode, ExistPredSet>();
2459
2460     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
2461       new Hashtable<RefEdge, ExistPredSet>();
2462
2463     Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >
2464     calleeNode2calleeStatesSatisfied =
2465       new Hashtable< HeapRegionNode, Hashtable<ReachState, ExistPredSet> >();
2466
2467     Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >
2468     calleeEdge2calleeStatesSatisfied =
2469       new Hashtable< RefEdge, Hashtable<ReachState, ExistPredSet> >();
2470
2471     Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >
2472     calleeEdge2calleeTaintsSatisfied =
2473       new Hashtable< RefEdge, Hashtable<Taint, ExistPredSet> >();
2474
2475     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
2476       new Hashtable< RefEdge, Set<RefSrcNode> >();
2477
2478
2479
2480     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2481     while( meItr.hasNext() ) {
2482       Map.Entry me        = (Map.Entry)meItr.next();
2483       Integer id        = (Integer)        me.getKey();
2484       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2485
2486       // if a callee element's predicates are satisfied then a set
2487       // of CALLER predicates is returned: they are the predicates
2488       // that the callee element moved into the caller context
2489       // should have, and it is inefficient to find this again later
2490       ExistPredSet predsIfSatis =
2491         hrnCallee.getPreds().isSatisfiedBy(this,
2492                                            callerNodeIDsCopiedToCallee,
2493                                            null);
2494
2495       if( predsIfSatis != null ) {
2496         calleeNodesSatisfied.put(hrnCallee, predsIfSatis);
2497       } else {
2498         // otherwise don't bother looking at edges to this node
2499         continue;
2500       }
2501
2502
2503
2504       // since the node is coming over, find out which reach
2505       // states on it should come over, too
2506       assert calleeNode2calleeStatesSatisfied.get(hrnCallee) == null;
2507
2508       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2509       while( stateItr.hasNext() ) {
2510         ReachState stateCallee = stateItr.next();
2511
2512         predsIfSatis =
2513           stateCallee.getPreds().isSatisfiedBy(this,
2514                                                callerNodeIDsCopiedToCallee,
2515                                                null);
2516         if( predsIfSatis != null ) {
2517
2518           Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2519             calleeNode2calleeStatesSatisfied.get(hrnCallee);
2520
2521           if( calleeStatesSatisfied == null ) {
2522             calleeStatesSatisfied =
2523               new Hashtable<ReachState, ExistPredSet>();
2524
2525             calleeNode2calleeStatesSatisfied.put(hrnCallee, calleeStatesSatisfied);
2526           }
2527
2528           calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2529         }
2530       }
2531
2532       // then look at edges to the node
2533       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2534       while( reItr.hasNext() ) {
2535         RefEdge reCallee  = reItr.next();
2536         RefSrcNode rsnCallee = reCallee.getSrc();
2537
2538         // (caller local variables to in-context heap regions)
2539         // have an (out-of-context heap region -> in-context heap region)
2540         // abstraction in the callEE, so its true we never need to
2541         // look at a (var node -> heap region) edge in callee to bring
2542         // those over for the call site transfer, except for the special
2543         // case of *RETURN var* -> heap region edges.
2544         // What about (param var->heap region)
2545         // edges in callee? They are dealt with below this loop.
2546
2547         if( rsnCallee instanceof VariableNode ) {
2548
2549           // looking for the return-value variable only
2550           VariableNode vnCallee = (VariableNode) rsnCallee;
2551           if( vnCallee.getTempDescriptor() != tdReturn ) {
2552             continue;
2553           }
2554
2555           TempDescriptor returnTemp = fc.getReturnTemp();
2556           if( returnTemp == null ||
2557               !DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2558               ) {
2559             continue;
2560           }
2561
2562           // note that the assignment of the return value is to a
2563           // variable in the caller which is out-of-context with
2564           // respect to the callee
2565           VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2566           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2567           rsnCallers.add(vnLhsCaller);
2568           calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2569
2570
2571         } else {
2572           // for HeapRegionNode callee sources...
2573
2574           // first see if the source is out-of-context, and only
2575           // proceed with this edge if we find some caller-context
2576           // matches
2577           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2578           boolean matchedOutOfContext = false;
2579
2580           if( !hrnSrcCallee.isOutOfContext() ) {
2581
2582             predsIfSatis =
2583               hrnSrcCallee.getPreds().isSatisfiedBy(this,
2584                                                     callerNodeIDsCopiedToCallee,
2585                                                     null);
2586             if( predsIfSatis != null ) {
2587               calleeNodesSatisfied.put(hrnSrcCallee, predsIfSatis);
2588             } else {
2589               // otherwise forget this edge
2590               continue;
2591             }
2592
2593           } else {
2594             // hrnSrcCallee is out-of-context
2595             assert !calleeEdges2oocCallerSrcMatches.containsKey(reCallee);
2596
2597             Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2598
2599             // use the isSatisfiedBy with a non-null callers set to capture
2600             // nodes in the caller that match the predicates
2601             reCallee.getPreds().isSatisfiedBy( this,
2602                                                callerNodeIDsCopiedToCallee,
2603                                                rsnCallers );
2604
2605             if( !rsnCallers.isEmpty() ) {
2606               matchedOutOfContext = true;
2607               calleeEdges2oocCallerSrcMatches.put(reCallee, rsnCallers);
2608             }
2609           }
2610
2611           if( hrnSrcCallee.isOutOfContext() &&
2612               !matchedOutOfContext ) {
2613             continue;
2614           }
2615         }
2616
2617
2618         predsIfSatis =
2619           reCallee.getPreds().isSatisfiedBy(this,
2620                                             callerNodeIDsCopiedToCallee,
2621                                             null);
2622
2623
2624         if( predsIfSatis != null ) {
2625           calleeEdgesSatisfied.put(reCallee, predsIfSatis);
2626
2627           // since the edge is coming over, find out which reach
2628           // states on it should come over, too
2629           assert calleeEdge2calleeStatesSatisfied.get(reCallee) == null;
2630
2631           stateItr = reCallee.getBeta().iterator();
2632           while( stateItr.hasNext() ) {
2633             ReachState stateCallee = stateItr.next();
2634
2635             predsIfSatis =
2636               stateCallee.getPreds().isSatisfiedBy(this,
2637                                                    callerNodeIDsCopiedToCallee,
2638                                                    null);
2639             if( predsIfSatis != null ) {
2640
2641               Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
2642                 calleeEdge2calleeStatesSatisfied.get(reCallee);
2643
2644               if( calleeStatesSatisfied == null ) {
2645                 calleeStatesSatisfied =
2646                   new Hashtable<ReachState, ExistPredSet>();
2647
2648                 calleeEdge2calleeStatesSatisfied.put(reCallee, calleeStatesSatisfied);
2649               }
2650
2651               calleeStatesSatisfied.put(stateCallee, predsIfSatis);
2652             }
2653           }
2654
2655           // since the edge is coming over, find out which taints
2656           // on it should come over, too
2657           assert calleeEdge2calleeTaintsSatisfied.get(reCallee) == null;
2658
2659           Iterator<Taint> tItr = reCallee.getTaints().iterator();
2660           while( tItr.hasNext() ) {
2661             Taint tCallee = tItr.next();
2662
2663             predsIfSatis =
2664               tCallee.getPreds().isSatisfiedBy(this,
2665                                                callerNodeIDsCopiedToCallee,
2666                                                null);
2667             if( predsIfSatis != null ) {
2668
2669               Hashtable<Taint, ExistPredSet> calleeTaintsSatisfied =
2670                 calleeEdge2calleeTaintsSatisfied.get(reCallee);
2671
2672               if( calleeTaintsSatisfied == null ) {
2673                 calleeTaintsSatisfied =
2674                   new Hashtable<Taint, ExistPredSet>();
2675
2676                 calleeEdge2calleeTaintsSatisfied.put(reCallee, calleeTaintsSatisfied);
2677               }
2678
2679               calleeTaintsSatisfied.put(tCallee, predsIfSatis);
2680             }
2681           }
2682         }
2683       }
2684     }
2685
2686     if( writeDebugDOTs ) {
2687       writeGraph(debugGraphPrefix+"caller20BeforeWipe",
2688                  resolveMethodDebugDOTwriteLabels,
2689                  resolveMethodDebugDOTselectTemps,
2690                  resolveMethodDebugDOTpruneGarbage,
2691                  resolveMethodDebugDOThideReach,
2692                  resolveMethodDebugDOThideSubsetReach,
2693                  resolveMethodDebugDOThidePreds,
2694                  resolveMethodDebugDOThideEdgeTaints);
2695     }
2696
2697
2698     // 2. predicates tested, ok to wipe out caller part
2699     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2700     while( hrnItr.hasNext() ) {
2701       Integer hrnID     = hrnItr.next();
2702       HeapRegionNode hrnCaller = id2hrn.get(hrnID);
2703       assert hrnCaller != null;
2704
2705       // when clearing off nodes, also eliminate variable
2706       // references
2707       wipeOut(hrnCaller, true);
2708     }
2709
2710     // if we are assigning the return value to something, clobber now
2711     // as part of the wipe
2712     TempDescriptor returnTemp = fc.getReturnTemp();
2713     if( returnTemp != null &&
2714         DisjointAnalysis.shouldAnalysisTrack(returnTemp.getType() )
2715         ) {
2716
2717       VariableNode vnLhsCaller = getVariableNodeFromTemp(returnTemp);
2718       clearRefEdgesFrom(vnLhsCaller, null, null, true);
2719     }
2720
2721
2722
2723
2724     if( writeDebugDOTs ) {
2725       writeGraph(debugGraphPrefix+"caller30BeforeAddingNodes",
2726                  resolveMethodDebugDOTwriteLabels,
2727                  resolveMethodDebugDOTselectTemps,
2728                  resolveMethodDebugDOTpruneGarbage,
2729                  resolveMethodDebugDOThideReach,
2730                  resolveMethodDebugDOThideSubsetReach,
2731                  resolveMethodDebugDOThidePreds,
2732                  resolveMethodDebugDOThideEdgeTaints);
2733     }
2734
2735
2736
2737
2738     // 3. callee elements with satisfied preds come in, note that
2739     //    the mapping of elements satisfied to preds is like this:
2740     //    A callee element EE has preds EEp that are satisfied by
2741     //    some caller element ER.  We bring EE into the caller
2742     //    context as ERee with the preds of ER, namely ERp, which
2743     //    in the following algorithm is the value in the mapping
2744
2745     // 3.a) nodes
2746     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2747     while( satisItr.hasNext() ) {
2748       Map.Entry me        = (Map.Entry)satisItr.next();
2749       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2750       ExistPredSet preds     = (ExistPredSet)   me.getValue();
2751
2752       // TODO: I think its true that the current implementation uses
2753       // the type of the OOC region and the predicates OF THE EDGE from
2754       // it to link everything up in caller context, so that's why we're
2755       // skipping this... maybe that's a sillier way to do it?
2756       if( hrnCallee.isOutOfContext() ) {
2757         continue;
2758       }
2759
2760       AllocSite as = hrnCallee.getAllocSite();
2761       allocSites.add(as);
2762
2763       Integer hrnIDshadow = as.getShadowIDfromID(hrnCallee.getID() );
2764
2765       HeapRegionNode hrnCaller = id2hrn.get(hrnIDshadow);
2766       if( hrnCaller == null ) {
2767         hrnCaller =
2768           createNewHeapRegionNode(hrnIDshadow,                 // id or null to generate a new one
2769                                   hrnCallee.isSingleObject(),  // single object?
2770                                   hrnCallee.isNewSummary(),    // summary?
2771                                   false,                       // out-of-context?
2772                                   hrnCallee.getType(),         // type
2773                                   hrnCallee.getAllocSite(),    // allocation site
2774                                   toCallerContext(hrnCallee.getInherent(),
2775                                                   calleeNode2calleeStatesSatisfied.get(hrnCallee) ),     // inherent reach
2776                                   null,                        // current reach
2777                                   predsEmpty,                  // predicates
2778                                   hrnCallee.getDescription()   // description
2779                                   );
2780       } else {
2781         assert hrnCaller.isWiped();
2782       }
2783
2784       hrnCaller.setAlpha(toCallerContext(hrnCallee.getAlpha(),
2785                                          calleeNode2calleeStatesSatisfied.get(hrnCallee)
2786                                          )
2787                          );
2788
2789       hrnCaller.setPreds(preds);
2790     }
2791
2792
2793
2794
2795
2796     if( writeDebugDOTs ) {
2797       writeGraph(debugGraphPrefix+"caller31BeforeAddingEdges",
2798                  resolveMethodDebugDOTwriteLabels,
2799                  resolveMethodDebugDOTselectTemps,
2800                  resolveMethodDebugDOTpruneGarbage,
2801                  resolveMethodDebugDOThideReach,
2802                  resolveMethodDebugDOThideSubsetReach,
2803                  resolveMethodDebugDOThidePreds,
2804                  resolveMethodDebugDOThideEdgeTaints);
2805     }
2806
2807
2808     // set these up during the next procedure so after
2809     // the caller has all of its nodes and edges put
2810     // back together we can propagate the callee's
2811     // reach changes backwards into the caller graph
2812     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2813
2814     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2815       new Hashtable<RefEdge, ChangeSet>();
2816
2817
2818     // 3.b) callee -> callee edges AND out-of-context -> callee
2819     //      which includes return temp -> callee edges now, too
2820     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2821     while( satisItr.hasNext() ) {
2822       Map.Entry me       = (Map.Entry)satisItr.next();
2823       RefEdge reCallee = (RefEdge)      me.getKey();
2824       ExistPredSet preds    = (ExistPredSet) me.getValue();
2825
2826       HeapRegionNode hrnDstCallee = reCallee.getDst();
2827       AllocSite asDst        = hrnDstCallee.getAllocSite();
2828       allocSites.add(asDst);
2829
2830       Integer hrnIDDstShadow =
2831         asDst.getShadowIDfromID(hrnDstCallee.getID() );
2832
2833       HeapRegionNode hrnDstCaller = id2hrn.get(hrnIDDstShadow);
2834       assert hrnDstCaller != null;
2835
2836
2837       RefSrcNode rsnCallee = reCallee.getSrc();
2838
2839       Set<RefSrcNode> rsnCallers =
2840         new HashSet<RefSrcNode>();
2841
2842       Set<RefSrcNode> oocCallers =
2843         calleeEdges2oocCallerSrcMatches.get(reCallee);
2844
2845       if( rsnCallee instanceof HeapRegionNode ) {
2846         HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2847         if( hrnCalleeSrc.isOutOfContext() ) {
2848           assert oocCallers != null;
2849         }
2850       }
2851
2852
2853       if( oocCallers == null ) {
2854         // there are no out-of-context matches, so it's
2855         // either a param/arg var or one in-context heap region
2856         if( rsnCallee instanceof VariableNode ) {
2857           // variable -> node in the callee should only
2858           // come into the caller if its from a param var
2859           VariableNode vnCallee = (VariableNode) rsnCallee;
2860           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2861           TempDescriptor tdArg    = fc.getArgMatchingParam(fmCallee,
2862                                                            tdParam);
2863           if( tdArg == null ) {
2864             // this means the variable isn't a parameter, its local
2865             // to the callee so we ignore it in call site transfer
2866             // shouldn't this NEVER HAPPEN?
2867             assert false;
2868           }
2869
2870           rsnCallers.add(this.getVariableNodeFromTemp(tdArg) );
2871
2872         } else {
2873           // otherwise source is in context, one region
2874
2875           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2876
2877           // translate an in-context node to shadow
2878           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2879           allocSites.add(asSrc);
2880
2881           Integer hrnIDSrcShadow =
2882             asSrc.getShadowIDfromID(hrnSrcCallee.getID() );
2883
2884           HeapRegionNode hrnSrcCallerShadow =
2885             this.id2hrn.get(hrnIDSrcShadow);
2886
2887           assert hrnSrcCallerShadow != null;
2888
2889           rsnCallers.add(hrnSrcCallerShadow);
2890         }
2891
2892       } else {
2893         // otherwise we have a set of out-of-context srcs
2894         // that should NOT be translated to shadow nodes
2895         assert !oocCallers.isEmpty();
2896         rsnCallers.addAll(oocCallers);
2897       }
2898
2899       // now make all caller edges we've identified from
2900       // this callee edge with a satisfied predicate
2901       assert !rsnCallers.isEmpty();
2902       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2903       while( rsnItr.hasNext() ) {
2904         RefSrcNode rsnCaller = rsnItr.next();
2905
2906         RefEdge reCaller = new RefEdge(rsnCaller,
2907                                        hrnDstCaller,
2908                                        reCallee.getType(),
2909                                        reCallee.getField(),
2910                                        toCallerContext(reCallee.getBeta(),
2911                                                        calleeEdge2calleeStatesSatisfied.get(reCallee) ),
2912                                        preds,
2913                                        toCallerContext(reCallee.getTaints(),
2914                                                        calleeEdge2calleeTaintsSatisfied.get(reCallee) )
2915                                        );
2916
2917         ChangeSet cs = ChangeSet.factory();
2918         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2919         while( rsItr.hasNext() ) {
2920           ReachState state          = rsItr.next();
2921           ExistPredSet predsPreCallee = state.getPreds();
2922
2923           if( state.isEmpty() ) {
2924             continue;
2925           }
2926
2927           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2928           while( predItr.hasNext() ) {
2929             ExistPred pred = predItr.next();
2930             ReachState old = pred.ne_state;
2931
2932             if( old == null ) {
2933               old = rstateEmpty;
2934             }
2935
2936             cs = Canonical.add(cs,
2937                                ChangeTuple.factory(old,
2938                                                    state
2939                                                    )
2940                                );
2941           }
2942         }
2943
2944         // we're just going to use the convenient "merge-if-exists"
2945         // edge call below, but still take a separate look if there
2946         // is an existing caller edge to build change sets properly
2947         if( !cs.isEmpty() ) {
2948           RefEdge edgeExisting = rsnCaller.getReferenceTo(hrnDstCaller,
2949                                                           reCallee.getType(),
2950                                                           reCallee.getField()
2951                                                           );
2952           if( edgeExisting != null ) {
2953             ChangeSet csExisting = edgePlannedChanges.get(edgeExisting);
2954             if( csExisting == null ) {
2955               csExisting = ChangeSet.factory();
2956             }
2957             edgePlannedChanges.put(edgeExisting,
2958                                    Canonical.union(csExisting,
2959                                                    cs
2960                                                    )
2961                                    );
2962           } else {
2963             edgesForPropagation.add(reCaller);
2964             assert !edgePlannedChanges.containsKey(reCaller);
2965             edgePlannedChanges.put(reCaller, cs);
2966           }
2967         }
2968
2969         // then add new caller edge or merge
2970         addEdgeOrMergeWithExisting(reCaller);
2971       }
2972     }
2973
2974
2975
2976
2977
2978     if( writeDebugDOTs ) {
2979       writeGraph(debugGraphPrefix+"caller38propagateReach",
2980                  resolveMethodDebugDOTwriteLabels,
2981                  resolveMethodDebugDOTselectTemps,
2982                  resolveMethodDebugDOTpruneGarbage,
2983                  resolveMethodDebugDOThideReach,
2984                  resolveMethodDebugDOThideSubsetReach,
2985                  resolveMethodDebugDOThidePreds,
2986                  resolveMethodDebugDOThideEdgeTaints);
2987     }
2988
2989     // propagate callee reachability changes to the rest
2990     // of the caller graph edges
2991     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2992
2993     propagateTokensOverEdges( edgesForPropagation,  // source edges
2994                               edgePlannedChanges,   // map src edge to change set
2995                               edgesUpdated,         // list of updated edges
2996                               null );
2997
2998     // commit beta' (beta<-betaNew)
2999     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
3000     while( edgeItr.hasNext() ) {
3001       edgeItr.next().applyBetaNew();
3002     }
3003
3004
3005
3006
3007
3008
3009
3010     if( writeDebugDOTs ) {
3011       writeGraph(debugGraphPrefix+"caller40BeforeShadowMerge",
3012                  resolveMethodDebugDOTwriteLabels,
3013                  resolveMethodDebugDOTselectTemps,
3014                  resolveMethodDebugDOTpruneGarbage,
3015                  resolveMethodDebugDOThideReach,
3016                  resolveMethodDebugDOThideSubsetReach,
3017                  resolveMethodDebugDOThidePreds,
3018                  resolveMethodDebugDOThideEdgeTaints);
3019     }
3020
3021
3022     // 4) merge shadow nodes so alloc sites are back to k
3023     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
3024     while( asItr.hasNext() ) {
3025       // for each allocation site do the following to merge
3026       // shadow nodes (newest from callee) with any existing
3027       // look for the newest normal and newest shadow "slot"
3028       // not being used, transfer normal to shadow.  Keep
3029       // doing this until there are no more normal nodes, or
3030       // no empty shadow slots: then merge all remaining normal
3031       // nodes into the shadow summary.  Finally, convert all
3032       // shadow to their normal versions.
3033       AllocSite as = asItr.next();
3034       int ageNorm = 0;
3035       int ageShad = 0;
3036
3037       while( ageNorm < allocationDepth &&
3038              ageShad < allocationDepth ) {
3039
3040         // first, are there any normal nodes left?
3041         Integer idNorm  = as.getIthOldest(ageNorm);
3042         HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3043         if( hrnNorm == null ) {
3044           // no, this age of normal node not in the caller graph
3045           ageNorm++;
3046           continue;
3047         }
3048
3049         // yes, a normal node exists, is there an empty shadow
3050         // "slot" to transfer it onto?
3051         HeapRegionNode hrnShad = getIthNode(as, ageShad, true);
3052         if( !hrnShad.isWiped() ) {
3053           // no, this age of shadow node is not empty
3054           ageShad++;
3055           continue;
3056         }
3057
3058         // yes, this shadow node is empty
3059         transferOnto(hrnNorm, hrnShad);
3060         ageNorm++;
3061         ageShad++;
3062       }
3063
3064       // now, while there are still normal nodes but no shadow
3065       // slots, merge normal nodes into the shadow summary
3066       while( ageNorm < allocationDepth ) {
3067
3068         // first, are there any normal nodes left?
3069         Integer idNorm  = as.getIthOldest(ageNorm);
3070         HeapRegionNode hrnNorm = id2hrn.get(idNorm);
3071         if( hrnNorm == null ) {
3072           // no, this age of normal node not in the caller graph
3073           ageNorm++;
3074           continue;
3075         }
3076
3077         // yes, a normal node exists, so get the shadow summary
3078         HeapRegionNode summShad = getSummaryNode(as, true);
3079         mergeIntoSummary(hrnNorm, summShad);
3080
3081         // now tokens in reachability sets need to age also
3082         Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3083         while( itrAllHRNodes.hasNext() ) {
3084           Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
3085           HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3086
3087           ageTuplesFrom(as, hrnToAge);
3088
3089           Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencers();
3090           while( itrEdges.hasNext() ) {
3091             ageTuplesFrom(as, itrEdges.next() );
3092           }
3093         }
3094
3095         ageNorm++;
3096       }
3097
3098       // if there is a normal summary, merge it into shadow summary
3099       Integer idNorm   = as.getSummary();
3100       HeapRegionNode summNorm = id2hrn.get(idNorm);
3101       if( summNorm != null ) {
3102         HeapRegionNode summShad = getSummaryNode(as, true);
3103         mergeIntoSummary(summNorm, summShad);
3104       }
3105
3106       // finally, flip all existing shadow nodes onto the normal
3107       for( int i = 0; i < allocationDepth; ++i ) {
3108         Integer idShad  = as.getIthOldestShadow(i);
3109         HeapRegionNode hrnShad = id2hrn.get(idShad);
3110         if( hrnShad != null ) {
3111           // flip it
3112           HeapRegionNode hrnNorm = getIthNode(as, i, false);
3113           assert hrnNorm.isWiped();
3114           transferOnto(hrnShad, hrnNorm);
3115         }
3116       }
3117
3118       Integer idShad   = as.getSummaryShadow();
3119       HeapRegionNode summShad = id2hrn.get(idShad);
3120       if( summShad != null ) {
3121         summNorm = getSummaryNode(as, false);
3122         transferOnto(summShad, summNorm);
3123       }
3124     }
3125
3126
3127
3128
3129
3130
3131     if( writeDebugDOTs ) {
3132       writeGraph(debugGraphPrefix+"caller45BeforeUnshadow",
3133                  resolveMethodDebugDOTwriteLabels,
3134                  resolveMethodDebugDOTselectTemps,
3135                  resolveMethodDebugDOTpruneGarbage,
3136                  resolveMethodDebugDOThideReach,
3137                  resolveMethodDebugDOThideSubsetReach,
3138                  resolveMethodDebugDOThidePreds,
3139                  resolveMethodDebugDOThideEdgeTaints);
3140     }
3141
3142
3143     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3144     while( itrAllHRNodes.hasNext() ) {
3145       Map.Entry me  = (Map.Entry)itrAllHRNodes.next();
3146       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3147
3148       hrn.setAlpha(unshadow(hrn.getAlpha() ) );
3149
3150       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
3151       while( itrEdges.hasNext() ) {
3152         RefEdge re = itrEdges.next();
3153         re.setBeta(unshadow(re.getBeta() ) );
3154       }
3155     }
3156
3157
3158
3159
3160     if( writeDebugDOTs ) {
3161       writeGraph(debugGraphPrefix+"caller50BeforeGlobalSweep",
3162                  resolveMethodDebugDOTwriteLabels,
3163                  resolveMethodDebugDOTselectTemps,
3164                  resolveMethodDebugDOTpruneGarbage,
3165                  resolveMethodDebugDOThideReach,
3166                  resolveMethodDebugDOThideSubsetReach,
3167                  resolveMethodDebugDOThidePreds,
3168                  resolveMethodDebugDOThideEdgeTaints);
3169     }
3170
3171
3172     // 5.
3173     if( !DISABLE_GLOBAL_SWEEP ) {
3174       globalSweep();
3175     }
3176
3177
3178     if( writeDebugDOTs ) {
3179       writeGraph(debugGraphPrefix+"caller90AfterTransfer",
3180                  resolveMethodDebugDOTwriteLabels,
3181                  resolveMethodDebugDOTselectTemps,
3182                  resolveMethodDebugDOTpruneGarbage,
3183                  resolveMethodDebugDOThideReach,
3184                  resolveMethodDebugDOThideSubsetReach,
3185                  resolveMethodDebugDOThidePreds,
3186                  resolveMethodDebugDOThideEdgeTaints);
3187     }
3188   }
3189
3190
3191
3192   ////////////////////////////////////////////////////
3193   //
3194   //  Abstract garbage collection simply removes
3195   //  heap region nodes that are not mechanically
3196   //  reachable from a root set.  This step is
3197   //  essential for testing node and edge existence
3198   //  predicates efficiently
3199   //
3200   ////////////////////////////////////////////////////
3201   public void abstractGarbageCollect(Set<TempDescriptor> liveSet) {
3202
3203     // calculate a root set, will be different for Java
3204     // version of analysis versus Bamboo version
3205     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
3206
3207     // visit every variable in graph while building root
3208     // set, and do iterating on a copy, so we can remove
3209     // dead variables while we're at this
3210     Iterator makeCopyItr = td2vn.entrySet().iterator();
3211     Set entrysCopy  = new HashSet();
3212     while( makeCopyItr.hasNext() ) {
3213       entrysCopy.add(makeCopyItr.next() );
3214     }
3215
3216     Iterator eItr = entrysCopy.iterator();
3217     while( eItr.hasNext() ) {
3218       Map.Entry me = (Map.Entry)eItr.next();
3219       TempDescriptor td = (TempDescriptor) me.getKey();
3220       VariableNode vn = (VariableNode)   me.getValue();
3221
3222       if( liveSet.contains(td) ) {
3223         toVisit.add(vn);
3224
3225       } else {
3226         // dead var, remove completely from graph
3227         td2vn.remove(td);
3228         clearRefEdgesFrom(vn, null, null, true);
3229       }
3230     }
3231
3232     // everything visited in a traversal is
3233     // considered abstractly live
3234     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
3235
3236     while( !toVisit.isEmpty() ) {
3237       RefSrcNode rsn = toVisit.iterator().next();
3238       toVisit.remove(rsn);
3239       visited.add(rsn);
3240
3241       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
3242       while( hrnItr.hasNext() ) {
3243         RefEdge edge = hrnItr.next();
3244         HeapRegionNode hrn  = edge.getDst();
3245
3246         if( !visited.contains(hrn) ) {
3247           toVisit.add(hrn);
3248         }
3249       }
3250     }
3251
3252     // get a copy of the set to iterate over because
3253     // we're going to monkey with the graph when we
3254     // identify a garbage node
3255     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
3256     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
3257     while( hrnItr.hasNext() ) {
3258       hrnAllPrior.add(hrnItr.next() );
3259     }
3260
3261     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
3262     while( hrnAllItr.hasNext() ) {
3263       HeapRegionNode hrn = hrnAllItr.next();
3264
3265       if( !visited.contains(hrn) ) {
3266
3267         // heap region nodes are compared across ReachGraph
3268         // objects by their integer ID, so when discarding
3269         // garbage nodes we must also discard entries in
3270         // the ID -> heap region hashtable.
3271         id2hrn.remove(hrn.getID() );
3272
3273         // RefEdge objects are two-way linked between
3274         // nodes, so when a node is identified as garbage,
3275         // actively clear references to and from it so
3276         // live nodes won't have dangling RefEdge's
3277         wipeOut(hrn, true);
3278
3279         // if we just removed the last node from an allocation
3280         // site, it should be taken out of the ReachGraph's list
3281         AllocSite as = hrn.getAllocSite();
3282         if( !hasNodesOf(as) ) {
3283           allocSites.remove(as);
3284         }
3285       }
3286     }
3287   }
3288
3289   protected boolean hasNodesOf(AllocSite as) {
3290     if( id2hrn.containsKey(as.getSummary() ) ) {
3291       return true;
3292     }
3293
3294     for( int i = 0; i < allocationDepth; ++i ) {
3295       if( id2hrn.containsKey(as.getIthOldest(i) ) ) {
3296         return true;
3297       }
3298     }
3299     return false;
3300   }
3301
3302
3303   ////////////////////////////////////////////////////
3304   //
3305   //  This global sweep is an optional step to prune
3306   //  reachability sets that are not internally
3307   //  consistent with the global graph.  It should be
3308   //  invoked after strong updates or method calls.
3309   //
3310   ////////////////////////////////////////////////////
3311   public void globalSweep() {
3312
3313     // boldB is part of the phase 1 sweep
3314     // it has an in-context table and an out-of-context table
3315     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
3316       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3317
3318     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
3319       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
3320
3321     // visit every heap region to initialize alphaNew and betaNew,
3322     // and make a map of every hrnID to the source nodes it should
3323     // propagate forward from.  In-context flagged hrnID's propagate
3324     // from only the in-context node they name, but out-of-context
3325     // ID's may propagate from several out-of-context nodes
3326     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
3327       new Hashtable< Integer, Set<HeapRegionNode> >();
3328
3329     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
3330       new Hashtable< Integer, Set<HeapRegionNode> >();
3331
3332
3333     Iterator itrHrns = id2hrn.entrySet().iterator();
3334     while( itrHrns.hasNext() ) {
3335       Map.Entry me    = (Map.Entry)itrHrns.next();
3336       Integer hrnID = (Integer)        me.getKey();
3337       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3338
3339       // assert that this node and incoming edges have clean alphaNew
3340       // and betaNew sets, respectively
3341       assert rsetEmpty.equals(hrn.getAlphaNew() );
3342
3343       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
3344       while( itrRers.hasNext() ) {
3345         RefEdge edge = itrRers.next();
3346         assert rsetEmpty.equals(edge.getBetaNew() );
3347       }
3348
3349       // make a mapping of IDs to heap regions they propagate from
3350       if( hrn.isFlagged() ) {
3351         assert !hrn.isOutOfContext();
3352         assert !icID2srcs.containsKey(hrn.getID() );
3353
3354         // in-context flagged node IDs simply propagate from the
3355         // node they name
3356         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
3357         srcs.add(hrn);
3358         icID2srcs.put(hrn.getID(), srcs);
3359       }
3360
3361       if( hrn.isOutOfContext() ) {
3362         assert !hrn.isFlagged();
3363
3364         // the reachability states on an out-of-context
3365         // node are not really important (combinations of
3366         // IDs or arity)--what matters is that the states
3367         // specify which nodes this out-of-context node
3368         // stands in for.  For example, if the state [17?, 19*]
3369         // appears on the ooc node, it may serve as a source
3370         // for node 17? and a source for node 19.
3371         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3372         while( stateItr.hasNext() ) {
3373           ReachState state = stateItr.next();
3374
3375           Iterator<ReachTuple> rtItr = state.iterator();
3376           while( rtItr.hasNext() ) {
3377             ReachTuple rt = rtItr.next();
3378             assert rt.isOutOfContext();
3379
3380             Set<HeapRegionNode> srcs = oocID2srcs.get(rt.getHrnID() );
3381             if( srcs == null ) {
3382               srcs = new HashSet<HeapRegionNode>();
3383             }
3384             srcs.add(hrn);
3385             oocID2srcs.put(rt.getHrnID(), srcs);
3386           }
3387         }
3388       }
3389     }
3390
3391     // calculate boldB for all hrnIDs identified by the above
3392     // node traversal, propagating from every source
3393     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
3394
3395       Integer hrnID;
3396       Set<HeapRegionNode> srcs;
3397       boolean inContext;
3398
3399       if( !icID2srcs.isEmpty() ) {
3400         Map.Entry me = (Map.Entry)icID2srcs.entrySet().iterator().next();
3401         hrnID = (Integer)             me.getKey();
3402         srcs  = (Set<HeapRegionNode>)me.getValue();
3403         inContext = true;
3404         icID2srcs.remove(hrnID);
3405
3406       } else {
3407         assert !oocID2srcs.isEmpty();
3408
3409         Map.Entry me = (Map.Entry)oocID2srcs.entrySet().iterator().next();
3410         hrnID = (Integer)             me.getKey();
3411         srcs  = (Set<HeapRegionNode>)me.getValue();
3412         inContext = false;
3413         oocID2srcs.remove(hrnID);
3414       }
3415
3416
3417       Hashtable<RefEdge, ReachSet> boldB_f =
3418         new Hashtable<RefEdge, ReachSet>();
3419
3420       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
3421
3422       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
3423       while( hrnItr.hasNext() ) {
3424         HeapRegionNode hrn = hrnItr.next();
3425
3426         assert workSetEdges.isEmpty();
3427
3428         // initial boldB_f constraints
3429         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
3430         while( itrRees.hasNext() ) {
3431           RefEdge edge = itrRees.next();
3432
3433           assert !boldB_f.containsKey(edge);
3434           boldB_f.put(edge, edge.getBeta() );
3435
3436           assert !workSetEdges.contains(edge);
3437           workSetEdges.add(edge);
3438         }
3439
3440         // enforce the boldB_f constraint at edges until we reach a fixed point
3441         while( !workSetEdges.isEmpty() ) {
3442           RefEdge edge = workSetEdges.iterator().next();
3443           workSetEdges.remove(edge);
3444
3445           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
3446           while( itrPrime.hasNext() ) {
3447             RefEdge edgePrime = itrPrime.next();
3448
3449             ReachSet prevResult   = boldB_f.get(edgePrime);
3450             ReachSet intersection = Canonical.intersection(boldB_f.get(edge),
3451                                                            edgePrime.getBeta()
3452                                                            );
3453
3454             if( prevResult == null ||
3455                 Canonical.unionORpreds(prevResult,
3456                                        intersection).size()
3457                 > prevResult.size()
3458                 ) {
3459
3460               if( prevResult == null ) {
3461                 boldB_f.put(edgePrime,
3462                             Canonical.unionORpreds(edgePrime.getBeta(),
3463                                                    intersection
3464                                                    )
3465                             );
3466               } else {
3467                 boldB_f.put(edgePrime,
3468                             Canonical.unionORpreds(prevResult,
3469                                                    intersection
3470                                                    )
3471                             );
3472               }
3473               workSetEdges.add(edgePrime);
3474             }
3475           }
3476         }
3477       }
3478
3479       if( inContext ) {
3480         boldBic.put(hrnID, boldB_f);
3481       } else {
3482         boldBooc.put(hrnID, boldB_f);
3483       }
3484     }
3485
3486
3487     // use boldB to prune hrnIDs from alpha states that are impossible
3488     // and propagate the differences backwards across edges
3489     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3490
3491     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3492       new Hashtable<RefEdge, ChangeSet>();
3493
3494
3495     itrHrns = id2hrn.entrySet().iterator();
3496     while( itrHrns.hasNext() ) {
3497       Map.Entry me    = (Map.Entry)itrHrns.next();
3498       Integer hrnID = (Integer)        me.getKey();
3499       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3500
3501       // out-of-context nodes don't participate in the
3502       // global sweep, they serve as sources for the pass
3503       // performed above
3504       if( hrn.isOutOfContext() ) {
3505         continue;
3506       }
3507
3508       // the inherent states of a region are the exception
3509       // to removal as the global sweep prunes
3510       ReachTuple rtException = ReachTuple.factory(hrnID,
3511                                                   !hrn.isSingleObject(),
3512                                                   ReachTuple.ARITY_ONE,
3513                                                   false  // out-of-context
3514                                                   );
3515
3516       ChangeSet cts = ChangeSet.factory();
3517
3518       // mark hrnIDs for removal
3519       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3520       while( stateItr.hasNext() ) {
3521         ReachState stateOld = stateItr.next();
3522
3523         ReachState markedHrnIDs = ReachState.factory();
3524
3525         Iterator<ReachTuple> rtItr = stateOld.iterator();
3526         while( rtItr.hasNext() ) {
3527           ReachTuple rtOld = rtItr.next();
3528
3529           // never remove the inherent hrnID from a flagged region
3530           // because it is trivially satisfied
3531           if( hrn.isFlagged() ) {
3532             if( rtOld == rtException ) {
3533               continue;
3534             }
3535           }
3536
3537           // does boldB allow this hrnID?
3538           boolean foundState = false;
3539           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3540           while( incidentEdgeItr.hasNext() ) {
3541             RefEdge incidentEdge = incidentEdgeItr.next();
3542
3543             Hashtable<RefEdge, ReachSet> B;
3544             if( rtOld.isOutOfContext() ) {
3545               B = boldBooc.get(rtOld.getHrnID() );
3546             } else {
3547
3548               if( !id2hrn.containsKey(rtOld.getHrnID() ) ) {
3549                 // let symbols not in the graph get pruned
3550                 break;
3551               }
3552
3553               B = boldBic.get(rtOld.getHrnID() );
3554             }
3555
3556             if( B != null ) {
3557               ReachSet boldB_rtOld_incident = B.get(incidentEdge);
3558               if( boldB_rtOld_incident != null &&
3559                   boldB_rtOld_incident.containsIgnorePreds(stateOld) != null
3560                   ) {
3561                 foundState = true;
3562               }
3563             }
3564           }
3565
3566           if( !foundState ) {
3567             markedHrnIDs = Canonical.addUpArity(markedHrnIDs, rtOld);
3568           }
3569         }
3570
3571         // if there is nothing marked, just move on
3572         if( markedHrnIDs.isEmpty() ) {
3573           hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3574                                         stateOld
3575                                         )
3576                           );
3577           continue;
3578         }
3579
3580         // remove all marked hrnIDs and establish a change set that should
3581         // propagate backwards over edges from this node
3582         ReachState statePruned = ReachState.factory();
3583         rtItr = stateOld.iterator();
3584         while( rtItr.hasNext() ) {
3585           ReachTuple rtOld = rtItr.next();
3586
3587           if( !markedHrnIDs.containsTuple(rtOld) ) {
3588             statePruned = Canonical.addUpArity(statePruned, rtOld);
3589           }
3590         }
3591         assert !stateOld.equals(statePruned);
3592
3593         hrn.setAlphaNew(Canonical.add(hrn.getAlphaNew(),
3594                                       statePruned
3595                                       )
3596                         );
3597         ChangeTuple ct = ChangeTuple.factory(stateOld,
3598                                              statePruned
3599                                              );
3600         cts = Canonical.add(cts, ct);
3601       }
3602
3603       // throw change tuple set on all incident edges
3604       if( !cts.isEmpty() ) {
3605         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3606         while( incidentEdgeItr.hasNext() ) {
3607           RefEdge incidentEdge = incidentEdgeItr.next();
3608
3609           edgesForPropagation.add(incidentEdge);
3610
3611           if( edgePlannedChanges.get(incidentEdge) == null ) {
3612             edgePlannedChanges.put(incidentEdge, cts);
3613           } else {
3614             edgePlannedChanges.put(
3615               incidentEdge,
3616               Canonical.union(edgePlannedChanges.get(incidentEdge),
3617                               cts
3618                               )
3619               );
3620           }
3621         }
3622       }
3623     }
3624
3625     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3626
3627     propagateTokensOverEdges(edgesForPropagation,
3628                              edgePlannedChanges,
3629                              edgesUpdated,
3630                              null);
3631
3632     // at the end of the 1st phase reference edges have
3633     // beta, betaNew that correspond to beta and betaR
3634     //
3635     // commit beta<-betaNew, so beta=betaR and betaNew
3636     // will represent the beta' calculation in 2nd phase
3637     //
3638     // commit alpha<-alphaNew because it won't change
3639     HashSet<RefEdge> res = new HashSet<RefEdge>();
3640
3641     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3642     while( nodeItr.hasNext() ) {
3643       HeapRegionNode hrn = nodeItr.next();
3644
3645       // as mentioned above, out-of-context nodes only serve
3646       // as sources of reach states for the sweep, not part
3647       // of the changes
3648       if( hrn.isOutOfContext() ) {
3649         assert hrn.getAlphaNew().equals(rsetEmpty);
3650       } else {
3651         hrn.applyAlphaNew();
3652       }
3653
3654       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3655       while( itrRes.hasNext() ) {
3656         res.add(itrRes.next() );
3657       }
3658     }
3659
3660
3661     // 2nd phase
3662     Iterator<RefEdge> edgeItr = res.iterator();
3663     while( edgeItr.hasNext() ) {
3664       RefEdge edge = edgeItr.next();
3665       HeapRegionNode hrn  = edge.getDst();
3666
3667       // commit results of last phase
3668       if( edgesUpdated.contains(edge) ) {
3669         edge.applyBetaNew();
3670       }
3671
3672       // compute intial condition of 2nd phase
3673       edge.setBetaNew(Canonical.intersection(edge.getBeta(),
3674                                              hrn.getAlpha()
3675                                              )
3676                       );
3677     }
3678
3679     // every edge in the graph is the initial workset
3680     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3681     while( !edgeWorkSet.isEmpty() ) {
3682       RefEdge edgePrime = edgeWorkSet.iterator().next();
3683       edgeWorkSet.remove(edgePrime);
3684
3685       RefSrcNode rsn = edgePrime.getSrc();
3686       if( !(rsn instanceof HeapRegionNode) ) {
3687         continue;
3688       }
3689       HeapRegionNode hrn = (HeapRegionNode) rsn;
3690
3691       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3692       while( itrEdge.hasNext() ) {
3693         RefEdge edge = itrEdge.next();
3694
3695         ReachSet prevResult = edge.getBetaNew();
3696         assert prevResult != null;
3697
3698         ReachSet intersection =
3699           Canonical.intersection(edge.getBeta(),
3700                                  edgePrime.getBetaNew()
3701                                  );
3702
3703         if( Canonical.unionORpreds(prevResult,
3704                                    intersection
3705                                    ).size()
3706             > prevResult.size()
3707             ) {
3708
3709           edge.setBetaNew(
3710             Canonical.unionORpreds(prevResult,
3711                                    intersection
3712                                    )
3713             );
3714           edgeWorkSet.add(edge);
3715         }
3716       }
3717     }
3718
3719     // commit beta' (beta<-betaNew)
3720     edgeItr = res.iterator();
3721     while( edgeItr.hasNext() ) {
3722       edgeItr.next().applyBetaNew();
3723     }
3724   }
3725
3726
3727   // a useful assertion for debugging:
3728   // every in-context tuple on any edge or
3729   // any node should name a node that is
3730   // part of the graph
3731   public boolean inContextTuplesInGraph() {
3732
3733     Iterator hrnItr = id2hrn.entrySet().iterator();
3734     while( hrnItr.hasNext() ) {
3735       Map.Entry me  = (Map.Entry)hrnItr.next();
3736       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3737
3738       {
3739         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3740         while( stateItr.hasNext() ) {
3741           ReachState state = stateItr.next();
3742
3743           Iterator<ReachTuple> rtItr = state.iterator();
3744           while( rtItr.hasNext() ) {
3745             ReachTuple rt = rtItr.next();
3746
3747             if( !rt.isOutOfContext() ) {
3748               if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3749                 System.out.println(rt.getHrnID()+" is missing");
3750                 return false;
3751               }
3752             }
3753           }
3754         }
3755       }
3756
3757       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3758       while( edgeItr.hasNext() ) {
3759         RefEdge edge = edgeItr.next();
3760
3761         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3762         while( stateItr.hasNext() ) {
3763           ReachState state = stateItr.next();
3764
3765           Iterator<ReachTuple> rtItr = state.iterator();
3766           while( rtItr.hasNext() ) {
3767             ReachTuple rt = rtItr.next();
3768
3769             if( !rt.isOutOfContext() ) {
3770               if( !id2hrn.containsKey(rt.getHrnID() ) ) {
3771                 System.out.println(rt.getHrnID()+" is missing");
3772                 return false;
3773               }
3774             }
3775           }
3776         }
3777       }
3778     }
3779
3780     return true;
3781   }
3782
3783
3784   // another useful assertion for debugging
3785   public boolean noEmptyReachSetsInGraph() {
3786
3787     Iterator hrnItr = id2hrn.entrySet().iterator();
3788     while( hrnItr.hasNext() ) {
3789       Map.Entry me  = (Map.Entry)hrnItr.next();
3790       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3791
3792       if( !hrn.isOutOfContext() &&
3793           !hrn.isWiped()        &&
3794           hrn.getAlpha().isEmpty()
3795           ) {
3796         System.out.println("!!! "+hrn+" has an empty ReachSet !!!");
3797         return false;
3798       }
3799
3800       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3801       while( edgeItr.hasNext() ) {
3802         RefEdge edge = edgeItr.next();
3803
3804         if( edge.getBeta().isEmpty() ) {
3805           System.out.println("!!! "+edge+" has an empty ReachSet !!!");
3806           return false;
3807         }
3808       }
3809     }
3810
3811     return true;
3812   }
3813
3814
3815   public boolean everyReachStateWTrue() {
3816
3817     Iterator hrnItr = id2hrn.entrySet().iterator();
3818     while( hrnItr.hasNext() ) {
3819       Map.Entry me  = (Map.Entry)hrnItr.next();
3820       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3821
3822       {
3823         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3824         while( stateItr.hasNext() ) {
3825           ReachState state = stateItr.next();
3826
3827           if( !state.getPreds().equals(predsTrue) ) {
3828             return false;
3829           }
3830         }
3831       }
3832
3833       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3834       while( edgeItr.hasNext() ) {
3835         RefEdge edge = edgeItr.next();
3836
3837         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3838         while( stateItr.hasNext() ) {
3839           ReachState state = stateItr.next();
3840
3841           if( !state.getPreds().equals(predsTrue) ) {
3842             return false;
3843           }
3844         }
3845       }
3846     }
3847
3848     return true;
3849   }
3850
3851
3852
3853
3854   ////////////////////////////////////////////////////
3855   // in merge() and equals() methods the suffix A
3856   // represents the passed in graph and the suffix
3857   // B refers to the graph in this object
3858   // Merging means to take the incoming graph A and
3859   // merge it into B, so after the operation graph B
3860   // is the final result.
3861   ////////////////////////////////////////////////////
3862   protected void merge(ReachGraph rg) {
3863
3864     if( rg == null ) {
3865       return;
3866     }
3867
3868     mergeNodes(rg);
3869     mergeRefEdges(rg);
3870     mergeAllocSites(rg);
3871     mergeInaccessibleVars(rg);
3872   }
3873
3874   protected void mergeNodes(ReachGraph rg) {
3875
3876     // start with heap region nodes
3877     Set sA = rg.id2hrn.entrySet();
3878     Iterator iA = sA.iterator();
3879     while( iA.hasNext() ) {
3880       Map.Entry meA  = (Map.Entry)iA.next();
3881       Integer idA  = (Integer)        meA.getKey();
3882       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3883
3884       // if this graph doesn't have a node the
3885       // incoming graph has, allocate it
3886       if( !id2hrn.containsKey(idA) ) {
3887         HeapRegionNode hrnB = hrnA.copy();
3888         id2hrn.put(idA, hrnB);
3889
3890       } else {
3891         // otherwise this is a node present in both graphs
3892         // so make the new reachability set a union of the
3893         // nodes' reachability sets
3894         HeapRegionNode hrnB = id2hrn.get(idA);
3895         hrnB.setAlpha(Canonical.unionORpreds(hrnB.getAlpha(),
3896                                              hrnA.getAlpha()
3897                                              )
3898                       );
3899
3900         hrnB.setPreds(Canonical.join(hrnB.getPreds(),
3901                                      hrnA.getPreds()
3902                                      )
3903                       );
3904
3905
3906
3907         if( !hrnA.equals(hrnB) ) {
3908           rg.writeGraph("graphA");
3909           this.writeGraph("graphB");
3910           throw new Error("flagged not matching");
3911         }
3912
3913
3914
3915       }
3916     }
3917
3918     // now add any variable nodes that are in graph B but
3919     // not in A
3920     sA = rg.td2vn.entrySet();
3921     iA = sA.iterator();
3922     while( iA.hasNext() ) {
3923       Map.Entry meA = (Map.Entry)iA.next();
3924       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3925       VariableNode lnA = (VariableNode)   meA.getValue();
3926
3927       // if the variable doesn't exist in B, allocate and add it
3928       VariableNode lnB = getVariableNodeFromTemp(tdA);
3929     }
3930   }
3931
3932   protected void mergeRefEdges(ReachGraph rg) {
3933
3934     // between heap regions
3935     Set sA = rg.id2hrn.entrySet();
3936     Iterator iA = sA.iterator();
3937     while( iA.hasNext() ) {
3938       Map.Entry meA  = (Map.Entry)iA.next();
3939       Integer idA  = (Integer)        meA.getKey();
3940       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3941
3942       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3943       while( heapRegionsItrA.hasNext() ) {
3944         RefEdge edgeA     = heapRegionsItrA.next();
3945         HeapRegionNode hrnChildA = edgeA.getDst();
3946         Integer idChildA  = hrnChildA.getID();
3947
3948         // at this point we know an edge in graph A exists
3949         // idA -> idChildA, does this exist in B?
3950         assert id2hrn.containsKey(idA);
3951         HeapRegionNode hrnB        = id2hrn.get(idA);
3952         RefEdge edgeToMerge = null;
3953
3954         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3955         while( heapRegionsItrB.hasNext() &&
3956                edgeToMerge == null          ) {
3957
3958           RefEdge edgeB     = heapRegionsItrB.next();
3959           HeapRegionNode hrnChildB = edgeB.getDst();
3960           Integer idChildB  = hrnChildB.getID();
3961
3962           // don't use the RefEdge.equals() here because
3963           // we're talking about existence between graphs,
3964           // not intragraph equal
3965           if( idChildB.equals(idChildA) &&
3966               edgeB.typeAndFieldEquals(edgeA) ) {
3967
3968             edgeToMerge = edgeB;
3969           }
3970         }
3971
3972         // if the edge from A was not found in B,
3973         // add it to B.
3974         if( edgeToMerge == null ) {
3975           assert id2hrn.containsKey(idChildA);
3976           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
3977           edgeToMerge = edgeA.copy();
3978           edgeToMerge.setSrc(hrnB);
3979           edgeToMerge.setDst(hrnChildB);
3980           addRefEdge(hrnB, hrnChildB, edgeToMerge);
3981         }
3982         // otherwise, the edge already existed in both graphs
3983         // so merge their reachability sets
3984         else {
3985           // just replace this beta set with the union
3986           assert edgeToMerge != null;
3987           edgeToMerge.setBeta(
3988             Canonical.unionORpreds(edgeToMerge.getBeta(),
3989                                    edgeA.getBeta()
3990                                    )
3991             );
3992           edgeToMerge.setPreds(
3993             Canonical.join(edgeToMerge.getPreds(),
3994                            edgeA.getPreds()
3995                            )
3996             );
3997           edgeToMerge.setTaints(
3998             Canonical.union(edgeToMerge.getTaints(),
3999                             edgeA.getTaints()
4000                             )
4001             );
4002         }
4003       }
4004     }
4005
4006     // and then again from variable nodes
4007     sA = rg.td2vn.entrySet();
4008     iA = sA.iterator();
4009     while( iA.hasNext() ) {
4010       Map.Entry meA = (Map.Entry)iA.next();
4011       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4012       VariableNode vnA = (VariableNode)   meA.getValue();
4013
4014       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
4015       while( heapRegionsItrA.hasNext() ) {
4016         RefEdge edgeA     = heapRegionsItrA.next();
4017         HeapRegionNode hrnChildA = edgeA.getDst();
4018         Integer idChildA  = hrnChildA.getID();
4019
4020         // at this point we know an edge in graph A exists
4021         // tdA -> idChildA, does this exist in B?
4022         assert td2vn.containsKey(tdA);
4023         VariableNode vnB         = td2vn.get(tdA);
4024         RefEdge edgeToMerge = null;
4025
4026         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
4027         while( heapRegionsItrB.hasNext() &&
4028                edgeToMerge == null          ) {
4029
4030           RefEdge edgeB     = heapRegionsItrB.next();
4031           HeapRegionNode hrnChildB = edgeB.getDst();
4032           Integer idChildB  = hrnChildB.getID();
4033
4034           // don't use the RefEdge.equals() here because
4035           // we're talking about existence between graphs
4036           if( idChildB.equals(idChildA) &&
4037               edgeB.typeAndFieldEquals(edgeA) ) {
4038
4039             edgeToMerge = edgeB;
4040           }
4041         }
4042
4043         // if the edge from A was not found in B,
4044         // add it to B.
4045         if( edgeToMerge == null ) {
4046           assert id2hrn.containsKey(idChildA);
4047           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
4048           edgeToMerge = edgeA.copy();
4049           edgeToMerge.setSrc(vnB);
4050           edgeToMerge.setDst(hrnChildB);
4051           addRefEdge(vnB, hrnChildB, edgeToMerge);
4052         }
4053         // otherwise, the edge already existed in both graphs
4054         // so merge their reachability sets
4055         else {
4056           // just replace this beta set with the union
4057           edgeToMerge.setBeta(Canonical.unionORpreds(edgeToMerge.getBeta(),
4058                                                      edgeA.getBeta()
4059                                                      )
4060                               );
4061           edgeToMerge.setPreds(Canonical.join(edgeToMerge.getPreds(),
4062                                               edgeA.getPreds()
4063                                               )
4064                                );
4065           edgeToMerge.setTaints(
4066             Canonical.union(edgeToMerge.getTaints(),
4067                             edgeA.getTaints()
4068                             )
4069             );
4070         }
4071       }
4072     }
4073   }
4074
4075   protected void mergeAllocSites(ReachGraph rg) {
4076     allocSites.addAll(rg.allocSites);
4077   }
4078
4079   protected void mergeInaccessibleVars(ReachGraph rg) {
4080     inaccessibleVars.addAll(rg.inaccessibleVars);
4081   }
4082
4083
4084
4085   static public boolean dbgEquals = false;
4086
4087
4088   // it is necessary in the equals() member functions
4089   // to "check both ways" when comparing the data
4090   // structures of two graphs.  For instance, if all
4091   // edges between heap region nodes in graph A are
4092   // present and equal in graph B it is not sufficient
4093   // to say the graphs are equal.  Consider that there
4094   // may be edges in graph B that are not in graph A.
4095   // the only way to know that all edges in both graphs
4096   // are equally present is to iterate over both data
4097   // structures and compare against the other graph.
4098   public boolean equals(ReachGraph rg) {
4099
4100     if( rg == null ) {
4101       if( dbgEquals ) {
4102         System.out.println("rg is null");
4103       }
4104       return false;
4105     }
4106
4107     if( !areHeapRegionNodesEqual(rg) ) {
4108       if( dbgEquals ) {
4109         System.out.println("hrn not equal");
4110       }
4111       return false;
4112     }
4113
4114     if( !areVariableNodesEqual(rg) ) {
4115       if( dbgEquals ) {
4116         System.out.println("vars not equal");
4117       }
4118       return false;
4119     }
4120
4121     if( !areRefEdgesEqual(rg) ) {
4122       if( dbgEquals ) {
4123         System.out.println("edges not equal");
4124       }
4125       return false;
4126     }
4127
4128     if( !inaccessibleVars.equals(rg.inaccessibleVars) ) {
4129       return false;
4130     }
4131
4132     // if everything is equal up to this point,
4133     // assert that allocSites is also equal--
4134     // this data is redundant but kept for efficiency
4135     assert allocSites.equals(rg.allocSites);
4136
4137     return true;
4138   }
4139
4140
4141   protected boolean areHeapRegionNodesEqual(ReachGraph rg) {
4142
4143     if( !areallHRNinAalsoinBandequal(this, rg) ) {
4144       return false;
4145     }
4146
4147     if( !areallHRNinAalsoinBandequal(rg, this) ) {
4148       return false;
4149     }
4150
4151     return true;
4152   }
4153
4154   static protected boolean areallHRNinAalsoinBandequal(ReachGraph rgA,
4155                                                        ReachGraph rgB) {
4156     Set sA = rgA.id2hrn.entrySet();
4157     Iterator iA = sA.iterator();
4158     while( iA.hasNext() ) {
4159       Map.Entry meA  = (Map.Entry)iA.next();
4160       Integer idA  = (Integer)        meA.getKey();
4161       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4162
4163       if( !rgB.id2hrn.containsKey(idA) ) {
4164         return false;
4165       }
4166
4167       HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4168       if( !hrnA.equalsIncludingAlphaAndPreds(hrnB) ) {
4169         return false;
4170       }
4171     }
4172
4173     return true;
4174   }
4175
4176   protected boolean areVariableNodesEqual(ReachGraph rg) {
4177
4178     if( !areallVNinAalsoinBandequal(this, rg) ) {
4179       return false;
4180     }
4181
4182     if( !areallVNinAalsoinBandequal(rg, this) ) {
4183       return false;
4184     }
4185
4186     return true;
4187   }
4188
4189   static protected boolean areallVNinAalsoinBandequal(ReachGraph rgA,
4190                                                       ReachGraph rgB) {
4191     Set sA = rgA.td2vn.entrySet();
4192     Iterator iA = sA.iterator();
4193     while( iA.hasNext() ) {
4194       Map.Entry meA = (Map.Entry)iA.next();
4195       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4196
4197       if( !rgB.td2vn.containsKey(tdA) ) {
4198         return false;
4199       }
4200     }
4201
4202     return true;
4203   }
4204
4205
4206   protected boolean areRefEdgesEqual(ReachGraph rg) {
4207     if( !areallREinAandBequal(this, rg) ) {
4208       return false;
4209     }
4210
4211     if( !areallREinAandBequal(rg, this) ) {
4212       return false;
4213     }
4214
4215     return true;
4216   }
4217
4218   static protected boolean areallREinAandBequal(ReachGraph rgA,
4219                                                 ReachGraph rgB) {
4220
4221     // check all the heap region->heap region edges
4222     Set sA = rgA.id2hrn.entrySet();
4223     Iterator iA = sA.iterator();
4224     while( iA.hasNext() ) {
4225       Map.Entry meA  = (Map.Entry)iA.next();
4226       Integer idA  = (Integer)        meA.getKey();
4227       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4228
4229       // we should have already checked that the same
4230       // heap regions exist in both graphs
4231       assert rgB.id2hrn.containsKey(idA);
4232
4233       if( !areallREfromAequaltoB(rgA, hrnA, rgB) ) {
4234         return false;
4235       }
4236
4237       // then check every edge in B for presence in A, starting
4238       // from the same parent HeapRegionNode
4239       HeapRegionNode hrnB = rgB.id2hrn.get(idA);
4240
4241       if( !areallREfromAequaltoB(rgB, hrnB, rgA) ) {
4242         return false;
4243       }
4244     }
4245
4246     // then check all the variable->heap region edges
4247     sA = rgA.td2vn.entrySet();
4248     iA = sA.iterator();
4249     while( iA.hasNext() ) {
4250       Map.Entry meA = (Map.Entry)iA.next();
4251       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4252       VariableNode vnA = (VariableNode)   meA.getValue();
4253
4254       // we should have already checked that the same
4255       // label nodes exist in both graphs
4256       assert rgB.td2vn.containsKey(tdA);
4257
4258       if( !areallREfromAequaltoB(rgA, vnA, rgB) ) {
4259         return false;
4260       }
4261
4262       // then check every edge in B for presence in A, starting
4263       // from the same parent VariableNode
4264       VariableNode vnB = rgB.td2vn.get(tdA);
4265
4266       if( !areallREfromAequaltoB(rgB, vnB, rgA) ) {
4267         return false;
4268       }
4269     }
4270
4271     return true;
4272   }
4273
4274
4275   static protected boolean areallREfromAequaltoB(ReachGraph rgA,
4276                                                  RefSrcNode rnA,
4277                                                  ReachGraph rgB) {
4278
4279     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
4280     while( itrA.hasNext() ) {
4281       RefEdge edgeA     = itrA.next();
4282       HeapRegionNode hrnChildA = edgeA.getDst();
4283       Integer idChildA  = hrnChildA.getID();
4284
4285       assert rgB.id2hrn.containsKey(idChildA);
4286
4287       // at this point we know an edge in graph A exists
4288       // rnA -> idChildA, does this exact edge exist in B?
4289       boolean edgeFound = false;
4290
4291       RefSrcNode rnB = null;
4292       if( rnA instanceof HeapRegionNode ) {
4293         HeapRegionNode hrnA = (HeapRegionNode) rnA;
4294         rnB = rgB.id2hrn.get(hrnA.getID() );
4295       } else {
4296         VariableNode vnA = (VariableNode) rnA;
4297         rnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4298       }
4299
4300       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
4301       while( itrB.hasNext() ) {
4302         RefEdge edgeB     = itrB.next();
4303         HeapRegionNode hrnChildB = edgeB.getDst();
4304         Integer idChildB  = hrnChildB.getID();
4305
4306         if( idChildA.equals(idChildB) &&
4307             edgeA.typeAndFieldEquals(edgeB) ) {
4308
4309           // there is an edge in the right place with the right field,
4310           // but do they have the same attributes?
4311           if( edgeA.equalsIncludingBetaPredsTaints( edgeB ) ) {
4312             edgeFound = true;
4313           }
4314         }
4315       }
4316
4317       if( !edgeFound ) {
4318         return false;
4319       }
4320     }
4321
4322     return true;
4323   }
4324
4325
4326   // can be used to assert monotonicity
4327   static public boolean isNoSmallerThan(ReachGraph rgA,
4328                                         ReachGraph rgB) {
4329
4330     //System.out.println( "*** Asking if A is no smaller than B ***" );
4331
4332     Iterator iA = rgA.id2hrn.entrySet().iterator();
4333     while( iA.hasNext() ) {
4334       Map.Entry meA  = (Map.Entry)iA.next();
4335       Integer idA  = (Integer)        meA.getKey();
4336       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4337
4338       if( !rgB.id2hrn.containsKey(idA) ) {
4339         System.out.println("  regions smaller");
4340         return false;
4341       }
4342     }
4343
4344     // this works just fine, no smaller than
4345     if( !areallVNinAalsoinBandequal(rgA, rgB) ) {
4346       System.out.println("  vars smaller:");
4347       System.out.println("    A:"+rgA.td2vn.keySet() );
4348       System.out.println("    B:"+rgB.td2vn.keySet() );
4349       return false;
4350     }
4351
4352
4353     iA = rgA.id2hrn.entrySet().iterator();
4354     while( iA.hasNext() ) {
4355       Map.Entry meA  = (Map.Entry)iA.next();
4356       Integer idA  = (Integer)        meA.getKey();
4357       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4358
4359       Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
4360       while( reItr.hasNext() ) {
4361         RefEdge edgeA = reItr.next();
4362         RefSrcNode rsnA  = edgeA.getSrc();
4363
4364         // we already checked that nodes were present
4365         HeapRegionNode hrnB = rgB.id2hrn.get(hrnA.getID() );
4366         assert hrnB != null;
4367
4368         RefSrcNode rsnB;
4369         if( rsnA instanceof VariableNode ) {
4370           VariableNode vnA = (VariableNode) rsnA;
4371           rsnB = rgB.td2vn.get(vnA.getTempDescriptor() );
4372
4373         } else {
4374           HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
4375           rsnB = rgB.id2hrn.get(hrnSrcA.getID() );
4376         }
4377         assert rsnB != null;
4378
4379         RefEdge edgeB = rsnB.getReferenceTo(hrnB,
4380                                             edgeA.getType(),
4381                                             edgeA.getField()
4382                                             );
4383         if( edgeB == null ) {
4384           System.out.println("  edges smaller:");
4385           return false;
4386         }
4387       }
4388     }
4389
4390
4391     return true;
4392   }
4393
4394
4395
4396
4397
4398   // this analysis no longer has the "match anything"
4399   // type which was represented by null
4400   protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4401                                             TypeDescriptor td2) {
4402     assert td1 != null;
4403     assert td2 != null;
4404
4405     if( td1.isNull() ) {
4406       return td2;
4407     }
4408     if( td2.isNull() ) {
4409       return td1;
4410     }
4411     return typeUtil.mostSpecific(td1, td2);
4412   }
4413
4414   protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4415                                             TypeDescriptor td2,
4416                                             TypeDescriptor td3) {
4417
4418     return mostSpecificType(td1,
4419                             mostSpecificType(td2, td3)
4420                             );
4421   }
4422
4423   protected TypeDescriptor mostSpecificType(TypeDescriptor td1,
4424                                             TypeDescriptor td2,
4425                                             TypeDescriptor td3,
4426                                             TypeDescriptor td4) {
4427
4428     return mostSpecificType(mostSpecificType(td1, td2),
4429                             mostSpecificType(td3, td4)
4430                             );
4431   }
4432
4433   protected boolean isSuperiorType(TypeDescriptor possibleSuper,
4434                                    TypeDescriptor possibleChild) {
4435     assert possibleSuper != null;
4436     assert possibleChild != null;
4437
4438     if( possibleSuper.isNull() ||
4439         possibleChild.isNull() ) {
4440       return true;
4441     }
4442
4443     return typeUtil.isSuperorType(possibleSuper, possibleChild);
4444   }
4445
4446
4447   protected boolean hasMatchingField(HeapRegionNode src,
4448                                      RefEdge edge) {
4449
4450     TypeDescriptor tdSrc = src.getType();
4451     assert tdSrc != null;
4452
4453     if( tdSrc.isArray() ) {
4454       TypeDescriptor td = edge.getType();
4455       assert td != null;
4456
4457       TypeDescriptor tdSrcDeref = tdSrc.dereference();
4458       assert tdSrcDeref != null;
4459
4460       if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
4461         return false;
4462       }
4463
4464       return edge.getField().equals(DisjointAnalysis.arrayElementFieldName);
4465     }
4466
4467     // if it's not a class, it doesn't have any fields to match
4468     if( !tdSrc.isClass() ) {
4469       return false;
4470     }
4471
4472     ClassDescriptor cd = tdSrc.getClassDesc();
4473     while( cd != null ) {
4474       Iterator fieldItr = cd.getFields();
4475
4476       while( fieldItr.hasNext() ) {
4477         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4478
4479         if( fd.getType().equals(edge.getType() ) &&
4480             fd.getSymbol().equals(edge.getField() ) ) {
4481           return true;
4482         }
4483       }
4484
4485       cd = cd.getSuperDesc();
4486     }
4487
4488     // otherwise it is a class with fields
4489     // but we didn't find a match
4490     return false;
4491   }
4492
4493   protected boolean hasMatchingType(RefEdge edge,
4494                                     HeapRegionNode dst) {
4495
4496     // if the region has no type, matches everything
4497     TypeDescriptor tdDst = dst.getType();
4498     assert tdDst != null;
4499
4500     // if the type is not a class or an array, don't
4501     // match because primitives are copied, no aliases
4502     ClassDescriptor cdDst = tdDst.getClassDesc();
4503     if( cdDst == null && !tdDst.isArray() ) {
4504       return false;
4505     }
4506
4507     // if the edge type is null, it matches everything
4508     TypeDescriptor tdEdge = edge.getType();
4509     assert tdEdge != null;
4510
4511     return typeUtil.isSuperorType(tdEdge, tdDst);
4512   }
4513
4514
4515
4516   // the default signature for quick-and-dirty debugging
4517   public void writeGraph(String graphName) {
4518     writeGraph(graphName,
4519                true,   // write labels
4520                true,   // label select
4521                true,   // prune garbage
4522                false,  // hide reachability
4523                true,   // hide subset reachability
4524                true,   // hide predicates
4525                false,   // hide edge taints
4526                null    // in-context boundary
4527                );
4528   }
4529
4530   public void writeGraph(String graphName,
4531                          boolean writeLabels,
4532                          boolean labelSelect,
4533                          boolean pruneGarbage,
4534                          boolean hideReachability,
4535                          boolean hideSubsetReachability,
4536                          boolean hidePredicates,
4537                          boolean hideEdgeTaints
4538                          ) {
4539     writeGraph(graphName,
4540                writeLabels,
4541                labelSelect,
4542                pruneGarbage,
4543                hideReachability,
4544                hideSubsetReachability,
4545                hidePredicates,
4546                hideEdgeTaints,
4547                null);
4548   }
4549
4550   public void writeGraph(String graphName,
4551                          boolean writeLabels,
4552                          boolean labelSelect,
4553                          boolean pruneGarbage,
4554                          boolean hideReachability,
4555                          boolean hideSubsetReachability,
4556                          boolean hidePredicates,
4557                          boolean hideEdgeTaints,
4558                          Set<Integer> callerNodeIDsCopiedToCallee
4559                          ) {
4560     try {
4561       // remove all non-word characters from the graph name so
4562       // the filename and identifier in dot don't cause errors
4563       // jjenista - also replace underscore '_' to prevent some
4564       // really, really long names from IHMS debugging
4565       graphName = graphName.replaceAll("[\\W_]", "");
4566
4567       BufferedWriter bw =
4568         new BufferedWriter(new FileWriter(graphName+".dot") );
4569
4570       bw.write("digraph "+graphName+" {\n");
4571
4572
4573       // this is an optional step to form the callee-reachable
4574       // "cut-out" into a DOT cluster for visualization
4575       if( callerNodeIDsCopiedToCallee != null ) {
4576
4577         bw.write("  subgraph cluster0 {\n");
4578         bw.write("    color=blue;\n");
4579
4580         Iterator i = id2hrn.entrySet().iterator();
4581         while( i.hasNext() ) {
4582           Map.Entry me  = (Map.Entry)i.next();
4583           HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4584
4585           if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4586             bw.write("    "+
4587                      hrn.toString()+
4588                      hrn.toStringDOT(hideReachability,
4589                                      hideSubsetReachability,
4590                                      hidePredicates)+
4591                      ";\n");
4592           }
4593         }
4594
4595         bw.write("  }\n");
4596       }
4597
4598
4599       Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4600
4601       // then visit every heap region node
4602       Iterator i = id2hrn.entrySet().iterator();
4603       while( i.hasNext() ) {
4604         Map.Entry me  = (Map.Entry)i.next();
4605         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4606
4607         // only visit nodes worth writing out--for instance
4608         // not every node at an allocation is referenced
4609         // (think of it as garbage-collected), etc.
4610         if( !pruneGarbage        ||
4611             hrn.isOutOfContext() ||
4612             (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4613             ) {
4614
4615           if( !visited.contains(hrn) ) {
4616             traverseHeapRegionNodes(hrn,
4617                                     bw,
4618                                     null,
4619                                     visited,
4620                                     hideReachability,
4621                                     hideSubsetReachability,
4622                                     hidePredicates,
4623                                     hideEdgeTaints,
4624                                     callerNodeIDsCopiedToCallee);
4625           }
4626         }
4627       }
4628
4629       bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
4630
4631
4632       // then visit every label node, useful for debugging
4633       if( writeLabels ) {
4634         i = td2vn.entrySet().iterator();
4635         while( i.hasNext() ) {
4636           Map.Entry me = (Map.Entry)i.next();
4637           VariableNode vn = (VariableNode) me.getValue();
4638
4639           if( labelSelect ) {
4640             String labelStr = vn.getTempDescriptorString();
4641             if( labelStr.startsWith("___temp")     ||
4642                 labelStr.startsWith("___dst")      ||
4643                 labelStr.startsWith("___srctmp")   ||
4644                 labelStr.startsWith("___neverused")
4645                 ) {
4646               continue;
4647             }
4648           }
4649
4650           Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4651           while( heapRegionsItr.hasNext() ) {
4652             RefEdge edge = heapRegionsItr.next();
4653             HeapRegionNode hrn  = edge.getDst();
4654
4655             if( !visited.contains(hrn) ) {
4656               traverseHeapRegionNodes(hrn,
4657                                       bw,
4658                                       null,
4659                                       visited,
4660                                       hideReachability,
4661                                       hideSubsetReachability,
4662                                       hidePredicates,
4663                                       hideEdgeTaints,
4664                                       callerNodeIDsCopiedToCallee);
4665             }
4666
4667             bw.write("  "+vn.toString()+
4668                      " -> "+hrn.toString()+
4669                      edge.toStringDOT(hideReachability,
4670                                       hideSubsetReachability,
4671                                       hidePredicates,
4672                                       hideEdgeTaints,
4673                                       "")+
4674                      ";\n");
4675           }
4676         }
4677       }
4678
4679       bw.write("}\n");
4680       bw.close();
4681
4682     } catch( IOException e ) {
4683       throw new Error("Error writing out DOT graph "+graphName);
4684     }
4685   }
4686
4687   protected void
4688   traverseHeapRegionNodes(HeapRegionNode hrn,
4689                           BufferedWriter bw,
4690                           TempDescriptor td,
4691                           Set<HeapRegionNode> visited,
4692                           boolean hideReachability,
4693                           boolean hideSubsetReachability,
4694                           boolean hidePredicates,
4695                           boolean hideEdgeTaints,
4696                           Set<Integer>        callerNodeIDsCopiedToCallee
4697                           ) throws java.io.IOException {
4698
4699     if( visited.contains(hrn) ) {
4700       return;
4701     }
4702     visited.add(hrn);
4703
4704     // if we're drawing the callee-view subgraph, only
4705     // write out the node info if it hasn't already been
4706     // written
4707     if( callerNodeIDsCopiedToCallee == null ||
4708         !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4709         ) {
4710       bw.write("  "+
4711                hrn.toString()+
4712                hrn.toStringDOT(hideReachability,
4713                                hideSubsetReachability,
4714                                hidePredicates)+
4715                ";\n");
4716     }
4717
4718     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4719     while( childRegionsItr.hasNext() ) {
4720       RefEdge edge     = childRegionsItr.next();
4721       HeapRegionNode hrnChild = edge.getDst();
4722
4723       if( callerNodeIDsCopiedToCallee != null &&
4724           (edge.getSrc() instanceof HeapRegionNode) ) {
4725         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4726         if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID()        ) &&
4727             callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4728             ) {
4729           bw.write("  "+hrn.toString()+
4730                    " -> "+hrnChild.toString()+
4731                    edge.toStringDOT(hideReachability,
4732                                     hideSubsetReachability,
4733                                     hidePredicates,
4734                                     hideEdgeTaints,
4735                                     ",color=blue")+
4736                    ";\n");
4737         } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID()       ) &&
4738                    callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4739                    ) {
4740           bw.write("  "+hrn.toString()+
4741                    " -> "+hrnChild.toString()+
4742                    edge.toStringDOT(hideReachability,
4743                                     hideSubsetReachability,
4744                                     hidePredicates,
4745                                     hideEdgeTaints,
4746                                     ",color=blue,style=dashed")+
4747                    ";\n");
4748         } else {
4749           bw.write("  "+hrn.toString()+
4750                    " -> "+hrnChild.toString()+
4751                    edge.toStringDOT(hideReachability,
4752                                     hideSubsetReachability,
4753                                     hidePredicates,
4754                                     hideEdgeTaints,
4755                                     "")+
4756                    ";\n");
4757         }
4758       } else {
4759         bw.write("  "+hrn.toString()+
4760                  " -> "+hrnChild.toString()+
4761                  edge.toStringDOT(hideReachability,
4762                                   hideSubsetReachability,
4763                                   hidePredicates,
4764                                   hideEdgeTaints,
4765                                   "")+
4766                  ";\n");
4767       }
4768
4769       traverseHeapRegionNodes(hrnChild,
4770                               bw,
4771                               td,
4772                               visited,
4773                               hideReachability,
4774                               hideSubsetReachability,
4775                               hidePredicates,
4776                               hideEdgeTaints,
4777                               callerNodeIDsCopiedToCallee);
4778     }
4779   }
4780
4781
4782
4783
4784
4785
4786   // return the set of heap regions from the given allocation
4787   // site, if any, that exist in this graph
4788   protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4789
4790     Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4791
4792     Integer idSum = as.getSummary();
4793     if( id2hrn.containsKey(idSum) ) {
4794       out.add(id2hrn.get(idSum) );
4795     }
4796
4797     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4798       Integer idI = as.getIthOldest(i);
4799       if( id2hrn.containsKey(idI) ) {
4800         out.add(id2hrn.get(idI) );
4801       }
4802     }
4803
4804     return out;
4805   }
4806
4807   // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4808   // from the given allocation site, if any, from regions for that
4809   // site that exist in this graph
4810   protected Set<ReachTuple> getAnyExisting(AllocSite as,
4811                                            boolean includeARITY_ZEROORMORE,
4812                                            boolean includeARITY_ONE) {
4813
4814     Set<ReachTuple> out = new HashSet<ReachTuple>();
4815
4816     Integer idSum = as.getSummary();
4817     if( id2hrn.containsKey(idSum) ) {
4818
4819       HeapRegionNode hrn = id2hrn.get(idSum);
4820       assert !hrn.isOutOfContext();
4821
4822       if( !includeARITY_ZEROORMORE ) {
4823         out.add(ReachTuple.factory(hrn.getID(),
4824                                    true,     // multi-obj region
4825                                    ReachTuple.ARITY_ZEROORMORE,
4826                                    false)    // ooc?
4827                 );
4828       }
4829
4830       if( includeARITY_ONE ) {
4831         out.add(ReachTuple.factory(hrn.getID(),
4832                                    true,     // multi-object region
4833                                    ReachTuple.ARITY_ONE,
4834                                    false)    // ooc?
4835                 );
4836       }
4837     }
4838
4839     if( !includeARITY_ONE ) {
4840       // no need to do the single-object regions that
4841       // only have an ARITY ONE possible
4842       return out;
4843     }
4844
4845     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4846
4847       Integer idI = as.getIthOldest(i);
4848       if( id2hrn.containsKey(idI) ) {
4849
4850         HeapRegionNode hrn = id2hrn.get(idI);
4851         assert !hrn.isOutOfContext();
4852
4853         out.add(ReachTuple.factory(hrn.getID(),
4854                                    false,    // multi-object region
4855                                    ReachTuple.ARITY_ONE,
4856                                    false)    // ooc?
4857                 );
4858       }
4859     }
4860
4861     return out;
4862   }
4863
4864
4865   // if an object allocated at the target site may be
4866   // reachable from both an object from root1 and an
4867   // object allocated at root2, return TRUE
4868   public boolean mayBothReachTarget(AllocSite asRoot1,
4869                                     AllocSite asRoot2,
4870                                     AllocSite asTarget) {
4871
4872     // consider all heap regions of the target and look
4873     // for a reach state that indicates regions of root1
4874     // and root2 might be able to reach same object
4875     Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4876
4877     // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4878     Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4879     Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4880
4881     Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4882     while( hrnItr.hasNext() ) {
4883       HeapRegionNode hrn = hrnItr.next();
4884
4885       Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4886       while( rtItr1.hasNext() ) {
4887         ReachTuple rt1 = rtItr1.next();
4888
4889         Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4890         while( rtItr2.hasNext() ) {
4891           ReachTuple rt2 = rtItr2.next();
4892
4893           if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4894             return true;
4895           }
4896         }
4897       }
4898     }
4899
4900     return false;
4901   }
4902
4903   // similar to the method above, return TRUE if ever
4904   // more than one object from the root allocation site
4905   // may reach an object from the target site
4906   public boolean mayManyReachTarget(AllocSite asRoot,
4907                                     AllocSite asTarget) {
4908
4909     // consider all heap regions of the target and look
4910     // for a reach state that multiple objects of root
4911     // might be able to reach the same object
4912     Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4913
4914     // get relevant reach tuples
4915     Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true,  false);
4916     Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4917
4918     Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4919     while( hrnItr.hasNext() ) {
4920       HeapRegionNode hrn = hrnItr.next();
4921
4922       // if any ZERORMORE tuples are here, TRUE
4923       Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4924       while( rtItr.hasNext() ) {
4925         ReachTuple rtZOM = rtItr.next();
4926
4927         if( hrn.getAlpha().containsTuple(rtZOM) ) {
4928           return true;
4929         }
4930       }
4931
4932       // otherwise, look for any pair of ONE tuples
4933       Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4934       while( rtItr1.hasNext() ) {
4935         ReachTuple rt1 = rtItr1.next();
4936
4937         Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4938         while( rtItr2.hasNext() ) {
4939           ReachTuple rt2 = rtItr2.next();
4940
4941           if( rt1 == rt2 ) {
4942             continue;
4943           }
4944
4945           if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4946             return true;
4947           }
4948         }
4949       }
4950     }
4951
4952     return false;
4953   }
4954
4955
4956
4957
4958
4959   public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4960
4961     Set<HeapRegionNode> exhibitProofState =
4962       new HashSet<HeapRegionNode>();
4963
4964     Iterator hrnItr = id2hrn.entrySet().iterator();
4965     while( hrnItr.hasNext() ) {
4966       Map.Entry me  = (Map.Entry)hrnItr.next();
4967       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4968
4969       ReachSet intersection =
4970         Canonical.intersection(proofOfSharing,
4971                                hrn.getAlpha()
4972                                );
4973       if( !intersection.isEmpty() ) {
4974         assert !hrn.isOutOfContext();
4975         exhibitProofState.add(hrn);
4976       }
4977     }
4978
4979     return exhibitProofState;
4980   }
4981
4982
4983   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4984                                                    HeapRegionNode hrn2) {
4985     assert hrn1 != null;
4986     assert hrn2 != null;
4987
4988     assert !hrn1.isOutOfContext();
4989     assert !hrn2.isOutOfContext();
4990
4991     assert belongsToThis(hrn1);
4992     assert belongsToThis(hrn2);
4993
4994     assert !hrn1.getID().equals(hrn2.getID() );
4995
4996
4997     // then get the various tokens for these heap regions
4998     ReachTuple h1 =
4999       ReachTuple.factory(hrn1.getID(),
5000                          !hrn1.isSingleObject(),  // multi?
5001                          ReachTuple.ARITY_ONE,
5002                          false);                  // ooc?
5003
5004     ReachTuple h1star = null;
5005     if( !hrn1.isSingleObject() ) {
5006       h1star =
5007         ReachTuple.factory(hrn1.getID(),
5008                            !hrn1.isSingleObject(),
5009                            ReachTuple.ARITY_ZEROORMORE,
5010                            false);
5011     }
5012
5013     ReachTuple h2 =
5014       ReachTuple.factory(hrn2.getID(),
5015                          !hrn2.isSingleObject(),
5016                          ReachTuple.ARITY_ONE,
5017                          false);
5018
5019     ReachTuple h2star = null;
5020     if( !hrn2.isSingleObject() ) {
5021       h2star =
5022         ReachTuple.factory(hrn2.getID(),
5023                            !hrn2.isSingleObject(),
5024                            ReachTuple.ARITY_ZEROORMORE,
5025                            false);
5026     }
5027
5028     // then get the merged beta of all out-going edges from these heap
5029     // regions
5030
5031     ReachSet beta1 = ReachSet.factory();
5032     Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
5033     while (itrEdge.hasNext()) {
5034       RefEdge edge = itrEdge.next();
5035       beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
5036     }
5037
5038     ReachSet beta2 = ReachSet.factory();
5039     itrEdge = hrn2.iteratorToReferencees();
5040     while (itrEdge.hasNext()) {
5041       RefEdge edge = itrEdge.next();
5042       beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
5043     }
5044
5045     ReachSet proofOfSharing = ReachSet.factory();
5046
5047     proofOfSharing =
5048       Canonical.unionORpreds(proofOfSharing,
5049                              beta1.getStatesWithBoth(h1, h2)
5050                              );
5051     proofOfSharing =
5052       Canonical.unionORpreds(proofOfSharing,
5053                              beta2.getStatesWithBoth(h1, h2)
5054                              );
5055
5056     if( !hrn1.isSingleObject() ) {
5057       proofOfSharing =
5058         Canonical.unionORpreds(proofOfSharing,
5059                                beta1.getStatesWithBoth(h1star, h2)
5060                                );
5061       proofOfSharing =
5062         Canonical.unionORpreds(proofOfSharing,
5063                                beta2.getStatesWithBoth(h1star, h2)
5064                                );
5065     }
5066
5067     if( !hrn2.isSingleObject() ) {
5068       proofOfSharing =
5069         Canonical.unionORpreds(proofOfSharing,
5070                                beta1.getStatesWithBoth(h1, h2star)
5071                                );
5072       proofOfSharing =
5073         Canonical.unionORpreds(proofOfSharing,
5074                                beta2.getStatesWithBoth(h1, h2star)
5075                                );
5076     }
5077
5078     if( !hrn1.isSingleObject() &&
5079         !hrn2.isSingleObject()
5080         ) {
5081       proofOfSharing =
5082         Canonical.unionORpreds(proofOfSharing,
5083                                beta1.getStatesWithBoth(h1star, h2star)
5084                                );
5085       proofOfSharing =
5086         Canonical.unionORpreds(proofOfSharing,
5087                                beta2.getStatesWithBoth(h1star, h2star)
5088                                );
5089     }
5090
5091     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5092     if( !proofOfSharing.isEmpty() ) {
5093       common = findCommonReachableNodes(proofOfSharing);
5094       if( !DISABLE_STRONG_UPDATES &&
5095           !DISABLE_GLOBAL_SWEEP
5096           ) {
5097         assert !common.isEmpty();
5098       }
5099     }
5100
5101     return common;
5102   }
5103
5104   // this version of the above method checks whether there is sharing
5105   // among the objects in a summary node
5106   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5107     assert hrn != null;
5108     assert hrn.isNewSummary();
5109     assert !hrn.isOutOfContext();
5110     assert belongsToThis(hrn);
5111
5112     ReachTuple hstar =
5113       ReachTuple.factory(hrn.getID(),
5114                          true,     // multi
5115                          ReachTuple.ARITY_ZEROORMORE,
5116                          false);   // ooc
5117
5118     // then get the merged beta of all out-going edges from
5119     // this heap region
5120
5121     ReachSet beta = ReachSet.factory();
5122     Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5123     while (itrEdge.hasNext()) {
5124       RefEdge edge = itrEdge.next();
5125       beta = Canonical.unionORpreds(beta, edge.getBeta());
5126     }
5127
5128     ReachSet proofOfSharing = ReachSet.factory();
5129
5130     proofOfSharing =
5131       Canonical.unionORpreds(proofOfSharing,
5132                              beta.getStatesWithBoth(hstar, hstar)
5133                              );
5134
5135     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5136     if( !proofOfSharing.isEmpty() ) {
5137       common = findCommonReachableNodes(proofOfSharing);
5138       if( !DISABLE_STRONG_UPDATES &&
5139           !DISABLE_GLOBAL_SWEEP
5140           ) {
5141         assert !common.isEmpty();
5142       }
5143     }
5144
5145     return common;
5146   }
5147
5148
5149   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5150                                                    Integer paramIndex1,
5151                                                    Integer paramIndex2) {
5152
5153     // get parameter's heap regions
5154     TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5155     assert this.hasVariable(paramTemp1);
5156     VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5157
5158
5159     if( !(paramVar1.getNumReferencees() == 1) ) {
5160       System.out.println("\n  fm="+fm+"\n  param="+paramTemp1);
5161       writeGraph("whatup");
5162     }
5163
5164
5165     assert paramVar1.getNumReferencees() == 1;
5166     RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5167     HeapRegionNode hrnParam1 = paramEdge1.getDst();
5168
5169     TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5170     assert this.hasVariable(paramTemp2);
5171     VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5172
5173     if( !(paramVar2.getNumReferencees() == 1) ) {
5174       System.out.println("\n  fm="+fm+"\n  param="+paramTemp2);
5175       writeGraph("whatup");
5176     }
5177
5178     assert paramVar2.getNumReferencees() == 1;
5179     RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5180     HeapRegionNode hrnParam2 = paramEdge2.getDst();
5181
5182     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5183     common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5184
5185     return common;
5186   }
5187
5188   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5189                                                    Integer paramIndex,
5190                                                    AllocSite as) {
5191
5192     // get parameter's heap regions
5193     TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5194     assert this.hasVariable(paramTemp);
5195     VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5196     assert paramVar.getNumReferencees() == 1;
5197     RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5198     HeapRegionNode hrnParam = paramEdge.getDst();
5199
5200     // get summary node
5201     HeapRegionNode hrnSummary=null;
5202     if(id2hrn.containsKey(as.getSummary())) {
5203       // if summary node doesn't exist, ignore this case
5204       hrnSummary = id2hrn.get(as.getSummary());
5205       assert hrnSummary != null;
5206     }
5207
5208     Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
5209     if(hrnSummary!=null) {
5210       common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5211     }
5212
5213     // check for other nodes
5214     for (int i = 0; i < as.getAllocationDepth(); ++i) {
5215
5216       assert id2hrn.containsKey(as.getIthOldest(i));
5217       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5218       assert hrnIthOldest != null;
5219
5220       common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5221
5222     }
5223
5224     return common;
5225   }
5226
5227   public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5228                                                    AllocSite as2) {
5229
5230     // get summary node 1's alpha
5231     Integer idSum1 = as1.getSummary();
5232     HeapRegionNode hrnSum1=null;
5233     if(id2hrn.containsKey(idSum1)) {
5234       hrnSum1 = id2hrn.get(idSum1);
5235     }
5236
5237     // get summary node 2's alpha
5238     Integer idSum2 = as2.getSummary();
5239     HeapRegionNode hrnSum2=null;
5240     if(id2hrn.containsKey(idSum2)) {
5241       hrnSum2 = id2hrn.get(idSum2);
5242     }
5243
5244     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5245     if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5246       common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5247     }
5248
5249     if(hrnSum1!=null) {
5250       // ask if objects from this summary share among each other
5251       common.addAll(mayReachSharedObjects(hrnSum1));
5252     }
5253
5254     // check sum2 against alloc1 nodes
5255     if(hrnSum2!=null) {
5256       for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5257         Integer idI1 = as1.getIthOldest(i);
5258         assert id2hrn.containsKey(idI1);
5259         HeapRegionNode hrnI1 = id2hrn.get(idI1);
5260         assert hrnI1 != null;
5261         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5262       }
5263
5264       // also ask if objects from this summary share among each other
5265       common.addAll(mayReachSharedObjects(hrnSum2));
5266     }
5267
5268     // check sum1 against alloc2 nodes
5269     for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5270       Integer idI2 = as2.getIthOldest(i);
5271       assert id2hrn.containsKey(idI2);
5272       HeapRegionNode hrnI2 = id2hrn.get(idI2);
5273       assert hrnI2 != null;
5274
5275       if(hrnSum1!=null) {
5276         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5277       }
5278
5279       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5280       for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5281         Integer idI1 = as1.getIthOldest(j);
5282
5283         // if these are the same site, don't look for the same token, no
5284         // alias.
5285         // different tokens of the same site could alias together though
5286         if (idI1.equals(idI2)) {
5287           continue;
5288         }
5289
5290         HeapRegionNode hrnI1 = id2hrn.get(idI1);
5291
5292         common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5293       }
5294     }
5295
5296     return common;
5297   }
5298
5299   public void makeInaccessible(Set<TempDescriptor> vars) {
5300     inaccessibleVars.addAll(vars);
5301   }
5302
5303   public void makeInaccessible(TempDescriptor td) {
5304     inaccessibleVars.add(td);
5305   }
5306
5307   public void makeAccessible(TempDescriptor td) {
5308     inaccessibleVars.remove(td);
5309   }
5310
5311   public boolean isAccessible(TempDescriptor td) {
5312     return !inaccessibleVars.contains(td);
5313   }
5314
5315   public Set<TempDescriptor> getInaccessibleVars() {
5316     return inaccessibleVars;
5317   }
5318
5319
5320
5321
5322   public Set<Alloc> canPointTo( TempDescriptor x ) {
5323
5324     if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5325       // if we don't care to track it, return null which means
5326       // "a client of this result shouldn't care either"
5327       return HeapAnalysis.DONTCARE_PTR;
5328     }
5329
5330     Set<Alloc> out = new HashSet<Alloc>();
5331
5332     VariableNode vn = getVariableNodeNoMutation( x );
5333     if( vn == null ) {
5334       // the empty set means "can't point to anything"
5335       return out;
5336     }
5337
5338     Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5339     while( edgeItr.hasNext() ) {
5340       HeapRegionNode hrn = edgeItr.next().getDst();
5341       out.add( hrn.getAllocSite() );
5342     }
5343
5344     return out;
5345   }
5346
5347
5348
5349   public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5350                                                     String         field,
5351                                                     TypeDescriptor fieldType ) {
5352
5353     if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5354       // if we don't care to track it, return null which means
5355       // "a client of this result shouldn't care either"
5356       return HeapAnalysis.DONTCARE_DREF;
5357     }
5358
5359     Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5360
5361     VariableNode vn = getVariableNodeNoMutation( x );
5362     if( vn == null ) {
5363       // the empty table means "x can't point to anything"
5364       return out;
5365     }
5366
5367     Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5368     while( edgeItr.hasNext() ) {
5369       HeapRegionNode hrn = edgeItr.next().getDst();
5370       Alloc          key = hrn.getAllocSite();
5371
5372       if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5373         // if we don't care to track it, put no entry which means
5374         // "a client of this result shouldn't care either"
5375         out.put( key, HeapAnalysis.DONTCARE_PTR );
5376         continue;
5377       }
5378
5379       Set<Alloc> moreValues = new HashSet<Alloc>();
5380       Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5381       while( edgeItr2.hasNext() ) {
5382         RefEdge edge = edgeItr2.next();
5383
5384         if( field.equals( edge.getField() ) ) {
5385           moreValues.add( edge.getDst().getAllocSite() );
5386         }
5387       }
5388
5389       if( out.containsKey( key ) ) {
5390         out.get( key ).addAll( moreValues );
5391       } else {
5392         out.put( key, moreValues );
5393       }
5394     }
5395
5396     return out;
5397   }
5398
5399
5400
5401   // for debugging
5402   public TempDescriptor findVariableByName( String name ) {
5403
5404     for( TempDescriptor td: td2vn.keySet() ) {
5405       if( td.getSymbol().contains( name ) ) {
5406         return td;
5407       }
5408     }
5409
5410     return null;
5411   }
5412
5413
5414   public String countGraphElements() {
5415     long numNodes = 0;
5416     long numEdges = 0;
5417     long numNodeStates = 0;
5418     long numEdgeStates = 0;
5419     long numNodeStateNonzero = 0;
5420     long numEdgeStateNonzero = 0;
5421
5422     for( HeapRegionNode node : id2hrn.values() ) {
5423       numNodes++;
5424       numNodeStates       += node.getAlpha().numStates();
5425       numNodeStateNonzero += node.getAlpha().numNonzeroTuples();
5426
5427       // all edges in the graph point TO a heap node, so scanning
5428       // all referencers of all nodes gets every edge
5429       Iterator<RefEdge> refItr = node.iteratorToReferencers();
5430       while( refItr.hasNext() ) {
5431         RefEdge edge = refItr.next();
5432
5433         numEdges++;
5434         numEdgeStates       += edge.getBeta().numStates();
5435         numEdgeStateNonzero += edge.getBeta().numNonzeroTuples();
5436       }
5437     }
5438
5439     return
5440       "################################################\n"+
5441       "Nodes                = "+numNodes+"\n"+
5442       "Edges                = "+numEdges+"\n"+
5443       "Node states          = "+numNodeStates+"\n"+
5444       "Edge states          = "+numEdgeStates+"\n"+
5445       "Node non-zero tuples = "+numNodeStateNonzero+"\n"+
5446       "Edge non-zero tuples = "+numEdgeStateNonzero+"\n"+
5447       "################################################\n";
5448   }
5449 }