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