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