1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/indexSet.hpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,471 @@
1.4 +/*
1.5 + * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#ifndef SHARE_VM_OPTO_INDEXSET_HPP
1.29 +#define SHARE_VM_OPTO_INDEXSET_HPP
1.30 +
1.31 +#include "memory/allocation.hpp"
1.32 +#include "memory/resourceArea.hpp"
1.33 +#include "opto/compile.hpp"
1.34 +#include "opto/regmask.hpp"
1.35 +
1.36 +// This file defines the IndexSet class, a set of sparse integer indices.
1.37 +// This data structure is used by the compiler in its liveness analysis and
1.38 +// during register allocation.
1.39 +
1.40 +//-------------------------------- class IndexSet ----------------------------
1.41 +// An IndexSet is a piece-wise bitvector. At the top level, we have an array
1.42 +// of pointers to bitvector chunks called BitBlocks. Each BitBlock has a fixed
1.43 +// size and is allocated from a shared free list. The bits which are set in
1.44 +// each BitBlock correspond to the elements of the set.
1.45 +
1.46 +class IndexSet : public ResourceObj {
1.47 + friend class IndexSetIterator;
1.48 +
1.49 + public:
1.50 + // When we allocate an IndexSet, it starts off with an array of top level block
1.51 + // pointers of a set length. This size is intended to be large enough for the
1.52 + // majority of IndexSets. In the cases when this size is not large enough,
1.53 + // a separately allocated array is used.
1.54 +
1.55 + // The length of the preallocated top level block array
1.56 + enum { preallocated_block_list_size = 16 };
1.57 +
1.58 + // Elements of a IndexSet get decomposed into three fields. The highest order
1.59 + // bits are the block index, which tell which high level block holds the element.
1.60 + // Within that block, the word index indicates which word holds the element.
1.61 + // Finally, the bit index determines which single bit within that word indicates
1.62 + // membership of the element in the set.
1.63 +
1.64 + // The lengths of the index bitfields
1.65 + enum { bit_index_length = 5,
1.66 + word_index_length = 3,
1.67 + block_index_length = 8 // not used
1.68 + };
1.69 +
1.70 + // Derived constants used for manipulating the index bitfields
1.71 + enum {
1.72 + bit_index_offset = 0, // not used
1.73 + word_index_offset = bit_index_length,
1.74 + block_index_offset = bit_index_length + word_index_length,
1.75 +
1.76 + bits_per_word = 1 << bit_index_length,
1.77 + words_per_block = 1 << word_index_length,
1.78 + bits_per_block = bits_per_word * words_per_block,
1.79 +
1.80 + bit_index_mask = right_n_bits(bit_index_length),
1.81 + word_index_mask = right_n_bits(word_index_length)
1.82 + };
1.83 +
1.84 + // These routines are used for extracting the block, word, and bit index
1.85 + // from an element.
1.86 + static uint get_block_index(uint element) {
1.87 + return element >> block_index_offset;
1.88 + }
1.89 + static uint get_word_index(uint element) {
1.90 + return mask_bits(element >> word_index_offset,word_index_mask);
1.91 + }
1.92 + static uint get_bit_index(uint element) {
1.93 + return mask_bits(element,bit_index_mask);
1.94 + }
1.95 +
1.96 + //------------------------------ class BitBlock ----------------------------
1.97 + // The BitBlock class is a segment of a bitvector set.
1.98 +
1.99 + class BitBlock : public ResourceObj {
1.100 + friend class IndexSetIterator;
1.101 + friend class IndexSet;
1.102 +
1.103 + private:
1.104 + // All of BitBlocks fields and methods are declared private. We limit
1.105 + // access to IndexSet and IndexSetIterator.
1.106 +
1.107 + // A BitBlock is composed of some number of 32 bit words. When a BitBlock
1.108 + // is not in use by any IndexSet, it is stored on a free list. The next field
1.109 + // is used by IndexSet to mainting this free list.
1.110 +
1.111 + union {
1.112 + uint32 _words[words_per_block];
1.113 + BitBlock *_next;
1.114 + } _data;
1.115 +
1.116 + // accessors
1.117 + uint32 *words() { return _data._words; }
1.118 + void set_next(BitBlock *next) { _data._next = next; }
1.119 + BitBlock *next() { return _data._next; }
1.120 +
1.121 + // Operations. A BitBlock supports four simple operations,
1.122 + // clear(), member(), insert(), and remove(). These methods do
1.123 + // not assume that the block index has been masked out.
1.124 +
1.125 + void clear() {
1.126 + memset(words(), 0, sizeof(uint32) * words_per_block);
1.127 + }
1.128 +
1.129 + bool member(uint element) {
1.130 + uint word_index = IndexSet::get_word_index(element);
1.131 + uint bit_index = IndexSet::get_bit_index(element);
1.132 +
1.133 + return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0);
1.134 + }
1.135 +
1.136 + bool insert(uint element) {
1.137 + uint word_index = IndexSet::get_word_index(element);
1.138 + uint bit_index = IndexSet::get_bit_index(element);
1.139 +
1.140 + uint32 bit = (0x1 << bit_index);
1.141 + uint32 before = words()[word_index];
1.142 + words()[word_index] = before | bit;
1.143 + return ((before & bit) != 0);
1.144 + }
1.145 +
1.146 + bool remove(uint element) {
1.147 + uint word_index = IndexSet::get_word_index(element);
1.148 + uint bit_index = IndexSet::get_bit_index(element);
1.149 +
1.150 + uint32 bit = (0x1 << bit_index);
1.151 + uint32 before = words()[word_index];
1.152 + words()[word_index] = before & ~bit;
1.153 + return ((before & bit) != 0);
1.154 + }
1.155 + };
1.156 +
1.157 + //-------------------------- BitBlock allocation ---------------------------
1.158 + private:
1.159 +
1.160 + // All IndexSets share an arena from which they allocate BitBlocks. Unused
1.161 + // BitBlocks are placed on a free list.
1.162 +
1.163 + // The number of BitBlocks to allocate at a time
1.164 + enum { bitblock_alloc_chunk_size = 50 };
1.165 +
1.166 + static Arena *arena() { return Compile::current()->indexSet_arena(); }
1.167 +
1.168 + static void populate_free_list();
1.169 +
1.170 + public:
1.171 +
1.172 + // Invalidate the current free BitBlock list and begin allocation
1.173 + // from a new arena. It is essential that this method is called whenever
1.174 + // the Arena being used for BitBlock allocation is reset.
1.175 + static void reset_memory(Compile* compile, Arena *arena) {
1.176 + compile->set_indexSet_free_block_list(NULL);
1.177 + compile->set_indexSet_arena(arena);
1.178 +
1.179 + // This should probably be done in a static initializer
1.180 + _empty_block.clear();
1.181 + }
1.182 +
1.183 + private:
1.184 + friend class BitBlock;
1.185 + // A distinguished BitBlock which always remains empty. When a new IndexSet is
1.186 + // created, all of its top level BitBlock pointers are initialized to point to
1.187 + // this.
1.188 + static BitBlock _empty_block;
1.189 +
1.190 + //-------------------------- Members ------------------------------------------
1.191 +
1.192 + // The number of elements in the set
1.193 + uint _count;
1.194 +
1.195 + // Our top level array of bitvector segments
1.196 + BitBlock **_blocks;
1.197 +
1.198 + BitBlock *_preallocated_block_list[preallocated_block_list_size];
1.199 +
1.200 + // The number of top level array entries in use
1.201 + uint _max_blocks;
1.202 +
1.203 + // Our assertions need to know the maximum number allowed in the set
1.204 +#ifdef ASSERT
1.205 + uint _max_elements;
1.206 +#endif
1.207 +
1.208 + // The next IndexSet on the free list (not used at same time as count)
1.209 + IndexSet *_next;
1.210 +
1.211 + public:
1.212 + //-------------------------- Free list operations ------------------------------
1.213 + // Individual IndexSets can be placed on a free list. This is done in PhaseLive.
1.214 +
1.215 + IndexSet *next() {
1.216 +#ifdef ASSERT
1.217 + if( VerifyOpto ) {
1.218 + check_watch("removed from free list?", ((_next == NULL) ? 0 : _next->_serial_number));
1.219 + }
1.220 +#endif
1.221 + return _next;
1.222 + }
1.223 +
1.224 + void set_next(IndexSet *next) {
1.225 +#ifdef ASSERT
1.226 + if( VerifyOpto ) {
1.227 + check_watch("put on free list?", ((next == NULL) ? 0 : next->_serial_number));
1.228 + }
1.229 +#endif
1.230 + _next = next;
1.231 + }
1.232 +
1.233 + private:
1.234 + //-------------------------- Utility methods -----------------------------------
1.235 +
1.236 + // Get the block which holds element
1.237 + BitBlock *get_block_containing(uint element) const {
1.238 + assert(element < _max_elements, "element out of bounds");
1.239 + return _blocks[get_block_index(element)];
1.240 + }
1.241 +
1.242 + // Set a block in the top level array
1.243 + void set_block(uint index, BitBlock *block) {
1.244 +#ifdef ASSERT
1.245 + if( VerifyOpto )
1.246 + check_watch("set block", index);
1.247 +#endif
1.248 + _blocks[index] = block;
1.249 + }
1.250 +
1.251 + // Get a BitBlock from the free list
1.252 + BitBlock *alloc_block();
1.253 +
1.254 + // Get a BitBlock from the free list and place it in the top level array
1.255 + BitBlock *alloc_block_containing(uint element);
1.256 +
1.257 + // Free a block from the top level array, placing it on the free BitBlock list
1.258 + void free_block(uint i);
1.259 +
1.260 + public:
1.261 + //-------------------------- Primitive set operations --------------------------
1.262 +
1.263 + void clear() {
1.264 +#ifdef ASSERT
1.265 + if( VerifyOpto )
1.266 + check_watch("clear");
1.267 +#endif
1.268 + _count = 0;
1.269 + for (uint i = 0; i < _max_blocks; i++) {
1.270 + BitBlock *block = _blocks[i];
1.271 + if (block != &_empty_block) {
1.272 + free_block(i);
1.273 + }
1.274 + }
1.275 + }
1.276 +
1.277 + uint count() const { return _count; }
1.278 +
1.279 + bool is_empty() const { return _count == 0; }
1.280 +
1.281 + bool member(uint element) const {
1.282 + return get_block_containing(element)->member(element);
1.283 + }
1.284 +
1.285 + bool insert(uint element) {
1.286 +#ifdef ASSERT
1.287 + if( VerifyOpto )
1.288 + check_watch("insert", element);
1.289 +#endif
1.290 + if (element == 0) {
1.291 + return 0;
1.292 + }
1.293 + BitBlock *block = get_block_containing(element);
1.294 + if (block == &_empty_block) {
1.295 + block = alloc_block_containing(element);
1.296 + }
1.297 + bool present = block->insert(element);
1.298 + if (!present) {
1.299 + _count++;
1.300 + }
1.301 + return !present;
1.302 + }
1.303 +
1.304 + bool remove(uint element) {
1.305 +#ifdef ASSERT
1.306 + if( VerifyOpto )
1.307 + check_watch("remove", element);
1.308 +#endif
1.309 +
1.310 + BitBlock *block = get_block_containing(element);
1.311 + bool present = block->remove(element);
1.312 + if (present) {
1.313 + _count--;
1.314 + }
1.315 + return present;
1.316 + }
1.317 +
1.318 + //-------------------------- Compound set operations ------------------------
1.319 + // Compute the union of all elements of one and two which interfere
1.320 + // with the RegMask mask. If the degree of the union becomes
1.321 + // exceeds fail_degree, the union bails out. The underlying set is
1.322 + // cleared before the union is performed.
1.323 + uint lrg_union(uint lr1, uint lr2,
1.324 + const uint fail_degree,
1.325 + const class PhaseIFG *ifg,
1.326 + const RegMask &mask);
1.327 +
1.328 +
1.329 + //------------------------- Construction, initialization -----------------------
1.330 +
1.331 + IndexSet() {}
1.332 +
1.333 + // This constructor is used for making a deep copy of a IndexSet.
1.334 + IndexSet(IndexSet *set);
1.335 +
1.336 + // Perform initialization on a IndexSet
1.337 + void initialize(uint max_element);
1.338 +
1.339 + // Initialize a IndexSet. If the top level BitBlock array needs to be
1.340 + // allocated, do it from the proffered arena. BitBlocks are still allocated
1.341 + // from the static Arena member.
1.342 + void initialize(uint max_element, Arena *arena);
1.343 +
1.344 + // Exchange two sets
1.345 + void swap(IndexSet *set);
1.346 +
1.347 + //-------------------------- Debugging and statistics --------------------------
1.348 +
1.349 +#ifndef PRODUCT
1.350 + // Output a IndexSet for debugging
1.351 + void dump() const;
1.352 +#endif
1.353 +
1.354 +#ifdef ASSERT
1.355 + void tally_iteration_statistics() const;
1.356 +
1.357 + // BitBlock allocation statistics
1.358 + static julong _alloc_new;
1.359 + static julong _alloc_total;
1.360 +
1.361 + // Block density statistics
1.362 + static julong _total_bits;
1.363 + static julong _total_used_blocks;
1.364 + static julong _total_unused_blocks;
1.365 +
1.366 + // Sanity tests
1.367 + void verify() const;
1.368 +
1.369 + static int _serial_count;
1.370 + int _serial_number;
1.371 +
1.372 + // Check to see if the serial number of the current set is the one we're tracing.
1.373 + // If it is, print a message.
1.374 + void check_watch(const char *operation, uint operand) const {
1.375 + if (IndexSetWatch != 0) {
1.376 + if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
1.377 + tty->print_cr("IndexSet %d : %s ( %d )", _serial_number, operation, operand);
1.378 + }
1.379 + }
1.380 + }
1.381 + void check_watch(const char *operation) const {
1.382 + if (IndexSetWatch != 0) {
1.383 + if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
1.384 + tty->print_cr("IndexSet %d : %s", _serial_number, operation);
1.385 + }
1.386 + }
1.387 + }
1.388 +
1.389 + public:
1.390 + static void print_statistics();
1.391 +
1.392 +#endif
1.393 +};
1.394 +
1.395 +
1.396 +//-------------------------------- class IndexSetIterator --------------------
1.397 +// An iterator for IndexSets.
1.398 +
1.399 +class IndexSetIterator VALUE_OBJ_CLASS_SPEC {
1.400 + friend class IndexSet;
1.401 +
1.402 + public:
1.403 +
1.404 + // We walk over the bits in a word in chunks of size window_size.
1.405 + enum { window_size = 5,
1.406 + window_mask = right_n_bits(window_size),
1.407 + table_size = (1 << window_size) };
1.408 +
1.409 + // For an integer of length window_size, what is the first set bit?
1.410 + static const byte _first_bit[table_size];
1.411 +
1.412 + // For an integer of length window_size, what is the second set bit?
1.413 + static const byte _second_bit[table_size];
1.414 +
1.415 + private:
1.416 + // The current word we are inspecting
1.417 + uint32 _current;
1.418 +
1.419 + // What element number are we currently on?
1.420 + uint _value;
1.421 +
1.422 + // The index of the next word we will inspect
1.423 + uint _next_word;
1.424 +
1.425 + // A pointer to the contents of the current block
1.426 + uint32 *_words;
1.427 +
1.428 + // The index of the next block we will inspect
1.429 + uint _next_block;
1.430 +
1.431 + // A pointer to the blocks in our set
1.432 + IndexSet::BitBlock **_blocks;
1.433 +
1.434 + // The number of blocks in the set
1.435 + uint _max_blocks;
1.436 +
1.437 + // If the iterator was created from a non-const set, we replace
1.438 + // non-canonical empty blocks with the _empty_block pointer. If
1.439 + // _set is NULL, we do no replacement.
1.440 + IndexSet *_set;
1.441 +
1.442 + // Advance to the next non-empty word and return the next
1.443 + // element in the set.
1.444 + uint advance_and_next();
1.445 +
1.446 +
1.447 + public:
1.448 +
1.449 + // If an iterator is built from a constant set then empty blocks
1.450 + // are not canonicalized.
1.451 + IndexSetIterator(IndexSet *set);
1.452 + IndexSetIterator(const IndexSet *set);
1.453 +
1.454 + // Return the next element of the set. Return 0 when done.
1.455 + uint next() {
1.456 + uint current = _current;
1.457 + if (current != 0) {
1.458 + uint value = _value;
1.459 + while (mask_bits(current,window_mask) == 0) {
1.460 + current >>= window_size;
1.461 + value += window_size;
1.462 + }
1.463 +
1.464 + uint advance = _second_bit[mask_bits(current,window_mask)];
1.465 + _current = current >> advance;
1.466 + _value = value + advance;
1.467 + return value + _first_bit[mask_bits(current,window_mask)];
1.468 + } else {
1.469 + return advance_and_next();
1.470 + }
1.471 + }
1.472 +};
1.473 +
1.474 +#endif // SHARE_VM_OPTO_INDEXSET_HPP
