Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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