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