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 ) { s.remove( vst ); }
 223
 224       s = get( vst.getSESE(), refVar );
 225       if( s != null ) { s.remove( vst ); }
 226     }
 227   }
 228
 229
 230   public void remove( FlatSESEEnterNode sese ) {
 231     removePrivate( sese );
 232     assertConsistency();
 233   }
 234
 235   public void removePrivate( FlatSESEEnterNode sese ) {
 236     Set<VariableSourceToken> s = sese2vst.get( sese );
 237     if( s == null ) {
 238       return;
 239     }
 240
 241     Iterator<VariableSourceToken> itr = s.iterator();
 242     while( itr.hasNext() ) {
 243       VariableSourceToken vst = itr.next();
 244       removePrivate( vst );
 245     }
 246
 247     sese2vst.remove( sese );
 248   }
 249
 250
 251   public void remove( TempDescriptor refVar ) {
 252     removePrivate( refVar );
 253     assertConsistency();
 254   }
 255
 256   private void removePrivate( TempDescriptor refVar ) {
 257     Set<VariableSourceToken> s = var2vst.get( refVar );
 258     if( s == null ) {
 259       return;
 260     }
 261
 262     Set<VariableSourceToken> forRemoval = new HashSet<VariableSourceToken>();
 263
 264     // iterate over tokens that this temp can reference, make a set
 265     // of tokens that need this temp stripped out of them
 266     Iterator<VariableSourceToken> itr = s.iterator();
 267     while( itr.hasNext() ) {
 268       VariableSourceToken vst = itr.next();
 269       Set<TempDescriptor> refVars = vst.getRefVars();
 270       assert refVars.contains( refVar );
 271       forRemoval.add( vst );
 272     }
 273
 274     itr = forRemoval.iterator();
 275     while( itr.hasNext() ) {
 276
 277       // here's a token marked for removal
 278       VariableSourceToken vst = itr.next();
 279       Set<TempDescriptor> refVars = vst.getRefVars();
 280
 281       // if there was only one one variable
 282       // referencing this token, just take it
 283       // out of the table all together
 284       if( refVars.size() == 1 ) {
 285         removePrivate( vst );
 286       }
 287
 288       refVars.remove( refVar );
 289     }
 290
 291     var2vst.remove( refVar );
 292   }
 293
 294
 295   public void remove( FlatSESEEnterNode sese,
 296                       TempDescriptor    var  ) {
 297
 298     // don't seem to need this, don't bother maintaining
 299     // until its clear we need it
 300     assert false;
 301   }
 302
 303
 304   // age tokens with respect to SESE curr, where
 305   // any curr tokens increase age by 1
 306   public void age( FlatSESEEnterNode curr ) {
 307
 308     Set<VariableSourceToken> forRemoval =
 309       new HashSet<VariableSourceToken>();
 310
 311     Set<VariableSourceToken> forAddition =
 312       new HashSet<VariableSourceToken>();
 313
 314     Iterator<VariableSourceToken> itr = trueSet.iterator();
 315     while( itr.hasNext() ) {
 316       VariableSourceToken vst = itr.next();
 317
 318       if( vst.getSESE().equals( curr ) ) {
 319
 320         // only age if the token isn't already the maximum age
 321         if( vst.getAge() < MAX_AGE ) {
 322
 323           forRemoval.add( vst );
 324
 325           forAddition.add( new VariableSourceToken( vst.getRefVars(),
 326                                                     curr,
 327                                                     vst.getAge() + 1,
 328                                                     vst.getAddrVar()
 329                                                     )
 330                            );
 331         }
 332       }
 333     }
 334
 335     itr = forRemoval.iterator();
 336     while( itr.hasNext() ) {
 337       VariableSourceToken vst = itr.next();
 338       remove( vst );
 339     }
 340
 341     itr = forRemoval.iterator();
 342     while( itr.hasNext() ) {
 343       VariableSourceToken vst = itr.next();
 344       add( vst );
 345     }
 346
 347     assertConsistency();
 348   }
 349
 350
 351   // at an SESE enter node, all ref vars in the SESE's in-set will
 352   // be copied into the SESE's local scope, change source to itself
 353   public void ownInSet( FlatSESEEnterNode curr ) {
 354     Iterator<TempDescriptor> inVarItr = curr.getInVarSet().iterator();
 355     while( inVarItr.hasNext() ) {
 356       TempDescriptor inVar = inVarItr.next();
 357
 358       remove( inVar );
 359       assertConsistency();
 360
 361       Set<TempDescriptor> refVars = new HashSet<TempDescriptor>();
 362       refVars.add( inVar );
 363       add( new VariableSourceToken( refVars,
 364                                     curr,
 365                                     new Integer( 0 ),
 366                                     inVar
 367                                     )
 368            );
 369       assertConsistency();
 370     }
 371   }
 372
 373
 374   // for the given SESE, change child tokens into this parent
 375   public void remapChildTokens( FlatSESEEnterNode curr ) {
 376
 377     Iterator<FlatSESEEnterNode> childItr = curr.getChildren().iterator();
 378     if( childItr.hasNext() ) {
 379       FlatSESEEnterNode child = childItr.next();
 380
 381       Iterator<VariableSourceToken> vstItr = get( child ).iterator();
 382       while( vstItr.hasNext() ) {
 383         VariableSourceToken vst = vstItr.next();
 384
 385         remove( vst );
 386
 387         add( new VariableSourceToken( vst.getRefVars(),
 388                                       curr,
 389                                       new Integer( 0 ),
 390                                       vst.getAddrVar()
 391                                       )
 392              );
 393       }
 394     }
 395
 396     assertConsistency();
 397   }
 398
 399
 400   // if we can get a value from the current SESE and the parent
 401   // or a sibling, just getting from the current SESE suffices now
 402   // return a set of temps that are virtually read
 403   public Set<TempDescriptor> removeParentAndSiblingTokens( FlatSESEEnterNode curr,
 404                                                            Set<TempDescriptor> liveIn ) {
 405
 406     HashSet<TempDescriptor> virtualLiveIn = new HashSet<TempDescriptor>();
 407
 408     FlatSESEEnterNode parent = curr.getParent();
 409     if( parent == null ) {
 410       // have no parent or siblings
 411       return virtualLiveIn;
 412     }
 413
 414     remove_A_if_B( parent, curr, liveIn, virtualLiveIn );
 415
 416     Iterator<FlatSESEEnterNode> childItr = parent.getChildren().iterator();
 417     if( childItr.hasNext() ) {
 418       FlatSESEEnterNode child = childItr.next();
 419
 420       if( !child.equals( curr ) ) {
 421         remove_A_if_B( child, curr, liveIn, virtualLiveIn );
 422       }
 423     }
 424
 425     assertConsistency();
 426     return virtualLiveIn;
 427   }
 428
 429   // if B is also a source for some variable, remove all entries
 430   // of A as a source for that variable: s is virtual reads
 431   protected void remove_A_if_B( FlatSESEEnterNode a,
 432                                 FlatSESEEnterNode b,
 433                                 Set<TempDescriptor> liveInCurrentSESE,
 434                                 Set<TempDescriptor> virtualLiveIn ) {
 435
 436     Set<VariableSourceToken> forRemoval = new HashSet<VariableSourceToken>();
 437
 438     Iterator<VariableSourceToken> vstItr = get( a ).iterator();
 439     while( vstItr.hasNext() ) {
 440       VariableSourceToken      vst       = vstItr.next();
 441       Iterator<TempDescriptor> refVarItr = vst.getRefVars().iterator();
 442       while( refVarItr.hasNext() ) {
 443         TempDescriptor           refVar = refVarItr.next();
 444         Set<VariableSourceToken> bSet   = get( b, refVar );
 445
 446         if( !bSet.isEmpty() ) {
 447           forRemoval.add( vst );
 448
 449           // mark this variable as a virtual read as well
 450           virtualLiveIn.add( refVar );
 451         }
 452       }
 453     }
 454
 455     vstItr = forRemoval.iterator();
 456     while( vstItr.hasNext() ) {
 457       VariableSourceToken vst = vstItr.next();
 458       remove( vst );
 459     }
 460
 461     assertConsistency();
 462   }
 463
 464
 465   // get the set of VST's that come from a child
 466   public Set<VariableSourceToken> getChildrenVSTs( FlatSESEEnterNode curr ) {
 467
 468     Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
 469
 470     Iterator<FlatSESEEnterNode> cItr = curr.getChildren().iterator();
 471     while( cItr.hasNext() ) {
 472       FlatSESEEnterNode child = cItr.next();
 473       out.addAll( get( child ) );
 474     }
 475
 476     return out;
 477   }
 478
 479
 480   // get the set of variables that have exactly one source
 481   // from the static perspective
 482   public Set<VariableSourceToken> getStaticSet() {
 483
 484     Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
 485
 486     Iterator itr = var2vst.entrySet().iterator();
 487     while( itr.hasNext() ) {
 488       Map.Entry                    me  = (Map.Entry)                    itr.next();
 489       TempDescriptor               var = (TempDescriptor)               me.getKey();
 490       HashSet<VariableSourceToken> s1  = (HashSet<VariableSourceToken>) me.getValue();
 491
 492       if( s1.size() == 1 ) {
 493         out.addAll( s1 );
 494       }
 495     }
 496
 497     return out;
 498   }
 499
 500
 501   // given a table from a subsequent program point, decide
 502   // which variables are going from a static source to a
 503   // dynamic source and return them
 504   public Hashtable<TempDescriptor, VariableSourceToken>
 505     getStatic2DynamicSet( VarSrcTokTable nextTable,
 506                           Set<TempDescriptor> nextLiveIn ) {
 507
 508     Hashtable<TempDescriptor, VariableSourceToken> out =
 509       new Hashtable<TempDescriptor, VariableSourceToken>();
 510
 511     Iterator itr = var2vst.entrySet().iterator();
 512     while( itr.hasNext() ) {
 513       Map.Entry                    me  = (Map.Entry)                    itr.next();
 514       TempDescriptor               var = (TempDescriptor)               me.getKey();
 515       HashSet<VariableSourceToken> s1  = (HashSet<VariableSourceToken>) me.getValue();
 516
 517       // only worth tracking if live
 518       if( nextLiveIn.contains( var ) ) {
 519
 520         // this is a variable with a static source if it
 521         // currently has one vst
 522         if( s1.size() == 1 ) {
 523           Set<VariableSourceToken> s2 = nextTable.get( var );
 524
 525           // and if in the next table, it is dynamic, then
 526           // this is a transition point, so
 527           if( s2.size() > 1 ) {
 528
 529             // remember the variable and the only source
 530             // it had before crossing the transition
 531             out.put( var, s1.iterator().next() );
 532           }
 533         }
 534       }
 535     }
 536
 537     return out;
 538   }
 539
 540
 541   // for some reference variable, return the type of source
 542   // it might have in this table, which might be:
 543   // 1. Ready -- this variable comes from your parent and is
 544   //      definitely available when you are issued.
 545   // 2. Static -- there is definitely one SESE that will
 546   //      produce the value for this variable
 547   // 3. Dynamic -- we don't know where the value will come
 548   //      from, so we'll track it dynamically
 549   public Integer getRefVarSrcType( TempDescriptor    refVar,
 550                                    FlatSESEEnterNode current,
 551                                    FlatSESEEnterNode parent ) {
 552     assert refVar != null;
 553
 554     // if you have no parent (root) and the variable in
 555     // question is in your in-set, it's a command line
 556     // argument and it is definitely available
 557     if( parent == null &&
 558         current.getInVarSet().contains( refVar ) ) {
 559       return SrcType_READY;
 560     }
 561
 562     Set<VariableSourceToken> srcs = get( refVar );
 563     assert !srcs.isEmpty();
 564
 565     // if the variable may have more than one source, or that
 566     // source is at the summary age, it must be tracked dynamically
 567     if( srcs.size() > 1 ||
 568         srcs.iterator().next().getAge() == MLPAnalysis.maxSESEage ) {
 569       return SrcType_DYNAMIC;
 570     }
 571
 572     // if it has one source that comes from the parent, it's ready
 573     if( srcs.iterator().next().getSESE() == parent ) {
 574       return SrcType_READY;
 575     }
 576
 577     // otherwise it comes from one source not the parent (sibling)
 578     // and we know exactly which static SESE/age it will come from
 579     return SrcType_STATIC;
 580   }
 581
 582
 583   // any reference variables that are not live can be pruned
 584   // from the table, and if any VSTs are then no longer
 585   // referenced, they can be dropped as well
 586   /* THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED
 587   public void pruneByLiveness( Set<TempDescriptor> rootLiveSet ) {
 588
 589     // the set of reference variables in the table minus the
 590     // live set gives the set of reference variables to remove
 591     Set<TempDescriptor> deadRefVars = new HashSet<TempDescriptor>();
 592     deadRefVars.addAll( var2vst.keySet() );
 593
 594     if( rootLiveSet != null ) {
 595       deadRefVars.removeAll( rootLiveSet );
 596     }
 597
 598     // just use the remove operation to prune the table now
 599     Iterator<TempDescriptor> deadItr = deadRefVars.iterator();
 600     while( deadItr.hasNext() ) {
 601       TempDescriptor dead = deadItr.next();
 602       removePrivate( dead );
 603     }
 604
 605     assertConsistency();
 606   }
 607   */
 608
 609
 610   // use as an aid for debugging, where true-set is checked
 611   // against the alternate mappings: assert that nothing is
 612   // missing or extra in the alternates
 613   public void assertConsistency() {
 614
 615     Iterator itr;
 616     Set s;
 617
 618     Set<VariableSourceToken> trueSetByAlts = new HashSet<VariableSourceToken>();
 619     itr = sese2vst.entrySet().iterator();
 620     while( itr.hasNext() ) {
 621       Map.Entry                    me   = (Map.Entry)                    itr.next();
 622       FlatSESEEnterNode            sese = (FlatSESEEnterNode)            me.getKey();
 623       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 624       assert s1 != null;
 625
 626       // the trueSet should have all entries in s1
 627       assert trueSet.containsAll( s1 );
 628
 629       // s1 should not have anything that doesn't appear in trueset
 630       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 631       sInt.removeAll( trueSet );
 632
 633       assert sInt.isEmpty();
 634
 635       // add s1 to a running union--at the end check if trueSet has extra
 636       trueSetByAlts.addAll( s1 );
 637     }
 638     // make sure trueSet isn't too big
 639     assert trueSetByAlts.containsAll( trueSet );
 640
 641
 642     trueSetByAlts = new HashSet<VariableSourceToken>();
 643     itr = var2vst.entrySet().iterator();
 644     while( itr.hasNext() ) {
 645       Map.Entry                    me   = (Map.Entry)                    itr.next();
 646       TempDescriptor               var  = (TempDescriptor)               me.getKey();
 647       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 648       assert s1 != null;
 649
 650       // the trueSet should have all entries in s1
 651       assert trueSet.containsAll( s1 );
 652
 653       // s1 should not have anything that doesn't appear in trueset
 654       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 655       sInt.removeAll( trueSet );
 656
 657       assert sInt.isEmpty();
 658
 659       // add s1 to a running union--at the end check if trueSet has extra
 660       trueSetByAlts.addAll( s1 );
 661     }
 662     // make sure trueSet isn't too big
 663     assert trueSetByAlts.containsAll( trueSet );
 664
 665
 666     trueSetByAlts = new HashSet<VariableSourceToken>();
 667     itr = sv2vst.entrySet().iterator();
 668     while( itr.hasNext() ) {
 669       Map.Entry                    me   = (Map.Entry)                    itr.next();
 670       SVKey                        key  = (SVKey)                        me.getKey();
 671       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 672       assert s1 != null;
 673
 674       // the trueSet should have all entries in s1
 675       assert trueSet.containsAll( s1 );
 676
 677       // s1 should not have anything that doesn't appear in trueset
 678       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 679       sInt.removeAll( trueSet );
 680
 681       assert sInt.isEmpty();
 682
 683       // add s1 to a running union--at the end check if trueSet has extra
 684       trueSetByAlts.addAll( s1 );
 685     }
 686     // make sure trueSet isn't too big
 687     assert trueSetByAlts.containsAll( trueSet );
 688
 689
 690     // also check that the reference var sets are consistent
 691     Hashtable<VariableSourceToken, Set<TempDescriptor> > vst2refVars =
 692       new Hashtable<VariableSourceToken, Set<TempDescriptor> >();
 693     itr = var2vst.entrySet().iterator();
 694     while( itr.hasNext() ) {
 695       Map.Entry                     me     = (Map.Entry)                    itr.next();
 696       TempDescriptor                refVar = (TempDescriptor)               me.getKey();
 697       HashSet<VariableSourceToken>  s1     = (HashSet<VariableSourceToken>) me.getValue();
 698       Iterator<VariableSourceToken> vstItr = s1.iterator();
 699       while( vstItr.hasNext() ) {
 700         VariableSourceToken vst = vstItr.next();
 701         assert vst.getRefVars().contains( refVar );
 702
 703         Set<TempDescriptor> refVarsPart = vst2refVars.get( vst );
 704         if( refVarsPart == null ) {
 705           refVarsPart = new HashSet<TempDescriptor>();
 706         }
 707         refVarsPart.add( refVar );
 708         vst2refVars.put( vst, refVarsPart );
 709       }
 710     }
 711     itr = vst2refVars.entrySet().iterator();
 712     while( itr.hasNext() ) {
 713       Map.Entry           me  = (Map.Entry)           itr.next();
 714       VariableSourceToken vst = (VariableSourceToken) me.getKey();
 715       Set<TempDescriptor> s1  = (Set<TempDescriptor>) me.getValue();
 716
 717       assert vst.getRefVars().equals( s1 );
 718     }
 719   }
 720
 721
 722   public boolean equals( Object o ) {
 723     if( o == null ) {
 724       return false;
 725     }
 726
 727     if( !(o instanceof VarSrcTokTable) ) {
 728       return false;
 729     }
 730
 731     VarSrcTokTable table = (VarSrcTokTable) o;
 732     return trueSet.equals( table.trueSet );
 733   }
 734
 735   public int hashCode() {
 736     return trueSet.hashCode();
 737   }
 738
 739   public Iterator<VariableSourceToken> iterator() {
 740     return trueSet.iterator();
 741   }
 742
 743   public String toString() {
 744     return toStringPretty();
 745   }
 746
 747   public String toStringVerbose() {
 748     return "trueSet ="+trueSet.toString()+"\n"+
 749            "sese2vst="+sese2vst.toString()+"\n"+
 750            "var2vst ="+var2vst.toString()+"\n"+
 751            "sv2vst  ="+sv2vst.toString();
 752   }
 753
 754   public String toStringPretty() {
 755     String tokHighlighter = "o";
 756
 757     String str = "VarSrcTokTable\n";
 758     Iterator<VariableSourceToken> vstItr = trueSet.iterator();
 759     while( vstItr.hasNext() ) {
 760       str += "   "+tokHighlighter+" "+vstItr.next()+"\n";
 761     }
 762     return str;
 763   }
 764
 765   public String toStringPrettyVerbose() {
 766     String tokHighlighter = "o";
 767
 768     String str = "VarSrcTokTable\n";
 769
 770     Set s;
 771     Iterator itr;
 772     Iterator<VariableSourceToken> vstItr;
 773
 774     str += "  trueSet\n";
 775     vstItr = trueSet.iterator();
 776     while( vstItr.hasNext() ) {
 777       str += "     "+tokHighlighter+" "+vstItr.next()+"\n";
 778     }
 779
 780     str += "  sese2vst\n";
 781     itr = sese2vst.entrySet().iterator();
 782     while( itr.hasNext() ) {
 783       Map.Entry                    me   = (Map.Entry)                    itr.next();
 784       FlatSESEEnterNode            sese = (FlatSESEEnterNode)            me.getKey();
 785       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 786       assert s1 != null;
 787
 788       str += "    "+sese.getPrettyIdentifier()+" -> \n";
 789
 790       vstItr = s1.iterator();
 791       while( vstItr.hasNext() ) {
 792         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 793       }
 794     }
 795
 796     str += "  var2vst\n";
 797     itr = var2vst.entrySet().iterator();
 798     while( itr.hasNext() ) {
 799       Map.Entry                me  = (Map.Entry)                itr.next();
 800       TempDescriptor           var = (TempDescriptor)           me.getKey();
 801       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>) me.getValue();
 802       assert s1 != null;
 803
 804       str += "    "+var+" -> \n";
 805
 806       vstItr = s1.iterator();
 807       while( vstItr.hasNext() ) {
 808         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 809       }
 810     }
 811
 812     str += "  sv2vst\n";
 813     itr = sv2vst.entrySet().iterator();
 814     while( itr.hasNext() ) {
 815       Map.Entry                me  = (Map.Entry)                itr.next();
 816       SVKey                    key = (SVKey)                    me.getKey();
 817       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>) me.getValue();
 818       assert s1 != null;
 819
 820       str += "    "+key+" -> \n";
 821
 822       vstItr = s1.iterator();
 823       while( vstItr.hasNext() ) {
 824         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 825       }
 826     }
 827
 828     return str;
 829   }
 830 }