Robust/src/Analysis/Disjoint/ReachGraph.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import Util.UtilAlgorithms;
   6 import java.util.*;
   7 import java.io.*;
   8
   9 public class ReachGraph {
  10
  11   // use to disable improvements for comparison
  12   protected static final boolean DISABLE_STRONG_UPDATES = false;
  13   protected static final boolean DISABLE_GLOBAL_SWEEP   = false;
  14
  15   // a special out-of-scope temp
  16   protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
  17
  18   // some frequently used reachability constants
  19   protected static final ReachState rstateEmpty        = ReachState.factory();
  20   protected static final ReachSet   rsetEmpty          = ReachSet.factory();
  21   protected static final ReachSet   rsetWithEmptyState = Canonical.makePredsTrue(ReachSet.factory( rstateEmpty ));
  22
  23   // predicate constants
  24   protected static final ExistPred    predTrue   = ExistPred.factory(); // if no args, true
  25   protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
  26   protected static final ExistPredSet predsTrue  = ExistPredSet.factory( predTrue );
  27
  28
  29   // from DisjointAnalysis for convenience
  30   protected static int      allocationDepth   = -1;
  31   protected static TypeUtil typeUtil          = null;
  32
  33
  34   // variable and heap region nodes indexed by unique ID
  35   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  36   public Hashtable<TempDescriptor, VariableNode  > td2vn;
  37
  38   // convenient set of alloc sites for all heap regions
  39   // present in the graph without having to search
  40   public HashSet<AllocSite> allocSites;
  41
  42   public ReachGraph() {
  43     id2hrn     = new Hashtable<Integer,        HeapRegionNode>();
  44     td2vn      = new Hashtable<TempDescriptor, VariableNode  >();
  45     allocSites = new HashSet<AllocSite>();
  46   }
  47
  48
  49   // temp descriptors are globally unique and map to
  50   // exactly one variable node, easy
  51   protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
  52     assert td != null;
  53
  54     if( !td2vn.containsKey( td ) ) {
  55       td2vn.put( td, new VariableNode( td ) );
  56     }
  57
  58     return td2vn.get( td );
  59   }
  60
  61   public boolean hasVariable( TempDescriptor td ) {
  62     return td2vn.containsKey( td );
  63   }
  64
  65
  66   // this suite of methods can be used to assert a
  67   // very important property of ReachGraph objects:
  68   // some element, HeapRegionNode, RefEdge etc.
  69   // should be referenced by at most ONE ReachGraph!!
  70   // If a heap region or edge or variable should be
  71   // in another graph, make a new object with
  72   // equivalent properties for a new graph
  73   public boolean belongsToThis( RefSrcNode rsn ) {
  74     if( rsn instanceof VariableNode ) {
  75       VariableNode vn = (VariableNode) rsn;
  76       return this.td2vn.get( vn.getTempDescriptor() ) == vn;
  77     }
  78     HeapRegionNode hrn = (HeapRegionNode) rsn;
  79     return this.id2hrn.get( hrn.getID() ) == hrn;
  80   }
  81
  82
  83
  84
  85
  86   // the reason for this method is to have the option
  87   // of creating new heap regions with specific IDs, or
  88   // duplicating heap regions with specific IDs (especially
  89   // in the merge() operation) or to create new heap
  90   // regions with a new unique ID
  91   protected HeapRegionNode
  92     createNewHeapRegionNode( Integer        id,
  93                              boolean        isSingleObject,
  94                              boolean        isNewSummary,
  95                              boolean        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   // in merge() and equals() methods the suffix A
3379   // represents the passed in graph and the suffix
3380   // B refers to the graph in this object
3381   // Merging means to take the incoming graph A and
3382   // merge it into B, so after the operation graph B
3383   // is the final result.
3384   ////////////////////////////////////////////////////
3385   protected void merge( ReachGraph rg ) {
3386
3387     if( rg == null ) {
3388       return;
3389     }
3390
3391     mergeNodes     ( rg );
3392     mergeRefEdges  ( rg );
3393     mergeAllocSites( rg );
3394   }
3395
3396   protected void mergeNodes( ReachGraph rg ) {
3397
3398     // start with heap region nodes
3399     Set      sA = rg.id2hrn.entrySet();
3400     Iterator iA = sA.iterator();
3401     while( iA.hasNext() ) {
3402       Map.Entry      meA  = (Map.Entry)      iA.next();
3403       Integer        idA  = (Integer)        meA.getKey();
3404       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3405
3406       // if this graph doesn't have a node the
3407       // incoming graph has, allocate it
3408       if( !id2hrn.containsKey( idA ) ) {
3409         HeapRegionNode hrnB = hrnA.copy();
3410         id2hrn.put( idA, hrnB );
3411
3412       } else {
3413         // otherwise this is a node present in both graphs
3414         // so make the new reachability set a union of the
3415         // nodes' reachability sets
3416         HeapRegionNode hrnB = id2hrn.get( idA );
3417         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3418                                         hrnA.getAlpha()
3419                                         )
3420                        );
3421
3422         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3423                                        hrnA.getPreds()
3424                                        )
3425                        );
3426       }
3427     }
3428
3429     // now add any variable nodes that are in graph B but
3430     // not in A
3431     sA = rg.td2vn.entrySet();
3432     iA = sA.iterator();
3433     while( iA.hasNext() ) {
3434       Map.Entry      meA = (Map.Entry)      iA.next();
3435       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3436       VariableNode   lnA = (VariableNode)   meA.getValue();
3437
3438       // if the variable doesn't exist in B, allocate and add it
3439       VariableNode lnB = getVariableNodeFromTemp( tdA );
3440     }
3441   }
3442
3443   protected void mergeRefEdges( ReachGraph rg ) {
3444
3445     // between heap regions
3446     Set      sA = rg.id2hrn.entrySet();
3447     Iterator iA = sA.iterator();
3448     while( iA.hasNext() ) {
3449       Map.Entry      meA  = (Map.Entry)      iA.next();
3450       Integer        idA  = (Integer)        meA.getKey();
3451       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3452
3453       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3454       while( heapRegionsItrA.hasNext() ) {
3455         RefEdge        edgeA     = heapRegionsItrA.next();
3456         HeapRegionNode hrnChildA = edgeA.getDst();
3457         Integer        idChildA  = hrnChildA.getID();
3458
3459         // at this point we know an edge in graph A exists
3460         // idA -> idChildA, does this exist in B?
3461         assert id2hrn.containsKey( idA );
3462         HeapRegionNode hrnB        = id2hrn.get( idA );
3463         RefEdge        edgeToMerge = null;
3464
3465         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3466         while( heapRegionsItrB.hasNext() &&
3467                edgeToMerge == null          ) {
3468
3469           RefEdge        edgeB     = heapRegionsItrB.next();
3470           HeapRegionNode hrnChildB = edgeB.getDst();
3471           Integer        idChildB  = hrnChildB.getID();
3472
3473           // don't use the RefEdge.equals() here because
3474           // we're talking about existence between graphs,
3475           // not intragraph equal
3476           if( idChildB.equals( idChildA ) &&
3477               edgeB.typeAndFieldEquals( edgeA ) ) {
3478
3479             edgeToMerge = edgeB;
3480           }
3481         }
3482
3483         // if the edge from A was not found in B,
3484         // add it to B.
3485         if( edgeToMerge == null ) {
3486           assert id2hrn.containsKey( idChildA );
3487           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3488           edgeToMerge = edgeA.copy();
3489           edgeToMerge.setSrc( hrnB );
3490           edgeToMerge.setDst( hrnChildB );
3491           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3492         }
3493         // otherwise, the edge already existed in both graphs
3494         // so merge their reachability sets
3495         else {
3496           // just replace this beta set with the union
3497           assert edgeToMerge != null;
3498           edgeToMerge.setBeta(
3499                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3500                                                edgeA.getBeta()
3501                                                )
3502                               );
3503           edgeToMerge.setPreds(
3504                                Canonical.join( edgeToMerge.getPreds(),
3505                                                edgeA.getPreds()
3506                                                )
3507                                );
3508         }
3509       }
3510     }
3511
3512     // and then again from variable nodes
3513     sA = rg.td2vn.entrySet();
3514     iA = sA.iterator();
3515     while( iA.hasNext() ) {
3516       Map.Entry      meA = (Map.Entry)      iA.next();
3517       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3518       VariableNode   vnA = (VariableNode)   meA.getValue();
3519
3520       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3521       while( heapRegionsItrA.hasNext() ) {
3522         RefEdge        edgeA     = heapRegionsItrA.next();
3523         HeapRegionNode hrnChildA = edgeA.getDst();
3524         Integer        idChildA  = hrnChildA.getID();
3525
3526         // at this point we know an edge in graph A exists
3527         // tdA -> idChildA, does this exist in B?
3528         assert td2vn.containsKey( tdA );
3529         VariableNode vnB         = td2vn.get( tdA );
3530         RefEdge      edgeToMerge = null;
3531
3532         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3533         while( heapRegionsItrB.hasNext() &&
3534                edgeToMerge == null          ) {
3535
3536           RefEdge        edgeB     = heapRegionsItrB.next();
3537           HeapRegionNode hrnChildB = edgeB.getDst();
3538           Integer        idChildB  = hrnChildB.getID();
3539
3540           // don't use the RefEdge.equals() here because
3541           // we're talking about existence between graphs
3542           if( idChildB.equals( idChildA ) &&
3543               edgeB.typeAndFieldEquals( edgeA ) ) {
3544
3545             edgeToMerge = edgeB;
3546           }
3547         }
3548
3549         // if the edge from A was not found in B,
3550         // add it to B.
3551         if( edgeToMerge == null ) {
3552           assert id2hrn.containsKey( idChildA );
3553           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3554           edgeToMerge = edgeA.copy();
3555           edgeToMerge.setSrc( vnB );
3556           edgeToMerge.setDst( hrnChildB );
3557           addRefEdge( vnB, hrnChildB, edgeToMerge );
3558         }
3559         // otherwise, the edge already existed in both graphs
3560         // so merge their reachability sets
3561         else {
3562           // just replace this beta set with the union
3563           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3564                                                 edgeA.getBeta()
3565                                                 )
3566                                );
3567           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3568                                                 edgeA.getPreds()
3569                                                 )
3570                                 );
3571         }
3572       }
3573     }
3574   }
3575
3576   protected void mergeAllocSites( ReachGraph rg ) {
3577     allocSites.addAll( rg.allocSites );
3578   }
3579
3580
3581
3582   static boolean dbgEquals = false;
3583
3584
3585   // it is necessary in the equals() member functions
3586   // to "check both ways" when comparing the data
3587   // structures of two graphs.  For instance, if all
3588   // edges between heap region nodes in graph A are
3589   // present and equal in graph B it is not sufficient
3590   // to say the graphs are equal.  Consider that there
3591   // may be edges in graph B that are not in graph A.
3592   // the only way to know that all edges in both graphs
3593   // are equally present is to iterate over both data
3594   // structures and compare against the other graph.
3595   public boolean equals( ReachGraph rg ) {
3596
3597     if( rg == null ) {
3598       if( dbgEquals ) {
3599         System.out.println( "rg is null" );
3600       }
3601       return false;
3602     }
3603
3604     if( !areHeapRegionNodesEqual( rg ) ) {
3605       if( dbgEquals ) {
3606         System.out.println( "hrn not equal" );
3607       }
3608       return false;
3609     }
3610
3611     if( !areVariableNodesEqual( rg ) ) {
3612       if( dbgEquals ) {
3613         System.out.println( "vars not equal" );
3614       }
3615       return false;
3616     }
3617
3618     if( !areRefEdgesEqual( rg ) ) {
3619       if( dbgEquals ) {
3620         System.out.println( "edges not equal" );
3621       }
3622       return false;
3623     }
3624
3625     // if everything is equal up to this point,
3626     // assert that allocSites is also equal--
3627     // this data is redundant but kept for efficiency
3628     assert allocSites.equals( rg.allocSites );
3629
3630     return true;
3631   }
3632
3633
3634   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3635
3636     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3637       return false;
3638     }
3639
3640     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3641       return false;
3642     }
3643
3644     return true;
3645   }
3646
3647   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3648                                                         ReachGraph rgB ) {
3649     Set      sA = rgA.id2hrn.entrySet();
3650     Iterator iA = sA.iterator();
3651     while( iA.hasNext() ) {
3652       Map.Entry      meA  = (Map.Entry)      iA.next();
3653       Integer        idA  = (Integer)        meA.getKey();
3654       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3655
3656       if( !rgB.id2hrn.containsKey( idA ) ) {
3657         return false;
3658       }
3659
3660       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3661       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3662         return false;
3663       }
3664     }
3665
3666     return true;
3667   }
3668
3669   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3670
3671     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3672       return false;
3673     }
3674
3675     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3676       return false;
3677     }
3678
3679     return true;
3680   }
3681
3682   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3683                                                        ReachGraph rgB ) {
3684     Set      sA = rgA.td2vn.entrySet();
3685     Iterator iA = sA.iterator();
3686     while( iA.hasNext() ) {
3687       Map.Entry      meA = (Map.Entry)      iA.next();
3688       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3689
3690       if( !rgB.td2vn.containsKey( tdA ) ) {
3691         return false;
3692       }
3693     }
3694
3695     return true;
3696   }
3697
3698
3699   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3700     if( !areallREinAandBequal( this, rg ) ) {
3701       return false;
3702     }
3703
3704     if( !areallREinAandBequal( rg, this ) ) {
3705       return false;
3706     }
3707
3708     return true;
3709   }
3710
3711   static protected boolean areallREinAandBequal( ReachGraph rgA,
3712                                                  ReachGraph rgB ) {
3713
3714     // check all the heap region->heap region edges
3715     Set      sA = rgA.id2hrn.entrySet();
3716     Iterator iA = sA.iterator();
3717     while( iA.hasNext() ) {
3718       Map.Entry      meA  = (Map.Entry)      iA.next();
3719       Integer        idA  = (Integer)        meA.getKey();
3720       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3721
3722       // we should have already checked that the same
3723       // heap regions exist in both graphs
3724       assert rgB.id2hrn.containsKey( idA );
3725
3726       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3727         return false;
3728       }
3729
3730       // then check every edge in B for presence in A, starting
3731       // from the same parent HeapRegionNode
3732       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3733
3734       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3735         return false;
3736       }
3737     }
3738
3739     // then check all the variable->heap region edges
3740     sA = rgA.td2vn.entrySet();
3741     iA = sA.iterator();
3742     while( iA.hasNext() ) {
3743       Map.Entry      meA = (Map.Entry)      iA.next();
3744       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3745       VariableNode   vnA = (VariableNode)   meA.getValue();
3746
3747       // we should have already checked that the same
3748       // label nodes exist in both graphs
3749       assert rgB.td2vn.containsKey( tdA );
3750
3751       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3752         return false;
3753       }
3754
3755       // then check every edge in B for presence in A, starting
3756       // from the same parent VariableNode
3757       VariableNode vnB = rgB.td2vn.get( tdA );
3758
3759       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3760         return false;
3761       }
3762     }
3763
3764     return true;
3765   }
3766
3767
3768   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3769                                                   RefSrcNode rnA,
3770                                                   ReachGraph rgB ) {
3771
3772     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3773     while( itrA.hasNext() ) {
3774       RefEdge        edgeA     = itrA.next();
3775       HeapRegionNode hrnChildA = edgeA.getDst();
3776       Integer        idChildA  = hrnChildA.getID();
3777
3778       assert rgB.id2hrn.containsKey( idChildA );
3779
3780       // at this point we know an edge in graph A exists
3781       // rnA -> idChildA, does this exact edge exist in B?
3782       boolean edgeFound = false;
3783
3784       RefSrcNode rnB = null;
3785       if( rnA instanceof HeapRegionNode ) {
3786         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3787         rnB = rgB.id2hrn.get( hrnA.getID() );
3788       } else {
3789         VariableNode vnA = (VariableNode) rnA;
3790         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3791       }
3792
3793       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3794       while( itrB.hasNext() ) {
3795         RefEdge        edgeB     = itrB.next();
3796         HeapRegionNode hrnChildB = edgeB.getDst();
3797         Integer        idChildB  = hrnChildB.getID();
3798
3799         if( idChildA.equals( idChildB ) &&
3800             edgeA.typeAndFieldEquals( edgeB ) ) {
3801
3802           // there is an edge in the right place with the right field,
3803           // but do they have the same attributes?
3804           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3805               edgeA.equalsPreds( edgeB )
3806               ) {
3807             edgeFound = true;
3808           }
3809         }
3810       }
3811
3812       if( !edgeFound ) {
3813         return false;
3814       }
3815     }
3816
3817     return true;
3818   }
3819
3820
3821   // can be used to assert monotonicity
3822   static public boolean isNoSmallerThan( ReachGraph rgA,
3823                                          ReachGraph rgB ) {
3824
3825     //System.out.println( "*** Asking if A is no smaller than B ***" );
3826
3827
3828     Iterator iA = rgA.id2hrn.entrySet().iterator();
3829     while( iA.hasNext() ) {
3830       Map.Entry      meA  = (Map.Entry)      iA.next();
3831       Integer        idA  = (Integer)        meA.getKey();
3832       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3833
3834       if( !rgB.id2hrn.containsKey( idA ) ) {
3835         System.out.println( "  regions smaller" );
3836         return false;
3837       }
3838
3839       //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3840       /* NOT EQUALS, NO SMALLER THAN!
3841       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3842         System.out.println( "  regions smaller" );
3843         return false;
3844       }
3845       */
3846     }
3847
3848     // this works just fine, no smaller than
3849     if( !areallVNinAalsoinBandequal( rgA, rgB ) ) {
3850       System.out.println( "  vars smaller:" );
3851       System.out.println( "    A:"+rgA.td2vn.keySet() );
3852       System.out.println( "    B:"+rgB.td2vn.keySet() );
3853       return false;
3854     }
3855
3856
3857     iA = rgA.id2hrn.entrySet().iterator();
3858     while( iA.hasNext() ) {
3859       Map.Entry      meA  = (Map.Entry)      iA.next();
3860       Integer        idA  = (Integer)        meA.getKey();
3861       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3862
3863       Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
3864       while( reItr.hasNext() ) {
3865         RefEdge    edgeA = reItr.next();
3866         RefSrcNode rsnA  = edgeA.getSrc();
3867
3868         // we already checked that nodes were present
3869         HeapRegionNode hrnB = rgB.id2hrn.get( hrnA.getID() );
3870         assert hrnB != null;
3871
3872         RefSrcNode rsnB;
3873         if( rsnA instanceof VariableNode ) {
3874           VariableNode vnA = (VariableNode) rsnA;
3875           rsnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3876
3877         } else {
3878           HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
3879           rsnB = rgB.id2hrn.get( hrnSrcA.getID() );
3880         }
3881         assert rsnB != null;
3882
3883         RefEdge edgeB = rsnB.getReferenceTo( hrnB,
3884                                              edgeA.getType(),
3885                                              edgeA.getField()
3886                                              );
3887         if( edgeB == null ) {
3888           System.out.println( "  edges smaller:" );
3889           return false;
3890         }
3891
3892         // REMEMBER, IS NO SMALLER THAN
3893         /*
3894           System.out.println( "  edges smaller" );
3895           return false;
3896           }
3897         */
3898
3899       }
3900     }
3901
3902
3903     return true;
3904   }
3905
3906
3907
3908
3909
3910   // this analysis no longer has the "match anything"
3911   // type which was represented by null
3912   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3913                                              TypeDescriptor td2 ) {
3914     assert td1 != null;
3915     assert td2 != null;
3916
3917     if( td1.isNull() ) {
3918       return td2;
3919     }
3920     if( td2.isNull() ) {
3921       return td1;
3922     }
3923     return typeUtil.mostSpecific( td1, td2 );
3924   }
3925
3926   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3927                                              TypeDescriptor td2,
3928                                              TypeDescriptor td3 ) {
3929
3930     return mostSpecificType( td1,
3931                              mostSpecificType( td2, td3 )
3932                              );
3933   }
3934
3935   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3936                                              TypeDescriptor td2,
3937                                              TypeDescriptor td3,
3938                                              TypeDescriptor td4 ) {
3939
3940     return mostSpecificType( mostSpecificType( td1, td2 ),
3941                              mostSpecificType( td3, td4 )
3942                              );
3943   }
3944
3945   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3946                                     TypeDescriptor possibleChild ) {
3947     assert possibleSuper != null;
3948     assert possibleChild != null;
3949
3950     if( possibleSuper.isNull() ||
3951         possibleChild.isNull() ) {
3952       return true;
3953     }
3954
3955     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3956   }
3957
3958
3959   protected boolean hasMatchingField( HeapRegionNode src,
3960                                       RefEdge        edge ) {
3961
3962     TypeDescriptor tdSrc = src.getType();
3963     assert tdSrc != null;
3964
3965     if( tdSrc.isArray() ) {
3966       TypeDescriptor td = edge.getType();
3967       assert td != null;
3968
3969       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3970       assert tdSrcDeref != null;
3971
3972       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3973         return false;
3974       }
3975
3976       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3977     }
3978
3979     // if it's not a class, it doesn't have any fields to match
3980     if( !tdSrc.isClass() ) {
3981       return false;
3982     }
3983
3984     ClassDescriptor cd = tdSrc.getClassDesc();
3985     while( cd != null ) {
3986       Iterator fieldItr = cd.getFields();
3987
3988       while( fieldItr.hasNext() ) {
3989         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3990
3991         if( fd.getType().equals( edge.getType() ) &&
3992             fd.getSymbol().equals( edge.getField() ) ) {
3993           return true;
3994         }
3995       }
3996
3997       cd = cd.getSuperDesc();
3998     }
3999
4000     // otherwise it is a class with fields
4001     // but we didn't find a match
4002     return false;
4003   }
4004
4005   protected boolean hasMatchingType( RefEdge        edge,
4006                                      HeapRegionNode dst  ) {
4007
4008     // if the region has no type, matches everything
4009     TypeDescriptor tdDst = dst.getType();
4010     assert tdDst != null;
4011
4012     // if the type is not a class or an array, don't
4013     // match because primitives are copied, no aliases
4014     ClassDescriptor cdDst = tdDst.getClassDesc();
4015     if( cdDst == null && !tdDst.isArray() ) {
4016       return false;
4017     }
4018
4019     // if the edge type is null, it matches everything
4020     TypeDescriptor tdEdge = edge.getType();
4021     assert tdEdge != null;
4022
4023     return typeUtil.isSuperorType( tdEdge, tdDst );
4024   }
4025
4026
4027
4028   // the default signature for quick-and-dirty debugging
4029   public void writeGraph( String graphName ) {
4030     writeGraph( graphName,
4031                 true, // write labels
4032                 true, // label select
4033                 true, // prune garbage
4034                 true, // hide subset reachability
4035                 true, // hide edge taints
4036                 null  // in-context boundary
4037                 );
4038   }
4039
4040   public void writeGraph( String  graphName,
4041                           boolean writeLabels,
4042                           boolean labelSelect,
4043                           boolean pruneGarbage,
4044                           boolean hideSubsetReachability,
4045                           boolean hideEdgeTaints
4046                           ) {
4047     writeGraph( graphName,
4048                 writeLabels,
4049                 labelSelect,
4050                 pruneGarbage,
4051                 hideSubsetReachability,
4052                 hideEdgeTaints,
4053                 null );
4054   }
4055
4056   public void writeGraph( String       graphName,
4057                           boolean      writeLabels,
4058                           boolean      labelSelect,
4059                           boolean      pruneGarbage,
4060                           boolean      hideSubsetReachability,
4061                           boolean      hideEdgeTaints,
4062                           Set<Integer> callerNodeIDsCopiedToCallee
4063                           ) {
4064
4065     try {
4066       // remove all non-word characters from the graph name so
4067       // the filename and identifier in dot don't cause errors
4068       graphName = graphName.replaceAll( "[\\W]", "" );
4069
4070       BufferedWriter bw =
4071         new BufferedWriter( new FileWriter( graphName+".dot" ) );
4072
4073       bw.write( "digraph "+graphName+" {\n" );
4074
4075
4076       // this is an optional step to form the callee-reachable
4077       // "cut-out" into a DOT cluster for visualization
4078       if( callerNodeIDsCopiedToCallee != null ) {
4079
4080         bw.write( "  subgraph cluster0 {\n" );
4081         bw.write( "    color=blue;\n" );
4082
4083         Iterator i = id2hrn.entrySet().iterator();
4084         while( i.hasNext() ) {
4085           Map.Entry      me  = (Map.Entry)      i.next();
4086           HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4087
4088           if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
4089             bw.write( "    "+hrn.toString()+
4090                       hrn.toStringDOT( hideSubsetReachability )+
4091                       ";\n" );
4092
4093           }
4094         }
4095
4096         bw.write( "  }\n" );
4097       }
4098
4099
4100       Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4101
4102       // then visit every heap region node
4103       Iterator i = id2hrn.entrySet().iterator();
4104       while( i.hasNext() ) {
4105         Map.Entry      me  = (Map.Entry)      i.next();
4106         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4107
4108         // only visit nodes worth writing out--for instance
4109         // not every node at an allocation is referenced
4110         // (think of it as garbage-collected), etc.
4111         if( !pruneGarbage        ||
4112             hrn.isOutOfContext()
4113             ) {
4114
4115           if( !visited.contains( hrn ) ) {
4116             traverseHeapRegionNodes( hrn,
4117                                      bw,
4118                                      null,
4119                                      visited,
4120                                      hideSubsetReachability,
4121                                      hideEdgeTaints,
4122                                      callerNodeIDsCopiedToCallee );
4123           }
4124         }
4125       }
4126
4127       bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
4128
4129
4130       // then visit every label node, useful for debugging
4131       if( writeLabels ) {
4132         i = td2vn.entrySet().iterator();
4133         while( i.hasNext() ) {
4134           Map.Entry    me = (Map.Entry)    i.next();
4135           VariableNode vn = (VariableNode) me.getValue();
4136
4137           if( labelSelect ) {
4138             String labelStr = vn.getTempDescriptorString();
4139             if( labelStr.startsWith( "___temp" )     ||
4140                 labelStr.startsWith( "___dst" )      ||
4141                 labelStr.startsWith( "___srctmp" )   ||
4142                 labelStr.startsWith( "___neverused" )
4143                 ) {
4144               continue;
4145             }
4146           }
4147
4148           Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4149           while( heapRegionsItr.hasNext() ) {
4150             RefEdge        edge = heapRegionsItr.next();
4151             HeapRegionNode hrn  = edge.getDst();
4152
4153             if( !visited.contains( hrn ) ) {
4154               traverseHeapRegionNodes( hrn,
4155                                        bw,
4156                                        null,
4157                                        visited,
4158                                        hideSubsetReachability,
4159                                        hideEdgeTaints,
4160                                        callerNodeIDsCopiedToCallee );
4161             }
4162
4163             bw.write( "  "+vn.toString()+
4164                       " -> "+hrn.toString()+
4165                       edge.toStringDOT( hideSubsetReachability, "" )+
4166                       ";\n" );
4167           }
4168         }
4169       }
4170
4171       bw.write( "}\n" );
4172       bw.close();
4173
4174     } catch( IOException e ) {
4175       throw new Error( "Error writing out DOT graph "+graphName );
4176     }
4177   }
4178
4179   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
4180                                           BufferedWriter      bw,
4181                                           TempDescriptor      td,
4182                                           Set<HeapRegionNode> visited,
4183                                           boolean             hideSubsetReachability,
4184                                           boolean             hideEdgeTaints,
4185                                           Set<Integer>        callerNodeIDsCopiedToCallee
4186                                           ) throws java.io.IOException {
4187
4188     if( visited.contains( hrn ) ) {
4189       return;
4190     }
4191     visited.add( hrn );
4192
4193     // if we're drawing the callee-view subgraph, only
4194     // write out the node info if it hasn't already been
4195     // written
4196     if( callerNodeIDsCopiedToCallee == null ||
4197         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4198         ) {
4199       bw.write( "  "+hrn.toString()+
4200                 hrn.toStringDOT( hideSubsetReachability )+
4201                 ";\n" );
4202     }
4203
4204     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4205     while( childRegionsItr.hasNext() ) {
4206       RefEdge        edge     = childRegionsItr.next();
4207       HeapRegionNode hrnChild = edge.getDst();
4208
4209       if( callerNodeIDsCopiedToCallee != null &&
4210           (edge.getSrc() instanceof HeapRegionNode) ) {
4211         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4212         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
4213             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4214             ) {
4215           bw.write( "  "+hrn.toString()+
4216                     " -> "+hrnChild.toString()+
4217                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4218                     ";\n");
4219         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
4220                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4221                    ) {
4222           bw.write( "  "+hrn.toString()+
4223                     " -> "+hrnChild.toString()+
4224                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4225                     ";\n");
4226         } else {
4227           bw.write( "  "+hrn.toString()+
4228                     " -> "+hrnChild.toString()+
4229                     edge.toStringDOT( hideSubsetReachability, "" )+
4230                     ";\n");
4231         }
4232       } else {
4233         bw.write( "  "+hrn.toString()+
4234                   " -> "+hrnChild.toString()+
4235                   edge.toStringDOT( hideSubsetReachability, "" )+
4236                   ";\n");
4237       }
4238
4239       traverseHeapRegionNodes( hrnChild,
4240                                bw,
4241                                td,
4242                                visited,
4243                                hideSubsetReachability,
4244                                hideEdgeTaints,
4245                                callerNodeIDsCopiedToCallee );
4246     }
4247   }
4248
4249
4250
4251
4252
4253   public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4254
4255     Set<HeapRegionNode> exhibitProofState =
4256       new HashSet<HeapRegionNode>();
4257
4258     Iterator hrnItr = id2hrn.entrySet().iterator();
4259     while( hrnItr.hasNext() ) {
4260       Map.Entry      me  = (Map.Entry) hrnItr.next();
4261       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4262
4263       ReachSet intersection =
4264         Canonical.intersection( proofOfSharing,
4265                                 hrn.getAlpha()
4266                                 );
4267       if( !intersection.isEmpty() ) {
4268         assert !hrn.isOutOfContext();
4269         exhibitProofState.add( hrn );
4270       }
4271     }
4272
4273     return exhibitProofState;
4274   }
4275
4276
4277   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4278                                                    HeapRegionNode hrn2) {
4279     assert hrn1 != null;
4280     assert hrn2 != null;
4281
4282     assert !hrn1.isOutOfContext();
4283     assert !hrn2.isOutOfContext();
4284
4285     assert belongsToThis( hrn1 );
4286     assert belongsToThis( hrn2 );
4287
4288     assert !hrn1.getID().equals( hrn2.getID() );
4289
4290
4291     // then get the various tokens for these heap regions
4292     ReachTuple h1 =
4293       ReachTuple.factory( hrn1.getID(),
4294                           !hrn1.isSingleObject(), // multi?
4295                           ReachTuple.ARITY_ONE,
4296                           false );                // ooc?
4297
4298     ReachTuple h1star = null;
4299     if( !hrn1.isSingleObject() ) {
4300       h1star =
4301         ReachTuple.factory( hrn1.getID(),
4302                             !hrn1.isSingleObject(),
4303                             ReachTuple.ARITY_ZEROORMORE,
4304                             false );
4305     }
4306
4307     ReachTuple h2 =
4308       ReachTuple.factory( hrn2.getID(),
4309                           !hrn2.isSingleObject(),
4310                           ReachTuple.ARITY_ONE,
4311                           false );
4312
4313     ReachTuple h2star = null;
4314     if( !hrn2.isSingleObject() ) {
4315       h2star =
4316         ReachTuple.factory( hrn2.getID(),
4317                             !hrn2.isSingleObject(),
4318                             ReachTuple.ARITY_ZEROORMORE,
4319                             false );
4320     }
4321
4322     // then get the merged beta of all out-going edges from these heap
4323     // regions
4324
4325     ReachSet beta1 = ReachSet.factory();
4326     Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4327     while (itrEdge.hasNext()) {
4328       RefEdge edge = itrEdge.next();
4329       beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4330     }
4331
4332     ReachSet beta2 = ReachSet.factory();
4333     itrEdge = hrn2.iteratorToReferencees();
4334     while (itrEdge.hasNext()) {
4335       RefEdge edge = itrEdge.next();
4336       beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4337     }
4338
4339     ReachSet proofOfSharing = ReachSet.factory();
4340
4341     proofOfSharing =
4342       Canonical.unionORpreds( proofOfSharing,
4343                               beta1.getStatesWithBoth( h1, h2 )
4344                               );
4345     proofOfSharing =
4346       Canonical.unionORpreds( proofOfSharing,
4347                               beta2.getStatesWithBoth( h1, h2 )
4348                               );
4349
4350     if( !hrn1.isSingleObject() ) {
4351       proofOfSharing =
4352         Canonical.unionORpreds( proofOfSharing,
4353                                 beta1.getStatesWithBoth( h1star, h2 )
4354                                 );
4355       proofOfSharing =
4356         Canonical.unionORpreds( proofOfSharing,
4357                                 beta2.getStatesWithBoth( h1star, h2 )
4358                                 );
4359     }
4360
4361     if( !hrn2.isSingleObject() ) {
4362       proofOfSharing =
4363         Canonical.unionORpreds( proofOfSharing,
4364                                 beta1.getStatesWithBoth( h1, h2star )
4365                                 );
4366       proofOfSharing =
4367         Canonical.unionORpreds( proofOfSharing,
4368                                 beta2.getStatesWithBoth( h1, h2star )
4369                                 );
4370     }
4371
4372     if( !hrn1.isSingleObject() &&
4373         !hrn2.isSingleObject()
4374         ) {
4375       proofOfSharing =
4376         Canonical.unionORpreds( proofOfSharing,
4377                                 beta1.getStatesWithBoth( h1star, h2star )
4378                                 );
4379       proofOfSharing =
4380         Canonical.unionORpreds( proofOfSharing,
4381                                 beta2.getStatesWithBoth( h1star, h2star )
4382                                 );
4383     }
4384
4385     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4386     if( !proofOfSharing.isEmpty() ) {
4387       common = findCommonReachableNodes( proofOfSharing );
4388       if( !DISABLE_STRONG_UPDATES &&
4389           !DISABLE_GLOBAL_SWEEP
4390           ) {
4391         assert !common.isEmpty();
4392       }
4393     }
4394
4395     return common;
4396   }
4397
4398   // this version of the above method checks whether there is sharing
4399   // among the objects in a summary node
4400   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4401     assert hrn != null;
4402     assert hrn.isNewSummary();
4403     assert !hrn.isOutOfContext();
4404     assert belongsToThis( hrn );
4405
4406     ReachTuple hstar =
4407       ReachTuple.factory( hrn.getID(),
4408                           true,    // multi
4409                           ReachTuple.ARITY_ZEROORMORE,
4410                           false ); // ooc
4411
4412     // then get the merged beta of all out-going edges from
4413     // this heap region
4414
4415     ReachSet beta = ReachSet.factory();
4416     Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4417     while (itrEdge.hasNext()) {
4418       RefEdge edge = itrEdge.next();
4419       beta = Canonical.unionORpreds(beta, edge.getBeta());
4420     }
4421
4422     ReachSet proofOfSharing = ReachSet.factory();
4423
4424     proofOfSharing =
4425       Canonical.unionORpreds( proofOfSharing,
4426                               beta.getStatesWithBoth( hstar, hstar )
4427                               );
4428
4429     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4430     if( !proofOfSharing.isEmpty() ) {
4431       common = findCommonReachableNodes( proofOfSharing );
4432       if( !DISABLE_STRONG_UPDATES &&
4433           !DISABLE_GLOBAL_SWEEP
4434           ) {
4435         assert !common.isEmpty();
4436       }
4437     }
4438
4439     return common;
4440   }
4441
4442
4443   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4444                                                    Integer paramIndex1,
4445                                                    Integer paramIndex2) {
4446
4447     // get parameter's heap regions
4448     TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4449     assert this.hasVariable( paramTemp1 );
4450     VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4451
4452
4453     if( !(paramVar1.getNumReferencees() == 1) ) {
4454       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp1 );
4455       writeGraph( "whatup" );
4456     }
4457
4458
4459     assert paramVar1.getNumReferencees() == 1;
4460     RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4461     HeapRegionNode hrnParam1 = paramEdge1.getDst();
4462
4463     TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4464     assert this.hasVariable( paramTemp2 );
4465     VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4466
4467     if( !(paramVar2.getNumReferencees() == 1) ) {
4468       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp2 );
4469       writeGraph( "whatup" );
4470     }
4471
4472     assert paramVar2.getNumReferencees() == 1;
4473     RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4474     HeapRegionNode hrnParam2 = paramEdge2.getDst();
4475
4476     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4477     common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4478
4479     return common;
4480   }
4481
4482   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4483                                                    Integer paramIndex,
4484                                                    AllocSite as) {
4485
4486     // get parameter's heap regions
4487     TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4488     assert this.hasVariable( paramTemp );
4489     VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4490     assert paramVar.getNumReferencees() == 1;
4491     RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4492     HeapRegionNode hrnParam = paramEdge.getDst();
4493
4494     // get summary node
4495     HeapRegionNode hrnSummary=null;
4496     if(id2hrn.containsKey(as.getSummary())){
4497       // if summary node doesn't exist, ignore this case
4498       hrnSummary = id2hrn.get(as.getSummary());
4499       assert hrnSummary != null;
4500     }
4501
4502     Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
4503     if(hrnSummary!=null){
4504       common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4505     }
4506
4507     // check for other nodes
4508     for (int i = 0; i < as.getAllocationDepth(); ++i) {
4509
4510       assert id2hrn.containsKey(as.getIthOldest(i));
4511       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4512       assert hrnIthOldest != null;
4513
4514       common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4515
4516     }
4517
4518     return common;
4519   }
4520
4521   public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4522                                                    AllocSite as2) {
4523
4524     // get summary node 1's alpha
4525     Integer idSum1 = as1.getSummary();
4526     HeapRegionNode hrnSum1=null;
4527     if(id2hrn.containsKey(idSum1)){
4528       hrnSum1 = id2hrn.get(idSum1);
4529     }
4530
4531     // get summary node 2's alpha
4532     Integer idSum2 = as2.getSummary();
4533     HeapRegionNode hrnSum2=null;
4534     if(id2hrn.containsKey(idSum2)){
4535       hrnSum2 = id2hrn.get(idSum2);
4536     }
4537
4538     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4539     if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4540       common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4541     }
4542
4543     if(hrnSum1!=null){
4544       // ask if objects from this summary share among each other
4545       common.addAll(mayReachSharedObjects(hrnSum1));
4546     }
4547
4548     // check sum2 against alloc1 nodes
4549     if(hrnSum2!=null){
4550       for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4551         Integer idI1 = as1.getIthOldest(i);
4552         assert id2hrn.containsKey(idI1);
4553         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4554         assert hrnI1 != null;
4555         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4556       }
4557
4558       // also ask if objects from this summary share among each other
4559       common.addAll(mayReachSharedObjects(hrnSum2));
4560     }
4561
4562     // check sum1 against alloc2 nodes
4563     for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4564       Integer idI2 = as2.getIthOldest(i);
4565       assert id2hrn.containsKey(idI2);
4566       HeapRegionNode hrnI2 = id2hrn.get(idI2);
4567       assert hrnI2 != null;
4568
4569       if(hrnSum1!=null){
4570         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4571       }
4572
4573       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4574       for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4575         Integer idI1 = as1.getIthOldest(j);
4576
4577         // if these are the same site, don't look for the same token, no
4578         // alias.
4579         // different tokens of the same site could alias together though
4580         if (idI1.equals(idI2)) {
4581           continue;
4582         }
4583
4584         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4585
4586         common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4587       }
4588     }
4589
4590     return common;
4591   }
4592 }