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       Iterator<VariableSourceToken> vstItr = get( child ).iterator();
 394       while( vstItr.hasNext() ) {
 395         VariableSourceToken vst = vstItr.next();
 396
 397         remove( vst );
 398
 399         add( new VariableSourceToken( vst.getRefVars(),
 400                                       curr,
 401                                       new Integer( 0 ),
 402                                       vst.getAddrVar()
 403                                       )
 404              );
 405       }
 406     }
 407
 408     assertConsistency();
 409   }
 410
 411
 412   // this method is called at the SESE exit of SESE 'curr'
 413   // if the sources for a variable written by curr can also
 414   // come from curr's parent or curr's siblings then we're not
 415   // sure that curr will actually modify the variable.  There are
 416   // many ways to handle this, but for now, mark the variable as
 417   // virtually read so curr insists on having ownership of it
 418   // whether it ends up writing to it or not.  It will always, then,
 419   // appear in curr's out-set.
 420   public Set<TempDescriptor>
 421     calcVirtReadsAndPruneParentAndSiblingTokens( FlatSESEEnterNode exiter,
 422                                                  Set<TempDescriptor> liveVars ) {
 423
 424     Set<TempDescriptor> virtReadSet = new HashSet<TempDescriptor>();
 425
 426     FlatSESEEnterNode parent = exiter.getParent();
 427     if( parent == null ) {
 428       // having no parent means no siblings, too
 429       return virtReadSet;
 430     }
 431
 432     Set<FlatSESEEnterNode> alternateSESEs = new HashSet<FlatSESEEnterNode>();
 433     alternateSESEs.add( parent );
 434     Iterator<FlatSESEEnterNode> childItr = parent.getChildren().iterator();
 435     while( childItr.hasNext() ) {
 436       FlatSESEEnterNode sibling = childItr.next();
 437       if( !sibling.equals( exiter ) ) {
 438         alternateSESEs.add( sibling );
 439       }
 440     }
 441
 442     // VSTs to remove if they are alternate sources for exiter VSTs
 443     // whose variables will become virtual reads
 444     Set<VariableSourceToken> forRemoval = new HashSet<VariableSourceToken>();
 445
 446     // look at all of this SESE's VSTs at exit...
 447     Iterator<VariableSourceToken> vstItr = get( exiter ).iterator();
 448     while( vstItr.hasNext() ) {
 449       VariableSourceToken vstExiterSrc = vstItr.next();
 450
 451       // only interested in tokens that come from our current instance
 452       if( vstExiterSrc.getAge() != 0 ) {
 453         continue;
 454       }
 455
 456       // for each variable that might come from those sources...
 457       Iterator<TempDescriptor> refVarItr = vstExiterSrc.getRefVars().iterator();
 458       while( refVarItr.hasNext() ) {
 459         TempDescriptor refVar = refVarItr.next();
 460
 461         // only matters for live variables at SESE exit program point
 462         if( !liveVars.contains( refVar ) ) {
 463           continue;
 464         }
 465
 466         // examine other sources for a variable...
 467         Iterator<VariableSourceToken> srcItr = get( refVar ).iterator();
 468         while( srcItr.hasNext() ) {
 469           VariableSourceToken vstPossibleOtherSrc = srcItr.next();
 470
 471           if( vstPossibleOtherSrc.getSESE().equals( exiter ) &&
 472               vstPossibleOtherSrc.getAge() > 0
 473             ) {
 474             // this is an alternate source if its
 475             // an older instance of this SESE
 476             virtReadSet.add( refVar );
 477             forRemoval.add( vstPossibleOtherSrc );
 478
 479           } else if( alternateSESEs.contains( vstPossibleOtherSrc.getSESE() ) ) {
 480             // this is an alternate source from parent or sibling
 481             virtReadSet.add( refVar );
 482             forRemoval.add( vstPossibleOtherSrc );
 483
 484           } else {
 485             assert vstPossibleOtherSrc.getSESE().equals( exiter );
 486             assert vstPossibleOtherSrc.getAge().equals( 0 );
 487           }
 488         }
 489       }
 490     }
 491
 492     vstItr = forRemoval.iterator();
 493     while( vstItr.hasNext() ) {
 494       VariableSourceToken vst = vstItr.next();
 495       remove( vst );
 496     }
 497     assertConsistency();
 498
 499     return virtReadSet;
 500   }
 501
 502
 503   // get the set of VST's that come from a child
 504   public Set<VariableSourceToken> getChildrenVSTs( FlatSESEEnterNode curr ) {
 505
 506     Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
 507
 508     Iterator<FlatSESEEnterNode> cItr = curr.getChildren().iterator();
 509     while( cItr.hasNext() ) {
 510       FlatSESEEnterNode child = cItr.next();
 511       out.addAll( get( child ) );
 512     }
 513
 514     return out;
 515   }
 516
 517
 518   // get a sufficient set of VariableSourceTokens to cover all static sources
 519   public Set<VariableSourceToken> getStaticSet( FlatSESEEnterNode current,
 520                                                 FlatSESEEnterNode parent
 521                                               ) {
 522
 523     Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
 524
 525     Iterator itr = var2vst.entrySet().iterator();
 526     while( itr.hasNext() ) {
 527       Map.Entry                    me  = (Map.Entry)                    itr.next();
 528       TempDescriptor               var = (TempDescriptor)               me.getKey();
 529       HashSet<VariableSourceToken> s1  = (HashSet<VariableSourceToken>) me.getValue();
 530
 531       if( getRefVarSrcType( var, current, parent ) == SrcType_STATIC ) {
 532         out.add( s1.iterator().next() );
 533       }
 534     }
 535
 536     return out;
 537   }
 538
 539
 540   // given a table from a subsequent program point, decide
 541   // which variables are going from a static source to a
 542   // dynamic source and return them
 543   public Hashtable<TempDescriptor, VariableSourceToken>
 544     getStatic2DynamicSet( VarSrcTokTable nextTable,
 545                           Set<TempDescriptor> nextLiveIn,
 546                           FlatSESEEnterNode current,
 547                           FlatSESEEnterNode parent
 548                         ) {
 549
 550     Hashtable<TempDescriptor, VariableSourceToken> out =
 551       new Hashtable<TempDescriptor, VariableSourceToken>();
 552
 553     Iterator itr = var2vst.entrySet().iterator();
 554     while( itr.hasNext() ) {
 555       Map.Entry                    me  = (Map.Entry)                    itr.next();
 556       TempDescriptor               var = (TempDescriptor)               me.getKey();
 557       HashSet<VariableSourceToken> s1  = (HashSet<VariableSourceToken>) me.getValue();
 558
 559       // only worth tracking if live
 560       if( nextLiveIn.contains( var ) ) {
 561
 562         if(      this.getRefVarSrcType( var, current, parent ) == SrcType_STATIC  &&
 563             nextTable.getRefVarSrcType( var, current, parent ) == SrcType_DYNAMIC
 564           ) {
 565           // remember the variable and a static source
 566           // it had before crossing the transition
 567           out.put( var, s1.iterator().next() );
 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 comes from your parent and is
 579   //      definitely available when you are issued.
 580   // 2. Static -- there is definitely one SESE that will
 581   //      produce the value for this variable
 582   // 3. Dynamic -- we don't know where the value will come
 583   //      from, so we'll track it dynamically
 584   public Integer getRefVarSrcType( TempDescriptor    refVar,
 585                                    FlatSESEEnterNode current,
 586                                    FlatSESEEnterNode parent ) {
 587     assert refVar != null;
 588
 589     // if you have no parent (root) and the variable in
 590     // question is in your in-set, it's a command line
 591     // argument and it is definitely available
 592     if( parent == null &&
 593         current.getInVarSet().contains( refVar ) ) {
 594       return SrcType_READY;
 595     }
 596
 597     // if there appear to be no sources, it means this variable
 598     // comes from outside of any statically-known SESE scope,
 599     // which means the system guarantees its READY
 600     Set<VariableSourceToken> srcs = get( refVar );
 601     if( srcs.isEmpty() ) {
 602       return SrcType_READY;
 603     }
 604
 605     // if the variable may have more than one source it might be
 606     // dynamic, unless all sources are from a placeholder
 607     if( srcs.size() > 1 ) {
 608       Iterator<VariableSourceToken> itrSrcs = srcs.iterator();
 609       VariableSourceToken oneSrc = itrSrcs.next();
 610       while( itrSrcs.hasNext() ) {
 611         VariableSourceToken anotherSrc = itrSrcs.next();
 612         if( !oneSrc.getSESE().equals( anotherSrc.getSESE() ) ||
 613             !oneSrc.getAge( ).equals( anotherSrc.getAge( ) )
 614           ) {
 615           return SrcType_DYNAMIC;
 616         }
 617       }
 618
 619       // all sources were same SESE and age, BUT, make sure it's
 620       // not a placeholder SESE, who's vars are always ready
 621       if( oneSrc.getSESE().getIsCallerSESEplaceholder() ) {
 622         return SrcType_READY;
 623       }
 624
 625       return SrcType_DYNAMIC;
 626     }
 627
 628     VariableSourceToken singleSrc = srcs.iterator().next();
 629     // if the one source is max age, track it dynamically
 630     if( singleSrc.getAge() == MLPAnalysis.maxSESEage ) {
 631       return SrcType_DYNAMIC;
 632     }
 633
 634     // if it has one source that comes from the parent, it's ready
 635     if( singleSrc.getSESE() == parent ) {
 636       return SrcType_READY;
 637     }
 638
 639     // if the one source is a placeholder SESE then it's ready
 640     if( singleSrc.getSESE().getIsCallerSESEplaceholder() ) {
 641       return SrcType_READY;
 642     }
 643
 644     // otherwise it comes from one source not the parent (sibling)
 645     // and we know exactly which static SESE/age it will come from
 646     return SrcType_STATIC;
 647   }
 648
 649
 650   // any reference variables that are not live can be pruned
 651   // from the table, and if any VSTs are then no longer
 652   // referenced, they can be dropped as well
 653   // THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED
 654   public void pruneByLiveness( Set<TempDescriptor> rootLiveSet ) {
 655
 656     // the set of reference variables in the table minus the
 657     // live set gives the set of reference variables to remove
 658     Set<TempDescriptor> deadRefVars = new HashSet<TempDescriptor>();
 659     deadRefVars.addAll( var2vst.keySet() );
 660
 661     if( rootLiveSet != null ) {
 662       deadRefVars.removeAll( rootLiveSet );
 663     }
 664
 665     // just use the remove operation to prune the table now
 666     Iterator<TempDescriptor> deadItr = deadRefVars.iterator();
 667     while( deadItr.hasNext() ) {
 668       TempDescriptor dead = deadItr.next();
 669       removePrivate( dead );
 670     }
 671
 672     assertConsistency();
 673   }
 674
 675
 676
 677   // use as an aid for debugging, where true-set is checked
 678   // against the alternate mappings: assert that nothing is
 679   // missing or extra in the alternates
 680   public void assertConsistency() {
 681
 682     Iterator itr;
 683     Set s;
 684
 685     Set<VariableSourceToken> trueSetByAlts = new HashSet<VariableSourceToken>();
 686     itr = sese2vst.entrySet().iterator();
 687     while( itr.hasNext() ) {
 688       Map.Entry                    me   = (Map.Entry)                    itr.next();
 689       FlatSESEEnterNode            sese = (FlatSESEEnterNode)            me.getKey();
 690       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 691       assert s1 != null;
 692
 693       // the trueSet should have all entries in s1
 694       assert trueSet.containsAll( s1 );
 695
 696       // s1 should not have anything that doesn't appear in trueset
 697       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 698       sInt.removeAll( trueSet );
 699
 700       assert sInt.isEmpty();
 701
 702       // add s1 to a running union--at the end check if trueSet has extra
 703       trueSetByAlts.addAll( s1 );
 704     }
 705     // make sure trueSet isn't too big
 706     assert trueSetByAlts.containsAll( trueSet );
 707
 708
 709     trueSetByAlts = new HashSet<VariableSourceToken>();
 710     itr = var2vst.entrySet().iterator();
 711     while( itr.hasNext() ) {
 712       Map.Entry                    me   = (Map.Entry)                    itr.next();
 713       TempDescriptor               var  = (TempDescriptor)               me.getKey();
 714       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 715       assert s1 != null;
 716
 717       // the trueSet should have all entries in s1
 718       assert trueSet.containsAll( s1 );
 719
 720       // s1 should not have anything that doesn't appear in trueset
 721       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 722       sInt.removeAll( trueSet );
 723
 724       assert sInt.isEmpty();
 725
 726       // add s1 to a running union--at the end check if trueSet has extra
 727       trueSetByAlts.addAll( s1 );
 728     }
 729     // make sure trueSet isn't too big
 730     assert trueSetByAlts.containsAll( trueSet );
 731
 732
 733     trueSetByAlts = new HashSet<VariableSourceToken>();
 734     itr = sv2vst.entrySet().iterator();
 735     while( itr.hasNext() ) {
 736       Map.Entry                    me   = (Map.Entry)                    itr.next();
 737       SVKey                        key  = (SVKey)                        me.getKey();
 738       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 739       assert s1 != null;
 740
 741       // the trueSet should have all entries in s1
 742       assert trueSet.containsAll( s1 );
 743
 744       // s1 should not have anything that doesn't appear in trueset
 745       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 746       sInt.removeAll( trueSet );
 747
 748       assert sInt.isEmpty();
 749
 750       // add s1 to a running union--at the end check if trueSet has extra
 751       trueSetByAlts.addAll( s1 );
 752     }
 753     // make sure trueSet isn't too big
 754     assert trueSetByAlts.containsAll( trueSet );
 755
 756
 757     // also check that the reference var sets are consistent
 758     Hashtable<VariableSourceToken, Set<TempDescriptor> > vst2refVars =
 759       new Hashtable<VariableSourceToken, Set<TempDescriptor> >();
 760     itr = var2vst.entrySet().iterator();
 761     while( itr.hasNext() ) {
 762       Map.Entry                     me     = (Map.Entry)                    itr.next();
 763       TempDescriptor                refVar = (TempDescriptor)               me.getKey();
 764       HashSet<VariableSourceToken>  s1     = (HashSet<VariableSourceToken>) me.getValue();
 765       Iterator<VariableSourceToken> vstItr = s1.iterator();
 766       while( vstItr.hasNext() ) {
 767         VariableSourceToken vst = vstItr.next();
 768         assert vst.getRefVars().contains( refVar );
 769
 770         Set<TempDescriptor> refVarsPart = vst2refVars.get( vst );
 771         if( refVarsPart == null ) {
 772           refVarsPart = new HashSet<TempDescriptor>();
 773         }
 774         refVarsPart.add( refVar );
 775         vst2refVars.put( vst, refVarsPart );
 776       }
 777     }
 778     itr = vst2refVars.entrySet().iterator();
 779     while( itr.hasNext() ) {
 780       Map.Entry           me  = (Map.Entry)           itr.next();
 781       VariableSourceToken vst = (VariableSourceToken) me.getKey();
 782       Set<TempDescriptor> s1  = (Set<TempDescriptor>) me.getValue();
 783
 784       assert vst.getRefVars().equals( s1 );
 785     }
 786   }
 787
 788
 789   public boolean equals( Object o ) {
 790     if( o == null ) {
 791       return false;
 792     }
 793
 794     if( !(o instanceof VarSrcTokTable) ) {
 795       return false;
 796     }
 797
 798     VarSrcTokTable table = (VarSrcTokTable) o;
 799     return trueSet.equals( table.trueSet );
 800   }
 801
 802   public int hashCode() {
 803     return trueSet.hashCode();
 804   }
 805
 806   public Iterator<VariableSourceToken> iterator() {
 807     return trueSet.iterator();
 808   }
 809
 810   public String toString() {
 811     return toStringPretty();
 812   }
 813
 814   public String toStringVerbose() {
 815     return "trueSet ="+trueSet.toString()+"\n"+
 816            "sese2vst="+sese2vst.toString()+"\n"+
 817            "var2vst ="+var2vst.toString()+"\n"+
 818            "sv2vst  ="+sv2vst.toString();
 819   }
 820
 821   public String toStringPretty() {
 822     String tokHighlighter = "o";
 823
 824     String str = "VarSrcTokTable\n";
 825     Iterator<VariableSourceToken> vstItr = trueSet.iterator();
 826     while( vstItr.hasNext() ) {
 827       str += "   "+tokHighlighter+" "+vstItr.next()+"\n";
 828     }
 829     return str;
 830   }
 831
 832   public String toStringPrettyVerbose() {
 833     String tokHighlighter = "o";
 834
 835     String str = "VarSrcTokTable\n";
 836
 837     Set s;
 838     Iterator itr;
 839     Iterator<VariableSourceToken> vstItr;
 840
 841     str += "  trueSet\n";
 842     vstItr = trueSet.iterator();
 843     while( vstItr.hasNext() ) {
 844       str += "     "+tokHighlighter+" "+vstItr.next()+"\n";
 845     }
 846
 847     str += "  sese2vst\n";
 848     itr = sese2vst.entrySet().iterator();
 849     while( itr.hasNext() ) {
 850       Map.Entry                    me   = (Map.Entry)                    itr.next();
 851       FlatSESEEnterNode            sese = (FlatSESEEnterNode)            me.getKey();
 852       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 853       assert s1 != null;
 854
 855       str += "    "+sese.getPrettyIdentifier()+" -> \n";
 856
 857       vstItr = s1.iterator();
 858       while( vstItr.hasNext() ) {
 859         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 860       }
 861     }
 862
 863     str += "  var2vst\n";
 864     itr = var2vst.entrySet().iterator();
 865     while( itr.hasNext() ) {
 866       Map.Entry                me  = (Map.Entry)                itr.next();
 867       TempDescriptor           var = (TempDescriptor)           me.getKey();
 868       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>) me.getValue();
 869       assert s1 != null;
 870
 871       str += "    "+var+" -> \n";
 872
 873       vstItr = s1.iterator();
 874       while( vstItr.hasNext() ) {
 875         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 876       }
 877     }
 878
 879     str += "  sv2vst\n";
 880     itr = sv2vst.entrySet().iterator();
 881     while( itr.hasNext() ) {
 882       Map.Entry                me  = (Map.Entry)                itr.next();
 883       SVKey                    key = (SVKey)                    me.getKey();
 884       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>) me.getValue();
 885       assert s1 != null;
 886
 887       str += "    "+key+" -> \n";
 888
 889       vstItr = s1.iterator();
 890       while( vstItr.hasNext() ) {
 891         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 892       }
 893     }
 894
 895     return str;
 896   }
 897 }