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