Robust/src/Analysis/MLP/VarSrcTokTable.java

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