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