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