Robust/src/Analysis/Disjoint/ReachGraph.java

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