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