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 = false;
2394   private static boolean resolveMethodDebugDOThidePreds       = true;
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
4571       if( state.DISJOINT_COUNT_GRAPH_ELEMENTS ) {
4572         GraphElementCount gec = new GraphElementCount();
4573         countGraphElements( gec );
4574         bw.write("/* Counting Graph Elements\n"+gec+" */\n");
4575       }
4576
4577
4578       bw.write("digraph "+graphName+" {\n");
4579
4580
4581       // this is an optional step to form the callee-reachable
4582       // "cut-out" into a DOT cluster for visualization
4583       if( callerNodeIDsCopiedToCallee != null ) {
4584
4585         bw.write("  subgraph cluster0 {\n");
4586         bw.write("    color=blue;\n");
4587
4588         Iterator i = id2hrn.entrySet().iterator();
4589         while( i.hasNext() ) {
4590           Map.Entry me  = (Map.Entry)i.next();
4591           HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4592
4593           if( callerNodeIDsCopiedToCallee.contains(hrn.getID() ) ) {
4594             bw.write("    "+
4595                      hrn.toString()+
4596                      hrn.toStringDOT(hideReachability,
4597                                      hideSubsetReachability,
4598                                      hidePredicates)+
4599                      ";\n");
4600           }
4601         }
4602
4603         bw.write("  }\n");
4604       }
4605
4606
4607       Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4608
4609       // then visit every heap region node
4610       Iterator i = id2hrn.entrySet().iterator();
4611       while( i.hasNext() ) {
4612         Map.Entry me  = (Map.Entry)i.next();
4613         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4614
4615         // only visit nodes worth writing out--for instance
4616         // not every node at an allocation is referenced
4617         // (think of it as garbage-collected), etc.
4618         if( !pruneGarbage        ||
4619             hrn.isOutOfContext() ||
4620             (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4621             ) {
4622
4623           if( !visited.contains(hrn) ) {
4624             traverseHeapRegionNodes(hrn,
4625                                     bw,
4626                                     null,
4627                                     visited,
4628                                     hideReachability,
4629                                     hideSubsetReachability,
4630                                     hidePredicates,
4631                                     hideEdgeTaints,
4632                                     callerNodeIDsCopiedToCallee);
4633           }
4634         }
4635       }
4636
4637       bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
4638
4639
4640       // then visit every label node, useful for debugging
4641       if( writeLabels ) {
4642         i = td2vn.entrySet().iterator();
4643         while( i.hasNext() ) {
4644           Map.Entry me = (Map.Entry)i.next();
4645           VariableNode vn = (VariableNode) me.getValue();
4646
4647           if( labelSelect ) {
4648             String labelStr = vn.getTempDescriptorString();
4649             if( labelStr.startsWith("___temp")     ||
4650                 labelStr.startsWith("___dst")      ||
4651                 labelStr.startsWith("___srctmp")   ||
4652                 labelStr.startsWith("___neverused")
4653                 ) {
4654               continue;
4655             }
4656           }
4657
4658           Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4659           while( heapRegionsItr.hasNext() ) {
4660             RefEdge edge = heapRegionsItr.next();
4661             HeapRegionNode hrn  = edge.getDst();
4662
4663             if( !visited.contains(hrn) ) {
4664               traverseHeapRegionNodes(hrn,
4665                                       bw,
4666                                       null,
4667                                       visited,
4668                                       hideReachability,
4669                                       hideSubsetReachability,
4670                                       hidePredicates,
4671                                       hideEdgeTaints,
4672                                       callerNodeIDsCopiedToCallee);
4673             }
4674
4675             bw.write("  "+vn.toString()+
4676                      " -> "+hrn.toString()+
4677                      edge.toStringDOT(hideReachability,
4678                                       hideSubsetReachability,
4679                                       hidePredicates,
4680                                       hideEdgeTaints,
4681                                       "")+
4682                      ";\n");
4683           }
4684         }
4685       }
4686
4687       bw.write("}\n");
4688       bw.close();
4689
4690     } catch( IOException e ) {
4691       throw new Error("Error writing out DOT graph "+graphName);
4692     }
4693   }
4694
4695   protected void
4696   traverseHeapRegionNodes(HeapRegionNode hrn,
4697                           BufferedWriter bw,
4698                           TempDescriptor td,
4699                           Set<HeapRegionNode> visited,
4700                           boolean hideReachability,
4701                           boolean hideSubsetReachability,
4702                           boolean hidePredicates,
4703                           boolean hideEdgeTaints,
4704                           Set<Integer>        callerNodeIDsCopiedToCallee
4705                           ) throws java.io.IOException {
4706
4707     if( visited.contains(hrn) ) {
4708       return;
4709     }
4710     visited.add(hrn);
4711
4712     // if we're drawing the callee-view subgraph, only
4713     // write out the node info if it hasn't already been
4714     // written
4715     if( callerNodeIDsCopiedToCallee == null ||
4716         !callerNodeIDsCopiedToCallee.contains(hrn.getID() )
4717         ) {
4718       bw.write("  "+
4719                hrn.toString()+
4720                hrn.toStringDOT(hideReachability,
4721                                hideSubsetReachability,
4722                                hidePredicates)+
4723                ";\n");
4724     }
4725
4726     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4727     while( childRegionsItr.hasNext() ) {
4728       RefEdge edge     = childRegionsItr.next();
4729       HeapRegionNode hrnChild = edge.getDst();
4730
4731       if( callerNodeIDsCopiedToCallee != null &&
4732           (edge.getSrc() instanceof HeapRegionNode) ) {
4733         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4734         if( callerNodeIDsCopiedToCallee.contains(hrnSrc.getID()        ) &&
4735             callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4736             ) {
4737           bw.write("  "+hrn.toString()+
4738                    " -> "+hrnChild.toString()+
4739                    edge.toStringDOT(hideReachability,
4740                                     hideSubsetReachability,
4741                                     hidePredicates,
4742                                     hideEdgeTaints,
4743                                     ",color=blue")+
4744                    ";\n");
4745         } else if( !callerNodeIDsCopiedToCallee.contains(hrnSrc.getID()       ) &&
4746                    callerNodeIDsCopiedToCallee.contains(edge.getDst().getID() )
4747                    ) {
4748           bw.write("  "+hrn.toString()+
4749                    " -> "+hrnChild.toString()+
4750                    edge.toStringDOT(hideReachability,
4751                                     hideSubsetReachability,
4752                                     hidePredicates,
4753                                     hideEdgeTaints,
4754                                     ",color=blue,style=dashed")+
4755                    ";\n");
4756         } else {
4757           bw.write("  "+hrn.toString()+
4758                    " -> "+hrnChild.toString()+
4759                    edge.toStringDOT(hideReachability,
4760                                     hideSubsetReachability,
4761                                     hidePredicates,
4762                                     hideEdgeTaints,
4763                                     "")+
4764                    ";\n");
4765         }
4766       } else {
4767         bw.write("  "+hrn.toString()+
4768                  " -> "+hrnChild.toString()+
4769                  edge.toStringDOT(hideReachability,
4770                                   hideSubsetReachability,
4771                                   hidePredicates,
4772                                   hideEdgeTaints,
4773                                   "")+
4774                  ";\n");
4775       }
4776
4777       traverseHeapRegionNodes(hrnChild,
4778                               bw,
4779                               td,
4780                               visited,
4781                               hideReachability,
4782                               hideSubsetReachability,
4783                               hidePredicates,
4784                               hideEdgeTaints,
4785                               callerNodeIDsCopiedToCallee);
4786     }
4787   }
4788
4789
4790
4791
4792
4793
4794   // return the set of heap regions from the given allocation
4795   // site, if any, that exist in this graph
4796   protected Set<HeapRegionNode> getAnyExisting(AllocSite as) {
4797
4798     Set<HeapRegionNode> out = new HashSet<HeapRegionNode>();
4799
4800     Integer idSum = as.getSummary();
4801     if( id2hrn.containsKey(idSum) ) {
4802       out.add(id2hrn.get(idSum) );
4803     }
4804
4805     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4806       Integer idI = as.getIthOldest(i);
4807       if( id2hrn.containsKey(idI) ) {
4808         out.add(id2hrn.get(idI) );
4809       }
4810     }
4811
4812     return out;
4813   }
4814
4815   // return the set of reach tuples (NOT A REACH STATE! JUST A SET!)
4816   // from the given allocation site, if any, from regions for that
4817   // site that exist in this graph
4818   protected Set<ReachTuple> getAnyExisting(AllocSite as,
4819                                            boolean includeARITY_ZEROORMORE,
4820                                            boolean includeARITY_ONE) {
4821
4822     Set<ReachTuple> out = new HashSet<ReachTuple>();
4823
4824     Integer idSum = as.getSummary();
4825     if( id2hrn.containsKey(idSum) ) {
4826
4827       HeapRegionNode hrn = id2hrn.get(idSum);
4828       assert !hrn.isOutOfContext();
4829
4830       if( !includeARITY_ZEROORMORE ) {
4831         out.add(ReachTuple.factory(hrn.getID(),
4832                                    true,     // multi-obj region
4833                                    ReachTuple.ARITY_ZEROORMORE,
4834                                    false)    // ooc?
4835                 );
4836       }
4837
4838       if( includeARITY_ONE ) {
4839         out.add(ReachTuple.factory(hrn.getID(),
4840                                    true,     // multi-object region
4841                                    ReachTuple.ARITY_ONE,
4842                                    false)    // ooc?
4843                 );
4844       }
4845     }
4846
4847     if( !includeARITY_ONE ) {
4848       // no need to do the single-object regions that
4849       // only have an ARITY ONE possible
4850       return out;
4851     }
4852
4853     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4854
4855       Integer idI = as.getIthOldest(i);
4856       if( id2hrn.containsKey(idI) ) {
4857
4858         HeapRegionNode hrn = id2hrn.get(idI);
4859         assert !hrn.isOutOfContext();
4860
4861         out.add(ReachTuple.factory(hrn.getID(),
4862                                    false,    // multi-object region
4863                                    ReachTuple.ARITY_ONE,
4864                                    false)    // ooc?
4865                 );
4866       }
4867     }
4868
4869     return out;
4870   }
4871
4872
4873   // if an object allocated at the target site may be
4874   // reachable from both an object from root1 and an
4875   // object allocated at root2, return TRUE
4876   public boolean mayBothReachTarget(AllocSite asRoot1,
4877                                     AllocSite asRoot2,
4878                                     AllocSite asTarget) {
4879
4880     // consider all heap regions of the target and look
4881     // for a reach state that indicates regions of root1
4882     // and root2 might be able to reach same object
4883     Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4884
4885     // get relevant reach tuples, include ARITY_ZEROORMORE and ARITY_ONE
4886     Set<ReachTuple> rtSet1 = getAnyExisting(asRoot1, true, true);
4887     Set<ReachTuple> rtSet2 = getAnyExisting(asRoot2, true, true);
4888
4889     Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4890     while( hrnItr.hasNext() ) {
4891       HeapRegionNode hrn = hrnItr.next();
4892
4893       Iterator<ReachTuple> rtItr1 = rtSet1.iterator();
4894       while( rtItr1.hasNext() ) {
4895         ReachTuple rt1 = rtItr1.next();
4896
4897         Iterator<ReachTuple> rtItr2 = rtSet2.iterator();
4898         while( rtItr2.hasNext() ) {
4899           ReachTuple rt2 = rtItr2.next();
4900
4901           if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4902             return true;
4903           }
4904         }
4905       }
4906     }
4907
4908     return false;
4909   }
4910
4911   // similar to the method above, return TRUE if ever
4912   // more than one object from the root allocation site
4913   // may reach an object from the target site
4914   public boolean mayManyReachTarget(AllocSite asRoot,
4915                                     AllocSite asTarget) {
4916
4917     // consider all heap regions of the target and look
4918     // for a reach state that multiple objects of root
4919     // might be able to reach the same object
4920     Set<HeapRegionNode> hrnSetTarget = getAnyExisting(asTarget);
4921
4922     // get relevant reach tuples
4923     Set<ReachTuple> rtSetZOM = getAnyExisting(asRoot, true,  false);
4924     Set<ReachTuple> rtSetONE = getAnyExisting(asRoot, false, true);
4925
4926     Iterator<HeapRegionNode> hrnItr = hrnSetTarget.iterator();
4927     while( hrnItr.hasNext() ) {
4928       HeapRegionNode hrn = hrnItr.next();
4929
4930       // if any ZERORMORE tuples are here, TRUE
4931       Iterator<ReachTuple> rtItr = rtSetZOM.iterator();
4932       while( rtItr.hasNext() ) {
4933         ReachTuple rtZOM = rtItr.next();
4934
4935         if( hrn.getAlpha().containsTuple(rtZOM) ) {
4936           return true;
4937         }
4938       }
4939
4940       // otherwise, look for any pair of ONE tuples
4941       Iterator<ReachTuple> rtItr1 = rtSetONE.iterator();
4942       while( rtItr1.hasNext() ) {
4943         ReachTuple rt1 = rtItr1.next();
4944
4945         Iterator<ReachTuple> rtItr2 = rtSetONE.iterator();
4946         while( rtItr2.hasNext() ) {
4947           ReachTuple rt2 = rtItr2.next();
4948
4949           if( rt1 == rt2 ) {
4950             continue;
4951           }
4952
4953           if( !hrn.getAlpha().getStatesWithBoth(rt1, rt2).isEmpty() ) {
4954             return true;
4955           }
4956         }
4957       }
4958     }
4959
4960     return false;
4961   }
4962
4963
4964
4965
4966
4967   public Set<HeapRegionNode> findCommonReachableNodes(ReachSet proofOfSharing) {
4968
4969     Set<HeapRegionNode> exhibitProofState =
4970       new HashSet<HeapRegionNode>();
4971
4972     Iterator hrnItr = id2hrn.entrySet().iterator();
4973     while( hrnItr.hasNext() ) {
4974       Map.Entry me  = (Map.Entry)hrnItr.next();
4975       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4976
4977       ReachSet intersection =
4978         Canonical.intersection(proofOfSharing,
4979                                hrn.getAlpha()
4980                                );
4981       if( !intersection.isEmpty() ) {
4982         assert !hrn.isOutOfContext();
4983         exhibitProofState.add(hrn);
4984       }
4985     }
4986
4987     return exhibitProofState;
4988   }
4989
4990
4991   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4992                                                    HeapRegionNode hrn2) {
4993     assert hrn1 != null;
4994     assert hrn2 != null;
4995
4996     assert !hrn1.isOutOfContext();
4997     assert !hrn2.isOutOfContext();
4998
4999     assert belongsToThis(hrn1);
5000     assert belongsToThis(hrn2);
5001
5002     assert !hrn1.getID().equals(hrn2.getID() );
5003
5004
5005     // then get the various tokens for these heap regions
5006     ReachTuple h1 =
5007       ReachTuple.factory(hrn1.getID(),
5008                          !hrn1.isSingleObject(),  // multi?
5009                          ReachTuple.ARITY_ONE,
5010                          false);                  // ooc?
5011
5012     ReachTuple h1star = null;
5013     if( !hrn1.isSingleObject() ) {
5014       h1star =
5015         ReachTuple.factory(hrn1.getID(),
5016                            !hrn1.isSingleObject(),
5017                            ReachTuple.ARITY_ZEROORMORE,
5018                            false);
5019     }
5020
5021     ReachTuple h2 =
5022       ReachTuple.factory(hrn2.getID(),
5023                          !hrn2.isSingleObject(),
5024                          ReachTuple.ARITY_ONE,
5025                          false);
5026
5027     ReachTuple h2star = null;
5028     if( !hrn2.isSingleObject() ) {
5029       h2star =
5030         ReachTuple.factory(hrn2.getID(),
5031                            !hrn2.isSingleObject(),
5032                            ReachTuple.ARITY_ZEROORMORE,
5033                            false);
5034     }
5035
5036     // then get the merged beta of all out-going edges from these heap
5037     // regions
5038
5039     ReachSet beta1 = ReachSet.factory();
5040     Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
5041     while (itrEdge.hasNext()) {
5042       RefEdge edge = itrEdge.next();
5043       beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
5044     }
5045
5046     ReachSet beta2 = ReachSet.factory();
5047     itrEdge = hrn2.iteratorToReferencees();
5048     while (itrEdge.hasNext()) {
5049       RefEdge edge = itrEdge.next();
5050       beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
5051     }
5052
5053     ReachSet proofOfSharing = ReachSet.factory();
5054
5055     proofOfSharing =
5056       Canonical.unionORpreds(proofOfSharing,
5057                              beta1.getStatesWithBoth(h1, h2)
5058                              );
5059     proofOfSharing =
5060       Canonical.unionORpreds(proofOfSharing,
5061                              beta2.getStatesWithBoth(h1, h2)
5062                              );
5063
5064     if( !hrn1.isSingleObject() ) {
5065       proofOfSharing =
5066         Canonical.unionORpreds(proofOfSharing,
5067                                beta1.getStatesWithBoth(h1star, h2)
5068                                );
5069       proofOfSharing =
5070         Canonical.unionORpreds(proofOfSharing,
5071                                beta2.getStatesWithBoth(h1star, h2)
5072                                );
5073     }
5074
5075     if( !hrn2.isSingleObject() ) {
5076       proofOfSharing =
5077         Canonical.unionORpreds(proofOfSharing,
5078                                beta1.getStatesWithBoth(h1, h2star)
5079                                );
5080       proofOfSharing =
5081         Canonical.unionORpreds(proofOfSharing,
5082                                beta2.getStatesWithBoth(h1, h2star)
5083                                );
5084     }
5085
5086     if( !hrn1.isSingleObject() &&
5087         !hrn2.isSingleObject()
5088         ) {
5089       proofOfSharing =
5090         Canonical.unionORpreds(proofOfSharing,
5091                                beta1.getStatesWithBoth(h1star, h2star)
5092                                );
5093       proofOfSharing =
5094         Canonical.unionORpreds(proofOfSharing,
5095                                beta2.getStatesWithBoth(h1star, h2star)
5096                                );
5097     }
5098
5099     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5100     if( !proofOfSharing.isEmpty() ) {
5101       common = findCommonReachableNodes(proofOfSharing);
5102       if( !DISABLE_STRONG_UPDATES &&
5103           !DISABLE_GLOBAL_SWEEP
5104           ) {
5105         assert !common.isEmpty();
5106       }
5107     }
5108
5109     return common;
5110   }
5111
5112   // this version of the above method checks whether there is sharing
5113   // among the objects in a summary node
5114   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
5115     assert hrn != null;
5116     assert hrn.isNewSummary();
5117     assert !hrn.isOutOfContext();
5118     assert belongsToThis(hrn);
5119
5120     ReachTuple hstar =
5121       ReachTuple.factory(hrn.getID(),
5122                          true,     // multi
5123                          ReachTuple.ARITY_ZEROORMORE,
5124                          false);   // ooc
5125
5126     // then get the merged beta of all out-going edges from
5127     // this heap region
5128
5129     ReachSet beta = ReachSet.factory();
5130     Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
5131     while (itrEdge.hasNext()) {
5132       RefEdge edge = itrEdge.next();
5133       beta = Canonical.unionORpreds(beta, edge.getBeta());
5134     }
5135
5136     ReachSet proofOfSharing = ReachSet.factory();
5137
5138     proofOfSharing =
5139       Canonical.unionORpreds(proofOfSharing,
5140                              beta.getStatesWithBoth(hstar, hstar)
5141                              );
5142
5143     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5144     if( !proofOfSharing.isEmpty() ) {
5145       common = findCommonReachableNodes(proofOfSharing);
5146       if( !DISABLE_STRONG_UPDATES &&
5147           !DISABLE_GLOBAL_SWEEP
5148           ) {
5149         assert !common.isEmpty();
5150       }
5151     }
5152
5153     return common;
5154   }
5155
5156
5157   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5158                                                    Integer paramIndex1,
5159                                                    Integer paramIndex2) {
5160
5161     // get parameter's heap regions
5162     TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
5163     assert this.hasVariable(paramTemp1);
5164     VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
5165
5166
5167     if( !(paramVar1.getNumReferencees() == 1) ) {
5168       System.out.println("\n  fm="+fm+"\n  param="+paramTemp1);
5169       writeGraph("whatup");
5170     }
5171
5172
5173     assert paramVar1.getNumReferencees() == 1;
5174     RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
5175     HeapRegionNode hrnParam1 = paramEdge1.getDst();
5176
5177     TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
5178     assert this.hasVariable(paramTemp2);
5179     VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
5180
5181     if( !(paramVar2.getNumReferencees() == 1) ) {
5182       System.out.println("\n  fm="+fm+"\n  param="+paramTemp2);
5183       writeGraph("whatup");
5184     }
5185
5186     assert paramVar2.getNumReferencees() == 1;
5187     RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
5188     HeapRegionNode hrnParam2 = paramEdge2.getDst();
5189
5190     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5191     common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
5192
5193     return common;
5194   }
5195
5196   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
5197                                                    Integer paramIndex,
5198                                                    AllocSite as) {
5199
5200     // get parameter's heap regions
5201     TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
5202     assert this.hasVariable(paramTemp);
5203     VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
5204     assert paramVar.getNumReferencees() == 1;
5205     RefEdge paramEdge = paramVar.iteratorToReferencees().next();
5206     HeapRegionNode hrnParam = paramEdge.getDst();
5207
5208     // get summary node
5209     HeapRegionNode hrnSummary=null;
5210     if(id2hrn.containsKey(as.getSummary())) {
5211       // if summary node doesn't exist, ignore this case
5212       hrnSummary = id2hrn.get(as.getSummary());
5213       assert hrnSummary != null;
5214     }
5215
5216     Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
5217     if(hrnSummary!=null) {
5218       common.addAll(mayReachSharedObjects(hrnParam, hrnSummary) );
5219     }
5220
5221     // check for other nodes
5222     for (int i = 0; i < as.getAllocationDepth(); ++i) {
5223
5224       assert id2hrn.containsKey(as.getIthOldest(i));
5225       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
5226       assert hrnIthOldest != null;
5227
5228       common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
5229
5230     }
5231
5232     return common;
5233   }
5234
5235   public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
5236                                                    AllocSite as2) {
5237
5238     // get summary node 1's alpha
5239     Integer idSum1 = as1.getSummary();
5240     HeapRegionNode hrnSum1=null;
5241     if(id2hrn.containsKey(idSum1)) {
5242       hrnSum1 = id2hrn.get(idSum1);
5243     }
5244
5245     // get summary node 2's alpha
5246     Integer idSum2 = as2.getSummary();
5247     HeapRegionNode hrnSum2=null;
5248     if(id2hrn.containsKey(idSum2)) {
5249       hrnSum2 = id2hrn.get(idSum2);
5250     }
5251
5252     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
5253     if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2) {
5254       common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
5255     }
5256
5257     if(hrnSum1!=null) {
5258       // ask if objects from this summary share among each other
5259       common.addAll(mayReachSharedObjects(hrnSum1));
5260     }
5261
5262     // check sum2 against alloc1 nodes
5263     if(hrnSum2!=null) {
5264       for (int i = 0; i < as1.getAllocationDepth(); ++i) {
5265         Integer idI1 = as1.getIthOldest(i);
5266         assert id2hrn.containsKey(idI1);
5267         HeapRegionNode hrnI1 = id2hrn.get(idI1);
5268         assert hrnI1 != null;
5269         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
5270       }
5271
5272       // also ask if objects from this summary share among each other
5273       common.addAll(mayReachSharedObjects(hrnSum2));
5274     }
5275
5276     // check sum1 against alloc2 nodes
5277     for (int i = 0; i < as2.getAllocationDepth(); ++i) {
5278       Integer idI2 = as2.getIthOldest(i);
5279       assert id2hrn.containsKey(idI2);
5280       HeapRegionNode hrnI2 = id2hrn.get(idI2);
5281       assert hrnI2 != null;
5282
5283       if(hrnSum1!=null) {
5284         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
5285       }
5286
5287       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
5288       for (int j = 0; j < as1.getAllocationDepth(); ++j) {
5289         Integer idI1 = as1.getIthOldest(j);
5290
5291         // if these are the same site, don't look for the same token, no
5292         // alias.
5293         // different tokens of the same site could alias together though
5294         if (idI1.equals(idI2)) {
5295           continue;
5296         }
5297
5298         HeapRegionNode hrnI1 = id2hrn.get(idI1);
5299
5300         common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
5301       }
5302     }
5303
5304     return common;
5305   }
5306
5307   public void makeInaccessible(Set<TempDescriptor> vars) {
5308     inaccessibleVars.addAll(vars);
5309   }
5310
5311   public void makeInaccessible(TempDescriptor td) {
5312     inaccessibleVars.add(td);
5313   }
5314
5315   public void makeAccessible(TempDescriptor td) {
5316     inaccessibleVars.remove(td);
5317   }
5318
5319   public boolean isAccessible(TempDescriptor td) {
5320     return !inaccessibleVars.contains(td);
5321   }
5322
5323   public Set<TempDescriptor> getInaccessibleVars() {
5324     return inaccessibleVars;
5325   }
5326
5327
5328
5329
5330   public Set<Alloc> canPointTo( TempDescriptor x ) {
5331
5332     if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5333       // if we don't care to track it, return null which means
5334       // "a client of this result shouldn't care either"
5335       return HeapAnalysis.DONTCARE_PTR;
5336     }
5337
5338     Set<Alloc> out = new HashSet<Alloc>();
5339
5340     VariableNode vn = getVariableNodeNoMutation( x );
5341     if( vn == null ) {
5342       // the empty set means "can't point to anything"
5343       return out;
5344     }
5345
5346     Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5347     while( edgeItr.hasNext() ) {
5348       HeapRegionNode hrn = edgeItr.next().getDst();
5349       out.add( hrn.getAllocSite() );
5350     }
5351
5352     return out;
5353   }
5354
5355
5356
5357   public Hashtable< Alloc, Set<Alloc> > canPointTo( TempDescriptor x,
5358                                                     String         field,
5359                                                     TypeDescriptor fieldType ) {
5360
5361     if( !DisjointAnalysis.shouldAnalysisTrack( x.getType() ) ) {
5362       // if we don't care to track it, return null which means
5363       // "a client of this result shouldn't care either"
5364       return HeapAnalysis.DONTCARE_DREF;
5365     }
5366
5367     Hashtable< Alloc, Set<Alloc> > out = new Hashtable< Alloc, Set<Alloc> >();
5368
5369     VariableNode vn = getVariableNodeNoMutation( x );
5370     if( vn == null ) {
5371       // the empty table means "x can't point to anything"
5372       return out;
5373     }
5374
5375     Iterator<RefEdge> edgeItr = vn.iteratorToReferencees();
5376     while( edgeItr.hasNext() ) {
5377       HeapRegionNode hrn = edgeItr.next().getDst();
5378       Alloc          key = hrn.getAllocSite();
5379
5380       if( !DisjointAnalysis.shouldAnalysisTrack( fieldType ) ) {
5381         // if we don't care to track it, put no entry which means
5382         // "a client of this result shouldn't care either"
5383         out.put( key, HeapAnalysis.DONTCARE_PTR );
5384         continue;
5385       }
5386
5387       Set<Alloc> moreValues = new HashSet<Alloc>();
5388       Iterator<RefEdge> edgeItr2 = hrn.iteratorToReferencees();
5389       while( edgeItr2.hasNext() ) {
5390         RefEdge edge = edgeItr2.next();
5391
5392         if( field.equals( edge.getField() ) ) {
5393           moreValues.add( edge.getDst().getAllocSite() );
5394         }
5395       }
5396
5397       if( out.containsKey( key ) ) {
5398         out.get( key ).addAll( moreValues );
5399       } else {
5400         out.put( key, moreValues );
5401       }
5402     }
5403
5404     return out;
5405   }
5406
5407
5408
5409   // for debugging
5410   public TempDescriptor findVariableByName( String name ) {
5411
5412     for( TempDescriptor td: td2vn.keySet() ) {
5413       if( td.getSymbol().contains( name ) ) {
5414         return td;
5415       }
5416     }
5417
5418     return null;
5419   }
5420
5421
5422   public void countGraphElements( GraphElementCount c ) {
5423
5424     for( HeapRegionNode node : id2hrn.values() ) {
5425
5426       if( node.isShadow() || node.isWiped() ) {
5427         // do not count nodes that are not functionally part of the
5428         // abstraction (they are in the graph for implementation
5429         // convenience when needed next)
5430         continue;
5431       }
5432
5433       c.nodeInc( 1 );
5434       c.nodeStateInc( node.getAlpha().numStates() );
5435       c.nodeStateNonzeroInc( node.getAlpha().numNonzeroTuples() );
5436
5437       // all edges in the graph point TO a heap node, so scanning
5438       // all referencers of all nodes gets every edge
5439       Iterator<RefEdge> refItr = node.iteratorToReferencers();
5440       while( refItr.hasNext() ) {
5441         RefEdge edge = refItr.next();
5442
5443         c.edgeInc( 1 );
5444         c.edgeStateInc( edge.getBeta().numStates() );
5445         c.edgeStateNonzeroInc( edge.getBeta().numNonzeroTuples() );
5446       }
5447     }
5448   }
5449
5450
5451   public void writeNodes( String filename ) {
5452
5453     try {
5454
5455       BufferedWriter bw = new BufferedWriter( new FileWriter( filename ) );
5456
5457       for( AllocSite as : allocSites ) {
5458         bw.write( "--------------------------\n" );
5459
5460         // allocation site ID, full type, assigned heap node IDs
5461         bw.write( as.toStringVerbose()+"\n"+
5462                   "  "+as.toStringJustIDs()+"\n" );
5463         bw.write( "  on "+
5464                   DisjointAnalysis.fn2filename.get( as.getFlatNew() )+":"+
5465                   as.getFlatNew().getNumLine()+"\n" );
5466
5467         // which of the nodes are actually in this graph?
5468         for( int i = 0; i < allocationDepth; ++i ) {
5469           Integer id = as.getIthOldest( i );
5470           String s = writeNodeFormat( id );
5471           if( s != null ) {
5472             bw.write( s );
5473           }
5474         }
5475         Integer id = as.getSummary();
5476         String s = writeNodeFormat( id );
5477         if( s != null ) {
5478           bw.write( s );
5479         }
5480       }
5481
5482       bw.close();
5483
5484     } catch( IOException e ) {
5485       System.out.println( "Error writing nodes to file: "+filename );
5486     }
5487   }
5488
5489   private String writeNodeFormat( Integer id ) {
5490     String s = null;
5491
5492     if( !id2hrn.containsKey( id ) ) {
5493       return s;
5494     }
5495
5496     s = "  "+id+" is present and refrenced by variables:\n";
5497
5498     HeapRegionNode hrn = id2hrn.get( id );
5499     Iterator<RefEdge> refItr = hrn.iteratorToReferencers();
5500     while( refItr.hasNext() ) {
5501       RefEdge    edge = refItr.next();
5502       RefSrcNode rsn  = edge.getSrc();
5503       if( rsn instanceof VariableNode ) {
5504         VariableNode vn = (VariableNode)rsn;
5505         s += "    "+vn+"\n";
5506       } else {
5507         HeapRegionNode hrnSrc = (HeapRegionNode)rsn;
5508         s += "    ";
5509         if( hrnSrc.isOutOfContext() ) {
5510           s += "(OOC)";
5511         }
5512         s += hrnSrc.getID()+"."+edge.getField()+"\n";
5513       }
5514     }
5515
5516     return s;
5517   }
5518 }