Java example source code file (indexSet.cpp)

This example Java source code file (indexSet.cpp) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

assert, bitblock, bitblock\*, collectindexsetstatistics, compile\:\:current, indexset, indexset::bitblock, indexset\:\:_empty_block, indexset\:\:bits_per_block, indexset\:\:words_per_block, indexsetiterator, lrg, null, uint64_format

The indexSet.cpp Java example source code

/*
 * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "precompiled.hpp"
#include "memory/allocation.inline.hpp"
#include "opto/chaitin.hpp"
#include "opto/compile.hpp"
#include "opto/indexSet.hpp"
#include "opto/regmask.hpp"

// This file defines the IndexSet class, a set of sparse integer indices.
// This data structure is used by the compiler in its liveness analysis and
// during register allocation.  It also defines an iterator for this class.

//-------------------------------- Initializations ------------------------------

IndexSet::BitBlock  IndexSet::_empty_block     = IndexSet::BitBlock();

#ifdef ASSERT
// Initialize statistics counters
julong IndexSet::_alloc_new = 0;
julong IndexSet::_alloc_total = 0;

julong IndexSet::_total_bits = 0;
julong IndexSet::_total_used_blocks = 0;
julong IndexSet::_total_unused_blocks = 0;

// Per set, or all sets operation tracing
int IndexSet::_serial_count = 1;
#endif

// What is the first set bit in a 5 bit integer?
const byte IndexSetIterator::_first_bit[32] = {
  0, 0, 1, 0,
  2, 0, 1, 0,
  3, 0, 1, 0,
  2, 0, 1, 0,
  4, 0, 1, 0,
  2, 0, 1, 0,
  3, 0, 1, 0,
  2, 0, 1, 0
};

// What is the second set bit in a 5 bit integer?
const byte IndexSetIterator::_second_bit[32] = {
  5, 5, 5, 1,
  5, 2, 2, 1,
  5, 3, 3, 1,
  3, 2, 2, 1,
  5, 4, 4, 1,
  4, 2, 2, 1,
  4, 3, 3, 1,
  3, 2, 2, 1
};

// I tried implementing the IndexSetIterator with a window_size of 8 and
// didn't seem to get a noticeable speedup.  I am leaving in the tables
// in case we want to switch back.

/*const byte IndexSetIterator::_first_bit[256] = {
  8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

const byte IndexSetIterator::_second_bit[256] = {
  8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1,
  8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
  8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
  8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
  6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
  6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
  8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
  7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
  7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
  7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
  6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
  6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1
};*/

//---------------------------- IndexSet::populate_free_list() -----------------------------
// Populate the free BitBlock list with a batch of BitBlocks.  The BitBlocks
// are 32 bit aligned.

void IndexSet::populate_free_list() {
  Compile *compile = Compile::current();
  BitBlock *free = (BitBlock*)compile->indexSet_free_block_list();

  char *mem = (char*)arena()->Amalloc_4(sizeof(BitBlock) *
                                        bitblock_alloc_chunk_size + 32);

  // Align the pointer to a 32 bit boundary.
  BitBlock *new_blocks = (BitBlock*)(((uintptr_t)mem + 32) & ~0x001F);

  // Add the new blocks to the free list.
  for (int i = 0; i < bitblock_alloc_chunk_size; i++) {
    new_blocks->set_next(free);
    free = new_blocks;
    new_blocks++;
  }

  compile->set_indexSet_free_block_list(free);

#ifdef ASSERT
  if (CollectIndexSetStatistics) {
    inc_stat_counter(&_alloc_new, bitblock_alloc_chunk_size);
  }
#endif
}


//---------------------------- IndexSet::alloc_block() ------------------------
// Allocate a BitBlock from the free list.  If the free list is empty,
// prime it.

IndexSet::BitBlock *IndexSet::alloc_block() {
#ifdef ASSERT
  if (CollectIndexSetStatistics) {
    inc_stat_counter(&_alloc_total, 1);
  }
#endif
  Compile *compile = Compile::current();
  BitBlock* free_list = (BitBlock*)compile->indexSet_free_block_list();
  if (free_list == NULL) {
    populate_free_list();
    free_list = (BitBlock*)compile->indexSet_free_block_list();
  }
  BitBlock *block = free_list;
  compile->set_indexSet_free_block_list(block->next());

  block->clear();
  return block;
}

