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   = true;
  14
  15   // a special out-of-scope temp
  16   protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
  17
  18   // some frequently used reachability constants
  19   protected static final ReachState rstateEmpty        = ReachState.factory();
  20   protected static final ReachSet   rsetEmpty          = ReachSet.factory();
  21   protected static final ReachSet   rsetWithEmptyState = ReachSet.factory( rstateEmpty );
  22
  23   // predicate constants
  24   protected static final ExistPred    predTrue   = ExistPred.factory(); // if no args, true
  25   protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
  26   protected static final ExistPredSet predsTrue  = ExistPredSet.factory( predTrue );
  27
  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   public ReachGraph() {
  43     id2hrn     = new Hashtable<Integer,        HeapRegionNode>();
  44     td2vn      = new Hashtable<TempDescriptor, VariableNode  >();
  45     allocSites = new HashSet<AllocSite>();
  46   }
  47
  48
  49   // temp descriptors are globally unique and map to
  50   // exactly one variable node, easy
  51   protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
  52     assert td != null;
  53
  54     if( !td2vn.containsKey( td ) ) {
  55       td2vn.put( td, new VariableNode( td ) );
  56     }
  57
  58     return td2vn.get( td );
  59   }
  60
  61   public boolean hasVariable( TempDescriptor td ) {
  62     return td2vn.containsKey( td );
  63   }
  64
  65
  66   // this suite of methods can be used to assert a
  67   // very important property of ReachGraph objects:
  68   // some element, HeapRegionNode, RefEdge etc.
  69   // should be referenced by at most ONE ReachGraph!!
  70   // If a heap region or edge or variable should be
  71   // in another graph, make a new object with
  72   // equivalent properties for a new graph
  73   public boolean belongsToThis( RefSrcNode rsn ) {
  74     if( rsn instanceof VariableNode ) {
  75       VariableNode vn = (VariableNode) rsn;
  76       return this.td2vn.get( vn.getTempDescriptor() ) == vn;
  77     }
  78     HeapRegionNode hrn = (HeapRegionNode) rsn;
  79     return this.id2hrn.get( hrn.getID() ) == hrn;
  80   }
  81
  82
  83
  84   // the reason for this method is to have the option
  85   // of creating new heap regions with specific IDs, or
  86   // duplicating heap regions with specific IDs (especially
  87   // in the merge() operation) or to create new heap
  88   // regions with a new unique ID
  89   protected HeapRegionNode
  90     createNewHeapRegionNode( Integer        id,
  91                              boolean        isSingleObject,
  92                              boolean        isNewSummary,
  93                              boolean        isFlagged,
  94                              boolean        isOutOfContext,
  95                              TypeDescriptor type,
  96                              AllocSite      allocSite,
  97                              ReachSet       inherent,
  98                              ReachSet       alpha,
  99                              ExistPredSet   preds,
 100                              String         description
 101                              ) {
 102
 103     boolean markForAnalysis = isFlagged;
 104
 105     TypeDescriptor typeToUse = null;
 106     if( allocSite != null ) {
 107       typeToUse = allocSite.getType();
 108       allocSites.add( allocSite );
 109     } else {
 110       typeToUse = type;
 111     }
 112
 113     if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
 114       markForAnalysis = true;
 115     }
 116
 117     if( id == null ) {
 118       id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
 119     }
 120
 121     if( inherent == null ) {
 122       if( markForAnalysis ) {
 123         inherent =
 124           ReachSet.factory(
 125                            ReachState.factory(
 126                                               ReachTuple.factory( id,
 127                                                                   !isSingleObject,
 128                                                                   ReachTuple.ARITY_ONE
 129                                                                   )
 130                                               )
 131                            );
 132       } else {
 133         inherent = rsetWithEmptyState;
 134       }
 135     }
 136
 137     if( alpha == null ) {
 138       alpha = inherent;
 139     }
 140
 141     if( preds == null ) {
 142       // TODO: do this right?  For out-of-context nodes?
 143       preds = ExistPredSet.factory();
 144     }
 145
 146     HeapRegionNode hrn = new HeapRegionNode( id,
 147                                              isSingleObject,
 148                                              markForAnalysis,
 149                                              isNewSummary,
 150                                              isOutOfContext,
 151                                              typeToUse,
 152                                              allocSite,
 153                                              inherent,
 154                                              alpha,
 155                                              preds,
 156                                              description );
 157     id2hrn.put( id, hrn );
 158     return hrn;
 159   }
 160
 161
 162
 163   ////////////////////////////////////////////////
 164   //
 165   //  Low-level referencee and referencer methods
 166   //
 167   //  These methods provide the lowest level for
 168   //  creating references between reachability nodes
 169   //  and handling the details of maintaining both
 170   //  list of referencers and referencees.
 171   //
 172   ////////////////////////////////////////////////
 173   protected void addRefEdge( RefSrcNode     referencer,
 174                              HeapRegionNode referencee,
 175                              RefEdge        edge ) {
 176     assert referencer != null;
 177     assert referencee != null;
 178     assert edge       != null;
 179     assert edge.getSrc() == referencer;
 180     assert edge.getDst() == referencee;
 181     assert belongsToThis( referencer );
 182     assert belongsToThis( referencee );
 183
 184     // edges are getting added twice to graphs now, the
 185     // kind that should have abstract facts merged--use
 186     // this check to prevent that
 187     assert referencer.getReferenceTo( referencee,
 188                                       edge.getType(),
 189                                       edge.getField()
 190                                       ) == null;
 191
 192     referencer.addReferencee( edge );
 193     referencee.addReferencer( edge );
 194   }
 195
 196   protected void removeRefEdge( RefEdge e ) {
 197     removeRefEdge( e.getSrc(),
 198                    e.getDst(),
 199                    e.getType(),
 200                    e.getField() );
 201   }
 202
 203   protected void removeRefEdge( RefSrcNode     referencer,
 204                                 HeapRegionNode referencee,
 205                                 TypeDescriptor type,
 206                                 String         field ) {
 207     assert referencer != null;
 208     assert referencee != null;
 209
 210     RefEdge edge = referencer.getReferenceTo( referencee,
 211                                               type,
 212                                               field );
 213     assert edge != null;
 214     assert edge == referencee.getReferenceFrom( referencer,
 215                                                 type,
 216                                                 field );
 217
 218     referencer.removeReferencee( edge );
 219     referencee.removeReferencer( edge );
 220   }
 221
 222   protected void clearRefEdgesFrom( RefSrcNode     referencer,
 223                                     TypeDescriptor type,
 224                                     String         field,
 225                                     boolean        removeAll ) {
 226     assert referencer != null;
 227
 228     // get a copy of the set to iterate over, otherwise
 229     // we will be trying to take apart the set as we
 230     // are iterating over it, which won't work
 231     Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
 232     while( i.hasNext() ) {
 233       RefEdge edge = i.next();
 234
 235       if( removeAll                                          ||
 236           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 237         ){
 238
 239         HeapRegionNode referencee = edge.getDst();
 240
 241         removeRefEdge( referencer,
 242                        referencee,
 243                        edge.getType(),
 244                        edge.getField() );
 245       }
 246     }
 247   }
 248
 249   protected void clearRefEdgesTo( HeapRegionNode referencee,
 250                                   TypeDescriptor type,
 251                                   String         field,
 252                                   boolean        removeAll ) {
 253     assert referencee != null;
 254
 255     // get a copy of the set to iterate over, otherwise
 256     // we will be trying to take apart the set as we
 257     // are iterating over it, which won't work
 258     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 259     while( i.hasNext() ) {
 260       RefEdge edge = i.next();
 261
 262       if( removeAll                                          ||
 263           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 264         ){
 265
 266         RefSrcNode referencer = edge.getSrc();
 267
 268         removeRefEdge( referencer,
 269                        referencee,
 270                        edge.getType(),
 271                        edge.getField() );
 272       }
 273     }
 274   }
 275
 276   protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
 277     assert referencee != null;
 278
 279     // get a copy of the set to iterate over, otherwise
 280     // we will be trying to take apart the set as we
 281     // are iterating over it, which won't work
 282     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 283     while( i.hasNext() ) {
 284       RefEdge edge = i.next();
 285       RefSrcNode referencer = edge.getSrc();
 286       if( !(referencer instanceof VariableNode) ) {
 287         removeRefEdge( referencer,
 288                        referencee,
 289                        edge.getType(),
 290                        edge.getField() );
 291       }
 292     }
 293   }
 294
 295
 296   ////////////////////////////////////////////////////
 297   //
 298   //  Assignment Operation Methods
 299   //
 300   //  These methods are high-level operations for
 301   //  modeling program assignment statements using
 302   //  the low-level reference create/remove methods
 303   //  above.
 304   //
 305   ////////////////////////////////////////////////////
 306
 307   public void assignTempXEqualToTempY( TempDescriptor x,
 308                                        TempDescriptor y ) {
 309     assignTempXEqualToCastedTempY( x, y, null );
 310   }
 311
 312   public void assignTempXEqualToCastedTempY( TempDescriptor x,
 313                                              TempDescriptor y,
 314                                              TypeDescriptor tdCast ) {
 315
 316     VariableNode lnX = getVariableNodeFromTemp( x );
 317     VariableNode lnY = getVariableNodeFromTemp( y );
 318
 319     clearRefEdgesFrom( lnX, null, null, true );
 320
 321     // note it is possible that the types of temps in the
 322     // flat node to analyze will reveal that some typed
 323     // edges in the reachability graph are impossible
 324     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 325
 326     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 327     while( itrYhrn.hasNext() ) {
 328       RefEdge        edgeY      = itrYhrn.next();
 329       HeapRegionNode referencee = edgeY.getDst();
 330       RefEdge        edgeNew    = edgeY.copy();
 331
 332       if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
 333         impossibleEdges.add( edgeY );
 334         continue;
 335       }
 336
 337       edgeNew.setSrc( lnX );
 338
 339       if( tdCast == null ) {
 340         edgeNew.setType( mostSpecificType( y.getType(),
 341                                            edgeY.getType(),
 342                                            referencee.getType()
 343                                            )
 344                          );
 345       } else {
 346         edgeNew.setType( mostSpecificType( y.getType(),
 347                                            edgeY.getType(),
 348                                            referencee.getType(),
 349                                            tdCast
 350                                            )
 351                          );
 352       }
 353
 354       edgeNew.setField( null );
 355
 356       addRefEdge( lnX, referencee, edgeNew );
 357     }
 358
 359     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 360     while( itrImp.hasNext() ) {
 361       RefEdge edgeImp = itrImp.next();
 362       removeRefEdge( edgeImp );
 363     }
 364   }
 365
 366
 367   public void assignTempXEqualToTempYFieldF( TempDescriptor  x,
 368                                              TempDescriptor  y,
 369                                              FieldDescriptor f ) {
 370     VariableNode lnX = getVariableNodeFromTemp( x );
 371     VariableNode lnY = getVariableNodeFromTemp( y );
 372
 373     clearRefEdgesFrom( lnX, null, null, true );
 374
 375     // note it is possible that the types of temps in the
 376     // flat node to analyze will reveal that some typed
 377     // edges in the reachability graph are impossible
 378     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 379
 380     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 381     while( itrYhrn.hasNext() ) {
 382       RefEdge        edgeY = itrYhrn.next();
 383       HeapRegionNode hrnY  = edgeY.getDst();
 384       ReachSet       betaY = edgeY.getBeta();
 385
 386       Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 387       while( itrHrnFhrn.hasNext() ) {
 388         RefEdge        edgeHrn = itrHrnFhrn.next();
 389         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 390         ReachSet       betaHrn = edgeHrn.getBeta();
 391
 392         // prune edges that are not a matching field
 393         if( edgeHrn.getType() != null &&
 394             !edgeHrn.getField().equals( f.getSymbol() )
 395             ) {
 396           continue;
 397         }
 398
 399         // check for impossible edges
 400         if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
 401           impossibleEdges.add( edgeHrn );
 402           continue;
 403         }
 404
 405         TypeDescriptor tdNewEdge =
 406           mostSpecificType( edgeHrn.getType(),
 407                             hrnHrn.getType()
 408                             );
 409
 410         RefEdge edgeNew = new RefEdge( lnX,
 411                                        hrnHrn,
 412                                        tdNewEdge,
 413                                        null,
 414                                        Canonical.intersection( betaY, betaHrn ),
 415                                        predsTrue
 416                                        );
 417
 418         addRefEdge( lnX, hrnHrn, edgeNew );
 419       }
 420     }
 421
 422     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 423     while( itrImp.hasNext() ) {
 424       RefEdge edgeImp = itrImp.next();
 425       removeRefEdge( edgeImp );
 426     }
 427
 428     // anytime you might remove edges between heap regions
 429     // you must global sweep to clean up broken reachability
 430     if( !impossibleEdges.isEmpty() ) {
 431       if( !DISABLE_GLOBAL_SWEEP ) {
 432         globalSweep();
 433       }
 434     }
 435   }
 436
 437
 438   public void assignTempXFieldFEqualToTempY( TempDescriptor  x,
 439                                              FieldDescriptor f,
 440                                              TempDescriptor  y ) {
 441
 442     VariableNode lnX = getVariableNodeFromTemp( x );
 443     VariableNode lnY = getVariableNodeFromTemp( y );
 444
 445     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 446     HashSet<RefEdge>        edgesWithNewBeta  = new HashSet<RefEdge>();
 447
 448     // note it is possible that the types of temps in the
 449     // flat node to analyze will reveal that some typed
 450     // edges in the reachability graph are impossible
 451     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 452
 453     // first look for possible strong updates and remove those edges
 454     boolean strongUpdate = false;
 455
 456     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 457     while( itrXhrn.hasNext() ) {
 458       RefEdge        edgeX = itrXhrn.next();
 459       HeapRegionNode hrnX  = edgeX.getDst();
 460
 461       // we can do a strong update here if one of two cases holds
 462       if( f != null &&
 463           f != DisjointAnalysis.getArrayField( f.getType() ) &&
 464           (   (hrnX.getNumReferencers()                         == 1) || // case 1
 465               (hrnX.isSingleObject() && lnX.getNumReferencees() == 1)    // case 2
 466               )
 467           ) {
 468         if( !DISABLE_STRONG_UPDATES ) {
 469           strongUpdate = true;
 470           clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
 471         }
 472       }
 473     }
 474
 475     // then do all token propagation
 476     itrXhrn = lnX.iteratorToReferencees();
 477     while( itrXhrn.hasNext() ) {
 478       RefEdge        edgeX = itrXhrn.next();
 479       HeapRegionNode hrnX  = edgeX.getDst();
 480       ReachSet       betaX = edgeX.getBeta();
 481       ReachSet       R     = Canonical.intersection( hrnX.getAlpha(),
 482                                                      edgeX.getBeta()
 483                                                      );
 484
 485       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 486       while( itrYhrn.hasNext() ) {
 487         RefEdge        edgeY = itrYhrn.next();
 488         HeapRegionNode hrnY  = edgeY.getDst();
 489         ReachSet       O     = edgeY.getBeta();
 490
 491         // check for impossible edges
 492         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 493           impossibleEdges.add( edgeY );
 494           continue;
 495         }
 496
 497         // propagate tokens over nodes starting from hrnSrc, and it will
 498         // take care of propagating back up edges from any touched nodes
 499         ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
 500         propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
 501
 502         // then propagate back just up the edges from hrn
 503         ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
 504         HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
 505
 506         Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
 507           new Hashtable<RefEdge, ChangeSet>();
 508
 509         Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
 510         while( referItr.hasNext() ) {
 511           RefEdge edgeUpstream = referItr.next();
 512           todoEdges.add( edgeUpstream );
 513           edgePlannedChanges.put( edgeUpstream, Cx );
 514         }
 515
 516         propagateTokensOverEdges( todoEdges,
 517                                   edgePlannedChanges,
 518                                   edgesWithNewBeta );
 519       }
 520     }
 521
 522
 523     // apply the updates to reachability
 524     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 525     while( nodeItr.hasNext() ) {
 526       nodeItr.next().applyAlphaNew();
 527     }
 528
 529     Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
 530     while( edgeItr.hasNext() ) {
 531       edgeItr.next().applyBetaNew();
 532     }
 533
 534
 535     // then go back through and add the new edges
 536     itrXhrn = lnX.iteratorToReferencees();
 537     while( itrXhrn.hasNext() ) {
 538       RefEdge        edgeX = itrXhrn.next();
 539       HeapRegionNode hrnX  = edgeX.getDst();
 540
 541       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 542       while( itrYhrn.hasNext() ) {
 543         RefEdge        edgeY = itrYhrn.next();
 544         HeapRegionNode hrnY  = edgeY.getDst();
 545
 546         // skip impossible edges here, we already marked them
 547         // when computing reachability propagations above
 548         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 549           continue;
 550         }
 551
 552         // prepare the new reference edge hrnX.f -> hrnY
 553         TypeDescriptor tdNewEdge =
 554           mostSpecificType( y.getType(),
 555                             edgeY.getType(),
 556                             hrnY.getType()
 557                             );
 558
 559         RefEdge edgeNew = new RefEdge( hrnX,
 560                                        hrnY,
 561                                        tdNewEdge,
 562                                        f.getSymbol(),
 563                                        Canonical.pruneBy( edgeY.getBeta(),
 564                                                           hrnX.getAlpha()
 565                                                           ),
 566                                        predsTrue
 567                                        );
 568
 569         // look to see if an edge with same field exists
 570         // and merge with it, otherwise just add the edge
 571         RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
 572                                                     tdNewEdge,
 573                                                     f.getSymbol() );
 574
 575         if( edgeExisting != null ) {
 576           edgeExisting.setBeta(
 577                                Canonical.union( edgeExisting.getBeta(),
 578                                                 edgeNew.getBeta()
 579                                                 )
 580                                );
 581           edgeExisting.setPreds(
 582                                 Canonical.join( edgeExisting.getPreds(),
 583                                                 edgeNew.getPreds()
 584                                                 )
 585                                 );
 586
 587         } else {
 588           addRefEdge( hrnX, hrnY, edgeNew );
 589         }
 590       }
 591     }
 592
 593     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 594     while( itrImp.hasNext() ) {
 595       RefEdge edgeImp = itrImp.next();
 596       removeRefEdge( edgeImp );
 597     }
 598
 599     // if there was a strong update, make sure to improve
 600     // reachability with a global sweep
 601     if( strongUpdate || !impossibleEdges.isEmpty() ) {
 602       if( !DISABLE_GLOBAL_SWEEP ) {
 603         globalSweep();
 604       }
 605     }
 606   }
 607
 608
 609   public void assignReturnEqualToTemp( TempDescriptor x ) {
 610
 611     VariableNode lnR = getVariableNodeFromTemp( tdReturn );
 612     VariableNode lnX = getVariableNodeFromTemp( x );
 613
 614     clearRefEdgesFrom( lnR, null, null, true );
 615
 616     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 617     while( itrXhrn.hasNext() ) {
 618       RefEdge        edgeX      = itrXhrn.next();
 619       HeapRegionNode referencee = edgeX.getDst();
 620       RefEdge        edgeNew    = edgeX.copy();
 621       edgeNew.setSrc( lnR );
 622
 623       addRefEdge( lnR, referencee, edgeNew );
 624     }
 625   }
 626
 627
 628   public void assignTempEqualToNewAlloc( TempDescriptor x,
 629                                          AllocSite      as ) {
 630     assert x  != null;
 631     assert as != null;
 632
 633     age( as );
 634
 635     // after the age operation the newest (or zero-ith oldest)
 636     // node associated with the allocation site should have
 637     // no references to it as if it were a newly allocated
 638     // heap region
 639     Integer        idNewest   = as.getIthOldest( 0 );
 640     HeapRegionNode hrnNewest  = id2hrn.get( idNewest );
 641     assert         hrnNewest != null;
 642
 643     VariableNode lnX = getVariableNodeFromTemp( x );
 644     clearRefEdgesFrom( lnX, null, null, true );
 645
 646     // make a new reference to allocated node
 647     TypeDescriptor type = as.getType();
 648
 649     RefEdge edgeNew =
 650       new RefEdge( lnX,                  // source
 651                    hrnNewest,            // dest
 652                    type,                 // type
 653                    null,                 // field name
 654                    hrnNewest.getAlpha(), // beta
 655                    predsTrue             // predicates
 656                    );
 657
 658     addRefEdge( lnX, hrnNewest, edgeNew );
 659   }
 660
 661
 662   // use the allocation site (unique to entire analysis) to
 663   // locate the heap region nodes in this reachability graph
 664   // that should be aged.  The process models the allocation
 665   // of new objects and collects all the oldest allocations
 666   // in a summary node to allow for a finite analysis
 667   //
 668   // There is an additional property of this method.  After
 669   // running it on a particular reachability graph (many graphs
 670   // may have heap regions related to the same allocation site)
 671   // the heap region node objects in this reachability graph will be
 672   // allocated.  Therefore, after aging a graph for an allocation
 673   // site, attempts to retrieve the heap region nodes using the
 674   // integer id's contained in the allocation site should always
 675   // return non-null heap regions.
 676   public void age( AllocSite as ) {
 677
 678     // keep track of allocation sites that are represented
 679     // in this graph for efficiency with other operations
 680     allocSites.add( as );
 681
 682     // if there is a k-th oldest node, it merges into
 683     // the summary node
 684     Integer idK = as.getOldest();
 685     if( id2hrn.containsKey( idK ) ) {
 686       HeapRegionNode hrnK = id2hrn.get( idK );
 687
 688       // retrieve the summary node, or make it
 689       // from scratch
 690       HeapRegionNode hrnSummary = getSummaryNode( as, false );
 691
 692       mergeIntoSummary( hrnK, hrnSummary );
 693     }
 694
 695     // move down the line of heap region nodes
 696     // clobbering the ith and transferring all references
 697     // to and from i-1 to node i.
 698     for( int i = allocationDepth - 1; i > 0; --i ) {
 699
 700       // only do the transfer if the i-1 node exists
 701       Integer idImin1th = as.getIthOldest( i - 1 );
 702       if( id2hrn.containsKey( idImin1th ) ) {
 703         HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
 704         if( hrnImin1.isWiped() ) {
 705           // there is no info on this node, just skip
 706           continue;
 707         }
 708
 709         // either retrieve or make target of transfer
 710         HeapRegionNode hrnI = getIthNode( as, i, false );
 711
 712         transferOnto( hrnImin1, hrnI );
 713       }
 714
 715     }
 716
 717     // as stated above, the newest node should have had its
 718     // references moved over to the second oldest, so we wipe newest
 719     // in preparation for being the new object to assign something to
 720     HeapRegionNode hrn0 = getIthNode( as, 0, false );
 721     wipeOut( hrn0, true );
 722
 723     // now tokens in reachability sets need to "age" also
 724     Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
 725     while( itrAllVariableNodes.hasNext() ) {
 726       Map.Entry    me = (Map.Entry)    itrAllVariableNodes.next();
 727       VariableNode ln = (VariableNode) me.getValue();
 728
 729       Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
 730       while( itrEdges.hasNext() ) {
 731         ageTuplesFrom( as, itrEdges.next() );
 732       }
 733     }
 734
 735     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 736     while( itrAllHRNodes.hasNext() ) {
 737       Map.Entry      me       = (Map.Entry)      itrAllHRNodes.next();
 738       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 739
 740       ageTuplesFrom( as, hrnToAge );
 741
 742       Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
 743       while( itrEdges.hasNext() ) {
 744         ageTuplesFrom( as, itrEdges.next() );
 745       }
 746     }
 747
 748
 749     // after tokens have been aged, reset newest node's reachability
 750     // and a brand new node has a "true" predicate
 751     hrn0.setAlpha( hrn0.getInherent() );
 752     hrn0.setPreds( predsTrue );
 753   }
 754
 755
 756   // either retrieve or create the needed heap region node
 757   protected HeapRegionNode getSummaryNode( AllocSite as,
 758                                            boolean   shadow ) {
 759
 760     Integer idSummary;
 761     if( shadow ) {
 762       idSummary = as.getSummaryShadow();
 763     } else {
 764       idSummary = as.getSummary();
 765     }
 766
 767     HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 768
 769     if( hrnSummary == null ) {
 770
 771       boolean hasFlags = false;
 772       if( as.getType().isClass() ) {
 773         hasFlags = as.getType().getClassDesc().hasFlags();
 774       }
 775
 776       if( as.getFlag() ){
 777         hasFlags = as.getFlag();
 778       }
 779
 780       String strDesc = as.toStringForDOT()+"\\nsummary";
 781       if( shadow ) {
 782         strDesc += " shadow";
 783       }
 784
 785       hrnSummary =
 786         createNewHeapRegionNode( idSummary,    // id or null to generate a new one
 787                                  false,        // single object?
 788                                  true,         // summary?
 789                                  hasFlags,     // flagged?
 790                                  false,        // out-of-context?
 791                                  as.getType(), // type
 792                                  as,           // allocation site
 793                                  null,         // inherent reach
 794                                  null,         // current reach
 795                                  predsEmpty,   // predicates
 796                                  strDesc       // description
 797                                  );
 798     }
 799
 800     return hrnSummary;
 801   }
 802
 803   // either retrieve or create the needed heap region node
 804   protected HeapRegionNode getIthNode( AllocSite as,
 805                                        Integer   i,
 806                                        boolean   shadow ) {
 807
 808     Integer idIth;
 809     if( shadow ) {
 810       idIth = as.getIthOldestShadow( i );
 811     } else {
 812       idIth = as.getIthOldest( i );
 813     }
 814
 815     HeapRegionNode hrnIth = id2hrn.get( idIth );
 816
 817     if( hrnIth == null ) {
 818
 819       boolean hasFlags = false;
 820       if( as.getType().isClass() ) {
 821         hasFlags = as.getType().getClassDesc().hasFlags();
 822       }
 823
 824       if( as.getFlag() ){
 825         hasFlags = as.getFlag();
 826       }
 827
 828       String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
 829       if( shadow ) {
 830         strDesc += " shadow";
 831       }
 832
 833       hrnIth = createNewHeapRegionNode( idIth,        // id or null to generate a new one
 834                                         true,         // single object?
 835                                         false,        // summary?
 836                                         hasFlags,     // flagged?
 837                                         false,        // out-of-context?
 838                                         as.getType(), // type
 839                                         as,           // allocation site
 840                                         null,         // inherent reach
 841                                         null,         // current reach
 842                                         predsEmpty,   // predicates
 843                                         strDesc       // description
 844                                         );
 845     }
 846
 847     return hrnIth;
 848   }
 849
 850
 851   protected void mergeIntoSummary( HeapRegionNode hrn,
 852                                    HeapRegionNode hrnSummary ) {
 853     assert hrnSummary.isNewSummary();
 854
 855     // assert that these nodes belong to THIS graph
 856     assert belongsToThis( hrn );
 857     assert belongsToThis( hrnSummary );
 858
 859     assert hrn != hrnSummary;
 860
 861     // transfer references _from_ hrn over to hrnSummary
 862     Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
 863     while( itrReferencee.hasNext() ) {
 864       RefEdge edge       = itrReferencee.next();
 865       RefEdge edgeMerged = edge.copy();
 866       edgeMerged.setSrc( hrnSummary );
 867
 868       HeapRegionNode hrnReferencee = edge.getDst();
 869       RefEdge        edgeSummary   =
 870         hrnSummary.getReferenceTo( hrnReferencee,
 871                                    edge.getType(),
 872                                    edge.getField()
 873                                    );
 874
 875       if( edgeSummary == null ) {
 876         // the merge is trivial, nothing to be done
 877         addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
 878
 879       } else {
 880         // otherwise an edge from the referencer to hrnSummary exists already
 881         // and the edge referencer->hrn should be merged with it
 882         edgeSummary.setBeta(
 883                             Canonical.union( edgeMerged.getBeta(),
 884                                              edgeSummary.getBeta()
 885                                              )
 886                              );
 887         edgeSummary.setPreds(
 888                              Canonical.join( edgeMerged.getPreds(),
 889                                              edgeSummary.getPreds()
 890                                              )
 891                               );
 892       }
 893     }
 894
 895     // next transfer references _to_ hrn over to hrnSummary
 896     Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
 897     while( itrReferencer.hasNext() ) {
 898       RefEdge edge         = itrReferencer.next();
 899       RefEdge edgeMerged   = edge.copy();
 900       edgeMerged.setDst( hrnSummary );
 901
 902       RefSrcNode onReferencer = edge.getSrc();
 903       RefEdge    edgeSummary  =
 904         onReferencer.getReferenceTo( hrnSummary,
 905                                      edge.getType(),
 906                                      edge.getField()
 907                                      );
 908
 909       if( edgeSummary == null ) {
 910         // the merge is trivial, nothing to be done
 911         addRefEdge( onReferencer, hrnSummary, edgeMerged );
 912
 913       } else {
 914         // otherwise an edge from the referencer to alpha_S exists already
 915         // and the edge referencer->alpha_K should be merged with it
 916         edgeSummary.setBeta(
 917                             Canonical.union( edgeMerged.getBeta(),
 918                                              edgeSummary.getBeta()
 919                                              )
 920                              );
 921         edgeSummary.setPreds(
 922                              Canonical.join( edgeMerged.getPreds(),
 923                                              edgeSummary.getPreds()
 924                                              )
 925                               );
 926       }
 927     }
 928
 929     // then merge hrn reachability into hrnSummary
 930     hrnSummary.setAlpha(
 931                         Canonical.union( hrnSummary.getAlpha(),
 932                                          hrn.getAlpha()
 933                                          )
 934                          );
 935
 936     hrnSummary.setPreds(
 937                         Canonical.join( hrnSummary.getPreds(),
 938                                         hrn.getPreds()
 939                                         )
 940                         );
 941
 942     // and afterward, this node is gone
 943     wipeOut( hrn, true );
 944   }
 945
 946
 947   protected void transferOnto( HeapRegionNode hrnA,
 948                                HeapRegionNode hrnB ) {
 949
 950     assert belongsToThis( hrnA );
 951     assert belongsToThis( hrnB );
 952     assert hrnA != hrnB;
 953
 954     // clear references in and out of node b?
 955     assert hrnB.isWiped();
 956
 957     // copy each: (edge in and out of A) to B
 958     Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
 959     while( itrReferencee.hasNext() ) {
 960       RefEdge        edge          = itrReferencee.next();
 961       HeapRegionNode hrnReferencee = edge.getDst();
 962       RefEdge        edgeNew       = edge.copy();
 963       edgeNew.setSrc( hrnB );
 964       edgeNew.setDst( hrnReferencee );
 965
 966       addRefEdge( hrnB, hrnReferencee, edgeNew );
 967     }
 968
 969     Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
 970     while( itrReferencer.hasNext() ) {
 971       RefEdge    edge          = itrReferencer.next();
 972       RefSrcNode rsnReferencer = edge.getSrc();
 973       RefEdge    edgeNew       = edge.copy();
 974       edgeNew.setSrc( rsnReferencer );
 975       edgeNew.setDst( hrnB );
 976
 977       addRefEdge( rsnReferencer, hrnB, edgeNew );
 978     }
 979
 980     // replace hrnB reachability and preds with hrnA's
 981     hrnB.setAlpha( hrnA.getAlpha() );
 982     hrnB.setPreds( hrnA.getPreds() );
 983
 984     // after transfer, wipe out source
 985     wipeOut( hrnA, true );
 986   }
 987
 988
 989   // the purpose of this method is to conceptually "wipe out"
 990   // a heap region from the graph--purposefully not called REMOVE
 991   // because the node is still hanging around in the graph, just
 992   // not mechanically connected or have any reach or predicate
 993   // information on it anymore--lots of ops can use this
 994   protected void wipeOut( HeapRegionNode hrn,
 995                           boolean        wipeVariableReferences ) {
 996
 997     assert belongsToThis( hrn );
 998
 999     clearRefEdgesFrom( hrn, null, null, true );
1000
1001     if( wipeVariableReferences ) {
1002       clearRefEdgesTo( hrn, null, null, true );
1003     } else {
1004       clearNonVarRefEdgesTo( hrn );
1005     }
1006
1007     hrn.setAlpha( rsetEmpty );
1008     hrn.setPreds( predsEmpty );
1009   }
1010
1011
1012   protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1013     edge.setBeta(
1014                  Canonical.ageTuplesFrom( edge.getBeta(),
1015                                           as
1016                                           )
1017                   );
1018   }
1019
1020   protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1021     hrn.setAlpha(
1022                  Canonical.ageTuplesFrom( hrn.getAlpha(),
1023                                           as
1024                                           )
1025                   );
1026   }
1027
1028
1029
1030   protected void propagateTokensOverNodes( HeapRegionNode          nPrime,
1031                                            ChangeSet               c0,
1032                                            HashSet<HeapRegionNode> nodesWithNewAlpha,
1033                                            HashSet<RefEdge>        edgesWithNewBeta ) {
1034
1035     HashSet<HeapRegionNode> todoNodes
1036       = new HashSet<HeapRegionNode>();
1037     todoNodes.add( nPrime );
1038
1039     HashSet<RefEdge> todoEdges
1040       = new HashSet<RefEdge>();
1041
1042     Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1043       = new Hashtable<HeapRegionNode, ChangeSet>();
1044     nodePlannedChanges.put( nPrime, c0 );
1045
1046     Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1047       = new Hashtable<RefEdge, ChangeSet>();
1048
1049     // first propagate change sets everywhere they can go
1050     while( !todoNodes.isEmpty() ) {
1051       HeapRegionNode n = todoNodes.iterator().next();
1052       ChangeSet      C = nodePlannedChanges.get( n );
1053
1054       Iterator<RefEdge> referItr = n.iteratorToReferencers();
1055       while( referItr.hasNext() ) {
1056         RefEdge edge = referItr.next();
1057         todoEdges.add( edge );
1058
1059         if( !edgePlannedChanges.containsKey( edge ) ) {
1060           edgePlannedChanges.put( edge,
1061                                   ChangeSet.factory()
1062                                   );
1063         }
1064
1065         edgePlannedChanges.put( edge,
1066                                 Canonical.union( edgePlannedChanges.get( edge ),
1067                                                  C
1068                                                  )
1069                                 );
1070       }
1071
1072       Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1073       while( refeeItr.hasNext() ) {
1074         RefEdge        edgeF = refeeItr.next();
1075         HeapRegionNode m     = edgeF.getDst();
1076
1077         ChangeSet changesToPass = ChangeSet.factory();
1078
1079         Iterator<ChangeTuple> itrCprime = C.iterator();
1080         while( itrCprime.hasNext() ) {
1081           ChangeTuple c = itrCprime.next();
1082           if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1083             changesToPass = Canonical.union( changesToPass, c );
1084           }
1085         }
1086
1087         if( !changesToPass.isEmpty() ) {
1088           if( !nodePlannedChanges.containsKey( m ) ) {
1089             nodePlannedChanges.put( m, ChangeSet.factory() );
1090           }
1091
1092           ChangeSet currentChanges = nodePlannedChanges.get( m );
1093
1094           if( !changesToPass.isSubset( currentChanges ) ) {
1095
1096             nodePlannedChanges.put( m,
1097                                     Canonical.union( currentChanges,
1098                                                      changesToPass
1099                                                      )
1100                                     );
1101             todoNodes.add( m );
1102           }
1103         }
1104       }
1105
1106       todoNodes.remove( n );
1107     }
1108
1109     // then apply all of the changes for each node at once
1110     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1111     while( itrMap.hasNext() ) {
1112       Map.Entry      me = (Map.Entry)      itrMap.next();
1113       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1114       ChangeSet      C  = (ChangeSet)      me.getValue();
1115
1116       // this propagation step is with respect to one change,
1117       // so we capture the full change from the old alpha:
1118       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1119                                                       C,
1120                                                       true
1121                                                       );
1122       // but this propagation may be only one of many concurrent
1123       // possible changes, so keep a running union with the node's
1124       // partially updated new alpha set
1125       n.setAlphaNew( Canonical.union( n.getAlphaNew(),
1126                                       localDelta
1127                                       )
1128                      );
1129
1130       nodesWithNewAlpha.add( n );
1131     }
1132
1133     propagateTokensOverEdges( todoEdges,
1134                               edgePlannedChanges,
1135                               edgesWithNewBeta
1136                               );
1137   }
1138
1139
1140   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1141                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1142                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1143
1144     // first propagate all change tuples everywhere they can go
1145     while( !todoEdges.isEmpty() ) {
1146       RefEdge edgeE = todoEdges.iterator().next();
1147       todoEdges.remove( edgeE );
1148
1149       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1150         edgePlannedChanges.put( edgeE,
1151                                 ChangeSet.factory()
1152                                 );
1153       }
1154
1155       ChangeSet C = edgePlannedChanges.get( edgeE );
1156
1157       ChangeSet changesToPass = ChangeSet.factory();
1158
1159       Iterator<ChangeTuple> itrC = C.iterator();
1160       while( itrC.hasNext() ) {
1161         ChangeTuple c = itrC.next();
1162         if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1163           changesToPass = Canonical.union( changesToPass, c );
1164         }
1165       }
1166
1167       RefSrcNode rsn = edgeE.getSrc();
1168
1169       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1170         HeapRegionNode n = (HeapRegionNode) rsn;
1171
1172         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1173         while( referItr.hasNext() ) {
1174           RefEdge edgeF = referItr.next();
1175
1176           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1177             edgePlannedChanges.put( edgeF,
1178                                     ChangeSet.factory()
1179                                     );
1180           }
1181
1182           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1183
1184           if( !changesToPass.isSubset( currentChanges ) ) {
1185             todoEdges.add( edgeF );
1186             edgePlannedChanges.put( edgeF,
1187                                     Canonical.union( currentChanges,
1188                                                      changesToPass
1189                                                      )
1190                                     );
1191           }
1192         }
1193       }
1194     }
1195
1196     // then apply all of the changes for each edge at once
1197     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1198     while( itrMap.hasNext() ) {
1199       Map.Entry me = (Map.Entry) itrMap.next();
1200       RefEdge   e  = (RefEdge)   me.getKey();
1201       ChangeSet C  = (ChangeSet) me.getValue();
1202
1203       // this propagation step is with respect to one change,
1204       // so we capture the full change from the old beta:
1205       ReachSet localDelta =
1206         Canonical.applyChangeSet( e.getBeta(),
1207                                   C,
1208                                   true
1209                                   );
1210
1211       // but this propagation may be only one of many concurrent
1212       // possible changes, so keep a running union with the edge's
1213       // partially updated new beta set
1214       e.setBetaNew( Canonical.union( e.getBetaNew(),
1215                                      localDelta
1216                                      )
1217                     );
1218
1219       edgesWithNewBeta.add( e );
1220     }
1221   }
1222
1223
1224   // used in makeCalleeView below to decide if there is
1225   // already an appropriate out-of-context edge in a callee
1226   // view graph for merging, or null if a new one will be added
1227   protected RefEdge
1228     getOutOfContextReferenceTo( HeapRegionNode hrn,
1229                                 TypeDescriptor srcType,
1230                                 TypeDescriptor refType,
1231                                 String         refField ) {
1232     assert belongsToThis( hrn );
1233
1234     HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1235     if( hrnInContext == null ) {
1236       return null;
1237     }
1238
1239     Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1240     while( refItr.hasNext() ) {
1241       RefEdge re = refItr.next();
1242
1243       assert belongsToThis( re.getSrc() );
1244       assert belongsToThis( re.getDst() );
1245
1246       if( !(re.getSrc() instanceof HeapRegionNode) ) {
1247         continue;
1248       }
1249
1250       HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1251       if( !hrnSrc.isOutOfContext() ) {
1252         continue;
1253       }
1254
1255       if( srcType == null ) {
1256         if( hrnSrc.getType() != null ) {
1257           continue;
1258         }
1259       } else {
1260         if( !srcType.equals( hrnSrc.getType() ) ) {
1261           continue;
1262         }
1263       }
1264
1265       if( !re.typeEquals( refType ) ) {
1266         continue;
1267       }
1268
1269       if( !re.fieldEquals( refField ) ) {
1270         continue;
1271       }
1272
1273       // tada!  We found it!
1274       return re;
1275     }
1276
1277     return null;
1278   }
1279
1280
1281   // use this method to make a new reach graph that is
1282   // what heap the FlatMethod callee from the FlatCall
1283   // would start with reaching from its arguments in
1284   // this reach graph
1285   public ReachGraph
1286     makeCalleeView( FlatCall     fc,
1287                     FlatMethod   fmCallee,
1288                     Set<Integer> callerNodeIDsCopiedToCallee,
1289                     boolean      writeDebugDOTs
1290                     ) {
1291
1292     // the callee view is a new graph: DON'T MODIFY
1293     // *THIS* graph
1294     ReachGraph rg = new ReachGraph();
1295
1296     // track what parts of this graph have already been
1297     // added to callee view, variables not needed.
1298     // Note that we need this because when we traverse
1299     // this caller graph for each parameter we may find
1300     // nodes and edges more than once (which the per-param
1301     // "visit" sets won't show) and we only want to create
1302     // an element in the new callee view one time
1303
1304
1305     // a conservative starting point is to take the
1306     // mechanically-reachable-from-arguments graph
1307     // as opposed to using reachability information
1308     // to prune the graph further
1309     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1310
1311       // for each parameter index, get the symbol in the
1312       // caller view and callee view
1313
1314       // argument defined here is the symbol in the caller
1315       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1316
1317       // parameter defined here is the symbol in the callee
1318       TempDescriptor tdParam = fmCallee.getParameter( i );
1319
1320       // use these two VariableNode objects to translate
1321       // between caller and callee--its easy to compare
1322       // a HeapRegionNode across callee and caller because
1323       // they will have the same heap region ID
1324       VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1325       VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1326
1327       // now traverse the calleR view using the argument to
1328       // build the calleE view which has the parameter symbol
1329       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1330       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1331       toVisitInCaller.add( vnCaller );
1332
1333       while( !toVisitInCaller.isEmpty() ) {
1334         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1335         RefSrcNode rsnCallee;
1336
1337         toVisitInCaller.remove( rsnCaller );
1338         visitedInCaller.add( rsnCaller );
1339
1340         // FIRST - setup the source end of an edge, and
1341         // remember the identifying info of the source
1342         // to build predicates
1343         TempDescriptor tdSrc    = null;
1344         Integer        hrnSrcID = null;
1345
1346         if( rsnCaller == vnCaller ) {
1347           // if the caller node is the param symbol, we
1348           // have to do this translation for the callee
1349           rsnCallee = vnCallee;
1350           tdSrc     = tdArg;
1351
1352         } else {
1353           // otherwise the callee-view node is a heap
1354           // region with the same ID, that may or may
1355           // not have been created already
1356           assert rsnCaller instanceof HeapRegionNode;
1357
1358           HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1359           hrnSrcID = hrnSrcCaller.getID();
1360
1361           if( !callerNodeIDsCopiedToCallee.contains( hrnSrcID ) ) {
1362
1363             ExistPred pred =
1364               ExistPred.factory( hrnSrcID, null );
1365
1366             ExistPredSet preds =
1367               ExistPredSet.factory( pred );
1368
1369             rsnCallee =
1370               rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1371                                           hrnSrcCaller.isSingleObject(),
1372                                           hrnSrcCaller.isNewSummary(),
1373                                           hrnSrcCaller.isFlagged(),
1374                                           false, // out-of-context?
1375                                           hrnSrcCaller.getType(),
1376                                           hrnSrcCaller.getAllocSite(),
1377                                           /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/,
1378                                           /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/,
1379                                           preds,
1380                                           hrnSrcCaller.getDescription()
1381                                           );
1382
1383             callerNodeIDsCopiedToCallee.add( hrnSrcID );
1384
1385           } else {
1386             rsnCallee = rg.id2hrn.get( hrnSrcID );
1387           }
1388         }
1389
1390         // SECOND - go over all edges from that source
1391
1392         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1393         while( itrRefEdges.hasNext() ) {
1394           RefEdge        reCaller  = itrRefEdges.next();
1395           HeapRegionNode hrnCaller = reCaller.getDst();
1396           HeapRegionNode hrnCallee;
1397
1398           // THIRD - setup destination ends of edges
1399           Integer hrnDstID = hrnCaller.getID();
1400
1401           if( !callerNodeIDsCopiedToCallee.contains( hrnDstID ) ) {
1402
1403             ExistPred pred =
1404               ExistPred.factory( hrnDstID, null );
1405
1406             ExistPredSet preds =
1407               ExistPredSet.factory( pred );
1408
1409             hrnCallee =
1410               rg.createNewHeapRegionNode( hrnDstID,
1411                                           hrnCaller.isSingleObject(),
1412                                           hrnCaller.isNewSummary(),
1413                                           hrnCaller.isFlagged(),
1414                                           false, // out-of-context?
1415                                           hrnCaller.getType(),
1416                                           hrnCaller.getAllocSite(),
1417                                           /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/,
1418                                           /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/,
1419                                           preds,
1420                                           hrnCaller.getDescription()
1421                                           );
1422
1423             callerNodeIDsCopiedToCallee.add( hrnDstID );
1424
1425           } else {
1426             hrnCallee = rg.id2hrn.get( hrnDstID );
1427           }
1428
1429           // FOURTH - copy edge over if needed
1430           RefEdge reCallee = rsnCallee.getReferenceTo( hrnCallee,
1431                                                        reCaller.getType(),
1432                                                        reCaller.getField()
1433                                                        );
1434           if( reCallee == null ) {
1435
1436             ExistPred pred =
1437               ExistPred.factory( tdSrc,
1438                                  hrnSrcID,
1439                                  hrnDstID,
1440                                  reCaller.getType(),
1441                                  reCaller.getField(),
1442                                  null,
1443                                  rsnCaller instanceof VariableNode ); // out-of-context
1444
1445             ExistPredSet preds =
1446               ExistPredSet.factory( pred );
1447
1448             rg.addRefEdge( rsnCallee,
1449                            hrnCallee,
1450                            new RefEdge( rsnCallee,
1451                                         hrnCallee,
1452                                         reCaller.getType(),
1453                                         reCaller.getField(),
1454                                         /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/,
1455                                         preds
1456                                         )
1457                            );
1458           }
1459
1460           // keep traversing nodes reachable from param i
1461           // that we haven't visited yet
1462           if( !visitedInCaller.contains( hrnCaller ) ) {
1463             toVisitInCaller.add( hrnCaller );
1464           }
1465
1466         } // end edge iteration
1467       } // end visiting heap nodes in caller
1468     } // end iterating over parameters as starting points
1469
1470
1471     // find the set of edges in this graph with source
1472     // out-of-context (not in nodes copied) and have a
1473     // destination in context (one of nodes copied) as
1474     // a starting point for building out-of-context nodes
1475     Iterator<Integer> itrInContext =
1476       callerNodeIDsCopiedToCallee.iterator();
1477     while( itrInContext.hasNext() ) {
1478       Integer        hrnID                 = itrInContext.next();
1479       HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1480
1481       Iterator<RefEdge> itrMightCross =
1482         hrnCallerAndInContext.iteratorToReferencers();
1483       while( itrMightCross.hasNext() ) {
1484         RefEdge edgeMightCross = itrMightCross.next();
1485
1486         RefSrcNode rsnCallerAndOutContext =
1487           edgeMightCross.getSrc();
1488
1489         TypeDescriptor oocNodeType;
1490         ReachSet       oocReach;
1491
1492         TempDescriptor oocPredSrcTemp = null;
1493         Integer        oocPredSrcID   = null;
1494
1495         if( rsnCallerAndOutContext instanceof VariableNode ) {
1496           // variables are always out-of-context
1497           oocNodeType = null;
1498           oocReach    = rsetEmpty;
1499           oocPredSrcTemp =
1500             ((VariableNode)rsnCallerAndOutContext).getTempDescriptor();
1501
1502         } else {
1503
1504           HeapRegionNode hrnCallerAndOutContext =
1505             (HeapRegionNode) rsnCallerAndOutContext;
1506
1507           // is this source node out-of-context?
1508           if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1509             // no, skip this edge
1510             continue;
1511           }
1512
1513           oocNodeType  = hrnCallerAndOutContext.getType();
1514           oocReach     = hrnCallerAndOutContext.getAlpha();
1515           oocPredSrcID = hrnCallerAndOutContext.getID();
1516         }
1517
1518         // if we're here we've found an out-of-context edge
1519
1520         ExistPred pred =
1521           ExistPred.factory( oocPredSrcTemp,
1522                              oocPredSrcID,
1523                              hrnID,
1524                              edgeMightCross.getType(),
1525                              edgeMightCross.getField(),
1526                              null,
1527                              true ); // out-of-context
1528
1529         ExistPredSet preds =
1530           ExistPredSet.factory( pred );
1531
1532
1533         HeapRegionNode hrnCalleeAndInContext =
1534           rg.id2hrn.get( hrnCallerAndInContext.getID() );
1535
1536         RefEdge oocEdgeExisting =
1537           rg.getOutOfContextReferenceTo( hrnCalleeAndInContext,
1538                                          oocNodeType,
1539                                          edgeMightCross.getType(),
1540                                          edgeMightCross.getField()
1541                                          );
1542
1543         if( oocEdgeExisting == null ) {
1544           // we found a reference that crosses from out-of-context
1545           // to in-context, so build a special out-of-context node
1546           // for the callee IHM and its reference edge
1547
1548           // for consistency, map one out-of-context "identifier"
1549           // to one heap region node id, otherwise no convergence
1550           String oocid = "oocid"+
1551             fmCallee+
1552             hrnCalleeAndInContext.getIDString()+
1553             oocNodeType+
1554             edgeMightCross.getType()+
1555             edgeMightCross.getField();
1556
1557           Integer oocHrnID = oocid2hrnid.get( oocid );
1558
1559           HeapRegionNode hrnCalleeAndOutContext;
1560
1561           if( oocHrnID == null ) {
1562
1563             hrnCalleeAndOutContext =
1564               rg.createNewHeapRegionNode( null,  // ID
1565                                           false, // single object?
1566                                           false, // new summary?
1567                                           false, // flagged?
1568                                           true,  // out-of-context?
1569                                           oocNodeType,
1570                                           null,  // alloc site, shouldn't be used
1571                                           /*toShadowTokens( this,*/ oocReach  /*)*/, // inherent
1572                                           /*toShadowTokens( this,*/ oocReach /*)*/, // alpha
1573                                           preds,
1574                                           "out-of-context"
1575                                           );
1576
1577             oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1578
1579           } else {
1580
1581             // the mapping already exists, so see if node is there
1582             hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1583
1584             if( hrnCalleeAndOutContext == null ) {
1585               // nope, make it
1586               hrnCalleeAndOutContext =
1587                 rg.createNewHeapRegionNode( oocHrnID,  // ID
1588                                             false, // single object?
1589                                             false, // new summary?
1590                                             false, // flagged?
1591                                             true,  // out-of-context?
1592                                             oocNodeType,
1593                                             null,  // alloc site, shouldn't be used
1594                                             /*toShadowTokens( this,*/ oocReach  /*)*/, // inherent
1595                                             /*toShadowTokens( this,*/ oocReach /*)*/, // alpha
1596                                             preds,
1597                                             "out-of-context"
1598                                             );
1599             }
1600           }
1601
1602           rg.addRefEdge( hrnCalleeAndOutContext,
1603                          hrnCalleeAndInContext,
1604                          new RefEdge( hrnCalleeAndOutContext,
1605                                       hrnCalleeAndInContext,
1606                                       edgeMightCross.getType(),
1607                                       edgeMightCross.getField(),
1608                                       /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/,
1609                                       preds
1610                                       )
1611                          );
1612
1613         } else {
1614           // the out-of-context edge already exists
1615           oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
1616                                                     edgeMightCross.getBeta()
1617                                                     )
1618                                    );
1619
1620           oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1621                                                     edgeMightCross.getPreds()
1622                                                     )
1623                                     );
1624
1625         }
1626       }
1627     }
1628
1629     if( writeDebugDOTs ) {
1630       try {
1631         rg.writeGraph( "calleeview", true, false, false, false, true, true );
1632       } catch( IOException e ) {}
1633     }
1634
1635     return rg;
1636   }
1637
1638   private static Hashtable<String, Integer> oocid2hrnid =
1639     new Hashtable<String, Integer>();
1640
1641
1642
1643   public void
1644     resolveMethodCall( FlatCall     fc,
1645                        FlatMethod   fmCallee,
1646                        ReachGraph   rgCallee,
1647                        Set<Integer> callerNodeIDsCopiedToCallee,
1648                        boolean      writeDebugDOTs
1649                        ) {
1650
1651
1652     if( writeDebugDOTs ) {
1653       try {
1654         rgCallee.writeGraph( "callee",
1655                              true, false, false, false, true, true );
1656         writeGraph( "caller00In",
1657                     true, false, false, false, true, true,
1658                     callerNodeIDsCopiedToCallee );
1659       } catch( IOException e ) {}
1660     }
1661
1662
1663     // method call transfer function steps:
1664     // 1. Use current callee-reachable heap (CRH) to test callee
1665     //    predicates and mark what will be coming in.
1666     // 2. Wipe CRH out of caller.
1667     // 3. Transplant marked callee parts in:
1668     //    a) bring in nodes
1669     //    b) bring in callee -> callee edges
1670     //    c) resolve out-of-context -> callee edges
1671     //    d) assign return value
1672     // 4. Collapse shadow nodes down
1673     // 5. Global sweep it.
1674
1675
1676
1677     // 1. mark what callee elements have satisfied predicates
1678     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1679       new Hashtable<HeapRegionNode, ExistPredSet>();
1680
1681     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1682       new Hashtable<RefEdge, ExistPredSet>();
1683
1684     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1685       new Hashtable< RefEdge, Set<RefSrcNode> >();
1686
1687     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1688     while( meItr.hasNext() ) {
1689       Map.Entry      me        = (Map.Entry)      meItr.next();
1690       Integer        id        = (Integer)        me.getKey();
1691       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1692
1693       // if a callee element's predicates are satisfied then a set
1694       // of CALLER predicates is returned: they are the predicates
1695       // that the callee element moved into the caller context
1696       // should have, and it is inefficient to find this again later
1697       ExistPredSet predsIfSatis =
1698         hrnCallee.getPreds().isSatisfiedBy( this,
1699                                             callerNodeIDsCopiedToCallee
1700                                             );
1701       if( predsIfSatis != null ) {
1702         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1703       } else {
1704         // otherwise don't bother looking at edges to this node
1705         continue;
1706       }
1707
1708       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
1709       while( reItr.hasNext() ) {
1710         RefEdge    reCallee  = reItr.next();
1711         RefSrcNode rsnCallee = reCallee.getSrc();
1712
1713         // (caller local variables to in-context heap regions)
1714         // have an (out-of-context heap region -> in-context heap region)
1715         // abstraction in the callEE, so its true we never need to
1716         // look at a (var node -> heap region) edge in callee to bring
1717         // those over for the call site transfer.  What about (param var->heap region)
1718         // edges in callee? They are dealt with below this loop.
1719         // So, yes, at this point skip (var->region) edges in callee
1720         if( rsnCallee instanceof VariableNode ) {
1721           continue;
1722         }
1723
1724         // first see if the source is out-of-context, and only
1725         // proceed with this edge if we find some caller-context
1726         // matches
1727         HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
1728         boolean matchedOutOfContext = false;
1729
1730         if( hrnSrcCallee.isOutOfContext() ) {
1731
1732           assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
1733           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
1734
1735           HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
1736           Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
1737           while( reDstItr.hasNext() ) {
1738             // the edge and field (either possibly null) must match
1739             RefEdge reCaller = reDstItr.next();
1740
1741             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
1742                 !reCaller.fieldEquals( reCallee.getField() )
1743                 ) {
1744               continue;
1745             }
1746
1747             RefSrcNode rsnCaller = reCaller.getSrc();
1748             if( rsnCaller instanceof VariableNode ) {
1749               // a variable node matches an OOC region with null type
1750               if( hrnSrcCallee.getType() != null ) {
1751                 continue;
1752               }
1753
1754             } else {
1755               // otherwise types should match
1756               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
1757               if( hrnSrcCallee.getType() == null ) {
1758                 if( hrnCallerSrc.getType() != null ) {
1759                   continue;
1760                 }
1761               } else {
1762                 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
1763                   continue;
1764                 }
1765               }
1766             }
1767
1768             rsnCallers.add( rsnCaller );
1769             matchedOutOfContext = true;
1770           }
1771
1772           if( !rsnCallers.isEmpty() ) {
1773             calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
1774           }
1775         }
1776
1777         if( hrnSrcCallee.isOutOfContext() &&
1778             !matchedOutOfContext ) {
1779           continue;
1780         }
1781
1782         predsIfSatis =
1783           reCallee.getPreds().isSatisfiedBy( this,
1784                                              callerNodeIDsCopiedToCallee
1785                                              );
1786         if( predsIfSatis != null ) {
1787           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1788         }
1789
1790       }
1791     }
1792
1793     // test param -> HRN edges, also
1794     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1795
1796       // parameter defined here is the symbol in the callee
1797       TempDescriptor tdParam  = fmCallee.getParameter( i );
1798       VariableNode   vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
1799
1800       Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
1801       while( reItr.hasNext() ) {
1802         RefEdge reCallee = reItr.next();
1803
1804         ExistPredSet ifDst =
1805           reCallee.getDst().getPreds().isSatisfiedBy( this,
1806                                                       callerNodeIDsCopiedToCallee
1807                                                       );
1808         if( ifDst == null ) {
1809           continue;
1810         }
1811
1812         ExistPredSet predsIfSatis =
1813           reCallee.getPreds().isSatisfiedBy( this,
1814                                              callerNodeIDsCopiedToCallee
1815                                              );
1816         if( predsIfSatis != null ) {
1817           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1818         }
1819       }
1820     }
1821
1822
1823
1824
1825     if( writeDebugDOTs ) {
1826       try {
1827         writeGraph( "caller20BeforeWipe",
1828                     true, false, false, false, true, true );
1829       } catch( IOException e ) {}
1830     }
1831
1832
1833     // 2. predicates tested, ok to wipe out caller part
1834     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
1835     while( hrnItr.hasNext() ) {
1836       Integer        hrnID     = hrnItr.next();
1837       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
1838       assert hrnCaller != null;
1839
1840       // when clearing off nodes, also eliminate variable
1841       // references
1842       wipeOut( hrnCaller, true );
1843     }
1844
1845
1846
1847     if( writeDebugDOTs ) {
1848       try {
1849         writeGraph( "caller30BeforeAddingNodes",
1850                     true, false, false, false, true, true );
1851       } catch( IOException e ) {}
1852     }
1853
1854
1855     // 3. callee elements with satisfied preds come in, note that
1856     //    the mapping of elements satisfied to preds is like this:
1857     //    A callee element EE has preds EEp that are satisfied by
1858     //    some caller element ER.  We bring EE into the caller
1859     //    context as ERee with the preds of ER, namely ERp, which
1860     //    in the following algorithm is the value in the mapping
1861
1862     // 3.a) nodes
1863     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
1864     while( satisItr.hasNext() ) {
1865       Map.Entry      me        = (Map.Entry)      satisItr.next();
1866       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
1867       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
1868
1869       // TODO: I think its true that the current implementation uses
1870       // the type of the OOC region and the predicates OF THE EDGE from
1871       // it to link everything up in caller context, so that's why we're
1872       // skipping this... maybe that's a sillier way to do it?
1873       if( hrnCallee.isOutOfContext() ) {
1874         continue;
1875       }
1876
1877       AllocSite as = hrnCallee.getAllocSite();
1878       allocSites.add( as );
1879
1880       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
1881
1882       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
1883       if( hrnCaller == null ) {
1884         hrnCaller =
1885           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
1886                                    hrnCallee.isSingleObject(), // single object?
1887                                    hrnCallee.isNewSummary(),   // summary?
1888                                    hrnCallee.isFlagged(),      // flagged?
1889                                    false,                      // out-of-context?
1890                                    hrnCallee.getType(),        // type
1891                                    hrnCallee.getAllocSite(),   // allocation site
1892                                    hrnCallee.getInherent(),    // inherent reach
1893                                    null,                       // current reach
1894                                    predsEmpty,                 // predicates
1895                                    hrnCallee.getDescription()  // description
1896                                    );
1897       } else {
1898         assert hrnCaller.isWiped();
1899       }
1900
1901       // TODO: alpha should be some rewritten version of callee in caller context
1902       hrnCaller.setAlpha( hrnCallee.getAlpha() );
1903
1904       hrnCaller.setPreds( preds );
1905     }
1906
1907
1908
1909     if( writeDebugDOTs ) {
1910       try {
1911         writeGraph( "caller31BeforeAddingEdges",
1912                     true, false, false, false, true, true );
1913       } catch( IOException e ) {}
1914     }
1915
1916
1917     // 3.b) callee -> callee edges AND out-of-context -> callee
1918     satisItr = calleeEdgesSatisfied.entrySet().iterator();
1919     while( satisItr.hasNext() ) {
1920       Map.Entry    me       = (Map.Entry)    satisItr.next();
1921       RefEdge      reCallee = (RefEdge)      me.getKey();
1922       ExistPredSet preds    = (ExistPredSet) me.getValue();
1923
1924       HeapRegionNode hrnDstCallee = reCallee.getDst();
1925       AllocSite      asDst        = hrnDstCallee.getAllocSite();
1926       allocSites.add( asDst );
1927
1928       Integer hrnIDDstShadow =
1929         asDst.getShadowIDfromID( hrnDstCallee.getID() );
1930
1931       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
1932       assert hrnDstCaller != null;
1933
1934
1935       RefSrcNode rsnCallee = reCallee.getSrc();
1936
1937       Set<RefSrcNode> rsnCallers =
1938         new HashSet<RefSrcNode>();
1939
1940       Set<RefSrcNode> oocCallers =
1941         calleeEdges2oocCallerSrcMatches.get( reCallee );
1942
1943       if( oocCallers == null ) {
1944         // there are no out-of-context matches, so it's
1945         // either a param/arg var or one in-context heap region
1946         if( rsnCallee instanceof VariableNode ) {
1947           // variable -> node in the callee should only
1948           // come into the caller if its from a param var
1949           VariableNode   vnCallee = (VariableNode) rsnCallee;
1950           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
1951           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
1952                                                             tdParam );
1953           if( tdArg == null ) {
1954             // this means the variable isn't a parameter, its local
1955             // to the callee so we ignore it in call site transfer
1956             // shouldn't this NEVER HAPPEN?
1957             assert false;
1958             //continue;
1959           }
1960           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
1961
1962         } else {
1963           // otherwise source is in context, one region
1964           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
1965
1966           // translate an in-context node to shadow
1967           AllocSite asSrc = hrnSrcCallee.getAllocSite();
1968           allocSites.add( asSrc );
1969
1970           Integer hrnIDSrcShadow =
1971             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
1972
1973           HeapRegionNode hrnSrcCallerShadow =
1974             this.id2hrn.get( hrnIDSrcShadow );
1975
1976           if( hrnSrcCallerShadow == null ) {
1977             hrnSrcCallerShadow =
1978               createNewHeapRegionNode( hrnIDSrcShadow,                // id or null to generate a new one
1979                                        hrnSrcCallee.isSingleObject(), // single object?
1980                                        hrnSrcCallee.isNewSummary(),   // summary?
1981                                        hrnSrcCallee.isFlagged(),      // flagged?
1982                                        false,                         // out-of-context?
1983                                        hrnSrcCallee.getType(),        // type
1984                                        hrnSrcCallee.getAllocSite(),   // allocation site
1985                                        hrnSrcCallee.getInherent(),    // inherent reach
1986                                        hrnSrcCallee.getAlpha(),       // current reach
1987                                        predsEmpty,                    // predicates
1988                                        hrnSrcCallee.getDescription()  // description
1989                                        );
1990           }
1991
1992           rsnCallers.add( hrnSrcCallerShadow );
1993         }
1994
1995       } else {
1996         // otherwise we have a set of out-of-context srcs
1997         // that should NOT be translated to shadow nodes
1998         assert !oocCallers.isEmpty();
1999         rsnCallers.addAll( oocCallers );
2000       }
2001
2002       // now make all caller edges we've identified from
2003       // this callee edge with a satisfied predicate
2004       assert !rsnCallers.isEmpty();
2005       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2006       while( rsnItr.hasNext() ) {
2007         RefSrcNode rsnCaller = rsnItr.next();
2008
2009         // TODO: beta rewrites
2010         RefEdge reCaller = new RefEdge( rsnCaller,
2011                                         hrnDstCaller,
2012                                         reCallee.getType(),
2013                                         reCallee.getField(),
2014                                         reCallee.getBeta(),
2015                                         preds
2016                                         );
2017
2018         // look to see if an edge with same field exists
2019         // and merge with it, otherwise just add the edge
2020         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2021                                                          reCallee.getType(),
2022                                                          reCallee.getField()
2023                                                          );
2024         if( edgeExisting != null ) {
2025           edgeExisting.setBeta(
2026                                Canonical.union( edgeExisting.getBeta(),
2027                                                 reCaller.getBeta()
2028                                                 )
2029                                );
2030           edgeExisting.setPreds(
2031                                 Canonical.join( edgeExisting.getPreds(),
2032                                                 reCaller.getPreds()
2033                                                 )
2034                                 );
2035
2036         } else {
2037           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2038         }
2039       }
2040     }
2041
2042
2043
2044
2045
2046     if( writeDebugDOTs ) {
2047       try {
2048         writeGraph( "caller35BeforeAssignReturnValue",
2049                     true, false, false, false, true, true );
2050       } catch( IOException e ) {}
2051     }
2052
2053
2054
2055     // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2056     // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2057     // EDGES, JUST BRINGING THEM ALL!  It'll work for now, over approximation
2058
2059     // 3.d) handle return value assignment if needed
2060     TempDescriptor returnTemp = fc.getReturnTemp();
2061     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2062
2063       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2064       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2065
2066       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2067       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2068       while( reCalleeItr.hasNext() ) {
2069         RefEdge        reCallee     = reCalleeItr.next();
2070         HeapRegionNode hrnDstCallee = reCallee.getDst();
2071
2072         // some edge types are not possible return values when we can
2073         // see what type variable we are assigning it to
2074         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2075           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2076                               reCallee+" for return temp "+returnTemp );
2077           // prune
2078           continue;
2079         }
2080
2081         AllocSite asDst = hrnDstCallee.getAllocSite();
2082         allocSites.add( asDst );
2083
2084         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2085
2086         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2087         if( hrnDstCaller == null ) {
2088           hrnDstCaller =
2089             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
2090                                      hrnDstCallee.isSingleObject(), // single object?
2091                                      hrnDstCallee.isNewSummary(),   // summary?
2092                                      hrnDstCallee.isFlagged(),      // flagged?
2093                                      false,                         // out-of-context?
2094                                      hrnDstCallee.getType(),        // type
2095                                      hrnDstCallee.getAllocSite(),   // allocation site
2096                                      hrnDstCallee.getInherent(),    // inherent reach
2097                                      hrnDstCallee.getAlpha(),       // current reach
2098                                      predsTrue,                     // predicates
2099                                      hrnDstCallee.getDescription()  // description
2100                                      );
2101         } else {
2102           assert hrnDstCaller.isWiped();
2103         }
2104
2105         TypeDescriptor tdNewEdge =
2106           mostSpecificType( reCallee.getType(),
2107                             hrnDstCallee.getType(),
2108                             hrnDstCaller.getType()
2109                             );
2110
2111         RefEdge reCaller = new RefEdge( vnLhsCaller,
2112                                         hrnDstCaller,
2113                                         tdNewEdge,
2114                                         null,
2115                                         reCallee.getBeta(),
2116                                         predsTrue
2117                                         );
2118
2119         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2120       }
2121     }
2122
2123
2124
2125     if( writeDebugDOTs ) {
2126       try {
2127         writeGraph( "caller40BeforeShadowMerge",
2128                     true, false, false, false, true, true );
2129       } catch( IOException e ) {}
2130     }
2131
2132
2133     // 4) merge shadow nodes so alloc sites are back to k
2134     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2135     while( asItr.hasNext() ) {
2136       // for each allocation site do the following to merge
2137       // shadow nodes (newest from callee) with any existing
2138       // look for the newest normal and newest shadow "slot"
2139       // not being used, transfer normal to shadow.  Keep
2140       // doing this until there are no more normal nodes, or
2141       // no empty shadow slots: then merge all remaining normal
2142       // nodes into the shadow summary.  Finally, convert all
2143       // shadow to their normal versions.
2144       AllocSite as = asItr.next();
2145       int ageNorm = 0;
2146       int ageShad = 0;
2147       while( ageNorm < allocationDepth &&
2148              ageShad < allocationDepth ) {
2149
2150         // first, are there any normal nodes left?
2151         Integer        idNorm  = as.getIthOldest( ageNorm );
2152         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2153         if( hrnNorm == null ) {
2154           // no, this age of normal node not in the caller graph
2155           ageNorm++;
2156           continue;
2157         }
2158
2159         // yes, a normal node exists, is there an empty shadow
2160         // "slot" to transfer it onto?
2161         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2162         if( !hrnShad.isWiped() ) {
2163           // no, this age of shadow node is not empty
2164           ageShad++;
2165           continue;
2166         }
2167
2168         // yes, this shadow node is empty
2169         transferOnto( hrnNorm, hrnShad );
2170         ageNorm++;
2171         ageShad++;
2172       }
2173
2174       // now, while there are still normal nodes but no shadow
2175       // slots, merge normal nodes into the shadow summary
2176       while( ageNorm < allocationDepth ) {
2177
2178         // first, are there any normal nodes left?
2179         Integer        idNorm  = as.getIthOldest( ageNorm );
2180         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2181         if( hrnNorm == null ) {
2182           // no, this age of normal node not in the caller graph
2183           ageNorm++;
2184           continue;
2185         }
2186
2187         // yes, a normal node exists, so get the shadow summary
2188         HeapRegionNode summShad = getSummaryNode( as, true );
2189         mergeIntoSummary( hrnNorm, summShad );
2190         ageNorm++;
2191       }
2192
2193       // if there is a normal summary, merge it into shadow summary
2194       Integer        idNorm   = as.getSummary();
2195       HeapRegionNode summNorm = id2hrn.get( idNorm );
2196       if( summNorm != null ) {
2197         HeapRegionNode summShad = getSummaryNode( as, true );
2198         mergeIntoSummary( summNorm, summShad );
2199       }
2200
2201       // finally, flip all existing shadow nodes onto the normal
2202       for( int i = 0; i < allocationDepth; ++i ) {
2203         Integer        idShad  = as.getIthOldestShadow( i );
2204         HeapRegionNode hrnShad = id2hrn.get( idShad );
2205         if( hrnShad != null ) {
2206           // flip it
2207           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2208           assert hrnNorm.isWiped();
2209           transferOnto( hrnShad, hrnNorm );
2210         }
2211       }
2212
2213       Integer        idShad   = as.getSummaryShadow();
2214       HeapRegionNode summShad = id2hrn.get( idShad );
2215       if( summShad != null ) {
2216         summNorm = getSummaryNode( as, false );
2217         transferOnto( summShad, summNorm );
2218       }
2219     }
2220
2221
2222     if( writeDebugDOTs ) {
2223       try {
2224         writeGraph( "caller50BeforeGlobalSweep",
2225                     true, false, false, false, true, true );
2226       } catch( IOException e ) {}
2227     }
2228
2229
2230     // 5.
2231     globalSweep();
2232
2233
2234
2235     if( writeDebugDOTs ) {
2236       try {
2237         writeGraph( "caller90AfterTransfer",
2238                     true, false, false, false, true, true );
2239       } catch( IOException e ) {}
2240     }
2241   }
2242
2243
2244
2245   ////////////////////////////////////////////////////
2246   //
2247   //  Abstract garbage collection simply removes
2248   //  heap region nodes that are not mechanically
2249   //  reachable from a root set.  This step is
2250   //  essential for testing node and edge existence
2251   //  predicates efficiently
2252   //
2253   ////////////////////////////////////////////////////
2254   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2255
2256     // calculate a root set, will be different for Java
2257     // version of analysis versus Bamboo version
2258     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2259
2260     // visit every variable in graph while building root
2261     // set, and do iterating on a copy, so we can remove
2262     // dead variables while we're at this
2263     Iterator makeCopyItr = td2vn.entrySet().iterator();
2264     Set      entrysCopy  = new HashSet();
2265     while( makeCopyItr.hasNext() ) {
2266       entrysCopy.add( makeCopyItr.next() );
2267     }
2268
2269     Iterator eItr = entrysCopy.iterator();
2270     while( eItr.hasNext() ) {
2271       Map.Entry      me = (Map.Entry)      eItr.next();
2272       TempDescriptor td = (TempDescriptor) me.getKey();
2273       VariableNode   vn = (VariableNode)   me.getValue();
2274
2275       if( liveSet.contains( td ) ) {
2276         toVisit.add( vn );
2277
2278       } else {
2279         // dead var, remove completely from graph
2280         td2vn.remove( td );
2281         clearRefEdgesFrom( vn, null, null, true );
2282       }
2283     }
2284
2285     // everything visited in a traversal is
2286     // considered abstractly live
2287     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2288
2289     while( !toVisit.isEmpty() ) {
2290       RefSrcNode rsn = toVisit.iterator().next();
2291       toVisit.remove( rsn );
2292       visited.add( rsn );
2293
2294       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2295       while( hrnItr.hasNext() ) {
2296         RefEdge        edge = hrnItr.next();
2297         HeapRegionNode hrn  = edge.getDst();
2298
2299         if( !visited.contains( hrn ) ) {
2300           toVisit.add( hrn );
2301         }
2302       }
2303     }
2304
2305     // get a copy of the set to iterate over because
2306     // we're going to monkey with the graph when we
2307     // identify a garbage node
2308     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2309     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2310     while( hrnItr.hasNext() ) {
2311       hrnAllPrior.add( hrnItr.next() );
2312     }
2313
2314     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2315     while( hrnAllItr.hasNext() ) {
2316       HeapRegionNode hrn = hrnAllItr.next();
2317
2318       if( !visited.contains( hrn ) ) {
2319
2320         // heap region nodes are compared across ReachGraph
2321         // objects by their integer ID, so when discarding
2322         // garbage nodes we must also discard entries in
2323         // the ID -> heap region hashtable.
2324         id2hrn.remove( hrn.getID() );
2325
2326         // RefEdge objects are two-way linked between
2327         // nodes, so when a node is identified as garbage,
2328         // actively clear references to and from it so
2329         // live nodes won't have dangling RefEdge's
2330         wipeOut( hrn, true );
2331
2332         // if we just removed the last node from an allocation
2333         // site, it should be taken out of the ReachGraph's list
2334         AllocSite as = hrn.getAllocSite();
2335         if( !hasNodesOf( as ) ) {
2336           allocSites.remove( as );
2337         }
2338       }
2339     }
2340   }
2341
2342   protected boolean hasNodesOf( AllocSite as ) {
2343     if( id2hrn.containsKey( as.getSummary() ) ) {
2344       return true;
2345     }
2346
2347     for( int i = 0; i < allocationDepth; ++i ) {
2348       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2349         return true;
2350       }
2351     }
2352     return false;
2353   }
2354
2355
2356   ////////////////////////////////////////////////////
2357   //
2358   //  This global sweep is an optional step to prune
2359   //  reachability sets that are not internally
2360   //  consistent with the global graph.  It should be
2361   //  invoked after strong updates or method calls.
2362   //
2363   ////////////////////////////////////////////////////
2364   public void globalSweep() {
2365
2366     // boldB is part of the phase 1 sweep
2367     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
2368       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2369
2370     // visit every heap region to initialize alphaNew and calculate boldB
2371     Iterator itrHrns = id2hrn.entrySet().iterator();
2372     while( itrHrns.hasNext() ) {
2373       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2374       Integer        hrnID = (Integer)        me.getKey();
2375       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2376
2377       // assert that this node and incoming edges have clean alphaNew
2378       // and betaNew sets, respectively
2379       assert rsetEmpty.equals( hrn.getAlphaNew() );
2380
2381       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2382       while( itrRers.hasNext() ) {
2383         RefEdge edge = itrRers.next();
2384         assert rsetEmpty.equals( edge.getBetaNew() );
2385       }
2386
2387       // calculate boldB for this flagged node
2388       if( hrn.isFlagged() ) {
2389
2390         Hashtable<RefEdge, ReachSet> boldB_f =
2391           new Hashtable<RefEdge, ReachSet>();
2392
2393         Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2394
2395         // initial boldB_f constraints
2396         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2397         while( itrRees.hasNext() ) {
2398           RefEdge edge = itrRees.next();
2399
2400           assert !boldB.containsKey( edge );
2401           boldB_f.put( edge, edge.getBeta() );
2402
2403           assert !workSetEdges.contains( edge );
2404           workSetEdges.add( edge );
2405         }
2406
2407         // enforce the boldB_f constraint at edges until we reach a fixed point
2408         while( !workSetEdges.isEmpty() ) {
2409           RefEdge edge = workSetEdges.iterator().next();
2410           workSetEdges.remove( edge );
2411
2412           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2413           while( itrPrime.hasNext() ) {
2414             RefEdge edgePrime = itrPrime.next();
2415
2416             ReachSet prevResult   = boldB_f.get( edgePrime );
2417             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2418                                                             edgePrime.getBeta()
2419                                                             );
2420
2421             if( prevResult == null ||
2422                 Canonical.union( prevResult,
2423                                  intersection ).size() > prevResult.size() ) {
2424
2425               if( prevResult == null ) {
2426                 boldB_f.put( edgePrime,
2427                              Canonical.union( edgePrime.getBeta(),
2428                                               intersection
2429                                               )
2430                              );
2431               } else {
2432                 boldB_f.put( edgePrime,
2433                              Canonical.union( prevResult,
2434                                               intersection
2435                                               )
2436                              );
2437               }
2438               workSetEdges.add( edgePrime );
2439             }
2440           }
2441         }
2442
2443         boldB.put( hrnID, boldB_f );
2444       }
2445     }
2446
2447
2448     // use boldB to prune hrnIDs from alpha states that are impossible
2449     // and propagate the differences backwards across edges
2450     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2451
2452     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2453       new Hashtable<RefEdge, ChangeSet>();
2454
2455
2456     itrHrns = id2hrn.entrySet().iterator();
2457     while( itrHrns.hasNext() ) {
2458       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2459       Integer        hrnID = (Integer)        me.getKey();
2460       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2461
2462       // create the inherent hrnID from a flagged region
2463       // as an exception to removal below
2464       ReachTuple rtException =
2465         ReachTuple.factory( hrnID,
2466                             !hrn.isSingleObject(),
2467                             ReachTuple.ARITY_ONE
2468                             );
2469
2470       ChangeSet cts = ChangeSet.factory();
2471
2472       // mark hrnIDs for removal
2473       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2474       while( stateItr.hasNext() ) {
2475         ReachState stateOld = stateItr.next();
2476
2477         ReachState markedHrnIDs = ReachState.factory();
2478
2479         Iterator<ReachTuple> rtItr = stateOld.iterator();
2480         while( rtItr.hasNext() ) {
2481           ReachTuple rtOld = rtItr.next();
2482
2483           // never remove the inherent hrnID from a flagged region
2484           // because it is trivially satisfied
2485           if( hrn.isFlagged() ) {
2486             if( rtOld == rtException ) {
2487               continue;
2488             }
2489           }
2490
2491           // does boldB_ttOld allow this hrnID?
2492           boolean foundState = false;
2493           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2494           while( incidentEdgeItr.hasNext() ) {
2495             RefEdge incidentEdge = incidentEdgeItr.next();
2496
2497             // if it isn't allowed, mark for removal
2498             Integer idOld = rtOld.getHrnID();
2499             assert id2hrn.containsKey( idOld );
2500             Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
2501             ReachSet boldB_ttOld_incident = B.get( incidentEdge );
2502             if( boldB_ttOld_incident != null &&
2503                 boldB_ttOld_incident.contains( stateOld ) ) {
2504               foundState = true;
2505             }
2506           }
2507
2508           if( !foundState ) {
2509             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
2510           }
2511         }
2512
2513         // if there is nothing marked, just move on
2514         if( markedHrnIDs.isEmpty() ) {
2515           hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2516                                             stateOld
2517                                             )
2518                            );
2519           continue;
2520         }
2521
2522         // remove all marked hrnIDs and establish a change set that should
2523         // propagate backwards over edges from this node
2524         ReachState statePruned = ReachState.factory();
2525         rtItr = stateOld.iterator();
2526         while( rtItr.hasNext() ) {
2527           ReachTuple rtOld = rtItr.next();
2528
2529           if( !markedHrnIDs.containsTuple( rtOld ) ) {
2530             statePruned = Canonical.union( statePruned, rtOld );
2531           }
2532         }
2533         assert !stateOld.equals( statePruned );
2534
2535         hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2536                                           statePruned
2537                                           )
2538                          );
2539         ChangeTuple ct = ChangeTuple.factory( stateOld,
2540                                               statePruned
2541                                               );
2542         cts = Canonical.union( cts, ct );
2543       }
2544
2545       // throw change tuple set on all incident edges
2546       if( !cts.isEmpty() ) {
2547         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2548         while( incidentEdgeItr.hasNext() ) {
2549           RefEdge incidentEdge = incidentEdgeItr.next();
2550
2551           edgesForPropagation.add( incidentEdge );
2552
2553           if( edgePlannedChanges.get( incidentEdge ) == null ) {
2554             edgePlannedChanges.put( incidentEdge, cts );
2555           } else {
2556             edgePlannedChanges.put(
2557                                    incidentEdge,
2558                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
2559                                                     cts
2560                                                     )
2561                                     );
2562           }
2563         }
2564       }
2565     }
2566
2567     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2568
2569     propagateTokensOverEdges( edgesForPropagation,
2570                               edgePlannedChanges,
2571                               edgesUpdated );
2572
2573     // at the end of the 1st phase reference edges have
2574     // beta, betaNew that correspond to beta and betaR
2575     //
2576     // commit beta<-betaNew, so beta=betaR and betaNew
2577     // will represent the beta' calculation in 2nd phase
2578     //
2579     // commit alpha<-alphaNew because it won't change
2580     HashSet<RefEdge> res = new HashSet<RefEdge>();
2581
2582     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2583     while( nodeItr.hasNext() ) {
2584       HeapRegionNode hrn = nodeItr.next();
2585       hrn.applyAlphaNew();
2586       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2587       while( itrRes.hasNext() ) {
2588         res.add( itrRes.next() );
2589       }
2590     }
2591
2592
2593     // 2nd phase
2594     Iterator<RefEdge> edgeItr = res.iterator();
2595     while( edgeItr.hasNext() ) {
2596       RefEdge        edge = edgeItr.next();
2597       HeapRegionNode hrn  = edge.getDst();
2598
2599       // commit results of last phase
2600       if( edgesUpdated.contains( edge ) ) {
2601         edge.applyBetaNew();
2602       }
2603
2604       // compute intial condition of 2nd phase
2605       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
2606                                                hrn.getAlpha()
2607                                                )
2608                        );
2609     }
2610
2611     // every edge in the graph is the initial workset
2612     Set<RefEdge> edgeWorkSet = (Set) res.clone();
2613     while( !edgeWorkSet.isEmpty() ) {
2614       RefEdge edgePrime = edgeWorkSet.iterator().next();
2615       edgeWorkSet.remove( edgePrime );
2616
2617       RefSrcNode rsn = edgePrime.getSrc();
2618       if( !(rsn instanceof HeapRegionNode) ) {
2619         continue;
2620       }
2621       HeapRegionNode hrn = (HeapRegionNode) rsn;
2622
2623       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2624       while( itrEdge.hasNext() ) {
2625         RefEdge edge = itrEdge.next();
2626
2627         ReachSet prevResult = edge.getBetaNew();
2628         assert prevResult != null;
2629
2630         ReachSet intersection =
2631           Canonical.intersection( edge.getBeta(),
2632                                   edgePrime.getBetaNew()
2633                                   );
2634
2635         if( Canonical.union( prevResult,
2636                              intersection
2637                              ).size() > prevResult.size() ) {
2638           edge.setBetaNew(
2639                           Canonical.union( prevResult,
2640                                            intersection
2641                                            )
2642                            );
2643           edgeWorkSet.add( edge );
2644         }
2645       }
2646     }
2647
2648     // commit beta' (beta<-betaNew)
2649     edgeItr = res.iterator();
2650     while( edgeItr.hasNext() ) {
2651       edgeItr.next().applyBetaNew();
2652     }
2653   }
2654
2655
2656
2657   ////////////////////////////////////////////////////
2658   // high-level merge operations
2659   ////////////////////////////////////////////////////
2660   public void merge_sameMethodContext( ReachGraph rg ) {
2661     // when merging two graphs that abstract the heap
2662     // of the same method context, we just call the
2663     // basic merge operation
2664     merge( rg );
2665   }
2666
2667   public void merge_diffMethodContext( ReachGraph rg ) {
2668     // when merging graphs for abstract heaps in
2669     // different method contexts we should:
2670     // 1) age the allocation sites?
2671     merge( rg );
2672   }
2673
2674   ////////////////////////////////////////////////////
2675   // in merge() and equals() methods the suffix A
2676   // represents the passed in graph and the suffix
2677   // B refers to the graph in this object
2678   // Merging means to take the incoming graph A and
2679   // merge it into B, so after the operation graph B
2680   // is the final result.
2681   ////////////////////////////////////////////////////
2682   protected void merge( ReachGraph rg ) {
2683
2684     if( rg == null ) {
2685       return;
2686     }
2687
2688     mergeNodes     ( rg );
2689     mergeRefEdges  ( rg );
2690     mergeAllocSites( rg );
2691   }
2692
2693   protected void mergeNodes( ReachGraph rg ) {
2694
2695     // start with heap region nodes
2696     Set      sA = rg.id2hrn.entrySet();
2697     Iterator iA = sA.iterator();
2698     while( iA.hasNext() ) {
2699       Map.Entry      meA  = (Map.Entry)      iA.next();
2700       Integer        idA  = (Integer)        meA.getKey();
2701       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2702
2703       // if this graph doesn't have a node the
2704       // incoming graph has, allocate it
2705       if( !id2hrn.containsKey( idA ) ) {
2706         HeapRegionNode hrnB = hrnA.copy();
2707         id2hrn.put( idA, hrnB );
2708
2709       } else {
2710         // otherwise this is a node present in both graphs
2711         // so make the new reachability set a union of the
2712         // nodes' reachability sets
2713         HeapRegionNode hrnB = id2hrn.get( idA );
2714         hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
2715                                         hrnA.getAlpha()
2716                                         )
2717                        );
2718
2719         // if hrnB is already dirty or hrnA is dirty,
2720         // the hrnB should end up dirty: TODO
2721         /*
2722         if( !hrnA.isClean() ) {
2723           hrnB.setIsClean( false );
2724         }
2725         */
2726       }
2727     }
2728
2729     // now add any variable nodes that are in graph B but
2730     // not in A
2731     sA = rg.td2vn.entrySet();
2732     iA = sA.iterator();
2733     while( iA.hasNext() ) {
2734       Map.Entry      meA = (Map.Entry)      iA.next();
2735       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2736       VariableNode   lnA = (VariableNode)   meA.getValue();
2737
2738       // if the variable doesn't exist in B, allocate and add it
2739       VariableNode lnB = getVariableNodeFromTemp( tdA );
2740     }
2741   }
2742
2743   protected void mergeRefEdges( ReachGraph rg ) {
2744
2745     // between heap regions
2746     Set      sA = rg.id2hrn.entrySet();
2747     Iterator iA = sA.iterator();
2748     while( iA.hasNext() ) {
2749       Map.Entry      meA  = (Map.Entry)      iA.next();
2750       Integer        idA  = (Integer)        meA.getKey();
2751       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2752
2753       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2754       while( heapRegionsItrA.hasNext() ) {
2755         RefEdge        edgeA     = heapRegionsItrA.next();
2756         HeapRegionNode hrnChildA = edgeA.getDst();
2757         Integer        idChildA  = hrnChildA.getID();
2758
2759         // at this point we know an edge in graph A exists
2760         // idA -> idChildA, does this exist in B?
2761         assert id2hrn.containsKey( idA );
2762         HeapRegionNode hrnB        = id2hrn.get( idA );
2763         RefEdge        edgeToMerge = null;
2764
2765         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2766         while( heapRegionsItrB.hasNext() &&
2767                edgeToMerge == null          ) {
2768
2769           RefEdge        edgeB     = heapRegionsItrB.next();
2770           HeapRegionNode hrnChildB = edgeB.getDst();
2771           Integer        idChildB  = hrnChildB.getID();
2772
2773           // don't use the RefEdge.equals() here because
2774           // we're talking about existence between graphs,
2775           // not intragraph equal
2776           if( idChildB.equals( idChildA ) &&
2777               edgeB.typeAndFieldEquals( edgeA ) ) {
2778
2779             edgeToMerge = edgeB;
2780           }
2781         }
2782
2783         // if the edge from A was not found in B,
2784         // add it to B.
2785         if( edgeToMerge == null ) {
2786           assert id2hrn.containsKey( idChildA );
2787           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2788           edgeToMerge = edgeA.copy();
2789           edgeToMerge.setSrc( hrnB );
2790           edgeToMerge.setDst( hrnChildB );
2791           addRefEdge( hrnB, hrnChildB, edgeToMerge );
2792         }
2793         // otherwise, the edge already existed in both graphs
2794         // so merge their reachability sets
2795         else {
2796           // just replace this beta set with the union
2797           assert edgeToMerge != null;
2798           edgeToMerge.setBeta(
2799                               Canonical.union( edgeToMerge.getBeta(),
2800                                                edgeA.getBeta()
2801                                                )
2802                               );
2803           // TODO: what?
2804           /*
2805           if( !edgeA.isClean() ) {
2806             edgeToMerge.setIsClean( false );
2807           }
2808           */
2809         }
2810       }
2811     }
2812
2813     // and then again from variable nodes
2814     sA = rg.td2vn.entrySet();
2815     iA = sA.iterator();
2816     while( iA.hasNext() ) {
2817       Map.Entry      meA = (Map.Entry)      iA.next();
2818       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2819       VariableNode   vnA = (VariableNode)   meA.getValue();
2820
2821       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
2822       while( heapRegionsItrA.hasNext() ) {
2823         RefEdge        edgeA     = heapRegionsItrA.next();
2824         HeapRegionNode hrnChildA = edgeA.getDst();
2825         Integer        idChildA  = hrnChildA.getID();
2826
2827         // at this point we know an edge in graph A exists
2828         // tdA -> idChildA, does this exist in B?
2829         assert td2vn.containsKey( tdA );
2830         VariableNode vnB         = td2vn.get( tdA );
2831         RefEdge      edgeToMerge = null;
2832
2833         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
2834         while( heapRegionsItrB.hasNext() &&
2835                edgeToMerge == null          ) {
2836
2837           RefEdge        edgeB     = heapRegionsItrB.next();
2838           HeapRegionNode hrnChildB = edgeB.getDst();
2839           Integer        idChildB  = hrnChildB.getID();
2840
2841           // don't use the RefEdge.equals() here because
2842           // we're talking about existence between graphs
2843           if( idChildB.equals( idChildA ) &&
2844               edgeB.typeAndFieldEquals( edgeA ) ) {
2845
2846             edgeToMerge = edgeB;
2847           }
2848         }
2849
2850         // if the edge from A was not found in B,
2851         // add it to B.
2852         if( edgeToMerge == null ) {
2853           assert id2hrn.containsKey( idChildA );
2854           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2855           edgeToMerge = edgeA.copy();
2856           edgeToMerge.setSrc( vnB );
2857           edgeToMerge.setDst( hrnChildB );
2858           addRefEdge( vnB, hrnChildB, edgeToMerge );
2859         }
2860         // otherwise, the edge already existed in both graphs
2861         // so merge their reachability sets
2862         else {
2863           // just replace this beta set with the union
2864           edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
2865                                                 edgeA.getBeta()
2866                                                 )
2867                                );
2868           // TODO: what?
2869           /*
2870           if( !edgeA.isClean() ) {
2871             edgeToMerge.setIsClean( false );
2872           }
2873           */
2874         }
2875       }
2876     }
2877   }
2878
2879   protected void mergeAllocSites( ReachGraph rg ) {
2880     allocSites.addAll( rg.allocSites );
2881   }
2882
2883
2884   // it is necessary in the equals() member functions
2885   // to "check both ways" when comparing the data
2886   // structures of two graphs.  For instance, if all
2887   // edges between heap region nodes in graph A are
2888   // present and equal in graph B it is not sufficient
2889   // to say the graphs are equal.  Consider that there
2890   // may be edges in graph B that are not in graph A.
2891   // the only way to know that all edges in both graphs
2892   // are equally present is to iterate over both data
2893   // structures and compare against the other graph.
2894   public boolean equals( ReachGraph rg ) {
2895
2896     if( rg == null ) {
2897       return false;
2898     }
2899
2900     if( !areHeapRegionNodesEqual( rg ) ) {
2901       return false;
2902     }
2903
2904     if( !areVariableNodesEqual( rg ) ) {
2905       return false;
2906     }
2907
2908     if( !areRefEdgesEqual( rg ) ) {
2909       return false;
2910     }
2911
2912     // if everything is equal up to this point,
2913     // assert that allocSites is also equal--
2914     // this data is redundant but kept for efficiency
2915     assert allocSites.equals( rg.allocSites );
2916
2917     return true;
2918   }
2919
2920
2921   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
2922
2923     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
2924       return false;
2925     }
2926
2927     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
2928       return false;
2929     }
2930
2931     return true;
2932   }
2933
2934   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
2935                                                         ReachGraph rgB ) {
2936     Set      sA = rgA.id2hrn.entrySet();
2937     Iterator iA = sA.iterator();
2938     while( iA.hasNext() ) {
2939       Map.Entry      meA  = (Map.Entry)      iA.next();
2940       Integer        idA  = (Integer)        meA.getKey();
2941       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2942
2943       if( !rgB.id2hrn.containsKey( idA ) ) {
2944         return false;
2945       }
2946
2947       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2948       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
2949         return false;
2950       }
2951     }
2952
2953     return true;
2954   }
2955
2956
2957   protected boolean areVariableNodesEqual( ReachGraph rg ) {
2958
2959     if( !areallVNinAalsoinBandequal( this, rg ) ) {
2960       return false;
2961     }
2962
2963     if( !areallVNinAalsoinBandequal( rg, this ) ) {
2964       return false;
2965     }
2966
2967     return true;
2968   }
2969
2970   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2971                                                        ReachGraph rgB ) {
2972     Set      sA = rgA.td2vn.entrySet();
2973     Iterator iA = sA.iterator();
2974     while( iA.hasNext() ) {
2975       Map.Entry      meA = (Map.Entry)      iA.next();
2976       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2977
2978       if( !rgB.td2vn.containsKey( tdA ) ) {
2979         return false;
2980       }
2981     }
2982
2983     return true;
2984   }
2985
2986
2987   protected boolean areRefEdgesEqual( ReachGraph rg ) {
2988     if( !areallREinAandBequal( this, rg ) ) {
2989       return false;
2990     }
2991
2992     return true;
2993   }
2994
2995   static protected boolean areallREinAandBequal( ReachGraph rgA,
2996                                                  ReachGraph rgB ) {
2997
2998     // check all the heap region->heap region edges
2999     Set      sA = rgA.id2hrn.entrySet();
3000     Iterator iA = sA.iterator();
3001     while( iA.hasNext() ) {
3002       Map.Entry      meA  = (Map.Entry)      iA.next();
3003       Integer        idA  = (Integer)        meA.getKey();
3004       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3005
3006       // we should have already checked that the same
3007       // heap regions exist in both graphs
3008       assert rgB.id2hrn.containsKey( idA );
3009
3010       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3011         return false;
3012       }
3013
3014       // then check every edge in B for presence in A, starting
3015       // from the same parent HeapRegionNode
3016       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3017
3018       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3019         return false;
3020       }
3021     }
3022
3023     // then check all the variable->heap region edges
3024     sA = rgA.td2vn.entrySet();
3025     iA = sA.iterator();
3026     while( iA.hasNext() ) {
3027       Map.Entry      meA = (Map.Entry)      iA.next();
3028       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3029       VariableNode   vnA = (VariableNode)   meA.getValue();
3030
3031       // we should have already checked that the same
3032       // label nodes exist in both graphs
3033       assert rgB.td2vn.containsKey( tdA );
3034
3035       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3036         return false;
3037       }
3038
3039       // then check every edge in B for presence in A, starting
3040       // from the same parent VariableNode
3041       VariableNode vnB = rgB.td2vn.get( tdA );
3042
3043       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3044         return false;
3045       }
3046     }
3047
3048     return true;
3049   }
3050
3051
3052   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3053                                                   RefSrcNode rnA,
3054                                                   ReachGraph rgB ) {
3055
3056     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3057     while( itrA.hasNext() ) {
3058       RefEdge        edgeA     = itrA.next();
3059       HeapRegionNode hrnChildA = edgeA.getDst();
3060       Integer        idChildA  = hrnChildA.getID();
3061
3062       assert rgB.id2hrn.containsKey( idChildA );
3063
3064       // at this point we know an edge in graph A exists
3065       // rnA -> idChildA, does this exact edge exist in B?
3066       boolean edgeFound = false;
3067
3068       RefSrcNode rnB = null;
3069       if( rnA instanceof HeapRegionNode ) {
3070         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3071         rnB = rgB.id2hrn.get( hrnA.getID() );
3072       } else {
3073         VariableNode vnA = (VariableNode) rnA;
3074         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3075       }
3076
3077       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3078       while( itrB.hasNext() ) {
3079         RefEdge        edgeB     = itrB.next();
3080         HeapRegionNode hrnChildB = edgeB.getDst();
3081         Integer        idChildB  = hrnChildB.getID();
3082
3083         if( idChildA.equals( idChildB ) &&
3084             edgeA.typeAndFieldEquals( edgeB ) ) {
3085
3086           // there is an edge in the right place with the right field,
3087           // but do they have the same attributes?
3088           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3089               edgeA.equalsPreds( edgeB )
3090               ) {
3091             edgeFound = true;
3092           }
3093         }
3094       }
3095
3096       if( !edgeFound ) {
3097         return false;
3098       }
3099     }
3100
3101     return true;
3102   }
3103
3104
3105
3106   // this analysis no longer has the "match anything"
3107   // type which was represented by null
3108   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3109                                              TypeDescriptor td2 ) {
3110     assert td1 != null;
3111     assert td2 != null;
3112
3113     if( td1.isNull() ) {
3114       return td2;
3115     }
3116     if( td2.isNull() ) {
3117       return td1;
3118     }
3119     return typeUtil.mostSpecific( td1, td2 );
3120   }
3121
3122   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3123                                              TypeDescriptor td2,
3124                                              TypeDescriptor td3 ) {
3125
3126     return mostSpecificType( td1,
3127                              mostSpecificType( td2, td3 )
3128                              );
3129   }
3130
3131   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3132                                              TypeDescriptor td2,
3133                                              TypeDescriptor td3,
3134                                              TypeDescriptor td4 ) {
3135
3136     return mostSpecificType( mostSpecificType( td1, td2 ),
3137                              mostSpecificType( td3, td4 )
3138                              );
3139   }
3140
3141   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3142                                     TypeDescriptor possibleChild ) {
3143     assert possibleSuper != null;
3144     assert possibleChild != null;
3145
3146     if( possibleSuper.isNull() ||
3147         possibleChild.isNull() ) {
3148       return true;
3149     }
3150
3151     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3152   }
3153
3154
3155   protected boolean hasMatchingField( HeapRegionNode src,
3156                                       RefEdge        edge ) {
3157
3158     TypeDescriptor tdSrc = src.getType();
3159     assert tdSrc != null;
3160
3161     if( tdSrc.isArray() ) {
3162       TypeDescriptor td = edge.getType();
3163       assert td != null;
3164
3165       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3166       assert tdSrcDeref != null;
3167
3168       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3169         return false;
3170       }
3171
3172       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3173     }
3174
3175     // if it's not a class, it doesn't have any fields to match
3176     if( !tdSrc.isClass() ) {
3177       return false;
3178     }
3179
3180     ClassDescriptor cd = tdSrc.getClassDesc();
3181     while( cd != null ) {
3182       Iterator fieldItr = cd.getFields();
3183
3184       while( fieldItr.hasNext() ) {
3185         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3186
3187         if( fd.getType().equals( edge.getType() ) &&
3188             fd.getSymbol().equals( edge.getField() ) ) {
3189           return true;
3190         }
3191       }
3192
3193       cd = cd.getSuperDesc();
3194     }
3195
3196     // otherwise it is a class with fields
3197     // but we didn't find a match
3198     return false;
3199   }
3200
3201   protected boolean hasMatchingType( RefEdge        edge,
3202                                      HeapRegionNode dst  ) {
3203
3204     // if the region has no type, matches everything
3205     TypeDescriptor tdDst = dst.getType();
3206     assert tdDst != null;
3207
3208     // if the type is not a class or an array, don't
3209     // match because primitives are copied, no aliases
3210     ClassDescriptor cdDst = tdDst.getClassDesc();
3211     if( cdDst == null && !tdDst.isArray() ) {
3212       return false;
3213     }
3214
3215     // if the edge type is null, it matches everything
3216     TypeDescriptor tdEdge = edge.getType();
3217     assert tdEdge != null;
3218
3219     return typeUtil.isSuperorType( tdEdge, tdDst );
3220   }
3221
3222
3223
3224   public void writeGraph( String  graphName,
3225                           boolean writeLabels,
3226                           boolean labelSelect,
3227                           boolean pruneGarbage,
3228                           boolean writeReferencers,
3229                           boolean hideSubsetReachability,
3230                           boolean hideEdgeTaints
3231                           ) throws java.io.IOException {
3232     writeGraph( graphName,
3233                 writeLabels,
3234                 labelSelect,
3235                 pruneGarbage,
3236                 writeReferencers,
3237                 hideSubsetReachability,
3238                 hideEdgeTaints,
3239                 null );
3240   }
3241
3242   public void writeGraph( String       graphName,
3243                           boolean      writeLabels,
3244                           boolean      labelSelect,
3245                           boolean      pruneGarbage,
3246                           boolean      writeReferencers,
3247                           boolean      hideSubsetReachability,
3248                           boolean      hideEdgeTaints,
3249                           Set<Integer> callerNodeIDsCopiedToCallee
3250                           ) throws java.io.IOException {
3251
3252     // remove all non-word characters from the graph name so
3253     // the filename and identifier in dot don't cause errors
3254     graphName = graphName.replaceAll( "[\\W]", "" );
3255
3256     BufferedWriter bw =
3257       new BufferedWriter( new FileWriter( graphName+".dot" ) );
3258
3259     bw.write( "digraph "+graphName+" {\n" );
3260
3261
3262     // this is an optional step to form the callee-reachable
3263     // "cut-out" into a DOT cluster for visualization
3264     if( callerNodeIDsCopiedToCallee != null ) {
3265
3266       bw.write( "  subgraph cluster0 {\n" );
3267       bw.write( "    color=blue;\n" );
3268
3269       Iterator i = id2hrn.entrySet().iterator();
3270       while( i.hasNext() ) {
3271         Map.Entry      me  = (Map.Entry)      i.next();
3272         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3273
3274         if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3275           bw.write( "    "+hrn.toString()+
3276                     hrn.toStringDOT( hideSubsetReachability )+
3277                     ";\n" );
3278
3279         }
3280       }
3281
3282       bw.write( "  }\n" );
3283     }
3284
3285
3286     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3287
3288     // then visit every heap region node
3289     Iterator i = id2hrn.entrySet().iterator();
3290     while( i.hasNext() ) {
3291       Map.Entry      me  = (Map.Entry)      i.next();
3292       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3293
3294       // only visit nodes worth writing out--for instance
3295       // not every node at an allocation is referenced
3296       // (think of it as garbage-collected), etc.
3297       if( !pruneGarbage                              ||
3298           (hrn.isFlagged() && hrn.getID() > 0)       ||
3299           hrn.getDescription().startsWith( "param" ) ||
3300           hrn.isOutOfContext()
3301           ) {
3302
3303         if( !visited.contains( hrn ) ) {
3304           traverseHeapRegionNodes( hrn,
3305                                    bw,
3306                                    null,
3307                                    visited,
3308                                    writeReferencers,
3309                                    hideSubsetReachability,
3310                                    hideEdgeTaints,
3311                                    callerNodeIDsCopiedToCallee );
3312         }
3313       }
3314     }
3315
3316     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
3317
3318
3319     // then visit every label node, useful for debugging
3320     if( writeLabels ) {
3321       i = td2vn.entrySet().iterator();
3322       while( i.hasNext() ) {
3323         Map.Entry    me = (Map.Entry)    i.next();
3324         VariableNode vn = (VariableNode) me.getValue();
3325
3326         if( labelSelect ) {
3327           String labelStr = vn.getTempDescriptorString();
3328           if( labelStr.startsWith("___temp") ||
3329               labelStr.startsWith("___dst") ||
3330               labelStr.startsWith("___srctmp") ||
3331               labelStr.startsWith("___neverused")
3332               ) {
3333             continue;
3334           }
3335         }
3336
3337         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3338         while( heapRegionsItr.hasNext() ) {
3339           RefEdge        edge = heapRegionsItr.next();
3340           HeapRegionNode hrn  = edge.getDst();
3341
3342           if( pruneGarbage && !visited.contains( hrn ) ) {
3343             traverseHeapRegionNodes( hrn,
3344                                      bw,
3345                                      null,
3346                                      visited,
3347                                      writeReferencers,
3348                                      hideSubsetReachability,
3349                                      hideEdgeTaints,
3350                                      callerNodeIDsCopiedToCallee );
3351           }
3352
3353           bw.write( "  "+vn.toString()+
3354                     " -> "+hrn.toString()+
3355                     edge.toStringDOT( hideSubsetReachability, "" )+
3356                     ";\n" );
3357         }
3358       }
3359     }
3360
3361     bw.write( "}\n" );
3362     bw.close();
3363   }
3364
3365   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
3366                                           BufferedWriter      bw,
3367                                           TempDescriptor      td,
3368                                           Set<HeapRegionNode> visited,
3369                                           boolean             writeReferencers,
3370                                           boolean             hideSubsetReachability,
3371                                           boolean             hideEdgeTaints,
3372                                           Set<Integer>        callerNodeIDsCopiedToCallee
3373                                           ) throws java.io.IOException {
3374
3375     if( visited.contains( hrn ) ) {
3376       return;
3377     }
3378     visited.add( hrn );
3379
3380     // if we're drawing the callee-view subgraph, only
3381     // write out the node info if it hasn't already been
3382     // written
3383     if( callerNodeIDsCopiedToCallee == null ||
3384         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3385         ) {
3386       bw.write( "  "+hrn.toString()+
3387                 hrn.toStringDOT( hideSubsetReachability )+
3388                 ";\n" );
3389     }
3390
3391     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3392     while( childRegionsItr.hasNext() ) {
3393       RefEdge        edge     = childRegionsItr.next();
3394       HeapRegionNode hrnChild = edge.getDst();
3395
3396       if( callerNodeIDsCopiedToCallee != null &&
3397           (edge.getSrc() instanceof HeapRegionNode) ) {
3398         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3399         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
3400             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3401             ) {
3402           bw.write( "  "+hrn.toString()+
3403                     " -> "+hrnChild.toString()+
3404                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3405                     ";\n");
3406         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
3407                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3408                    ) {
3409           bw.write( "  "+hrn.toString()+
3410                     " -> "+hrnChild.toString()+
3411                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3412                     ";\n");
3413         } else {
3414           bw.write( "  "+hrn.toString()+
3415                     " -> "+hrnChild.toString()+
3416                     edge.toStringDOT( hideSubsetReachability, "" )+
3417                     ";\n");
3418         }
3419       } else {
3420         bw.write( "  "+hrn.toString()+
3421                   " -> "+hrnChild.toString()+
3422                   edge.toStringDOT( hideSubsetReachability, "" )+
3423                   ";\n");
3424       }
3425
3426       traverseHeapRegionNodes( hrnChild,
3427                                bw,
3428                                td,
3429                                visited,
3430                                writeReferencers,
3431                                hideSubsetReachability,
3432                                hideEdgeTaints,
3433                                callerNodeIDsCopiedToCallee );
3434     }
3435   }
3436
3437 }