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
2085       System.out.println("  "+mc+" is calling "+fm);
2086     }
2087
2088
2089
2090     // define rewrite rules and other structures to organize data by parameter/argument index
2091     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_p = new Hashtable<Integer, ReachabilitySet>();
2092     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH_s = new Hashtable<Integer, ReachabilitySet>();
2093
2094     Hashtable<String,  ReachabilitySet> paramIndex2rewriteJ_p2p = new Hashtable<String,  ReachabilitySet>(); // select( i, j, f )
2095     Hashtable<String,  ReachabilitySet> paramIndex2rewriteJ_p2s = new Hashtable<String,  ReachabilitySet>(); // select( i,    f )
2096     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2p = new Hashtable<Integer, ReachabilitySet>();
2097     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ_s2s = new Hashtable<Integer, ReachabilitySet>();
2098
2099     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p  = new Hashtable<Integer, ReachabilitySet>();
2100     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_p2 = new Hashtable<Integer, ReachabilitySet>();
2101     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK_s  = new Hashtable<Integer, ReachabilitySet>();
2102
2103     Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_p = new Hashtable<Integer, ReachabilitySet>();
2104     Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d_s = new Hashtable<Integer, ReachabilitySet>();
2105
2106     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD = new Hashtable<Integer, ReachabilitySet>();
2107
2108
2109     Hashtable<Integer, LabelNode> paramIndex2ln = new Hashtable<Integer, LabelNode>();
2110
2111
2112     paramIndex2rewriteH_p.put(bogusIndex, rsIdentity);
2113     paramIndex2rewriteH_s.put(bogusIndex, rsIdentity);
2114
2115     paramIndex2rewriteJ_p2p.put(bogusIndex.toString(), rsIdentity);
2116     paramIndex2rewriteJ_p2s.put(bogusIndex.toString(), rsIdentity);
2117     paramIndex2rewriteJ_s2p.put(bogusIndex,            rsIdentity);
2118     paramIndex2rewriteJ_s2s.put(bogusIndex,            rsIdentity);
2119
2120
2121     for( int i = 0; i < fm.numParameters(); ++i ) {
2122       Integer paramIndex = new Integer(i);
2123
2124       if( !ogCallee.paramIndex2idPrimary.containsKey(paramIndex) ) {
2125         // skip this immutable parameter
2126         continue;
2127       }
2128
2129       // setup H (primary)
2130       Integer idPrimary = ogCallee.paramIndex2idPrimary.get(paramIndex);
2131       assert ogCallee.id2hrn.containsKey(idPrimary);
2132       HeapRegionNode hrnPrimary = ogCallee.id2hrn.get(idPrimary);
2133       assert hrnPrimary != null;
2134       paramIndex2rewriteH_p.put(paramIndex, toShadowTokens(ogCallee, hrnPrimary.getAlpha() ) );
2135
2136       // setup J (primary->X)
2137       Iterator<ReferenceEdge> p2xItr = hrnPrimary.iteratorToReferencees();
2138       while( p2xItr.hasNext() ) {
2139         ReferenceEdge p2xEdge = p2xItr.next();
2140
2141         // we only care about initial parameter edges here
2142         if( !p2xEdge.isInitialParam() ) {
2143           continue;
2144         }
2145
2146         HeapRegionNode hrnDst = p2xEdge.getDst();
2147
2148         if( ogCallee.idPrimary2paramIndexSet.containsKey(hrnDst.getID() ) ) {
2149           Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get(hrnDst.getID() ).iterator();
2150           while( jItr.hasNext() ) {
2151             Integer j = jItr.next();
2152             paramIndex2rewriteJ_p2p.put(makeMapKey(i, j, p2xEdge.getField() ),
2153                                         toShadowTokens(ogCallee, p2xEdge.getBeta() ) );
2154           }
2155
2156         } else {
2157           assert ogCallee.idSecondary2paramIndexSet.containsKey(hrnDst.getID() );
2158           paramIndex2rewriteJ_p2s.put(makeMapKey(i, p2xEdge.getField() ),
2159                                       toShadowTokens(ogCallee, p2xEdge.getBeta() ) );
2160         }
2161       }
2162
2163       // setup K (primary)
2164       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
2165       assert tdParamQ != null;
2166       LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
2167       assert lnParamQ != null;
2168       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnPrimary, null, null);
2169       assert edgeSpecialQ_i != null;
2170       ReachabilitySet qBeta = toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() );
2171
2172       TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get(paramIndex);
2173       TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get(paramIndex);
2174
2175       ReachabilitySet K_p  = new ReachabilitySet().makeCanonical();
2176       ReachabilitySet K_p2 = new ReachabilitySet().makeCanonical();
2177       if( s_i == null ) {
2178         K_p = qBeta;
2179       } else {
2180         // sort qBeta into K_p1 and K_p2
2181         Iterator<TokenTupleSet> ttsItr = qBeta.iterator();
2182         while( ttsItr.hasNext() ) {
2183           TokenTupleSet tts = ttsItr.next();
2184           if( s_i != null && tts.containsBoth(p_i, s_i) ) {
2185             K_p2 = K_p2.union(tts);
2186           } else {
2187             K_p = K_p.union(tts);
2188           }
2189         }
2190       }
2191       paramIndex2rewriteK_p.put(paramIndex, K_p);
2192       paramIndex2rewriteK_p2.put(paramIndex, K_p2);
2193
2194
2195       // if there is a secondary node, compute the rest of the rewrite rules
2196       if( ogCallee.paramIndex2idSecondary.containsKey(paramIndex) ) {
2197
2198         // setup H (secondary)
2199         Integer idSecondary = ogCallee.paramIndex2idSecondary.get(paramIndex);
2200         assert ogCallee.id2hrn.containsKey(idSecondary);
2201         HeapRegionNode hrnSecondary = ogCallee.id2hrn.get(idSecondary);
2202         assert hrnSecondary != null;
2203         paramIndex2rewriteH_s.put(paramIndex, toShadowTokens(ogCallee, hrnSecondary.getAlpha() ) );
2204
2205         // setup J (secondary->X)
2206         Iterator<ReferenceEdge> s2xItr = hrnSecondary.iteratorToReferencees();
2207         while( s2xItr.hasNext() ) {
2208           ReferenceEdge s2xEdge = s2xItr.next();
2209
2210           if( !s2xEdge.isInitialParam() ) {
2211             continue;
2212           }
2213
2214           HeapRegionNode hrnDst = s2xEdge.getDst();
2215
2216           if( ogCallee.idPrimary2paramIndexSet.containsKey(hrnDst.getID() ) ) {
2217             Iterator<Integer> jItr = ogCallee.idPrimary2paramIndexSet.get(hrnDst.getID() ).iterator();
2218             while( jItr.hasNext() ) {
2219               Integer j = jItr.next();
2220               paramIndex2rewriteJ_s2p.put(i, toShadowTokens(ogCallee, s2xEdge.getBeta() ) );
2221             }
2222
2223           } else {
2224             assert ogCallee.idSecondary2paramIndexSet.containsKey(hrnDst.getID() );
2225             paramIndex2rewriteJ_s2s.put(i, toShadowTokens(ogCallee, s2xEdge.getBeta() ) );
2226           }
2227         }
2228
2229         // setup K (secondary)
2230         TempDescriptor tdParamR = ogCallee.paramIndex2tdR.get(paramIndex);
2231         assert tdParamR != null;
2232         LabelNode lnParamR = ogCallee.td2ln.get(tdParamR);
2233         assert lnParamR != null;
2234         ReferenceEdge edgeSpecialR_i = lnParamR.getReferenceTo(hrnSecondary, null, null);
2235         assert edgeSpecialR_i != null;
2236         paramIndex2rewriteK_s.put(paramIndex,
2237                                   toShadowTokens(ogCallee, edgeSpecialR_i.getBeta() ) );
2238       }
2239
2240
2241       // now depending on whether the callee is static or not
2242       // we need to account for a "this" argument in order to
2243       // find the matching argument in the caller context
2244       TempDescriptor argTemp_i = fc.getArgMatchingParamIndex(fm, paramIndex);
2245
2246       // remember which caller arg label maps to param index
2247       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
2248       paramIndex2ln.put(paramIndex, argLabel_i);
2249
2250       // do a callee-effect strong update pre-pass here
2251       if( argTemp_i.getType().isClass() ) {
2252
2253         Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2254         while( edgeItr.hasNext() ) {
2255           ReferenceEdge edge = edgeItr.next();
2256           HeapRegionNode hrn = edge.getDst();
2257
2258           if( (hrn.getNumReferencers()                                == 1) || // case 1
2259               (hrn.isSingleObject() && argLabel_i.getNumReferencees() == 1)    // case 2
2260               ) {
2261             if( !DISABLE_STRONG_UPDATES ) {
2262               effectCalleeStrongUpdates(paramIndex, ogCallee, hrn);
2263             }
2264           }
2265         }
2266       }
2267
2268       // then calculate the d and D rewrite rules
2269       ReachabilitySet d_i_p = new ReachabilitySet().makeCanonical();
2270       ReachabilitySet d_i_s = new ReachabilitySet().makeCanonical();
2271       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
2272       while( edgeItr.hasNext() ) {
2273         ReferenceEdge edge = edgeItr.next();
2274
2275         d_i_p = d_i_p.union(edge.getBeta().intersection(edge.getDst().getAlpha() ) );
2276         d_i_s = d_i_s.union(edge.getBeta() );
2277       }
2278       paramIndex2rewrite_d_p.put(paramIndex, d_i_p);
2279       paramIndex2rewrite_d_s.put(paramIndex, d_i_s);
2280
2281       // TODO: we should only do this when we need it, and then
2282       // memoize it for the rest of the mapping procedure
2283       ReachabilitySet D_i = d_i_s.exhaustiveArityCombinations();
2284       paramIndex2rewriteD.put(paramIndex, D_i);
2285     }
2286
2287
2288     // with respect to each argument, map parameter effects into caller
2289     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
2290     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
2291
2292     Hashtable<Integer, Set<HeapRegionNode> > pi2dr =
2293       new Hashtable<Integer, Set<HeapRegionNode> >();
2294
2295     Hashtable<Integer, Set<HeapRegionNode> > pi2r =
2296       new Hashtable<Integer, Set<HeapRegionNode> >();
2297
2298     Set<HeapRegionNode> defParamObj = new HashSet<HeapRegionNode>();
2299
2300     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
2301     while( lnArgItr.hasNext() ) {
2302       Map.Entry me      = (Map.Entry)lnArgItr.next();
2303       Integer index   = (Integer)   me.getKey();
2304       LabelNode lnArg_i = (LabelNode) me.getValue();
2305
2306       Set<HeapRegionNode> dr   = new HashSet<HeapRegionNode>();
2307       Set<HeapRegionNode> r    = new HashSet<HeapRegionNode>();
2308       Set<HeapRegionNode> todo = new HashSet<HeapRegionNode>();
2309
2310       // find all reachable nodes starting with label referencees
2311       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
2312       while( edgeArgItr.hasNext() ) {
2313         ReferenceEdge edge = edgeArgItr.next();
2314         HeapRegionNode hrn = edge.getDst();
2315
2316         dr.add(hrn);
2317
2318         if( lnArg_i.getNumReferencees() == 1 && hrn.isSingleObject() ) {
2319           defParamObj.add(hrn);
2320         }
2321
2322         Iterator<ReferenceEdge> edgeHrnItr = hrn.iteratorToReferencees();
2323         while( edgeHrnItr.hasNext() ) {
2324           ReferenceEdge edger = edgeHrnItr.next();
2325           todo.add(edger.getDst() );
2326         }
2327
2328         // then follow links until all reachable nodes have been found
2329         while( !todo.isEmpty() ) {
2330           HeapRegionNode hrnr = todo.iterator().next();
2331           todo.remove(hrnr);
2332
2333           r.add(hrnr);
2334
2335           Iterator<ReferenceEdge> edgeItr = hrnr.iteratorToReferencees();
2336           while( edgeItr.hasNext() ) {
2337             ReferenceEdge edger = edgeItr.next();
2338             if( !r.contains(edger.getDst() ) ) {
2339               todo.add(edger.getDst() );
2340             }
2341           }
2342         }
2343
2344         if( hrn.isSingleObject() ) {
2345           r.remove(hrn);
2346         }
2347       }
2348
2349       pi2dr.put(index, dr);
2350       pi2r.put(index, r);
2351     }
2352
2353     assert defParamObj.size() <= fm.numParameters();
2354
2355     // if we're in parameter decomposition mode, report some results here
2356     if( pd != null ) {
2357       Iterator mapItr;
2358
2359       // report primary parameter object mappings
2360       mapItr = pi2dr.entrySet().iterator();
2361       while( mapItr.hasNext() ) {
2362         Map.Entry me         = (Map.Entry)mapItr.next();
2363         Integer paramIndex = (Integer)             me.getKey();
2364         Set<HeapRegionNode> hrnAset    = (Set<HeapRegionNode>)me.getValue();
2365
2366         Iterator<HeapRegionNode> hrnItr = hrnAset.iterator();
2367         while( hrnItr.hasNext() ) {
2368           HeapRegionNode hrnA = hrnItr.next();
2369           pd.mapRegionToParamObject(hrnA, paramIndex);
2370         }
2371       }
2372
2373       // report parameter-reachable mappings
2374       mapItr = pi2r.entrySet().iterator();
2375       while( mapItr.hasNext() ) {
2376         Map.Entry me         = (Map.Entry)mapItr.next();
2377         Integer paramIndex = (Integer)             me.getKey();
2378         Set<HeapRegionNode> hrnRset    = (Set<HeapRegionNode>)me.getValue();
2379
2380         Iterator<HeapRegionNode> hrnItr = hrnRset.iterator();
2381         while( hrnItr.hasNext() ) {
2382           HeapRegionNode hrnR = hrnItr.next();
2383           pd.mapRegionToParamReachable(hrnR, paramIndex);
2384         }
2385       }
2386
2387       // and we're done in this method for special param decomp mode
2388       return;
2389     }
2390
2391
2392     // now iterate over reachable nodes to rewrite their alpha, and
2393     // classify edges found for beta rewrite
2394     Hashtable<TokenTuple, ReachabilitySet> tokens2states = new Hashtable<TokenTuple, ReachabilitySet>();
2395
2396     Hashtable< Integer, Set<Vector> > edges_p2p   = new Hashtable< Integer, Set<Vector> >();
2397     Hashtable< Integer, Set<Vector> > edges_p2s   = new Hashtable< Integer, Set<Vector> >();
2398     Hashtable< Integer, Set<Vector> > edges_s2p   = new Hashtable< Integer, Set<Vector> >();
2399     Hashtable< Integer, Set<Vector> > edges_s2s   = new Hashtable< Integer, Set<Vector> >();
2400     Hashtable< Integer, Set<Vector> > edges_up_dr = new Hashtable< Integer, Set<Vector> >();
2401     Hashtable< Integer, Set<Vector> > edges_up_r  = new Hashtable< Integer, Set<Vector> >();
2402
2403     // so again, with respect to some arg i...
2404     lnArgItr = paramIndex2ln.entrySet().iterator();
2405     while( lnArgItr.hasNext() ) {
2406       Map.Entry me      = (Map.Entry)lnArgItr.next();
2407       Integer index   = (Integer)   me.getKey();
2408       LabelNode lnArg_i = (LabelNode) me.getValue();
2409
2410       TokenTuple p_i = ogCallee.paramIndex2paramTokenPrimary.get(index);
2411       TokenTuple s_i = ogCallee.paramIndex2paramTokenSecondary.get(index);
2412       assert p_i != null;
2413
2414       ensureEmptyEdgeIndexPair(edges_p2p,   index);
2415       ensureEmptyEdgeIndexPair(edges_p2s,   index);
2416       ensureEmptyEdgeIndexPair(edges_s2p,   index);
2417       ensureEmptyEdgeIndexPair(edges_s2s,   index);
2418       ensureEmptyEdgeIndexPair(edges_up_dr, index);
2419       ensureEmptyEdgeIndexPair(edges_up_r,  index);
2420
2421       Set<HeapRegionNode> dr = pi2dr.get(index);
2422       Iterator<HeapRegionNode> hrnItr = dr.iterator();
2423       while( hrnItr.hasNext() ) {
2424         // this heap region is definitely an "a_i" or primary by virtue of being in dr
2425         HeapRegionNode hrn = hrnItr.next();
2426
2427         tokens2states.clear();
2428         tokens2states.put(p_i, hrn.getAlpha() );
2429
2430         rewriteCallerReachability(index,
2431                                   hrn,
2432                                   null,
2433                                   paramIndex2rewriteH_p.get(index),
2434                                   tokens2states,
2435                                   paramIndex2rewrite_d_p,
2436                                   paramIndex2rewrite_d_s,
2437                                   paramIndex2rewriteD,
2438                                   ogCallee,
2439                                   false,
2440                                   null);
2441
2442         nodesWithNewAlpha.add(hrn);
2443
2444         // sort edges
2445         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2446         while( edgeItr.hasNext() ) {
2447           ReferenceEdge edge = edgeItr.next();
2448           OwnershipNode on   = edge.getSrc();
2449
2450           boolean edge_classified = false;
2451
2452
2453           if( on instanceof HeapRegionNode ) {
2454             // hrn0 may be "a_j" and/or "r_j" or even neither
2455             HeapRegionNode hrn0 = (HeapRegionNode) on;
2456
2457             Iterator itr = pi2dr.entrySet().iterator();
2458             while( itr.hasNext() ) {
2459               Map.Entry mo   = (Map.Entry)itr.next();
2460               Integer pi   = (Integer)             mo.getKey();
2461               Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>)mo.getValue();
2462
2463               if( dr_i.contains(hrn0) ) {
2464                 addEdgeIndexPair(edges_p2p, pi, edge, index);
2465                 edge_classified = true;
2466               }
2467             }
2468
2469             itr = pi2r.entrySet().iterator();
2470             while( itr.hasNext() ) {
2471               Map.Entry mo  = (Map.Entry)itr.next();
2472               Integer pi  = (Integer)             mo.getKey();
2473               Set<HeapRegionNode> r_i = (Set<HeapRegionNode>)mo.getValue();
2474
2475               if( r_i.contains(hrn0) ) {
2476                 addEdgeIndexPair(edges_s2p, pi, edge, index);
2477                 edge_classified = true;
2478               }
2479             }
2480           }
2481
2482           // all of these edges are upstream of directly reachable objects
2483           if( !edge_classified ) {
2484             addEdgeIndexPair(edges_up_dr, index, edge, index);
2485           }
2486         }
2487       }
2488
2489
2490       Set<HeapRegionNode> r = pi2r.get(index);
2491       hrnItr = r.iterator();
2492       while( hrnItr.hasNext() ) {
2493         // this heap region is definitely an "r_i" or secondary by virtue of being in r
2494         HeapRegionNode hrn = hrnItr.next();
2495
2496         if( paramIndex2rewriteH_s.containsKey(index) ) {
2497
2498           tokens2states.clear();
2499           tokens2states.put(p_i, new ReachabilitySet().makeCanonical() );
2500           tokens2states.put(s_i, hrn.getAlpha() );
2501
2502           rewriteCallerReachability(index,
2503                                     hrn,
2504                                     null,
2505                                     paramIndex2rewriteH_s.get(index),
2506                                     tokens2states,
2507                                     paramIndex2rewrite_d_p,
2508                                     paramIndex2rewrite_d_s,
2509                                     paramIndex2rewriteD,
2510                                     ogCallee,
2511                                     false,
2512                                     null);
2513
2514           nodesWithNewAlpha.add(hrn);
2515         }
2516
2517         // sort edges
2518         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
2519         while( edgeItr.hasNext() ) {
2520           ReferenceEdge edge = edgeItr.next();
2521           OwnershipNode on   = edge.getSrc();
2522
2523           boolean edge_classified = false;
2524
2525           if( on instanceof HeapRegionNode ) {
2526             // hrn0 may be "a_j" and/or "r_j" or even neither
2527             HeapRegionNode hrn0 = (HeapRegionNode) on;
2528
2529             Iterator itr = pi2dr.entrySet().iterator();
2530             while( itr.hasNext() ) {
2531               Map.Entry mo   = (Map.Entry)itr.next();
2532               Integer pi   = (Integer)             mo.getKey();
2533               Set<HeapRegionNode> dr_i = (Set<HeapRegionNode>)mo.getValue();
2534
2535               if( dr_i.contains(hrn0) ) {
2536                 addEdgeIndexPair(edges_p2s, pi, edge, index);
2537                 edge_classified = true;
2538               }
2539             }
2540
2541             itr = pi2r.entrySet().iterator();
2542             while( itr.hasNext() ) {
2543               Map.Entry mo  = (Map.Entry)itr.next();
2544               Integer pi  = (Integer)             mo.getKey();
2545               Set<HeapRegionNode> r_i = (Set<HeapRegionNode>)mo.getValue();
2546
2547               if( r_i.contains(hrn0) ) {
2548                 addEdgeIndexPair(edges_s2s, pi, edge, index);
2549                 edge_classified = true;
2550               }
2551             }
2552           }
2553
2554           // these edges are all upstream of some reachable node
2555           if( !edge_classified ) {
2556             addEdgeIndexPair(edges_up_r, index, edge, index);
2557           }
2558         }
2559       }
2560     }
2561
2562
2563     // and again, with respect to some arg i...
2564     lnArgItr = paramIndex2ln.entrySet().iterator();
2565     while( lnArgItr.hasNext() ) {
2566       Map.Entry me      = (Map.Entry)lnArgItr.next();
2567       Integer index   = (Integer)   me.getKey();
2568       LabelNode lnArg_i = (LabelNode) me.getValue();
2569
2570
2571       // update reachable edges
2572       Iterator edgeItr = edges_p2p.get(index).iterator();
2573       while( edgeItr.hasNext() ) {
2574         Vector mo     = (Vector)        edgeItr.next();
2575         ReferenceEdge edge   = (ReferenceEdge) mo.get(0);
2576         Integer indexJ = (Integer)       mo.get(1);
2577
2578         if( !paramIndex2rewriteJ_p2p.containsKey(makeMapKey(index,
2579                                                             indexJ,
2580                                                             edge.getField() ) ) ) {
2581           continue;
2582         }
2583
2584         TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get(indexJ);
2585         assert p_j != null;
2586
2587         tokens2states.clear();
2588         tokens2states.put(p_j, edge.getBeta() );
2589
2590         rewriteCallerReachability(index,
2591                                   null,
2592                                   edge,
2593                                   paramIndex2rewriteJ_p2p.get(makeMapKey(index,
2594                                                                          indexJ,
2595                                                                          edge.getField() ) ),
2596                                   tokens2states,
2597                                   paramIndex2rewrite_d_p,
2598                                   paramIndex2rewrite_d_s,
2599                                   paramIndex2rewriteD,
2600                                   ogCallee,
2601                                   false,
2602                                   null);
2603
2604         edgesWithNewBeta.add(edge);
2605       }
2606
2607
2608       edgeItr = edges_p2s.get(index).iterator();
2609       while( edgeItr.hasNext() ) {
2610         Vector mo     = (Vector)        edgeItr.next();
2611         ReferenceEdge edge   = (ReferenceEdge) mo.get(0);
2612         Integer indexJ = (Integer)       mo.get(1);
2613
2614         if( !paramIndex2rewriteJ_p2s.containsKey(makeMapKey(index,
2615                                                             edge.getField() ) ) ) {
2616           continue;
2617         }
2618
2619         TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get(indexJ);
2620         assert s_j != null;
2621
2622         tokens2states.clear();
2623         tokens2states.put(s_j, edge.getBeta() );
2624
2625         rewriteCallerReachability(index,
2626                                   null,
2627                                   edge,
2628                                   paramIndex2rewriteJ_p2s.get(makeMapKey(index,
2629                                                                          edge.getField() ) ),
2630                                   tokens2states,
2631                                   paramIndex2rewrite_d_p,
2632                                   paramIndex2rewrite_d_s,
2633                                   paramIndex2rewriteD,
2634                                   ogCallee,
2635                                   false,
2636                                   null);
2637
2638         edgesWithNewBeta.add(edge);
2639       }
2640
2641
2642       edgeItr = edges_s2p.get(index).iterator();
2643       while( edgeItr.hasNext() ) {
2644         Vector mo     = (Vector)        edgeItr.next();
2645         ReferenceEdge edge   = (ReferenceEdge) mo.get(0);
2646         Integer indexJ = (Integer)       mo.get(1);
2647
2648         if( !paramIndex2rewriteJ_s2p.containsKey(index) ) {
2649           continue;
2650         }
2651
2652         TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get(indexJ);
2653         assert p_j != null;
2654
2655         tokens2states.clear();
2656         tokens2states.put(p_j, edge.getBeta() );
2657
2658         rewriteCallerReachability(index,
2659                                   null,
2660                                   edge,
2661                                   paramIndex2rewriteJ_s2p.get(index),
2662                                   tokens2states,
2663                                   paramIndex2rewrite_d_p,
2664                                   paramIndex2rewrite_d_s,
2665                                   paramIndex2rewriteD,
2666                                   ogCallee,
2667                                   false,
2668                                   null);
2669
2670         edgesWithNewBeta.add(edge);
2671       }
2672
2673
2674       edgeItr = edges_s2s.get(index).iterator();
2675       while( edgeItr.hasNext() ) {
2676         Vector mo     = (Vector)        edgeItr.next();
2677         ReferenceEdge edge   = (ReferenceEdge) mo.get(0);
2678         Integer indexJ = (Integer)       mo.get(1);
2679
2680         if( !paramIndex2rewriteJ_s2s.containsKey(index) ) {
2681           continue;
2682         }
2683
2684         TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get(indexJ);
2685         assert s_j != null;
2686
2687         tokens2states.clear();
2688         tokens2states.put(s_j, edge.getBeta() );
2689
2690         rewriteCallerReachability(index,
2691                                   null,
2692                                   edge,
2693                                   paramIndex2rewriteJ_s2s.get(index),
2694                                   tokens2states,
2695                                   paramIndex2rewrite_d_p,
2696                                   paramIndex2rewrite_d_s,
2697                                   paramIndex2rewriteD,
2698                                   ogCallee,
2699                                   false,
2700                                   null);
2701
2702         edgesWithNewBeta.add(edge);
2703       }
2704
2705
2706       // update directly upstream edges
2707       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
2708         new Hashtable<ReferenceEdge, ChangeTupleSet>();
2709
2710       HashSet<ReferenceEdge> edgesDirectlyUpstream =
2711         new HashSet<ReferenceEdge>();
2712
2713       edgeItr = edges_up_dr.get(index).iterator();
2714       while( edgeItr.hasNext() ) {
2715         Vector mo     = (Vector)        edgeItr.next();
2716         ReferenceEdge edge   = (ReferenceEdge) mo.get(0);
2717         Integer indexJ = (Integer)       mo.get(1);
2718
2719         edgesDirectlyUpstream.add(edge);
2720
2721         TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get(indexJ);
2722         assert p_j != null;
2723
2724         // start with K_p2 and p_j
2725         tokens2states.clear();
2726         tokens2states.put(p_j, edge.getBeta() );
2727
2728         rewriteCallerReachability(index,
2729                                   null,
2730                                   edge,
2731                                   paramIndex2rewriteK_p2.get(index),
2732                                   tokens2states,
2733                                   paramIndex2rewrite_d_p,
2734                                   paramIndex2rewrite_d_s,
2735                                   paramIndex2rewriteD,
2736                                   ogCallee,
2737                                   true,
2738                                   edgeUpstreamPlannedChanges);
2739
2740         // and add in s_j, if required, and do K_p
2741         TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get(indexJ);
2742         if( s_j != null ) {
2743           tokens2states.put(s_j, edge.getBeta() );
2744         }
2745
2746         rewriteCallerReachability(index,
2747                                   null,
2748                                   edge,
2749                                   paramIndex2rewriteK_p.get(index),
2750                                   tokens2states,
2751                                   paramIndex2rewrite_d_p,
2752                                   paramIndex2rewrite_d_s,
2753                                   paramIndex2rewriteD,
2754                                   ogCallee,
2755                                   true,
2756                                   edgeUpstreamPlannedChanges);
2757
2758         edgesWithNewBeta.add(edge);
2759       }
2760
2761       propagateTokensOverEdges(edgesDirectlyUpstream,
2762                                edgeUpstreamPlannedChanges,
2763                                edgesWithNewBeta);
2764
2765
2766       // update upstream edges
2767       edgeUpstreamPlannedChanges =
2768         new Hashtable<ReferenceEdge, ChangeTupleSet>();
2769
2770       HashSet<ReferenceEdge> edgesUpstream =
2771         new HashSet<ReferenceEdge>();
2772
2773       edgeItr = edges_up_r.get(index).iterator();
2774       while( edgeItr.hasNext() ) {
2775         Vector mo     = (Vector)        edgeItr.next();
2776         ReferenceEdge edge   = (ReferenceEdge) mo.get(0);
2777         Integer indexJ = (Integer)       mo.get(1);
2778
2779         if( !paramIndex2rewriteK_s.containsKey(index) ) {
2780           continue;
2781         }
2782
2783         edgesUpstream.add(edge);
2784
2785         TokenTuple p_j = ogCallee.paramIndex2paramTokenPrimary.get(indexJ);
2786         assert p_j != null;
2787
2788         TokenTuple s_j = ogCallee.paramIndex2paramTokenSecondary.get(indexJ);
2789         assert s_j != null;
2790
2791         tokens2states.clear();
2792         tokens2states.put(p_j, rsWttsEmpty);
2793         tokens2states.put(s_j, edge.getBeta() );
2794
2795         rewriteCallerReachability(index,
2796                                   null,
2797                                   edge,
2798                                   paramIndex2rewriteK_s.get(index),
2799                                   tokens2states,
2800                                   paramIndex2rewrite_d_p,
2801                                   paramIndex2rewrite_d_s,
2802                                   paramIndex2rewriteD,
2803                                   ogCallee,
2804                                   true,
2805                                   edgeUpstreamPlannedChanges);
2806
2807         edgesWithNewBeta.add(edge);
2808       }
2809
2810       propagateTokensOverEdges(edgesUpstream,
2811                                edgeUpstreamPlannedChanges,
2812                                edgesWithNewBeta);
2813
2814     } // end effects per argument/parameter map
2815
2816
2817     // commit changes to alpha and beta
2818     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
2819     while( nodeItr.hasNext() ) {
2820       nodeItr.next().applyAlphaNew();
2821     }
2822
2823     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
2824     while( edgeItr.hasNext() ) {
2825       edgeItr.next().applyBetaNew();
2826     }
2827
2828
2829     // verify the existence of allocation sites and their
2830     // shadows from the callee in the context of this caller graph
2831     // then map allocated nodes of callee onto the caller shadows
2832     // of them
2833     Hashtable<TokenTuple, ReachabilitySet> tokens2statesEmpty = new Hashtable<TokenTuple, ReachabilitySet>();
2834
2835     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
2836     while( asItr.hasNext() ) {
2837       AllocationSite allocSite  = asItr.next();
2838
2839       // grab the summary in the caller just to make sure
2840       // the allocation site has nodes in the caller
2841       HeapRegionNode hrnSummary = getSummaryNode(allocSite);
2842
2843       // assert that the shadow nodes have no reference edges
2844       // because they're brand new to the graph, or last time
2845       // they were used they should have been cleared of edges
2846       HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
2847       assert hrnShadowSummary.getNumReferencers() == 0;
2848       assert hrnShadowSummary.getNumReferencees() == 0;
2849
2850       // then bring g_ij onto g'_ij and rewrite
2851       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
2852       hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
2853
2854       // shadow nodes only are touched by a rewrite one time,
2855       // so rewrite and immediately commit--and they don't belong
2856       // to a particular parameter, so use a bogus param index
2857       // that pulls a self-rewrite out of H
2858       rewriteCallerReachability(bogusIndex,
2859                                 hrnShadowSummary,
2860                                 null,
2861                                 funcScriptR(hrnShadowSummary.getAlpha(), ogCallee, mc),
2862                                 tokens2statesEmpty,
2863                                 paramIndex2rewrite_d_p,
2864                                 paramIndex2rewrite_d_s,
2865                                 paramIndex2rewriteD,
2866                                 ogCallee,
2867                                 false,
2868                                 null);
2869
2870       hrnShadowSummary.applyAlphaNew();
2871
2872
2873       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
2874         Integer idIth = allocSite.getIthOldest(i);
2875         assert id2hrn.containsKey(idIth);
2876         HeapRegionNode hrnIth = id2hrn.get(idIth);
2877
2878         Integer idShadowIth = -(allocSite.getIthOldest(i));
2879         assert id2hrn.containsKey(idShadowIth);
2880         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
2881         assert hrnIthShadow.getNumReferencers() == 0;
2882         assert hrnIthShadow.getNumReferencees() == 0;
2883
2884         assert ogCallee.id2hrn.containsKey(idIth);
2885         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
2886         hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
2887
2888         rewriteCallerReachability(bogusIndex,
2889                                   hrnIthShadow,
2890                                   null,
2891                                   funcScriptR(hrnIthShadow.getAlpha(), ogCallee, mc),
2892                                   tokens2statesEmpty,
2893                                   paramIndex2rewrite_d_p,
2894                                   paramIndex2rewrite_d_s,
2895                                   paramIndex2rewriteD,
2896                                   ogCallee,
2897                                   false,
2898                                   null);
2899
2900         hrnIthShadow.applyAlphaNew();
2901       }
2902     }
2903
2904
2905     // for every heap region->heap region edge in the
2906     // callee graph, create the matching edge or edges
2907     // in the caller graph
2908     Set sCallee = ogCallee.id2hrn.entrySet();
2909     Iterator iCallee = sCallee.iterator();
2910
2911     while( iCallee.hasNext() ) {
2912       Map.Entry meCallee  = (Map.Entry)iCallee.next();
2913       Integer idCallee  = (Integer)        meCallee.getKey();
2914       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
2915
2916       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
2917       while( heapRegionsItrCallee.hasNext() ) {
2918         ReferenceEdge edgeCallee     = heapRegionsItrCallee.next();
2919         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
2920         Integer idChildCallee  = hrnChildCallee.getID();
2921
2922         // only address this edge if it is not a special initial edge
2923         if( !edgeCallee.isInitialParam() ) {
2924
2925           // now we know that in the callee method's ownership graph
2926           // there is a heap region->heap region reference edge given
2927           // by heap region pointers:
2928           // hrnCallee -> heapChildCallee
2929           //
2930           // or by the ownership-graph independent ID's:
2931           // idCallee -> idChildCallee
2932
2933           // make the edge with src and dst so beta info is
2934           // calculated once, then copy it for each new edge in caller
2935
2936           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
2937                                                                     null,
2938                                                                     edgeCallee.getType(),
2939                                                                     edgeCallee.getField(),
2940                                                                     false,
2941                                                                     funcScriptR(toShadowTokens(ogCallee,
2942                                                                                                edgeCallee.getBeta()
2943                                                                                                ),
2944                                                                                 ogCallee,
2945                                                                                 mc)
2946                                                                     );
2947
2948           rewriteCallerReachability(bogusIndex,
2949                                     null,
2950                                     edgeNewInCallerTemplate,
2951                                     edgeNewInCallerTemplate.getBeta(),
2952                                     tokens2statesEmpty,
2953                                     paramIndex2rewrite_d_p,
2954                                     paramIndex2rewrite_d_s,
2955                                     paramIndex2rewriteD,
2956                                     ogCallee,
2957                                     false,
2958                                     null);
2959
2960           edgeNewInCallerTemplate.applyBetaNew();
2961
2962
2963           // So now make a set of possible source heaps in the caller graph
2964           // and a set of destination heaps in the caller graph, and make
2965           // a reference edge in the caller for every possible (src,dst) pair
2966           HashSet<HeapRegionNode> possibleCallerSrcs =
2967             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
2968                                                 (HeapRegionNode) edgeCallee.getSrc(),
2969                                                 pi2dr,
2970                                                 pi2r);
2971
2972           HashSet<HeapRegionNode> possibleCallerDsts =
2973             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
2974                                                 edgeCallee.getDst(),
2975                                                 pi2dr,
2976                                                 pi2r);
2977
2978           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
2979           Iterator srcItr = possibleCallerSrcs.iterator();
2980           while( srcItr.hasNext() ) {
2981             HeapRegionNode src = (HeapRegionNode) srcItr.next();
2982
2983             if( !hasMatchingField(src, edgeCallee) ) {
2984               // prune this source node possibility
2985               continue;
2986             }
2987
2988             Iterator dstItr = possibleCallerDsts.iterator();
2989             while( dstItr.hasNext() ) {
2990               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
2991
2992               if( !hasMatchingType(edgeCallee, dst) ) {
2993                 // prune
2994                 continue;
2995               }
2996
2997
2998               /*
2999                  //// KEEP THIS HACK AROUND FOR EXPERIMENTING WITH EDGE REMOVAL
3000                  TypeDescriptor tdX = src.getType();
3001                  TypeDescriptor tdY = dst.getType();
3002                  if( tdX != null && tdY != null ) {
3003                  if( tdX.toPrettyString().equals( "Object[]" ) &&
3004                     tdY.toPrettyString().equals( "D2" ) ) {
3005                   System.out.println( "Skipping an edge from Object[] -> D2 during call mapping" );
3006                   continue;
3007                  }
3008                  if( tdX.toPrettyString().equals( "Object[]" ) &&
3009                     tdY.toPrettyString().equals( "MessageList" ) ) {
3010                   System.out.println( "Skipping an edge from Object[] -> MessageList during call mapping" );
3011                   continue;
3012                  }
3013                  }
3014                */
3015
3016
3017               // otherwise the caller src and dst pair can match the edge, so make it
3018               TypeDescriptor tdNewEdge =
3019                 mostSpecificType(edgeCallee.getType(),
3020                                  hrnChildCallee.getType(),
3021                                  dst.getType()
3022                                  );
3023
3024               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
3025               edgeNewInCaller.setSrc(src);
3026               edgeNewInCaller.setDst(dst);
3027               edgeNewInCaller.setType(tdNewEdge);
3028
3029
3030               // handle taint info if callee created this edge
3031               // added by eom
3032               Set<Integer> pParamSet=idPrimary2paramIndexSet.get(dst.getID());
3033               Set<Integer> sParamSet=idSecondary2paramIndexSet.get(dst.getID());
3034               HashSet<Integer> paramSet=new  HashSet<Integer>();
3035               if(pParamSet!=null) {
3036                 paramSet.addAll(pParamSet);
3037               }
3038               if(sParamSet!=null) {
3039                 paramSet.addAll(sParamSet);
3040               }
3041               Iterator<Integer> paramIter=paramSet.iterator();
3042               int newTaintIdentifier=0;
3043               while(paramIter.hasNext()) {
3044                 Integer paramIdx=paramIter.next();
3045                 edgeNewInCaller.tainedBy(paramIdx);
3046               }
3047
3048               ReferenceEdge edgeExisting = src.getReferenceTo(dst,
3049                                                               edgeNewInCaller.getType(),
3050                                                               edgeNewInCaller.getField() );
3051               if( edgeExisting == null ) {
3052                 // if this edge doesn't exist in the caller, create it
3053                 addReferenceEdge(src, dst, edgeNewInCaller);
3054
3055               } else {
3056                 // if it already exists, merge with it
3057                 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
3058               }
3059             }
3060           }
3061         }
3062       }
3063     }
3064
3065
3066
3067     // return value may need to be assigned in caller
3068     TempDescriptor returnTemp = fc.getReturnTemp();
3069     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
3070
3071       LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
3072       clearReferenceEdgesFrom(lnLhsCaller, null, null, true);
3073
3074       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
3075       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
3076       while( edgeCalleeItr.hasNext() ) {
3077         ReferenceEdge edgeCallee     = edgeCalleeItr.next();
3078         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
3079
3080         // some edge types are not possible return values when we can
3081         // see what type variable we are assigning it to
3082         if( !isSuperiorType(returnTemp.getType(), edgeCallee.getType() ) ) {
3083           System.out.println("*** NOT EXPECTING TO SEE THIS: Throwing out "+edgeCallee+" for return temp "+returnTemp);
3084           // prune
3085           continue;
3086         }
3087
3088         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
3089                                                                   null,
3090                                                                   edgeCallee.getType(),
3091                                                                   edgeCallee.getField(),
3092                                                                   false,
3093                                                                   funcScriptR(toShadowTokens(ogCallee,
3094                                                                                              edgeCallee.getBeta() ),
3095                                                                               ogCallee,
3096                                                                               mc)
3097                                                                   );
3098         rewriteCallerReachability(bogusIndex,
3099                                   null,
3100                                   edgeNewInCallerTemplate,
3101                                   edgeNewInCallerTemplate.getBeta(),
3102                                   tokens2statesEmpty,
3103                                   paramIndex2rewrite_d_p,
3104                                   paramIndex2rewrite_d_s,
3105                                   paramIndex2rewriteD,
3106                                   ogCallee,
3107                                   false,
3108                                   null);
3109
3110         edgeNewInCallerTemplate.applyBetaNew();
3111
3112
3113         HashSet<HeapRegionNode> assignCallerRhs =
3114           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
3115                                               edgeCallee.getDst(),
3116                                               pi2dr,
3117                                               pi2r);
3118
3119         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
3120         while( itrHrn.hasNext() ) {
3121           HeapRegionNode hrnCaller = itrHrn.next();
3122
3123           // don't make edge in caller if it is disallowed by types
3124           if( !isSuperiorType(returnTemp.getType(), hrnCaller.getType() ) ) {
3125             // prune
3126             continue;
3127           }
3128
3129           if( !isSuperiorType(returnTemp.getType(), hrnChildCallee.getType() ) ) {
3130             // prune
3131             continue;
3132           }
3133
3134           if( !isSuperiorType(edgeCallee.getType(), hrnCaller.getType() ) ) {
3135             // prune
3136             continue;
3137           }
3138
3139           TypeDescriptor tdNewEdge =
3140             mostSpecificType(edgeCallee.getType(),
3141                              hrnChildCallee.getType(),
3142                              hrnCaller.getType()
3143                              );
3144
3145           // otherwise caller node can match callee edge, so make it
3146           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
3147           edgeNewInCaller.setSrc(lnLhsCaller);
3148           edgeNewInCaller.setDst(hrnCaller);
3149           edgeNewInCaller.setType(tdNewEdge);
3150
3151           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller,
3152                                                                   tdNewEdge,
3153                                                                   edgeNewInCaller.getField() );
3154           if( edgeExisting == null ) {
3155
3156             // if this edge doesn't exist in the caller, create it
3157             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
3158           } else {
3159             // if it already exists, merge with it
3160             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
3161           }
3162         }
3163       }
3164     }
3165
3166
3167     /*
3168        if( debugCallMap &&
3169         mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3170         fm.getMethod().getSymbol().equals( debugCallee )
3171         ) {
3172
3173        try {
3174         writeGraph("debug7JustBeforeMergeToKCapacity",
3175                    true,  // write labels (variables)
3176                    true,  // selectively hide intermediate temp vars
3177                    true,  // prune unreachable heap regions
3178                    false, // show back edges to confirm graph validity
3179                    false, // show parameter indices (unmaintained!)
3180                    true,  // hide subset reachability states
3181                    true); // hide edge taints
3182        } catch( IOException e ) {}
3183        }
3184      */
3185
3186
3187     // merge the shadow nodes of allocation sites back down to normal capacity
3188     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
3189     while( allocItr.hasNext() ) {
3190       AllocationSite as = allocItr.next();
3191
3192       // first age each allocation site enough times to make room for the shadow nodes
3193       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3194         age(as);
3195       }
3196
3197       // then merge the shadow summary into the normal summary
3198       HeapRegionNode hrnSummary = getSummaryNode(as);
3199       assert hrnSummary != null;
3200
3201       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
3202       assert hrnSummaryShadow != null;
3203
3204       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
3205
3206       // then clear off after merge
3207       clearReferenceEdgesFrom(hrnSummaryShadow, null, null, true);
3208       clearReferenceEdgesTo(hrnSummaryShadow, null, null, true);
3209       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
3210
3211       // then transplant shadow nodes onto the now clean normal nodes
3212       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3213
3214         Integer idIth        = as.getIthOldest(i);
3215         HeapRegionNode hrnIth       = id2hrn.get(idIth);
3216         Integer idIthShadow  = as.getIthOldestShadow(i);
3217         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
3218
3219         transferOnto(hrnIthShadow, hrnIth);
3220
3221         // clear off shadow nodes after transfer
3222         clearReferenceEdgesFrom(hrnIthShadow, null, null, true);
3223         clearReferenceEdgesTo(hrnIthShadow, null, null, true);
3224         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
3225       }
3226
3227       // finally, globally change shadow tokens into normal tokens
3228       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
3229       while( itrAllLabelNodes.hasNext() ) {
3230         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
3231         LabelNode ln = (LabelNode) me.getValue();
3232
3233         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
3234         while( itrEdges.hasNext() ) {
3235           unshadowTokens(as, itrEdges.next() );
3236         }
3237       }
3238
3239       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
3240       while( itrAllHRNodes.hasNext() ) {
3241         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
3242         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
3243
3244         unshadowTokens(as, hrnToAge);
3245
3246         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
3247         while( itrEdges.hasNext() ) {
3248           unshadowTokens(as, itrEdges.next() );
3249         }
3250       }
3251     }
3252
3253
3254     /*
3255        if( debugCallMap &&
3256         mc.getDescriptor().getSymbol().equals( debugCaller ) &&
3257         fm.getMethod().getSymbol().equals( debugCallee )
3258         ) {
3259
3260        try {
3261         writeGraph( "debug8JustBeforeSweep",
3262                     true,  // write labels (variables)
3263                     true,  // selectively hide intermediate temp vars
3264                     true,  // prune unreachable heap regions
3265                     false, // show back edges to confirm graph validity
3266                     false, // show parameter indices (unmaintained!)
3267                     true,  // hide subset reachability states
3268                     true); // hide edge taints
3269        } catch( IOException e ) {}
3270        }
3271      */
3272
3273
3274     // improve reachability as much as possible
3275     if( !DISABLE_GLOBAL_SWEEP ) {
3276       globalSweep();
3277     }
3278
3279
3280     if( debugCallMap &&
3281         mc.getDescriptor().getSymbol().equals(debugCaller) &&
3282         fm.getMethod().getSymbol().equals(debugCallee)
3283         ) {
3284
3285       try {
3286         writeGraph("debug9endResolveCall",
3287                    true,   // write labels (variables)
3288                    true,   // selectively hide intermediate temp vars
3289                    true,   // prune unreachable heap regions
3290                    false,  // show back edges to confirm graph validity
3291                    false,  // show parameter indices (unmaintained!)
3292                    true,   // hide subset reachability states
3293                    true);  // hide edge taints
3294       } catch( IOException e ) {
3295       }
3296       System.out.println("  "+mc+" done calling "+fm);
3297       ++x;
3298       if( x == debugCallMapCount ) {
3299         System.exit(0);
3300       }
3301     }
3302   }
3303
3304   static int x = 0;
3305
3306
3307   protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
3308
3309     // if no type, then it's a match-everything region
3310     TypeDescriptor tdSrc = src.getType();
3311     if( tdSrc == null ) {
3312       return true;
3313     }
3314
3315     if( tdSrc.isArray() ) {
3316       TypeDescriptor td = edge.getType();
3317       assert td != null;
3318
3319       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3320       assert tdSrcDeref != null;
3321
3322       if( !typeUtil.isSuperorType(tdSrcDeref, td) ) {
3323         return false;
3324       }
3325
3326       return edge.getField().equals(OwnershipAnalysis.arrayElementFieldName);
3327     }
3328
3329     // if it's not a class, it doesn't have any fields to match
3330     if( !tdSrc.isClass() ) {
3331       return false;
3332     }
3333
3334     ClassDescriptor cd = tdSrc.getClassDesc();
3335     while( cd != null ) {
3336       Iterator fieldItr = cd.getFields();
3337
3338       while( fieldItr.hasNext() ) {
3339         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
3340
3341         if( fd.getType().equals(edge.getType() ) &&
3342             fd.getSymbol().equals(edge.getField() ) ) {
3343           return true;
3344         }
3345       }
3346
3347       cd = cd.getSuperDesc();
3348     }
3349
3350     // otherwise it is a class with fields
3351     // but we didn't find a match
3352     return false;
3353   }
3354
3355
3356   protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
3357
3358     // if the region has no type, matches everything
3359     TypeDescriptor tdDst = dst.getType();
3360     if( tdDst == null ) {
3361       return true;
3362     }
3363
3364     // if the type is not a class or an array, don't
3365     // match because primitives are copied, no aliases
3366     ClassDescriptor cdDst = tdDst.getClassDesc();
3367     if( cdDst == null && !tdDst.isArray() ) {
3368       return false;
3369     }
3370
3371     // if the edge type is null, it matches everything
3372     TypeDescriptor tdEdge = edge.getType();
3373     if( tdEdge == null ) {
3374       return true;
3375     }
3376
3377     return typeUtil.isSuperorType(tdEdge, tdDst);
3378   }
3379
3380
3381   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
3382     edge.setBeta(edge.getBeta().unshadowTokens(as) );
3383   }
3384
3385   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
3386     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
3387   }
3388
3389
3390   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
3391                                          ReachabilitySet rsIn) {
3392
3393     ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
3394
3395     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
3396     while( allocItr.hasNext() ) {
3397       AllocationSite as = allocItr.next();
3398
3399       rsOut = rsOut.toShadowTokens(as);
3400     }
3401
3402     return rsOut.makeCanonical();
3403   }
3404
3405
3406   private void rewriteCallerReachability(Integer paramIndex,
3407                                          HeapRegionNode hrn,
3408                                          ReferenceEdge edge,
3409                                          ReachabilitySet rules,
3410                                          Hashtable<TokenTuple, ReachabilitySet> tokens2states,
3411                                          Hashtable<Integer,    ReachabilitySet> paramIndex2rewrite_d_p,
3412                                          Hashtable<Integer,    ReachabilitySet> paramIndex2rewrite_d_s,
3413                                          Hashtable<Integer,    ReachabilitySet> paramIndex2rewriteD,
3414                                          OwnershipGraph ogCallee,
3415                                          boolean makeChangeSet,
3416                                          Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
3417
3418     assert(hrn == null && edge != null) ||
3419     (hrn != null && edge == null);
3420
3421     assert rules         != null;
3422     assert tokens2states != null;
3423
3424     ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
3425
3426     // for initializing structures in this method
3427     TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
3428
3429     // use this to construct a change set if required; the idea is to
3430     // map every partially rewritten token tuple set to the set of
3431     // caller-context token tuple sets that were used to generate it
3432     Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
3433       new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
3434     rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
3435
3436
3437     Iterator<TokenTupleSet> rulesItr = rules.iterator();
3438     while(rulesItr.hasNext()) {
3439       TokenTupleSet rule = rulesItr.next();
3440
3441       ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
3442
3443       Iterator<TokenTuple> ruleItr = rule.iterator();
3444       while(ruleItr.hasNext()) {
3445         TokenTuple ttCallee = ruleItr.next();
3446
3447         // compute the possibilities for rewriting this callee token
3448         ReachabilitySet ttCalleeRewrites = null;
3449         boolean callerSourceUsed = false;
3450
3451         if( tokens2states.containsKey(ttCallee) ) {
3452           callerSourceUsed = true;
3453           ttCalleeRewrites = tokens2states.get(ttCallee);
3454           assert ttCalleeRewrites != null;
3455
3456         } else if( ogCallee.paramTokenPrimary2paramIndex.containsKey(ttCallee) ) {
3457           // use little d_p
3458           Integer paramIndex_j = ogCallee.paramTokenPrimary2paramIndex.get(ttCallee);
3459           assert paramIndex_j != null;
3460           ttCalleeRewrites = paramIndex2rewrite_d_p.get(paramIndex_j);
3461           assert ttCalleeRewrites != null;
3462
3463         } else if( ogCallee.paramTokenSecondary2paramIndex.containsKey(ttCallee) ) {
3464           // use little d_s
3465           Integer paramIndex_j = ogCallee.paramTokenSecondary2paramIndex.get(ttCallee);
3466           assert paramIndex_j != null;
3467           ttCalleeRewrites = paramIndex2rewrite_d_s.get(paramIndex_j);
3468           assert ttCalleeRewrites != null;
3469
3470         } else if( ogCallee.paramTokenSecondaryPlus2paramIndex.containsKey(ttCallee) ) {
3471           // worse, use big D
3472           Integer paramIndex_j = ogCallee.paramTokenSecondaryPlus2paramIndex.get(ttCallee);
3473           assert paramIndex_j != null;
3474           ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
3475           assert ttCalleeRewrites != null;
3476
3477         } else if( ogCallee.paramTokenSecondaryStar2paramIndex.containsKey(ttCallee) ) {
3478           // worse, use big D
3479           Integer paramIndex_j = ogCallee.paramTokenSecondaryStar2paramIndex.get(ttCallee);
3480           assert paramIndex_j != null;
3481           ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
3482           assert ttCalleeRewrites != null;
3483
3484         } else {
3485           // otherwise there's no need for a rewrite, just pass this one on
3486           TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
3487           ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
3488         }
3489
3490         // branch every version of the working rewritten rule with
3491         // the possibilities for rewriting the current callee token
3492         ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
3493
3494         Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
3495         while( rewrittenRuleItr.hasNext() ) {
3496           TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
3497
3498           Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
3499           while( ttCalleeRewritesItr.hasNext() ) {
3500             TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
3501
3502             TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity(ttsBranch);
3503
3504             if( makeChangeSet ) {
3505               // in order to keep the list of source token tuple sets
3506               // start with the sets used to make the partially rewritten
3507               // rule up to this point
3508               HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewritten);
3509               assert sourceSets != null;
3510
3511               // make a shallow copy for possible modification
3512               sourceSets = (HashSet<TokenTupleSet>)sourceSets.clone();
3513
3514               // if we used something from the caller to rewrite it, remember
3515               if( callerSourceUsed ) {
3516                 sourceSets.add(ttsBranch);
3517               }
3518
3519               // set mapping for the further rewritten rule
3520               rewritten2source.put(ttsRewrittenNext, sourceSets);
3521             }
3522
3523             rewrittenRuleWithTTCallee =
3524               rewrittenRuleWithTTCallee.union(ttsRewrittenNext);
3525           }
3526         }
3527
3528         // now the rewritten rule's possibilities have been extended by
3529         // rewriting the current callee token, remember result
3530         rewrittenRule = rewrittenRuleWithTTCallee;
3531       }
3532
3533       // the rule has been entirely rewritten into the caller context
3534       // now, so add it to the new reachability information
3535       callerReachabilityNew =
3536         callerReachabilityNew.union(rewrittenRule);
3537     }
3538
3539     if( makeChangeSet ) {
3540       ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
3541
3542       // each possibility for the final reachability should have a set of
3543       // caller sources mapped to it, use to create the change set
3544       Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
3545       while( callerReachabilityItr.hasNext() ) {
3546         TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
3547         HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewrittenFinal);
3548         assert sourceSets != null;
3549
3550         Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
3551         while( sourceSetsItr.hasNext() ) {
3552           TokenTupleSet ttsSource = sourceSetsItr.next();
3553
3554           callerChangeSet =
3555             callerChangeSet.union(new ChangeTuple(ttsSource, ttsRewrittenFinal) );
3556         }
3557       }
3558
3559       assert edgePlannedChanges != null;
3560       edgePlannedChanges.put(edge, callerChangeSet);
3561     }
3562
3563     if( hrn == null ) {
3564       edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
3565     } else {
3566       hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
3567     }
3568   }
3569
3570
3571
3572   private HashSet<HeapRegionNode>
3573   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
3574                                       HeapRegionNode hrnCallee,
3575                                       Hashtable<Integer, Set<HeapRegionNode> > pi2dr,
3576                                       Hashtable<Integer, Set<HeapRegionNode> > pi2r
3577                                       ) {
3578
3579     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
3580
3581     Set<Integer> paramIndicesCallee_p = ogCallee.idPrimary2paramIndexSet.get(hrnCallee.getID() );
3582     Set<Integer> paramIndicesCallee_s = ogCallee.idSecondary2paramIndexSet.get(hrnCallee.getID() );
3583
3584     if( paramIndicesCallee_p == null &&
3585         paramIndicesCallee_s == null ) {
3586       // this is a node allocated in the callee and it has
3587       // exactly one shadow node in the caller to map to
3588       AllocationSite as = hrnCallee.getAllocationSite();
3589       assert as != null;
3590
3591       int age = as.getAgeCategory(hrnCallee.getID() );
3592       assert age != AllocationSite.AGE_notInThisSite;
3593
3594       Integer idCaller;
3595       if( age == AllocationSite.AGE_summary ) {
3596         idCaller = as.getSummaryShadow();
3597
3598       } else if( age == AllocationSite.AGE_oldest ) {
3599         idCaller = as.getOldestShadow();
3600
3601       } else {
3602         assert age == AllocationSite.AGE_in_I;
3603
3604         Integer I = as.getAge(hrnCallee.getID() );
3605         assert I != null;
3606
3607         idCaller = as.getIthOldestShadow(I);
3608       }
3609
3610       assert id2hrn.containsKey(idCaller);
3611       possibleCallerHRNs.add(id2hrn.get(idCaller) );
3612
3613       return possibleCallerHRNs;
3614     }
3615
3616     // find out what primary objects this might be
3617     if( paramIndicesCallee_p != null ) {
3618       // this is a node that was created to represent a parameter
3619       // so it maps to some regions directly reachable from the arg labels
3620       Iterator<Integer> itrIndex = paramIndicesCallee_p.iterator();
3621       while( itrIndex.hasNext() ) {
3622         Integer paramIndexCallee = itrIndex.next();
3623         assert pi2dr.containsKey(paramIndexCallee);
3624         possibleCallerHRNs.addAll(pi2dr.get(paramIndexCallee) );
3625       }
3626     }
3627
3628     // find out what secondary objects this might be
3629     if( paramIndicesCallee_s != null ) {
3630       // this is a node that was created to represent objs reachable from
3631       // some parameter, so it maps to regions reachable from the arg labels
3632       Iterator<Integer> itrIndex = paramIndicesCallee_s.iterator();
3633       while( itrIndex.hasNext() ) {
3634         Integer paramIndexCallee = itrIndex.next();
3635         assert pi2r.containsKey(paramIndexCallee);
3636         possibleCallerHRNs.addAll(pi2r.get(paramIndexCallee) );
3637       }
3638     }
3639
3640     // TODO: is this true?
3641     // one of the two cases above should have put something in here
3642     //assert !possibleCallerHRNs.isEmpty();
3643
3644     return possibleCallerHRNs;
3645   }
3646
3647
3648
3649   ////////////////////////////////////////////////////
3650   //
3651   //  This global sweep is an optional step to prune
3652   //  reachability sets that are not internally
3653   //  consistent with the global graph.  It should be
3654   //  invoked after strong updates or method calls.
3655   //
3656   ////////////////////////////////////////////////////
3657   public void globalSweep() {
3658
3659     // boldB is part of the phase 1 sweep
3660     Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
3661       new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
3662
3663     // visit every heap region to initialize alphaNew and calculate boldB
3664     Set hrns = id2hrn.entrySet();
3665     Iterator itrHrns = hrns.iterator();
3666     while( itrHrns.hasNext() ) {
3667       Map.Entry me = (Map.Entry)itrHrns.next();
3668       Integer token = (Integer) me.getKey();
3669       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3670
3671       // assert that this node and incoming edges have clean alphaNew
3672       // and betaNew sets, respectively
3673       assert rsEmpty.equals(hrn.getAlphaNew() );
3674
3675       Iterator<ReferenceEdge> itrRers = hrn.iteratorToReferencers();
3676       while( itrRers.hasNext() ) {
3677         ReferenceEdge edge = itrRers.next();
3678         assert rsEmpty.equals(edge.getBetaNew() );
3679       }
3680
3681       // calculate boldB for this flagged node
3682       if( hrn.isFlagged() || hrn.isParameter() ) {
3683
3684         Hashtable<ReferenceEdge, ReachabilitySet> boldB_f =
3685           new Hashtable<ReferenceEdge, ReachabilitySet>();
3686
3687         Set<ReferenceEdge> workSetEdges = new HashSet<ReferenceEdge>();
3688
3689         // initial boldB_f constraints
3690         Iterator<ReferenceEdge> itrRees = hrn.iteratorToReferencees();
3691         while( itrRees.hasNext() ) {
3692           ReferenceEdge edge = itrRees.next();
3693
3694           assert !boldB.containsKey(edge);
3695           boldB_f.put(edge, edge.getBeta() );
3696
3697           assert !workSetEdges.contains(edge);
3698           workSetEdges.add(edge);
3699         }
3700
3701         // enforce the boldB_f constraint at edges until we reach a fixed point
3702         while( !workSetEdges.isEmpty() ) {
3703           ReferenceEdge edge = workSetEdges.iterator().next();
3704           workSetEdges.remove(edge);
3705
3706           Iterator<ReferenceEdge> itrPrime = edge.getDst().iteratorToReferencees();
3707           while( itrPrime.hasNext() ) {
3708             ReferenceEdge edgePrime = itrPrime.next();
3709
3710             ReachabilitySet prevResult   = boldB_f.get(edgePrime);
3711             ReachabilitySet intersection = boldB_f.get(edge).intersection(edgePrime.getBeta() );
3712
3713             if( prevResult == null ||
3714                 prevResult.union(intersection).size() > prevResult.size() ) {
3715
3716               if( prevResult == null ) {
3717                 boldB_f.put(edgePrime, edgePrime.getBeta().union(intersection) );
3718               } else {
3719                 boldB_f.put(edgePrime, prevResult.union(intersection) );
3720               }
3721               workSetEdges.add(edgePrime);
3722             }
3723           }
3724         }
3725
3726         boldB.put(token, boldB_f);
3727       }
3728     }
3729
3730
3731     // use boldB to prune tokens from alpha states that are impossible
3732     // and propagate the differences backwards across edges
3733     HashSet<ReferenceEdge> edgesForPropagation = new HashSet<ReferenceEdge>();
3734
3735     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
3736       new Hashtable<ReferenceEdge, ChangeTupleSet>();
3737
3738     hrns = id2hrn.entrySet();
3739     itrHrns = hrns.iterator();
3740     while( itrHrns.hasNext() ) {
3741       Map.Entry me = (Map.Entry)itrHrns.next();
3742       Integer token = (Integer) me.getKey();
3743       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3744
3745       // never remove the identity token from a flagged region
3746       // because it is trivially satisfied
3747       TokenTuple ttException = new TokenTuple(token,
3748                                               !hrn.isSingleObject(),
3749                                               TokenTuple.ARITY_ONE).makeCanonical();
3750
3751       ChangeTupleSet cts = new ChangeTupleSet().makeCanonical();
3752
3753       // mark tokens for removal
3754       Iterator<TokenTupleSet> stateItr = hrn.getAlpha().iterator();
3755       while( stateItr.hasNext() ) {
3756         TokenTupleSet ttsOld = stateItr.next();
3757
3758         TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical();
3759
3760         Iterator<TokenTuple> ttItr = ttsOld.iterator();
3761         while( ttItr.hasNext() ) {
3762           TokenTuple ttOld = ttItr.next();
3763
3764           // never remove the identity token from a flagged region
3765           // because it is trivially satisfied
3766           if( hrn.isFlagged() || hrn.isParameter() ) {
3767             if( ttOld == ttException ) {
3768               continue;
3769             }
3770           }
3771
3772           // does boldB_ttOld allow this token?
3773           boolean foundState = false;
3774           Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3775           while( incidentEdgeItr.hasNext() ) {
3776             ReferenceEdge incidentEdge = incidentEdgeItr.next();
3777
3778             // if it isn't allowed, mark for removal
3779             Integer idOld = ttOld.getToken();
3780             assert id2hrn.containsKey(idOld);
3781             Hashtable<ReferenceEdge, ReachabilitySet> B = boldB.get(idOld);
3782             ReachabilitySet boldB_ttOld_incident = B.get(incidentEdge);  // B is NULL!
3783             if( boldB_ttOld_incident != null &&
3784                 boldB_ttOld_incident.contains(ttsOld) ) {
3785               foundState = true;
3786             }
3787           }
3788
3789           if( !foundState ) {
3790             markedTokens = markedTokens.add(ttOld);
3791           }
3792         }
3793
3794         // if there is nothing marked, just move on
3795         if( markedTokens.isEmpty() ) {
3796           hrn.setAlphaNew(hrn.getAlphaNew().union(ttsOld) );
3797           continue;
3798         }
3799
3800         // remove all marked tokens and establish a change set that should
3801         // propagate backwards over edges from this node
3802         TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical();
3803         ttItr = ttsOld.iterator();
3804         while( ttItr.hasNext() ) {
3805           TokenTuple ttOld = ttItr.next();
3806
3807           if( !markedTokens.containsTuple(ttOld) ) {
3808             ttsPruned = ttsPruned.union(ttOld);
3809           }
3810         }
3811         assert !ttsOld.equals(ttsPruned);
3812
3813         hrn.setAlphaNew(hrn.getAlphaNew().union(ttsPruned) );
3814         ChangeTuple ct = new ChangeTuple(ttsOld, ttsPruned).makeCanonical();
3815         cts = cts.union(ct);
3816       }
3817
3818       // throw change tuple set on all incident edges
3819       if( !cts.isEmpty() ) {
3820         Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3821         while( incidentEdgeItr.hasNext() ) {
3822           ReferenceEdge incidentEdge = incidentEdgeItr.next();
3823
3824           edgesForPropagation.add(incidentEdge);
3825
3826           if( edgePlannedChanges.get(incidentEdge) == null ) {
3827             edgePlannedChanges.put(incidentEdge, cts);
3828           } else {
3829             edgePlannedChanges.put(
3830               incidentEdge,
3831               edgePlannedChanges.get(incidentEdge).union(cts)
3832               );
3833           }
3834         }
3835       }
3836     }
3837
3838     HashSet<ReferenceEdge> edgesUpdated = new HashSet<ReferenceEdge>();
3839
3840     propagateTokensOverEdges(edgesForPropagation,
3841                              edgePlannedChanges,
3842                              edgesUpdated);
3843
3844     // at the end of the 1st phase reference edges have
3845     // beta, betaNew that correspond to beta and betaR
3846     //
3847     // commit beta<-betaNew, so beta=betaR and betaNew
3848     // will represent the beta' calculation in 2nd phase
3849     //
3850     // commit alpha<-alphaNew because it won't change
3851     HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
3852
3853     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3854     while( nodeItr.hasNext() ) {
3855       HeapRegionNode hrn = nodeItr.next();
3856       hrn.applyAlphaNew();
3857       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
3858       while( itrRes.hasNext() ) {
3859         res.add(itrRes.next() );
3860       }
3861     }
3862
3863
3864     // 2nd phase
3865     Iterator<ReferenceEdge> edgeItr = res.iterator();
3866     while( edgeItr.hasNext() ) {
3867       ReferenceEdge edge = edgeItr.next();
3868       HeapRegionNode hrn = edge.getDst();
3869
3870       // commit results of last phase
3871       if( edgesUpdated.contains(edge) ) {
3872         edge.applyBetaNew();
3873       }
3874
3875       // compute intial condition of 2nd phase
3876       edge.setBetaNew(edge.getBeta().intersection(hrn.getAlpha() ) );
3877     }
3878
3879     // every edge in the graph is the initial workset
3880     Set<ReferenceEdge> edgeWorkSet = (Set) res.clone();
3881     while( !edgeWorkSet.isEmpty() ) {
3882       ReferenceEdge edgePrime = edgeWorkSet.iterator().next();
3883       edgeWorkSet.remove(edgePrime);
3884
3885       OwnershipNode on = edgePrime.getSrc();
3886       if( !(on instanceof HeapRegionNode) ) {
3887         continue;
3888       }
3889       HeapRegionNode hrn = (HeapRegionNode) on;
3890
3891       Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
3892       while( itrEdge.hasNext() ) {
3893         ReferenceEdge edge = itrEdge.next();
3894
3895         ReachabilitySet prevResult = edge.getBetaNew();
3896         assert prevResult != null;
3897
3898         ReachabilitySet intersection = edge.getBeta().intersection(edgePrime.getBetaNew() );
3899
3900         if( prevResult.union(intersection).size() > prevResult.size() ) {
3901           edge.setBetaNew(prevResult.union(intersection) );
3902           edgeWorkSet.add(edge);
3903         }
3904       }
3905     }
3906
3907     // commit beta' (beta<-betaNew)
3908     edgeItr = res.iterator();
3909     while( edgeItr.hasNext() ) {
3910       edgeItr.next().applyBetaNew();
3911     }
3912   }
3913
3914
3915
3916   ////////////////////////////////////////////////////
3917   // in merge() and equals() methods the suffix A
3918   // represents the passed in graph and the suffix
3919   // B refers to the graph in this object
3920   // Merging means to take the incoming graph A and
3921   // merge it into B, so after the operation graph B
3922   // is the final result.
3923   ////////////////////////////////////////////////////
3924   public void merge(OwnershipGraph og) {
3925
3926     if( og == null ) {
3927       return;
3928     }
3929
3930     mergeOwnershipNodes(og);
3931     mergeReferenceEdges(og);
3932     mergeParamIndexMappings(og);
3933     mergeAllocationSites(og);
3934     mergeAccessPaths(og);
3935     mergeTempAndLabelCategories(og);
3936   }
3937
3938
3939   protected void mergeOwnershipNodes(OwnershipGraph og) {
3940     Set sA = og.id2hrn.entrySet();
3941     Iterator iA = sA.iterator();
3942     while( iA.hasNext() ) {
3943       Map.Entry meA  = (Map.Entry)iA.next();
3944       Integer idA  = (Integer)        meA.getKey();
3945       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3946
3947       // if this graph doesn't have a node the
3948       // incoming graph has, allocate it
3949       if( !id2hrn.containsKey(idA) ) {
3950         HeapRegionNode hrnB = hrnA.copy();
3951         id2hrn.put(idA, hrnB);
3952         gid2hrn.put(hrnA.getGloballyUniqueIdentifier(), hrnB);
3953
3954       } else {
3955         // otherwise this is a node present in both graphs
3956         // so make the new reachability set a union of the
3957         // nodes' reachability sets
3958         HeapRegionNode hrnB = id2hrn.get(idA);
3959         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
3960       }
3961     }
3962
3963     // now add any label nodes that are in graph B but
3964     // not in A
3965     sA = og.td2ln.entrySet();
3966     iA = sA.iterator();
3967     while( iA.hasNext() ) {
3968       Map.Entry meA = (Map.Entry)iA.next();
3969       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3970       LabelNode lnA = (LabelNode)      meA.getValue();
3971
3972       // if the label doesn't exist in B, allocate and add it
3973       LabelNode lnB = getLabelNodeFromTemp(tdA);
3974     }
3975   }
3976
3977   protected void mergeReferenceEdges(OwnershipGraph og) {
3978
3979     // heap regions
3980     Set sA = og.id2hrn.entrySet();
3981     Iterator iA = sA.iterator();
3982     while( iA.hasNext() ) {
3983       Map.Entry meA  = (Map.Entry)iA.next();
3984       Integer idA  = (Integer)        meA.getKey();
3985       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3986
3987       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3988       while( heapRegionsItrA.hasNext() ) {
3989         ReferenceEdge edgeA     = heapRegionsItrA.next();
3990         HeapRegionNode hrnChildA = edgeA.getDst();
3991         Integer idChildA  = hrnChildA.getID();
3992
3993         // at this point we know an edge in graph A exists
3994         // idA -> idChildA, does this exist in B?
3995         assert id2hrn.containsKey(idA);
3996         HeapRegionNode hrnB        = id2hrn.get(idA);
3997         ReferenceEdge edgeToMerge = null;
3998
3999         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
4000         while( heapRegionsItrB.hasNext() &&
4001                edgeToMerge == null          ) {
4002
4003           ReferenceEdge edgeB     = heapRegionsItrB.next();
4004           HeapRegionNode hrnChildB = edgeB.getDst();
4005           Integer idChildB  = hrnChildB.getID();
4006
4007           // don't use the ReferenceEdge.equals() here because
4008           // we're talking about existence between graphs
4009           if( idChildB.equals(idChildA) &&
4010               edgeB.typeAndFieldEquals(edgeA) ) {
4011
4012             edgeToMerge = edgeB;
4013           }
4014         }
4015
4016         // if the edge from A was not found in B,
4017         // add it to B.
4018         if( edgeToMerge == null ) {
4019           assert id2hrn.containsKey(idChildA);
4020           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
4021           edgeToMerge = edgeA.copy();
4022           edgeToMerge.setSrc(hrnB);
4023           edgeToMerge.setDst(hrnChildB);
4024           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
4025         }
4026         // otherwise, the edge already existed in both graphs
4027         // so merge their reachability sets
4028         else {
4029           // just replace this beta set with the union
4030           assert edgeToMerge != null;
4031           edgeToMerge.setBeta(
4032             edgeToMerge.getBeta().union(edgeA.getBeta() )
4033             );
4034           //TODO eom
4035           edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
4036           if( !edgeA.isInitialParam() ) {
4037             edgeToMerge.setIsInitialParam(false);
4038           }
4039         }
4040       }
4041     }
4042
4043     // and then again with label nodes
4044     sA = og.td2ln.entrySet();
4045     iA = sA.iterator();
4046     while( iA.hasNext() ) {
4047       Map.Entry meA = (Map.Entry)iA.next();
4048       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4049       LabelNode lnA = (LabelNode)      meA.getValue();
4050
4051       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
4052       while( heapRegionsItrA.hasNext() ) {
4053         ReferenceEdge edgeA     = heapRegionsItrA.next();
4054         HeapRegionNode hrnChildA = edgeA.getDst();
4055         Integer idChildA  = hrnChildA.getID();
4056
4057         // at this point we know an edge in graph A exists
4058         // tdA -> idChildA, does this exist in B?
4059         assert td2ln.containsKey(tdA);
4060         LabelNode lnB         = td2ln.get(tdA);
4061         ReferenceEdge edgeToMerge = null;
4062
4063         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
4064         while( heapRegionsItrB.hasNext() &&
4065                edgeToMerge == null          ) {
4066
4067           ReferenceEdge edgeB     = heapRegionsItrB.next();
4068           HeapRegionNode hrnChildB = edgeB.getDst();
4069           Integer idChildB  = hrnChildB.getID();
4070
4071           // don't use the ReferenceEdge.equals() here because
4072           // we're talking about existence between graphs
4073           if( idChildB.equals(idChildA) &&
4074               edgeB.typeAndFieldEquals(edgeA) ) {
4075
4076             edgeToMerge = edgeB;
4077           }
4078         }
4079
4080         // if the edge from A was not found in B,
4081         // add it to B.
4082         if( edgeToMerge == null ) {
4083           assert id2hrn.containsKey(idChildA);
4084           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
4085           edgeToMerge = edgeA.copy();
4086           edgeToMerge.setSrc(lnB);
4087           edgeToMerge.setDst(hrnChildB);
4088           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
4089         }
4090         // otherwise, the edge already existed in both graphs
4091         // so merge their reachability sets
4092         else {
4093           // just replace this beta set with the union
4094           edgeToMerge.setBeta(
4095             edgeToMerge.getBeta().union(edgeA.getBeta() )
4096             );
4097           edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier());
4098           if( !edgeA.isInitialParam() ) {
4099             edgeToMerge.setIsInitialParam(false);
4100           }
4101         }
4102       }
4103     }
4104   }
4105
4106   // you should only merge ownership graphs that have the
4107   // same number of parameters, or if one or both parameter
4108   // index tables are empty
4109   protected void mergeParamIndexMappings(OwnershipGraph og) {
4110
4111     if( idPrimary2paramIndexSet.size() == 0 ) {
4112
4113       idPrimary2paramIndexSet            = og.idPrimary2paramIndexSet;
4114       paramIndex2idPrimary               = og.paramIndex2idPrimary;
4115
4116       idSecondary2paramIndexSet          = og.idSecondary2paramIndexSet;
4117       paramIndex2idSecondary             = og.paramIndex2idSecondary;
4118
4119       paramIndex2tdQ                     = og.paramIndex2tdQ;
4120       paramIndex2tdR                     = og.paramIndex2tdR;
4121
4122       paramTokenPrimary2paramIndex       = og.paramTokenPrimary2paramIndex;
4123       paramIndex2paramTokenPrimary       = og.paramIndex2paramTokenPrimary;
4124
4125       paramTokenSecondary2paramIndex     = og.paramTokenSecondary2paramIndex;
4126       paramIndex2paramTokenSecondary     = og.paramIndex2paramTokenSecondary;
4127       paramTokenSecondaryPlus2paramIndex = og.paramTokenSecondaryPlus2paramIndex;
4128       paramIndex2paramTokenSecondaryPlus = og.paramIndex2paramTokenSecondaryPlus;
4129       paramTokenSecondaryStar2paramIndex = og.paramTokenSecondaryStar2paramIndex;
4130       paramIndex2paramTokenSecondaryStar = og.paramIndex2paramTokenSecondaryStar;
4131
4132       return;
4133     }
4134
4135     if( og.idPrimary2paramIndexSet.size() == 0 ) {
4136
4137       og.idPrimary2paramIndexSet            = idPrimary2paramIndexSet;
4138       og.paramIndex2idPrimary               = paramIndex2idPrimary;
4139
4140       og.idSecondary2paramIndexSet          = idSecondary2paramIndexSet;
4141       og.paramIndex2idSecondary             = paramIndex2idSecondary;
4142
4143       og.paramIndex2tdQ                     = paramIndex2tdQ;
4144       og.paramIndex2tdR                     = paramIndex2tdR;
4145
4146       og.paramTokenPrimary2paramIndex       = paramTokenPrimary2paramIndex;
4147       og.paramIndex2paramTokenPrimary       = paramIndex2paramTokenPrimary;
4148
4149       og.paramTokenSecondary2paramIndex     = paramTokenSecondary2paramIndex;
4150       og.paramIndex2paramTokenSecondary     = paramIndex2paramTokenSecondary;
4151       og.paramTokenSecondaryPlus2paramIndex = paramTokenSecondaryPlus2paramIndex;
4152       og.paramIndex2paramTokenSecondaryPlus = paramIndex2paramTokenSecondaryPlus;
4153       og.paramTokenSecondaryStar2paramIndex = paramTokenSecondaryStar2paramIndex;
4154       og.paramIndex2paramTokenSecondaryStar = paramIndex2paramTokenSecondaryStar;
4155
4156       return;
4157     }
4158
4159     assert idPrimary2paramIndexSet.size()   == og.idPrimary2paramIndexSet.size();
4160     assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
4161   }
4162
4163   protected void mergeAllocationSites(OwnershipGraph og) {
4164     allocationSites.addAll(og.allocationSites);
4165   }
4166
4167   protected void mergeAccessPaths(OwnershipGraph og) {
4168     UtilAlgorithms.mergeHashtablesWithHashSetValues(temp2accessPaths,
4169                                                     og.temp2accessPaths);
4170   }
4171
4172   protected void mergeTempAndLabelCategories(OwnershipGraph og) {
4173     outOfScopeTemps.addAll(og.outOfScopeTemps);
4174     outOfScopeLabels.addAll(og.outOfScopeLabels);
4175     parameterTemps.addAll(og.parameterTemps);
4176     parameterLabels.addAll(og.parameterLabels);
4177   }
4178
4179
4180
4181   // it is necessary in the equals() member functions
4182   // to "check both ways" when comparing the data
4183   // structures of two graphs.  For instance, if all
4184   // edges between heap region nodes in graph A are
4185   // present and equal in graph B it is not sufficient
4186   // to say the graphs are equal.  Consider that there
4187   // may be edges in graph B that are not in graph A.
4188   // the only way to know that all edges in both graphs
4189   // are equally present is to iterate over both data
4190   // structures and compare against the other graph.
4191   public boolean equals(OwnershipGraph og) {
4192
4193     if( og == null ) {
4194       return false;
4195     }
4196
4197     if( !areHeapRegionNodesEqual(og) ) {
4198       return false;
4199     }
4200
4201     if( !areLabelNodesEqual(og) ) {
4202       return false;
4203     }
4204
4205     if( !areReferenceEdgesEqual(og) ) {
4206       return false;
4207     }
4208
4209     if( !areParamIndexMappingsEqual(og) ) {
4210       return false;
4211     }
4212
4213     if( !areAccessPathsEqual(og) ) {
4214       return false;
4215     }
4216
4217     // if everything is equal up to this point,
4218     // assert that allocationSites is also equal--
4219     // this data is redundant and kept for efficiency
4220     assert allocationSites.equals(og.allocationSites);
4221     assert outOfScopeTemps.equals(og.outOfScopeTemps);
4222     assert outOfScopeLabels.equals(og.outOfScopeLabels);
4223     assert parameterTemps.equals(og.parameterTemps);
4224     assert parameterLabels.equals(og.parameterLabels);
4225
4226     return true;
4227   }
4228
4229   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
4230
4231     if( !areallHRNinAalsoinBandequal(this, og) ) {
4232       return false;
4233     }
4234
4235     if( !areallHRNinAalsoinBandequal(og, this) ) {
4236       return false;
4237     }
4238
4239     return true;
4240   }
4241
4242   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
4243                                                        OwnershipGraph ogB) {
4244     Set sA = ogA.id2hrn.entrySet();
4245     Iterator iA = sA.iterator();
4246     while( iA.hasNext() ) {
4247       Map.Entry meA  = (Map.Entry)iA.next();
4248       Integer idA  = (Integer)        meA.getKey();
4249       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4250
4251       if( !ogB.id2hrn.containsKey(idA) ) {
4252         return false;
4253       }
4254
4255       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4256       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
4257         return false;
4258       }
4259     }
4260
4261     return true;
4262   }
4263
4264
4265   protected boolean areLabelNodesEqual(OwnershipGraph og) {
4266
4267     if( !areallLNinAalsoinBandequal(this, og) ) {
4268       return false;
4269     }
4270
4271     if( !areallLNinAalsoinBandequal(og, this) ) {
4272       return false;
4273     }
4274
4275     return true;
4276   }
4277
4278   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
4279                                                       OwnershipGraph ogB) {
4280     Set sA = ogA.td2ln.entrySet();
4281     Iterator iA = sA.iterator();
4282     while( iA.hasNext() ) {
4283       Map.Entry meA = (Map.Entry)iA.next();
4284       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4285
4286       if( !ogB.td2ln.containsKey(tdA) ) {
4287         return false;
4288       }
4289     }
4290
4291     return true;
4292   }
4293
4294
4295   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
4296     if( !areallREinAandBequal(this, og) ) {
4297       return false;
4298     }
4299
4300     return true;
4301   }
4302
4303   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
4304                                                 OwnershipGraph ogB) {
4305
4306     // check all the heap region->heap region edges
4307     Set sA = ogA.id2hrn.entrySet();
4308     Iterator iA = sA.iterator();
4309     while( iA.hasNext() ) {
4310       Map.Entry meA  = (Map.Entry)iA.next();
4311       Integer idA  = (Integer)        meA.getKey();
4312       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
4313
4314       // we should have already checked that the same
4315       // heap regions exist in both graphs
4316       assert ogB.id2hrn.containsKey(idA);
4317
4318       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
4319         return false;
4320       }
4321
4322       // then check every edge in B for presence in A, starting
4323       // from the same parent HeapRegionNode
4324       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
4325
4326       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
4327         return false;
4328       }
4329     }
4330
4331     // then check all the label->heap region edges
4332     sA = ogA.td2ln.entrySet();
4333     iA = sA.iterator();
4334     while( iA.hasNext() ) {
4335       Map.Entry meA = (Map.Entry)iA.next();
4336       TempDescriptor tdA = (TempDescriptor) meA.getKey();
4337       LabelNode lnA = (LabelNode)      meA.getValue();
4338
4339       // we should have already checked that the same
4340       // label nodes exist in both graphs
4341       assert ogB.td2ln.containsKey(tdA);
4342
4343       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
4344         return false;
4345       }
4346
4347       // then check every edge in B for presence in A, starting
4348       // from the same parent LabelNode
4349       LabelNode lnB = ogB.td2ln.get(tdA);
4350
4351       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
4352         return false;
4353       }
4354     }
4355
4356     return true;
4357   }
4358
4359
4360   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
4361                                                  OwnershipNode onA,
4362                                                  OwnershipGraph ogB) {
4363
4364     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
4365     while( itrA.hasNext() ) {
4366       ReferenceEdge edgeA     = itrA.next();
4367       HeapRegionNode hrnChildA = edgeA.getDst();
4368       Integer idChildA  = hrnChildA.getID();
4369
4370       assert ogB.id2hrn.containsKey(idChildA);
4371
4372       // at this point we know an edge in graph A exists
4373       // onA -> idChildA, does this exact edge exist in B?
4374       boolean edgeFound = false;
4375
4376       OwnershipNode onB = null;
4377       if( onA instanceof HeapRegionNode ) {
4378         HeapRegionNode hrnA = (HeapRegionNode) onA;
4379         onB = ogB.id2hrn.get(hrnA.getID() );
4380       } else {
4381         LabelNode lnA = (LabelNode) onA;
4382         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
4383       }
4384
4385       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
4386       while( itrB.hasNext() ) {
4387         ReferenceEdge edgeB     = itrB.next();
4388         HeapRegionNode hrnChildB = edgeB.getDst();
4389         Integer idChildB  = hrnChildB.getID();
4390
4391         if( idChildA.equals(idChildB) &&
4392             edgeA.typeAndFieldEquals(edgeB) ) {
4393
4394           // there is an edge in the right place with the right field,
4395           // but do they have the same attributes?
4396           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
4397             edgeFound = true;
4398           }
4399         }
4400       }
4401
4402       if( !edgeFound ) {
4403         return false;
4404       }
4405     }
4406
4407     return true;
4408   }
4409
4410
4411   protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
4412
4413     if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
4414       return false;
4415     }
4416
4417     if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
4418       return false;
4419     }
4420
4421     return true;
4422   }
4423
4424
4425   protected boolean areAccessPathsEqual(OwnershipGraph og) {
4426     return temp2accessPaths.equals(og.temp2accessPaths);
4427   }
4428
4429
4430
4431   public Set<HeapRegionNode> hasPotentialAlias(HeapRegionNode hrn1, HeapRegionNode hrn2) {
4432     assert hrn1 != null;
4433     assert hrn2 != null;
4434
4435     // then get the various tokens for these heap regions
4436     TokenTuple h1 = new TokenTuple(hrn1.getID(),
4437                                    !hrn1.isSingleObject(),
4438                                    TokenTuple.ARITY_ONE).makeCanonical();
4439
4440     TokenTuple h1plus = new TokenTuple(hrn1.getID(),
4441                                        !hrn1.isSingleObject(),
4442                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
4443
4444     TokenTuple h1star = new TokenTuple(hrn1.getID(),
4445                                        !hrn1.isSingleObject(),
4446                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4447
4448     TokenTuple h2 = new TokenTuple(hrn2.getID(),
4449                                    !hrn2.isSingleObject(),
4450                                    TokenTuple.ARITY_ONE).makeCanonical();
4451
4452     TokenTuple h2plus = new TokenTuple(hrn2.getID(),
4453                                        !hrn2.isSingleObject(),
4454                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
4455
4456     TokenTuple h2star = new TokenTuple(hrn2.getID(),
4457                                        !hrn2.isSingleObject(),
4458                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
4459
4460     // then get the merged beta of all out-going edges from these heap regions
4461     ReachabilitySet beta1 = new ReachabilitySet().makeCanonical();
4462     Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
4463     while( itrEdge.hasNext() ) {
4464       ReferenceEdge edge = itrEdge.next();
4465       beta1 = beta1.union(edge.getBeta() );
4466     }
4467
4468     ReachabilitySet beta2 = new ReachabilitySet().makeCanonical();
4469     itrEdge = hrn2.iteratorToReferencees();
4470     while( itrEdge.hasNext() ) {
4471       ReferenceEdge edge = itrEdge.next();
4472       beta2 = beta2.union(edge.getBeta() );
4473     }
4474
4475     boolean aliasDetected = false;
4476
4477     // only do this one if they are different tokens
4478     if( h1 != h2 &&
4479         beta1.containsTupleSetWithBoth(h1,     h2) ) {
4480       aliasDetected = true;
4481     }
4482     if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
4483       aliasDetected = true;
4484     }
4485     if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
4486       aliasDetected = true;
4487     }
4488     if( beta1.containsTupleSetWithBoth(h1,     h2plus) ) {
4489       aliasDetected = true;
4490     }
4491     if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
4492       aliasDetected = true;
4493     }
4494     if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
4495       aliasDetected = true;
4496     }
4497     if( beta1.containsTupleSetWithBoth(h1,     h2star) ) {
4498       aliasDetected = true;
4499     }
4500     if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
4501       aliasDetected = true;
4502     }
4503     if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
4504       aliasDetected = true;
4505     }
4506
4507     if( h1 != h2 &&
4508         beta2.containsTupleSetWithBoth(h1,     h2) ) {
4509       aliasDetected = true;
4510     }
4511     if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
4512       aliasDetected = true;
4513     }
4514     if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
4515       aliasDetected = true;
4516     }
4517     if( beta2.containsTupleSetWithBoth(h1,     h2plus) ) {
4518       aliasDetected = true;
4519     }
4520     if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
4521       aliasDetected = true;
4522     }
4523     if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
4524       aliasDetected = true;
4525     }
4526     if( beta2.containsTupleSetWithBoth(h1,     h2star) ) {
4527       aliasDetected = true;
4528     }
4529     if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
4530       aliasDetected = true;
4531     }
4532     if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
4533       aliasDetected = true;
4534     }
4535
4536     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4537     if( aliasDetected ) {
4538       common = findCommonReachableNodes(hrn1, hrn2);
4539       if( !(DISABLE_STRONG_UPDATES || DISABLE_GLOBAL_SWEEP) ) {
4540         assert !common.isEmpty();
4541       }
4542     }
4543
4544     return common;
4545   }
4546
4547
4548   public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
4549
4550     // get parameter 1's heap regions
4551     assert paramIndex2idPrimary.containsKey(paramIndex1);
4552     Integer idParamPri1 = paramIndex2idPrimary.get(paramIndex1);
4553
4554     assert id2hrn.containsKey(idParamPri1);
4555     HeapRegionNode hrnParamPri1 = id2hrn.get(idParamPri1);
4556     assert hrnParamPri1 != null;
4557
4558     HeapRegionNode hrnParamSec1 = null;
4559     if( paramIndex2idSecondary.containsKey(paramIndex1) ) {
4560       Integer idParamSec1 = paramIndex2idSecondary.get(paramIndex1);
4561
4562       assert id2hrn.containsKey(idParamSec1);
4563       hrnParamSec1 = id2hrn.get(idParamSec1);
4564       assert hrnParamSec1 != null;
4565     }
4566
4567
4568     // get the other parameter
4569     assert paramIndex2idPrimary.containsKey(paramIndex2);
4570     Integer idParamPri2 = paramIndex2idPrimary.get(paramIndex2);
4571
4572     assert id2hrn.containsKey(idParamPri2);
4573     HeapRegionNode hrnParamPri2 = id2hrn.get(idParamPri2);
4574     assert hrnParamPri2 != null;
4575
4576     HeapRegionNode hrnParamSec2 = null;
4577     if( paramIndex2idSecondary.containsKey(paramIndex2) ) {
4578       Integer idParamSec2 = paramIndex2idSecondary.get(paramIndex2);
4579
4580       assert id2hrn.containsKey(idParamSec2);
4581       hrnParamSec2 = id2hrn.get(idParamSec2);
4582       assert hrnParamSec2 != null;
4583     }
4584
4585     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4586     common.addAll(hasPotentialAlias(hrnParamPri1, hrnParamPri2) );
4587
4588     if( hrnParamSec1 != null ) {
4589       common.addAll(hasPotentialAlias(hrnParamSec1, hrnParamPri2) );
4590     }
4591
4592     if( hrnParamSec2 != null ) {
4593       common.addAll(hasPotentialAlias(hrnParamSec2, hrnParamPri1) );
4594     }
4595
4596     if( hrnParamSec1 != null && hrnParamSec2 != null ) {
4597       common.addAll(hasPotentialAlias(hrnParamSec1, hrnParamSec2) );
4598     }
4599
4600     return common;
4601   }
4602
4603
4604   public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
4605
4606     // get parameter's heap regions
4607     assert paramIndex2idPrimary.containsKey(paramIndex);
4608     Integer idParamPri = paramIndex2idPrimary.get(paramIndex);
4609
4610     assert id2hrn.containsKey(idParamPri);
4611     HeapRegionNode hrnParamPri = id2hrn.get(idParamPri);
4612     assert hrnParamPri != null;
4613
4614     HeapRegionNode hrnParamSec = null;
4615     if( paramIndex2idSecondary.containsKey(paramIndex) ) {
4616       Integer idParamSec = paramIndex2idSecondary.get(paramIndex);
4617
4618       assert id2hrn.containsKey(idParamSec);
4619       hrnParamSec = id2hrn.get(idParamSec);
4620       assert hrnParamSec != null;
4621     }
4622
4623     // get summary node
4624     assert id2hrn.containsKey(as.getSummary() );
4625     HeapRegionNode hrnSummary = id2hrn.get(as.getSummary() );
4626     assert hrnSummary != null;
4627
4628     Set<HeapRegionNode> common = hasPotentialAlias(hrnParamPri, hrnSummary);
4629
4630     if( hrnParamSec != null ) {
4631       common.addAll(hasPotentialAlias(hrnParamSec, hrnSummary) );
4632     }
4633
4634     // check for other nodes
4635     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
4636
4637       assert id2hrn.containsKey(as.getIthOldest(i) );
4638       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i) );
4639       assert hrnIthOldest != null;
4640
4641       common = hasPotentialAlias(hrnParamPri, hrnIthOldest);
4642
4643       if( hrnParamSec != null ) {
4644         common.addAll(hasPotentialAlias(hrnParamSec, hrnIthOldest) );
4645       }
4646     }
4647
4648     return common;
4649   }
4650
4651
4652   public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
4653
4654     // get summary node 1's alpha
4655     Integer idSum1 = as1.getSummary();
4656     assert id2hrn.containsKey(idSum1);
4657     HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
4658     assert hrnSum1 != null;
4659
4660     // get summary node 2's alpha
4661     Integer idSum2 = as2.getSummary();
4662     assert id2hrn.containsKey(idSum2);
4663     HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
4664     assert hrnSum2 != null;
4665
4666     Set<HeapRegionNode> common = hasPotentialAlias(hrnSum1, hrnSum2);
4667
4668     // check sum2 against alloc1 nodes
4669     for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
4670       Integer idI1 = as1.getIthOldest(i);
4671       assert id2hrn.containsKey(idI1);
4672       HeapRegionNode hrnI1 = id2hrn.get(idI1);
4673       assert hrnI1 != null;
4674
4675       common.addAll(hasPotentialAlias(hrnI1, hrnSum2) );
4676     }
4677
4678     // check sum1 against alloc2 nodes
4679     for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
4680       Integer idI2 = as2.getIthOldest(i);
4681       assert id2hrn.containsKey(idI2);
4682       HeapRegionNode hrnI2 = id2hrn.get(idI2);
4683       assert hrnI2 != null;
4684
4685       common.addAll(hasPotentialAlias(hrnSum1, hrnI2) );
4686
4687       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4688       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
4689         Integer idI1 = as1.getIthOldest(j);
4690
4691         // if these are the same site, don't look for the same token, no alias.
4692         // different tokens of the same site could alias together though
4693         if( idI1.equals(idI2) ) {
4694           continue;
4695         }
4696
4697         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4698
4699         common.addAll(hasPotentialAlias(hrnI1, hrnI2) );
4700       }
4701     }
4702
4703     return common;
4704   }
4705
4706
4707   public Set<HeapRegionNode> findCommonReachableNodes(HeapRegionNode hrn1,
4708                                                       HeapRegionNode hrn2) {
4709
4710     Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
4711     Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
4712
4713     Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
4714     todoNodes1.add(hrn1);
4715
4716     Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
4717     todoNodes2.add(hrn2);
4718
4719     // follow links until all reachable nodes have been found
4720     while( !todoNodes1.isEmpty() ) {
4721       HeapRegionNode hrn = todoNodes1.iterator().next();
4722       todoNodes1.remove(hrn);
4723       reachableNodes1.add(hrn);
4724
4725       Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4726       while( edgeItr.hasNext() ) {
4727         ReferenceEdge edge = edgeItr.next();
4728
4729         if( !reachableNodes1.contains(edge.getDst() ) ) {
4730           todoNodes1.add(edge.getDst() );
4731         }
4732       }
4733     }
4734
4735     while( !todoNodes2.isEmpty() ) {
4736       HeapRegionNode hrn = todoNodes2.iterator().next();
4737       todoNodes2.remove(hrn);
4738       reachableNodes2.add(hrn);
4739
4740       Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
4741       while( edgeItr.hasNext() ) {
4742         ReferenceEdge edge = edgeItr.next();
4743
4744         if( !reachableNodes2.contains(edge.getDst() ) ) {
4745           todoNodes2.add(edge.getDst() );
4746         }
4747       }
4748     }
4749
4750     Set<HeapRegionNode> intersection =
4751       new HashSet<HeapRegionNode>(reachableNodes1);
4752
4753     intersection.retainAll(reachableNodes2);
4754
4755     return intersection;
4756   }
4757
4758
4759   public void writeGraph(String graphName,
4760                          boolean writeLabels,
4761                          boolean labelSelect,
4762                          boolean pruneGarbage,
4763                          boolean writeReferencers,
4764                          boolean writeParamMappings,
4765                          boolean hideSubsetReachability,
4766                          boolean hideEdgeTaints
4767                          ) throws java.io.IOException {
4768
4769     // remove all non-word characters from the graph name so
4770     // the filename and identifier in dot don't cause errors
4771     graphName = graphName.replaceAll("[\\W]", "");
4772
4773     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
4774     bw.write("digraph "+graphName+" {\n");
4775
4776     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4777
4778     // then visit every heap region node
4779     Set s = id2hrn.entrySet();
4780     Iterator i = s.iterator();
4781     while( i.hasNext() ) {
4782       Map.Entry me  = (Map.Entry)i.next();
4783       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4784
4785       if( !pruneGarbage ||
4786           (hrn.isFlagged() && hrn.getID() > 0) ||
4787           hrn.getDescription().startsWith("param")
4788           ) {
4789
4790         if( !visited.contains(hrn) ) {
4791           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4792                                   hrn,
4793                                   bw,
4794                                   null,
4795                                   visited,
4796                                   writeReferencers,
4797                                   hideSubsetReachability,
4798                                   hideEdgeTaints);
4799         }
4800       }
4801     }
4802
4803     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
4804
4805     if( writeParamMappings ) {
4806       /* UNMAINTAINED
4807          Set df = paramIndex2id.entrySet();
4808          Iterator ih = df.iterator();
4809          while( ih.hasNext() ) {
4810          Map.Entry meh = (Map.Entry)ih.next();
4811          Integer pi = (Integer) meh.getKey();
4812          Integer id = (Integer) meh.getValue();
4813          bw.write("  pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
4814          }
4815        */
4816     }
4817
4818     // then visit every label node, useful for debugging
4819     if( writeLabels ) {
4820       s = td2ln.entrySet();
4821       i = s.iterator();
4822       while( i.hasNext() ) {
4823         Map.Entry me = (Map.Entry)i.next();
4824         LabelNode ln = (LabelNode) me.getValue();
4825
4826         if( labelSelect ) {
4827           String labelStr = ln.getTempDescriptorString();
4828           if( labelStr.startsWith("___temp") ||
4829               labelStr.startsWith("___dst") ||
4830               labelStr.startsWith("___srctmp") ||
4831               labelStr.startsWith("___neverused") ||
4832               labelStr.contains(qString) ||
4833               labelStr.contains(rString) ||
4834               labelStr.contains(blobString)
4835               ) {
4836             continue;
4837           }
4838         }
4839
4840         //bw.write("  "+ln.toString() + ";\n");
4841
4842         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
4843         while( heapRegionsItr.hasNext() ) {
4844           ReferenceEdge edge = heapRegionsItr.next();
4845           HeapRegionNode hrn  = edge.getDst();
4846
4847           if( pruneGarbage && !visited.contains(hrn) ) {
4848             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
4849                                     hrn,
4850                                     bw,
4851                                     null,
4852                                     visited,
4853                                     writeReferencers,
4854                                     hideSubsetReachability,
4855                                     hideEdgeTaints);
4856           }
4857
4858           bw.write("  "        + ln.toString() +
4859                    " -> "      + hrn.toString() +
4860                    "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4861                                                         hideEdgeTaints) +
4862                    "\",decorate];\n");
4863         }
4864       }
4865     }
4866
4867
4868     bw.write("}\n");
4869     bw.close();
4870   }
4871
4872   protected void traverseHeapRegionNodes(int mode,
4873                                          HeapRegionNode hrn,
4874                                          BufferedWriter bw,
4875                                          TempDescriptor td,
4876                                          HashSet<HeapRegionNode> visited,
4877                                          boolean writeReferencers,
4878                                          boolean hideSubsetReachability,
4879                                          boolean hideEdgeTaints
4880                                          ) throws java.io.IOException {
4881
4882     if( visited.contains(hrn) ) {
4883       return;
4884     }
4885     visited.add(hrn);
4886
4887     switch( mode ) {
4888     case VISIT_HRN_WRITE_FULL:
4889
4890       String attributes = "[";
4891
4892       if( hrn.isSingleObject() ) {
4893         attributes += "shape=box";
4894       } else {
4895         attributes += "shape=Msquare";
4896       }
4897
4898       if( hrn.isFlagged() ) {
4899         attributes += ",style=filled,fillcolor=lightgrey";
4900       }
4901
4902       attributes += ",label=\"ID" +
4903                     hrn.getID()   +
4904                     "\\n";
4905
4906       if( hrn.getType() != null ) {
4907         attributes += hrn.getType().toPrettyString() + "\\n";
4908       }
4909
4910       attributes += hrn.getDescription() +
4911                     "\\n"                +
4912                     hrn.getAlphaString(hideSubsetReachability) +
4913                     "\"]";
4914
4915       bw.write("  " + hrn.toString() + attributes + ";\n");
4916       break;
4917     }
4918
4919
4920     // useful for debugging
4921     // UNMAINTAINED
4922     /*
4923        if( writeReferencers ) {
4924        OwnershipNode onRef  = null;
4925        Iterator refItr = hrn.iteratorToReferencers();
4926        while( refItr.hasNext() ) {
4927         onRef = (OwnershipNode) refItr.next();
4928
4929         switch( mode ) {
4930         case VISIT_HRN_WRITE_FULL:
4931           bw.write("  "                    + hrn.toString() +
4932                    " -> "                  + onRef.toString() +
4933                    "[color=lightgray];\n");
4934           break;
4935         }
4936        }
4937        }
4938      */
4939
4940     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
4941     while( childRegionsItr.hasNext() ) {
4942       ReferenceEdge edge     = childRegionsItr.next();
4943       HeapRegionNode hrnChild = edge.getDst();
4944
4945       switch( mode ) {
4946       case VISIT_HRN_WRITE_FULL:
4947         bw.write("  "        + hrn.toString() +
4948                  " -> "      + hrnChild.toString() +
4949                  "[label=\"" + edge.toGraphEdgeString(hideSubsetReachability,
4950                                                       hideEdgeTaints) +
4951                  "\",decorate];\n");
4952         break;
4953       }
4954
4955       traverseHeapRegionNodes(mode,
4956                               hrnChild,
4957                               bw,
4958                               td,
4959                               visited,
4960                               writeReferencers,
4961                               hideSubsetReachability,
4962                               hideEdgeTaints);
4963     }
4964   }
4965
4966   public int getTaintIdentifierFromHRN(HeapRegionNode hrn) {
4967     HashSet<ReferenceEdge> referenceEdges=hrn.referencers;
4968     Iterator<ReferenceEdge> iter=referenceEdges.iterator();
4969
4970     int taintIdentifier=0;
4971     while(iter.hasNext()) {
4972       ReferenceEdge edge=iter.next();
4973       taintIdentifier=taintIdentifier | edge.getTaintIdentifier();
4974     }
4975
4976     return taintIdentifier;
4977
4978   }
4979
4980   public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet) {
4981
4982     HashSet<ReferenceEdge> setEdge=hrn.referencers;
4983     Iterator<ReferenceEdge> iter=setEdge.iterator();
4984     while(iter.hasNext()) {
4985       ReferenceEdge edge= iter.next();
4986       edge.unionTaintIdentifier(newTaintIdentifier);
4987       if(edge.getSrc() instanceof HeapRegionNode) {
4988
4989         HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
4990         //check whether it is reflexive edge
4991         if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)) {
4992           visitedSet.add(refHRN);
4993           propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
4994         }
4995
4996       }
4997     }
4998
4999   }
5000
5001   public void depropagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet<HeapRegionNode> visitedSet) {
5002
5003     HashSet<ReferenceEdge> setEdge=hrn.referencers;
5004     Iterator<ReferenceEdge> iter=setEdge.iterator();
5005     while(iter.hasNext()) {
5006       ReferenceEdge edge= iter.next();
5007       edge.minusTaintIdentifier(newTaintIdentifier);
5008       if(edge.getSrc() instanceof HeapRegionNode) {
5009
5010         HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc();
5011         //check whether it is reflexive edge
5012         if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)) {
5013           visitedSet.add(refHRN);
5014           depropagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet);
5015         }
5016
5017       }
5018     }
5019
5020   }
5021
5022
5023   // in this analysis specifically:
5024   // we have a notion that a null type is the "match any" type,
5025   // so wrap calls to the utility methods that deal with null
5026   public TypeDescriptor mostSpecificType(TypeDescriptor td1,
5027                                          TypeDescriptor td2) {
5028     if( td1 == null ) {
5029       return td2;
5030     }
5031     if( td2 == null ) {
5032       return td1;
5033     }
5034     if( td1.isNull() ) {
5035       return td2;
5036     }
5037     if( td2.isNull() ) {
5038       return td1;
5039     }
5040     return typeUtil.mostSpecific(td1, td2);
5041   }
5042
5043   public TypeDescriptor mostSpecificType(TypeDescriptor td1,
5044                                          TypeDescriptor td2,
5045                                          TypeDescriptor td3) {
5046
5047     return mostSpecificType(td1,
5048                             mostSpecificType(td2, td3)
5049                             );
5050   }
5051
5052   public TypeDescriptor mostSpecificType(TypeDescriptor td1,
5053                                          TypeDescriptor td2,
5054                                          TypeDescriptor td3,
5055                                          TypeDescriptor td4) {
5056
5057     return mostSpecificType(mostSpecificType(td1, td2),
5058                             mostSpecificType(td3, td4)
5059                             );
5060   }
5061
5062   // remember, in this analysis a null type means "any type"
5063   public boolean isSuperiorType(TypeDescriptor possibleSuper,
5064                                 TypeDescriptor possibleChild) {
5065     if( possibleSuper == null ||
5066         possibleChild == null ) {
5067       return true;
5068     }
5069
5070     if( possibleSuper.isNull() ||
5071         possibleChild.isNull() ) {
5072       return true;
5073     }
5074
5075     return typeUtil.isSuperorType(possibleSuper, possibleChild);
5076   }
5077
5078   public String generateUniqueIdentifier(FlatMethod fm, int paramIdx, String type) {
5079
5080     //type: A->aliapsed parameter heap region
5081     // P -> primary paramter heap region
5082     // S -> secondary paramter heap region
5083
5084     String identifier;
5085     if(type.equals("A")) {
5086       //aliased param
5087       identifier="FM"+fm.hashCode()+".A";
5088     } else {
5089       identifier="FM"+fm.hashCode()+"."+paramIdx+"."+type;
5090     }
5091     return identifier;
5092
5093   }
5094
5095   public String generateUniqueIdentifier(AllocationSite as, int age, boolean isSummary) {
5096
5097     String identifier;
5098
5099     FlatNew fn=as.getFlatNew();
5100
5101     if(isSummary) {
5102       identifier="FN"+fn.hashCode()+".S";
5103     } else {
5104       identifier="FN"+fn.hashCode()+"."+age;
5105     }
5106
5107     return identifier;
5108
5109   }
5110
5111   public HeapRegionNode getHRNbyUniqueID(String id) {
5112
5113     Enumeration<HeapRegionNode> elements = id2hrn.elements();
5114     while (elements.hasMoreElements()) {
5115       HeapRegionNode hrn = elements.nextElement();
5116       if (hrn.getGloballyUniqueIdentifier().equals(id)) {
5117         return hrn;
5118       }
5119     }
5120
5121     return null;
5122
5123   }
5124
5125 }