Robust/src/Analysis/Disjoint/ReachGraph.java

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