Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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