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