Robust/src/Analysis/OoOJava/VarSrcTokTable.java

   1 package Analysis.OoOJava;
   2
   3 import IR.*;
   4 import IR.Flat.*;
   5 import java.util.*;
   6 import java.io.*;
   7 import Analysis.Pointer.MySet;
   8
   9 // This class formerly had lazy consistency properties, but
  10 // it is being changed so that the full set and the extra
  11 // hash tables to access the full set efficiently by different
  12 // elements will be consistent after EVERY operation.  Also,
  13 // a consistent assert method allows a debugger to ask whether
  14 // an operation has produced an inconsistent VarSrcTokTable.
  15
  16 // in an effort to make sure operations keep the table consistent,
  17 // all public methods that are also used by other methods for
  18 // intermediate results (add and remove are used in other methods)
  19 // there should be a public version that calls the private version
  20 // so consistency is checked after public ops, but not private ops
  21 public class VarSrcTokTable {
  22
  23   // a set of every token in the table
  24   private MySet<VariableSourceToken> trueSet;
  25
  26   // these hashtables provide an efficient retreival from the true set
  27   private Hashtable< TempDescriptor,    Set<VariableSourceToken> >  var2vst;
  28   private Hashtable< FlatSESEEnterNode, Set<VariableSourceToken> > sese2vst;
  29   private Hashtable< SVKey,             Set<VariableSourceToken> >   sv2vst;
  30
  31   // maximum age from aging operation
  32   private static final Integer MAX_AGE = new Integer(2);
  33
  34   public static final Integer SrcType_READY   = new Integer(34);
  35   public static final Integer SrcType_STATIC  = new Integer(35);
  36   public static final Integer SrcType_DYNAMIC = new Integer(36);
  37
  38   public static RBlockRelationAnalysis rblockRel;
  39
  40
  41
  42   public VarSrcTokTable() {
  43     trueSet  = new MySet<VariableSourceToken>();
  44
  45     sese2vst = new Hashtable< FlatSESEEnterNode, Set<VariableSourceToken> >();
  46     var2vst  = new Hashtable< TempDescriptor,    Set<VariableSourceToken> >();
  47     sv2vst   = new Hashtable< SVKey,             Set<VariableSourceToken> >();
  48
  49     assertConsistency();
  50   }
  51
  52
  53   // make a deep copy of the in table
  54   public VarSrcTokTable(VarSrcTokTable in) {
  55     this();
  56     merge(in);
  57     assertConsistency();
  58   }
  59
  60
  61   public void add(VariableSourceToken vst) {
  62     addPrivate(vst);
  63     assertConsistency();
  64   }
  65
  66   private void addPrivate(VariableSourceToken vst) {
  67
  68     // make sure we aren't clobbering anything!
  69     if( trueSet.contains(vst) ) {
  70       // if something with the same hashcode is in the true set, they might
  71       // have different reference variable sets because that set is not considered
  72       // in a token's equality, so make sure we smooth that out right here
  73
  74       VariableSourceToken vstAlready = trueSet.get(vst);
  75       if (vstAlready!=null) {
  76         removePrivate(vstAlready);
  77         HashSet<TempDescriptor> toAddSet=new HashSet<TempDescriptor>();
  78         toAddSet.addAll(vstAlready.getRefVars());
  79         toAddSet.addAll(vst.getRefVars());
  80         vst.setRefVars(toAddSet);
  81       }
  82     }
  83
  84     trueSet.add(vst);
  85
  86     Set<VariableSourceToken> s = sese2vst.get(vst.getSESE() );
  87     if( s == null ) {
  88       s = new HashSet<VariableSourceToken>();
  89       sese2vst.put(vst.getSESE(), s);
  90     }
  91     s.add(vst);
  92
  93     Iterator<TempDescriptor> refVarItr = vst.getRefVars().iterator();
  94     while( refVarItr.hasNext() ) {
  95       TempDescriptor refVar = refVarItr.next();
  96       s = var2vst.get(refVar);
  97       if( s == null ) {
  98         s = new HashSet<VariableSourceToken>();
  99         var2vst.put(refVar, s);
 100       }
 101       s.add(vst);
 102
 103       SVKey key = new SVKey(vst.getSESE(), refVar);
 104       s = sv2vst.get(key);
 105       if( s == null ) {
 106         s = new HashSet<VariableSourceToken>();
 107         sv2vst.put(key, s);
 108       }
 109       s.add(vst);
 110     }
 111   }
 112
 113   public void addAll(Set<VariableSourceToken> s) {
 114     Iterator<VariableSourceToken> itr = s.iterator();
 115     while( itr.hasNext() ) {
 116       addPrivate(itr.next() );
 117     }
 118     assertConsistency();
 119   }
 120
 121
 122   public Set<VariableSourceToken> get() {
 123     return trueSet;
 124   }
 125
 126   public Set<VariableSourceToken> get(FlatSESEEnterNode sese) {
 127     Set<VariableSourceToken> s = sese2vst.get(sese);
 128     if( s == null ) {
 129       s = new HashSet<VariableSourceToken>();
 130       sese2vst.put(sese, s);
 131     }
 132     return s;
 133   }
 134
 135   public Set<VariableSourceToken> get(TempDescriptor refVar) {
 136     Set<VariableSourceToken> s = var2vst.get(refVar);
 137     if( s == null ) {
 138       s = new HashSet<VariableSourceToken>();
 139       var2vst.put(refVar, s);
 140     }
 141     return s;
 142   }
 143
 144   public Set<VariableSourceToken> get(FlatSESEEnterNode sese,
 145                                       TempDescriptor refVar) {
 146     SVKey key = new SVKey(sese, refVar);
 147     Set<VariableSourceToken> s = sv2vst.get(key);
 148     if( s == null ) {
 149       s = new HashSet<VariableSourceToken>();
 150       sv2vst.put(key, s);
 151     }
 152     return s;
 153   }
 154
 155   public Set<VariableSourceToken> get(FlatSESEEnterNode sese,
 156                                       Integer age) {
 157
 158     HashSet<VariableSourceToken> s0 = (HashSet<VariableSourceToken>)sese2vst.get(sese);
 159     if( s0 == null ) {
 160       s0 = new HashSet<VariableSourceToken>();
 161       sese2vst.put(sese, s0);
 162     }
 163
 164     Set<VariableSourceToken> s = (Set<VariableSourceToken>)s0.clone();
 165     Iterator<VariableSourceToken> sItr = s.iterator();
 166     while( sItr.hasNext() ) {
 167       VariableSourceToken vst = sItr.next();
 168       if( !vst.getAge().equals(age) ) {
 169         s.remove(vst);
 170       }
 171     }
 172
 173     return s;
 174   }
 175
 176
 177   // merge now makes a deep copy of incoming stuff because tokens may
 178   // be modified (reference var sets) by later ops that change more
 179   // than one table, causing inconsistency
 180   public void merge(VarSrcTokTable in) {
 181
 182     if( in == null ) {
 183       return;
 184     }
 185
 186     Iterator<VariableSourceToken> vstItr = in.trueSet.iterator();
 187     while( vstItr.hasNext() ) {
 188       VariableSourceToken vst = vstItr.next();
 189       this.addPrivate(vst.copy() );
 190     }
 191
 192     assertConsistency();
 193   }
 194
 195
 196   // remove operations must leave the trueSet
 197   // and the hash maps consistent
 198   public void remove(VariableSourceToken vst) {
 199     removePrivate(vst);
 200     assertConsistency();
 201   }
 202
 203   private void removePrivate(VariableSourceToken vst) {
 204     trueSet.remove(vst);
 205
 206     Set<VariableSourceToken> s;
 207
 208     s = get(vst.getSESE() );
 209     if( s != null ) {
 210       s.remove(vst);
 211     }
 212
 213     Iterator<TempDescriptor> refVarItr = vst.getRefVars().iterator();
 214     while( refVarItr.hasNext() ) {
 215       TempDescriptor refVar = refVarItr.next();
 216
 217       s = get(refVar);
 218       if( s != null ) {
 219         s.remove(vst);
 220         if( s.isEmpty() ) {
 221           var2vst.remove(refVar);
 222         }
 223       }
 224
 225       s = get(vst.getSESE(), refVar);
 226       if( s != null ) {
 227         s.remove(vst);
 228         if( s.isEmpty() ) {
 229           sv2vst.remove(new SVKey(vst.getSESE(), refVar) );
 230         }
 231       }
 232     }
 233   }
 234
 235
 236   public void remove(FlatSESEEnterNode sese) {
 237     removePrivate(sese);
 238     assertConsistency();
 239   }
 240
 241   public void removePrivate(FlatSESEEnterNode sese) {
 242     Set<VariableSourceToken> s = sese2vst.get(sese);
 243     if( s == null ) {
 244       return;
 245     }
 246
 247     Iterator<VariableSourceToken> itr = s.iterator();
 248     while( itr.hasNext() ) {
 249       VariableSourceToken vst = itr.next();
 250       removePrivate(vst);
 251     }
 252
 253     sese2vst.remove(sese);
 254   }
 255
 256
 257   public void remove(TempDescriptor refVar) {
 258     removePrivate(refVar);
 259     assertConsistency();
 260   }
 261
 262   private void removePrivate(TempDescriptor refVar) {
 263     Set<VariableSourceToken> s = var2vst.get(refVar);
 264     if( s == null ) {
 265       return;
 266     }
 267
 268     Set<VariableSourceToken> forRemoval = new HashSet<VariableSourceToken>();
 269
 270     // iterate over tokens that this temp can reference, make a set
 271     // of tokens that need this temp stripped out of them
 272     Iterator<VariableSourceToken> itr = s.iterator();
 273     while( itr.hasNext() ) {
 274       VariableSourceToken vst = itr.next();
 275       Set<TempDescriptor> refVars = vst.getRefVars();
 276       assert refVars.contains(refVar);
 277       forRemoval.add(vst);
 278     }
 279
 280     itr = forRemoval.iterator();
 281     while( itr.hasNext() ) {
 282
 283       // here's a token marked for removal
 284       VariableSourceToken vst = itr.next();
 285       Set<TempDescriptor> refVars = vst.getRefVars();
 286
 287       // if there was only one one variable
 288       // referencing this token, just take it
 289       // out of the table all together
 290       if( refVars.size() == 1 ) {
 291         removePrivate(vst);
 292       }
 293
 294       sv2vst.remove(new SVKey(vst.getSESE(), refVar) );
 295
 296       HashSet<TempDescriptor> newset=new HashSet<TempDescriptor>();
 297       newset.addAll(vst.getRefVars());
 298       newset.remove(refVar);
 299       vst.setRefVars(newset);
 300     }
 301
 302
 303     var2vst.remove(refVar);
 304   }
 305
 306
 307   public void remove(FlatSESEEnterNode sese,
 308                      TempDescriptor var) {
 309
 310     // don't seem to need this, don't bother maintaining
 311     // until its clear we need it
 312     assert false;
 313   }
 314
 315
 316   // age tokens with respect to SESE curr, where
 317   // any curr tokens increase age by 1
 318   public void age(FlatSESEEnterNode curr) {
 319
 320     Set<VariableSourceToken> forRemoval =
 321       new HashSet<VariableSourceToken>();
 322
 323     Set<VariableSourceToken> forAddition =
 324       new HashSet<VariableSourceToken>();
 325
 326     Iterator<VariableSourceToken> itr = trueSet.iterator();
 327     while( itr.hasNext() ) {
 328       VariableSourceToken vst = itr.next();
 329
 330       if( vst.getSESE().equals(curr) ) {
 331
 332         // only age if the token isn't already the maximum age
 333         if( vst.getAge() < MAX_AGE ) {
 334
 335           forRemoval.add(vst);
 336
 337           forAddition.add(new VariableSourceToken(vst.getRefVars(),
 338                                                   curr,
 339                                                   vst.getAge() + 1,
 340                                                   vst.getAddrVar()
 341                                                   )
 342                           );
 343         }
 344       }
 345     }
 346
 347     itr = forRemoval.iterator();
 348     while( itr.hasNext() ) {
 349       VariableSourceToken vst = itr.next();
 350       remove(vst);
 351     }
 352
 353     itr = forRemoval.iterator();
 354     while( itr.hasNext() ) {
 355       VariableSourceToken vst = itr.next();
 356       add(vst);
 357     }
 358
 359     assertConsistency();
 360   }
 361
 362
 363   // at an SESE enter node, all ref vars in the SESE's in-set will
 364   // be copied into the SESE's local scope, change source to itself
 365   public void ownInSet(FlatSESEEnterNode curr) {
 366     Iterator<TempDescriptor> inVarItr = curr.getInVarSet().iterator();
 367     while( inVarItr.hasNext() ) {
 368       TempDescriptor inVar = inVarItr.next();
 369
 370       remove(inVar);
 371       assertConsistency();
 372
 373       Set<TempDescriptor> refVars = new HashSet<TempDescriptor>();
 374       refVars.add(inVar);
 375       add(new VariableSourceToken(refVars,
 376                                   curr,
 377                                   new Integer(0),
 378                                   inVar
 379                                   )
 380           );
 381       assertConsistency();
 382     }
 383   }
 384
 385
 386   // for the given SESE, change child tokens into this parent
 387   public void remapChildTokens(FlatSESEEnterNode curr) {
 388
 389     Iterator<FlatSESEEnterNode> childItr = curr.getLocalChildren().iterator();
 390     while( childItr.hasNext() ) {
 391       FlatSESEEnterNode child = childItr.next();
 392
 393       // set of VSTs for removal
 394       HashSet<VariableSourceToken> removalSet=new HashSet<VariableSourceToken>();
 395       // set of VSTs for additon
 396       HashSet<VariableSourceToken> additionSet=new HashSet<VariableSourceToken>();
 397
 398       Iterator<VariableSourceToken> vstItr = get(child).iterator();
 399       while( vstItr.hasNext() ) {
 400         VariableSourceToken vst = vstItr.next();
 401         removalSet.add(vst);
 402
 403         additionSet.add(new VariableSourceToken(vst.getRefVars(),
 404                                                 curr,
 405                                                 new Integer(0),
 406                                                 vst.getAddrVar()
 407                                                 )
 408                         );
 409       }
 410
 411       // remove( eah item in forremoval )
 412       vstItr = removalSet.iterator();
 413       while( vstItr.hasNext() ) {
 414         VariableSourceToken vst = vstItr.next();
 415         remove(vst);
 416       }
 417       // add( each  ite inm for additon _
 418       vstItr = additionSet.iterator();
 419       while( vstItr.hasNext() ) {
 420         VariableSourceToken vst = vstItr.next();
 421         add(vst);
 422       }
 423     }
 424
 425     assertConsistency();
 426   }
 427
 428
 429   // this method is called at the SESE exit of SESE 'curr'
 430   // if the sources for a variable written by curr can also
 431   // come from curr's parent or curr's siblings then we're not
 432   // sure that curr will actually modify the variable.  There are
 433   // many ways to handle this, but for now, mark the variable as
 434   // virtually read so curr insists on having ownership of it
 435   // whether it ends up writing to it or not.  It will always, then,
 436   // appear in curr's out-set.
 437   public Set<TempDescriptor>
 438   calcVirtReadsAndPruneParentAndSiblingTokens(FlatSESEEnterNode exiter,
 439                                               Set<TempDescriptor> liveVars) {
 440
 441     Set<TempDescriptor> virtReadSet = new HashSet<TempDescriptor>();
 442
 443     // this calculation is unneeded for the main task, just return an
 444     // empty set of virtual reads
 445     if( rblockRel.getMainSESE() == exiter ) {
 446       return virtReadSet;
 447     }
 448
 449     // who can be the alternate sources?  Your siblings.  Your parent.
 450     // your parent's siblings.  Your parent's parent and its siblings, etc.
 451     // So find your ancestors and grab siblings along the way.
 452     Set<FlatSESEEnterNode> alternateSESEs = new HashSet<FlatSESEEnterNode>();
 453
 454     FlatSESEEnterNode ancestor = exiter;
 455     boolean findMore = true;
 456
 457     while( findMore ) {
 458       // first move up to the next ancestor
 459       ancestor = ancestor.getLocalParent();
 460       Iterator<FlatSESEEnterNode> childItr;
 461
 462       if( ancestor == null ) {
 463         // when some caller task is the next parent, the siblings
 464         // of the current task are other local root tasks
 465         ancestor = rblockRel.getCallerProxySESE();
 466         childItr = rblockRel.getLocalRootSESEs(exiter.getfmEnclosing() ).iterator();
 467         findMore = false;
 468       } else {
 469         // otherwise, the siblings are locally-defined
 470         childItr = ancestor.getLocalChildren().iterator();
 471
 472         // and there is no further ancestry beyond the main task
 473         if( ancestor.equals(rblockRel.getMainSESE() ) ) {
 474           findMore = false;
 475         }
 476       }
 477
 478       // this ancestor and its children are valid alternate sources
 479       alternateSESEs.add(ancestor);
 480       while( childItr.hasNext() ) {
 481         FlatSESEEnterNode sibling = childItr.next();
 482         alternateSESEs.add(sibling);
 483       }
 484     }
 485
 486
 487     // VSTs to remove if they are alternate sources for exiter VSTs
 488     // whose variables will become virtual reads
 489     Set<VariableSourceToken> forRemoval = new HashSet<VariableSourceToken>();
 490
 491     // look at all of this SESE's VSTs at exit...
 492     Iterator<VariableSourceToken> vstItr = get(exiter).iterator();
 493     while( vstItr.hasNext() ) {
 494       VariableSourceToken vstExiterSrc = vstItr.next();
 495
 496       // only interested in sources from our current instance
 497       if( vstExiterSrc.getAge() != 0 ) {
 498         continue;
 499       }
 500
 501       // for each variable that might come from those sources...
 502       Iterator<TempDescriptor> refVarItr = vstExiterSrc.getRefVars().iterator();
 503       while( refVarItr.hasNext() ) {
 504         TempDescriptor refVar = refVarItr.next();
 505
 506         // only matters for live variables at SESE exit program point
 507         if( !liveVars.contains(refVar) ) {
 508           continue;
 509         }
 510
 511         // examine other sources for a variable...
 512         Iterator<VariableSourceToken> srcItr = get(refVar).iterator();
 513         while( srcItr.hasNext() ) {
 514           VariableSourceToken vstPossibleOtherSrc = srcItr.next();
 515
 516           if( vstPossibleOtherSrc.getSESE().equals(exiter) &&
 517               vstPossibleOtherSrc.getAge() > 0
 518               ) {
 519             // this is an alternate source if its
 520             // an older instance of this SESE
 521             virtReadSet.add(refVar);
 522             forRemoval.add(vstPossibleOtherSrc);
 523
 524           } else if( alternateSESEs.contains(vstPossibleOtherSrc.getSESE() ) ) {
 525             // this is an alternate source from ancestor or ancestor's sibling
 526             virtReadSet.add(refVar);
 527             forRemoval.add(vstPossibleOtherSrc);
 528
 529           } else {
 530             if( !(vstPossibleOtherSrc.getSESE().equals(exiter) &&
 531                   vstPossibleOtherSrc.getAge().equals(0)
 532                   )
 533                 ) {
 534               System.out.println("For refVar="+refVar+" at exit of "+exiter+
 535                                  ", unexpected possible variable source "+vstPossibleOtherSrc);
 536               assert false;
 537             }
 538           }
 539         }
 540       }
 541     }
 542
 543     vstItr = forRemoval.iterator();
 544     while( vstItr.hasNext() ) {
 545       VariableSourceToken vst = vstItr.next();
 546       remove(vst);
 547     }
 548     assertConsistency();
 549
 550     return virtReadSet;
 551   }
 552
 553
 554   // given a table from a subsequent program point, decide
 555   // which variables are going from a non-dynamic to a
 556   // dynamic source and return them
 557   public Hashtable<TempDescriptor, VSTWrapper>
 558   getReadyOrStatic2DynamicSet(VarSrcTokTable nextTable,
 559                               Set<TempDescriptor> nextLiveIn,
 560                               FlatSESEEnterNode current
 561                               ) {
 562
 563     Hashtable<TempDescriptor, VSTWrapper> out =
 564       new Hashtable<TempDescriptor, VSTWrapper>();
 565
 566     Iterator itr = var2vst.entrySet().iterator();
 567     while( itr.hasNext() ) {
 568       Map.Entry me  = (Map.Entry)itr.next();
 569       TempDescriptor var = (TempDescriptor)               me.getKey();
 570       HashSet<VariableSourceToken> s1  = (HashSet<VariableSourceToken>)me.getValue();
 571
 572       // only worth tracking if live
 573       if( nextLiveIn.contains(var) ) {
 574
 575         VSTWrapper vstIfStaticBefore = new VSTWrapper();
 576         VSTWrapper vstIfStaticAfter  = new VSTWrapper();
 577
 578         Integer srcTypeBefore =      this.getRefVarSrcType(var, current, vstIfStaticBefore);
 579         Integer srcTypeAfter  = nextTable.getRefVarSrcType(var, current, vstIfStaticAfter);
 580
 581         if( !srcTypeBefore.equals(SrcType_DYNAMIC) &&
 582             srcTypeAfter.equals(SrcType_DYNAMIC)
 583             ) {
 584           // remember the variable and a source
 585           // it had before crossing the transition
 586           // 1) if it was ready, vstIfStatic.vst is null
 587           // 2) if is was static, use vstIfStatic.vst
 588           out.put(var, vstIfStaticBefore);
 589         }
 590       }
 591     }
 592
 593     return out;
 594   }
 595
 596
 597   // for some reference variable, return the type of source
 598   // it might have in this table, which might be:
 599   // 1. Ready -- this variable is
 600   //      definitely available when you are issued.
 601   // 2. Static -- there is definitely one child SESE with
 602   //      a known age that will produce the value
 603   // 3. Dynamic -- we don't know where the value will come
 604   //      from statically, so we'll track it dynamically
 605   public Integer getRefVarSrcType(TempDescriptor refVar,
 606                                   FlatSESEEnterNode currentSESE,
 607                                   VSTWrapper vstIfStatic) {
 608     assert refVar      != null;
 609     assert vstIfStatic != null;
 610
 611     vstIfStatic.vst = null;
 612
 613     // when the current SESE is null, that simply means it is
 614     // an unknown placeholder, in which case the system will
 615     // ensure that any variables are READY
 616     if( currentSESE == null ) {
 617       return SrcType_READY;
 618     }
 619
 620     // if there appear to be no sources, it means this variable
 621     // comes from outside of any statically-known SESE scope,
 622     // which means the system guarantees its READY, so jump over
 623     // while loop
 624     Set<VariableSourceToken>      srcs    = get(refVar);
 625     Iterator<VariableSourceToken> itrSrcs = srcs.iterator();
 626     while( itrSrcs.hasNext() ) {
 627       VariableSourceToken vst = itrSrcs.next();
 628
 629       // to make the refVar non-READY we have to find at least
 630       // one child token, there are two cases
 631       //  1. if the current task invoked the local method context,
 632       //     its children are the locally-defined root tasks
 633       boolean case1 =
 634         currentSESE.getIsCallerProxySESE() &&
 635         rblockRel.getLocalRootSESEs().contains(vst.getSESE() );
 636
 637       //  2. if the child task is a locally-defined child of the current task
 638       boolean case2 = currentSESE.getLocalChildren().contains(vst.getSESE() );
 639
 640       if( case1 || case2 ) {
 641
 642         // if we ever have at least one child source with an
 643         // unknown age, have to treat var as dynamic
 644         if( vst.getAge().equals(OoOJavaAnalysis.maxSESEage) ) {
 645           return SrcType_DYNAMIC;
 646         }
 647
 648         // if we have a known-age child source, this var is
 649         // either static or dynamic now: it's static if this
 650         // source is the only source, otherwise dynamic
 651         if( srcs.size() > 1 ) {
 652           return SrcType_DYNAMIC;
 653         }
 654
 655         vstIfStatic.vst = vst;
 656         return SrcType_STATIC;
 657       }
 658     }
 659
 660     // if we never found a child source, all other
 661     // sources must be READY before we could even
 662     // begin executing!
 663     return SrcType_READY;
 664   }
 665
 666
 667   // any reference variables that are not live can be pruned
 668   // from the table, and if any VSTs are then no longer
 669   // referenced, they can be dropped as well
 670   // THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED
 671   public void pruneByLiveness(Set<TempDescriptor> rootLiveSet) {
 672
 673     // the set of reference variables in the table minus the
 674     // live set gives the set of reference variables to remove
 675     Set<TempDescriptor> deadRefVars = new HashSet<TempDescriptor>();
 676     deadRefVars.addAll(var2vst.keySet() );
 677
 678     if( rootLiveSet != null ) {
 679       deadRefVars.removeAll(rootLiveSet);
 680     }
 681
 682     // just use the remove operation to prune the table now
 683     Iterator<TempDescriptor> deadItr = deadRefVars.iterator();
 684     while( deadItr.hasNext() ) {
 685       TempDescriptor dead = deadItr.next();
 686       removePrivate(dead);
 687     }
 688
 689     assertConsistency();
 690   }
 691
 692
 693
 694   // use as an aid for debugging, where true-set is checked
 695   // against the alternate mappings: assert that nothing is
 696   // missing or extra in the alternates
 697
 698   public void assertConsistency() {
 699   }
 700   /*  public void assertConsistency() {
 701
 702      Iterator itr;
 703      Set s;
 704
 705      Set<VariableSourceToken> trueSetByAlts = new HashSet<VariableSourceToken>();
 706      itr = sese2vst.entrySet().iterator();
 707      while( itr.hasNext() ) {
 708       Map.Entry                    me   = (Map.Entry)                    itr.next();
 709       FlatSESEEnterNode            sese = (FlatSESEEnterNode)            me.getKey();
 710       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 711       assert s1 != null;
 712
 713       // the trueSet should have all entries in s1
 714       assert trueSet.containsAll( s1 );
 715
 716       // s1 should not have anything that doesn't appear in trueset
 717       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 718       sInt.removeAll( trueSet );
 719
 720       assert sInt.isEmpty();
 721
 722       // add s1 to a running union--at the end check if trueSet has extra
 723       trueSetByAlts.addAll( s1 );
 724      }
 725      // make sure trueSet isn't too big
 726      assert trueSetByAlts.containsAll( trueSet );
 727
 728
 729      trueSetByAlts = new HashSet<VariableSourceToken>();
 730      itr = var2vst.entrySet().iterator();
 731      while( itr.hasNext() ) {
 732       Map.Entry                    me   = (Map.Entry)                    itr.next();
 733       TempDescriptor               var  = (TempDescriptor)               me.getKey();
 734       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 735       assert s1 != null;
 736
 737       // the trueSet should have all entries in s1
 738       assert trueSet.containsAll( s1 );
 739
 740       // s1 should not have anything that doesn't appear in trueset
 741       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 742       sInt.removeAll( trueSet );
 743
 744       assert sInt.isEmpty();
 745
 746       // add s1 to a running union--at the end check if trueSet has extra
 747       trueSetByAlts.addAll( s1 );
 748      }
 749      // make sure trueSet isn't too big
 750      assert trueSetByAlts.containsAll( trueSet );
 751
 752
 753      trueSetByAlts = new HashSet<VariableSourceToken>();
 754      itr = sv2vst.entrySet().iterator();
 755      while( itr.hasNext() ) {
 756       Map.Entry                    me   = (Map.Entry)                    itr.next();
 757       SVKey                        key  = (SVKey)                        me.getKey();
 758       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 759       assert s1 != null;
 760
 761       // the trueSet should have all entries in s1
 762       assert trueSet.containsAll( s1 );
 763
 764       // s1 should not have anything that doesn't appear in trueset
 765       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 766       sInt.removeAll( trueSet );
 767
 768       assert sInt.isEmpty();
 769
 770       // add s1 to a running union--at the end check if trueSet has extra
 771       trueSetByAlts.addAll( s1 );
 772      }
 773      // make sure trueSet isn't too big
 774      assert trueSetByAlts.containsAll( trueSet );
 775
 776
 777      // also check that the reference var sets are consistent
 778      Hashtable<VariableSourceToken, Set<TempDescriptor> > vst2refVars =
 779       new Hashtable<VariableSourceToken, Set<TempDescriptor> >();
 780      itr = var2vst.entrySet().iterator();
 781      while( itr.hasNext() ) {
 782       Map.Entry                     me     = (Map.Entry)                    itr.next();
 783       TempDescriptor                refVar = (TempDescriptor)               me.getKey();
 784       HashSet<VariableSourceToken>  s1     = (HashSet<VariableSourceToken>) me.getValue();
 785       Iterator<VariableSourceToken> vstItr = s1.iterator();
 786       while( vstItr.hasNext() ) {
 787         VariableSourceToken vst = vstItr.next();
 788         assert vst.getRefVars().contains( refVar );
 789
 790         Set<TempDescriptor> refVarsPart = vst2refVars.get( vst );
 791         if( refVarsPart == null ) {
 792           refVarsPart = new HashSet<TempDescriptor>();
 793         }
 794         refVarsPart.add( refVar );
 795         vst2refVars.put( vst, refVarsPart );
 796       }
 797      }
 798      itr = vst2refVars.entrySet().iterator();
 799      while( itr.hasNext() ) {
 800       Map.Entry           me  = (Map.Entry)           itr.next();
 801       VariableSourceToken vst = (VariableSourceToken) me.getKey();
 802       Set<TempDescriptor> s1  = (Set<TempDescriptor>) me.getValue();
 803
 804       assert vst.getRefVars().equals( s1 );
 805      }
 806      }*/
 807
 808
 809   public boolean equals(Object o) {
 810     if( o == null ) {
 811       return false;
 812     }
 813
 814     if( !(o instanceof VarSrcTokTable) ) {
 815       return false;
 816     }
 817
 818     VarSrcTokTable table = (VarSrcTokTable) o;
 819     return trueSet.equals(table.trueSet);
 820   }
 821
 822   public int hashCode() {
 823     return trueSet.hashCode();
 824   }
 825
 826   public Iterator<VariableSourceToken> iterator() {
 827     return trueSet.iterator();
 828   }
 829
 830   public String toString() {
 831     return toStringPretty();
 832   }
 833
 834   public String toStringVerbose() {
 835     return "trueSet ="+trueSet.toString()+"\n"+
 836            "sese2vst="+sese2vst.toString()+"\n"+
 837            "var2vst ="+var2vst.toString()+"\n"+
 838            "sv2vst  ="+sv2vst.toString();
 839   }
 840
 841   public String toStringPretty() {
 842     String tokHighlighter = "o";
 843
 844     String str = "VarSrcTokTable\n";
 845     Iterator<VariableSourceToken> vstItr = trueSet.iterator();
 846     while( vstItr.hasNext() ) {
 847       str += "   "+tokHighlighter+" "+vstItr.next()+"\n";
 848     }
 849     return str;
 850   }
 851
 852   public String toStringPrettyVerbose() {
 853     String tokHighlighter = "o";
 854
 855     String str = "VarSrcTokTable\n";
 856
 857     Set s;
 858     Iterator itr;
 859     Iterator<VariableSourceToken> vstItr;
 860
 861     str += "  trueSet\n";
 862     vstItr = trueSet.iterator();
 863     while( vstItr.hasNext() ) {
 864       str += "     "+tokHighlighter+" "+vstItr.next()+"\n";
 865     }
 866
 867     str += "  sese2vst\n";
 868     itr = sese2vst.entrySet().iterator();
 869     while( itr.hasNext() ) {
 870       Map.Entry me   = (Map.Entry)itr.next();
 871       FlatSESEEnterNode sese = (FlatSESEEnterNode)            me.getKey();
 872       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>)me.getValue();
 873       assert s1 != null;
 874
 875       str += "    "+sese.getPrettyIdentifier()+" -> \n";
 876
 877       vstItr = s1.iterator();
 878       while( vstItr.hasNext() ) {
 879         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 880       }
 881     }
 882
 883     str += "  var2vst\n";
 884     itr = var2vst.entrySet().iterator();
 885     while( itr.hasNext() ) {
 886       Map.Entry me  = (Map.Entry)itr.next();
 887       TempDescriptor var = (TempDescriptor)           me.getKey();
 888       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>)me.getValue();
 889       assert s1 != null;
 890
 891       str += "    "+var+" -> \n";
 892
 893       vstItr = s1.iterator();
 894       while( vstItr.hasNext() ) {
 895         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 896       }
 897     }
 898
 899     str += "  sv2vst\n";
 900     itr = sv2vst.entrySet().iterator();
 901     while( itr.hasNext() ) {
 902       Map.Entry me  = (Map.Entry)itr.next();
 903       SVKey key = (SVKey)                    me.getKey();
 904       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>)me.getValue();
 905       assert s1 != null;
 906
 907       str += "    "+key+" -> \n";
 908
 909       vstItr = s1.iterator();
 910       while( vstItr.hasNext() ) {
 911         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 912       }
 913     }
 914
 915     return str;
 916   }
 917 }