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