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        = new ReachState().makeCanonical();
  20   protected static final ReachSet   rsetEmpty          = new ReachSet().makeCanonical();
  21   protected static final ReachSet   rsetWithEmptyState = new ReachSet( rstateEmpty ).makeCanonical();
  22
  23   // predicate constants
  24   protected static final ExistPredTrue predTrue   = new ExistPredTrue();
  25   protected static final ExistPredSet  predsEmpty = new ExistPredSet().makeCanonical();
  26   protected static final ExistPredSet  predsTrue  = new ExistPredSet( predTrue ).makeCanonical();
  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 = new ReachSet(
 106                                 new ReachTuple( id,
 107                                                 !isSingleObject,
 108                                                 ReachTuple.ARITY_ONE
 109                                                 ).makeCanonical()
 110                                 ).makeCanonical();
 111       } else {
 112         inherent = rsetWithEmptyState;
 113       }
 114     }
 115
 116     if( alpha == null ) {
 117       alpha = inherent;
 118     }
 119
 120     if( preds == null ) {
 121       // TODO: do this right?  For out-of-context nodes?
 122       preds = new ExistPredSet().makeCanonical();
 123     }
 124
 125     HeapRegionNode hrn = new HeapRegionNode( id,
 126                                              isSingleObject,
 127                                              markForAnalysis,
 128                                              isNewSummary,
 129                                              isOutOfContext,
 130                                              typeToUse,
 131                                              allocSite,
 132                                              inherent,
 133                                              alpha,
 134                                              preds,
 135                                              description );
 136     id2hrn.put( id, hrn );
 137     return hrn;
 138   }
 139
 140
 141
 142   ////////////////////////////////////////////////
 143   //
 144   //  Low-level referencee and referencer methods
 145   //
 146   //  These methods provide the lowest level for
 147   //  creating references between reachability nodes
 148   //  and handling the details of maintaining both
 149   //  list of referencers and referencees.
 150   //
 151   ////////////////////////////////////////////////
 152   protected void addRefEdge( RefSrcNode     referencer,
 153                              HeapRegionNode referencee,
 154                              RefEdge        edge ) {
 155     assert referencer != null;
 156     assert referencee != null;
 157     assert edge       != null;
 158     assert edge.getSrc() == referencer;
 159     assert edge.getDst() == referencee;
 160
 161     referencer.addReferencee( edge );
 162     referencee.addReferencer( edge );
 163   }
 164
 165   protected void removeRefEdge( RefEdge e ) {
 166     removeRefEdge( e.getSrc(),
 167                    e.getDst(),
 168                    e.getType(),
 169                    e.getField() );
 170   }
 171
 172   protected void removeRefEdge( RefSrcNode     referencer,
 173                                 HeapRegionNode referencee,
 174                                 TypeDescriptor type,
 175                                 String         field ) {
 176     assert referencer != null;
 177     assert referencee != null;
 178
 179     RefEdge edge = referencer.getReferenceTo( referencee,
 180                                               type,
 181                                               field );
 182     assert edge != null;
 183     assert edge == referencee.getReferenceFrom( referencer,
 184                                                 type,
 185                                                 field );
 186
 187     referencer.removeReferencee( edge );
 188     referencee.removeReferencer( edge );
 189   }
 190
 191   protected void clearRefEdgesFrom( RefSrcNode     referencer,
 192                                     TypeDescriptor type,
 193                                     String         field,
 194                                     boolean        removeAll ) {
 195     assert referencer != null;
 196
 197     // get a copy of the set to iterate over, otherwise
 198     // we will be trying to take apart the set as we
 199     // are iterating over it, which won't work
 200     Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
 201     while( i.hasNext() ) {
 202       RefEdge edge = i.next();
 203
 204       if( removeAll                                          ||
 205           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 206         ){
 207
 208         HeapRegionNode referencee = edge.getDst();
 209
 210         removeRefEdge( referencer,
 211                        referencee,
 212                        edge.getType(),
 213                        edge.getField() );
 214       }
 215     }
 216   }
 217
 218   protected void clearRefEdgesTo( HeapRegionNode referencee,
 219                                   TypeDescriptor type,
 220                                   String         field,
 221                                   boolean        removeAll ) {
 222     assert referencee != null;
 223
 224     // get a copy of the set to iterate over, otherwise
 225     // we will be trying to take apart the set as we
 226     // are iterating over it, which won't work
 227     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 228     while( i.hasNext() ) {
 229       RefEdge edge = i.next();
 230
 231       if( removeAll                                          ||
 232           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 233         ){
 234
 235         RefSrcNode referencer = edge.getSrc();
 236
 237         removeRefEdge( referencer,
 238                        referencee,
 239                        edge.getType(),
 240                        edge.getField() );
 241       }
 242     }
 243   }
 244
 245
 246   ////////////////////////////////////////////////////
 247   //
 248   //  Assignment Operation Methods
 249   //
 250   //  These methods are high-level operations for
 251   //  modeling program assignment statements using
 252   //  the low-level reference create/remove methods
 253   //  above.
 254   //
 255   ////////////////////////////////////////////////////
 256
 257   public void assignTempXEqualToTempY( TempDescriptor x,
 258                                        TempDescriptor y ) {
 259     assignTempXEqualToCastedTempY( x, y, null );
 260   }
 261
 262   public void assignTempXEqualToCastedTempY( TempDescriptor x,
 263                                              TempDescriptor y,
 264                                              TypeDescriptor tdCast ) {
 265
 266     VariableNode lnX = getVariableNodeFromTemp( x );
 267     VariableNode lnY = getVariableNodeFromTemp( y );
 268
 269     clearRefEdgesFrom( lnX, null, null, true );
 270
 271     // note it is possible that the types of temps in the
 272     // flat node to analyze will reveal that some typed
 273     // edges in the reachability graph are impossible
 274     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 275
 276     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 277     while( itrYhrn.hasNext() ) {
 278       RefEdge        edgeY      = itrYhrn.next();
 279       HeapRegionNode referencee = edgeY.getDst();
 280       RefEdge        edgeNew    = edgeY.copy();
 281
 282       if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
 283         impossibleEdges.add( edgeY );
 284         continue;
 285       }
 286
 287       edgeNew.setSrc( lnX );
 288
 289       if( tdCast == null ) {
 290         edgeNew.setType( mostSpecificType( y.getType(),
 291                                            edgeY.getType(),
 292                                            referencee.getType()
 293                                            )
 294                          );
 295       } else {
 296         edgeNew.setType( mostSpecificType( y.getType(),
 297                                            edgeY.getType(),
 298                                            referencee.getType(),
 299                                            tdCast
 300                                            )
 301                          );
 302       }
 303
 304       edgeNew.setField( null );
 305
 306       addRefEdge( lnX, referencee, edgeNew );
 307     }
 308
 309     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 310     while( itrImp.hasNext() ) {
 311       RefEdge edgeImp = itrImp.next();
 312       removeRefEdge( edgeImp );
 313     }
 314   }
 315
 316
 317   public void assignTempXEqualToTempYFieldF( TempDescriptor  x,
 318                                              TempDescriptor  y,
 319                                              FieldDescriptor f ) {
 320     VariableNode lnX = getVariableNodeFromTemp( x );
 321     VariableNode lnY = getVariableNodeFromTemp( y );
 322
 323     clearRefEdgesFrom( lnX, null, null, true );
 324
 325     // note it is possible that the types of temps in the
 326     // flat node to analyze will reveal that some typed
 327     // edges in the reachability graph are impossible
 328     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 329
 330     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 331     while( itrYhrn.hasNext() ) {
 332       RefEdge        edgeY = itrYhrn.next();
 333       HeapRegionNode hrnY  = edgeY.getDst();
 334       ReachSet       betaY = edgeY.getBeta();
 335
 336       Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 337       while( itrHrnFhrn.hasNext() ) {
 338         RefEdge        edgeHrn = itrHrnFhrn.next();
 339         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 340         ReachSet       betaHrn = edgeHrn.getBeta();
 341
 342         // prune edges that are not a matching field
 343         if( edgeHrn.getType() != null &&
 344             !edgeHrn.getField().equals( f.getSymbol() )
 345             ) {
 346           continue;
 347         }
 348
 349         // check for impossible edges
 350         if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
 351           impossibleEdges.add( edgeHrn );
 352           continue;
 353         }
 354
 355         TypeDescriptor tdNewEdge =
 356           mostSpecificType( edgeHrn.getType(),
 357                             hrnHrn.getType()
 358                             );
 359
 360         RefEdge edgeNew = new RefEdge( lnX,
 361                                        hrnHrn,
 362                                        tdNewEdge,
 363                                        null,
 364                                        betaY.intersection( betaHrn ),
 365                                        predsTrue
 366                                        );
 367
 368         addRefEdge( lnX, hrnHrn, edgeNew );
 369       }
 370     }
 371
 372     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 373     while( itrImp.hasNext() ) {
 374       RefEdge edgeImp = itrImp.next();
 375       removeRefEdge( edgeImp );
 376     }
 377
 378     // anytime you might remove edges between heap regions
 379     // you must global sweep to clean up broken reachability
 380     if( !impossibleEdges.isEmpty() ) {
 381       if( !DISABLE_GLOBAL_SWEEP ) {
 382         globalSweep();
 383       }
 384     }
 385   }
 386
 387
 388   public void assignTempXFieldFEqualToTempY( TempDescriptor  x,
 389                                              FieldDescriptor f,
 390                                              TempDescriptor  y ) {
 391
 392     VariableNode lnX = getVariableNodeFromTemp( x );
 393     VariableNode lnY = getVariableNodeFromTemp( y );
 394
 395     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 396     HashSet<RefEdge>        edgesWithNewBeta  = new HashSet<RefEdge>();
 397
 398     // note it is possible that the types of temps in the
 399     // flat node to analyze will reveal that some typed
 400     // edges in the reachability graph are impossible
 401     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 402
 403     // first look for possible strong updates and remove those edges
 404     boolean strongUpdate = false;
 405
 406     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 407     while( itrXhrn.hasNext() ) {
 408       RefEdge        edgeX = itrXhrn.next();
 409       HeapRegionNode hrnX  = edgeX.getDst();
 410
 411       // we can do a strong update here if one of two cases holds
 412       if( f != null &&
 413           f != DisjointAnalysis.getArrayField( f.getType() ) &&
 414           (   (hrnX.getNumReferencers()                         == 1) || // case 1
 415               (hrnX.isSingleObject() && lnX.getNumReferencees() == 1)    // case 2
 416               )
 417           ) {
 418         if( !DISABLE_STRONG_UPDATES ) {
 419           strongUpdate = true;
 420           clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
 421         }
 422       }
 423     }
 424
 425     // then do all token propagation
 426     itrXhrn = lnX.iteratorToReferencees();
 427     while( itrXhrn.hasNext() ) {
 428       RefEdge        edgeX = itrXhrn.next();
 429       HeapRegionNode hrnX  = edgeX.getDst();
 430       ReachSet       betaX = edgeX.getBeta();
 431       ReachSet       R     = hrnX.getAlpha().intersection( edgeX.getBeta() );
 432
 433       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 434       while( itrYhrn.hasNext() ) {
 435         RefEdge        edgeY = itrYhrn.next();
 436         HeapRegionNode hrnY  = edgeY.getDst();
 437         ReachSet       O     = edgeY.getBeta();
 438
 439         // check for impossible edges
 440         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 441           impossibleEdges.add( edgeY );
 442           continue;
 443         }
 444
 445         // propagate tokens over nodes starting from hrnSrc, and it will
 446         // take care of propagating back up edges from any touched nodes
 447         ChangeSet Cy = O.unionUpArityToChangeSet( R );
 448         propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
 449
 450         // then propagate back just up the edges from hrn
 451         ChangeSet Cx = R.unionUpArityToChangeSet(O);
 452         HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
 453
 454         Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
 455           new Hashtable<RefEdge, ChangeSet>();
 456
 457         Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
 458         while( referItr.hasNext() ) {
 459           RefEdge edgeUpstream = referItr.next();
 460           todoEdges.add( edgeUpstream );
 461           edgePlannedChanges.put( edgeUpstream, Cx );
 462         }
 463
 464         propagateTokensOverEdges( todoEdges,
 465                                   edgePlannedChanges,
 466                                   edgesWithNewBeta );
 467       }
 468     }
 469
 470
 471     // apply the updates to reachability
 472     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 473     while( nodeItr.hasNext() ) {
 474       nodeItr.next().applyAlphaNew();
 475     }
 476
 477     Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
 478     while( edgeItr.hasNext() ) {
 479       edgeItr.next().applyBetaNew();
 480     }
 481
 482
 483     // then go back through and add the new edges
 484     itrXhrn = lnX.iteratorToReferencees();
 485     while( itrXhrn.hasNext() ) {
 486       RefEdge        edgeX = itrXhrn.next();
 487       HeapRegionNode hrnX  = edgeX.getDst();
 488
 489       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 490       while( itrYhrn.hasNext() ) {
 491         RefEdge        edgeY = itrYhrn.next();
 492         HeapRegionNode hrnY  = edgeY.getDst();
 493
 494         // skip impossible edges here, we already marked them
 495         // when computing reachability propagations above
 496         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 497           continue;
 498         }
 499
 500         // prepare the new reference edge hrnX.f -> hrnY
 501         TypeDescriptor tdNewEdge =
 502           mostSpecificType( y.getType(),
 503                             edgeY.getType(),
 504                             hrnY.getType()
 505                             );
 506
 507         RefEdge edgeNew = new RefEdge( hrnX,
 508                                        hrnY,
 509                                        tdNewEdge,
 510                                        f.getSymbol(),
 511                                        edgeY.getBeta().pruneBy( hrnX.getAlpha() ),
 512                                        predsTrue
 513                                        );
 514
 515         // look to see if an edge with same field exists
 516         // and merge with it, otherwise just add the edge
 517         RefEdge edgeExisting = hrnX.getReferenceTo( hrnY,
 518                                                     tdNewEdge,
 519                                                     f.getSymbol() );
 520
 521         if( edgeExisting != null ) {
 522           edgeExisting.setBeta(
 523                                edgeExisting.getBeta().union( edgeNew.getBeta() )
 524                                );
 525           edgeExisting.setPreds(
 526                                 edgeExisting.getPreds().join( edgeNew.getPreds() )
 527                                 );
 528
 529         } else {
 530           addRefEdge( hrnX, hrnY, edgeNew );
 531         }
 532       }
 533     }
 534
 535     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 536     while( itrImp.hasNext() ) {
 537       RefEdge edgeImp = itrImp.next();
 538       removeRefEdge( edgeImp );
 539     }
 540
 541     // if there was a strong update, make sure to improve
 542     // reachability with a global sweep
 543     if( strongUpdate || !impossibleEdges.isEmpty() ) {
 544       if( !DISABLE_GLOBAL_SWEEP ) {
 545         globalSweep();
 546       }
 547     }
 548   }
 549
 550
 551   public void assignReturnEqualToTemp( TempDescriptor x ) {
 552
 553     VariableNode lnR = getVariableNodeFromTemp( tdReturn );
 554     VariableNode lnX = getVariableNodeFromTemp( x );
 555
 556     clearRefEdgesFrom( lnR, null, null, true );
 557
 558     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 559     while( itrXhrn.hasNext() ) {
 560       RefEdge        edgeX      = itrXhrn.next();
 561       HeapRegionNode referencee = edgeX.getDst();
 562       RefEdge        edgeNew    = edgeX.copy();
 563       edgeNew.setSrc( lnR );
 564
 565       addRefEdge( lnR, referencee, edgeNew );
 566     }
 567   }
 568
 569
 570   public void assignTempEqualToNewAlloc( TempDescriptor x,
 571                                          AllocSite      as ) {
 572     assert x  != null;
 573     assert as != null;
 574
 575     age( as );
 576
 577     // after the age operation the newest (or zero-ith oldest)
 578     // node associated with the allocation site should have
 579     // no references to it as if it were a newly allocated
 580     // heap region
 581     Integer        idNewest   = as.getIthOldest( 0 );
 582     HeapRegionNode hrnNewest  = id2hrn.get( idNewest );
 583     assert         hrnNewest != null;
 584
 585     VariableNode lnX = getVariableNodeFromTemp( x );
 586     clearRefEdgesFrom( lnX, null, null, true );
 587
 588     // make a new reference to allocated node
 589     TypeDescriptor type = as.getType();
 590
 591     RefEdge edgeNew =
 592       new RefEdge( lnX,                  // source
 593                    hrnNewest,            // dest
 594                    type,                 // type
 595                    null,                 // field name
 596                    hrnNewest.getAlpha(), // beta
 597                    predsTrue             // predicates
 598                    );
 599
 600     addRefEdge( lnX, hrnNewest, edgeNew );
 601   }
 602
 603
 604   // use the allocation site (unique to entire analysis) to
 605   // locate the heap region nodes in this reachability graph
 606   // that should be aged.  The process models the allocation
 607   // of new objects and collects all the oldest allocations
 608   // in a summary node to allow for a finite analysis
 609   //
 610   // There is an additional property of this method.  After
 611   // running it on a particular reachability graph (many graphs
 612   // may have heap regions related to the same allocation site)
 613   // the heap region node objects in this reachability graph will be
 614   // allocated.  Therefore, after aging a graph for an allocation
 615   // site, attempts to retrieve the heap region nodes using the
 616   // integer id's contained in the allocation site should always
 617   // return non-null heap regions.
 618   public void age( AllocSite as ) {
 619
 620     // aging adds this allocation site to the graph's
 621     // list of sites that exist in the graph, or does
 622     // nothing if the site is already in the list
 623     allocSites.add( as );
 624
 625     // get the summary node for the allocation site in the context
 626     // of this particular reachability graph
 627     HeapRegionNode hrnSummary = getSummaryNode( as );
 628
 629     // merge oldest node into summary
 630     Integer        idK  = as.getOldest();
 631     HeapRegionNode hrnK = id2hrn.get( idK );
 632     mergeIntoSummary( hrnK, hrnSummary );
 633
 634     // move down the line of heap region nodes
 635     // clobbering the ith and transferring all references
 636     // to and from i-1 to node i.  Note that this clobbers
 637     // the oldest node (hrnK) that was just merged into
 638     // the summary
 639     for( int i = allocationDepth - 1; i > 0; --i ) {
 640
 641       // move references from the i-1 oldest to the ith oldest
 642       Integer        idIth     = as.getIthOldest( i );
 643       HeapRegionNode hrnI      = id2hrn.get( idIth );
 644       Integer        idImin1th = as.getIthOldest( i - 1 );
 645       HeapRegionNode hrnImin1  = id2hrn.get( idImin1th );
 646
 647       transferOnto( hrnImin1, hrnI );
 648     }
 649
 650     // as stated above, the newest node should have had its
 651     // references moved over to the second oldest, so we wipe newest
 652     // in preparation for being the new object to assign something to
 653     Integer        id0th = as.getIthOldest( 0 );
 654     HeapRegionNode hrn0  = id2hrn.get( id0th );
 655     assert hrn0 != null;
 656
 657     // clear all references in and out of newest node
 658     clearRefEdgesFrom( hrn0, null, null, true );
 659     clearRefEdgesTo  ( hrn0, null, null, true );
 660
 661
 662     // now tokens in reachability sets need to "age" also
 663     Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
 664     while( itrAllVariableNodes.hasNext() ) {
 665       Map.Entry    me = (Map.Entry)    itrAllVariableNodes.next();
 666       VariableNode ln = (VariableNode) me.getValue();
 667
 668       Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
 669       while( itrEdges.hasNext() ) {
 670         ageTokens(as, itrEdges.next() );
 671       }
 672     }
 673
 674     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 675     while( itrAllHRNodes.hasNext() ) {
 676       Map.Entry      me       = (Map.Entry)      itrAllHRNodes.next();
 677       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 678
 679       ageTokens( as, hrnToAge );
 680
 681       Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
 682       while( itrEdges.hasNext() ) {
 683         ageTokens( as, itrEdges.next() );
 684       }
 685     }
 686
 687
 688     // after tokens have been aged, reset newest node's reachability
 689     // and a brand new node has a "true" predicate
 690     hrn0.setAlpha( hrn0.getInherent() );
 691     hrn0.setPreds( predsTrue );
 692   }
 693
 694
 695   protected HeapRegionNode getSummaryNode( AllocSite as ) {
 696
 697     Integer        idSummary  = as.getSummary();
 698     HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 699
 700     // If this is null then we haven't touched this allocation site
 701     // in the context of the current reachability graph, so allocate
 702     // heap region nodes appropriate for the entire allocation site.
 703     // This should only happen once per reachability graph per allocation site,
 704     // and a particular integer id can be used to locate the heap region
 705     // in different reachability graphs that represents the same part of an
 706     // allocation site.
 707     if( hrnSummary == null ) {
 708
 709       boolean hasFlags = false;
 710       if( as.getType().isClass() ) {
 711         hasFlags = as.getType().getClassDesc().hasFlags();
 712       }
 713
 714       if( as.getFlag() ){
 715         hasFlags = as.getFlag();
 716       }
 717
 718       String strDesc = as.toStringForDOT()+"\\nsummary";
 719       hrnSummary =
 720         createNewHeapRegionNode( idSummary,    // id or null to generate a new one
 721                                  false,        // single object?
 722                                  true,         // summary?
 723                                  hasFlags,     // flagged?
 724                                  false,        // out-of-context?
 725                                  as.getType(), // type
 726                                  as,           // allocation site
 727                                  null,         // inherent reach
 728                                  null,         // current reach
 729                                  predsEmpty,   // predicates
 730                                  strDesc       // description
 731                                  );
 732
 733       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 734         Integer idIth = as.getIthOldest( i );
 735         assert !id2hrn.containsKey( idIth );
 736         strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
 737         createNewHeapRegionNode( idIth,        // id or null to generate a new one
 738                                  true,         // single object?
 739                                  false,        // summary?
 740                                  hasFlags,     // flagged?
 741                                  false,        // out-of-context?
 742                                  as.getType(), // type
 743                                  as,           // allocation site
 744                                  null,         // inherent reach
 745                                  null,         // current reach
 746                                  predsEmpty,   // predicates
 747                                  strDesc       // description
 748                                  );
 749       }
 750     }
 751
 752     return hrnSummary;
 753   }
 754
 755
 756   protected HeapRegionNode getShadowSummaryNode( AllocSite as ) {
 757
 758     Integer        idShadowSummary  = as.getSummaryShadow();
 759     HeapRegionNode hrnShadowSummary = id2hrn.get( idShadowSummary );
 760
 761     if( hrnShadowSummary == null ) {
 762
 763       boolean hasFlags = false;
 764       if( as.getType().isClass() ) {
 765         hasFlags = as.getType().getClassDesc().hasFlags();
 766       }
 767
 768       if( as.getFlag() ){
 769         hasFlags = as.getFlag();
 770       }
 771
 772       String strDesc = as+"\\n"+as.getType()+"\\nshadowSum";
 773       hrnShadowSummary =
 774         createNewHeapRegionNode( idShadowSummary, // id or null to generate a new one
 775                                  false,           // single object?
 776                                  true,            // summary?
 777                                  hasFlags,        // flagged?
 778                                  false,           // out-of-context?
 779                                  as.getType(),    // type
 780                                  as,              // allocation site
 781                                  null,            // inherent reach
 782                                  null,            // current reach
 783                                  predsEmpty,      // predicates
 784                                  strDesc          // description
 785                                  );
 786
 787       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 788         Integer idShadowIth = as.getIthOldestShadow( i );
 789         assert !id2hrn.containsKey( idShadowIth );
 790         strDesc = as+"\\n"+as.getType()+"\\n"+i+" shadow";
 791         createNewHeapRegionNode( idShadowIth,  // id or null to generate a new one
 792                                  true,         // single object?
 793                                  false,        // summary?
 794                                  hasFlags,     // flagged?
 795                                  false,        // out-of-context?
 796                                  as.getType(), // type
 797                                  as,           // allocation site
 798                                  null,         // inherent reach
 799                                  null,         // current reach
 800                                  predsEmpty,   // predicates
 801                                  strDesc       // description
 802                                  );
 803       }
 804     }
 805
 806     return hrnShadowSummary;
 807   }
 808
 809
 810   protected void mergeIntoSummary( HeapRegionNode hrn,
 811                                    HeapRegionNode hrnSummary ) {
 812     assert hrnSummary.isNewSummary();
 813
 814     // transfer references _from_ hrn over to hrnSummary
 815     Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
 816     while( itrReferencee.hasNext() ) {
 817       RefEdge edge       = itrReferencee.next();
 818       RefEdge edgeMerged = edge.copy();
 819       edgeMerged.setSrc( hrnSummary );
 820
 821       HeapRegionNode hrnReferencee = edge.getDst();
 822       RefEdge        edgeSummary   =
 823         hrnSummary.getReferenceTo( hrnReferencee,
 824                                    edge.getType(),
 825                                    edge.getField()
 826                                    );
 827
 828       if( edgeSummary == null ) {
 829         // the merge is trivial, nothing to be done
 830       } else {
 831         // otherwise an edge from the referencer to hrnSummary exists already
 832         // and the edge referencer->hrn should be merged with it
 833         edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
 834         edgeMerged.setPreds( edgeMerged.getPreds().join( edgeSummary.getPreds() ) );
 835       }
 836
 837       addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
 838     }
 839
 840     // next transfer references _to_ hrn over to hrnSummary
 841     Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
 842     while( itrReferencer.hasNext() ) {
 843       RefEdge edge         = itrReferencer.next();
 844       RefEdge edgeMerged   = edge.copy();
 845       edgeMerged.setDst( hrnSummary );
 846
 847       RefSrcNode onReferencer = edge.getSrc();
 848       RefEdge    edgeSummary  =
 849         onReferencer.getReferenceTo( hrnSummary,
 850                                      edge.getType(),
 851                                      edge.getField()
 852                                      );
 853
 854       if( edgeSummary == null ) {
 855         // the merge is trivial, nothing to be done
 856       } else {
 857         // otherwise an edge from the referencer to alpha_S exists already
 858         // and the edge referencer->alpha_K should be merged with it
 859         edgeMerged.setBeta( edgeMerged.getBeta().union( edgeSummary.getBeta() ) );
 860         edgeMerged.setPreds( edgeMerged.getPreds().join( edgeSummary.getPreds() ) );
 861       }
 862
 863       addRefEdge( onReferencer, hrnSummary, edgeMerged );
 864     }
 865
 866     // then merge hrn reachability into hrnSummary
 867     hrnSummary.setAlpha( hrnSummary.getAlpha().union( hrn.getAlpha() ) );
 868   }
 869
 870
 871   protected void transferOnto( HeapRegionNode hrnA,
 872                                HeapRegionNode hrnB ) {
 873
 874     // clear references in and out of node b
 875     clearRefEdgesFrom( hrnB, null, null, true );
 876     clearRefEdgesTo  ( hrnB, null, null, true );
 877
 878     // copy each edge in and out of A to B
 879     Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
 880     while( itrReferencee.hasNext() ) {
 881       RefEdge        edge          = itrReferencee.next();
 882       HeapRegionNode hrnReferencee = edge.getDst();
 883       RefEdge        edgeNew       = edge.copy();
 884       edgeNew.setSrc( hrnB );
 885
 886       addRefEdge( hrnB, hrnReferencee, edgeNew );
 887     }
 888
 889     Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
 890     while( itrReferencer.hasNext() ) {
 891       RefEdge    edge         = itrReferencer.next();
 892       RefSrcNode onReferencer = edge.getSrc();
 893       RefEdge    edgeNew      = edge.copy();
 894       edgeNew.setDst( hrnB );
 895
 896       addRefEdge( onReferencer, hrnB, edgeNew );
 897     }
 898
 899     // replace hrnB reachability and preds with hrnA's
 900     hrnB.setAlpha( hrnA.getAlpha() );
 901     hrnB.setPreds( hrnA.getPreds() );
 902   }
 903
 904
 905   protected void ageTokens( AllocSite as, RefEdge edge ) {
 906     edge.setBeta( edge.getBeta().ageTokens( as ) );
 907   }
 908
 909   protected void ageTokens( AllocSite as, HeapRegionNode hrn ) {
 910     hrn.setAlpha( hrn.getAlpha().ageTokens( as ) );
 911   }
 912
 913
 914
 915   protected void propagateTokensOverNodes(
 916     HeapRegionNode          nPrime,
 917     ChangeSet               c0,
 918     HashSet<HeapRegionNode> nodesWithNewAlpha,
 919     HashSet<RefEdge>        edgesWithNewBeta ) {
 920
 921     HashSet<HeapRegionNode> todoNodes
 922       = new HashSet<HeapRegionNode>();
 923     todoNodes.add(nPrime);
 924
 925     HashSet<RefEdge> todoEdges
 926       = new HashSet<RefEdge>();
 927
 928     Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
 929       = new Hashtable<HeapRegionNode, ChangeSet>();
 930     nodePlannedChanges.put(nPrime, c0);
 931
 932     Hashtable<RefEdge, ChangeSet> edgePlannedChanges
 933       = new Hashtable<RefEdge, ChangeSet>();
 934
 935     // first propagate change sets everywhere they can go
 936     while( !todoNodes.isEmpty() ) {
 937       HeapRegionNode n = todoNodes.iterator().next();
 938       ChangeSet C = nodePlannedChanges.get(n);
 939
 940       Iterator<RefEdge> referItr = n.iteratorToReferencers();
 941       while( referItr.hasNext() ) {
 942         RefEdge edge = referItr.next();
 943         todoEdges.add(edge);
 944
 945         if( !edgePlannedChanges.containsKey(edge) ) {
 946           edgePlannedChanges.put(edge, new ChangeSet().makeCanonical() );
 947         }
 948
 949         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 950       }
 951
 952       Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
 953       while( refeeItr.hasNext() ) {
 954         RefEdge edgeF = refeeItr.next();
 955         HeapRegionNode m     = edgeF.getDst();
 956
 957         ChangeSet changesToPass = new ChangeSet().makeCanonical();
 958
 959         Iterator<ChangeTuple> itrCprime = C.iterator();
 960         while( itrCprime.hasNext() ) {
 961           ChangeTuple c = itrCprime.next();
 962           if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
 963             changesToPass = changesToPass.union(c);
 964           }
 965         }
 966
 967         if( !changesToPass.isEmpty() ) {
 968           if( !nodePlannedChanges.containsKey(m) ) {
 969             nodePlannedChanges.put(m, new ChangeSet().makeCanonical() );
 970           }
 971
 972           ChangeSet currentChanges = nodePlannedChanges.get(m);
 973
 974           if( !changesToPass.isSubset(currentChanges) ) {
 975
 976             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 977             todoNodes.add(m);
 978           }
 979         }
 980       }
 981
 982       todoNodes.remove(n);
 983     }
 984
 985     // then apply all of the changes for each node at once
 986     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
 987     while( itrMap.hasNext() ) {
 988       Map.Entry      me = (Map.Entry)      itrMap.next();
 989       HeapRegionNode n  = (HeapRegionNode) me.getKey();
 990       ChangeSet C  = (ChangeSet) me.getValue();
 991
 992       // this propagation step is with respect to one change,
 993       // so we capture the full change from the old alpha:
 994       ReachSet localDelta = n.getAlpha().applyChangeSet( C, true );
 995
 996       // but this propagation may be only one of many concurrent
 997       // possible changes, so keep a running union with the node's
 998       // partially updated new alpha set
 999       n.setAlphaNew( n.getAlphaNew().union( localDelta ) );
1000
1001       nodesWithNewAlpha.add( n );
1002     }
1003
1004     propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1005   }
1006
1007
1008   protected void propagateTokensOverEdges(
1009     HashSet  <RefEdge>            todoEdges,
1010     Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1011     HashSet  <RefEdge>            edgesWithNewBeta ) {
1012
1013     // first propagate all change tuples everywhere they can go
1014     while( !todoEdges.isEmpty() ) {
1015       RefEdge edgeE = todoEdges.iterator().next();
1016       todoEdges.remove(edgeE);
1017
1018       if( !edgePlannedChanges.containsKey(edgeE) ) {
1019         edgePlannedChanges.put(edgeE, new ChangeSet().makeCanonical() );
1020       }
1021
1022       ChangeSet C = edgePlannedChanges.get(edgeE);
1023
1024       ChangeSet changesToPass = new ChangeSet().makeCanonical();
1025
1026       Iterator<ChangeTuple> itrC = C.iterator();
1027       while( itrC.hasNext() ) {
1028         ChangeTuple c = itrC.next();
1029         if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1030           changesToPass = changesToPass.union(c);
1031         }
1032       }
1033
1034       RefSrcNode onSrc = edgeE.getSrc();
1035
1036       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1037         HeapRegionNode n = (HeapRegionNode) onSrc;
1038
1039         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1040         while( referItr.hasNext() ) {
1041           RefEdge edgeF = referItr.next();
1042
1043           if( !edgePlannedChanges.containsKey(edgeF) ) {
1044             edgePlannedChanges.put(edgeF, new ChangeSet().makeCanonical() );
1045           }
1046
1047           ChangeSet currentChanges = edgePlannedChanges.get(edgeF);
1048
1049           if( !changesToPass.isSubset(currentChanges) ) {
1050             todoEdges.add(edgeF);
1051             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1052           }
1053         }
1054       }
1055     }
1056
1057     // then apply all of the changes for each edge at once
1058     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1059     while( itrMap.hasNext() ) {
1060       Map.Entry      me = (Map.Entry)      itrMap.next();
1061       RefEdge  e  = (RefEdge)  me.getKey();
1062       ChangeSet C  = (ChangeSet) me.getValue();
1063
1064       // this propagation step is with respect to one change,
1065       // so we capture the full change from the old beta:
1066       ReachSet localDelta = e.getBeta().applyChangeSet( C, true );
1067
1068       // but this propagation may be only one of many concurrent
1069       // possible changes, so keep a running union with the edge's
1070       // partially updated new beta set
1071       e.setBetaNew( e.getBetaNew().union( localDelta  ) );
1072
1073       edgesWithNewBeta.add( e );
1074     }
1075   }
1076
1077
1078
1079   // use this method to make a new reach graph that is
1080   // what heap the FlatMethod callee from the FlatCall
1081   // would start with reaching from its arguments in
1082   // this reach graph
1083   public ReachGraph makeCalleeView( FlatCall   fc,
1084                                     FlatMethod fm ) {
1085
1086     // the callee view is a new graph: DON'T MODIFY
1087     // *THIS* graph
1088     ReachGraph rg = new ReachGraph();
1089
1090     // track what parts of this graph have already been
1091     // added to callee view, variables not needed.
1092     // Note that we need this because when we traverse
1093     // this caller graph for each parameter we may find
1094     // nodes and edges more than once (which the per-param
1095     // "visit" sets won't show) and we only want to create
1096     // an element in the new callee view one time
1097     Set callerNodesCopiedToCallee = new HashSet<HeapRegionNode>();
1098     Set callerEdgesCopiedToCallee = new HashSet<RefEdge>();
1099
1100
1101     // a conservative starting point is to take the
1102     // mechanically-reachable-from-arguments graph
1103     // as opposed to using reachability information
1104     // to prune the graph further
1105     for( int i = 0; i < fm.numParameters(); ++i ) {
1106
1107       // for each parameter index, get the symbol in the
1108       // caller view and callee view
1109
1110       // argument defined here is the symbol in the caller
1111       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fm, i );
1112
1113       // parameter defined here is the symbol in the callee
1114       TempDescriptor tdParam = fm.getParameter( i );
1115
1116       // use these two VariableNode objects to translate
1117       // between caller and callee--its easy to compare
1118       // a HeapRegionNode across callee and caller because
1119       // they will have the same heap region ID
1120       VariableNode vnCaller = this.getVariableNodeFromTemp( tdArg );
1121       VariableNode vnCallee = rg.getVariableNodeFromTemp( tdParam );
1122
1123       // now traverse the calleR view using the argument to
1124       // build the calleE view which has the parameter symbol
1125       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1126       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1127       toVisitInCaller.add( vnCaller );
1128
1129       while( !toVisitInCaller.isEmpty() ) {
1130         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1131         RefSrcNode rsnCallee;
1132
1133         toVisitInCaller.remove( rsnCaller );
1134         visitedInCaller.add( rsnCaller );
1135
1136         // FIRST - setup the source end of an edge, and
1137         // remember the identifying info of the source
1138         // to build predicates
1139         TempDescriptor tdSrc    = null;
1140         Integer        hrnSrcID = null;
1141
1142         if( rsnCaller == vnCaller ) {
1143           // if the caller node is the param symbol, we
1144           // have to do this translation for the callee
1145           rsnCallee = vnCallee;
1146           tdSrc     = tdArg;
1147
1148         } else {
1149           // otherwise the callee-view node is a heap
1150           // region with the same ID, that may or may
1151           // not have been created already
1152           assert rsnCaller instanceof HeapRegionNode;
1153
1154           HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;                   hrnSrcID = hrnSrcCaller.getID();
1155
1156           if( !callerNodesCopiedToCallee.contains( rsnCaller ) ) {
1157
1158             ExistPredNode pred =
1159               new ExistPredNode( hrnSrcID, null );
1160
1161             ExistPredSet preds = new ExistPredSet();
1162             preds.add( pred );
1163
1164             rsnCallee =
1165               rg.createNewHeapRegionNode( hrnSrcCaller.getID(),
1166                                           hrnSrcCaller.isSingleObject(),
1167                                           hrnSrcCaller.isNewSummary(),
1168                                           hrnSrcCaller.isFlagged(),
1169                                           false, // out-of-context?
1170                                           hrnSrcCaller.getType(),
1171                                           hrnSrcCaller.getAllocSite(),
1172                                           toShadowTokens( this, hrnSrcCaller.getInherent() ),
1173                                           toShadowTokens( this, hrnSrcCaller.getAlpha() ),
1174                                           preds,
1175                                           hrnSrcCaller.getDescription()
1176                                           );
1177             callerNodesCopiedToCallee.add( rsnCaller );
1178
1179           } else {
1180             rsnCallee = rg.id2hrn.get( hrnSrcID );
1181           }
1182         }
1183
1184         // SECOND - go over all edges from that source
1185
1186         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1187         while( itrRefEdges.hasNext() ) {
1188           RefEdge        reCaller  = itrRefEdges.next();
1189           HeapRegionNode hrnCaller = reCaller.getDst();
1190           HeapRegionNode hrnCallee;
1191
1192           // THIRD - setup destination ends of edges
1193           Integer hrnDstID = hrnCaller.getID();
1194
1195           if( !callerNodesCopiedToCallee.contains( hrnCaller ) ) {
1196
1197             ExistPredNode pred =
1198               new ExistPredNode( hrnDstID, null );
1199
1200             ExistPredSet preds = new ExistPredSet();
1201             preds.add( pred );
1202
1203             hrnCallee =
1204               rg.createNewHeapRegionNode( hrnCaller.getID(),
1205                                           hrnCaller.isSingleObject(),
1206                                           hrnCaller.isNewSummary(),
1207                                           hrnCaller.isFlagged(),
1208                                           false, // out-of-context?
1209                                           hrnCaller.getType(),
1210                                           hrnCaller.getAllocSite(),
1211                                           toShadowTokens( this, hrnCaller.getInherent() ),
1212                                           toShadowTokens( this, hrnCaller.getAlpha() ),
1213                                           preds,
1214                                           hrnCaller.getDescription()
1215                                           );
1216             callerNodesCopiedToCallee.add( hrnCaller );
1217           } else {
1218             hrnCallee = rg.id2hrn.get( hrnDstID );
1219           }
1220
1221           // FOURTH - copy edge over if needed
1222           if( !callerEdgesCopiedToCallee.contains( reCaller ) ) {
1223
1224             ExistPredEdge pred =
1225               new ExistPredEdge( tdSrc,
1226                                  hrnSrcID,
1227                                  hrnDstID,
1228                                  reCaller.getType(),
1229                                  reCaller.getField(),
1230                                  null );
1231
1232             ExistPredSet preds = new ExistPredSet();
1233             preds.add( pred );
1234
1235             rg.addRefEdge( rsnCallee,
1236                            hrnCallee,
1237                            new RefEdge( rsnCallee,
1238                                         hrnCallee,
1239                                         reCaller.getType(),
1240                                         reCaller.getField(),
1241                                         toShadowTokens( this, reCaller.getBeta() ),
1242                                         preds
1243                                         )
1244                            );
1245             callerEdgesCopiedToCallee.add( reCaller );
1246           }
1247
1248           // keep traversing nodes reachable from param i
1249           // that we haven't visited yet
1250           if( !visitedInCaller.contains( hrnCaller ) ) {
1251             toVisitInCaller.add( hrnCaller );
1252           }
1253
1254         } // end edge iteration
1255       } // end visiting heap nodes in caller
1256     } // end iterating over parameters as starting points
1257
1258
1259     // find the set of edges in this graph with source
1260     // out-of-context (not in nodes copied) and have a
1261     // destination in context (one of nodes copied) as
1262     // a starting point for building out-of-context nodes
1263     Iterator<HeapRegionNode> itrInContext =
1264       callerNodesCopiedToCallee.iterator();
1265     while( itrInContext.hasNext() ) {
1266       HeapRegionNode hrnCallerAndInContext = itrInContext.next();
1267
1268       Iterator<RefEdge> itrMightCross =
1269         hrnCallerAndInContext.iteratorToReferencers();
1270       while( itrMightCross.hasNext() ) {
1271         RefEdge edgeMightCross = itrMightCross.next();
1272
1273         // we're only interested in edges with a source
1274         // 1) out-of-context and 2) is a heap region
1275         if( callerNodesCopiedToCallee.contains( edgeMightCross.getSrc() ) ||
1276             !(edgeMightCross.getSrc() instanceof HeapRegionNode)
1277             ) {
1278           // then just skip
1279           continue;
1280         }
1281
1282         HeapRegionNode hrnCallerAndOutContext =
1283           (HeapRegionNode)edgeMightCross.getSrc();
1284
1285         // we found a reference that crosses from out-of-context
1286         // to in-context, so build a special out-of-context node
1287         // for the callee IHM and its reference edge
1288         HeapRegionNode hrnCalleeAndOutContext =
1289           rg.createNewHeapRegionNode( null,  // ID
1290                                       false, // single object?
1291                                       false, // new summary?
1292                                       false, // flagged?
1293                                       true,  // out-of-context?
1294                                       hrnCallerAndOutContext.getType(),
1295                                       null,  // alloc site, shouldn't be used
1296                                       toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // inherent
1297                                       toShadowTokens( this, hrnCallerAndOutContext.getAlpha() ), // alpha
1298                                       predsEmpty,
1299                                       "out-of-context"
1300                                       );
1301
1302         HeapRegionNode hrnCalleeAndInContext =
1303           rg.id2hrn.get( hrnCallerAndInContext.getID() );
1304
1305         rg.addRefEdge( hrnCalleeAndOutContext,
1306                        hrnCalleeAndInContext,
1307                        new RefEdge( hrnCalleeAndOutContext,
1308                                     hrnCalleeAndInContext,
1309                                     edgeMightCross.getType(),
1310                                     edgeMightCross.getField(),
1311                                     toShadowTokens( this, edgeMightCross.getBeta() ),
1312                                     predsEmpty
1313                                     )
1314                        );
1315       }
1316     }
1317
1318
1319     try {
1320       rg.writeGraph( "calleeview", true, true, true, false, true, true );
1321     } catch( IOException e ) {}
1322
1323     if( fc.getMethod().getSymbol().equals( "addSomething" ) ) {
1324       System.exit( 0 );
1325     }
1326
1327
1328     return rg;
1329   }
1330
1331   public void resolveMethodCall( FlatCall   fc,
1332                                  FlatMethod fm,
1333                                  ReachGraph rgCallee
1334                                  ) {
1335     /*
1336     // to map the callee effects into the caller graph,
1337     // traverse the callee and categorize each element as,
1338     // Callee elements:
1339     // 1) new node (not in caller)
1340     // 2) old node, clean (not modified in callee)
1341     // 3) old node, dirty
1342     // 4) new edge,
1343     // 5) old edge, clean
1344     // 6) old edge, dirty
1345     // 7) out-of-context nodes
1346     // 8) edge that crosses out-of-context to in-
1347
1348     Iterator hrnItr = rgCallee.id2hrn.entrySet().iterator();
1349     while( hrnItr.hasNext() ) {
1350       Map.Entry      me        = (Map.Entry)      hrnItr.next();
1351       Integer        id        = (Integer)        me.getKey();
1352       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1353
1354       if( hrnCallee.isOutOfContext() ) {
1355         // 7) out-of-context nodes aren't altered by callee
1356         // analysis, they just help calculate changes to other
1357         // elements, so do nothing for this node
1358
1359       } else {
1360         // node is in the callee context...
1361
1362         if( !this.id2hrn.containsKey( id ) ) {
1363           // 1) this is a new node in the callee
1364           assert !hrnCallee.isClean();
1365
1366           // bring this node into caller as-is, and do the
1367           // unshadow of tokens in-place
1368           this.createNewHeapRegionNode( id,
1369                                         hrnCallee.isSingleObject(),
1370                                         hrnCallee.isNewSummary(),
1371                                         hrnCallee.isFlagged(),
1372                                         false, // clean?
1373                                         false, // out-of-context?
1374                                         hrnCallee.getType(),
1375                                         hrnCallee.getAllocSite(),
1376                                         unShadowTokens( rgCallee, hrnCallee.getInherent() ),
1377                                         unShadowTokens( rgCallee, hrnCallee.getAlpha() ),
1378                                         predsEmpty,
1379                                         hrnCallee.getDescription()
1380                                         );
1381
1382         } else {
1383           // otherwise, both graphs have this node, so...
1384
1385           if( hrnCallee.isClean() ) {
1386             // 2) this node was not modified by callee,
1387             // just leave it alone in caller
1388
1389           } else {
1390             // 3) this node is already in caller, was modified
1391             // by the callee, so update caller node in-place
1392             hrnCaller = this.id2hrn.get( id );
1393
1394             assert hrnCaller.getInherent().equals(
1395                                                   unShadowTokens( rgCallee, hrnCallee.getInherent() )
1396                                                    );
1397             hrnCaller.setAlpha(
1398                                unShadowTokens( rgCallee, hrnCallee.getAlpha() )
1399                                 );
1400
1401             hrnCaller.setClean( false );
1402           }
1403         }
1404       }
1405     } // end visiting callee nodes
1406
1407     // what else?
1408     */
1409   }
1410
1411
1412   protected void unshadowTokens( AllocSite as,
1413                                  RefEdge   edge
1414                                  ) {
1415     edge.setBeta( edge.getBeta().unshadowTokens( as ) );
1416   }
1417
1418   protected void unshadowTokens( AllocSite      as,
1419                                  HeapRegionNode hrn
1420                                  ) {
1421     hrn.setAlpha( hrn.getAlpha().unshadowTokens( as ) );
1422   }
1423
1424
1425   private ReachSet toShadowTokens( ReachGraph rg,
1426                                    ReachSet   rsIn
1427                                    ) {
1428     ReachSet rsOut = new ReachSet( rsIn ).makeCanonical();
1429
1430     Iterator<AllocSite> allocItr = rg.allocSites.iterator();
1431     while( allocItr.hasNext() ) {
1432       AllocSite as = allocItr.next();
1433       rsOut = rsOut.toShadowTokens( as );
1434     }
1435
1436     return rsOut.makeCanonical();
1437   }
1438
1439
1440
1441   ////////////////////////////////////////////////////
1442   //
1443   //  This global sweep is an optional step to prune
1444   //  reachability sets that are not internally
1445   //  consistent with the global graph.  It should be
1446   //  invoked after strong updates or method calls.
1447   //
1448   ////////////////////////////////////////////////////
1449   public void globalSweep() {
1450
1451     // boldB is part of the phase 1 sweep
1452     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldB =
1453       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
1454
1455     // visit every heap region to initialize alphaNew and calculate boldB
1456     Set hrns = id2hrn.entrySet();
1457     Iterator itrHrns = hrns.iterator();
1458     while( itrHrns.hasNext() ) {
1459       Map.Entry me = (Map.Entry)itrHrns.next();
1460       Integer token = (Integer) me.getKey();
1461       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1462
1463       // assert that this node and incoming edges have clean alphaNew
1464       // and betaNew sets, respectively
1465       assert rstateEmpty.equals( hrn.getAlphaNew() );
1466
1467       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
1468       while( itrRers.hasNext() ) {
1469         RefEdge edge = itrRers.next();
1470         assert rstateEmpty.equals( edge.getBetaNew() );
1471       }
1472
1473       // calculate boldB for this flagged node
1474       if( hrn.isFlagged() ) {
1475
1476         Hashtable<RefEdge, ReachSet> boldB_f =
1477           new Hashtable<RefEdge, ReachSet>();
1478
1479         Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
1480
1481         // initial boldB_f constraints
1482         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
1483         while( itrRees.hasNext() ) {
1484           RefEdge edge = itrRees.next();
1485
1486           assert !boldB.containsKey( edge );
1487           boldB_f.put( edge, edge.getBeta() );
1488
1489           assert !workSetEdges.contains( edge );
1490           workSetEdges.add( edge );
1491         }
1492
1493         // enforce the boldB_f constraint at edges until we reach a fixed point
1494         while( !workSetEdges.isEmpty() ) {
1495           RefEdge edge = workSetEdges.iterator().next();
1496           workSetEdges.remove( edge );
1497
1498           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
1499           while( itrPrime.hasNext() ) {
1500             RefEdge edgePrime = itrPrime.next();
1501
1502             ReachSet prevResult   = boldB_f.get( edgePrime );
1503             ReachSet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
1504
1505             if( prevResult == null ||
1506                 prevResult.union( intersection ).size() > prevResult.size() ) {
1507
1508               if( prevResult == null ) {
1509                 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
1510               } else {
1511                 boldB_f.put( edgePrime, prevResult         .union( intersection ) );
1512               }
1513               workSetEdges.add( edgePrime );
1514             }
1515           }
1516         }
1517
1518         boldB.put( token, boldB_f );
1519       }
1520     }
1521
1522
1523     // use boldB to prune tokens from alpha states that are impossible
1524     // and propagate the differences backwards across edges
1525     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
1526
1527     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
1528       new Hashtable<RefEdge, ChangeSet>();
1529
1530     hrns = id2hrn.entrySet();
1531     itrHrns = hrns.iterator();
1532     while( itrHrns.hasNext() ) {
1533       Map.Entry me = (Map.Entry)itrHrns.next();
1534       Integer token = (Integer) me.getKey();
1535       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
1536
1537       // never remove the identity token from a flagged region
1538       // because it is trivially satisfied
1539       ReachTuple ttException = new ReachTuple( token,
1540                                                !hrn.isSingleObject(),
1541                                                ReachTuple.ARITY_ONE ).makeCanonical();
1542
1543       ChangeSet cts = new ChangeSet().makeCanonical();
1544
1545       // mark tokens for removal
1546       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
1547       while( stateItr.hasNext() ) {
1548         ReachState ttsOld = stateItr.next();
1549
1550         ReachState markedTokens = new ReachState().makeCanonical();
1551
1552         Iterator<ReachTuple> ttItr = ttsOld.iterator();
1553         while( ttItr.hasNext() ) {
1554           ReachTuple ttOld = ttItr.next();
1555
1556           // never remove the identity token from a flagged region
1557           // because it is trivially satisfied
1558           if( hrn.isFlagged() ) {
1559             if( ttOld == ttException ) {
1560               continue;
1561             }
1562           }
1563
1564           // does boldB_ttOld allow this token?
1565           boolean foundState = false;
1566           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1567           while( incidentEdgeItr.hasNext() ) {
1568             RefEdge incidentEdge = incidentEdgeItr.next();
1569
1570             // if it isn't allowed, mark for removal
1571             Integer idOld = ttOld.getToken();
1572             assert id2hrn.containsKey( idOld );
1573             Hashtable<RefEdge, ReachSet> B = boldB.get( idOld );
1574             ReachSet boldB_ttOld_incident = B.get( incidentEdge );// B is NULL!
1575             if( boldB_ttOld_incident != null &&
1576                 boldB_ttOld_incident.contains( ttsOld ) ) {
1577               foundState = true;
1578             }
1579           }
1580
1581           if( !foundState ) {
1582             markedTokens = markedTokens.add( ttOld );
1583           }
1584         }
1585
1586         // if there is nothing marked, just move on
1587         if( markedTokens.isEmpty() ) {
1588           hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
1589           continue;
1590         }
1591
1592         // remove all marked tokens and establish a change set that should
1593         // propagate backwards over edges from this node
1594         ReachState ttsPruned = new ReachState().makeCanonical();
1595         ttItr = ttsOld.iterator();
1596         while( ttItr.hasNext() ) {
1597           ReachTuple ttOld = ttItr.next();
1598
1599           if( !markedTokens.containsTuple( ttOld ) ) {
1600             ttsPruned = ttsPruned.union( ttOld );
1601           }
1602         }
1603         assert !ttsOld.equals( ttsPruned );
1604
1605         hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
1606         ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
1607         cts = cts.union( ct );
1608       }
1609
1610       // throw change tuple set on all incident edges
1611       if( !cts.isEmpty() ) {
1612         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
1613         while( incidentEdgeItr.hasNext() ) {
1614           RefEdge incidentEdge = incidentEdgeItr.next();
1615
1616           edgesForPropagation.add( incidentEdge );
1617
1618           if( edgePlannedChanges.get( incidentEdge ) == null ) {
1619             edgePlannedChanges.put( incidentEdge, cts );
1620           } else {
1621             edgePlannedChanges.put(
1622               incidentEdge,
1623               edgePlannedChanges.get( incidentEdge ).union( cts )
1624                                   );
1625           }
1626         }
1627       }
1628     }
1629
1630     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
1631
1632     propagateTokensOverEdges( edgesForPropagation,
1633                               edgePlannedChanges,
1634                               edgesUpdated );
1635
1636     // at the end of the 1st phase reference edges have
1637     // beta, betaNew that correspond to beta and betaR
1638     //
1639     // commit beta<-betaNew, so beta=betaR and betaNew
1640     // will represent the beta' calculation in 2nd phase
1641     //
1642     // commit alpha<-alphaNew because it won't change
1643     HashSet<RefEdge> res = new HashSet<RefEdge>();
1644
1645     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
1646     while( nodeItr.hasNext() ) {
1647       HeapRegionNode hrn = nodeItr.next();
1648       hrn.applyAlphaNew();
1649       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
1650       while( itrRes.hasNext() ) {
1651         res.add( itrRes.next() );
1652       }
1653     }
1654
1655
1656     // 2nd phase
1657     Iterator<RefEdge> edgeItr = res.iterator();
1658     while( edgeItr.hasNext() ) {
1659       RefEdge edge = edgeItr.next();
1660       HeapRegionNode hrn = edge.getDst();
1661
1662       // commit results of last phase
1663       if( edgesUpdated.contains( edge ) ) {
1664         edge.applyBetaNew();
1665       }
1666
1667       // compute intial condition of 2nd phase
1668       edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
1669     }
1670
1671     // every edge in the graph is the initial workset
1672     Set<RefEdge> edgeWorkSet = (Set) res.clone();
1673     while( !edgeWorkSet.isEmpty() ) {
1674       RefEdge edgePrime = edgeWorkSet.iterator().next();
1675       edgeWorkSet.remove( edgePrime );
1676
1677       RefSrcNode on = edgePrime.getSrc();
1678       if( !(on instanceof HeapRegionNode) ) {
1679         continue;
1680       }
1681       HeapRegionNode hrn = (HeapRegionNode) on;
1682
1683       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
1684       while( itrEdge.hasNext() ) {
1685         RefEdge edge = itrEdge.next();
1686
1687         ReachSet prevResult = edge.getBetaNew();
1688         assert prevResult != null;
1689
1690         ReachSet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
1691
1692         if( prevResult.union( intersection ).size() > prevResult.size() ) {
1693           edge.setBetaNew( prevResult.union( intersection ) );
1694           edgeWorkSet.add( edge );
1695         }
1696       }
1697     }
1698
1699     // commit beta' (beta<-betaNew)
1700     edgeItr = res.iterator();
1701     while( edgeItr.hasNext() ) {
1702       edgeItr.next().applyBetaNew();
1703     }
1704   }
1705
1706
1707
1708   ////////////////////////////////////////////////////
1709   // high-level merge operations
1710   ////////////////////////////////////////////////////
1711   public void merge_sameMethodContext( ReachGraph rg ) {
1712     // when merging two graphs that abstract the heap
1713     // of the same method context, we just call the
1714     // basic merge operation
1715     merge( rg );
1716   }
1717
1718   public void merge_diffMethodContext( ReachGraph rg ) {
1719     // when merging graphs for abstract heaps in
1720     // different method contexts we should:
1721     // 1) age the allocation sites?
1722     merge( rg );
1723   }
1724
1725   ////////////////////////////////////////////////////
1726   // in merge() and equals() methods the suffix A
1727   // represents the passed in graph and the suffix
1728   // B refers to the graph in this object
1729   // Merging means to take the incoming graph A and
1730   // merge it into B, so after the operation graph B
1731   // is the final result.
1732   ////////////////////////////////////////////////////
1733   protected void merge( ReachGraph rg ) {
1734
1735     if( rg == null ) {
1736       return;
1737     }
1738
1739     mergeNodes     ( rg );
1740     mergeRefEdges  ( rg );
1741     mergeAllocSites( rg );
1742   }
1743
1744   protected void mergeNodes( ReachGraph rg ) {
1745
1746     // start with heap region nodes
1747     Set      sA = rg.id2hrn.entrySet();
1748     Iterator iA = sA.iterator();
1749     while( iA.hasNext() ) {
1750       Map.Entry      meA  = (Map.Entry)      iA.next();
1751       Integer        idA  = (Integer)        meA.getKey();
1752       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1753
1754       // if this graph doesn't have a node the
1755       // incoming graph has, allocate it
1756       if( !id2hrn.containsKey( idA ) ) {
1757         HeapRegionNode hrnB = hrnA.copy();
1758         id2hrn.put( idA, hrnB );
1759
1760       } else {
1761         // otherwise this is a node present in both graphs
1762         // so make the new reachability set a union of the
1763         // nodes' reachability sets
1764         HeapRegionNode hrnB = id2hrn.get( idA );
1765         hrnB.setAlpha( hrnB.getAlpha().union( hrnA.getAlpha() ) );
1766
1767         // if hrnB is already dirty or hrnA is dirty,
1768         // the hrnB should end up dirty: TODO
1769         /*
1770         if( !hrnA.isClean() ) {
1771           hrnB.setIsClean( false );
1772         }
1773         */
1774       }
1775     }
1776
1777     // now add any variable nodes that are in graph B but
1778     // not in A
1779     sA = rg.td2vn.entrySet();
1780     iA = sA.iterator();
1781     while( iA.hasNext() ) {
1782       Map.Entry      meA = (Map.Entry)      iA.next();
1783       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1784       VariableNode   lnA = (VariableNode)   meA.getValue();
1785
1786       // if the variable doesn't exist in B, allocate and add it
1787       VariableNode lnB = getVariableNodeFromTemp( tdA );
1788     }
1789   }
1790
1791   protected void mergeRefEdges( ReachGraph rg ) {
1792
1793     // between heap regions
1794     Set      sA = rg.id2hrn.entrySet();
1795     Iterator iA = sA.iterator();
1796     while( iA.hasNext() ) {
1797       Map.Entry      meA  = (Map.Entry)      iA.next();
1798       Integer        idA  = (Integer)        meA.getKey();
1799       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1800
1801       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1802       while( heapRegionsItrA.hasNext() ) {
1803         RefEdge        edgeA     = heapRegionsItrA.next();
1804         HeapRegionNode hrnChildA = edgeA.getDst();
1805         Integer        idChildA  = hrnChildA.getID();
1806
1807         // at this point we know an edge in graph A exists
1808         // idA -> idChildA, does this exist in B?
1809         assert id2hrn.containsKey( idA );
1810         HeapRegionNode hrnB        = id2hrn.get( idA );
1811         RefEdge        edgeToMerge = null;
1812
1813         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1814         while( heapRegionsItrB.hasNext() &&
1815                edgeToMerge == null          ) {
1816
1817           RefEdge        edgeB     = heapRegionsItrB.next();
1818           HeapRegionNode hrnChildB = edgeB.getDst();
1819           Integer        idChildB  = hrnChildB.getID();
1820
1821           // don't use the RefEdge.equals() here because
1822           // we're talking about existence between graphs,
1823           // not intragraph equal
1824           if( idChildB.equals( idChildA ) &&
1825               edgeB.typeAndFieldEquals( edgeA ) ) {
1826
1827             edgeToMerge = edgeB;
1828           }
1829         }
1830
1831         // if the edge from A was not found in B,
1832         // add it to B.
1833         if( edgeToMerge == null ) {
1834           assert id2hrn.containsKey( idChildA );
1835           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
1836           edgeToMerge = edgeA.copy();
1837           edgeToMerge.setSrc( hrnB );
1838           edgeToMerge.setDst( hrnChildB );
1839           addRefEdge( hrnB, hrnChildB, edgeToMerge );
1840         }
1841         // otherwise, the edge already existed in both graphs
1842         // so merge their reachability sets
1843         else {
1844           // just replace this beta set with the union
1845           assert edgeToMerge != null;
1846           edgeToMerge.setBeta(
1847             edgeToMerge.getBeta().union( edgeA.getBeta() )
1848             );
1849           // TODO: what?
1850           /*
1851           if( !edgeA.isClean() ) {
1852             edgeToMerge.setIsClean( false );
1853           }
1854           */
1855         }
1856       }
1857     }
1858
1859     // and then again from variable nodes
1860     sA = rg.td2vn.entrySet();
1861     iA = sA.iterator();
1862     while( iA.hasNext() ) {
1863       Map.Entry      meA = (Map.Entry)      iA.next();
1864       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1865       VariableNode   vnA = (VariableNode)   meA.getValue();
1866
1867       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
1868       while( heapRegionsItrA.hasNext() ) {
1869         RefEdge        edgeA     = heapRegionsItrA.next();
1870         HeapRegionNode hrnChildA = edgeA.getDst();
1871         Integer        idChildA  = hrnChildA.getID();
1872
1873         // at this point we know an edge in graph A exists
1874         // tdA -> idChildA, does this exist in B?
1875         assert td2vn.containsKey( tdA );
1876         VariableNode vnB         = td2vn.get( tdA );
1877         RefEdge      edgeToMerge = null;
1878
1879         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
1880         while( heapRegionsItrB.hasNext() &&
1881                edgeToMerge == null          ) {
1882
1883           RefEdge        edgeB     = heapRegionsItrB.next();
1884           HeapRegionNode hrnChildB = edgeB.getDst();
1885           Integer        idChildB  = hrnChildB.getID();
1886
1887           // don't use the RefEdge.equals() here because
1888           // we're talking about existence between graphs
1889           if( idChildB.equals( idChildA ) &&
1890               edgeB.typeAndFieldEquals( edgeA ) ) {
1891
1892             edgeToMerge = edgeB;
1893           }
1894         }
1895
1896         // if the edge from A was not found in B,
1897         // add it to B.
1898         if( edgeToMerge == null ) {
1899           assert id2hrn.containsKey( idChildA );
1900           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
1901           edgeToMerge = edgeA.copy();
1902           edgeToMerge.setSrc( vnB );
1903           edgeToMerge.setDst( hrnChildB );
1904           addRefEdge( vnB, hrnChildB, edgeToMerge );
1905         }
1906         // otherwise, the edge already existed in both graphs
1907         // so merge their reachability sets
1908         else {
1909           // just replace this beta set with the union
1910           edgeToMerge.setBeta(
1911             edgeToMerge.getBeta().union( edgeA.getBeta() )
1912             );
1913           // TODO: what?
1914           /*
1915           if( !edgeA.isClean() ) {
1916             edgeToMerge.setIsClean( false );
1917           }
1918           */
1919         }
1920       }
1921     }
1922   }
1923
1924   protected void mergeAllocSites( ReachGraph rg ) {
1925     allocSites.addAll( rg.allocSites );
1926   }
1927
1928
1929   // it is necessary in the equals() member functions
1930   // to "check both ways" when comparing the data
1931   // structures of two graphs.  For instance, if all
1932   // edges between heap region nodes in graph A are
1933   // present and equal in graph B it is not sufficient
1934   // to say the graphs are equal.  Consider that there
1935   // may be edges in graph B that are not in graph A.
1936   // the only way to know that all edges in both graphs
1937   // are equally present is to iterate over both data
1938   // structures and compare against the other graph.
1939   public boolean equals( ReachGraph rg ) {
1940
1941     if( rg == null ) {
1942       return false;
1943     }
1944
1945     if( !areHeapRegionNodesEqual( rg ) ) {
1946       return false;
1947     }
1948
1949     if( !areVariableNodesEqual( rg ) ) {
1950       return false;
1951     }
1952
1953     if( !areRefEdgesEqual( rg ) ) {
1954       return false;
1955     }
1956
1957     // if everything is equal up to this point,
1958     // assert that allocSites is also equal--
1959     // this data is redundant but kept for efficiency
1960     assert allocSites.equals( rg.allocSites );
1961
1962     return true;
1963   }
1964
1965
1966   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
1967
1968     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
1969       return false;
1970     }
1971
1972     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
1973       return false;
1974     }
1975
1976     return true;
1977   }
1978
1979   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
1980                                                         ReachGraph rgB ) {
1981     Set      sA = rgA.id2hrn.entrySet();
1982     Iterator iA = sA.iterator();
1983     while( iA.hasNext() ) {
1984       Map.Entry      meA  = (Map.Entry)      iA.next();
1985       Integer        idA  = (Integer)        meA.getKey();
1986       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1987
1988       if( !rgB.id2hrn.containsKey( idA ) ) {
1989         return false;
1990       }
1991
1992       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
1993       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
1994         return false;
1995       }
1996     }
1997
1998     return true;
1999   }
2000
2001
2002   protected boolean areVariableNodesEqual( ReachGraph rg ) {
2003
2004     if( !areallVNinAalsoinBandequal( this, rg ) ) {
2005       return false;
2006     }
2007
2008     if( !areallVNinAalsoinBandequal( rg, this ) ) {
2009       return false;
2010     }
2011
2012     return true;
2013   }
2014
2015   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
2016                                                        ReachGraph rgB ) {
2017     Set      sA = rgA.td2vn.entrySet();
2018     Iterator iA = sA.iterator();
2019     while( iA.hasNext() ) {
2020       Map.Entry      meA = (Map.Entry)      iA.next();
2021       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2022
2023       if( !rgB.td2vn.containsKey( tdA ) ) {
2024         return false;
2025       }
2026     }
2027
2028     return true;
2029   }
2030
2031
2032   protected boolean areRefEdgesEqual( ReachGraph rg ) {
2033     if( !areallREinAandBequal( this, rg ) ) {
2034       return false;
2035     }
2036
2037     return true;
2038   }
2039
2040   static protected boolean areallREinAandBequal( ReachGraph rgA,
2041                                                  ReachGraph rgB ) {
2042
2043     // check all the heap region->heap region edges
2044     Set      sA = rgA.id2hrn.entrySet();
2045     Iterator iA = sA.iterator();
2046     while( iA.hasNext() ) {
2047       Map.Entry      meA  = (Map.Entry)      iA.next();
2048       Integer        idA  = (Integer)        meA.getKey();
2049       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2050
2051       // we should have already checked that the same
2052       // heap regions exist in both graphs
2053       assert rgB.id2hrn.containsKey( idA );
2054
2055       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
2056         return false;
2057       }
2058
2059       // then check every edge in B for presence in A, starting
2060       // from the same parent HeapRegionNode
2061       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
2062
2063       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
2064         return false;
2065       }
2066     }
2067
2068     // then check all the variable->heap region edges
2069     sA = rgA.td2vn.entrySet();
2070     iA = sA.iterator();
2071     while( iA.hasNext() ) {
2072       Map.Entry      meA = (Map.Entry)      iA.next();
2073       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2074       VariableNode   vnA = (VariableNode)   meA.getValue();
2075
2076       // we should have already checked that the same
2077       // label nodes exist in both graphs
2078       assert rgB.td2vn.containsKey( tdA );
2079
2080       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
2081         return false;
2082       }
2083
2084       // then check every edge in B for presence in A, starting
2085       // from the same parent VariableNode
2086       VariableNode vnB = rgB.td2vn.get( tdA );
2087
2088       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
2089         return false;
2090       }
2091     }
2092
2093     return true;
2094   }
2095
2096
2097   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
2098                                                   RefSrcNode rnA,
2099                                                   ReachGraph rgB ) {
2100
2101     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
2102     while( itrA.hasNext() ) {
2103       RefEdge        edgeA     = itrA.next();
2104       HeapRegionNode hrnChildA = edgeA.getDst();
2105       Integer        idChildA  = hrnChildA.getID();
2106
2107       assert rgB.id2hrn.containsKey( idChildA );
2108
2109       // at this point we know an edge in graph A exists
2110       // rnA -> idChildA, does this exact edge exist in B?
2111       boolean edgeFound = false;
2112
2113       RefSrcNode rnB = null;
2114       if( rnA instanceof HeapRegionNode ) {
2115         HeapRegionNode hrnA = (HeapRegionNode) rnA;
2116         rnB = rgB.id2hrn.get( hrnA.getID() );
2117       } else {
2118         VariableNode vnA = (VariableNode) rnA;
2119         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
2120       }
2121
2122       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
2123       while( itrB.hasNext() ) {
2124         RefEdge        edgeB     = itrB.next();
2125         HeapRegionNode hrnChildB = edgeB.getDst();
2126         Integer        idChildB  = hrnChildB.getID();
2127
2128         if( idChildA.equals( idChildB ) &&
2129             edgeA.typeAndFieldEquals( edgeB ) ) {
2130
2131           // there is an edge in the right place with the right field,
2132           // but do they have the same attributes?
2133           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
2134               edgeA.equalsPreds( edgeB )
2135               ) {
2136             edgeFound = true;
2137           }
2138         }
2139       }
2140
2141       if( !edgeFound ) {
2142         return false;
2143       }
2144     }
2145
2146     return true;
2147   }
2148
2149
2150
2151   // this analysis no longer has the "match anything"
2152   // type which was represented by null
2153   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2154                                              TypeDescriptor td2 ) {
2155     assert td1 != null;
2156     assert td2 != null;
2157
2158     if( td1.isNull() ) {
2159       return td2;
2160     }
2161     if( td2.isNull() ) {
2162       return td1;
2163     }
2164     return typeUtil.mostSpecific( td1, td2 );
2165   }
2166
2167   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2168                                              TypeDescriptor td2,
2169                                              TypeDescriptor td3 ) {
2170
2171     return mostSpecificType( td1,
2172                              mostSpecificType( td2, td3 )
2173                              );
2174   }
2175
2176   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
2177                                              TypeDescriptor td2,
2178                                              TypeDescriptor td3,
2179                                              TypeDescriptor td4 ) {
2180
2181     return mostSpecificType( mostSpecificType( td1, td2 ),
2182                              mostSpecificType( td3, td4 )
2183                              );
2184   }
2185
2186   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
2187                                     TypeDescriptor possibleChild ) {
2188     assert possibleSuper != null;
2189     assert possibleChild != null;
2190
2191     if( possibleSuper.isNull() ||
2192         possibleChild.isNull() ) {
2193       return true;
2194     }
2195
2196     return typeUtil.isSuperorType( possibleSuper, possibleChild );
2197   }
2198
2199
2200   protected boolean hasMatchingField( HeapRegionNode src,
2201                                       RefEdge        edge ) {
2202
2203     TypeDescriptor tdSrc = src.getType();
2204     assert tdSrc != null;
2205
2206     if( tdSrc.isArray() ) {
2207       TypeDescriptor td = edge.getType();
2208       assert td != null;
2209
2210       TypeDescriptor tdSrcDeref = tdSrc.dereference();
2211       assert tdSrcDeref != null;
2212
2213       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2214         return false;
2215       }
2216
2217       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
2218     }
2219
2220     // if it's not a class, it doesn't have any fields to match
2221     if( !tdSrc.isClass() ) {
2222       return false;
2223     }
2224
2225     ClassDescriptor cd = tdSrc.getClassDesc();
2226     while( cd != null ) {
2227       Iterator fieldItr = cd.getFields();
2228
2229       while( fieldItr.hasNext() ) {
2230         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
2231
2232         if( fd.getType().equals( edge.getType() ) &&
2233             fd.getSymbol().equals( edge.getField() ) ) {
2234           return true;
2235         }
2236       }
2237
2238       cd = cd.getSuperDesc();
2239     }
2240
2241     // otherwise it is a class with fields
2242     // but we didn't find a match
2243     return false;
2244   }
2245
2246   protected boolean hasMatchingType( RefEdge        edge,
2247                                      HeapRegionNode dst  ) {
2248
2249     // if the region has no type, matches everything
2250     TypeDescriptor tdDst = dst.getType();
2251     assert tdDst != null;
2252
2253     // if the type is not a class or an array, don't
2254     // match because primitives are copied, no aliases
2255     ClassDescriptor cdDst = tdDst.getClassDesc();
2256     if( cdDst == null && !tdDst.isArray() ) {
2257       return false;
2258     }
2259
2260     // if the edge type is null, it matches everything
2261     TypeDescriptor tdEdge = edge.getType();
2262     assert tdEdge != null;
2263
2264     return typeUtil.isSuperorType( tdEdge, tdDst );
2265   }
2266
2267
2268   public void writeGraph( String graphName,
2269                           boolean writeLabels,
2270                           boolean labelSelect,
2271                           boolean pruneGarbage,
2272                           boolean writeReferencers,
2273                           boolean hideSubsetReachability,
2274                           boolean hideEdgeTaints
2275                           ) throws java.io.IOException {
2276
2277     // remove all non-word characters from the graph name so
2278     // the filename and identifier in dot don't cause errors
2279     graphName = graphName.replaceAll( "[\\W]", "" );
2280
2281     BufferedWriter bw =
2282       new BufferedWriter( new FileWriter( graphName+".dot" ) );
2283
2284     bw.write( "digraph "+graphName+" {\n" );
2285
2286     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2287
2288     // then visit every heap region node
2289     Set      s = id2hrn.entrySet();
2290     Iterator i = s.iterator();
2291     while( i.hasNext() ) {
2292       Map.Entry      me  = (Map.Entry)      i.next();
2293       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2294
2295       // only visit nodes worth writing out--for instance
2296       // not every node at an allocation is referenced
2297       // (think of it as garbage-collected), etc.
2298       if( !pruneGarbage                              ||
2299           (hrn.isFlagged() && hrn.getID() > 0)       ||
2300           hrn.getDescription().startsWith( "param" ) ||
2301           hrn.isOutOfContext()
2302           ) {
2303
2304         if( !visited.contains( hrn ) ) {
2305           traverseHeapRegionNodes( hrn,
2306                                    bw,
2307                                    null,
2308                                    visited,
2309                                    writeReferencers,
2310                                    hideSubsetReachability,
2311                                    hideEdgeTaints );
2312         }
2313       }
2314     }
2315
2316     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
2317
2318
2319     // then visit every label node, useful for debugging
2320     if( writeLabels ) {
2321       s = td2vn.entrySet();
2322       i = s.iterator();
2323       while( i.hasNext() ) {
2324         Map.Entry    me = (Map.Entry)    i.next();
2325         VariableNode vn = (VariableNode) me.getValue();
2326
2327         if( labelSelect ) {
2328           String labelStr = vn.getTempDescriptorString();
2329           if( labelStr.startsWith("___temp") ||
2330               labelStr.startsWith("___dst") ||
2331               labelStr.startsWith("___srctmp") ||
2332               labelStr.startsWith("___neverused")
2333               ) {
2334             continue;
2335           }
2336         }
2337
2338         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
2339         while( heapRegionsItr.hasNext() ) {
2340           RefEdge        edge = heapRegionsItr.next();
2341           HeapRegionNode hrn  = edge.getDst();
2342
2343           if( pruneGarbage && !visited.contains( hrn ) ) {
2344             traverseHeapRegionNodes( hrn,
2345                                      bw,
2346                                      null,
2347                                      visited,
2348                                      writeReferencers,
2349                                      hideSubsetReachability,
2350                                      hideEdgeTaints );
2351           }
2352
2353           bw.write( "  "+vn.toString()+
2354                     " -> "+hrn.toString()+
2355                     edge.toStringDOT( hideSubsetReachability )+
2356                     ";\n" );
2357         }
2358       }
2359     }
2360
2361     bw.write( "}\n" );
2362     bw.close();
2363   }
2364
2365   protected void traverseHeapRegionNodes( HeapRegionNode hrn,
2366                                           BufferedWriter bw,
2367                                           TempDescriptor td,
2368                                           Set<HeapRegionNode> visited,
2369                                           boolean writeReferencers,
2370                                           boolean hideSubsetReachability,
2371                                           boolean hideEdgeTaints
2372                                           ) throws java.io.IOException {
2373
2374     if( visited.contains( hrn ) ) {
2375       return;
2376     }
2377     visited.add( hrn );
2378
2379     bw.write( "  "+hrn.toString()+
2380               hrn.toStringDOT( hideSubsetReachability )+
2381               ";\n" );
2382
2383     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
2384     while( childRegionsItr.hasNext() ) {
2385       RefEdge        edge     = childRegionsItr.next();
2386       HeapRegionNode hrnChild = edge.getDst();
2387
2388       bw.write( "  "+hrn.toString()+
2389                 " -> "+hrnChild.toString()+
2390                 edge.toStringDOT( hideSubsetReachability )+
2391                 ";\n");
2392
2393       traverseHeapRegionNodes( hrnChild,
2394                                bw,
2395                                td,
2396                                visited,
2397                                writeReferencers,
2398                                hideSubsetReachability,
2399                                hideEdgeTaints );
2400     }
2401   }
2402
2403 }