Robust/src/Analysis/Disjoint/ReachGraph.java

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