Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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