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