Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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