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