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       VariableNode   vnCaller  = (VariableNode) reArg.getSrc();
1618       TempDescriptor argCaller = vnCaller.getTempDescriptor();
1619
1620       TempDescriptor paramCallee = fmCallee.getParameter( index );
1621       VariableNode   vnCallee    = rg.getVariableNodeFromTemp( paramCallee );
1622
1623       HeapRegionNode hrnDstCaller = reArg.getDst();
1624       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1625       assert hrnDstCallee != null;
1626
1627       ExistPred pred =
1628         ExistPred.factory( argCaller,
1629                            null,
1630                            hrnDstCallee.getID(),
1631                            reArg.getType(),
1632                            reArg.getField(),
1633                            null,
1634                            true,  // out-of-callee-context
1635                            false  // out-of-caller-context
1636                            );
1637
1638       ExistPredSet preds =
1639         ExistPredSet.factory( pred );
1640
1641       RefEdge reCallee =
1642         new RefEdge( vnCallee,
1643                      hrnDstCallee,
1644                      reArg.getType(),
1645                      reArg.getField(),
1646                      toCalleeContext( reArg.getBeta(),
1647                                       preds,
1648                                       oocHrnIdOoc2callee
1649                                       ),
1650                      preds
1651                      );
1652
1653       rg.addRefEdge( vnCallee,
1654                      hrnDstCallee,
1655                      reCallee
1656                      );
1657     }
1658
1659     // add in-context edges to callee graph
1660     Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1661     while( reItr.hasNext() ) {
1662       RefEdge    reCaller  = reItr.next();
1663       RefSrcNode rsnCaller = reCaller.getSrc();
1664       assert rsnCaller instanceof HeapRegionNode;
1665       HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1666       HeapRegionNode hrnDstCaller = reCaller.getDst();
1667
1668       HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1669       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1670       assert hrnSrcCallee != null;
1671       assert hrnDstCallee != null;
1672
1673       ExistPred pred =
1674         ExistPred.factory( null,
1675                            hrnSrcCallee.getID(),
1676                            hrnDstCallee.getID(),
1677                            reCaller.getType(),
1678                            reCaller.getField(),
1679                            null,
1680                            false, // out-of-callee-context
1681                            false  // out-of-caller-context
1682                            );
1683
1684       ExistPredSet preds =
1685         ExistPredSet.factory( pred );
1686
1687       RefEdge reCallee =
1688         new RefEdge( hrnSrcCallee,
1689                      hrnDstCallee,
1690                      reCaller.getType(),
1691                      reCaller.getField(),
1692                      toCalleeContext( reCaller.getBeta(),
1693                                       preds,
1694                                       oocHrnIdOoc2callee
1695                                       ),
1696                      preds
1697                      );
1698
1699       rg.addRefEdge( hrnSrcCallee,
1700                      hrnDstCallee,
1701                      reCallee
1702                      );
1703     }
1704
1705     // add out-of-context edges to callee graph
1706     reItr = oocCallerEdges.iterator();
1707     while( reItr.hasNext() ) {
1708       RefEdge        reCaller     = reItr.next();
1709       RefSrcNode     rsnCaller    = reCaller.getSrc();
1710       HeapRegionNode hrnDstCaller = reCaller.getDst();
1711       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1712       assert hrnDstCallee != null;
1713
1714       TypeDescriptor oocNodeType;
1715       ReachSet       oocReach;
1716       TempDescriptor oocPredSrcTemp = null;
1717       Integer        oocPredSrcID   = null;
1718       boolean        outOfCalleeContext;
1719       boolean        outOfCallerContext;
1720
1721       if( rsnCaller instanceof VariableNode ) {
1722         VariableNode vnCaller = (VariableNode) rsnCaller;
1723         oocNodeType    = null;
1724         oocReach       = rsetEmpty;
1725         oocPredSrcTemp = vnCaller.getTempDescriptor();
1726         outOfCalleeContext = true;
1727         outOfCallerContext = false;
1728
1729       } else {
1730         HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1731         assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1732         oocNodeType  = hrnSrcCaller.getType();
1733         oocReach     = hrnSrcCaller.getAlpha();
1734         oocPredSrcID = hrnSrcCaller.getID();
1735         if( hrnSrcCaller.isOutOfContext() ) {
1736           outOfCalleeContext = false;
1737           outOfCallerContext = true;
1738         } else {
1739           outOfCalleeContext = true;
1740           outOfCallerContext = false;
1741         }
1742       }
1743
1744       ExistPred pred =
1745         ExistPred.factory( oocPredSrcTemp,
1746                            oocPredSrcID,
1747                            hrnDstCallee.getID(),
1748                            reCaller.getType(),
1749                            reCaller.getField(),
1750                            null,
1751                            outOfCalleeContext,
1752                            outOfCallerContext
1753                            );
1754
1755       ExistPredSet preds =
1756         ExistPredSet.factory( pred );
1757
1758       RefEdge oocEdgeExisting =
1759         rg.getOutOfContextReferenceTo( hrnDstCallee,
1760                                        oocNodeType,
1761                                        reCaller.getType(),
1762                                        reCaller.getField()
1763                                        );
1764
1765       if( oocEdgeExisting == null ) {
1766           // for consistency, map one out-of-context "identifier"
1767           // to one heap region node id, otherwise no convergence
1768         String oocid = "oocid"+
1769           fmCallee+
1770           hrnDstCallee.getIDString()+
1771           oocNodeType+
1772           reCaller.getType()+
1773           reCaller.getField();
1774
1775         Integer oocHrnID = oocid2hrnid.get( oocid );
1776
1777         HeapRegionNode hrnCalleeAndOutContext;
1778
1779         if( oocHrnID == null ) {
1780
1781           hrnCalleeAndOutContext =
1782             rg.createNewHeapRegionNode( null,  // ID
1783                                         false, // single object?
1784                                         false, // new summary?
1785                                         true,  // out-of-context?
1786                                         oocNodeType,
1787                                         null,  // alloc site, shouldn't be used
1788                                         toCalleeContext( oocReach,
1789                                                          preds,
1790                                                          oocHrnIdOoc2callee
1791                                                          ),
1792                                         toCalleeContext( oocReach,
1793                                                          preds,
1794                                                          oocHrnIdOoc2callee
1795                                                          ),
1796                                         preds,
1797                                         "out-of-context"
1798                                         );
1799
1800           oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1801
1802         } else {
1803
1804           // the mapping already exists, so see if node is there
1805           hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1806
1807           if( hrnCalleeAndOutContext == null ) {
1808             // nope, make it
1809             hrnCalleeAndOutContext =
1810               rg.createNewHeapRegionNode( oocHrnID,  // ID
1811                                           false, // single object?
1812                                           false, // new summary?
1813                                           true,  // out-of-context?
1814                                           oocNodeType,
1815                                           null,  // alloc site, shouldn't be used
1816                                           toCalleeContext( oocReach,
1817                                                            preds,
1818                                                            oocHrnIdOoc2callee
1819                                                            ),
1820                                           toCalleeContext( oocReach,
1821                                                            preds,
1822                                                            oocHrnIdOoc2callee
1823                                                            ),
1824                                           preds,
1825                                           "out-of-context"
1826                                           );
1827
1828           } else {
1829             // otherwise it is there, so merge reachability
1830             hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1831                                                                      toCalleeContext( oocReach,
1832                                                                                       preds,
1833                                                                                       oocHrnIdOoc2callee
1834                                                                                       )
1835                                                                      )
1836                                              );
1837           }
1838         }
1839
1840         assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1841
1842         rg.addRefEdge( hrnCalleeAndOutContext,
1843                        hrnDstCallee,
1844                        new RefEdge( hrnCalleeAndOutContext,
1845                                     hrnDstCallee,
1846                                     reCaller.getType(),
1847                                     reCaller.getField(),
1848                                     toCalleeContext( reCaller.getBeta(),
1849                                                      preds,
1850                                                      oocHrnIdOoc2callee
1851                                                      ),
1852                                     preds
1853                                     )
1854                        );
1855
1856         } else {
1857         // the out-of-context edge already exists
1858         oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1859                                                          toCalleeContext( reCaller.getBeta(),
1860                                                                           preds,
1861                                                                           oocHrnIdOoc2callee
1862                                                                           )
1863                                                   )
1864                                  );
1865
1866         oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1867                                                   preds
1868                                                   )
1869                                   );
1870
1871         HeapRegionNode hrnCalleeAndOutContext =
1872           (HeapRegionNode) oocEdgeExisting.getSrc();
1873         hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1874                                                                  toCalleeContext( oocReach,
1875                                                                                   preds,
1876                                                                                   oocHrnIdOoc2callee
1877                                                                                   )
1878                                                                  )
1879                                          );
1880
1881         assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1882       }
1883     }
1884
1885
1886     if( writeDebugDOTs ) {
1887       debugGraphPrefix = String.format( "call%03d", debugCallSiteVisitCounter );
1888       rg.writeGraph( debugGraphPrefix+"calleeview",
1889                      resolveMethodDebugDOTwriteLabels,
1890                      resolveMethodDebugDOTselectTemps,
1891                      resolveMethodDebugDOTpruneGarbage,
1892                      resolveMethodDebugDOThideSubsetReach,
1893                      resolveMethodDebugDOThideEdgeTaints );
1894     }
1895
1896     return rg;
1897   }
1898
1899   private static Hashtable<String, Integer> oocid2hrnid =
1900     new Hashtable<String, Integer>();
1901
1902
1903   // useful since many graphs writes in the method call debug code
1904   private static boolean resolveMethodDebugDOTwriteLabels     = true;
1905   private static boolean resolveMethodDebugDOTselectTemps     = true;
1906   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
1907   private static boolean resolveMethodDebugDOThideSubsetReach = true;
1908   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
1909
1910   static String debugGraphPrefix;
1911   static int debugCallSiteVisitCounter;
1912   static int debugCallSiteVisitStartCapture;
1913   static int debugCallSiteNumVisitsToCapture;
1914   static boolean debugCallSiteStopAfter;
1915
1916
1917   public void
1918     resolveMethodCall( FlatCall     fc,
1919                        FlatMethod   fmCallee,
1920                        ReachGraph   rgCallee,
1921                        Set<Integer> callerNodeIDsCopiedToCallee,
1922                        boolean      writeDebugDOTs
1923                        ) {
1924
1925     if( writeDebugDOTs ) {
1926       System.out.println( "  Writing out visit "+
1927                           debugCallSiteVisitCounter+
1928                           " to debug call site" );
1929
1930       debugGraphPrefix = String.format( "call%03d",
1931                                         debugCallSiteVisitCounter );
1932
1933       rgCallee.writeGraph( debugGraphPrefix+"callee",
1934                            resolveMethodDebugDOTwriteLabels,
1935                            resolveMethodDebugDOTselectTemps,
1936                            resolveMethodDebugDOTpruneGarbage,
1937                            resolveMethodDebugDOThideSubsetReach,
1938                            resolveMethodDebugDOThideEdgeTaints );
1939
1940       writeGraph( debugGraphPrefix+"caller00In",
1941                   resolveMethodDebugDOTwriteLabels,
1942                   resolveMethodDebugDOTselectTemps,
1943                   resolveMethodDebugDOTpruneGarbage,
1944                   resolveMethodDebugDOThideSubsetReach,
1945                   resolveMethodDebugDOThideEdgeTaints,
1946                   callerNodeIDsCopiedToCallee );
1947     }
1948
1949
1950
1951     // method call transfer function steps:
1952     // 1. Use current callee-reachable heap (CRH) to test callee
1953     //    predicates and mark what will be coming in.
1954     // 2. Wipe CRH out of caller.
1955     // 3. Transplant marked callee parts in:
1956     //    a) bring in nodes
1957     //    b) bring in callee -> callee edges
1958     //    c) resolve out-of-context -> callee edges
1959     //    d) assign return value
1960     // 4. Collapse shadow nodes down
1961     // 5. Global sweep it.
1962
1963
1964     // 1. mark what callee elements have satisfied predicates
1965     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1966       new Hashtable<HeapRegionNode, ExistPredSet>();
1967
1968     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1969       new Hashtable<RefEdge, ExistPredSet>();
1970
1971     Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1972       new Hashtable<ReachState, ExistPredSet>();
1973
1974     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1975       new Hashtable< RefEdge, Set<RefSrcNode> >();
1976
1977     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1978     while( meItr.hasNext() ) {
1979       Map.Entry      me        = (Map.Entry)      meItr.next();
1980       Integer        id        = (Integer)        me.getKey();
1981       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1982
1983       // if a callee element's predicates are satisfied then a set
1984       // of CALLER predicates is returned: they are the predicates
1985       // that the callee element moved into the caller context
1986       // should have, and it is inefficient to find this again later
1987       ExistPredSet predsIfSatis =
1988         hrnCallee.getPreds().isSatisfiedBy( this,
1989                                             callerNodeIDsCopiedToCallee
1990                                             );
1991
1992       if( predsIfSatis != null ) {
1993         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1994       } else {
1995         // otherwise don't bother looking at edges to this node
1996         continue;
1997       }
1998
1999       // since the node is coming over, find out which reach
2000       // states on it should come over, too
2001       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2002       while( stateItr.hasNext() ) {
2003         ReachState stateCallee = stateItr.next();
2004
2005         predsIfSatis =
2006           stateCallee.getPreds().isSatisfiedBy( this,
2007                                                 callerNodeIDsCopiedToCallee
2008                                                 );
2009         if( predsIfSatis != null ) {
2010           ExistPredSet predsAlready = calleeStatesSatisfied.get( stateCallee );
2011           if( predsAlready == null ) {
2012             calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2013           } else {
2014             calleeStatesSatisfied.put( stateCallee,
2015                                        Canonical.join( predsIfSatis,
2016                                                        predsAlready
2017                                                        )
2018                                        );
2019           }
2020         }
2021       }
2022
2023       // then look at edges to the node
2024       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2025       while( reItr.hasNext() ) {
2026         RefEdge    reCallee  = reItr.next();
2027         RefSrcNode rsnCallee = reCallee.getSrc();
2028
2029         // (caller local variables to in-context heap regions)
2030         // have an (out-of-context heap region -> in-context heap region)
2031         // abstraction in the callEE, so its true we never need to
2032         // look at a (var node -> heap region) edge in callee to bring
2033         // those over for the call site transfer, except for the special
2034         // case of *RETURN var* -> heap region edges.
2035         // What about (param var->heap region)
2036         // edges in callee? They are dealt with below this loop.
2037
2038         if( rsnCallee instanceof VariableNode ) {
2039
2040           // looking for the return-value variable only
2041           VariableNode vnCallee = (VariableNode) rsnCallee;
2042           if( vnCallee.getTempDescriptor() != tdReturn ) {
2043             continue;
2044           }
2045
2046           TempDescriptor returnTemp = fc.getReturnTemp();
2047           if( returnTemp == null ||
2048               !DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2049               ) {
2050             continue;
2051           }
2052
2053           // note that the assignment of the return value is to a
2054           // variable in the caller which is out-of-context with
2055           // respect to the callee
2056           VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2057           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2058           rsnCallers.add( vnLhsCaller  );
2059           calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2060
2061
2062         } else {
2063           // for HeapRegionNode callee sources...
2064
2065           // first see if the source is out-of-context, and only
2066           // proceed with this edge if we find some caller-context
2067           // matches
2068           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2069           boolean matchedOutOfContext = false;
2070
2071           if( !hrnSrcCallee.isOutOfContext() ) {
2072
2073             predsIfSatis =
2074               hrnSrcCallee.getPreds().isSatisfiedBy( this,
2075                                                      callerNodeIDsCopiedToCallee
2076                                                      );
2077             if( predsIfSatis != null ) {
2078               calleeNodesSatisfied.put( hrnSrcCallee, predsIfSatis );
2079             } else {
2080               // otherwise forget this edge
2081               continue;
2082             }
2083
2084           } else {
2085             // hrnSrcCallee is out-of-context
2086
2087             assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2088
2089             Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2090
2091             // is the target node in the caller?
2092             HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2093             if( hrnDstCaller == null ) {
2094               continue;
2095             }
2096
2097             Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2098             while( reDstItr.hasNext() ) {
2099               // the edge and field (either possibly null) must match
2100               RefEdge reCaller = reDstItr.next();
2101
2102               if( !reCaller.typeEquals ( reCallee.getType()  ) ||
2103                   !reCaller.fieldEquals( reCallee.getField() )
2104                   ) {
2105                 continue;
2106               }
2107
2108               RefSrcNode rsnCaller = reCaller.getSrc();
2109               if( rsnCaller instanceof VariableNode ) {
2110
2111                 // a variable node matches an OOC region with null type
2112                 if( hrnSrcCallee.getType() != null ) {
2113                   continue;
2114                 }
2115
2116               } else {
2117                 // otherwise types should match
2118                 HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2119                 if( hrnSrcCallee.getType() == null ) {
2120                   if( hrnCallerSrc.getType() != null ) {
2121                     continue;
2122                   }
2123                 } else {
2124                   if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2125                     continue;
2126                   }
2127                 }
2128               }
2129
2130               rsnCallers.add( rsnCaller );
2131               matchedOutOfContext = true;
2132             }
2133
2134             if( !rsnCallers.isEmpty() ) {
2135               calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2136             }
2137           }
2138
2139           if( hrnSrcCallee.isOutOfContext() &&
2140               !matchedOutOfContext ) {
2141             continue;
2142           }
2143         }
2144
2145
2146         predsIfSatis =
2147           reCallee.getPreds().isSatisfiedBy( this,
2148                                              callerNodeIDsCopiedToCallee
2149                                              );
2150
2151         if( predsIfSatis != null ) {
2152           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2153
2154           // since the edge is coming over, find out which reach
2155           // states on it should come over, too
2156           stateItr = reCallee.getBeta().iterator();
2157           while( stateItr.hasNext() ) {
2158             ReachState stateCallee = stateItr.next();
2159
2160             predsIfSatis =
2161               stateCallee.getPreds().isSatisfiedBy( this,
2162                                                     callerNodeIDsCopiedToCallee
2163                                                     );
2164             if( predsIfSatis != null ) {
2165               ExistPredSet predsAlready = calleeStatesSatisfied.get( stateCallee );
2166               if( predsAlready == null ) {
2167                 calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2168               } else {
2169                 calleeStatesSatisfied.put( stateCallee,
2170                                            Canonical.join( predsIfSatis,
2171                                                            predsAlready
2172                                                            )
2173                                            );
2174               }
2175             }
2176           }
2177         }
2178       }
2179     }
2180
2181     if( writeDebugDOTs ) {
2182       writeGraph( debugGraphPrefix+"caller20BeforeWipe",
2183                   resolveMethodDebugDOTwriteLabels,
2184                   resolveMethodDebugDOTselectTemps,
2185                   resolveMethodDebugDOTpruneGarbage,
2186                   resolveMethodDebugDOThideSubsetReach,
2187                   resolveMethodDebugDOThideEdgeTaints );
2188     }
2189
2190
2191     // 2. predicates tested, ok to wipe out caller part
2192     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2193     while( hrnItr.hasNext() ) {
2194       Integer        hrnID     = hrnItr.next();
2195       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2196       assert hrnCaller != null;
2197
2198       // when clearing off nodes, also eliminate variable
2199       // references
2200       wipeOut( hrnCaller, true );
2201     }
2202
2203     // if we are assigning the return value to something, clobber now
2204     // as part of the wipe
2205     TempDescriptor returnTemp = fc.getReturnTemp();
2206     if( returnTemp != null &&
2207         DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2208         ) {
2209
2210       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2211       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2212     }
2213
2214
2215
2216
2217     if( writeDebugDOTs ) {
2218       writeGraph( debugGraphPrefix+"caller30BeforeAddingNodes",
2219                   resolveMethodDebugDOTwriteLabels,
2220                   resolveMethodDebugDOTselectTemps,
2221                   resolveMethodDebugDOTpruneGarbage,
2222                   resolveMethodDebugDOThideSubsetReach,
2223                   resolveMethodDebugDOThideEdgeTaints );
2224     }
2225
2226
2227
2228
2229     // 3. callee elements with satisfied preds come in, note that
2230     //    the mapping of elements satisfied to preds is like this:
2231     //    A callee element EE has preds EEp that are satisfied by
2232     //    some caller element ER.  We bring EE into the caller
2233     //    context as ERee with the preds of ER, namely ERp, which
2234     //    in the following algorithm is the value in the mapping
2235
2236     // 3.a) nodes
2237     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2238     while( satisItr.hasNext() ) {
2239       Map.Entry      me        = (Map.Entry)      satisItr.next();
2240       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2241       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
2242
2243       // TODO: I think its true that the current implementation uses
2244       // the type of the OOC region and the predicates OF THE EDGE from
2245       // it to link everything up in caller context, so that's why we're
2246       // skipping this... maybe that's a sillier way to do it?
2247       if( hrnCallee.isOutOfContext() ) {
2248         continue;
2249       }
2250
2251       AllocSite as = hrnCallee.getAllocSite();
2252       allocSites.add( as );
2253
2254       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2255
2256       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2257       if( hrnCaller == null ) {
2258         hrnCaller =
2259           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
2260                                    hrnCallee.isSingleObject(), // single object?
2261                                    hrnCallee.isNewSummary(),   // summary?
2262                                    false,                      // out-of-context?
2263                                    hrnCallee.getType(),        // type
2264                                    hrnCallee.getAllocSite(),   // allocation site
2265                                    toCallerContext( hrnCallee.getInherent(),
2266                                                     calleeStatesSatisfied  ),    // inherent reach
2267                                    null,                       // current reach
2268                                    predsEmpty,                 // predicates
2269                                    hrnCallee.getDescription()  // description
2270                                    );
2271       } else {
2272         assert hrnCaller.isWiped();
2273       }
2274
2275       hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2276                                            calleeStatesSatisfied
2277                                            )
2278                           );
2279
2280       hrnCaller.setPreds( preds );
2281     }
2282
2283
2284
2285
2286
2287     if( writeDebugDOTs ) {
2288       writeGraph( debugGraphPrefix+"caller31BeforeAddingEdges",
2289                   resolveMethodDebugDOTwriteLabels,
2290                   resolveMethodDebugDOTselectTemps,
2291                   resolveMethodDebugDOTpruneGarbage,
2292                   resolveMethodDebugDOThideSubsetReach,
2293                   resolveMethodDebugDOThideEdgeTaints );
2294     }
2295
2296
2297     // set these up during the next procedure so after
2298     // the caller has all of its nodes and edges put
2299     // back together we can propagate the callee's
2300     // reach changes backwards into the caller graph
2301     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2302
2303     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2304       new Hashtable<RefEdge, ChangeSet>();
2305
2306
2307     // 3.b) callee -> callee edges AND out-of-context -> callee
2308     //      which includes return temp -> callee edges now, too
2309     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2310     while( satisItr.hasNext() ) {
2311       Map.Entry    me       = (Map.Entry)    satisItr.next();
2312       RefEdge      reCallee = (RefEdge)      me.getKey();
2313       ExistPredSet preds    = (ExistPredSet) me.getValue();
2314
2315       HeapRegionNode hrnDstCallee = reCallee.getDst();
2316       AllocSite      asDst        = hrnDstCallee.getAllocSite();
2317       allocSites.add( asDst );
2318
2319       Integer hrnIDDstShadow =
2320         asDst.getShadowIDfromID( hrnDstCallee.getID() );
2321
2322       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2323       assert hrnDstCaller != null;
2324
2325
2326       RefSrcNode rsnCallee = reCallee.getSrc();
2327
2328       Set<RefSrcNode> rsnCallers =
2329         new HashSet<RefSrcNode>();
2330
2331       Set<RefSrcNode> oocCallers =
2332         calleeEdges2oocCallerSrcMatches.get( reCallee );
2333
2334       if( rsnCallee instanceof HeapRegionNode ) {
2335         HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2336         if( hrnCalleeSrc.isOutOfContext() ) {
2337           assert oocCallers != null;
2338         }
2339       }
2340
2341
2342       if( oocCallers == null ) {
2343         // there are no out-of-context matches, so it's
2344         // either a param/arg var or one in-context heap region
2345         if( rsnCallee instanceof VariableNode ) {
2346           // variable -> node in the callee should only
2347           // come into the caller if its from a param var
2348           VariableNode   vnCallee = (VariableNode) rsnCallee;
2349           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2350           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
2351                                                             tdParam );
2352           if( tdArg == null ) {
2353             // this means the variable isn't a parameter, its local
2354             // to the callee so we ignore it in call site transfer
2355             // shouldn't this NEVER HAPPEN?
2356             assert false;
2357           }
2358
2359           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2360
2361         } else {
2362           // otherwise source is in context, one region
2363
2364           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2365
2366           // translate an in-context node to shadow
2367           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2368           allocSites.add( asSrc );
2369
2370           Integer hrnIDSrcShadow =
2371             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2372
2373           HeapRegionNode hrnSrcCallerShadow =
2374             this.id2hrn.get( hrnIDSrcShadow );
2375
2376           assert hrnSrcCallerShadow != null;
2377
2378           rsnCallers.add( hrnSrcCallerShadow );
2379         }
2380
2381       } else {
2382         // otherwise we have a set of out-of-context srcs
2383         // that should NOT be translated to shadow nodes
2384         assert !oocCallers.isEmpty();
2385         rsnCallers.addAll( oocCallers );
2386       }
2387
2388       // now make all caller edges we've identified from
2389       // this callee edge with a satisfied predicate
2390       assert !rsnCallers.isEmpty();
2391       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2392       while( rsnItr.hasNext() ) {
2393         RefSrcNode rsnCaller = rsnItr.next();
2394
2395         RefEdge reCaller = new RefEdge( rsnCaller,
2396                                         hrnDstCaller,
2397                                         reCallee.getType(),
2398                                         reCallee.getField(),
2399                                         toCallerContext( reCallee.getBeta(),
2400                                                          calleeStatesSatisfied ),
2401                                         preds
2402                                         );
2403
2404         ChangeSet cs = ChangeSet.factory();
2405         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2406         while( rsItr.hasNext() ) {
2407           ReachState   state          = rsItr.next();
2408           ExistPredSet predsPreCallee = state.getPreds();
2409
2410           if( state.isEmpty() ) {
2411             continue;
2412           }
2413
2414           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2415           while( predItr.hasNext() ) {
2416             ExistPred pred = predItr.next();
2417             ReachState old = pred.ne_state;
2418
2419             if( old == null ) {
2420               old = rstateEmpty;
2421             }
2422
2423             cs = Canonical.add( cs,
2424                                 ChangeTuple.factory( old,
2425                                                      state
2426                                                      )
2427                                 );
2428           }
2429         }
2430
2431
2432         // look to see if an edge with same field exists
2433         // and merge with it, otherwise just add the edge
2434         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2435                                                          reCallee.getType(),
2436                                                          reCallee.getField()
2437                                                          );
2438         if( edgeExisting != null ) {
2439           edgeExisting.setBeta(
2440                                Canonical.unionORpreds( edgeExisting.getBeta(),
2441                                                 reCaller.getBeta()
2442                                                 )
2443                                );
2444           edgeExisting.setPreds(
2445                                 Canonical.join( edgeExisting.getPreds(),
2446                                                 reCaller.getPreds()
2447                                                 )
2448                                 );
2449
2450           // for reach propagation
2451           if( !cs.isEmpty() ) {
2452             ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
2453             if( csExisting == null ) {
2454               csExisting = ChangeSet.factory();
2455             }
2456             edgePlannedChanges.put( edgeExisting,
2457                                     Canonical.union( csExisting,
2458                                                      cs
2459                                                      )
2460                                     );
2461           }
2462
2463         } else {
2464           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2465
2466           // for reach propagation
2467           if( !cs.isEmpty() ) {
2468             edgesForPropagation.add( reCaller );
2469             assert !edgePlannedChanges.containsKey( reCaller );
2470             edgePlannedChanges.put( reCaller, cs );
2471           }
2472         }
2473       }
2474     }
2475
2476
2477
2478
2479
2480     if( writeDebugDOTs ) {
2481       writeGraph( debugGraphPrefix+"caller38propagateReach",
2482                   resolveMethodDebugDOTwriteLabels,
2483                   resolveMethodDebugDOTselectTemps,
2484                   resolveMethodDebugDOTpruneGarbage,
2485                   resolveMethodDebugDOThideSubsetReach,
2486                   resolveMethodDebugDOThideEdgeTaints );
2487     }
2488
2489     // propagate callee reachability changes to the rest
2490     // of the caller graph edges
2491     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2492
2493     propagateTokensOverEdges( edgesForPropagation, // source edges
2494                               edgePlannedChanges,  // map src edge to change set
2495                               edgesUpdated );      // list of updated edges
2496
2497     // commit beta' (beta<-betaNew)
2498     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2499     while( edgeItr.hasNext() ) {
2500       edgeItr.next().applyBetaNew();
2501     }
2502
2503
2504
2505
2506
2507
2508
2509     if( writeDebugDOTs ) {
2510       writeGraph( debugGraphPrefix+"caller40BeforeShadowMerge",
2511                   resolveMethodDebugDOTwriteLabels,
2512                   resolveMethodDebugDOTselectTemps,
2513                   resolveMethodDebugDOTpruneGarbage,
2514                   resolveMethodDebugDOThideSubsetReach,
2515                   resolveMethodDebugDOThideEdgeTaints );
2516     }
2517
2518
2519     // 4) merge shadow nodes so alloc sites are back to k
2520     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2521     while( asItr.hasNext() ) {
2522       // for each allocation site do the following to merge
2523       // shadow nodes (newest from callee) with any existing
2524       // look for the newest normal and newest shadow "slot"
2525       // not being used, transfer normal to shadow.  Keep
2526       // doing this until there are no more normal nodes, or
2527       // no empty shadow slots: then merge all remaining normal
2528       // nodes into the shadow summary.  Finally, convert all
2529       // shadow to their normal versions.
2530       AllocSite as = asItr.next();
2531       int ageNorm = 0;
2532       int ageShad = 0;
2533       while( ageNorm < allocationDepth &&
2534              ageShad < allocationDepth ) {
2535
2536         // first, are there any normal nodes left?
2537         Integer        idNorm  = as.getIthOldest( ageNorm );
2538         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2539         if( hrnNorm == null ) {
2540           // no, this age of normal node not in the caller graph
2541           ageNorm++;
2542           continue;
2543         }
2544
2545         // yes, a normal node exists, is there an empty shadow
2546         // "slot" to transfer it onto?
2547         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2548         if( !hrnShad.isWiped() ) {
2549           // no, this age of shadow node is not empty
2550           ageShad++;
2551           continue;
2552         }
2553
2554         // yes, this shadow node is empty
2555         transferOnto( hrnNorm, hrnShad );
2556         ageNorm++;
2557         ageShad++;
2558       }
2559
2560       // now, while there are still normal nodes but no shadow
2561       // slots, merge normal nodes into the shadow summary
2562       while( ageNorm < allocationDepth ) {
2563
2564         // first, are there any normal nodes left?
2565         Integer        idNorm  = as.getIthOldest( ageNorm );
2566         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2567         if( hrnNorm == null ) {
2568           // no, this age of normal node not in the caller graph
2569           ageNorm++;
2570           continue;
2571         }
2572
2573         // yes, a normal node exists, so get the shadow summary
2574         HeapRegionNode summShad = getSummaryNode( as, true );
2575         mergeIntoSummary( hrnNorm, summShad );
2576         ageNorm++;
2577       }
2578
2579       // if there is a normal summary, merge it into shadow summary
2580       Integer        idNorm   = as.getSummary();
2581       HeapRegionNode summNorm = id2hrn.get( idNorm );
2582       if( summNorm != null ) {
2583         HeapRegionNode summShad = getSummaryNode( as, true );
2584         mergeIntoSummary( summNorm, summShad );
2585       }
2586
2587       // finally, flip all existing shadow nodes onto the normal
2588       for( int i = 0; i < allocationDepth; ++i ) {
2589         Integer        idShad  = as.getIthOldestShadow( i );
2590         HeapRegionNode hrnShad = id2hrn.get( idShad );
2591         if( hrnShad != null ) {
2592           // flip it
2593           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2594           assert hrnNorm.isWiped();
2595           transferOnto( hrnShad, hrnNorm );
2596         }
2597       }
2598
2599       Integer        idShad   = as.getSummaryShadow();
2600       HeapRegionNode summShad = id2hrn.get( idShad );
2601       if( summShad != null ) {
2602         summNorm = getSummaryNode( as, false );
2603         transferOnto( summShad, summNorm );
2604       }
2605     }
2606
2607
2608
2609
2610
2611
2612     if( writeDebugDOTs ) {
2613       writeGraph( debugGraphPrefix+"caller45BeforeUnshadow",
2614                   resolveMethodDebugDOTwriteLabels,
2615                   resolveMethodDebugDOTselectTemps,
2616                   resolveMethodDebugDOTpruneGarbage,
2617                   resolveMethodDebugDOThideSubsetReach,
2618                   resolveMethodDebugDOThideEdgeTaints );
2619     }
2620
2621
2622     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2623     while( itrAllHRNodes.hasNext() ) {
2624       Map.Entry      me  = (Map.Entry)      itrAllHRNodes.next();
2625       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2626
2627       hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2628
2629       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2630       while( itrEdges.hasNext() ) {
2631         RefEdge re = itrEdges.next();
2632         re.setBeta( unshadow( re.getBeta() ) );
2633       }
2634     }
2635
2636
2637
2638
2639     if( writeDebugDOTs ) {
2640       writeGraph( debugGraphPrefix+"caller50BeforeGlobalSweep",
2641                   resolveMethodDebugDOTwriteLabels,
2642                   resolveMethodDebugDOTselectTemps,
2643                   resolveMethodDebugDOTpruneGarbage,
2644                   resolveMethodDebugDOThideSubsetReach,
2645                   resolveMethodDebugDOThideEdgeTaints );
2646     }
2647
2648
2649     // 5.
2650     if( !DISABLE_GLOBAL_SWEEP ) {
2651       globalSweep();
2652     }
2653
2654
2655     if( writeDebugDOTs ) {
2656       writeGraph( debugGraphPrefix+"caller90AfterTransfer",
2657                   resolveMethodDebugDOTwriteLabels,
2658                   resolveMethodDebugDOTselectTemps,
2659                   resolveMethodDebugDOTpruneGarbage,
2660                   resolveMethodDebugDOThideSubsetReach,
2661                   resolveMethodDebugDOThideEdgeTaints );
2662     }
2663   }
2664
2665
2666
2667   ////////////////////////////////////////////////////
2668   //
2669   //  Abstract garbage collection simply removes
2670   //  heap region nodes that are not mechanically
2671   //  reachable from a root set.  This step is
2672   //  essential for testing node and edge existence
2673   //  predicates efficiently
2674   //
2675   ////////////////////////////////////////////////////
2676   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2677
2678     // calculate a root set, will be different for Java
2679     // version of analysis versus Bamboo version
2680     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2681
2682     // visit every variable in graph while building root
2683     // set, and do iterating on a copy, so we can remove
2684     // dead variables while we're at this
2685     Iterator makeCopyItr = td2vn.entrySet().iterator();
2686     Set      entrysCopy  = new HashSet();
2687     while( makeCopyItr.hasNext() ) {
2688       entrysCopy.add( makeCopyItr.next() );
2689     }
2690
2691     Iterator eItr = entrysCopy.iterator();
2692     while( eItr.hasNext() ) {
2693       Map.Entry      me = (Map.Entry)      eItr.next();
2694       TempDescriptor td = (TempDescriptor) me.getKey();
2695       VariableNode   vn = (VariableNode)   me.getValue();
2696
2697       if( liveSet.contains( td ) ) {
2698         toVisit.add( vn );
2699
2700       } else {
2701         // dead var, remove completely from graph
2702         td2vn.remove( td );
2703         clearRefEdgesFrom( vn, null, null, true );
2704       }
2705     }
2706
2707     // everything visited in a traversal is
2708     // considered abstractly live
2709     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2710
2711     while( !toVisit.isEmpty() ) {
2712       RefSrcNode rsn = toVisit.iterator().next();
2713       toVisit.remove( rsn );
2714       visited.add( rsn );
2715
2716       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2717       while( hrnItr.hasNext() ) {
2718         RefEdge        edge = hrnItr.next();
2719         HeapRegionNode hrn  = edge.getDst();
2720
2721         if( !visited.contains( hrn ) ) {
2722           toVisit.add( hrn );
2723         }
2724       }
2725     }
2726
2727     // get a copy of the set to iterate over because
2728     // we're going to monkey with the graph when we
2729     // identify a garbage node
2730     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2731     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2732     while( hrnItr.hasNext() ) {
2733       hrnAllPrior.add( hrnItr.next() );
2734     }
2735
2736     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2737     while( hrnAllItr.hasNext() ) {
2738       HeapRegionNode hrn = hrnAllItr.next();
2739
2740       if( !visited.contains( hrn ) ) {
2741
2742         // heap region nodes are compared across ReachGraph
2743         // objects by their integer ID, so when discarding
2744         // garbage nodes we must also discard entries in
2745         // the ID -> heap region hashtable.
2746         id2hrn.remove( hrn.getID() );
2747
2748         // RefEdge objects are two-way linked between
2749         // nodes, so when a node is identified as garbage,
2750         // actively clear references to and from it so
2751         // live nodes won't have dangling RefEdge's
2752         wipeOut( hrn, true );
2753
2754         // if we just removed the last node from an allocation
2755         // site, it should be taken out of the ReachGraph's list
2756         AllocSite as = hrn.getAllocSite();
2757         if( !hasNodesOf( as ) ) {
2758           allocSites.remove( as );
2759         }
2760       }
2761     }
2762   }
2763
2764   protected boolean hasNodesOf( AllocSite as ) {
2765     if( id2hrn.containsKey( as.getSummary() ) ) {
2766       return true;
2767     }
2768
2769     for( int i = 0; i < allocationDepth; ++i ) {
2770       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2771         return true;
2772       }
2773     }
2774     return false;
2775   }
2776
2777
2778   ////////////////////////////////////////////////////
2779   //
2780   //  This global sweep is an optional step to prune
2781   //  reachability sets that are not internally
2782   //  consistent with the global graph.  It should be
2783   //  invoked after strong updates or method calls.
2784   //
2785   ////////////////////////////////////////////////////
2786   public void globalSweep() {
2787
2788     // boldB is part of the phase 1 sweep
2789     // it has an in-context table and an out-of-context table
2790     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2791       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2792
2793     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2794       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2795
2796     // visit every heap region to initialize alphaNew and betaNew,
2797     // and make a map of every hrnID to the source nodes it should
2798     // propagate forward from.  In-context flagged hrnID's propagate
2799     // from only the in-context node they name, but out-of-context
2800     // ID's may propagate from several out-of-context nodes
2801     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2802       new Hashtable< Integer, Set<HeapRegionNode> >();
2803
2804     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2805       new Hashtable< Integer, Set<HeapRegionNode> >();
2806
2807
2808     Iterator itrHrns = id2hrn.entrySet().iterator();
2809     while( itrHrns.hasNext() ) {
2810       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2811       Integer        hrnID = (Integer)        me.getKey();
2812       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2813
2814       // assert that this node and incoming edges have clean alphaNew
2815       // and betaNew sets, respectively
2816       assert rsetEmpty.equals( hrn.getAlphaNew() );
2817
2818       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2819       while( itrRers.hasNext() ) {
2820         RefEdge edge = itrRers.next();
2821         assert rsetEmpty.equals( edge.getBetaNew() );
2822       }
2823
2824       // make a mapping of IDs to heap regions they propagate from
2825       if( hrn.isFlagged() ) {
2826         assert !hrn.isOutOfContext();
2827         assert !icID2srcs.containsKey( hrn.getID() );
2828
2829         // in-context flagged node IDs simply propagate from the
2830         // node they name
2831         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2832         srcs.add( hrn );
2833         icID2srcs.put( hrn.getID(), srcs );
2834       }
2835
2836       if( hrn.isOutOfContext() ) {
2837         assert !hrn.isFlagged();
2838
2839         // the reachability states on an out-of-context
2840         // node are not really important (combinations of
2841         // IDs or arity)--what matters is that the states
2842         // specify which nodes this out-of-context node
2843         // stands in for.  For example, if the state [17?, 19*]
2844         // appears on the ooc node, it may serve as a source
2845         // for node 17? and a source for node 19.
2846         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2847         while( stateItr.hasNext() ) {
2848           ReachState state = stateItr.next();
2849
2850           Iterator<ReachTuple> rtItr = state.iterator();
2851           while( rtItr.hasNext() ) {
2852             ReachTuple rt = rtItr.next();
2853             assert rt.isOutOfContext();
2854
2855             Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2856             if( srcs == null ) {
2857               srcs = new HashSet<HeapRegionNode>();
2858             }
2859             srcs.add( hrn );
2860             oocID2srcs.put( rt.getHrnID(), srcs );
2861           }
2862         }
2863       }
2864     }
2865
2866     // calculate boldB for all hrnIDs identified by the above
2867     // node traversal, propagating from every source
2868     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2869
2870       Integer             hrnID;
2871       Set<HeapRegionNode> srcs;
2872       boolean             inContext;
2873
2874       if( !icID2srcs.isEmpty() ) {
2875         Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2876         hrnID = (Integer)             me.getKey();
2877         srcs  = (Set<HeapRegionNode>) me.getValue();
2878         inContext = true;
2879         icID2srcs.remove( hrnID );
2880
2881       } else {
2882         assert !oocID2srcs.isEmpty();
2883
2884         Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2885         hrnID = (Integer)             me.getKey();
2886         srcs  = (Set<HeapRegionNode>) me.getValue();
2887         inContext = false;
2888         oocID2srcs.remove( hrnID );
2889       }
2890
2891
2892       Hashtable<RefEdge, ReachSet> boldB_f =
2893         new Hashtable<RefEdge, ReachSet>();
2894
2895       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2896
2897       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2898       while( hrnItr.hasNext() ) {
2899         HeapRegionNode hrn = hrnItr.next();
2900
2901         assert workSetEdges.isEmpty();
2902
2903         // initial boldB_f constraints
2904         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2905         while( itrRees.hasNext() ) {
2906           RefEdge edge = itrRees.next();
2907
2908           assert !boldB_f.containsKey( edge );
2909           boldB_f.put( edge, edge.getBeta() );
2910
2911           assert !workSetEdges.contains( edge );
2912           workSetEdges.add( edge );
2913         }
2914
2915         // enforce the boldB_f constraint at edges until we reach a fixed point
2916         while( !workSetEdges.isEmpty() ) {
2917           RefEdge edge = workSetEdges.iterator().next();
2918           workSetEdges.remove( edge );
2919
2920           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2921           while( itrPrime.hasNext() ) {
2922             RefEdge edgePrime = itrPrime.next();
2923
2924             ReachSet prevResult   = boldB_f.get( edgePrime );
2925             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2926                                                             edgePrime.getBeta()
2927                                                             );
2928
2929             if( prevResult == null ||
2930                 Canonical.unionORpreds( prevResult,
2931                                         intersection ).size()
2932                 > prevResult.size()
2933                 ) {
2934
2935               if( prevResult == null ) {
2936                 boldB_f.put( edgePrime,
2937                              Canonical.unionORpreds( edgePrime.getBeta(),
2938                                                      intersection
2939                                                      )
2940                              );
2941               } else {
2942                 boldB_f.put( edgePrime,
2943                              Canonical.unionORpreds( prevResult,
2944                                                      intersection
2945                                                      )
2946                              );
2947               }
2948               workSetEdges.add( edgePrime );
2949             }
2950           }
2951         }
2952       }
2953
2954       if( inContext ) {
2955         boldBic.put( hrnID, boldB_f );
2956       } else {
2957         boldBooc.put( hrnID, boldB_f );
2958       }
2959     }
2960
2961
2962     // use boldB to prune hrnIDs from alpha states that are impossible
2963     // and propagate the differences backwards across edges
2964     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2965
2966     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2967       new Hashtable<RefEdge, ChangeSet>();
2968
2969
2970     itrHrns = id2hrn.entrySet().iterator();
2971     while( itrHrns.hasNext() ) {
2972       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2973       Integer        hrnID = (Integer)        me.getKey();
2974       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2975
2976       // out-of-context nodes don't participate in the
2977       // global sweep, they serve as sources for the pass
2978       // performed above
2979       if( hrn.isOutOfContext() ) {
2980         continue;
2981       }
2982
2983       // the inherent states of a region are the exception
2984       // to removal as the global sweep prunes
2985       ReachTuple rtException = ReachTuple.factory( hrnID,
2986                                                    !hrn.isSingleObject(),
2987                                                    ReachTuple.ARITY_ONE,
2988                                                    false // out-of-context
2989                                                    );
2990
2991       ChangeSet cts = ChangeSet.factory();
2992
2993       // mark hrnIDs for removal
2994       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2995       while( stateItr.hasNext() ) {
2996         ReachState stateOld = stateItr.next();
2997
2998         ReachState markedHrnIDs = ReachState.factory();
2999
3000         Iterator<ReachTuple> rtItr = stateOld.iterator();
3001         while( rtItr.hasNext() ) {
3002           ReachTuple rtOld = rtItr.next();
3003
3004           // never remove the inherent hrnID from a flagged region
3005           // because it is trivially satisfied
3006           if( hrn.isFlagged() ) {
3007             if( rtOld == rtException ) {
3008               continue;
3009             }
3010           }
3011
3012           // does boldB allow this hrnID?
3013           boolean foundState = false;
3014           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3015           while( incidentEdgeItr.hasNext() ) {
3016             RefEdge incidentEdge = incidentEdgeItr.next();
3017
3018             Hashtable<RefEdge, ReachSet> B;
3019             if( rtOld.isOutOfContext() ) {
3020               B = boldBooc.get( rtOld.getHrnID() );
3021             } else {
3022
3023               if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
3024                 // let symbols not in the graph get pruned
3025                 break;
3026               }
3027
3028               B = boldBic.get( rtOld.getHrnID() );
3029             }
3030
3031             if( B != null ) {
3032               ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3033               if( boldB_rtOld_incident != null &&
3034                   boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3035                   ) {
3036                 foundState = true;
3037               }
3038             }
3039           }
3040
3041           if( !foundState ) {
3042             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3043           }
3044         }
3045
3046         // if there is nothing marked, just move on
3047         if( markedHrnIDs.isEmpty() ) {
3048           hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3049                                           stateOld
3050                                           )
3051                            );
3052           continue;
3053         }
3054
3055         // remove all marked hrnIDs and establish a change set that should
3056         // propagate backwards over edges from this node
3057         ReachState statePruned = ReachState.factory();
3058         rtItr = stateOld.iterator();
3059         while( rtItr.hasNext() ) {
3060           ReachTuple rtOld = rtItr.next();
3061
3062           if( !markedHrnIDs.containsTuple( rtOld ) ) {
3063             statePruned = Canonical.add( statePruned, rtOld );
3064           }
3065         }
3066         assert !stateOld.equals( statePruned );
3067
3068         hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3069                                         statePruned
3070                                         )
3071                          );
3072         ChangeTuple ct = ChangeTuple.factory( stateOld,
3073                                               statePruned
3074                                               );
3075         cts = Canonical.add( cts, ct );
3076       }
3077
3078       // throw change tuple set on all incident edges
3079       if( !cts.isEmpty() ) {
3080         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3081         while( incidentEdgeItr.hasNext() ) {
3082           RefEdge incidentEdge = incidentEdgeItr.next();
3083
3084           edgesForPropagation.add( incidentEdge );
3085
3086           if( edgePlannedChanges.get( incidentEdge ) == null ) {
3087             edgePlannedChanges.put( incidentEdge, cts );
3088           } else {
3089             edgePlannedChanges.put(
3090                                    incidentEdge,
3091                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
3092                                                     cts
3093                                                     )
3094                                     );
3095           }
3096         }
3097       }
3098     }
3099
3100     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3101
3102     propagateTokensOverEdges( edgesForPropagation,
3103                               edgePlannedChanges,
3104                               edgesUpdated );
3105
3106     // at the end of the 1st phase reference edges have
3107     // beta, betaNew that correspond to beta and betaR
3108     //
3109     // commit beta<-betaNew, so beta=betaR and betaNew
3110     // will represent the beta' calculation in 2nd phase
3111     //
3112     // commit alpha<-alphaNew because it won't change
3113     HashSet<RefEdge> res = new HashSet<RefEdge>();
3114
3115     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3116     while( nodeItr.hasNext() ) {
3117       HeapRegionNode hrn = nodeItr.next();
3118
3119       // as mentioned above, out-of-context nodes only serve
3120       // as sources of reach states for the sweep, not part
3121       // of the changes
3122       if( hrn.isOutOfContext() ) {
3123         assert hrn.getAlphaNew().equals( rsetEmpty );
3124       } else {
3125         hrn.applyAlphaNew();
3126       }
3127
3128       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3129       while( itrRes.hasNext() ) {
3130         res.add( itrRes.next() );
3131       }
3132     }
3133
3134
3135     // 2nd phase
3136     Iterator<RefEdge> edgeItr = res.iterator();
3137     while( edgeItr.hasNext() ) {
3138       RefEdge        edge = edgeItr.next();
3139       HeapRegionNode hrn  = edge.getDst();
3140
3141       // commit results of last phase
3142       if( edgesUpdated.contains( edge ) ) {
3143         edge.applyBetaNew();
3144       }
3145
3146       // compute intial condition of 2nd phase
3147       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3148                                                hrn.getAlpha()
3149                                                )
3150                        );
3151     }
3152
3153     // every edge in the graph is the initial workset
3154     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3155     while( !edgeWorkSet.isEmpty() ) {
3156       RefEdge edgePrime = edgeWorkSet.iterator().next();
3157       edgeWorkSet.remove( edgePrime );
3158
3159       RefSrcNode rsn = edgePrime.getSrc();
3160       if( !(rsn instanceof HeapRegionNode) ) {
3161         continue;
3162       }
3163       HeapRegionNode hrn = (HeapRegionNode) rsn;
3164
3165       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3166       while( itrEdge.hasNext() ) {
3167         RefEdge edge = itrEdge.next();
3168
3169         ReachSet prevResult = edge.getBetaNew();
3170         assert prevResult != null;
3171
3172         ReachSet intersection =
3173           Canonical.intersection( edge.getBeta(),
3174                                   edgePrime.getBetaNew()
3175                                   );
3176
3177         if( Canonical.unionORpreds( prevResult,
3178                                     intersection
3179                                     ).size()
3180             > prevResult.size()
3181             ) {
3182
3183           edge.setBetaNew(
3184                           Canonical.unionORpreds( prevResult,
3185                                                   intersection
3186                                                   )
3187                            );
3188           edgeWorkSet.add( edge );
3189         }
3190       }
3191     }
3192
3193     // commit beta' (beta<-betaNew)
3194     edgeItr = res.iterator();
3195     while( edgeItr.hasNext() ) {
3196       edgeItr.next().applyBetaNew();
3197     }
3198   }
3199
3200
3201   // a useful assertion for debugging:
3202   // every in-context tuple on any edge or
3203   // any node should name a node that is
3204   // part of the graph
3205   public boolean inContextTuplesInGraph() {
3206
3207     Iterator hrnItr = id2hrn.entrySet().iterator();
3208     while( hrnItr.hasNext() ) {
3209       Map.Entry      me  = (Map.Entry)      hrnItr.next();
3210       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3211
3212       {
3213         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3214         while( stateItr.hasNext() ) {
3215           ReachState state = stateItr.next();
3216
3217           Iterator<ReachTuple> rtItr = state.iterator();
3218           while( rtItr.hasNext() ) {
3219             ReachTuple rt = rtItr.next();
3220
3221             if( !rt.isOutOfContext() ) {
3222               if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3223                 System.out.println( rt.getHrnID()+" is missing" );
3224                 return false;
3225               }
3226             }
3227           }
3228         }
3229       }
3230
3231       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3232       while( edgeItr.hasNext() ) {
3233         RefEdge edge = edgeItr.next();
3234
3235         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3236         while( stateItr.hasNext() ) {
3237           ReachState state = stateItr.next();
3238
3239           Iterator<ReachTuple> rtItr = state.iterator();
3240           while( rtItr.hasNext() ) {
3241             ReachTuple rt = rtItr.next();
3242
3243             if( !rt.isOutOfContext() ) {
3244               if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3245                 System.out.println( rt.getHrnID()+" is missing" );
3246                 return false;
3247               }
3248             }
3249           }
3250         }
3251       }
3252     }
3253
3254     return true;
3255   }
3256
3257
3258   // another useful assertion for debugging
3259   public boolean noEmptyReachSetsInGraph() {
3260
3261     Iterator hrnItr = id2hrn.entrySet().iterator();
3262     while( hrnItr.hasNext() ) {
3263       Map.Entry      me  = (Map.Entry)      hrnItr.next();
3264       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3265
3266       if( !hrn.isOutOfContext() &&
3267           !hrn.isWiped()        &&
3268           hrn.getAlpha().isEmpty()
3269           ) {
3270         System.out.println( "!!! "+hrn+" has an empty ReachSet !!!" );
3271         return false;
3272       }
3273
3274       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3275       while( edgeItr.hasNext() ) {
3276         RefEdge edge = edgeItr.next();
3277
3278         if( edge.getBeta().isEmpty() ) {
3279           System.out.println( "!!! "+edge+" has an empty ReachSet !!!" );
3280           return false;
3281         }
3282       }
3283     }
3284
3285     return true;
3286   }
3287
3288
3289   public boolean everyReachStateWTrue() {
3290
3291     Iterator hrnItr = id2hrn.entrySet().iterator();
3292     while( hrnItr.hasNext() ) {
3293       Map.Entry      me  = (Map.Entry)      hrnItr.next();
3294       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3295
3296       {
3297         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3298         while( stateItr.hasNext() ) {
3299           ReachState state = stateItr.next();
3300
3301           if( !state.getPreds().equals( predsTrue ) ) {
3302             return false;
3303           }
3304         }
3305       }
3306
3307       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3308       while( edgeItr.hasNext() ) {
3309         RefEdge edge = edgeItr.next();
3310
3311         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3312         while( stateItr.hasNext() ) {
3313           ReachState state = stateItr.next();
3314
3315           if( !state.getPreds().equals( predsTrue ) ) {
3316             return false;
3317           }
3318         }
3319       }
3320     }
3321
3322     return true;
3323   }
3324
3325
3326
3327
3328   ////////////////////////////////////////////////////
3329   // in merge() and equals() methods the suffix A
3330   // represents the passed in graph and the suffix
3331   // B refers to the graph in this object
3332   // Merging means to take the incoming graph A and
3333   // merge it into B, so after the operation graph B
3334   // is the final result.
3335   ////////////////////////////////////////////////////
3336   protected void merge( ReachGraph rg ) {
3337
3338     if( rg == null ) {
3339       return;
3340     }
3341
3342     mergeNodes     ( rg );
3343     mergeRefEdges  ( rg );
3344     mergeAllocSites( rg );
3345   }
3346
3347   protected void mergeNodes( ReachGraph rg ) {
3348
3349     // start with heap region nodes
3350     Set      sA = rg.id2hrn.entrySet();
3351     Iterator iA = sA.iterator();
3352     while( iA.hasNext() ) {
3353       Map.Entry      meA  = (Map.Entry)      iA.next();
3354       Integer        idA  = (Integer)        meA.getKey();
3355       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3356
3357       // if this graph doesn't have a node the
3358       // incoming graph has, allocate it
3359       if( !id2hrn.containsKey( idA ) ) {
3360         HeapRegionNode hrnB = hrnA.copy();
3361         id2hrn.put( idA, hrnB );
3362
3363       } else {
3364         // otherwise this is a node present in both graphs
3365         // so make the new reachability set a union of the
3366         // nodes' reachability sets
3367         HeapRegionNode hrnB = id2hrn.get( idA );
3368         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3369                                         hrnA.getAlpha()
3370                                         )
3371                        );
3372
3373         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3374                                        hrnA.getPreds()
3375                                        )
3376                        );
3377
3378
3379
3380         if( !hrnA.equals( hrnB ) ) {
3381           rg.writeGraph( "graphA" );
3382           this.writeGraph( "graphB" );
3383           throw new Error( "flagged not matching" );
3384         }
3385
3386
3387
3388       }
3389     }
3390
3391     // now add any variable nodes that are in graph B but
3392     // not in A
3393     sA = rg.td2vn.entrySet();
3394     iA = sA.iterator();
3395     while( iA.hasNext() ) {
3396       Map.Entry      meA = (Map.Entry)      iA.next();
3397       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3398       VariableNode   lnA = (VariableNode)   meA.getValue();
3399
3400       // if the variable doesn't exist in B, allocate and add it
3401       VariableNode lnB = getVariableNodeFromTemp( tdA );
3402     }
3403   }
3404
3405   protected void mergeRefEdges( ReachGraph rg ) {
3406
3407     // between heap regions
3408     Set      sA = rg.id2hrn.entrySet();
3409     Iterator iA = sA.iterator();
3410     while( iA.hasNext() ) {
3411       Map.Entry      meA  = (Map.Entry)      iA.next();
3412       Integer        idA  = (Integer)        meA.getKey();
3413       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3414
3415       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3416       while( heapRegionsItrA.hasNext() ) {
3417         RefEdge        edgeA     = heapRegionsItrA.next();
3418         HeapRegionNode hrnChildA = edgeA.getDst();
3419         Integer        idChildA  = hrnChildA.getID();
3420
3421         // at this point we know an edge in graph A exists
3422         // idA -> idChildA, does this exist in B?
3423         assert id2hrn.containsKey( idA );
3424         HeapRegionNode hrnB        = id2hrn.get( idA );
3425         RefEdge        edgeToMerge = null;
3426
3427         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3428         while( heapRegionsItrB.hasNext() &&
3429                edgeToMerge == null          ) {
3430
3431           RefEdge        edgeB     = heapRegionsItrB.next();
3432           HeapRegionNode hrnChildB = edgeB.getDst();
3433           Integer        idChildB  = hrnChildB.getID();
3434
3435           // don't use the RefEdge.equals() here because
3436           // we're talking about existence between graphs,
3437           // not intragraph equal
3438           if( idChildB.equals( idChildA ) &&
3439               edgeB.typeAndFieldEquals( edgeA ) ) {
3440
3441             edgeToMerge = edgeB;
3442           }
3443         }
3444
3445         // if the edge from A was not found in B,
3446         // add it to B.
3447         if( edgeToMerge == null ) {
3448           assert id2hrn.containsKey( idChildA );
3449           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3450           edgeToMerge = edgeA.copy();
3451           edgeToMerge.setSrc( hrnB );
3452           edgeToMerge.setDst( hrnChildB );
3453           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3454         }
3455         // otherwise, the edge already existed in both graphs
3456         // so merge their reachability sets
3457         else {
3458           // just replace this beta set with the union
3459           assert edgeToMerge != null;
3460           edgeToMerge.setBeta(
3461                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3462                                                edgeA.getBeta()
3463                                                )
3464                               );
3465           edgeToMerge.setPreds(
3466                                Canonical.join( edgeToMerge.getPreds(),
3467                                                edgeA.getPreds()
3468                                                )
3469                                );
3470         }
3471       }
3472     }
3473
3474     // and then again from variable nodes
3475     sA = rg.td2vn.entrySet();
3476     iA = sA.iterator();
3477     while( iA.hasNext() ) {
3478       Map.Entry      meA = (Map.Entry)      iA.next();
3479       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3480       VariableNode   vnA = (VariableNode)   meA.getValue();
3481
3482       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3483       while( heapRegionsItrA.hasNext() ) {
3484         RefEdge        edgeA     = heapRegionsItrA.next();
3485         HeapRegionNode hrnChildA = edgeA.getDst();
3486         Integer        idChildA  = hrnChildA.getID();
3487
3488         // at this point we know an edge in graph A exists
3489         // tdA -> idChildA, does this exist in B?
3490         assert td2vn.containsKey( tdA );
3491         VariableNode vnB         = td2vn.get( tdA );
3492         RefEdge      edgeToMerge = null;
3493
3494         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3495         while( heapRegionsItrB.hasNext() &&
3496                edgeToMerge == null          ) {
3497
3498           RefEdge        edgeB     = heapRegionsItrB.next();
3499           HeapRegionNode hrnChildB = edgeB.getDst();
3500           Integer        idChildB  = hrnChildB.getID();
3501
3502           // don't use the RefEdge.equals() here because
3503           // we're talking about existence between graphs
3504           if( idChildB.equals( idChildA ) &&
3505               edgeB.typeAndFieldEquals( edgeA ) ) {
3506
3507             edgeToMerge = edgeB;
3508           }
3509         }
3510
3511         // if the edge from A was not found in B,
3512         // add it to B.
3513         if( edgeToMerge == null ) {
3514           assert id2hrn.containsKey( idChildA );
3515           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3516           edgeToMerge = edgeA.copy();
3517           edgeToMerge.setSrc( vnB );
3518           edgeToMerge.setDst( hrnChildB );
3519           addRefEdge( vnB, hrnChildB, edgeToMerge );
3520         }
3521         // otherwise, the edge already existed in both graphs
3522         // so merge their reachability sets
3523         else {
3524           // just replace this beta set with the union
3525           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3526                                                 edgeA.getBeta()
3527                                                 )
3528                                );
3529           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3530                                                 edgeA.getPreds()
3531                                                 )
3532                                 );
3533         }
3534       }
3535     }
3536   }
3537
3538   protected void mergeAllocSites( ReachGraph rg ) {
3539     allocSites.addAll( rg.allocSites );
3540   }
3541
3542
3543
3544   static boolean dbgEquals = false;
3545
3546
3547   // it is necessary in the equals() member functions
3548   // to "check both ways" when comparing the data
3549   // structures of two graphs.  For instance, if all
3550   // edges between heap region nodes in graph A are
3551   // present and equal in graph B it is not sufficient
3552   // to say the graphs are equal.  Consider that there
3553   // may be edges in graph B that are not in graph A.
3554   // the only way to know that all edges in both graphs
3555   // are equally present is to iterate over both data
3556   // structures and compare against the other graph.
3557   public boolean equals( ReachGraph rg ) {
3558
3559     if( rg == null ) {
3560       if( dbgEquals ) {
3561         System.out.println( "rg is null" );
3562       }
3563       return false;
3564     }
3565
3566     if( !areHeapRegionNodesEqual( rg ) ) {
3567       if( dbgEquals ) {
3568         System.out.println( "hrn not equal" );
3569       }
3570       return false;
3571     }
3572
3573     if( !areVariableNodesEqual( rg ) ) {
3574       if( dbgEquals ) {
3575         System.out.println( "vars not equal" );
3576       }
3577       return false;
3578     }
3579
3580     if( !areRefEdgesEqual( rg ) ) {
3581       if( dbgEquals ) {
3582         System.out.println( "edges not equal" );
3583       }
3584       return false;
3585     }
3586
3587     // if everything is equal up to this point,
3588     // assert that allocSites is also equal--
3589     // this data is redundant but kept for efficiency
3590     assert allocSites.equals( rg.allocSites );
3591
3592     return true;
3593   }
3594
3595
3596   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3597
3598     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3599       return false;
3600     }
3601
3602     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3603       return false;
3604     }
3605
3606     return true;
3607   }
3608
3609   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3610                                                         ReachGraph rgB ) {
3611     Set      sA = rgA.id2hrn.entrySet();
3612     Iterator iA = sA.iterator();
3613     while( iA.hasNext() ) {
3614       Map.Entry      meA  = (Map.Entry)      iA.next();
3615       Integer        idA  = (Integer)        meA.getKey();
3616       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3617
3618       if( !rgB.id2hrn.containsKey( idA ) ) {
3619         return false;
3620       }
3621
3622       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3623       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3624         return false;
3625       }
3626     }
3627
3628     return true;
3629   }
3630
3631   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3632
3633     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3634       return false;
3635     }
3636
3637     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3638       return false;
3639     }
3640
3641     return true;
3642   }
3643
3644   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3645                                                        ReachGraph rgB ) {
3646     Set      sA = rgA.td2vn.entrySet();
3647     Iterator iA = sA.iterator();
3648     while( iA.hasNext() ) {
3649       Map.Entry      meA = (Map.Entry)      iA.next();
3650       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3651
3652       if( !rgB.td2vn.containsKey( tdA ) ) {
3653         return false;
3654       }
3655     }
3656
3657     return true;
3658   }
3659
3660
3661   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3662     if( !areallREinAandBequal( this, rg ) ) {
3663       return false;
3664     }
3665
3666     if( !areallREinAandBequal( rg, this ) ) {
3667       return false;
3668     }
3669
3670     return true;
3671   }
3672
3673   static protected boolean areallREinAandBequal( ReachGraph rgA,
3674                                                  ReachGraph rgB ) {
3675
3676     // check all the heap region->heap region edges
3677     Set      sA = rgA.id2hrn.entrySet();
3678     Iterator iA = sA.iterator();
3679     while( iA.hasNext() ) {
3680       Map.Entry      meA  = (Map.Entry)      iA.next();
3681       Integer        idA  = (Integer)        meA.getKey();
3682       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3683
3684       // we should have already checked that the same
3685       // heap regions exist in both graphs
3686       assert rgB.id2hrn.containsKey( idA );
3687
3688       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3689         return false;
3690       }
3691
3692       // then check every edge in B for presence in A, starting
3693       // from the same parent HeapRegionNode
3694       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3695
3696       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3697         return false;
3698       }
3699     }
3700
3701     // then check all the variable->heap region edges
3702     sA = rgA.td2vn.entrySet();
3703     iA = sA.iterator();
3704     while( iA.hasNext() ) {
3705       Map.Entry      meA = (Map.Entry)      iA.next();
3706       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3707       VariableNode   vnA = (VariableNode)   meA.getValue();
3708
3709       // we should have already checked that the same
3710       // label nodes exist in both graphs
3711       assert rgB.td2vn.containsKey( tdA );
3712
3713       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3714         return false;
3715       }
3716
3717       // then check every edge in B for presence in A, starting
3718       // from the same parent VariableNode
3719       VariableNode vnB = rgB.td2vn.get( tdA );
3720
3721       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3722         return false;
3723       }
3724     }
3725
3726     return true;
3727   }
3728
3729
3730   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3731                                                   RefSrcNode rnA,
3732                                                   ReachGraph rgB ) {
3733
3734     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3735     while( itrA.hasNext() ) {
3736       RefEdge        edgeA     = itrA.next();
3737       HeapRegionNode hrnChildA = edgeA.getDst();
3738       Integer        idChildA  = hrnChildA.getID();
3739
3740       assert rgB.id2hrn.containsKey( idChildA );
3741
3742       // at this point we know an edge in graph A exists
3743       // rnA -> idChildA, does this exact edge exist in B?
3744       boolean edgeFound = false;
3745
3746       RefSrcNode rnB = null;
3747       if( rnA instanceof HeapRegionNode ) {
3748         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3749         rnB = rgB.id2hrn.get( hrnA.getID() );
3750       } else {
3751         VariableNode vnA = (VariableNode) rnA;
3752         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3753       }
3754
3755       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3756       while( itrB.hasNext() ) {
3757         RefEdge        edgeB     = itrB.next();
3758         HeapRegionNode hrnChildB = edgeB.getDst();
3759         Integer        idChildB  = hrnChildB.getID();
3760
3761         if( idChildA.equals( idChildB ) &&
3762             edgeA.typeAndFieldEquals( edgeB ) ) {
3763
3764           // there is an edge in the right place with the right field,
3765           // but do they have the same attributes?
3766           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3767               edgeA.equalsPreds( edgeB )
3768               ) {
3769             edgeFound = true;
3770           }
3771         }
3772       }
3773
3774       if( !edgeFound ) {
3775         return false;
3776       }
3777     }
3778
3779     return true;
3780   }
3781
3782
3783   // can be used to assert monotonicity
3784   static public boolean isNoSmallerThan( ReachGraph rgA,
3785                                          ReachGraph rgB ) {
3786
3787     //System.out.println( "*** Asking if A is no smaller than B ***" );
3788
3789
3790     Iterator iA = rgA.id2hrn.entrySet().iterator();
3791     while( iA.hasNext() ) {
3792       Map.Entry      meA  = (Map.Entry)      iA.next();
3793       Integer        idA  = (Integer)        meA.getKey();
3794       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3795
3796       if( !rgB.id2hrn.containsKey( idA ) ) {
3797         System.out.println( "  regions smaller" );
3798         return false;
3799       }
3800
3801       //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3802       /* NOT EQUALS, NO SMALLER THAN!
3803       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3804         System.out.println( "  regions smaller" );
3805         return false;
3806       }
3807       */
3808     }
3809
3810     // this works just fine, no smaller than
3811     if( !areallVNinAalsoinBandequal( rgA, rgB ) ) {
3812       System.out.println( "  vars smaller:" );
3813       System.out.println( "    A:"+rgA.td2vn.keySet() );
3814       System.out.println( "    B:"+rgB.td2vn.keySet() );
3815       return false;
3816     }
3817
3818
3819     iA = rgA.id2hrn.entrySet().iterator();
3820     while( iA.hasNext() ) {
3821       Map.Entry      meA  = (Map.Entry)      iA.next();
3822       Integer        idA  = (Integer)        meA.getKey();
3823       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3824
3825       Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
3826       while( reItr.hasNext() ) {
3827         RefEdge    edgeA = reItr.next();
3828         RefSrcNode rsnA  = edgeA.getSrc();
3829
3830         // we already checked that nodes were present
3831         HeapRegionNode hrnB = rgB.id2hrn.get( hrnA.getID() );
3832         assert hrnB != null;
3833
3834         RefSrcNode rsnB;
3835         if( rsnA instanceof VariableNode ) {
3836           VariableNode vnA = (VariableNode) rsnA;
3837           rsnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3838
3839         } else {
3840           HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
3841           rsnB = rgB.id2hrn.get( hrnSrcA.getID() );
3842         }
3843         assert rsnB != null;
3844
3845         RefEdge edgeB = rsnB.getReferenceTo( hrnB,
3846                                              edgeA.getType(),
3847                                              edgeA.getField()
3848                                              );
3849         if( edgeB == null ) {
3850           System.out.println( "  edges smaller:" );
3851           return false;
3852         }
3853
3854         // REMEMBER, IS NO SMALLER THAN
3855         /*
3856           System.out.println( "  edges smaller" );
3857           return false;
3858           }
3859         */
3860
3861       }
3862     }
3863
3864
3865     return true;
3866   }
3867
3868
3869
3870
3871
3872   // this analysis no longer has the "match anything"
3873   // type which was represented by null
3874   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3875                                              TypeDescriptor td2 ) {
3876     assert td1 != null;
3877     assert td2 != null;
3878
3879     if( td1.isNull() ) {
3880       return td2;
3881     }
3882     if( td2.isNull() ) {
3883       return td1;
3884     }
3885     return typeUtil.mostSpecific( td1, td2 );
3886   }
3887
3888   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3889                                              TypeDescriptor td2,
3890                                              TypeDescriptor td3 ) {
3891
3892     return mostSpecificType( td1,
3893                              mostSpecificType( td2, td3 )
3894                              );
3895   }
3896
3897   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3898                                              TypeDescriptor td2,
3899                                              TypeDescriptor td3,
3900                                              TypeDescriptor td4 ) {
3901
3902     return mostSpecificType( mostSpecificType( td1, td2 ),
3903                              mostSpecificType( td3, td4 )
3904                              );
3905   }
3906
3907   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3908                                     TypeDescriptor possibleChild ) {
3909     assert possibleSuper != null;
3910     assert possibleChild != null;
3911
3912     if( possibleSuper.isNull() ||
3913         possibleChild.isNull() ) {
3914       return true;
3915     }
3916
3917     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3918   }
3919
3920
3921   protected boolean hasMatchingField( HeapRegionNode src,
3922                                       RefEdge        edge ) {
3923
3924     TypeDescriptor tdSrc = src.getType();
3925     assert tdSrc != null;
3926
3927     if( tdSrc.isArray() ) {
3928       TypeDescriptor td = edge.getType();
3929       assert td != null;
3930
3931       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3932       assert tdSrcDeref != null;
3933
3934       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3935         return false;
3936       }
3937
3938       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3939     }
3940
3941     // if it's not a class, it doesn't have any fields to match
3942     if( !tdSrc.isClass() ) {
3943       return false;
3944     }
3945
3946     ClassDescriptor cd = tdSrc.getClassDesc();
3947     while( cd != null ) {
3948       Iterator fieldItr = cd.getFields();
3949
3950       while( fieldItr.hasNext() ) {
3951         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3952
3953         if( fd.getType().equals( edge.getType() ) &&
3954             fd.getSymbol().equals( edge.getField() ) ) {
3955           return true;
3956         }
3957       }
3958
3959       cd = cd.getSuperDesc();
3960     }
3961
3962     // otherwise it is a class with fields
3963     // but we didn't find a match
3964     return false;
3965   }
3966
3967   protected boolean hasMatchingType( RefEdge        edge,
3968                                      HeapRegionNode dst  ) {
3969
3970     // if the region has no type, matches everything
3971     TypeDescriptor tdDst = dst.getType();
3972     assert tdDst != null;
3973
3974     // if the type is not a class or an array, don't
3975     // match because primitives are copied, no aliases
3976     ClassDescriptor cdDst = tdDst.getClassDesc();
3977     if( cdDst == null && !tdDst.isArray() ) {
3978       return false;
3979     }
3980
3981     // if the edge type is null, it matches everything
3982     TypeDescriptor tdEdge = edge.getType();
3983     assert tdEdge != null;
3984
3985     return typeUtil.isSuperorType( tdEdge, tdDst );
3986   }
3987
3988
3989
3990   // the default signature for quick-and-dirty debugging
3991   public void writeGraph( String graphName ) {
3992     writeGraph( graphName,
3993                 true, // write labels
3994                 true, // label select
3995                 true, // prune garbage
3996                 true, // hide subset reachability
3997                 true, // hide edge taints
3998                 null  // in-context boundary
3999                 );
4000   }
4001
4002   public void writeGraph( String  graphName,
4003                           boolean writeLabels,
4004                           boolean labelSelect,
4005                           boolean pruneGarbage,
4006                           boolean hideSubsetReachability,
4007                           boolean hideEdgeTaints
4008                           ) {
4009     writeGraph( graphName,
4010                 writeLabels,
4011                 labelSelect,
4012                 pruneGarbage,
4013                 hideSubsetReachability,
4014                 hideEdgeTaints,
4015                 null );
4016   }
4017
4018   public void writeGraph( String       graphName,
4019                           boolean      writeLabels,
4020                           boolean      labelSelect,
4021                           boolean      pruneGarbage,
4022                           boolean      hideSubsetReachability,
4023                           boolean      hideEdgeTaints,
4024                           Set<Integer> callerNodeIDsCopiedToCallee
4025                           ) {
4026
4027     try {
4028       // remove all non-word characters from the graph name so
4029       // the filename and identifier in dot don't cause errors
4030       graphName = graphName.replaceAll( "[\\W]", "" );
4031
4032       BufferedWriter bw =
4033         new BufferedWriter( new FileWriter( graphName+".dot" ) );
4034
4035       bw.write( "digraph "+graphName+" {\n" );
4036
4037
4038       // this is an optional step to form the callee-reachable
4039       // "cut-out" into a DOT cluster for visualization
4040       if( callerNodeIDsCopiedToCallee != null ) {
4041
4042         bw.write( "  subgraph cluster0 {\n" );
4043         bw.write( "    color=blue;\n" );
4044
4045         Iterator i = id2hrn.entrySet().iterator();
4046         while( i.hasNext() ) {
4047           Map.Entry      me  = (Map.Entry)      i.next();
4048           HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4049
4050           if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
4051             bw.write( "    "+hrn.toString()+
4052                       hrn.toStringDOT( hideSubsetReachability )+
4053                       ";\n" );
4054
4055           }
4056         }
4057
4058         bw.write( "  }\n" );
4059       }
4060
4061
4062       Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4063
4064       // then visit every heap region node
4065       Iterator i = id2hrn.entrySet().iterator();
4066       while( i.hasNext() ) {
4067         Map.Entry      me  = (Map.Entry)      i.next();
4068         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4069
4070         // only visit nodes worth writing out--for instance
4071         // not every node at an allocation is referenced
4072         // (think of it as garbage-collected), etc.
4073         if( !pruneGarbage        ||
4074             hrn.isOutOfContext() ||
4075             (hrn.isFlagged() && hrn.getID() > 0 && !hrn.isWiped()) // a non-shadow flagged node
4076             ) {
4077
4078           if( !visited.contains( hrn ) ) {
4079             traverseHeapRegionNodes( hrn,
4080                                      bw,
4081                                      null,
4082                                      visited,
4083                                      hideSubsetReachability,
4084                                      hideEdgeTaints,
4085                                      callerNodeIDsCopiedToCallee );
4086           }
4087         }
4088       }
4089
4090       bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
4091
4092
4093       // then visit every label node, useful for debugging
4094       if( writeLabels ) {
4095         i = td2vn.entrySet().iterator();
4096         while( i.hasNext() ) {
4097           Map.Entry    me = (Map.Entry)    i.next();
4098           VariableNode vn = (VariableNode) me.getValue();
4099
4100           if( labelSelect ) {
4101             String labelStr = vn.getTempDescriptorString();
4102             if( labelStr.startsWith( "___temp" )     ||
4103                 labelStr.startsWith( "___dst" )      ||
4104                 labelStr.startsWith( "___srctmp" )   ||
4105                 labelStr.startsWith( "___neverused" )
4106                 ) {
4107               continue;
4108             }
4109           }
4110
4111           Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4112           while( heapRegionsItr.hasNext() ) {
4113             RefEdge        edge = heapRegionsItr.next();
4114             HeapRegionNode hrn  = edge.getDst();
4115
4116             if( !visited.contains( hrn ) ) {
4117               traverseHeapRegionNodes( hrn,
4118                                        bw,
4119                                        null,
4120                                        visited,
4121                                        hideSubsetReachability,
4122                                        hideEdgeTaints,
4123                                        callerNodeIDsCopiedToCallee );
4124             }
4125
4126             bw.write( "  "+vn.toString()+
4127                       " -> "+hrn.toString()+
4128                       edge.toStringDOT( hideSubsetReachability, "" )+
4129                       ";\n" );
4130           }
4131         }
4132       }
4133
4134       bw.write( "}\n" );
4135       bw.close();
4136
4137     } catch( IOException e ) {
4138       throw new Error( "Error writing out DOT graph "+graphName );
4139     }
4140   }
4141
4142   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
4143                                           BufferedWriter      bw,
4144                                           TempDescriptor      td,
4145                                           Set<HeapRegionNode> visited,
4146                                           boolean             hideSubsetReachability,
4147                                           boolean             hideEdgeTaints,
4148                                           Set<Integer>        callerNodeIDsCopiedToCallee
4149                                           ) throws java.io.IOException {
4150
4151     if( visited.contains( hrn ) ) {
4152       return;
4153     }
4154     visited.add( hrn );
4155
4156     // if we're drawing the callee-view subgraph, only
4157     // write out the node info if it hasn't already been
4158     // written
4159     if( callerNodeIDsCopiedToCallee == null ||
4160         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4161         ) {
4162       bw.write( "  "+hrn.toString()+
4163                 hrn.toStringDOT( hideSubsetReachability )+
4164                 ";\n" );
4165     }
4166
4167     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4168     while( childRegionsItr.hasNext() ) {
4169       RefEdge        edge     = childRegionsItr.next();
4170       HeapRegionNode hrnChild = edge.getDst();
4171
4172       if( callerNodeIDsCopiedToCallee != null &&
4173           (edge.getSrc() instanceof HeapRegionNode) ) {
4174         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4175         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
4176             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4177             ) {
4178           bw.write( "  "+hrn.toString()+
4179                     " -> "+hrnChild.toString()+
4180                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4181                     ";\n");
4182         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
4183                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4184                    ) {
4185           bw.write( "  "+hrn.toString()+
4186                     " -> "+hrnChild.toString()+
4187                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4188                     ";\n");
4189         } else {
4190           bw.write( "  "+hrn.toString()+
4191                     " -> "+hrnChild.toString()+
4192                     edge.toStringDOT( hideSubsetReachability, "" )+
4193                     ";\n");
4194         }
4195       } else {
4196         bw.write( "  "+hrn.toString()+
4197                   " -> "+hrnChild.toString()+
4198                   edge.toStringDOT( hideSubsetReachability, "" )+
4199                   ";\n");
4200       }
4201
4202       traverseHeapRegionNodes( hrnChild,
4203                                bw,
4204                                td,
4205                                visited,
4206                                hideSubsetReachability,
4207                                hideEdgeTaints,
4208                                callerNodeIDsCopiedToCallee );
4209     }
4210   }
4211
4212
4213
4214
4215
4216   public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4217
4218     Set<HeapRegionNode> exhibitProofState =
4219       new HashSet<HeapRegionNode>();
4220
4221     Iterator hrnItr = id2hrn.entrySet().iterator();
4222     while( hrnItr.hasNext() ) {
4223       Map.Entry      me  = (Map.Entry) hrnItr.next();
4224       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4225
4226       ReachSet intersection =
4227         Canonical.intersection( proofOfSharing,
4228                                 hrn.getAlpha()
4229                                 );
4230       if( !intersection.isEmpty() ) {
4231         assert !hrn.isOutOfContext();
4232         exhibitProofState.add( hrn );
4233       }
4234     }
4235
4236     return exhibitProofState;
4237   }
4238
4239
4240   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4241                                                    HeapRegionNode hrn2) {
4242     assert hrn1 != null;
4243     assert hrn2 != null;
4244
4245     assert !hrn1.isOutOfContext();
4246     assert !hrn2.isOutOfContext();
4247
4248     assert belongsToThis( hrn1 );
4249     assert belongsToThis( hrn2 );
4250
4251     assert !hrn1.getID().equals( hrn2.getID() );
4252
4253
4254     // then get the various tokens for these heap regions
4255     ReachTuple h1 =
4256       ReachTuple.factory( hrn1.getID(),
4257                           !hrn1.isSingleObject(), // multi?
4258                           ReachTuple.ARITY_ONE,
4259                           false );                // ooc?
4260
4261     ReachTuple h1star = null;
4262     if( !hrn1.isSingleObject() ) {
4263       h1star =
4264         ReachTuple.factory( hrn1.getID(),
4265                             !hrn1.isSingleObject(),
4266                             ReachTuple.ARITY_ZEROORMORE,
4267                             false );
4268     }
4269
4270     ReachTuple h2 =
4271       ReachTuple.factory( hrn2.getID(),
4272                           !hrn2.isSingleObject(),
4273                           ReachTuple.ARITY_ONE,
4274                           false );
4275
4276     ReachTuple h2star = null;
4277     if( !hrn2.isSingleObject() ) {
4278       h2star =
4279         ReachTuple.factory( hrn2.getID(),
4280                             !hrn2.isSingleObject(),
4281                             ReachTuple.ARITY_ZEROORMORE,
4282                             false );
4283     }
4284
4285     // then get the merged beta of all out-going edges from these heap
4286     // regions
4287
4288     ReachSet beta1 = ReachSet.factory();
4289     Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4290     while (itrEdge.hasNext()) {
4291       RefEdge edge = itrEdge.next();
4292       beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4293     }
4294
4295     ReachSet beta2 = ReachSet.factory();
4296     itrEdge = hrn2.iteratorToReferencees();
4297     while (itrEdge.hasNext()) {
4298       RefEdge edge = itrEdge.next();
4299       beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4300     }
4301
4302     ReachSet proofOfSharing = ReachSet.factory();
4303
4304     proofOfSharing =
4305       Canonical.unionORpreds( proofOfSharing,
4306                               beta1.getStatesWithBoth( h1, h2 )
4307                               );
4308     proofOfSharing =
4309       Canonical.unionORpreds( proofOfSharing,
4310                               beta2.getStatesWithBoth( h1, h2 )
4311                               );
4312
4313     if( !hrn1.isSingleObject() ) {
4314       proofOfSharing =
4315         Canonical.unionORpreds( proofOfSharing,
4316                                 beta1.getStatesWithBoth( h1star, h2 )
4317                                 );
4318       proofOfSharing =
4319         Canonical.unionORpreds( proofOfSharing,
4320                                 beta2.getStatesWithBoth( h1star, h2 )
4321                                 );
4322     }
4323
4324     if( !hrn2.isSingleObject() ) {
4325       proofOfSharing =
4326         Canonical.unionORpreds( proofOfSharing,
4327                                 beta1.getStatesWithBoth( h1, h2star )
4328                                 );
4329       proofOfSharing =
4330         Canonical.unionORpreds( proofOfSharing,
4331                                 beta2.getStatesWithBoth( h1, h2star )
4332                                 );
4333     }
4334
4335     if( !hrn1.isSingleObject() &&
4336         !hrn2.isSingleObject()
4337         ) {
4338       proofOfSharing =
4339         Canonical.unionORpreds( proofOfSharing,
4340                                 beta1.getStatesWithBoth( h1star, h2star )
4341                                 );
4342       proofOfSharing =
4343         Canonical.unionORpreds( proofOfSharing,
4344                                 beta2.getStatesWithBoth( h1star, h2star )
4345                                 );
4346     }
4347
4348     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4349     if( !proofOfSharing.isEmpty() ) {
4350       common = findCommonReachableNodes( proofOfSharing );
4351       if( !DISABLE_STRONG_UPDATES &&
4352           !DISABLE_GLOBAL_SWEEP
4353           ) {
4354         assert !common.isEmpty();
4355       }
4356     }
4357
4358     return common;
4359   }
4360
4361   // this version of the above method checks whether there is sharing
4362   // among the objects in a summary node
4363   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4364     assert hrn != null;
4365     assert hrn.isNewSummary();
4366     assert !hrn.isOutOfContext();
4367     assert belongsToThis( hrn );
4368
4369     ReachTuple hstar =
4370       ReachTuple.factory( hrn.getID(),
4371                           true,    // multi
4372                           ReachTuple.ARITY_ZEROORMORE,
4373                           false ); // ooc
4374
4375     // then get the merged beta of all out-going edges from
4376     // this heap region
4377
4378     ReachSet beta = ReachSet.factory();
4379     Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4380     while (itrEdge.hasNext()) {
4381       RefEdge edge = itrEdge.next();
4382       beta = Canonical.unionORpreds(beta, edge.getBeta());
4383     }
4384
4385     ReachSet proofOfSharing = ReachSet.factory();
4386
4387     proofOfSharing =
4388       Canonical.unionORpreds( proofOfSharing,
4389                               beta.getStatesWithBoth( hstar, hstar )
4390                               );
4391
4392     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4393     if( !proofOfSharing.isEmpty() ) {
4394       common = findCommonReachableNodes( proofOfSharing );
4395       if( !DISABLE_STRONG_UPDATES &&
4396           !DISABLE_GLOBAL_SWEEP
4397           ) {
4398         assert !common.isEmpty();
4399       }
4400     }
4401
4402     return common;
4403   }
4404
4405
4406   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4407                                                    Integer paramIndex1,
4408                                                    Integer paramIndex2) {
4409
4410     // get parameter's heap regions
4411     TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4412     assert this.hasVariable( paramTemp1 );
4413     VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4414
4415
4416     if( !(paramVar1.getNumReferencees() == 1) ) {
4417       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp1 );
4418       writeGraph( "whatup" );
4419     }
4420
4421
4422     assert paramVar1.getNumReferencees() == 1;
4423     RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4424     HeapRegionNode hrnParam1 = paramEdge1.getDst();
4425
4426     TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4427     assert this.hasVariable( paramTemp2 );
4428     VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4429
4430     if( !(paramVar2.getNumReferencees() == 1) ) {
4431       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp2 );
4432       writeGraph( "whatup" );
4433     }
4434
4435     assert paramVar2.getNumReferencees() == 1;
4436     RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4437     HeapRegionNode hrnParam2 = paramEdge2.getDst();
4438
4439     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4440     common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4441
4442     return common;
4443   }
4444
4445   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4446                                                    Integer paramIndex,
4447                                                    AllocSite as) {
4448
4449     // get parameter's heap regions
4450     TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4451     assert this.hasVariable( paramTemp );
4452     VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4453     assert paramVar.getNumReferencees() == 1;
4454     RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4455     HeapRegionNode hrnParam = paramEdge.getDst();
4456
4457     // get summary node
4458     HeapRegionNode hrnSummary=null;
4459     if(id2hrn.containsKey(as.getSummary())){
4460       // if summary node doesn't exist, ignore this case
4461       hrnSummary = id2hrn.get(as.getSummary());
4462       assert hrnSummary != null;
4463     }
4464
4465     Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
4466     if(hrnSummary!=null){
4467       common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4468     }
4469
4470     // check for other nodes
4471     for (int i = 0; i < as.getAllocationDepth(); ++i) {
4472
4473       assert id2hrn.containsKey(as.getIthOldest(i));
4474       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4475       assert hrnIthOldest != null;
4476
4477       common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4478
4479     }
4480
4481     return common;
4482   }
4483
4484   public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4485                                                    AllocSite as2) {
4486
4487     // get summary node 1's alpha
4488     Integer idSum1 = as1.getSummary();
4489     HeapRegionNode hrnSum1=null;
4490     if(id2hrn.containsKey(idSum1)){
4491       hrnSum1 = id2hrn.get(idSum1);
4492     }
4493
4494     // get summary node 2's alpha
4495     Integer idSum2 = as2.getSummary();
4496     HeapRegionNode hrnSum2=null;
4497     if(id2hrn.containsKey(idSum2)){
4498       hrnSum2 = id2hrn.get(idSum2);
4499     }
4500
4501     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4502     if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4503       common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4504     }
4505
4506     if(hrnSum1!=null){
4507       // ask if objects from this summary share among each other
4508       common.addAll(mayReachSharedObjects(hrnSum1));
4509     }
4510
4511     // check sum2 against alloc1 nodes
4512     if(hrnSum2!=null){
4513       for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4514         Integer idI1 = as1.getIthOldest(i);
4515         assert id2hrn.containsKey(idI1);
4516         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4517         assert hrnI1 != null;
4518         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4519       }
4520
4521       // also ask if objects from this summary share among each other
4522       common.addAll(mayReachSharedObjects(hrnSum2));
4523     }
4524
4525     // check sum1 against alloc2 nodes
4526     for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4527       Integer idI2 = as2.getIthOldest(i);
4528       assert id2hrn.containsKey(idI2);
4529       HeapRegionNode hrnI2 = id2hrn.get(idI2);
4530       assert hrnI2 != null;
4531
4532       if(hrnSum1!=null){
4533         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4534       }
4535
4536       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4537       for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4538         Integer idI1 = as1.getIthOldest(j);
4539
4540         // if these are the same site, don't look for the same token, no
4541         // alias.
4542         // different tokens of the same site could alias together though
4543         if (idI1.equals(idI2)) {
4544           continue;
4545         }
4546
4547         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4548
4549         common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4550       }
4551     }
4552
4553     return common;
4554   }
4555 }