Robust/src/Analysis/Disjoint/ReachGraph.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import Util.UtilAlgorithms;
   6 import java.util.*;
   7 import java.io.*;
   8
   9 public class ReachGraph {
  10
  11   // use to disable improvements for comparison
  12   protected static final boolean DISABLE_STRONG_UPDATES = false;
  13   protected static final boolean DISABLE_GLOBAL_SWEEP   = false;
  14
  15   // a special out-of-scope temp
  16   protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
  17
  18   // 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.unionORpreds( 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.unionORpreds( 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.unionORpreds( 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.unionORpreds( 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().containsIgnorePreds( c.getStateToMatch() )
1084               != null
1085               ) {
1086             changesToPass = Canonical.add( changesToPass, c );
1087           }
1088         }
1089
1090         if( !changesToPass.isEmpty() ) {
1091           if( !nodePlannedChanges.containsKey( m ) ) {
1092             nodePlannedChanges.put( m, ChangeSet.factory() );
1093           }
1094
1095           ChangeSet currentChanges = nodePlannedChanges.get( m );
1096
1097           if( !changesToPass.isSubset( currentChanges ) ) {
1098
1099             nodePlannedChanges.put( m,
1100                                     Canonical.union( currentChanges,
1101                                                      changesToPass
1102                                                      )
1103                                     );
1104             todoNodes.add( m );
1105           }
1106         }
1107       }
1108
1109       todoNodes.remove( n );
1110     }
1111
1112     // then apply all of the changes for each node at once
1113     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1114     while( itrMap.hasNext() ) {
1115       Map.Entry      me = (Map.Entry)      itrMap.next();
1116       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1117       ChangeSet      C  = (ChangeSet)      me.getValue();
1118
1119       // this propagation step is with respect to one change,
1120       // so we capture the full change from the old alpha:
1121       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1122                                                       C,
1123                                                       true
1124                                                       );
1125       // but this propagation may be only one of many concurrent
1126       // possible changes, so keep a running union with the node's
1127       // partially updated new alpha set
1128       n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1129                                       localDelta
1130                                       )
1131                      );
1132
1133       nodesWithNewAlpha.add( n );
1134     }
1135
1136     propagateTokensOverEdges( todoEdges,
1137                               edgePlannedChanges,
1138                               edgesWithNewBeta
1139                               );
1140   }
1141
1142
1143   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1144                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1145                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1146
1147     // first propagate all change tuples everywhere they can go
1148     while( !todoEdges.isEmpty() ) {
1149       RefEdge edgeE = todoEdges.iterator().next();
1150       todoEdges.remove( edgeE );
1151
1152       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1153         edgePlannedChanges.put( edgeE,
1154                                 ChangeSet.factory()
1155                                 );
1156       }
1157
1158       ChangeSet C = edgePlannedChanges.get( edgeE );
1159
1160       ChangeSet changesToPass = ChangeSet.factory();
1161
1162       Iterator<ChangeTuple> itrC = C.iterator();
1163       while( itrC.hasNext() ) {
1164         ChangeTuple c = itrC.next();
1165         if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1166             != null
1167             ) {
1168           changesToPass = Canonical.add( changesToPass, c );
1169         }
1170       }
1171
1172       RefSrcNode rsn = edgeE.getSrc();
1173
1174       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1175         HeapRegionNode n = (HeapRegionNode) rsn;
1176
1177         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1178         while( referItr.hasNext() ) {
1179           RefEdge edgeF = referItr.next();
1180
1181           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1182             edgePlannedChanges.put( edgeF,
1183                                     ChangeSet.factory()
1184                                     );
1185           }
1186
1187           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1188
1189           if( !changesToPass.isSubset( currentChanges ) ) {
1190             todoEdges.add( edgeF );
1191             edgePlannedChanges.put( edgeF,
1192                                     Canonical.union( currentChanges,
1193                                                      changesToPass
1194                                                      )
1195                                     );
1196           }
1197         }
1198       }
1199     }
1200
1201     // then apply all of the changes for each edge at once
1202     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1203     while( itrMap.hasNext() ) {
1204       Map.Entry me = (Map.Entry) itrMap.next();
1205       RefEdge   e  = (RefEdge)   me.getKey();
1206       ChangeSet C  = (ChangeSet) me.getValue();
1207
1208       // this propagation step is with respect to one change,
1209       // so we capture the full change from the old beta:
1210       ReachSet localDelta =
1211         Canonical.applyChangeSet( e.getBeta(),
1212                                   C,
1213                                   true
1214                                   );
1215
1216       // but this propagation may be only one of many concurrent
1217       // possible changes, so keep a running union with the edge's
1218       // partially updated new beta set
1219       e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1220                                      localDelta
1221                                      )
1222                     );
1223
1224       edgesWithNewBeta.add( e );
1225     }
1226   }
1227
1228
1229   // used in makeCalleeView below to decide if there is
1230   // already an appropriate out-of-context edge in a callee
1231   // view graph for merging, or null if a new one will be added
1232   protected RefEdge
1233     getOutOfContextReferenceTo( HeapRegionNode hrn,
1234                                 TypeDescriptor srcType,
1235                                 TypeDescriptor refType,
1236                                 String         refField ) {
1237     assert belongsToThis( hrn );
1238
1239     HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1240     if( hrnInContext == null ) {
1241       return null;
1242     }
1243
1244     Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1245     while( refItr.hasNext() ) {
1246       RefEdge re = refItr.next();
1247
1248       assert belongsToThis( re.getSrc() );
1249       assert belongsToThis( re.getDst() );
1250
1251       if( !(re.getSrc() instanceof HeapRegionNode) ) {
1252         continue;
1253       }
1254
1255       HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1256       if( !hrnSrc.isOutOfContext() ) {
1257         continue;
1258       }
1259
1260       if( srcType == null ) {
1261         if( hrnSrc.getType() != null ) {
1262           continue;
1263         }
1264       } else {
1265         if( !srcType.equals( hrnSrc.getType() ) ) {
1266           continue;
1267         }
1268       }
1269
1270       if( !re.typeEquals( refType ) ) {
1271         continue;
1272       }
1273
1274       if( !re.fieldEquals( refField ) ) {
1275         continue;
1276       }
1277
1278       // tada!  We found it!
1279       return re;
1280     }
1281
1282     return null;
1283   }
1284
1285   // used below to convert a ReachSet to its callee-context
1286   // equivalent with respect to allocation sites in this graph
1287   protected ReachSet toCalleeContext( ReachSet        rs,
1288                                       ExistPredSet    preds,
1289                                       Set<ReachTuple> oocTuples
1290                                       ) {
1291     ReachSet out = ReachSet.factory();
1292
1293     Iterator<ReachState> itr = rs.iterator();
1294     while( itr.hasNext() ) {
1295       ReachState stateCaller = itr.next();
1296
1297       ReachState stateCallee = stateCaller;
1298
1299       Iterator<AllocSite> asItr = allocSites.iterator();
1300       while( asItr.hasNext() ) {
1301         AllocSite as = asItr.next();
1302
1303         ReachState stateNew = ReachState.factory();
1304         Iterator<ReachTuple> rtItr = stateCallee.iterator();
1305         while( rtItr.hasNext() ) {
1306           ReachTuple rt = rtItr.next();
1307
1308           // only translate this tuple if it is
1309           // in the out-callee-context bag
1310           if( !oocTuples.contains( rt ) ) {
1311             stateNew = Canonical.add( stateNew, rt );
1312             continue;
1313           }
1314
1315           int age = as.getAgeCategory( rt.getHrnID() );
1316
1317           // this is the current mapping, where 0, 1, 2S were allocated
1318           // in the current context, 0?, 1? and 2S? were allocated in a
1319           // previous context, and we're translating to a future context
1320           //
1321           // 0    -> 0?
1322           // 1    -> 1?
1323           // 2S   -> 2S?
1324           // 2S*  -> 2S?*
1325           //
1326           // 0?   -> 2S?
1327           // 1?   -> 2S?
1328           // 2S?  -> 2S?
1329           // 2S?* -> 2S?*
1330
1331           if( age == AllocSite.AGE_notInThisSite ) {
1332             // things not from the site just go back in
1333             stateNew = Canonical.add( stateNew, rt );
1334
1335           } else if( age == AllocSite.AGE_summary ||
1336                      rt.isOutOfContext()
1337                      ) {
1338             // the in-context summary and all existing out-of-context
1339             // stuff all become
1340             stateNew = Canonical.add( stateNew,
1341                                       ReachTuple.factory( as.getSummary(),
1342                                                           true, // multi
1343                                                           rt.getArity(),
1344                                                           true  // out-of-context
1345                                                           )
1346                                       );
1347           } else {
1348             // otherwise everything else just goes to an out-of-context
1349             // version, everything else the same
1350             Integer I = as.getAge( rt.getHrnID() );
1351             assert I != null;
1352
1353             assert !rt.isMultiObject();
1354
1355             stateNew = Canonical.add( stateNew,
1356                                       ReachTuple.factory( rt.getHrnID(),
1357                                                           rt.isMultiObject(),
1358                                                           rt.getArity(),
1359                                                           true  // out-of-context
1360                                                           )
1361                                       );
1362           }
1363         }
1364
1365         stateCallee = stateNew;
1366       }
1367
1368       // attach the passed in preds
1369       stateCallee = Canonical.attach( stateCallee,
1370                                       preds );
1371
1372       out = Canonical.add( out,
1373                            stateCallee
1374                            );
1375
1376     }
1377     assert out.isCanonical();
1378     return out;
1379   }
1380
1381   // used below to convert a ReachSet to its caller-context
1382   // equivalent with respect to allocation sites in this graph
1383   protected ReachSet
1384     toCallerContext( ReachSet                            rs,
1385                      Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1386                      ) {
1387     ReachSet out = ReachSet.factory();
1388
1389     Iterator<ReachState> itr = rs.iterator();
1390     while( itr.hasNext() ) {
1391       ReachState stateCallee = itr.next();
1392
1393       if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1394
1395         // starting from one callee state...
1396         ReachSet rsCaller = ReachSet.factory( stateCallee );
1397
1398         // possibly branch it into many states, which any
1399         // allocation site might do, so lots of derived states
1400         Iterator<AllocSite> asItr = allocSites.iterator();
1401         while( asItr.hasNext() ) {
1402           AllocSite as = asItr.next();
1403           rsCaller = Canonical.toCallerContext( rsCaller, as );
1404         }
1405
1406         // then before adding each derived, now caller-context
1407         // states to the output, attach the appropriate pred
1408         // based on the source callee state
1409         Iterator<ReachState> stateItr = rsCaller.iterator();
1410         while( stateItr.hasNext() ) {
1411           ReachState stateCaller = stateItr.next();
1412           stateCaller = Canonical.attach( stateCaller,
1413                                           calleeStatesSatisfied.get( stateCallee )
1414                                           );
1415           out = Canonical.add( out,
1416                                stateCaller
1417                                );
1418         }
1419       }
1420     }
1421
1422     assert out.isCanonical();
1423     return out;
1424   }
1425
1426   // used below to convert a ReachSet to an equivalent
1427   // version with shadow IDs merged into unshadowed IDs
1428   protected ReachSet unshadow( ReachSet rs ) {
1429     ReachSet out = rs;
1430     Iterator<AllocSite> asItr = allocSites.iterator();
1431     while( asItr.hasNext() ) {
1432       AllocSite as = asItr.next();
1433       out = Canonical.unshadow( out, as );
1434     }
1435     assert out.isCanonical();
1436     return out;
1437   }
1438
1439
1440   // use this method to make a new reach graph that is
1441   // what heap the FlatMethod callee from the FlatCall
1442   // would start with reaching from its arguments in
1443   // this reach graph
1444   public ReachGraph
1445     makeCalleeView( FlatCall     fc,
1446                     FlatMethod   fmCallee,
1447                     Set<Integer> callerNodeIDsCopiedToCallee,
1448                     boolean      writeDebugDOTs
1449                     ) {
1450
1451
1452     // first traverse this context to find nodes and edges
1453     //  that will be callee-reachable
1454     Set<HeapRegionNode> reachableCallerNodes =
1455       new HashSet<HeapRegionNode>();
1456
1457     // caller edges between callee-reachable nodes
1458     Set<RefEdge> reachableCallerEdges =
1459       new HashSet<RefEdge>();
1460
1461     // caller edges from arg vars, and the matching param index
1462     // because these become a special edge in callee
1463     Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1464       new Hashtable<RefEdge, Integer>();
1465
1466     // caller edges from local vars or callee-unreachable nodes
1467     // (out-of-context sources) to callee-reachable nodes
1468     Set<RefEdge> oocCallerEdges =
1469       new HashSet<RefEdge>();
1470
1471
1472     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1473
1474       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1475       VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1476
1477       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1478       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1479
1480       toVisitInCaller.add( vnArgCaller );
1481
1482       while( !toVisitInCaller.isEmpty() ) {
1483         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1484         toVisitInCaller.remove( rsnCaller );
1485         visitedInCaller.add( rsnCaller );
1486
1487         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1488         while( itrRefEdges.hasNext() ) {
1489           RefEdge        reCaller  = itrRefEdges.next();
1490           HeapRegionNode hrnCaller = reCaller.getDst();
1491
1492           callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1493           reachableCallerNodes.add( hrnCaller );
1494
1495           if( reCaller.getSrc() instanceof HeapRegionNode ) {
1496             reachableCallerEdges.add( reCaller );
1497           } else {
1498             if( rsnCaller.equals( vnArgCaller ) ) {
1499               reachableCallerArgEdges2paramIndex.put( reCaller, i );
1500             } else {
1501               oocCallerEdges.add( reCaller );
1502             }
1503           }
1504
1505           if( !visitedInCaller.contains( hrnCaller ) ) {
1506             toVisitInCaller.add( hrnCaller );
1507           }
1508
1509         } // end edge iteration
1510       } // end visiting heap nodes in caller
1511     } // end iterating over parameters as starting points
1512
1513
1514     // now collect out-of-context reach tuples and
1515     // more out-of-context edges
1516     Set<ReachTuple> oocTuples = new HashSet<ReachTuple>();
1517
1518     Iterator<Integer> itrInContext =
1519       callerNodeIDsCopiedToCallee.iterator();
1520     while( itrInContext.hasNext() ) {
1521       Integer        hrnID                 = itrInContext.next();
1522       HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1523
1524       Iterator<RefEdge> itrMightCross =
1525         hrnCallerAndInContext.iteratorToReferencers();
1526       while( itrMightCross.hasNext() ) {
1527         RefEdge edgeMightCross = itrMightCross.next();
1528
1529         RefSrcNode rsnCallerAndOutContext =
1530           edgeMightCross.getSrc();
1531
1532         if( rsnCallerAndOutContext instanceof VariableNode ) {
1533           // variables do not have out-of-context reach states,
1534           // so jump out now
1535           oocCallerEdges.add( edgeMightCross );
1536           continue;
1537         }
1538
1539         HeapRegionNode hrnCallerAndOutContext =
1540           (HeapRegionNode) rsnCallerAndOutContext;
1541
1542         // is this source node out-of-context?
1543         if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1544           // no, skip this edge
1545           continue;
1546         }
1547
1548         // okay, we got one
1549         oocCallerEdges.add( edgeMightCross );
1550
1551         // add all reach tuples on the node to list
1552         // of things that are out-of-context: insight
1553         // if this node is reachable from someting that WAS
1554         // in-context, then this node should already be in-context
1555         Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1556         while( stateItr.hasNext() ) {
1557           ReachState state = stateItr.next();
1558
1559           Iterator<ReachTuple> rtItr = state.iterator();
1560           while( rtItr.hasNext() ) {
1561             ReachTuple rt = rtItr.next();
1562
1563             oocTuples.add( rt );
1564           }
1565         }
1566       }
1567     }
1568
1569
1570     // the callee view is a new graph: DON'T MODIFY *THIS* graph
1571     ReachGraph rg = new ReachGraph();
1572
1573     // add nodes to callee graph
1574     Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1575     while( hrnItr.hasNext() ) {
1576       HeapRegionNode hrnCaller = hrnItr.next();
1577
1578       assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1579       assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1580
1581       ExistPred    pred  = ExistPred.factory( hrnCaller.getID(), null );
1582       ExistPredSet preds = ExistPredSet.factory( pred );
1583
1584       rg.createNewHeapRegionNode( hrnCaller.getID(),
1585                                   hrnCaller.isSingleObject(),
1586                                   hrnCaller.isNewSummary(),
1587                                   hrnCaller.isFlagged(),
1588                                   false, // out-of-context?
1589                                   hrnCaller.getType(),
1590                                   hrnCaller.getAllocSite(),
1591                                   toCalleeContext( hrnCaller.getInherent(),
1592                                                    preds,
1593                                                    oocTuples
1594                                                    ),
1595                                   toCalleeContext( hrnCaller.getAlpha(),
1596                                                    preds,
1597                                                    oocTuples
1598                                                    ),
1599                                   preds,
1600                                   hrnCaller.getDescription()
1601                                   );
1602     }
1603
1604     // add param edges to callee graph
1605     Iterator argEdges =
1606       reachableCallerArgEdges2paramIndex.entrySet().iterator();
1607     while( argEdges.hasNext() ) {
1608       Map.Entry me    = (Map.Entry) argEdges.next();
1609       RefEdge   reArg = (RefEdge)   me.getKey();
1610       Integer   index = (Integer)   me.getValue();
1611
1612       TempDescriptor arg = fmCallee.getParameter( index );
1613
1614       VariableNode vnCallee =
1615         rg.getVariableNodeFromTemp( arg );
1616
1617       HeapRegionNode hrnDstCaller = reArg.getDst();
1618       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1619       assert hrnDstCallee != null;
1620
1621       ExistPred pred =
1622         ExistPred.factory( arg,
1623                            null,
1624                            hrnDstCallee.getID(),
1625                            reArg.getType(),
1626                            reArg.getField(),
1627                            null,
1628                            true,  // out-of-callee-context
1629                            false  // out-of-caller-context
1630                            );
1631
1632       ExistPredSet preds =
1633         ExistPredSet.factory( pred );
1634
1635       RefEdge reCallee =
1636         new RefEdge( vnCallee,
1637                      hrnDstCallee,
1638                      reArg.getType(),
1639                      reArg.getField(),
1640                      toCalleeContext( reArg.getBeta(),
1641                                       preds,
1642                                       oocTuples
1643                                       ),
1644                      preds
1645                      );
1646
1647       rg.addRefEdge( vnCallee,
1648                      hrnDstCallee,
1649                      reCallee
1650                      );
1651     }
1652
1653     // add in-context edges to callee graph
1654     Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1655     while( reItr.hasNext() ) {
1656       RefEdge    reCaller  = reItr.next();
1657       RefSrcNode rsnCaller = reCaller.getSrc();
1658       assert rsnCaller instanceof HeapRegionNode;
1659       HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1660       HeapRegionNode hrnDstCaller = reCaller.getDst();
1661
1662       HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1663       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1664       assert hrnSrcCallee != null;
1665       assert hrnDstCallee != null;
1666
1667       ExistPred pred =
1668         ExistPred.factory( null,
1669                            hrnSrcCallee.getID(),
1670                            hrnDstCallee.getID(),
1671                            reCaller.getType(),
1672                            reCaller.getField(),
1673                            null,
1674                            false, // out-of-callee-context
1675                            false  // out-of-caller-context
1676                            );
1677
1678       ExistPredSet preds =
1679         ExistPredSet.factory( pred );
1680
1681       RefEdge reCallee =
1682         new RefEdge( hrnSrcCallee,
1683                      hrnDstCallee,
1684                      reCaller.getType(),
1685                      reCaller.getField(),
1686                      toCalleeContext( reCaller.getBeta(),
1687                                       preds,
1688                                       oocTuples
1689                                       ),
1690                      preds
1691                      );
1692
1693       rg.addRefEdge( hrnSrcCallee,
1694                      hrnDstCallee,
1695                      reCallee
1696                      );
1697     }
1698
1699     // add out-of-context edges to callee graph
1700     reItr = oocCallerEdges.iterator();
1701     while( reItr.hasNext() ) {
1702       RefEdge        reCaller     = reItr.next();
1703       RefSrcNode     rsnCaller    = reCaller.getSrc();
1704       HeapRegionNode hrnDstCaller = reCaller.getDst();
1705       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1706       assert hrnDstCallee != null;
1707
1708       TypeDescriptor oocNodeType;
1709       ReachSet       oocReach;
1710       TempDescriptor oocPredSrcTemp = null;
1711       Integer        oocPredSrcID   = null;
1712       boolean        outOfCalleeContext;
1713       boolean        outOfCallerContext;
1714
1715       if( rsnCaller instanceof VariableNode ) {
1716         VariableNode vnCaller = (VariableNode) rsnCaller;
1717         oocNodeType    = null;
1718         oocReach       = rsetEmpty;
1719         oocPredSrcTemp = vnCaller.getTempDescriptor();
1720         outOfCalleeContext = true;
1721         outOfCallerContext = false;
1722
1723       } else {
1724         HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1725         assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1726         oocNodeType  = hrnSrcCaller.getType();
1727         oocReach     = hrnSrcCaller.getAlpha();
1728         oocPredSrcID = hrnSrcCaller.getID();
1729         if( hrnSrcCaller.isOutOfContext() ) {
1730           outOfCalleeContext = false;
1731           outOfCallerContext = true;
1732         } else {
1733           outOfCalleeContext = true;
1734           outOfCallerContext = false;
1735         }
1736       }
1737
1738       ExistPred pred =
1739         ExistPred.factory( oocPredSrcTemp,
1740                            oocPredSrcID,
1741                            hrnDstCallee.getID(),
1742                            reCaller.getType(),
1743                            reCaller.getField(),
1744                            null,
1745                            outOfCalleeContext,
1746                            outOfCallerContext
1747                            );
1748
1749       ExistPredSet preds =
1750         ExistPredSet.factory( pred );
1751
1752       RefEdge oocEdgeExisting =
1753         rg.getOutOfContextReferenceTo( hrnDstCallee,
1754                                        oocNodeType,
1755                                        reCaller.getType(),
1756                                        reCaller.getField()
1757                                        );
1758
1759       if( oocEdgeExisting == null ) {
1760           // for consistency, map one out-of-context "identifier"
1761           // to one heap region node id, otherwise no convergence
1762         String oocid = "oocid"+
1763           fmCallee+
1764           hrnDstCallee.getIDString()+
1765           oocNodeType+
1766           reCaller.getType()+
1767           reCaller.getField();
1768
1769         Integer oocHrnID = oocid2hrnid.get( oocid );
1770
1771         HeapRegionNode hrnCalleeAndOutContext;
1772
1773         if( oocHrnID == null ) {
1774
1775           hrnCalleeAndOutContext =
1776             rg.createNewHeapRegionNode( null,  // ID
1777                                         false, // single object?
1778                                         false, // new summary?
1779                                         false, // flagged?
1780                                         true,  // out-of-context?
1781                                         oocNodeType,
1782                                         null,  // alloc site, shouldn't be used
1783                                         toCalleeContext( oocReach,
1784                                                          preds,
1785                                                          oocTuples
1786                                                          ),
1787                                         toCalleeContext( oocReach,
1788                                                          preds,
1789                                                          oocTuples
1790                                                          ),
1791                                         preds,
1792                                         "out-of-context"
1793                                         );
1794
1795           oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1796
1797         } else {
1798
1799           // the mapping already exists, so see if node is there
1800           hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1801
1802           if( hrnCalleeAndOutContext == null ) {
1803             // nope, make it
1804             hrnCalleeAndOutContext =
1805               rg.createNewHeapRegionNode( oocHrnID,  // ID
1806                                           false, // single object?
1807                                           false, // new summary?
1808                                           false, // flagged?
1809                                           true,  // out-of-context?
1810                                           oocNodeType,
1811                                           null,  // alloc site, shouldn't be used
1812                                           toCalleeContext( oocReach,
1813                                                            preds,
1814                                                            oocTuples
1815                                                            ),
1816                                           toCalleeContext( oocReach,
1817                                                            preds,
1818                                                            oocTuples
1819                                                            ),
1820                                           preds,
1821                                           "out-of-context"
1822                                           );
1823           }
1824         }
1825
1826         rg.addRefEdge( hrnCalleeAndOutContext,
1827                        hrnDstCallee,
1828                        new RefEdge( hrnCalleeAndOutContext,
1829                                     hrnDstCallee,
1830                                     reCaller.getType(),
1831                                     reCaller.getField(),
1832                                     toCalleeContext( reCaller.getBeta(),
1833                                                      preds,
1834                                                      oocTuples
1835                                                      ),
1836                                     preds
1837                                     )
1838                        );
1839
1840         } else {
1841         // the out-of-context edge already exists
1842         oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1843                                                          toCalleeContext( reCaller.getBeta(),
1844                                                                           preds,
1845                                                                           oocTuples
1846                                                                           )
1847                                                   )
1848                                  );
1849
1850         oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1851                                                   reCaller.getPreds()
1852                                                   )
1853                                   );
1854
1855       }
1856     }
1857
1858
1859     if( writeDebugDOTs ) {
1860       try {
1861         rg.writeGraph( "calleeview",
1862                        resolveMethodDebugDOTwriteLabels,
1863                        resolveMethodDebugDOTselectTemps,
1864                        resolveMethodDebugDOTpruneGarbage,
1865                        resolveMethodDebugDOThideSubsetReach,
1866                        resolveMethodDebugDOThideEdgeTaints );
1867       } catch( IOException e ) {}
1868     }
1869
1870     return rg;
1871   }
1872
1873   private static Hashtable<String, Integer> oocid2hrnid =
1874     new Hashtable<String, Integer>();
1875
1876
1877   // useful since many graphs writes in the method call debug code
1878   private static boolean resolveMethodDebugDOTwriteLabels     = true;
1879   private static boolean resolveMethodDebugDOTselectTemps     = true;
1880   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
1881   private static boolean resolveMethodDebugDOThideSubsetReach = false;
1882   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
1883
1884
1885
1886   public void
1887     resolveMethodCall( FlatCall     fc,
1888                        FlatMethod   fmCallee,
1889                        ReachGraph   rgCallee,
1890                        Set<Integer> callerNodeIDsCopiedToCallee,
1891                        boolean      writeDebugDOTs
1892                        ) {
1893
1894
1895     if( writeDebugDOTs ) {
1896       try {
1897         rgCallee.writeGraph( "callee",
1898                        resolveMethodDebugDOTwriteLabels,
1899                        resolveMethodDebugDOTselectTemps,
1900                        resolveMethodDebugDOTpruneGarbage,
1901                        resolveMethodDebugDOThideSubsetReach,
1902                        resolveMethodDebugDOThideEdgeTaints );
1903
1904         writeGraph( "caller00In",
1905                     resolveMethodDebugDOTwriteLabels,
1906                     resolveMethodDebugDOTselectTemps,
1907                     resolveMethodDebugDOTpruneGarbage,
1908                     resolveMethodDebugDOThideSubsetReach,
1909                     resolveMethodDebugDOThideEdgeTaints,
1910                     callerNodeIDsCopiedToCallee );
1911       } catch( IOException e ) {}
1912     }
1913
1914
1915     // method call transfer function steps:
1916     // 1. Use current callee-reachable heap (CRH) to test callee
1917     //    predicates and mark what will be coming in.
1918     // 2. Wipe CRH out of caller.
1919     // 3. Transplant marked callee parts in:
1920     //    a) bring in nodes
1921     //    b) bring in callee -> callee edges
1922     //    c) resolve out-of-context -> callee edges
1923     //    d) assign return value
1924     // 4. Collapse shadow nodes down
1925     // 5. Global sweep it.
1926
1927
1928
1929     // 1. mark what callee elements have satisfied predicates
1930     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1931       new Hashtable<HeapRegionNode, ExistPredSet>();
1932
1933     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1934       new Hashtable<RefEdge, ExistPredSet>();
1935
1936     Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1937       new Hashtable<ReachState, ExistPredSet>();
1938
1939     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1940       new Hashtable< RefEdge, Set<RefSrcNode> >();
1941
1942     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1943     while( meItr.hasNext() ) {
1944       Map.Entry      me        = (Map.Entry)      meItr.next();
1945       Integer        id        = (Integer)        me.getKey();
1946       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1947
1948       // if a callee element's predicates are satisfied then a set
1949       // of CALLER predicates is returned: they are the predicates
1950       // that the callee element moved into the caller context
1951       // should have, and it is inefficient to find this again later
1952       ExistPredSet predsIfSatis =
1953         hrnCallee.getPreds().isSatisfiedBy( this,
1954                                             callerNodeIDsCopiedToCallee
1955                                             );
1956       if( predsIfSatis != null ) {
1957         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1958       } else {
1959         // otherwise don't bother looking at edges to this node
1960         continue;
1961       }
1962
1963       // since the node is coming over, find out which reach
1964       // states on it should come over, too
1965       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
1966       while( stateItr.hasNext() ) {
1967         ReachState stateCallee = stateItr.next();
1968
1969         predsIfSatis =
1970           stateCallee.getPreds().isSatisfiedBy( this,
1971                                                 callerNodeIDsCopiedToCallee
1972                                                 );
1973         if( predsIfSatis != null ) {
1974           calleeStatesSatisfied.put( stateCallee, predsIfSatis );
1975         }
1976       }
1977
1978       // then look at edges to the node
1979       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
1980       while( reItr.hasNext() ) {
1981         RefEdge    reCallee  = reItr.next();
1982         RefSrcNode rsnCallee = reCallee.getSrc();
1983
1984         // (caller local variables to in-context heap regions)
1985         // have an (out-of-context heap region -> in-context heap region)
1986         // abstraction in the callEE, so its true we never need to
1987         // look at a (var node -> heap region) edge in callee to bring
1988         // those over for the call site transfer.  What about (param var->heap region)
1989         // edges in callee? They are dealt with below this loop.
1990         // So, yes, at this point skip (var->region) edges in callee
1991         if( rsnCallee instanceof VariableNode ) {
1992           continue;
1993         }
1994
1995         // first see if the source is out-of-context, and only
1996         // proceed with this edge if we find some caller-context
1997         // matches
1998         HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
1999         boolean matchedOutOfContext = false;
2000
2001         if( hrnSrcCallee.isOutOfContext() ) {
2002
2003           assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2004           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2005
2006           HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2007           Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2008           while( reDstItr.hasNext() ) {
2009             // the edge and field (either possibly null) must match
2010             RefEdge reCaller = reDstItr.next();
2011
2012             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
2013                 !reCaller.fieldEquals( reCallee.getField() )
2014                 ) {
2015               continue;
2016             }
2017
2018             RefSrcNode rsnCaller = reCaller.getSrc();
2019             if( rsnCaller instanceof VariableNode ) {
2020               // a variable node matches an OOC region with null type
2021               if( hrnSrcCallee.getType() != null ) {
2022                 continue;
2023               }
2024
2025             } else {
2026               // otherwise types should match
2027               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2028               if( hrnSrcCallee.getType() == null ) {
2029                 if( hrnCallerSrc.getType() != null ) {
2030                   continue;
2031                 }
2032               } else {
2033                 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2034                   continue;
2035                 }
2036               }
2037             }
2038
2039             rsnCallers.add( rsnCaller );
2040             matchedOutOfContext = true;
2041           }
2042
2043           if( !rsnCallers.isEmpty() ) {
2044             calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2045           }
2046         }
2047
2048         if( hrnSrcCallee.isOutOfContext() &&
2049             !matchedOutOfContext ) {
2050           continue;
2051         }
2052
2053         predsIfSatis =
2054           reCallee.getPreds().isSatisfiedBy( this,
2055                                              callerNodeIDsCopiedToCallee
2056                                              );
2057         if( predsIfSatis != null ) {
2058           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2059
2060           // since the edge is coming over, find out which reach
2061           // states on it should come over, too
2062           stateItr = reCallee.getBeta().iterator();
2063           while( stateItr.hasNext() ) {
2064             ReachState stateCallee = stateItr.next();
2065
2066             predsIfSatis =
2067               stateCallee.getPreds().isSatisfiedBy( this,
2068                                                     callerNodeIDsCopiedToCallee
2069                                                     );
2070             if( predsIfSatis != null ) {
2071               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2072             }
2073           }
2074         }
2075       }
2076     }
2077
2078     // test param -> HRN edges, also
2079     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2080
2081       // parameter defined here is the symbol in the callee
2082       TempDescriptor tdParam  = fmCallee.getParameter( i );
2083       VariableNode   vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2084
2085       Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2086       while( reItr.hasNext() ) {
2087         RefEdge reCallee = reItr.next();
2088
2089         ExistPredSet ifDst =
2090           reCallee.getDst().getPreds().isSatisfiedBy( this,
2091                                                       callerNodeIDsCopiedToCallee
2092                                                       );
2093         if( ifDst == null ) {
2094           continue;
2095         }
2096
2097         ExistPredSet predsIfSatis =
2098           reCallee.getPreds().isSatisfiedBy( this,
2099                                              callerNodeIDsCopiedToCallee
2100                                              );
2101         if( predsIfSatis != null ) {
2102           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2103
2104           // since the edge is coming over, find out which reach
2105           // states on it should come over, too
2106           Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2107           while( stateItr.hasNext() ) {
2108             ReachState stateCallee = stateItr.next();
2109
2110             predsIfSatis =
2111               stateCallee.getPreds().isSatisfiedBy( this,
2112                                                     callerNodeIDsCopiedToCallee
2113                                                     );
2114             if( predsIfSatis != null ) {
2115               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2116             }
2117           }
2118
2119         }
2120       }
2121     }
2122
2123
2124
2125
2126     if( writeDebugDOTs ) {
2127       try {
2128         writeGraph( "caller20BeforeWipe",
2129                     resolveMethodDebugDOTwriteLabels,
2130                     resolveMethodDebugDOTselectTemps,
2131                     resolveMethodDebugDOTpruneGarbage,
2132                     resolveMethodDebugDOThideSubsetReach,
2133                     resolveMethodDebugDOThideEdgeTaints );
2134       } catch( IOException e ) {}
2135     }
2136
2137
2138     // 2. predicates tested, ok to wipe out caller part
2139     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2140     while( hrnItr.hasNext() ) {
2141       Integer        hrnID     = hrnItr.next();
2142       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2143       assert hrnCaller != null;
2144
2145       // when clearing off nodes, also eliminate variable
2146       // references
2147       wipeOut( hrnCaller, true );
2148     }
2149
2150
2151
2152     if( writeDebugDOTs ) {
2153       try {
2154         writeGraph( "caller30BeforeAddingNodes",
2155                     resolveMethodDebugDOTwriteLabels,
2156                     resolveMethodDebugDOTselectTemps,
2157                     resolveMethodDebugDOTpruneGarbage,
2158                     resolveMethodDebugDOThideSubsetReach,
2159                     resolveMethodDebugDOThideEdgeTaints );
2160       } catch( IOException e ) {}
2161     }
2162
2163
2164     // 3. callee elements with satisfied preds come in, note that
2165     //    the mapping of elements satisfied to preds is like this:
2166     //    A callee element EE has preds EEp that are satisfied by
2167     //    some caller element ER.  We bring EE into the caller
2168     //    context as ERee with the preds of ER, namely ERp, which
2169     //    in the following algorithm is the value in the mapping
2170
2171     // 3.a) nodes
2172     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2173     while( satisItr.hasNext() ) {
2174       Map.Entry      me        = (Map.Entry)      satisItr.next();
2175       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2176       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
2177
2178       // TODO: I think its true that the current implementation uses
2179       // the type of the OOC region and the predicates OF THE EDGE from
2180       // it to link everything up in caller context, so that's why we're
2181       // skipping this... maybe that's a sillier way to do it?
2182       if( hrnCallee.isOutOfContext() ) {
2183         continue;
2184       }
2185
2186       AllocSite as = hrnCallee.getAllocSite();
2187       allocSites.add( as );
2188
2189       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2190
2191       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2192       if( hrnCaller == null ) {
2193         hrnCaller =
2194           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
2195                                    hrnCallee.isSingleObject(), // single object?
2196                                    hrnCallee.isNewSummary(),   // summary?
2197                                    hrnCallee.isFlagged(),      // flagged?
2198                                    false,                      // out-of-context?
2199                                    hrnCallee.getType(),        // type
2200                                    hrnCallee.getAllocSite(),   // allocation site
2201                                    toCallerContext( hrnCallee.getInherent(),
2202                                                     calleeStatesSatisfied  ),    // inherent reach
2203                                    null,                       // current reach
2204                                    predsEmpty,                 // predicates
2205                                    hrnCallee.getDescription()  // description
2206                                    );
2207       } else {
2208         assert hrnCaller.isWiped();
2209       }
2210
2211       hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2212                                            calleeStatesSatisfied
2213                                            )
2214                           );
2215
2216       hrnCaller.setPreds( preds );
2217     }
2218
2219
2220
2221     if( writeDebugDOTs ) {
2222       try {
2223         writeGraph( "caller31BeforeAddingEdges",
2224                     resolveMethodDebugDOTwriteLabels,
2225                     resolveMethodDebugDOTselectTemps,
2226                     resolveMethodDebugDOTpruneGarbage,
2227                     resolveMethodDebugDOThideSubsetReach,
2228                     resolveMethodDebugDOThideEdgeTaints );
2229       } catch( IOException e ) {}
2230     }
2231
2232
2233     // set these up during the next procedure so after
2234     // the caller has all of its nodes and edges put
2235     // back together we can propagate the callee's
2236     // reach changes backwards into the caller graph
2237     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2238
2239     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2240       new Hashtable<RefEdge, ChangeSet>();
2241
2242
2243     // 3.b) callee -> callee edges AND out-of-context -> callee
2244     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2245     while( satisItr.hasNext() ) {
2246       Map.Entry    me       = (Map.Entry)    satisItr.next();
2247       RefEdge      reCallee = (RefEdge)      me.getKey();
2248       ExistPredSet preds    = (ExistPredSet) me.getValue();
2249
2250       HeapRegionNode hrnDstCallee = reCallee.getDst();
2251       AllocSite      asDst        = hrnDstCallee.getAllocSite();
2252       allocSites.add( asDst );
2253
2254       Integer hrnIDDstShadow =
2255         asDst.getShadowIDfromID( hrnDstCallee.getID() );
2256
2257       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2258       assert hrnDstCaller != null;
2259
2260
2261       RefSrcNode rsnCallee = reCallee.getSrc();
2262
2263       Set<RefSrcNode> rsnCallers =
2264         new HashSet<RefSrcNode>();
2265
2266       Set<RefSrcNode> oocCallers =
2267         calleeEdges2oocCallerSrcMatches.get( reCallee );
2268
2269       boolean oocEdges = false;
2270
2271       if( oocCallers == null ) {
2272         // there are no out-of-context matches, so it's
2273         // either a param/arg var or one in-context heap region
2274         if( rsnCallee instanceof VariableNode ) {
2275           // variable -> node in the callee should only
2276           // come into the caller if its from a param var
2277           VariableNode   vnCallee = (VariableNode) rsnCallee;
2278           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2279           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
2280                                                             tdParam );
2281           if( tdArg == null ) {
2282             // this means the variable isn't a parameter, its local
2283             // to the callee so we ignore it in call site transfer
2284             // shouldn't this NEVER HAPPEN?
2285             assert false;
2286           }
2287           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2288           oocEdges = true;
2289
2290         } else {
2291           // otherwise source is in context, one region
2292           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2293
2294           // translate an in-context node to shadow
2295           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2296           allocSites.add( asSrc );
2297
2298           Integer hrnIDSrcShadow =
2299             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2300
2301           HeapRegionNode hrnSrcCallerShadow =
2302             this.id2hrn.get( hrnIDSrcShadow );
2303
2304           if( hrnSrcCallerShadow == null ) {
2305             hrnSrcCallerShadow =
2306               createNewHeapRegionNode( hrnIDSrcShadow,                // id or null to generate a new one
2307                                        hrnSrcCallee.isSingleObject(), // single object?
2308                                        hrnSrcCallee.isNewSummary(),   // summary?
2309                                        hrnSrcCallee.isFlagged(),      // flagged?
2310                                        false,                         // out-of-context?
2311                                        hrnSrcCallee.getType(),        // type
2312                                        hrnSrcCallee.getAllocSite(),   // allocation site
2313                                        toCallerContext( hrnSrcCallee.getInherent(),
2314                                                         calleeStatesSatisfied ),    // inherent reach
2315                                        toCallerContext( hrnSrcCallee.getAlpha(),
2316                                                         calleeStatesSatisfied ),       // current reach
2317                                        predsEmpty,                    // predicates
2318                                        hrnSrcCallee.getDescription()  // description
2319                                        );
2320           }
2321
2322           rsnCallers.add( hrnSrcCallerShadow );
2323         }
2324
2325       } else {
2326         // otherwise we have a set of out-of-context srcs
2327         // that should NOT be translated to shadow nodes
2328         assert !oocCallers.isEmpty();
2329         rsnCallers.addAll( oocCallers );
2330         oocEdges = true;
2331       }
2332
2333       // now make all caller edges we've identified from
2334       // this callee edge with a satisfied predicate
2335       assert !rsnCallers.isEmpty();
2336       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2337       while( rsnItr.hasNext() ) {
2338         RefSrcNode rsnCaller = rsnItr.next();
2339
2340         RefEdge reCaller = new RefEdge( rsnCaller,
2341                                         hrnDstCaller,
2342                                         reCallee.getType(),
2343                                         reCallee.getField(),
2344                                         toCallerContext( reCallee.getBeta(),
2345                                                          calleeStatesSatisfied ),
2346                                         preds
2347                                         );
2348
2349         ChangeSet cs = ChangeSet.factory();
2350         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2351         while( rsItr.hasNext() ) {
2352           ReachState   state          = rsItr.next();
2353           ExistPredSet predsPreCallee = state.getPreds();
2354
2355           if( state.isEmpty() ) {
2356             continue;
2357           }
2358
2359           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2360           while( predItr.hasNext() ) {
2361             ExistPred pred = predItr.next();
2362             ReachState old = pred.ne_state;
2363
2364             if( old == null ) {
2365               old = rstateEmpty;
2366             }
2367
2368             cs = Canonical.add( cs,
2369                                 ChangeTuple.factory( old,
2370                                                      state
2371                                                      )
2372                                 );
2373           }
2374         }
2375
2376
2377         // look to see if an edge with same field exists
2378         // and merge with it, otherwise just add the edge
2379         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2380                                                          reCallee.getType(),
2381                                                          reCallee.getField()
2382                                                          );
2383         if( edgeExisting != null ) {
2384           edgeExisting.setBeta(
2385                                Canonical.unionORpreds( edgeExisting.getBeta(),
2386                                                 reCaller.getBeta()
2387                                                 )
2388                                );
2389           edgeExisting.setPreds(
2390                                 Canonical.join( edgeExisting.getPreds(),
2391                                                 reCaller.getPreds()
2392                                                 )
2393                                 );
2394
2395           // for reach propagation
2396           if( !cs.isEmpty() ) {
2397             edgePlannedChanges.put(
2398                                    edgeExisting,
2399                                    Canonical.union( edgePlannedChanges.get( edgeExisting ),
2400                                                     cs
2401                                                     )
2402                                     );
2403           }
2404
2405         } else {
2406           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2407
2408           // for reach propagation
2409           if( !cs.isEmpty() ) {
2410             edgesForPropagation.add( reCaller );
2411             assert !edgePlannedChanges.containsKey( reCaller );
2412             edgePlannedChanges.put( reCaller, cs );
2413           }
2414         }
2415       }
2416     }
2417
2418
2419
2420
2421
2422     if( writeDebugDOTs ) {
2423       try {
2424         writeGraph( "caller35BeforeAssignReturnValue",
2425                     resolveMethodDebugDOTwriteLabels,
2426                     resolveMethodDebugDOTselectTemps,
2427                     resolveMethodDebugDOTpruneGarbage,
2428                     resolveMethodDebugDOThideSubsetReach,
2429                     resolveMethodDebugDOThideEdgeTaints );
2430       } catch( IOException e ) {}
2431     }
2432
2433
2434
2435     // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2436     // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2437     // EDGES, JUST BRINGING THEM ALL!  It'll work for now, over approximation
2438
2439     // 3.d) handle return value assignment if needed
2440     TempDescriptor returnTemp = fc.getReturnTemp();
2441     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2442
2443       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2444       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2445
2446       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2447       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2448       while( reCalleeItr.hasNext() ) {
2449         RefEdge        reCallee     = reCalleeItr.next();
2450         HeapRegionNode hrnDstCallee = reCallee.getDst();
2451
2452         // some edge types are not possible return values when we can
2453         // see what type variable we are assigning it to
2454         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2455           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2456                               reCallee+" for return temp "+returnTemp );
2457           // prune
2458           continue;
2459         }
2460
2461         AllocSite asDst = hrnDstCallee.getAllocSite();
2462         allocSites.add( asDst );
2463
2464         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2465
2466         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2467         if( hrnDstCaller == null ) {
2468           hrnDstCaller =
2469             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
2470                                      hrnDstCallee.isSingleObject(), // single object?
2471                                      hrnDstCallee.isNewSummary(),   // summary?
2472                                      hrnDstCallee.isFlagged(),      // flagged?
2473                                      false,                         // out-of-context?
2474                                      hrnDstCallee.getType(),        // type
2475                                      hrnDstCallee.getAllocSite(),   // allocation site
2476                                      toCallerContext( hrnDstCallee.getInherent(),
2477                                                       calleeStatesSatisfied  ),    // inherent reach
2478                                      toCallerContext( hrnDstCallee.getAlpha(),
2479                                                       calleeStatesSatisfied  ),    // current reach
2480                                      predsTrue,                     // predicates
2481                                      hrnDstCallee.getDescription()  // description
2482                                      );
2483         } else {
2484           assert hrnDstCaller.isWiped();
2485         }
2486
2487         TypeDescriptor tdNewEdge =
2488           mostSpecificType( reCallee.getType(),
2489                             hrnDstCallee.getType(),
2490                             hrnDstCaller.getType()
2491                             );
2492
2493         RefEdge reCaller = new RefEdge( vnLhsCaller,
2494                                         hrnDstCaller,
2495                                         tdNewEdge,
2496                                         null,
2497                                         toCallerContext( reCallee.getBeta(),
2498                                                          calleeStatesSatisfied ),
2499                                         predsTrue
2500                                         );
2501
2502         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2503       }
2504     }
2505
2506
2507
2508     if( writeDebugDOTs ) {
2509       try {
2510         writeGraph( "caller38propagateReach",
2511                     resolveMethodDebugDOTwriteLabels,
2512                     resolveMethodDebugDOTselectTemps,
2513                     resolveMethodDebugDOTpruneGarbage,
2514                     resolveMethodDebugDOThideSubsetReach,
2515                     resolveMethodDebugDOThideEdgeTaints );
2516       } catch( IOException e ) {}
2517     }
2518
2519     // propagate callee reachability changes to the rest
2520     // of the caller graph edges
2521     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2522
2523     propagateTokensOverEdges( edgesForPropagation, // source edges
2524                               edgePlannedChanges,  // map src edge to change set
2525                               edgesUpdated );      // list of updated edges
2526
2527     // commit beta' (beta<-betaNew)
2528     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2529     while( edgeItr.hasNext() ) {
2530       edgeItr.next().applyBetaNew();
2531     }
2532
2533
2534
2535
2536
2537
2538     if( writeDebugDOTs ) {
2539       try {
2540         writeGraph( "caller40BeforeShadowMerge",
2541                     resolveMethodDebugDOTwriteLabels,
2542                     resolveMethodDebugDOTselectTemps,
2543                     resolveMethodDebugDOTpruneGarbage,
2544                     resolveMethodDebugDOThideSubsetReach,
2545                     resolveMethodDebugDOThideEdgeTaints );
2546       } catch( IOException e ) {}
2547     }
2548
2549
2550     // 4) merge shadow nodes so alloc sites are back to k
2551     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2552     while( asItr.hasNext() ) {
2553       // for each allocation site do the following to merge
2554       // shadow nodes (newest from callee) with any existing
2555       // look for the newest normal and newest shadow "slot"
2556       // not being used, transfer normal to shadow.  Keep
2557       // doing this until there are no more normal nodes, or
2558       // no empty shadow slots: then merge all remaining normal
2559       // nodes into the shadow summary.  Finally, convert all
2560       // shadow to their normal versions.
2561       AllocSite as = asItr.next();
2562       int ageNorm = 0;
2563       int ageShad = 0;
2564       while( ageNorm < allocationDepth &&
2565              ageShad < allocationDepth ) {
2566
2567         // first, are there any normal nodes left?
2568         Integer        idNorm  = as.getIthOldest( ageNorm );
2569         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2570         if( hrnNorm == null ) {
2571           // no, this age of normal node not in the caller graph
2572           ageNorm++;
2573           continue;
2574         }
2575
2576         // yes, a normal node exists, is there an empty shadow
2577         // "slot" to transfer it onto?
2578         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2579         if( !hrnShad.isWiped() ) {
2580           // no, this age of shadow node is not empty
2581           ageShad++;
2582           continue;
2583         }
2584
2585         // yes, this shadow node is empty
2586         transferOnto( hrnNorm, hrnShad );
2587         ageNorm++;
2588         ageShad++;
2589       }
2590
2591       // now, while there are still normal nodes but no shadow
2592       // slots, merge normal nodes into the shadow summary
2593       while( ageNorm < allocationDepth ) {
2594
2595         // first, are there any normal nodes left?
2596         Integer        idNorm  = as.getIthOldest( ageNorm );
2597         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2598         if( hrnNorm == null ) {
2599           // no, this age of normal node not in the caller graph
2600           ageNorm++;
2601           continue;
2602         }
2603
2604         // yes, a normal node exists, so get the shadow summary
2605         HeapRegionNode summShad = getSummaryNode( as, true );
2606         mergeIntoSummary( hrnNorm, summShad );
2607         ageNorm++;
2608       }
2609
2610       // if there is a normal summary, merge it into shadow summary
2611       Integer        idNorm   = as.getSummary();
2612       HeapRegionNode summNorm = id2hrn.get( idNorm );
2613       if( summNorm != null ) {
2614         HeapRegionNode summShad = getSummaryNode( as, true );
2615         mergeIntoSummary( summNorm, summShad );
2616       }
2617
2618       // finally, flip all existing shadow nodes onto the normal
2619       for( int i = 0; i < allocationDepth; ++i ) {
2620         Integer        idShad  = as.getIthOldestShadow( i );
2621         HeapRegionNode hrnShad = id2hrn.get( idShad );
2622         if( hrnShad != null ) {
2623           // flip it
2624           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2625           assert hrnNorm.isWiped();
2626           transferOnto( hrnShad, hrnNorm );
2627         }
2628       }
2629
2630       Integer        idShad   = as.getSummaryShadow();
2631       HeapRegionNode summShad = id2hrn.get( idShad );
2632       if( summShad != null ) {
2633         summNorm = getSummaryNode( as, false );
2634         transferOnto( summShad, summNorm );
2635       }
2636     }
2637
2638
2639     if( writeDebugDOTs ) {
2640       try {
2641         writeGraph( "caller45BeforeUnshadow",
2642                     resolveMethodDebugDOTwriteLabels,
2643                     resolveMethodDebugDOTselectTemps,
2644                     resolveMethodDebugDOTpruneGarbage,
2645                     resolveMethodDebugDOThideSubsetReach,
2646                     resolveMethodDebugDOThideEdgeTaints );
2647       } catch( IOException e ) {}
2648     }
2649
2650
2651     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2652     while( itrAllHRNodes.hasNext() ) {
2653       Map.Entry      me  = (Map.Entry)      itrAllHRNodes.next();
2654       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2655
2656       hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2657
2658       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2659       while( itrEdges.hasNext() ) {
2660         RefEdge re = itrEdges.next();
2661         re.setBeta( unshadow( re.getBeta() ) );
2662       }
2663     }
2664
2665
2666
2667     if( writeDebugDOTs ) {
2668       try {
2669         writeGraph( "caller50BeforeGlobalSweep",
2670                     resolveMethodDebugDOTwriteLabels,
2671                     resolveMethodDebugDOTselectTemps,
2672                     resolveMethodDebugDOTpruneGarbage,
2673                     resolveMethodDebugDOThideSubsetReach,
2674                     resolveMethodDebugDOThideEdgeTaints );
2675       } catch( IOException e ) {}
2676     }
2677
2678
2679     // 5.
2680     if( !DISABLE_GLOBAL_SWEEP ) {
2681       globalSweep();
2682     }
2683
2684
2685
2686     if( writeDebugDOTs ) {
2687       try {
2688         writeGraph( "caller90AfterTransfer",
2689                     resolveMethodDebugDOTwriteLabels,
2690                     resolveMethodDebugDOTselectTemps,
2691                     resolveMethodDebugDOTpruneGarbage,
2692                     resolveMethodDebugDOThideSubsetReach,
2693                     resolveMethodDebugDOThideEdgeTaints );
2694       } catch( IOException e ) {}
2695     }
2696   }
2697
2698
2699
2700   ////////////////////////////////////////////////////
2701   //
2702   //  Abstract garbage collection simply removes
2703   //  heap region nodes that are not mechanically
2704   //  reachable from a root set.  This step is
2705   //  essential for testing node and edge existence
2706   //  predicates efficiently
2707   //
2708   ////////////////////////////////////////////////////
2709   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2710
2711     // calculate a root set, will be different for Java
2712     // version of analysis versus Bamboo version
2713     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2714
2715     // visit every variable in graph while building root
2716     // set, and do iterating on a copy, so we can remove
2717     // dead variables while we're at this
2718     Iterator makeCopyItr = td2vn.entrySet().iterator();
2719     Set      entrysCopy  = new HashSet();
2720     while( makeCopyItr.hasNext() ) {
2721       entrysCopy.add( makeCopyItr.next() );
2722     }
2723
2724     Iterator eItr = entrysCopy.iterator();
2725     while( eItr.hasNext() ) {
2726       Map.Entry      me = (Map.Entry)      eItr.next();
2727       TempDescriptor td = (TempDescriptor) me.getKey();
2728       VariableNode   vn = (VariableNode)   me.getValue();
2729
2730       if( liveSet.contains( td ) ) {
2731         toVisit.add( vn );
2732
2733       } else {
2734         // dead var, remove completely from graph
2735         td2vn.remove( td );
2736         clearRefEdgesFrom( vn, null, null, true );
2737       }
2738     }
2739
2740     // everything visited in a traversal is
2741     // considered abstractly live
2742     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2743
2744     while( !toVisit.isEmpty() ) {
2745       RefSrcNode rsn = toVisit.iterator().next();
2746       toVisit.remove( rsn );
2747       visited.add( rsn );
2748
2749       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2750       while( hrnItr.hasNext() ) {
2751         RefEdge        edge = hrnItr.next();
2752         HeapRegionNode hrn  = edge.getDst();
2753
2754         if( !visited.contains( hrn ) ) {
2755           toVisit.add( hrn );
2756         }
2757       }
2758     }
2759
2760     // get a copy of the set to iterate over because
2761     // we're going to monkey with the graph when we
2762     // identify a garbage node
2763     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2764     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2765     while( hrnItr.hasNext() ) {
2766       hrnAllPrior.add( hrnItr.next() );
2767     }
2768
2769     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2770     while( hrnAllItr.hasNext() ) {
2771       HeapRegionNode hrn = hrnAllItr.next();
2772
2773       if( !visited.contains( hrn ) ) {
2774
2775         // heap region nodes are compared across ReachGraph
2776         // objects by their integer ID, so when discarding
2777         // garbage nodes we must also discard entries in
2778         // the ID -> heap region hashtable.
2779         id2hrn.remove( hrn.getID() );
2780
2781         // RefEdge objects are two-way linked between
2782         // nodes, so when a node is identified as garbage,
2783         // actively clear references to and from it so
2784         // live nodes won't have dangling RefEdge's
2785         wipeOut( hrn, true );
2786
2787         // if we just removed the last node from an allocation
2788         // site, it should be taken out of the ReachGraph's list
2789         AllocSite as = hrn.getAllocSite();
2790         if( !hasNodesOf( as ) ) {
2791           allocSites.remove( as );
2792         }
2793       }
2794     }
2795   }
2796
2797   protected boolean hasNodesOf( AllocSite as ) {
2798     if( id2hrn.containsKey( as.getSummary() ) ) {
2799       return true;
2800     }
2801
2802     for( int i = 0; i < allocationDepth; ++i ) {
2803       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2804         return true;
2805       }
2806     }
2807     return false;
2808   }
2809
2810
2811   ////////////////////////////////////////////////////
2812   //
2813   //  This global sweep is an optional step to prune
2814   //  reachability sets that are not internally
2815   //  consistent with the global graph.  It should be
2816   //  invoked after strong updates or method calls.
2817   //
2818   ////////////////////////////////////////////////////
2819   public void globalSweep() {
2820
2821     // boldB is part of the phase 1 sweep
2822     // it has an in-context table and an out-of-context table
2823     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2824       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2825
2826     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2827       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2828
2829     // visit every heap region to initialize alphaNew and betaNew,
2830     // and make a map of every hrnID to the source nodes it should
2831     // propagate forward from.  In-context flagged hrnID's propagate
2832     // from only the in-context node they name, but out-of-context
2833     // ID's may propagate from several out-of-context nodes
2834     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2835       new Hashtable< Integer, Set<HeapRegionNode> >();
2836
2837     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2838       new Hashtable< Integer, Set<HeapRegionNode> >();
2839
2840
2841     Iterator itrHrns = id2hrn.entrySet().iterator();
2842     while( itrHrns.hasNext() ) {
2843       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2844       Integer        hrnID = (Integer)        me.getKey();
2845       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2846
2847       // assert that this node and incoming edges have clean alphaNew
2848       // and betaNew sets, respectively
2849       assert rsetEmpty.equals( hrn.getAlphaNew() );
2850
2851       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2852       while( itrRers.hasNext() ) {
2853         RefEdge edge = itrRers.next();
2854         assert rsetEmpty.equals( edge.getBetaNew() );
2855       }
2856
2857       // calculate boldB for this flagged node, or out-of-context node
2858       if( hrn.isFlagged() ) {
2859         assert !hrn.isOutOfContext();
2860         assert !icID2srcs.containsKey( hrn.getID() );
2861         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2862         srcs.add( hrn );
2863         icID2srcs.put( hrn.getID(), srcs );
2864       }
2865
2866       if( hrn.isOutOfContext() ) {
2867         assert !hrn.isFlagged();
2868
2869         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2870         while( stateItr.hasNext() ) {
2871           ReachState state = stateItr.next();
2872
2873           Iterator<ReachTuple> rtItr = state.iterator();
2874           while( rtItr.hasNext() ) {
2875             ReachTuple rt = rtItr.next();
2876             assert rt.isOutOfContext();
2877
2878             Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2879             if( srcs == null ) {
2880               srcs = new HashSet<HeapRegionNode>();
2881             }
2882             srcs.add( hrn );
2883             oocID2srcs.put( rt.getHrnID(), srcs );
2884           }
2885         }
2886       }
2887     }
2888
2889     // calculate boldB for all hrnIDs identified by the above
2890     // node traversal, propagating from every source
2891     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2892
2893       Integer             hrnID;
2894       Set<HeapRegionNode> srcs;
2895       boolean             inContext;
2896
2897       if( !icID2srcs.isEmpty() ) {
2898         Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2899         hrnID = (Integer)             me.getKey();
2900         srcs  = (Set<HeapRegionNode>) me.getValue();
2901         inContext = true;
2902         icID2srcs.remove( hrnID );
2903
2904       } else {
2905         assert !oocID2srcs.isEmpty();
2906
2907         Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2908         hrnID = (Integer)             me.getKey();
2909         srcs  = (Set<HeapRegionNode>) me.getValue();
2910         inContext = false;
2911         oocID2srcs.remove( hrnID );
2912       }
2913
2914
2915       Hashtable<RefEdge, ReachSet> boldB_f =
2916         new Hashtable<RefEdge, ReachSet>();
2917
2918       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2919
2920       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2921       while( hrnItr.hasNext() ) {
2922         HeapRegionNode hrn = hrnItr.next();
2923
2924         assert workSetEdges.isEmpty();
2925
2926         // initial boldB_f constraints
2927         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2928         while( itrRees.hasNext() ) {
2929           RefEdge edge = itrRees.next();
2930
2931           assert !boldB_f.containsKey( edge );
2932           boldB_f.put( edge, edge.getBeta() );
2933
2934           assert !workSetEdges.contains( edge );
2935           workSetEdges.add( edge );
2936         }
2937
2938         // enforce the boldB_f constraint at edges until we reach a fixed point
2939         while( !workSetEdges.isEmpty() ) {
2940           RefEdge edge = workSetEdges.iterator().next();
2941           workSetEdges.remove( edge );
2942
2943           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2944           while( itrPrime.hasNext() ) {
2945             RefEdge edgePrime = itrPrime.next();
2946
2947             ReachSet prevResult   = boldB_f.get( edgePrime );
2948             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2949                                                             edgePrime.getBeta()
2950                                                             );
2951
2952             if( prevResult == null ||
2953                 Canonical.unionORpreds( prevResult,
2954                                         intersection ).size()
2955                 > prevResult.size()
2956                 ) {
2957
2958               if( prevResult == null ) {
2959                 boldB_f.put( edgePrime,
2960                              Canonical.unionORpreds( edgePrime.getBeta(),
2961                                                      intersection
2962                                                      )
2963                              );
2964               } else {
2965                 boldB_f.put( edgePrime,
2966                              Canonical.unionORpreds( prevResult,
2967                                                      intersection
2968                                                      )
2969                              );
2970               }
2971               workSetEdges.add( edgePrime );
2972             }
2973           }
2974         }
2975       }
2976
2977       if( inContext ) {
2978         boldBic.put( hrnID, boldB_f );
2979       } else {
2980         boldBooc.put( hrnID, boldB_f );
2981       }
2982     }
2983
2984
2985     // use boldB to prune hrnIDs from alpha states that are impossible
2986     // and propagate the differences backwards across edges
2987     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2988
2989     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2990       new Hashtable<RefEdge, ChangeSet>();
2991
2992
2993     itrHrns = id2hrn.entrySet().iterator();
2994     while( itrHrns.hasNext() ) {
2995       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2996       Integer        hrnID = (Integer)        me.getKey();
2997       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2998
2999       // out-of-context nodes don't participate in the
3000       // global sweep, they serve as sources for the pass
3001       // performed above
3002       if( hrn.isOutOfContext() ) {
3003         continue;
3004       }
3005
3006       // the inherent states of a region are the exception
3007       // to removal as the global sweep prunes
3008       ReachTuple rtException = ReachTuple.factory( hrnID,
3009                                                    !hrn.isSingleObject(),
3010                                                    ReachTuple.ARITY_ONE,
3011                                                    false // out-of-context
3012                                                    );
3013
3014       ChangeSet cts = ChangeSet.factory();
3015
3016       // mark hrnIDs for removal
3017       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3018       while( stateItr.hasNext() ) {
3019         ReachState stateOld = stateItr.next();
3020
3021         ReachState markedHrnIDs = ReachState.factory();
3022
3023         Iterator<ReachTuple> rtItr = stateOld.iterator();
3024         while( rtItr.hasNext() ) {
3025           ReachTuple rtOld = rtItr.next();
3026
3027           // never remove the inherent hrnID from a flagged region
3028           // because it is trivially satisfied
3029           if( hrn.isFlagged() ) {
3030             if( rtOld == rtException ) {
3031               continue;
3032             }
3033           }
3034
3035           // does boldB allow this hrnID?
3036           boolean foundState = false;
3037           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3038           while( incidentEdgeItr.hasNext() ) {
3039             RefEdge incidentEdge = incidentEdgeItr.next();
3040
3041             Hashtable<RefEdge, ReachSet> B;
3042             if( rtOld.isOutOfContext() ) {
3043               B = boldBooc.get( rtOld.getHrnID() );
3044             } else {
3045               assert id2hrn.containsKey( rtOld.getHrnID() );
3046               B = boldBic.get( rtOld.getHrnID() );
3047             }
3048
3049             if( B != null ) {
3050               ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3051               if( boldB_rtOld_incident != null &&
3052                   boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3053                   ) {
3054                 foundState = true;
3055               }
3056             }
3057           }
3058
3059           if( !foundState ) {
3060             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3061           }
3062         }
3063
3064         // if there is nothing marked, just move on
3065         if( markedHrnIDs.isEmpty() ) {
3066           hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3067                                           stateOld
3068                                           )
3069                            );
3070           continue;
3071         }
3072
3073         // remove all marked hrnIDs and establish a change set that should
3074         // propagate backwards over edges from this node
3075         ReachState statePruned = ReachState.factory();
3076         rtItr = stateOld.iterator();
3077         while( rtItr.hasNext() ) {
3078           ReachTuple rtOld = rtItr.next();
3079
3080           if( !markedHrnIDs.containsTuple( rtOld ) ) {
3081             statePruned = Canonical.add( statePruned, rtOld );
3082           }
3083         }
3084         assert !stateOld.equals( statePruned );
3085
3086         hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3087                                         statePruned
3088                                         )
3089                          );
3090         ChangeTuple ct = ChangeTuple.factory( stateOld,
3091                                               statePruned
3092                                               );
3093         cts = Canonical.add( cts, ct );
3094       }
3095
3096       // throw change tuple set on all incident edges
3097       if( !cts.isEmpty() ) {
3098         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3099         while( incidentEdgeItr.hasNext() ) {
3100           RefEdge incidentEdge = incidentEdgeItr.next();
3101
3102           edgesForPropagation.add( incidentEdge );
3103
3104           if( edgePlannedChanges.get( incidentEdge ) == null ) {
3105             edgePlannedChanges.put( incidentEdge, cts );
3106           } else {
3107             edgePlannedChanges.put(
3108                                    incidentEdge,
3109                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
3110                                                     cts
3111                                                     )
3112                                     );
3113           }
3114         }
3115       }
3116     }
3117
3118     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3119
3120     propagateTokensOverEdges( edgesForPropagation,
3121                               edgePlannedChanges,
3122                               edgesUpdated );
3123
3124     // at the end of the 1st phase reference edges have
3125     // beta, betaNew that correspond to beta and betaR
3126     //
3127     // commit beta<-betaNew, so beta=betaR and betaNew
3128     // will represent the beta' calculation in 2nd phase
3129     //
3130     // commit alpha<-alphaNew because it won't change
3131     HashSet<RefEdge> res = new HashSet<RefEdge>();
3132
3133     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3134     while( nodeItr.hasNext() ) {
3135       HeapRegionNode hrn = nodeItr.next();
3136       hrn.applyAlphaNew();
3137       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3138       while( itrRes.hasNext() ) {
3139         res.add( itrRes.next() );
3140       }
3141     }
3142
3143
3144     // 2nd phase
3145     Iterator<RefEdge> edgeItr = res.iterator();
3146     while( edgeItr.hasNext() ) {
3147       RefEdge        edge = edgeItr.next();
3148       HeapRegionNode hrn  = edge.getDst();
3149
3150       // commit results of last phase
3151       if( edgesUpdated.contains( edge ) ) {
3152         edge.applyBetaNew();
3153       }
3154
3155       // compute intial condition of 2nd phase
3156       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3157                                                hrn.getAlpha()
3158                                                )
3159                        );
3160     }
3161
3162     // every edge in the graph is the initial workset
3163     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3164     while( !edgeWorkSet.isEmpty() ) {
3165       RefEdge edgePrime = edgeWorkSet.iterator().next();
3166       edgeWorkSet.remove( edgePrime );
3167
3168       RefSrcNode rsn = edgePrime.getSrc();
3169       if( !(rsn instanceof HeapRegionNode) ) {
3170         continue;
3171       }
3172       HeapRegionNode hrn = (HeapRegionNode) rsn;
3173
3174       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3175       while( itrEdge.hasNext() ) {
3176         RefEdge edge = itrEdge.next();
3177
3178         ReachSet prevResult = edge.getBetaNew();
3179         assert prevResult != null;
3180
3181         ReachSet intersection =
3182           Canonical.intersection( edge.getBeta(),
3183                                   edgePrime.getBetaNew()
3184                                   );
3185
3186         if( Canonical.unionORpreds( prevResult,
3187                                     intersection
3188                                     ).size()
3189             > prevResult.size()
3190             ) {
3191
3192           edge.setBetaNew(
3193                           Canonical.unionORpreds( prevResult,
3194                                                   intersection
3195                                                   )
3196                            );
3197           edgeWorkSet.add( edge );
3198         }
3199       }
3200     }
3201
3202     // commit beta' (beta<-betaNew)
3203     edgeItr = res.iterator();
3204     while( edgeItr.hasNext() ) {
3205       edgeItr.next().applyBetaNew();
3206     }
3207   }
3208
3209
3210
3211   ////////////////////////////////////////////////////
3212   // high-level merge operations
3213   ////////////////////////////////////////////////////
3214   public void merge_sameMethodContext( ReachGraph rg ) {
3215     // when merging two graphs that abstract the heap
3216     // of the same method context, we just call the
3217     // basic merge operation
3218     merge( rg );
3219   }
3220
3221   public void merge_diffMethodContext( ReachGraph rg ) {
3222     // when merging graphs for abstract heaps in
3223     // different method contexts we should:
3224     // 1) age the allocation sites?
3225     merge( rg );
3226   }
3227
3228   ////////////////////////////////////////////////////
3229   // in merge() and equals() methods the suffix A
3230   // represents the passed in graph and the suffix
3231   // B refers to the graph in this object
3232   // Merging means to take the incoming graph A and
3233   // merge it into B, so after the operation graph B
3234   // is the final result.
3235   ////////////////////////////////////////////////////
3236   protected void merge( ReachGraph rg ) {
3237
3238     if( rg == null ) {
3239       return;
3240     }
3241
3242     mergeNodes     ( rg );
3243     mergeRefEdges  ( rg );
3244     mergeAllocSites( rg );
3245   }
3246
3247   protected void mergeNodes( ReachGraph rg ) {
3248
3249     // start with heap region nodes
3250     Set      sA = rg.id2hrn.entrySet();
3251     Iterator iA = sA.iterator();
3252     while( iA.hasNext() ) {
3253       Map.Entry      meA  = (Map.Entry)      iA.next();
3254       Integer        idA  = (Integer)        meA.getKey();
3255       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3256
3257       // if this graph doesn't have a node the
3258       // incoming graph has, allocate it
3259       if( !id2hrn.containsKey( idA ) ) {
3260         HeapRegionNode hrnB = hrnA.copy();
3261         id2hrn.put( idA, hrnB );
3262
3263       } else {
3264         // otherwise this is a node present in both graphs
3265         // so make the new reachability set a union of the
3266         // nodes' reachability sets
3267         HeapRegionNode hrnB = id2hrn.get( idA );
3268         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3269                                         hrnA.getAlpha()
3270                                         )
3271                        );
3272
3273         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3274                                        hrnA.getPreds()
3275                                        )
3276                        );
3277       }
3278     }
3279
3280     // now add any variable nodes that are in graph B but
3281     // not in A
3282     sA = rg.td2vn.entrySet();
3283     iA = sA.iterator();
3284     while( iA.hasNext() ) {
3285       Map.Entry      meA = (Map.Entry)      iA.next();
3286       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3287       VariableNode   lnA = (VariableNode)   meA.getValue();
3288
3289       // if the variable doesn't exist in B, allocate and add it
3290       VariableNode lnB = getVariableNodeFromTemp( tdA );
3291     }
3292   }
3293
3294   protected void mergeRefEdges( ReachGraph rg ) {
3295
3296     // between heap regions
3297     Set      sA = rg.id2hrn.entrySet();
3298     Iterator iA = sA.iterator();
3299     while( iA.hasNext() ) {
3300       Map.Entry      meA  = (Map.Entry)      iA.next();
3301       Integer        idA  = (Integer)        meA.getKey();
3302       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3303
3304       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3305       while( heapRegionsItrA.hasNext() ) {
3306         RefEdge        edgeA     = heapRegionsItrA.next();
3307         HeapRegionNode hrnChildA = edgeA.getDst();
3308         Integer        idChildA  = hrnChildA.getID();
3309
3310         // at this point we know an edge in graph A exists
3311         // idA -> idChildA, does this exist in B?
3312         assert id2hrn.containsKey( idA );
3313         HeapRegionNode hrnB        = id2hrn.get( idA );
3314         RefEdge        edgeToMerge = null;
3315
3316         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3317         while( heapRegionsItrB.hasNext() &&
3318                edgeToMerge == null          ) {
3319
3320           RefEdge        edgeB     = heapRegionsItrB.next();
3321           HeapRegionNode hrnChildB = edgeB.getDst();
3322           Integer        idChildB  = hrnChildB.getID();
3323
3324           // don't use the RefEdge.equals() here because
3325           // we're talking about existence between graphs,
3326           // not intragraph equal
3327           if( idChildB.equals( idChildA ) &&
3328               edgeB.typeAndFieldEquals( edgeA ) ) {
3329
3330             edgeToMerge = edgeB;
3331           }
3332         }
3333
3334         // if the edge from A was not found in B,
3335         // add it to B.
3336         if( edgeToMerge == null ) {
3337           assert id2hrn.containsKey( idChildA );
3338           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3339           edgeToMerge = edgeA.copy();
3340           edgeToMerge.setSrc( hrnB );
3341           edgeToMerge.setDst( hrnChildB );
3342           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3343         }
3344         // otherwise, the edge already existed in both graphs
3345         // so merge their reachability sets
3346         else {
3347           // just replace this beta set with the union
3348           assert edgeToMerge != null;
3349           edgeToMerge.setBeta(
3350                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3351                                                edgeA.getBeta()
3352                                                )
3353                               );
3354           edgeToMerge.setPreds(
3355                                Canonical.join( edgeToMerge.getPreds(),
3356                                                edgeA.getPreds()
3357                                                )
3358                                );
3359         }
3360       }
3361     }
3362
3363     // and then again from variable nodes
3364     sA = rg.td2vn.entrySet();
3365     iA = sA.iterator();
3366     while( iA.hasNext() ) {
3367       Map.Entry      meA = (Map.Entry)      iA.next();
3368       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3369       VariableNode   vnA = (VariableNode)   meA.getValue();
3370
3371       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3372       while( heapRegionsItrA.hasNext() ) {
3373         RefEdge        edgeA     = heapRegionsItrA.next();
3374         HeapRegionNode hrnChildA = edgeA.getDst();
3375         Integer        idChildA  = hrnChildA.getID();
3376
3377         // at this point we know an edge in graph A exists
3378         // tdA -> idChildA, does this exist in B?
3379         assert td2vn.containsKey( tdA );
3380         VariableNode vnB         = td2vn.get( tdA );
3381         RefEdge      edgeToMerge = null;
3382
3383         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3384         while( heapRegionsItrB.hasNext() &&
3385                edgeToMerge == null          ) {
3386
3387           RefEdge        edgeB     = heapRegionsItrB.next();
3388           HeapRegionNode hrnChildB = edgeB.getDst();
3389           Integer        idChildB  = hrnChildB.getID();
3390
3391           // don't use the RefEdge.equals() here because
3392           // we're talking about existence between graphs
3393           if( idChildB.equals( idChildA ) &&
3394               edgeB.typeAndFieldEquals( edgeA ) ) {
3395
3396             edgeToMerge = edgeB;
3397           }
3398         }
3399
3400         // if the edge from A was not found in B,
3401         // add it to B.
3402         if( edgeToMerge == null ) {
3403           assert id2hrn.containsKey( idChildA );
3404           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3405           edgeToMerge = edgeA.copy();
3406           edgeToMerge.setSrc( vnB );
3407           edgeToMerge.setDst( hrnChildB );
3408           addRefEdge( vnB, hrnChildB, edgeToMerge );
3409         }
3410         // otherwise, the edge already existed in both graphs
3411         // so merge their reachability sets
3412         else {
3413           // just replace this beta set with the union
3414           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3415                                                 edgeA.getBeta()
3416                                                 )
3417                                );
3418           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3419                                                 edgeA.getPreds()
3420                                                 )
3421                                 );
3422         }
3423       }
3424     }
3425   }
3426
3427   protected void mergeAllocSites( ReachGraph rg ) {
3428     allocSites.addAll( rg.allocSites );
3429   }
3430
3431
3432   // it is necessary in the equals() member functions
3433   // to "check both ways" when comparing the data
3434   // structures of two graphs.  For instance, if all
3435   // edges between heap region nodes in graph A are
3436   // present and equal in graph B it is not sufficient
3437   // to say the graphs are equal.  Consider that there
3438   // may be edges in graph B that are not in graph A.
3439   // the only way to know that all edges in both graphs
3440   // are equally present is to iterate over both data
3441   // structures and compare against the other graph.
3442   public boolean equals( ReachGraph rg ) {
3443
3444     if( rg == null ) {
3445       return false;
3446     }
3447
3448     if( !areHeapRegionNodesEqual( rg ) ) {
3449       return false;
3450     }
3451
3452     if( !areVariableNodesEqual( rg ) ) {
3453       return false;
3454     }
3455
3456     if( !areRefEdgesEqual( rg ) ) {
3457       return false;
3458     }
3459
3460     // if everything is equal up to this point,
3461     // assert that allocSites is also equal--
3462     // this data is redundant but kept for efficiency
3463     assert allocSites.equals( rg.allocSites );
3464
3465     return true;
3466   }
3467
3468
3469   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3470
3471     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3472       return false;
3473     }
3474
3475     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3476       return false;
3477     }
3478
3479     return true;
3480   }
3481
3482   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3483                                                         ReachGraph rgB ) {
3484     Set      sA = rgA.id2hrn.entrySet();
3485     Iterator iA = sA.iterator();
3486     while( iA.hasNext() ) {
3487       Map.Entry      meA  = (Map.Entry)      iA.next();
3488       Integer        idA  = (Integer)        meA.getKey();
3489       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3490
3491       if( !rgB.id2hrn.containsKey( idA ) ) {
3492         return false;
3493       }
3494
3495       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3496       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3497         return false;
3498       }
3499     }
3500
3501     return true;
3502   }
3503
3504
3505   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3506
3507     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3508       return false;
3509     }
3510
3511     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3512       return false;
3513     }
3514
3515     return true;
3516   }
3517
3518   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3519                                                        ReachGraph rgB ) {
3520     Set      sA = rgA.td2vn.entrySet();
3521     Iterator iA = sA.iterator();
3522     while( iA.hasNext() ) {
3523       Map.Entry      meA = (Map.Entry)      iA.next();
3524       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3525
3526       if( !rgB.td2vn.containsKey( tdA ) ) {
3527         return false;
3528       }
3529     }
3530
3531     return true;
3532   }
3533
3534
3535   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3536     if( !areallREinAandBequal( this, rg ) ) {
3537       return false;
3538     }
3539
3540     return true;
3541   }
3542
3543   static protected boolean areallREinAandBequal( ReachGraph rgA,
3544                                                  ReachGraph rgB ) {
3545
3546     // check all the heap region->heap region edges
3547     Set      sA = rgA.id2hrn.entrySet();
3548     Iterator iA = sA.iterator();
3549     while( iA.hasNext() ) {
3550       Map.Entry      meA  = (Map.Entry)      iA.next();
3551       Integer        idA  = (Integer)        meA.getKey();
3552       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3553
3554       // we should have already checked that the same
3555       // heap regions exist in both graphs
3556       assert rgB.id2hrn.containsKey( idA );
3557
3558       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3559         return false;
3560       }
3561
3562       // then check every edge in B for presence in A, starting
3563       // from the same parent HeapRegionNode
3564       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3565
3566       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3567         return false;
3568       }
3569     }
3570
3571     // then check all the variable->heap region edges
3572     sA = rgA.td2vn.entrySet();
3573     iA = sA.iterator();
3574     while( iA.hasNext() ) {
3575       Map.Entry      meA = (Map.Entry)      iA.next();
3576       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3577       VariableNode   vnA = (VariableNode)   meA.getValue();
3578
3579       // we should have already checked that the same
3580       // label nodes exist in both graphs
3581       assert rgB.td2vn.containsKey( tdA );
3582
3583       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3584         return false;
3585       }
3586
3587       // then check every edge in B for presence in A, starting
3588       // from the same parent VariableNode
3589       VariableNode vnB = rgB.td2vn.get( tdA );
3590
3591       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3592         return false;
3593       }
3594     }
3595
3596     return true;
3597   }
3598
3599
3600   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3601                                                   RefSrcNode rnA,
3602                                                   ReachGraph rgB ) {
3603
3604     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3605     while( itrA.hasNext() ) {
3606       RefEdge        edgeA     = itrA.next();
3607       HeapRegionNode hrnChildA = edgeA.getDst();
3608       Integer        idChildA  = hrnChildA.getID();
3609
3610       assert rgB.id2hrn.containsKey( idChildA );
3611
3612       // at this point we know an edge in graph A exists
3613       // rnA -> idChildA, does this exact edge exist in B?
3614       boolean edgeFound = false;
3615
3616       RefSrcNode rnB = null;
3617       if( rnA instanceof HeapRegionNode ) {
3618         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3619         rnB = rgB.id2hrn.get( hrnA.getID() );
3620       } else {
3621         VariableNode vnA = (VariableNode) rnA;
3622         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3623       }
3624
3625       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3626       while( itrB.hasNext() ) {
3627         RefEdge        edgeB     = itrB.next();
3628         HeapRegionNode hrnChildB = edgeB.getDst();
3629         Integer        idChildB  = hrnChildB.getID();
3630
3631         if( idChildA.equals( idChildB ) &&
3632             edgeA.typeAndFieldEquals( edgeB ) ) {
3633
3634           // there is an edge in the right place with the right field,
3635           // but do they have the same attributes?
3636           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3637               edgeA.equalsPreds( edgeB )
3638               ) {
3639             edgeFound = true;
3640           }
3641         }
3642       }
3643
3644       if( !edgeFound ) {
3645         return false;
3646       }
3647     }
3648
3649     return true;
3650   }
3651
3652
3653
3654   // this analysis no longer has the "match anything"
3655   // type which was represented by null
3656   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3657                                              TypeDescriptor td2 ) {
3658     assert td1 != null;
3659     assert td2 != null;
3660
3661     if( td1.isNull() ) {
3662       return td2;
3663     }
3664     if( td2.isNull() ) {
3665       return td1;
3666     }
3667     return typeUtil.mostSpecific( td1, td2 );
3668   }
3669
3670   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3671                                              TypeDescriptor td2,
3672                                              TypeDescriptor td3 ) {
3673
3674     return mostSpecificType( td1,
3675                              mostSpecificType( td2, td3 )
3676                              );
3677   }
3678
3679   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3680                                              TypeDescriptor td2,
3681                                              TypeDescriptor td3,
3682                                              TypeDescriptor td4 ) {
3683
3684     return mostSpecificType( mostSpecificType( td1, td2 ),
3685                              mostSpecificType( td3, td4 )
3686                              );
3687   }
3688
3689   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3690                                     TypeDescriptor possibleChild ) {
3691     assert possibleSuper != null;
3692     assert possibleChild != null;
3693
3694     if( possibleSuper.isNull() ||
3695         possibleChild.isNull() ) {
3696       return true;
3697     }
3698
3699     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3700   }
3701
3702
3703   protected boolean hasMatchingField( HeapRegionNode src,
3704                                       RefEdge        edge ) {
3705
3706     TypeDescriptor tdSrc = src.getType();
3707     assert tdSrc != null;
3708
3709     if( tdSrc.isArray() ) {
3710       TypeDescriptor td = edge.getType();
3711       assert td != null;
3712
3713       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3714       assert tdSrcDeref != null;
3715
3716       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3717         return false;
3718       }
3719
3720       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3721     }
3722
3723     // if it's not a class, it doesn't have any fields to match
3724     if( !tdSrc.isClass() ) {
3725       return false;
3726     }
3727
3728     ClassDescriptor cd = tdSrc.getClassDesc();
3729     while( cd != null ) {
3730       Iterator fieldItr = cd.getFields();
3731
3732       while( fieldItr.hasNext() ) {
3733         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3734
3735         if( fd.getType().equals( edge.getType() ) &&
3736             fd.getSymbol().equals( edge.getField() ) ) {
3737           return true;
3738         }
3739       }
3740
3741       cd = cd.getSuperDesc();
3742     }
3743
3744     // otherwise it is a class with fields
3745     // but we didn't find a match
3746     return false;
3747   }
3748
3749   protected boolean hasMatchingType( RefEdge        edge,
3750                                      HeapRegionNode dst  ) {
3751
3752     // if the region has no type, matches everything
3753     TypeDescriptor tdDst = dst.getType();
3754     assert tdDst != null;
3755
3756     // if the type is not a class or an array, don't
3757     // match because primitives are copied, no aliases
3758     ClassDescriptor cdDst = tdDst.getClassDesc();
3759     if( cdDst == null && !tdDst.isArray() ) {
3760       return false;
3761     }
3762
3763     // if the edge type is null, it matches everything
3764     TypeDescriptor tdEdge = edge.getType();
3765     assert tdEdge != null;
3766
3767     return typeUtil.isSuperorType( tdEdge, tdDst );
3768   }
3769
3770
3771
3772   public void writeGraph( String  graphName,
3773                           boolean writeLabels,
3774                           boolean labelSelect,
3775                           boolean pruneGarbage,
3776                           boolean hideSubsetReachability,
3777                           boolean hideEdgeTaints
3778                           ) throws java.io.IOException {
3779     writeGraph( graphName,
3780                 writeLabels,
3781                 labelSelect,
3782                 pruneGarbage,
3783                 hideSubsetReachability,
3784                 hideEdgeTaints,
3785                 null );
3786   }
3787
3788   public void writeGraph( String       graphName,
3789                           boolean      writeLabels,
3790                           boolean      labelSelect,
3791                           boolean      pruneGarbage,
3792                           boolean      hideSubsetReachability,
3793                           boolean      hideEdgeTaints,
3794                           Set<Integer> callerNodeIDsCopiedToCallee
3795                           ) throws java.io.IOException {
3796
3797     // remove all non-word characters from the graph name so
3798     // the filename and identifier in dot don't cause errors
3799     graphName = graphName.replaceAll( "[\\W]", "" );
3800
3801     BufferedWriter bw =
3802       new BufferedWriter( new FileWriter( graphName+".dot" ) );
3803
3804     bw.write( "digraph "+graphName+" {\n" );
3805
3806
3807     // this is an optional step to form the callee-reachable
3808     // "cut-out" into a DOT cluster for visualization
3809     if( callerNodeIDsCopiedToCallee != null ) {
3810
3811       bw.write( "  subgraph cluster0 {\n" );
3812       bw.write( "    color=blue;\n" );
3813
3814       Iterator i = id2hrn.entrySet().iterator();
3815       while( i.hasNext() ) {
3816         Map.Entry      me  = (Map.Entry)      i.next();
3817         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3818
3819         if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3820           bw.write( "    "+hrn.toString()+
3821                     hrn.toStringDOT( hideSubsetReachability )+
3822                     ";\n" );
3823
3824         }
3825       }
3826
3827       bw.write( "  }\n" );
3828     }
3829
3830
3831     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3832
3833     // then visit every heap region node
3834     Iterator i = id2hrn.entrySet().iterator();
3835     while( i.hasNext() ) {
3836       Map.Entry      me  = (Map.Entry)      i.next();
3837       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3838
3839       // only visit nodes worth writing out--for instance
3840       // not every node at an allocation is referenced
3841       // (think of it as garbage-collected), etc.
3842       if( !pruneGarbage        ||
3843           hrn.isOutOfContext()
3844           ) {
3845
3846         if( !visited.contains( hrn ) ) {
3847           traverseHeapRegionNodes( hrn,
3848                                    bw,
3849                                    null,
3850                                    visited,
3851                                    hideSubsetReachability,
3852                                    hideEdgeTaints,
3853                                    callerNodeIDsCopiedToCallee );
3854         }
3855       }
3856     }
3857
3858     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
3859
3860
3861     // then visit every label node, useful for debugging
3862     if( writeLabels ) {
3863       i = td2vn.entrySet().iterator();
3864       while( i.hasNext() ) {
3865         Map.Entry    me = (Map.Entry)    i.next();
3866         VariableNode vn = (VariableNode) me.getValue();
3867
3868         if( labelSelect ) {
3869           String labelStr = vn.getTempDescriptorString();
3870           if( labelStr.startsWith( "___temp" )     ||
3871               labelStr.startsWith( "___dst" )      ||
3872               labelStr.startsWith( "___srctmp" )   ||
3873               labelStr.startsWith( "___neverused" )
3874               ) {
3875             continue;
3876           }
3877         }
3878
3879         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3880         while( heapRegionsItr.hasNext() ) {
3881           RefEdge        edge = heapRegionsItr.next();
3882           HeapRegionNode hrn  = edge.getDst();
3883
3884           if( !visited.contains( hrn ) ) {
3885             traverseHeapRegionNodes( hrn,
3886                                      bw,
3887                                      null,
3888                                      visited,
3889                                      hideSubsetReachability,
3890                                      hideEdgeTaints,
3891                                      callerNodeIDsCopiedToCallee );
3892           }
3893
3894           bw.write( "  "+vn.toString()+
3895                     " -> "+hrn.toString()+
3896                     edge.toStringDOT( hideSubsetReachability, "" )+
3897                     ";\n" );
3898         }
3899       }
3900     }
3901
3902     bw.write( "}\n" );
3903     bw.close();
3904   }
3905
3906   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
3907                                           BufferedWriter      bw,
3908                                           TempDescriptor      td,
3909                                           Set<HeapRegionNode> visited,
3910                                           boolean             hideSubsetReachability,
3911                                           boolean             hideEdgeTaints,
3912                                           Set<Integer>        callerNodeIDsCopiedToCallee
3913                                           ) throws java.io.IOException {
3914
3915     if( visited.contains( hrn ) ) {
3916       return;
3917     }
3918     visited.add( hrn );
3919
3920     // if we're drawing the callee-view subgraph, only
3921     // write out the node info if it hasn't already been
3922     // written
3923     if( callerNodeIDsCopiedToCallee == null ||
3924         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3925         ) {
3926       bw.write( "  "+hrn.toString()+
3927                 hrn.toStringDOT( hideSubsetReachability )+
3928                 ";\n" );
3929     }
3930
3931     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3932     while( childRegionsItr.hasNext() ) {
3933       RefEdge        edge     = childRegionsItr.next();
3934       HeapRegionNode hrnChild = edge.getDst();
3935
3936       if( callerNodeIDsCopiedToCallee != null &&
3937           (edge.getSrc() instanceof HeapRegionNode) ) {
3938         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3939         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
3940             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3941             ) {
3942           bw.write( "  "+hrn.toString()+
3943                     " -> "+hrnChild.toString()+
3944                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3945                     ";\n");
3946         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
3947                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3948                    ) {
3949           bw.write( "  "+hrn.toString()+
3950                     " -> "+hrnChild.toString()+
3951                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3952                     ";\n");
3953         } else {
3954           bw.write( "  "+hrn.toString()+
3955                     " -> "+hrnChild.toString()+
3956                     edge.toStringDOT( hideSubsetReachability, "" )+
3957                     ";\n");
3958         }
3959       } else {
3960         bw.write( "  "+hrn.toString()+
3961                   " -> "+hrnChild.toString()+
3962                   edge.toStringDOT( hideSubsetReachability, "" )+
3963                   ";\n");
3964       }
3965
3966       traverseHeapRegionNodes( hrnChild,
3967                                bw,
3968                                td,
3969                                visited,
3970                                hideSubsetReachability,
3971                                hideEdgeTaints,
3972                                callerNodeIDsCopiedToCallee );
3973     }
3974   }
3975
3976         public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
3977                         HeapRegionNode hrn2) {
3978
3979                 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
3980                 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
3981
3982                 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
3983                 todoNodes1.add(hrn1);
3984
3985                 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
3986                 todoNodes2.add(hrn2);
3987
3988                 // follow links until all reachable nodes have been found
3989                 while (!todoNodes1.isEmpty()) {
3990                         HeapRegionNode hrn = todoNodes1.iterator().next();
3991                         todoNodes1.remove(hrn);
3992                         reachableNodes1.add(hrn);
3993
3994                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
3995                         while (edgeItr.hasNext()) {
3996                                 RefEdge edge = edgeItr.next();
3997
3998                                 if (!reachableNodes1.contains(edge.getDst())) {
3999                                         todoNodes1.add(edge.getDst());
4000                                 }
4001                         }
4002                 }
4003
4004                 while (!todoNodes2.isEmpty()) {
4005                         HeapRegionNode hrn = todoNodes2.iterator().next();
4006                         todoNodes2.remove(hrn);
4007                         reachableNodes2.add(hrn);
4008
4009                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4010                         while (edgeItr.hasNext()) {
4011                                 RefEdge edge = edgeItr.next();
4012
4013                                 if (!reachableNodes2.contains(edge.getDst())) {
4014                                         todoNodes2.add(edge.getDst());
4015                                 }
4016                         }
4017                 }
4018
4019                 Set<HeapRegionNode> intersection =
4020                   new HashSet<HeapRegionNode>( reachableNodes1 );
4021
4022                 intersection.retainAll( reachableNodes2 );
4023
4024                 return intersection;
4025         }
4026
4027         public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4028                         HeapRegionNode hrn2) {
4029                 assert hrn1 != null;
4030                 assert hrn2 != null;
4031
4032                 // then get the various tokens for these heap regions
4033                 ReachTuple h1 = ReachTuple.factory(hrn1.getID(),
4034                                 !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false);
4035
4036                 int arity;
4037                 if(hrn1.isSingleObject){
4038                         arity=ReachTuple.ARITY_ONE;
4039                 }else{
4040                         arity=ReachTuple.ARITY_ZEROORMORE;
4041                 }
4042                 ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1
4043                                 .isSingleObject(), arity, false);
4044
4045                 ReachTuple h2 = ReachTuple.factory(hrn2.getID(),
4046                                 !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false);
4047
4048                 if(hrn2.isSingleObject){
4049                         arity=ReachTuple.ARITY_ONE;
4050                 }else{
4051                         arity=ReachTuple.ARITY_ZEROORMORE;
4052                 }
4053
4054                 ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2
4055                                 .isSingleObject(), arity, false);
4056
4057                 // then get the merged beta of all out-going edges from these heap
4058                 // regions
4059
4060                 ReachSet beta1 = ReachSet.factory();
4061                 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4062                 while (itrEdge.hasNext()) {
4063                         RefEdge edge = itrEdge.next();
4064                         beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4065                 }
4066
4067                 ReachSet beta2 = ReachSet.factory();
4068                 itrEdge = hrn2.iteratorToReferencees();
4069                 while (itrEdge.hasNext()) {
4070                         RefEdge edge = itrEdge.next();
4071                         beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4072                 }
4073
4074                 boolean aliasDetected = false;
4075
4076                 // only do this one if they are different tokens
4077                 if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) {
4078                         aliasDetected = true;
4079                 }
4080 //              if (beta1.containsStateWithBoth(h1plus, h2)) {
4081 //                      aliasDetected = true;
4082 //              }
4083                 if (beta1.containsStateWithBoth(h1star, h2)) {
4084                         aliasDetected = true;
4085                 }
4086 //              if (beta1.containsStateWithBoth(h1, h2plus)) {
4087 //                      aliasDetected = true;
4088 //              }
4089 //              if (beta1.containsStateWithBoth(h1plus, h2plus)) {
4090 //                      aliasDetected = true;
4091 //              }
4092 //              if (beta1.containsStateWithBoth(h1star, h2plus)) {
4093 //                      aliasDetected = true;
4094 //              }
4095                 if (beta1.containsStateWithBoth(h1, h2star)) {
4096                         aliasDetected = true;
4097                 }
4098 //              if (beta1.containsStateWithBoth(h1plus, h2star)) {
4099 //                      aliasDetected = true;
4100 //              }
4101                 if (beta1.containsStateWithBoth(h1star, h2star)) {
4102                         aliasDetected = true;
4103                 }
4104
4105                 if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) {
4106                         aliasDetected = true;
4107                 }
4108 //              if (beta2.containsStateWithBoth(h1plus, h2)) {
4109 //                      aliasDetected = true;
4110 //              }
4111                 if (beta2.containsStateWithBoth(h1star, h2)) {
4112                         aliasDetected = true;
4113                 }
4114 //              if (beta2.containsStateWithBoth(h1, h2plus)) {
4115 //                      aliasDetected = true;
4116 //              }
4117 //              if (beta2.containsStateWithBoth(h1plus, h2plus)) {
4118 //                      aliasDetected = true;
4119 //              }
4120 //              if (beta2.containsStateWithBoth(h1star, h2plus)) {
4121 //                      aliasDetected = true;
4122 //              }
4123                 if (beta2.containsStateWithBoth(h1, h2star)) {
4124                         aliasDetected = true;
4125                 }
4126 //              if (beta2.containsStateWithBoth(h1plus, h2star)) {
4127 //                      aliasDetected = true;
4128 //              }
4129                 if (beta2.containsStateWithBoth(h1star, h2star)) {
4130                         aliasDetected = true;
4131                 }
4132
4133                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4134                 if (aliasDetected) {
4135                         common = findCommonReachableNodes(hrn1, hrn2);
4136                         if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) {
4137                                 assert !common.isEmpty();
4138                         }
4139                 }
4140
4141                 return common;
4142         }
4143
4144         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4145                         Integer paramIndex1, Integer paramIndex2) {
4146
4147                 // get parameter's heap regions
4148                 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4149                 VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1);
4150                 RefEdge argEdge1 = argVar1.iteratorToReferencees().next();
4151                 HeapRegionNode hrnParam1 = argEdge1.getDst();
4152
4153                 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4154                 VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2);
4155                 RefEdge argEdge2 = argVar2.iteratorToReferencees().next();
4156                 HeapRegionNode hrnParam2 = argEdge2.getDst();
4157
4158                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4159                 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4160
4161                 return common;
4162         }
4163
4164         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4165                         Integer paramIndex, AllocSite as) {
4166
4167                 // get parameter's heap regions
4168                 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4169                 VariableNode argVar = getVariableNodeFromTemp(paramTemp);
4170                 RefEdge argEdge = argVar.iteratorToReferencees().next();
4171                 HeapRegionNode hrnParam = argEdge.getDst();
4172
4173                 // get summary node
4174                 HeapRegionNode hrnSummary=null;
4175                 if(id2hrn.containsKey(as.getSummary())){
4176                         // if summary node doesn't exist, ignore this case
4177                         hrnSummary = id2hrn.get(as.getSummary());
4178                         assert hrnSummary != null;
4179                 }
4180
4181                 Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
4182                 if(hrnSummary!=null){
4183                         common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4184                 }
4185
4186                 // check for other nodes
4187                 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4188
4189                         assert id2hrn.containsKey(as.getIthOldest(i));
4190                         HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4191                         assert hrnIthOldest != null;
4192
4193                         common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4194
4195                 }
4196
4197                 return common;
4198         }
4199
4200         public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4201                         AllocSite as2) {
4202
4203                 // get summary node 1's alpha
4204                 Integer idSum1 = as1.getSummary();
4205                 HeapRegionNode hrnSum1=null;
4206                 if(id2hrn.containsKey(idSum1)){
4207                         hrnSum1 = id2hrn.get(idSum1);
4208                 }
4209
4210                 // get summary node 2's alpha
4211                 Integer idSum2 = as2.getSummary();
4212                 HeapRegionNode hrnSum2=null;
4213                 if(id2hrn.containsKey(idSum2)){
4214                         hrnSum2 = id2hrn.get(idSum2);
4215                 }
4216
4217                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4218                 if(hrnSum1!=null && hrnSum2!=null){
4219                         common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4220                 }
4221
4222                 // check sum2 against alloc1 nodes
4223                 if(hrnSum2!=null){
4224                 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4225                         Integer idI1 = as1.getIthOldest(i);
4226                         assert id2hrn.containsKey(idI1);
4227                         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4228                         assert hrnI1 != null;
4229                         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4230                 }
4231                 }
4232
4233                 // check sum1 against alloc2 nodes
4234                 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4235                         Integer idI2 = as2.getIthOldest(i);
4236                         assert id2hrn.containsKey(idI2);
4237                         HeapRegionNode hrnI2 = id2hrn.get(idI2);
4238                         assert hrnI2 != null;
4239
4240                         if(hrnSum1!=null){
4241                                 common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4242                         }
4243
4244                         // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4245                         for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4246                                 Integer idI1 = as1.getIthOldest(j);
4247
4248                                 // if these are the same site, don't look for the same token, no
4249                                 // alias.
4250                                 // different tokens of the same site could alias together though
4251                                 if (idI1.equals(idI2)) {
4252                                         continue;
4253                                 }
4254
4255                                 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4256
4257                                 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4258                         }
4259                 }
4260
4261                 return common;
4262         }
4263
4264 }