Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

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