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