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