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