Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java

   1 package Analysis.OwnershipAnalysis;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7
   8 public class OwnershipGraph {
   9
  10   private int allocationDepth;
  11   private TypeUtil typeUtil;
  12
  13   // there was already one other very similar reason
  14   // for traversing heap nodes that is no longer needed
  15   // instead of writing a new heap region visitor, use
  16   // the existing method with a new mode to describe what
  17   // actions to take during the traversal
  18   protected static final int VISIT_HRN_WRITE_FULL = 0;
  19
  20   protected static TempDescriptor tdReturn = new TempDescriptor("_Return___");
  21
  22
  23   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  24   public Hashtable<TempDescriptor, LabelNode     > td2ln;
  25   public Hashtable<Integer,        Integer       > id2paramIndex;
  26   public Hashtable<Integer,        Integer       > paramIndex2id;
  27   public Hashtable<Integer,        TempDescriptor> paramIndex2tdQ;
  28
  29   public HashSet<AllocationSite> allocationSites;
  30
  31
  32
  33
  34   public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
  35     this.allocationDepth = allocationDepth;
  36     this.typeUtil        = typeUtil;
  37
  38     id2hrn         = new Hashtable<Integer,        HeapRegionNode>();
  39     td2ln          = new Hashtable<TempDescriptor, LabelNode     >();
  40     id2paramIndex  = new Hashtable<Integer,        Integer       >();
  41     paramIndex2id  = new Hashtable<Integer,        Integer       >();
  42     paramIndex2tdQ = new Hashtable<Integer,        TempDescriptor>();
  43
  44     allocationSites = new HashSet <AllocationSite>();
  45   }
  46
  47
  48   // label nodes are much easier to deal with than
  49   // heap region nodes.  Whenever there is a request
  50   // for the label node that is associated with a
  51   // temp descriptor we can either find it or make a
  52   // new one and return it.  This is because temp
  53   // descriptors are globally unique and every label
  54   // node is mapped to exactly one temp descriptor.
  55   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  56     assert td != null;
  57
  58     if( !td2ln.containsKey(td) ) {
  59       td2ln.put(td, new LabelNode(td) );
  60     }
  61
  62     return td2ln.get(td);
  63   }
  64
  65
  66   // the reason for this method is to have the option
  67   // creating new heap regions with specific IDs, or
  68   // duplicating heap regions with specific IDs (especially
  69   // in the merge() operation) or to create new heap
  70   // regions with a new unique ID.
  71   protected HeapRegionNode
  72   createNewHeapRegionNode(Integer id,
  73                           boolean isSingleObject,
  74                           boolean isFlagged,
  75                           boolean isNewSummary,
  76                           boolean isParameter,
  77                           AllocationSite allocSite,
  78                           ReachabilitySet alpha,
  79                           String description) {
  80
  81     if( id == null ) {
  82       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
  83     }
  84
  85     if( alpha == null ) {
  86       if( isFlagged || isParameter ) {
  87         alpha = new ReachabilitySet(new TokenTuple(id,
  88                                                    !isSingleObject,
  89                                                    TokenTuple.ARITY_ONE)
  90                                     ).makeCanonical();
  91       } else {
  92         alpha = new ReachabilitySet(new TokenTupleSet()
  93                                     ).makeCanonical();
  94       }
  95     }
  96
  97     HeapRegionNode hrn = new HeapRegionNode(id,
  98                                             isSingleObject,
  99                                             isFlagged,
 100                                             isNewSummary,
 101                                             allocSite,
 102                                             alpha,
 103                                             description);
 104     id2hrn.put(id, hrn);
 105     return hrn;
 106   }
 107
 108
 109
 110   ////////////////////////////////////////////////
 111   //
 112   //  Low-level referencee and referencer methods
 113   //
 114   //  These methods provide the lowest level for
 115   //  creating references between ownership nodes
 116   //  and handling the details of maintaining both
 117   //  list of referencers and referencees.
 118   //
 119   ////////////////////////////////////////////////
 120   protected void addReferenceEdge(OwnershipNode referencer,
 121                                   HeapRegionNode referencee,
 122                                   ReferenceEdge edge) {
 123     assert referencer != null;
 124     assert referencee != null;
 125     assert edge       != null;
 126     assert edge.getSrc() == referencer;
 127     assert edge.getDst() == referencee;
 128
 129     referencer.addReferencee(edge);
 130     referencee.addReferencer(edge);
 131   }
 132
 133   protected void removeReferenceEdge(OwnershipNode referencer,
 134                                      HeapRegionNode referencee,
 135                                      FieldDescriptor fieldDesc) {
 136     assert referencer != null;
 137     assert referencee != null;
 138
 139     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 140                                                    fieldDesc);
 141     assert edge != null;
 142     assert edge == referencee.getReferenceFrom(referencer,
 143                                                fieldDesc);
 144
 145     referencer.removeReferencee(edge);
 146     referencee.removeReferencer(edge);
 147   }
 148
 149   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 150                                          FieldDescriptor fieldDesc,
 151                                          boolean removeAll) {
 152     assert referencer != null;
 153
 154     // get a copy of the set to iterate over, otherwise
 155     // we will be trying to take apart the set as we
 156     // are iterating over it, which won't work
 157     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 158     while( i.hasNext() ) {
 159       ReferenceEdge edge = i.next();
 160
 161       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 162         HeapRegionNode referencee = edge.getDst();
 163
 164         removeReferenceEdge(referencer,
 165                             referencee,
 166                             edge.getFieldDesc() );
 167       }
 168     }
 169   }
 170
 171   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 172                                        FieldDescriptor fieldDesc,
 173                                        boolean removeAll) {
 174     assert referencee != null;
 175
 176     // get a copy of the set to iterate over, otherwise
 177     // we will be trying to take apart the set as we
 178     // are iterating over it, which won't work
 179     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 180     while( i.hasNext() ) {
 181       ReferenceEdge edge = i.next();
 182
 183       if( removeAll || edge.getFieldDesc() == fieldDesc ) {
 184         OwnershipNode referencer = edge.getSrc();
 185         removeReferenceEdge(referencer,
 186                             referencee,
 187                             edge.getFieldDesc() );
 188       }
 189     }
 190   }
 191
 192
 193   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
 194                                           ChangeTupleSet c0,
 195                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
 196                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
 197
 198     HashSet<HeapRegionNode> todoNodes
 199     = new HashSet<HeapRegionNode>();
 200     todoNodes.add(nPrime);
 201
 202     HashSet<ReferenceEdge> todoEdges
 203     = new HashSet<ReferenceEdge>();
 204
 205     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
 206     = new Hashtable<HeapRegionNode, ChangeTupleSet>();
 207     nodePlannedChanges.put(nPrime, c0);
 208
 209     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
 210     = new Hashtable<ReferenceEdge, ChangeTupleSet>();
 211
 212
 213     while( !todoNodes.isEmpty() ) {
 214       HeapRegionNode n = todoNodes.iterator().next();
 215       ChangeTupleSet C = nodePlannedChanges.get(n);
 216
 217       Iterator itrC = C.iterator();
 218       while( itrC.hasNext() ) {
 219         ChangeTuple c = (ChangeTuple) itrC.next();
 220
 221         if( n.getAlpha().contains(c.getSetToMatch() ) ) {
 222           ReachabilitySet withChange = n.getAlpha().union(c.getSetToAdd() );
 223           n.setAlphaNew(n.getAlphaNew().union(withChange) );
 224           nodesWithNewAlpha.add(n);
 225         }
 226       }
 227
 228       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 229       while( referItr.hasNext() ) {
 230         ReferenceEdge edge = referItr.next();
 231         todoEdges.add(edge);
 232
 233         if( !edgePlannedChanges.containsKey(edge) ) {
 234           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
 235         }
 236
 237         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
 238       }
 239
 240       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
 241       while( refeeItr.hasNext() ) {
 242         ReferenceEdge edgeF = refeeItr.next();
 243         HeapRegionNode m     = edgeF.getDst();
 244
 245         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 246
 247         Iterator<ChangeTuple> itrCprime = C.iterator();
 248         while( itrCprime.hasNext() ) {
 249           ChangeTuple c = itrCprime.next();
 250           if( edgeF.getBeta().contains(c.getSetToMatch() ) ) {
 251             changesToPass = changesToPass.union(c);
 252           }
 253         }
 254
 255         if( !changesToPass.isEmpty() ) {
 256           if( !nodePlannedChanges.containsKey(m) ) {
 257             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
 258           }
 259
 260           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
 261
 262           if( !changesToPass.isSubset(currentChanges) ) {
 263
 264             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
 265             todoNodes.add(m);
 266           }
 267         }
 268       }
 269
 270       todoNodes.remove(n);
 271     }
 272
 273     propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
 274   }
 275
 276
 277   protected void propagateTokensOverEdges(
 278     HashSet<ReferenceEdge>                   todoEdges,
 279     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
 280     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
 281
 282
 283     while( !todoEdges.isEmpty() ) {
 284       ReferenceEdge edgeE = todoEdges.iterator().next();
 285       todoEdges.remove(edgeE);
 286
 287       if( !edgePlannedChanges.containsKey(edgeE) ) {
 288         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
 289       }
 290
 291       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
 292
 293       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
 294
 295       Iterator<ChangeTuple> itrC = C.iterator();
 296       while( itrC.hasNext() ) {
 297         ChangeTuple c = itrC.next();
 298         if( edgeE.getBeta().contains(c.getSetToMatch() ) ) {
 299           ReachabilitySet withChange = edgeE.getBeta().union(c.getSetToAdd() );
 300           edgeE.setBetaNew(edgeE.getBetaNew().union(withChange) );
 301           edgesWithNewBeta.add(edgeE);
 302           changesToPass = changesToPass.union(c);
 303         }
 304       }
 305
 306       OwnershipNode onSrc = edgeE.getSrc();
 307
 308       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
 309         HeapRegionNode n = (HeapRegionNode) onSrc;
 310
 311         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
 312         while( referItr.hasNext() ) {
 313           ReferenceEdge edgeF = referItr.next();
 314
 315           if( !edgePlannedChanges.containsKey(edgeF) ) {
 316             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
 317           }
 318
 319           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
 320
 321           if( !changesToPass.isSubset(currentChanges) ) {
 322             todoEdges.add(edgeF);
 323             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
 324           }
 325         }
 326       }
 327     }
 328   }
 329
 330
 331   ////////////////////////////////////////////////////
 332   //
 333   //  Assignment Operation Methods
 334   //
 335   //  These methods are high-level operations for
 336   //  modeling program assignment statements using
 337   //  the low-level reference create/remove methods
 338   //  above.
 339   //
 340   //  The destination in an assignment statement is
 341   //  going to have new references.  The method of
 342   //  determining the references depends on the type
 343   //  of the FlatNode assignment and the predicates
 344   //  of the nodes and edges involved.
 345   //
 346   ////////////////////////////////////////////////////
 347   public void assignTempXEqualToTempY(TempDescriptor x,
 348                                       TempDescriptor y) {
 349
 350     LabelNode lnX = getLabelNodeFromTemp(x);
 351     LabelNode lnY = getLabelNodeFromTemp(y);
 352
 353     clearReferenceEdgesFrom(lnX, null, true);
 354
 355     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 356     while( itrYhrn.hasNext() ) {
 357       ReferenceEdge edgeY       = itrYhrn.next();
 358       HeapRegionNode referencee = edgeY.getDst();
 359       ReferenceEdge edgeNew    = edgeY.copy();
 360       edgeNew.setSrc(lnX);
 361
 362       addReferenceEdge(lnX, referencee, edgeNew);
 363     }
 364   }
 365
 366
 367   public void assignTempXEqualToTempYFieldF(TempDescriptor x,
 368                                             TempDescriptor y,
 369                                             FieldDescriptor f) {
 370     LabelNode lnX = getLabelNodeFromTemp(x);
 371     LabelNode lnY = getLabelNodeFromTemp(y);
 372
 373     clearReferenceEdgesFrom(lnX, null, true);
 374
 375     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 376     while( itrYhrn.hasNext() ) {
 377       ReferenceEdge edgeY = itrYhrn.next();
 378       HeapRegionNode hrnY  = edgeY.getDst();
 379       ReachabilitySet betaY = edgeY.getBeta();
 380
 381       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 382       while( itrHrnFhrn.hasNext() ) {
 383         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 384         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 385         ReachabilitySet betaHrn = edgeHrn.getBeta();
 386
 387         if( edgeHrn.getFieldDesc() == null ||
 388             edgeHrn.getFieldDesc() == f ) {
 389
 390           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 391                                                     hrnHrn,
 392                                                     f,
 393                                                     false,
 394                                                     betaY.intersection(betaHrn) );
 395
 396           addReferenceEdge(lnX, hrnHrn, edgeNew);
 397         }
 398       }
 399     }
 400   }
 401
 402
 403   public void assignTempXFieldFEqualToTempY(TempDescriptor x,
 404                                             FieldDescriptor f,
 405                                             TempDescriptor y) {
 406     LabelNode lnX = getLabelNodeFromTemp(x);
 407     LabelNode lnY = getLabelNodeFromTemp(y);
 408
 409     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 410     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 411
 412     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 413     while( itrXhrn.hasNext() ) {
 414       ReferenceEdge edgeX = itrXhrn.next();
 415       HeapRegionNode hrnX  = edgeX.getDst();
 416       ReachabilitySet betaX = edgeX.getBeta();
 417
 418       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 419
 420       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 421       while( itrYhrn.hasNext() ) {
 422         ReferenceEdge edgeY = itrYhrn.next();
 423         HeapRegionNode hrnY  = edgeY.getDst();
 424         ReachabilitySet O     = edgeY.getBeta();
 425
 426
 427         // propagate tokens over nodes starting from hrnSrc, and it will
 428         // take care of propagating back up edges from any touched nodes
 429         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 430         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 431
 432
 433         // then propagate back just up the edges from hrn
 434         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 435
 436
 437         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 438
 439         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 440           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 441
 442         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 443         while( referItr.hasNext() ) {
 444           ReferenceEdge edgeUpstream = referItr.next();
 445           todoEdges.add(edgeUpstream);
 446           edgePlannedChanges.put(edgeUpstream, Cx);
 447         }
 448
 449         propagateTokensOverEdges(todoEdges,
 450                                  edgePlannedChanges,
 451                                  edgesWithNewBeta);
 452
 453
 454         if( edgeY.getBetaNew().equals( new ReachabilitySet() ) ) {
 455           edgeY.setBetaNew( new ReachabilitySet( new TokenTupleSet().makeCanonical() ).makeCanonical() );
 456         }
 457
 458         /*
 459         System.out.println( "---------------------------\n" +
 460                             edgeY.getBetaNew() +
 461                             "\nbeing pruned by\n" +
 462                             hrnX.getAlpha() +
 463                             "\nis\n" +
 464                             edgeY.getBetaNew().pruneBy(hrnX.getAlpha())
 465                             );
 466         */
 467
 468         // create the actual reference edge hrnX.f -> hrnY
 469         ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
 470                                                   hrnY,
 471                                                   f,
 472                                                   false,
 473                                                   edgeY.getBetaNew().pruneBy(hrnX.getAlpha() )
 474                                                   //edgeY.getBeta().pruneBy( hrnX.getAlpha() )
 475                                                   );
 476         addReferenceEdge(hrnX, hrnY, edgeNew);
 477
 478         /*
 479            if( f != null ) {
 480             // we can do a strong update here if one of two cases holds
 481             // SAVE FOR LATER, WITHOUT STILL CORRECT
 482             if( (hrnX.getNumReferencers() == 1)                           ||
 483                 ( lnX.getNumReferencees() == 1 && hrnX.isSingleObject() )
 484               ) {
 485                 clearReferenceEdgesFrom( hrnX, f, false );
 486             }
 487
 488             addReferenceEdge( hrnX, hrnY, edgeNew );
 489
 490            } else {
 491             // if the field is null, or "any" field, then
 492             // look to see if an any field already exists
 493             // and merge with it, otherwise just add the edge
 494             ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY, f );
 495
 496             if( edgeExisting != null ) {
 497                 edgeExisting.setBetaNew(
 498                   edgeExisting.getBetaNew().union( edgeNew.getBeta() )
 499                                        );
 500                 // a new edge here cannot be reflexive, so existing will
 501                 // always be also not reflexive anymore
 502                 edgeExisting.setIsInitialParamReflexive( false );
 503
 504             } else {
 505                 addReferenceEdge( hrnX, hrnY, edgeNew );
 506             }
 507            }
 508          */
 509       }
 510     }
 511
 512     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 513     while( nodeItr.hasNext() ) {
 514       nodeItr.next().applyAlphaNew();
 515     }
 516
 517     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
 518     while( edgeItr.hasNext() ) {
 519       edgeItr.next().applyBetaNew();
 520     }
 521   }
 522
 523
 524   public void assignTempEqualToParamAlloc(TempDescriptor td,
 525                                           boolean isTask,
 526                                           Integer paramIndex) {
 527     assert td != null;
 528
 529     LabelNode lnParam = getLabelNodeFromTemp(td);
 530     HeapRegionNode hrn = createNewHeapRegionNode(null,
 531                                                  false,
 532                                                  isTask,
 533                                                  false,
 534                                                  true,
 535                                                  null,
 536                                                  null,
 537                                                  "param" + paramIndex);
 538
 539     // this is a non-program-accessible label that picks up beta
 540     // info to be used for fixing a caller of this method
 541     TempDescriptor tdParamQ = new TempDescriptor(td+"specialQ");
 542     LabelNode lnParamQ = getLabelNodeFromTemp(tdParamQ);
 543
 544     // keep track of heap regions that were created for
 545     // parameter labels, the index of the parameter they
 546     // are for is important when resolving method calls
 547     Integer newID = hrn.getID();
 548     assert !id2paramIndex.containsKey(newID);
 549     assert !id2paramIndex.containsValue(paramIndex);
 550     id2paramIndex.put(newID, paramIndex);
 551     paramIndex2id.put(paramIndex, newID);
 552     paramIndex2tdQ.put(paramIndex, tdParamQ);
 553
 554     ReachabilitySet beta = new ReachabilitySet(new TokenTuple(newID,
 555                                                               true,
 556                                                               TokenTuple.ARITY_ONE) );
 557
 558     // heap regions for parameters are always multiple object (see above)
 559     // and have a reference to themselves, because we can't know the
 560     // structure of memory that is passed into the method.  We're assuming
 561     // the worst here.
 562
 563     ReferenceEdge edgeFromLabel =
 564       new ReferenceEdge(lnParam, hrn, null, false, beta);
 565
 566     ReferenceEdge edgeFromLabelQ =
 567       new ReferenceEdge(lnParamQ, hrn, null, false, beta);
 568
 569     ReferenceEdge edgeReflexive =
 570       new ReferenceEdge(hrn,     hrn, null, true,  beta);
 571
 572     addReferenceEdge(lnParam,  hrn, edgeFromLabel);
 573     addReferenceEdge(lnParamQ, hrn, edgeFromLabelQ);
 574     addReferenceEdge(hrn,      hrn, edgeReflexive);
 575   }
 576
 577
 578   public void assignReturnEqualToTemp(TempDescriptor x) {
 579
 580     LabelNode lnR = getLabelNodeFromTemp(tdReturn);
 581     LabelNode lnX = getLabelNodeFromTemp(x);
 582
 583     clearReferenceEdgesFrom(lnR, null, true);
 584
 585     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 586     while( itrXhrn.hasNext() ) {
 587       ReferenceEdge edgeX       = itrXhrn.next();
 588       HeapRegionNode referencee = edgeX.getDst();
 589       ReferenceEdge edgeNew    = edgeX.copy();
 590       edgeNew.setSrc(lnR);
 591
 592       addReferenceEdge(lnR, referencee, edgeNew);
 593     }
 594   }
 595
 596
 597   public void assignTempEqualToNewAlloc(TempDescriptor x,
 598                                         AllocationSite as) {
 599     assert x  != null;
 600     assert as != null;
 601
 602     age(as);
 603
 604     // after the age operation the newest (or zero-ith oldest)
 605     // node associated with the allocation site should have
 606     // no references to it as if it were a newly allocated
 607     // heap region, so make a reference to it to complete
 608     // this operation
 609
 610     Integer idNewest  = as.getIthOldest(0);
 611     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 612     assert hrnNewest != null;
 613
 614     LabelNode lnX = getLabelNodeFromTemp(x);
 615     clearReferenceEdgesFrom(lnX, null, true);
 616
 617     ReferenceEdge edgeNew =
 618       new ReferenceEdge(lnX, hrnNewest, null, false, hrnNewest.getAlpha() );
 619
 620     addReferenceEdge(lnX, hrnNewest, edgeNew);
 621   }
 622
 623
 624   // use the allocation site (unique to entire analysis) to
 625   // locate the heap region nodes in this ownership graph
 626   // that should be aged.  The process models the allocation
 627   // of new objects and collects all the oldest allocations
 628   // in a summary node to allow for a finite analysis
 629   //
 630   // There is an additional property of this method.  After
 631   // running it on a particular ownership graph (many graphs
 632   // may have heap regions related to the same allocation site)
 633   // the heap region node objects in this ownership graph will be
 634   // allocated.  Therefore, after aging a graph for an allocation
 635   // site, attempts to retrieve the heap region nodes using the
 636   // integer id's contained in the allocation site should always
 637   // return non-null heap regions.
 638   public void age(AllocationSite as) {
 639
 640     // aging adds this allocation site to the graph's
 641     // list of sites that exist in the graph, or does
 642     // nothing if the site is already in the list
 643     allocationSites.add(as);
 644
 645     // get the summary node for the allocation site in the context
 646     // of this particular ownership graph
 647     HeapRegionNode hrnSummary = getSummaryNode(as);
 648
 649     // merge oldest node into summary
 650     Integer idK  = as.getOldest();
 651     HeapRegionNode hrnK = id2hrn.get(idK);
 652     mergeIntoSummary(hrnK, hrnSummary);
 653
 654     // move down the line of heap region nodes
 655     // clobbering the ith and transferring all references
 656     // to and from i-1 to node i.  Note that this clobbers
 657     // the oldest node (hrnK) that was just merged into
 658     // the summary
 659     for( int i = allocationDepth - 1; i > 0; --i ) {
 660
 661       // move references from the i-1 oldest to the ith oldest
 662       Integer idIth     = as.getIthOldest(i);
 663       HeapRegionNode hrnI      = id2hrn.get(idIth);
 664       Integer idImin1th = as.getIthOldest(i - 1);
 665       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 666
 667       transferOnto(hrnImin1, hrnI);
 668     }
 669
 670     // as stated above, the newest node should have had its
 671     // references moved over to the second oldest, so we wipe newest
 672     // in preparation for being the new object to assign something to
 673     Integer id0th = as.getIthOldest(0);
 674     HeapRegionNode hrn0  = id2hrn.get(id0th);
 675     assert hrn0 != null;
 676
 677     // clear all references in and out of newest node
 678     clearReferenceEdgesFrom(hrn0, null, true);
 679     clearReferenceEdgesTo(hrn0, null, true);
 680
 681
 682     // now tokens in reachability sets need to "age" also
 683     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 684     while( itrAllLabelNodes.hasNext() ) {
 685       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 686       LabelNode ln = (LabelNode) me.getValue();
 687
 688       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 689       while( itrEdges.hasNext() ) {
 690         ageTokens(as, itrEdges.next() );
 691       }
 692     }
 693
 694     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 695     while( itrAllHRNodes.hasNext() ) {
 696       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
 697       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 698
 699       ageTokens(as, hrnToAge);
 700
 701       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
 702       while( itrEdges.hasNext() ) {
 703         ageTokens(as, itrEdges.next() );
 704       }
 705     }
 706
 707
 708     // after tokens have been aged, reset newest node's reachability
 709     if( hrn0.isFlagged() ) {
 710       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet(
 711                                           new TokenTuple(hrn0)
 712                                           )
 713                                         ).makeCanonical()
 714                     );
 715     } else {
 716       hrn0.setAlpha(new ReachabilitySet(new TokenTupleSet()
 717                                         ).makeCanonical()
 718                     );
 719     }
 720   }
 721
 722
 723   protected HeapRegionNode getSummaryNode(AllocationSite as) {
 724
 725     Integer idSummary  = as.getSummary();
 726     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
 727
 728     // If this is null then we haven't touched this allocation site
 729     // in the context of the current ownership graph, so allocate
 730     // heap region nodes appropriate for the entire allocation site.
 731     // This should only happen once per ownership graph per allocation site,
 732     // and a particular integer id can be used to locate the heap region
 733     // in different ownership graphs that represents the same part of an
 734     // allocation site.
 735     if( hrnSummary == null ) {
 736
 737       boolean hasFlags = false;
 738       if( as.getType().isClass() ) {
 739         hasFlags = as.getType().getClassDesc().hasFlags();
 740       }
 741
 742       hrnSummary = createNewHeapRegionNode(idSummary,
 743                                            false,
 744                                            hasFlags,
 745                                            true,
 746                                            false,
 747                                            as,
 748                                            null,
 749                                            as + "\\n" + as.getType() + "\\nsummary");
 750
 751       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 752         Integer idIth = as.getIthOldest(i);
 753         assert !id2hrn.containsKey(idIth);
 754         createNewHeapRegionNode(idIth,
 755                                 true,
 756                                 hasFlags,
 757                                 false,
 758                                 false,
 759                                 as,
 760                                 null,
 761                                 as + "\\n" + as.getType() + "\\n" + i + " oldest");
 762       }
 763     }
 764
 765     return hrnSummary;
 766   }
 767
 768
 769   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
 770
 771     Integer idShadowSummary  = as.getSummaryShadow();
 772     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
 773
 774     if( hrnShadowSummary == null ) {
 775
 776       boolean hasFlags = false;
 777       if( as.getType().isClass() ) {
 778         hasFlags = as.getType().getClassDesc().hasFlags();
 779       }
 780
 781       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary,
 782                                                  false,
 783                                                  hasFlags,
 784                                                  true,
 785                                                  false,
 786                                                  as,
 787                                                  null,
 788                                                  as + "\\n" + as.getType() + "\\nshadowSum");
 789
 790       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
 791         Integer idShadowIth = as.getIthOldestShadow(i);
 792         assert !id2hrn.containsKey(idShadowIth);
 793         createNewHeapRegionNode(idShadowIth,
 794                                 true,
 795                                 hasFlags,
 796                                 false,
 797                                 false,
 798                                 as,
 799                                 null,
 800                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
 801       }
 802     }
 803
 804     return hrnShadowSummary;
 805   }
 806
 807
 808   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
 809     assert hrnSummary.isNewSummary();
 810
 811     // transfer references _from_ hrn over to hrnSummary
 812     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
 813     while( itrReferencee.hasNext() ) {
 814       ReferenceEdge edge       = itrReferencee.next();
 815       ReferenceEdge edgeMerged = edge.copy();
 816       edgeMerged.setSrc(hrnSummary);
 817
 818       HeapRegionNode hrnReferencee = edge.getDst();
 819       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee, edge.getFieldDesc() );
 820
 821       if( edgeSummary == null ) {
 822         // the merge is trivial, nothing to be done
 823       } else {
 824         // otherwise an edge from the referencer to hrnSummary exists already
 825         // and the edge referencer->hrn should be merged with it
 826         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 827       }
 828
 829       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
 830     }
 831
 832     // next transfer references _to_ hrn over to hrnSummary
 833     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
 834     while( itrReferencer.hasNext() ) {
 835       ReferenceEdge edge         = itrReferencer.next();
 836       ReferenceEdge edgeMerged   = edge.copy();
 837       edgeMerged.setDst(hrnSummary);
 838
 839       OwnershipNode onReferencer = edge.getSrc();
 840       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary, edge.getFieldDesc() );
 841
 842       if( edgeSummary == null ) {
 843         // the merge is trivial, nothing to be done
 844       } else {
 845         // otherwise an edge from the referencer to alpha_S exists already
 846         // and the edge referencer->alpha_K should be merged with it
 847         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
 848       }
 849
 850       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
 851     }
 852
 853     // then merge hrn reachability into hrnSummary
 854     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
 855   }
 856
 857
 858   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
 859
 860     // clear references in and out of node i
 861     clearReferenceEdgesFrom(hrnB, null, true);
 862     clearReferenceEdgesTo(hrnB, null, true);
 863
 864     // copy each edge in and out of A to B
 865     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
 866     while( itrReferencee.hasNext() ) {
 867       ReferenceEdge edge          = itrReferencee.next();
 868       HeapRegionNode hrnReferencee = edge.getDst();
 869       ReferenceEdge edgeNew       = edge.copy();
 870       edgeNew.setSrc(hrnB);
 871
 872       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
 873     }
 874
 875     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
 876     while( itrReferencer.hasNext() ) {
 877       ReferenceEdge edge         = itrReferencer.next();
 878       OwnershipNode onReferencer = edge.getSrc();
 879       ReferenceEdge edgeNew      = edge.copy();
 880       edgeNew.setDst(hrnB);
 881
 882       addReferenceEdge(onReferencer, hrnB, edgeNew);
 883     }
 884
 885     // replace hrnB reachability with hrnA's
 886     hrnB.setAlpha(hrnA.getAlpha() );
 887   }
 888
 889
 890   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
 891     edge.setBeta(edge.getBeta().ageTokens(as) );
 892   }
 893
 894   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
 895     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
 896   }
 897
 898
 899   public void resolveMethodCall(FlatCall fc,
 900                                 boolean isStatic,
 901                                 FlatMethod fm,
 902                                 OwnershipGraph ogCallee) {
 903
 904     // define rewrite rules and other structures to organize
 905     // data by parameter/argument index
 906     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
 907       new Hashtable<Integer, ReachabilitySet>();
 908
 909     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
 910       new Hashtable<Integer, ReachabilitySet>();
 911
 912     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
 913       new Hashtable<Integer, ReachabilitySet>();
 914
 915     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
 916       new Hashtable<Integer, ReachabilitySet>();
 917
 918     // helpful structures
 919     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
 920       new Hashtable<TokenTuple, Integer>();
 921
 922     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
 923       new Hashtable<Integer, TokenTuple>();
 924
 925     Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
 926       new Hashtable<TokenTuple, Integer>();
 927
 928     Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
 929       new Hashtable<Integer, TokenTuple>();
 930
 931     Hashtable<Integer, LabelNode> paramIndex2ln =
 932       new Hashtable<Integer, LabelNode>();
 933
 934     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
 935       new Hashtable<Integer, HashSet<HeapRegionNode> >();
 936
 937
 938     // add a bogus entry with the identity rule for easy rewrite
 939     // of new callee nodes and edges, doesn't belong to any parameter
 940     Integer bogusID = new Integer(-1);
 941     Integer bogusIndex = new Integer(-1);
 942     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE);
 943     TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_MANY);
 944     ReachabilitySet rsIdentity =
 945       new ReachabilitySet(new TokenTupleSet(bogusToken).makeCanonical() ).makeCanonical();
 946
 947     paramIndex2rewriteH.put(bogusIndex, rsIdentity);
 948     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
 949     paramToken2paramIndex.put(bogusToken, bogusIndex);
 950     paramIndex2paramToken.put(bogusIndex, bogusToken);
 951     paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
 952     paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
 953
 954
 955     for( int i = 0; i < fm.numParameters(); ++i ) {
 956       Integer paramIndex = new Integer(i);
 957
 958       assert ogCallee.paramIndex2id.containsKey(paramIndex);
 959       Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
 960
 961       assert ogCallee.id2hrn.containsKey(idParam);
 962       HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
 963       assert hrnParam != null;
 964       paramIndex2rewriteH.put(paramIndex,
 965
 966                               toShadowTokens(ogCallee, hrnParam.getAlpha() )
 967                               );
 968
 969       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null);
 970       assert edgeReflexive_i != null;
 971       paramIndex2rewriteJ.put(paramIndex,
 972                               toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
 973                               );
 974
 975       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
 976       assert tdParamQ != null;
 977       LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
 978       assert lnParamQ != null;
 979       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null);
 980       assert edgeSpecialQ_i != null;
 981       paramIndex2rewriteK.put(paramIndex,
 982                               toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
 983                               );
 984
 985       TokenTuple p_i = new TokenTuple(hrnParam.getID(),
 986                                       true,
 987                                       TokenTuple.ARITY_ONE).makeCanonical();
 988       paramToken2paramIndex.put(p_i, paramIndex);
 989       paramIndex2paramToken.put(paramIndex, p_i);
 990
 991       TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
 992                                            true,
 993                                            TokenTuple.ARITY_MANY).makeCanonical();
 994       paramTokenStar2paramIndex.put(p_i_star, paramIndex);
 995       paramIndex2paramTokenStar.put(paramIndex, p_i_star);
 996
 997       // now depending on whether the callee is static or not
 998       // we need to account for a "this" argument in order to
 999       // find the matching argument in the caller context
