1 /*

     2  * Copyright 1998-2005 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    20  * CA 95054 USA or visit www.sun.com if you need additional information or

    21  * have any questions.

    22  *

    23  */

    24 

    25 // This file defines the IndexSet class, a set of sparse integer indices.

    26 // This data structure is used by the compiler in its liveness analysis and

    27 // during register allocation.

    28 

    29 //-------------------------------- class IndexSet ----------------------------

    30 // An IndexSet is a piece-wise bitvector.  At the top level, we have an array

    31 // of pointers to bitvector chunks called BitBlocks.  Each BitBlock has a fixed

    32 // size and is allocated from a shared free list.  The bits which are set in

    33 // each BitBlock correspond to the elements of the set.

    34 

    35 class IndexSet : public ResourceObj {

    36  friend class IndexSetIterator;

    37 

    38  public:

    39   // When we allocate an IndexSet, it starts off with an array of top level block

    40   // pointers of a set length.  This size is intended to be large enough for the

    41   // majority of IndexSets.  In the cases when this size is not large enough,

    42   // a separately allocated array is used.

    43 

    44   // The length of the preallocated top level block array

    45   enum { preallocated_block_list_size = 16 };

    46 

    47   // Elements of a IndexSet get decomposed into three fields.  The highest order

    48   // bits are the block index, which tell which high level block holds the element.

    49   // Within that block, the word index indicates which word holds the element.

    50   // Finally, the bit index determines which single bit within that word indicates

    51   // membership of the element in the set.

    52 

    53   // The lengths of the index bitfields

    54   enum { bit_index_length = 5,

    55          word_index_length = 3,

    56          block_index_length = 8 // not used

    57   };

    58 

    59   // Derived constants used for manipulating the index bitfields

    60   enum {

    61          bit_index_offset = 0, // not used

    62          word_index_offset = bit_index_length,

    63          block_index_offset = bit_index_length + word_index_length,

    64 

    65          bits_per_word = 1 << bit_index_length,

    66          words_per_block = 1 << word_index_length,

    67          bits_per_block = bits_per_word * words_per_block,

    68 

    69          bit_index_mask = right_n_bits(bit_index_length),

    70          word_index_mask = right_n_bits(word_index_length)

    71   };

    72 

    73   // These routines are used for extracting the block, word, and bit index

    74   // from an element.

    75   static uint get_block_index(uint element) {

    76     return element >> block_index_offset;

    77   }

    78   static uint get_word_index(uint element) {

    79     return mask_bits(element >> word_index_offset,word_index_mask);

    80   }

    81   static uint get_bit_index(uint element) {

    82     return mask_bits(element,bit_index_mask);

    83   }

    84 

    85   //------------------------------ class BitBlock ----------------------------

    86   // The BitBlock class is a segment of a bitvector set.

    87 

    88   class BitBlock : public ResourceObj {

    89    friend class IndexSetIterator;

    90    friend class IndexSet;

    91 

    92    private:

    93     // All of BitBlocks fields and methods are declared private.  We limit

    94     // access to IndexSet and IndexSetIterator.

    95 

    96     // A BitBlock is composed of some number of 32 bit words.  When a BitBlock

    97     // is not in use by any IndexSet, it is stored on a free list.  The next field

    98     // is used by IndexSet to mainting this free list.

    99 

   100     union {

   101       uint32 _words[words_per_block];

   102       BitBlock *_next;

   103     } _data;

   104 

   105     // accessors

   106     uint32 *words() { return _data._words; }

   107     void set_next(BitBlock *next) { _data._next = next; }

   108     BitBlock *next() { return _data._next; }

   109 

   110     // Operations.  A BitBlock supports four simple operations,

   111     // clear(), member(), insert(), and remove().  These methods do

   112     // not assume that the block index has been masked out.

   113 

   114     void clear() {

   115       memset(words(), 0, sizeof(uint32) * words_per_block);

   116     }

   117 

   118     bool member(uint element) {

   119       uint word_index = IndexSet::get_word_index(element);

   120       uint bit_index = IndexSet::get_bit_index(element);

   121 

   122       return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0);

   123     }

   124 

   125     bool insert(uint element) {

   126       uint word_index = IndexSet::get_word_index(element);

   127       uint bit_index = IndexSet::get_bit_index(element);

   128 

   129       uint32 bit = (0x1 << bit_index);

   130       uint32 before = words()[word_index];

   131       words()[word_index] = before | bit;

   132       return ((before & bit) != 0);

   133     }

   134 

   135     bool remove(uint element) {

   136       uint word_index = IndexSet::get_word_index(element);

   137       uint bit_index = IndexSet::get_bit_index(element);

   138 

   139       uint32 bit = (0x1 << bit_index);

   140       uint32 before = words()[word_index];

   141       words()[word_index] = before & ~bit;

   142       return ((before & bit) != 0);

   143     }

   144   };

   145 

   146   //-------------------------- BitBlock allocation ---------------------------

   147  private:

   148 

   149   // All IndexSets share an arena from which they allocate BitBlocks.  Unused

   150   // BitBlocks are placed on a free list.

   151 

   152   // The number of BitBlocks to allocate at a time

   153   enum { bitblock_alloc_chunk_size = 50 };

   154 

   155   static Arena *arena() { return Compile::current()->indexSet_arena(); }

   156 

   157   static void populate_free_list();

   158 

   159  public:

   160 

   161   // Invalidate the current free BitBlock list and begin allocation

   162   // from a new arena.  It is essential that this method is called whenever

   163   // the Arena being used for BitBlock allocation is reset.

   164   static void reset_memory(Compile* compile, Arena *arena) {

   165     compile->set_indexSet_free_block_list(NULL);

   166     compile->set_indexSet_arena(arena);

   167 

   168    // This should probably be done in a static initializer

   169    _empty_block.clear();

   170   }

   171 

   172  private:

   173   friend class BitBlock;

   174   // A distinguished BitBlock which always remains empty.  When a new IndexSet is

   175   // created, all of its top level BitBlock pointers are initialized to point to

   176   // this.

   177   static BitBlock _empty_block;

   178 

   179   //-------------------------- Members ------------------------------------------

   180 

   181   // The number of elements in the set

   182   uint      _count;

   183 

   184   // Our top level array of bitvector segments

   185   BitBlock **_blocks;

   186 

   187   BitBlock  *_preallocated_block_list[preallocated_block_list_size];

   188 

   189   // The number of top level array entries in use

   190   uint       _max_blocks;

   191 

   192   // Our assertions need to know the maximum number allowed in the set

   193 #ifdef ASSERT

   194   uint       _max_elements;

   195 #endif

   196 

   197   // The next IndexSet on the free list (not used at same time as count)

   198   IndexSet *_next;

   199 

   200  public:

   201   //-------------------------- Free list operations ------------------------------

   202   // Individual IndexSets can be placed on a free list.  This is done in PhaseLive.

   203 

   204   IndexSet *next() {

   205 #ifdef ASSERT

   206     if( VerifyOpto ) {

   207       check_watch("removed from free list?", ((_next == NULL) ? 0 : _next->_serial_number));

   208     }

   209 #endif

   210     return _next;

   211   }

   212 

   213   void set_next(IndexSet *next) {

   214 #ifdef ASSERT

   215     if( VerifyOpto ) {

   216       check_watch("put on free list?", ((next == NULL) ? 0 : next->_serial_number));

   217     }

   218 #endif

   219     _next = next;

   220   }

   221 

   222  private:

   223   //-------------------------- Utility methods -----------------------------------

   224 

   225   // Get the block which holds element

   226   BitBlock *get_block_containing(uint element) const {

   227     assert(element < _max_elements, "element out of bounds");

   228     return _blocks[get_block_index(element)];

   229   }

   230 

   231   // Set a block in the top level array

   232   void set_block(uint index, BitBlock *block) {

   233 #ifdef ASSERT

   234     if( VerifyOpto )

   235       check_watch("set block", index);

   236 #endif

   237     _blocks[index] = block;

   238   }

   239 

   240   // Get a BitBlock from the free list

   241   BitBlock *alloc_block();

   242 

   243   // Get a BitBlock from the free list and place it in the top level array

   244   BitBlock *alloc_block_containing(uint element);

   245 

   246   // Free a block from the top level array, placing it on the free BitBlock list

   247   void free_block(uint i);

   248 

   249  public:

   250   //-------------------------- Primitive set operations --------------------------

   251 

   252   void clear() {

   253 #ifdef ASSERT

   254     if( VerifyOpto )

   255       check_watch("clear");

   256 #endif

   257     _count = 0;

   258     for (uint i = 0; i < _max_blocks; i++) {

   259       BitBlock *block = _blocks[i];

   260       if (block != &_empty_block) {

   261         free_block(i);

   262       }

   263     }

   264   }

   265 

   266   uint count() const { return _count; }

   267 

   268   bool is_empty() const { return _count == 0; }

   269 

   270   bool member(uint element) const {

   271     return get_block_containing(element)->member(element);

   272   }

   273 

   274   bool insert(uint element) {

   275 #ifdef ASSERT

   276     if( VerifyOpto )

   277       check_watch("insert", element);

   278 #endif

   279     if (element == 0) {

   280       return 0;

   281     }

   282     BitBlock *block = get_block_containing(element);

   283     if (block == &_empty_block) {

   284       block = alloc_block_containing(element);

   285     }

   286     bool present = block->insert(element);

   287     if (!present) {

   288       _count++;

   289     }

   290     return !present;

   291   }

   292 

   293   bool remove(uint element) {

   294 #ifdef ASSERT

   295     if( VerifyOpto )

   296       check_watch("remove", element);

   297 #endif

   298 

   299     BitBlock *block = get_block_containing(element);

   300     bool present = block->remove(element);

   301     if (present) {

   302       _count--;

   303     }

   304     return present;

   305   }

   306 

   307   //-------------------------- Compound set operations ------------------------

   308   // Compute the union of all elements of one and two which interfere

   309   // with the RegMask mask.  If the degree of the union becomes

   310   // exceeds fail_degree, the union bails out.  The underlying set is

   311   // cleared before the union is performed.

   312   uint lrg_union(uint lr1, uint lr2,

   313                  const uint fail_degree,

   314                  const class PhaseIFG *ifg,

   315                  const RegMask &mask);

   316 

   317 

   318   //------------------------- Construction, initialization -----------------------

   319 

   320   IndexSet() {}

   321 

   322   // This constructor is used for making a deep copy of a IndexSet.

   323   IndexSet(IndexSet *set);

   324 

   325   // Perform initialization on a IndexSet

   326   void initialize(uint max_element);

   327 

   328   // Initialize a IndexSet.  If the top level BitBlock array needs to be

   329   // allocated, do it from the proffered arena.  BitBlocks are still allocated

   330   // from the static Arena member.

   331   void initialize(uint max_element, Arena *arena);

   332 

   333   // Exchange two sets

   334   void swap(IndexSet *set);

   335 

   336   //-------------------------- Debugging and statistics --------------------------

   337 

   338 #ifndef PRODUCT

   339   // Output a IndexSet for debugging

   340   void dump() const;

   341 #endif

   342 

   343 #ifdef ASSERT

   344   void tally_iteration_statistics() const;

   345 

   346   // BitBlock allocation statistics

   347   static uint _alloc_new;

   348   static uint _alloc_total;

   349 

   350   // Block density statistics

   351   static long _total_bits;

   352   static long _total_used_blocks;

   353   static long _total_unused_blocks;

   354 

   355   // Sanity tests

   356   void verify() const;

   357 

   358   static int _serial_count;

   359   int        _serial_number;

   360 

   361   // Check to see if the serial number of the current set is the one we're tracing.

   362   // If it is, print a message.

   363   void check_watch(const char *operation, uint operand) const {

   364     if (IndexSetWatch != 0) {

   365       if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {

   366         tty->print_cr("IndexSet %d : %s ( %d )", _serial_number, operation, operand);

   367       }

   368     }

   369   }

   370   void check_watch(const char *operation) const {

   371     if (IndexSetWatch != 0) {

   372       if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {

   373         tty->print_cr("IndexSet %d : %s", _serial_number, operation);

   374       }

   375     }

   376   }

   377 

   378  public:

   379   static void print_statistics();

   380 

   381 #endif

   382 };

   383 

   384 

   385 //-------------------------------- class IndexSetIterator --------------------

   386 // An iterator for IndexSets.

   387 

   388 class IndexSetIterator VALUE_OBJ_CLASS_SPEC {

   389  friend class IndexSet;

   390 

   391  public:

   392 

   393   // We walk over the bits in a word in chunks of size window_size.

   394   enum { window_size = 5,

   395          window_mask = right_n_bits(window_size),

   396          table_size  = (1 << window_size) };

   397 

   398   // For an integer of length window_size, what is the first set bit?

   399   static const byte _first_bit[table_size];

   400 

   401   // For an integer of length window_size, what is the second set bit?

   402   static const byte _second_bit[table_size];

   403 

   404  private:

   405   // The current word we are inspecting

   406   uint32                _current;

   407 

   408   // What element number are we currently on?

   409   uint                  _value;

   410 

   411   // The index of the next word we will inspect

   412   uint                  _next_word;

   413 

   414   // A pointer to the contents of the current block

   415   uint32               *_words;

   416 

   417   // The index of the next block we will inspect

   418   uint                  _next_block;

   419 

   420   // A pointer to the blocks in our set

   421   IndexSet::BitBlock **_blocks;

   422 

   423   // The number of blocks in the set

   424   uint                  _max_blocks;

   425 

   426   // If the iterator was created from a non-const set, we replace

   427   // non-canonical empty blocks with the _empty_block pointer.  If

   428   // _set is NULL, we do no replacement.

   429   IndexSet            *_set;

   430 

   431   // Advance to the next non-empty word and return the next

   432   // element in the set.

   433   uint advance_and_next();

   434 

   435 

   436  public:

   437 

   438   // If an iterator is built from a constant set then empty blocks

   439   // are not canonicalized.

   440   IndexSetIterator(IndexSet *set);

   441   IndexSetIterator(const IndexSet *set);

   442 

   443   // Return the next element of the set.  Return 0 when done.

   444   uint next() {

   445     uint current = _current;

   446     if (current != 0) {

   447       uint value = _value;

   448       while (mask_bits(current,window_mask) == 0) {

   449         current >>= window_size;

   450         value += window_size;

   451       }

   452 

   453       uint advance = _second_bit[mask_bits(current,window_mask)];

   454       _current = current >> advance;

   455       _value = value + advance;

   456       return value + _first_bit[mask_bits(current,window_mask)];

   457     } else {

   458       return advance_and_next();

   459     }

   460   }

   461 };