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