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