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