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