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