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.unionORpreds( 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.unionORpreds( 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.unionORpreds( 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.unionORpreds( 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().containsIgnorePreds( c.getStateToMatch() )
1084               != null
1085               ) {
1086             changesToPass = Canonical.add( changesToPass, c );
1087           }
1088         }
1089
1090         if( !changesToPass.isEmpty() ) {
1091           if( !nodePlannedChanges.containsKey( m ) ) {
1092             nodePlannedChanges.put( m, ChangeSet.factory() );
1093           }
1094
1095           ChangeSet currentChanges = nodePlannedChanges.get( m );
1096
1097           if( !changesToPass.isSubset( currentChanges ) ) {
1098
1099             nodePlannedChanges.put( m,
1100                                     Canonical.union( currentChanges,
1101                                                      changesToPass
1102                                                      )
1103                                     );
1104             todoNodes.add( m );
1105           }
1106         }
1107       }
1108
1109       todoNodes.remove( n );
1110     }
1111
1112     // then apply all of the changes for each node at once
1113     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1114     while( itrMap.hasNext() ) {
1115       Map.Entry      me = (Map.Entry)      itrMap.next();
1116       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1117       ChangeSet      C  = (ChangeSet)      me.getValue();
1118
1119       // this propagation step is with respect to one change,
1120       // so we capture the full change from the old alpha:
1121       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1122                                                       C,
1123                                                       true
1124                                                       );
1125       // but this propagation may be only one of many concurrent
1126       // possible changes, so keep a running union with the node's
1127       // partially updated new alpha set
1128       n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1129                                       localDelta
1130                                       )
1131                      );
1132
1133       nodesWithNewAlpha.add( n );
1134     }
1135
1136     propagateTokensOverEdges( todoEdges,
1137                               edgePlannedChanges,
1138                               edgesWithNewBeta
1139                               );
1140   }
1141
1142
1143   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1144                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1145                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1146
1147     // first propagate all change tuples everywhere they can go
1148     while( !todoEdges.isEmpty() ) {
1149       RefEdge edgeE = todoEdges.iterator().next();
1150       todoEdges.remove( edgeE );
1151
1152       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1153         edgePlannedChanges.put( edgeE,
1154                                 ChangeSet.factory()
1155                                 );
1156       }
1157
1158       ChangeSet C = edgePlannedChanges.get( edgeE );
1159
1160       ChangeSet changesToPass = ChangeSet.factory();
1161
1162       Iterator<ChangeTuple> itrC = C.iterator();
1163       while( itrC.hasNext() ) {
1164         ChangeTuple c = itrC.next();
1165         if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1166             != null
1167             ) {
1168           changesToPass = Canonical.add( changesToPass, c );
1169         }
1170       }
1171
1172       RefSrcNode rsn = edgeE.getSrc();
1173
1174       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1175         HeapRegionNode n = (HeapRegionNode) rsn;
1176
1177         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1178         while( referItr.hasNext() ) {
1179           RefEdge edgeF = referItr.next();
1180
1181           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1182             edgePlannedChanges.put( edgeF,
1183                                     ChangeSet.factory()
1184                                     );
1185           }
1186
1187           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1188
1189           if( !changesToPass.isSubset( currentChanges ) ) {
1190             todoEdges.add( edgeF );
1191             edgePlannedChanges.put( edgeF,
1192                                     Canonical.union( currentChanges,
1193                                                      changesToPass
1194                                                      )
1195                                     );
1196           }
1197         }
1198       }
1199     }
1200
1201     // then apply all of the changes for each edge at once
1202     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1203     while( itrMap.hasNext() ) {
1204       Map.Entry me = (Map.Entry) itrMap.next();
1205       RefEdge   e  = (RefEdge)   me.getKey();
1206       ChangeSet C  = (ChangeSet) me.getValue();
1207
1208       // this propagation step is with respect to one change,
1209       // so we capture the full change from the old beta:
1210       ReachSet localDelta =
1211         Canonical.applyChangeSet( e.getBeta(),
1212                                   C,
1213                                   true
1214                                   );
1215
1216       // but this propagation may be only one of many concurrent
1217       // possible changes, so keep a running union with the edge's
1218       // partially updated new beta set
1219       e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1220                                      localDelta
1221                                      )
1222                     );
1223
1224       edgesWithNewBeta.add( e );
1225     }
1226   }
1227
1228
1229   // used in makeCalleeView below to decide if there is
1230   // already an appropriate out-of-context edge in a callee
1231   // view graph for merging, or null if a new one will be added
1232   protected RefEdge
1233     getOutOfContextReferenceTo( HeapRegionNode hrn,
1234                                 TypeDescriptor srcType,
1235                                 TypeDescriptor refType,
1236                                 String         refField ) {
1237     assert belongsToThis( hrn );
1238
1239     HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1240     if( hrnInContext == null ) {
1241       return null;
1242     }
1243
1244     Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1245     while( refItr.hasNext() ) {
1246       RefEdge re = refItr.next();
1247
1248       assert belongsToThis( re.getSrc() );
1249       assert belongsToThis( re.getDst() );
1250
1251       if( !(re.getSrc() instanceof HeapRegionNode) ) {
1252         continue;
1253       }
1254
1255       HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1256       if( !hrnSrc.isOutOfContext() ) {
1257         continue;
1258       }
1259
1260       if( srcType == null ) {
1261         if( hrnSrc.getType() != null ) {
1262           continue;
1263         }
1264       } else {
1265         if( !srcType.equals( hrnSrc.getType() ) ) {
1266           continue;
1267         }
1268       }
1269
1270       if( !re.typeEquals( refType ) ) {
1271         continue;
1272       }
1273
1274       if( !re.fieldEquals( refField ) ) {
1275         continue;
1276       }
1277
1278       // tada!  We found it!
1279       return re;
1280     }
1281
1282     return null;
1283   }
1284
1285   // used below to convert a ReachSet to its callee-context
1286   // equivalent with respect to allocation sites in this graph
1287   protected ReachSet toCalleeContext( Set<ReachTuple> oocTuples,
1288                                       ReachSet        rs,
1289                                       Integer         hrnID,
1290                                       TempDescriptor  tdSrc,
1291                                       Integer         hrnSrcID,
1292                                       Integer         hrnDstID,
1293                                       TypeDescriptor  type,
1294                                       String          field,
1295                                       boolean         outOfContext
1296                                       ) {
1297     ReachSet out = ReachSet.factory();
1298
1299     Iterator<ReachState> itr = rs.iterator();
1300     while( itr.hasNext() ) {
1301       ReachState stateCaller = itr.next();
1302
1303       ReachState stateCallee = stateCaller;
1304
1305       Iterator<AllocSite> asItr = allocSites.iterator();
1306       while( asItr.hasNext() ) {
1307         AllocSite as = asItr.next();
1308
1309         ReachState stateNew = ReachState.factory();
1310         Iterator<ReachTuple> rtItr = stateCallee.iterator();
1311         while( rtItr.hasNext() ) {
1312           ReachTuple rt = rtItr.next();
1313
1314           // only translate this tuple if it is in the out-context bag
1315           if( !oocTuples.contains( rt ) ) {
1316             stateNew = Canonical.add( stateNew, rt );
1317             continue;
1318           }
1319
1320           int age = as.getAgeCategory( rt.getHrnID() );
1321
1322           // this is the current mapping, where 0, 1, 2S were allocated
1323           // in the current context, 0?, 1? and 2S? were allocated in a
1324           // previous context, and we're translating to a future context
1325           //
1326           // 0    -> 0?
1327           // 1    -> 1?
1328           // 2S   -> 2S?
1329           // 2S*  -> 2S?*
1330           //
1331           // 0?   -> 2S?
1332           // 1?   -> 2S?
1333           // 2S?  -> 2S?
1334           // 2S?* -> 2S?*
1335
1336           if( age == AllocSite.AGE_notInThisSite ) {
1337             // things not from the site just go back in
1338             stateNew = Canonical.add( stateNew, rt );
1339
1340           } else if( age == AllocSite.AGE_summary ||
1341                      rt.isOutOfContext()
1342                      ) {
1343             // the in-context summary and all existing out-of-context
1344             // stuff all become
1345             stateNew = Canonical.add( stateNew,
1346                                       ReachTuple.factory( as.getSummary(),
1347                                                           true, // multi
1348                                                           rt.getArity(),
1349                                                           true  // out-of-context
1350                                                           )
1351                                       );
1352           } else {
1353             // otherwise everything else just goes to an out-of-context
1354             // version, everything else the same
1355             Integer I = as.getAge( rt.getHrnID() );
1356             assert I != null;
1357
1358             assert !rt.isMultiObject();
1359
1360             stateNew = Canonical.add( stateNew,
1361                                       ReachTuple.factory( rt.getHrnID(),
1362                                                           rt.isMultiObject(),
1363                                                           rt.getArity(),
1364                                                           true  // out-of-context
1365                                                           )
1366                                       );
1367           }
1368         }
1369
1370         stateCallee = stateNew;
1371       }
1372
1373
1374       ExistPredSet preds;
1375
1376       if( outOfContext ) {
1377         preds = predsEmpty;
1378       } else {
1379         ExistPred pred;
1380         if( hrnID != null ) {
1381           assert tdSrc    == null;
1382           assert hrnSrcID == null;
1383           assert hrnDstID == null;
1384           pred = ExistPred.factory( hrnID,
1385                                     stateCaller );
1386         } else {
1387           assert tdSrc != null || hrnSrcID != null;
1388           assert hrnDstID != null;
1389           pred = ExistPred.factory( tdSrc,
1390                                     hrnSrcID,
1391                                     hrnDstID,
1392                                     type,
1393                                     field,
1394                                     stateCaller,
1395                                     false );
1396         }
1397         preds = ExistPredSet.factory( pred );
1398       }
1399
1400       stateCallee = Canonical.attach( stateCallee,
1401                                       preds );
1402
1403       out = Canonical.add( out,
1404                            stateCallee
1405                            );
1406
1407     }
1408     assert out.isCanonical();
1409     return out;
1410   }
1411
1412   // used below to convert a ReachSet to its caller-context
1413   // equivalent with respect to allocation sites in this graph
1414   protected ReachSet
1415     toCallerContext( ReachSet                            rs,
1416                      Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1417                      ) {
1418     ReachSet out = ReachSet.factory();
1419
1420     Iterator<ReachState> itr = rs.iterator();
1421     while( itr.hasNext() ) {
1422       ReachState stateCallee = itr.next();
1423
1424       if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1425
1426         // starting from one callee state...
1427         ReachSet rsCaller = ReachSet.factory( stateCallee );
1428
1429         // possibly branch it into many states, which any
1430         // allocation site might do, so lots of derived states
1431         Iterator<AllocSite> asItr = allocSites.iterator();
1432         while( asItr.hasNext() ) {
1433           AllocSite as = asItr.next();
1434           rsCaller = Canonical.toCallerContext( rsCaller, as );
1435         }
1436
1437         // then before adding each derived, now caller-context
1438         // states to the output, attach the appropriate pred
1439         // based on the source callee state
1440         Iterator<ReachState> stateItr = rsCaller.iterator();
1441         while( stateItr.hasNext() ) {
1442           ReachState stateCaller = stateItr.next();
1443           stateCaller = Canonical.attach( stateCaller,
1444                                           calleeStatesSatisfied.get( stateCallee )
1445                                           );
1446           out = Canonical.add( out,
1447                                  stateCaller
1448                                  );
1449         }
1450       }
1451     }
1452
1453     assert out.isCanonical();
1454     return out;
1455   }
1456
1457   // used below to convert a ReachSet to an equivalent
1458   // version with shadow IDs merged into unshadowed IDs
1459   protected ReachSet unshadow( ReachSet rs ) {
1460     ReachSet out = rs;
1461     Iterator<AllocSite> asItr = allocSites.iterator();
1462     while( asItr.hasNext() ) {
1463       AllocSite as = asItr.next();
1464       out = Canonical.unshadow( out, as );
1465     }
1466     assert out.isCanonical();
1467     return out;
1468   }
1469
1470
1471   // use this method to make a new reach graph that is
1472   // what heap the FlatMethod callee from the FlatCall
1473   // would start with reaching from its arguments in
1474   // this reach graph
1475   public ReachGraph
1476     makeCalleeView( FlatCall     fc,
1477                     FlatMethod   fmCallee,
1478                     Set<Integer> callerNodeIDsCopiedToCallee,
1479                     boolean      writeDebugDOTs
1480                     ) {
1481
1482
1483     // first traverse this context to find nodes and edges
1484     //  that will be callee-reachable
1485     Set<HeapRegionNode> reachableCallerNodes =
1486       new HashSet<HeapRegionNode>();
1487
1488     // caller edges between callee-reachable nodes
1489     Set<RefEdge> reachableCallerEdges =
1490       new HashSet<RefEdge>();
1491
1492     // caller edges from arg vars, and the matching param index
1493     // because these become a special edge in callee
1494     Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1495       new Hashtable<RefEdge, Integer>();
1496
1497     // caller edges from local vars or callee-unreachable nodes
1498     // (out-of-context sources) to callee-reachable nodes
1499     Set<RefEdge> oocCallerEdges =
1500       new HashSet<RefEdge>();
1501
1502
1503     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1504
1505       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1506       VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1507
1508       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1509       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1510
1511       toVisitInCaller.add( vnArgCaller );
1512
1513       while( !toVisitInCaller.isEmpty() ) {
1514         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1515         toVisitInCaller.remove( rsnCaller );
1516         visitedInCaller.add( rsnCaller );
1517
1518         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1519         while( itrRefEdges.hasNext() ) {
1520           RefEdge        reCaller  = itrRefEdges.next();
1521           HeapRegionNode hrnCaller = reCaller.getDst();
1522
1523           callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1524           reachableCallerNodes.add( hrnCaller );
1525
1526           if( reCaller.getSrc() instanceof HeapRegionNode ) {
1527             reachableCallerEdges.add( reCaller );
1528           } else {
1529             if( rsnCaller.equals( vnArgCaller ) ) {
1530               reachableCallerArgEdges2paramIndex.put( reCaller, i );
1531             } else {
1532               oocCallerEdges.add( reCaller );
1533             }
1534           }
1535
1536           if( !visitedInCaller.contains( hrnCaller ) ) {
1537             toVisitInCaller.add( hrnCaller );
1538           }
1539
1540         } // end edge iteration
1541       } // end visiting heap nodes in caller
1542     } // end iterating over parameters as starting points
1543
1544
1545     // now collect out-of-context reach tuples and
1546     // more out-of-context edges
1547     Set<ReachTuple> oocTuples = new HashSet<ReachTuple>();
1548
1549     Iterator<Integer> itrInContext =
1550       callerNodeIDsCopiedToCallee.iterator();
1551     while( itrInContext.hasNext() ) {
1552       Integer        hrnID                 = itrInContext.next();
1553       HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1554
1555       Iterator<RefEdge> itrMightCross =
1556         hrnCallerAndInContext.iteratorToReferencers();
1557       while( itrMightCross.hasNext() ) {
1558         RefEdge edgeMightCross = itrMightCross.next();
1559
1560         RefSrcNode rsnCallerAndOutContext =
1561           edgeMightCross.getSrc();
1562
1563         if( rsnCallerAndOutContext instanceof VariableNode ) {
1564           // variables do not have out-of-context reach states,
1565           // so jump out now
1566           oocCallerEdges.add( edgeMightCross );
1567           continue;
1568         }
1569
1570         HeapRegionNode hrnCallerAndOutContext =
1571           (HeapRegionNode) rsnCallerAndOutContext;
1572
1573         // is this source node out-of-context?
1574         if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1575           // no, skip this edge
1576           continue;
1577         }
1578
1579         // okay, we got one
1580         oocCallerEdges.add( edgeMightCross );
1581
1582         // add all reach tuples on the node to list
1583         // of things that are out-of-context: insight
1584         // if this node is reachable from someting that WAS
1585         // in-context, then this node should already be in-context
1586         Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1587         while( stateItr.hasNext() ) {
1588           ReachState state = stateItr.next();
1589
1590           Iterator<ReachTuple> rtItr = state.iterator();
1591           while( rtItr.hasNext() ) {
1592             ReachTuple rt = rtItr.next();
1593
1594             oocTuples.add( rt );
1595           }
1596         }
1597       }
1598     }
1599
1600
1601     // the callee view is a new graph: DON'T MODIFY *THIS* graph
1602     ReachGraph rg = new ReachGraph();
1603
1604     // add nodes to callee graph
1605     Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1606     while( hrnItr.hasNext() ) {
1607       HeapRegionNode hrnCaller = hrnItr.next();
1608
1609       assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1610       assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1611
1612       ExistPred    pred  = ExistPred.factory( hrnCaller.getID(), null );
1613       ExistPredSet preds = ExistPredSet.factory( pred );
1614
1615       rg.createNewHeapRegionNode( hrnCaller.getID(),
1616                                   hrnCaller.isSingleObject(),
1617                                   hrnCaller.isNewSummary(),
1618                                   hrnCaller.isFlagged(),
1619                                   false, // out-of-context?
1620                                   hrnCaller.getType(),
1621                                   hrnCaller.getAllocSite(),
1622                                   toCalleeContext( oocTuples,
1623                                                    hrnCaller.getInherent(),      // in state
1624                                                    hrnCaller.getID(),            // node pred
1625                                                    null, null, null, null, null, // edge pred
1626                                                    false ),                      // ooc pred
1627                                   toCalleeContext( oocTuples,
1628                                                    hrnCaller.getAlpha(),         // in state
1629                                                    hrnCaller.getID(),            // node pred
1630                                                    null, null, null, null, null, // edge pred
1631                                                    false ),                      // ooc pred
1632                                   preds,
1633                                   hrnCaller.getDescription()
1634                                   );
1635     }
1636
1637     // add param edges to callee graph
1638     Iterator argEdges =
1639       reachableCallerArgEdges2paramIndex.entrySet().iterator();
1640     while( argEdges.hasNext() ) {
1641       Map.Entry me    = (Map.Entry) argEdges.next();
1642       RefEdge   reArg = (RefEdge)   me.getKey();
1643       Integer   index = (Integer)   me.getValue();
1644
1645       TempDescriptor arg = fmCallee.getParameter( index );
1646
1647       VariableNode vnCallee =
1648         rg.getVariableNodeFromTemp( arg );
1649
1650       HeapRegionNode hrnDstCaller = reArg.getDst();
1651       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1652       assert hrnDstCallee != null;
1653
1654       ExistPred pred =
1655         ExistPred.factory( arg,
1656                            null,
1657                            hrnDstCallee.getID(),
1658                            reArg.getType(),
1659                            reArg.getField(),
1660                            null,
1661                            false ); // out-of-context
1662
1663       ExistPredSet preds =
1664         ExistPredSet.factory( pred );
1665
1666       RefEdge reCallee =
1667         new RefEdge( vnCallee,
1668                      hrnDstCallee,
1669                      reArg.getType(),
1670                      reArg.getField(),
1671                      toCalleeContext( oocTuples,
1672                                       reArg.getBeta(),      // in state
1673                                       null,                 // node pred
1674                                       arg,                  // edge pred
1675                                       null,                 // edge pred
1676                                       hrnDstCallee.getID(), // edge pred
1677                                       reArg.getType(),      // edge pred
1678                                       reArg.getField(),     // edge pred
1679                                       false ),              // ooc pred
1680                      preds
1681                      );
1682
1683       rg.addRefEdge( vnCallee,
1684                      hrnDstCallee,
1685                      reCallee
1686                      );
1687     }
1688
1689     // add in-context edges to callee graph
1690     Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1691     while( reItr.hasNext() ) {
1692       RefEdge    reCaller  = reItr.next();
1693       RefSrcNode rsnCaller = reCaller.getSrc();
1694       assert rsnCaller instanceof HeapRegionNode;
1695       HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1696       HeapRegionNode hrnDstCaller = reCaller.getDst();
1697
1698       HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1699       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1700       assert hrnSrcCallee != null;
1701       assert hrnDstCallee != null;
1702
1703       ExistPred pred =
1704         ExistPred.factory( null,
1705                            hrnSrcCallee.getID(),
1706                            hrnDstCallee.getID(),
1707                            reCaller.getType(),
1708                            reCaller.getField(),
1709                            null,
1710                            false ); // out-of-context
1711
1712       ExistPredSet preds =
1713         ExistPredSet.factory( pred );
1714
1715       RefEdge reCallee =
1716         new RefEdge( hrnSrcCallee,
1717                      hrnDstCallee,
1718                      reCaller.getType(),
1719                      reCaller.getField(),
1720                      toCalleeContext( oocTuples,
1721                                       reCaller.getBeta(),   // in state
1722                                       null,                 // node pred
1723                                       null,                 // edge pred
1724                                       hrnSrcCallee.getID(), // edge pred
1725                                       hrnDstCallee.getID(), // edge pred
1726                                       reCaller.getType(),   // edge pred
1727                                       reCaller.getField(),  // edge pred
1728                                       false ),              // ooc pred
1729                      preds
1730                      );
1731
1732       rg.addRefEdge( hrnSrcCallee,
1733                      hrnDstCallee,
1734                      reCallee
1735                      );
1736     }
1737
1738     // add out-of-context edges to callee graph
1739     reItr = oocCallerEdges.iterator();
1740     while( reItr.hasNext() ) {
1741       RefEdge        reCaller     = reItr.next();
1742       RefSrcNode     rsnCaller    = reCaller.getSrc();
1743       HeapRegionNode hrnDstCaller = reCaller.getDst();
1744       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1745       assert hrnDstCallee != null;
1746
1747       TypeDescriptor oocNodeType;
1748       ReachSet       oocReach;
1749       TempDescriptor oocPredSrcTemp = null;
1750       Integer        oocPredSrcID   = null;
1751
1752       if( rsnCaller instanceof VariableNode ) {
1753         VariableNode vnCaller = (VariableNode) rsnCaller;
1754         oocNodeType    = null;
1755         oocReach       = rsetEmpty;
1756         oocPredSrcTemp = vnCaller.getTempDescriptor();
1757
1758       } else {
1759         HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1760         assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1761         oocNodeType  = hrnSrcCaller.getType();
1762         oocReach     = hrnSrcCaller.getAlpha();
1763         oocPredSrcID = hrnSrcCaller.getID();
1764       }
1765
1766       ExistPred pred =
1767         ExistPred.factory( oocPredSrcTemp,
1768                            oocPredSrcID,
1769                            hrnDstCallee.getID(),
1770                            reCaller.getType(),
1771                            reCaller.getField(),
1772                            null,
1773                            true ); // out-of-context
1774
1775       ExistPredSet preds =
1776         ExistPredSet.factory( pred );
1777
1778       RefEdge oocEdgeExisting =
1779         rg.getOutOfContextReferenceTo( hrnDstCallee,
1780                                        oocNodeType,
1781                                        reCaller.getType(),
1782                                        reCaller.getField()
1783                                        );
1784
1785       if( oocEdgeExisting == null ) {
1786           // for consistency, map one out-of-context "identifier"
1787           // to one heap region node id, otherwise no convergence
1788         String oocid = "oocid"+
1789           fmCallee+
1790           hrnDstCallee.getIDString()+
1791           oocNodeType+
1792           reCaller.getType()+
1793           reCaller.getField();
1794
1795         Integer oocHrnID = oocid2hrnid.get( oocid );
1796
1797         HeapRegionNode hrnCalleeAndOutContext;
1798
1799         if( oocHrnID == null ) {
1800
1801           hrnCalleeAndOutContext =
1802             rg.createNewHeapRegionNode( null,  // ID
1803                                         false, // single object?
1804                                         false, // new summary?
1805                                         false, // flagged?
1806                                         true,  // out-of-context?
1807                                         oocNodeType,
1808                                         null,  // alloc site, shouldn't be used
1809                                         toCalleeContext( oocTuples,
1810                                                          oocReach,                     // in state
1811                                                          null,                         // node pred
1812                                                          null, null, null, null, null, // edge pred
1813                                                          true                          // ooc pred
1814                                                          ), // inherent
1815                                         toCalleeContext( oocTuples,
1816                                                          oocReach,                     // in state
1817                                                          null,                         // node pred
1818                                                          null, null, null, null, null, // edge pred
1819                                                          true                          // ooc pred
1820                                                          ), // alpha
1821                                         preds,
1822                                         "out-of-context"
1823                                         );
1824
1825           oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1826
1827         } else {
1828
1829           // the mapping already exists, so see if node is there
1830           hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1831
1832           if( hrnCalleeAndOutContext == null ) {
1833             // nope, make it
1834             hrnCalleeAndOutContext =
1835               rg.createNewHeapRegionNode( oocHrnID,  // ID
1836                                           false, // single object?
1837                                           false, // new summary?
1838                                           false, // flagged?
1839                                           true,  // out-of-context?
1840                                           oocNodeType,
1841                                           null,  // alloc site, shouldn't be used
1842                                           toCalleeContext( oocTuples,
1843                                                            oocReach,                     // in state
1844                                                            null,                         // node pred
1845                                                            null, null, null, null, null, // edge pred
1846                                                            true                          // ooc pred
1847                                                            ), // inherent
1848                                           toCalleeContext( oocTuples,
1849                                                            oocReach,                     // in state
1850                                                            null,                         // node pred
1851                                                            null, null, null, null, null, // edge pred
1852                                                            true                          // ooc pred
1853                                                            ), // alpha
1854                                           preds,
1855                                           "out-of-context"
1856                                           );
1857           }
1858         }
1859
1860         rg.addRefEdge( hrnCalleeAndOutContext,
1861                        hrnDstCallee,
1862                        new RefEdge( hrnCalleeAndOutContext,
1863                                     hrnDstCallee,
1864                                     reCaller.getType(),
1865                                     reCaller.getField(),
1866                                     toCalleeContext( oocTuples,
1867                                                      reCaller.getBeta(),   // in state
1868                                                      null,                 // node pred
1869                                                      oocPredSrcTemp,       // edge pred
1870                                                      oocPredSrcID,         // edge pred
1871                                                      hrnDstCaller.getID(), // edge pred
1872                                                      reCaller.getType(),   // edge pred
1873                                                      reCaller.getField(),  // edge pred
1874                                                      false                 // ooc pred
1875                                                      ),
1876                                     preds
1877                                     )
1878                        );
1879
1880         } else {
1881         // the out-of-context edge already exists
1882         oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1883                                                   toCalleeContext( oocTuples,
1884                                                                    reCaller.getBeta(),   // in state
1885                                                                    null,                 // node pred
1886                                                                    oocPredSrcTemp,       // edge pred
1887                                                                    oocPredSrcID,         // edge pred
1888                                                                    hrnDstCaller.getID(), // edge pred
1889                                                                    reCaller.getType(),   // edge pred
1890                                                                    reCaller.getField(),  // edge pred
1891                                                                    false                 // ooc pred
1892                                                                    )
1893                                                   )
1894                                  );
1895
1896         oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1897                                                   reCaller.getPreds()
1898                                                   )
1899                                   );
1900
1901       }
1902     }
1903
1904
1905     if( writeDebugDOTs ) {
1906       try {
1907         rg.writeGraph( "calleeview",
1908                        resolveMethodDebugDOTwriteLabels,
1909                        resolveMethodDebugDOTselectTemps,
1910                        resolveMethodDebugDOTpruneGarbage,
1911                        resolveMethodDebugDOThideSubsetReach,
1912                        resolveMethodDebugDOThideEdgeTaints );
1913       } catch( IOException e ) {}
1914     }
1915
1916     return rg;
1917   }
1918
1919   private static Hashtable<String, Integer> oocid2hrnid =
1920     new Hashtable<String, Integer>();
1921
1922
1923   // useful since many graphs writes in the method call debug code
1924   private static boolean resolveMethodDebugDOTwriteLabels     = true;
1925   private static boolean resolveMethodDebugDOTselectTemps     = true;
1926   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
1927   private static boolean resolveMethodDebugDOThideSubsetReach = false;
1928   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
1929
1930
1931
1932   public void
1933     resolveMethodCall( FlatCall     fc,
1934                        FlatMethod   fmCallee,
1935                        ReachGraph   rgCallee,
1936                        Set<Integer> callerNodeIDsCopiedToCallee,
1937                        boolean      writeDebugDOTs
1938                        ) {
1939
1940
1941     if( writeDebugDOTs ) {
1942       try {
1943         rgCallee.writeGraph( "callee",
1944                        resolveMethodDebugDOTwriteLabels,
1945                        resolveMethodDebugDOTselectTemps,
1946                        resolveMethodDebugDOTpruneGarbage,
1947                        resolveMethodDebugDOThideSubsetReach,
1948                        resolveMethodDebugDOThideEdgeTaints );
1949
1950         writeGraph( "caller00In",
1951                     resolveMethodDebugDOTwriteLabels,
1952                     resolveMethodDebugDOTselectTemps,
1953                     resolveMethodDebugDOTpruneGarbage,
1954                     resolveMethodDebugDOThideSubsetReach,
1955                     resolveMethodDebugDOThideEdgeTaints,
1956                     callerNodeIDsCopiedToCallee );
1957       } catch( IOException e ) {}
1958     }
1959
1960
1961     // method call transfer function steps:
1962     // 1. Use current callee-reachable heap (CRH) to test callee
1963     //    predicates and mark what will be coming in.
1964     // 2. Wipe CRH out of caller.
1965     // 3. Transplant marked callee parts in:
1966     //    a) bring in nodes
1967     //    b) bring in callee -> callee edges
1968     //    c) resolve out-of-context -> callee edges
1969     //    d) assign return value
1970     // 4. Collapse shadow nodes down
1971     // 5. Global sweep it.
1972
1973
1974
1975     // 1. mark what callee elements have satisfied predicates
1976     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1977       new Hashtable<HeapRegionNode, ExistPredSet>();
1978
1979     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1980       new Hashtable<RefEdge, ExistPredSet>();
1981
1982     Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1983       new Hashtable<ReachState, ExistPredSet>();
1984
1985     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1986       new Hashtable< RefEdge, Set<RefSrcNode> >();
1987
1988     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
1989     while( meItr.hasNext() ) {
1990       Map.Entry      me        = (Map.Entry)      meItr.next();
1991       Integer        id        = (Integer)        me.getKey();
1992       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
1993
1994       // if a callee element's predicates are satisfied then a set
1995       // of CALLER predicates is returned: they are the predicates
1996       // that the callee element moved into the caller context
1997       // should have, and it is inefficient to find this again later
1998       ExistPredSet predsIfSatis =
1999         hrnCallee.getPreds().isSatisfiedBy( this,
2000                                             callerNodeIDsCopiedToCallee
2001                                             );
2002       if( predsIfSatis != null ) {
2003         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
2004       } else {
2005         // otherwise don't bother looking at edges to this node
2006         continue;
2007       }
2008
2009       // since the node is coming over, find out which reach
2010       // states on it should come over, too
2011       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2012       while( stateItr.hasNext() ) {
2013         ReachState stateCallee = stateItr.next();
2014
2015         predsIfSatis =
2016           stateCallee.getPreds().isSatisfiedBy( this,
2017                                                 callerNodeIDsCopiedToCallee
2018                                                 );
2019         if( predsIfSatis != null ) {
2020           calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2021         }
2022       }
2023
2024       // then look at edges to the node
2025       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2026       while( reItr.hasNext() ) {
2027         RefEdge    reCallee  = reItr.next();
2028         RefSrcNode rsnCallee = reCallee.getSrc();
2029
2030         // (caller local variables to in-context heap regions)
2031         // have an (out-of-context heap region -> in-context heap region)
2032         // abstraction in the callEE, so its true we never need to
2033         // look at a (var node -> heap region) edge in callee to bring
2034         // those over for the call site transfer.  What about (param var->heap region)
2035         // edges in callee? They are dealt with below this loop.
2036         // So, yes, at this point skip (var->region) edges in callee
2037         if( rsnCallee instanceof VariableNode ) {
2038           continue;
2039         }
2040
2041         // first see if the source is out-of-context, and only
2042         // proceed with this edge if we find some caller-context
2043         // matches
2044         HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2045         boolean matchedOutOfContext = false;
2046
2047         if( hrnSrcCallee.isOutOfContext() ) {
2048
2049           assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2050           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2051
2052           HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2053           Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2054           while( reDstItr.hasNext() ) {
2055             // the edge and field (either possibly null) must match
2056             RefEdge reCaller = reDstItr.next();
2057
2058             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
2059                 !reCaller.fieldEquals( reCallee.getField() )
2060                 ) {
2061               continue;
2062             }
2063
2064             RefSrcNode rsnCaller = reCaller.getSrc();
2065             if( rsnCaller instanceof VariableNode ) {
2066               // a variable node matches an OOC region with null type
2067               if( hrnSrcCallee.getType() != null ) {
2068                 continue;
2069               }
2070
2071             } else {
2072               // otherwise types should match
2073               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2074               if( hrnSrcCallee.getType() == null ) {
2075                 if( hrnCallerSrc.getType() != null ) {
2076                   continue;
2077                 }
2078               } else {
2079                 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2080                   continue;
2081                 }
2082               }
2083             }
2084
2085             rsnCallers.add( rsnCaller );
2086             matchedOutOfContext = true;
2087           }
2088
2089           if( !rsnCallers.isEmpty() ) {
2090             calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2091           }
2092         }
2093
2094         if( hrnSrcCallee.isOutOfContext() &&
2095             !matchedOutOfContext ) {
2096           continue;
2097         }
2098
2099         predsIfSatis =
2100           reCallee.getPreds().isSatisfiedBy( this,
2101                                              callerNodeIDsCopiedToCallee
2102                                              );
2103         if( predsIfSatis != null ) {
2104           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2105
2106           // since the edge is coming over, find out which reach
2107           // states on it should come over, too
2108           stateItr = reCallee.getBeta().iterator();
2109           while( stateItr.hasNext() ) {
2110             ReachState stateCallee = stateItr.next();
2111
2112             predsIfSatis =
2113               stateCallee.getPreds().isSatisfiedBy( this,
2114                                                     callerNodeIDsCopiedToCallee
2115                                                     );
2116             if( predsIfSatis != null ) {
2117               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2118             }
2119           }
2120
2121         }
2122
2123       }
2124     }
2125
2126     // test param -> HRN edges, also
2127     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
2128
2129       // parameter defined here is the symbol in the callee
2130       TempDescriptor tdParam  = fmCallee.getParameter( i );
2131       VariableNode   vnCallee = rgCallee.getVariableNodeFromTemp( tdParam );
2132
2133       Iterator<RefEdge> reItr = vnCallee.iteratorToReferencees();
2134       while( reItr.hasNext() ) {
2135         RefEdge reCallee = reItr.next();
2136
2137         ExistPredSet ifDst =
2138           reCallee.getDst().getPreds().isSatisfiedBy( this,
2139                                                       callerNodeIDsCopiedToCallee
2140                                                       );
2141         if( ifDst == null ) {
2142           continue;
2143         }
2144
2145         ExistPredSet predsIfSatis =
2146           reCallee.getPreds().isSatisfiedBy( this,
2147                                              callerNodeIDsCopiedToCallee
2148                                              );
2149         if( predsIfSatis != null ) {
2150           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2151
2152           // since the edge is coming over, find out which reach
2153           // states on it should come over, too
2154           Iterator<ReachState> stateItr = reCallee.getBeta().iterator();
2155           while( stateItr.hasNext() ) {
2156             ReachState stateCallee = stateItr.next();
2157
2158             predsIfSatis =
2159               stateCallee.getPreds().isSatisfiedBy( this,
2160                                                     callerNodeIDsCopiedToCallee
2161                                                     );
2162             if( predsIfSatis != null ) {
2163               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2164             }
2165           }
2166
2167         }
2168       }
2169     }
2170
2171
2172
2173
2174     if( writeDebugDOTs ) {
2175       try {
2176         writeGraph( "caller20BeforeWipe",
2177                     resolveMethodDebugDOTwriteLabels,
2178                     resolveMethodDebugDOTselectTemps,
2179                     resolveMethodDebugDOTpruneGarbage,
2180                     resolveMethodDebugDOThideSubsetReach,
2181                     resolveMethodDebugDOThideEdgeTaints );
2182       } catch( IOException e ) {}
2183     }
2184
2185
2186     // 2. predicates tested, ok to wipe out caller part
2187     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2188     while( hrnItr.hasNext() ) {
2189       Integer        hrnID     = hrnItr.next();
2190       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2191       assert hrnCaller != null;
2192
2193       // when clearing off nodes, also eliminate variable
2194       // references
2195       wipeOut( hrnCaller, true );
2196     }
2197
2198
2199
2200     if( writeDebugDOTs ) {
2201       try {
2202         writeGraph( "caller30BeforeAddingNodes",
2203                     resolveMethodDebugDOTwriteLabels,
2204                     resolveMethodDebugDOTselectTemps,
2205                     resolveMethodDebugDOTpruneGarbage,
2206                     resolveMethodDebugDOThideSubsetReach,
2207                     resolveMethodDebugDOThideEdgeTaints );
2208       } catch( IOException e ) {}
2209     }
2210
2211
2212     // 3. callee elements with satisfied preds come in, note that
2213     //    the mapping of elements satisfied to preds is like this:
2214     //    A callee element EE has preds EEp that are satisfied by
2215     //    some caller element ER.  We bring EE into the caller
2216     //    context as ERee with the preds of ER, namely ERp, which
2217     //    in the following algorithm is the value in the mapping
2218
2219     // 3.a) nodes
2220     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2221     while( satisItr.hasNext() ) {
2222       Map.Entry      me        = (Map.Entry)      satisItr.next();
2223       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2224       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
2225
2226       // TODO: I think its true that the current implementation uses
2227       // the type of the OOC region and the predicates OF THE EDGE from
2228       // it to link everything up in caller context, so that's why we're
2229       // skipping this... maybe that's a sillier way to do it?
2230       if( hrnCallee.isOutOfContext() ) {
2231         continue;
2232       }
2233
2234       AllocSite as = hrnCallee.getAllocSite();
2235       allocSites.add( as );
2236
2237       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2238
2239       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2240       if( hrnCaller == null ) {
2241         hrnCaller =
2242           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
2243                                    hrnCallee.isSingleObject(), // single object?
2244                                    hrnCallee.isNewSummary(),   // summary?
2245                                    hrnCallee.isFlagged(),      // flagged?
2246                                    false,                      // out-of-context?
2247                                    hrnCallee.getType(),        // type
2248                                    hrnCallee.getAllocSite(),   // allocation site
2249                                    toCallerContext( hrnCallee.getInherent(),
2250                                                     calleeStatesSatisfied  ),    // inherent reach
2251                                    null,                       // current reach
2252                                    predsEmpty,                 // predicates
2253                                    hrnCallee.getDescription()  // description
2254                                    );
2255       } else {
2256         assert hrnCaller.isWiped();
2257       }
2258
2259       hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2260                                            calleeStatesSatisfied
2261                                            )
2262                           );
2263
2264       hrnCaller.setPreds( preds );
2265     }
2266
2267
2268
2269     if( writeDebugDOTs ) {
2270       try {
2271         writeGraph( "caller31BeforeAddingEdges",
2272                     resolveMethodDebugDOTwriteLabels,
2273                     resolveMethodDebugDOTselectTemps,
2274                     resolveMethodDebugDOTpruneGarbage,
2275                     resolveMethodDebugDOThideSubsetReach,
2276                     resolveMethodDebugDOThideEdgeTaints );
2277       } catch( IOException e ) {}
2278     }
2279
2280
2281     // set these up during the next procedure so after
2282     // the caller has all of its nodes and edges put
2283     // back together we can propagate the callee's
2284     // reach changes backwards into the caller graph
2285     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2286
2287     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2288       new Hashtable<RefEdge, ChangeSet>();
2289
2290
2291     // 3.b) callee -> callee edges AND out-of-context -> callee
2292     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2293     while( satisItr.hasNext() ) {
2294       Map.Entry    me       = (Map.Entry)    satisItr.next();
2295       RefEdge      reCallee = (RefEdge)      me.getKey();
2296       ExistPredSet preds    = (ExistPredSet) me.getValue();
2297
2298       HeapRegionNode hrnDstCallee = reCallee.getDst();
2299       AllocSite      asDst        = hrnDstCallee.getAllocSite();
2300       allocSites.add( asDst );
2301
2302       Integer hrnIDDstShadow =
2303         asDst.getShadowIDfromID( hrnDstCallee.getID() );
2304
2305       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2306       assert hrnDstCaller != null;
2307
2308
2309       RefSrcNode rsnCallee = reCallee.getSrc();
2310
2311       Set<RefSrcNode> rsnCallers =
2312         new HashSet<RefSrcNode>();
2313
2314       Set<RefSrcNode> oocCallers =
2315         calleeEdges2oocCallerSrcMatches.get( reCallee );
2316
2317       boolean oocEdges = false;
2318
2319       if( oocCallers == null ) {
2320         // there are no out-of-context matches, so it's
2321         // either a param/arg var or one in-context heap region
2322         if( rsnCallee instanceof VariableNode ) {
2323           // variable -> node in the callee should only
2324           // come into the caller if its from a param var
2325           VariableNode   vnCallee = (VariableNode) rsnCallee;
2326           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2327           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
2328                                                             tdParam );
2329           if( tdArg == null ) {
2330             // this means the variable isn't a parameter, its local
2331             // to the callee so we ignore it in call site transfer
2332             // shouldn't this NEVER HAPPEN?
2333             assert false;
2334           }
2335           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2336           oocEdges = true;
2337
2338         } else {
2339           // otherwise source is in context, one region
2340           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2341
2342           // translate an in-context node to shadow
2343           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2344           allocSites.add( asSrc );
2345
2346           Integer hrnIDSrcShadow =
2347             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2348
2349           HeapRegionNode hrnSrcCallerShadow =
2350             this.id2hrn.get( hrnIDSrcShadow );
2351
2352           if( hrnSrcCallerShadow == null ) {
2353             hrnSrcCallerShadow =
2354               createNewHeapRegionNode( hrnIDSrcShadow,                // id or null to generate a new one
2355                                        hrnSrcCallee.isSingleObject(), // single object?
2356                                        hrnSrcCallee.isNewSummary(),   // summary?
2357                                        hrnSrcCallee.isFlagged(),      // flagged?
2358                                        false,                         // out-of-context?
2359                                        hrnSrcCallee.getType(),        // type
2360                                        hrnSrcCallee.getAllocSite(),   // allocation site
2361                                        toCallerContext( hrnSrcCallee.getInherent(),
2362                                                         calleeStatesSatisfied ),    // inherent reach
2363                                        toCallerContext( hrnSrcCallee.getAlpha(),
2364                                                         calleeStatesSatisfied ),       // current reach
2365                                        predsEmpty,                    // predicates
2366                                        hrnSrcCallee.getDescription()  // description
2367                                        );
2368           }
2369
2370           rsnCallers.add( hrnSrcCallerShadow );
2371         }
2372
2373       } else {
2374         // otherwise we have a set of out-of-context srcs
2375         // that should NOT be translated to shadow nodes
2376         assert !oocCallers.isEmpty();
2377         rsnCallers.addAll( oocCallers );
2378         oocEdges = true;
2379       }
2380
2381       // now make all caller edges we've identified from
2382       // this callee edge with a satisfied predicate
2383       assert !rsnCallers.isEmpty();
2384       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2385       while( rsnItr.hasNext() ) {
2386         RefSrcNode rsnCaller = rsnItr.next();
2387
2388         RefEdge reCaller = new RefEdge( rsnCaller,
2389                                         hrnDstCaller,
2390                                         reCallee.getType(),
2391                                         reCallee.getField(),
2392                                         toCallerContext( reCallee.getBeta(),
2393                                                          calleeStatesSatisfied ),
2394                                         preds
2395                                         );
2396
2397         ChangeSet cs = ChangeSet.factory();
2398         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2399         while( rsItr.hasNext() ) {
2400           ReachState   state          = rsItr.next();
2401           ExistPredSet predsPreCallee = state.getPreds();
2402
2403           if( state.isEmpty() ) {
2404             continue;
2405           }
2406
2407           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2408           while( predItr.hasNext() ) {
2409             ExistPred pred = predItr.next();
2410             ReachState old = pred.ne_state;
2411
2412             if( old == null ) {
2413               old = rstateEmpty;
2414             }
2415
2416             cs = Canonical.add( cs,
2417                                 ChangeTuple.factory( old,
2418                                                      state
2419                                                      )
2420                                 );
2421           }
2422         }
2423
2424         // look to see if an edge with same field exists
2425         // and merge with it, otherwise just add the edge
2426         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2427                                                          reCallee.getType(),
2428                                                          reCallee.getField()
2429                                                          );
2430         if( edgeExisting != null ) {
2431           edgeExisting.setBeta(
2432                                Canonical.unionORpreds( edgeExisting.getBeta(),
2433                                                 reCaller.getBeta()
2434                                                 )
2435                                );
2436           edgeExisting.setPreds(
2437                                 Canonical.join( edgeExisting.getPreds(),
2438                                                 reCaller.getPreds()
2439                                                 )
2440                                 );
2441
2442           // for reach propagation
2443           if( !cs.isEmpty() ) {
2444             edgePlannedChanges.put(
2445                                    edgeExisting,
2446                                    Canonical.union( edgePlannedChanges.get( edgeExisting ),
2447                                                     cs
2448                                                     )
2449                                     );
2450           }
2451
2452         } else {
2453           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2454
2455           // for reach propagation
2456           if( !cs.isEmpty() ) {
2457             edgesForPropagation.add( reCaller );
2458             assert !edgePlannedChanges.containsKey( reCaller );
2459             edgePlannedChanges.put( reCaller, cs );
2460           }
2461         }
2462       }
2463     }
2464
2465
2466
2467
2468
2469     if( writeDebugDOTs ) {
2470       try {
2471         writeGraph( "caller35BeforeAssignReturnValue",
2472                     resolveMethodDebugDOTwriteLabels,
2473                     resolveMethodDebugDOTselectTemps,
2474                     resolveMethodDebugDOTpruneGarbage,
2475                     resolveMethodDebugDOThideSubsetReach,
2476                     resolveMethodDebugDOThideEdgeTaints );
2477       } catch( IOException e ) {}
2478     }
2479
2480
2481
2482     // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2483     // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2484     // EDGES, JUST BRINGING THEM ALL!  It'll work for now, over approximation
2485
2486     // 3.d) handle return value assignment if needed
2487     TempDescriptor returnTemp = fc.getReturnTemp();
2488     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
2489
2490       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2491       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2492
2493       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2494       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2495       while( reCalleeItr.hasNext() ) {
2496         RefEdge        reCallee     = reCalleeItr.next();
2497         HeapRegionNode hrnDstCallee = reCallee.getDst();
2498
2499         // some edge types are not possible return values when we can
2500         // see what type variable we are assigning it to
2501         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2502           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2503                               reCallee+" for return temp "+returnTemp );
2504           // prune
2505           continue;
2506         }
2507
2508         AllocSite asDst = hrnDstCallee.getAllocSite();
2509         allocSites.add( asDst );
2510
2511         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2512
2513         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2514         if( hrnDstCaller == null ) {
2515           hrnDstCaller =
2516             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
2517                                      hrnDstCallee.isSingleObject(), // single object?
2518                                      hrnDstCallee.isNewSummary(),   // summary?
2519                                      hrnDstCallee.isFlagged(),      // flagged?
2520                                      false,                         // out-of-context?
2521                                      hrnDstCallee.getType(),        // type
2522                                      hrnDstCallee.getAllocSite(),   // allocation site
2523                                      toCallerContext( hrnDstCallee.getInherent(),
2524                                                       calleeStatesSatisfied  ),    // inherent reach
2525                                      toCallerContext( hrnDstCallee.getAlpha(),
2526                                                       calleeStatesSatisfied  ),    // current reach
2527                                      predsTrue,                     // predicates
2528                                      hrnDstCallee.getDescription()  // description
2529                                      );
2530         } else {
2531           assert hrnDstCaller.isWiped();
2532         }
2533
2534         TypeDescriptor tdNewEdge =
2535           mostSpecificType( reCallee.getType(),
2536                             hrnDstCallee.getType(),
2537                             hrnDstCaller.getType()
2538                             );
2539
2540         RefEdge reCaller = new RefEdge( vnLhsCaller,
2541                                         hrnDstCaller,
2542                                         tdNewEdge,
2543                                         null,
2544                                         toCallerContext( reCallee.getBeta(),
2545                                                          calleeStatesSatisfied ),
2546                                         predsTrue
2547                                         );
2548
2549         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2550       }
2551     }
2552
2553
2554
2555     if( writeDebugDOTs ) {
2556       try {
2557         writeGraph( "caller38propagateReach",
2558                     resolveMethodDebugDOTwriteLabels,
2559                     resolveMethodDebugDOTselectTemps,
2560                     resolveMethodDebugDOTpruneGarbage,
2561                     resolveMethodDebugDOThideSubsetReach,
2562                     resolveMethodDebugDOThideEdgeTaints );
2563       } catch( IOException e ) {}
2564     }
2565
2566     // propagate callee reachability changes to the rest
2567     // of the caller graph edges
2568     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2569
2570     propagateTokensOverEdges( edgesForPropagation, // source edges
2571                               edgePlannedChanges,  // map src edge to change set
2572                               edgesUpdated );      // list of updated edges
2573
2574     // commit beta' (beta<-betaNew)
2575     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2576     while( edgeItr.hasNext() ) {
2577       edgeItr.next().applyBetaNew();
2578     }
2579
2580
2581
2582
2583
2584
2585     if( writeDebugDOTs ) {
2586       try {
2587         writeGraph( "caller40BeforeShadowMerge",
2588                     resolveMethodDebugDOTwriteLabels,
2589                     resolveMethodDebugDOTselectTemps,
2590                     resolveMethodDebugDOTpruneGarbage,
2591                     resolveMethodDebugDOThideSubsetReach,
2592                     resolveMethodDebugDOThideEdgeTaints );
2593       } catch( IOException e ) {}
2594     }
2595
2596
2597     // 4) merge shadow nodes so alloc sites are back to k
2598     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2599     while( asItr.hasNext() ) {
2600       // for each allocation site do the following to merge
2601       // shadow nodes (newest from callee) with any existing
2602       // look for the newest normal and newest shadow "slot"
2603       // not being used, transfer normal to shadow.  Keep
2604       // doing this until there are no more normal nodes, or
2605       // no empty shadow slots: then merge all remaining normal
2606       // nodes into the shadow summary.  Finally, convert all
2607       // shadow to their normal versions.
2608       AllocSite as = asItr.next();
2609       int ageNorm = 0;
2610       int ageShad = 0;
2611       while( ageNorm < allocationDepth &&
2612              ageShad < allocationDepth ) {
2613
2614         // first, are there any normal nodes left?
2615         Integer        idNorm  = as.getIthOldest( ageNorm );
2616         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2617         if( hrnNorm == null ) {
2618           // no, this age of normal node not in the caller graph
2619           ageNorm++;
2620           continue;
2621         }
2622
2623         // yes, a normal node exists, is there an empty shadow
2624         // "slot" to transfer it onto?
2625         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2626         if( !hrnShad.isWiped() ) {
2627           // no, this age of shadow node is not empty
2628           ageShad++;
2629           continue;
2630         }
2631
2632         // yes, this shadow node is empty
2633         transferOnto( hrnNorm, hrnShad );
2634         ageNorm++;
2635         ageShad++;
2636       }
2637
2638       // now, while there are still normal nodes but no shadow
2639       // slots, merge normal nodes into the shadow summary
2640       while( ageNorm < allocationDepth ) {
2641
2642         // first, are there any normal nodes left?
2643         Integer        idNorm  = as.getIthOldest( ageNorm );
2644         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2645         if( hrnNorm == null ) {
2646           // no, this age of normal node not in the caller graph
2647           ageNorm++;
2648           continue;
2649         }
2650
2651         // yes, a normal node exists, so get the shadow summary
2652         HeapRegionNode summShad = getSummaryNode( as, true );
2653         mergeIntoSummary( hrnNorm, summShad );
2654         ageNorm++;
2655       }
2656
2657       // if there is a normal summary, merge it into shadow summary
2658       Integer        idNorm   = as.getSummary();
2659       HeapRegionNode summNorm = id2hrn.get( idNorm );
2660       if( summNorm != null ) {
2661         HeapRegionNode summShad = getSummaryNode( as, true );
2662         mergeIntoSummary( summNorm, summShad );
2663       }
2664
2665       // finally, flip all existing shadow nodes onto the normal
2666       for( int i = 0; i < allocationDepth; ++i ) {
2667         Integer        idShad  = as.getIthOldestShadow( i );
2668         HeapRegionNode hrnShad = id2hrn.get( idShad );
2669         if( hrnShad != null ) {
2670           // flip it
2671           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2672           assert hrnNorm.isWiped();
2673           transferOnto( hrnShad, hrnNorm );
2674         }
2675       }
2676
2677       Integer        idShad   = as.getSummaryShadow();
2678       HeapRegionNode summShad = id2hrn.get( idShad );
2679       if( summShad != null ) {
2680         summNorm = getSummaryNode( as, false );
2681         transferOnto( summShad, summNorm );
2682       }
2683     }
2684
2685
2686     if( writeDebugDOTs ) {
2687       try {
2688         writeGraph( "caller45BeforeUnshadow",
2689                     resolveMethodDebugDOTwriteLabels,
2690                     resolveMethodDebugDOTselectTemps,
2691                     resolveMethodDebugDOTpruneGarbage,
2692                     resolveMethodDebugDOThideSubsetReach,
2693                     resolveMethodDebugDOThideEdgeTaints );
2694       } catch( IOException e ) {}
2695     }
2696
2697
2698     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2699     while( itrAllHRNodes.hasNext() ) {
2700       Map.Entry      me  = (Map.Entry)      itrAllHRNodes.next();
2701       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2702
2703       hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2704
2705       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2706       while( itrEdges.hasNext() ) {
2707         RefEdge re = itrEdges.next();
2708         re.setBeta( unshadow( re.getBeta() ) );
2709       }
2710     }
2711
2712
2713
2714     if( writeDebugDOTs ) {
2715       try {
2716         writeGraph( "caller50BeforeGlobalSweep",
2717                     resolveMethodDebugDOTwriteLabels,
2718                     resolveMethodDebugDOTselectTemps,
2719                     resolveMethodDebugDOTpruneGarbage,
2720                     resolveMethodDebugDOThideSubsetReach,
2721                     resolveMethodDebugDOThideEdgeTaints );
2722       } catch( IOException e ) {}
2723     }
2724
2725
2726     // 5.
2727     if( !DISABLE_GLOBAL_SWEEP ) {
2728       globalSweep();
2729     }
2730
2731
2732
2733     if( writeDebugDOTs ) {
2734       try {
2735         writeGraph( "caller90AfterTransfer",
2736                     resolveMethodDebugDOTwriteLabels,
2737                     resolveMethodDebugDOTselectTemps,
2738                     resolveMethodDebugDOTpruneGarbage,
2739                     resolveMethodDebugDOThideSubsetReach,
2740                     resolveMethodDebugDOThideEdgeTaints );
2741       } catch( IOException e ) {}
2742     }
2743   }
2744
2745
2746
2747   ////////////////////////////////////////////////////
2748   //
2749   //  Abstract garbage collection simply removes
2750   //  heap region nodes that are not mechanically
2751   //  reachable from a root set.  This step is
2752   //  essential for testing node and edge existence
2753   //  predicates efficiently
2754   //
2755   ////////////////////////////////////////////////////
2756   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2757
2758     // calculate a root set, will be different for Java
2759     // version of analysis versus Bamboo version
2760     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2761
2762     // visit every variable in graph while building root
2763     // set, and do iterating on a copy, so we can remove
2764     // dead variables while we're at this
2765     Iterator makeCopyItr = td2vn.entrySet().iterator();
2766     Set      entrysCopy  = new HashSet();
2767     while( makeCopyItr.hasNext() ) {
2768       entrysCopy.add( makeCopyItr.next() );
2769     }
2770
2771     Iterator eItr = entrysCopy.iterator();
2772     while( eItr.hasNext() ) {
2773       Map.Entry      me = (Map.Entry)      eItr.next();
2774       TempDescriptor td = (TempDescriptor) me.getKey();
2775       VariableNode   vn = (VariableNode)   me.getValue();
2776
2777       if( liveSet.contains( td ) ) {
2778         toVisit.add( vn );
2779
2780       } else {
2781         // dead var, remove completely from graph
2782         td2vn.remove( td );
2783         clearRefEdgesFrom( vn, null, null, true );
2784       }
2785     }
2786
2787     // everything visited in a traversal is
2788     // considered abstractly live
2789     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2790
2791     while( !toVisit.isEmpty() ) {
2792       RefSrcNode rsn = toVisit.iterator().next();
2793       toVisit.remove( rsn );
2794       visited.add( rsn );
2795
2796       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2797       while( hrnItr.hasNext() ) {
2798         RefEdge        edge = hrnItr.next();
2799         HeapRegionNode hrn  = edge.getDst();
2800
2801         if( !visited.contains( hrn ) ) {
2802           toVisit.add( hrn );
2803         }
2804       }
2805     }
2806
2807     // get a copy of the set to iterate over because
2808     // we're going to monkey with the graph when we
2809     // identify a garbage node
2810     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2811     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2812     while( hrnItr.hasNext() ) {
2813       hrnAllPrior.add( hrnItr.next() );
2814     }
2815
2816     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2817     while( hrnAllItr.hasNext() ) {
2818       HeapRegionNode hrn = hrnAllItr.next();
2819
2820       if( !visited.contains( hrn ) ) {
2821
2822         // heap region nodes are compared across ReachGraph
2823         // objects by their integer ID, so when discarding
2824         // garbage nodes we must also discard entries in
2825         // the ID -> heap region hashtable.
2826         id2hrn.remove( hrn.getID() );
2827
2828         // RefEdge objects are two-way linked between
2829         // nodes, so when a node is identified as garbage,
2830         // actively clear references to and from it so
2831         // live nodes won't have dangling RefEdge's
2832         wipeOut( hrn, true );
2833
2834         // if we just removed the last node from an allocation
2835         // site, it should be taken out of the ReachGraph's list
2836         AllocSite as = hrn.getAllocSite();
2837         if( !hasNodesOf( as ) ) {
2838           allocSites.remove( as );
2839         }
2840       }
2841     }
2842   }
2843
2844   protected boolean hasNodesOf( AllocSite as ) {
2845     if( id2hrn.containsKey( as.getSummary() ) ) {
2846       return true;
2847     }
2848
2849     for( int i = 0; i < allocationDepth; ++i ) {
2850       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2851         return true;
2852       }
2853     }
2854     return false;
2855   }
2856
2857
2858   ////////////////////////////////////////////////////
2859   //
2860   //  This global sweep is an optional step to prune
2861   //  reachability sets that are not internally
2862   //  consistent with the global graph.  It should be
2863   //  invoked after strong updates or method calls.
2864   //
2865   ////////////////////////////////////////////////////
2866   public void globalSweep() {
2867
2868     // boldB is part of the phase 1 sweep
2869     // it has an in-context table and an out-of-context table
2870     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2871       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2872
2873     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2874       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2875
2876     // visit every heap region to initialize alphaNew and betaNew,
2877     // and make a map of every hrnID to the source nodes it should
2878     // propagate forward from.  In-context flagged hrnID's propagate
2879     // from only the in-context node they name, but out-of-context
2880     // ID's may propagate from several out-of-context nodes
2881     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2882       new Hashtable< Integer, Set<HeapRegionNode> >();
2883
2884     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2885       new Hashtable< Integer, Set<HeapRegionNode> >();
2886
2887
2888     Iterator itrHrns = id2hrn.entrySet().iterator();
2889     while( itrHrns.hasNext() ) {
2890       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2891       Integer        hrnID = (Integer)        me.getKey();
2892       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2893
2894       // assert that this node and incoming edges have clean alphaNew
2895       // and betaNew sets, respectively
2896       assert rsetEmpty.equals( hrn.getAlphaNew() );
2897
2898       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2899       while( itrRers.hasNext() ) {
2900         RefEdge edge = itrRers.next();
2901         assert rsetEmpty.equals( edge.getBetaNew() );
2902       }
2903
2904       // calculate boldB for this flagged node, or out-of-context node
2905       if( hrn.isFlagged() ) {
2906         assert !hrn.isOutOfContext();
2907         assert !icID2srcs.containsKey( hrn.getID() );
2908         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2909         srcs.add( hrn );
2910         icID2srcs.put( hrn.getID(), srcs );
2911       }
2912
2913       if( hrn.isOutOfContext() ) {
2914         assert !hrn.isFlagged();
2915
2916         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2917         while( stateItr.hasNext() ) {
2918           ReachState state = stateItr.next();
2919
2920           Iterator<ReachTuple> rtItr = state.iterator();
2921           while( rtItr.hasNext() ) {
2922             ReachTuple rt = rtItr.next();
2923             assert rt.isOutOfContext();
2924
2925             Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2926             if( srcs == null ) {
2927               srcs = new HashSet<HeapRegionNode>();
2928             }
2929             srcs.add( hrn );
2930             oocID2srcs.put( rt.getHrnID(), srcs );
2931           }
2932         }
2933       }
2934     }
2935
2936     // calculate boldB for all hrnIDs identified by the above
2937     // node traversal, propagating from every source
2938     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2939
2940       Integer             hrnID;
2941       Set<HeapRegionNode> srcs;
2942       boolean             inContext;
2943
2944       if( !icID2srcs.isEmpty() ) {
2945         Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2946         hrnID = (Integer)             me.getKey();
2947         srcs  = (Set<HeapRegionNode>) me.getValue();
2948         inContext = true;
2949         icID2srcs.remove( hrnID );
2950
2951       } else {
2952         assert !oocID2srcs.isEmpty();
2953
2954         Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2955         hrnID = (Integer)             me.getKey();
2956         srcs  = (Set<HeapRegionNode>) me.getValue();
2957         inContext = false;
2958         oocID2srcs.remove( hrnID );
2959       }
2960
2961
2962       Hashtable<RefEdge, ReachSet> boldB_f =
2963         new Hashtable<RefEdge, ReachSet>();
2964
2965       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2966
2967       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2968       while( hrnItr.hasNext() ) {
2969         HeapRegionNode hrn = hrnItr.next();
2970
2971         assert workSetEdges.isEmpty();
2972
2973         // initial boldB_f constraints
2974         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2975         while( itrRees.hasNext() ) {
2976           RefEdge edge = itrRees.next();
2977
2978           assert !boldB_f.containsKey( edge );
2979           boldB_f.put( edge, edge.getBeta() );
2980
2981           assert !workSetEdges.contains( edge );
2982           workSetEdges.add( edge );
2983         }
2984
2985         // enforce the boldB_f constraint at edges until we reach a fixed point
2986         while( !workSetEdges.isEmpty() ) {
2987           RefEdge edge = workSetEdges.iterator().next();
2988           workSetEdges.remove( edge );
2989
2990           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2991           while( itrPrime.hasNext() ) {
2992             RefEdge edgePrime = itrPrime.next();
2993
2994             ReachSet prevResult   = boldB_f.get( edgePrime );
2995             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2996                                                             edgePrime.getBeta()
2997                                                             );
2998
2999             if( prevResult == null ||
3000                 Canonical.unionORpreds( prevResult,
3001                                         intersection ).size()
3002                 > prevResult.size()
3003                 ) {
3004
3005               if( prevResult == null ) {
3006                 boldB_f.put( edgePrime,
3007                              Canonical.unionORpreds( edgePrime.getBeta(),
3008                                                      intersection
3009                                                      )
3010                              );
3011               } else {
3012                 boldB_f.put( edgePrime,
3013                              Canonical.unionORpreds( prevResult,
3014                                                      intersection
3015                                                      )
3016                              );
3017               }
3018               workSetEdges.add( edgePrime );
3019             }
3020           }
3021         }
3022       }
3023
3024       if( inContext ) {
3025         boldBic.put( hrnID, boldB_f );
3026       } else {
3027         boldBooc.put( hrnID, boldB_f );
3028       }
3029     }
3030
3031
3032     // use boldB to prune hrnIDs from alpha states that are impossible
3033     // and propagate the differences backwards across edges
3034     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3035
3036     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3037       new Hashtable<RefEdge, ChangeSet>();
3038
3039
3040     itrHrns = id2hrn.entrySet().iterator();
3041     while( itrHrns.hasNext() ) {
3042       Map.Entry      me    = (Map.Entry)      itrHrns.next();
3043       Integer        hrnID = (Integer)        me.getKey();
3044       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3045
3046       // out-of-context nodes don't participate in the
3047       // global sweep, they serve as sources for the pass
3048       // performed above
3049       if( hrn.isOutOfContext() ) {
3050         continue;
3051       }
3052
3053       // the inherent states of a region are the exception
3054       // to removal as the global sweep prunes
3055       ReachTuple rtException = ReachTuple.factory( hrnID,
3056                                                    !hrn.isSingleObject(),
3057                                                    ReachTuple.ARITY_ONE,
3058                                                    false // out-of-context
3059                                                    );
3060
3061       ChangeSet cts = ChangeSet.factory();
3062
3063       // mark hrnIDs for removal
3064       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3065       while( stateItr.hasNext() ) {
3066         ReachState stateOld = stateItr.next();
3067
3068         ReachState markedHrnIDs = ReachState.factory();
3069
3070         Iterator<ReachTuple> rtItr = stateOld.iterator();
3071         while( rtItr.hasNext() ) {
3072           ReachTuple rtOld = rtItr.next();
3073
3074           // never remove the inherent hrnID from a flagged region
3075           // because it is trivially satisfied
3076           if( hrn.isFlagged() ) {
3077             if( rtOld == rtException ) {
3078               continue;
3079             }
3080           }
3081
3082           // does boldB allow this hrnID?
3083           boolean foundState = false;
3084           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3085           while( incidentEdgeItr.hasNext() ) {
3086             RefEdge incidentEdge = incidentEdgeItr.next();
3087
3088             Hashtable<RefEdge, ReachSet> B;
3089             if( rtOld.isOutOfContext() ) {
3090               B = boldBooc.get( rtOld.getHrnID() );
3091             } else {
3092               assert id2hrn.containsKey( rtOld.getHrnID() );
3093               B = boldBic.get( rtOld.getHrnID() );
3094             }
3095
3096             if( B != null ) {
3097               ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3098               if( boldB_rtOld_incident != null &&
3099                   boldB_rtOld_incident.contains( stateOld ) ) {
3100                 foundState = true;
3101               }
3102             }
3103           }
3104
3105           if( !foundState ) {
3106             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3107           }
3108         }
3109
3110         // if there is nothing marked, just move on
3111         if( markedHrnIDs.isEmpty() ) {
3112           hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3113                                           stateOld
3114                                           )
3115                            );
3116           continue;
3117         }
3118
3119         // remove all marked hrnIDs and establish a change set that should
3120         // propagate backwards over edges from this node
3121         ReachState statePruned = ReachState.factory();
3122         rtItr = stateOld.iterator();
3123         while( rtItr.hasNext() ) {
3124           ReachTuple rtOld = rtItr.next();
3125
3126           if( !markedHrnIDs.containsTuple( rtOld ) ) {
3127             statePruned = Canonical.add( statePruned, rtOld );
3128           }
3129         }
3130         assert !stateOld.equals( statePruned );
3131
3132         hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3133                                         statePruned
3134                                         )
3135                          );
3136         ChangeTuple ct = ChangeTuple.factory( stateOld,
3137                                               statePruned
3138                                               );
3139         cts = Canonical.add( cts, ct );
3140       }
3141
3142       // throw change tuple set on all incident edges
3143       if( !cts.isEmpty() ) {
3144         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3145         while( incidentEdgeItr.hasNext() ) {
3146           RefEdge incidentEdge = incidentEdgeItr.next();
3147
3148           edgesForPropagation.add( incidentEdge );
3149
3150           if( edgePlannedChanges.get( incidentEdge ) == null ) {
3151             edgePlannedChanges.put( incidentEdge, cts );
3152           } else {
3153             edgePlannedChanges.put(
3154                                    incidentEdge,
3155                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
3156                                                     cts
3157                                                     )
3158                                     );
3159           }
3160         }
3161       }
3162     }
3163
3164     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3165
3166     propagateTokensOverEdges( edgesForPropagation,
3167                               edgePlannedChanges,
3168                               edgesUpdated );
3169
3170     // at the end of the 1st phase reference edges have
3171     // beta, betaNew that correspond to beta and betaR
3172     //
3173     // commit beta<-betaNew, so beta=betaR and betaNew
3174     // will represent the beta' calculation in 2nd phase
3175     //
3176     // commit alpha<-alphaNew because it won't change
3177     HashSet<RefEdge> res = new HashSet<RefEdge>();
3178
3179     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3180     while( nodeItr.hasNext() ) {
3181       HeapRegionNode hrn = nodeItr.next();
3182       hrn.applyAlphaNew();
3183       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3184       while( itrRes.hasNext() ) {
3185         res.add( itrRes.next() );
3186       }
3187     }
3188
3189
3190     // 2nd phase
3191     Iterator<RefEdge> edgeItr = res.iterator();
3192     while( edgeItr.hasNext() ) {
3193       RefEdge        edge = edgeItr.next();
3194       HeapRegionNode hrn  = edge.getDst();
3195
3196       // commit results of last phase
3197       if( edgesUpdated.contains( edge ) ) {
3198         edge.applyBetaNew();
3199       }
3200
3201       // compute intial condition of 2nd phase
3202       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3203                                                hrn.getAlpha()
3204                                                )
3205                        );
3206     }
3207
3208     // every edge in the graph is the initial workset
3209     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3210     while( !edgeWorkSet.isEmpty() ) {
3211       RefEdge edgePrime = edgeWorkSet.iterator().next();
3212       edgeWorkSet.remove( edgePrime );
3213
3214       RefSrcNode rsn = edgePrime.getSrc();
3215       if( !(rsn instanceof HeapRegionNode) ) {
3216         continue;
3217       }
3218       HeapRegionNode hrn = (HeapRegionNode) rsn;
3219
3220       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3221       while( itrEdge.hasNext() ) {
3222         RefEdge edge = itrEdge.next();
3223
3224         ReachSet prevResult = edge.getBetaNew();
3225         assert prevResult != null;
3226
3227         ReachSet intersection =
3228           Canonical.intersection( edge.getBeta(),
3229                                   edgePrime.getBetaNew()
3230                                   );
3231
3232         if( Canonical.unionORpreds( prevResult,
3233                                     intersection
3234                                     ).size()
3235             > prevResult.size()
3236             ) {
3237
3238           edge.setBetaNew(
3239                           Canonical.unionORpreds( prevResult,
3240                                                   intersection
3241                                                   )
3242                            );
3243           edgeWorkSet.add( edge );
3244         }
3245       }
3246     }
3247
3248     // commit beta' (beta<-betaNew)
3249     edgeItr = res.iterator();
3250     while( edgeItr.hasNext() ) {
3251       edgeItr.next().applyBetaNew();
3252     }
3253   }
3254
3255
3256
3257   ////////////////////////////////////////////////////
3258   // high-level merge operations
3259   ////////////////////////////////////////////////////
3260   public void merge_sameMethodContext( ReachGraph rg ) {
3261     // when merging two graphs that abstract the heap
3262     // of the same method context, we just call the
3263     // basic merge operation
3264     merge( rg );
3265   }
3266
3267   public void merge_diffMethodContext( ReachGraph rg ) {
3268     // when merging graphs for abstract heaps in
3269     // different method contexts we should:
3270     // 1) age the allocation sites?
3271     merge( rg );
3272   }
3273
3274   ////////////////////////////////////////////////////
3275   // in merge() and equals() methods the suffix A
3276   // represents the passed in graph and the suffix
3277   // B refers to the graph in this object
3278   // Merging means to take the incoming graph A and
3279   // merge it into B, so after the operation graph B
3280   // is the final result.
3281   ////////////////////////////////////////////////////
3282   protected void merge( ReachGraph rg ) {
3283
3284     if( rg == null ) {
3285       return;
3286     }
3287
3288     mergeNodes     ( rg );
3289     mergeRefEdges  ( rg );
3290     mergeAllocSites( rg );
3291   }
3292
3293   protected void mergeNodes( ReachGraph rg ) {
3294
3295     // start with heap region nodes
3296     Set      sA = rg.id2hrn.entrySet();
3297     Iterator iA = sA.iterator();
3298     while( iA.hasNext() ) {
3299       Map.Entry      meA  = (Map.Entry)      iA.next();
3300       Integer        idA  = (Integer)        meA.getKey();
3301       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3302
3303       // if this graph doesn't have a node the
3304       // incoming graph has, allocate it
3305       if( !id2hrn.containsKey( idA ) ) {
3306         HeapRegionNode hrnB = hrnA.copy();
3307         id2hrn.put( idA, hrnB );
3308
3309       } else {
3310         // otherwise this is a node present in both graphs
3311         // so make the new reachability set a union of the
3312         // nodes' reachability sets
3313         HeapRegionNode hrnB = id2hrn.get( idA );
3314         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3315                                         hrnA.getAlpha()
3316                                         )
3317                        );
3318
3319         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3320                                        hrnA.getPreds()
3321                                        )
3322                        );
3323       }
3324     }
3325
3326     // now add any variable nodes that are in graph B but
3327     // not in A
3328     sA = rg.td2vn.entrySet();
3329     iA = sA.iterator();
3330     while( iA.hasNext() ) {
3331       Map.Entry      meA = (Map.Entry)      iA.next();
3332       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3333       VariableNode   lnA = (VariableNode)   meA.getValue();
3334
3335       // if the variable doesn't exist in B, allocate and add it
3336       VariableNode lnB = getVariableNodeFromTemp( tdA );
3337     }
3338   }
3339
3340   protected void mergeRefEdges( ReachGraph rg ) {
3341
3342     // between heap regions
3343     Set      sA = rg.id2hrn.entrySet();
3344     Iterator iA = sA.iterator();
3345     while( iA.hasNext() ) {
3346       Map.Entry      meA  = (Map.Entry)      iA.next();
3347       Integer        idA  = (Integer)        meA.getKey();
3348       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3349
3350       Iterator<RefEdge> heapRegionsItrA = hrnA.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         // idA -> idChildA, does this exist in B?
3358         assert id2hrn.containsKey( idA );
3359         HeapRegionNode hrnB        = id2hrn.get( idA );
3360         RefEdge        edgeToMerge = null;
3361
3362         Iterator<RefEdge> heapRegionsItrB = hrnB.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           // not intragraph equal
3373           if( idChildB.equals( idChildA ) &&
3374               edgeB.typeAndFieldEquals( edgeA ) ) {
3375
3376             edgeToMerge = edgeB;
3377           }
3378         }
3379
3380         // if the edge from A was not found in B,
3381         // add it to B.
3382         if( edgeToMerge == null ) {
3383           assert id2hrn.containsKey( idChildA );
3384           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3385           edgeToMerge = edgeA.copy();
3386           edgeToMerge.setSrc( hrnB );
3387           edgeToMerge.setDst( hrnChildB );
3388           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3389         }
3390         // otherwise, the edge already existed in both graphs
3391         // so merge their reachability sets
3392         else {
3393           // just replace this beta set with the union
3394           assert edgeToMerge != null;
3395           edgeToMerge.setBeta(
3396                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3397                                                edgeA.getBeta()
3398                                                )
3399                               );
3400           edgeToMerge.setPreds(
3401                                Canonical.join( edgeToMerge.getPreds(),
3402                                                edgeA.getPreds()
3403                                                )
3404                                );
3405         }
3406       }
3407     }
3408
3409     // and then again from variable nodes
3410     sA = rg.td2vn.entrySet();
3411     iA = sA.iterator();
3412     while( iA.hasNext() ) {
3413       Map.Entry      meA = (Map.Entry)      iA.next();
3414       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3415       VariableNode   vnA = (VariableNode)   meA.getValue();
3416
3417       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3418       while( heapRegionsItrA.hasNext() ) {
3419         RefEdge        edgeA     = heapRegionsItrA.next();
3420         HeapRegionNode hrnChildA = edgeA.getDst();
3421         Integer        idChildA  = hrnChildA.getID();
3422
3423         // at this point we know an edge in graph A exists
3424         // tdA -> idChildA, does this exist in B?
3425         assert td2vn.containsKey( tdA );
3426         VariableNode vnB         = td2vn.get( tdA );
3427         RefEdge      edgeToMerge = null;
3428
3429         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3430         while( heapRegionsItrB.hasNext() &&
3431                edgeToMerge == null          ) {
3432
3433           RefEdge        edgeB     = heapRegionsItrB.next();
3434           HeapRegionNode hrnChildB = edgeB.getDst();
3435           Integer        idChildB  = hrnChildB.getID();
3436
3437           // don't use the RefEdge.equals() here because
3438           // we're talking about existence between graphs
3439           if( idChildB.equals( idChildA ) &&
3440               edgeB.typeAndFieldEquals( edgeA ) ) {
3441
3442             edgeToMerge = edgeB;
3443           }
3444         }
3445
3446         // if the edge from A was not found in B,
3447         // add it to B.
3448         if( edgeToMerge == null ) {
3449           assert id2hrn.containsKey( idChildA );
3450           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3451           edgeToMerge = edgeA.copy();
3452           edgeToMerge.setSrc( vnB );
3453           edgeToMerge.setDst( hrnChildB );
3454           addRefEdge( vnB, hrnChildB, edgeToMerge );
3455         }
3456         // otherwise, the edge already existed in both graphs
3457         // so merge their reachability sets
3458         else {
3459           // just replace this beta set with the union
3460           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3461                                                 edgeA.getBeta()
3462                                                 )
3463                                );
3464           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3465                                                 edgeA.getPreds()
3466                                                 )
3467                                 );
3468         }
3469       }
3470     }
3471   }
3472
3473   protected void mergeAllocSites( ReachGraph rg ) {
3474     allocSites.addAll( rg.allocSites );
3475   }
3476
3477
3478   // it is necessary in the equals() member functions
3479   // to "check both ways" when comparing the data
3480   // structures of two graphs.  For instance, if all
3481   // edges between heap region nodes in graph A are
3482   // present and equal in graph B it is not sufficient
3483   // to say the graphs are equal.  Consider that there
3484   // may be edges in graph B that are not in graph A.
3485   // the only way to know that all edges in both graphs
3486   // are equally present is to iterate over both data
3487   // structures and compare against the other graph.
3488   public boolean equals( ReachGraph rg ) {
3489
3490     if( rg == null ) {
3491       return false;
3492     }
3493
3494     if( !areHeapRegionNodesEqual( rg ) ) {
3495       return false;
3496     }
3497
3498     if( !areVariableNodesEqual( rg ) ) {
3499       return false;
3500     }
3501
3502     if( !areRefEdgesEqual( rg ) ) {
3503       return false;
3504     }
3505
3506     // if everything is equal up to this point,
3507     // assert that allocSites is also equal--
3508     // this data is redundant but kept for efficiency
3509     assert allocSites.equals( rg.allocSites );
3510
3511     return true;
3512   }
3513
3514
3515   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3516
3517     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3518       return false;
3519     }
3520
3521     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3522       return false;
3523     }
3524
3525     return true;
3526   }
3527
3528   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3529                                                         ReachGraph rgB ) {
3530     Set      sA = rgA.id2hrn.entrySet();
3531     Iterator iA = sA.iterator();
3532     while( iA.hasNext() ) {
3533       Map.Entry      meA  = (Map.Entry)      iA.next();
3534       Integer        idA  = (Integer)        meA.getKey();
3535       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3536
3537       if( !rgB.id2hrn.containsKey( idA ) ) {
3538         return false;
3539       }
3540
3541       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3542       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3543         return false;
3544       }
3545     }
3546
3547     return true;
3548   }
3549
3550
3551   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3552
3553     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3554       return false;
3555     }
3556
3557     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3558       return false;
3559     }
3560
3561     return true;
3562   }
3563
3564   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3565                                                        ReachGraph rgB ) {
3566     Set      sA = rgA.td2vn.entrySet();
3567     Iterator iA = sA.iterator();
3568     while( iA.hasNext() ) {
3569       Map.Entry      meA = (Map.Entry)      iA.next();
3570       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3571
3572       if( !rgB.td2vn.containsKey( tdA ) ) {
3573         return false;
3574       }
3575     }
3576
3577     return true;
3578   }
3579
3580
3581   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3582     if( !areallREinAandBequal( this, rg ) ) {
3583       return false;
3584     }
3585
3586     return true;
3587   }
3588
3589   static protected boolean areallREinAandBequal( ReachGraph rgA,
3590                                                  ReachGraph rgB ) {
3591
3592     // check all the heap region->heap region edges
3593     Set      sA = rgA.id2hrn.entrySet();
3594     Iterator iA = sA.iterator();
3595     while( iA.hasNext() ) {
3596       Map.Entry      meA  = (Map.Entry)      iA.next();
3597       Integer        idA  = (Integer)        meA.getKey();
3598       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3599
3600       // we should have already checked that the same
3601       // heap regions exist in both graphs
3602       assert rgB.id2hrn.containsKey( idA );
3603
3604       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3605         return false;
3606       }
3607
3608       // then check every edge in B for presence in A, starting
3609       // from the same parent HeapRegionNode
3610       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3611
3612       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3613         return false;
3614       }
3615     }
3616
3617     // then check all the variable->heap region edges
3618     sA = rgA.td2vn.entrySet();
3619     iA = sA.iterator();
3620     while( iA.hasNext() ) {
3621       Map.Entry      meA = (Map.Entry)      iA.next();
3622       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3623       VariableNode   vnA = (VariableNode)   meA.getValue();
3624
3625       // we should have already checked that the same
3626       // label nodes exist in both graphs
3627       assert rgB.td2vn.containsKey( tdA );
3628
3629       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3630         return false;
3631       }
3632
3633       // then check every edge in B for presence in A, starting
3634       // from the same parent VariableNode
3635       VariableNode vnB = rgB.td2vn.get( tdA );
3636
3637       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3638         return false;
3639       }
3640     }
3641
3642     return true;
3643   }
3644
3645
3646   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3647                                                   RefSrcNode rnA,
3648                                                   ReachGraph rgB ) {
3649
3650     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3651     while( itrA.hasNext() ) {
3652       RefEdge        edgeA     = itrA.next();
3653       HeapRegionNode hrnChildA = edgeA.getDst();
3654       Integer        idChildA  = hrnChildA.getID();
3655
3656       assert rgB.id2hrn.containsKey( idChildA );
3657
3658       // at this point we know an edge in graph A exists
3659       // rnA -> idChildA, does this exact edge exist in B?
3660       boolean edgeFound = false;
3661
3662       RefSrcNode rnB = null;
3663       if( rnA instanceof HeapRegionNode ) {
3664         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3665         rnB = rgB.id2hrn.get( hrnA.getID() );
3666       } else {
3667         VariableNode vnA = (VariableNode) rnA;
3668         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3669       }
3670
3671       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3672       while( itrB.hasNext() ) {
3673         RefEdge        edgeB     = itrB.next();
3674         HeapRegionNode hrnChildB = edgeB.getDst();
3675         Integer        idChildB  = hrnChildB.getID();
3676
3677         if( idChildA.equals( idChildB ) &&
3678             edgeA.typeAndFieldEquals( edgeB ) ) {
3679
3680           // there is an edge in the right place with the right field,
3681           // but do they have the same attributes?
3682           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3683               edgeA.equalsPreds( edgeB )
3684               ) {
3685             edgeFound = true;
3686           }
3687         }
3688       }
3689
3690       if( !edgeFound ) {
3691         return false;
3692       }
3693     }
3694
3695     return true;
3696   }
3697
3698
3699
3700   // this analysis no longer has the "match anything"
3701   // type which was represented by null
3702   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3703                                              TypeDescriptor td2 ) {
3704     assert td1 != null;
3705     assert td2 != null;
3706
3707     if( td1.isNull() ) {
3708       return td2;
3709     }
3710     if( td2.isNull() ) {
3711       return td1;
3712     }
3713     return typeUtil.mostSpecific( td1, td2 );
3714   }
3715
3716   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3717                                              TypeDescriptor td2,
3718                                              TypeDescriptor td3 ) {
3719
3720     return mostSpecificType( td1,
3721                              mostSpecificType( td2, td3 )
3722                              );
3723   }
3724
3725   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3726                                              TypeDescriptor td2,
3727                                              TypeDescriptor td3,
3728                                              TypeDescriptor td4 ) {
3729
3730     return mostSpecificType( mostSpecificType( td1, td2 ),
3731                              mostSpecificType( td3, td4 )
3732                              );
3733   }
3734
3735   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3736                                     TypeDescriptor possibleChild ) {
3737     assert possibleSuper != null;
3738     assert possibleChild != null;
3739
3740     if( possibleSuper.isNull() ||
3741         possibleChild.isNull() ) {
3742       return true;
3743     }
3744
3745     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3746   }
3747
3748
3749   protected boolean hasMatchingField( HeapRegionNode src,
3750                                       RefEdge        edge ) {
3751
3752     TypeDescriptor tdSrc = src.getType();
3753     assert tdSrc != null;
3754
3755     if( tdSrc.isArray() ) {
3756       TypeDescriptor td = edge.getType();
3757       assert td != null;
3758
3759       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3760       assert tdSrcDeref != null;
3761
3762       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3763         return false;
3764       }
3765
3766       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3767     }
3768
3769     // if it's not a class, it doesn't have any fields to match
3770     if( !tdSrc.isClass() ) {
3771       return false;
3772     }
3773
3774     ClassDescriptor cd = tdSrc.getClassDesc();
3775     while( cd != null ) {
3776       Iterator fieldItr = cd.getFields();
3777
3778       while( fieldItr.hasNext() ) {
3779         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3780
3781         if( fd.getType().equals( edge.getType() ) &&
3782             fd.getSymbol().equals( edge.getField() ) ) {
3783           return true;
3784         }
3785       }
3786
3787       cd = cd.getSuperDesc();
3788     }
3789
3790     // otherwise it is a class with fields
3791     // but we didn't find a match
3792     return false;
3793   }
3794
3795   protected boolean hasMatchingType( RefEdge        edge,
3796                                      HeapRegionNode dst  ) {
3797
3798     // if the region has no type, matches everything
3799     TypeDescriptor tdDst = dst.getType();
3800     assert tdDst != null;
3801
3802     // if the type is not a class or an array, don't
3803     // match because primitives are copied, no aliases
3804     ClassDescriptor cdDst = tdDst.getClassDesc();
3805     if( cdDst == null && !tdDst.isArray() ) {
3806       return false;
3807     }
3808
3809     // if the edge type is null, it matches everything
3810     TypeDescriptor tdEdge = edge.getType();
3811     assert tdEdge != null;
3812
3813     return typeUtil.isSuperorType( tdEdge, tdDst );
3814   }
3815
3816
3817
3818   public void writeGraph( String  graphName,
3819                           boolean writeLabels,
3820                           boolean labelSelect,
3821                           boolean pruneGarbage,
3822                           boolean hideSubsetReachability,
3823                           boolean hideEdgeTaints
3824                           ) throws java.io.IOException {
3825     writeGraph( graphName,
3826                 writeLabels,
3827                 labelSelect,
3828                 pruneGarbage,
3829                 hideSubsetReachability,
3830                 hideEdgeTaints,
3831                 null );
3832   }
3833
3834   public void writeGraph( String       graphName,
3835                           boolean      writeLabels,
3836                           boolean      labelSelect,
3837                           boolean      pruneGarbage,
3838                           boolean      hideSubsetReachability,
3839                           boolean      hideEdgeTaints,
3840                           Set<Integer> callerNodeIDsCopiedToCallee
3841                           ) throws java.io.IOException {
3842
3843     // remove all non-word characters from the graph name so
3844     // the filename and identifier in dot don't cause errors
3845     graphName = graphName.replaceAll( "[\\W]", "" );
3846
3847     BufferedWriter bw =
3848       new BufferedWriter( new FileWriter( graphName+".dot" ) );
3849
3850     bw.write( "digraph "+graphName+" {\n" );
3851
3852
3853     // this is an optional step to form the callee-reachable
3854     // "cut-out" into a DOT cluster for visualization
3855     if( callerNodeIDsCopiedToCallee != null ) {
3856
3857       bw.write( "  subgraph cluster0 {\n" );
3858       bw.write( "    color=blue;\n" );
3859
3860       Iterator i = id2hrn.entrySet().iterator();
3861       while( i.hasNext() ) {
3862         Map.Entry      me  = (Map.Entry)      i.next();
3863         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3864
3865         if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
3866           bw.write( "    "+hrn.toString()+
3867                     hrn.toStringDOT( hideSubsetReachability )+
3868                     ";\n" );
3869
3870         }
3871       }
3872
3873       bw.write( "  }\n" );
3874     }
3875
3876
3877     Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3878
3879     // then visit every heap region node
3880     Iterator i = id2hrn.entrySet().iterator();
3881     while( i.hasNext() ) {
3882       Map.Entry      me  = (Map.Entry)      i.next();
3883       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3884
3885       // only visit nodes worth writing out--for instance
3886       // not every node at an allocation is referenced
3887       // (think of it as garbage-collected), etc.
3888       if( !pruneGarbage        ||
3889           hrn.isOutOfContext()
3890           ) {
3891
3892         if( !visited.contains( hrn ) ) {
3893           traverseHeapRegionNodes( hrn,
3894                                    bw,
3895                                    null,
3896                                    visited,
3897                                    hideSubsetReachability,
3898                                    hideEdgeTaints,
3899                                    callerNodeIDsCopiedToCallee );
3900         }
3901       }
3902     }
3903
3904     bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
3905
3906
3907     // then visit every label node, useful for debugging
3908     if( writeLabels ) {
3909       i = td2vn.entrySet().iterator();
3910       while( i.hasNext() ) {
3911         Map.Entry    me = (Map.Entry)    i.next();
3912         VariableNode vn = (VariableNode) me.getValue();
3913
3914         if( labelSelect ) {
3915           String labelStr = vn.getTempDescriptorString();
3916           if( labelStr.startsWith( "___temp" )     ||
3917               labelStr.startsWith( "___dst" )      ||
3918               labelStr.startsWith( "___srctmp" )   ||
3919               labelStr.startsWith( "___neverused" )
3920               ) {
3921             continue;
3922           }
3923         }
3924
3925         Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
3926         while( heapRegionsItr.hasNext() ) {
3927           RefEdge        edge = heapRegionsItr.next();
3928           HeapRegionNode hrn  = edge.getDst();
3929
3930           if( !visited.contains( hrn ) ) {
3931             traverseHeapRegionNodes( hrn,
3932                                      bw,
3933                                      null,
3934                                      visited,
3935                                      hideSubsetReachability,
3936                                      hideEdgeTaints,
3937                                      callerNodeIDsCopiedToCallee );
3938           }
3939
3940           bw.write( "  "+vn.toString()+
3941                     " -> "+hrn.toString()+
3942                     edge.toStringDOT( hideSubsetReachability, "" )+
3943                     ";\n" );
3944         }
3945       }
3946     }
3947
3948     bw.write( "}\n" );
3949     bw.close();
3950   }
3951
3952   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
3953                                           BufferedWriter      bw,
3954                                           TempDescriptor      td,
3955                                           Set<HeapRegionNode> visited,
3956                                           boolean             hideSubsetReachability,
3957                                           boolean             hideEdgeTaints,
3958                                           Set<Integer>        callerNodeIDsCopiedToCallee
3959                                           ) throws java.io.IOException {
3960
3961     if( visited.contains( hrn ) ) {
3962       return;
3963     }
3964     visited.add( hrn );
3965
3966     // if we're drawing the callee-view subgraph, only
3967     // write out the node info if it hasn't already been
3968     // written
3969     if( callerNodeIDsCopiedToCallee == null ||
3970         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
3971         ) {
3972       bw.write( "  "+hrn.toString()+
3973                 hrn.toStringDOT( hideSubsetReachability )+
3974                 ";\n" );
3975     }
3976
3977     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
3978     while( childRegionsItr.hasNext() ) {
3979       RefEdge        edge     = childRegionsItr.next();
3980       HeapRegionNode hrnChild = edge.getDst();
3981
3982       if( callerNodeIDsCopiedToCallee != null &&
3983           (edge.getSrc() instanceof HeapRegionNode) ) {
3984         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
3985         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
3986             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3987             ) {
3988           bw.write( "  "+hrn.toString()+
3989                     " -> "+hrnChild.toString()+
3990                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
3991                     ";\n");
3992         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
3993                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
3994                    ) {
3995           bw.write( "  "+hrn.toString()+
3996                     " -> "+hrnChild.toString()+
3997                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
3998                     ";\n");
3999         } else {
4000           bw.write( "  "+hrn.toString()+
4001                     " -> "+hrnChild.toString()+
4002                     edge.toStringDOT( hideSubsetReachability, "" )+
4003                     ";\n");
4004         }
4005       } else {
4006         bw.write( "  "+hrn.toString()+
4007                   " -> "+hrnChild.toString()+
4008                   edge.toStringDOT( hideSubsetReachability, "" )+
4009                   ";\n");
4010       }
4011
4012       traverseHeapRegionNodes( hrnChild,
4013                                bw,
4014                                td,
4015                                visited,
4016                                hideSubsetReachability,
4017                                hideEdgeTaints,
4018                                callerNodeIDsCopiedToCallee );
4019     }
4020   }
4021
4022         public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
4023                         HeapRegionNode hrn2) {
4024
4025                 Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4026                 Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4027
4028                 Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4029                 todoNodes1.add(hrn1);
4030
4031                 Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4032                 todoNodes2.add(hrn2);
4033
4034                 // follow links until all reachable nodes have been found
4035                 while (!todoNodes1.isEmpty()) {
4036                         HeapRegionNode hrn = todoNodes1.iterator().next();
4037                         todoNodes1.remove(hrn);
4038                         reachableNodes1.add(hrn);
4039
4040                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4041                         while (edgeItr.hasNext()) {
4042                                 RefEdge edge = edgeItr.next();
4043
4044                                 if (!reachableNodes1.contains(edge.getDst())) {
4045                                         todoNodes1.add(edge.getDst());
4046                                 }
4047                         }
4048                 }
4049
4050                 while (!todoNodes2.isEmpty()) {
4051                         HeapRegionNode hrn = todoNodes2.iterator().next();
4052                         todoNodes2.remove(hrn);
4053                         reachableNodes2.add(hrn);
4054
4055                         Iterator<RefEdge> edgeItr = hrn.iteratorToReferencees();
4056                         while (edgeItr.hasNext()) {
4057                                 RefEdge edge = edgeItr.next();
4058
4059                                 if (!reachableNodes2.contains(edge.getDst())) {
4060                                         todoNodes2.add(edge.getDst());
4061                                 }
4062                         }
4063                 }
4064
4065                 Set<HeapRegionNode> intersection =
4066                   new HashSet<HeapRegionNode>( reachableNodes1 );
4067
4068                 intersection.retainAll( reachableNodes2 );
4069
4070                 return intersection;
4071         }
4072
4073         public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4074                         HeapRegionNode hrn2) {
4075                 assert hrn1 != null;
4076                 assert hrn2 != null;
4077
4078                 // then get the various tokens for these heap regions
4079                 ReachTuple h1 = ReachTuple.factory(hrn1.getID(),
4080                                 !hrn1.isSingleObject(), ReachTuple.ARITY_ONE, false);
4081
4082                 ReachTuple h1plus = ReachTuple.factory(hrn1.getID(), !hrn1
4083                                 .isSingleObject(), ReachTuple.ARITY_ONEORMORE, false);
4084
4085                 ReachTuple h1star = ReachTuple.factory(hrn1.getID(), !hrn1
4086                                 .isSingleObject(), ReachTuple.ARITY_ZEROORMORE, false);
4087
4088                 ReachTuple h2 = ReachTuple.factory(hrn2.getID(),
4089                                 !hrn2.isSingleObject(), ReachTuple.ARITY_ONE, false);
4090
4091                 ReachTuple h2plus = ReachTuple.factory(hrn2.getID(), !hrn2
4092                                 .isSingleObject(), ReachTuple.ARITY_ONEORMORE, false);
4093
4094                 ReachTuple h2star = ReachTuple.factory(hrn2.getID(), !hrn2
4095                                 .isSingleObject(), ReachTuple.ARITY_ZEROORMORE, false);
4096
4097                 // then get the merged beta of all out-going edges from these heap
4098                 // regions
4099
4100                 ReachSet beta1 = ReachSet.factory();
4101                 Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4102                 while (itrEdge.hasNext()) {
4103                         RefEdge edge = itrEdge.next();
4104                         beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4105                 }
4106
4107                 ReachSet beta2 = ReachSet.factory();
4108                 itrEdge = hrn2.iteratorToReferencees();
4109                 while (itrEdge.hasNext()) {
4110                         RefEdge edge = itrEdge.next();
4111                         beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4112                 }
4113
4114                 boolean aliasDetected = false;
4115
4116                 // only do this one if they are different tokens
4117                 if (h1 != h2 && beta1.containsStateWithBoth(h1, h2)) {
4118                         aliasDetected = true;
4119                 }
4120                 if (beta1.containsStateWithBoth(h1plus, h2)) {
4121                         aliasDetected = true;
4122                 }
4123                 if (beta1.containsStateWithBoth(h1star, h2)) {
4124                         aliasDetected = true;
4125                 }
4126                 if (beta1.containsStateWithBoth(h1, h2plus)) {
4127                         aliasDetected = true;
4128                 }
4129                 if (beta1.containsStateWithBoth(h1plus, h2plus)) {
4130                         aliasDetected = true;
4131                 }
4132                 if (beta1.containsStateWithBoth(h1star, h2plus)) {
4133                         aliasDetected = true;
4134                 }
4135                 if (beta1.containsStateWithBoth(h1, h2star)) {
4136                         aliasDetected = true;
4137                 }
4138                 if (beta1.containsStateWithBoth(h1plus, h2star)) {
4139                         aliasDetected = true;
4140                 }
4141                 if (beta1.containsStateWithBoth(h1star, h2star)) {
4142                         aliasDetected = true;
4143                 }
4144
4145                 if (h1 != h2 && beta2.containsStateWithBoth(h1, h2)) {
4146                         aliasDetected = true;
4147                 }
4148                 if (beta2.containsStateWithBoth(h1plus, h2)) {
4149                         aliasDetected = true;
4150                 }
4151                 if (beta2.containsStateWithBoth(h1star, h2)) {
4152                         aliasDetected = true;
4153                 }
4154                 if (beta2.containsStateWithBoth(h1, h2plus)) {
4155                         aliasDetected = true;
4156                 }
4157                 if (beta2.containsStateWithBoth(h1plus, h2plus)) {
4158                         aliasDetected = true;
4159                 }
4160                 if (beta2.containsStateWithBoth(h1star, h2plus)) {
4161                         aliasDetected = true;
4162                 }
4163                 if (beta2.containsStateWithBoth(h1, h2star)) {
4164                         aliasDetected = true;
4165                 }
4166                 if (beta2.containsStateWithBoth(h1plus, h2star)) {
4167                         aliasDetected = true;
4168                 }
4169                 if (beta2.containsStateWithBoth(h1star, h2star)) {
4170                         aliasDetected = true;
4171                 }
4172
4173                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4174                 if (aliasDetected) {
4175                         common = findCommonReachableNodes(hrn1, hrn2);
4176                         if (!(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP)) {
4177                                 assert !common.isEmpty();
4178                         }
4179                 }
4180
4181                 return common;
4182         }
4183
4184         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4185                         Integer paramIndex1, Integer paramIndex2) {
4186
4187                 // get parameter's heap regions
4188                 TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4189                 VariableNode argVar1 = getVariableNodeFromTemp(paramTemp1);
4190                 RefEdge argEdge1 = argVar1.iteratorToReferencees().next();
4191                 HeapRegionNode hrnParam1 = argEdge1.getDst();
4192
4193                 TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4194                 VariableNode argVar2 = getVariableNodeFromTemp(paramTemp2);
4195                 RefEdge argEdge2 = argVar2.iteratorToReferencees().next();
4196                 HeapRegionNode hrnParam2 = argEdge2.getDst();
4197
4198                 Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4199                 common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4200
4201                 return common;
4202         }
4203
4204         public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4205                         Integer paramIndex, AllocSite as) {
4206
4207                 // get parameter's heap regions
4208                 TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4209                 VariableNode argVar = getVariableNodeFromTemp(paramTemp);
4210                 RefEdge argEdge = argVar.iteratorToReferencees().next();
4211                 HeapRegionNode hrnParam = argEdge.getDst();
4212
4213                 // get summary node
4214                 assert id2hrn.containsKey(as.getSummary());
4215                 HeapRegionNode hrnSummary = id2hrn.get(as.getSummary());
4216                 assert hrnSummary != null;
4217
4218                 Set<HeapRegionNode> common = mayReachSharedObjects(hrnParam, hrnSummary);
4219
4220                 // check for other nodes
4221                 for (int i = 0; i < as.getAllocationDepth(); ++i) {
4222
4223                         assert id2hrn.containsKey(as.getIthOldest(i));
4224                         HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4225                         assert hrnIthOldest != null;
4226
4227                         common = mayReachSharedObjects(hrnParam, hrnIthOldest);
4228
4229                 }
4230
4231                 return common;
4232         }
4233
4234         public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4235                         AllocSite as2) {
4236
4237                 // get summary node 1's alpha
4238                 Integer idSum1 = as1.getSummary();
4239                 assert id2hrn.containsKey(idSum1);
4240                 HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
4241                 assert hrnSum1 != null;
4242
4243                 // get summary node 2's alpha
4244                 Integer idSum2 = as2.getSummary();
4245                 assert id2hrn.containsKey(idSum2);
4246                 HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
4247                 assert hrnSum2 != null;
4248
4249                 Set<HeapRegionNode> common = mayReachSharedObjects(hrnSum1, hrnSum2);
4250
4251                 // check sum2 against alloc1 nodes
4252                 for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4253                         Integer idI1 = as1.getIthOldest(i);
4254                         assert id2hrn.containsKey(idI1);
4255                         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4256                         assert hrnI1 != null;
4257
4258                         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4259                 }
4260
4261                 // check sum1 against alloc2 nodes
4262                 for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4263                         Integer idI2 = as2.getIthOldest(i);
4264                         assert id2hrn.containsKey(idI2);
4265                         HeapRegionNode hrnI2 = id2hrn.get(idI2);
4266                         assert hrnI2 != null;
4267
4268                         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4269
4270                         // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4271                         for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4272                                 Integer idI1 = as1.getIthOldest(j);
4273
4274                                 // if these are the same site, don't look for the same token, no
4275                                 // alias.
4276                                 // different tokens of the same site could alias together though
4277                                 if (idI1.equals(idI2)) {
4278                                         continue;
4279                                 }
4280
4281                                 HeapRegionNode hrnI1 = id2hrn.get(idI1);
4282
4283                                 common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4284                         }
4285                 }
4286
4287                 return common;
4288         }
4289
4290 }