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