Robust/src/Analysis/Disjoint/ReachGraph.java

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