//---------------------------- IndexSet::alloc_block_containing() -------------
// Allocate a new BitBlock and put it into the position in the _blocks array
// corresponding to element.

IndexSet::BitBlock *IndexSet::alloc_block_containing(uint element) {
  BitBlock *block = alloc_block();
  uint bi = get_block_index(element);
  _blocks[bi] = block;
  return block;
}

//---------------------------- IndexSet::free_block() -------------------------
// Add a BitBlock to the free list.

void IndexSet::free_block(uint i) {
  debug_only(check_watch("free block", i));
  assert(i < _max_blocks, "block index too large");
  BitBlock *block = _blocks[i];
  assert(block != &_empty_block, "cannot free the empty block");
  block->set_next((IndexSet::BitBlock*)Compile::current()->indexSet_free_block_list());
  Compile::current()->set_indexSet_free_block_list(block);
  set_block(i,&_empty_block);
}

//------------------------------lrg_union--------------------------------------
// Compute the union of all elements of one and two which interfere with
// the RegMask mask.  If the degree of the union becomes exceeds
// fail_degree, the union bails out.  The underlying set is cleared before
// the union is performed.

uint IndexSet::lrg_union(uint lr1, uint lr2,
                         const uint fail_degree,
                         const PhaseIFG *ifg,
                         const RegMask &mask ) {
  IndexSet *one = ifg->neighbors(lr1);
  IndexSet *two = ifg->neighbors(lr2);
  LRG &lrg1 = ifg->lrgs(lr1);
  LRG &lrg2 = ifg->lrgs(lr2);
#ifdef ASSERT
  assert(_max_elements == one->_max_elements, "max element mismatch");
  check_watch("union destination");
  one->check_watch("union source");
  two->check_watch("union source");
#endif

  // Compute the degree of the combined live-range.  The combined
  // live-range has the union of the original live-ranges' neighbors set as
  // well as the neighbors of all intermediate copies, minus those neighbors
  // that can not use the intersected allowed-register-set.

  // Copy the larger set.  Insert the smaller set into the larger.
  if (two->count() > one->count()) {
    IndexSet *temp = one;
    one = two;
    two = temp;
  }

  clear();

  // Used to compute degree of register-only interferences.  Infinite-stack
  // neighbors do not alter colorability, as they can always color to some
  // other color.  (A variant of the Briggs assertion)
  uint reg_degree = 0;

  uint element;
  // Load up the combined interference set with the neighbors of one
  IndexSetIterator elements(one);
  while ((element = elements.next()) != 0) {
    LRG &lrg = ifg->lrgs(element);
    if (mask.overlap(lrg.mask())) {
      insert(element);
      if( !lrg.mask().is_AllStack() ) {
        reg_degree += lrg1.compute_degree(lrg);
        if( reg_degree >= fail_degree ) return reg_degree;
      } else {
        // !!!!! Danger!  No update to reg_degree despite having a neighbor.
        // A variant of the Briggs assertion.
        // Not needed if I simplify during coalesce, ala George/Appel.
        assert( lrg.lo_degree(), "" );
      }
    }
  }
  // Add neighbors of two as well
  IndexSetIterator elements2(two);
  while ((element = elements2.next()) != 0) {
    LRG &lrg = ifg->lrgs(element);
    if (mask.overlap(lrg.mask())) {
      if (insert(element)) {
        if( !lrg.mask().is_AllStack() ) {
          reg_degree += lrg2.compute_degree(lrg);
          if( reg_degree >= fail_degree ) return reg_degree;
        } else {
          // !!!!! Danger!  No update to reg_degree despite having a neighbor.
          // A variant of the Briggs assertion.
          // Not needed if I simplify during coalesce, ala George/Appel.
          assert( lrg.lo_degree(), "" );
        }
      }
    }
  }

  return reg_degree;
}

//---------------------------- IndexSet() -----------------------------
// A deep copy constructor.  This is used when you need a scratch copy of this set.

