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   protected static final int bogusParamIndexInt = -2;
  23
  24
  25   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  26   public Hashtable<TempDescriptor, LabelNode     > td2ln;
  27   public Hashtable<Integer,        Set<Integer>  > idPrimary2paramIndexSet;
  28   public Hashtable<Integer,        Integer       > paramIndex2idPrimary;
  29   public Hashtable<Integer,        Set<Integer>  > idSecondary2paramIndexSet;
  30   public Hashtable<Integer,        Integer       > paramIndex2idSecondary;
  31   public Hashtable<Integer,        TempDescriptor> paramIndex2tdQ;
  32
  33   public HashSet<AllocationSite> allocationSites;
  34
  35
  36   public OwnershipGraph(int allocationDepth, TypeUtil typeUtil) {
  37     this.allocationDepth = allocationDepth;
  38     this.typeUtil        = typeUtil;
  39
  40     id2hrn                    = new Hashtable<Integer,        HeapRegionNode>();
  41     td2ln                     = new Hashtable<TempDescriptor, LabelNode     >();
  42     idPrimary2paramIndexSet   = new Hashtable<Integer,        Set<Integer>  >();
  43     paramIndex2idPrimary      = new Hashtable<Integer,        Integer       >();
  44     idSecondary2paramIndexSet = new Hashtable<Integer,        Set<Integer>  >();
  45     paramIndex2idSecondary    = new Hashtable<Integer,        Integer       >();
  46     paramIndex2tdQ            = new Hashtable<Integer,        TempDescriptor>();
  47
  48     allocationSites = new HashSet <AllocationSite>();
  49   }
  50
  51
  52   // label nodes are much easier to deal with than
  53   // heap region nodes.  Whenever there is a request
  54   // for the label node that is associated with a
  55   // temp descriptor we can either find it or make a
  56   // new one and return it.  This is because temp
  57   // descriptors are globally unique and every label
  58   // node is mapped to exactly one temp descriptor.
  59   protected LabelNode getLabelNodeFromTemp(TempDescriptor td) {
  60     assert td != null;
  61
  62     if( !td2ln.containsKey(td) ) {
  63       td2ln.put(td, new LabelNode(td) );
  64     }
  65
  66     return td2ln.get(td);
  67   }
  68
  69
  70   // the reason for this method is to have the option
  71   // creating new heap regions with specific IDs, or
  72   // duplicating heap regions with specific IDs (especially
  73   // in the merge() operation) or to create new heap
  74   // regions with a new unique ID.
  75   protected HeapRegionNode
  76   createNewHeapRegionNode(Integer id,
  77                           boolean isSingleObject,
  78                           boolean isNewSummary,
  79                           boolean isFlagged,
  80                           boolean isParameter,
  81                           TypeDescriptor type,
  82                           AllocationSite allocSite,
  83                           ReachabilitySet alpha,
  84                           String description) {
  85
  86     boolean markForAnalysis = isFlagged || isParameter;
  87
  88     TypeDescriptor typeToUse = null;
  89     if( allocSite != null ) {
  90       typeToUse = allocSite.getType();
  91     } else {
  92       typeToUse = type;
  93     }
  94
  95     if( allocSite != null && allocSite.getDisjointId() != null ) {
  96       markForAnalysis = true;
  97     }
  98
  99     if( id == null ) {
 100       id = OwnershipAnalysis.generateUniqueHeapRegionNodeID();
 101     }
 102
 103     if( alpha == null ) {
 104       if( markForAnalysis ) {
 105         alpha = new ReachabilitySet(
 106           new TokenTuple(id,
 107                          !isSingleObject,
 108                          TokenTuple.ARITY_ONE
 109                          ).makeCanonical()
 110           ).makeCanonical();
 111       } else {
 112         alpha = new ReachabilitySet(
 113           new TokenTupleSet().makeCanonical()
 114           ).makeCanonical();
 115       }
 116     }
 117
 118     HeapRegionNode hrn = new HeapRegionNode(id,
 119                                             isSingleObject,
 120                                             markForAnalysis,
 121                                             isParameter,
 122                                             isNewSummary,
 123                                             typeToUse,
 124                                             allocSite,
 125                                             alpha,
 126                                             description);
 127     id2hrn.put(id, hrn);
 128     return hrn;
 129   }
 130
 131
 132
 133   ////////////////////////////////////////////////
 134   //
 135   //  Low-level referencee and referencer methods
 136   //
 137   //  These methods provide the lowest level for
 138   //  creating references between ownership nodes
 139   //  and handling the details of maintaining both
 140   //  list of referencers and referencees.
 141   //
 142   ////////////////////////////////////////////////
 143   protected void addReferenceEdge(OwnershipNode referencer,
 144                                   HeapRegionNode referencee,
 145                                   ReferenceEdge edge) {
 146     assert referencer != null;
 147     assert referencee != null;
 148     assert edge       != null;
 149     assert edge.getSrc() == referencer;
 150     assert edge.getDst() == referencee;
 151
 152     referencer.addReferencee(edge);
 153     referencee.addReferencer(edge);
 154   }
 155
 156   protected void removeReferenceEdge(OwnershipNode referencer,
 157                                      HeapRegionNode referencee,
 158                                      TypeDescriptor type,
 159                                      String field) {
 160     assert referencer != null;
 161     assert referencee != null;
 162
 163     ReferenceEdge edge = referencer.getReferenceTo(referencee,
 164                                                    type,
 165                                                    field);
 166     assert edge != null;
 167     assert edge == referencee.getReferenceFrom(referencer,
 168                                                type,
 169                                                field);
 170
 171     referencer.removeReferencee(edge);
 172     referencee.removeReferencer(edge);
 173   }
 174
 175   protected void clearReferenceEdgesFrom(OwnershipNode referencer,
 176                                          TypeDescriptor type,
 177                                          String field,
 178                                          boolean removeAll) {
 179     assert referencer != null;
 180
 181     // get a copy of the set to iterate over, otherwise
 182     // we will be trying to take apart the set as we
 183     // are iterating over it, which won't work
 184     Iterator<ReferenceEdge> i = referencer.iteratorToReferenceesClone();
 185     while( i.hasNext() ) {
 186       ReferenceEdge edge = i.next();
 187
 188       if( removeAll                                          ||
 189           (type  != null && edge.getType() .equals( type  )) ||
 190           (field != null && edge.getField().equals( field ))
 191         ){
 192
 193         HeapRegionNode referencee = edge.getDst();
 194
 195         removeReferenceEdge(referencer,
 196                             referencee,
 197                             edge.getType(),
 198                             edge.getField() );
 199       }
 200     }
 201   }
 202
 203   protected void clearReferenceEdgesTo(HeapRegionNode referencee,
 204                                        TypeDescriptor type,
 205                                        String field,
 206                                        boolean removeAll) {
 207     assert referencee != null;
 208
 209     // get a copy of the set to iterate over, otherwise
 210     // we will be trying to take apart the set as we
 211     // are iterating over it, which won't work
 212     Iterator<ReferenceEdge> i = referencee.iteratorToReferencersClone();
 213     while( i.hasNext() ) {
 214       ReferenceEdge edge = i.next();
 215
 216       if( removeAll                                          ||
 217           (type  != null && edge.getType() .equals( type  )) ||
 218           (field != null && edge.getField().equals( field ))
 219         ){
 220
 221         OwnershipNode referencer = edge.getSrc();
 222
 223         removeReferenceEdge(referencer,
 224                             referencee,
 225                             edge.getType(),
 226                             edge.getField() );
 227       }
 228     }
 229   }
 230
 231
 232   ////////////////////////////////////////////////////
 233   //
 234   //  Assignment Operation Methods
 235   //
 236   //  These methods are high-level operations for
 237   //  modeling program assignment statements using
 238   //  the low-level reference create/remove methods
 239   //  above.
 240   //
 241   //  The destination in an assignment statement is
 242   //  going to have new references.  The method of
 243   //  determining the references depends on the type
 244   //  of the FlatNode assignment and the predicates
 245   //  of the nodes and edges involved.
 246   //
 247   ////////////////////////////////////////////////////
 248   public void assignTempXEqualToTempY(TempDescriptor x,
 249                                       TempDescriptor y) {
 250
 251     LabelNode lnX = getLabelNodeFromTemp(x);
 252     LabelNode lnY = getLabelNodeFromTemp(y);
 253
 254     clearReferenceEdgesFrom(lnX, null, null, true);
 255
 256     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 257     while( itrYhrn.hasNext() ) {
 258       ReferenceEdge  edgeY      = itrYhrn.next();
 259       HeapRegionNode referencee = edgeY.getDst();
 260       ReferenceEdge  edgeNew    = edgeY.copy();
 261       edgeNew.setSrc(lnX);
 262
 263       addReferenceEdge(lnX, referencee, edgeNew);
 264     }
 265   }
 266
 267
 268   public void assignTypedTempXEqualToTempY(TempDescriptor x,
 269                                            TempDescriptor y,
 270                                            TypeDescriptor type) {
 271
 272     LabelNode lnX = getLabelNodeFromTemp(x);
 273     LabelNode lnY = getLabelNodeFromTemp(y);
 274
 275     clearReferenceEdgesFrom(lnX, null, null, true);
 276
 277     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 278     while( itrYhrn.hasNext() ) {
 279       ReferenceEdge  edgeY      = itrYhrn.next();
 280       HeapRegionNode referencee = edgeY.getDst();
 281       ReferenceEdge  edgeNew    = edgeY.copy();
 282       edgeNew.setSrc( lnX );
 283       edgeNew.setType( type );
 284       edgeNew.setField( null );
 285
 286       addReferenceEdge(lnX, referencee, edgeNew);
 287     }
 288   }
 289
 290
 291   public void assignTempXEqualToTempYFieldF(TempDescriptor x,
 292                                             TempDescriptor y,
 293                                             FieldDescriptor f) {
 294     LabelNode lnX = getLabelNodeFromTemp(x);
 295     LabelNode lnY = getLabelNodeFromTemp(y);
 296
 297     clearReferenceEdgesFrom(lnX, null, null, true);
 298
 299     Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 300     while( itrYhrn.hasNext() ) {
 301       ReferenceEdge edgeY = itrYhrn.next();
 302       HeapRegionNode hrnY  = edgeY.getDst();
 303       ReachabilitySet betaY = edgeY.getBeta();
 304
 305       Iterator<ReferenceEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 306       while( itrHrnFhrn.hasNext() ) {
 307         ReferenceEdge edgeHrn = itrHrnFhrn.next();
 308         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 309         ReachabilitySet betaHrn = edgeHrn.getBeta();
 310
 311         if( edgeHrn.getType() == null ||
 312             edgeHrn.getType().equals( f.getType() ) ) {
 313
 314           ReferenceEdge edgeNew = new ReferenceEdge(lnX,
 315                                                     hrnHrn,
 316                                                     f.getType(),
 317                                                     null,
 318                                                     false,
 319                                                     betaY.intersection(betaHrn) );
 320
 321           addReferenceEdge(lnX, hrnHrn, edgeNew);
 322         }
 323       }
 324     }
 325   }
 326
 327
 328   public void assignTempXFieldFEqualToTempY(TempDescriptor x,
 329                                             FieldDescriptor f,
 330                                             TempDescriptor y) {
 331     LabelNode lnX = getLabelNodeFromTemp(x);
 332     LabelNode lnY = getLabelNodeFromTemp(y);
 333
 334     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 335     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
 336
 337
 338     // first look for possible strong updates and remove those edges
 339     boolean strongUpdate = false;
 340
 341     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 342     while( itrXhrn.hasNext() ) {
 343       ReferenceEdge edgeX = itrXhrn.next();
 344       HeapRegionNode hrnX = edgeX.getDst();
 345
 346       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 347       while( itrYhrn.hasNext() ) {
 348         ReferenceEdge edgeY = itrYhrn.next();
 349         HeapRegionNode hrnY = edgeY.getDst();
 350
 351         // we can do a strong update here if one of two cases holds
 352         if( f != null &&
 353             hrnX.isSingleObject() &&
 354             (   (hrnX.getNumReferencers() == 1) ||
 355                 ( lnX.getNumReferencees() == 1)
 356             )
 357           ) {
 358           strongUpdate = true;
 359           clearReferenceEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
 360         }
 361       }
 362     }
 363
 364     // then do all token propagation
 365     itrXhrn = lnX.iteratorToReferencees();
 366     while( itrXhrn.hasNext() ) {
 367       ReferenceEdge edgeX = itrXhrn.next();
 368       HeapRegionNode hrnX = edgeX.getDst();
 369       ReachabilitySet betaX = edgeX.getBeta();
 370
 371       ReachabilitySet R = hrnX.getAlpha().intersection(edgeX.getBeta() );
 372
 373       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 374       while( itrYhrn.hasNext() ) {
 375         ReferenceEdge edgeY = itrYhrn.next();
 376         HeapRegionNode hrnY = edgeY.getDst();
 377         ReachabilitySet O = edgeY.getBeta();
 378
 379
 380         // propagate tokens over nodes starting from hrnSrc, and it will
 381         // take care of propagating back up edges from any touched nodes
 382         ChangeTupleSet Cy = O.unionUpArityToChangeSet(R);
 383         propagateTokensOverNodes(hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta);
 384
 385
 386         // then propagate back just up the edges from hrn
 387         ChangeTupleSet Cx = R.unionUpArityToChangeSet(O);
 388
 389
 390         HashSet<ReferenceEdge> todoEdges = new HashSet<ReferenceEdge>();
 391
 392         Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
 393           new Hashtable<ReferenceEdge, ChangeTupleSet>();
 394
 395         Iterator<ReferenceEdge> referItr = hrnX.iteratorToReferencers();
 396         while( referItr.hasNext() ) {
 397           ReferenceEdge edgeUpstream = referItr.next();
 398           todoEdges.add(edgeUpstream);
 399           edgePlannedChanges.put(edgeUpstream, Cx);
 400         }
 401
 402         propagateTokensOverEdges(todoEdges,
 403                                  edgePlannedChanges,
 404                                  edgesWithNewBeta);
 405       }
 406     }
 407
 408
 409     // apply the updates to reachability
 410     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 411     while( nodeItr.hasNext() ) {
 412       nodeItr.next().applyAlphaNew();
 413     }
 414
 415     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
 416     while( edgeItr.hasNext() ) {
 417       edgeItr.next().applyBetaNew();
 418     }
 419
 420     // then go back through and add the new edges
 421     itrXhrn = lnX.iteratorToReferencees();
 422     while( itrXhrn.hasNext() ) {
 423       ReferenceEdge edgeX = itrXhrn.next();
 424       HeapRegionNode hrnX = edgeX.getDst();
 425
 426       Iterator<ReferenceEdge> itrYhrn = lnY.iteratorToReferencees();
 427       while( itrYhrn.hasNext() ) {
 428         ReferenceEdge edgeY = itrYhrn.next();
 429         HeapRegionNode hrnY = edgeY.getDst();
 430
 431         // prepare the new reference edge hrnX.f -> hrnY
 432         ReferenceEdge edgeNew = new ReferenceEdge(hrnX,
 433                                                   hrnY,
 434                                                   f.getType(),
 435                                                   f.getSymbol(),
 436                                                   false,
 437                                                   edgeY.getBeta().pruneBy( hrnX.getAlpha() )
 438                                                   );
 439
 440         // look to see if an edge with same field exists
 441         // and merge with it, otherwise just add the edge
 442         ReferenceEdge edgeExisting = hrnX.getReferenceTo( hrnY,
 443                                                           f.getType(),
 444                                                           f.getSymbol() );
 445
 446         if( edgeExisting != null ) {
 447           edgeExisting.setBeta(
 448                                edgeExisting.getBeta().union( edgeNew.getBeta() )
 449                               );
 450           // a new edge here cannot be reflexive, so existing will
 451           // always be also not reflexive anymore
 452           edgeExisting.setIsInitialParamReflexive( false );
 453         } else {
 454           addReferenceEdge( hrnX, hrnY, edgeNew );
 455         }
 456       }
 457     }
 458
 459     // if there was a strong update, make sure to improve
 460     // reachability with a global sweep
 461     if( strongUpdate ) {
 462       globalSweep();
 463     }
 464   }
 465
 466
 467   // the parameter model is to use a single-object heap region
 468   // for the primary parameter, and a multiple-object heap
 469   // region for the secondary objects reachable through the
 470   // primary object, if necessary
 471   public void assignTempEqualToParamAlloc( TempDescriptor td,
 472                                            boolean isTask,
 473                                            Integer paramIndex ) {
 474     assert td != null;
 475
 476     TypeDescriptor typeParam = td.getType();
 477     assert typeParam != null;
 478
 479     // either the parameter is an array or a class to be in this method
 480     assert typeParam.isArray() || typeParam.isClass();
 481
 482     // discover some info from the param type and use it below
 483     // to get parameter model as precise as we can
 484     boolean createSecondaryRegion = false;
 485     Set<FieldDescriptor> primary2primaryFields   = new HashSet<FieldDescriptor>();
 486     Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
 487
 488     // there might be an element reference for array types
 489     if( typeParam.isArray() ) {
 490       // only bother with this if the dereferenced type can
 491       // affect reachability
 492       TypeDescriptor typeDeref = typeParam.dereference();
 493       if( !typeDeref.isImmutable() || typeDeref.isArray() ) {
 494         primary2secondaryFields.add(
 495           OwnershipAnalysis.getArrayField( typeDeref )
 496                                    );
 497         createSecondaryRegion = true;
 498       }
 499     }
 500
 501     // there might be member references for class types
 502     if( typeParam.isClass() ) {
 503       ClassDescriptor cd = typeParam.getClassDesc();
 504       Iterator fieldItr = cd.getFields();
 505       while( fieldItr.hasNext() ) {
 506         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
 507         TypeDescriptor typeField = fd.getType();
 508         assert typeField != null;
 509
 510         if( !typeField.isImmutable() || typeField.isArray() ) {
 511           primary2secondaryFields.add( fd );
 512           createSecondaryRegion = true;
 513         }
 514
 515         if( typeUtil.isSuperorType( typeField, typeParam ) ) {
 516           primary2primaryFields.add( fd );
 517         }
 518       }
 519     }
 520
 521
 522     // now build everything we need
 523     LabelNode lnParam = getLabelNodeFromTemp( td );
 524     HeapRegionNode hrnPrimary = createNewHeapRegionNode( null,       // id or null to generate a new one
 525                                                          true,       // single object?
 526                                                          false,      // summary?
 527                                                          false,      // flagged?
 528                                                          true,       // is a parameter?
 529                                                          typeParam,  // type
 530                                                          null,       // allocation site
 531                                                          null,       // reachability set
 532                                                          "param"+paramIndex+" obj" );
 533
 534     // this is a non-program-accessible label that picks up beta
 535     // info to be used for fixing a caller of this method
 536     TempDescriptor tdParamQ = new TempDescriptor( td+"specialQ" );
 537     paramIndex2tdQ.put( paramIndex, tdParamQ );
 538
 539     // keep track of heap regions that were created for
 540     // parameter labels, the index of the parameter they
 541     // are for is important when resolving method calls
 542     Integer newPrimaryID = hrnPrimary.getID();
 543     assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
 544     Set<Integer> s = new HashSet<Integer>();
 545     s.add( paramIndex );
 546     idPrimary2paramIndexSet.put( newPrimaryID, s );
 547     paramIndex2idPrimary.put( paramIndex, newPrimaryID );
 548
 549     TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
 550                                            false, // multi-object
 551                                            TokenTuple.ARITY_ONE ).makeCanonical();
 552
 553     HeapRegionNode hrnSecondary = null;
 554     Integer newSecondaryID = null;
 555     TokenTuple ttSecondary = null;
 556     if( createSecondaryRegion ) {
 557       hrnSecondary = createNewHeapRegionNode( null,  // id or null to generate a new one
 558                                               false, // single object?
 559                                               false, // summary?
 560                                               false, // flagged?
 561                                               true,  // is a parameter?
 562                                               null,  // type
 563                                               null,  // allocation site
 564                                               null,  // reachability set
 565                                               "param"+paramIndex+" reachable" );
 566
 567       newSecondaryID = hrnSecondary.getID();
 568       assert !idSecondary2paramIndexSet.containsKey( newSecondaryID );
 569       Set<Integer> s2 = new HashSet<Integer>();
 570       s2.add( paramIndex );
 571       idSecondary2paramIndexSet.put( newSecondaryID, s2 );
 572       paramIndex2idSecondary.put( paramIndex, newSecondaryID );
 573
 574       ttSecondary = new TokenTuple( newSecondaryID,
 575                                     true, // multi-object
 576                                     TokenTuple.ARITY_ONE ).makeCanonical();
 577     }
 578
 579     // use a beta that has everything and put it all over the
 580     // parameter model, then use a global sweep later to fix
 581     // it up, since parameters can have different shapes
 582     TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
 583     ReachabilitySet betaSoup;
 584     if( createSecondaryRegion ) {
 585       TokenTupleSet tts1 = new TokenTupleSet( ttSecondary ).makeCanonical();
 586       TokenTupleSet tts2 = new TokenTupleSet( ttPrimary   ).union( ttSecondary );
 587       betaSoup = new ReachabilitySet().union( tts0 ).union( tts1 ).union( tts2 );
 588     } else {
 589       betaSoup = new ReachabilitySet().union( tts0 );
 590     }
 591
 592     LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
 593
 594     ReferenceEdge edgeFromLabel =
 595       new ReferenceEdge( lnParam,            // src
 596                          hrnPrimary,         // dst
 597                          typeParam,          // type
 598                          null,               // field
 599                          false,              // special param initial (not needed on label->node)
 600                          betaSoup );         // reachability
 601     addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
 602
 603     ReferenceEdge edgeFromLabelQ =
 604       new ReferenceEdge( lnParamQ,           // src
 605                          hrnPrimary,         // dst
 606                          typeParam,          // type
 607                          null,               // field
 608                          false,              // special param initial (not needed on label->node)
 609                          betaSoup );         // reachability
 610     addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
 611
 612
 613     ReferenceEdge edgeSecondaryReflexive;
 614     if( createSecondaryRegion ) {
 615       edgeSecondaryReflexive =
 616         new ReferenceEdge( hrnSecondary,    // src
 617                            hrnSecondary,    // dst
 618                            null,            // match all types
 619                            null,            // match all fields
 620                            true,            // special param initial
 621                            betaSoup );      // reachability
 622       addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive );
 623
 624       ReferenceEdge edgeSecondary2Primary =
 625         new ReferenceEdge( hrnSecondary,    // src
 626                            hrnPrimary,      // dst
 627                            null,            // match all types
 628                            null,            // match all fields
 629                            true,            // special param initial
 630                            betaSoup );      // reachability
 631       addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary );
 632     }
 633
 634     Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
 635     while( fieldItr.hasNext() ) {
 636       FieldDescriptor fd = fieldItr.next();
 637
 638       ReferenceEdge edgePrimaryReflexive =
 639         new ReferenceEdge( hrnPrimary,     // src
 640                            hrnPrimary,     // dst
 641                            fd.getType(),   // type
 642                            fd.getSymbol(), // field
 643                            true,           // special param initial
 644                            betaSoup );     // reachability
 645       addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
 646     }
 647
 648     fieldItr = primary2secondaryFields.iterator();
 649     while( fieldItr.hasNext() ) {
 650       FieldDescriptor fd = fieldItr.next();
 651
 652       ReferenceEdge edgePrimary2Secondary =
 653         new ReferenceEdge( hrnPrimary,     // src
 654                            hrnSecondary,   // dst
 655                            fd.getType(),   // type
 656                            fd.getSymbol(), // field
 657                            true,           // special param initial
 658                            betaSoup );     // reachability
 659       addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary );
 660     }
 661   }
 662
 663   public void makeAliasedParamHeapRegionNode( TempDescriptor td ) {
 664     assert td != null;
 665
 666     LabelNode lnParam = getLabelNodeFromTemp( td );
 667     HeapRegionNode hrn = createNewHeapRegionNode( null,  // id or null to generate a new one
 668                                                   false, // single object?
 669                                                   false, // summary?
 670                                                   false, // flagged?
 671                                                   true,  // is a parameter?
 672                                                   null,  // type
 673                                                   null,  // allocation site
 674                                                   null,  // reachability set
 675                                                   "aliasedParams" );
 676
 677     ReachabilitySet beta = new ReachabilitySet( new TokenTuple( hrn.getID(),
 678                                                                 true,
 679                                                                 TokenTuple.ARITY_ONE).makeCanonical()
 680                                                 ).makeCanonical();
 681
 682     ReferenceEdge edgeFromLabel =
 683       new ReferenceEdge( lnParam, hrn, null, null, false, beta );
 684
 685     ReferenceEdge edgeReflexive =
 686       new ReferenceEdge( hrn,     hrn, null, null, true,  beta );
 687
 688     addReferenceEdge( lnParam, hrn, edgeFromLabel );
 689     addReferenceEdge( hrn,     hrn, edgeReflexive );
 690   }
 691
 692   public void assignTempEqualToAliasedParam(TempDescriptor tdParam,
 693                                             TempDescriptor tdAliased,
 694                                             Integer        paramIndex,
 695                                             boolean        aliasedPiIsSuperOfPj ) {
 696     assert tdParam   != null;
 697     assert tdAliased != null;
 698
 699     TypeDescriptor typeParam = tdParam.getType();
 700     assert typeParam != null;
 701
 702     LabelNode lnParam   = getLabelNodeFromTemp(tdParam);
 703     LabelNode lnAliased = getLabelNodeFromTemp(tdAliased);
 704
 705     // this is a non-program-accessible label that picks up beta
 706     // info to be used for fixing a caller of this method
 707     TempDescriptor tdParamQ = new TempDescriptor( tdParam+"specialQ" );
 708     paramIndex2tdQ.put( paramIndex, tdParamQ );
 709
 710     LabelNode lnParamQ = getLabelNodeFromTemp( tdParamQ );
 711
 712     // the lnAliased should always only reference one node, and that
 713     // heap region node is the aliased param blob
 714     assert lnAliased.getNumReferencees() == 1;
 715     HeapRegionNode hrnAliasBlob = lnAliased.iteratorToReferencees().next().getDst();
 716     Integer idAliased = hrnAliasBlob.getID();
 717
 718     TokenTuple ttAliased = new TokenTuple( idAliased,
 719                                            true, // multi-object
 720                                            TokenTuple.ARITY_ONE ).makeCanonical();
 721
 722     if( aliasedPiIsSuperOfPj ) {
 723       // we point parameter labels directly at the alias blob
 724       // and just have to live with bad precision
 725       Set<Integer> s = idPrimary2paramIndexSet.get( idAliased );
 726       if( s == null ) {
 727         s = new HashSet<Integer>();
 728       }
 729       s.add( paramIndex );
 730       idPrimary2paramIndexSet.put( idAliased, s );
 731       paramIndex2idPrimary.put( paramIndex, idAliased );
 732
 733       ReachabilitySet beta = new ReachabilitySet( ttAliased ).makeCanonical();
 734
 735       ReferenceEdge edgeFromLabel =
 736         new ReferenceEdge( lnParam,  hrnAliasBlob, typeParam, null, false, beta );
 737
 738       ReferenceEdge edgeFromLabelQ =
 739         new ReferenceEdge( lnParamQ, hrnAliasBlob, typeParam, null, false, beta );
 740
 741       addReferenceEdge( lnParam,  hrnAliasBlob, edgeFromLabel  );
 742       addReferenceEdge( lnParamQ, hrnAliasBlob, edgeFromLabelQ );
 743
 744       return;
 745     }
 746
 747     // otherwise there is no problem with bringing out each
 748     // parameter's primary object with the necessary edges
 749     Set<FieldDescriptor> primary2primaryFields   = new HashSet<FieldDescriptor>();
 750     Set<FieldDescriptor> primary2secondaryFields = new HashSet<FieldDescriptor>();
 751
 752     // there might be an element reference for array types
 753     if( typeParam.isArray() ) {
 754       // only bother with this if the dereferenced type can
 755       // affect reachability
 756       TypeDescriptor typeDeref = typeParam.dereference();
 757
 758       // for this parameter to be aliased the following must be true
 759       assert !typeDeref.isImmutable() || typeDeref.isArray();
 760
 761       primary2secondaryFields.add(
 762         OwnershipAnalysis.getArrayField( typeDeref )
 763                                  );
 764     }
 765
 766     // there might be member references for class types
 767     if( typeParam.isClass() ) {
 768       ClassDescriptor cd = typeParam.getClassDesc();
 769       Iterator fieldItr = cd.getFields();
 770       while( fieldItr.hasNext() ) {
 771         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
 772         TypeDescriptor typeField = fd.getType();
 773         assert typeField != null;
 774
 775         if( !typeField.isImmutable() || typeField.isArray() ) {
 776           primary2secondaryFields.add( fd );
 777         }
 778
 779         if( typeUtil.isSuperorType( typeField, typeParam ) ) {
 780           primary2primaryFields.add( fd );
 781         }
 782       }
 783     }
 784
 785     // for aliased parameters with separate primary objects,
 786     // there must be at least one edge into the blob
 787     assert primary2secondaryFields.size() > 0;
 788
 789     HeapRegionNode hrnPrimary = createNewHeapRegionNode( null,      // id or null to generate a new one
 790                                                          true,      // single object?
 791                                                          false,     // summary?
 792                                                          false,     // flagged?
 793                                                          true,      // is a parameter?
 794                                                          typeParam, // type
 795                                                          null,      // allocation site
 796                                                          null,      // reachability set
 797                                                          "param"+paramIndex+" obj" );
 798
 799     Integer newPrimaryID = hrnPrimary.getID();
 800     assert !idPrimary2paramIndexSet.containsKey( newPrimaryID );
 801     Set<Integer> s1 = new HashSet<Integer>();
 802     s1.add( paramIndex );
 803     idPrimary2paramIndexSet.put( newPrimaryID, s1 );
 804     paramIndex2idPrimary.put( paramIndex, newPrimaryID );
 805
 806     Set<Integer> s2 = idSecondary2paramIndexSet.get( idAliased );
 807     if( s2 == null ) {
 808       s2 = new HashSet<Integer>();
 809     }
 810     s2.add( paramIndex );
 811     idSecondary2paramIndexSet.put( idAliased, s2 );
 812     paramIndex2idSecondary.put( paramIndex, idAliased );
 813
 814
 815     TokenTuple ttPrimary = new TokenTuple( newPrimaryID,
 816                                            false, // multi-object
 817                                            TokenTuple.ARITY_ONE ).makeCanonical();
 818
 819     TokenTupleSet tts0 = new TokenTupleSet( ttPrimary ).makeCanonical();
 820     TokenTupleSet tts1 = new TokenTupleSet( ttAliased ).makeCanonical();
 821     TokenTupleSet tts2 = new TokenTupleSet( ttPrimary ).union( ttAliased );
 822     ReachabilitySet betaSoup = new ReachabilitySet().union( tts0 ).union( tts1 ).union( tts2 );
 823
 824
 825     ReferenceEdge edgeFromLabel =
 826       new ReferenceEdge( lnParam,            // src
 827                          hrnPrimary,         // dst
 828                          typeParam,          // type
 829                          null,               // field
 830                          false,              // special param initial (not needed on label->node)
 831                          betaSoup );         // reachability
 832     addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel );
 833
 834     ReferenceEdge edgeFromLabelQ =
 835       new ReferenceEdge( lnParamQ,           // src
 836                          hrnPrimary,         // dst
 837                          typeParam,          // type
 838                          null,               // field
 839                          false,              // special param initial (not needed on label->node)
 840                          betaSoup );         // reachability
 841     addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ );
 842
 843     ReferenceEdge edgeAliased2Primary =
 844       new ReferenceEdge( hrnAliasBlob,    // src
 845                          hrnPrimary,      // dst
 846                          null,            // match all types
 847                          null,            // match all fields
 848                          true,            // special param initial
 849                          betaSoup );      // reachability
 850     addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary );
 851
 852     Iterator<FieldDescriptor> fieldItr = primary2primaryFields.iterator();
 853     while( fieldItr.hasNext() ) {
 854       FieldDescriptor fd = fieldItr.next();
 855
 856       ReferenceEdge edgePrimaryReflexive =
 857         new ReferenceEdge( hrnPrimary,     // src
 858                            hrnPrimary,     // dst
 859                            fd.getType(),   // type
 860                            fd.getSymbol(), // field
 861                            true,           // special param initial
 862                            betaSoup );     // reachability
 863       addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive );
 864     }
 865
 866     fieldItr = primary2secondaryFields.iterator();
 867     while( fieldItr.hasNext() ) {
 868       FieldDescriptor fd = fieldItr.next();
 869
 870       ReferenceEdge edgePrimary2Secondary =
 871         new ReferenceEdge( hrnPrimary,     // src
 872                            hrnAliasBlob,   // dst
 873                            fd.getType(),   // type
 874                            fd.getSymbol(), // field
 875                            true,           // special param initial
 876                            betaSoup );     // reachability
 877       addReferenceEdge( hrnPrimary, hrnAliasBlob, edgePrimary2Secondary );
 878     }
 879   }
 880
 881
 882
 883   public void assignReturnEqualToTemp(TempDescriptor x) {
 884
 885     LabelNode lnR = getLabelNodeFromTemp(tdReturn);
 886     LabelNode lnX = getLabelNodeFromTemp(x);
 887
 888     clearReferenceEdgesFrom(lnR, null, null, true);
 889
 890     Iterator<ReferenceEdge> itrXhrn = lnX.iteratorToReferencees();
 891     while( itrXhrn.hasNext() ) {
 892       ReferenceEdge edgeX       = itrXhrn.next();
 893       HeapRegionNode referencee = edgeX.getDst();
 894       ReferenceEdge edgeNew    = edgeX.copy();
 895       edgeNew.setSrc(lnR);
 896
 897       addReferenceEdge(lnR, referencee, edgeNew);
 898     }
 899   }
 900
 901
 902   public void assignTempEqualToNewAlloc(TempDescriptor x,
 903                                         AllocationSite as) {
 904     assert x  != null;
 905     assert as != null;
 906
 907     age(as);
 908
 909     // after the age operation the newest (or zero-ith oldest)
 910     // node associated with the allocation site should have
 911     // no references to it as if it were a newly allocated
 912     // heap region, so make a reference to it to complete
 913     // this operation
 914
 915     Integer idNewest  = as.getIthOldest(0);
 916     HeapRegionNode hrnNewest = id2hrn.get(idNewest);
 917     assert hrnNewest != null;
 918
 919     LabelNode lnX = getLabelNodeFromTemp(x);
 920     clearReferenceEdgesFrom(lnX, null, null, true);
 921
 922     ReferenceEdge edgeNew =
 923       new ReferenceEdge(lnX, hrnNewest, null, null, false, hrnNewest.getAlpha() );
 924
 925     addReferenceEdge(lnX, hrnNewest, edgeNew);
 926   }
 927
 928
 929   // use the allocation site (unique to entire analysis) to
 930   // locate the heap region nodes in this ownership graph
 931   // that should be aged.  The process models the allocation
 932   // of new objects and collects all the oldest allocations
 933   // in a summary node to allow for a finite analysis
 934   //
 935   // There is an additional property of this method.  After
 936   // running it on a particular ownership graph (many graphs
 937   // may have heap regions related to the same allocation site)
 938   // the heap region node objects in this ownership graph will be
 939   // allocated.  Therefore, after aging a graph for an allocation
 940   // site, attempts to retrieve the heap region nodes using the
 941   // integer id's contained in the allocation site should always
 942   // return non-null heap regions.
 943   public void age(AllocationSite as) {
 944
 945     // aging adds this allocation site to the graph's
 946     // list of sites that exist in the graph, or does
 947     // nothing if the site is already in the list
 948     allocationSites.add(as);
 949
 950     // get the summary node for the allocation site in the context
 951     // of this particular ownership graph
 952     HeapRegionNode hrnSummary = getSummaryNode(as);
 953
 954     // merge oldest node into summary
 955     Integer idK  = as.getOldest();
 956     HeapRegionNode hrnK = id2hrn.get(idK);
 957     mergeIntoSummary(hrnK, hrnSummary);
 958
 959     // move down the line of heap region nodes
 960     // clobbering the ith and transferring all references
 961     // to and from i-1 to node i.  Note that this clobbers
 962     // the oldest node (hrnK) that was just merged into
 963     // the summary
 964     for( int i = allocationDepth - 1; i > 0; --i ) {
 965
 966       // move references from the i-1 oldest to the ith oldest
 967       Integer idIth     = as.getIthOldest(i);
 968       HeapRegionNode hrnI      = id2hrn.get(idIth);
 969       Integer idImin1th = as.getIthOldest(i - 1);
 970       HeapRegionNode hrnImin1  = id2hrn.get(idImin1th);
 971
 972       transferOnto(hrnImin1, hrnI);
 973     }
 974
 975     // as stated above, the newest node should have had its
 976     // references moved over to the second oldest, so we wipe newest
 977     // in preparation for being the new object to assign something to
 978     Integer id0th = as.getIthOldest(0);
 979     HeapRegionNode hrn0  = id2hrn.get(id0th);
 980     assert hrn0 != null;
 981
 982     // clear all references in and out of newest node
 983     clearReferenceEdgesFrom(hrn0, null, null, true);
 984     clearReferenceEdgesTo(hrn0, null, null, true);
 985
 986
 987     // now tokens in reachability sets need to "age" also
 988     Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
 989     while( itrAllLabelNodes.hasNext() ) {
 990       Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
 991       LabelNode ln = (LabelNode) me.getValue();
 992
 993       Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
 994       while( itrEdges.hasNext() ) {
 995         ageTokens(as, itrEdges.next() );
 996       }
 997     }
 998
 999     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
1000     while( itrAllHRNodes.hasNext() ) {
1001       Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
1002       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
1003
1004       ageTokens(as, hrnToAge);
1005
1006       Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
1007       while( itrEdges.hasNext() ) {
1008         ageTokens(as, itrEdges.next() );
1009       }
1010     }
1011
1012
1013     // after tokens have been aged, reset newest node's reachability
1014     if( hrn0.isFlagged() ) {
1015       hrn0.setAlpha(new ReachabilitySet(
1016                       new TokenTupleSet(
1017                         new TokenTuple(hrn0).makeCanonical()
1018                         ).makeCanonical()
1019                       ).makeCanonical()
1020                     );
1021     } else {
1022       hrn0.setAlpha(new ReachabilitySet(
1023                       new TokenTupleSet().makeCanonical()
1024                       ).makeCanonical()
1025                     );
1026     }
1027   }
1028
1029
1030   protected HeapRegionNode getSummaryNode(AllocationSite as) {
1031
1032     Integer idSummary  = as.getSummary();
1033     HeapRegionNode hrnSummary = id2hrn.get(idSummary);
1034
1035     // If this is null then we haven't touched this allocation site
1036     // in the context of the current ownership graph, so allocate
1037     // heap region nodes appropriate for the entire allocation site.
1038     // This should only happen once per ownership graph per allocation site,
1039     // and a particular integer id can be used to locate the heap region
1040     // in different ownership graphs that represents the same part of an
1041     // allocation site.
1042     if( hrnSummary == null ) {
1043
1044       boolean hasFlags = false;
1045       if( as.getType().isClass() ) {
1046         hasFlags = as.getType().getClassDesc().hasFlags();
1047       }
1048
1049       hrnSummary = createNewHeapRegionNode(idSummary,    // id or null to generate a new one
1050                                            false,        // single object?
1051                                            true,         // summary?
1052                                            hasFlags,     // flagged?
1053                                            false,        // is a parameter?
1054                                            as.getType(), // type
1055                                            as,           // allocation site
1056                                            null,         // reachability set
1057                                            as.toStringForDOT() + "\\nsummary");
1058
1059       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1060         Integer idIth = as.getIthOldest(i);
1061         assert !id2hrn.containsKey(idIth);
1062         createNewHeapRegionNode(idIth,        // id or null to generate a new one
1063                                 true,         // single object?
1064                                 false,        // summary?
1065                                 hasFlags,     // flagged?
1066                                 false,        // is a parameter?
1067                                 as.getType(), // type
1068                                 as,           // allocation site
1069                                 null,         // reachability set
1070                                 as.toStringForDOT() + "\\n" + i + " oldest");
1071       }
1072     }
1073
1074     return hrnSummary;
1075   }
1076
1077
1078   protected HeapRegionNode getShadowSummaryNode(AllocationSite as) {
1079
1080     Integer idShadowSummary  = as.getSummaryShadow();
1081     HeapRegionNode hrnShadowSummary = id2hrn.get(idShadowSummary);
1082
1083     if( hrnShadowSummary == null ) {
1084
1085       boolean hasFlags = false;
1086       if( as.getType().isClass() ) {
1087         hasFlags = as.getType().getClassDesc().hasFlags();
1088       }
1089
1090       hrnShadowSummary = createNewHeapRegionNode(idShadowSummary, // id or null to generate a new one
1091                                                  false,           // single object?
1092                                                  true,            // summary?
1093                                                  hasFlags,        // flagged?
1094                                                  false,           // is a parameter?
1095                                                  as.getType(),    // type
1096                                                  as,              // allocation site
1097                                                  null,            // reachability set
1098                                                  as + "\\n" + as.getType() + "\\nshadowSum");
1099
1100       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
1101         Integer idShadowIth = as.getIthOldestShadow(i);
1102         assert !id2hrn.containsKey(idShadowIth);
1103         createNewHeapRegionNode(idShadowIth,  // id or null to generate a new one
1104                                 true,         // single object?
1105                                 false,        // summary?
1106                                 hasFlags,     // flagged?
1107                                 false,        // is a parameter?
1108                                 as.getType(), // type
1109                                 as,           // allocation site
1110                                 null,         // reachability set
1111                                 as + "\\n" + as.getType() + "\\n" + i + " shadow");
1112       }
1113     }
1114
1115     return hrnShadowSummary;
1116   }
1117
1118
1119   protected void mergeIntoSummary(HeapRegionNode hrn, HeapRegionNode hrnSummary) {
1120     assert hrnSummary.isNewSummary();
1121
1122     // transfer references _from_ hrn over to hrnSummary
1123     Iterator<ReferenceEdge> itrReferencee = hrn.iteratorToReferencees();
1124     while( itrReferencee.hasNext() ) {
1125       ReferenceEdge edge       = itrReferencee.next();
1126       ReferenceEdge edgeMerged = edge.copy();
1127       edgeMerged.setSrc(hrnSummary);
1128
1129       HeapRegionNode hrnReferencee = edge.getDst();
1130       ReferenceEdge edgeSummary   = hrnSummary.getReferenceTo(hrnReferencee,
1131                                                               edge.getType(),
1132                                                               edge.getField() );
1133
1134       if( edgeSummary == null ) {
1135         // the merge is trivial, nothing to be done
1136       } else {
1137         // otherwise an edge from the referencer to hrnSummary exists already
1138         // and the edge referencer->hrn should be merged with it
1139         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1140       }
1141
1142       addReferenceEdge(hrnSummary, hrnReferencee, edgeMerged);
1143     }
1144
1145     // next transfer references _to_ hrn over to hrnSummary
1146     Iterator<ReferenceEdge> itrReferencer = hrn.iteratorToReferencers();
1147     while( itrReferencer.hasNext() ) {
1148       ReferenceEdge edge         = itrReferencer.next();
1149       ReferenceEdge edgeMerged   = edge.copy();
1150       edgeMerged.setDst(hrnSummary);
1151
1152       OwnershipNode onReferencer = edge.getSrc();
1153       ReferenceEdge edgeSummary  = onReferencer.getReferenceTo(hrnSummary,
1154                                                                edge.getType(),
1155                                                                edge.getField() );
1156
1157       if( edgeSummary == null ) {
1158         // the merge is trivial, nothing to be done
1159       } else {
1160         // otherwise an edge from the referencer to alpha_S exists already
1161         // and the edge referencer->alpha_K should be merged with it
1162         edgeMerged.setBeta(edgeMerged.getBeta().union(edgeSummary.getBeta() ) );
1163       }
1164
1165       addReferenceEdge(onReferencer, hrnSummary, edgeMerged);
1166     }
1167
1168     // then merge hrn reachability into hrnSummary
1169     hrnSummary.setAlpha(hrnSummary.getAlpha().union(hrn.getAlpha() ) );
1170   }
1171
1172
1173   protected void transferOnto(HeapRegionNode hrnA, HeapRegionNode hrnB) {
1174
1175     // clear references in and out of node b
1176     clearReferenceEdgesFrom(hrnB, null, null, true);
1177     clearReferenceEdgesTo(hrnB, null, null, true);
1178
1179     // copy each edge in and out of A to B
1180     Iterator<ReferenceEdge> itrReferencee = hrnA.iteratorToReferencees();
1181     while( itrReferencee.hasNext() ) {
1182       ReferenceEdge edge          = itrReferencee.next();
1183       HeapRegionNode hrnReferencee = edge.getDst();
1184       ReferenceEdge edgeNew       = edge.copy();
1185       edgeNew.setSrc(hrnB);
1186
1187       addReferenceEdge(hrnB, hrnReferencee, edgeNew);
1188     }
1189
1190     Iterator<ReferenceEdge> itrReferencer = hrnA.iteratorToReferencers();
1191     while( itrReferencer.hasNext() ) {
1192       ReferenceEdge edge         = itrReferencer.next();
1193       OwnershipNode onReferencer = edge.getSrc();
1194       ReferenceEdge edgeNew      = edge.copy();
1195       edgeNew.setDst(hrnB);
1196
1197       addReferenceEdge(onReferencer, hrnB, edgeNew);
1198     }
1199
1200     // replace hrnB reachability with hrnA's
1201     hrnB.setAlpha(hrnA.getAlpha() );
1202   }
1203
1204
1205   protected void ageTokens(AllocationSite as, ReferenceEdge edge) {
1206     edge.setBeta(edge.getBeta().ageTokens(as) );
1207   }
1208
1209   protected void ageTokens(AllocationSite as, HeapRegionNode hrn) {
1210     hrn.setAlpha(hrn.getAlpha().ageTokens(as) );
1211   }
1212
1213
1214
1215   protected void propagateTokensOverNodes(HeapRegionNode nPrime,
1216                                           ChangeTupleSet c0,
1217                                           HashSet<HeapRegionNode> nodesWithNewAlpha,
1218                                           HashSet<ReferenceEdge>  edgesWithNewBeta) {
1219
1220     HashSet<HeapRegionNode> todoNodes
1221       = new HashSet<HeapRegionNode>();
1222     todoNodes.add(nPrime);
1223
1224     HashSet<ReferenceEdge> todoEdges
1225       = new HashSet<ReferenceEdge>();
1226
1227     Hashtable<HeapRegionNode, ChangeTupleSet> nodePlannedChanges
1228       = new Hashtable<HeapRegionNode, ChangeTupleSet>();
1229     nodePlannedChanges.put(nPrime, c0);
1230
1231     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges
1232       = new Hashtable<ReferenceEdge, ChangeTupleSet>();
1233
1234     // first propagate change sets everywhere they can go
1235     while( !todoNodes.isEmpty() ) {
1236       HeapRegionNode n = todoNodes.iterator().next();
1237       ChangeTupleSet C = nodePlannedChanges.get(n);
1238
1239       Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1240       while( referItr.hasNext() ) {
1241         ReferenceEdge edge = referItr.next();
1242         todoEdges.add(edge);
1243
1244         if( !edgePlannedChanges.containsKey(edge) ) {
1245           edgePlannedChanges.put(edge, new ChangeTupleSet().makeCanonical() );
1246         }
1247
1248         edgePlannedChanges.put(edge, edgePlannedChanges.get(edge).union(C) );
1249       }
1250
1251       Iterator<ReferenceEdge> refeeItr = n.iteratorToReferencees();
1252       while( refeeItr.hasNext() ) {
1253         ReferenceEdge edgeF = refeeItr.next();
1254         HeapRegionNode m     = edgeF.getDst();
1255
1256         ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1257
1258         Iterator<ChangeTuple> itrCprime = C.iterator();
1259         while( itrCprime.hasNext() ) {
1260           ChangeTuple c = itrCprime.next();
1261           if( edgeF.getBeta().contains( c.getSetToMatch() ) ) {
1262             changesToPass = changesToPass.union(c);
1263           }
1264         }
1265
1266         if( !changesToPass.isEmpty() ) {
1267           if( !nodePlannedChanges.containsKey(m) ) {
1268             nodePlannedChanges.put(m, new ChangeTupleSet().makeCanonical() );
1269           }
1270
1271           ChangeTupleSet currentChanges = nodePlannedChanges.get(m);
1272
1273           if( !changesToPass.isSubset(currentChanges) ) {
1274
1275             nodePlannedChanges.put(m, currentChanges.union(changesToPass) );
1276             todoNodes.add(m);
1277           }
1278         }
1279       }
1280
1281       todoNodes.remove(n);
1282     }
1283
1284     // then apply all of the changes for each node at once
1285     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1286     while( itrMap.hasNext() ) {
1287       Map.Entry      me = (Map.Entry)      itrMap.next();
1288       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1289       ChangeTupleSet C  = (ChangeTupleSet) me.getValue();
1290
1291       n.setAlphaNew( n.getAlpha().applyChangeSet( C, false ) );
1292       nodesWithNewAlpha.add( n );
1293     }
1294
1295     propagateTokensOverEdges(todoEdges, edgePlannedChanges, edgesWithNewBeta);
1296   }
1297
1298
1299   protected void propagateTokensOverEdges(
1300     HashSet<ReferenceEdge>                   todoEdges,
1301     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges,
1302     HashSet<ReferenceEdge>                   edgesWithNewBeta) {
1303
1304     // first propagate all change tuples everywhere they can go
1305     while( !todoEdges.isEmpty() ) {
1306       ReferenceEdge edgeE = todoEdges.iterator().next();
1307       todoEdges.remove(edgeE);
1308
1309       if( !edgePlannedChanges.containsKey(edgeE) ) {
1310         edgePlannedChanges.put(edgeE, new ChangeTupleSet().makeCanonical() );
1311       }
1312
1313       ChangeTupleSet C = edgePlannedChanges.get(edgeE);
1314
1315       ChangeTupleSet changesToPass = new ChangeTupleSet().makeCanonical();
1316
1317
1318       Iterator<ChangeTuple> itrC = C.iterator();
1319       while( itrC.hasNext() ) {
1320         ChangeTuple c = itrC.next();
1321         if( edgeE.getBeta().contains( c.getSetToMatch() ) ) {
1322           changesToPass = changesToPass.union(c);
1323         }
1324       }
1325
1326       OwnershipNode onSrc = edgeE.getSrc();
1327
1328       if( !changesToPass.isEmpty() && onSrc instanceof HeapRegionNode ) {
1329         HeapRegionNode n = (HeapRegionNode) onSrc;
1330
1331         Iterator<ReferenceEdge> referItr = n.iteratorToReferencers();
1332         while( referItr.hasNext() ) {
1333           ReferenceEdge edgeF = referItr.next();
1334
1335           if( !edgePlannedChanges.containsKey(edgeF) ) {
1336             edgePlannedChanges.put(edgeF, new ChangeTupleSet().makeCanonical() );
1337           }
1338
1339           ChangeTupleSet currentChanges = edgePlannedChanges.get(edgeF);
1340
1341           if( !changesToPass.isSubset(currentChanges) ) {
1342             todoEdges.add(edgeF);
1343             edgePlannedChanges.put(edgeF, currentChanges.union(changesToPass) );
1344           }
1345         }
1346       }
1347     }
1348
1349     // then apply all of the changes for each edge at once
1350     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1351     while( itrMap.hasNext() ) {
1352       Map.Entry      me = (Map.Entry)      itrMap.next();
1353       ReferenceEdge  e  = (ReferenceEdge)  me.getKey();
1354       ChangeTupleSet C  = (ChangeTupleSet) me.getValue();
1355
1356       e.setBetaNew( e.getBeta().applyChangeSet( C, true ) );
1357       edgesWithNewBeta.add( e );
1358     }
1359   }
1360
1361
1362   public Set<Integer> calculateAliasedParamSet(FlatCall fc,
1363                                                boolean isStatic,
1364                                                FlatMethod fm) {
1365
1366     Hashtable<Integer, LabelNode> paramIndex2ln =
1367       new Hashtable<Integer, LabelNode>();
1368
1369     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1370       new Hashtable<Integer, HashSet<HeapRegionNode> >();
1371
1372     for( int i = 0; i < fm.numParameters(); ++i ) {
1373       Integer paramIndex = new Integer(i);
1374
1375       // now depending on whether the callee is static or not
1376       // we need to account for a "this" argument in order to
1377       // find the matching argument in the caller context
1378       TempDescriptor argTemp_i;
1379       if( isStatic ) {
1380         argTemp_i = fc.getArg(paramIndex);
1381       } else {
1382         if( paramIndex.equals(0) ) {
1383           argTemp_i = fc.getThis();
1384         } else {
1385           argTemp_i = fc.getArg(paramIndex - 1);
1386         }
1387       }
1388
1389       // in non-static methods there is a "this" pointer
1390       // that should be taken into account
1391       if( isStatic ) {
1392         assert fc.numArgs()     == fm.numParameters();
1393       } else {
1394         assert fc.numArgs() + 1 == fm.numParameters();
1395       }
1396
1397       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1398       paramIndex2ln.put(paramIndex, argLabel_i);
1399     }
1400
1401     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1402     while( lnArgItr.hasNext() ) {
1403       Map.Entry me      = (Map.Entry)lnArgItr.next();
1404       Integer index   = (Integer)   me.getKey();
1405       LabelNode lnArg_i = (LabelNode) me.getValue();
1406
1407       // rewrite alpha for the nodes reachable from argument label i
1408       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1409       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1410
1411       // to find all reachable nodes, start with label referencees
1412       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1413       while( edgeArgItr.hasNext() ) {
1414         ReferenceEdge edge = edgeArgItr.next();
1415         todoNodes.add(edge.getDst() );
1416       }
1417
1418       // then follow links until all reachable nodes have been found
1419       while( !todoNodes.isEmpty() ) {
1420         HeapRegionNode hrn = todoNodes.iterator().next();
1421         todoNodes.remove(hrn);
1422         reachableNodes.add(hrn);
1423
1424         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1425         while( edgeItr.hasNext() ) {
1426           ReferenceEdge edge = edgeItr.next();
1427
1428           if( !reachableNodes.contains(edge.getDst() ) ) {
1429             todoNodes.add(edge.getDst() );
1430           }
1431         }
1432       }
1433
1434       // save for later
1435       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1436     }
1437
1438     Set<Integer> aliasedIndices = new HashSet<Integer>();
1439
1440     // check for arguments that are aliased
1441     for( int i = 0; i < fm.numParameters(); ++i ) {
1442       for( int j = 0; j < i; ++j ) {
1443         HashSet<HeapRegionNode> s1 = paramIndex2reachableCallerNodes.get( i );
1444         HashSet<HeapRegionNode> s2 = paramIndex2reachableCallerNodes.get( j );
1445
1446         Set<HeapRegionNode> intersection = new HashSet<HeapRegionNode>(s1);
1447         intersection.retainAll(s2);
1448
1449         if( !intersection.isEmpty() ) {
1450           aliasedIndices.add( new Integer( i ) );
1451           aliasedIndices.add( new Integer( j ) );
1452         }
1453       }
1454     }
1455
1456     return aliasedIndices;
1457   }
1458
1459
1460   public void resolveMethodCall(FlatCall fc,
1461                                 boolean isStatic,
1462                                 FlatMethod fm,
1463                                 OwnershipGraph ogCallee,
1464                                 MethodContext mc // this is only included for identifying caller while debugging
1465                                 ) {
1466     /*
1467     String debugCaller = "foo";
1468     String debugCallee = "bar";
1469
1470     if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
1471         fm.getMethod().getSymbol().equals( debugCallee ) ) {
1472
1473       try {
1474         writeGraph( "debug1Before", true, true, true, false, false );
1475         ogCallee.writeGraph( "debug0Callee", true, true, true, false, false );
1476       } catch( IOException e ) {}
1477
1478       System.out.println( "  "+mc+" is calling "+fm );
1479     }
1480
1481
1482     // define rewrite rules and other structures to organize
1483     // data by parameter/argument index
1484     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteH =
1485       new Hashtable<Integer, ReachabilitySet>();
1486
1487     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteJ =
1488       new Hashtable<Integer, ReachabilitySet>();
1489
1490     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteK =
1491       new Hashtable<Integer, ReachabilitySet>();
1492
1493     Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d =
1494       new Hashtable<Integer, ReachabilitySet>();
1495
1496     Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD =
1497       new Hashtable<Integer, ReachabilitySet>();
1498
1499     // helpful structures
1500     Hashtable<TokenTuple, Integer> paramToken2paramIndex =
1501       new Hashtable<TokenTuple, Integer>();
1502
1503     Hashtable<Integer, TokenTuple> paramIndex2paramToken =
1504       new Hashtable<Integer, TokenTuple>();
1505
1506     Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex =
1507       new Hashtable<TokenTuple, Integer>();
1508
1509     Hashtable<Integer, TokenTuple> paramIndex2paramTokenPlus =
1510       new Hashtable<Integer, TokenTuple>();
1511
1512     Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex =
1513       new Hashtable<TokenTuple, Integer>();
1514
1515     Hashtable<Integer, TokenTuple> paramIndex2paramTokenStar =
1516       new Hashtable<Integer, TokenTuple>();
1517
1518     Hashtable<Integer, LabelNode> paramIndex2ln =
1519       new Hashtable<Integer, LabelNode>();
1520
1521     Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes =
1522       new Hashtable<Integer, HashSet<HeapRegionNode> >();
1523
1524
1525     // add a bogus entry with the identity rule for easy rewrite
1526     // of new callee nodes and edges, doesn't belong to any parameter
1527     Integer bogusID = new Integer(bogusParamIndexInt);
1528     Integer bogusIndex = new Integer(bogusParamIndexInt);
1529     TokenTuple bogusToken = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONE).makeCanonical();
1530     TokenTuple bogusTokenPlus = new TokenTuple(bogusID, true, TokenTuple.ARITY_ONEORMORE).makeCanonical();
1531     TokenTuple bogusTokenStar = new TokenTuple(bogusID, true, TokenTuple.ARITY_ZEROORMORE).makeCanonical();
1532     ReachabilitySet rsIdentity =
1533       new ReachabilitySet(
1534         new TokenTupleSet(bogusToken).makeCanonical()
1535         ).makeCanonical();
1536
1537     paramIndex2rewriteH.put(bogusIndex, rsIdentity);
1538     paramIndex2rewriteJ.put(bogusIndex, rsIdentity);
1539     paramToken2paramIndex.put(bogusToken, bogusIndex);
1540     paramIndex2paramToken.put(bogusIndex, bogusToken);
1541     paramTokenPlus2paramIndex.put(bogusTokenPlus, bogusIndex);
1542     paramIndex2paramTokenPlus.put(bogusIndex, bogusTokenPlus);
1543     paramTokenStar2paramIndex.put(bogusTokenStar, bogusIndex);
1544     paramIndex2paramTokenStar.put(bogusIndex, bogusTokenStar);
1545
1546     for( int i = 0; i < fm.numParameters(); ++i ) {
1547       Integer paramIndex = new Integer(i);
1548
1549       assert ogCallee.paramIndex2id.containsKey(paramIndex);
1550       Integer idParam = ogCallee.paramIndex2id.get(paramIndex);
1551
1552       assert ogCallee.id2hrn.containsKey(idParam);
1553       HeapRegionNode hrnParam = ogCallee.id2hrn.get(idParam);
1554       assert hrnParam != null;
1555       paramIndex2rewriteH.put(paramIndex,
1556                               toShadowTokens(ogCallee, hrnParam.getAlpha() )
1557                               );
1558
1559       ReferenceEdge edgeReflexive_i = hrnParam.getReferenceTo(hrnParam, null, null);
1560       assert edgeReflexive_i != null;
1561       paramIndex2rewriteJ.put(paramIndex,
1562                               toShadowTokens(ogCallee, edgeReflexive_i.getBeta() )
1563                               );
1564
1565       TempDescriptor tdParamQ = ogCallee.paramIndex2tdQ.get(paramIndex);
1566       assert tdParamQ != null;
1567       LabelNode lnParamQ = ogCallee.td2ln.get(tdParamQ);
1568       assert lnParamQ != null;
1569       ReferenceEdge edgeSpecialQ_i = lnParamQ.getReferenceTo(hrnParam, null, null);
1570       assert edgeSpecialQ_i != null;
1571       paramIndex2rewriteK.put(paramIndex,
1572                               toShadowTokens(ogCallee, edgeSpecialQ_i.getBeta() )
1573                               );
1574
1575       TokenTuple p_i = new TokenTuple(hrnParam.getID(),
1576                                       true,
1577                                       TokenTuple.ARITY_ONE).makeCanonical();
1578       paramToken2paramIndex.put(p_i, paramIndex);
1579       paramIndex2paramToken.put(paramIndex, p_i);
1580
1581       TokenTuple p_i_plus = new TokenTuple(hrnParam.getID(),
1582                                            true,
1583                                            TokenTuple.ARITY_ONEORMORE).makeCanonical();
1584       paramTokenPlus2paramIndex.put(p_i_plus, paramIndex);
1585       paramIndex2paramTokenPlus.put(paramIndex, p_i_plus);
1586
1587       TokenTuple p_i_star = new TokenTuple(hrnParam.getID(),
1588                                            true,
1589                                            TokenTuple.ARITY_ZEROORMORE).makeCanonical();
1590       paramTokenStar2paramIndex.put(p_i_star, paramIndex);
1591       paramIndex2paramTokenStar.put(paramIndex, p_i_star);
1592
1593       // now depending on whether the callee is static or not
1594       // we need to account for a "this" argument in order to
1595       // find the matching argument in the caller context
1596       TempDescriptor argTemp_i;
1597       if( isStatic ) {
1598         argTemp_i = fc.getArg(paramIndex);
1599       } else {
1600         if( paramIndex.equals(0) ) {
1601           argTemp_i = fc.getThis();
1602         } else {
1603           argTemp_i = fc.getArg(paramIndex - 1);
1604         }
1605       }
1606
1607       // in non-static methods there is a "this" pointer
1608       // that should be taken into account
1609       if( isStatic ) {
1610         assert fc.numArgs()     == fm.numParameters();
1611       } else {
1612         assert fc.numArgs() + 1 == fm.numParameters();
1613       }
1614
1615       LabelNode argLabel_i = getLabelNodeFromTemp(argTemp_i);
1616       paramIndex2ln.put(paramIndex, argLabel_i);
1617
1618       ReachabilitySet d_i = new ReachabilitySet().makeCanonical();
1619       Iterator<ReferenceEdge> edgeItr = argLabel_i.iteratorToReferencees();
1620       while( edgeItr.hasNext() ) {
1621         ReferenceEdge edge = edgeItr.next();
1622         d_i = d_i.union(edge.getBeta());
1623       }
1624       paramIndex2rewrite_d.put(paramIndex, d_i);
1625
1626       ReachabilitySet D_i = d_i.exhaustiveArityCombinations();
1627       paramIndex2rewriteD.put(paramIndex, D_i);
1628     }
1629
1630
1631     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
1632     HashSet<ReferenceEdge>  edgesWithNewBeta  = new HashSet<ReferenceEdge>();
1633
1634     HashSet<ReferenceEdge>  edgesReachable    = new HashSet<ReferenceEdge>();
1635     HashSet<ReferenceEdge>  edgesUpstream     = new HashSet<ReferenceEdge>();
1636
1637     Iterator lnArgItr = paramIndex2ln.entrySet().iterator();
1638     while( lnArgItr.hasNext() ) {
1639       Map.Entry me      = (Map.Entry) lnArgItr.next();
1640       Integer index     = (Integer)   me.getKey();
1641       LabelNode lnArg_i = (LabelNode) me.getValue();
1642
1643       // rewrite alpha for the nodes reachable from argument label i
1644       HashSet<HeapRegionNode> reachableNodes = new HashSet<HeapRegionNode>();
1645       HashSet<HeapRegionNode> todoNodes = new HashSet<HeapRegionNode>();
1646
1647       // to find all reachable nodes, start with label referencees
1648       Iterator<ReferenceEdge> edgeArgItr = lnArg_i.iteratorToReferencees();
1649       while( edgeArgItr.hasNext() ) {
1650         ReferenceEdge edge = edgeArgItr.next();
1651         todoNodes.add(edge.getDst() );
1652       }
1653
1654       // then follow links until all reachable nodes have been found
1655       while( !todoNodes.isEmpty() ) {
1656         HeapRegionNode hrn = todoNodes.iterator().next();
1657         todoNodes.remove(hrn);
1658         reachableNodes.add(hrn);
1659
1660         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
1661         while( edgeItr.hasNext() ) {
1662           ReferenceEdge edge = edgeItr.next();
1663
1664           if( !reachableNodes.contains(edge.getDst() ) ) {
1665             todoNodes.add(edge.getDst() );
1666           }
1667         }
1668       }
1669
1670       // save for later
1671       paramIndex2reachableCallerNodes.put(index, reachableNodes);
1672
1673       // now iterate over reachable nodes to update their alpha, and
1674       // classify edges found as "argument reachable" or "upstream"
1675       Iterator<HeapRegionNode> hrnItr = reachableNodes.iterator();
1676       while( hrnItr.hasNext() ) {
1677         HeapRegionNode hrn = hrnItr.next();
1678
1679         rewriteCallerReachability(index,
1680                                   hrn,
1681                                   null,
1682                                   paramIndex2rewriteH.get(index),
1683                                   paramIndex2rewrite_d,
1684                                   paramIndex2rewriteD,
1685                                   paramIndex2paramToken.get(index),
1686                                   paramToken2paramIndex,
1687                                   paramTokenPlus2paramIndex,
1688                                   paramTokenStar2paramIndex,
1689                                   false,
1690                                   null);
1691
1692         nodesWithNewAlpha.add(hrn);
1693
1694         // look at all incoming edges to the reachable nodes
1695         // and sort them as edges reachable from the argument
1696         // label node, or upstream edges
1697         Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencers();
1698         while( edgeItr.hasNext() ) {
1699           ReferenceEdge edge = edgeItr.next();
1700
1701           OwnershipNode on = edge.getSrc();
1702
1703           if( on instanceof LabelNode ) {
1704
1705             LabelNode ln0 = (LabelNode) on;
1706             if( ln0.equals(lnArg_i) ) {
1707               edgesReachable.add(edge);
1708             } else {
1709               edgesUpstream.add(edge);
1710             }
1711
1712           } else {
1713
1714             HeapRegionNode hrn0 = (HeapRegionNode) on;
1715             if( reachableNodes.contains(hrn0) ) {
1716               edgesReachable.add(edge);
1717             } else {
1718               edgesUpstream.add(edge);
1719             }
1720           }
1721         }
1722       }
1723
1724       // update reachable edges
1725       Iterator<ReferenceEdge> edgeReachableItr = edgesReachable.iterator();
1726       while( edgeReachableItr.hasNext() ) {
1727         ReferenceEdge edgeReachable = edgeReachableItr.next();
1728
1729         rewriteCallerReachability(index,
1730                                   null,
1731                                   edgeReachable,
1732                                   paramIndex2rewriteJ.get(index),
1733                                   paramIndex2rewrite_d,
1734                                   paramIndex2rewriteD,
1735                                   paramIndex2paramToken.get(index),
1736                                   paramToken2paramIndex,
1737                                   paramTokenPlus2paramIndex,
1738                                   paramTokenStar2paramIndex,
1739                                   false,
1740                                   null);
1741
1742         edgesWithNewBeta.add(edgeReachable);
1743       }
1744
1745       // update upstream edges
1746       Hashtable<ReferenceEdge, ChangeTupleSet> edgeUpstreamPlannedChanges =
1747         new Hashtable<ReferenceEdge, ChangeTupleSet>();
1748
1749       Iterator<ReferenceEdge> edgeUpstreamItr = edgesUpstream.iterator();
1750       while( edgeUpstreamItr.hasNext() ) {
1751         ReferenceEdge edgeUpstream = edgeUpstreamItr.next();
1752
1753         rewriteCallerReachability(index,
1754                                   null,
1755                                   edgeUpstream,
1756                                   paramIndex2rewriteK.get(index),
1757                                   paramIndex2rewrite_d,
1758                                   paramIndex2rewriteD,
1759                                   paramIndex2paramToken.get(index),
1760                                   paramToken2paramIndex,
1761                                   paramTokenPlus2paramIndex,
1762                                   paramTokenStar2paramIndex,
1763                                   true,
1764                                   edgeUpstreamPlannedChanges);
1765
1766         edgesWithNewBeta.add(edgeUpstream);
1767       }
1768
1769       propagateTokensOverEdges(edgesUpstream,
1770                                edgeUpstreamPlannedChanges,
1771                                edgesWithNewBeta);
1772     }
1773
1774
1775     // commit changes to alpha and beta
1776     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
1777     while( nodeItr.hasNext() ) {
1778       nodeItr.next().applyAlphaNew();
1779     }
1780
1781     Iterator<ReferenceEdge> edgeItr = edgesWithNewBeta.iterator();
1782     while( edgeItr.hasNext() ) {
1783       edgeItr.next().applyBetaNew();
1784     }
1785
1786
1787     // verify the existence of allocation sites and their
1788     // shadows from the callee in the context of this caller graph
1789     // then map allocated nodes of callee onto the caller shadows
1790     // of them
1791     Iterator<AllocationSite> asItr = ogCallee.allocationSites.iterator();
1792     while( asItr.hasNext() ) {
1793       AllocationSite allocSite  = asItr.next();
1794
1795       // grab the summary in the caller just to make sure
1796       // the allocation site has nodes in the caller
1797       HeapRegionNode hrnSummary = getSummaryNode(allocSite);
1798
1799       // assert that the shadow nodes have no reference edges
1800       // because they're brand new to the graph, or last time
1801       // they were used they should have been cleared of edges
1802       HeapRegionNode hrnShadowSummary = getShadowSummaryNode(allocSite);
1803       assert hrnShadowSummary.getNumReferencers() == 0;
1804       assert hrnShadowSummary.getNumReferencees() == 0;
1805
1806       // then bring g_ij onto g'_ij and rewrite
1807       HeapRegionNode hrnSummaryCallee = ogCallee.getSummaryNode(allocSite);
1808       hrnShadowSummary.setAlpha(toShadowTokens(ogCallee, hrnSummaryCallee.getAlpha() ) );
1809
1810       // shadow nodes only are touched by a rewrite one time,
1811       // so rewrite and immediately commit--and they don't belong
1812       // to a particular parameter, so use a bogus param index
1813       // that pulls a self-rewrite out of H
1814       rewriteCallerReachability(bogusIndex,
1815                                 hrnShadowSummary,
1816                                 null,
1817                                 hrnShadowSummary.getAlpha(),
1818                                 paramIndex2rewrite_d,
1819                                 paramIndex2rewriteD,
1820                                 bogusToken,
1821                                 paramToken2paramIndex,
1822                                 paramTokenPlus2paramIndex,
1823                                 paramTokenStar2paramIndex,
1824                                 false,
1825                                 null);
1826
1827       hrnShadowSummary.applyAlphaNew();
1828
1829
1830       for( int i = 0; i < allocSite.getAllocationDepth(); ++i ) {
1831         Integer idIth = allocSite.getIthOldest(i);
1832         assert id2hrn.containsKey(idIth);
1833         HeapRegionNode hrnIth = id2hrn.get(idIth);
1834
1835         Integer idShadowIth = -(allocSite.getIthOldest(i));
1836         assert id2hrn.containsKey(idShadowIth);
1837         HeapRegionNode hrnIthShadow = id2hrn.get(idShadowIth);
1838         assert hrnIthShadow.getNumReferencers() == 0;
1839         assert hrnIthShadow.getNumReferencees() == 0;
1840
1841         assert ogCallee.id2hrn.containsKey(idIth);
1842         HeapRegionNode hrnIthCallee = ogCallee.id2hrn.get(idIth);
1843         hrnIthShadow.setAlpha(toShadowTokens(ogCallee, hrnIthCallee.getAlpha() ) );
1844
1845         rewriteCallerReachability(bogusIndex,
1846                                   hrnIthShadow,
1847                                   null,
1848                                   hrnIthShadow.getAlpha(),
1849                                   paramIndex2rewrite_d,
1850                                   paramIndex2rewriteD,
1851                                   bogusToken,
1852                                   paramToken2paramIndex,
1853                                   paramTokenPlus2paramIndex,
1854                                   paramTokenStar2paramIndex,
1855                                   false,
1856                                   null);
1857
1858         hrnIthShadow.applyAlphaNew();
1859       }
1860     }
1861
1862
1863     // for every heap region->heap region edge in the
1864     // callee graph, create the matching edge or edges
1865     // in the caller graph
1866     Set sCallee = ogCallee.id2hrn.entrySet();
1867     Iterator iCallee = sCallee.iterator();
1868     while( iCallee.hasNext() ) {
1869       Map.Entry meCallee  = (Map.Entry)iCallee.next();
1870       Integer idCallee  = (Integer)        meCallee.getKey();
1871       HeapRegionNode hrnCallee = (HeapRegionNode) meCallee.getValue();
1872
1873       Iterator<ReferenceEdge> heapRegionsItrCallee = hrnCallee.iteratorToReferencees();
1874       while( heapRegionsItrCallee.hasNext() ) {
1875         ReferenceEdge edgeCallee      =  heapRegionsItrCallee.next();
1876         HeapRegionNode hrnChildCallee = edgeCallee.getDst();
1877         Integer idChildCallee         = hrnChildCallee.getID();
1878
1879         // only address this edge if it is not a special reflexive edge
1880         if( !edgeCallee.isInitialParamReflexive() ) {
1881
1882           // now we know that in the callee method's ownership graph
1883           // there is a heap region->heap region reference edge given
1884           // by heap region pointers:
1885           // hrnCallee -> heapChildCallee
1886           //
1887           // or by the ownership-graph independent ID's:
1888           // idCallee -> idChildCallee
1889
1890           // make the edge with src and dst so beta info is
1891           // calculated once, then copy it for each new edge in caller
1892           ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1893                                                                     null,
1894                                                                     edgeCallee.getType(),
1895                                                                     edgeCallee.getField(),
1896                                                                     false,
1897                                                                     toShadowTokens(ogCallee,
1898                                                                                    edgeCallee.getBeta() )
1899                                                                     );
1900           rewriteCallerReachability(bogusIndex,
1901                                     null,
1902                                     edgeNewInCallerTemplate,
1903                                     edgeNewInCallerTemplate.getBeta(),
1904                                     paramIndex2rewrite_d,
1905                                     paramIndex2rewriteD,
1906                                     bogusToken,
1907                                     paramToken2paramIndex,
1908                                     paramTokenPlus2paramIndex,
1909                                     paramTokenStar2paramIndex,
1910                                     false,
1911                                     null);
1912
1913           edgeNewInCallerTemplate.applyBetaNew();
1914
1915
1916           // So now make a set of possible source heaps in the caller graph
1917           // and a set of destination heaps in the caller graph, and make
1918           // a reference edge in the caller for every possible (src,dst) pair
1919           HashSet<HeapRegionNode> possibleCallerSrcs =
1920             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1921                                                 (HeapRegionNode) edgeCallee.getSrc(),
1922                                                 paramIndex2reachableCallerNodes);
1923
1924           HashSet<HeapRegionNode> possibleCallerDsts =
1925             getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
1926                                                 edgeCallee.getDst(),
1927                                                 paramIndex2reachableCallerNodes);
1928
1929
1930           // make every possible pair of {srcSet} -> {dstSet} edges in the caller
1931           Iterator srcItr = possibleCallerSrcs.iterator();
1932           while( srcItr.hasNext() ) {
1933             HeapRegionNode src = (HeapRegionNode) srcItr.next();
1934
1935             if( !hasMatchingField(src, edgeCallee) ) {
1936               // prune this source node possibility
1937               continue;
1938             }
1939
1940             Iterator dstItr = possibleCallerDsts.iterator();
1941             while( dstItr.hasNext() ) {
1942               HeapRegionNode dst = (HeapRegionNode) dstItr.next();
1943
1944               if( !hasMatchingType(edgeCallee, dst) ) {
1945                 // prune
1946                 continue;
1947               }
1948
1949               // otherwise the caller src and dst pair can match the edge, so make it
1950               ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
1951               edgeNewInCaller.setSrc(src);
1952               edgeNewInCaller.setDst(dst);
1953
1954               ReferenceEdge edgeExisting = src.getReferenceTo(dst,
1955                                                               edgeNewInCaller.getType(),
1956                                                               edgeNewInCaller.getField() );
1957               if( edgeExisting == null ) {
1958                 // if this edge doesn't exist in the caller, create it
1959                 addReferenceEdge(src, dst, edgeNewInCaller);
1960
1961               } else {
1962                 // if it already exists, merge with it
1963                 edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
1964               }
1965             }
1966           }
1967         }
1968       }
1969     }
1970
1971
1972     // return value may need to be assigned in caller
1973     TempDescriptor returnTemp = fc.getReturnTemp();
1974     if( returnTemp != null && !returnTemp.getType().isImmutable() ) {
1975
1976       LabelNode lnLhsCaller = getLabelNodeFromTemp(returnTemp);
1977       clearReferenceEdgesFrom(lnLhsCaller, null, null, true);
1978
1979       LabelNode lnReturnCallee = ogCallee.getLabelNodeFromTemp(tdReturn);
1980       Iterator<ReferenceEdge> edgeCalleeItr = lnReturnCallee.iteratorToReferencees();
1981       while( edgeCalleeItr.hasNext() ) {
1982         ReferenceEdge edgeCallee = edgeCalleeItr.next();
1983
1984         ReferenceEdge edgeNewInCallerTemplate = new ReferenceEdge(null,
1985                                                                   null,
1986                                                                   edgeCallee.getType(),
1987                                                                   edgeCallee.getField(),
1988                                                                   false,
1989                                                                   toShadowTokens(ogCallee,
1990                                                                                  edgeCallee.getBeta() )
1991                                                                   );
1992         rewriteCallerReachability(bogusIndex,
1993                                   null,
1994                                   edgeNewInCallerTemplate,
1995                                   edgeNewInCallerTemplate.getBeta(),
1996                                   paramIndex2rewrite_d,
1997                                   paramIndex2rewriteD,
1998                                   bogusToken,
1999                                   paramToken2paramIndex,
2000                                   paramTokenPlus2paramIndex,
2001                                   paramTokenStar2paramIndex,
2002                                   false,
2003                                   null);
2004
2005         edgeNewInCallerTemplate.applyBetaNew();
2006
2007
2008         HashSet<HeapRegionNode> assignCallerRhs =
2009           getHRNSetThatPossiblyMapToCalleeHRN(ogCallee,
2010                                               edgeCallee.getDst(),
2011                                               paramIndex2reachableCallerNodes);
2012
2013         Iterator<HeapRegionNode> itrHrn = assignCallerRhs.iterator();
2014         while( itrHrn.hasNext() ) {
2015           HeapRegionNode hrnCaller = itrHrn.next();
2016
2017           if( !hasMatchingType(edgeCallee, hrnCaller) ) {
2018             // prune
2019             continue;
2020           }
2021
2022           // otherwise caller node can match callee edge, so make it
2023           ReferenceEdge edgeNewInCaller = edgeNewInCallerTemplate.copy();
2024           edgeNewInCaller.setSrc(lnLhsCaller);
2025           edgeNewInCaller.setDst(hrnCaller);
2026
2027           ReferenceEdge edgeExisting = lnLhsCaller.getReferenceTo(hrnCaller,
2028                                                                   edgeNewInCaller.getType(),
2029                                                                   edgeNewInCaller.getField() );
2030           if( edgeExisting == null ) {
2031
2032             // if this edge doesn't exist in the caller, create it
2033             addReferenceEdge(lnLhsCaller, hrnCaller, edgeNewInCaller);
2034           } else {
2035             // if it already exists, merge with it
2036             edgeExisting.setBeta(edgeExisting.getBeta().union(edgeNewInCaller.getBeta() ) );
2037           }
2038         }
2039       }
2040     }
2041
2042
2043     // merge the shadow nodes of allocation sites back down to normal capacity
2044     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
2045     while( allocItr.hasNext() ) {
2046       AllocationSite as = allocItr.next();
2047
2048       // first age each allocation site enough times to make room for the shadow nodes
2049       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2050         age(as);
2051       }
2052
2053       // then merge the shadow summary into the normal summary
2054       HeapRegionNode hrnSummary = getSummaryNode(as);
2055       assert hrnSummary != null;
2056
2057       HeapRegionNode hrnSummaryShadow = getShadowSummaryNode(as);
2058       assert hrnSummaryShadow != null;
2059
2060       mergeIntoSummary(hrnSummaryShadow, hrnSummary);
2061
2062       // then clear off after merge
2063       clearReferenceEdgesFrom(hrnSummaryShadow, null, null, true);
2064       clearReferenceEdgesTo(hrnSummaryShadow, null, null, true);
2065       hrnSummaryShadow.setAlpha(new ReachabilitySet().makeCanonical() );
2066
2067       // then transplant shadow nodes onto the now clean normal nodes
2068       for( int i = 0; i < as.getAllocationDepth(); ++i ) {
2069
2070         Integer idIth = as.getIthOldest(i);
2071         HeapRegionNode hrnIth = id2hrn.get(idIth);
2072
2073         Integer idIthShadow = as.getIthOldestShadow(i);
2074         HeapRegionNode hrnIthShadow = id2hrn.get(idIthShadow);
2075
2076         transferOnto(hrnIthShadow, hrnIth);
2077
2078         // clear off shadow nodes after transfer
2079         clearReferenceEdgesFrom(hrnIthShadow, null, null, true);
2080         clearReferenceEdgesTo(hrnIthShadow, null, null, true);
2081         hrnIthShadow.setAlpha(new ReachabilitySet().makeCanonical() );
2082       }
2083
2084       // finally, globally change shadow tokens into normal tokens
2085       Iterator itrAllLabelNodes = td2ln.entrySet().iterator();
2086       while( itrAllLabelNodes.hasNext() ) {
2087         Map.Entry me = (Map.Entry)itrAllLabelNodes.next();
2088         LabelNode ln = (LabelNode) me.getValue();
2089
2090         Iterator<ReferenceEdge> itrEdges = ln.iteratorToReferencees();
2091         while( itrEdges.hasNext() ) {
2092           unshadowTokens(as, itrEdges.next() );
2093         }
2094       }
2095
2096       Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2097       while( itrAllHRNodes.hasNext() ) {
2098         Map.Entry me       = (Map.Entry)itrAllHRNodes.next();
2099         HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
2100
2101         unshadowTokens(as, hrnToAge);
2102
2103         Iterator<ReferenceEdge> itrEdges = hrnToAge.iteratorToReferencees();
2104         while( itrEdges.hasNext() ) {
2105           unshadowTokens(as, itrEdges.next() );
2106         }
2107       }
2108     }
2109
2110
2111     if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2112         fm.getMethod().getSymbol().equals( debugCallee ) ) {
2113       try {
2114         writeGraph( "debug2JustBeforeSweep", true, true, true, false, false );
2115       } catch( IOException e ) {}
2116     }
2117
2118
2119     // improve reachability as much as possible
2120     globalSweep();
2121
2122
2123     if( mc.getDescriptor().getSymbol().equals( debugCaller ) &&
2124         fm.getMethod().getSymbol().equals( debugCallee ) ) {
2125       try {
2126         writeGraph( "debug9endResolveCall", true, true, true, false, false );
2127       } catch( IOException e ) {}
2128       System.out.println( "  "+mc+" done calling "+fm );
2129     }
2130     */
2131   }
2132
2133
2134   protected boolean hasMatchingField(HeapRegionNode src, ReferenceEdge edge) {
2135
2136     // if no type, then it's a match-everything region
2137     TypeDescriptor tdSrc = src.getType();
2138     if( tdSrc == null ) {
2139       return true;
2140     }
2141
2142     if( tdSrc.isArray() ) {
2143       TypeDescriptor td = edge.getType();
2144       assert td != null;
2145
2146       TypeDescriptor tdSrcDeref = tdSrc.dereference();
2147       assert tdSrcDeref != null;
2148
2149       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
2150         return false;
2151       }
2152
2153       return edge.getField().equals( OwnershipAnalysis.arrayElementFieldName );
2154     }
2155
2156     // if it's not a class, it doesn't have any fields to match
2157     if( !tdSrc.isClass() ) {
2158       return false;
2159     }
2160
2161     Iterator fieldsSrcItr = tdSrc.getClassDesc().getFields();
2162     while( fieldsSrcItr.hasNext() ) {
2163       FieldDescriptor fd = (FieldDescriptor) fieldsSrcItr.next();
2164       if( fd.getType().equals( edge.getType() ) &&
2165           fd.getSymbol().equals( edge.getField() ) ) {
2166         return true;
2167       }
2168     }
2169
2170     // otherwise it is a class with fields
2171     // but we didn't find a match
2172     return false;
2173   }
2174
2175
2176   protected boolean hasMatchingType(ReferenceEdge edge, HeapRegionNode dst) {
2177
2178     // if the region has no type, matches everything
2179     TypeDescriptor tdDst = dst.getType();
2180     if( tdDst == null ) {
2181       return true;
2182     }
2183
2184     // if the type is not a class or an array, don't
2185     // match because primitives are copied, no aliases
2186     ClassDescriptor cdDst = tdDst.getClassDesc();
2187     if( cdDst == null && !tdDst.isArray() ) {
2188       return false;
2189     }
2190
2191     // if the edge type is null, it matches everything
2192     TypeDescriptor tdEdge = edge.getType();
2193     if( tdEdge == null ) {
2194       return true;
2195     }
2196
2197     return typeUtil.isSuperorType(tdEdge, tdDst);
2198   }
2199
2200
2201
2202   protected void unshadowTokens(AllocationSite as, ReferenceEdge edge) {
2203     edge.setBeta(edge.getBeta().unshadowTokens(as) );
2204   }
2205
2206   protected void unshadowTokens(AllocationSite as, HeapRegionNode hrn) {
2207     hrn.setAlpha(hrn.getAlpha().unshadowTokens(as) );
2208   }
2209
2210
2211   private ReachabilitySet toShadowTokens(OwnershipGraph ogCallee,
2212                                          ReachabilitySet rsIn) {
2213
2214     ReachabilitySet rsOut = new ReachabilitySet(rsIn).makeCanonical();
2215
2216     Iterator<AllocationSite> allocItr = ogCallee.allocationSites.iterator();
2217     while( allocItr.hasNext() ) {
2218       AllocationSite as = allocItr.next();
2219
2220       rsOut = rsOut.toShadowTokens(as);
2221     }
2222
2223     return rsOut.makeCanonical();
2224   }
2225
2226
2227   private void rewriteCallerReachability(Integer paramIndex,
2228                                          HeapRegionNode hrn,
2229                                          ReferenceEdge edge,
2230                                          ReachabilitySet rules,
2231                                          Hashtable<Integer, ReachabilitySet> paramIndex2rewrite_d,
2232                                          Hashtable<Integer, ReachabilitySet> paramIndex2rewriteD,
2233                                          TokenTuple p_i,
2234                                          Hashtable<TokenTuple, Integer> paramToken2paramIndex,
2235                                          Hashtable<TokenTuple, Integer> paramTokenPlus2paramIndex,
2236                                          Hashtable<TokenTuple, Integer> paramTokenStar2paramIndex,
2237                                          boolean makeChangeSet,
2238                                          Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges) {
2239
2240     assert(hrn == null && edge != null) ||
2241           (hrn != null && edge == null);
2242
2243     assert rules != null;
2244     assert p_i   != null;
2245
2246     ReachabilitySet callerReachabilityCurrent;
2247     if( hrn == null ) {
2248       callerReachabilityCurrent = edge.getBeta();
2249     } else {
2250       callerReachabilityCurrent = hrn.getAlpha();
2251     }
2252
2253     ReachabilitySet callerReachabilityNew = new ReachabilitySet().makeCanonical();
2254
2255     // for initializing structures in this method
2256     TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
2257
2258     // use this to construct a change set if required; the idea is to
2259     // map every partially rewritten token tuple set to the set of
2260     // caller-context token tuple sets that were used to generate it
2261     Hashtable<TokenTupleSet, HashSet<TokenTupleSet> > rewritten2source =
2262       new Hashtable<TokenTupleSet, HashSet<TokenTupleSet> >();
2263     rewritten2source.put(ttsEmpty, new HashSet<TokenTupleSet>() );
2264
2265
2266     Iterator<TokenTupleSet> rulesItr = rules.iterator();
2267     while(rulesItr.hasNext()) {
2268       TokenTupleSet rule = rulesItr.next();
2269
2270       ReachabilitySet rewrittenRule = new ReachabilitySet(ttsEmpty).makeCanonical();
2271
2272       Iterator<TokenTuple> ruleItr = rule.iterator();
2273       while(ruleItr.hasNext()) {
2274         TokenTuple ttCallee = ruleItr.next();
2275
2276         // compute the possibilities for rewriting this callee token
2277         ReachabilitySet ttCalleeRewrites = null;
2278         boolean callerSourceUsed = false;
2279
2280         if( ttCallee.equals(p_i) ) {
2281           // replace the arity-one token of the current parameter with the reachability
2282           // information from the caller edge
2283           ttCalleeRewrites = callerReachabilityCurrent;
2284           callerSourceUsed = true;
2285
2286         } else if( paramToken2paramIndex.containsKey(ttCallee) ) {
2287           // use little d
2288           Integer paramIndex_j = paramToken2paramIndex.get(ttCallee);
2289           assert paramIndex_j != null;
2290           ttCalleeRewrites = paramIndex2rewrite_d.get(paramIndex_j);
2291           assert ttCalleeRewrites != null;
2292
2293         } else if( paramTokenPlus2paramIndex.containsKey(ttCallee) ) {
2294           // worse, use big D
2295           Integer paramIndex_j = paramTokenPlus2paramIndex.get(ttCallee);
2296           assert paramIndex_j != null;
2297           ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
2298           assert ttCalleeRewrites != null;
2299
2300         } else if( paramTokenStar2paramIndex.containsKey(ttCallee) ) {
2301           // worse, use big D
2302           Integer paramIndex_j = paramTokenStar2paramIndex.get(ttCallee);
2303           assert paramIndex_j != null;
2304           ttCalleeRewrites = paramIndex2rewriteD.get(paramIndex_j);
2305           assert ttCalleeRewrites != null;
2306
2307         } else {
2308           // otherwise there's no need for a rewrite, just pass this one on
2309           TokenTupleSet ttsCaller = new TokenTupleSet(ttCallee).makeCanonical();
2310           ttCalleeRewrites = new ReachabilitySet(ttsCaller).makeCanonical();
2311         }
2312
2313         // branch every version of the working rewritten rule with
2314         // the possibilities for rewriting the current callee token
2315         ReachabilitySet rewrittenRuleWithTTCallee = new ReachabilitySet().makeCanonical();
2316
2317         Iterator<TokenTupleSet> rewrittenRuleItr = rewrittenRule.iterator();
2318         while( rewrittenRuleItr.hasNext() ) {
2319           TokenTupleSet ttsRewritten = rewrittenRuleItr.next();
2320
2321           Iterator<TokenTupleSet> ttCalleeRewritesItr = ttCalleeRewrites.iterator();
2322           while( ttCalleeRewritesItr.hasNext() ) {
2323             TokenTupleSet ttsBranch = ttCalleeRewritesItr.next();
2324
2325             TokenTupleSet ttsRewrittenNext = ttsRewritten.unionUpArity(ttsBranch);
2326
2327             if( makeChangeSet ) {
2328               // in order to keep the list of source token tuple sets
2329               // start with the sets used to make the partially rewritten
2330               // rule up to this point
2331               HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewritten);
2332               assert sourceSets != null;
2333
2334               // make a shallow copy for possible modification
2335               sourceSets = (HashSet<TokenTupleSet>)sourceSets.clone();
2336
2337               // if we used something from the caller to rewrite it, remember
2338               if( callerSourceUsed ) {
2339                 sourceSets.add(ttsBranch);
2340               }
2341
2342               // set mapping for the further rewritten rule
2343               rewritten2source.put(ttsRewrittenNext, sourceSets);
2344             }
2345
2346             rewrittenRuleWithTTCallee =
2347               rewrittenRuleWithTTCallee.union(ttsRewrittenNext);
2348           }
2349         }
2350
2351         // now the rewritten rule's possibilities have been extended by
2352         // rewriting the current callee token, remember result
2353         rewrittenRule = rewrittenRuleWithTTCallee;
2354       }
2355
2356       // the rule has been entirely rewritten into the caller context
2357       // now, so add it to the new reachability information
2358       callerReachabilityNew =
2359         callerReachabilityNew.union(rewrittenRule);
2360     }
2361
2362     if( makeChangeSet ) {
2363       ChangeTupleSet callerChangeSet = new ChangeTupleSet().makeCanonical();
2364
2365       // each possibility for the final reachability should have a set of
2366       // caller sources mapped to it, use to create the change set
2367       Iterator<TokenTupleSet> callerReachabilityItr = callerReachabilityNew.iterator();
2368       while( callerReachabilityItr.hasNext() ) {
2369         TokenTupleSet ttsRewrittenFinal = callerReachabilityItr.next();
2370         HashSet<TokenTupleSet> sourceSets = rewritten2source.get(ttsRewrittenFinal);
2371         assert sourceSets != null;
2372
2373         Iterator<TokenTupleSet> sourceSetsItr = sourceSets.iterator();
2374         while( sourceSetsItr.hasNext() ) {
2375           TokenTupleSet ttsSource = sourceSetsItr.next();
2376
2377           callerChangeSet =
2378             callerChangeSet.union(new ChangeTuple(ttsSource, ttsRewrittenFinal) );
2379         }
2380       }
2381
2382       assert edgePlannedChanges != null;
2383       edgePlannedChanges.put(edge, callerChangeSet);
2384     }
2385
2386     if( hrn == null ) {
2387       edge.setBetaNew(edge.getBetaNew().union(callerReachabilityNew) );
2388     } else {
2389       hrn.setAlphaNew(hrn.getAlphaNew().union(callerReachabilityNew) );
2390     }
2391   }
2392
2393
2394
2395   private HashSet<HeapRegionNode>
2396   getHRNSetThatPossiblyMapToCalleeHRN(OwnershipGraph ogCallee,
2397                                       HeapRegionNode hrnCallee,
2398                                       Hashtable<Integer, HashSet<HeapRegionNode> > paramIndex2reachableCallerNodes
2399                                       ) {
2400     /*
2401     HashSet<HeapRegionNode> possibleCallerHRNs = new HashSet<HeapRegionNode>();
2402
2403     Set<Integer> paramIndicesCallee = ogCallee.id2paramIndexSet.get( hrnCallee.getID() );
2404
2405     if( paramIndicesCallee == null ) {
2406       // this is a node allocated in the callee then and it has
2407       // exactly one shadow node in the caller to map to
2408       AllocationSite as = hrnCallee.getAllocationSite();
2409       assert as != null;
2410
2411       int age = as.getAgeCategory(hrnCallee.getID() );
2412       assert age != AllocationSite.AGE_notInThisSite;
2413
2414       Integer idCaller;
2415       if( age == AllocationSite.AGE_summary ) {
2416         idCaller = as.getSummaryShadow();
2417       } else if( age == AllocationSite.AGE_oldest ) {
2418         idCaller = as.getOldestShadow();
2419       } else {
2420         assert age == AllocationSite.AGE_in_I;
2421
2422         Integer I = as.getAge(hrnCallee.getID() );
2423         assert I != null;
2424
2425         idCaller = as.getIthOldestShadow(I);
2426       }
2427
2428       assert id2hrn.containsKey(idCaller);
2429       HeapRegionNode hrnCaller = id2hrn.get(idCaller);
2430       possibleCallerHRNs.add(hrnCaller);
2431
2432     } else {
2433       // this is a node that was created to represent a parameter
2434       // so it maps to a whole mess of heap regions
2435       Iterator<Integer> itrIndex = paramIndicesCallee.iterator();
2436       while( itrIndex.hasNext() ) {
2437         Integer paramIndexCallee = itrIndex.next();
2438         assert paramIndex2reachableCallerNodes.containsKey(paramIndexCallee);
2439         possibleCallerHRNs.addAll( paramIndex2reachableCallerNodes.get(paramIndexCallee) );
2440       }
2441     }
2442
2443     return possibleCallerHRNs;
2444     */
2445     return new HashSet<HeapRegionNode>();
2446   }
2447
2448
2449
2450   ////////////////////////////////////////////////////
2451   //
2452   //  This global sweep is an optional step to prune
2453   //  reachability sets that are not internally
2454   //  consistent with the global graph.  It should be
2455   //  invoked after strong updates or method calls.
2456   //
2457   ////////////////////////////////////////////////////
2458   public void globalSweep() {
2459
2460     // boldB is part of the phase 1 sweep
2461     Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> > boldB =
2462       new Hashtable< Integer, Hashtable<ReferenceEdge, ReachabilitySet> >();
2463
2464     // visit every heap region to initialize alphaNew and calculate boldB
2465     Set hrns = id2hrn.entrySet();
2466     Iterator itrHrns = hrns.iterator();
2467     while( itrHrns.hasNext() ) {
2468       Map.Entry me = (Map.Entry)itrHrns.next();
2469       Integer token = (Integer) me.getKey();
2470       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2471
2472       // assert that this node and incoming edges have clean alphaNew
2473       // and betaNew sets, respectively
2474       ReachabilitySet rsEmpty = new ReachabilitySet().makeCanonical();
2475       assert rsEmpty.equals( hrn.getAlphaNew() );
2476
2477       Iterator<ReferenceEdge> itrRers = hrn.iteratorToReferencers();
2478       while( itrRers.hasNext() ) {
2479         ReferenceEdge edge = itrRers.next();
2480         assert rsEmpty.equals( edge.getBetaNew() );
2481       }
2482
2483       // calculate boldB for this flagged node
2484       if( hrn.isFlagged() || hrn.isParameter() ) {
2485
2486         Hashtable<ReferenceEdge, ReachabilitySet> boldB_f =
2487           new Hashtable<ReferenceEdge, ReachabilitySet>();
2488
2489         Set<ReferenceEdge> workSetEdges = new HashSet<ReferenceEdge>();
2490
2491         // initial boldB_f constraints
2492         Iterator<ReferenceEdge> itrRees = hrn.iteratorToReferencees();
2493         while( itrRees.hasNext() ) {
2494           ReferenceEdge edge = itrRees.next();
2495
2496           assert !boldB.containsKey( edge );
2497           boldB_f.put( edge, edge.getBeta() );
2498
2499           assert !workSetEdges.contains( edge );
2500           workSetEdges.add( edge );
2501         }
2502
2503         // enforce the boldB_f constraint at edges until we reach a fixed point
2504         while( !workSetEdges.isEmpty() ) {
2505           ReferenceEdge edge = workSetEdges.iterator().next();
2506           workSetEdges.remove( edge );
2507
2508           Iterator<ReferenceEdge> itrPrime = edge.getDst().iteratorToReferencees();
2509           while( itrPrime.hasNext() ) {
2510             ReferenceEdge edgePrime = itrPrime.next();
2511
2512             ReachabilitySet prevResult   = boldB_f.get( edgePrime );
2513             ReachabilitySet intersection = boldB_f.get( edge ).intersection( edgePrime.getBeta() );
2514
2515             if( prevResult == null ||
2516                 prevResult.union( intersection ).size() > prevResult.size() ) {
2517
2518               if( prevResult == null ) {
2519                 boldB_f.put( edgePrime, edgePrime.getBeta().union( intersection ) );
2520               } else {
2521                 boldB_f.put( edgePrime, prevResult.union( intersection ) );
2522               }
2523               workSetEdges.add( edgePrime );
2524             }
2525           }
2526         }
2527
2528         boldB.put( token, boldB_f );
2529       }
2530     }
2531
2532
2533     // use boldB to prune tokens from alpha states that are impossible
2534     // and propagate the differences backwards across edges
2535     HashSet<ReferenceEdge> edgesForPropagation = new HashSet<ReferenceEdge>();
2536
2537     Hashtable<ReferenceEdge, ChangeTupleSet> edgePlannedChanges =
2538       new Hashtable<ReferenceEdge, ChangeTupleSet>();
2539
2540     hrns = id2hrn.entrySet();
2541     itrHrns = hrns.iterator();
2542     while( itrHrns.hasNext() ) {
2543       Map.Entry me = (Map.Entry)itrHrns.next();
2544       Integer token = (Integer) me.getKey();
2545       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2546
2547       // never remove the identity token from a flagged region
2548       // because it is trivially satisfied
2549       TokenTuple ttException = new TokenTuple( token, !hrn.isSingleObject(), TokenTuple.ARITY_ONE ).makeCanonical();
2550
2551       ChangeTupleSet cts = new ChangeTupleSet().makeCanonical();
2552
2553       // mark tokens for removal
2554       Iterator<TokenTupleSet> stateItr = hrn.getAlpha().iterator();
2555       while( stateItr.hasNext() ) {
2556         TokenTupleSet ttsOld = stateItr.next();
2557
2558         TokenTupleSet markedTokens = new TokenTupleSet().makeCanonical();
2559
2560         Iterator<TokenTuple> ttItr = ttsOld.iterator();
2561         while( ttItr.hasNext() ) {
2562           TokenTuple ttOld = ttItr.next();
2563
2564           // never remove the identity token from a flagged region
2565           // because it is trivially satisfied
2566           if( hrn.isFlagged() || hrn.isParameter() ) {
2567             if( ttOld == ttException ) {
2568               continue;
2569             }
2570           }
2571
2572           // does boldB_ttOld allow this token?
2573           boolean foundState = false;
2574           Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2575           while( incidentEdgeItr.hasNext() ) {
2576             ReferenceEdge incidentEdge = incidentEdgeItr.next();
2577
2578             // if it isn't allowed, mark for removal
2579             ReachabilitySet boldB_ttOld_incident = boldB.get( ttOld.getToken() ).get( incidentEdge );
2580             if( boldB_ttOld_incident != null &&
2581                 boldB_ttOld_incident.contains( ttsOld ) ) {
2582               foundState = true;
2583             }
2584           }
2585
2586           if( !foundState ) {
2587             markedTokens = markedTokens.add( ttOld );
2588           }
2589         }
2590
2591         // if there is nothing marked, just move on
2592         if( markedTokens.isEmpty() ) {
2593           hrn.setAlphaNew( hrn.getAlphaNew().union( ttsOld ) );
2594           continue;
2595         }
2596
2597         // remove all marked tokens and establish a change set that should
2598         // propagate backwards over edges from this node
2599         TokenTupleSet ttsPruned = new TokenTupleSet().makeCanonical();
2600         ttItr = ttsOld.iterator();
2601         while( ttItr.hasNext() ) {
2602           TokenTuple ttOld = ttItr.next();
2603
2604           if( !markedTokens.containsTuple( ttOld ) ) {
2605             ttsPruned = ttsPruned.union( ttOld );
2606           }
2607         }
2608         assert !ttsOld.equals( ttsPruned );
2609
2610         hrn.setAlphaNew( hrn.getAlphaNew().union( ttsPruned ) );
2611         ChangeTuple ct = new ChangeTuple( ttsOld, ttsPruned ).makeCanonical();
2612         cts = cts.union( ct );
2613       }
2614
2615       // throw change tuple set on all incident edges
2616       if( !cts.isEmpty() ) {
2617         Iterator<ReferenceEdge> incidentEdgeItr = hrn.iteratorToReferencers();
2618         while( incidentEdgeItr.hasNext() ) {
2619           ReferenceEdge incidentEdge = incidentEdgeItr.next();
2620
2621           edgesForPropagation.add( incidentEdge );
2622
2623           if( edgePlannedChanges.get( incidentEdge ) == null ) {
2624             edgePlannedChanges.put( incidentEdge, cts );
2625           } else {
2626             edgePlannedChanges.put(
2627               incidentEdge,
2628               edgePlannedChanges.get( incidentEdge ).union( cts )
2629                                   );
2630           }
2631         }
2632       }
2633     }
2634
2635     HashSet<ReferenceEdge> edgesUpdated = new HashSet<ReferenceEdge>();
2636
2637     propagateTokensOverEdges( edgesForPropagation,
2638                               edgePlannedChanges,
2639                               edgesUpdated );
2640
2641     // at the end of the 1st phase reference edges have
2642     // beta, betaNew that correspond to beta and betaR
2643     //
2644     // commit beta<-betaNew, so beta=betaR and betaNew
2645     // will represent the beta' calculation in 2nd phase
2646     //
2647     // commit alpha<-alphaNew because it won't change
2648     HashSet<ReferenceEdge> res = new HashSet<ReferenceEdge>();
2649
2650     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
2651     while( nodeItr.hasNext() ) {
2652       HeapRegionNode hrn = nodeItr.next();
2653       hrn.applyAlphaNew();
2654       Iterator<ReferenceEdge> itrRes = hrn.iteratorToReferencers();
2655       while( itrRes.hasNext() ) {
2656         res.add( itrRes.next() );
2657       }
2658     }
2659
2660
2661     // 2nd phase
2662     Iterator<ReferenceEdge> edgeItr = res.iterator();
2663     while( edgeItr.hasNext() ) {
2664       ReferenceEdge edge = edgeItr.next();
2665       HeapRegionNode hrn = edge.getDst();
2666
2667       // commit results of last phase
2668       if( edgesUpdated.contains( edge ) ) {
2669         edge.applyBetaNew();
2670       }
2671
2672       // compute intial condition of 2nd phase
2673       edge.setBetaNew( edge.getBeta().intersection( hrn.getAlpha() ) );
2674     }
2675
2676     // every edge in the graph is the initial workset
2677     Set<ReferenceEdge> edgeWorkSet = (Set) res.clone();
2678     while( !edgeWorkSet.isEmpty() ) {
2679       ReferenceEdge edgePrime = edgeWorkSet.iterator().next();
2680       edgeWorkSet.remove( edgePrime );
2681
2682       OwnershipNode on = edgePrime.getSrc();
2683       if( !(on instanceof HeapRegionNode) ) {
2684         continue;
2685       }
2686       HeapRegionNode hrn = (HeapRegionNode) on;
2687
2688       Iterator<ReferenceEdge> itrEdge = hrn.iteratorToReferencers();
2689       while( itrEdge.hasNext() ) {
2690         ReferenceEdge edge = itrEdge.next();
2691
2692         ReachabilitySet prevResult = edge.getBetaNew();
2693         assert prevResult != null;
2694
2695         ReachabilitySet intersection = edge.getBeta().intersection( edgePrime.getBetaNew() );
2696
2697         if( prevResult.union( intersection ).size() > prevResult.size() ) {
2698           edge.setBetaNew( prevResult.union( intersection ) );
2699           edgeWorkSet.add( edge );
2700         }
2701       }
2702     }
2703
2704     // commit beta' (beta<-betaNew)
2705     edgeItr = res.iterator();
2706     while( edgeItr.hasNext() ) {
2707       edgeItr.next().applyBetaNew();
2708     }
2709   }
2710
2711
2712
2713   ////////////////////////////////////////////////////
2714   // in merge() and equals() methods the suffix A
2715   // represents the passed in graph and the suffix
2716   // B refers to the graph in this object
2717   // Merging means to take the incoming graph A and
2718   // merge it into B, so after the operation graph B
2719   // is the final result.
2720   ////////////////////////////////////////////////////
2721   public void merge(OwnershipGraph og) {
2722
2723     if( og == null ) {
2724       return;
2725     }
2726
2727     mergeOwnershipNodes(og);
2728     mergeReferenceEdges(og);
2729     mergeParamIndexMappings(og);
2730     mergeAllocationSites(og);
2731   }
2732
2733
2734   protected void mergeOwnershipNodes(OwnershipGraph og) {
2735     Set sA = og.id2hrn.entrySet();
2736     Iterator iA = sA.iterator();
2737     while( iA.hasNext() ) {
2738       Map.Entry meA  = (Map.Entry)iA.next();
2739       Integer idA  = (Integer)        meA.getKey();
2740       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2741
2742       // if this graph doesn't have a node the
2743       // incoming graph has, allocate it
2744       if( !id2hrn.containsKey(idA) ) {
2745         HeapRegionNode hrnB = hrnA.copy();
2746         id2hrn.put(idA, hrnB);
2747
2748       } else {
2749         // otherwise this is a node present in both graphs
2750         // so make the new reachability set a union of the
2751         // nodes' reachability sets
2752         HeapRegionNode hrnB = id2hrn.get(idA);
2753         hrnB.setAlpha(hrnB.getAlpha().union(hrnA.getAlpha() ) );
2754       }
2755     }
2756
2757     // now add any label nodes that are in graph B but
2758     // not in A
2759     sA = og.td2ln.entrySet();
2760     iA = sA.iterator();
2761     while( iA.hasNext() ) {
2762       Map.Entry meA = (Map.Entry)iA.next();
2763       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2764       LabelNode lnA = (LabelNode)      meA.getValue();
2765
2766       // if the label doesn't exist in B, allocate and add it
2767       LabelNode lnB = getLabelNodeFromTemp(tdA);
2768     }
2769   }
2770
2771   protected void mergeReferenceEdges(OwnershipGraph og) {
2772
2773     // heap regions
2774     Set sA = og.id2hrn.entrySet();
2775     Iterator iA = sA.iterator();
2776     while( iA.hasNext() ) {
2777       Map.Entry meA  = (Map.Entry)iA.next();
2778       Integer idA  = (Integer)        meA.getKey();
2779       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2780
2781       Iterator<ReferenceEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
2782       while( heapRegionsItrA.hasNext() ) {
2783         ReferenceEdge edgeA     = heapRegionsItrA.next();
2784         HeapRegionNode hrnChildA = edgeA.getDst();
2785         Integer idChildA  = hrnChildA.getID();
2786
2787         // at this point we know an edge in graph A exists
2788         // idA -> idChildA, does this exist in B?
2789         assert id2hrn.containsKey(idA);
2790         HeapRegionNode hrnB        = id2hrn.get(idA);
2791         ReferenceEdge edgeToMerge = null;
2792
2793         Iterator<ReferenceEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
2794         while( heapRegionsItrB.hasNext() &&
2795                edgeToMerge == null          ) {
2796
2797           ReferenceEdge edgeB     = heapRegionsItrB.next();
2798           HeapRegionNode hrnChildB = edgeB.getDst();
2799           Integer idChildB  = hrnChildB.getID();
2800
2801           // don't use the ReferenceEdge.equals() here because
2802           // we're talking about existence between graphs
2803           if( idChildB.equals( idChildA ) &&
2804               edgeB.typeAndFieldEquals( edgeA ) ) {
2805
2806             edgeToMerge = edgeB;
2807           }
2808         }
2809
2810         // if the edge from A was not found in B,
2811         // add it to B.
2812         if( edgeToMerge == null ) {
2813           assert id2hrn.containsKey(idChildA);
2814           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2815           edgeToMerge = edgeA.copy();
2816           edgeToMerge.setSrc(hrnB);
2817           edgeToMerge.setDst(hrnChildB);
2818           addReferenceEdge(hrnB, hrnChildB, edgeToMerge);
2819         }
2820         // otherwise, the edge already existed in both graphs
2821         // so merge their reachability sets
2822         else {
2823           // just replace this beta set with the union
2824           assert edgeToMerge != null;
2825           edgeToMerge.setBeta(
2826             edgeToMerge.getBeta().union(edgeA.getBeta() )
2827             );
2828           if( !edgeA.isInitialParamReflexive() ) {
2829             edgeToMerge.setIsInitialParamReflexive(false);
2830           }
2831         }
2832       }
2833     }
2834
2835     // and then again with label nodes
2836     sA = og.td2ln.entrySet();
2837     iA = sA.iterator();
2838     while( iA.hasNext() ) {
2839       Map.Entry meA = (Map.Entry)iA.next();
2840       TempDescriptor tdA = (TempDescriptor) meA.getKey();
2841       LabelNode lnA = (LabelNode)      meA.getValue();
2842
2843       Iterator<ReferenceEdge> heapRegionsItrA = lnA.iteratorToReferencees();
2844       while( heapRegionsItrA.hasNext() ) {
2845         ReferenceEdge edgeA     = heapRegionsItrA.next();
2846         HeapRegionNode hrnChildA = edgeA.getDst();
2847         Integer idChildA  = hrnChildA.getID();
2848
2849         // at this point we know an edge in graph A exists
2850         // tdA -> idChildA, does this exist in B?
2851         assert td2ln.containsKey(tdA);
2852         LabelNode lnB         = td2ln.get(tdA);
2853         ReferenceEdge edgeToMerge = null;
2854
2855         Iterator<ReferenceEdge> heapRegionsItrB = lnB.iteratorToReferencees();
2856         while( heapRegionsItrB.hasNext() &&
2857                edgeToMerge == null          ) {
2858
2859           ReferenceEdge  edgeB     = heapRegionsItrB.next();
2860           HeapRegionNode hrnChildB = edgeB.getDst();
2861           Integer        idChildB  = hrnChildB.getID();
2862
2863           // don't use the ReferenceEdge.equals() here because
2864           // we're talking about existence between graphs
2865           if( idChildB.equals( idChildA ) &&
2866               edgeB.typeAndFieldEquals( edgeA ) ) {
2867
2868             edgeToMerge = edgeB;
2869           }
2870         }
2871
2872         // if the edge from A was not found in B,
2873         // add it to B.
2874         if( edgeToMerge == null ) {
2875           assert id2hrn.containsKey(idChildA);
2876           HeapRegionNode hrnChildB = id2hrn.get(idChildA);
2877           edgeToMerge = edgeA.copy();
2878           edgeToMerge.setSrc(lnB);
2879           edgeToMerge.setDst(hrnChildB);
2880           addReferenceEdge(lnB, hrnChildB, edgeToMerge);
2881         }
2882         // otherwise, the edge already existed in both graphs
2883         // so merge their reachability sets
2884         else {
2885           // just replace this beta set with the union
2886           edgeToMerge.setBeta(
2887             edgeToMerge.getBeta().union(edgeA.getBeta() )
2888             );
2889           if( !edgeA.isInitialParamReflexive() ) {
2890             edgeToMerge.setIsInitialParamReflexive(false);
2891           }
2892         }
2893       }
2894     }
2895   }
2896
2897   // you should only merge ownership graphs that have the
2898   // same number of parameters, or if one or both parameter
2899   // index tables are empty
2900   protected void mergeParamIndexMappings(OwnershipGraph og) {
2901
2902     if( idPrimary2paramIndexSet.size() == 0 ) {
2903       idPrimary2paramIndexSet = og.idPrimary2paramIndexSet;
2904       paramIndex2idPrimary    = og.paramIndex2idPrimary;
2905
2906       idSecondary2paramIndexSet = og.idSecondary2paramIndexSet;
2907       paramIndex2idSecondary    = og.paramIndex2idSecondary;
2908
2909       paramIndex2tdQ   = og.paramIndex2tdQ;
2910       return;
2911     }
2912
2913     if( og.idPrimary2paramIndexSet.size() == 0 ) {
2914       return;
2915     }
2916
2917     assert idPrimary2paramIndexSet.size() == og.idPrimary2paramIndexSet.size();
2918     assert idSecondary2paramIndexSet.size() == og.idSecondary2paramIndexSet.size();
2919   }
2920
2921   protected void mergeAllocationSites(OwnershipGraph og) {
2922     allocationSites.addAll(og.allocationSites);
2923   }
2924
2925
2926
2927   // it is necessary in the equals() member functions
2928   // to "check both ways" when comparing the data
2929   // structures of two graphs.  For instance, if all
2930   // edges between heap region nodes in graph A are
2931   // present and equal in graph B it is not sufficient
2932   // to say the graphs are equal.  Consider that there
2933   // may be edges in graph B that are not in graph A.
2934   // the only way to know that all edges in both graphs
2935   // are equally present is to iterate over both data
2936   // structures and compare against the other graph.
2937   public boolean equals(OwnershipGraph og) {
2938
2939     if( og == null ) {
2940       return false;
2941     }
2942
2943     if( !areHeapRegionNodesEqual(og) ) {
2944       return false;
2945     }
2946
2947     if( !areLabelNodesEqual(og) ) {
2948       return false;
2949     }
2950
2951     if( !areReferenceEdgesEqual(og) ) {
2952       return false;
2953     }
2954
2955     if( !areParamIndexMappingsEqual(og) ) {
2956       return false;
2957     }
2958
2959     // if everything is equal up to this point,
2960     // assert that allocationSites is also equal--
2961     // this data is redundant and kept for efficiency
2962     assert allocationSites.equals(og.allocationSites);
2963
2964     return true;
2965   }
2966
2967   protected boolean areHeapRegionNodesEqual(OwnershipGraph og) {
2968
2969     if( !areallHRNinAalsoinBandequal(this, og) ) {
2970       return false;
2971     }
2972
2973     if( !areallHRNinAalsoinBandequal(og, this) ) {
2974       return false;
2975     }
2976
2977     return true;
2978   }
2979
2980   static protected boolean areallHRNinAalsoinBandequal(OwnershipGraph ogA,
2981                                                        OwnershipGraph ogB) {
2982     Set sA = ogA.id2hrn.entrySet();
2983     Iterator iA = sA.iterator();
2984     while( iA.hasNext() ) {
2985       Map.Entry meA  = (Map.Entry)iA.next();
2986       Integer idA  = (Integer)        meA.getKey();
2987       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
2988
2989       if( !ogB.id2hrn.containsKey(idA) ) {
2990         return false;
2991       }
2992
2993       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
2994       if( !hrnA.equalsIncludingAlpha(hrnB) ) {
2995         return false;
2996       }
2997     }
2998
2999     return true;
3000   }
3001
3002
3003   protected boolean areLabelNodesEqual(OwnershipGraph og) {
3004
3005     if( !areallLNinAalsoinBandequal(this, og) ) {
3006       return false;
3007     }
3008
3009     if( !areallLNinAalsoinBandequal(og, this) ) {
3010       return false;
3011     }
3012
3013     return true;
3014   }
3015
3016   static protected boolean areallLNinAalsoinBandequal(OwnershipGraph ogA,
3017                                                       OwnershipGraph ogB) {
3018     Set sA = ogA.td2ln.entrySet();
3019     Iterator iA = sA.iterator();
3020     while( iA.hasNext() ) {
3021       Map.Entry meA = (Map.Entry)iA.next();
3022       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3023
3024       if( !ogB.td2ln.containsKey(tdA) ) {
3025         return false;
3026       }
3027     }
3028
3029     return true;
3030   }
3031
3032
3033   protected boolean areReferenceEdgesEqual(OwnershipGraph og) {
3034     if( !areallREinAandBequal(this, og) ) {
3035       return false;
3036     }
3037
3038     return true;
3039   }
3040
3041   static protected boolean areallREinAandBequal(OwnershipGraph ogA,
3042                                                 OwnershipGraph ogB) {
3043
3044     // check all the heap region->heap region edges
3045     Set sA = ogA.id2hrn.entrySet();
3046     Iterator iA = sA.iterator();
3047     while( iA.hasNext() ) {
3048       Map.Entry meA  = (Map.Entry)iA.next();
3049       Integer idA  = (Integer)        meA.getKey();
3050       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3051
3052       // we should have already checked that the same
3053       // heap regions exist in both graphs
3054       assert ogB.id2hrn.containsKey(idA);
3055
3056       if( !areallREfromAequaltoB(ogA, hrnA, ogB) ) {
3057         return false;
3058       }
3059
3060       // then check every edge in B for presence in A, starting
3061       // from the same parent HeapRegionNode
3062       HeapRegionNode hrnB = ogB.id2hrn.get(idA);
3063
3064       if( !areallREfromAequaltoB(ogB, hrnB, ogA) ) {
3065         return false;
3066       }
3067     }
3068
3069     // then check all the label->heap region edges
3070     sA = ogA.td2ln.entrySet();
3071     iA = sA.iterator();
3072     while( iA.hasNext() ) {
3073       Map.Entry meA = (Map.Entry)iA.next();
3074       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3075       LabelNode lnA = (LabelNode)      meA.getValue();
3076
3077       // we should have already checked that the same
3078       // label nodes exist in both graphs
3079       assert ogB.td2ln.containsKey(tdA);
3080
3081       if( !areallREfromAequaltoB(ogA, lnA, ogB) ) {
3082         return false;
3083       }
3084
3085       // then check every edge in B for presence in A, starting
3086       // from the same parent LabelNode
3087       LabelNode lnB = ogB.td2ln.get(tdA);
3088
3089       if( !areallREfromAequaltoB(ogB, lnB, ogA) ) {
3090         return false;
3091       }
3092     }
3093
3094     return true;
3095   }
3096
3097
3098   static protected boolean areallREfromAequaltoB(OwnershipGraph ogA,
3099                                                  OwnershipNode onA,
3100                                                  OwnershipGraph ogB) {
3101
3102     Iterator<ReferenceEdge> itrA = onA.iteratorToReferencees();
3103     while( itrA.hasNext() ) {
3104       ReferenceEdge edgeA     = itrA.next();
3105       HeapRegionNode hrnChildA = edgeA.getDst();
3106       Integer idChildA  = hrnChildA.getID();
3107
3108       assert ogB.id2hrn.containsKey(idChildA);
3109
3110       // at this point we know an edge in graph A exists
3111       // onA -> idChildA, does this exact edge exist in B?
3112       boolean edgeFound = false;
3113
3114       OwnershipNode onB = null;
3115       if( onA instanceof HeapRegionNode ) {
3116         HeapRegionNode hrnA = (HeapRegionNode) onA;
3117         onB = ogB.id2hrn.get(hrnA.getID() );
3118       } else {
3119         LabelNode lnA = (LabelNode) onA;
3120         onB = ogB.td2ln.get(lnA.getTempDescriptor() );
3121       }
3122
3123       Iterator<ReferenceEdge> itrB = onB.iteratorToReferencees();
3124       while( itrB.hasNext() ) {
3125         ReferenceEdge edgeB     = itrB.next();
3126         HeapRegionNode hrnChildB = edgeB.getDst();
3127         Integer idChildB  = hrnChildB.getID();
3128
3129         if( idChildA.equals( idChildB ) &&
3130             edgeA.typeAndFieldEquals( edgeB ) ) {
3131
3132           // there is an edge in the right place with the right field,
3133           // but do they have the same attributes?
3134           if( edgeA.getBeta().equals(edgeB.getBeta() ) ) {
3135             edgeFound = true;
3136           }
3137         }
3138       }
3139
3140       if( !edgeFound ) {
3141         return false;
3142       }
3143     }
3144
3145     return true;
3146   }
3147
3148
3149   protected boolean areParamIndexMappingsEqual(OwnershipGraph og) {
3150
3151     if( idPrimary2paramIndexSet.size() != og.idPrimary2paramIndexSet.size() ) {
3152       return false;
3153     }
3154
3155     if( idSecondary2paramIndexSet.size() != og.idSecondary2paramIndexSet.size() ) {
3156       return false;
3157     }
3158
3159     return true;
3160   }
3161
3162
3163   public Set<HeapRegionNode> hasPotentialAlias( HeapRegionNode hrn1, HeapRegionNode hrn2 ) {
3164     /*
3165     assert hrn1 != null;
3166     assert hrn2 != null;
3167
3168     // then get the various tokens for these heap regions
3169     TokenTuple h1 = new TokenTuple(hrn1.getID(),
3170                                    !hrn1.isSingleObject(),
3171                                    TokenTuple.ARITY_ONE).makeCanonical();
3172
3173     TokenTuple h1plus = new TokenTuple(hrn1.getID(),
3174                                        !hrn1.isSingleObject(),
3175                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
3176
3177     TokenTuple h1star = new TokenTuple(hrn1.getID(),
3178                                        !hrn1.isSingleObject(),
3179                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
3180
3181     TokenTuple h2 = new TokenTuple(hrn2.getID(),
3182                                    !hrn2.isSingleObject(),
3183                                    TokenTuple.ARITY_ONE).makeCanonical();
3184
3185     TokenTuple h2plus = new TokenTuple(hrn2.getID(),
3186                                        !hrn2.isSingleObject(),
3187                                        TokenTuple.ARITY_ONEORMORE).makeCanonical();
3188
3189     TokenTuple h2star = new TokenTuple(hrn2.getID(),
3190                                        !hrn2.isSingleObject(),
3191                                        TokenTuple.ARITY_ZEROORMORE).makeCanonical();
3192
3193     // then get the merged beta of all out-going edges from these heap regions
3194     ReachabilitySet beta1 = new ReachabilitySet();
3195     Iterator<ReferenceEdge> itrEdge = hrn1.iteratorToReferencees();
3196     while( itrEdge.hasNext() ) {
3197       ReferenceEdge edge = itrEdge.next();
3198       beta1 = beta1.union( edge.getBeta() );
3199     }
3200
3201     ReachabilitySet beta2 = new ReachabilitySet();
3202     itrEdge = hrn2.iteratorToReferencees();
3203     while( itrEdge.hasNext() ) {
3204       ReferenceEdge edge = itrEdge.next();
3205       beta2 = beta2.union( edge.getBeta() );
3206     }
3207
3208     boolean aliasDetected = false;
3209
3210     // only do this one if they are different tokens
3211     if( h1 != h2 &&
3212         beta1.containsTupleSetWithBoth(h1,     h2) ) {
3213       aliasDetected = true;
3214     }
3215     if( beta1.containsTupleSetWithBoth(h1plus, h2) ) {
3216       aliasDetected = true;
3217     }
3218     if( beta1.containsTupleSetWithBoth(h1star, h2) ) {
3219       aliasDetected = true;
3220     }
3221     if( beta1.containsTupleSetWithBoth(h1,     h2plus) ) {
3222       aliasDetected = true;
3223     }
3224     if( beta1.containsTupleSetWithBoth(h1plus, h2plus) ) {
3225       aliasDetected = true;
3226     }
3227     if( beta1.containsTupleSetWithBoth(h1star, h2plus) ) {
3228       aliasDetected = true;
3229     }
3230     if( beta1.containsTupleSetWithBoth(h1,     h2star) ) {
3231       aliasDetected = true;
3232     }
3233     if( beta1.containsTupleSetWithBoth(h1plus, h2star) ) {
3234       aliasDetected = true;
3235     }
3236     if( beta1.containsTupleSetWithBoth(h1star, h2star) ) {
3237       aliasDetected = true;
3238     }
3239
3240     if( h1 != h2 &&
3241         beta2.containsTupleSetWithBoth(h1,     h2) ) {
3242       aliasDetected = true;
3243     }
3244     if( beta2.containsTupleSetWithBoth(h1plus, h2) ) {
3245       aliasDetected = true;
3246     }
3247     if( beta2.containsTupleSetWithBoth(h1star, h2) ) {
3248       aliasDetected = true;
3249     }
3250     if( beta2.containsTupleSetWithBoth(h1,     h2plus) ) {
3251       aliasDetected = true;
3252     }
3253     if( beta2.containsTupleSetWithBoth(h1plus, h2plus) ) {
3254       aliasDetected = true;
3255     }
3256     if( beta2.containsTupleSetWithBoth(h1star, h2plus) ) {
3257       aliasDetected = true;
3258     }
3259     if( beta2.containsTupleSetWithBoth(h1,     h2star) ) {
3260       aliasDetected = true;
3261     }
3262     if( beta2.containsTupleSetWithBoth(h1plus, h2star) ) {
3263       aliasDetected = true;
3264     }
3265     if( beta2.containsTupleSetWithBoth(h1star, h2star) ) {
3266       aliasDetected = true;
3267     }
3268
3269     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
3270     if( aliasDetected ) {
3271       common = findCommonReachableNodes( hrn1, hrn2 );
3272       assert !common.isEmpty();
3273     }
3274
3275     return common;
3276     */
3277     return new HashSet<HeapRegionNode>();
3278   }
3279
3280
3281   public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex1, Integer paramIndex2) {
3282     /*
3283     // get parameter's heap region
3284     assert paramIndex2id.containsKey(paramIndex1);
3285     Integer idParam1 = paramIndex2id.get(paramIndex1);
3286
3287     assert id2hrn.containsKey(idParam1);
3288     HeapRegionNode hrnParam1 = id2hrn.get(idParam1);
3289     assert hrnParam1 != null;
3290
3291
3292     // get tokens for the other parameter
3293     assert paramIndex2id.containsKey(paramIndex2);
3294     Integer idParam2 = paramIndex2id.get(paramIndex2);
3295
3296     assert id2hrn.containsKey(idParam2);
3297     HeapRegionNode hrnParam2 = id2hrn.get(idParam2);
3298     assert hrnParam2 != null;
3299
3300     return hasPotentialAlias( hrnParam1, hrnParam2 );
3301     */
3302     return new HashSet<HeapRegionNode>();
3303   }
3304
3305
3306   public Set<HeapRegionNode> hasPotentialAlias(Integer paramIndex, AllocationSite as) {
3307     /*
3308     // get parameter's heap region
3309     assert paramIndex2id.containsKey(paramIndex);
3310     Integer idParam = paramIndex2id.get(paramIndex);
3311
3312     assert id2hrn.containsKey(idParam);
3313     HeapRegionNode hrnParam = id2hrn.get(idParam);
3314     assert hrnParam != null;
3315
3316     // get summary node
3317     assert id2hrn.containsKey( as.getSummary() );
3318     HeapRegionNode hrnSummary = id2hrn.get( as.getSummary() );
3319     assert hrnSummary != null;
3320
3321     Set<HeapRegionNode> common = hasPotentialAlias( hrnParam, hrnSummary );
3322     if( !common.isEmpty() ) {
3323       return common;
3324     }
3325
3326     // check for other nodes
3327     for( int i = 0; i < as.getAllocationDepth(); ++i ) {
3328
3329       assert id2hrn.containsKey( as.getIthOldest( i ) );
3330       HeapRegionNode hrnIthOldest = id2hrn.get( as.getIthOldest( i ) );
3331       assert hrnIthOldest != null;
3332
3333       common = hasPotentialAlias( hrnParam, hrnIthOldest );
3334       if( !common.isEmpty() ) {
3335         return common;
3336       }
3337     }
3338     */
3339     return new HashSet<HeapRegionNode>();
3340   }
3341
3342
3343   public Set<HeapRegionNode> hasPotentialAlias(AllocationSite as1, AllocationSite as2) {
3344     /*
3345     // get summary node 1's alpha
3346     Integer idSum1 = as1.getSummary();
3347     assert id2hrn.containsKey(idSum1);
3348     HeapRegionNode hrnSum1 = id2hrn.get(idSum1);
3349     assert hrnSum1 != null;
3350
3351     // get summary node 2's alpha
3352     Integer idSum2 = as2.getSummary();
3353     assert id2hrn.containsKey(idSum2);
3354     HeapRegionNode hrnSum2 = id2hrn.get(idSum2);
3355     assert hrnSum2 != null;
3356
3357     Set<HeapRegionNode> common = hasPotentialAlias( hrnSum1, hrnSum2 );
3358     if( !common.isEmpty() ) {
3359       return common;
3360     }
3361
3362     // check sum2 against alloc1 nodes
3363     for( int i = 0; i < as1.getAllocationDepth(); ++i ) {
3364       Integer idI1 = as1.getIthOldest(i);
3365       assert id2hrn.containsKey(idI1);
3366       HeapRegionNode hrnI1 = id2hrn.get(idI1);
3367       assert hrnI1 != null;
3368
3369       common = hasPotentialAlias( hrnI1, hrnSum2 );
3370       if( !common.isEmpty() ) {
3371         return common;
3372       }
3373     }
3374
3375     // check sum1 against alloc2 nodes
3376     for( int i = 0; i < as2.getAllocationDepth(); ++i ) {
3377       Integer idI2 = as2.getIthOldest(i);
3378       assert id2hrn.containsKey(idI2);
3379       HeapRegionNode hrnI2 = id2hrn.get(idI2);
3380       assert hrnI2 != null;
3381
3382       common = hasPotentialAlias( hrnSum1, hrnI2 );
3383       if( common.isEmpty() ) {
3384         return common;
3385       }
3386
3387       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
3388       for( int j = 0; j < as1.getAllocationDepth(); ++j ) {
3389         Integer idI1 = as1.getIthOldest(j);
3390
3391         // if these are the same site, don't look for the same token, no alias.
3392         // different tokens of the same site could alias together though
3393         if( idI1.equals( idI2 ) ) {
3394           continue;
3395         }
3396
3397         HeapRegionNode hrnI1 = id2hrn.get(idI1);
3398
3399         common = hasPotentialAlias( hrnI1, hrnI2 );
3400         if( !common.isEmpty() ) {
3401           return common;
3402         }
3403       }
3404     }
3405     */
3406     return new HashSet<HeapRegionNode>();
3407   }
3408
3409
3410   public Set<HeapRegionNode> findCommonReachableNodes( HeapRegionNode hrn1,
3411                                                        HeapRegionNode hrn2 ) {
3412     //assert hrn1 != hrn2;
3413
3414     Set<HeapRegionNode> reachableNodes1 = new HashSet<HeapRegionNode>();
3415     Set<HeapRegionNode> reachableNodes2 = new HashSet<HeapRegionNode>();
3416
3417     Set<HeapRegionNode> todoNodes1 = new HashSet<HeapRegionNode>();
3418     todoNodes1.add( hrn1 );
3419
3420     Set<HeapRegionNode> todoNodes2 = new HashSet<HeapRegionNode>();
3421     todoNodes2.add( hrn2 );
3422
3423     // follow links until all reachable nodes have been found
3424     while( !todoNodes1.isEmpty() ) {
3425       HeapRegionNode hrn = todoNodes1.iterator().next();
3426       todoNodes1.remove( hrn );
3427       reachableNodes1.add(hrn);
3428
3429       Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
3430       while( edgeItr.hasNext() ) {
3431         ReferenceEdge edge = edgeItr.next();
3432
3433         if( !reachableNodes1.contains( edge.getDst() ) ) {
3434           todoNodes1.add( edge.getDst() );
3435         }
3436       }
3437     }
3438
3439     while( !todoNodes2.isEmpty() ) {
3440       HeapRegionNode hrn = todoNodes2.iterator().next();
3441       todoNodes2.remove( hrn );
3442       reachableNodes2.add(hrn);
3443
3444       Iterator<ReferenceEdge> edgeItr = hrn.iteratorToReferencees();
3445       while( edgeItr.hasNext() ) {
3446         ReferenceEdge edge = edgeItr.next();
3447
3448         if( !reachableNodes2.contains( edge.getDst() ) ) {
3449           todoNodes2.add( edge.getDst() );
3450         }
3451       }
3452     }
3453
3454     Set<HeapRegionNode> intersection =
3455       new HashSet<HeapRegionNode>( reachableNodes1 );
3456
3457     intersection.retainAll( reachableNodes2 );
3458
3459     return intersection;
3460   }
3461
3462
3463   // for writing ownership graphs to dot files
3464   public void writeGraph(MethodContext mc,
3465                          FlatNode fn,
3466                          boolean writeLabels,
3467                          boolean labelSelect,
3468                          boolean pruneGarbage,
3469                          boolean writeReferencers,
3470                          boolean writeParamMappings
3471                          ) throws java.io.IOException {
3472     writeGraph(
3473       mc.toString() +
3474       fn.toString(),
3475       writeLabels,
3476       labelSelect,
3477       pruneGarbage,
3478       writeReferencers,
3479       writeParamMappings
3480       );
3481   }
3482
3483   public void writeGraph(MethodContext mc,
3484                          boolean writeLabels,
3485                          boolean labelSelect,
3486                          boolean pruneGarbage,
3487                          boolean writeReferencers,
3488                          boolean writeParamMappings
3489                          ) throws java.io.IOException {
3490
3491     writeGraph(mc+"COMPLETE",
3492                writeLabels,
3493                labelSelect,
3494                pruneGarbage,
3495                writeReferencers,
3496                writeParamMappings
3497                );
3498   }
3499
3500   public void writeGraph(MethodContext mc,
3501                          Integer numUpdate,
3502                          boolean writeLabels,
3503                          boolean labelSelect,
3504                          boolean pruneGarbage,
3505                          boolean writeReferencers,
3506                          boolean writeParamMappings
3507                          ) throws java.io.IOException {
3508
3509
3510
3511     writeGraph(mc+"COMPLETE"+String.format("%05d", numUpdate),
3512                writeLabels,
3513                labelSelect,
3514                pruneGarbage,
3515                writeReferencers,
3516                writeParamMappings
3517                );
3518   }
3519
3520   public void writeGraph(String graphName,
3521                          boolean writeLabels,
3522                          boolean labelSelect,
3523                          boolean pruneGarbage,
3524                          boolean writeReferencers,
3525                          boolean writeParamMappings
3526                          ) throws java.io.IOException {
3527
3528     // remove all non-word characters from the graph name so
3529     // the filename and identifier in dot don't cause errors
3530     graphName = graphName.replaceAll("[\\W]", "");
3531
3532     BufferedWriter bw = new BufferedWriter(new FileWriter(graphName+".dot") );
3533     bw.write("digraph "+graphName+" {\n");
3534
3535     HashSet<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
3536
3537     // then visit every heap region node
3538     Set s = id2hrn.entrySet();
3539     Iterator i = s.iterator();
3540     while( i.hasNext() ) {
3541       Map.Entry me  = (Map.Entry)i.next();
3542       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3543
3544       if( !pruneGarbage ||
3545           (hrn.isFlagged() && hrn.getID() > 0) ||
3546           hrn.getDescription().startsWith("param")
3547           ) {
3548
3549         if( !visited.contains(hrn) ) {
3550           traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
3551                                   hrn,
3552                                   bw,
3553                                   null,
3554                                   visited,
3555                                   writeReferencers);
3556         }
3557       }
3558     }
3559
3560     bw.write("  graphTitle[label=\""+graphName+"\",shape=box];\n");
3561
3562     if( writeParamMappings ) {
3563       /*
3564       Set df = paramIndex2id.entrySet();
3565       Iterator ih = df.iterator();
3566       while( ih.hasNext() ) {
3567         Map.Entry meh = (Map.Entry)ih.next();
3568         Integer pi = (Integer) meh.getKey();
3569         Integer id = (Integer) meh.getValue();
3570         bw.write("  pindex"+pi+"[label=\""+pi+" to "+id+"\",shape=box];\n");
3571       }
3572       */
3573     }
3574
3575     // then visit every label node, useful for debugging
3576     if( writeLabels ) {
3577       s = td2ln.entrySet();
3578       i = s.iterator();
3579       while( i.hasNext() ) {
3580         Map.Entry me = (Map.Entry)i.next();
3581         LabelNode ln = (LabelNode) me.getValue();
3582
3583         if( labelSelect ) {
3584           String labelStr = ln.getTempDescriptorString();
3585           if( labelStr.startsWith("___temp") ||
3586               labelStr.startsWith("___dst") ||
3587               labelStr.startsWith("___srctmp") ||
3588               labelStr.startsWith("___neverused")   ) {
3589             continue;
3590           }
3591         }
3592
3593         //bw.write("  "+ln.toString() + ";\n");
3594
3595         Iterator<ReferenceEdge> heapRegionsItr = ln.iteratorToReferencees();
3596         while( heapRegionsItr.hasNext() ) {
3597           ReferenceEdge edge = heapRegionsItr.next();
3598           HeapRegionNode hrn  = edge.getDst();
3599
3600           if( pruneGarbage && !visited.contains(hrn) ) {
3601             traverseHeapRegionNodes(VISIT_HRN_WRITE_FULL,
3602                                     hrn,
3603                                     bw,
3604                                     null,
3605                                     visited,
3606                                     writeReferencers);
3607           }
3608
3609           bw.write("  "        + ln.toString() +
3610                    " -> "      + hrn.toString() +
3611                    "[label=\"" + edge.toGraphEdgeString() +
3612                    "\",decorate];\n");
3613         }
3614       }
3615     }
3616
3617
3618     bw.write("}\n");
3619     bw.close();
3620   }
3621
3622   protected void traverseHeapRegionNodes(int mode,
3623                                          HeapRegionNode hrn,
3624                                          BufferedWriter bw,
3625                                          TempDescriptor td,
3626                                          HashSet<HeapRegionNode> visited,
3627                                          boolean writeReferencers
3628                                          ) throws java.io.IOException {
3629
3630     if( visited.contains(hrn) ) {
3631       return;
3632     }
3633     visited.add(hrn);
3634
3635     switch( mode ) {
3636     case VISIT_HRN_WRITE_FULL:
3637
3638       String attributes = "[";
3639
3640       if( hrn.isSingleObject() ) {
3641         attributes += "shape=box";
3642       } else {
3643         attributes += "shape=Msquare";
3644       }
3645
3646       if( hrn.isFlagged() ) {
3647         attributes += ",style=filled,fillcolor=lightgrey";
3648       }
3649
3650       attributes += ",label=\"ID" +
3651                     hrn.getID()   +
3652                     "\\n";
3653
3654       if( hrn.getType() != null ) {
3655         attributes += hrn.getType() + "\\n";
3656       }
3657
3658       attributes += hrn.getDescription() +
3659                     "\\n"                +
3660                     hrn.getAlphaString() +
3661                     "\"]";
3662
3663       bw.write("  " + hrn.toString() + attributes + ";\n");
3664       break;
3665     }
3666
3667
3668     // useful for debugging
3669     // UNMAINTAINED
3670     /*
3671     if( writeReferencers ) {
3672       OwnershipNode onRef  = null;
3673       Iterator refItr = hrn.iteratorToReferencers();
3674       while( refItr.hasNext() ) {
3675         onRef = (OwnershipNode) refItr.next();
3676
3677         switch( mode ) {
3678         case VISIT_HRN_WRITE_FULL:
3679           bw.write("  "                    + hrn.toString() +
3680                    " -> "                  + onRef.toString() +
3681                    "[color=lightgray];\n");
3682           break;
3683         }
3684       }
3685     }
3686     */
3687
3688     Iterator<ReferenceEdge> childRegionsItr = hrn.iteratorToReferencees();
3689     while( childRegionsItr.hasNext() ) {
3690       ReferenceEdge edge     = childRegionsItr.next();
3691       HeapRegionNode hrnChild = edge.getDst();
3692
3693       switch( mode ) {
3694       case VISIT_HRN_WRITE_FULL:
3695         bw.write("  "        + hrn.toString() +
3696                  " -> "      + hrnChild.toString() +
3697                  "[label=\"" + edge.toGraphEdgeString() +
3698                  "\",decorate];\n");
3699         break;
3700       }
3701
3702       traverseHeapRegionNodes(mode,
3703                               hrnChild,
3704                               bw,
3705                               td,
3706                               visited,
3707                               writeReferencers);
3708     }
3709   }
3710 }