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