IndexSet::IndexSet (IndexSet *set) {
#ifdef ASSERT
  _serial_number = _serial_count++;
  set->check_watch("copied", _serial_number);
  check_watch("initialized by copy", set->_serial_number);
  _max_elements = set->_max_elements;
#endif
  _count = set->_count;
  _max_blocks = set->_max_blocks;
  if (_max_blocks <= preallocated_block_list_size) {
    _blocks = _preallocated_block_list;
  } else {
    _blocks =
      (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
  }
  for (uint i = 0; i < _max_blocks; i++) {
    BitBlock *block = set->_blocks[i];
    if (block == &_empty_block) {
      set_block(i, &_empty_block);
    } else {
      BitBlock *new_block = alloc_block();
      memcpy(new_block->words(), block->words(), sizeof(uint32) * words_per_block);
      set_block(i, new_block);
    }
  }
}

//---------------------------- IndexSet::initialize() -----------------------------
// Prepare an IndexSet for use.

void IndexSet::initialize(uint max_elements) {
#ifdef ASSERT
  _serial_number = _serial_count++;
  check_watch("initialized", max_elements);
  _max_elements = max_elements;
#endif
  _count = 0;
  _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block;

  if (_max_blocks <= preallocated_block_list_size) {
    _blocks = _preallocated_block_list;
  } else {
    _blocks = (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
  }
  for (uint i = 0; i < _max_blocks; i++) {
    set_block(i, &_empty_block);
  }
}

//---------------------------- IndexSet::initialize()------------------------------
// Prepare an IndexSet for use.  If it needs to allocate its _blocks array, it does
// so from the Arena passed as a parameter.  BitBlock allocation is still done from
// the static Arena which was set with reset_memory().

void IndexSet::initialize(uint max_elements, Arena *arena) {
#ifdef ASSERT
  _serial_number = _serial_count++;
  check_watch("initialized2", max_elements);
  _max_elements = max_elements;
#endif // ASSERT
  _count = 0;
  _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block;

  if (_max_blocks <= preallocated_block_list_size) {
    _blocks = _preallocated_block_list;
  } else {
    _blocks = (IndexSet::BitBlock**) arena->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks);
  }
  for (uint i = 0; i < _max_blocks; i++) {
    set_block(i, &_empty_block);
  }
}

//---------------------------- IndexSet::swap() -----------------------------
// Exchange two IndexSets.

void IndexSet::swap(IndexSet *set) {
#ifdef ASSERT
  assert(_max_elements == set->_max_elements, "must have same universe size to swap");
  check_watch("swap", set->_serial_number);
  set->check_watch("swap", _serial_number);
#endif

  for (uint i = 0; i < _max_blocks; i++) {
    BitBlock *temp = _blocks[i];
    set_block(i, set->_blocks[i]);
    set->set_block(i, temp);
  }
  uint temp = _count;
  _count = set->_count;
  set->_count = temp;
}

//---------------------------- IndexSet::dump() -----------------------------
// Print this set.  Used for debugging.

#ifndef PRODUCT
void IndexSet::dump() const {
  IndexSetIterator elements(this);

  tty->print("{");
  uint i;
  while ((i = elements.next()) != 0) {
    tty->print("L%d ", i);
  }
  tty->print_cr("}");
}
#endif

#ifdef ASSERT
//---------------------------- IndexSet::tally_iteration_statistics() -----------------------------
// Update block/bit counts to reflect that this set has been iterated over.

void IndexSet::tally_iteration_statistics() const {
  inc_stat_counter(&_total_bits, count());

  for (uint i = 0; i < _max_blocks; i++) {
    if (_blocks[i] != &_empty_block) {
      inc_stat_counter(&_total_used_blocks, 1);
    } else {
      inc_stat_counter(&_total_unused_blocks, 1);
    }
  }
}

//---------------------------- IndexSet::print_statistics() -----------------------------
// Print statistics about IndexSet usage.

void IndexSet::print_statistics() {
  julong total_blocks = _total_used_blocks + _total_unused_blocks;
  tty->print_cr ("Accumulated IndexSet usage statistics:");
  tty->print_cr ("--------------------------------------");
  tty->print_cr ("  Iteration:");
  tty->print_cr ("    blocks visited: " UINT64_FORMAT, total_blocks);
  tty->print_cr ("    blocks empty: %4.2f%%", 100.0*(double)_total_unused_blocks/total_blocks);
  tty->print_cr ("    bit density (bits/used blocks): %4.2f", (double)_total_bits/_total_used_blocks);
  tty->print_cr ("    bit density (bits/all blocks): %4.2f", (double)_total_bits/total_blocks);
  tty->print_cr ("  Allocation:");
  tty->print_cr ("    blocks allocated: " UINT64_FORMAT, _alloc_new);
  tty->print_cr ("    blocks used/reused: " UINT64_FORMAT, _alloc_total);
}

//---------------------------- IndexSet::verify() -----------------------------
// Expensive test of IndexSet sanity.  Ensure that the count agrees with the
// number of bits in the blocks.  Make sure the iterator is seeing all elements
// of the set.  Meant for use during development.

void IndexSet::verify() const {
  assert(!member(0), "zero cannot be a member");
  uint count = 0;
  uint i;
  for (i = 1; i < _max_elements; i++) {
    if (member(i)) {
      count++;
      assert(count <= _count, "_count is messed up");
    }
  }

  IndexSetIterator elements(this);
  count = 0;
  while ((i = elements.next()) != 0) {
    count++;
    assert(member(i), "returned a non member");
    assert(count <= _count, "iterator returned wrong number of elements");
  }
}
#endif

//---------------------------- IndexSetIterator() -----------------------------
// Create an iterator for a set.  If empty blocks are detected when iterating
// over the set, these blocks are replaced.

IndexSetIterator::IndexSetIterator(IndexSet *set) {
#ifdef ASSERT
  if (CollectIndexSetStatistics) {
    set->tally_iteration_statistics();
  }
  set->check_watch("traversed", set->count());
#endif
  if (set->is_empty()) {
    _current = 0;
    _next_word = IndexSet::words_per_block;
    _next_block = 1;
    _max_blocks = 1;

    // We don't need the following values when we iterate over an empty set.
    // The commented out code is left here to document that the omission
    // is intentional.
    //
    //_value = 0;
    //_words = NULL;
    //_blocks = NULL;
    //_set = NULL;
  } else {
    _current = 0;
    _value = 0;
    _next_block = 0;
    _next_word = IndexSet::words_per_block;

    _max_blocks = set->_max_blocks;
    _words = NULL;
    _blocks = set->_blocks;
    _set = set;
  }
}

//---------------------------- IndexSetIterator(const) -----------------------------
// Iterate over a constant IndexSet.

IndexSetIterator::IndexSetIterator(const IndexSet *set) {
#ifdef ASSERT
  if (CollectIndexSetStatistics) {
    set->tally_iteration_statistics();
  }
  // We don't call check_watch from here to avoid bad recursion.
  //   set->check_watch("traversed const", set->count());
#endif
  if (set->is_empty()) {
    _current = 0;
    _next_word = IndexSet::words_per_block;
    _next_block = 1;
    _max_blocks = 1;

    // We don't need the following values when we iterate over an empty set.
    // The commented out code is left here to document that the omission
    // is intentional.
    //
    //_value = 0;
    //_words = NULL;
    //_blocks = NULL;
    //_set = NULL;
  } else {
    _current = 0;
    _value = 0;
    _next_block = 0;
    _next_word = IndexSet::words_per_block;

    _max_blocks = set->_max_blocks;
    _words = NULL;
    _blocks = set->_blocks;
    _set = NULL;
  }
}

//---------------------------- List16Iterator::advance_and_next() -----------------------------
// Advance to the next non-empty word in the set being iterated over.  Return the next element
// if there is one.  If we are done, return 0.  This method is called from the next() method
// when it gets done with a word.

uint IndexSetIterator::advance_and_next() {
  // See if there is another non-empty word in the current block.
  for (uint wi = _next_word; wi < (unsigned)IndexSet::words_per_block; wi++) {
    if (_words[wi] != 0) {
      // Found a non-empty word.
      _value = ((_next_block - 1) * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word);
      _current = _words[wi];

      _next_word = wi+1;

      return next();
    }
  }

  // We ran out of words in the current block.  Advance to next non-empty block.
  for (uint bi = _next_block; bi < _max_blocks; bi++) {
    if (_blocks[bi] != &IndexSet::_empty_block) {
      // Found a non-empty block.

      _words = _blocks[bi]->words();
      for (uint wi = 0; wi < (unsigned)IndexSet::words_per_block; wi++) {
        if (_words[wi] != 0) {
          // Found a non-empty word.
          _value = (bi * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word);
          _current = _words[wi];

          _next_block = bi+1;
          _next_word = wi+1;

          return next();
        }
      }

      // All of the words in the block were empty.  Replace
      // the block with the empty block.
      if (_set) {
        _set->free_block(bi);
      }
    }
  }

  // These assignments make redundant calls to next on a finished iterator
  // faster.  Probably not necessary.
  _next_block = _max_blocks;
  _next_word = IndexSet::words_per_block;

  // No more words.
  return 0;
}