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   = true;
  14
  15   // a special out-of-scope temp
  16   protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
  17
  18   // some frequently used reachability constants
  19   protected static final ReachState rstateEmpty        = ReachState.factory();
  20   protected static final ReachSet   rsetEmpty          = ReachSet.factory();
  21   protected static final ReachSet   rsetWithEmptyState = ReachSet.factory( rstateEmpty );
  22
  23   // predicate constants
  24   protected static final ExistPred    predTrue   = ExistPred.factory(); // if no args, true
  25   protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
  26   protected static final ExistPredSet predsTrue  = ExistPredSet.factory( predTrue );
  27
  28
  29   // from DisjointAnalysis for convenience
  30   protected static int      allocationDepth   = -1;
  31   protected static TypeUtil typeUtil          = null;
  32
  33
  34   // variable and heap region nodes indexed by unique ID
  35   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  36   public Hashtable<TempDescriptor, VariableNode  > td2vn;
  37
  38   // convenient set of alloc sites for all heap regions
  39   // present in the graph without having to search
  40   public HashSet<AllocSite> allocSites;
  41
  42   public ReachGraph() {
  43     id2hrn     = new Hashtable<Integer,        HeapRegionNode>();
  44     td2vn      = new Hashtable<TempDescriptor, VariableNode  >();
  45     allocSites = new HashSet<AllocSite>();
  46   }
  47
  48
  49   // temp descriptors are globally unique and map to
  50   // exactly one variable node, easy
  51   protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
  52     assert td != null;
  53
  54     if( !td2vn.containsKey( td ) ) {
  55       td2vn.put( td, new VariableNode( td ) );
  56     }
  57
  58     return td2vn.get( td );
  59   }
  60
  61   public boolean hasVariable( TempDescriptor td ) {
  62     return td2vn.containsKey( td );
  63   }
  64
  65
  66   // the reason for this method is to have the option
  67   // of creating new heap regions with specific IDs, or
  68   // duplicating heap regions with specific IDs (especially
  69   // in the merge() operation) or to create new heap
  70   // regions with a new unique ID
  71   protected HeapRegionNode
  72     createNewHeapRegionNode( Integer        id,
  73                              boolean        isSingleObject,
  74                              boolean        isNewSummary,
  75                              boolean        isFlagged,
  76                              boolean        isOutOfContext,
  77                              TypeDescriptor type,
  78                              AllocSite      allocSite,
  79                              ReachSet       inherent,
  80                              ReachSet       alpha,
  81                              ExistPredSet   preds,
  82                              String         description
  83                              ) {
  84
  85     boolean markForAnalysis = isFlagged;
  86
  87     TypeDescriptor typeToUse = null;
  88     if( allocSite != null ) {
  89       typeToUse = allocSite.getType();
  90       allocSites.add( allocSite );
  91     } else {
  92       typeToUse = type;
  93     }
  94
  95     if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
  96       markForAnalysis = true;
  97     }
  98
  99     if( id == null ) {
 100       id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
 101     }
 102
 103     if( inherent == null ) {
 104       if( markForAnalysis ) {
 105         inherent =
 106           ReachSet.factory(
 107                            ReachState.factory(
 108                                               ReachTuple.factory( id,
 109                                                                   !isSingleObject,
 110                                                                   ReachTuple.ARITY_ONE
 111                                                                   )
 112                                               )
 113                            );
 114       } else {
 115         inherent = rsetWithEmptyState;
 116       }
 117     }
 118
 119     if( alpha == null ) {
 120       alpha = inherent;
 121     }
 122
 123     if( preds == null ) {
 124       // TODO: do this right?  For out-of-context nodes?
 125       preds = ExistPredSet.factory();
 126     }
 127
 128     HeapRegionNode hrn = new HeapRegionNode( id,
 129                                              isSingleObject,
 130                                              markForAnalysis,
 131                                              isNewSummary,
 132                                              isOutOfContext,
 133                                              typeToUse,
 134                                              allocSite,
 135                                              inherent,
 136                                              alpha,
 137                                              preds,
 138                                              description );
 139     id2hrn.put( id, hrn );
 140     return hrn;
 141   }
 142
 143
 144
 145   ////////////////////////////////////////////////
 146   //
 147   //  Low-level referencee and referencer methods
 148   //
 149   //  These methods provide the lowest level for
 150   //  creating references between reachability nodes
 151   //  and handling the details of maintaining both
 152   //  list of referencers and referencees.
 153   //
 154   ////////////////////////////////////////////////
 155   protected void addRefEdge( RefSrcNode     referencer,
 156                              HeapRegionNode referencee,
 157                              RefEdge        edge ) {
 158     assert referencer != null;
 159     assert referencee != null;
 160     assert edge       != null;
 161     assert edge.getSrc() == referencer;
 162     assert edge.getDst() == referencee;
 163
 164     // edges are getting added twice to graphs now, the
 165     // kind that should have abstract facts merged--use
 166     // this check to prevent that
 167     assert referencer.getReferenceTo( referencee,
 168                                       edge.getType(),
 169                                       edge.getField()
 170                                       ) == null;
 171
 172     referencer.addReferencee( edge );
 173     referencee.addReferencer( edge );
 174   }
 175
 176   protected void removeRefEdge( RefEdge e ) {
 177     removeRefEdge( e.getSrc(),
 178                    e.getDst(),
 179                    e.getType(),
 180                    e.getField() );
 181   }
 182
 183   protected void removeRefEdge( RefSrcNode     referencer,
 184                                 HeapRegionNode referencee,
 185                                 TypeDescriptor type,
 186                                 String         field ) {
 187     assert referencer != null;
 188     assert referencee != null;
 189
 190     RefEdge edge = referencer.getReferenceTo( referencee,
 191                                               type,
 192                                               field );
 193     assert edge != null;
 194     assert edge == referencee.getReferenceFrom( referencer,
 195                                                 type,
 196                                                 field );
 197
 198     referencer.removeReferencee( edge );
 199     referencee.removeReferencer( edge );
 200   }
 201
 202   protected void clearRefEdgesFrom( RefSrcNode     referencer,
 203                                     TypeDescriptor type,
 204                                     String         field,
 205                                     boolean        removeAll ) {
 206     assert referencer != null;
 207
 208     // get a copy of the set to iterate over, otherwise
 209     // we will be trying to take apart the set as we
 210     // are iterating over it, which won't work
 211     Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
 212     while( i.hasNext() ) {
 213       RefEdge edge = i.next();
 214
 215       if( removeAll                                          ||
 216           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 217         ){
 218
 219         HeapRegionNode referencee = edge.getDst();
 220
 221         removeRefEdge( referencer,
 222                        referencee,
 223                        edge.getType(),
 224                        edge.getField() );
 225       }
 226     }
 227   }
 228
 229   protected void clearRefEdgesTo( HeapRegionNode referencee,
 230                                   TypeDescriptor type,
 231                                   String         field,
 232                                   boolean        removeAll ) {
 233     assert referencee != null;
 234
 235     // get a copy of the set to iterate over, otherwise
 236     // we will be trying to take apart the set as we
 237     // are iterating over it, which won't work
 238     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 239     while( i.hasNext() ) {
 240       RefEdge edge = i.next();
 241
 242       if( removeAll                                          ||
 243           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 244         ){
 245
 246         RefSrcNode referencer = edge.getSrc();
 247
 248         removeRefEdge( referencer,
 249                        referencee,
 250                        edge.getType(),
 251                        edge.getField() );
 252       }
 253     }
 254   }
 255
 256   protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
 257     assert referencee != null;
 258
 259     // get a copy of the set to iterate over, otherwise
 260     // we will be trying to take apart the set as we
 261     // are iterating over it, which won't work
 262     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 263     while( i.hasNext() ) {
 264       RefEdge edge = i.next();
 265       RefSrcNode referencer = edge.getSrc();
 266       if( !(referencer instanceof VariableNode) ) {
 267         removeRefEdge( referencer,
 268                        referencee,
 269                        edge.getType(),
 270                        edge.getField() );
 271       }
 272     }
 273   }
 274
 275
 276   ////////////////////////////////////////////////////
 277   //
 278   //  Assignment Operation Methods
 279   //
 280   //  These methods are high-level operations for
 281   //  modeling program assignment statements using
 282   //  the low-level reference create/remove methods
 283   //  above.
 284   //
 285   ////////////////////////////////////////////////////
 286
 287   public void assignTempXEqualToTempY( TempDescriptor x,
 288                                        TempDescriptor y ) {
 289     assignTempXEqualToCastedTempY( x, y, null );
 290   }
 291
 292   public void assignTempXEqualToCastedTempY( TempDescriptor x,
 293                                              TempDescriptor y,
 294                                              TypeDescriptor tdCast ) {
 295
 296     VariableNode lnX = getVariableNodeFromTemp( x );
 297     VariableNode lnY = getVariableNodeFromTemp( y );
 298
 299     clearRefEdgesFrom( lnX, null, null, true );
 300
 301     // note it is possible that the types of temps in the
 302     // flat node to analyze will reveal that some typed
 303     // edges in the reachability graph are impossible
 304     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 305
 306     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 307     while( itrYhrn.hasNext() ) {
 308       RefEdge        edgeY      = itrYhrn.next();
 309       HeapRegionNode referencee = edgeY.getDst();
 310       RefEdge        edgeNew    = edgeY.copy();
 311
 312       if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
 313         impossibleEdges.add( edgeY );
 314         continue;
 315       }
 316
 317       edgeNew.setSrc( lnX );
 318
 319       if( tdCast == null ) {
 320         edgeNew.setType( mostSpecificType( y.getType(),
 321                                            edgeY.getType(),
 322                                            referencee.getType()
 323                                            )
 324                          );
 325       } else {
 326         edgeNew.setType( mostSpecificType( y.getType(),
 327                                            edgeY.getType(),
 328                                            referencee.getType(),
 329                                            tdCast
 330                                            )
 331                          );
 332       }
 333
 334       edgeNew.setField( null );
 335
 336       addRefEdge( lnX, referencee, edgeNew );
 337     }
 338
 339     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 340     while( itrImp.hasNext() ) {
 341       RefEdge edgeImp = itrImp.next();
 342       removeRefEdge( edgeImp );
 343     }
 344   }
 345
 346
 347   public void assignTempXEqualToTempYFieldF( TempDescriptor  x,
 348                                              TempDescriptor  y,
 349                                              FieldDescriptor f ) {
 350     VariableNode lnX = getVariableNodeFromTemp( x );
 351     VariableNode lnY = getVariableNodeFromTemp( y );
 352
 353     clearRefEdgesFrom( lnX, null, null, true );
 354
 355     // note it is possible that the types of temps in the
 356     // flat node to analyze will reveal that some typed
 357     // edges in the reachability graph are impossible
 358     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 359
 360     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 361     while( itrYhrn.hasNext() ) {
 362       RefEdge        edgeY = itrYhrn.next();
 363       HeapRegionNode hrnY  = edgeY.getDst();
 364       ReachSet       betaY = edgeY.getBeta();
 365
 366       Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 367       while( itrHrnFhrn.hasNext() ) {
 368         RefEdge        edgeHrn = itrHrnFhrn.next();
 369         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 370         ReachSet       betaHrn = edgeHrn.getBeta();
 371
 372         // prune edges that are not a matching field
 373         if( edgeHrn.getType() != null &&
 374             !edgeHrn.getField().equals( f.getSymbol() )
 375             ) {
 376           continue;
 377         }
 378
 379         // check for impossible edges
 380         if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
 381           impossibleEdges.add( edgeHrn );
 382           continue;
 383         }
 384
 385         TypeDescriptor tdNewEdge =
 386           mostSpecificType( edgeHrn.getType(),
 387                             hrnHrn.getType()
 388                             );
 389
 390         RefEdge edgeNew = new RefEdge( lnX,
 391                                        hrnHrn,
 392                                        tdNewEdge,
 393                                        null,
 394                                        Canonical.intersection( betaY, betaHrn ),
 395                                        predsTrue
 396                                        );
 397
 398         addRefEdge( lnX, hrnHrn, edgeNew );
 399       }
 400     }
 401
 402     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 403     while( itrImp.hasNext() ) {
 404       RefEdge edgeImp = itrImp.next();
 405       removeRefEdge( edgeImp );
 406     }
 407
 408     // anytime you might remove edges between heap regions
 409     // you must global sweep to clean up broken reachability
 410     if( !impossibleEdges.isEmpty() ) {
 411       if( !DISABLE_GLOBAL_SWEEP ) {
 412         globalSweep();
 413       }
 414     }
 415   }
 416
 417
 418   public void assignTempXFieldFEqualToTempY( TempDescriptor  x,
 419                                              FieldDescriptor f,
 420                                              TempDescriptor  y ) {
 421
 422     VariableNode lnX = getVariableNodeFromTemp( x );
 423     VariableNode lnY = getVariableNodeFromTemp( y );
 424
 425     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 426     HashSet<RefEdge>        edgesWithNewBeta  = new HashSet<RefEdge>();
 427
 428     // note it is possible that the types of temps in the
 429     // flat node to analyze will reveal that some typed
 430     // edges in the reachability graph are impossible
 431     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 432
 433     // first look for possible strong updates and remove those edges
 434     boolean strongUpdate = false;
 435
 436     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 437     while( itrXhrn.hasNext() ) {
 438       RefEdge        edgeX = itrXhrn.next();
 439       HeapRegionNode hrnX  = edgeX.getDst();
 440
 441       // we can do a strong update here if one of two cases holds
 442       if( f != null &&
 443           f != DisjointAnalysis.getArrayField( f.getType() ) &&
 444           (   (hrnX.getNumReferencers()                         == 1) || // case 1
 445               (hrnX.isSingleObject() && lnX.getNumReferencees() == 1)    // case 2
 446               )
 447           ) {
 448         if( !DISABLE_STRONG_UPDATES ) {
 449           strongUpdate = true;
 450           clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
 451         }
 452       }
 453     }
 454
 455     // then do all token propagation
 456     itrXhrn = lnX.iteratorToReferencees();
 457     while( itrXhrn.hasNext() ) {
 458       RefEdge        edgeX = itrXhrn.next();
 459       HeapRegionNode hrnX  = edgeX.getDst();
 460       ReachSet       betaX = edgeX.getBeta();
 461       ReachSet       R     = Canonical.intersection( hrnX.getAlpha(),
 462                                                      edgeX.getBeta()
 463                                                      );
 464
 465       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 466       while( itrYhrn.hasNext() ) {
 467         RefEdge        edgeY = itrYhrn.next();
 468         HeapRegionNode hrnY  = edgeY.getDst();
 469         ReachSet       O     = edgeY.getBeta();
 470
 471         // check for impossible edges
 472         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 473           impossibleEdges.add( edgeY );
 474           continue;
 475         }
 476
 477         // propagate tokens over nodes starting from hrnSrc, and it will
 478         // take care of propagating back up edges from any touched nodes
 479         ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
 480         propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
 481
 482         // then propagate back just up the edges from hrn
 483         ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
 484         HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
 485
 486         Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
 487           new Hashtable<RefEdge, ChangeSet>();
 488
 489         Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
 490         while( referItr.hasNext() ) {
 491           RefEdge edgeUpstream = referItr.next();
 492           todoEdges.add( edgeUpstream );
 493           edgePlannedChanges.put( edgeUpstream, Cx );
 494         }
 495
 496         propagateTokensOverEdges( todoEdges,
 497                                   edgePlannedChanges,
 498                                   edgesWithNewBeta );
 499       }
 500     }
 501
 502
 503     // apply the updates to reachability
 504     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 505     while( nodeItr.hasNext() ) {
 506       nodeItr.next().applyAlphaNew();
 507     }
 508
 509     Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
 510     while( edgeItr.hasNext() ) {
 511       edgeItr.next().applyBetaNew();
 512     }
 513
 514
 515     // then go back through and add the new edges
 516     itrXhrn = lnX.iteratorToReferencees();
 517     while( itrXhrn.hasNext() ) {
 518       RefEdge        edgeX = itrXhrn.next();
 519       HeapRegionNode hrnX  = edgeX.getDst();
 520
 521       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 522       while( itrYhrn.hasNext() ) {
 523         RefEdge        edgeY = itrYhrn.next();
 524         HeapRegionNode hrnY  = edgeY.getDst();
 525
 526         // skip impossible edges here, we already marked them
 527         // when computing reachability propagations above
 528         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 529           continue;
 530         }
 531
 532         // prepare the new reference edge hrnX.f -> hrnY
 533         TypeDescriptor tdNewEdge =
 534           mostSpecificType( y.getType(),
 535                             edgeY.getType(),
 536                             hrnY.getType()
 537                             );
 538
 539         RefEdge edgeNew = new RefEdge( hrnX,
 540                                        hrnY,
 541                                        tdNewEdge,
 542                                        f.getSymbol(),
 543                                        Canonical.pruneBy( edgeY.getBeta(),
 544                                                           hrnX.getAlpha()
 545                                                           ),
 546                                        predsTrue
 547                                        );
 548
 549         // look to see if an edge with same field exists
 550         // and merge with it, otherwise just add the edge
 551         RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
 552                                                     tdNewEdge,
 553                                                     f.getSymbol() );
 554
 555         if( edgeExisting != null ) {
 556           edgeExisting.setBeta(
 557                                Canonical.union( edgeExisting.getBeta(),
 558                                                 edgeNew.getBeta()
 559                                                 )
 560                                );
 561           edgeExisting.setPreds(
 562                                 Canonical.join( edgeExisting.getPreds(),
 563                                                 edgeNew.getPreds()
 564                                                 )
 565                                 );
 566
 567         } else {
 568           addRefEdge( hrnX, hrnY, edgeNew );
 569         }
 570       }
 571     }
 572
 573     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 574     while( itrImp.hasNext() ) {
 575       RefEdge edgeImp = itrImp.next();
 576       removeRefEdge( edgeImp );
 577     }
 578
 579     // if there was a strong update, make sure to improve
 580     // reachability with a global sweep
 581     if( strongUpdate || !impossibleEdges.isEmpty() ) {
 582       if( !DISABLE_GLOBAL_SWEEP ) {
 583         globalSweep();
 584       }
 585     }
 586   }
 587
 588
 589   public void assignReturnEqualToTemp( TempDescriptor x ) {
 590
 591     VariableNode lnR = getVariableNodeFromTemp( tdReturn );
 592     VariableNode lnX = getVariableNodeFromTemp( x );
 593
 594     clearRefEdgesFrom( lnR, null, null, true );
 595
 596     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 597     while( itrXhrn.hasNext() ) {
 598       RefEdge        edgeX      = itrXhrn.next();
 599       HeapRegionNode referencee = edgeX.getDst();
 600       RefEdge        edgeNew    = edgeX.copy();
 601       edgeNew.setSrc( lnR );
 602
 603       addRefEdge( lnR, referencee, edgeNew );
 604     }
 605   }
 606
 607
 608   public void assignTempEqualToNewAlloc( TempDescriptor x,
 609                                          AllocSite      as ) {
 610     assert x  != null;
 611     assert as != null;
 612
 613     age( as );
 614
 615     // after the age operation the newest (or zero-ith oldest)
 616     // node associated with the allocation site should have
 617     // no references to it as if it were a newly allocated
 618     // heap region
 619     Integer        idNewest   = as.getIthOldest( 0 );
 620     HeapRegionNode hrnNewest  = id2hrn.get( idNewest );
 621     assert         hrnNewest != null;
 622
 623     VariableNode lnX = getVariableNodeFromTemp( x );
 624     clearRefEdgesFrom( lnX, null, null, true );
 625
 626     // make a new reference to allocated node
 627     TypeDescriptor type = as.getType();
 628
 629     RefEdge edgeNew =
 630       new RefEdge( lnX,                  // source
 631                    hrnNewest,            // dest
 632                    type,                 // type
 633                    null,                 // field name
 634                    hrnNewest.getAlpha(), // beta
 635                    predsTrue             // predicates
 636                    );
 637
 638     addRefEdge( lnX, hrnNewest, edgeNew );
 639   }
 640
 641
 642   // use the allocation site (unique to entire analysis) to
 643   // locate the heap region nodes in this reachability graph
 644   // that should be aged.  The process models the allocation
 645   // of new objects and collects all the oldest allocations
 646   // in a summary node to allow for a finite analysis
 647   //
 648   // There is an additional property of this method.  After
 649   // running it on a particular reachability graph (many graphs
 650   // may have heap regions related to the same allocation site)
 651   // the heap region node objects in this reachability graph will be
 652   // allocated.  Therefore, after aging a graph for an allocation
 653   // site, attempts to retrieve the heap region nodes using the
 654   // integer id's contained in the allocation site should always
 655   // return non-null heap regions.
 656   public void age( AllocSite as ) {
 657
 658     // keep track of allocation sites that are represented
 659     // in this graph for efficiency with other operations
 660     allocSites.add( as );
 661
 662     // if there is a k-th oldest node, it merges into
 663     // the summary node
 664     Integer idK = as.getOldest();
 665     if( id2hrn.containsKey( idK ) ) {
 666       HeapRegionNode hrnK = id2hrn.get( idK );
 667
 668       // retrieve the summary node, or make it
 669       // from scratch
 670       HeapRegionNode hrnSummary = getSummaryNode( as, false );
 671
 672       mergeIntoSummary( hrnK, hrnSummary );
 673     }
 674
 675     // move down the line of heap region nodes
 676     // clobbering the ith and transferring all references
 677     // to and from i-1 to node i.
 678     for( int i = allocationDepth - 1; i > 0; --i ) {
 679
 680       // only do the transfer if the i-1 node exists
 681       Integer idImin1th = as.getIthOldest( i - 1 );
 682       if( id2hrn.containsKey( idImin1th ) ) {
 683         HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
 684         if( hrnImin1.isWiped() ) {
 685           // there is no info on this node, just skip
 686           continue;
 687         }
 688
 689         // either retrieve or make target of transfer
 690         HeapRegionNode hrnI = getIthNode( as, i, false );
 691
 692         transferOnto( hrnImin1, hrnI );
 693       }
 694
 695     }
 696
 697     // as stated above, the newest node should have had its
 698     // references moved over to the second oldest, so we wipe newest
 699     // in preparation for being the new object to assign something to
 700     HeapRegionNode hrn0 = getIthNode( as, 0, false );
 701     wipeOut( hrn0, true );
 702
 703     // now tokens in reachability sets need to "age" also
 704     Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
 705     while( itrAllVariableNodes.hasNext() ) {
 706       Map.Entry    me = (Map.Entry)    itrAllVariableNodes.next();
 707       VariableNode ln = (VariableNode) me.getValue();
 708
 709       Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
 710       while( itrEdges.hasNext() ) {
 711         ageTuplesFrom( as, itrEdges.next() );
 712       }
 713     }
 714
 715     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 716     while( itrAllHRNodes.hasNext() ) {
 717       Map.Entry      me       = (Map.Entry)      itrAllHRNodes.next();
 718       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 719
 720       ageTuplesFrom( as, hrnToAge );
 721
 722       Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
 723       while( itrEdges.hasNext() ) {
 724         ageTuplesFrom( as, itrEdges.next() );
 725       }
 726     }
 727
 728
 729     // after tokens have been aged, reset newest node's reachability
 730     // and a brand new node has a "true" predicate
 731     hrn0.setAlpha( hrn0.getInherent() );
 732     hrn0.setPreds( predsTrue );
 733   }
 734
 735
 736   // either retrieve or create the needed heap region node
 737   protected HeapRegionNode getSummaryNode( AllocSite as,
 738                                            boolean   shadow ) {
 739
 740     Integer idSummary;
 741     if( shadow ) {
 742       idSummary = as.getSummaryShadow();
 743     } else {
 744       idSummary = as.getSummary();
 745     }
 746
 747     HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 748
 749     if( hrnSummary == null ) {
 750
 751       boolean hasFlags = false;
 752       if( as.getType().isClass() ) {
 753         hasFlags = as.getType().getClassDesc().hasFlags();
 754       }
 755
 756       if( as.getFlag() ){
 757         hasFlags = as.getFlag();
 758       }
 759
 760       String strDesc = as.toStringForDOT()+"\\nsummary";
 761       if( shadow ) {
 762         strDesc += " shadow";
 763       }
 764
 765       hrnSummary =
 766         createNewHeapRegionNode( idSummary,    // id or null to generate a new one
 767                                  false,        // single object?
 768                                  true,         // summary?
 769                                  hasFlags,     // flagged?
 770                                  false,        // out-of-context?
 771                                  as.getType(), // type
 772                                  as,           // allocation site
 773                                  null,         // inherent reach
 774                                  null,         // current reach
 775                                  predsEmpty,   // predicates
 776                                  strDesc       // description
 777                                  );
 778     }
 779
 780     return hrnSummary;
 781   }
 782
 783   // either retrieve or create the needed heap region node
 784   protected HeapRegionNode getIthNode( AllocSite as,
 785                                        Integer   i,
 786                                        boolean   shadow ) {
 787
 788     Integer idIth;
 789     if( shadow ) {
 790       idIth = as.getIthOldestShadow( i );
 791     } else {
 792       idIth = as.getIthOldest( i );
 793     }
 794
 795     HeapRegionNode hrnIth = id2hrn.get( idIth );
 796
 797     if( hrnIth == null ) {
 798
 799       boolean hasFlags = false;
 800       if( as.getType().isClass() ) {
 801         hasFlags = as.getType().getClassDesc().hasFlags();
 802       }
 803
 804       if( as.getFlag() ){
 805         hasFlags = as.getFlag();
 806       }
 807
 808       String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
 809       if( shadow ) {
 810         strDesc += " shadow";
 811       }
 812
 813       hrnIth = createNewHeapRegionNode( idIth,        // id or null to generate a new one
 814                                         true,         // single object?
 815                                         false,        // summary?
 816                                         hasFlags,     // flagged?
 817                                         false,        // out-of-context?
 818                                         as.getType(), // type
 819                                         as,           // allocation site
 820                                         null,         // inherent reach
 821                                         null,         // current reach
 822                                         predsEmpty,   // predicates
 823                                         strDesc       // description
 824                                         );
 825     }
 826
 827     return hrnIth;
 828   }
 829
 830
 831   // used to assert that the given node object
 832   // belongs to THIS graph instance, some gross bugs
 833   // have popped up where a node from one graph works
 834   // itself into another
 835   public boolean belongsToThis( HeapRegionNode hrn ) {
 836     return this.id2hrn.get( hrn.getID() ) == hrn;
 837   }
 838
 839   protected void mergeIntoSummary( HeapRegionNode hrn,
 840                                    HeapRegionNode hrnSummary ) {
 841     assert hrnSummary.isNewSummary();
 842
 843     // assert that these nodes belong to THIS graph
 844     assert belongsToThis( hrn );
 845     assert belongsToThis( hrnSummary );
 846
 847     // transfer references _from_ hrn over to hrnSummary
 848     Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
 849     while( itrReferencee.hasNext() ) {
 850       RefEdge edge       = itrReferencee.next();
 851       RefEdge edgeMerged = edge.copy();
 852       edgeMerged.setSrc( hrnSummary );
 853
 854       HeapRegionNode hrnReferencee = edge.getDst();
 855       RefEdge        edgeSummary   =
 856         hrnSummary.getReferenceTo( hrnReferencee,
 857                                    edge.getType(),
 858                                    edge.getField()
 859                                    );
 860
 861       if( edgeSummary == null ) {
 862         // the merge is trivial, nothing to be done
 863         addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
 864
 865       } else {
 866         // otherwise an edge from the referencer to hrnSummary exists already
 867         // and the edge referencer->hrn should be merged with it
 868         edgeSummary.setBeta(
 869                             Canonical.union( edgeMerged.getBeta(),
 870                                              edgeSummary.getBeta()
 871                                              )
 872                              );
 873         edgeSummary.setPreds(
 874                              Canonical.join( edgeMerged.getPreds(),
 875                                              edgeSummary.getPreds()
 876                                              )
 877                               );
 878       }
 879     }
 880
 881     // next transfer references _to_ hrn over to hrnSummary
 882     Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
 883     while( itrReferencer.hasNext() ) {
 884       RefEdge edge         = itrReferencer.next();
 885       RefEdge edgeMerged   = edge.copy();
 886       edgeMerged.setDst( hrnSummary );
 887
 888       RefSrcNode onReferencer = edge.getSrc();
 889       RefEdge    edgeSummary  =
 890         onReferencer.getReferenceTo( hrnSummary,
 891                                      edge.getType(),
 892                                      edge.getField()
 893                                      );
 894
 895       if( edgeSummary == null ) {
 896         // the merge is trivial, nothing to be done
 897         addRefEdge( onReferencer, hrnSummary, edgeMerged );
 898
 899       } else {
 900         // otherwise an edge from the referencer to alpha_S exists already
 901         // and the edge referencer->alpha_K should be merged with it
 902         edgeSummary.setBeta(
 903                             Canonical.union( edgeMerged.getBeta(),
 904                                              edgeSummary.getBeta()
 905                                              )
 906                              );
 907         edgeSummary.setPreds(
 908                              Canonical.join( edgeMerged.getPreds(),
 909                                              edgeSummary.getPreds()
 910                                              )
 911                               );
 912       }
 913     }
 914
 915     // then merge hrn reachability into hrnSummary
 916     hrnSummary.setAlpha(
 917                         Canonical.union( hrnSummary.getAlpha(),
 918                                          hrn.getAlpha()
 919                                          )
 920                          );
 921
 922     hrnSummary.setPreds(
 923                         Canonical.join( hrnSummary.getPreds(),
 924                                         hrn.getPreds()
 925                                         )
 926                         );
 927
 928     // and afterward, this node is gone
 929     wipeOut( hrn, true );
 930   }
 931
 932
 933   protected void transferOnto( HeapRegionNode hrnA,
 934                                HeapRegionNode hrnB ) {
 935
 936     assert belongsToThis( hrnA );
 937     assert belongsToThis( hrnB );
 938
 939     // clear references in and out of node b
 940     assert hrnB.isWiped();
 941
 942     // copy each edge in and out of A to B
 943     Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
 944     while( itrReferencee.hasNext() ) {
 945       RefEdge        edge          = itrReferencee.next();
 946       HeapRegionNode hrnReferencee = edge.getDst();
 947       RefEdge        edgeNew       = edge.copy();
 948       edgeNew.setSrc( hrnB );
 949       edgeNew.setDst( hrnReferencee );
 950
 951       addRefEdge( hrnB, hrnReferencee, edgeNew );
 952     }
 953
 954     Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
 955     while( itrReferencer.hasNext() ) {
 956       RefEdge    edge         = itrReferencer.next();
 957       RefSrcNode onReferencer = edge.getSrc();
 958       RefEdge    edgeNew      = edge.copy();
 959       edgeNew.setDst( hrnB );
 960       edgeNew.setDst( hrnB );
 961
 962       addRefEdge( onReferencer, hrnB, edgeNew );
 963     }
 964
 965     // replace hrnB reachability and preds with hrnA's
 966     hrnB.setAlpha( hrnA.getAlpha() );
 967     hrnB.setPreds( hrnA.getPreds() );
 968
 969     // after transfer, wipe out source
 970     wipeOut( hrnA, true );
 971   }
 972
 973
 974   // the purpose of this method is to conceptually "wipe out"
 975   // a heap region from the graph--purposefully not called REMOVE
 976   // because the node is still hanging around in the graph, just
 977   // not mechanically connected or have any reach or predicate
 978   // information on it anymore--lots of ops can use this
 979   protected void wipeOut( HeapRegionNode hrn,
 980                           boolean        wipeVariableReferences ) {
 981
 982     assert belongsToThis( hrn );
 983
 984     clearRefEdgesFrom( hrn, null, null, true );
 985
 986     if( wipeVariableReferences ) {
 987       clearRefEdgesTo( hrn, null, null, true );
 988     } else {
 989       clearNonVarRefEdgesTo( hrn );
 990     }
 991
 992     hrn.setAlpha( rsetEmpty );
 993     hrn.setPreds( predsEmpty );
 994   }
 995
 996
 997   protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
 998     edge.setBeta(
 999                  Canonical.ageTuplesFrom( edge.getBeta(),
1000                                           as
1001                                           )
1002                   );
1003   }
1004
1005   protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1006     hrn.setAlpha(
1007                  Canonical.ageTuplesFrom( hrn.getAlpha(),
1008                                           as
1009                                           )
1010                   );
1011   }
1012
1013
1014
1015   protected void propagateTokensOverNodes( HeapRegionNode          nPrime,
1016                                            ChangeSet               c0,
1017                                            HashSet<HeapRegionNode> nodesWithNewAlpha,
1018                                            HashSet<RefEdge>        edgesWithNewBeta ) {
1019
1020     HashSet<HeapRegionNode> todoNodes
1021       = new HashSet<HeapRegionNode>();
1022     todoNodes.add( nPrime );
1023
1024     HashSet<RefEdge> todoEdges
1025       = new HashSet<RefEdge>();
1026
1027     Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1028       = new Hashtable<HeapRegionNode, ChangeSet>();
1029     nodePlannedChanges.put( nPrime, c0 );
1030
1031     Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1032       = new Hashtable<RefEdge, ChangeSet>();
1033
1034     // first propagate change sets everywhere they can go
1035     while( !todoNodes.isEmpty() ) {
1036       HeapRegionNode n = todoNodes.iterator().next();
1037       ChangeSet      C = nodePlannedChanges.get( n );
1038
1039       Iterator<RefEdge> referItr = n.iteratorToReferencers();
1040       while( referItr.hasNext() ) {
1041         RefEdge edge = referItr.next();
1042         todoEdges.add( edge );
1043
1044         if( !edgePlannedChanges.containsKey( edge ) ) {
1045           edgePlannedChanges.put( edge,
1046                                   ChangeSet.factory()
1047                                   );
1048         }
1049
1050         edgePlannedChanges.put( edge,
1051                                 Canonical.union( edgePlannedChanges.get( edge ),
1052                                                  C
1053                                                  )
1054                                 );
1055       }
1056
1057       Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1058       while( refeeItr.hasNext() ) {
1059         RefEdge        edgeF = refeeItr.next();
1060         HeapRegionNode m     = edgeF.getDst();
1061
1062         ChangeSet changesToPass = ChangeSet.factory();
1063
1064         Iterator<ChangeTuple> itrCprime = C.iterator();
1065         while( itrCprime.hasNext() ) {
1066           ChangeTuple c = itrCprime.next();
1067           if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1068             changesToPass = Canonical.union( changesToPass, c );
1069           }
1070         }
1071
1072         if( !changesToPass.isEmpty() ) {
1073           if( !nodePlannedChanges.containsKey( m ) ) {
1074             nodePlannedChanges.put( m, ChangeSet.factory() );
1075           }
1076
1077           ChangeSet currentChanges = nodePlannedChanges.get( m );
1078
1079           if( !changesToPass.isSubset( currentChanges ) ) {
1080
1081             nodePlannedChanges.put( m,
1082                                     Canonical.union( currentChanges,
1083                                                      changesToPass
1084                                                      )
1085                                     );
1086             todoNodes.add( m );
1087           }
1088         }
1089       }
1090
1091       todoNodes.remove( n );
1092     }
1093
1094     // then apply all of the changes for each node at once
1095     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1096     while( itrMap.hasNext() ) {
1097       Map.Entry      me = (Map.Entry)      itrMap.next();
1098       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1099       ChangeSet      C  = (ChangeSet)      me.getValue();
1100
1101       // this propagation step is with respect to one change,
1102       // so we capture the full change from the old alpha:
1103       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1104                                                       C,
1105                                                       true
1106                                                       );
1107       // but this propagation may be only one of many concurrent
1108       // possible changes, so keep a running union with the node's
1109       // partially updated new alpha set
1110       n.setAlphaNew( Canonical.union( n.getAlphaNew(),
1111                                       localDelta
1112                                       )
1113                      );
1114
1115       nodesWithNewAlpha.add( n );
1116     }
1117
1118     propagateTokensOverEdges( todoEdges,
1119                               edgePlannedChanges,
1120                               edgesWithNewBeta
1121                               );
1122   }
1123
1124
1125   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1126                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1127                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1128
1129     // first propagate all change tuples everywhere they can go
1130     while( !todoEdges.isEmpty() ) {
1131       RefEdge edgeE = todoEdges.iterator().next();
1132       todoEdges.remove( edgeE );
1133
1134       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1135         edgePlannedChanges.put( edgeE,
1136                                 ChangeSet.factory()
1137                                 );
1138       }
1139
1140       ChangeSet C = edgePlannedChanges.get( edgeE );
1141
1142       ChangeSet changesToPass = ChangeSet.factory();
1143
1144       Iterator<ChangeTuple> itrC = C.iterator();
1145       while( itrC.hasNext() ) {
1146         ChangeTuple c = itrC.next();
1147         if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1148           changesToPass = Canonical.union( changesToPass, c );
1149         }
1150       }
1151
1152       RefSrcNode rsn = edgeE.getSrc();
1153
1154       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1155         HeapRegionNode n = (HeapRegionNode) rsn;
1156
1157         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1158         while( referItr.hasNext() ) {
1159           RefEdge edgeF = referItr.next();
1160
1161           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1162             edgePlannedChanges.put( edgeF,
1163                                     ChangeSet.factory()
1164                                     );
1165           }
1166
1167           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1168
1169           if( !changesToPass.isSubset( currentChanges ) ) {
1170             todoEdges.add( edgeF );
1171             edgePlannedChanges.put( edgeF,
1172                                     Canonical.union( currentChanges,
1173                                                      changesToPass
1174                                                      )
1175                                     );
1176           }
1177         }
1178       }
1179     }
1180
1181     // then apply all of the changes for each edge at once
1182     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1183     while( itrMap.hasNext() ) {
1184       Map.Entry me = (Map.Entry) itrMap.next();
1185       RefEdge   e  = (RefEdge)   me.getKey();
1186       ChangeSet C  = (ChangeSet) me.getValue();
1187
1188       // this propagation step is with respect to one change,
1189       // so we capture the full change from the old beta:
1190       ReachSet localDelta =
1191         Canonical.applyChangeSet( e.getBeta(),
1192                                   C,
1193                                   true
1194                                   );
1195
1196       // but this propagation may be only one of many concurrent
1197       // possible changes, so keep a running union with the edge's
1198       // partially updated new beta set
1199       e.setBetaNew( Canonical.union( e.getBetaNew(),
1200                                      localDelta
1201                                      )
1202                     );
1203
1204       edgesWithNewBeta.add( e );
1205     }
1206   }
1207
1208
1209   // used in makeCalleeView below to decide if there is
1210   // already an appropriate out-of-context edge in a callee
1211   // view graph for merging, or null if a new one will be added
1212   protected RefEdge
1213     getOutOfContextReferenceTo( HeapRegionNode hrn,
1214                                 TypeDescriptor srcType,
1215                                 TypeDescriptor refType,
1216                                 String         refField ) {
1217
1218     HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1219     if( hrnInContext == null ) {
1220       return null;
1221     }
1222
1223     Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1224     while( refItr.hasNext() ) {
1225       RefEdge re = refItr.next();
1226       if( !(re.getSrc() instanceof HeapRegionNode) ) {
1227         continue;
1228       }
1229
1230       HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1231       if( !hrnSrc.isOutOfContext() ) {
1232         continue;
1233       }
1234
1235       if( srcType == null ) {
1236         if( hrnSrc.getType() != null ) {
1237           continue;
1238         }
1239       } else {
1240         if( !srcType.equals( hrnSrc.getType() ) ) {
1241           continue;
1242         }
1243       }
1244
1245       if( !re.typeEquals( refType ) ) {
1246         continue;
1247       }
1248
1249       if( !re.fieldEquals( refField ) ) {
1250         continue;
1251       }
1252
1253       // tada!  We found it!
1254       return re;
1255     }
1256
1257     return null;
1258   }
1259
1260
1261   // use this method to make a new reach graph that is
1262   // what heap the FlatMethod callee from the FlatCall
1263   // would start with reaching from its arguments in
1264   // this reach graph
1265   public ReachGraph
1266     makeCalleeView( FlatCall     fc,
1267                     FlatMethod   fm,
1268                     Set<Integer> callerNodeIDsCopiedToCallee,
1269                     boolean      writeDebugDOTs
1270                     ) {
1271
1272     // the callee view is a new graph: DON'T MODIFY
1273     // *THIS* graph
1274     ReachGraph rg = new ReachGraph();
1275
1276     // track what parts of this graph have already been
1277     // added to callee view, variables not needed.
1278     // Note that we need this because when we traverse
1279     // this caller graph for each parameter we may find
1280     // nodes and edges more than once (which the per-param
1281     // "visit" sets won't show) and we only want to create
1282     // an element in the new callee view one time
1283
1284
1285     // a conservative starting point is to take the
1286     // mechanically-reachable-from-arguments graph
1287     // as opposed to using reachability information
1288     // to prune the graph further
1289     for( int i = 0; i < fm.numParameters(); ++i ) {
1290
1291       // for each parameter index, get the symbol in the
1292       // caller view and callee view
1293
1294       // argument defined here is the symbol in the caller
1295       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
1296
1297       // parameter defined here is the symbol in the callee
1298       TempDescriptor tdParam = fm.getParameter( i );
1299
1300       // use these two VariableNode objects to translate
1301       // between caller and callee--its easy to compare
1302       // a HeapRegionNode across callee and caller because
1303       // they will have the same heap region ID
1304       VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1305       VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1306
1307       // now traverse the calleR view using the argument to
1308       // build the calleE view which has the parameter symbol
1309       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1310       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1311       toVisitInCaller.add( vnCaller );
1312
1313       while( !toVisitInCaller.isEmpty() ) {
1314         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1315         RefSrcNode rsnCallee;
1316
1317         toVisitInCaller.remove( rsnCaller );
1318         visitedInCaller.add( rsnCaller );
1319
1320         // FIRST - setup the source end of an edge, and
1321         // remember the identifying info of the source
1322         // to build predicates
1323         TempDescriptor tdSrc    = null;
1324         Integer        hrnSrcID = null;
1325
1326         if( rsnCaller == vnCaller ) {
1327           // if the caller node is the param symbol, we
1328           // have to do this translation for the callee
1329           rsnCallee = vnCallee;
1330           tdSrc     = tdArg;
1331
1332         } else {
1333           // otherwise the callee-view node is a heap
1334           // region with the same ID, that may or may
1335           // not have been created already
1336           assert rsnCaller instanceof HeapRegionNode;
1337
1338           HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1339           hrnSrcID = hrnSrcCaller.getID();
1340
1341           if( !callerNodeIDsCopiedToCallee.contains( hrnSrcID ) ) {
1342
1343             ExistPred pred =
1344               ExistPred.factory( hrnSrcID, null );
1345
1346             ExistPredSet preds =
1347               ExistPredSet.factory( pred );
1348
1349             rsnCallee =
1350               rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1351                                           hrnSrcCaller.isSingleObject(),
1352                                           hrnSrcCaller.isNewSummary(),
1353                                           hrnSrcCaller.isFlagged(),
1354                                           false, // out-of-context?
1355                                           hrnSrcCaller.getType(),
1356                                           hrnSrcCaller.getAllocSite(),
1357                                           /*toShadowTokens( this,*/ hrnSrcCaller.getInherent() /*)*/,
1358                                           /*toShadowTokens( this,*/ hrnSrcCaller.getAlpha() /*)*/,
1359                                           preds,
1360                                           hrnSrcCaller.getDescription()
1361                                           );
1362
1363             callerNodeIDsCopiedToCallee.add( hrnSrcID );
1364
1365           } else {
1366             rsnCallee = rg.id2hrn.get( hrnSrcID );
1367           }
1368         }
1369
1370         // SECOND - go over all edges from that source
1371
1372         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1373         while( itrRefEdges.hasNext() ) {
1374           RefEdge        reCaller  = itrRefEdges.next();
1375           HeapRegionNode hrnCaller = reCaller.getDst();
1376           HeapRegionNode hrnCallee;
1377
1378           // THIRD - setup destination ends of edges
1379           Integer hrnDstID = hrnCaller.getID();
1380
1381           if( !callerNodeIDsCopiedToCallee.contains( hrnDstID ) ) {
1382
1383             ExistPred pred =
1384               ExistPred.factory( hrnDstID, null );
1385
1386             ExistPredSet preds =
1387               ExistPredSet.factory( pred );
1388
1389             hrnCallee =
1390               rg.createNewHeapRegionNode( hrnDstID,
1391                                           hrnCaller.isSingleObject(),
1392                                           hrnCaller.isNewSummary(),
1393                                           hrnCaller.isFlagged(),
1394                                           false, // out-of-context?
1395                                           hrnCaller.getType(),
1396                                           hrnCaller.getAllocSite(),
1397                                           /*toShadowTokens( this,*/ hrnCaller.getInherent() /*)*/,
1398                                           /*toShadowTokens( this,*/ hrnCaller.getAlpha() /*)*/,
1399                                           preds,
1400                                           hrnCaller.getDescription()
1401                                           );
1402
1403             callerNodeIDsCopiedToCallee.add( hrnDstID );
1404
1405           } else {
1406             hrnCallee = rg.id2hrn.get( hrnDstID );
1407           }
1408
1409           // FOURTH - copy edge over if needed
1410           RefEdge reCallee = rsnCallee.getReferenceTo( hrnCallee,
1411                                                        reCaller.getType(),
1412                                                        reCaller.getField()
1413                                                        );
1414           if( reCallee == null ) {
1415
1416             ExistPred pred =
1417               ExistPred.factory( tdSrc,
1418                                  hrnSrcID,
1419                                  hrnDstID,
1420                                  reCaller.getType(),
1421                                  reCaller.getField(),
1422                                  null,
1423                                  rsnCaller instanceof VariableNode ); // out-of-context
1424
1425             ExistPredSet preds =
1426               ExistPredSet.factory( pred );
1427
1428             rg.addRefEdge( rsnCallee,
1429                            hrnCallee,
1430                            new RefEdge( rsnCallee,
1431                                         hrnCallee,
1432                                         reCaller.getType(),
1433                                         reCaller.getField(),
1434                                         /*toShadowTokens( this,*/ reCaller.getBeta() /*)*/,
1435                                         preds
1436                                         )
1437                            );
1438           }
1439
1440           // keep traversing nodes reachable from param i
1441           // that we haven't visited yet
1442           if( !visitedInCaller.contains( hrnCaller ) ) {
1443             toVisitInCaller.add( hrnCaller );
1444           }
1445
1446         } // end edge iteration
1447       } // end visiting heap nodes in caller
1448     } // end iterating over parameters as starting points
1449
1450
1451     // find the set of edges in this graph with source
1452     // out-of-context (not in nodes copied) and have a
1453     // destination in context (one of nodes copied) as
1454     // a starting point for building out-of-context nodes
1455     Iterator<Integer> itrInContext =
1456       callerNodeIDsCopiedToCallee.iterator();
1457     while( itrInContext.hasNext() ) {
1458       Integer        hrnID                 = itrInContext.next();
1459       HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1460
1461       Iterator<RefEdge> itrMightCross =
1462         hrnCallerAndInContext.iteratorToReferencers();
1463       while( itrMightCross.hasNext() ) {
1464         RefEdge edgeMightCross = itrMightCross.next();
1465
1466         RefSrcNode rsnCallerAndOutContext =
1467           edgeMightCross.getSrc();
1468
1469         TypeDescriptor oocNodeType;
1470         ReachSet       oocReach;
1471
1472         TempDescriptor oocPredSrcTemp = null;
1473         Integer        oocPredSrcID   = null;
1474
1475         if( rsnCallerAndOutContext instanceof VariableNode ) {
1476           // variables are always out-of-context
1477           oocNodeType = null;
1478           oocReach    = rsetEmpty;
1479           oocPredSrcTemp =
1480             ((VariableNode)rsnCallerAndOutContext).getTempDescriptor();
1481
1482         } else {
1483
1484           HeapRegionNode hrnCallerAndOutContext =
1485             (HeapRegionNode) rsnCallerAndOutContext;
1486
1487           // is this source node out-of-context?
1488           if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1489             // no, skip this edge
1490             continue;
1491           }
1492
1493           oocNodeType  = hrnCallerAndOutContext.getType();
1494           oocReach     = hrnCallerAndOutContext.getAlpha();
1495           oocPredSrcID = hrnCallerAndOutContext.getID();
1496         }
1497
1498         // if we're here we've found an out-of-context edge
1499
1500         ExistPred pred =
1501           ExistPred.factory( oocPredSrcTemp,
1502                              oocPredSrcID,
1503                              hrnID,
1504                              edgeMightCross.getType(),
1505                              edgeMightCross.getField(),
1506                              null,
1507                              true ); // out-of-context
1508
1509         ExistPredSet preds =
1510           ExistPredSet.factory( pred );
1511
1512
1513         HeapRegionNode hrnCalleeAndInContext =
1514           rg.id2hrn.get( hrnCallerAndInContext.getID() );
1515
1516         RefEdge oocEdgeExisting =
1517           rg.getOutOfContextReferenceTo( hrnCalleeAndInContext,
1518                                          oocNodeType,
1519                                          edgeMightCross.getType(),
1520                                          edgeMightCross.getField()
1521                                          );
1522
1523         if( oocEdgeExisting == null ) {
1524           // we found a reference that crosses from out-of-context
1525           // to in-context, so build a special out-of-context node
1526           // for the callee IHM and its reference edge
1527
1528           // for consistency, map one out-of-context "identifier"
1529           // to one heap region node id, otherwise no convergence
1530           String oocid = "oocid"+
1531             hrnCalleeAndInContext.getIDString()+
1532             oocNodeType+
1533             edgeMightCross.getType()+
1534             edgeMightCross.getField();
1535
1536           Integer oocHrnID = oocid2hrnid.get( oocid );
1537
1538           HeapRegionNode hrnCalleeAndOutContext;
1539
1540           if( oocHrnID == null ) {
1541
1542             hrnCalleeAndOutContext =
1543               rg.createNewHeapRegionNode( null,  // ID
1544                                           false, // single object?
1545                                           false, // new summary?
1546                                           false, // flagged?
1547                                           true,  // out-of-context?
1548                                           oocNodeType,
1549                                           null,  // alloc site, shouldn't be used
1550                                           /*toShadowTokens( this,*/ oocReach  /*)*/, // inherent
1551                                           /*toShadowTokens( this,*/ oocReach /*)*/, // alpha
1552                                           preds,
1553                                           "out-of-context"
1554                                           );
1555
1556             oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1557
1558           } else {
1559             hrnCalleeAndOutContext =
1560               rg.createNewHeapRegionNode( oocHrnID,  // ID
1561                                           false, // single object?
1562                                           false, // new summary?
1563                                           false, // flagged?
1564                                           true,  // out-of-context?
1565                                           oocNodeType,
1566                                           null,  // alloc site, shouldn't be used
1567                                           /*toShadowTokens( this,*/ oocReach  /*)*/, // inherent
1568                                           /*toShadowTokens( this,*/ oocReach /*)*/, // alpha
1569                                           preds,
1570                                           "out-of-context"
1571                                           );
1572           }
1573
1574           rg.addRefEdge( hrnCalleeAndOutContext,
1575                          hrnCalleeAndInContext,
1576                          new RefEdge( hrnCalleeAndOutContext,
1577                                       hrnCalleeAndInContext,
1578                                       edgeMightCross.getType(),
1579                                       edgeMightCross.getField(),
1580                                       /*toShadowTokens( this,*/ edgeMightCross.getBeta() /*)*/,
1581                                       preds
1582                                       )
1583                          );
1584
1585         } else {
1586           // the out-of-context edge already exists
1587           oocEdgeExisting.setBeta( Canonical.union( oocEdgeExisting.getBeta(),
1588                                                     edgeMightCross.getBeta()
1589                                                     )
1590                                    );
1591         }
1592       }
1593     }
1594
1595     if( writeDebugDOTs ) {
1596       try {
1597         rg.writeGraph( "calleeview", true, false, false, false, true, true );
1598       } catch( IOException e ) {}
1599     }
1600
1601     return rg;
1602   }
1603
1604   private static Hashtable<String, Integer> oocid2hrnid =
1605     new Hashtable<String, Integer>();
1606
1607
1608
1609   public void
1610     resolveMethodCall( FlatCall     fc,
1611                        FlatMethod   fm,
1612                        ReachGraph   rgCallee,
1613                        Set<Integer> callerNodeIDsCopiedToCallee,
1614                        boolean      writeDebugDOTs
1615                        ) {
1616
1617
1618     if( writeDebugDOTs ) {
1619       try {
1620         rgCallee.writeGraph( "callee",
1621                              true, false, false, false, true, true );
1622         writeGraph( "caller00In",
1623                     true, false, false, false, true, true,
1624                     callerNodeIDsCopiedToCallee );
1625       } catch( IOException e ) {}
1626     }
1627
1628
1629     // method call transfer function steps:
1630     // 1. Use current callee-reachable heap (CRH) to test callee
1631     //    predicates and mark what will be coming in.
1632     // 2. Wipe CRH out of caller.
1633     // 3. Transplant marked callee parts in:
1634     //    a) bring in nodes
1635     //    b) bring in callee -> callee edges
1636     //    c) resolve out-of-context -> callee edges
1637     //    d) assign return value
1638     // 4. Collapse shadow nodes down
1639     // 5. Global sweep it.
1640
1641
1642
1643     // 1. mark what callee elements have satisfied predicates
1644     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1645       new Hashtable<HeapRegionNode, ExistPredSet>();
1646
1647     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1648       new Hashtable<RefEdge, ExistPredSet>();
1649
1650     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1651     while( meItr.hasNext() ) {
1652       Map.Entry      me        = (Map.Entry)      meItr.next();
1653       Integer        id        = (Integer)        me.getKey();
1654       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1655
1656       ExistPredSet predsIfSatis =
1657         hrnCallee.getPreds().isSatisfiedBy( this,
1658                                             callerNodeIDsCopiedToCallee
1659                                             );
1660       if( predsIfSatis != null ) {
1661         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
1662       } else {
1663         // otherwise don't bother looking at edges from this node
1664         continue;
1665       }
1666
1667       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencees();
1668       while( reItr.hasNext() ) {
1669         RefEdge reCallee = reItr.next();
1670
1671         ExistPredSet ifDst =
1672           reCallee.getDst().getPreds().isSatisfiedBy( this,
1673                                                       callerNodeIDsCopiedToCallee
1674                                                       );
1675         if( ifDst == null ) {
1676           continue;
1677         }
1678
1679         predsIfSatis =
1680           reCallee.getPreds().isSatisfiedBy( this,
1681                                              callerNodeIDsCopiedToCallee
1682                                              );
1683         if( predsIfSatis != null ) {
1684           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1685         }
1686       }
1687     }
1688
1689     // test param -> HRN edges, also
1690     for( int i = 0; i < fm.numParameters(); ++i ) {
1691
1692       // parameter defined here is the symbol in the callee
1693       TempDescriptor tdParam  = fm.getParameter( i );
1694       VariableNode   vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
1695
1696       Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
1697       while( reItr.hasNext() ) {
1698         RefEdge reCallee = reItr.next();
1699
1700         ExistPredSet ifDst =
1701           reCallee.getDst().getPreds().isSatisfiedBy( this,
1702                                                       callerNodeIDsCopiedToCallee
1703                                                       );
1704         if( ifDst == null ) {
1705           continue;
1706         }
1707
1708         ExistPredSet predsIfSatis =
1709           reCallee.getPreds().isSatisfiedBy( this,
1710                                              callerNodeIDsCopiedToCallee
1711                                              );
1712         if( predsIfSatis != null ) {
1713           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
1714         }
1715       }
1716     }
1717
1718
1719
1720
1721     if( writeDebugDOTs ) {
1722       try {
1723         writeGraph( "caller20BeforeWipe",
1724                     true, false, false, false, true, true );
1725       } catch( IOException e ) {}
1726     }
1727
1728
1729     // 2. predicates tested, ok to wipe out caller part
1730     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
1731     while( hrnItr.hasNext() ) {
1732       Integer        hrnID     = hrnItr.next();
1733       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
1734       assert hrnCaller != null;
1735
1736       // when clearing off nodes, also eliminate variable
1737       // references
1738       wipeOut( hrnCaller, true );
1739     }
1740
1741
1742
1743     if( writeDebugDOTs ) {
1744       try {
1745         writeGraph( "caller30BeforeAddingNodes",
1746                     true, false, false, false, true, true );
1747       } catch( IOException e ) {}
1748     }
1749
1750
1751     // 3. callee elements with satisfied preds come in, note that
1752     //    the mapping of elements satisfied to preds is like this:
1753     //    A callee element EE has preds EEp that are satisfied by
1754     //    some caller element ER.  We bring EE into the caller
1755     //    context as ERee with the preds of ER, namely ERp, which
1756     //    in the following algorithm is the value in the mapping
1757
1758     // 3.a) nodes
1759     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
1760     while( satisItr.hasNext() ) {
1761       Map.Entry      me        = (Map.Entry)      satisItr.next();
1762       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
1763       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
1764
1765       if( hrnCallee.isOutOfContext() ) {
1766         continue;
1767       }
1768
1769       AllocSite as = hrnCallee.getAllocSite();
1770       allocSites.add( as );
1771
1772       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
1773
1774       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
1775       if( hrnCaller == null ) {
1776         hrnCaller =
1777           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
1778                                    hrnCallee.isSingleObject(), // single object?
1779                                    hrnCallee.isNewSummary(),   // summary?
1780                                    hrnCallee.isFlagged(),      // flagged?
1781                                    false,                      // out-of-context?
1782                                    hrnCallee.getType(),        // type
1783                                    hrnCallee.getAllocSite(),   // allocation site
1784                                    hrnCallee.getInherent(),    // inherent reach
1785                                    null,                       // current reach
1786                                    predsEmpty,                 // predicates
1787                                    hrnCallee.getDescription()  // description
1788                                    );
1789       } else {
1790         assert hrnCaller.isWiped();
1791       }
1792
1793       // TODO: alpha should be some rewritten version of callee in caller context
1794       hrnCaller.setAlpha( rsetEmpty );
1795
1796       hrnCaller.setPreds( preds );
1797     }
1798
1799
1800
1801     if( writeDebugDOTs ) {
1802       try {
1803         writeGraph( "caller31BeforeAddingEdges",
1804                     true, false, false, false, true, true );
1805       } catch( IOException e ) {}
1806     }
1807
1808
1809     // 3.b) callee -> callee edges AND out-of-context -> callee
1810     satisItr = calleeEdgesSatisfied.entrySet().iterator();
1811     while( satisItr.hasNext() ) {
1812       Map.Entry    me       = (Map.Entry)    satisItr.next();
1813       RefEdge      reCallee = (RefEdge)      me.getKey();
1814       ExistPredSet preds    = (ExistPredSet) me.getValue();
1815
1816       RefSrcNode     rsnCallee    = reCallee.getSrc();
1817       HeapRegionNode hrnDstCallee = reCallee.getDst();
1818
1819       // even though we don't know yet what we're doing with
1820       // this edge, do this translation from callee dst to
1821       // caller dst a little early so we can use the result
1822       // for out-of-context matching below
1823       AllocSite asDst =
1824         hrnDstCallee.getAllocSite();
1825       Integer hrnIDDstShadow =
1826         asDst.getShadowIDfromID( hrnDstCallee.getID() );
1827       HeapRegionNode hrnDstCaller =
1828         id2hrn.get( hrnIDDstShadow );
1829
1830       // we'll find the set of sources in the caller that
1831       // this callee source could be (out-of-context node
1832       // can potentially map to multiple caller nodes)
1833       Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
1834
1835       if( rsnCallee instanceof VariableNode ) {
1836         // variable -> node in the callee should only
1837         // come into the caller if its from a param var
1838         VariableNode   vnCallee = (VariableNode) rsnCallee;
1839         TempDescriptor tdParam  = vnCallee.getTempDescriptor();
1840         TempDescriptor tdArg    = fc.getArgMatchingParam( fm,
1841                                                           tdParam );
1842         if( tdArg == null ) {
1843           // this means the variable isn't a parameter, its local
1844           // to the callee so we ignore it in call site transfer
1845           continue;
1846         }
1847
1848         rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
1849
1850       } else {
1851         HeapRegionNode hrnSrcCallee = (HeapRegionNode) reCallee.getSrc();
1852
1853         if( !hrnSrcCallee.isOutOfContext() ) {
1854           AllocSite asSrc = hrnSrcCallee.getAllocSite();
1855           allocSites.add( asSrc );
1856
1857           Integer hrnIDSrcShadow = asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
1858           rsnCallers.add( id2hrn.get( hrnIDSrcShadow ) );
1859
1860         } else {
1861           // for out-of-context sources we have to find all
1862           // caller sources that might match
1863           assert hrnDstCaller != null;
1864
1865           Iterator<RefEdge> reItr = hrnDstCaller.iteratorToReferencers();
1866           while( reItr.hasNext() ) {
1867             // the edge and field (either possibly null) must match
1868             RefEdge reCaller = reItr.next();
1869             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
1870                 !reCaller.fieldEquals( reCallee.getField() )
1871                 ) {
1872               continue;
1873             }
1874
1875             RefSrcNode rsnCaller = reCaller.getSrc();
1876             if( rsnCaller instanceof VariableNode ) {
1877               // a variable node matches an OOC region with null type
1878               if( hrnSrcCallee.getType() != null ) {
1879                 continue;
1880               }
1881
1882             } else {
1883               // otherwise types should match
1884               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
1885               if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
1886                 continue;
1887               }
1888             }
1889
1890             // it matches, add to sources of edges to make
1891             rsnCallers.add( rsnCaller );
1892           }
1893         }
1894       }
1895
1896       assert !rsnCallers.isEmpty();
1897
1898       allocSites.add( asDst );
1899
1900       assert hrnDstCaller != null;
1901
1902       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
1903       while( rsnItr.hasNext() ) {
1904         RefSrcNode rsnCaller = rsnItr.next();
1905
1906         // TODO: beta rewrites
1907         RefEdge reCaller = new RefEdge( rsnCaller,
1908                                         hrnDstCaller,
1909                                         reCallee.getType(),
1910                                         reCallee.getField(),
1911                                         rsetEmpty,
1912                                         preds
1913                                         );
1914
1915         // look to see if an edge with same field exists
1916         // and merge with it, otherwise just add the edge
1917         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
1918                                                          reCallee.getType(),
1919                                                          reCallee.getField()
1920                                                          );
1921         if( edgeExisting != null ) {
1922           edgeExisting.setBeta(
1923                                Canonical.union( edgeExisting.getBeta(),
1924                                                 reCaller.getBeta()
1925                                                 )
1926                                );
1927           edgeExisting.setPreds(
1928                                 Canonical.join( edgeExisting.getPreds(),
1929                                                 reCaller.getPreds()
1930                                                 )
1931                                 );
1932
1933         } else {
1934           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
1935         }
1936       }
1937     }
1938
1939
1940     /*
1941     if( writeDebugDOTs ) {
1942       try {
1943         writeGraph( "caller33BeforeResolveOutOfContextEdges",
1944                     true, false, false, false, true, true );
1945       } catch( IOException e ) {}
1946     }
1947     */
1948
1949
1950
1951
1952     if( writeDebugDOTs ) {
1953       try {
1954         writeGraph( "caller35BeforeAssignReturnValue",
1955                     true, false, false, false, true, true );
1956       } catch( IOException e ) {}
1957     }
1958
1959
1960     // 3.d) handle return value assignment if needed
1961     TempDescriptor returnTemp = fc.getReturnTemp();
1962     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1963
1964       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
1965       clearRefEdgesFrom( vnLhsCaller, null, null, true );
1966
1967       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
1968       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
1969       while( reCalleeItr.hasNext() ) {
1970         RefEdge        reCallee     = reCalleeItr.next();
1971         HeapRegionNode hrnDstCallee = reCallee.getDst();
1972
1973         // some edge types are not possible return values when we can
1974         // see what type variable we are assigning it to
1975         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
1976           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
1977                               reCallee+" for return temp "+returnTemp );
1978           // prune
1979           continue;
1980         }
1981
1982         AllocSite asDst = hrnDstCallee.getAllocSite();
1983         allocSites.add( asDst );
1984
1985         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
1986
1987         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
1988         if( hrnDstCaller == null ) {
1989           hrnDstCaller =
1990             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
1991                                      hrnDstCallee.isSingleObject(), // single object?
1992                                      hrnDstCallee.isNewSummary(),   // summary?
1993                                      hrnDstCallee.isFlagged(),      // flagged?
1994                                      false,                      // out-of-context?
1995                                      hrnDstCallee.getType(),        // type
1996                                      hrnDstCallee.getAllocSite(),   // allocation site
1997                                      hrnDstCallee.getInherent(),    // inherent reach
1998                                      null,                       // current reach
1999                                      predsTrue,                 // predicates
2000                                      hrnDstCallee.getDescription()  // description
2001                                      );
2002         } else {
2003           assert hrnDstCaller.isWiped();
2004         }
2005
2006         TypeDescriptor tdNewEdge =
2007           mostSpecificType( reCallee.getType(),
2008                             hrnDstCallee.getType(),
2009                             hrnDstCaller.getType()
2010                             );
2011
2012         RefEdge reCaller = new RefEdge( vnLhsCaller,
2013                                         hrnDstCaller,
2014                                         tdNewEdge,
2015                                         null,
2016                                         rsetEmpty,
2017                                         predsTrue
2018                                         );
2019
2020         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2021       }
2022     }
2023
2024
2025
2026     if( writeDebugDOTs ) {
2027       try {
2028         writeGraph( "caller40BeforeShadowMerge",
2029                     true, false, false, false, true, true );
2030       } catch( IOException e ) {}
2031     }
2032
2033
2034     // 4) merge shadow nodes so alloc sites are back to k
2035     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2036     while( asItr.hasNext() ) {
2037       // for each allocation site do the following to merge
2038       // shadow nodes (newest from callee) with any existing
2039       // look for the newest normal and newest shadow "slot"
2040       // not being used, transfer normal to shadow.  Keep
2041       // doing this until there are no more normal nodes, or
2042       // no empty shadow slots: then merge all remaining normal
2043       // nodes into the shadow summary.  Finally, convert all
2044       // shadow to their normal versions.
2045       AllocSite as = asItr.next();
2046       int ageNorm = 0;
2047       int ageShad = 0;
2048       while( ageNorm < allocationDepth &&
2049              ageShad < allocationDepth ) {
2050
2051         // first, are there any normal nodes left?
2052         Integer        idNorm  = as.getIthOldest( ageNorm );
2053         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2054         if( hrnNorm == null ) {
2055           // no, this age of normal node not in the caller graph
2056           ageNorm++;
2057           continue;
2058         }
2059
2060         // yes, a normal node exists, is there an empty shadow
2061         // "slot" to transfer it onto?
2062         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2063         if( !hrnShad.isWiped() ) {
2064           // no, this age of shadow node is not empty
2065           ageShad++;
2066           continue;
2067         }
2068
2069         // yes, this shadow node is empty
2070         transferOnto( hrnNorm, hrnShad );
2071         ageNorm++;
2072         ageShad++;
2073       }
2074
2075       // now, while there are still normal nodes but no shadow
2076       // slots, merge normal nodes into the shadow summary
2077       while( ageNorm < allocationDepth ) {
2078
2079         // first, are there any normal nodes left?
2080         Integer        idNorm  = as.getIthOldest( ageNorm );
2081         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2082         if( hrnNorm == null ) {
2083           // no, this age of normal node not in the caller graph
2084           ageNorm++;
2085           continue;
2086         }
2087
2088         // yes, a normal node exists, so get the shadow summary
2089         HeapRegionNode summShad = getSummaryNode( as, true );
2090         mergeIntoSummary( hrnNorm, summShad );
2091         ageNorm++;
2092       }
2093
2094       // if there is a normal summary, merge it into shadow summary
2095       Integer        idNorm   = as.getSummary();
2096       HeapRegionNode summNorm = id2hrn.get( idNorm );
2097       if( summNorm != null ) {
2098         HeapRegionNode summShad = getSummaryNode( as, true );
2099         mergeIntoSummary( summNorm, summShad );
2100       }
2101
2102       // finally, flip all existing shadow nodes onto the normal
2103       for( int i = 0; i < allocationDepth; ++i ) {
2104         Integer        idShad  = as.getIthOldestShadow( i );
2105         HeapRegionNode hrnShad = id2hrn.get( idShad );
2106         if( hrnShad != null ) {
2107           // flip it
2108           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2109           assert hrnNorm.isWiped();
2110           transferOnto( hrnShad, hrnNorm );
2111         }
2112       }
2113
2114       Integer        idShad   = as.getSummaryShadow();
2115       HeapRegionNode summShad = id2hrn.get( idShad );
2116       if( summShad != null ) {
2117         summNorm = getSummaryNode( as, false );
2118         transferOnto( summShad, summNorm );
2119       }
2120     }
2121
2122
2123     if( writeDebugDOTs ) {
2124       try {
2125         writeGraph( "caller50BeforeGlobalSweep",
2126                     true, false, false, false, true, true );
2127       } catch( IOException e ) {}
2128     }
2129
2130
2131     // 5.
2132     globalSweep();
2133
2134
2135
2136     if( writeDebugDOTs ) {
2137       try {
2138         writeGraph( "caller90AfterTransfer",
2139                     true, false, false, false, true, true );
2140       } catch( IOException e ) {}
2141     }
2142   }
2143
2144
2145
2146   ////////////////////////////////////////////////////
2147   //
2148   //  Abstract garbage collection simply removes
2149   //  heap region nodes that are not mechanically
2150   //  reachable from a root set.  This step is
2151   //  essential for testing node and edge existence
2152   //  predicates efficiently
2153   //
2154   ////////////////////////////////////////////////////
2155   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2156
2157     // calculate a root set, will be different for Java
2158     // version of analysis versus Bamboo version
2159     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2160
2161     // visit every variable in graph while building root
2162     // set, and do iterating on a copy, so we can remove
2163     // dead variables while we're at this
2164     Iterator makeCopyItr = td2vn.entrySet().iterator();
2165     Set      entrysCopy  = new HashSet();
2166     while( makeCopyItr.hasNext() ) {
2167       entrysCopy.add( makeCopyItr.next() );
2168     }
2169
2170     Iterator eItr = entrysCopy.iterator();
2171     while( eItr.hasNext() ) {
2172       Map.Entry      me = (Map.Entry)      eItr.next();
2173       TempDescriptor td = (TempDescriptor) me.getKey();
2174       VariableNode   vn = (VariableNode)   me.getValue();
2175
2176       if( liveSet.contains( td ) ) {
2177         toVisit.add( vn );
2178
2179       } else {
2180         // dead var, remove completely from graph
2181         td2vn.remove( td );
2182         clearRefEdgesFrom( vn, null, null, true );
2183       }
2184     }
2185
2186     // everything visited in a traversal is
2187     // considered abstractly live
2188     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2189
2190     while( !toVisit.isEmpty() ) {
2191       RefSrcNode rsn = toVisit.iterator().next();
2192       toVisit.remove( rsn );
2193       visited.add( rsn );
2194
2195       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2196       while( hrnItr.hasNext() ) {
2197         RefEdge        edge = hrnItr.next();
2198         HeapRegionNode hrn  = edge.getDst();
2199
2200         if( !visited.contains( hrn ) ) {
2201           toVisit.add( hrn );
2202         }
2203       }
2204     }
2205
2206     // get a copy of the set to iterate over because
2207     // we're going to monkey with the graph when we
2208     // identify a garbage node
2209     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2210     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2211     while( hrnItr.hasNext() ) {
2212       hrnAllPrior.add( hrnItr.next() );
2213     }
2214
2215     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2216     while( hrnAllItr.hasNext() ) {
2217       HeapRegionNode hrn = hrnAllItr.next();
2218
2219       if( !visited.contains( hrn ) ) {
2220
2221         // heap region nodes are compared across ReachGraph
2222         // objects by their integer ID, so when discarding
2223         // garbage nodes we must also discard entries in
2224         // the ID -> heap region hashtable.
2225         id2hrn.remove( hrn.getID() );
2226
2227         // RefEdge objects are two-way linked between
2228         // nodes, so when a node is identified as garbage,
2229         // actively clear references to and from it so
2230         // live nodes won't have dangling RefEdge's
2231         wipeOut( hrn, true );
2232
2233         // if we just removed the last node from an allocation
2234         // site, it should be taken out of the ReachGraph's list
2235         AllocSite as = hrn.getAllocSite();
2236         if( !hasNodesOf( as ) ) {
2237           allocSites.remove( as );
2238         }
2239       }
2240     }
2241   }
2242
2243   protected boolean hasNodesOf( AllocSite as ) {
2244     if( id2hrn.containsKey( as.getSummary() ) ) {
2245       return true;
2246     }
2247
2248     for( int i = 0; i < allocationDepth; ++i ) {
2249       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2250         return true;
2251       }
2252     }
2253     return false;
2254   }
2255
2256
2257   ////////////////////////////////////////////////////
2258   //
2259   //  This global sweep is an optional step to prune
2260   //  reachability sets that are not internally
2261   //  consistent with the global graph.  It should be
2262   //  invoked after strong updates or method calls.
2263   //
2264   ////////////////////////////////////////////////////
2265   public void globalSweep() {
2266
2267     // boldB is part of the phase 1 sweep
2268     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
2269       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2270
2271     // visit every heap region to initialize alphaNew and calculate boldB
2272     Iterator itrHrns = id2hrn.entrySet().iterator();
2273     while( itrHrns.hasNext() ) {
2274       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2275       Integer        hrnID = (Integer)        me.getKey();
2276       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2277
2278       // assert that this node and incoming edges have clean alphaNew
2279       // and betaNew sets, respectively
2280       assert rsetEmpty.equals( hrn.getAlphaNew() );
2281
2282       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2283       while( itrRers.hasNext() ) {
2284         RefEdge edge = itrRers.next();
2285         assert rsetEmpty.equals( edge.getBetaNew() );
2286       }
2287
2288       // calculate boldB for this flagged node
2289       if( hrn.isFlagged() ) {
2290
2291         Hashtable<RefEdge, ReachSet> boldB_f =
2292           new Hashtable<RefEdge, ReachSet>();
2293
2294         Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2295
2296         // initial boldB_f constraints
2297         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2298         while( itrRees.hasNext() ) {
2299           RefEdge edge = itrRees.next();
2300
2301           assert !boldB.containsKey( edge );
2302           boldB_f.put( edge, edge.getBeta() );
2303
2304           assert !workSetEdges.contains( edge );
2305           workSetEdges.add( edge );
2306         }
2307
2308         // enforce the boldB_f constraint at edges until we reach a fixed point
2309         while( !workSetEdges.isEmpty() ) {
2310           RefEdge edge = workSetEdges.iterator().next();
2311           workSetEdges.remove( edge );
2312
2313           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2314           while( itrPrime.hasNext() ) {
2315             RefEdge edgePrime = itrPrime.next();
2316
2317             ReachSet prevResult   = boldB_f.get( edgePrime );
2318             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2319                                                             edgePrime.getBeta()
2320                                                             );
2321
2322             if( prevResult == null ||
2323                 Canonical.union( prevResult,
2324                                  intersection ).size() > prevResult.size() ) {
2325
2326               if( prevResult == null ) {
2327                 boldB_f.put( edgePrime,
2328                              Canonical.union( edgePrime.getBeta(),
2329                                               intersection
2330                                               )
2331                              );
2332               } else {
2333                 boldB_f.put( edgePrime,
2334                              Canonical.union( prevResult,
2335                                               intersection
2336                                               )
2337                              );
2338               }
2339               workSetEdges.add( edgePrime );
2340             }
2341           }
2342         }
2343
2344         boldB.put( hrnID, boldB_f );
2345       }
2346     }
2347
2348
2349     // use boldB to prune hrnIDs from alpha states that are impossible
2350     // and propagate the differences backwards across edges
2351     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2352
2353     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2354       new Hashtable<RefEdge, ChangeSet>();
2355
2356
2357     itrHrns = id2hrn.entrySet().iterator();
2358     while( itrHrns.hasNext() ) {
2359       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2360       Integer        hrnID = (Integer)        me.getKey();
2361       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2362
2363       // create the inherent hrnID from a flagged region
2364       // as an exception to removal below
2365       ReachTuple rtException =
2366         ReachTuple.factory( hrnID,
2367                             !hrn.isSingleObject(),
2368                             ReachTuple.ARITY_ONE
2369                             );
2370
2371       ChangeSet cts = ChangeSet.factory();
2372
2373       // mark hrnIDs for removal
2374       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2375       while( stateItr.hasNext() ) {
2376         ReachState stateOld = stateItr.next();
2377
2378         ReachState markedHrnIDs = ReachState.factory();
2379
2380         Iterator<ReachTuple> rtItr = stateOld.iterator();
2381         while( rtItr.hasNext() ) {
2382           ReachTuple rtOld = rtItr.next();
2383
2384           // never remove the inherent hrnID from a flagged region
2385           // because it is trivially satisfied
2386           if( hrn.isFlagged() ) {
2387             if( rtOld == rtException ) {
2388               continue;
2389             }
2390           }
2391
2392           // does boldB_ttOld allow this hrnID?
2393           boolean foundState = false;
2394           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2395           while( incidentEdgeItr.hasNext() ) {
2396             RefEdge incidentEdge = incidentEdgeItr.next();
2397
2398             // if it isn't allowed, mark for removal
2399             Integer idOld = rtOld.getHrnID();
2400             assert id2hrn.containsKey( idOld );
2401             Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
2402             ReachSet boldB_ttOld_incident = B.get( incidentEdge );
2403             if( boldB_ttOld_incident != null &&
2404                 boldB_ttOld_incident.contains( stateOld ) ) {
2405               foundState = true;
2406             }
2407           }
2408
2409           if( !foundState ) {
2410             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
2411           }
2412         }
2413
2414         // if there is nothing marked, just move on
2415         if( markedHrnIDs.isEmpty() ) {
2416           hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2417                                             stateOld
2418                                             )
2419                            );
2420           continue;
2421         }
2422
2423         // remove all marked hrnIDs and establish a change set that should
2424         // propagate backwards over edges from this node
2425         ReachState statePruned = ReachState.factory();
2426         rtItr = stateOld.iterator();
2427         while( rtItr.hasNext() ) {
2428           ReachTuple rtOld = rtItr.next();
2429
2430           if( !markedHrnIDs.containsTuple( rtOld ) ) {
2431             statePruned = Canonical.union( statePruned, rtOld );
2432           }
2433         }
2434         assert !stateOld.equals( statePruned );
2435
2436         hrn.setAlphaNew( Canonical.union( hrn.getAlphaNew(),
2437                                           statePruned
2438                                           )
2439                          );
2440         ChangeTuple ct = ChangeTuple.factory( stateOld,
2441                                               statePruned
2442                                               );
2443         cts = Canonical.union( cts, ct );
2444       }
2445
2446       // throw change tuple set on all incident edges
2447       if( !cts.isEmpty() ) {
2448         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2449         while( incidentEdgeItr.hasNext() ) {
2450           RefEdge incidentEdge = incidentEdgeItr.next();
2451
2452           edgesForPropagation.add( incidentEdge );
2453
2454           if( edgePlannedChanges.get( incidentEdge ) == null ) {
2455             edgePlannedChanges.put( incidentEdge, cts );
2456           } else {
2457             edgePlannedChanges.put(
2458                                    incidentEdge,
2459                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
2460                                                     cts
2461                                                     )
2462                                     );
2463           }
2464         }
2465       }
2466     }
2467
2468     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2469
2470     propagateTokensOverEdges( edgesForPropagation,
2471                               edgePlannedChanges,
2472                               edgesUpdated );
2473
2474     // at the end of the 1st phase reference edges have
2475     // beta, betaNew that correspond to beta and betaR
2476     //
2477     // commit beta<-betaNew, so beta=betaR and betaNew
2478     // will represent the beta' calculation in 2nd phase
2479     //
2480     // commit alpha<-alphaNew because it won't change
2481     HashSet<RefEdge> res = new HashSet<RefEdge>();
2482
2483     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2484     while( nodeItr.hasNext() ) {
2485       HeapRegionNode hrn = nodeItr.next();
2486       hrn.applyAlphaNew();
2487       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
2488       while( itrRes.hasNext() ) {
2489         res.add( itrRes.next() );
2490       }
2491     }
2492
2493
2494     // 2nd phase
2495     Iterator<RefEdge> edgeItr = res.iterator();
2496     while( edgeItr.hasNext() ) {
2497       RefEdge        edge = edgeItr.next();
2498       HeapRegionNode hrn  = edge.getDst();
2499
2500       // commit results of last phase
2501       if( edgesUpdated.contains( edge ) ) {
2502         edge.applyBetaNew();
2503       }
2504
2505       // compute intial condition of 2nd phase
2506       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
2507                                                hrn.getAlpha()
2508                                                )
2509                        );
2510     }
2511
2512     // every edge in the graph is the initial workset
2513     Set<RefEdge> edgeWorkSet = (Set) res.clone();
2514     while( !edgeWorkSet.isEmpty() ) {
2515       RefEdge edgePrime = edgeWorkSet.iterator().next();
2516       edgeWorkSet.remove( edgePrime );
2517
2518       RefSrcNode rsn = edgePrime.getSrc();
2519       if( !(rsn instanceof HeapRegionNode) ) {
2520         continue;
2521       }
2522       HeapRegionNode hrn = (HeapRegionNode) rsn;
2523
2524       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
2525       while( itrEdge.hasNext() ) {
2526         RefEdge edge = itrEdge.next();
2527
2528         ReachSet prevResult = edge.getBetaNew();
2529         assert prevResult != null;
2530
2531         ReachSet intersection =
2532           Canonical.intersection( edge.getBeta(),
2533                                   edgePrime.getBetaNew()
2534                                   );
2535
2536         if( Canonical.union( prevResult,
2537                              intersection
2538                              ).size() > prevResult.size() ) {
2539           edge.setBetaNew(
2540                           Canonical.union( prevResult,
2541                                            intersection
2542                                            )
2543                            );
2544           edgeWorkSet.add( edge );
2545         }
2546       }
2547     }
2548
2549     // commit beta' (beta<-betaNew)
2550     edgeItr = res.iterator();
2551     while( edgeItr.hasNext() ) {
2552       edgeItr.next().applyBetaNew();
2553     }
2554   }
2555
2556
2557
2558   ////////////////////////////////////////////////////
2559   // high-level merge operations
2560   ////////////////////////////////////////////////////
2561   public void merge_sameMethodContext( ReachGraph rg ) {
2562     // when merging two graphs that abstract the heap
2563     // of the same method context, we just call the
2564     // basic merge operation
2565     merge( rg );
2566   }
2567
2568   public void merge_diffMethodContext( ReachGraph rg ) {
2569     // when merging graphs for abstract heaps in
2570     // different method contexts we should:
2571     // 1) age the allocation sites?
2572     merge( rg );
2573   }
2574
2575   ////////////////////////////////////////////////////
2576   // in merge() and equals() methods the suffix A
2577   // represents the passed in graph and the suffix
2578   // B refers to the graph in this object
2579   // Merging means to take the incoming graph A and
2580   // merge it into B, so after the operation graph B
2581   // is the final result.
2582   ////////////////////////////////////////////////////
2583   protected void merge( ReachGraph rg ) {
2584
2585     if( rg == null ) {
2586       return;
2587     }
2588
2589     mergeNodes     ( rg );
2590     mergeRefEdges  ( rg );
2591     mergeAllocSites( rg );
2592   }
2593
2594   protected void mergeNodes( ReachGraph rg ) {
2595
2596     // start with heap region nodes
2597     Set      sA = rg.id2hrn.entrySet();
2598     Iterator iA = sA.iterator();
2599     while( iA.hasNext() ) {
2600       Map.Entry      meA  = (Map.Entry)      iA.next();
2601       Integer        idA  = (Integer)        meA.getKey();
2602       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2603
2604       // if this graph doesn't have a node the
2605       // incoming graph has, allocate it
2606       if( !id2hrn.containsKey( idA ) ) {
2607         HeapRegionNode hrnB = hrnA.copy();
2608         id2hrn.put( idA, hrnB );
2609
2610       } else {
2611         // otherwise this is a node present in both graphs
2612         // so make the new reachability set a union of the
2613         // nodes' reachability sets
2614         HeapRegionNode hrnB = id2hrn.get( idA );
2615         hrnB.setAlpha( Canonical.union( hrnB.getAlpha(),
2616                                         hrnA.getAlpha()
2617                                         )
2618                        );
2619
2620         // if hrnB is already dirty or hrnA is dirty,
2621         // the hrnB should end up dirty: TODO
2622         /*
2623         if( !hrnA.isClean() ) {
2624           hrnB.setIsClean( false );
2625         }
2626         */
2627       }
2628     }
2629
2630     // now add any variable nodes that are in graph B but
2631     // not in A
2632     sA = rg.td2vn.entrySet();
2633     iA = sA.iterator();
2634     while( iA.hasNext() ) {
2635       Map.Entry      meA = (Map.Entry)      iA.next();
2636       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2637       VariableNode   lnA = (VariableNode)   meA.getValue();
2638
2639       // if the variable doesn't exist in B, allocate and add it
2640       VariableNode lnB = getVariableNodeFromTemp( tdA );
2641     }
2642   }
2643
2644   protected void mergeRefEdges( ReachGraph rg ) {
2645
2646     // between heap regions
2647     Set      sA = rg.id2hrn.entrySet();
2648     Iterator iA = sA.iterator();
2649     while( iA.hasNext() ) {
2650       Map.Entry      meA  = (Map.Entry)      iA.next();
2651       Integer        idA  = (Integer)        meA.getKey();
2652       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2653
2654       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2655       while( heapRegionsItrA.hasNext() ) {
2656         RefEdge        edgeA     = heapRegionsItrA.next();
2657         HeapRegionNode hrnChildA = edgeA.getDst();
2658         Integer        idChildA  = hrnChildA.getID();
2659
2660         // at this point we know an edge in graph A exists
2661         // idA -> idChildA, does this exist in B?
2662         assert id2hrn.containsKey( idA );
2663         HeapRegionNode hrnB        = id2hrn.get( idA );
2664         RefEdge        edgeToMerge = null;
2665
2666         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2667         while( heapRegionsItrB.hasNext() &&
2668                edgeToMerge == null          ) {
2669
2670           RefEdge        edgeB     = heapRegionsItrB.next();
2671           HeapRegionNode hrnChildB = edgeB.getDst();
2672           Integer        idChildB  = hrnChildB.getID();
2673
2674           // don't use the RefEdge.equals() here because
2675           // we're talking about existence between graphs,
2676           // not intragraph equal
2677           if( idChildB.equals( idChildA ) &&
2678               edgeB.typeAndFieldEquals( edgeA ) ) {
2679
2680             edgeToMerge = edgeB;
2681           }
2682         }
2683
2684         // if the edge from A was not found in B,
2685         // add it to B.
2686         if( edgeToMerge == null ) {
2687           assert id2hrn.containsKey( idChildA );
2688           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2689           edgeToMerge = edgeA.copy();
2690           edgeToMerge.setSrc( hrnB );
2691           edgeToMerge.setDst( hrnChildB );
2692           addRefEdge( hrnB, hrnChildB, edgeToMerge );
2693         }
2694         // otherwise, the edge already existed in both graphs
2695         // so merge their reachability sets
2696         else {
2697           // just replace this beta set with the union
2698           assert edgeToMerge != null;
2699           edgeToMerge.setBeta(
2700                               Canonical.union( edgeToMerge.getBeta(),
2701                                                edgeA.getBeta()
2702                                                )
2703                               );
2704           // TODO: what?
2705           /*
2706           if( !edgeA.isClean() ) {
2707             edgeToMerge.setIsClean( false );
2708           }
2709           */
2710         }
2711       }
2712     }
2713
2714     // and then again from variable nodes
2715     sA = rg.td2vn.entrySet();
2716     iA = sA.iterator();
2717     while( iA.hasNext() ) {
2718       Map.Entry      meA = (Map.Entry)      iA.next();
2719       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2720       VariableNode   vnA = (VariableNode)   meA.getValue();
2721
2722       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
2723       while( heapRegionsItrA.hasNext() ) {
2724         RefEdge        edgeA     = heapRegionsItrA.next();
2725         HeapRegionNode hrnChildA = edgeA.getDst();
2726         Integer        idChildA  = hrnChildA.getID();
2727
2728         // at this point we know an edge in graph A exists
2729         // tdA -> idChildA, does this exist in B?
2730         assert td2vn.containsKey( tdA );
2731         VariableNode vnB         = td2vn.get( tdA );
2732         RefEdge      edgeToMerge = null;
2733
2734         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
2735         while( heapRegionsItrB.hasNext() &&
2736                edgeToMerge == null          ) {
2737
2738           RefEdge        edgeB     = heapRegionsItrB.next();
2739           HeapRegionNode hrnChildB = edgeB.getDst();
2740           Integer        idChildB  = hrnChildB.getID();
2741
2742           // don't use the RefEdge.equals() here because
2743           // we're talking about existence between graphs
2744           if( idChildB.equals( idChildA ) &&
2745               edgeB.typeAndFieldEquals( edgeA ) ) {
2746
2747             edgeToMerge = edgeB;
2748           }
2749         }
2750
2751         // if the edge from A was not found in B,
2752         // add it to B.
2753         if( edgeToMerge == null ) {
2754           assert id2hrn.containsKey( idChildA );
2755           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
2756           edgeToMerge = edgeA.copy();
2757           edgeToMerge.setSrc( vnB );
2758           edgeToMerge.setDst( hrnChildB );
2759           addRefEdge( vnB, hrnChildB, edgeToMerge );
2760         }
2761         // otherwise, the edge already existed in both graphs
2762         // so merge their reachability sets
2763         else {
2764           // just replace this beta set with the union
2765           edgeToMerge.setBeta( Canonical.union( edgeToMerge.getBeta(),
2766                                                 edgeA.getBeta()
2767                                                 )
2768                                );
2769           // TODO: what?
2770           /*
2771           if( !edgeA.isClean() ) {
2772             edgeToMerge.setIsClean( false );
2773           }
2774           */
2775         }
2776       }
2777     }
2778   }
2779
2780   protected void mergeAllocSites( ReachGraph rg ) {
2781     allocSites.addAll( rg.allocSites );
2782   }
2783
2784
2785   // it is necessary in the equals() member functions
2786   // to "check both ways" when comparing the data
2787   // structures of two graphs.  For instance, if all
2788   // edges between heap region nodes in graph A are
2789   // present and equal in graph B it is not sufficient
2790   // to say the graphs are equal.  Consider that there
2791   // may be edges in graph B that are not in graph A.
2792   // the only way to know that all edges in both graphs
2793   // are equally present is to iterate over both data
2794   // structures and compare against the other graph.
2795   public boolean equals( ReachGraph rg ) {
2796
2797     if( rg == null ) {
2798       return false;
2799     }
2800
2801     if( !areHeapRegionNodesEqual( rg ) ) {
2802       return false;
2803     }
2804
2805     if( !areVariableNodesEqual( rg ) ) {
2806       return false;
2807     }
2808
2809     if( !areRefEdgesEqual( rg ) ) {
2810       return false;
2811     }
2812
2813     // if everything is equal up to this point,
2814     // assert that allocSites is also equal--
2815     // this data is redundant but kept for efficiency
2816     assert allocSites.equals( rg.allocSites );
2817
2818     return true;
2819   }
2820
2821
2822   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
2823
2824     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
2825       return false;
2826     }
2827
2828     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
2829       return false;
2830     }
2831
2832     return true;
2833   }
2834
2835   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
2836                                                         ReachGraph rgB ) {
2837     Set      sA = rgA.id2hrn.entrySet();
2838     Iterator iA = sA.iterator();
2839     while( iA.hasNext() ) {
2840       Map.Entry      meA  = (Map.Entry)      iA.next();
2841       Integer        idA  = (Integer)        meA.getKey();
2842       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2843
2844       if( !rgB.id2hrn.containsKey( idA ) ) {
2845         return false;
2846       }
2847
2848       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2849       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
2850         return false;
2851       }
2852     }
2853
2854     return true;
2855   }
2856
2857
2858   protected boolean areVariableNodesEqual( ReachGraph rg ) {
2859
2860     if( !areallVNinAalsoinBandequal( this, rg ) ) {
2861       return false;
2862     }
2863
2864     if( !areallVNinAalsoinBandequal( rg, this ) ) {
2865       return false;
2866     }
2867
2868     return true;
2869   }
2870
2871   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2872                                                        ReachGraph rgB ) {
2873     Set      sA = rgA.td2vn.entrySet();
2874     Iterator iA = sA.iterator();
2875     while( iA.hasNext() ) {
2876       Map.Entry      meA = (Map.Entry)      iA.next();
2877       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2878
2879       if( !rgB.td2vn.containsKey( tdA ) ) {
2880         return false;
2881       }
2882     }
2883
2884     return true;
2885   }
2886
2887
2888   protected boolean areRefEdgesEqual( ReachGraph rg ) {
2889     if( !areallREinAandBequal( this, rg ) ) {
2890       return false;
2891     }
2892
2893     return true;
2894   }
2895
2896   static protected boolean areallREinAandBequal( ReachGraph rgA,
2897                                                  ReachGraph rgB ) {
2898
2899     // check all the heap region->heap region edges
2900     Set      sA = rgA.id2hrn.entrySet();
2901     Iterator iA = sA.iterator();
2902     while( iA.hasNext() ) {
2903       Map.Entry      meA  = (Map.Entry)      iA.next();
2904       Integer        idA  = (Integer)        meA.getKey();
2905       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2906
2907       // we should have already checked that the same
2908       // heap regions exist in both graphs
2909       assert rgB.id2hrn.containsKey( idA );
2910
2911       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
2912         return false;
2913       }
2914
2915       // then check every edge in B for presence in A, starting
2916       // from the same parent HeapRegionNode
2917       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2918
2919       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
2920         return false;
2921       }
2922     }
2923
2924     // then check all the variable->heap region edges
2925     sA = rgA.td2vn.entrySet();
2926     iA = sA.iterator();
2927     while( iA.hasNext() ) {
2928       Map.Entry      meA = (Map.Entry)      iA.next();
2929       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2930       VariableNode   vnA = (VariableNode)   meA.getValue();
2931
2932       // we should have already checked that the same
2933       // label nodes exist in both graphs
2934       assert rgB.td2vn.containsKey( tdA );
2935
2936       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
2937         return false;
2938       }
2939
2940       // then check every edge in B for presence in A, starting
2941       // from the same parent VariableNode
2942       VariableNode vnB = rgB.td2vn.get( tdA );
2943
2944       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
2945         return false;
2946       }
2947     }
2948
2949     return true;
2950   }
2951
2952
2953   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
2954                                                   RefSrcNode rnA,
2955                                                   ReachGraph rgB ) {
2956
2957     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
2958     while( itrA.hasNext() ) {
2959       RefEdge        edgeA     = itrA.next();
2960       HeapRegionNode hrnChildA = edgeA.getDst();
2961       Integer        idChildA  = hrnChildA.getID();
2962
2963       assert rgB.id2hrn.containsKey( idChildA );
2964
2965       // at this point we know an edge in graph A exists
2966       // rnA -> idChildA, does this exact edge exist in B?
2967       boolean edgeFound = false;
2968
2969       RefSrcNode rnB = null;
2970       if( rnA instanceof HeapRegionNode ) {
2971         HeapRegionNode hrnA = (HeapRegionNode) rnA;
2972         rnB = rgB.id2hrn.get( hrnA.getID() );
2973       } else {
2974         VariableNode vnA = (VariableNode) rnA;
2975         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
2976       }
2977
2978       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
2979       while( itrB.hasNext() ) {
2980         RefEdge        edgeB     = itrB.next();
2981         HeapRegionNode hrnChildB = edgeB.getDst();
2982         Integer        idChildB  = hrnChildB.getID();
2983
2984         if( idChildA.equals( idChildB ) &&
2985             edgeA.typeAndFieldEquals( edgeB ) ) {
2986
2987           // there is an edge in the right place with the right field,
2988           // but do they have the same attributes?
2989           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
2990               edgeA.equalsPreds( edgeB )
2991               ) {
2992             edgeFound = true;
2993           }
2994         }
2995       }
2996
2997       if( !edgeFound ) {
2998         return false;
2999       }
3000     }
3001
3002     return true;
3003   }
3004
3005
3006
3007   // this analysis no longer has the "match anything"
3008   // type which was represented by null
3009   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3010                                              TypeDescriptor td2 ) {
3011     assert td1 != null;
3012     assert td2 != null;
3013
3014     if( td1.isNull() ) {
3015       return td2;
3016     }
3017     if( td2.isNull() ) {
3018       return td1;
3019     }
3020     return typeUtil.mostSpecific( td1, td2 );
3021   }
3022
3023   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3024                                              TypeDescriptor td2,
3025                                              TypeDescriptor td3 ) {
3026
3027     return mostSpecificType( td1,
3028                              mostSpecificType( td2, td3 )
3029                              );
3030   }
3031
3032   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3033                                              TypeDescriptor td2,
3034                                              TypeDescriptor td3,
3035                                              TypeDescriptor td4 ) {
3036
3037     return mostSpecificType( mostSpecificType( td1, td2 ),
3038                              mostSpecificType( td3, td4 )
3039                              );
3040   }
3041
3042   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3043                                     TypeDescriptor possibleChild ) {
3044     assert possibleSuper != null;
3045     assert possibleChild != null;
3046
3047     if( possibleSuper.isNull() ||
3048         possibleChild.isNull() ) {
3049       return true;
3050     }
3051
3052     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3053   }
3054
3055
3056   protected boolean hasMatchingField( HeapRegionNode src,
3057                                       RefEdge        edge ) {
3058
3059     TypeDescriptor tdSrc = src.getType();
3060     assert tdSrc != null;
3061
3062     if( tdSrc.isArray() ) {
3063       TypeDescriptor td = edge.getType();
3064       assert td != null;
3065
3066       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3067       assert tdSrcDeref != null;
3068
3069       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3070         return false;
3071       }
3072
3073       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3074     }
3075
3076     // if it's not a class, it doesn't have any fields to match
3077     if( !tdSrc.isClass() ) {
3078       return false;
3079     }
3080
3081     ClassDescriptor cd = tdSrc.getClassDesc();
3082     while( cd != null ) {
3083       Iterator fieldItr = cd.getFields();
3084
3085       while( fieldItr.hasNext() ) {
3086         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3087
3088         if( fd.getType().equals( edge.getType() ) &&
3089             fd.getSymbol().equals( edge.getField() ) ) {
3090           return true;
3091         }
3092       }
3093
3094       cd = cd.getSuperDesc();
3095     }
3096
3097     // otherwise it is a class with fields
3098     // but we didn't find a match
3099     return false;
3100   }
3101
3102   protected boolean hasMatchingType( RefEdge        edge,
3103                                      HeapRegionNode dst  ) {
3104
3105     // if the region has no type, matches everything
3106     TypeDescriptor tdDst = dst.getType();
3107     assert tdDst != null;
3108
3109     // if the type is not a class or an array, don't
3110     // match because primitives are copied, no aliases
3111     ClassDescriptor cdDst = tdDst.getClassDesc();
3112     if( cdDst == null && !tdDst.isArray() ) {
3113       return false;
3114     }
3115
3116     // if the edge type is null, it matches everything
3117     TypeDescriptor tdEdge = edge.getType();
3118     assert tdEdge != null;
3119
3120     return typeUtil.isSuperorType( tdEdge, tdDst );
3121   }
3122
3123
3124
3125   public void writeGraph( String  graphName,
3126                           boolean writeLabels,
3127                           boolean labelSelect,
3128                           boolean pruneGarbage,
3129                           boolean writeReferencers,
3130                           boolean hideSubsetReachability,
3131                           boolean hideEdgeTaints
3132                           ) throws java.io.IOException {
3133     writeGraph( graphName,
3134                 writeLabels,
3135                 labelSelect,
3136                 pruneGarbage,
3137                 writeReferencers,
3138                 hideSubsetReachability,
3139                 hideEdgeTaints,
3140                 null );
3141   }
3142
3143   public void writeGraph( String       graphName,
3144                           boolean      writeLabels,
3145                           boolean      labelSelect,
3146                           boolean      pruneGarbage,
3147                           boolean      writeReferencers,
3148                           boolean      hideSubsetReachability,
3149                           boolean      hideEdgeTaints,
3150                           Set<Integer> callerNodeIDsCopiedToCallee
3151                           ) throws java.io.IOException {
3152
3153     // remove all non-word characters from the graph name so
3154     // the filename and identifier in dot don't cause errors
3155     graphName = graphName.replaceAll( "[\\W]", "" );
3156
3157     BufferedWriter bw =
3158       new BufferedWriter( new FileWriter( graphName+".dot" ) );
3159
3160     bw.write( "digraph "+graphName+" {\n" );
3161
3162
3163     // this is an optional step to form the callee-reachable
3164     // "cut-out" into a DOT cluster for visualization
3165     if( callerNodeIDsCopiedToCallee != null ) {
3166
3167       bw.write( "  subgraph cluster0 {\n" );
3168       bw.write( "    color=blue;\n" );
3169
3170       Iterator i = id2hrn.entrySet().iterator();
3171       while( i.hasNext() ) {
3172         Map.Entry      me  = (Map.Entry)      i.next();
3173         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3174
3175         if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3176           bw.write( "    "+hrn.toString()+
3177                     hrn.toStringDOT( hideSubsetReachability )+
3178                     ";\n" );
3179
3180         }
3181       }
3182
3183       bw.write( "  }\n" );
3184     }
3185
3186
3187     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3188
3189     // then visit every heap region node
3190     Iterator i = id2hrn.entrySet().iterator();
3191     while( i.hasNext() ) {
3192       Map.Entry      me  = (Map.Entry)      i.next();
3193       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3194
3195       // only visit nodes worth writing out--for instance
3196       // not every node at an allocation is referenced
3197       // (think of it as garbage-collected), etc.
3198       if( !pruneGarbage                              ||
3199           (hrn.isFlagged() && hrn.getID() > 0)       ||
3200           hrn.getDescription().startsWith( "param" ) ||
3201           hrn.isOutOfContext()
3202           ) {
3203
3204         if( !visited.contains( hrn ) ) {
3205           traverseHeapRegionNodes( hrn,
3206                                    bw,
3207                                    null,
3208                                    visited,
3209                                    writeReferencers,
3210                                    hideSubsetReachability,
3211                                    hideEdgeTaints,
3212                                    callerNodeIDsCopiedToCallee );
3213         }
3214       }
3215     }
3216
3217     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
3218
3219
3220     // then visit every label node, useful for debugging
3221     if( writeLabels ) {
3222       i = td2vn.entrySet().iterator();
3223       while( i.hasNext() ) {
3224         Map.Entry    me = (Map.Entry)    i.next();
3225         VariableNode vn = (VariableNode) me.getValue();
3226
3227         if( labelSelect ) {
3228           String labelStr = vn.getTempDescriptorString();
3229           if( labelStr.startsWith("___temp") ||
3230               labelStr.startsWith("___dst") ||
3231               labelStr.startsWith("___srctmp") ||
3232               labelStr.startsWith("___neverused")
3233               ) {
3234             continue;
3235           }
3236         }
3237
3238         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3239         while( heapRegionsItr.hasNext() ) {
3240           RefEdge        edge = heapRegionsItr.next();
3241           HeapRegionNode hrn  = edge.getDst();
3242
3243           if( pruneGarbage && !visited.contains( hrn ) ) {
3244             traverseHeapRegionNodes( hrn,
3245                                      bw,
3246                                      null,
3247                                      visited,
3248                                      writeReferencers,
3249                                      hideSubsetReachability,
3250                                      hideEdgeTaints,
3251                                      callerNodeIDsCopiedToCallee );
3252           }
3253
3254           bw.write( "  "+vn.toString()+
3255                     " -> "+hrn.toString()+
3256                     edge.toStringDOT( hideSubsetReachability, "" )+
3257                     ";\n" );
3258         }
3259       }
3260     }
3261
3262     bw.write( "}\n" );
3263     bw.close();
3264   }
3265
3266   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
3267                                           BufferedWriter      bw,
3268                                           TempDescriptor      td,
3269                                           Set<HeapRegionNode> visited,
3270                                           boolean             writeReferencers,
3271                                           boolean             hideSubsetReachability,
3272                                           boolean             hideEdgeTaints,
3273                                           Set<Integer>        callerNodeIDsCopiedToCallee
3274                                           ) throws java.io.IOException {
3275
3276     if( visited.contains( hrn ) ) {
3277       return;
3278     }
3279     visited.add( hrn );
3280
3281     // if we're drawing the callee-view subgraph, only
3282     // write out the node info if it hasn't already been
3283     // written
3284     if( callerNodeIDsCopiedToCallee == null ||
3285         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3286         ) {
3287       bw.write( "  "+hrn.toString()+
3288                 hrn.toStringDOT( hideSubsetReachability )+
3289                 ";\n" );
3290     }
3291
3292     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3293     while( childRegionsItr.hasNext() ) {
3294       RefEdge        edge     = childRegionsItr.next();
3295       HeapRegionNode hrnChild = edge.getDst();
3296
3297       if( callerNodeIDsCopiedToCallee != null &&
3298           (edge.getSrc() instanceof HeapRegionNode) ) {
3299         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3300         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
3301             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3302             ) {
3303           bw.write( "  "+hrn.toString()+
3304                     " -> "+hrnChild.toString()+
3305                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3306                     ";\n");
3307         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
3308                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3309                    ) {
3310           bw.write( "  "+hrn.toString()+
3311                     " -> "+hrnChild.toString()+
3312                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3313                     ";\n");
3314         } else {
3315           bw.write( "  "+hrn.toString()+
3316                     " -> "+hrnChild.toString()+
3317                     edge.toStringDOT( hideSubsetReachability, "" )+
3318                     ";\n");
3319         }
3320       } else {
3321         bw.write( "  "+hrn.toString()+
3322                   " -> "+hrnChild.toString()+
3323                   edge.toStringDOT( hideSubsetReachability, "" )+
3324                   ";\n");
3325       }
3326
3327       traverseHeapRegionNodes( hrnChild,
3328                                bw,
3329                                td,
3330                                visited,
3331                                writeReferencers,
3332                                hideSubsetReachability,
3333                                hideEdgeTaints,
3334                                callerNodeIDsCopiedToCallee );
3335     }
3336   }
3337
3338 }