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