Robust/src/Analysis/Disjoint/ReachGraph.java

   1 package Analysis.Disjoint;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import Util.UtilAlgorithms;
   6 import java.util.*;
   7 import java.io.*;
   8
   9 public class ReachGraph {
  10
  11   // use to disable improvements for comparison
  12   protected static final boolean DISABLE_STRONG_UPDATES = false;
  13   protected static final boolean DISABLE_GLOBAL_SWEEP   = false;
  14
  15   // a special out-of-scope temp
  16   protected static final TempDescriptor tdReturn = new TempDescriptor( "_Return___" );
  17
  18   // some frequently used reachability constants
  19   protected static final ReachState rstateEmpty        = ReachState.factory();
  20   protected static final ReachSet   rsetEmpty          = ReachSet.factory();
  21   protected static final ReachSet   rsetWithEmptyState = Canonical.makePredsTrue(ReachSet.factory( rstateEmpty ));
  22
  23   // predicate constants
  24   protected static final ExistPred    predTrue   = ExistPred.factory(); // if no args, true
  25   protected static final ExistPredSet predsEmpty = ExistPredSet.factory();
  26   protected static final ExistPredSet predsTrue  = ExistPredSet.factory( predTrue );
  27
  28
  29   // from DisjointAnalysis for convenience
  30   protected static int      allocationDepth   = -1;
  31   protected static TypeUtil typeUtil          = null;
  32
  33
  34   // variable and heap region nodes indexed by unique ID
  35   public Hashtable<Integer,        HeapRegionNode> id2hrn;
  36   public Hashtable<TempDescriptor, VariableNode  > td2vn;
  37
  38   // convenient set of alloc sites for all heap regions
  39   // present in the graph without having to search
  40   public HashSet<AllocSite> allocSites;
  41
  42   public ReachGraph() {
  43     id2hrn     = new Hashtable<Integer,        HeapRegionNode>();
  44     td2vn      = new Hashtable<TempDescriptor, VariableNode  >();
  45     allocSites = new HashSet<AllocSite>();
  46   }
  47
  48
  49   // temp descriptors are globally unique and map to
  50   // exactly one variable node, easy
  51   protected VariableNode getVariableNodeFromTemp( TempDescriptor td ) {
  52     assert td != null;
  53
  54     if( !td2vn.containsKey( td ) ) {
  55       td2vn.put( td, new VariableNode( td ) );
  56     }
  57
  58     return td2vn.get( td );
  59   }
  60
  61   public boolean hasVariable( TempDescriptor td ) {
  62     return td2vn.containsKey( td );
  63   }
  64
  65
  66   // this suite of methods can be used to assert a
  67   // very important property of ReachGraph objects:
  68   // some element, HeapRegionNode, RefEdge etc.
  69   // should be referenced by at most ONE ReachGraph!!
  70   // If a heap region or edge or variable should be
  71   // in another graph, make a new object with
  72   // equivalent properties for a new graph
  73   public boolean belongsToThis( RefSrcNode rsn ) {
  74     if( rsn instanceof VariableNode ) {
  75       VariableNode vn = (VariableNode) rsn;
  76       return this.td2vn.get( vn.getTempDescriptor() ) == vn;
  77     }
  78     HeapRegionNode hrn = (HeapRegionNode) rsn;
  79     return this.id2hrn.get( hrn.getID() ) == hrn;
  80   }
  81
  82
  83
  84
  85
  86   // the reason for this method is to have the option
  87   // of creating new heap regions with specific IDs, or
  88   // duplicating heap regions with specific IDs (especially
  89   // in the merge() operation) or to create new heap
  90   // regions with a new unique ID
  91   protected HeapRegionNode
  92     createNewHeapRegionNode( Integer        id,
  93                              boolean        isSingleObject,
  94                              boolean        isNewSummary,
  95                              boolean        isFlagged,
  96                              boolean        isOutOfContext,
  97                              TypeDescriptor type,
  98                              AllocSite      allocSite,
  99                              ReachSet       inherent,
 100                              ReachSet       alpha,
 101                              ExistPredSet   preds,
 102                              String         description
 103                              ) {
 104
 105     boolean markForAnalysis = isFlagged;
 106
 107     TypeDescriptor typeToUse = null;
 108     if( allocSite != null ) {
 109       typeToUse = allocSite.getType();
 110       allocSites.add( allocSite );
 111     } else {
 112       typeToUse = type;
 113     }
 114
 115     if( allocSite != null && allocSite.getDisjointAnalysisId() != null ) {
 116       markForAnalysis = true;
 117     }
 118
 119
 120     if( allocSite == null ) {
 121       assert !markForAnalysis;
 122
 123     } else if( markForAnalysis != allocSite.getFlag() ) {
 124       assert false;
 125     }
 126
 127
 128     if( id == null ) {
 129       id = DisjointAnalysis.generateUniqueHeapRegionNodeID();
 130     }
 131
 132     if( inherent == null ) {
 133       if( markForAnalysis ) {
 134         inherent =
 135           Canonical.makePredsTrue(
 136                                   ReachSet.factory(
 137                                                    ReachState.factory(
 138                                                                       ReachTuple.factory( id,
 139                                                                                           !isSingleObject,
 140                                                                                           ReachTuple.ARITY_ONE,
 141                                                                                           false // out-of-context
 142                                                                                           )
 143                                                                       )
 144                                                    )
 145                                   );
 146       } else {
 147         inherent = rsetWithEmptyState;
 148       }
 149     }
 150
 151     if( alpha == null ) {
 152       alpha = inherent;
 153     }
 154
 155     assert preds != null;
 156
 157     HeapRegionNode hrn = new HeapRegionNode( id,
 158                                              isSingleObject,
 159                                              markForAnalysis,
 160                                              isNewSummary,
 161                                              isOutOfContext,
 162                                              typeToUse,
 163                                              allocSite,
 164                                              inherent,
 165                                              alpha,
 166                                              preds,
 167                                              description );
 168     id2hrn.put( id, hrn );
 169     return hrn;
 170   }
 171
 172
 173
 174   ////////////////////////////////////////////////
 175   //
 176   //  Low-level referencee and referencer methods
 177   //
 178   //  These methods provide the lowest level for
 179   //  creating references between reachability nodes
 180   //  and handling the details of maintaining both
 181   //  list of referencers and referencees.
 182   //
 183   ////////////////////////////////////////////////
 184   protected void addRefEdge( RefSrcNode     referencer,
 185                              HeapRegionNode referencee,
 186                              RefEdge        edge ) {
 187     assert referencer != null;
 188     assert referencee != null;
 189     assert edge       != null;
 190     assert edge.getSrc() == referencer;
 191     assert edge.getDst() == referencee;
 192     assert belongsToThis( referencer );
 193     assert belongsToThis( referencee );
 194
 195     // edges are getting added twice to graphs now, the
 196     // kind that should have abstract facts merged--use
 197     // this check to prevent that
 198     assert referencer.getReferenceTo( referencee,
 199                                       edge.getType(),
 200                                       edge.getField()
 201                                       ) == null;
 202
 203     referencer.addReferencee( edge );
 204     referencee.addReferencer( edge );
 205   }
 206
 207   protected void removeRefEdge( RefEdge e ) {
 208     removeRefEdge( e.getSrc(),
 209                    e.getDst(),
 210                    e.getType(),
 211                    e.getField() );
 212   }
 213
 214   protected void removeRefEdge( RefSrcNode     referencer,
 215                                 HeapRegionNode referencee,
 216                                 TypeDescriptor type,
 217                                 String         field ) {
 218     assert referencer != null;
 219     assert referencee != null;
 220
 221     RefEdge edge = referencer.getReferenceTo( referencee,
 222                                               type,
 223                                               field );
 224     assert edge != null;
 225     assert edge == referencee.getReferenceFrom( referencer,
 226                                                 type,
 227                                                 field );
 228
 229     referencer.removeReferencee( edge );
 230     referencee.removeReferencer( edge );
 231   }
 232
 233   protected void clearRefEdgesFrom( RefSrcNode     referencer,
 234                                     TypeDescriptor type,
 235                                     String         field,
 236                                     boolean        removeAll ) {
 237     assert referencer != null;
 238
 239     // get a copy of the set to iterate over, otherwise
 240     // we will be trying to take apart the set as we
 241     // are iterating over it, which won't work
 242     Iterator<RefEdge> i = referencer.iteratorToReferenceesClone();
 243     while( i.hasNext() ) {
 244       RefEdge edge = i.next();
 245
 246       if( removeAll                                          ||
 247           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 248         ){
 249
 250         HeapRegionNode referencee = edge.getDst();
 251
 252         removeRefEdge( referencer,
 253                        referencee,
 254                        edge.getType(),
 255                        edge.getField() );
 256       }
 257     }
 258   }
 259
 260   protected void clearRefEdgesTo( HeapRegionNode referencee,
 261                                   TypeDescriptor type,
 262                                   String         field,
 263                                   boolean        removeAll ) {
 264     assert referencee != null;
 265
 266     // get a copy of the set to iterate over, otherwise
 267     // we will be trying to take apart the set as we
 268     // are iterating over it, which won't work
 269     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 270     while( i.hasNext() ) {
 271       RefEdge edge = i.next();
 272
 273       if( removeAll                                          ||
 274           (edge.typeEquals( type ) && edge.fieldEquals( field ))
 275         ){
 276
 277         RefSrcNode referencer = edge.getSrc();
 278
 279         removeRefEdge( referencer,
 280                        referencee,
 281                        edge.getType(),
 282                        edge.getField() );
 283       }
 284     }
 285   }
 286
 287   protected void clearNonVarRefEdgesTo( HeapRegionNode referencee ) {
 288     assert referencee != null;
 289
 290     // get a copy of the set to iterate over, otherwise
 291     // we will be trying to take apart the set as we
 292     // are iterating over it, which won't work
 293     Iterator<RefEdge> i = referencee.iteratorToReferencersClone();
 294     while( i.hasNext() ) {
 295       RefEdge edge = i.next();
 296       RefSrcNode referencer = edge.getSrc();
 297       if( !(referencer instanceof VariableNode) ) {
 298         removeRefEdge( referencer,
 299                        referencee,
 300                        edge.getType(),
 301                        edge.getField() );
 302       }
 303     }
 304   }
 305
 306   // this is a common operation in many transfer functions: we want
 307   // to add an edge, but if there is already such an edge we should
 308   // merge the properties of the existing and the new edges
 309   protected void addEdgeOrMergeWithExisting( RefEdge edgeNew ) {
 310
 311     RefSrcNode src = edgeNew.getSrc();
 312     assert belongsToThis( src );
 313
 314     HeapRegionNode dst = edgeNew.getDst();
 315     assert belongsToThis( dst );
 316
 317     // look to see if an edge with same field exists
 318     // and merge with it, otherwise just add the edge
 319     RefEdge edgeExisting = src.getReferenceTo( dst,
 320                                                edgeNew.getType(),
 321                                                edgeNew.getField()
 322                                                );
 323
 324     if( edgeExisting != null ) {
 325       edgeExisting.setBeta(
 326                            Canonical.unionORpreds( edgeExisting.getBeta(),
 327                                                    edgeNew.getBeta()
 328                                                    )
 329                            );
 330       edgeExisting.setPreds(
 331                             Canonical.join( edgeExisting.getPreds(),
 332                                             edgeNew.getPreds()
 333                                             )
 334                             );
 335
 336     } else {
 337       addRefEdge( src, dst, edgeNew );
 338     }
 339   }
 340
 341
 342
 343   ////////////////////////////////////////////////////
 344   //
 345   //  Assignment Operation Methods
 346   //
 347   //  These methods are high-level operations for
 348   //  modeling program assignment statements using
 349   //  the low-level reference create/remove methods
 350   //  above.
 351   //
 352   ////////////////////////////////////////////////////
 353
 354   public void assignTempXEqualToTempY( TempDescriptor x,
 355                                        TempDescriptor y ) {
 356     assignTempXEqualToCastedTempY( x, y, null );
 357   }
 358
 359   public void assignTempXEqualToCastedTempY( TempDescriptor x,
 360                                              TempDescriptor y,
 361                                              TypeDescriptor tdCast ) {
 362
 363     VariableNode lnX = getVariableNodeFromTemp( x );
 364     VariableNode lnY = getVariableNodeFromTemp( y );
 365
 366     clearRefEdgesFrom( lnX, null, null, true );
 367
 368     // note it is possible that the types of temps in the
 369     // flat node to analyze will reveal that some typed
 370     // edges in the reachability graph are impossible
 371     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 372
 373     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 374     while( itrYhrn.hasNext() ) {
 375       RefEdge        edgeY      = itrYhrn.next();
 376       HeapRegionNode referencee = edgeY.getDst();
 377       RefEdge        edgeNew    = edgeY.copy();
 378
 379       if( !isSuperiorType( x.getType(), edgeY.getType() ) ) {
 380         impossibleEdges.add( edgeY );
 381         continue;
 382       }
 383
 384       edgeNew.setSrc( lnX );
 385
 386       if( tdCast == null ) {
 387         edgeNew.setType( mostSpecificType( y.getType(),
 388                                            edgeY.getType(),
 389                                            referencee.getType()
 390                                            )
 391                          );
 392       } else {
 393         edgeNew.setType( mostSpecificType( y.getType(),
 394                                            edgeY.getType(),
 395                                            referencee.getType(),
 396                                            tdCast
 397                                            )
 398                          );
 399       }
 400
 401       edgeNew.setField( null );
 402
 403       addRefEdge( lnX, referencee, edgeNew );
 404     }
 405
 406     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 407     while( itrImp.hasNext() ) {
 408       RefEdge edgeImp = itrImp.next();
 409       removeRefEdge( edgeImp );
 410     }
 411   }
 412
 413
 414   public void assignTempXEqualToTempYFieldF( TempDescriptor  x,
 415                                              TempDescriptor  y,
 416                                              FieldDescriptor f ) {
 417     VariableNode lnX = getVariableNodeFromTemp( x );
 418     VariableNode lnY = getVariableNodeFromTemp( y );
 419
 420     clearRefEdgesFrom( lnX, null, null, true );
 421
 422     // note it is possible that the types of temps in the
 423     // flat node to analyze will reveal that some typed
 424     // edges in the reachability graph are impossible
 425     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 426
 427     Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 428     while( itrYhrn.hasNext() ) {
 429       RefEdge        edgeY = itrYhrn.next();
 430       HeapRegionNode hrnY  = edgeY.getDst();
 431       ReachSet       betaY = edgeY.getBeta();
 432
 433       Iterator<RefEdge> itrHrnFhrn = hrnY.iteratorToReferencees();
 434       while( itrHrnFhrn.hasNext() ) {
 435         RefEdge        edgeHrn = itrHrnFhrn.next();
 436         HeapRegionNode hrnHrn  = edgeHrn.getDst();
 437         ReachSet       betaHrn = edgeHrn.getBeta();
 438
 439         // prune edges that are not a matching field
 440         if( edgeHrn.getType() != null &&
 441             !edgeHrn.getField().equals( f.getSymbol() )
 442             ) {
 443           continue;
 444         }
 445
 446         // check for impossible edges
 447         if( !isSuperiorType( x.getType(), edgeHrn.getType() ) ) {
 448           impossibleEdges.add( edgeHrn );
 449           continue;
 450         }
 451
 452         TypeDescriptor tdNewEdge =
 453           mostSpecificType( edgeHrn.getType(),
 454                             hrnHrn.getType()
 455                             );
 456
 457         RefEdge edgeNew = new RefEdge( lnX,
 458                                        hrnHrn,
 459                                        tdNewEdge,
 460                                        null,
 461                                        Canonical.intersection( betaY, betaHrn ),
 462                                        predsTrue
 463                                        );
 464
 465         addEdgeOrMergeWithExisting( edgeNew );
 466       }
 467     }
 468
 469     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 470     while( itrImp.hasNext() ) {
 471       RefEdge edgeImp = itrImp.next();
 472       removeRefEdge( edgeImp );
 473     }
 474
 475     // anytime you might remove edges between heap regions
 476     // you must global sweep to clean up broken reachability
 477     if( !impossibleEdges.isEmpty() ) {
 478       if( !DISABLE_GLOBAL_SWEEP ) {
 479         globalSweep();
 480       }
 481     }
 482   }
 483
 484
 485   public void assignTempXFieldFEqualToTempY( TempDescriptor  x,
 486                                              FieldDescriptor f,
 487                                              TempDescriptor  y ) {
 488
 489     VariableNode lnX = getVariableNodeFromTemp( x );
 490     VariableNode lnY = getVariableNodeFromTemp( y );
 491
 492     HashSet<HeapRegionNode> nodesWithNewAlpha = new HashSet<HeapRegionNode>();
 493     HashSet<RefEdge>        edgesWithNewBeta  = new HashSet<RefEdge>();
 494
 495     // note it is possible that the types of temps in the
 496     // flat node to analyze will reveal that some typed
 497     // edges in the reachability graph are impossible
 498     Set<RefEdge> impossibleEdges = new HashSet<RefEdge>();
 499
 500     // first look for possible strong updates and remove those edges
 501     boolean strongUpdate = false;
 502
 503     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 504     while( itrXhrn.hasNext() ) {
 505       RefEdge        edgeX = itrXhrn.next();
 506       HeapRegionNode hrnX  = edgeX.getDst();
 507
 508       // we can do a strong update here if one of two cases holds
 509       if( f != null &&
 510           f != DisjointAnalysis.getArrayField( f.getType() ) &&
 511           (   (hrnX.getNumReferencers()                         == 1) || // case 1
 512               (hrnX.isSingleObject() && lnX.getNumReferencees() == 1)    // case 2
 513               )
 514           ) {
 515         if( !DISABLE_STRONG_UPDATES ) {
 516           strongUpdate = true;
 517           clearRefEdgesFrom( hrnX, f.getType(), f.getSymbol(), false );
 518         }
 519       }
 520     }
 521
 522     // then do all token propagation
 523     itrXhrn = lnX.iteratorToReferencees();
 524     while( itrXhrn.hasNext() ) {
 525       RefEdge        edgeX = itrXhrn.next();
 526       HeapRegionNode hrnX  = edgeX.getDst();
 527       ReachSet       betaX = edgeX.getBeta();
 528       ReachSet       R     = Canonical.intersection( hrnX.getAlpha(),
 529                                                      edgeX.getBeta()
 530                                                      );
 531
 532       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 533       while( itrYhrn.hasNext() ) {
 534         RefEdge        edgeY = itrYhrn.next();
 535         HeapRegionNode hrnY  = edgeY.getDst();
 536         ReachSet       O     = edgeY.getBeta();
 537
 538         // check for impossible edges
 539         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 540           impossibleEdges.add( edgeY );
 541           continue;
 542         }
 543
 544         // propagate tokens over nodes starting from hrnSrc, and it will
 545         // take care of propagating back up edges from any touched nodes
 546         ChangeSet Cy = Canonical.unionUpArityToChangeSet( O, R );
 547         propagateTokensOverNodes( hrnY, Cy, nodesWithNewAlpha, edgesWithNewBeta );
 548
 549         // then propagate back just up the edges from hrn
 550         ChangeSet Cx = Canonical.unionUpArityToChangeSet( R, O );
 551         HashSet<RefEdge> todoEdges = new HashSet<RefEdge>();
 552
 553         Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
 554           new Hashtable<RefEdge, ChangeSet>();
 555
 556         Iterator<RefEdge> referItr = hrnX.iteratorToReferencers();
 557         while( referItr.hasNext() ) {
 558           RefEdge edgeUpstream = referItr.next();
 559           todoEdges.add( edgeUpstream );
 560           edgePlannedChanges.put( edgeUpstream, Cx );
 561         }
 562
 563         propagateTokensOverEdges( todoEdges,
 564                                   edgePlannedChanges,
 565                                   edgesWithNewBeta );
 566       }
 567     }
 568
 569
 570     // apply the updates to reachability
 571     Iterator<HeapRegionNode> nodeItr = nodesWithNewAlpha.iterator();
 572     while( nodeItr.hasNext() ) {
 573       nodeItr.next().applyAlphaNew();
 574     }
 575
 576     Iterator<RefEdge> edgeItr = edgesWithNewBeta.iterator();
 577     while( edgeItr.hasNext() ) {
 578       edgeItr.next().applyBetaNew();
 579     }
 580
 581
 582     // then go back through and add the new edges
 583     itrXhrn = lnX.iteratorToReferencees();
 584     while( itrXhrn.hasNext() ) {
 585       RefEdge        edgeX = itrXhrn.next();
 586       HeapRegionNode hrnX  = edgeX.getDst();
 587
 588       Iterator<RefEdge> itrYhrn = lnY.iteratorToReferencees();
 589       while( itrYhrn.hasNext() ) {
 590         RefEdge        edgeY = itrYhrn.next();
 591         HeapRegionNode hrnY  = edgeY.getDst();
 592
 593         // skip impossible edges here, we already marked them
 594         // when computing reachability propagations above
 595         if( !isSuperiorType( f.getType(), edgeY.getType() ) ) {
 596           continue;
 597         }
 598
 599         // prepare the new reference edge hrnX.f -> hrnY
 600         TypeDescriptor tdNewEdge =
 601           mostSpecificType( y.getType(),
 602                             edgeY.getType(),
 603                             hrnY.getType()
 604                             );
 605
 606         RefEdge edgeNew =
 607           new RefEdge( hrnX,
 608                        hrnY,
 609                        tdNewEdge,
 610                        f.getSymbol(),
 611                        Canonical.makePredsTrue(
 612                                                Canonical.pruneBy( edgeY.getBeta(),
 613                                                                   hrnX.getAlpha()
 614                                                                   )
 615                                                ),
 616                        predsTrue
 617                        );
 618
 619         addEdgeOrMergeWithExisting( edgeNew );
 620       }
 621     }
 622
 623     Iterator<RefEdge> itrImp = impossibleEdges.iterator();
 624     while( itrImp.hasNext() ) {
 625       RefEdge edgeImp = itrImp.next();
 626       removeRefEdge( edgeImp );
 627     }
 628
 629     // if there was a strong update, make sure to improve
 630     // reachability with a global sweep
 631     if( strongUpdate || !impossibleEdges.isEmpty() ) {
 632       if( !DISABLE_GLOBAL_SWEEP ) {
 633         globalSweep();
 634       }
 635     }
 636   }
 637
 638
 639   public void assignReturnEqualToTemp( TempDescriptor x ) {
 640
 641     VariableNode lnR = getVariableNodeFromTemp( tdReturn );
 642     VariableNode lnX = getVariableNodeFromTemp( x );
 643
 644     clearRefEdgesFrom( lnR, null, null, true );
 645
 646     Iterator<RefEdge> itrXhrn = lnX.iteratorToReferencees();
 647     while( itrXhrn.hasNext() ) {
 648       RefEdge        edgeX      = itrXhrn.next();
 649       HeapRegionNode referencee = edgeX.getDst();
 650       RefEdge        edgeNew    = edgeX.copy();
 651       edgeNew.setSrc( lnR );
 652
 653       addRefEdge( lnR, referencee, edgeNew );
 654     }
 655   }
 656
 657
 658   public void assignTempEqualToNewAlloc( TempDescriptor x,
 659                                          AllocSite      as ) {
 660     assert x  != null;
 661     assert as != null;
 662
 663     age( as );
 664
 665     // after the age operation the newest (or zero-ith oldest)
 666     // node associated with the allocation site should have
 667     // no references to it as if it were a newly allocated
 668     // heap region
 669     Integer        idNewest   = as.getIthOldest( 0 );
 670     HeapRegionNode hrnNewest  = id2hrn.get( idNewest );
 671     assert         hrnNewest != null;
 672
 673     VariableNode lnX = getVariableNodeFromTemp( x );
 674     clearRefEdgesFrom( lnX, null, null, true );
 675
 676     // make a new reference to allocated node
 677     TypeDescriptor type = as.getType();
 678
 679     RefEdge edgeNew =
 680       new RefEdge( lnX,                  // source
 681                    hrnNewest,            // dest
 682                    type,                 // type
 683                    null,                 // field name
 684                    hrnNewest.getAlpha(), // beta
 685                    predsTrue             // predicates
 686                    );
 687
 688     addRefEdge( lnX, hrnNewest, edgeNew );
 689   }
 690
 691
 692   // use the allocation site (unique to entire analysis) to
 693   // locate the heap region nodes in this reachability graph
 694   // that should be aged.  The process models the allocation
 695   // of new objects and collects all the oldest allocations
 696   // in a summary node to allow for a finite analysis
 697   //
 698   // There is an additional property of this method.  After
 699   // running it on a particular reachability graph (many graphs
 700   // may have heap regions related to the same allocation site)
 701   // the heap region node objects in this reachability graph will be
 702   // allocated.  Therefore, after aging a graph for an allocation
 703   // site, attempts to retrieve the heap region nodes using the
 704   // integer id's contained in the allocation site should always
 705   // return non-null heap regions.
 706   public void age( AllocSite as ) {
 707
 708     // keep track of allocation sites that are represented
 709     // in this graph for efficiency with other operations
 710     allocSites.add( as );
 711
 712     // if there is a k-th oldest node, it merges into
 713     // the summary node
 714     Integer idK = as.getOldest();
 715     if( id2hrn.containsKey( idK ) ) {
 716       HeapRegionNode hrnK = id2hrn.get( idK );
 717
 718       // retrieve the summary node, or make it
 719       // from scratch
 720       HeapRegionNode hrnSummary = getSummaryNode( as, false );
 721
 722       mergeIntoSummary( hrnK, hrnSummary );
 723     }
 724
 725     // move down the line of heap region nodes
 726     // clobbering the ith and transferring all references
 727     // to and from i-1 to node i.
 728     for( int i = allocationDepth - 1; i > 0; --i ) {
 729
 730       // only do the transfer if the i-1 node exists
 731       Integer idImin1th = as.getIthOldest( i - 1 );
 732       if( id2hrn.containsKey( idImin1th ) ) {
 733         HeapRegionNode hrnImin1 = id2hrn.get( idImin1th );
 734         if( hrnImin1.isWiped() ) {
 735           // there is no info on this node, just skip
 736           continue;
 737         }
 738
 739         // either retrieve or make target of transfer
 740         HeapRegionNode hrnI = getIthNode( as, i, false );
 741
 742         transferOnto( hrnImin1, hrnI );
 743       }
 744
 745     }
 746
 747     // as stated above, the newest node should have had its
 748     // references moved over to the second oldest, so we wipe newest
 749     // in preparation for being the new object to assign something to
 750     HeapRegionNode hrn0 = getIthNode( as, 0, false );
 751     wipeOut( hrn0, true );
 752
 753     // now tokens in reachability sets need to "age" also
 754     Iterator itrAllVariableNodes = td2vn.entrySet().iterator();
 755     while( itrAllVariableNodes.hasNext() ) {
 756       Map.Entry    me = (Map.Entry)    itrAllVariableNodes.next();
 757       VariableNode ln = (VariableNode) me.getValue();
 758
 759       Iterator<RefEdge> itrEdges = ln.iteratorToReferencees();
 760       while( itrEdges.hasNext() ) {
 761         ageTuplesFrom( as, itrEdges.next() );
 762       }
 763     }
 764
 765     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
 766     while( itrAllHRNodes.hasNext() ) {
 767       Map.Entry      me       = (Map.Entry)      itrAllHRNodes.next();
 768       HeapRegionNode hrnToAge = (HeapRegionNode) me.getValue();
 769
 770       ageTuplesFrom( as, hrnToAge );
 771
 772       Iterator<RefEdge> itrEdges = hrnToAge.iteratorToReferencees();
 773       while( itrEdges.hasNext() ) {
 774         ageTuplesFrom( as, itrEdges.next() );
 775       }
 776     }
 777
 778
 779     // after tokens have been aged, reset newest node's reachability
 780     // and a brand new node has a "true" predicate
 781     hrn0.setAlpha( hrn0.getInherent() );
 782     hrn0.setPreds( predsTrue );
 783   }
 784
 785
 786   // either retrieve or create the needed heap region node
 787   protected HeapRegionNode getSummaryNode( AllocSite as,
 788                                            boolean   shadow ) {
 789
 790     Integer idSummary;
 791     if( shadow ) {
 792       idSummary = as.getSummaryShadow();
 793     } else {
 794       idSummary = as.getSummary();
 795     }
 796
 797     HeapRegionNode hrnSummary = id2hrn.get( idSummary );
 798
 799     if( hrnSummary == null ) {
 800
 801       boolean hasFlags = false;
 802       if( as.getType().isClass() ) {
 803         hasFlags = as.getType().getClassDesc().hasFlags();
 804       }
 805
 806       if( as.getFlag() ){
 807         hasFlags = true;
 808       }
 809
 810       String strDesc = as.toStringForDOT()+"\\nsummary";
 811
 812       hrnSummary =
 813         createNewHeapRegionNode( idSummary,    // id or null to generate a new one
 814                                  false,        // single object?
 815                                  true,         // summary?
 816                                  hasFlags,     // flagged?
 817                                  false,        // out-of-context?
 818                                  as.getType(), // type
 819                                  as,           // allocation site
 820                                  null,         // inherent reach
 821                                  null,         // current reach
 822                                  predsEmpty,   // predicates
 823                                  strDesc       // description
 824                                  );
 825     }
 826
 827     return hrnSummary;
 828   }
 829
 830   // either retrieve or create the needed heap region node
 831   protected HeapRegionNode getIthNode( AllocSite as,
 832                                        Integer   i,
 833                                        boolean   shadow ) {
 834
 835     Integer idIth;
 836     if( shadow ) {
 837       idIth = as.getIthOldestShadow( i );
 838     } else {
 839       idIth = as.getIthOldest( i );
 840     }
 841
 842     HeapRegionNode hrnIth = id2hrn.get( idIth );
 843
 844     if( hrnIth == null ) {
 845
 846       boolean hasFlags = false;
 847       if( as.getType().isClass() ) {
 848         hasFlags = as.getType().getClassDesc().hasFlags();
 849       }
 850
 851       if( as.getFlag() ){
 852         hasFlags = true;
 853       }
 854
 855       String strDesc = as.toStringForDOT()+"\\n"+i+" oldest";
 856
 857       hrnIth = createNewHeapRegionNode( idIth,        // id or null to generate a new one
 858                                         true,         // single object?
 859                                         false,        // summary?
 860                                         hasFlags,     // flagged?
 861                                         false,        // out-of-context?
 862                                         as.getType(), // type
 863                                         as,           // allocation site
 864                                         null,         // inherent reach
 865                                         null,         // current reach
 866                                         predsEmpty,   // predicates
 867                                         strDesc       // description
 868                                         );
 869     }
 870
 871     return hrnIth;
 872   }
 873
 874
 875   protected void mergeIntoSummary( HeapRegionNode hrn,
 876                                    HeapRegionNode hrnSummary ) {
 877     assert hrnSummary.isNewSummary();
 878
 879     // assert that these nodes belong to THIS graph
 880     assert belongsToThis( hrn );
 881     assert belongsToThis( hrnSummary );
 882
 883     assert hrn != hrnSummary;
 884
 885     // transfer references _from_ hrn over to hrnSummary
 886     Iterator<RefEdge> itrReferencee = hrn.iteratorToReferencees();
 887     while( itrReferencee.hasNext() ) {
 888       RefEdge edge       = itrReferencee.next();
 889       RefEdge edgeMerged = edge.copy();
 890       edgeMerged.setSrc( hrnSummary );
 891
 892       HeapRegionNode hrnReferencee = edge.getDst();
 893       RefEdge        edgeSummary   =
 894         hrnSummary.getReferenceTo( hrnReferencee,
 895                                    edge.getType(),
 896                                    edge.getField()
 897                                    );
 898
 899       if( edgeSummary == null ) {
 900         // the merge is trivial, nothing to be done
 901         addRefEdge( hrnSummary, hrnReferencee, edgeMerged );
 902
 903       } else {
 904         // otherwise an edge from the referencer to hrnSummary exists already
 905         // and the edge referencer->hrn should be merged with it
 906         edgeSummary.setBeta(
 907                             Canonical.unionORpreds( edgeMerged.getBeta(),
 908                                              edgeSummary.getBeta()
 909                                              )
 910                              );
 911         edgeSummary.setPreds(
 912                              Canonical.join( edgeMerged.getPreds(),
 913                                              edgeSummary.getPreds()
 914                                              )
 915                               );
 916       }
 917     }
 918
 919     // next transfer references _to_ hrn over to hrnSummary
 920     Iterator<RefEdge> itrReferencer = hrn.iteratorToReferencers();
 921     while( itrReferencer.hasNext() ) {
 922       RefEdge edge         = itrReferencer.next();
 923       RefEdge edgeMerged   = edge.copy();
 924       edgeMerged.setDst( hrnSummary );
 925
 926       RefSrcNode onReferencer = edge.getSrc();
 927       RefEdge    edgeSummary  =
 928         onReferencer.getReferenceTo( hrnSummary,
 929                                      edge.getType(),
 930                                      edge.getField()
 931                                      );
 932
 933       if( edgeSummary == null ) {
 934         // the merge is trivial, nothing to be done
 935         addRefEdge( onReferencer, hrnSummary, edgeMerged );
 936
 937       } else {
 938         // otherwise an edge from the referencer to alpha_S exists already
 939         // and the edge referencer->alpha_K should be merged with it
 940         edgeSummary.setBeta(
 941                             Canonical.unionORpreds( edgeMerged.getBeta(),
 942                                              edgeSummary.getBeta()
 943                                              )
 944                              );
 945         edgeSummary.setPreds(
 946                              Canonical.join( edgeMerged.getPreds(),
 947                                              edgeSummary.getPreds()
 948                                              )
 949                               );
 950       }
 951     }
 952
 953     // then merge hrn reachability into hrnSummary
 954     hrnSummary.setAlpha(
 955                         Canonical.unionORpreds( hrnSummary.getAlpha(),
 956                                          hrn.getAlpha()
 957                                          )
 958                          );
 959
 960     hrnSummary.setPreds(
 961                         Canonical.join( hrnSummary.getPreds(),
 962                                         hrn.getPreds()
 963                                         )
 964                         );
 965
 966     // and afterward, this node is gone
 967     wipeOut( hrn, true );
 968   }
 969
 970
 971   protected void transferOnto( HeapRegionNode hrnA,
 972                                HeapRegionNode hrnB ) {
 973
 974     assert belongsToThis( hrnA );
 975     assert belongsToThis( hrnB );
 976     assert hrnA != hrnB;
 977
 978     // clear references in and out of node b?
 979     assert hrnB.isWiped();
 980
 981     // copy each: (edge in and out of A) to B
 982     Iterator<RefEdge> itrReferencee = hrnA.iteratorToReferencees();
 983     while( itrReferencee.hasNext() ) {
 984       RefEdge        edge          = itrReferencee.next();
 985       HeapRegionNode hrnReferencee = edge.getDst();
 986       RefEdge        edgeNew       = edge.copy();
 987       edgeNew.setSrc( hrnB );
 988       edgeNew.setDst( hrnReferencee );
 989
 990       addRefEdge( hrnB, hrnReferencee, edgeNew );
 991     }
 992
 993     Iterator<RefEdge> itrReferencer = hrnA.iteratorToReferencers();
 994     while( itrReferencer.hasNext() ) {
 995       RefEdge    edge          = itrReferencer.next();
 996       RefSrcNode rsnReferencer = edge.getSrc();
 997       RefEdge    edgeNew       = edge.copy();
 998       edgeNew.setSrc( rsnReferencer );
 999       edgeNew.setDst( hrnB );
1000
1001       addRefEdge( rsnReferencer, hrnB, edgeNew );
1002     }
1003
1004     // replace hrnB reachability and preds with hrnA's
1005     hrnB.setAlpha( hrnA.getAlpha() );
1006     hrnB.setPreds( hrnA.getPreds() );
1007
1008     // after transfer, wipe out source
1009     wipeOut( hrnA, true );
1010   }
1011
1012
1013   // the purpose of this method is to conceptually "wipe out"
1014   // a heap region from the graph--purposefully not called REMOVE
1015   // because the node is still hanging around in the graph, just
1016   // not mechanically connected or have any reach or predicate
1017   // information on it anymore--lots of ops can use this
1018   protected void wipeOut( HeapRegionNode hrn,
1019                           boolean        wipeVariableReferences ) {
1020
1021     assert belongsToThis( hrn );
1022
1023     clearRefEdgesFrom( hrn, null, null, true );
1024
1025     if( wipeVariableReferences ) {
1026       clearRefEdgesTo( hrn, null, null, true );
1027     } else {
1028       clearNonVarRefEdgesTo( hrn );
1029     }
1030
1031     hrn.setAlpha( rsetEmpty );
1032     hrn.setPreds( predsEmpty );
1033   }
1034
1035
1036   protected void ageTuplesFrom( AllocSite as, RefEdge edge ) {
1037     edge.setBeta(
1038                  Canonical.ageTuplesFrom( edge.getBeta(),
1039                                           as
1040                                           )
1041                   );
1042   }
1043
1044   protected void ageTuplesFrom( AllocSite as, HeapRegionNode hrn ) {
1045     hrn.setAlpha(
1046                  Canonical.ageTuplesFrom( hrn.getAlpha(),
1047                                           as
1048                                           )
1049                   );
1050   }
1051
1052
1053
1054   protected void propagateTokensOverNodes( HeapRegionNode          nPrime,
1055                                            ChangeSet               c0,
1056                                            HashSet<HeapRegionNode> nodesWithNewAlpha,
1057                                            HashSet<RefEdge>        edgesWithNewBeta ) {
1058
1059     HashSet<HeapRegionNode> todoNodes
1060       = new HashSet<HeapRegionNode>();
1061     todoNodes.add( nPrime );
1062
1063     HashSet<RefEdge> todoEdges
1064       = new HashSet<RefEdge>();
1065
1066     Hashtable<HeapRegionNode, ChangeSet> nodePlannedChanges
1067       = new Hashtable<HeapRegionNode, ChangeSet>();
1068     nodePlannedChanges.put( nPrime, c0 );
1069
1070     Hashtable<RefEdge, ChangeSet> edgePlannedChanges
1071       = new Hashtable<RefEdge, ChangeSet>();
1072
1073     // first propagate change sets everywhere they can go
1074     while( !todoNodes.isEmpty() ) {
1075       HeapRegionNode n = todoNodes.iterator().next();
1076       ChangeSet      C = nodePlannedChanges.get( n );
1077
1078       Iterator<RefEdge> referItr = n.iteratorToReferencers();
1079       while( referItr.hasNext() ) {
1080         RefEdge edge = referItr.next();
1081         todoEdges.add( edge );
1082
1083         if( !edgePlannedChanges.containsKey( edge ) ) {
1084           edgePlannedChanges.put( edge,
1085                                   ChangeSet.factory()
1086                                   );
1087         }
1088
1089         edgePlannedChanges.put( edge,
1090                                 Canonical.union( edgePlannedChanges.get( edge ),
1091                                                  C
1092                                                  )
1093                                 );
1094       }
1095
1096       Iterator<RefEdge> refeeItr = n.iteratorToReferencees();
1097       while( refeeItr.hasNext() ) {
1098         RefEdge        edgeF = refeeItr.next();
1099         HeapRegionNode m     = edgeF.getDst();
1100
1101         ChangeSet changesToPass = ChangeSet.factory();
1102
1103         Iterator<ChangeTuple> itrCprime = C.iterator();
1104         while( itrCprime.hasNext() ) {
1105           ChangeTuple c = itrCprime.next();
1106           if( edgeF.getBeta().containsIgnorePreds( c.getStateToMatch() )
1107               != null
1108               ) {
1109             changesToPass = Canonical.add( changesToPass, c );
1110           }
1111         }
1112
1113         if( !changesToPass.isEmpty() ) {
1114           if( !nodePlannedChanges.containsKey( m ) ) {
1115             nodePlannedChanges.put( m, ChangeSet.factory() );
1116           }
1117
1118           ChangeSet currentChanges = nodePlannedChanges.get( m );
1119
1120           if( !changesToPass.isSubset( currentChanges ) ) {
1121
1122             nodePlannedChanges.put( m,
1123                                     Canonical.union( currentChanges,
1124                                                      changesToPass
1125                                                      )
1126                                     );
1127             todoNodes.add( m );
1128           }
1129         }
1130       }
1131
1132       todoNodes.remove( n );
1133     }
1134
1135     // then apply all of the changes for each node at once
1136     Iterator itrMap = nodePlannedChanges.entrySet().iterator();
1137     while( itrMap.hasNext() ) {
1138       Map.Entry      me = (Map.Entry)      itrMap.next();
1139       HeapRegionNode n  = (HeapRegionNode) me.getKey();
1140       ChangeSet      C  = (ChangeSet)      me.getValue();
1141
1142       // this propagation step is with respect to one change,
1143       // so we capture the full change from the old alpha:
1144       ReachSet localDelta = Canonical.applyChangeSet( n.getAlpha(),
1145                                                       C,
1146                                                       true
1147                                                       );
1148       // but this propagation may be only one of many concurrent
1149       // possible changes, so keep a running union with the node's
1150       // partially updated new alpha set
1151       n.setAlphaNew( Canonical.unionORpreds( n.getAlphaNew(),
1152                                       localDelta
1153                                       )
1154                      );
1155
1156       nodesWithNewAlpha.add( n );
1157     }
1158
1159     propagateTokensOverEdges( todoEdges,
1160                               edgePlannedChanges,
1161                               edgesWithNewBeta
1162                               );
1163   }
1164
1165
1166   protected void propagateTokensOverEdges( HashSet  <RefEdge>            todoEdges,
1167                                            Hashtable<RefEdge, ChangeSet> edgePlannedChanges,
1168                                            HashSet  <RefEdge>            edgesWithNewBeta ) {
1169
1170     // first propagate all change tuples everywhere they can go
1171     while( !todoEdges.isEmpty() ) {
1172       RefEdge edgeE = todoEdges.iterator().next();
1173       todoEdges.remove( edgeE );
1174
1175       if( !edgePlannedChanges.containsKey( edgeE ) ) {
1176         edgePlannedChanges.put( edgeE,
1177                                 ChangeSet.factory()
1178                                 );
1179       }
1180
1181       ChangeSet C = edgePlannedChanges.get( edgeE );
1182
1183       ChangeSet changesToPass = ChangeSet.factory();
1184
1185       Iterator<ChangeTuple> itrC = C.iterator();
1186       while( itrC.hasNext() ) {
1187         ChangeTuple c = itrC.next();
1188         if( edgeE.getBeta().containsIgnorePreds( c.getStateToMatch() )
1189             != null
1190             ) {
1191           changesToPass = Canonical.add( changesToPass, c );
1192         }
1193       }
1194
1195       RefSrcNode rsn = edgeE.getSrc();
1196
1197       if( !changesToPass.isEmpty() && rsn instanceof HeapRegionNode ) {
1198         HeapRegionNode n = (HeapRegionNode) rsn;
1199
1200         Iterator<RefEdge> referItr = n.iteratorToReferencers();
1201         while( referItr.hasNext() ) {
1202           RefEdge edgeF = referItr.next();
1203
1204           if( !edgePlannedChanges.containsKey( edgeF ) ) {
1205             edgePlannedChanges.put( edgeF,
1206                                     ChangeSet.factory()
1207                                     );
1208           }
1209
1210           ChangeSet currentChanges = edgePlannedChanges.get( edgeF );
1211
1212           if( !changesToPass.isSubset( currentChanges ) ) {
1213             todoEdges.add( edgeF );
1214             edgePlannedChanges.put( edgeF,
1215                                     Canonical.union( currentChanges,
1216                                                      changesToPass
1217                                                      )
1218                                     );
1219           }
1220         }
1221       }
1222     }
1223
1224     // then apply all of the changes for each edge at once
1225     Iterator itrMap = edgePlannedChanges.entrySet().iterator();
1226     while( itrMap.hasNext() ) {
1227       Map.Entry me = (Map.Entry) itrMap.next();
1228       RefEdge   e  = (RefEdge)   me.getKey();
1229       ChangeSet C  = (ChangeSet) me.getValue();
1230
1231       // this propagation step is with respect to one change,
1232       // so we capture the full change from the old beta:
1233       ReachSet localDelta =
1234         Canonical.applyChangeSet( e.getBeta(),
1235                                   C,
1236                                   true
1237                                   );
1238
1239       // but this propagation may be only one of many concurrent
1240       // possible changes, so keep a running union with the edge's
1241       // partially updated new beta set
1242       e.setBetaNew( Canonical.unionORpreds( e.getBetaNew(),
1243                                      localDelta
1244                                      )
1245                     );
1246
1247       edgesWithNewBeta.add( e );
1248     }
1249   }
1250
1251
1252   // used in makeCalleeView below to decide if there is
1253   // already an appropriate out-of-context edge in a callee
1254   // view graph for merging, or null if a new one will be added
1255   protected RefEdge
1256     getOutOfContextReferenceTo( HeapRegionNode hrn,
1257                                 TypeDescriptor srcType,
1258                                 TypeDescriptor refType,
1259                                 String         refField ) {
1260     assert belongsToThis( hrn );
1261
1262     HeapRegionNode hrnInContext = id2hrn.get( hrn.getID() );
1263     if( hrnInContext == null ) {
1264       return null;
1265     }
1266
1267     Iterator<RefEdge> refItr = hrnInContext.iteratorToReferencers();
1268     while( refItr.hasNext() ) {
1269       RefEdge re = refItr.next();
1270
1271       assert belongsToThis( re.getSrc() );
1272       assert belongsToThis( re.getDst() );
1273
1274       if( !(re.getSrc() instanceof HeapRegionNode) ) {
1275         continue;
1276       }
1277
1278       HeapRegionNode hrnSrc = (HeapRegionNode) re.getSrc();
1279       if( !hrnSrc.isOutOfContext() ) {
1280         continue;
1281       }
1282
1283       if( srcType == null ) {
1284         if( hrnSrc.getType() != null ) {
1285           continue;
1286         }
1287       } else {
1288         if( !srcType.equals( hrnSrc.getType() ) ) {
1289           continue;
1290         }
1291       }
1292
1293       if( !re.typeEquals( refType ) ) {
1294         continue;
1295       }
1296
1297       if( !re.fieldEquals( refField ) ) {
1298         continue;
1299       }
1300
1301       // tada!  We found it!
1302       return re;
1303     }
1304
1305     return null;
1306   }
1307
1308   // used below to convert a ReachSet to its callee-context
1309   // equivalent with respect to allocation sites in this graph
1310   protected ReachSet toCalleeContext( ReachSet      rs,
1311                                       ExistPredSet  preds,
1312                                       Set<HrnIdOoc> oocHrnIdOoc2callee
1313                                       ) {
1314     ReachSet out = ReachSet.factory();
1315
1316     Iterator<ReachState> itr = rs.iterator();
1317     while( itr.hasNext() ) {
1318       ReachState stateCaller = itr.next();
1319
1320       ReachState stateCallee = stateCaller;
1321
1322       Iterator<AllocSite> asItr = allocSites.iterator();
1323       while( asItr.hasNext() ) {
1324         AllocSite as = asItr.next();
1325
1326         ReachState stateNew = ReachState.factory();
1327         Iterator<ReachTuple> rtItr = stateCallee.iterator();
1328         while( rtItr.hasNext() ) {
1329           ReachTuple rt = rtItr.next();
1330
1331           // only translate this tuple if it is
1332           // in the out-callee-context bag
1333           HrnIdOoc hio = new HrnIdOoc( rt.getHrnID(),
1334                                        rt.isOutOfContext()
1335                                        );
1336           if( !oocHrnIdOoc2callee.contains( hio ) ) {
1337             stateNew = Canonical.add( stateNew, rt );
1338             continue;
1339           }
1340
1341           int age = as.getAgeCategory( rt.getHrnID() );
1342
1343           // this is the current mapping, where 0, 1, 2S were allocated
1344           // in the current context, 0?, 1? and 2S? were allocated in a
1345           // previous context, and we're translating to a future context
1346           //
1347           // 0    -> 0?
1348           // 1    -> 1?
1349           // 2S   -> 2S?
1350           // 2S*  -> 2S?*
1351           //
1352           // 0?   -> 2S?
1353           // 1?   -> 2S?
1354           // 2S?  -> 2S?
1355           // 2S?* -> 2S?*
1356
1357           if( age == AllocSite.AGE_notInThisSite ) {
1358             // things not from the site just go back in
1359             stateNew = Canonical.add( stateNew, rt );
1360
1361           } else if( age == AllocSite.AGE_summary ||
1362                      rt.isOutOfContext()
1363                      ) {
1364             // the in-context summary and all existing out-of-context
1365             // stuff all become
1366             stateNew = Canonical.add( stateNew,
1367                                       ReachTuple.factory( as.getSummary(),
1368                                                           true, // multi
1369                                                           rt.getArity(),
1370                                                           true  // out-of-context
1371                                                           )
1372                                       );
1373           } else {
1374             // otherwise everything else just goes to an out-of-context
1375             // version, everything else the same
1376             Integer I = as.getAge( rt.getHrnID() );
1377             assert I != null;
1378
1379             assert !rt.isMultiObject();
1380
1381             stateNew = Canonical.add( stateNew,
1382                                       ReachTuple.factory( rt.getHrnID(),
1383                                                           rt.isMultiObject(),
1384                                                           rt.getArity(),
1385                                                           true  // out-of-context
1386                                                           )
1387                                       );
1388           }
1389         }
1390
1391         stateCallee = stateNew;
1392       }
1393
1394       // attach the passed in preds
1395       stateCallee = Canonical.attach( stateCallee,
1396                                       preds );
1397
1398       out = Canonical.add( out,
1399                            stateCallee
1400                            );
1401
1402     }
1403     assert out.isCanonical();
1404     return out;
1405   }
1406
1407   // used below to convert a ReachSet to its caller-context
1408   // equivalent with respect to allocation sites in this graph
1409   protected ReachSet
1410     toCallerContext( ReachSet                            rs,
1411                      Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied
1412                      ) {
1413     ReachSet out = ReachSet.factory();
1414
1415     Iterator<ReachState> itr = rs.iterator();
1416     while( itr.hasNext() ) {
1417       ReachState stateCallee = itr.next();
1418
1419       if( calleeStatesSatisfied.containsKey( stateCallee ) ) {
1420
1421         // starting from one callee state...
1422         ReachSet rsCaller = ReachSet.factory( stateCallee );
1423
1424         // possibly branch it into many states, which any
1425         // allocation site might do, so lots of derived states
1426         Iterator<AllocSite> asItr = allocSites.iterator();
1427         while( asItr.hasNext() ) {
1428           AllocSite as = asItr.next();
1429           rsCaller = Canonical.toCallerContext( rsCaller, as );
1430         }
1431
1432         // then before adding each derived, now caller-context
1433         // states to the output, attach the appropriate pred
1434         // based on the source callee state
1435         Iterator<ReachState> stateItr = rsCaller.iterator();
1436         while( stateItr.hasNext() ) {
1437           ReachState stateCaller = stateItr.next();
1438           stateCaller = Canonical.attach( stateCaller,
1439                                           calleeStatesSatisfied.get( stateCallee )
1440                                           );
1441           out = Canonical.add( out,
1442                                stateCaller
1443                                );
1444         }
1445       }
1446     }
1447
1448     assert out.isCanonical();
1449     return out;
1450   }
1451
1452   // used below to convert a ReachSet to an equivalent
1453   // version with shadow IDs merged into unshadowed IDs
1454   protected ReachSet unshadow( ReachSet rs ) {
1455     ReachSet out = rs;
1456     Iterator<AllocSite> asItr = allocSites.iterator();
1457     while( asItr.hasNext() ) {
1458       AllocSite as = asItr.next();
1459       out = Canonical.unshadow( out, as );
1460     }
1461     assert out.isCanonical();
1462     return out;
1463   }
1464
1465
1466   // use this method to make a new reach graph that is
1467   // what heap the FlatMethod callee from the FlatCall
1468   // would start with reaching from its arguments in
1469   // this reach graph
1470   public ReachGraph
1471     makeCalleeView( FlatCall     fc,
1472                     FlatMethod   fmCallee,
1473                     Set<Integer> callerNodeIDsCopiedToCallee,
1474                     boolean      writeDebugDOTs
1475                     ) {
1476
1477
1478     // first traverse this context to find nodes and edges
1479     //  that will be callee-reachable
1480     Set<HeapRegionNode> reachableCallerNodes =
1481       new HashSet<HeapRegionNode>();
1482
1483     // caller edges between callee-reachable nodes
1484     Set<RefEdge> reachableCallerEdges =
1485       new HashSet<RefEdge>();
1486
1487     // caller edges from arg vars, and the matching param index
1488     // because these become a special edge in callee
1489     Hashtable<RefEdge, Integer> reachableCallerArgEdges2paramIndex =
1490       new Hashtable<RefEdge, Integer>();
1491
1492     // caller edges from local vars or callee-unreachable nodes
1493     // (out-of-context sources) to callee-reachable nodes
1494     Set<RefEdge> oocCallerEdges =
1495       new HashSet<RefEdge>();
1496
1497
1498     for( int i = 0; i < fmCallee.numParameters(); ++i ) {
1499
1500       TempDescriptor tdArg = fc.getArgMatchingParamIndex( fmCallee, i );
1501       VariableNode vnArgCaller = this.getVariableNodeFromTemp( tdArg );
1502
1503       Set<RefSrcNode> toVisitInCaller = new HashSet<RefSrcNode>();
1504       Set<RefSrcNode> visitedInCaller = new HashSet<RefSrcNode>();
1505
1506       toVisitInCaller.add( vnArgCaller );
1507
1508       while( !toVisitInCaller.isEmpty() ) {
1509         RefSrcNode rsnCaller = toVisitInCaller.iterator().next();
1510         toVisitInCaller.remove( rsnCaller );
1511         visitedInCaller.add( rsnCaller );
1512
1513         Iterator<RefEdge> itrRefEdges = rsnCaller.iteratorToReferencees();
1514         while( itrRefEdges.hasNext() ) {
1515           RefEdge        reCaller  = itrRefEdges.next();
1516           HeapRegionNode hrnCaller = reCaller.getDst();
1517
1518           callerNodeIDsCopiedToCallee.add( hrnCaller.getID() );
1519           reachableCallerNodes.add( hrnCaller );
1520
1521           if( reCaller.getSrc() instanceof HeapRegionNode ) {
1522             reachableCallerEdges.add( reCaller );
1523           } else {
1524             if( rsnCaller.equals( vnArgCaller ) ) {
1525               reachableCallerArgEdges2paramIndex.put( reCaller, i );
1526             } else {
1527               oocCallerEdges.add( reCaller );
1528             }
1529           }
1530
1531           if( !visitedInCaller.contains( hrnCaller ) ) {
1532             toVisitInCaller.add( hrnCaller );
1533           }
1534
1535         } // end edge iteration
1536       } // end visiting heap nodes in caller
1537     } // end iterating over parameters as starting points
1538
1539
1540     // now collect out-of-callee-context IDs and
1541     // map them to whether the ID is out of the caller
1542     // context as well
1543     Set<HrnIdOoc> oocHrnIdOoc2callee = new HashSet<HrnIdOoc>();
1544
1545     Iterator<Integer> itrInContext =
1546       callerNodeIDsCopiedToCallee.iterator();
1547     while( itrInContext.hasNext() ) {
1548       Integer        hrnID                 = itrInContext.next();
1549       HeapRegionNode hrnCallerAndInContext = id2hrn.get( hrnID );
1550
1551       Iterator<RefEdge> itrMightCross =
1552         hrnCallerAndInContext.iteratorToReferencers();
1553       while( itrMightCross.hasNext() ) {
1554         RefEdge edgeMightCross = itrMightCross.next();
1555
1556         RefSrcNode rsnCallerAndOutContext =
1557           edgeMightCross.getSrc();
1558
1559         if( rsnCallerAndOutContext instanceof VariableNode ) {
1560           // variables do not have out-of-context reach states,
1561           // so jump out now
1562           oocCallerEdges.add( edgeMightCross );
1563           continue;
1564         }
1565
1566         HeapRegionNode hrnCallerAndOutContext =
1567           (HeapRegionNode) rsnCallerAndOutContext;
1568
1569         // is this source node out-of-context?
1570         if( callerNodeIDsCopiedToCallee.contains( hrnCallerAndOutContext.getID() ) ) {
1571           // no, skip this edge
1572           continue;
1573         }
1574
1575         // okay, we got one
1576         oocCallerEdges.add( edgeMightCross );
1577
1578         // add all reach tuples on the node to list
1579         // of things that are out-of-context: insight
1580         // if this node is reachable from someting that WAS
1581         // in-context, then this node should already be in-context
1582         Iterator<ReachState> stateItr = hrnCallerAndOutContext.getAlpha().iterator();
1583         while( stateItr.hasNext() ) {
1584           ReachState state = stateItr.next();
1585
1586           Iterator<ReachTuple> rtItr = state.iterator();
1587           while( rtItr.hasNext() ) {
1588             ReachTuple rt = rtItr.next();
1589
1590             oocHrnIdOoc2callee.add( new HrnIdOoc( rt.getHrnID(),
1591                                                   rt.isOutOfContext()
1592                                                   )
1593                                     );
1594           }
1595         }
1596       }
1597     }
1598
1599     // the callee view is a new graph: DON'T MODIFY *THIS* graph
1600     ReachGraph rg = new ReachGraph();
1601
1602     // add nodes to callee graph
1603     Iterator<HeapRegionNode> hrnItr = reachableCallerNodes.iterator();
1604     while( hrnItr.hasNext() ) {
1605       HeapRegionNode hrnCaller = hrnItr.next();
1606
1607       assert callerNodeIDsCopiedToCallee.contains( hrnCaller.getID() );
1608       assert !rg.id2hrn.containsKey( hrnCaller.getID() );
1609
1610       ExistPred    pred  = ExistPred.factory( hrnCaller.getID(), null );
1611       ExistPredSet preds = ExistPredSet.factory( pred );
1612
1613       rg.createNewHeapRegionNode( hrnCaller.getID(),
1614                                   hrnCaller.isSingleObject(),
1615                                   hrnCaller.isNewSummary(),
1616                                   hrnCaller.isFlagged(),
1617                                   false, // out-of-context?
1618                                   hrnCaller.getType(),
1619                                   hrnCaller.getAllocSite(),
1620                                   toCalleeContext( hrnCaller.getInherent(),
1621                                                    preds,
1622                                                    oocHrnIdOoc2callee
1623                                                    ),
1624                                   toCalleeContext( hrnCaller.getAlpha(),
1625                                                    preds,
1626                                                    oocHrnIdOoc2callee
1627                                                    ),
1628                                   preds,
1629                                   hrnCaller.getDescription()
1630                                   );
1631     }
1632
1633     // add param edges to callee graph
1634     Iterator argEdges =
1635       reachableCallerArgEdges2paramIndex.entrySet().iterator();
1636     while( argEdges.hasNext() ) {
1637       Map.Entry me    = (Map.Entry) argEdges.next();
1638       RefEdge   reArg = (RefEdge)   me.getKey();
1639       Integer   index = (Integer)   me.getValue();
1640
1641       TempDescriptor arg = fmCallee.getParameter( index );
1642
1643       VariableNode vnCallee =
1644         rg.getVariableNodeFromTemp( arg );
1645
1646       HeapRegionNode hrnDstCaller = reArg.getDst();
1647       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1648       assert hrnDstCallee != null;
1649
1650       ExistPred pred =
1651         ExistPred.factory( arg,
1652                            null,
1653                            hrnDstCallee.getID(),
1654                            reArg.getType(),
1655                            reArg.getField(),
1656                            null,
1657                            true,  // out-of-callee-context
1658                            false  // out-of-caller-context
1659                            );
1660
1661       ExistPredSet preds =
1662         ExistPredSet.factory( pred );
1663
1664       RefEdge reCallee =
1665         new RefEdge( vnCallee,
1666                      hrnDstCallee,
1667                      reArg.getType(),
1668                      reArg.getField(),
1669                      toCalleeContext( reArg.getBeta(),
1670                                       preds,
1671                                       oocHrnIdOoc2callee
1672                                       ),
1673                      preds
1674                      );
1675
1676       rg.addRefEdge( vnCallee,
1677                      hrnDstCallee,
1678                      reCallee
1679                      );
1680     }
1681
1682     // add in-context edges to callee graph
1683     Iterator<RefEdge> reItr = reachableCallerEdges.iterator();
1684     while( reItr.hasNext() ) {
1685       RefEdge    reCaller  = reItr.next();
1686       RefSrcNode rsnCaller = reCaller.getSrc();
1687       assert rsnCaller instanceof HeapRegionNode;
1688       HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1689       HeapRegionNode hrnDstCaller = reCaller.getDst();
1690
1691       HeapRegionNode hrnSrcCallee = rg.id2hrn.get( hrnSrcCaller.getID() );
1692       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1693       assert hrnSrcCallee != null;
1694       assert hrnDstCallee != null;
1695
1696       ExistPred pred =
1697         ExistPred.factory( null,
1698                            hrnSrcCallee.getID(),
1699                            hrnDstCallee.getID(),
1700                            reCaller.getType(),
1701                            reCaller.getField(),
1702                            null,
1703                            false, // out-of-callee-context
1704                            false  // out-of-caller-context
1705                            );
1706
1707       ExistPredSet preds =
1708         ExistPredSet.factory( pred );
1709
1710       RefEdge reCallee =
1711         new RefEdge( hrnSrcCallee,
1712                      hrnDstCallee,
1713                      reCaller.getType(),
1714                      reCaller.getField(),
1715                      toCalleeContext( reCaller.getBeta(),
1716                                       preds,
1717                                       oocHrnIdOoc2callee
1718                                       ),
1719                      preds
1720                      );
1721
1722       rg.addRefEdge( hrnSrcCallee,
1723                      hrnDstCallee,
1724                      reCallee
1725                      );
1726     }
1727
1728     // add out-of-context edges to callee graph
1729     reItr = oocCallerEdges.iterator();
1730     while( reItr.hasNext() ) {
1731       RefEdge        reCaller     = reItr.next();
1732       RefSrcNode     rsnCaller    = reCaller.getSrc();
1733       HeapRegionNode hrnDstCaller = reCaller.getDst();
1734       HeapRegionNode hrnDstCallee = rg.id2hrn.get( hrnDstCaller.getID() );
1735       assert hrnDstCallee != null;
1736
1737       TypeDescriptor oocNodeType;
1738       ReachSet       oocReach;
1739       TempDescriptor oocPredSrcTemp = null;
1740       Integer        oocPredSrcID   = null;
1741       boolean        outOfCalleeContext;
1742       boolean        outOfCallerContext;
1743
1744       if( rsnCaller instanceof VariableNode ) {
1745         VariableNode vnCaller = (VariableNode) rsnCaller;
1746         oocNodeType    = null;
1747         oocReach       = rsetEmpty;
1748         oocPredSrcTemp = vnCaller.getTempDescriptor();
1749         outOfCalleeContext = true;
1750         outOfCallerContext = false;
1751
1752       } else {
1753         HeapRegionNode hrnSrcCaller = (HeapRegionNode) rsnCaller;
1754         assert !callerNodeIDsCopiedToCallee.contains( hrnSrcCaller.getID() );
1755         oocNodeType  = hrnSrcCaller.getType();
1756         oocReach     = hrnSrcCaller.getAlpha();
1757         oocPredSrcID = hrnSrcCaller.getID();
1758         if( hrnSrcCaller.isOutOfContext() ) {
1759           outOfCalleeContext = false;
1760           outOfCallerContext = true;
1761         } else {
1762           outOfCalleeContext = true;
1763           outOfCallerContext = false;
1764         }
1765       }
1766
1767       ExistPred pred =
1768         ExistPred.factory( oocPredSrcTemp,
1769                            oocPredSrcID,
1770                            hrnDstCallee.getID(),
1771                            reCaller.getType(),
1772                            reCaller.getField(),
1773                            null,
1774                            outOfCalleeContext,
1775                            outOfCallerContext
1776                            );
1777
1778       ExistPredSet preds =
1779         ExistPredSet.factory( pred );
1780
1781       RefEdge oocEdgeExisting =
1782         rg.getOutOfContextReferenceTo( hrnDstCallee,
1783                                        oocNodeType,
1784                                        reCaller.getType(),
1785                                        reCaller.getField()
1786                                        );
1787
1788       if( oocEdgeExisting == null ) {
1789           // for consistency, map one out-of-context "identifier"
1790           // to one heap region node id, otherwise no convergence
1791         String oocid = "oocid"+
1792           fmCallee+
1793           hrnDstCallee.getIDString()+
1794           oocNodeType+
1795           reCaller.getType()+
1796           reCaller.getField();
1797
1798         Integer oocHrnID = oocid2hrnid.get( oocid );
1799
1800         HeapRegionNode hrnCalleeAndOutContext;
1801
1802         if( oocHrnID == null ) {
1803
1804           hrnCalleeAndOutContext =
1805             rg.createNewHeapRegionNode( null,  // ID
1806                                         false, // single object?
1807                                         false, // new summary?
1808                                         false, // flagged?
1809                                         true,  // out-of-context?
1810                                         oocNodeType,
1811                                         null,  // alloc site, shouldn't be used
1812                                         toCalleeContext( oocReach,
1813                                                          preds,
1814                                                          oocHrnIdOoc2callee
1815                                                          ),
1816                                         toCalleeContext( oocReach,
1817                                                          preds,
1818                                                          oocHrnIdOoc2callee
1819                                                          ),
1820                                         preds,
1821                                         "out-of-context"
1822                                         );
1823
1824           oocid2hrnid.put( oocid, hrnCalleeAndOutContext.getID() );
1825
1826         } else {
1827
1828           // the mapping already exists, so see if node is there
1829           hrnCalleeAndOutContext = rg.id2hrn.get( oocHrnID );
1830
1831           if( hrnCalleeAndOutContext == null ) {
1832             // nope, make it
1833             hrnCalleeAndOutContext =
1834               rg.createNewHeapRegionNode( oocHrnID,  // ID
1835                                           false, // single object?
1836                                           false, // new summary?
1837                                           false, // flagged?
1838                                           true,  // out-of-context?
1839                                           oocNodeType,
1840                                           null,  // alloc site, shouldn't be used
1841                                           toCalleeContext( oocReach,
1842                                                            preds,
1843                                                            oocHrnIdOoc2callee
1844                                                            ),
1845                                           toCalleeContext( oocReach,
1846                                                            preds,
1847                                                            oocHrnIdOoc2callee
1848                                                            ),
1849                                           preds,
1850                                           "out-of-context"
1851                                           );
1852
1853           } else {
1854             // otherwise it is there, so merge reachability
1855             hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1856                                                                      toCalleeContext( oocReach,
1857                                                                                       preds,
1858                                                                                       oocHrnIdOoc2callee
1859                                                                                       )
1860                                                                      )
1861                                              );
1862           }
1863         }
1864
1865         assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1866
1867         rg.addRefEdge( hrnCalleeAndOutContext,
1868                        hrnDstCallee,
1869                        new RefEdge( hrnCalleeAndOutContext,
1870                                     hrnDstCallee,
1871                                     reCaller.getType(),
1872                                     reCaller.getField(),
1873                                     toCalleeContext( reCaller.getBeta(),
1874                                                      preds,
1875                                                      oocHrnIdOoc2callee
1876                                                      ),
1877                                     preds
1878                                     )
1879                        );
1880
1881         } else {
1882         // the out-of-context edge already exists
1883         oocEdgeExisting.setBeta( Canonical.unionORpreds( oocEdgeExisting.getBeta(),
1884                                                          toCalleeContext( reCaller.getBeta(),
1885                                                                           preds,
1886                                                                           oocHrnIdOoc2callee
1887                                                                           )
1888                                                   )
1889                                  );
1890
1891         oocEdgeExisting.setPreds( Canonical.join( oocEdgeExisting.getPreds(),
1892                                                   preds
1893                                                   )
1894                                   );
1895
1896         HeapRegionNode hrnCalleeAndOutContext =
1897           (HeapRegionNode) oocEdgeExisting.getSrc();
1898         hrnCalleeAndOutContext.setAlpha( Canonical.unionORpreds( hrnCalleeAndOutContext.getAlpha(),
1899                                                                  toCalleeContext( oocReach,
1900                                                                                   preds,
1901                                                                                   oocHrnIdOoc2callee
1902                                                                                   )
1903                                                                  )
1904                                          );
1905
1906         assert hrnCalleeAndOutContext.reachHasOnlyOOC();
1907       }
1908     }
1909
1910
1911     if( writeDebugDOTs ) {
1912       debugGraphPrefix = String.format( "call%02d", debugCallSiteVisits );
1913       rg.writeGraph( debugGraphPrefix+"calleeview",
1914                      resolveMethodDebugDOTwriteLabels,
1915                      resolveMethodDebugDOTselectTemps,
1916                      resolveMethodDebugDOTpruneGarbage,
1917                      resolveMethodDebugDOThideSubsetReach,
1918                      resolveMethodDebugDOThideEdgeTaints );
1919     }
1920
1921     return rg;
1922   }
1923
1924   private static Hashtable<String, Integer> oocid2hrnid =
1925     new Hashtable<String, Integer>();
1926
1927
1928   // useful since many graphs writes in the method call debug code
1929   private static boolean resolveMethodDebugDOTwriteLabels     = true;
1930   private static boolean resolveMethodDebugDOTselectTemps     = true;
1931   private static boolean resolveMethodDebugDOTpruneGarbage    = true;
1932   private static boolean resolveMethodDebugDOThideSubsetReach = false;
1933   private static boolean resolveMethodDebugDOThideEdgeTaints  = true;
1934
1935   static String debugGraphPrefix;
1936   static int debugCallSiteVisits = 0;
1937   static int debugCallSiteVisitsUntilExit = 0;
1938
1939
1940   public void
1941     resolveMethodCall( FlatCall     fc,
1942                        FlatMethod   fmCallee,
1943                        ReachGraph   rgCallee,
1944                        Set<Integer> callerNodeIDsCopiedToCallee,
1945                        boolean      writeDebugDOTs
1946                        ) {
1947
1948     if( writeDebugDOTs ) {
1949       System.out.println( "  Writing out visit "+
1950                           debugCallSiteVisits+
1951                           " to debug call site" );
1952
1953       debugGraphPrefix = String.format( "call%02d",
1954                                         debugCallSiteVisits );
1955
1956       rgCallee.writeGraph( debugGraphPrefix+"callee",
1957                            resolveMethodDebugDOTwriteLabels,
1958                            resolveMethodDebugDOTselectTemps,
1959                            resolveMethodDebugDOTpruneGarbage,
1960                            resolveMethodDebugDOThideSubsetReach,
1961                            resolveMethodDebugDOThideEdgeTaints );
1962
1963       writeGraph( debugGraphPrefix+"caller00In",
1964                   resolveMethodDebugDOTwriteLabels,
1965                   resolveMethodDebugDOTselectTemps,
1966                   resolveMethodDebugDOTpruneGarbage,
1967                   resolveMethodDebugDOThideSubsetReach,
1968                   resolveMethodDebugDOThideEdgeTaints,
1969                   callerNodeIDsCopiedToCallee );
1970     }
1971
1972
1973
1974     // method call transfer function steps:
1975     // 1. Use current callee-reachable heap (CRH) to test callee
1976     //    predicates and mark what will be coming in.
1977     // 2. Wipe CRH out of caller.
1978     // 3. Transplant marked callee parts in:
1979     //    a) bring in nodes
1980     //    b) bring in callee -> callee edges
1981     //    c) resolve out-of-context -> callee edges
1982     //    d) assign return value
1983     // 4. Collapse shadow nodes down
1984     // 5. Global sweep it.
1985
1986
1987     // 1. mark what callee elements have satisfied predicates
1988     Hashtable<HeapRegionNode, ExistPredSet> calleeNodesSatisfied =
1989       new Hashtable<HeapRegionNode, ExistPredSet>();
1990
1991     Hashtable<RefEdge, ExistPredSet> calleeEdgesSatisfied =
1992       new Hashtable<RefEdge, ExistPredSet>();
1993
1994     Hashtable<ReachState, ExistPredSet> calleeStatesSatisfied =
1995       new Hashtable<ReachState, ExistPredSet>();
1996
1997     Hashtable< RefEdge, Set<RefSrcNode> > calleeEdges2oocCallerSrcMatches =
1998       new Hashtable< RefEdge, Set<RefSrcNode> >();
1999
2000     Iterator meItr = rgCallee.id2hrn.entrySet().iterator();
2001     while( meItr.hasNext() ) {
2002       Map.Entry      me        = (Map.Entry)      meItr.next();
2003       Integer        id        = (Integer)        me.getKey();
2004       HeapRegionNode hrnCallee = (HeapRegionNode) me.getValue();
2005
2006       // if a callee element's predicates are satisfied then a set
2007       // of CALLER predicates is returned: they are the predicates
2008       // that the callee element moved into the caller context
2009       // should have, and it is inefficient to find this again later
2010       ExistPredSet predsIfSatis =
2011         hrnCallee.getPreds().isSatisfiedBy( this,
2012                                             callerNodeIDsCopiedToCallee
2013                                             );
2014
2015       if( predsIfSatis != null ) {
2016         calleeNodesSatisfied.put( hrnCallee, predsIfSatis );
2017       } else {
2018         // otherwise don't bother looking at edges to this node
2019         continue;
2020       }
2021
2022       // since the node is coming over, find out which reach
2023       // states on it should come over, too
2024       Iterator<ReachState> stateItr = hrnCallee.getAlpha().iterator();
2025       while( stateItr.hasNext() ) {
2026         ReachState stateCallee = stateItr.next();
2027
2028         predsIfSatis =
2029           stateCallee.getPreds().isSatisfiedBy( this,
2030                                                 callerNodeIDsCopiedToCallee
2031                                                 );
2032         if( predsIfSatis != null ) {
2033           calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2034         }
2035       }
2036
2037       // then look at edges to the node
2038       Iterator<RefEdge> reItr = hrnCallee.iteratorToReferencers();
2039       while( reItr.hasNext() ) {
2040         RefEdge    reCallee  = reItr.next();
2041         RefSrcNode rsnCallee = reCallee.getSrc();
2042
2043         // (caller local variables to in-context heap regions)
2044         // have an (out-of-context heap region -> in-context heap region)
2045         // abstraction in the callEE, so its true we never need to
2046         // look at a (var node -> heap region) edge in callee to bring
2047         // those over for the call site transfer.  What about (param var->heap region)
2048         // edges in callee? They are dealt with below this loop.
2049         // So, yes, at this point skip (var->region) edges in callee
2050         if( rsnCallee instanceof VariableNode ) {
2051           continue;
2052         }
2053
2054         // first see if the source is out-of-context, and only
2055         // proceed with this edge if we find some caller-context
2056         // matches
2057         HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2058         boolean matchedOutOfContext = false;
2059
2060         if( !hrnSrcCallee.isOutOfContext() ) {
2061
2062           predsIfSatis =
2063             hrnSrcCallee.getPreds().isSatisfiedBy( this,
2064                                                    callerNodeIDsCopiedToCallee
2065                                                    );
2066           if( predsIfSatis != null ) {
2067             calleeNodesSatisfied.put( hrnSrcCallee, predsIfSatis );
2068           } else {
2069             // otherwise forget this edge
2070             continue;
2071           }
2072
2073         } else {
2074           // hrnSrcCallee is out-of-context
2075
2076           assert !calleeEdges2oocCallerSrcMatches.containsKey( reCallee );
2077
2078           Set<RefSrcNode> rsnCallers = new HashSet<RefSrcNode>();
2079
2080           // is the target node in the caller?
2081           HeapRegionNode hrnDstCaller = this.id2hrn.get( hrnCallee.getID() );
2082           if( hrnDstCaller == null ) {
2083             continue;
2084           }
2085
2086           Iterator<RefEdge> reDstItr = hrnDstCaller.iteratorToReferencers();
2087           while( reDstItr.hasNext() ) {
2088             // the edge and field (either possibly null) must match
2089             RefEdge reCaller = reDstItr.next();
2090
2091             if( !reCaller.typeEquals ( reCallee.getType()  ) ||
2092                 !reCaller.fieldEquals( reCallee.getField() )
2093                 ) {
2094               continue;
2095             }
2096
2097             RefSrcNode rsnCaller = reCaller.getSrc();
2098             if( rsnCaller instanceof VariableNode ) {
2099
2100               // a variable node matches an OOC region with null type
2101               if( hrnSrcCallee.getType() != null ) {
2102                 continue;
2103               }
2104
2105             } else {
2106               // otherwise types should match
2107               HeapRegionNode hrnCallerSrc = (HeapRegionNode) rsnCaller;
2108               if( hrnSrcCallee.getType() == null ) {
2109                 if( hrnCallerSrc.getType() != null ) {
2110                   continue;
2111                 }
2112               } else {
2113                 if( !hrnSrcCallee.getType().equals( hrnCallerSrc.getType() ) ) {
2114                   continue;
2115                 }
2116               }
2117             }
2118
2119             rsnCallers.add( rsnCaller );
2120             matchedOutOfContext = true;
2121           }
2122
2123           if( !rsnCallers.isEmpty() ) {
2124             calleeEdges2oocCallerSrcMatches.put( reCallee, rsnCallers );
2125           }
2126         }
2127
2128         if( hrnSrcCallee.isOutOfContext() &&
2129             !matchedOutOfContext ) {
2130           continue;
2131         }
2132
2133         predsIfSatis =
2134           reCallee.getPreds().isSatisfiedBy( this,
2135                                              callerNodeIDsCopiedToCallee
2136                                              );
2137
2138         if( predsIfSatis != null ) {
2139           calleeEdgesSatisfied.put( reCallee, predsIfSatis );
2140
2141           // since the edge is coming over, find out which reach
2142           // states on it should come over, too
2143           stateItr = reCallee.getBeta().iterator();
2144           while( stateItr.hasNext() ) {
2145             ReachState stateCallee = stateItr.next();
2146
2147             predsIfSatis =
2148               stateCallee.getPreds().isSatisfiedBy( this,
2149                                                     callerNodeIDsCopiedToCallee
2150                                                     );
2151             if( predsIfSatis != null ) {
2152               calleeStatesSatisfied.put( stateCallee, predsIfSatis );
2153             }
2154           }
2155         }
2156       }
2157     }
2158
2159     if( writeDebugDOTs ) {
2160       writeGraph( debugGraphPrefix+"caller20BeforeWipe",
2161                   resolveMethodDebugDOTwriteLabels,
2162                   resolveMethodDebugDOTselectTemps,
2163                   resolveMethodDebugDOTpruneGarbage,
2164                   resolveMethodDebugDOThideSubsetReach,
2165                   resolveMethodDebugDOThideEdgeTaints );
2166     }
2167
2168
2169     // 2. predicates tested, ok to wipe out caller part
2170     Iterator<Integer> hrnItr = callerNodeIDsCopiedToCallee.iterator();
2171     while( hrnItr.hasNext() ) {
2172       Integer        hrnID     = hrnItr.next();
2173       HeapRegionNode hrnCaller = id2hrn.get( hrnID );
2174       assert hrnCaller != null;
2175
2176       // when clearing off nodes, also eliminate variable
2177       // references
2178       wipeOut( hrnCaller, true );
2179     }
2180
2181
2182
2183     if( writeDebugDOTs ) {
2184       writeGraph( debugGraphPrefix+"caller30BeforeAddingNodes",
2185                   resolveMethodDebugDOTwriteLabels,
2186                   resolveMethodDebugDOTselectTemps,
2187                   resolveMethodDebugDOTpruneGarbage,
2188                   resolveMethodDebugDOThideSubsetReach,
2189                   resolveMethodDebugDOThideEdgeTaints );
2190     }
2191
2192
2193
2194
2195     // 3. callee elements with satisfied preds come in, note that
2196     //    the mapping of elements satisfied to preds is like this:
2197     //    A callee element EE has preds EEp that are satisfied by
2198     //    some caller element ER.  We bring EE into the caller
2199     //    context as ERee with the preds of ER, namely ERp, which
2200     //    in the following algorithm is the value in the mapping
2201
2202     // 3.a) nodes
2203     Iterator satisItr = calleeNodesSatisfied.entrySet().iterator();
2204     while( satisItr.hasNext() ) {
2205       Map.Entry      me        = (Map.Entry)      satisItr.next();
2206       HeapRegionNode hrnCallee = (HeapRegionNode) me.getKey();
2207       ExistPredSet   preds     = (ExistPredSet)   me.getValue();
2208
2209       // TODO: I think its true that the current implementation uses
2210       // the type of the OOC region and the predicates OF THE EDGE from
2211       // it to link everything up in caller context, so that's why we're
2212       // skipping this... maybe that's a sillier way to do it?
2213       if( hrnCallee.isOutOfContext() ) {
2214         continue;
2215       }
2216
2217       AllocSite as = hrnCallee.getAllocSite();
2218       allocSites.add( as );
2219
2220       Integer hrnIDshadow = as.getShadowIDfromID( hrnCallee.getID() );
2221
2222       HeapRegionNode hrnCaller = id2hrn.get( hrnIDshadow );
2223       if( hrnCaller == null ) {
2224         hrnCaller =
2225           createNewHeapRegionNode( hrnIDshadow,                // id or null to generate a new one
2226                                    hrnCallee.isSingleObject(), // single object?
2227                                    hrnCallee.isNewSummary(),   // summary?
2228                                    hrnCallee.isFlagged(),      // flagged?
2229                                    false,                      // out-of-context?
2230                                    hrnCallee.getType(),        // type
2231                                    hrnCallee.getAllocSite(),   // allocation site
2232                                    toCallerContext( hrnCallee.getInherent(),
2233                                                     calleeStatesSatisfied  ),    // inherent reach
2234                                    null,                       // current reach
2235                                    predsEmpty,                 // predicates
2236                                    hrnCallee.getDescription()  // description
2237                                    );
2238       } else {
2239         assert hrnCaller.isWiped();
2240       }
2241
2242       hrnCaller.setAlpha( toCallerContext( hrnCallee.getAlpha(),
2243                                            calleeStatesSatisfied
2244                                            )
2245                           );
2246
2247       hrnCaller.setPreds( preds );
2248     }
2249
2250
2251
2252
2253
2254     if( writeDebugDOTs ) {
2255       writeGraph( debugGraphPrefix+"caller31BeforeAddingEdges",
2256                   resolveMethodDebugDOTwriteLabels,
2257                   resolveMethodDebugDOTselectTemps,
2258                   resolveMethodDebugDOTpruneGarbage,
2259                   resolveMethodDebugDOThideSubsetReach,
2260                   resolveMethodDebugDOThideEdgeTaints );
2261     }
2262
2263
2264     // set these up during the next procedure so after
2265     // the caller has all of its nodes and edges put
2266     // back together we can propagate the callee's
2267     // reach changes backwards into the caller graph
2268     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
2269
2270     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
2271       new Hashtable<RefEdge, ChangeSet>();
2272
2273
2274     // 3.b) callee -> callee edges AND out-of-context -> callee
2275     satisItr = calleeEdgesSatisfied.entrySet().iterator();
2276     while( satisItr.hasNext() ) {
2277       Map.Entry    me       = (Map.Entry)    satisItr.next();
2278       RefEdge      reCallee = (RefEdge)      me.getKey();
2279       ExistPredSet preds    = (ExistPredSet) me.getValue();
2280
2281       HeapRegionNode hrnDstCallee = reCallee.getDst();
2282       AllocSite      asDst        = hrnDstCallee.getAllocSite();
2283       allocSites.add( asDst );
2284
2285       Integer hrnIDDstShadow =
2286         asDst.getShadowIDfromID( hrnDstCallee.getID() );
2287
2288       HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2289       assert hrnDstCaller != null;
2290
2291
2292       RefSrcNode rsnCallee = reCallee.getSrc();
2293
2294       Set<RefSrcNode> rsnCallers =
2295         new HashSet<RefSrcNode>();
2296
2297       Set<RefSrcNode> oocCallers =
2298         calleeEdges2oocCallerSrcMatches.get( reCallee );
2299
2300       if( rsnCallee instanceof HeapRegionNode ) {
2301         HeapRegionNode hrnCalleeSrc = (HeapRegionNode) rsnCallee;
2302         if( hrnCalleeSrc.isOutOfContext() ) {
2303           assert oocCallers != null;
2304         }
2305       }
2306
2307
2308       if( oocCallers == null ) {
2309         // there are no out-of-context matches, so it's
2310         // either a param/arg var or one in-context heap region
2311         if( rsnCallee instanceof VariableNode ) {
2312           // variable -> node in the callee should only
2313           // come into the caller if its from a param var
2314           VariableNode   vnCallee = (VariableNode) rsnCallee;
2315           TempDescriptor tdParam  = vnCallee.getTempDescriptor();
2316           TempDescriptor tdArg    = fc.getArgMatchingParam( fmCallee,
2317                                                             tdParam );
2318           if( tdArg == null ) {
2319             // this means the variable isn't a parameter, its local
2320             // to the callee so we ignore it in call site transfer
2321             // shouldn't this NEVER HAPPEN?
2322             assert false;
2323           }
2324
2325           rsnCallers.add( this.getVariableNodeFromTemp( tdArg ) );
2326
2327         } else {
2328           // otherwise source is in context, one region
2329
2330           HeapRegionNode hrnSrcCallee = (HeapRegionNode) rsnCallee;
2331
2332           // translate an in-context node to shadow
2333           AllocSite asSrc = hrnSrcCallee.getAllocSite();
2334           allocSites.add( asSrc );
2335
2336           Integer hrnIDSrcShadow =
2337             asSrc.getShadowIDfromID( hrnSrcCallee.getID() );
2338
2339           HeapRegionNode hrnSrcCallerShadow =
2340             this.id2hrn.get( hrnIDSrcShadow );
2341
2342           assert hrnSrcCallerShadow != null;
2343
2344           rsnCallers.add( hrnSrcCallerShadow );
2345         }
2346
2347       } else {
2348         // otherwise we have a set of out-of-context srcs
2349         // that should NOT be translated to shadow nodes
2350         assert !oocCallers.isEmpty();
2351         rsnCallers.addAll( oocCallers );
2352       }
2353
2354       // now make all caller edges we've identified from
2355       // this callee edge with a satisfied predicate
2356       assert !rsnCallers.isEmpty();
2357       Iterator<RefSrcNode> rsnItr = rsnCallers.iterator();
2358       while( rsnItr.hasNext() ) {
2359         RefSrcNode rsnCaller = rsnItr.next();
2360
2361         RefEdge reCaller = new RefEdge( rsnCaller,
2362                                         hrnDstCaller,
2363                                         reCallee.getType(),
2364                                         reCallee.getField(),
2365                                         toCallerContext( reCallee.getBeta(),
2366                                                          calleeStatesSatisfied ),
2367                                         preds
2368                                         );
2369
2370         ChangeSet cs = ChangeSet.factory();
2371         Iterator<ReachState> rsItr = reCaller.getBeta().iterator();
2372         while( rsItr.hasNext() ) {
2373           ReachState   state          = rsItr.next();
2374           ExistPredSet predsPreCallee = state.getPreds();
2375
2376           if( state.isEmpty() ) {
2377             continue;
2378           }
2379
2380           Iterator<ExistPred> predItr = predsPreCallee.iterator();
2381           while( predItr.hasNext() ) {
2382             ExistPred pred = predItr.next();
2383             ReachState old = pred.ne_state;
2384
2385             if( old == null ) {
2386               old = rstateEmpty;
2387             }
2388
2389             cs = Canonical.add( cs,
2390                                 ChangeTuple.factory( old,
2391                                                      state
2392                                                      )
2393                                 );
2394           }
2395         }
2396
2397
2398         // look to see if an edge with same field exists
2399         // and merge with it, otherwise just add the edge
2400         RefEdge edgeExisting = rsnCaller.getReferenceTo( hrnDstCaller,
2401                                                          reCallee.getType(),
2402                                                          reCallee.getField()
2403                                                          );
2404         if( edgeExisting != null ) {
2405           edgeExisting.setBeta(
2406                                Canonical.unionORpreds( edgeExisting.getBeta(),
2407                                                 reCaller.getBeta()
2408                                                 )
2409                                );
2410           edgeExisting.setPreds(
2411                                 Canonical.join( edgeExisting.getPreds(),
2412                                                 reCaller.getPreds()
2413                                                 )
2414                                 );
2415
2416           // for reach propagation
2417           if( !cs.isEmpty() ) {
2418             ChangeSet csExisting = edgePlannedChanges.get( edgeExisting );
2419             if( csExisting == null ) {
2420               csExisting = ChangeSet.factory();
2421             }
2422             edgePlannedChanges.put( edgeExisting,
2423                                     Canonical.union( csExisting,
2424                                                      cs
2425                                                      )
2426                                     );
2427           }
2428
2429         } else {
2430           addRefEdge( rsnCaller, hrnDstCaller, reCaller );
2431
2432           // for reach propagation
2433           if( !cs.isEmpty() ) {
2434             edgesForPropagation.add( reCaller );
2435             assert !edgePlannedChanges.containsKey( reCaller );
2436             edgePlannedChanges.put( reCaller, cs );
2437           }
2438         }
2439       }
2440     }
2441
2442
2443
2444
2445     if( writeDebugDOTs ) {
2446       writeGraph( debugGraphPrefix+"caller35BeforeAssignReturnValue",
2447                   resolveMethodDebugDOTwriteLabels,
2448                   resolveMethodDebugDOTselectTemps,
2449                   resolveMethodDebugDOTpruneGarbage,
2450                   resolveMethodDebugDOThideSubsetReach,
2451                   resolveMethodDebugDOThideEdgeTaints );
2452     }
2453
2454
2455
2456     // TODO: WAIT! THIS SHOULD BE MERGED INTO OTHER PARTS, BECAUSE
2457     // AS IT IS WE'RE NOT VERIFYING PREDICATES OF RETURN VALUE
2458     // EDGES, JUST BRINGING THEM ALL!  It'll work for now, over approximation
2459
2460     // 3.d) handle return value assignment if needed
2461     TempDescriptor returnTemp = fc.getReturnTemp();
2462     if( returnTemp != null &&
2463         DisjointAnalysis.shouldAnalysisTrack( returnTemp.getType() )
2464         ) {
2465
2466       VariableNode vnLhsCaller = getVariableNodeFromTemp( returnTemp );
2467       clearRefEdgesFrom( vnLhsCaller, null, null, true );
2468
2469       VariableNode vnReturnCallee = rgCallee.getVariableNodeFromTemp( tdReturn );
2470       Iterator<RefEdge> reCalleeItr = vnReturnCallee.iteratorToReferencees();
2471       while( reCalleeItr.hasNext() ) {
2472         RefEdge        reCallee     = reCalleeItr.next();
2473         HeapRegionNode hrnDstCallee = reCallee.getDst();
2474
2475         // some edge types are not possible return values when we can
2476         // see what type variable we are assigning it to
2477         if( !isSuperiorType( returnTemp.getType(), reCallee.getType() ) ) {
2478           System.out.println( "*** NOT EXPECTING TO SEE THIS: Throwing out "+
2479                               reCallee+" for return temp "+returnTemp );
2480           // prune
2481           continue;
2482         }
2483
2484         AllocSite asDst = hrnDstCallee.getAllocSite();
2485         allocSites.add( asDst );
2486
2487         Integer hrnIDDstShadow = asDst.getShadowIDfromID( hrnDstCallee.getID() );
2488
2489         HeapRegionNode hrnDstCaller = id2hrn.get( hrnIDDstShadow );
2490         if( hrnDstCaller == null ) {
2491           hrnDstCaller =
2492             createNewHeapRegionNode( hrnIDDstShadow,                // id or null to generate a new one
2493                                      hrnDstCallee.isSingleObject(), // single object?
2494                                      hrnDstCallee.isNewSummary(),   // summary?
2495                                      hrnDstCallee.isFlagged(),      // flagged?
2496                                      false,                         // out-of-context?
2497                                      hrnDstCallee.getType(),        // type
2498                                      hrnDstCallee.getAllocSite(),   // allocation site
2499                                      toCallerContext( hrnDstCallee.getInherent(),
2500                                                       calleeStatesSatisfied  ),    // inherent reach
2501                                      toCallerContext( hrnDstCallee.getAlpha(),
2502                                                       calleeStatesSatisfied  ),    // current reach
2503                                      predsTrue,                     // predicates
2504                                      hrnDstCallee.getDescription()  // description
2505                                      );
2506         }
2507
2508         TypeDescriptor tdNewEdge =
2509           mostSpecificType( reCallee.getType(),
2510                             hrnDstCallee.getType(),
2511                             hrnDstCaller.getType()
2512                             );
2513
2514         RefEdge reCaller = new RefEdge( vnLhsCaller,
2515                                         hrnDstCaller,
2516                                         tdNewEdge,
2517                                         null,
2518                                         toCallerContext( reCallee.getBeta(),
2519                                                          calleeStatesSatisfied ),
2520                                         predsTrue
2521                                         );
2522
2523         addRefEdge( vnLhsCaller, hrnDstCaller, reCaller );
2524       }
2525     }
2526
2527
2528
2529     if( writeDebugDOTs ) {
2530       writeGraph( debugGraphPrefix+"caller38propagateReach",
2531                   resolveMethodDebugDOTwriteLabels,
2532                   resolveMethodDebugDOTselectTemps,
2533                   resolveMethodDebugDOTpruneGarbage,
2534                   resolveMethodDebugDOThideSubsetReach,
2535                   resolveMethodDebugDOThideEdgeTaints );
2536     }
2537
2538     // propagate callee reachability changes to the rest
2539     // of the caller graph edges
2540     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
2541
2542     propagateTokensOverEdges( edgesForPropagation, // source edges
2543                               edgePlannedChanges,  // map src edge to change set
2544                               edgesUpdated );      // list of updated edges
2545
2546     // commit beta' (beta<-betaNew)
2547     Iterator<RefEdge> edgeItr = edgesUpdated.iterator();
2548     while( edgeItr.hasNext() ) {
2549       edgeItr.next().applyBetaNew();
2550     }
2551
2552
2553
2554
2555
2556
2557
2558     if( writeDebugDOTs ) {
2559       writeGraph( debugGraphPrefix+"caller40BeforeShadowMerge",
2560                   resolveMethodDebugDOTwriteLabels,
2561                   resolveMethodDebugDOTselectTemps,
2562                   resolveMethodDebugDOTpruneGarbage,
2563                   resolveMethodDebugDOThideSubsetReach,
2564                   resolveMethodDebugDOThideEdgeTaints );
2565     }
2566
2567
2568     // 4) merge shadow nodes so alloc sites are back to k
2569     Iterator<AllocSite> asItr = rgCallee.allocSites.iterator();
2570     while( asItr.hasNext() ) {
2571       // for each allocation site do the following to merge
2572       // shadow nodes (newest from callee) with any existing
2573       // look for the newest normal and newest shadow "slot"
2574       // not being used, transfer normal to shadow.  Keep
2575       // doing this until there are no more normal nodes, or
2576       // no empty shadow slots: then merge all remaining normal
2577       // nodes into the shadow summary.  Finally, convert all
2578       // shadow to their normal versions.
2579       AllocSite as = asItr.next();
2580       int ageNorm = 0;
2581       int ageShad = 0;
2582       while( ageNorm < allocationDepth &&
2583              ageShad < allocationDepth ) {
2584
2585         // first, are there any normal nodes left?
2586         Integer        idNorm  = as.getIthOldest( ageNorm );
2587         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2588         if( hrnNorm == null ) {
2589           // no, this age of normal node not in the caller graph
2590           ageNorm++;
2591           continue;
2592         }
2593
2594         // yes, a normal node exists, is there an empty shadow
2595         // "slot" to transfer it onto?
2596         HeapRegionNode hrnShad = getIthNode( as, ageShad, true );
2597         if( !hrnShad.isWiped() ) {
2598           // no, this age of shadow node is not empty
2599           ageShad++;
2600           continue;
2601         }
2602
2603         // yes, this shadow node is empty
2604         transferOnto( hrnNorm, hrnShad );
2605         ageNorm++;
2606         ageShad++;
2607       }
2608
2609       // now, while there are still normal nodes but no shadow
2610       // slots, merge normal nodes into the shadow summary
2611       while( ageNorm < allocationDepth ) {
2612
2613         // first, are there any normal nodes left?
2614         Integer        idNorm  = as.getIthOldest( ageNorm );
2615         HeapRegionNode hrnNorm = id2hrn.get( idNorm );
2616         if( hrnNorm == null ) {
2617           // no, this age of normal node not in the caller graph
2618           ageNorm++;
2619           continue;
2620         }
2621
2622         // yes, a normal node exists, so get the shadow summary
2623         HeapRegionNode summShad = getSummaryNode( as, true );
2624         mergeIntoSummary( hrnNorm, summShad );
2625         ageNorm++;
2626       }
2627
2628       // if there is a normal summary, merge it into shadow summary
2629       Integer        idNorm   = as.getSummary();
2630       HeapRegionNode summNorm = id2hrn.get( idNorm );
2631       if( summNorm != null ) {
2632         HeapRegionNode summShad = getSummaryNode( as, true );
2633         mergeIntoSummary( summNorm, summShad );
2634       }
2635
2636       // finally, flip all existing shadow nodes onto the normal
2637       for( int i = 0; i < allocationDepth; ++i ) {
2638         Integer        idShad  = as.getIthOldestShadow( i );
2639         HeapRegionNode hrnShad = id2hrn.get( idShad );
2640         if( hrnShad != null ) {
2641           // flip it
2642           HeapRegionNode hrnNorm = getIthNode( as, i, false );
2643           assert hrnNorm.isWiped();
2644           transferOnto( hrnShad, hrnNorm );
2645         }
2646       }
2647
2648       Integer        idShad   = as.getSummaryShadow();
2649       HeapRegionNode summShad = id2hrn.get( idShad );
2650       if( summShad != null ) {
2651         summNorm = getSummaryNode( as, false );
2652         transferOnto( summShad, summNorm );
2653       }
2654     }
2655
2656
2657
2658
2659
2660
2661     if( writeDebugDOTs ) {
2662       writeGraph( debugGraphPrefix+"caller45BeforeUnshadow",
2663                   resolveMethodDebugDOTwriteLabels,
2664                   resolveMethodDebugDOTselectTemps,
2665                   resolveMethodDebugDOTpruneGarbage,
2666                   resolveMethodDebugDOThideSubsetReach,
2667                   resolveMethodDebugDOThideEdgeTaints );
2668     }
2669
2670
2671     Iterator itrAllHRNodes = id2hrn.entrySet().iterator();
2672     while( itrAllHRNodes.hasNext() ) {
2673       Map.Entry      me  = (Map.Entry)      itrAllHRNodes.next();
2674       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
2675
2676       hrn.setAlpha( unshadow( hrn.getAlpha() ) );
2677
2678       Iterator<RefEdge> itrEdges = hrn.iteratorToReferencers();
2679       while( itrEdges.hasNext() ) {
2680         RefEdge re = itrEdges.next();
2681         re.setBeta( unshadow( re.getBeta() ) );
2682       }
2683     }
2684
2685
2686
2687
2688     if( writeDebugDOTs ) {
2689       writeGraph( debugGraphPrefix+"caller50BeforeGlobalSweep",
2690                   resolveMethodDebugDOTwriteLabels,
2691                   resolveMethodDebugDOTselectTemps,
2692                   resolveMethodDebugDOTpruneGarbage,
2693                   resolveMethodDebugDOThideSubsetReach,
2694                   resolveMethodDebugDOThideEdgeTaints );
2695     }
2696
2697
2698     // 5.
2699     if( !DISABLE_GLOBAL_SWEEP ) {
2700       globalSweep();
2701     }
2702
2703
2704
2705
2706
2707     if( writeDebugDOTs ) {
2708       writeGraph( debugGraphPrefix+"caller90AfterTransfer",
2709                   resolveMethodDebugDOTwriteLabels,
2710                   resolveMethodDebugDOTselectTemps,
2711                   resolveMethodDebugDOTpruneGarbage,
2712                   resolveMethodDebugDOThideSubsetReach,
2713                   resolveMethodDebugDOThideEdgeTaints );
2714
2715       ++debugCallSiteVisits;
2716       if( debugCallSiteVisits >= debugCallSiteVisitsUntilExit ) {
2717         System.out.println( "!!! Exiting after requested visits to call site. !!!" );
2718         System.exit( 0 );
2719       }
2720     }
2721   }
2722
2723
2724
2725   ////////////////////////////////////////////////////
2726   //
2727   //  Abstract garbage collection simply removes
2728   //  heap region nodes that are not mechanically
2729   //  reachable from a root set.  This step is
2730   //  essential for testing node and edge existence
2731   //  predicates efficiently
2732   //
2733   ////////////////////////////////////////////////////
2734   public void abstractGarbageCollect( Set<TempDescriptor> liveSet ) {
2735
2736     // calculate a root set, will be different for Java
2737     // version of analysis versus Bamboo version
2738     Set<RefSrcNode> toVisit = new HashSet<RefSrcNode>();
2739
2740     // visit every variable in graph while building root
2741     // set, and do iterating on a copy, so we can remove
2742     // dead variables while we're at this
2743     Iterator makeCopyItr = td2vn.entrySet().iterator();
2744     Set      entrysCopy  = new HashSet();
2745     while( makeCopyItr.hasNext() ) {
2746       entrysCopy.add( makeCopyItr.next() );
2747     }
2748
2749     Iterator eItr = entrysCopy.iterator();
2750     while( eItr.hasNext() ) {
2751       Map.Entry      me = (Map.Entry)      eItr.next();
2752       TempDescriptor td = (TempDescriptor) me.getKey();
2753       VariableNode   vn = (VariableNode)   me.getValue();
2754
2755       if( liveSet.contains( td ) ) {
2756         toVisit.add( vn );
2757
2758       } else {
2759         // dead var, remove completely from graph
2760         td2vn.remove( td );
2761         clearRefEdgesFrom( vn, null, null, true );
2762       }
2763     }
2764
2765     // everything visited in a traversal is
2766     // considered abstractly live
2767     Set<RefSrcNode> visited = new HashSet<RefSrcNode>();
2768
2769     while( !toVisit.isEmpty() ) {
2770       RefSrcNode rsn = toVisit.iterator().next();
2771       toVisit.remove( rsn );
2772       visited.add( rsn );
2773
2774       Iterator<RefEdge> hrnItr = rsn.iteratorToReferencees();
2775       while( hrnItr.hasNext() ) {
2776         RefEdge        edge = hrnItr.next();
2777         HeapRegionNode hrn  = edge.getDst();
2778
2779         if( !visited.contains( hrn ) ) {
2780           toVisit.add( hrn );
2781         }
2782       }
2783     }
2784
2785     // get a copy of the set to iterate over because
2786     // we're going to monkey with the graph when we
2787     // identify a garbage node
2788     Set<HeapRegionNode> hrnAllPrior = new HashSet<HeapRegionNode>();
2789     Iterator<HeapRegionNode> hrnItr = id2hrn.values().iterator();
2790     while( hrnItr.hasNext() ) {
2791       hrnAllPrior.add( hrnItr.next() );
2792     }
2793
2794     Iterator<HeapRegionNode> hrnAllItr = hrnAllPrior.iterator();
2795     while( hrnAllItr.hasNext() ) {
2796       HeapRegionNode hrn = hrnAllItr.next();
2797
2798       if( !visited.contains( hrn ) ) {
2799
2800         // heap region nodes are compared across ReachGraph
2801         // objects by their integer ID, so when discarding
2802         // garbage nodes we must also discard entries in
2803         // the ID -> heap region hashtable.
2804         id2hrn.remove( hrn.getID() );
2805
2806         // RefEdge objects are two-way linked between
2807         // nodes, so when a node is identified as garbage,
2808         // actively clear references to and from it so
2809         // live nodes won't have dangling RefEdge's
2810         wipeOut( hrn, true );
2811
2812         // if we just removed the last node from an allocation
2813         // site, it should be taken out of the ReachGraph's list
2814         AllocSite as = hrn.getAllocSite();
2815         if( !hasNodesOf( as ) ) {
2816           allocSites.remove( as );
2817         }
2818       }
2819     }
2820   }
2821
2822   protected boolean hasNodesOf( AllocSite as ) {
2823     if( id2hrn.containsKey( as.getSummary() ) ) {
2824       return true;
2825     }
2826
2827     for( int i = 0; i < allocationDepth; ++i ) {
2828       if( id2hrn.containsKey( as.getIthOldest( i ) ) ) {
2829         return true;
2830       }
2831     }
2832     return false;
2833   }
2834
2835
2836   ////////////////////////////////////////////////////
2837   //
2838   //  This global sweep is an optional step to prune
2839   //  reachability sets that are not internally
2840   //  consistent with the global graph.  It should be
2841   //  invoked after strong updates or method calls.
2842   //
2843   ////////////////////////////////////////////////////
2844   public void globalSweep() {
2845
2846     // boldB is part of the phase 1 sweep
2847     // it has an in-context table and an out-of-context table
2848     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBic =
2849       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2850
2851     Hashtable< Integer, Hashtable<RefEdge, ReachSet> > boldBooc =
2852       new Hashtable< Integer, Hashtable<RefEdge, ReachSet> >();
2853
2854     // visit every heap region to initialize alphaNew and betaNew,
2855     // and make a map of every hrnID to the source nodes it should
2856     // propagate forward from.  In-context flagged hrnID's propagate
2857     // from only the in-context node they name, but out-of-context
2858     // ID's may propagate from several out-of-context nodes
2859     Hashtable< Integer, Set<HeapRegionNode> > icID2srcs =
2860       new Hashtable< Integer, Set<HeapRegionNode> >();
2861
2862     Hashtable< Integer, Set<HeapRegionNode> > oocID2srcs =
2863       new Hashtable< Integer, Set<HeapRegionNode> >();
2864
2865
2866     Iterator itrHrns = id2hrn.entrySet().iterator();
2867     while( itrHrns.hasNext() ) {
2868       Map.Entry      me    = (Map.Entry)      itrHrns.next();
2869       Integer        hrnID = (Integer)        me.getKey();
2870       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
2871
2872       // assert that this node and incoming edges have clean alphaNew
2873       // and betaNew sets, respectively
2874       assert rsetEmpty.equals( hrn.getAlphaNew() );
2875
2876       Iterator<RefEdge> itrRers = hrn.iteratorToReferencers();
2877       while( itrRers.hasNext() ) {
2878         RefEdge edge = itrRers.next();
2879         assert rsetEmpty.equals( edge.getBetaNew() );
2880       }
2881
2882       // make a mapping of IDs to heap regions they propagate from
2883       if( hrn.isFlagged() ) {
2884         assert !hrn.isOutOfContext();
2885         assert !icID2srcs.containsKey( hrn.getID() );
2886
2887         // in-context flagged node IDs simply propagate from the
2888         // node they name
2889         Set<HeapRegionNode> srcs = new HashSet<HeapRegionNode>();
2890         srcs.add( hrn );
2891         icID2srcs.put( hrn.getID(), srcs );
2892       }
2893
2894       if( hrn.isOutOfContext() ) {
2895         assert !hrn.isFlagged();
2896
2897         // the reachability states on an out-of-context
2898         // node are not really important (combinations of
2899         // IDs or arity)--what matters is that the states
2900         // specify which nodes this out-of-context node
2901         // stands in for.  For example, if the state [17?, 19*]
2902         // appears on the ooc node, it may serve as a source
2903         // for node 17? and a source for node 19.
2904         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
2905         while( stateItr.hasNext() ) {
2906           ReachState state = stateItr.next();
2907
2908           Iterator<ReachTuple> rtItr = state.iterator();
2909           while( rtItr.hasNext() ) {
2910             ReachTuple rt = rtItr.next();
2911             assert rt.isOutOfContext();
2912
2913             Set<HeapRegionNode> srcs = oocID2srcs.get( rt.getHrnID() );
2914             if( srcs == null ) {
2915               srcs = new HashSet<HeapRegionNode>();
2916             }
2917             srcs.add( hrn );
2918             oocID2srcs.put( rt.getHrnID(), srcs );
2919           }
2920         }
2921       }
2922     }
2923
2924     // calculate boldB for all hrnIDs identified by the above
2925     // node traversal, propagating from every source
2926     while( !icID2srcs.isEmpty() || !oocID2srcs.isEmpty() ) {
2927
2928       Integer             hrnID;
2929       Set<HeapRegionNode> srcs;
2930       boolean             inContext;
2931
2932       if( !icID2srcs.isEmpty() ) {
2933         Map.Entry me = (Map.Entry) icID2srcs.entrySet().iterator().next();
2934         hrnID = (Integer)             me.getKey();
2935         srcs  = (Set<HeapRegionNode>) me.getValue();
2936         inContext = true;
2937         icID2srcs.remove( hrnID );
2938
2939       } else {
2940         assert !oocID2srcs.isEmpty();
2941
2942         Map.Entry me = (Map.Entry) oocID2srcs.entrySet().iterator().next();
2943         hrnID = (Integer)             me.getKey();
2944         srcs  = (Set<HeapRegionNode>) me.getValue();
2945         inContext = false;
2946         oocID2srcs.remove( hrnID );
2947       }
2948
2949
2950       Hashtable<RefEdge, ReachSet> boldB_f =
2951         new Hashtable<RefEdge, ReachSet>();
2952
2953       Set<RefEdge> workSetEdges = new HashSet<RefEdge>();
2954
2955       Iterator<HeapRegionNode> hrnItr = srcs.iterator();
2956       while( hrnItr.hasNext() ) {
2957         HeapRegionNode hrn = hrnItr.next();
2958
2959         assert workSetEdges.isEmpty();
2960
2961         // initial boldB_f constraints
2962         Iterator<RefEdge> itrRees = hrn.iteratorToReferencees();
2963         while( itrRees.hasNext() ) {
2964           RefEdge edge = itrRees.next();
2965
2966           assert !boldB_f.containsKey( edge );
2967           boldB_f.put( edge, edge.getBeta() );
2968
2969           assert !workSetEdges.contains( edge );
2970           workSetEdges.add( edge );
2971         }
2972
2973         // enforce the boldB_f constraint at edges until we reach a fixed point
2974         while( !workSetEdges.isEmpty() ) {
2975           RefEdge edge = workSetEdges.iterator().next();
2976           workSetEdges.remove( edge );
2977
2978           Iterator<RefEdge> itrPrime = edge.getDst().iteratorToReferencees();
2979           while( itrPrime.hasNext() ) {
2980             RefEdge edgePrime = itrPrime.next();
2981
2982             ReachSet prevResult   = boldB_f.get( edgePrime );
2983             ReachSet intersection = Canonical.intersection( boldB_f.get( edge ),
2984                                                             edgePrime.getBeta()
2985                                                             );
2986
2987             if( prevResult == null ||
2988                 Canonical.unionORpreds( prevResult,
2989                                         intersection ).size()
2990                 > prevResult.size()
2991                 ) {
2992
2993               if( prevResult == null ) {
2994                 boldB_f.put( edgePrime,
2995                              Canonical.unionORpreds( edgePrime.getBeta(),
2996                                                      intersection
2997                                                      )
2998                              );
2999               } else {
3000                 boldB_f.put( edgePrime,
3001                              Canonical.unionORpreds( prevResult,
3002                                                      intersection
3003                                                      )
3004                              );
3005               }
3006               workSetEdges.add( edgePrime );
3007             }
3008           }
3009         }
3010       }
3011
3012       if( inContext ) {
3013         boldBic.put( hrnID, boldB_f );
3014       } else {
3015         boldBooc.put( hrnID, boldB_f );
3016       }
3017     }
3018
3019
3020     // use boldB to prune hrnIDs from alpha states that are impossible
3021     // and propagate the differences backwards across edges
3022     HashSet<RefEdge> edgesForPropagation = new HashSet<RefEdge>();
3023
3024     Hashtable<RefEdge, ChangeSet> edgePlannedChanges =
3025       new Hashtable<RefEdge, ChangeSet>();
3026
3027
3028     itrHrns = id2hrn.entrySet().iterator();
3029     while( itrHrns.hasNext() ) {
3030       Map.Entry      me    = (Map.Entry)      itrHrns.next();
3031       Integer        hrnID = (Integer)        me.getKey();
3032       HeapRegionNode hrn   = (HeapRegionNode) me.getValue();
3033
3034       // out-of-context nodes don't participate in the
3035       // global sweep, they serve as sources for the pass
3036       // performed above
3037       if( hrn.isOutOfContext() ) {
3038         continue;
3039       }
3040
3041       // the inherent states of a region are the exception
3042       // to removal as the global sweep prunes
3043       ReachTuple rtException = ReachTuple.factory( hrnID,
3044                                                    !hrn.isSingleObject(),
3045                                                    ReachTuple.ARITY_ONE,
3046                                                    false // out-of-context
3047                                                    );
3048
3049       ChangeSet cts = ChangeSet.factory();
3050
3051       // mark hrnIDs for removal
3052       Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3053       while( stateItr.hasNext() ) {
3054         ReachState stateOld = stateItr.next();
3055
3056         ReachState markedHrnIDs = ReachState.factory();
3057
3058         Iterator<ReachTuple> rtItr = stateOld.iterator();
3059         while( rtItr.hasNext() ) {
3060           ReachTuple rtOld = rtItr.next();
3061
3062           // never remove the inherent hrnID from a flagged region
3063           // because it is trivially satisfied
3064           if( hrn.isFlagged() ) {
3065             if( rtOld == rtException ) {
3066               continue;
3067             }
3068           }
3069
3070           // does boldB allow this hrnID?
3071           boolean foundState = false;
3072           Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3073           while( incidentEdgeItr.hasNext() ) {
3074             RefEdge incidentEdge = incidentEdgeItr.next();
3075
3076             Hashtable<RefEdge, ReachSet> B;
3077             if( rtOld.isOutOfContext() ) {
3078               B = boldBooc.get( rtOld.getHrnID() );
3079             } else {
3080
3081               if( !id2hrn.containsKey( rtOld.getHrnID() ) ) {
3082                 // let symbols not in the graph get pruned
3083                 break;
3084               }
3085
3086               B = boldBic.get( rtOld.getHrnID() );
3087             }
3088
3089             if( B != null ) {
3090               ReachSet boldB_rtOld_incident = B.get( incidentEdge );
3091               if( boldB_rtOld_incident != null &&
3092                   boldB_rtOld_incident.containsIgnorePreds( stateOld ) != null
3093                   ) {
3094                 foundState = true;
3095               }
3096             }
3097           }
3098
3099           if( !foundState ) {
3100             markedHrnIDs = Canonical.add( markedHrnIDs, rtOld );
3101           }
3102         }
3103
3104         // if there is nothing marked, just move on
3105         if( markedHrnIDs.isEmpty() ) {
3106           hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3107                                           stateOld
3108                                           )
3109                            );
3110           continue;
3111         }
3112
3113         // remove all marked hrnIDs and establish a change set that should
3114         // propagate backwards over edges from this node
3115         ReachState statePruned = ReachState.factory();
3116         rtItr = stateOld.iterator();
3117         while( rtItr.hasNext() ) {
3118           ReachTuple rtOld = rtItr.next();
3119
3120           if( !markedHrnIDs.containsTuple( rtOld ) ) {
3121             statePruned = Canonical.add( statePruned, rtOld );
3122           }
3123         }
3124         assert !stateOld.equals( statePruned );
3125
3126         hrn.setAlphaNew( Canonical.add( hrn.getAlphaNew(),
3127                                         statePruned
3128                                         )
3129                          );
3130         ChangeTuple ct = ChangeTuple.factory( stateOld,
3131                                               statePruned
3132                                               );
3133         cts = Canonical.add( cts, ct );
3134       }
3135
3136       // throw change tuple set on all incident edges
3137       if( !cts.isEmpty() ) {
3138         Iterator<RefEdge> incidentEdgeItr = hrn.iteratorToReferencers();
3139         while( incidentEdgeItr.hasNext() ) {
3140           RefEdge incidentEdge = incidentEdgeItr.next();
3141
3142           edgesForPropagation.add( incidentEdge );
3143
3144           if( edgePlannedChanges.get( incidentEdge ) == null ) {
3145             edgePlannedChanges.put( incidentEdge, cts );
3146           } else {
3147             edgePlannedChanges.put(
3148                                    incidentEdge,
3149                                    Canonical.union( edgePlannedChanges.get( incidentEdge ),
3150                                                     cts
3151                                                     )
3152                                     );
3153           }
3154         }
3155       }
3156     }
3157
3158     HashSet<RefEdge> edgesUpdated = new HashSet<RefEdge>();
3159
3160     propagateTokensOverEdges( edgesForPropagation,
3161                               edgePlannedChanges,
3162                               edgesUpdated );
3163
3164     // at the end of the 1st phase reference edges have
3165     // beta, betaNew that correspond to beta and betaR
3166     //
3167     // commit beta<-betaNew, so beta=betaR and betaNew
3168     // will represent the beta' calculation in 2nd phase
3169     //
3170     // commit alpha<-alphaNew because it won't change
3171     HashSet<RefEdge> res = new HashSet<RefEdge>();
3172
3173     Iterator<HeapRegionNode> nodeItr = id2hrn.values().iterator();
3174     while( nodeItr.hasNext() ) {
3175       HeapRegionNode hrn = nodeItr.next();
3176
3177       // as mentioned above, out-of-context nodes only serve
3178       // as sources of reach states for the sweep, not part
3179       // of the changes
3180       if( hrn.isOutOfContext() ) {
3181         assert hrn.getAlphaNew().equals( rsetEmpty );
3182       } else {
3183         hrn.applyAlphaNew();
3184       }
3185
3186       Iterator<RefEdge> itrRes = hrn.iteratorToReferencers();
3187       while( itrRes.hasNext() ) {
3188         res.add( itrRes.next() );
3189       }
3190     }
3191
3192
3193     // 2nd phase
3194     Iterator<RefEdge> edgeItr = res.iterator();
3195     while( edgeItr.hasNext() ) {
3196       RefEdge        edge = edgeItr.next();
3197       HeapRegionNode hrn  = edge.getDst();
3198
3199       // commit results of last phase
3200       if( edgesUpdated.contains( edge ) ) {
3201         edge.applyBetaNew();
3202       }
3203
3204       // compute intial condition of 2nd phase
3205       edge.setBetaNew( Canonical.intersection( edge.getBeta(),
3206                                                hrn.getAlpha()
3207                                                )
3208                        );
3209     }
3210
3211     // every edge in the graph is the initial workset
3212     Set<RefEdge> edgeWorkSet = (Set) res.clone();
3213     while( !edgeWorkSet.isEmpty() ) {
3214       RefEdge edgePrime = edgeWorkSet.iterator().next();
3215       edgeWorkSet.remove( edgePrime );
3216
3217       RefSrcNode rsn = edgePrime.getSrc();
3218       if( !(rsn instanceof HeapRegionNode) ) {
3219         continue;
3220       }
3221       HeapRegionNode hrn = (HeapRegionNode) rsn;
3222
3223       Iterator<RefEdge> itrEdge = hrn.iteratorToReferencers();
3224       while( itrEdge.hasNext() ) {
3225         RefEdge edge = itrEdge.next();
3226
3227         ReachSet prevResult = edge.getBetaNew();
3228         assert prevResult != null;
3229
3230         ReachSet intersection =
3231           Canonical.intersection( edge.getBeta(),
3232                                   edgePrime.getBetaNew()
3233                                   );
3234
3235         if( Canonical.unionORpreds( prevResult,
3236                                     intersection
3237                                     ).size()
3238             > prevResult.size()
3239             ) {
3240
3241           edge.setBetaNew(
3242                           Canonical.unionORpreds( prevResult,
3243                                                   intersection
3244                                                   )
3245                            );
3246           edgeWorkSet.add( edge );
3247         }
3248       }
3249     }
3250
3251     // commit beta' (beta<-betaNew)
3252     edgeItr = res.iterator();
3253     while( edgeItr.hasNext() ) {
3254       edgeItr.next().applyBetaNew();
3255     }
3256   }
3257
3258
3259   // a useful assertion for debugging:
3260   // every in-context tuple on any edge or
3261   // any node should name a node that is
3262   // part of the graph
3263   public boolean inContextTuplesInGraph() {
3264
3265     Iterator hrnItr = id2hrn.entrySet().iterator();
3266     while( hrnItr.hasNext() ) {
3267       Map.Entry      me  = (Map.Entry)      hrnItr.next();
3268       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3269
3270       {
3271         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3272         while( stateItr.hasNext() ) {
3273           ReachState state = stateItr.next();
3274
3275           Iterator<ReachTuple> rtItr = state.iterator();
3276           while( rtItr.hasNext() ) {
3277             ReachTuple rt = rtItr.next();
3278
3279             if( !rt.isOutOfContext() ) {
3280               if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3281                 System.out.println( rt.getHrnID()+" is missing" );
3282                 return false;
3283               }
3284             }
3285           }
3286         }
3287       }
3288
3289       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3290       while( edgeItr.hasNext() ) {
3291         RefEdge edge = edgeItr.next();
3292
3293         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3294         while( stateItr.hasNext() ) {
3295           ReachState state = stateItr.next();
3296
3297           Iterator<ReachTuple> rtItr = state.iterator();
3298           while( rtItr.hasNext() ) {
3299             ReachTuple rt = rtItr.next();
3300
3301             if( !rt.isOutOfContext() ) {
3302               if( !id2hrn.containsKey( rt.getHrnID() ) ) {
3303                 System.out.println( rt.getHrnID()+" is missing" );
3304                 return false;
3305               }
3306             }
3307           }
3308         }
3309       }
3310     }
3311
3312     return true;
3313   }
3314
3315
3316   // another useful assertion for debugging
3317   public boolean noEmptyReachSetsInGraph() {
3318
3319     Iterator hrnItr = id2hrn.entrySet().iterator();
3320     while( hrnItr.hasNext() ) {
3321       Map.Entry      me  = (Map.Entry)      hrnItr.next();
3322       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3323
3324       if( !hrn.isOutOfContext() &&
3325           !hrn.isWiped()        &&
3326           hrn.getAlpha().isEmpty()
3327           ) {
3328         System.out.println( "!!! "+hrn+" has an empty ReachSet !!!" );
3329         return false;
3330       }
3331
3332       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3333       while( edgeItr.hasNext() ) {
3334         RefEdge edge = edgeItr.next();
3335
3336         if( edge.getBeta().isEmpty() ) {
3337           System.out.println( "!!! "+edge+" has an empty ReachSet !!!" );
3338           return false;
3339         }
3340       }
3341     }
3342
3343     return true;
3344   }
3345
3346
3347   public boolean everyReachStateWTrue() {
3348
3349     Iterator hrnItr = id2hrn.entrySet().iterator();
3350     while( hrnItr.hasNext() ) {
3351       Map.Entry      me  = (Map.Entry)      hrnItr.next();
3352       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
3353
3354       {
3355         Iterator<ReachState> stateItr = hrn.getAlpha().iterator();
3356         while( stateItr.hasNext() ) {
3357           ReachState state = stateItr.next();
3358
3359           if( !state.getPreds().equals( predsTrue ) ) {
3360             return false;
3361           }
3362         }
3363       }
3364
3365       Iterator<RefEdge> edgeItr = hrn.iteratorToReferencers();
3366       while( edgeItr.hasNext() ) {
3367         RefEdge edge = edgeItr.next();
3368
3369         Iterator<ReachState> stateItr = edge.getBeta().iterator();
3370         while( stateItr.hasNext() ) {
3371           ReachState state = stateItr.next();
3372
3373           if( !state.getPreds().equals( predsTrue ) ) {
3374             return false;
3375           }
3376         }
3377       }
3378     }
3379
3380     return true;
3381   }
3382
3383
3384
3385
3386   ////////////////////////////////////////////////////
3387   // in merge() and equals() methods the suffix A
3388   // represents the passed in graph and the suffix
3389   // B refers to the graph in this object
3390   // Merging means to take the incoming graph A and
3391   // merge it into B, so after the operation graph B
3392   // is the final result.
3393   ////////////////////////////////////////////////////
3394   protected void merge( ReachGraph rg ) {
3395
3396     if( rg == null ) {
3397       return;
3398     }
3399
3400     mergeNodes     ( rg );
3401     mergeRefEdges  ( rg );
3402     mergeAllocSites( rg );
3403   }
3404
3405   protected void mergeNodes( ReachGraph rg ) {
3406
3407     // start with heap region nodes
3408     Set      sA = rg.id2hrn.entrySet();
3409     Iterator iA = sA.iterator();
3410     while( iA.hasNext() ) {
3411       Map.Entry      meA  = (Map.Entry)      iA.next();
3412       Integer        idA  = (Integer)        meA.getKey();
3413       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3414
3415       // if this graph doesn't have a node the
3416       // incoming graph has, allocate it
3417       if( !id2hrn.containsKey( idA ) ) {
3418         HeapRegionNode hrnB = hrnA.copy();
3419         id2hrn.put( idA, hrnB );
3420
3421       } else {
3422         // otherwise this is a node present in both graphs
3423         // so make the new reachability set a union of the
3424         // nodes' reachability sets
3425         HeapRegionNode hrnB = id2hrn.get( idA );
3426         hrnB.setAlpha( Canonical.unionORpreds( hrnB.getAlpha(),
3427                                         hrnA.getAlpha()
3428                                         )
3429                        );
3430
3431         hrnB.setPreds( Canonical.join( hrnB.getPreds(),
3432                                        hrnA.getPreds()
3433                                        )
3434                        );
3435
3436
3437
3438         if( !hrnA.equals( hrnB ) ) {
3439           rg.writeGraph( "graphA" );
3440           this.writeGraph( "graphB" );
3441           throw new Error( "flagged not matching" );
3442         }
3443
3444
3445
3446       }
3447     }
3448
3449     // now add any variable nodes that are in graph B but
3450     // not in A
3451     sA = rg.td2vn.entrySet();
3452     iA = sA.iterator();
3453     while( iA.hasNext() ) {
3454       Map.Entry      meA = (Map.Entry)      iA.next();
3455       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3456       VariableNode   lnA = (VariableNode)   meA.getValue();
3457
3458       // if the variable doesn't exist in B, allocate and add it
3459       VariableNode lnB = getVariableNodeFromTemp( tdA );
3460     }
3461   }
3462
3463   protected void mergeRefEdges( ReachGraph rg ) {
3464
3465     // between heap regions
3466     Set      sA = rg.id2hrn.entrySet();
3467     Iterator iA = sA.iterator();
3468     while( iA.hasNext() ) {
3469       Map.Entry      meA  = (Map.Entry)      iA.next();
3470       Integer        idA  = (Integer)        meA.getKey();
3471       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3472
3473       Iterator<RefEdge> heapRegionsItrA = hrnA.iteratorToReferencees();
3474       while( heapRegionsItrA.hasNext() ) {
3475         RefEdge        edgeA     = heapRegionsItrA.next();
3476         HeapRegionNode hrnChildA = edgeA.getDst();
3477         Integer        idChildA  = hrnChildA.getID();
3478
3479         // at this point we know an edge in graph A exists
3480         // idA -> idChildA, does this exist in B?
3481         assert id2hrn.containsKey( idA );
3482         HeapRegionNode hrnB        = id2hrn.get( idA );
3483         RefEdge        edgeToMerge = null;
3484
3485         Iterator<RefEdge> heapRegionsItrB = hrnB.iteratorToReferencees();
3486         while( heapRegionsItrB.hasNext() &&
3487                edgeToMerge == null          ) {
3488
3489           RefEdge        edgeB     = heapRegionsItrB.next();
3490           HeapRegionNode hrnChildB = edgeB.getDst();
3491           Integer        idChildB  = hrnChildB.getID();
3492
3493           // don't use the RefEdge.equals() here because
3494           // we're talking about existence between graphs,
3495           // not intragraph equal
3496           if( idChildB.equals( idChildA ) &&
3497               edgeB.typeAndFieldEquals( edgeA ) ) {
3498
3499             edgeToMerge = edgeB;
3500           }
3501         }
3502
3503         // if the edge from A was not found in B,
3504         // add it to B.
3505         if( edgeToMerge == null ) {
3506           assert id2hrn.containsKey( idChildA );
3507           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3508           edgeToMerge = edgeA.copy();
3509           edgeToMerge.setSrc( hrnB );
3510           edgeToMerge.setDst( hrnChildB );
3511           addRefEdge( hrnB, hrnChildB, edgeToMerge );
3512         }
3513         // otherwise, the edge already existed in both graphs
3514         // so merge their reachability sets
3515         else {
3516           // just replace this beta set with the union
3517           assert edgeToMerge != null;
3518           edgeToMerge.setBeta(
3519                               Canonical.unionORpreds( edgeToMerge.getBeta(),
3520                                                edgeA.getBeta()
3521                                                )
3522                               );
3523           edgeToMerge.setPreds(
3524                                Canonical.join( edgeToMerge.getPreds(),
3525                                                edgeA.getPreds()
3526                                                )
3527                                );
3528         }
3529       }
3530     }
3531
3532     // and then again from variable nodes
3533     sA = rg.td2vn.entrySet();
3534     iA = sA.iterator();
3535     while( iA.hasNext() ) {
3536       Map.Entry      meA = (Map.Entry)      iA.next();
3537       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3538       VariableNode   vnA = (VariableNode)   meA.getValue();
3539
3540       Iterator<RefEdge> heapRegionsItrA = vnA.iteratorToReferencees();
3541       while( heapRegionsItrA.hasNext() ) {
3542         RefEdge        edgeA     = heapRegionsItrA.next();
3543         HeapRegionNode hrnChildA = edgeA.getDst();
3544         Integer        idChildA  = hrnChildA.getID();
3545
3546         // at this point we know an edge in graph A exists
3547         // tdA -> idChildA, does this exist in B?
3548         assert td2vn.containsKey( tdA );
3549         VariableNode vnB         = td2vn.get( tdA );
3550         RefEdge      edgeToMerge = null;
3551
3552         Iterator<RefEdge> heapRegionsItrB = vnB.iteratorToReferencees();
3553         while( heapRegionsItrB.hasNext() &&
3554                edgeToMerge == null          ) {
3555
3556           RefEdge        edgeB     = heapRegionsItrB.next();
3557           HeapRegionNode hrnChildB = edgeB.getDst();
3558           Integer        idChildB  = hrnChildB.getID();
3559
3560           // don't use the RefEdge.equals() here because
3561           // we're talking about existence between graphs
3562           if( idChildB.equals( idChildA ) &&
3563               edgeB.typeAndFieldEquals( edgeA ) ) {
3564
3565             edgeToMerge = edgeB;
3566           }
3567         }
3568
3569         // if the edge from A was not found in B,
3570         // add it to B.
3571         if( edgeToMerge == null ) {
3572           assert id2hrn.containsKey( idChildA );
3573           HeapRegionNode hrnChildB = id2hrn.get( idChildA );
3574           edgeToMerge = edgeA.copy();
3575           edgeToMerge.setSrc( vnB );
3576           edgeToMerge.setDst( hrnChildB );
3577           addRefEdge( vnB, hrnChildB, edgeToMerge );
3578         }
3579         // otherwise, the edge already existed in both graphs
3580         // so merge their reachability sets
3581         else {
3582           // just replace this beta set with the union
3583           edgeToMerge.setBeta( Canonical.unionORpreds( edgeToMerge.getBeta(),
3584                                                 edgeA.getBeta()
3585                                                 )
3586                                );
3587           edgeToMerge.setPreds( Canonical.join( edgeToMerge.getPreds(),
3588                                                 edgeA.getPreds()
3589                                                 )
3590                                 );
3591         }
3592       }
3593     }
3594   }
3595
3596   protected void mergeAllocSites( ReachGraph rg ) {
3597     allocSites.addAll( rg.allocSites );
3598   }
3599
3600
3601
3602   static boolean dbgEquals = false;
3603
3604
3605   // it is necessary in the equals() member functions
3606   // to "check both ways" when comparing the data
3607   // structures of two graphs.  For instance, if all
3608   // edges between heap region nodes in graph A are
3609   // present and equal in graph B it is not sufficient
3610   // to say the graphs are equal.  Consider that there
3611   // may be edges in graph B that are not in graph A.
3612   // the only way to know that all edges in both graphs
3613   // are equally present is to iterate over both data
3614   // structures and compare against the other graph.
3615   public boolean equals( ReachGraph rg ) {
3616
3617     if( rg == null ) {
3618       if( dbgEquals ) {
3619         System.out.println( "rg is null" );
3620       }
3621       return false;
3622     }
3623
3624     if( !areHeapRegionNodesEqual( rg ) ) {
3625       if( dbgEquals ) {
3626         System.out.println( "hrn not equal" );
3627       }
3628       return false;
3629     }
3630
3631     if( !areVariableNodesEqual( rg ) ) {
3632       if( dbgEquals ) {
3633         System.out.println( "vars not equal" );
3634       }
3635       return false;
3636     }
3637
3638     if( !areRefEdgesEqual( rg ) ) {
3639       if( dbgEquals ) {
3640         System.out.println( "edges not equal" );
3641       }
3642       return false;
3643     }
3644
3645     // if everything is equal up to this point,
3646     // assert that allocSites is also equal--
3647     // this data is redundant but kept for efficiency
3648     assert allocSites.equals( rg.allocSites );
3649
3650     return true;
3651   }
3652
3653
3654   protected boolean areHeapRegionNodesEqual( ReachGraph rg ) {
3655
3656     if( !areallHRNinAalsoinBandequal( this, rg ) ) {
3657       return false;
3658     }
3659
3660     if( !areallHRNinAalsoinBandequal( rg, this ) ) {
3661       return false;
3662     }
3663
3664     return true;
3665   }
3666
3667   static protected boolean areallHRNinAalsoinBandequal( ReachGraph rgA,
3668                                                         ReachGraph rgB ) {
3669     Set      sA = rgA.id2hrn.entrySet();
3670     Iterator iA = sA.iterator();
3671     while( iA.hasNext() ) {
3672       Map.Entry      meA  = (Map.Entry)      iA.next();
3673       Integer        idA  = (Integer)        meA.getKey();
3674       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3675
3676       if( !rgB.id2hrn.containsKey( idA ) ) {
3677         return false;
3678       }
3679
3680       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3681       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3682         return false;
3683       }
3684     }
3685
3686     return true;
3687   }
3688
3689   protected boolean areVariableNodesEqual( ReachGraph rg ) {
3690
3691     if( !areallVNinAalsoinBandequal( this, rg ) ) {
3692       return false;
3693     }
3694
3695     if( !areallVNinAalsoinBandequal( rg, this ) ) {
3696       return false;
3697     }
3698
3699     return true;
3700   }
3701
3702   static protected boolean areallVNinAalsoinBandequal( ReachGraph rgA,
3703                                                        ReachGraph rgB ) {
3704     Set      sA = rgA.td2vn.entrySet();
3705     Iterator iA = sA.iterator();
3706     while( iA.hasNext() ) {
3707       Map.Entry      meA = (Map.Entry)      iA.next();
3708       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3709
3710       if( !rgB.td2vn.containsKey( tdA ) ) {
3711         return false;
3712       }
3713     }
3714
3715     return true;
3716   }
3717
3718
3719   protected boolean areRefEdgesEqual( ReachGraph rg ) {
3720     if( !areallREinAandBequal( this, rg ) ) {
3721       return false;
3722     }
3723
3724     if( !areallREinAandBequal( rg, this ) ) {
3725       return false;
3726     }
3727
3728     return true;
3729   }
3730
3731   static protected boolean areallREinAandBequal( ReachGraph rgA,
3732                                                  ReachGraph rgB ) {
3733
3734     // check all the heap region->heap region edges
3735     Set      sA = rgA.id2hrn.entrySet();
3736     Iterator iA = sA.iterator();
3737     while( iA.hasNext() ) {
3738       Map.Entry      meA  = (Map.Entry)      iA.next();
3739       Integer        idA  = (Integer)        meA.getKey();
3740       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3741
3742       // we should have already checked that the same
3743       // heap regions exist in both graphs
3744       assert rgB.id2hrn.containsKey( idA );
3745
3746       if( !areallREfromAequaltoB( rgA, hrnA, rgB ) ) {
3747         return false;
3748       }
3749
3750       // then check every edge in B for presence in A, starting
3751       // from the same parent HeapRegionNode
3752       HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3753
3754       if( !areallREfromAequaltoB( rgB, hrnB, rgA ) ) {
3755         return false;
3756       }
3757     }
3758
3759     // then check all the variable->heap region edges
3760     sA = rgA.td2vn.entrySet();
3761     iA = sA.iterator();
3762     while( iA.hasNext() ) {
3763       Map.Entry      meA = (Map.Entry)      iA.next();
3764       TempDescriptor tdA = (TempDescriptor) meA.getKey();
3765       VariableNode   vnA = (VariableNode)   meA.getValue();
3766
3767       // we should have already checked that the same
3768       // label nodes exist in both graphs
3769       assert rgB.td2vn.containsKey( tdA );
3770
3771       if( !areallREfromAequaltoB( rgA, vnA, rgB ) ) {
3772         return false;
3773       }
3774
3775       // then check every edge in B for presence in A, starting
3776       // from the same parent VariableNode
3777       VariableNode vnB = rgB.td2vn.get( tdA );
3778
3779       if( !areallREfromAequaltoB( rgB, vnB, rgA ) ) {
3780         return false;
3781       }
3782     }
3783
3784     return true;
3785   }
3786
3787
3788   static protected boolean areallREfromAequaltoB( ReachGraph rgA,
3789                                                   RefSrcNode rnA,
3790                                                   ReachGraph rgB ) {
3791
3792     Iterator<RefEdge> itrA = rnA.iteratorToReferencees();
3793     while( itrA.hasNext() ) {
3794       RefEdge        edgeA     = itrA.next();
3795       HeapRegionNode hrnChildA = edgeA.getDst();
3796       Integer        idChildA  = hrnChildA.getID();
3797
3798       assert rgB.id2hrn.containsKey( idChildA );
3799
3800       // at this point we know an edge in graph A exists
3801       // rnA -> idChildA, does this exact edge exist in B?
3802       boolean edgeFound = false;
3803
3804       RefSrcNode rnB = null;
3805       if( rnA instanceof HeapRegionNode ) {
3806         HeapRegionNode hrnA = (HeapRegionNode) rnA;
3807         rnB = rgB.id2hrn.get( hrnA.getID() );
3808       } else {
3809         VariableNode vnA = (VariableNode) rnA;
3810         rnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3811       }
3812
3813       Iterator<RefEdge> itrB = rnB.iteratorToReferencees();
3814       while( itrB.hasNext() ) {
3815         RefEdge        edgeB     = itrB.next();
3816         HeapRegionNode hrnChildB = edgeB.getDst();
3817         Integer        idChildB  = hrnChildB.getID();
3818
3819         if( idChildA.equals( idChildB ) &&
3820             edgeA.typeAndFieldEquals( edgeB ) ) {
3821
3822           // there is an edge in the right place with the right field,
3823           // but do they have the same attributes?
3824           if( edgeA.getBeta().equals( edgeB.getBeta() ) &&
3825               edgeA.equalsPreds( edgeB )
3826               ) {
3827             edgeFound = true;
3828           }
3829         }
3830       }
3831
3832       if( !edgeFound ) {
3833         return false;
3834       }
3835     }
3836
3837     return true;
3838   }
3839
3840
3841   // can be used to assert monotonicity
3842   static public boolean isNoSmallerThan( ReachGraph rgA,
3843                                          ReachGraph rgB ) {
3844
3845     //System.out.println( "*** Asking if A is no smaller than B ***" );
3846
3847
3848     Iterator iA = rgA.id2hrn.entrySet().iterator();
3849     while( iA.hasNext() ) {
3850       Map.Entry      meA  = (Map.Entry)      iA.next();
3851       Integer        idA  = (Integer)        meA.getKey();
3852       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3853
3854       if( !rgB.id2hrn.containsKey( idA ) ) {
3855         System.out.println( "  regions smaller" );
3856         return false;
3857       }
3858
3859       //HeapRegionNode hrnB = rgB.id2hrn.get( idA );
3860       /* NOT EQUALS, NO SMALLER THAN!
3861       if( !hrnA.equalsIncludingAlphaAndPreds( hrnB ) ) {
3862         System.out.println( "  regions smaller" );
3863         return false;
3864       }
3865       */
3866     }
3867
3868     // this works just fine, no smaller than
3869     if( !areallVNinAalsoinBandequal( rgA, rgB ) ) {
3870       System.out.println( "  vars smaller:" );
3871       System.out.println( "    A:"+rgA.td2vn.keySet() );
3872       System.out.println( "    B:"+rgB.td2vn.keySet() );
3873       return false;
3874     }
3875
3876
3877     iA = rgA.id2hrn.entrySet().iterator();
3878     while( iA.hasNext() ) {
3879       Map.Entry      meA  = (Map.Entry)      iA.next();
3880       Integer        idA  = (Integer)        meA.getKey();
3881       HeapRegionNode hrnA = (HeapRegionNode) meA.getValue();
3882
3883       Iterator<RefEdge> reItr = hrnA.iteratorToReferencers();
3884       while( reItr.hasNext() ) {
3885         RefEdge    edgeA = reItr.next();
3886         RefSrcNode rsnA  = edgeA.getSrc();
3887
3888         // we already checked that nodes were present
3889         HeapRegionNode hrnB = rgB.id2hrn.get( hrnA.getID() );
3890         assert hrnB != null;
3891
3892         RefSrcNode rsnB;
3893         if( rsnA instanceof VariableNode ) {
3894           VariableNode vnA = (VariableNode) rsnA;
3895           rsnB = rgB.td2vn.get( vnA.getTempDescriptor() );
3896
3897         } else {
3898           HeapRegionNode hrnSrcA = (HeapRegionNode) rsnA;
3899           rsnB = rgB.id2hrn.get( hrnSrcA.getID() );
3900         }
3901         assert rsnB != null;
3902
3903         RefEdge edgeB = rsnB.getReferenceTo( hrnB,
3904                                              edgeA.getType(),
3905                                              edgeA.getField()
3906                                              );
3907         if( edgeB == null ) {
3908           System.out.println( "  edges smaller:" );
3909           return false;
3910         }
3911
3912         // REMEMBER, IS NO SMALLER THAN
3913         /*
3914           System.out.println( "  edges smaller" );
3915           return false;
3916           }
3917         */
3918
3919       }
3920     }
3921
3922
3923     return true;
3924   }
3925
3926
3927
3928
3929
3930   // this analysis no longer has the "match anything"
3931   // type which was represented by null
3932   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3933                                              TypeDescriptor td2 ) {
3934     assert td1 != null;
3935     assert td2 != null;
3936
3937     if( td1.isNull() ) {
3938       return td2;
3939     }
3940     if( td2.isNull() ) {
3941       return td1;
3942     }
3943     return typeUtil.mostSpecific( td1, td2 );
3944   }
3945
3946   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3947                                              TypeDescriptor td2,
3948                                              TypeDescriptor td3 ) {
3949
3950     return mostSpecificType( td1,
3951                              mostSpecificType( td2, td3 )
3952                              );
3953   }
3954
3955   protected TypeDescriptor mostSpecificType( TypeDescriptor td1,
3956                                              TypeDescriptor td2,
3957                                              TypeDescriptor td3,
3958                                              TypeDescriptor td4 ) {
3959
3960     return mostSpecificType( mostSpecificType( td1, td2 ),
3961                              mostSpecificType( td3, td4 )
3962                              );
3963   }
3964
3965   protected boolean isSuperiorType( TypeDescriptor possibleSuper,
3966                                     TypeDescriptor possibleChild ) {
3967     assert possibleSuper != null;
3968     assert possibleChild != null;
3969
3970     if( possibleSuper.isNull() ||
3971         possibleChild.isNull() ) {
3972       return true;
3973     }
3974
3975     return typeUtil.isSuperorType( possibleSuper, possibleChild );
3976   }
3977
3978
3979   protected boolean hasMatchingField( HeapRegionNode src,
3980                                       RefEdge        edge ) {
3981
3982     TypeDescriptor tdSrc = src.getType();
3983     assert tdSrc != null;
3984
3985     if( tdSrc.isArray() ) {
3986       TypeDescriptor td = edge.getType();
3987       assert td != null;
3988
3989       TypeDescriptor tdSrcDeref = tdSrc.dereference();
3990       assert tdSrcDeref != null;
3991
3992       if( !typeUtil.isSuperorType( tdSrcDeref, td ) ) {
3993         return false;
3994       }
3995
3996       return edge.getField().equals( DisjointAnalysis.arrayElementFieldName );
3997     }
3998
3999     // if it's not a class, it doesn't have any fields to match
4000     if( !tdSrc.isClass() ) {
4001       return false;
4002     }
4003
4004     ClassDescriptor cd = tdSrc.getClassDesc();
4005     while( cd != null ) {
4006       Iterator fieldItr = cd.getFields();
4007
4008       while( fieldItr.hasNext() ) {
4009         FieldDescriptor fd = (FieldDescriptor) fieldItr.next();
4010
4011         if( fd.getType().equals( edge.getType() ) &&
4012             fd.getSymbol().equals( edge.getField() ) ) {
4013           return true;
4014         }
4015       }
4016
4017       cd = cd.getSuperDesc();
4018     }
4019
4020     // otherwise it is a class with fields
4021     // but we didn't find a match
4022     return false;
4023   }
4024
4025   protected boolean hasMatchingType( RefEdge        edge,
4026                                      HeapRegionNode dst  ) {
4027
4028     // if the region has no type, matches everything
4029     TypeDescriptor tdDst = dst.getType();
4030     assert tdDst != null;
4031
4032     // if the type is not a class or an array, don't
4033     // match because primitives are copied, no aliases
4034     ClassDescriptor cdDst = tdDst.getClassDesc();
4035     if( cdDst == null && !tdDst.isArray() ) {
4036       return false;
4037     }
4038
4039     // if the edge type is null, it matches everything
4040     TypeDescriptor tdEdge = edge.getType();
4041     assert tdEdge != null;
4042
4043     return typeUtil.isSuperorType( tdEdge, tdDst );
4044   }
4045
4046
4047
4048   // the default signature for quick-and-dirty debugging
4049   public void writeGraph( String graphName ) {
4050     writeGraph( graphName,
4051                 true, // write labels
4052                 true, // label select
4053                 true, // prune garbage
4054                 true, // hide subset reachability
4055                 true, // hide edge taints
4056                 null  // in-context boundary
4057                 );
4058   }
4059
4060   public void writeGraph( String  graphName,
4061                           boolean writeLabels,
4062                           boolean labelSelect,
4063                           boolean pruneGarbage,
4064                           boolean hideSubsetReachability,
4065                           boolean hideEdgeTaints
4066                           ) {
4067     writeGraph( graphName,
4068                 writeLabels,
4069                 labelSelect,
4070                 pruneGarbage,
4071                 hideSubsetReachability,
4072                 hideEdgeTaints,
4073                 null );
4074   }
4075
4076   public void writeGraph( String       graphName,
4077                           boolean      writeLabels,
4078                           boolean      labelSelect,
4079                           boolean      pruneGarbage,
4080                           boolean      hideSubsetReachability,
4081                           boolean      hideEdgeTaints,
4082                           Set<Integer> callerNodeIDsCopiedToCallee
4083                           ) {
4084
4085     try {
4086       // remove all non-word characters from the graph name so
4087       // the filename and identifier in dot don't cause errors
4088       graphName = graphName.replaceAll( "[\\W]", "" );
4089
4090       BufferedWriter bw =
4091         new BufferedWriter( new FileWriter( graphName+".dot" ) );
4092
4093       bw.write( "digraph "+graphName+" {\n" );
4094
4095
4096       // this is an optional step to form the callee-reachable
4097       // "cut-out" into a DOT cluster for visualization
4098       if( callerNodeIDsCopiedToCallee != null ) {
4099
4100         bw.write( "  subgraph cluster0 {\n" );
4101         bw.write( "    color=blue;\n" );
4102
4103         Iterator i = id2hrn.entrySet().iterator();
4104         while( i.hasNext() ) {
4105           Map.Entry      me  = (Map.Entry)      i.next();
4106           HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4107
4108           if( callerNodeIDsCopiedToCallee.contains( hrn.getID() ) ) {
4109             bw.write( "    "+hrn.toString()+
4110                       hrn.toStringDOT( hideSubsetReachability )+
4111                       ";\n" );
4112
4113           }
4114         }
4115
4116         bw.write( "  }\n" );
4117       }
4118
4119
4120       Set<HeapRegionNode> visited = new HashSet<HeapRegionNode>();
4121
4122       // then visit every heap region node
4123       Iterator i = id2hrn.entrySet().iterator();
4124       while( i.hasNext() ) {
4125         Map.Entry      me  = (Map.Entry)      i.next();
4126         HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4127
4128         // only visit nodes worth writing out--for instance
4129         // not every node at an allocation is referenced
4130         // (think of it as garbage-collected), etc.
4131         if( !pruneGarbage        ||
4132             hrn.isOutOfContext()
4133             ) {
4134
4135           if( !visited.contains( hrn ) ) {
4136             traverseHeapRegionNodes( hrn,
4137                                      bw,
4138                                      null,
4139                                      visited,
4140                                      hideSubsetReachability,
4141                                      hideEdgeTaints,
4142                                      callerNodeIDsCopiedToCallee );
4143           }
4144         }
4145       }
4146
4147       bw.write( "  graphTitle[label=\""+graphName+"\",shape=box];\n" );
4148
4149
4150       // then visit every label node, useful for debugging
4151       if( writeLabels ) {
4152         i = td2vn.entrySet().iterator();
4153         while( i.hasNext() ) {
4154           Map.Entry    me = (Map.Entry)    i.next();
4155           VariableNode vn = (VariableNode) me.getValue();
4156
4157           if( labelSelect ) {
4158             String labelStr = vn.getTempDescriptorString();
4159             if( labelStr.startsWith( "___temp" )     ||
4160                 labelStr.startsWith( "___dst" )      ||
4161                 labelStr.startsWith( "___srctmp" )   ||
4162                 labelStr.startsWith( "___neverused" )
4163                 ) {
4164               continue;
4165             }
4166           }
4167
4168           Iterator<RefEdge> heapRegionsItr = vn.iteratorToReferencees();
4169           while( heapRegionsItr.hasNext() ) {
4170             RefEdge        edge = heapRegionsItr.next();
4171             HeapRegionNode hrn  = edge.getDst();
4172
4173             if( !visited.contains( hrn ) ) {
4174               traverseHeapRegionNodes( hrn,
4175                                        bw,
4176                                        null,
4177                                        visited,
4178                                        hideSubsetReachability,
4179                                        hideEdgeTaints,
4180                                        callerNodeIDsCopiedToCallee );
4181             }
4182
4183             bw.write( "  "+vn.toString()+
4184                       " -> "+hrn.toString()+
4185                       edge.toStringDOT( hideSubsetReachability, "" )+
4186                       ";\n" );
4187           }
4188         }
4189       }
4190
4191       bw.write( "}\n" );
4192       bw.close();
4193
4194     } catch( IOException e ) {
4195       throw new Error( "Error writing out DOT graph "+graphName );
4196     }
4197   }
4198
4199   protected void traverseHeapRegionNodes( HeapRegionNode      hrn,
4200                                           BufferedWriter      bw,
4201                                           TempDescriptor      td,
4202                                           Set<HeapRegionNode> visited,
4203                                           boolean             hideSubsetReachability,
4204                                           boolean             hideEdgeTaints,
4205                                           Set<Integer>        callerNodeIDsCopiedToCallee
4206                                           ) throws java.io.IOException {
4207
4208     if( visited.contains( hrn ) ) {
4209       return;
4210     }
4211     visited.add( hrn );
4212
4213     // if we're drawing the callee-view subgraph, only
4214     // write out the node info if it hasn't already been
4215     // written
4216     if( callerNodeIDsCopiedToCallee == null ||
4217         !callerNodeIDsCopiedToCallee.contains( hrn.getID() )
4218         ) {
4219       bw.write( "  "+hrn.toString()+
4220                 hrn.toStringDOT( hideSubsetReachability )+
4221                 ";\n" );
4222     }
4223
4224     Iterator<RefEdge> childRegionsItr = hrn.iteratorToReferencees();
4225     while( childRegionsItr.hasNext() ) {
4226       RefEdge        edge     = childRegionsItr.next();
4227       HeapRegionNode hrnChild = edge.getDst();
4228
4229       if( callerNodeIDsCopiedToCallee != null &&
4230           (edge.getSrc() instanceof HeapRegionNode) ) {
4231         HeapRegionNode hrnSrc = (HeapRegionNode) edge.getSrc();
4232         if( callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()        ) &&
4233             callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4234             ) {
4235           bw.write( "  "+hrn.toString()+
4236                     " -> "+hrnChild.toString()+
4237                     edge.toStringDOT( hideSubsetReachability, ",color=blue" )+
4238                     ";\n");
4239         } else if( !callerNodeIDsCopiedToCallee.contains( hrnSrc.getID()       ) &&
4240                    callerNodeIDsCopiedToCallee.contains( edge.getDst().getID() )
4241                    ) {
4242           bw.write( "  "+hrn.toString()+
4243                     " -> "+hrnChild.toString()+
4244                     edge.toStringDOT( hideSubsetReachability, ",color=blue,style=dashed" )+
4245                     ";\n");
4246         } else {
4247           bw.write( "  "+hrn.toString()+
4248                     " -> "+hrnChild.toString()+
4249                     edge.toStringDOT( hideSubsetReachability, "" )+
4250                     ";\n");
4251         }
4252       } else {
4253         bw.write( "  "+hrn.toString()+
4254                   " -> "+hrnChild.toString()+
4255                   edge.toStringDOT( hideSubsetReachability, "" )+
4256                   ";\n");
4257       }
4258
4259       traverseHeapRegionNodes( hrnChild,
4260                                bw,
4261                                td,
4262                                visited,
4263                                hideSubsetReachability,
4264                                hideEdgeTaints,
4265                                callerNodeIDsCopiedToCallee );
4266     }
4267   }
4268
4269
4270
4271
4272
4273   public Set<HeapRegionNode> findCommonReachableNodes( ReachSet proofOfSharing ) {
4274
4275     Set<HeapRegionNode> exhibitProofState =
4276       new HashSet<HeapRegionNode>();
4277
4278     Iterator hrnItr = id2hrn.entrySet().iterator();
4279     while( hrnItr.hasNext() ) {
4280       Map.Entry      me  = (Map.Entry) hrnItr.next();
4281       HeapRegionNode hrn = (HeapRegionNode) me.getValue();
4282
4283       ReachSet intersection =
4284         Canonical.intersection( proofOfSharing,
4285                                 hrn.getAlpha()
4286                                 );
4287       if( !intersection.isEmpty() ) {
4288         assert !hrn.isOutOfContext();
4289         exhibitProofState.add( hrn );
4290       }
4291     }
4292
4293     return exhibitProofState;
4294   }
4295
4296
4297   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn1,
4298                                                    HeapRegionNode hrn2) {
4299     assert hrn1 != null;
4300     assert hrn2 != null;
4301
4302     assert !hrn1.isOutOfContext();
4303     assert !hrn2.isOutOfContext();
4304
4305     assert belongsToThis( hrn1 );
4306     assert belongsToThis( hrn2 );
4307
4308     assert !hrn1.getID().equals( hrn2.getID() );
4309
4310
4311     // then get the various tokens for these heap regions
4312     ReachTuple h1 =
4313       ReachTuple.factory( hrn1.getID(),
4314                           !hrn1.isSingleObject(), // multi?
4315                           ReachTuple.ARITY_ONE,
4316                           false );                // ooc?
4317
4318     ReachTuple h1star = null;
4319     if( !hrn1.isSingleObject() ) {
4320       h1star =
4321         ReachTuple.factory( hrn1.getID(),
4322                             !hrn1.isSingleObject(),
4323                             ReachTuple.ARITY_ZEROORMORE,
4324                             false );
4325     }
4326
4327     ReachTuple h2 =
4328       ReachTuple.factory( hrn2.getID(),
4329                           !hrn2.isSingleObject(),
4330                           ReachTuple.ARITY_ONE,
4331                           false );
4332
4333     ReachTuple h2star = null;
4334     if( !hrn2.isSingleObject() ) {
4335       h2star =
4336         ReachTuple.factory( hrn2.getID(),
4337                             !hrn2.isSingleObject(),
4338                             ReachTuple.ARITY_ZEROORMORE,
4339                             false );
4340     }
4341
4342     // then get the merged beta of all out-going edges from these heap
4343     // regions
4344
4345     ReachSet beta1 = ReachSet.factory();
4346     Iterator<RefEdge> itrEdge = hrn1.iteratorToReferencees();
4347     while (itrEdge.hasNext()) {
4348       RefEdge edge = itrEdge.next();
4349       beta1 = Canonical.unionORpreds(beta1, edge.getBeta());
4350     }
4351
4352     ReachSet beta2 = ReachSet.factory();
4353     itrEdge = hrn2.iteratorToReferencees();
4354     while (itrEdge.hasNext()) {
4355       RefEdge edge = itrEdge.next();
4356       beta2 = Canonical.unionORpreds(beta2, edge.getBeta());
4357     }
4358
4359     ReachSet proofOfSharing = ReachSet.factory();
4360
4361     proofOfSharing =
4362       Canonical.unionORpreds( proofOfSharing,
4363                               beta1.getStatesWithBoth( h1, h2 )
4364                               );
4365     proofOfSharing =
4366       Canonical.unionORpreds( proofOfSharing,
4367                               beta2.getStatesWithBoth( h1, h2 )
4368                               );
4369
4370     if( !hrn1.isSingleObject() ) {
4371       proofOfSharing =
4372         Canonical.unionORpreds( proofOfSharing,
4373                                 beta1.getStatesWithBoth( h1star, h2 )
4374                                 );
4375       proofOfSharing =
4376         Canonical.unionORpreds( proofOfSharing,
4377                                 beta2.getStatesWithBoth( h1star, h2 )
4378                                 );
4379     }
4380
4381     if( !hrn2.isSingleObject() ) {
4382       proofOfSharing =
4383         Canonical.unionORpreds( proofOfSharing,
4384                                 beta1.getStatesWithBoth( h1, h2star )
4385                                 );
4386       proofOfSharing =
4387         Canonical.unionORpreds( proofOfSharing,
4388                                 beta2.getStatesWithBoth( h1, h2star )
4389                                 );
4390     }
4391
4392     if( !hrn1.isSingleObject() &&
4393         !hrn2.isSingleObject()
4394         ) {
4395       proofOfSharing =
4396         Canonical.unionORpreds( proofOfSharing,
4397                                 beta1.getStatesWithBoth( h1star, h2star )
4398                                 );
4399       proofOfSharing =
4400         Canonical.unionORpreds( proofOfSharing,
4401                                 beta2.getStatesWithBoth( h1star, h2star )
4402                                 );
4403     }
4404
4405     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4406     if( !proofOfSharing.isEmpty() ) {
4407       common = findCommonReachableNodes( proofOfSharing );
4408       if( !DISABLE_STRONG_UPDATES &&
4409           !DISABLE_GLOBAL_SWEEP
4410           ) {
4411         assert !common.isEmpty();
4412       }
4413     }
4414
4415     return common;
4416   }
4417
4418   // this version of the above method checks whether there is sharing
4419   // among the objects in a summary node
4420   public Set<HeapRegionNode> mayReachSharedObjects(HeapRegionNode hrn) {
4421     assert hrn != null;
4422     assert hrn.isNewSummary();
4423     assert !hrn.isOutOfContext();
4424     assert belongsToThis( hrn );
4425
4426     ReachTuple hstar =
4427       ReachTuple.factory( hrn.getID(),
4428                           true,    // multi
4429                           ReachTuple.ARITY_ZEROORMORE,
4430                           false ); // ooc
4431
4432     // then get the merged beta of all out-going edges from
4433     // this heap region
4434
4435     ReachSet beta = ReachSet.factory();
4436     Iterator<RefEdge> itrEdge = hrn.iteratorToReferencees();
4437     while (itrEdge.hasNext()) {
4438       RefEdge edge = itrEdge.next();
4439       beta = Canonical.unionORpreds(beta, edge.getBeta());
4440     }
4441
4442     ReachSet proofOfSharing = ReachSet.factory();
4443
4444     proofOfSharing =
4445       Canonical.unionORpreds( proofOfSharing,
4446                               beta.getStatesWithBoth( hstar, hstar )
4447                               );
4448
4449     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4450     if( !proofOfSharing.isEmpty() ) {
4451       common = findCommonReachableNodes( proofOfSharing );
4452       if( !DISABLE_STRONG_UPDATES &&
4453           !DISABLE_GLOBAL_SWEEP
4454           ) {
4455         assert !common.isEmpty();
4456       }
4457     }
4458
4459     return common;
4460   }
4461
4462
4463   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4464                                                    Integer paramIndex1,
4465                                                    Integer paramIndex2) {
4466
4467     // get parameter's heap regions
4468     TempDescriptor paramTemp1 = fm.getParameter(paramIndex1.intValue());
4469     assert this.hasVariable( paramTemp1 );
4470     VariableNode paramVar1 = getVariableNodeFromTemp(paramTemp1);
4471
4472
4473     if( !(paramVar1.getNumReferencees() == 1) ) {
4474       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp1 );
4475       writeGraph( "whatup" );
4476     }
4477
4478
4479     assert paramVar1.getNumReferencees() == 1;
4480     RefEdge paramEdge1 = paramVar1.iteratorToReferencees().next();
4481     HeapRegionNode hrnParam1 = paramEdge1.getDst();
4482
4483     TempDescriptor paramTemp2 = fm.getParameter(paramIndex2.intValue());
4484     assert this.hasVariable( paramTemp2 );
4485     VariableNode paramVar2 = getVariableNodeFromTemp(paramTemp2);
4486
4487     if( !(paramVar2.getNumReferencees() == 1) ) {
4488       System.out.println( "\n  fm="+fm+"\n  param="+paramTemp2 );
4489       writeGraph( "whatup" );
4490     }
4491
4492     assert paramVar2.getNumReferencees() == 1;
4493     RefEdge paramEdge2 = paramVar2.iteratorToReferencees().next();
4494     HeapRegionNode hrnParam2 = paramEdge2.getDst();
4495
4496     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4497     common.addAll(mayReachSharedObjects(hrnParam1, hrnParam2));
4498
4499     return common;
4500   }
4501
4502   public Set<HeapRegionNode> mayReachSharedObjects(FlatMethod fm,
4503                                                    Integer paramIndex,
4504                                                    AllocSite as) {
4505
4506     // get parameter's heap regions
4507     TempDescriptor paramTemp = fm.getParameter(paramIndex.intValue());
4508     assert this.hasVariable( paramTemp );
4509     VariableNode paramVar = getVariableNodeFromTemp(paramTemp);
4510     assert paramVar.getNumReferencees() == 1;
4511     RefEdge paramEdge = paramVar.iteratorToReferencees().next();
4512     HeapRegionNode hrnParam = paramEdge.getDst();
4513
4514     // get summary node
4515     HeapRegionNode hrnSummary=null;
4516     if(id2hrn.containsKey(as.getSummary())){
4517       // if summary node doesn't exist, ignore this case
4518       hrnSummary = id2hrn.get(as.getSummary());
4519       assert hrnSummary != null;
4520     }
4521
4522     Set<HeapRegionNode> common  = new HashSet<HeapRegionNode>();
4523     if(hrnSummary!=null){
4524       common.addAll( mayReachSharedObjects(hrnParam, hrnSummary) );
4525     }
4526
4527     // check for other nodes
4528     for (int i = 0; i < as.getAllocationDepth(); ++i) {
4529
4530       assert id2hrn.containsKey(as.getIthOldest(i));
4531       HeapRegionNode hrnIthOldest = id2hrn.get(as.getIthOldest(i));
4532       assert hrnIthOldest != null;
4533
4534       common.addAll(mayReachSharedObjects(hrnParam, hrnIthOldest));
4535
4536     }
4537
4538     return common;
4539   }
4540
4541   public Set<HeapRegionNode> mayReachSharedObjects(AllocSite as1,
4542                                                    AllocSite as2) {
4543
4544     // get summary node 1's alpha
4545     Integer idSum1 = as1.getSummary();
4546     HeapRegionNode hrnSum1=null;
4547     if(id2hrn.containsKey(idSum1)){
4548       hrnSum1 = id2hrn.get(idSum1);
4549     }
4550
4551     // get summary node 2's alpha
4552     Integer idSum2 = as2.getSummary();
4553     HeapRegionNode hrnSum2=null;
4554     if(id2hrn.containsKey(idSum2)){
4555       hrnSum2 = id2hrn.get(idSum2);
4556     }
4557
4558     Set<HeapRegionNode> common = new HashSet<HeapRegionNode>();
4559     if(hrnSum1!=null && hrnSum2!=null && hrnSum1!=hrnSum2){
4560       common.addAll(mayReachSharedObjects(hrnSum1, hrnSum2));
4561     }
4562
4563     if(hrnSum1!=null){
4564       // ask if objects from this summary share among each other
4565       common.addAll(mayReachSharedObjects(hrnSum1));
4566     }
4567
4568     // check sum2 against alloc1 nodes
4569     if(hrnSum2!=null){
4570       for (int i = 0; i < as1.getAllocationDepth(); ++i) {
4571         Integer idI1 = as1.getIthOldest(i);
4572         assert id2hrn.containsKey(idI1);
4573         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4574         assert hrnI1 != null;
4575         common.addAll(mayReachSharedObjects(hrnI1, hrnSum2));
4576       }
4577
4578       // also ask if objects from this summary share among each other
4579       common.addAll(mayReachSharedObjects(hrnSum2));
4580     }
4581
4582     // check sum1 against alloc2 nodes
4583     for (int i = 0; i < as2.getAllocationDepth(); ++i) {
4584       Integer idI2 = as2.getIthOldest(i);
4585       assert id2hrn.containsKey(idI2);
4586       HeapRegionNode hrnI2 = id2hrn.get(idI2);
4587       assert hrnI2 != null;
4588
4589       if(hrnSum1!=null){
4590         common.addAll(mayReachSharedObjects(hrnSum1, hrnI2));
4591       }
4592
4593       // while we're at it, do an inner loop for alloc2 vs alloc1 nodes
4594       for (int j = 0; j < as1.getAllocationDepth(); ++j) {
4595         Integer idI1 = as1.getIthOldest(j);
4596
4597         // if these are the same site, don't look for the same token, no
4598         // alias.
4599         // different tokens of the same site could alias together though
4600         if (idI1.equals(idI2)) {
4601           continue;
4602         }
4603
4604         HeapRegionNode hrnI1 = id2hrn.get(idI1);
4605
4606         common.addAll(mayReachSharedObjects(hrnI1, hrnI2));
4607       }
4608     }
4609
4610     return common;
4611   }
4612 }