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