1000       TempDescriptor argTemp_i;
1001       if( isStatic ) {
1002         argTemp_i = fc.getArg(paramIndex);
1003       } else {
1004         if( paramIndex.equals( 0 ) ) {
1005           argTemp_i = fc.getThis();
1006         } else {
1007           argTemp_i = fc.getArg(paramIndex - 1);
1008         }
1009       }
1010
1011       // in non-static methods there is a "this" pointer
1012       // that should be taken into account
1013       if( isStatic ) {
1014         assert fc.numArgs()     == fm.numParameters();
1015       } else {
1016         assert fc.numArgs() + 1 == fm.numParameters();
1017       }
1018
1019       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1020       paramIndex2ln.put(paramIndex, argLabel_i);
1021
1022       ReachabilitySet D_i = new ReachabilitySet().makeCanonical();
1023       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1024       while( edgeItr.hasNext() ) {
1025         ReferenceEdge edge = edgeItr.next();
1026         D_i = D_i.union(edge.getBeta());
1027       }
1028
1029       D_i = D_i.exhaustiveArityCombinations();
1030
1031       paramIndex2rewriteD.put(paramIndex, D_i);
1032     }
1033
1034
1035     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1036     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1037
1038     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1039     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1040
1041     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1042     while( lnArgItr.hasNext() ) {
1043       Map.Entry me      = (Map.Entry)lnArgItr.next();
1044       Integer index   = (Integer)   me.getKey();
1045       LabelNode lnArg_i = (LabelNode) me.getValue();
1046
1047       // rewrite alpha for the nodes reachable from argument label i
1048       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1049       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1050
1051       // to find all reachable nodes, start with label referencees
1052       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1053       while( edgeArgItr.hasNext() ) {
1054         ReferenceEdge edge = edgeArgItr.next();
1055         todoNodes.add(edge.getDst() );
1056       }
1057
1058       // then follow links until all reachable nodes have been found
1059       while( !todoNodes.isEmpty() ) {
1060         HeapRegionNode hrn = todoNodes.iterator().next();
1061         todoNodes.remove(hrn);
1062         reachableNodes.add(hrn);
1063
1064         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1065         while( edgeItr.hasNext() ) {
1066           ReferenceEdge edge = edgeItr.next();
1067
1068           if( !reachableNodes.contains(edge.getDst() ) ) {
1069             todoNodes.add(edge.getDst() );
1070           }
1071         }
1072       }
1073
1074       // save for later
1075       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1076
1077       // now iterate over reachable nodes to update their alpha, and
1078       // classify edges found as "argument reachable" or "upstream"
1079       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1080       while( hrnItr.hasNext() ) {
1081         HeapRegionNode hrn = hrnItr.next();
1082
1083         rewriteCallerReachability(index,
1084                                   hrn,
1085                                   null,
1086                                   paramIndex2rewriteH.get(index),
1087                                   paramIndex2rewriteD,
1088                                   paramIndex2paramToken.get(index),
1089                                   paramToken2paramIndex,
1090                                   paramTokenStar2paramIndex,
1091                                   false,
1092                                   null);
1093
1094         nodesWithNewAlpha.add(hrn);
1095
1096         // look at all incoming edges to the reachable nodes
1097         // and sort them as edges reachable from the argument
1098         // label node, or upstream edges
1099         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1100         while( edgeItr.hasNext() ) {
1101           ReferenceEdge edge = edgeItr.next();
1102
1103           OwnershipNode on = edge.getSrc();
1104
1105           if( on instanceof LabelNode ) {
1106
1107             LabelNode ln0 = (LabelNode) on;
1108             if( ln0.equals(lnArg_i) ) {
1109               edgesReachable.add(edge);
1110             } else {
1111               edgesUpstream.add(edge);
1112             }
1113
1114           } else {
1115
1116             HeapRegionNode hrn0 = (HeapRegionNode) on;
1117             if( reachableNodes.contains(hrn0) ) {
1118               edgesReachable.add(edge);
1119             } else {
1120               edgesUpstream.add(edge);
1121             }
1122           }
1123         }
1124       }
1125
1126       // update reachable edges
1127       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1128       while( edgeReachableItr.hasNext() ) {
1129         ReferenceEdge edgeReachable = edgeReachableItr.next();
1130
1131         rewriteCallerReachability(index,
1132                                   null,
1133                                   edgeReachable,
1134                                   paramIndex2rewriteJ.get(index),
1135                                   paramIndex2rewriteD,
1136                                   paramIndex2paramToken.get(index),
1137                                   paramToken2paramIndex,
1138                                   paramTokenStar2paramIndex,
1139                                   false,
1140                                   null);
1141
1142         edgesWithNewBeta.add(edgeReachable);
1143       }
1144
1145       // update upstream edges
1146       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1147         new Hashtable<ReferenceEdge, ChangeTupleSet>();
1148
1149       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1150       while( edgeUpstreamItr.hasNext() ) {
1151         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1152
1153         rewriteCallerReachability(index,
1154                                   null,
1155                                   edgeUpstream,
1156                                   paramIndex2rewriteK.get(index),
1157                                   paramIndex2rewriteD,
1158                                   paramIndex2paramToken.get(index),
1159                                   paramToken2paramIndex,
1160                                   paramTokenStar2paramIndex,
1161                                   true,
1162                                   edgeUpstreamPlannedChanges);
1163
1164         edgesWithNewBeta.add(edgeUpstream);
1165       }
1166
1167       propagateTokensOverEdges(edgesUpstream,
1168                                edgeUpstreamPlannedChanges,
1169                                edgesWithNewBeta);
1170     }
1171
1172
1173     // commit changes to alpha and beta
1174     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1175     while( nodeItr.hasNext() ) {
1176       nodeItr.next().applyAlphaNew();
1177     }
1178
1179     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1180     while( edgeItr.hasNext() ) {
1181       edgeItr.next().applyBetaNew();
1182     }
1183
1184
1185     // verify the existence of allocation sites and their
1186     // shadows from the callee in the context of this caller graph
1187     // then map allocated nodes of callee onto the caller shadows
1188     // of them
1189     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1190     while( asItr.hasNext() ) {
1191       AllocationSite allocSite  = asItr.next();
1192       HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1193
1194       // assert that the shadow nodes have no reference edges
1195       // because they're brand new to the graph, or last time
1196       // they were used they should have been cleared of edges
1197       HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1198       assert hrnShadowSummary.getNumReferencers() == 0;
1199       assert hrnShadowSummary.getNumReferencees() == 0;
1200
1201       // then bring g_ij onto g'_ij and rewrite
1202       transferOnto(hrnSummary, hrnShadowSummary);
1203
1204       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1205       hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1206
1207       // shadow nodes only are touched by a rewrite one time,
1208       // so rewrite and immediately commit--and they don't belong
1209       // to a particular parameter, so use a bogus param index
1210       // that pulls a self-rewrite out of H
1211       rewriteCallerReachability(bogusIndex,
1212                                 hrnShadowSummary,
1213                                 null,
1214                                 hrnShadowSummary.getAlpha(),
1215                                 paramIndex2rewriteD,
1216                                 bogusToken,
1217                                 paramToken2paramIndex,
1218                                 paramTokenStar2paramIndex,
1219                                 false,
1220                                 null);
1221
1222       hrnShadowSummary.applyAlphaNew();
1223
1224
1225       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1226         Integer idIth = allocSite.getIthOldest(i);
1227         assert id2hrn.containsKey(idIth);
1228         HeapRegionNode hrnIth = id2hrn.get(idIth);
1229
1230         Integer idShadowIth = -(allocSite.getIthOldest(i));
1231         assert id2hrn.containsKey(idShadowIth);
1232         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1233         assert hrnIthShadow.getNumReferencers() == 0;
1234         assert hrnIthShadow.getNumReferencees() == 0;
1235
1236         transferOnto(hrnIth, hrnIthShadow);
1237
1238         assert ogCallee.id2hrn.containsKey(idIth);
1239         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1240         hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1241
1242         rewriteCallerReachability(bogusIndex,
1243                                   hrnIthShadow,
1244                                   null,
1245                                   hrnIthShadow.getAlpha(),
1246                                   paramIndex2rewriteD,
1247                                   bogusToken,
1248                                   paramToken2paramIndex,
1249                                   paramTokenStar2paramIndex,
1250                                   false,
1251                                   null);
1252
1253         hrnIthShadow.applyAlphaNew();
1254       }
1255     }
1256
1257
1258     // for every heap region->heap region edge in the
1259     // callee graph, create the matching edge or edges
1260     // in the caller graph
1261     Set sCallee = ogCallee.id2hrn.entrySet();
1262     Iterator iCallee = sCallee.iterator();
1263     while( iCallee.hasNext() ) {
1264       Map.Entry meCallee  = (Map.Entry)iCallee.next();
1265       Integer idCallee  = (Integer)        meCallee.getKey();
1266       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1267
1268       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1269       while( heapRegionsItrCallee.hasNext() ) {
1270         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1271         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1272         Integer idChildCallee         = hrnChildCallee.getID();
1273
1274         // only address this edge if it is not a special reflexive edge
1275         if( !edgeCallee.isInitialParamReflexive() ) {
1276
1277           // now we know that in the callee method's ownership graph
1278           // there is a heap region->heap region reference edge given
1279           // by heap region pointers:
1280           // hrnCallee -> heapChildCallee
1281           //
1282           // or by the ownership-graph independent ID's:
1283           // idCallee -> idChildCallee
1284
1285           // make the edge with src and dst so beta info is
1286           // calculated once, then copy it for each new edge in caller
1287           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1288                                                                     null,
1289                                                                     edgeCallee.getFieldDesc(),
1290                                                                     false,
1291                                                                     toShadowTokens(ogCallee, edgeCallee.getBeta() )
1292                                                                     );
1293           rewriteCallerReachability(bogusIndex,
1294                                     null,
1295                                     edgeNewInCallerTemplate,
1296                                     edgeNewInCallerTemplate.getBeta(),
1297                                     paramIndex2rewriteD,
1298                                     bogusToken,
1299                                     paramToken2paramIndex,
1300                                     paramTokenStar2paramIndex,
1301                                     false,
1302                                     null);
1303
1304           edgeNewInCallerTemplate.applyBetaNew();
1305
1306
1307           // So now make a set of possible source heaps in the caller graph
1308           // and a set of destination heaps in the caller graph, and make
1309           // a reference edge in the caller for every possible (src,dst) pair
1310           HashSet<HeapRegionNode> possibleCallerSrcs =
1311             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1312                                                 (HeapRegionNode) edgeCallee.getSrc(),
1313                                                 paramIndex2reachableCallerNodes);
1314
1315           HashSet<HeapRegionNode> possibleCallerDsts =
1316             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1317                                                 edgeCallee.getDst(),
1318                                                 paramIndex2reachableCallerNodes);
1319
1320
1321           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1322           Iterator srcItr = possibleCallerSrcs.iterator();
1323           while( srcItr.hasNext() ) {
1324             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1325
1326             if( !hasMatchingField(src, edgeCallee) ) {
1327               // prune this source node possibility
1328               continue;
1329             }
1330
1331             Iterator dstItr = possibleCallerDsts.iterator();
1332             while( dstItr.hasNext() ) {
1333               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1334
1335               if( !hasMatchingType(edgeCallee, dst) ) {
1336                 // prune
1337                 continue;
1338               }
1339
1340               // otherwise the caller src and dst pair can match the edge, so make it
1341               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1342               edgeNewInCaller.setSrc(src);
1343               edgeNewInCaller.setDst(dst);
1344
1345               ReferenceEdge edgeExisting = src.getReferenceTo(dst, edgeNewInCaller.getFieldDesc() );
1346               if( edgeExisting == null ) {
1347                 // if this edge doesn't exist in the caller, create it
1348                 addReferenceEdge(src, dst, edgeNewInCaller);
1349               } else {
1350                 // if it already exists, merge with it
1351                 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1352               }
1353             }
1354           }
1355         }
1356       }
1357     }
1358
1359
1360     // return value may need to be assigned in caller
1361     TempDescriptor returnTemp = fc.getReturnTemp();
1362     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1363
1364       LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1365       clearReferenceEdgesFrom(lnLhsCaller, null, true);
1366
1367       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1368       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1369       while( edgeCalleeItr.hasNext() ) {
1370         ReferenceEdge edgeCallee = edgeCalleeItr.next();
1371
1372         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1373                                                                   null,
1374                                                                   edgeCallee.getFieldDesc(),
1375                                                                   false,
1376                                                                   toShadowTokens(ogCallee, edgeCallee.getBeta() )
1377                                                                   );
1378         rewriteCallerReachability(bogusIndex,
1379                                   null,
1380                                   edgeNewInCallerTemplate,
1381                                   edgeNewInCallerTemplate.getBeta(),
1382                                   paramIndex2rewriteD,
1383                                   bogusToken,
1384                                   paramToken2paramIndex,
1385                                   paramTokenStar2paramIndex,
1386                                   false,
1387                                   null);
1388
1389         edgeNewInCallerTemplate.applyBetaNew();
1390
1391
1392         HashSet<HeapRegionNode> assignCallerRhs =
1393           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1394                                               edgeCallee.getDst(),
1395                                               paramIndex2reachableCallerNodes);
1396
1397         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
1398         while( itrHrn.hasNext() ) {
1399           HeapRegionNode hrnCaller = itrHrn.next();
1400
1401           if( !hasMatchingType(edgeCallee, hrnCaller) ) {
1402             // prune
1403             continue;
1404           }
1405
1406           // otherwise caller node can match callee edge, so make it
1407           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1408           edgeNewInCaller.setSrc(lnLhsCaller);
1409           edgeNewInCaller.setDst(hrnCaller);
1410
1411           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller, edgeNewInCaller.getFieldDesc() );
1412           if( edgeExisting == null ) {
1413
1414             // if this edge doesn't exist in the caller, create it
1415             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
1416           } else {
1417             // if it already exists, merge with it
1418             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1419           }
1420         }
1421       }
1422     }
1423
1424
1425     // merge the shadow nodes of allocation sites back down to normal capacity
1426     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1427     while( allocItr.hasNext() ) {
1428       AllocationSite as = allocItr.next();
1429
1430       // first age each allocation site enough times to make room for the shadow nodes
1431       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1432         age(as);
1433       }
1434
1435       // then merge the shadow summary into the normal summary
1436       HeapRegionNode hrnSummary = getSummaryNode(as);
1437       assert hrnSummary != null;
1438
1439       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
1440       assert hrnSummaryShadow != null;
1441
1442       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
1443
1444       // then clear off after merge
1445       clearReferenceEdgesFrom(hrnSummaryShadow, null, true);
1446       clearReferenceEdgesTo(hrnSummaryShadow, null, true);
1447       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1448
1449       // then transplant shadow nodes onto the now clean normal nodes
1450       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1451
1452         Integer idIth = as.getIthOldest(i);
1453         HeapRegionNode hrnIth = id2hrn.get(idIth);
1454
1455         Integer idIthShadow = as.getIthOldestShadow(i);
1456         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
1457
1458         transferOnto(hrnIthShadow, hrnIth);
1459
1460         // clear off shadow nodes after transfer
1461         clearReferenceEdgesFrom(hrnIthShadow, null, true);
1462         clearReferenceEdgesTo(hrnIthShadow, null, true);
1463         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
1464       }
1465
1466       // finally, globally change shadow tokens into normal tokens
1467       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
1468       while( itrAllLabelNodes.hasNext() ) {
1469         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
1470         LabelNode ln = (LabelNode) me.getValue();
1471
1472         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
1473         while( itrEdges.hasNext() ) {
1474           unshadowTokens(as, itrEdges.next() );
1475         }
1476       }
1477
1478       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1479       while( itrAllHRNodes.hasNext() ) {
1480         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1481         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1482
1483         unshadowTokens(as, hrnToAge);
1484
1485         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1486         while( itrEdges.hasNext() ) {
1487           unshadowTokens(as, itrEdges.next() );
1488         }
1489       }
1490     }
1491   }
1492
1493
1494   protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
1495
1496     // if no allocation site, then it's a match-everything region
1497     AllocationSite asSrc = src.getAllocationSite();
1498     if( asSrc == null ) {
1499       return true;
1500     }
1501
1502     TypeDescriptor tdSrc = asSrc.getType();
1503     assert tdSrc != null;
1504
1505     // if it's not a class, it doesn't have any fields to match
1506     if( !tdSrc.isClass() ) {
1507       return false;
1508     }
1509
1510     Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
1511     while( fieldsSrcItr.hasNext() ) {
1512       FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
1513       if( fd == edge.getFieldDesc() ) {
1514         return true;
1515       }
1516     }
1517
1518     // otherwise it is a class with fields
1519     // but we didn't find a match
1520     return false;
1521   }
1522
1523
1524   protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
1525
1526     // if the region has no type, matches everything
1527     AllocationSite asDst = dst.getAllocationSite();
1528     if( asDst == null ) {
1529       return true;
1530     }
1531
1532     TypeDescriptor tdDst = asDst.getType();
1533     assert tdDst != null;
1534
1535     // if the type is not a class don't match because
1536     // primitives are copied, no memory aliases
1537     ClassDescriptor cdDst = tdDst.getClassDesc();
1538     if( cdDst == null ) {
1539       return false;
1540     }
1541
1542     // if the field is null, it matches everything
1543     FieldDescriptor fd = edge.getFieldDesc();
1544     if( fd == null ) {
1545       return true;
1546     }
1547     TypeDescriptor tdFd = fd.getType();
1548     assert tdFd != null;
1549
1550     return typeUtil.isSuperorType(tdFd, tdDst);
1551   }
1552
1553
1554
1555   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
1556     edge.setBeta(edge.getBeta().unshadowTokens(as) );
1557   }
1558
1559   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
1560     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
1561   }
1562
1563
1564   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
1565                                          ReachabilitySet rsIn) {
1566
1567     ReachabilitySet rsOut = new ReachabilitySet(rsIn);
1568
1569     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
1570     while( allocItr.hasNext() ) {
1571       AllocationSite as = allocItr.next();
1572
1573       rsOut = rsOut.toShadowTokens(as);
1574     }
1575
1576     return rsOut.makeCanonical();
1577   }
1578
1579
1580   private void rewriteCallerReachability(Integer paramIndex,
1581                                          HeapRegionNode hrn,
1582                                          ReferenceEdge edge,
1583                                          ReachabilitySet rules,
1584                                          Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
1585                                          TokenTuple p_i,
1586                                          Hashtable<TokenTuple, Integer> paramToken2paramIndex,
1587                                          Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex,
1588                                          boolean makeChangeSet,
1589                                          Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
1590     assert (hrn == null && edge != null) ||
1591            (hrn != null && edge == null);
1592
1593     assert rules != null;
1594     assert p_i != null;
1595
1596     ReachabilitySet callerReachabilityCurrent;
1597     if( hrn == null ) {
1598       callerReachabilityCurrent = edge.getBeta();
1599     } else {
1600       callerReachabilityCurrent = hrn.getAlpha();
1601     }
1602
1603     ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
1604
1605     // for initializing structures in this method
1606     TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
1607
1608     // use this to construct a change set if required; the idea is to
1609     // map every partially rewritten token tuple set to the set of
1610     // caller-context token tuple sets that were used to generate it
1611     Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
1612       new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
1613     rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
1614
1615
1616     Iterator<TokenTupleSet> rulesItr = rules.iterator();
1617     while(rulesItr.hasNext()) {
1618       TokenTupleSet rule = rulesItr.next();
1619
1620       ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
1621
1622       Iterator<TokenTuple> ruleItr = rule.iterator();
1623       while(ruleItr.hasNext()) {
1624         TokenTuple ttCallee = ruleItr.next();
1625
1626         // compute the possibilities for rewriting this callee token
1627         ReachabilitySet ttCalleeRewrites = null;
1628         boolean callerSourceUsed = false;
1629
1630         if( ttCallee.equals( p_i ) ) {
1631           // replace the arity-one token of the current parameter with the reachability
1632           // information from the caller edge
1633           ttCalleeRewrites = callerReachabilityCurrent;
1634           callerSourceUsed = true;
1635
1636         } else if( paramToken2paramIndex.containsKey( ttCallee ) ||
1637                    paramTokenStar2paramIndex.containsKey( ttCallee ) ) {
1638
1639           // this token is another callee parameter, or any ARITY_MANY callee parameter,
1640           // so rewrite it with the D rules for that parameter
1641           Integer paramIndex_j;
1642           if( paramToken2paramIndex.containsKey( ttCallee ) ) {
1643             paramIndex_j = paramToken2paramIndex.get( ttCallee );
1644           } else {
1645             paramIndex_j = paramTokenStar2paramIndex.get( ttCallee );
1646           }
1647
1648           ttCalleeRewrites = paramIndex2rewriteD.get( paramIndex_j );
1649           assert ttCalleeRewrites != null;
1650
1651         } else {
1652
1653           // otherwise there's no need for a rewrite, just pass this one on
1654           TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
1655           ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
1656         }
1657
1658         // branch every version of the working rewritten rule with
1659         // the possibilities for rewriting the current callee token
1660         ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
1661
1662         Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
1663         while( rewrittenRuleItr.hasNext() ) {
1664           TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
1665
1666           Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
1667           while( ttCalleeRewritesItr.hasNext() ) {
1668             TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
1669
1670             TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity( ttsBranch );
1671
1672             if( makeChangeSet ) {
1673               // in order to keep the list of source token tuple sets
1674               // start with the sets used to make the partially rewritten
1675               // rule up to this point
1676               HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewritten );
1677               assert sourceSets != null;
1678
1679               // make a shallow copy for possible modification
1680               sourceSets = (HashSet<TokenTupleSet>) sourceSets.clone();
1681
1682               // if we used something from the caller to rewrite it, remember
1683               if( callerSourceUsed ) {
1684                 sourceSets.add( ttsBranch );
1685               }
1686
1687               // set mapping for the further rewritten rule
1688               rewritten2source.put( ttsRewrittenNext, sourceSets );
1689             }
1690
1691             rewrittenRuleWithTTCallee =
1692               rewrittenRuleWithTTCallee.union( ttsRewrittenNext );
1693           }
1694         }
1695
1696         // now the rewritten rule's possibilities have been extended by
1697         // rewriting the current callee token, remember result
1698         rewrittenRule = rewrittenRuleWithTTCallee;
1699       }
1700
1701       // the rule has been entirely rewritten into the caller context
1702       // now, so add it to the new reachability information
1703       callerReachabilityNew =
1704         callerReachabilityNew.union( rewrittenRule );
1705     }
1706
1707     if( makeChangeSet ) {
1708       ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
1709
1710       // each possibility for the final reachability should have a set of
1711       // caller sources mapped to it, use to create the change set
1712       Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
1713       while( callerReachabilityItr.hasNext() ) {
1714         TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
1715         HashSet<TokenTupleSet> sourceSets = rewritten2source.get( ttsRewrittenFinal );
1716         assert sourceSets != null;
1717
1718         Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
1719         while( sourceSetsItr.hasNext() ) {
1720           TokenTupleSet ttsSource = sourceSetsItr.next();
1721
1722           callerChangeSet =
1723             callerChangeSet.union( new ChangeTuple( ttsSource, ttsRewrittenFinal ) );
1724         }
1725       }
1726
1727       assert edgePlannedChanges != null;
1728       edgePlannedChanges.put(edge, callerChangeSet);
1729     }
1730
1731     if( hrn == null ) {
1732       edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
1733     } else {
1734       hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
1735     }
1736   }
1737
1738
1739
1740   private HashSet<HeapRegionNode>
1741   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
1742                                       HeapRegionNode hrnCallee,
1743                                       Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
1744                                       ) {
1745
1746     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
1747
1748     Integer paramIndexCallee = ogCallee.id2paramIndex.get(hrnCallee.getID() );
1749
1750     if( paramIndexCallee == null ) {
1751       // this is a node allocated in the callee then and it has
1752       // exactly one shadow node in the caller to map to
1753       AllocationSite as = hrnCallee.getAllocationSite();
1754       assert as != null;
1755
1756       int age = as.getAgeCategory(hrnCallee.getID() );
1757       assert age != AllocationSite.AGE_notInThisSite;
1758
1759       Integer idCaller;
1760       if( age == AllocationSite.AGE_summary ) {
1761         idCaller = as.getSummaryShadow();
1762       } else if( age == AllocationSite.AGE_oldest ) {
1763         idCaller = as.getOldestShadow();
1764       } else {
1765         assert age == AllocationSite.AGE_in_I;
1766
1767         Integer I = as.getAge(hrnCallee.getID() );
1768         assert I != null;
1769
1770         idCaller = as.getIthOldestShadow(I);
1771       }
1772
1773       assert id2hrn.containsKey(idCaller);
1774       HeapRegionNode hrnCaller = id2hrn.get(idCaller);
1775       possibleCallerHRNs.add(hrnCaller);
1776
1777     } else {
1778       // this is a node that was created to represent a parameter
1779       // so it maps to a whole mess of heap regions
1780       assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
1781       possibleCallerHRNs = paramIndex2reachableCallerNodes.get(paramIndexCallee);
1782     }
1783
1784     return possibleCallerHRNs;
1785   }
1786
1787
1788
1789   ////////////////////////////////////////////////////
1790   // in merge() and equals() methods the suffix A
1791   // represents the passed in graph and the suffix
1792   // B refers to the graph in this object
1793   // Merging means to take the incoming graph A and
1794   // merge it into B, so after the operation graph B
1795   // is the final result.
1796   ////////////////////////////////////////////////////
1797   public void merge(OwnershipGraph og) {
1798
1799     if( og == null ) {
1800       return;
1801     }
1802
1803     mergeOwnershipNodes(og);
1804     mergeReferenceEdges(og);
1805     mergeId2paramIndex(og);
1806     mergeAllocationSites(og);
1807   }
1808
1809
1810   protected void mergeOwnershipNodes(OwnershipGraph og) {
1811     Set sA = og.id2hrn.entrySet();
1812     Iterator iA = sA.iterator();
1813     while( iA.hasNext() ) {
1814       Map.Entry meA  = (Map.Entry)iA.next();
1815       Integer idA  = (Integer)        meA.getKey();
1816       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1817
1818       // if this graph doesn't have a node the
1819       // incoming graph has, allocate it
1820       if( !id2hrn.containsKey(idA) ) {
1821         HeapRegionNode hrnB = hrnA.copy();
1822         id2hrn.put(idA, hrnB);
1823
1824       } else {
1825         // otherwise this is a node present in both graphs
1826         // so make the new reachability set a union of the
1827         // nodes' reachability sets
1828         HeapRegionNode hrnB = id2hrn.get(idA);
1829         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
1830       }
1831     }
1832
1833     // now add any label nodes that are in graph B but
1834     // not in A
1835     sA = og.td2ln.entrySet();
1836     iA = sA.iterator();
1837     while( iA.hasNext() ) {
1838       Map.Entry meA = (Map.Entry)iA.next();
1839       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1840       LabelNode lnA = (LabelNode)      meA.getValue();
1841
1842       // if the label doesn't exist in B, allocate and add it
1843       LabelNode lnB = getLabelNodeFromTemp(tdA);
1844     }
1845   }
1846
1847   protected void mergeReferenceEdges(OwnershipGraph og) {
1848
1849     // heap regions
1850     Set sA = og.id2hrn.entrySet();
1851     Iterator iA = sA.iterator();
1852     while( iA.hasNext() ) {
1853       Map.Entry meA  = (Map.Entry)iA.next();
1854       Integer idA  = (Integer)        meA.getKey();
1855       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
1856
1857       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
1858       while( heapRegionsItrA.hasNext() ) {
1859         ReferenceEdge edgeA     = heapRegionsItrA.next();
1860         HeapRegionNode hrnChildA = edgeA.getDst();
1861         Integer idChildA  = hrnChildA.getID();
1862
1863         // at this point we know an edge in graph A exists
1864         // idA -> idChildA, does this exist in B?
1865         assert id2hrn.containsKey(idA);
1866         HeapRegionNode hrnB        = id2hrn.get(idA);
1867         ReferenceEdge edgeToMerge = null;
1868
1869         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
1870         while( heapRegionsItrB.hasNext() &&
1871                edgeToMerge == null          ) {
1872
1873           ReferenceEdge edgeB     = heapRegionsItrB.next();
1874           HeapRegionNode hrnChildB = edgeB.getDst();
1875           Integer idChildB  = hrnChildB.getID();
1876
1877           // don't use the ReferenceEdge.equals() here because
1878           // we're talking about existence between graphs
1879           if( idChildB.equals(idChildA) &&
1880               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1881             edgeToMerge = edgeB;
1882           }
1883         }
1884
1885         // if the edge from A was not found in B,
1886         // add it to B.
1887         if( edgeToMerge == null ) {
1888           assert id2hrn.containsKey(idChildA);
1889           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1890           edgeToMerge = edgeA.copy();
1891           edgeToMerge.setSrc(hrnB);
1892           edgeToMerge.setDst(hrnChildB);
1893           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
1894         }
1895         // otherwise, the edge already existed in both graphs
1896         // so merge their reachability sets
1897         else {
1898           // just replace this beta set with the union
1899           assert edgeToMerge != null;
1900           edgeToMerge.setBeta(
1901             edgeToMerge.getBeta().union(edgeA.getBeta() )
1902             );
1903           if( !edgeA.isInitialParamReflexive() ) {
1904             edgeToMerge.setIsInitialParamReflexive(false);
1905           }
1906         }
1907       }
1908     }
1909
1910     // and then again with label nodes
1911     sA = og.td2ln.entrySet();
1912     iA = sA.iterator();
1913     while( iA.hasNext() ) {
1914       Map.Entry meA = (Map.Entry)iA.next();
1915       TempDescriptor tdA = (TempDescriptor) meA.getKey();
1916       LabelNode lnA = (LabelNode)      meA.getValue();
1917
1918       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
1919       while( heapRegionsItrA.hasNext() ) {
1920         ReferenceEdge edgeA     = heapRegionsItrA.next();
1921         HeapRegionNode hrnChildA = edgeA.getDst();
1922         Integer idChildA  = hrnChildA.getID();
1923
1924         // at this point we know an edge in graph A exists
1925         // tdA -> idChildA, does this exist in B?
1926         assert td2ln.containsKey(tdA);
1927         LabelNode lnB         = td2ln.get(tdA);
1928         ReferenceEdge edgeToMerge = null;
1929
1930         // labels never have edges with a field
1931         //assert edgeA.getFieldDesc() == null;
1932
1933         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
1934         while( heapRegionsItrB.hasNext() &&
1935                edgeToMerge == null          ) {
1936
1937           ReferenceEdge edgeB     = heapRegionsItrB.next();
1938           HeapRegionNode hrnChildB = edgeB.getDst();
1939           Integer idChildB  = hrnChildB.getID();
1940
1941           // labels never have edges with a field
1942           //assert edgeB.getFieldDesc() == null;
1943
1944           // don't use the ReferenceEdge.equals() here because
1945           // we're talking about existence between graphs
1946           if( idChildB.equals(idChildA) &&
1947               edgeB.getFieldDesc() == edgeA.getFieldDesc() ) {
1948             edgeToMerge = edgeB;
1949           }
1950         }
1951
1952         // if the edge from A was not found in B,
1953         // add it to B.
1954         if( edgeToMerge == null ) {
1955           assert id2hrn.containsKey(idChildA);
1956           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
1957           edgeToMerge = edgeA.copy();
1958           edgeToMerge.setSrc(lnB);
1959           edgeToMerge.setDst(hrnChildB);
1960           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
1961         }
1962         // otherwise, the edge already existed in both graphs
1963         // so merge their reachability sets
1964         else {
1965           // just replace this beta set with the union
1966           edgeToMerge.setBeta(
1967             edgeToMerge.getBeta().union(edgeA.getBeta() )
1968             );
1969           if( !edgeA.isInitialParamReflexive() ) {
1970             edgeToMerge.setIsInitialParamReflexive(false);
1971           }
1972         }
1973       }
1974     }
1975   }
1976
1977   // you should only merge ownership graphs that have the
1978   // same number of parameters, or if one or both parameter
1979   // index tables are empty
1980   protected void mergeId2paramIndex(OwnershipGraph og) {
1981     if( id2paramIndex.size() == 0 ) {
1982       id2paramIndex  = og.id2paramIndex;
1983       paramIndex2id  = og.paramIndex2id;
1984       paramIndex2tdQ = og.paramIndex2tdQ;
1985       return;
1986     }
1987
1988     if( og.id2paramIndex.size() == 0 ) {
1989       return;
1990     }
1991
1992     assert id2paramIndex.size() == og.id2paramIndex.size();
1993   }
1994
1995   protected void mergeAllocationSites(OwnershipGraph og) {
1996     allocationSites.addAll(og.allocationSites);
1997   }
1998
1999
2000
2001   // it is necessary in the equals() member functions
2002   // to "check both ways" when comparing the data
2003   // structures of two graphs.  For instance, if all
2004   // edges between heap region nodes in graph A are
2005   // present and equal in graph B it is not sufficient
2006   // to say the graphs are equal.  Consider that there
2007   // may be edges in graph B that are not in graph A.
2008   // the only way to know that all edges in both graphs
2009   // are equally present is to iterate over both data
2010   // structures and compare against the other graph.
2011   public boolean equals(OwnershipGraph og) {
2012
2013     if( og == null ) {
2014       return false;
2015     }
2016
2017     if( !areHeapRegionNodesEqual(og) ) {
2018       return false;
2019     }
2020
2021     if( !areLabelNodesEqual(og) ) {
2022       return false;
2023     }
2024
2025     if( !areReferenceEdgesEqual(og) ) {
2026       return false;
2027     }
2028
2029     if( !areId2paramIndexEqual(og) ) {
2030       return false;
2031     }
2032
2033     // if everything is equal up to this point,
2034     // assert that allocationSites is also equal--
2035     // this data is redundant and kept for efficiency
2036     assert allocationSites.equals(og.allocationSites);
2037
2038     return true;
2039   }
2040
2041   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2042
2043     if( !areallHRNinAalsoinBandequal(this, og) ) {
2044       return false;
2045     }
2046
2047     if( !areallHRNinAalsoinBandequal(og, this) ) {
2048       return false;
2049     }
2050
2051     return true;
2052   }
2053
2054   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2055                                                        OwnershipGraph ogB) {
2056     Set sA = ogA.id2hrn.entrySet();
2057     Iterator iA = sA.iterator();
2058     while( iA.hasNext() ) {
2059       Map.Entry meA  = (Map.Entry)iA.next();
2060       Integer idA  = (Integer)        meA.getKey();
2061       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2062
2063       if( !ogB.id2hrn.containsKey(idA) ) {
2064         return false;
2065       }
2066
2067       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2068       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2069         return false;
2070       }
2071     }
2072
2073     return true;
2074   }
2075
2076
2077   protected boolean areLabelNodesEqual(OwnershipGraph og) {
2078
2079     if( !areallLNinAalsoinBandequal(this, og) ) {
2080       return false;
2081     }
2082
2083     if( !areallLNinAalsoinBandequal(og, this) ) {
2084       return false;
2085     }
2086
2087     return true;
2088   }
2089
2090   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
2091                                                       OwnershipGraph ogB) {
2092     Set sA = ogA.td2ln.entrySet();
2093     Iterator iA = sA.iterator();
2094     while( iA.hasNext() ) {
2095       Map.Entry meA = (Map.Entry)iA.next();
2096       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2097
2098       if( !ogB.td2ln.containsKey(tdA) ) {
2099         return false;
2100       }
2101     }
2102
2103     return true;
2104   }
2105
2106
2107   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
2108     if( !areallREinAandBequal(this, og) ) {
2109       return false;
2110     }
2111
2112     return true;
2113   }
2114
2115   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
2116                                                 OwnershipGraph ogB) {
2117
2118     // check all the heap region->heap region edges
2119     Set sA = ogA.id2hrn.entrySet();
2120     Iterator iA = sA.iterator();
2121     while( iA.hasNext() ) {
2122       Map.Entry meA  = (Map.Entry)iA.next();
2123       Integer idA  = (Integer)        meA.getKey();
2124       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2125
2126       // we should have already checked that the same
2127       // heap regions exist in both graphs
2128       assert ogB.id2hrn.containsKey(idA);
2129
2130       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
2131         return false;
2132       }
2133
2134       // then check every edge in B for presence in A, starting
2135       // from the same parent HeapRegionNode
2136       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2137
2138       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
2139         return false;
2140       }
2141     }
2142
2143     // then check all the label->heap region edges
2144     sA = ogA.td2ln.entrySet();
2145     iA = sA.iterator();
2146     while( iA.hasNext() ) {
2147       Map.Entry meA = (Map.Entry)iA.next();
2148       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2149       LabelNode lnA = (LabelNode)      meA.getValue();
2150
2151       // we should have already checked that the same
2152       // label nodes exist in both graphs
2153       assert ogB.td2ln.containsKey(tdA);
2154
2155       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
2156         return false;
2157       }
2158
2159       // then check every edge in B for presence in A, starting
2160       // from the same parent LabelNode
2161       LabelNode lnB = ogB.td2ln.get(tdA);
2162
2163       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
2164         return false;
2165       }
2166     }
2167
2168     return true;
2169   }
2170
2171
2172   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
2173                                                  OwnershipNode onA,
2174                                                  OwnershipGraph ogB) {
2175
2176     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
2177     while( itrA.hasNext() ) {
2178       ReferenceEdge edgeA     = itrA.next();
2179       HeapRegionNode hrnChildA = edgeA.getDst();
2180       Integer idChildA  = hrnChildA.getID();
2181
2182       assert ogB.id2hrn.containsKey(idChildA);
2183
2184       // at this point we know an edge in graph A exists
2185       // onA -> idChildA, does this exact edge exist in B?
2186       boolean edgeFound = false;
2187
2188       OwnershipNode onB = null;
2189       if( onA instanceof HeapRegionNode ) {
2190         HeapRegionNode hrnA = (HeapRegionNode) onA;
2191         onB = ogB.id2hrn.get(hrnA.getID() );
2192       } else {
2193         LabelNode lnA = (LabelNode) onA;
2194         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
2195       }
2196
2197       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
2198       while( itrB.hasNext() ) {
2199         ReferenceEdge edgeB     = itrB.next();
2200         HeapRegionNode hrnChildB = edgeB.getDst();
2201         Integer idChildB  = hrnChildB.getID();
2202
2203         if( idChildA.equals(idChildB) &&
2204             edgeA.getFieldDesc() == edgeB.getFieldDesc() ) {
2205
2206           // there is an edge in the right place with the right field,
2207           // but do they have the same attributes?
2208           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
2209
2210             edgeFound = true;
2211             //} else {
2212             //return false;
2213           }
2214         }
2215       }
2216
2217       if( !edgeFound ) {
2218         return false;
2219       }
2220     }
2221
2222     return true;
2223   }
2224
2225
2226   protected boolean areId2paramIndexEqual(OwnershipGraph og) {
2227     return id2paramIndex.size() == og.id2paramIndex.size();
2228   }
2229
2230
2231   public boolean hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
2232
2233     // get parameter's heap region
2234     assert paramIndex2id.containsKey(paramIndex1);
2235     Integer idParam1 = paramIndex2id.get(paramIndex1);
2236
2237     assert id2hrn.containsKey(idParam1);
2238     HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
2239     assert hrnParam1 != null;
2240
2241     // get tokens for this parameter
2242     TokenTuple p1 = new TokenTuple(hrnParam1.getID(),
2243                                    true,
2244                                    TokenTuple.ARITY_ONE).makeCanonical();
2245
2246     TokenTuple pStar1 = new TokenTuple(hrnParam1.getID(),
2247                                        true,
2248                                        TokenTuple.ARITY_MANY).makeCanonical();
2249
2250
2251     // get tokens for the other parameter
2252     assert paramIndex2id.containsKey(paramIndex2);
2253     Integer idParam2 = paramIndex2id.get(paramIndex2);
2254
2255     assert id2hrn.containsKey(idParam2);
2256     HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
2257     assert hrnParam2 != null;
2258
2259     TokenTuple p2 = new TokenTuple(hrnParam2.getID(),
2260                                    true,
2261                                    TokenTuple.ARITY_ONE).makeCanonical();
2262
2263     TokenTuple pStar2 = new TokenTuple(hrnParam2.getID(),
2264                                        true,
2265                                        TokenTuple.ARITY_MANY).makeCanonical();
2266
2267
2268     // get special label p_q for first parameter
2269     TempDescriptor tdParamQ1 = paramIndex2tdQ.get(paramIndex1);
2270     assert tdParamQ1 != null;
2271     LabelNode lnParamQ1 = td2ln.get(tdParamQ1);
2272     assert lnParamQ1 != null;
2273
2274     // then get the edge from label q to parameter's hrn
2275     ReferenceEdge edgeSpecialQ1 = lnParamQ1.getReferenceTo(hrnParam1, null);
2276     assert edgeSpecialQ1 != null;
2277
2278     // if the beta of this edge has tokens from both parameters in one
2279     // token tuple set, then there is a potential alias between them
2280     ReachabilitySet beta1 = edgeSpecialQ1.getBeta();
2281     assert beta1 != null;
2282
2283     if( beta1.containsTupleSetWithBoth(p1,     p2) ) {
2284       return true;
2285     }
2286     if( beta1.containsTupleSetWithBoth(pStar1, p2) ) {
2287       return true;
2288     }
2289     if( beta1.containsTupleSetWithBoth(p1,     pStar2) ) {
2290       return true;
2291     }
2292     if( beta1.containsTupleSetWithBoth(pStar1, pStar2) ) {
2293       return true;
2294     }
2295
2296     return false;
2297   }
2298
2299
2300   public boolean hasPotentialAlias(Integer paramIndex, AllocationSite as) {
2301
2302     // get parameter's heap region
2303     assert paramIndex2id.containsKey(paramIndex);
2304     Integer idParam = paramIndex2id.get(paramIndex);
2305
2306     assert id2hrn.containsKey(idParam);
2307     HeapRegionNode hrnParam = id2hrn.get(idParam);
2308     assert hrnParam != null;
2309
2310     // get tokens for this parameter
2311     TokenTuple p = new TokenTuple(hrnParam.getID(),
2312                                   true,
2313                                   TokenTuple.ARITY_ONE).makeCanonical();
2314
2315     TokenTuple pStar = new TokenTuple(hrnParam.getID(),
2316                                       true,
2317                                       TokenTuple.ARITY_MANY).makeCanonical();
2318
2319     // get special label p_q
2320     TempDescriptor tdParamQ = paramIndex2tdQ.get(paramIndex);
2321     assert tdParamQ != null;
2322     LabelNode lnParamQ = td2ln.get(tdParamQ);
2323     assert lnParamQ != null;
2324
2325     // then get the edge from label q to parameter's hrn
2326     ReferenceEdge edgeSpecialQ = lnParamQ.getReferenceTo(hrnParam, null);
2327     assert edgeSpecialQ != null;
2328
2329     // look through this beta set for potential aliases
2330     ReachabilitySet beta = edgeSpecialQ.getBeta();
2331     assert beta != null;
2332
2333
2334     // get tokens for summary node
2335     TokenTuple gs = new TokenTuple(as.getSummary(),
2336                                    true,
2337                                    TokenTuple.ARITY_ONE).makeCanonical();
2338
2339     TokenTuple gsStar = new TokenTuple(as.getSummary(),
2340                                        true,
2341                                        TokenTuple.ARITY_MANY).makeCanonical();
2342
2343     if( beta.containsTupleSetWithBoth(p,     gs) ) {
2344       return true;
2345     }
2346     if( beta.containsTupleSetWithBoth(pStar, gs) ) {
2347       return true;
2348     }
2349     if( beta.containsTupleSetWithBoth(p,     gsStar) ) {
2350       return true;
2351     }
2352     if( beta.containsTupleSetWithBoth(pStar, gsStar) ) {
2353       return true;
2354     }
2355
2356     // check for other nodes
2357     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2358
2359       // the other nodes of an allocation site are single, no stars
2360       TokenTuple gi = new TokenTuple(as.getIthOldest(i),
2361                                      false,
2362                                      TokenTuple.ARITY_ONE).makeCanonical();
2363
2364       if( beta.containsTupleSetWithBoth(p,     gi) ) {
2365         return true;
2366       }
2367       if( beta.containsTupleSetWithBoth(pStar, gi) ) {
2368         return true;
2369       }
2370     }
2371
2372     return false;
2373   }
2374
2375
2376   public boolean hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
2377
2378     // get tokens for summary nodes
2379     TokenTuple gs1 = new TokenTuple(as1.getSummary(),
2380                                     true,
2381                                     TokenTuple.ARITY_ONE).makeCanonical();
2382
2383     TokenTuple gsStar1 = new TokenTuple(as1.getSummary(),
2384                                         true,
2385                                         TokenTuple.ARITY_MANY).makeCanonical();
2386
2387     // get summary node's alpha
2388     Integer idSum1 = as1.getSummary();
2389     assert id2hrn.containsKey(idSum1);
2390     HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
2391     assert hrnSum1 != null;
2392     ReachabilitySet alphaSum1 = hrnSum1.getAlpha();
2393     assert alphaSum1 != null;
2394
2395
2396     // and for the other one
2397     TokenTuple gs2 = new TokenTuple(as2.getSummary(),
2398                                     true,
2399                                     TokenTuple.ARITY_ONE).makeCanonical();
2400
2401     TokenTuple gsStar2 = new TokenTuple(as2.getSummary(),
2402                                         true,
2403                                         TokenTuple.ARITY_MANY).makeCanonical();
2404
2405     // get summary node's alpha
2406     Integer idSum2 = as2.getSummary();
2407     assert id2hrn.containsKey(idSum2);
2408     HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
2409     assert hrnSum2 != null;
2410     ReachabilitySet alphaSum2 = hrnSum2.getAlpha();
2411     assert alphaSum2 != null;
2412
2413     // does either one report reachability from the other tokens?
2414     if( alphaSum1.containsTuple(gsStar2) ) {
2415       return true;
2416     }
2417     if( alphaSum2.containsTuple(gsStar1) ) {
2418       return true;
2419     }
2420
2421     // only check non-star token if they are different sites
2422     if( as1 != as2 ) {
2423       if( alphaSum1.containsTuple(gs2) ) {
2424         return true;
2425       }
2426       if( alphaSum2.containsTuple(gs1) ) {
2427         return true;
2428       }
2429     }
2430
2431
2432     // check sum2 against alloc1 nodes
2433     for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
2434       Integer idI1 = as1.getIthOldest(i);
2435       assert id2hrn.containsKey(idI1);
2436       HeapRegionNode hrnI1 = id2hrn.get(idI1);
2437       assert hrnI1 != null;
2438       ReachabilitySet alphaI1 = hrnI1.getAlpha();
2439       assert alphaI1 != null;
2440
2441       // the other nodes of an allocation site are single, no stars
2442       TokenTuple gi1 = new TokenTuple(as1.getIthOldest(i),
2443                                       false,
2444                                       TokenTuple.ARITY_ONE).makeCanonical();
2445
2446       if( alphaSum2.containsTuple(gi1) ) {
2447         return true;
2448       }
2449       if( alphaI1.containsTuple(gs2) ) {
2450         return true;
2451       }
2452       if( alphaI1.containsTuple(gsStar2) ) {
2453         return true;
2454       }
2455     }
2456
2457     // check sum1 against alloc2 nodes
2458     for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
2459       Integer idI2 = as2.getIthOldest(i);
2460       assert id2hrn.containsKey(idI2);
2461       HeapRegionNode hrnI2 = id2hrn.get(idI2);
2462       assert hrnI2 != null;
2463       ReachabilitySet alphaI2 = hrnI2.getAlpha();
2464       assert alphaI2 != null;
2465
2466       TokenTuple gi2 = new TokenTuple(as2.getIthOldest(i),
2467                                       false,
2468                                       TokenTuple.ARITY_ONE).makeCanonical();
2469
2470       if( alphaSum1.containsTuple(gi2) ) {
2471         return true;
2472       }
2473       if( alphaI2.containsTuple(gs1) ) {
2474         return true;
2475       }
2476       if( alphaI2.containsTuple(gsStar1) ) {
2477         return true;
2478       }
2479
2480       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
2481       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
2482         Integer idI1 = as1.getIthOldest(j);
2483
2484         // if these are the same site, don't look for the same token, no alias
2485         // different tokens of the same site could alias together though
2486         if( idI1 == idI2 ) {
2487           continue;
2488         }
2489
2490         HeapRegionNode hrnI1 = id2hrn.get(idI1);
2491         ReachabilitySet alphaI1 = hrnI1.getAlpha();
2492         TokenTuple gi1 = new TokenTuple(as1.getIthOldest(j),
2493                                         false,
2494                                         TokenTuple.ARITY_ONE).makeCanonical();
2495         if( alphaI2.containsTuple(gi1) ) {
2496           return true;
2497         }
2498         if( alphaI1.containsTuple(gi2) ) {
2499           return true;
2500         }
2501       }
2502     }
2503
2504     return false;
2505   }
2506
2507
2508   // for writing ownership graphs to dot files
2509   public void writeGraph(Descriptor methodDesc,
2510                          FlatNode fn,
2511                          boolean writeLabels,
2512                          boolean labelSelect,
2513                          boolean pruneGarbage,
2514                          boolean writeReferencers,
2515                          boolean writeParamMappings
2516                          ) throws java.io.IOException {
2517     writeGraph(
2518       methodDesc.getSymbol() +
2519       methodDesc.getNum() +
2520       fn.toString(),
2521       writeLabels,
2522       labelSelect,
2523       pruneGarbage,
2524       writeReferencers,
2525       writeParamMappings
2526       );
2527   }
2528
2529   public void writeGraph(Descriptor methodDesc,
2530                          boolean writeLabels,
2531                          boolean labelSelect,
2532                          boolean pruneGarbage,
2533                          boolean writeReferencers,
2534                          boolean writeParamMappings
2535                          ) throws java.io.IOException {
2536
2537     writeGraph(methodDesc+"COMPLETE",
2538                writeLabels,
2539                labelSelect,
2540                pruneGarbage,
2541                writeReferencers,
2542                writeParamMappings
2543                );
2544   }
2545
2546   public void writeGraph(Descriptor methodDesc,
2547                          Integer numUpdate,
2548                          boolean writeLabels,
2549                          boolean labelSelect,
2550                          boolean pruneGarbage,
2551                          boolean writeReferencers,
2552                          boolean writeParamMappings
2553                          ) throws java.io.IOException {
2554
2555     writeGraph(methodDesc+"COMPLETE"+String.format("%05d", numUpdate),
2556                writeLabels,
2557                labelSelect,
2558                pruneGarbage,
2559                writeReferencers,
2560                writeParamMappings
2561                );
2562   }
2563
2564   public void writeGraph(String graphName,
2565                          boolean writeLabels,
2566                          boolean labelSelect,
2567                          boolean pruneGarbage,
2568                          boolean writeReferencers,
2569                          boolean writeParamMappings
2570                          ) throws java.io.IOException {
2571
2572     // remove all non-word characters from the graph name so
2573     // the filename and identifier in dot don't cause errors
2574     graphName = graphName.replaceAll("[\\W]", "");
2575
2576     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
2577     bw.write("digraph "+graphName+" {\n");
2578
2579     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
2580
2581     // then visit every heap region node
2582     if( !pruneGarbage ) {
2583       Set s = id2hrn.entrySet();
2584       Iterator i = s.iterator();
2585       while( i.hasNext() ) {
2586         Map.Entry me  = (Map.Entry)i.next();
2587         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2588         if( !visited.contains(hrn) ) {
2589           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2590                                   hrn,
2591                                   bw,
2592                                   null,
2593                                   visited,
2594                                   writeReferencers);
2595         }
2596       }
2597     }
2598
2599     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
2600
2601     if( writeParamMappings ) {
2602       Set df = paramIndex2id.entrySet();
2603       Iterator ih = df.iterator();
2604       while( ih.hasNext() ) {
2605         Map.Entry meh = (Map.Entry)ih.next();
2606         Integer pi = (Integer) meh.getKey();
2607         Integer id = (Integer) meh.getValue();
2608         bw.write("  pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
2609       }
2610     }
2611
2612     // then visit every label node, useful for debugging
2613     if( writeLabels ) {
2614       Set s = td2ln.entrySet();
2615       Iterator i = s.iterator();
2616       while( i.hasNext() ) {
2617         Map.Entry me = (Map.Entry)i.next();
2618         LabelNode ln = (LabelNode) me.getValue();
2619
2620         if( labelSelect ) {
2621           String labelStr = ln.getTempDescriptorString();
2622           if( labelStr.startsWith("___temp") ||
2623               labelStr.startsWith("___dst") ||
2624               labelStr.startsWith("___srctmp") ||
2625               labelStr.startsWith("___neverused")   ) {
2626             continue;
2627           }
2628         }
2629
2630         //bw.write("  "+ln.toString() + ";\n");
2631
2632         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
2633         while( heapRegionsItr.hasNext() ) {
2634           ReferenceEdge edge = heapRegionsItr.next();
2635           HeapRegionNode hrn  = edge.getDst();
2636
2637           if( pruneGarbage && !visited.contains(hrn) ) {
2638             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
2639                                     hrn,
2640                                     bw,
2641                                     null,
2642                                     visited,
2643                                     writeReferencers);
2644           }
2645
2646           bw.write("  "        + ln.toString() +
2647                    " -> "      + hrn.toString() +
2648                    "[label=\"" + edge.toGraphEdgeString() +
2649                    "\",decorate];\n");
2650         }
2651       }
2652     }
2653
2654
2655     bw.write("}\n");
2656     bw.close();
2657   }
2658
2659   protected void traverseHeapRegionNodes(int mode,
2660                                          HeapRegionNode hrn,
2661                                          BufferedWriter bw,
2662                                          TempDescriptor td,
2663                                          HashSet<HeapRegionNode> visited,
2664                                          boolean writeReferencers
2665                                          ) throws java.io.IOException {
2666
2667     if( visited.contains(hrn) ) {
2668       return;
2669     }
2670     visited.add(hrn);
2671
2672     switch( mode ) {
2673     case VISIT_HRN_WRITE_FULL:
2674
2675       String attributes = "[";
2676
2677       if( hrn.isSingleObject() ) {
2678         attributes += "shape=box";
2679       } else {
2680         attributes += "shape=Msquare";
2681       }
2682
2683       if( hrn.isFlagged() ) {
2684         attributes += ",style=filled,fillcolor=lightgrey";
2685       }
2686
2687       attributes += ",label=\"ID"        +
2688                     hrn.getID()          +
2689                     "\\n"                +
2690                     hrn.getDescription() +
2691                     "\\n"                +
2692                     hrn.getAlphaString() +
2693                     "\"]";
2694
2695       bw.write("  " + hrn.toString() + attributes + ";\n");
2696       break;
2697     }
2698
2699
2700     // useful for debugging
2701     if( writeReferencers ) {
2702       OwnershipNode onRef  = null;
2703       Iterator refItr = hrn.iteratorToReferencers();
2704       while( refItr.hasNext() ) {
2705         onRef = (OwnershipNode) refItr.next();
2706
2707         switch( mode ) {
2708         case VISIT_HRN_WRITE_FULL:
2709           bw.write("  "                    + hrn.toString() +
2710                    " -> "                  + onRef.toString() +
2711                    "[color=lightgray];\n");
2712           break;
2713         }
2714       }
2715     }
2716
2717     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
2718     while( childRegionsItr.hasNext() ) {
2719       ReferenceEdge edge     = childRegionsItr.next();
2720       HeapRegionNode hrnChild = edge.getDst();
2721
2722       switch( mode ) {
2723       case VISIT_HRN_WRITE_FULL:
2724         bw.write("  "        + hrn.toString() +
2725                  " -> "      + hrnChild.toString() +
2726                  "[label=\"" + edge.toGraphEdgeString() +
2727                  "\",decorate];\n");
2728         break;
2729       }
2730
2731       traverseHeapRegionNodes(mode,
2732                               hrnChild,
2733                               bw,
2734                               td,
2735                               visited,
2736                               writeReferencers);
2737     }
2738   }
2739 }