indexSet.hpp revision 0:a61af66fc99e
11590Srgrimes/* 21590Srgrimes * Copyright 1998-2005 Sun Microsystems, Inc. All Rights Reserved. 31590Srgrimes * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 41590Srgrimes * 51590Srgrimes * This code is free software; you can redistribute it and/or modify it 61590Srgrimes * under the terms of the GNU General Public License version 2 only, as 71590Srgrimes * published by the Free Software Foundation. 81590Srgrimes * 91590Srgrimes * This code is distributed in the hope that it will be useful, but WITHOUT 101590Srgrimes * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 111590Srgrimes * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 121590Srgrimes * version 2 for more details (a copy is included in the LICENSE file that 131590Srgrimes * accompanied this code). 141590Srgrimes * 151590Srgrimes * You should have received a copy of the GNU General Public License version 161590Srgrimes * 2 along with this work; if not, write to the Free Software Foundation, 171590Srgrimes * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 181590Srgrimes * 191590Srgrimes * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 201590Srgrimes * CA 95054 USA or visit www.sun.com if you need additional information or 211590Srgrimes * have any questions. 221590Srgrimes * 231590Srgrimes */ 241590Srgrimes 251590Srgrimes// This file defines the IndexSet class, a set of sparse integer indices. 261590Srgrimes// This data structure is used by the compiler in its liveness analysis and 271590Srgrimes// during register allocation. 281590Srgrimes 291590Srgrimes//-------------------------------- class IndexSet ---------------------------- 301590Srgrimes// An IndexSet is a piece-wise bitvector. At the top level, we have an array 311590Srgrimes// of pointers to bitvector chunks called BitBlocks. Each BitBlock has a fixed 3226960Scharnier// size and is allocated from a shared free list. The bits which are set in 3332069Salex// each BitBlock correspond to the elements of the set. 341590Srgrimes 351590Srgrimesclass IndexSet : public ResourceObj { 361590Srgrimes friend class IndexSetIterator; 371590Srgrimes 381590Srgrimes public: 391590Srgrimes // When we allocate an IndexSet, it starts off with an array of top level block 401590Srgrimes // pointers of a set length. This size is intended to be large enough for the 411590Srgrimes // majority of IndexSets. In the cases when this size is not large enough, 421590Srgrimes // a separately allocated array is used. 4323690Speter 441590Srgrimes // The length of the preallocated top level block array 451590Srgrimes enum { preallocated_block_list_size = 16 }; 461590Srgrimes 471590Srgrimes // Elements of a IndexSet get decomposed into three fields. The highest order 4826960Scharnier // bits are the block index, which tell which high level block holds the element. 491590Srgrimes // Within that block, the word index indicates which word holds the element. 501590Srgrimes // Finally, the bit index determines which single bit within that word indicates 511590Srgrimes // membership of the element in the set. 521590Srgrimes 5323690Speter // The lengths of the index bitfields 541590Srgrimes enum { bit_index_length = 5, 551590Srgrimes word_index_length = 3, 561590Srgrimes block_index_length = 8 // not used 571590Srgrimes }; 5826960Scharnier 591590Srgrimes // Derived constants used for manipulating the index bitfields 601590Srgrimes enum { 611590Srgrimes bit_index_offset = 0, // not used 621590Srgrimes word_index_offset = bit_index_length, 631590Srgrimes block_index_offset = bit_index_length + word_index_length, 641590Srgrimes 651590Srgrimes bits_per_word = 1 << bit_index_length, 661590Srgrimes words_per_block = 1 << word_index_length, 671590Srgrimes bits_per_block = bits_per_word * words_per_block, 681590Srgrimes 6924360Simp bit_index_mask = right_n_bits(bit_index_length), 701590Srgrimes word_index_mask = right_n_bits(word_index_length) 711590Srgrimes }; 721590Srgrimes 731590Srgrimes // These routines are used for extracting the block, word, and bit index 741590Srgrimes // from an element. 751590Srgrimes static uint get_block_index(uint element) { 761590Srgrimes return element >> block_index_offset; 771590Srgrimes } 781590Srgrimes static uint get_word_index(uint element) { 791590Srgrimes return mask_bits(element >> word_index_offset,word_index_mask); 801590Srgrimes } 811590Srgrimes static uint get_bit_index(uint element) { 821590Srgrimes return mask_bits(element,bit_index_mask); 8326960Scharnier } 841590Srgrimes 851590Srgrimes //------------------------------ class BitBlock ---------------------------- 861590Srgrimes // The BitBlock class is a segment of a bitvector set. 871590Srgrimes 8826960Scharnier class BitBlock : public ResourceObj { 891590Srgrimes friend class IndexSetIterator; 901590Srgrimes friend class IndexSet; 911590Srgrimes 921590Srgrimes private: 931590Srgrimes // All of BitBlocks fields and methods are declared private. We limit 941590Srgrimes // access to IndexSet and IndexSetIterator. 951590Srgrimes 961590Srgrimes // A BitBlock is composed of some number of 32 bit words. When a BitBlock 9726960Scharnier // is not in use by any IndexSet, it is stored on a free list. The next field 981590Srgrimes // is used by IndexSet to mainting this free list. 991590Srgrimes 1001590Srgrimes union { 1011590Srgrimes uint32 _words[words_per_block]; 1021590Srgrimes BitBlock *_next; 1031590Srgrimes } _data; 1041590Srgrimes 1051590Srgrimes // accessors 1061590Srgrimes uint32 *words() { return _data._words; } 1071590Srgrimes void set_next(BitBlock *next) { _data._next = next; } 1081590Srgrimes BitBlock *next() { return _data._next; } 1091590Srgrimes 1101590Srgrimes // Operations. A BitBlock supports four simple operations, 1111590Srgrimes // clear(), member(), insert(), and remove(). These methods do 1121590Srgrimes // not assume that the block index has been masked out. 1131590Srgrimes 1141590Srgrimes void clear() { 1151590Srgrimes memset(words(), 0, sizeof(uint32) * words_per_block); 1161590Srgrimes } 1171590Srgrimes 1181590Srgrimes bool member(uint element) { 11932069Salex uint word_index = IndexSet::get_word_index(element); 1201590Srgrimes uint bit_index = IndexSet::get_bit_index(element); 1211590Srgrimes 1221590Srgrimes return ((words()[word_index] & (uint32)(0x1 << bit_index)) != 0); 1231590Srgrimes } 1241590Srgrimes 1251590Srgrimes bool insert(uint element) { 1261590Srgrimes uint word_index = IndexSet::get_word_index(element); 1271590Srgrimes uint bit_index = IndexSet::get_bit_index(element); 1281590Srgrimes 1291590Srgrimes uint32 bit = (0x1 << bit_index); 1301590Srgrimes uint32 before = words()[word_index]; 1311590Srgrimes words()[word_index] = before | bit; 13226960Scharnier return ((before & bit) != 0); 1331590Srgrimes } 1341590Srgrimes 1351590Srgrimes bool remove(uint element) { 1361590Srgrimes uint word_index = IndexSet::get_word_index(element); 1371590Srgrimes uint bit_index = IndexSet::get_bit_index(element); 1381590Srgrimes 1391590Srgrimes uint32 bit = (0x1 << bit_index); 1401590Srgrimes uint32 before = words()[word_index]; 1411590Srgrimes 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 388class 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}; 462