2122N/A * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 0N/A * published by the Free Software Foundation. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 0N/A// This file defines the IndexSet class, a set of sparse integer indices. 0N/A// This data structure is used by the compiler in its liveness analysis and 0N/A// during register allocation. 0N/A//-------------------------------- class IndexSet ---------------------------- 0N/A// An IndexSet is a piece-wise bitvector. At the top level, we have an array 0N/A// of pointers to bitvector chunks called BitBlocks. Each BitBlock has a fixed 0N/A// size and is allocated from a shared free list. The bits which are set in 0N/A// each BitBlock correspond to the elements of the set. 0N/A // When we allocate an IndexSet, it starts off with an array of top level block 0N/A // pointers of a set length. This size is intended to be large enough for the 0N/A // majority of IndexSets. In the cases when this size is not large enough, 0N/A // a separately allocated array is used. 0N/A // The length of the preallocated top level block array 0N/A // Elements of a IndexSet get decomposed into three fields. The highest order 0N/A // bits are the block index, which tell which high level block holds the element. 0N/A // Within that block, the word index indicates which word holds the element. 0N/A // Finally, the bit index determines which single bit within that word indicates 0N/A // membership of the element in the set. 0N/A // The lengths of the index bitfields 0N/A // Derived constants used for manipulating the index bitfields 0N/A // These routines are used for extracting the block, word, and bit index 0N/A //------------------------------ class BitBlock ---------------------------- 0N/A // The BitBlock class is a segment of a bitvector set. 0N/A // All of BitBlocks fields and methods are declared private. We limit 0N/A // access to IndexSet and IndexSetIterator. 0N/A // A BitBlock is composed of some number of 32 bit words. When a BitBlock 0N/A // is not in use by any IndexSet, it is stored on a free list. The next field 0N/A // is used by IndexSet to mainting this free list. 0N/A // Operations. A BitBlock supports four simple operations, 0N/A // clear(), member(), insert(), and remove(). These methods do 0N/A // not assume that the block index has been masked out. 0N/A //-------------------------- BitBlock allocation --------------------------- 0N/A // All IndexSets share an arena from which they allocate BitBlocks. Unused 0N/A // BitBlocks are placed on a free list. 0N/A // The number of BitBlocks to allocate at a time 0N/A // Invalidate the current free BitBlock list and begin allocation 0N/A // from a new arena. It is essential that this method is called whenever 0N/A // the Arena being used for BitBlock allocation is reset. 0N/A // This should probably be done in a static initializer 0N/A // A distinguished BitBlock which always remains empty. When a new IndexSet is 0N/A // created, all of its top level BitBlock pointers are initialized to point to 0N/A //-------------------------- Members ------------------------------------------ 0N/A // The number of elements in the set 0N/A // Our top level array of bitvector segments 0N/A // The number of top level array entries in use 0N/A // Our assertions need to know the maximum number allowed in the set 0N/A // The next IndexSet on the free list (not used at same time as count) 0N/A //-------------------------- Free list operations ------------------------------ 0N/A // Individual IndexSets can be placed on a free list. This is done in PhaseLive. 0N/A //-------------------------- Utility methods ----------------------------------- 0N/A // Get the block which holds element 0N/A // Set a block in the top level array 0N/A // Get a BitBlock from the free list 0N/A // Get a BitBlock from the free list and place it in the top level array 0N/A // Free a block from the top level array, placing it on the free BitBlock list 0N/A //-------------------------- Primitive set operations -------------------------- 0N/A //-------------------------- Compound set operations ------------------------ 0N/A // Compute the union of all elements of one and two which interfere 0N/A // with the RegMask mask. If the degree of the union becomes 0N/A // exceeds fail_degree, the union bails out. The underlying set is 0N/A // cleared before the union is performed. 0N/A //------------------------- Construction, initialization ----------------------- 0N/A // This constructor is used for making a deep copy of a IndexSet. 0N/A // Perform initialization on a IndexSet 0N/A // Initialize a IndexSet. If the top level BitBlock array needs to be 0N/A // allocated, do it from the proffered arena. BitBlocks are still allocated 0N/A // from the static Arena member. 0N/A // Exchange two sets 0N/A //-------------------------- Debugging and statistics -------------------------- 0N/A // Output a IndexSet for debugging 0N/A // BitBlock allocation statistics 0N/A // Block density statistics 0N/A // Check to see if the serial number of the current set is the one we're tracing. 0N/A // If it is, print a message. 0N/A//-------------------------------- class IndexSetIterator -------------------- 0N/A// An iterator for IndexSets. 0N/A // We walk over the bits in a word in chunks of size window_size. 0N/A // For an integer of length window_size, what is the first set bit? 0N/A // For an integer of length window_size, what is the second set bit? 0N/A // The current word we are inspecting 0N/A // What element number are we currently on? 0N/A // The index of the next word we will inspect 0N/A // A pointer to the contents of the current block 0N/A // The index of the next block we will inspect 0N/A // A pointer to the blocks in our set 0N/A // The number of blocks in the set 0N/A // If the iterator was created from a non-const set, we replace 0N/A // non-canonical empty blocks with the _empty_block pointer. If 0N/A // _set is NULL, we do no replacement. 0N/A // Advance to the next non-empty word and return the next 0N/A // element in the set. 0N/A // If an iterator is built from a constant set then empty blocks 0N/A // are not canonicalized. 0N/A // Return the next element of the set. Return 0 when done. 1879N/A#
endif // SHARE_VM_OPTO_INDEXSET_HPP