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   // get a sufficient set of VariableSourceTokens to cover all static sources
 534   public Set<VariableSourceToken> getStaticSet( FlatSESEEnterNode current,
 535                                                 FlatSESEEnterNode parent
 536                                               ) {
 537
 538     Set<VariableSourceToken> out = new HashSet<VariableSourceToken>();
 539
 540     Iterator itr = var2vst.entrySet().iterator();
 541     while( itr.hasNext() ) {
 542       Map.Entry                    me  = (Map.Entry)                    itr.next();
 543       TempDescriptor               var = (TempDescriptor)               me.getKey();
 544       HashSet<VariableSourceToken> s1  = (HashSet<VariableSourceToken>) me.getValue();
 545
 546       if( getRefVarSrcType( var, current, parent ) == SrcType_STATIC ) {
 547         out.add( s1.iterator().next() );
 548       }
 549     }
 550
 551     return out;
 552   }
 553
 554
 555   // given a table from a subsequent program point, decide
 556   // which variables are going from a static source to a
 557   // dynamic source and return them
 558   public Hashtable<TempDescriptor, VariableSourceToken>
 559     getStatic2DynamicSet( VarSrcTokTable nextTable,
 560                           Set<TempDescriptor> nextLiveIn,
 561                           FlatSESEEnterNode current,
 562                           FlatSESEEnterNode parent
 563                         ) {
 564
 565     Hashtable<TempDescriptor, VariableSourceToken> out =
 566       new Hashtable<TempDescriptor, VariableSourceToken>();
 567
 568     Iterator itr = var2vst.entrySet().iterator();
 569     while( itr.hasNext() ) {
 570       Map.Entry                    me  = (Map.Entry)                    itr.next();
 571       TempDescriptor               var = (TempDescriptor)               me.getKey();
 572       HashSet<VariableSourceToken> s1  = (HashSet<VariableSourceToken>) me.getValue();
 573
 574       // only worth tracking if live
 575       if( nextLiveIn.contains( var ) ) {
 576
 577         if(      this.getRefVarSrcType( var, current, parent ) == SrcType_STATIC  &&
 578             nextTable.getRefVarSrcType( var, current, parent ) == SrcType_DYNAMIC
 579           ) {
 580           // remember the variable and a static source
 581           // it had before crossing the transition
 582           out.put( var, s1.iterator().next() );
 583         }
 584       }
 585     }
 586
 587     return out;
 588   }
 589
 590
 591   // for some reference variable, return the type of source
 592   // it might have in this table, which might be:
 593   // 1. Ready -- this variable comes from your parent and is
 594   //      definitely available when you are issued.
 595   // 2. Static -- there is definitely one SESE that will
 596   //      produce the value for this variable
 597   // 3. Dynamic -- we don't know where the value will come
 598   //      from, so we'll track it dynamically
 599   public Integer getRefVarSrcType( TempDescriptor    refVar,
 600                                    FlatSESEEnterNode current,
 601                                    FlatSESEEnterNode parent ) {
 602     assert refVar != null;
 603
 604     // if you have no parent (root) and the variable in
 605     // question is in your in-set, it's a command line
 606     // argument and it is definitely available
 607     if( parent == null &&
 608         current.getInVarSet().contains( refVar ) ) {
 609       return SrcType_READY;
 610     }
 611
 612     // if there appear to be no sources, it means this variable
 613     // comes from outside of any statically-known SESE scope,
 614     // which means the system guarantees its READY
 615     Set<VariableSourceToken> srcs = get( refVar );
 616     if( srcs.isEmpty() ) {
 617       return SrcType_READY;
 618     }
 619
 620     // if the variable may have more than one source it might be
 621     // dynamic, unless all sources are from a placeholder
 622     if( srcs.size() > 1 ) {
 623       Iterator<VariableSourceToken> itrSrcs = srcs.iterator();
 624       VariableSourceToken oneSrc = itrSrcs.next();
 625       while( itrSrcs.hasNext() ) {
 626         VariableSourceToken anotherSrc = itrSrcs.next();
 627         if( !oneSrc.getSESE().equals( anotherSrc.getSESE() ) ||
 628             !oneSrc.getAge( ).equals( anotherSrc.getAge( ) )
 629           ) {
 630           return SrcType_DYNAMIC;
 631         }
 632       }
 633
 634       // all sources were same SESE and age, BUT, make sure it's
 635       // not a placeholder SESE, who's vars are always ready
 636       if( oneSrc.getSESE().getIsCallerSESEplaceholder() ) {
 637         return SrcType_READY;
 638       }
 639
 640       return SrcType_DYNAMIC;
 641     }
 642
 643     VariableSourceToken singleSrc = srcs.iterator().next();
 644     // if the one source is max age, track it dynamically
 645     if( singleSrc.getAge() == MLPAnalysis.maxSESEage ) {
 646       return SrcType_DYNAMIC;
 647     }
 648
 649     // if it has one source that comes from the parent, it's ready
 650     if( singleSrc.getSESE() == parent ) {
 651       return SrcType_READY;
 652     }
 653
 654     // if the one source is a placeholder SESE then it's ready
 655     if( singleSrc.getSESE().getIsCallerSESEplaceholder() ) {
 656       return SrcType_READY;
 657     }
 658
 659     // otherwise it comes from one source not the parent (sibling)
 660     // and we know exactly which static SESE/age it will come from
 661     return SrcType_STATIC;
 662   }
 663
 664
 665   // any reference variables that are not live can be pruned
 666   // from the table, and if any VSTs are then no longer
 667   // referenced, they can be dropped as well
 668   // THIS CAUSES INCONSISTENCY, FIX LATER, NOT REQUIRED
 669   public void pruneByLiveness( Set<TempDescriptor> rootLiveSet ) {
 670
 671     // the set of reference variables in the table minus the
 672     // live set gives the set of reference variables to remove
 673     Set<TempDescriptor> deadRefVars = new HashSet<TempDescriptor>();
 674     deadRefVars.addAll( var2vst.keySet() );
 675
 676     if( rootLiveSet != null ) {
 677       deadRefVars.removeAll( rootLiveSet );
 678     }
 679
 680     // just use the remove operation to prune the table now
 681     Iterator<TempDescriptor> deadItr = deadRefVars.iterator();
 682     while( deadItr.hasNext() ) {
 683       TempDescriptor dead = deadItr.next();
 684       removePrivate( dead );
 685     }
 686
 687     assertConsistency();
 688   }
 689
 690
 691
 692   // use as an aid for debugging, where true-set is checked
 693   // against the alternate mappings: assert that nothing is
 694   // missing or extra in the alternates
 695   public void assertConsistency() {
 696
 697     Iterator itr;
 698     Set s;
 699
 700     Set<VariableSourceToken> trueSetByAlts = new HashSet<VariableSourceToken>();
 701     itr = sese2vst.entrySet().iterator();
 702     while( itr.hasNext() ) {
 703       Map.Entry                    me   = (Map.Entry)                    itr.next();
 704       FlatSESEEnterNode            sese = (FlatSESEEnterNode)            me.getKey();
 705       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 706       assert s1 != null;
 707
 708       // the trueSet should have all entries in s1
 709       assert trueSet.containsAll( s1 );
 710
 711       // s1 should not have anything that doesn't appear in trueset
 712       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 713       sInt.removeAll( trueSet );
 714
 715       assert sInt.isEmpty();
 716
 717       // add s1 to a running union--at the end check if trueSet has extra
 718       trueSetByAlts.addAll( s1 );
 719     }
 720     // make sure trueSet isn't too big
 721     assert trueSetByAlts.containsAll( trueSet );
 722
 723
 724     trueSetByAlts = new HashSet<VariableSourceToken>();
 725     itr = var2vst.entrySet().iterator();
 726     while( itr.hasNext() ) {
 727       Map.Entry                    me   = (Map.Entry)                    itr.next();
 728       TempDescriptor               var  = (TempDescriptor)               me.getKey();
 729       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 730       assert s1 != null;
 731
 732       // the trueSet should have all entries in s1
 733       assert trueSet.containsAll( s1 );
 734
 735       // s1 should not have anything that doesn't appear in trueset
 736       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 737       sInt.removeAll( trueSet );
 738
 739       assert sInt.isEmpty();
 740
 741       // add s1 to a running union--at the end check if trueSet has extra
 742       trueSetByAlts.addAll( s1 );
 743     }
 744     // make sure trueSet isn't too big
 745     assert trueSetByAlts.containsAll( trueSet );
 746
 747
 748     trueSetByAlts = new HashSet<VariableSourceToken>();
 749     itr = sv2vst.entrySet().iterator();
 750     while( itr.hasNext() ) {
 751       Map.Entry                    me   = (Map.Entry)                    itr.next();
 752       SVKey                        key  = (SVKey)                        me.getKey();
 753       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 754       assert s1 != null;
 755
 756       // the trueSet should have all entries in s1
 757       assert trueSet.containsAll( s1 );
 758
 759       // s1 should not have anything that doesn't appear in trueset
 760       Set<VariableSourceToken> sInt = (Set<VariableSourceToken>) s1.clone();
 761       sInt.removeAll( trueSet );
 762
 763       assert sInt.isEmpty();
 764
 765       // add s1 to a running union--at the end check if trueSet has extra
 766       trueSetByAlts.addAll( s1 );
 767     }
 768     // make sure trueSet isn't too big
 769     assert trueSetByAlts.containsAll( trueSet );
 770
 771
 772     // also check that the reference var sets are consistent
 773     Hashtable<VariableSourceToken, Set<TempDescriptor> > vst2refVars =
 774       new Hashtable<VariableSourceToken, Set<TempDescriptor> >();
 775     itr = var2vst.entrySet().iterator();
 776     while( itr.hasNext() ) {
 777       Map.Entry                     me     = (Map.Entry)                    itr.next();
 778       TempDescriptor                refVar = (TempDescriptor)               me.getKey();
 779       HashSet<VariableSourceToken>  s1     = (HashSet<VariableSourceToken>) me.getValue();
 780       Iterator<VariableSourceToken> vstItr = s1.iterator();
 781       while( vstItr.hasNext() ) {
 782         VariableSourceToken vst = vstItr.next();
 783         assert vst.getRefVars().contains( refVar );
 784
 785         Set<TempDescriptor> refVarsPart = vst2refVars.get( vst );
 786         if( refVarsPart == null ) {
 787           refVarsPart = new HashSet<TempDescriptor>();
 788         }
 789         refVarsPart.add( refVar );
 790         vst2refVars.put( vst, refVarsPart );
 791       }
 792     }
 793     itr = vst2refVars.entrySet().iterator();
 794     while( itr.hasNext() ) {
 795       Map.Entry           me  = (Map.Entry)           itr.next();
 796       VariableSourceToken vst = (VariableSourceToken) me.getKey();
 797       Set<TempDescriptor> s1  = (Set<TempDescriptor>) me.getValue();
 798
 799       assert vst.getRefVars().equals( s1 );
 800     }
 801   }
 802
 803
 804   public boolean equals( Object o ) {
 805     if( o == null ) {
 806       return false;
 807     }
 808
 809     if( !(o instanceof VarSrcTokTable) ) {
 810       return false;
 811     }
 812
 813     VarSrcTokTable table = (VarSrcTokTable) o;
 814     return trueSet.equals( table.trueSet );
 815   }
 816
 817   public int hashCode() {
 818     return trueSet.hashCode();
 819   }
 820
 821   public Iterator<VariableSourceToken> iterator() {
 822     return trueSet.iterator();
 823   }
 824
 825   public String toString() {
 826     return toStringPretty();
 827   }
 828
 829   public String toStringVerbose() {
 830     return "trueSet ="+trueSet.toString()+"\n"+
 831            "sese2vst="+sese2vst.toString()+"\n"+
 832            "var2vst ="+var2vst.toString()+"\n"+
 833            "sv2vst  ="+sv2vst.toString();
 834   }
 835
 836   public String toStringPretty() {
 837     String tokHighlighter = "o";
 838
 839     String str = "VarSrcTokTable\n";
 840     Iterator<VariableSourceToken> vstItr = trueSet.iterator();
 841     while( vstItr.hasNext() ) {
 842       str += "   "+tokHighlighter+" "+vstItr.next()+"\n";
 843     }
 844     return str;
 845   }
 846
 847   public String toStringPrettyVerbose() {
 848     String tokHighlighter = "o";
 849
 850     String str = "VarSrcTokTable\n";
 851
 852     Set s;
 853     Iterator itr;
 854     Iterator<VariableSourceToken> vstItr;
 855
 856     str += "  trueSet\n";
 857     vstItr = trueSet.iterator();
 858     while( vstItr.hasNext() ) {
 859       str += "     "+tokHighlighter+" "+vstItr.next()+"\n";
 860     }
 861
 862     str += "  sese2vst\n";
 863     itr = sese2vst.entrySet().iterator();
 864     while( itr.hasNext() ) {
 865       Map.Entry                    me   = (Map.Entry)                    itr.next();
 866       FlatSESEEnterNode            sese = (FlatSESEEnterNode)            me.getKey();
 867       HashSet<VariableSourceToken> s1   = (HashSet<VariableSourceToken>) me.getValue();
 868       assert s1 != null;
 869
 870       str += "    "+sese.getPrettyIdentifier()+" -> \n";
 871
 872       vstItr = s1.iterator();
 873       while( vstItr.hasNext() ) {
 874         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 875       }
 876     }
 877
 878     str += "  var2vst\n";
 879     itr = var2vst.entrySet().iterator();
 880     while( itr.hasNext() ) {
 881       Map.Entry                me  = (Map.Entry)                itr.next();
 882       TempDescriptor           var = (TempDescriptor)           me.getKey();
 883       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>) me.getValue();
 884       assert s1 != null;
 885
 886       str += "    "+var+" -> \n";
 887
 888       vstItr = s1.iterator();
 889       while( vstItr.hasNext() ) {
 890         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 891       }
 892     }
 893
 894     str += "  sv2vst\n";
 895     itr = sv2vst.entrySet().iterator();
 896     while( itr.hasNext() ) {
 897       Map.Entry                me  = (Map.Entry)                itr.next();
 898       SVKey                    key = (SVKey)                    me.getKey();
 899       Set<VariableSourceToken> s1  = (Set<VariableSourceToken>) me.getValue();
 900       assert s1 != null;
 901
 902       str += "    "+key+" -> \n";
 903
 904       vstItr = s1.iterator();
 905       while( vstItr.hasNext() ) {
 906         str += "       "+tokHighlighter+" "+vstItr.next()+"\n";
 907       }
 908     }
 909
 910     return str;
 911   }
 912 }