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