1 /*
   2  * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "memory/allocation.inline.hpp"
  27 #include "opto/chaitin.hpp"
  28 #include "opto/compile.hpp"
  29 #include "opto/indexSet.hpp"
  30 #include "opto/regmask.hpp"
  31 
  32 // This file defines the IndexSet class, a set of sparse integer indices.
  33 // This data structure is used by the compiler in its liveness analysis and
  34 // during register allocation.  It also defines an iterator for this class.
  35 
  36 //-------------------------------- Initializations ------------------------------
  37 
  38 IndexSet::BitBlock  IndexSet::_empty_block     = IndexSet::BitBlock();
  39 
  40 #ifdef ASSERT
  41 // Initialize statistics counters
  42 julong IndexSet::_alloc_new = 0;
  43 julong IndexSet::_alloc_total = 0;
  44 
  45 julong IndexSet::_total_bits = 0;
  46 julong IndexSet::_total_used_blocks = 0;
  47 julong IndexSet::_total_unused_blocks = 0;
  48 
  49 // Per set, or all sets operation tracing
  50 int IndexSet::_serial_count = 1;
  51 #endif
  52 
  53 // What is the first set bit in a 5 bit integer?
  54 const uint8_t IndexSetIterator::_first_bit[32] = {
  55   0, 0, 1, 0,
  56   2, 0, 1, 0,
  57   3, 0, 1, 0,
  58   2, 0, 1, 0,
  59   4, 0, 1, 0,
  60   2, 0, 1, 0,
  61   3, 0, 1, 0,
  62   2, 0, 1, 0
  63 };
  64 
  65 // What is the second set bit in a 5 bit integer?
  66 const uint8_t IndexSetIterator::_second_bit[32] = {
  67   5, 5, 5, 1,
  68   5, 2, 2, 1,
  69   5, 3, 3, 1,
  70   3, 2, 2, 1,
  71   5, 4, 4, 1,
  72   4, 2, 2, 1,
  73   4, 3, 3, 1,
  74   3, 2, 2, 1
  75 };
  76 
  77 // I tried implementing the IndexSetIterator with a window_size of 8 and
  78 // didn't seem to get a noticeable speedup.  I am leaving in the tables
  79 // in case we want to switch back.
  80 
  81 /*const byte IndexSetIterator::_first_bit[256] = {
  82   8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  83   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  84   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  85   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  86   6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  87   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  88   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  89   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  90   7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  91   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  92   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  93   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  94   6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  95   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  96   5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  97   4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  98 };
  99 
 100 const byte IndexSetIterator::_second_bit[256] = {
 101   8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1,
 102   8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
 103   8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
 104   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
 105   8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
 106   6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
 107   6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
 108   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
 109   8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
 110   7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
 111   7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
 112   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
 113   7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
 114   6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
 115   6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
 116   5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1
 117 };*/
 118 
 119 //---------------------------- IndexSet::populate_free_list() -----------------------------
 120 // Populate the free BitBlock list with a batch of BitBlocks.  The BitBlocks
 121 // are 32 bit aligned.
 122 
 123 void IndexSet::populate_free_list() {
 124   Compile *compile = Compile::current();
 125   BitBlock *free = (BitBlock*)compile->indexSet_free_block_list();
 126 
 127   char *mem = (char*)arena()->Amalloc_4(sizeof(BitBlock) *
 128                                         bitblock_alloc_chunk_size + 32);
 129 
 130   // Align the pointer to a 32 bit boundary.
 131   BitBlock *new_blocks = (BitBlock*)(((uintptr_t)mem + 32) & ~0x001F);
 132 
 133   // Add the new blocks to the free list.
 134   for (int i = 0; i < bitblock_alloc_chunk_size; i++) {
 135     new_blocks->set_next(free);
 136     free = new_blocks;
 137     new_blocks++;
 138   }
 139 
 140   compile->set_indexSet_free_block_list(free);
 141 
 142 #ifdef ASSERT
 143   if (CollectIndexSetStatistics) {
 144     inc_stat_counter(&_alloc_new, bitblock_alloc_chunk_size);
 145   }
 146 #endif
 147 }
 148 
 149 
 150 //---------------------------- IndexSet::alloc_block() ------------------------
 151 // Allocate a BitBlock from the free list.  If the free list is empty,
 152 // prime it.
 153 
 154 IndexSet::BitBlock *IndexSet::alloc_block() {
 155 #ifdef ASSERT
 156   if (CollectIndexSetStatistics) {
 157     inc_stat_counter(&_alloc_total, 1);
 158   }
 159 #endif
 160   Compile *compile = Compile::current();
 161   BitBlock* free_list = (BitBlock*)compile->indexSet_free_block_list();
 162   if (free_list == NULL) {
 163     populate_free_list();
 164     free_list = (BitBlock*)compile->indexSet_free_block_list();
 165   }
 166   BitBlock *block = free_list;
 167   compile->set_indexSet_free_block_list(block->next());
 168 
 169   block->clear();
 170   return block;
 171 }
 172 
 173 //---------------------------- IndexSet::alloc_block_containing() -------------
 174 // Allocate a new BitBlock and put it into the position in the _blocks array
 175 // corresponding to element.
 176 
 177 IndexSet::BitBlock *IndexSet::alloc_block_containing(uint element) {
 178   BitBlock *block = alloc_block();
 179   uint bi = get_block_index(element);
 180   _blocks[bi] = block;
 181   return block;
 182 }
 183 
 184 //---------------------------- IndexSet::free_block() -------------------------
 185 // Add a BitBlock to the free list.
 186 
 187 void IndexSet::free_block(uint i) {
 188   debug_only(check_watch("free block", i));
 189   assert(i < _max_blocks, "block index too large");
 190   BitBlock *block = _blocks[i];
 191   assert(block != &_empty_block, "cannot free the empty block");
 192   block->set_next((IndexSet::BitBlock*)Compile::current()->indexSet_free_block_list());
 193   Compile::current()->set_indexSet_free_block_list(block);
 194   set_block(i,&_empty_block);
 195 }
 196 
 197 //------------------------------lrg_union--------------------------------------
 198 // Compute the union of all elements of one and two which interfere with
 199 // the RegMask mask.  If the degree of the union becomes exceeds
 200 // fail_degree, the union bails out.  The underlying set is cleared before
 201 // the union is performed.
 202 
 203 uint IndexSet::lrg_union(uint lr1, uint lr2,
 204                          const uint fail_degree,
 205                          const PhaseIFG *ifg,
 206                          const RegMask &mask ) {
 207   IndexSet *one = ifg->neighbors(lr1);
 208   IndexSet *two = ifg->neighbors(lr2);
 209   LRG &lrg1 = ifg->lrgs(lr1);
 210   LRG &lrg2 = ifg->lrgs(lr2);
 211 #ifdef ASSERT
 212   assert(_max_elements == one->_max_elements, "max element mismatch");
 213   check_watch("union destination");
 214   one->check_watch("union source");
 215   two->check_watch("union source");
 216 #endif
 217 
 218   // Compute the degree of the combined live-range.  The combined
 219   // live-range has the union of the original live-ranges' neighbors set as
 220   // well as the neighbors of all intermediate copies, minus those neighbors
 221   // that can not use the intersected allowed-register-set.
 222 
 223   // Copy the larger set.  Insert the smaller set into the larger.
 224   if (two->count() > one->count()) {
 225     IndexSet *temp = one;
 226     one = two;
 227     two = temp;
 228   }
 229 
 230   clear();
 231 
 232   // Used to compute degree of register-only interferences.  Infinite-stack
 233   // neighbors do not alter colorability, as they can always color to some
 234   // other color.  (A variant of the Briggs assertion)
 235   uint reg_degree = 0;
 236 
 237   uint element;
 238   // Load up the combined interference set with the neighbors of one
 239   IndexSetIterator elements(one);
 240   while ((element = elements.next()) != 0) {
 241     LRG &lrg = ifg->lrgs(element);
 242     if (mask.overlap(lrg.mask())) {
 243       insert(element);
 244       if( !lrg.mask().is_AllStack() ) {
 245         reg_degree += lrg1.compute_degree(lrg);
 246         if( reg_degree >= fail_degree ) return reg_degree;
 247       } else {
 248         // !!!!! Danger!  No update to reg_degree despite having a neighbor.
 249         // A variant of the Briggs assertion.
 250         // Not needed if I simplify during coalesce, ala George/Appel.
 251         assert( lrg.lo_degree(), "" );
 252       }
 253     }
 254   }
 255   // Add neighbors of two as well
 256   IndexSetIterator elements2(two);
 257   while ((element = elements2.next()) != 0) {
 258     LRG &lrg = ifg->lrgs(element);
 259     if (mask.overlap(lrg.mask())) {
 260       if (insert(element)) {
 261         if( !lrg.mask().is_AllStack() ) {
 262           reg_degree += lrg2.compute_degree(lrg);
 263           if( reg_degree >= fail_degree ) return reg_degree;
 264         } else {
 265           // !!!!! Danger!  No update to reg_degree despite having a neighbor.
 266           // A variant of the Briggs assertion.
 267           // Not needed if I simplify during coalesce, ala George/Appel.
 268           assert( lrg.lo_degree(), "" );
 269         }
 270       }
 271     }
 272   }
 273 
 274   return reg_degree;
 275 }
 276 
 277 //---------------------------- IndexSet() -----------------------------
 278 // A deep copy constructor.  This is used when you need a scratch copy of this set.
 279 
 280 IndexSet::IndexSet (IndexSet *set) {
 281 #ifdef ASSERT
 282   _serial_number = _serial_count++;
 283   set->check_watch("copied", _serial_number);
 284   check_watch("initialized by copy", set->_serial_number);
 285   _max_elements = set->_max_elements;
 286 #endif
 287   _count = set->_count;
 288   _max_blocks = set->_max_blocks;
 289   if (_max_blocks <= preallocated_block_list_size) {
 290     _blocks = _preallocated_block_list;
 291   } else {
 292     _blocks =
 293       (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
 294   }
 295   for (uint i = 0; i < _max_blocks; i++) {
 296     BitBlock *block = set->_blocks[i];
 297     if (block == &_empty_block) {
 298       set_block(i, &_empty_block);
 299     } else {
 300       BitBlock *new_block = alloc_block();
 301       memcpy(new_block->words(), block->words(), sizeof(uint32_t) * words_per_block);
 302       set_block(i, new_block);
 303     }
 304   }
 305 }
 306 
 307 //---------------------------- IndexSet::initialize() -----------------------------
 308 // Prepare an IndexSet for use.
 309 
 310 void IndexSet::initialize(uint max_elements) {
 311 #ifdef ASSERT
 312   _serial_number = _serial_count++;
 313   check_watch("initialized", max_elements);
 314   _max_elements = max_elements;
 315 #endif
 316   _count = 0;
 317   _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block;
 318 
 319   if (_max_blocks <= preallocated_block_list_size) {
 320     _blocks = _preallocated_block_list;
 321   } else {
 322     _blocks = (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
 323   }
 324   for (uint i = 0; i < _max_blocks; i++) {
 325     set_block(i, &_empty_block);
 326   }
 327 }
 328 
 329 //---------------------------- IndexSet::initialize()------------------------------
 330 // Prepare an IndexSet for use.  If it needs to allocate its _blocks array, it does
 331 // so from the Arena passed as a parameter.  BitBlock allocation is still done from
 332 // the static Arena which was set with reset_memory().
 333 
 334 void IndexSet::initialize(uint max_elements, Arena *arena) {
 335 #ifdef ASSERT
 336   _serial_number = _serial_count++;
 337   check_watch("initialized2", max_elements);
 338   _max_elements = max_elements;
 339 #endif // ASSERT
 340   _count = 0;
 341   _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block;
 342 
 343   if (_max_blocks <= preallocated_block_list_size) {
 344     _blocks = _preallocated_block_list;
 345   } else {
 346     _blocks = (IndexSet::BitBlock**) arena->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
 347   }
 348   for (uint i = 0; i < _max_blocks; i++) {
 349     set_block(i, &_empty_block);
 350   }
 351 }
 352 
 353 //---------------------------- IndexSet::swap() -----------------------------
 354 // Exchange two IndexSets.
 355 
 356 void IndexSet::swap(IndexSet *set) {
 357 #ifdef ASSERT
 358   assert(_max_elements == set->_max_elements, "must have same universe size to swap");
 359   check_watch("swap", set->_serial_number);
 360   set->check_watch("swap", _serial_number);
 361 #endif
 362 
 363   for (uint i = 0; i < _max_blocks; i++) {
 364     BitBlock *temp = _blocks[i];
 365     set_block(i, set->_blocks[i]);
 366     set->set_block(i, temp);
 367   }
 368   uint temp = _count;
 369   _count = set->_count;
 370   set->_count = temp;
 371 }
 372 
 373 //---------------------------- IndexSet::dump() -----------------------------
 374 // Print this set.  Used for debugging.
 375 
 376 #ifndef PRODUCT
 377 void IndexSet::dump() const {
 378   IndexSetIterator elements(this);
 379 
 380   tty->print("{");
 381   uint i;
 382   while ((i = elements.next()) != 0) {
 383     tty->print("L%d ", i);
 384   }
 385   tty->print_cr("}");
 386 }
 387 #endif
 388 
 389 #ifdef ASSERT
 390 //---------------------------- IndexSet::tally_iteration_statistics() -----------------------------
 391 // Update block/bit counts to reflect that this set has been iterated over.
 392 
 393 void IndexSet::tally_iteration_statistics() const {
 394   inc_stat_counter(&_total_bits, count());
 395 
 396   for (uint i = 0; i < _max_blocks; i++) {
 397     if (_blocks[i] != &_empty_block) {
 398       inc_stat_counter(&_total_used_blocks, 1);
 399     } else {
 400       inc_stat_counter(&_total_unused_blocks, 1);
 401     }
 402   }
 403 }
 404 
 405 //---------------------------- IndexSet::print_statistics() -----------------------------
 406 // Print statistics about IndexSet usage.
 407 
 408 void IndexSet::print_statistics() {
 409   julong total_blocks = _total_used_blocks + _total_unused_blocks;
 410   tty->print_cr ("Accumulated IndexSet usage statistics:");
 411   tty->print_cr ("--------------------------------------");
 412   tty->print_cr ("  Iteration:");
 413   tty->print_cr ("    blocks visited: " UINT64_FORMAT, total_blocks);
 414   tty->print_cr ("    blocks empty: %4.2f%%", 100.0*(double)_total_unused_blocks/total_blocks);
 415   tty->print_cr ("    bit density (bits/used blocks): %4.2f", (double)_total_bits/_total_used_blocks);
 416   tty->print_cr ("    bit density (bits/all blocks): %4.2f", (double)_total_bits/total_blocks);
 417   tty->print_cr ("  Allocation:");
 418   tty->print_cr ("    blocks allocated: " UINT64_FORMAT, _alloc_new);
 419   tty->print_cr ("    blocks used/reused: " UINT64_FORMAT, _alloc_total);
 420 }
 421 
 422 //---------------------------- IndexSet::verify() -----------------------------
 423 // Expensive test of IndexSet sanity.  Ensure that the count agrees with the
 424 // number of bits in the blocks.  Make sure the iterator is seeing all elements
 425 // of the set.  Meant for use during development.
 426 
 427 void IndexSet::verify() const {
 428   assert(!member(0), "zero cannot be a member");
 429   uint count = 0;
 430   uint i;
 431   for (i = 1; i < _max_elements; i++) {
 432     if (member(i)) {
 433       count++;
 434       assert(count <= _count, "_count is messed up");
 435     }
 436   }
 437 
 438   IndexSetIterator elements(this);
 439   count = 0;
 440   while ((i = elements.next()) != 0) {
 441     count++;
 442     assert(member(i), "returned a non member");
 443     assert(count <= _count, "iterator returned wrong number of elements");
 444   }
 445 }
 446 #endif
 447 
 448 //---------------------------- IndexSetIterator() -----------------------------
 449 // Create an iterator for a set.  If empty blocks are detected when iterating
 450 // over the set, these blocks are replaced.
 451 
 452 IndexSetIterator::IndexSetIterator(IndexSet *set) {
 453 #ifdef ASSERT
 454   if (CollectIndexSetStatistics) {
 455     set->tally_iteration_statistics();
 456   }
 457   set->check_watch("traversed", set->count());
 458 #endif
 459   if (set->is_empty()) {
 460     _current = 0;
 461     _next_word = IndexSet::words_per_block;
 462     _next_block = 1;
 463     _max_blocks = 1;
 464 
 465     // We don't need the following values when we iterate over an empty set.
 466     // The commented out code is left here to document that the omission
 467     // is intentional.
 468     //
 469     //_value = 0;
 470     //_words = NULL;
 471     //_blocks = NULL;
 472     //_set = NULL;
 473   } else {
 474     _current = 0;
 475     _value = 0;
 476     _next_block = 0;
 477     _next_word = IndexSet::words_per_block;
 478 
 479     _max_blocks = set->_max_blocks;
 480     _words = NULL;
 481     _blocks = set->_blocks;
 482     _set = set;
 483   }
 484 }
 485 
 486 //---------------------------- IndexSetIterator(const) -----------------------------
 487 // Iterate over a constant IndexSet.
 488 
 489 IndexSetIterator::IndexSetIterator(const IndexSet *set) {
 490 #ifdef ASSERT
 491   if (CollectIndexSetStatistics) {
 492     set->tally_iteration_statistics();
 493   }
 494   // We don't call check_watch from here to avoid bad recursion.
 495   //   set->check_watch("traversed const", set->count());
 496 #endif
 497   if (set->is_empty()) {
 498     _current = 0;
 499     _next_word = IndexSet::words_per_block;
 500     _next_block = 1;
 501     _max_blocks = 1;
 502 
 503     // We don't need the following values when we iterate over an empty set.
 504     // The commented out code is left here to document that the omission
 505     // is intentional.
 506     //
 507     //_value = 0;
 508     //_words = NULL;
 509     //_blocks = NULL;
 510     //_set = NULL;
 511   } else {
 512     _current = 0;
 513     _value = 0;
 514     _next_block = 0;
 515     _next_word = IndexSet::words_per_block;
 516 
 517     _max_blocks = set->_max_blocks;
 518     _words = NULL;
 519     _blocks = set->_blocks;
 520     _set = NULL;
 521   }
 522 }
 523 
 524 //---------------------------- List16Iterator::advance_and_next() -----------------------------
 525 // Advance to the next non-empty word in the set being iterated over.  Return the next element
 526 // if there is one.  If we are done, return 0.  This method is called from the next() method
 527 // when it gets done with a word.
 528 
 529 uint IndexSetIterator::advance_and_next() {
 530   // See if there is another non-empty word in the current block.
 531   for (uint wi = _next_word; wi < (unsigned)IndexSet::words_per_block; wi++) {
 532     if (_words[wi] != 0) {
 533       // Found a non-empty word.
 534       _value = ((_next_block - 1) * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word);
 535       _current = _words[wi];
 536 
 537       _next_word = wi+1;
 538 
 539       return next();
 540     }
 541   }
 542 
 543   // We ran out of words in the current block.  Advance to next non-empty block.
 544   for (uint bi = _next_block; bi < _max_blocks; bi++) {
 545     if (_blocks[bi] != &IndexSet::_empty_block) {
 546       // Found a non-empty block.
 547 
 548       _words = _blocks[bi]->words();
 549       for (uint wi = 0; wi < (unsigned)IndexSet::words_per_block; wi++) {
 550         if (_words[wi] != 0) {
 551           // Found a non-empty word.
 552           _value = (bi * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word);
 553           _current = _words[wi];
 554 
 555           _next_block = bi+1;
 556           _next_word = wi+1;
 557 
 558           return next();
 559         }
 560       }
 561 
 562       // All of the words in the block were empty.  Replace
 563       // the block with the empty block.
 564       if (_set) {
 565         _set->free_block(bi);
 566       }
 567     }
 568   }
 569 
 570   // These assignments make redundant calls to next on a finished iterator
 571   // faster.  Probably not necessary.
 572   _next_block = _max_blocks;
 573   _next_word = IndexSet::words_per_block;
 574 
 575   // No more words.
 576   return 0;
 577 }