indexSet.cpp revision 1472:c18cbe5936b8
1/* 2 * Copyright (c) 1998, 2004, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * 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. It also defines an iterator for this class. 28 29#include "incls/_precompiled.incl" 30#include "incls/_indexSet.cpp.incl" 31 32//-------------------------------- Initializations ------------------------------ 33 34IndexSet::BitBlock IndexSet::_empty_block = IndexSet::BitBlock(); 35 36#ifdef ASSERT 37// Initialize statistics counters 38uint IndexSet::_alloc_new = 0; 39uint IndexSet::_alloc_total = 0; 40 41long IndexSet::_total_bits = 0; 42long IndexSet::_total_used_blocks = 0; 43long IndexSet::_total_unused_blocks = 0; 44 45// Per set, or all sets operation tracing 46int IndexSet::_serial_count = 1; 47#endif 48 49// What is the first set bit in a 5 bit integer? 50const byte IndexSetIterator::_first_bit[32] = { 51 0, 0, 1, 0, 52 2, 0, 1, 0, 53 3, 0, 1, 0, 54 2, 0, 1, 0, 55 4, 0, 1, 0, 56 2, 0, 1, 0, 57 3, 0, 1, 0, 58 2, 0, 1, 0 59}; 60 61// What is the second set bit in a 5 bit integer? 62const byte IndexSetIterator::_second_bit[32] = { 63 5, 5, 5, 1, 64 5, 2, 2, 1, 65 5, 3, 3, 1, 66 3, 2, 2, 1, 67 5, 4, 4, 1, 68 4, 2, 2, 1, 69 4, 3, 3, 1, 70 3, 2, 2, 1 71}; 72 73// I tried implementing the IndexSetIterator with a window_size of 8 and 74// didn't seem to get a noticeable speedup. I am leaving in the tables 75// in case we want to switch back. 76 77/*const byte IndexSetIterator::_first_bit[256] = { 78 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 79 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 80 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 81 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 82 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 83 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 84 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 85 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 86 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 87 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 88 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 89 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 90 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 91 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 92 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 93 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 94}; 95 96const byte IndexSetIterator::_second_bit[256] = { 97 8, 8, 8, 1, 8, 2, 2, 1, 8, 3, 3, 1, 3, 2, 2, 1, 98 8, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 99 8, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 100 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 101 8, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 102 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 103 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 104 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 105 8, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1, 106 7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 107 7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 108 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 109 7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 110 6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 111 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 112 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1 113};*/ 114 115//---------------------------- IndexSet::populate_free_list() ----------------------------- 116// Populate the free BitBlock list with a batch of BitBlocks. The BitBlocks 117// are 32 bit aligned. 118 119void IndexSet::populate_free_list() { 120 Compile *compile = Compile::current(); 121 BitBlock *free = (BitBlock*)compile->indexSet_free_block_list(); 122 123 char *mem = (char*)arena()->Amalloc_4(sizeof(BitBlock) * 124 bitblock_alloc_chunk_size + 32); 125 126 // Align the pointer to a 32 bit boundary. 127 BitBlock *new_blocks = (BitBlock*)(((uintptr_t)mem + 32) & ~0x001F); 128 129 // Add the new blocks to the free list. 130 for (int i = 0; i < bitblock_alloc_chunk_size; i++) { 131 new_blocks->set_next(free); 132 free = new_blocks; 133 new_blocks++; 134 } 135 136 compile->set_indexSet_free_block_list(free); 137 138#ifdef ASSERT 139 if (CollectIndexSetStatistics) { 140 _alloc_new += bitblock_alloc_chunk_size; 141 } 142#endif 143} 144 145 146//---------------------------- IndexSet::alloc_block() ------------------------ 147// Allocate a BitBlock from the free list. If the free list is empty, 148// prime it. 149 150IndexSet::BitBlock *IndexSet::alloc_block() { 151#ifdef ASSERT 152 if (CollectIndexSetStatistics) { 153 _alloc_total++; 154 } 155#endif 156 Compile *compile = Compile::current(); 157 BitBlock* free_list = (BitBlock*)compile->indexSet_free_block_list(); 158 if (free_list == NULL) { 159 populate_free_list(); 160 free_list = (BitBlock*)compile->indexSet_free_block_list(); 161 } 162 BitBlock *block = free_list; 163 compile->set_indexSet_free_block_list(block->next()); 164 165 block->clear(); 166 return block; 167} 168 169//---------------------------- IndexSet::alloc_block_containing() ------------- 170// Allocate a new BitBlock and put it into the position in the _blocks array 171// corresponding to element. 172 173IndexSet::BitBlock *IndexSet::alloc_block_containing(uint element) { 174 BitBlock *block = alloc_block(); 175 uint bi = get_block_index(element); 176 _blocks[bi] = block; 177 return block; 178} 179 180//---------------------------- IndexSet::free_block() ------------------------- 181// Add a BitBlock to the free list. 182 183void IndexSet::free_block(uint i) { 184 debug_only(check_watch("free block", i)); 185 assert(i < _max_blocks, "block index too large"); 186 BitBlock *block = _blocks[i]; 187 assert(block != &_empty_block, "cannot free the empty block"); 188 block->set_next((IndexSet::BitBlock*)Compile::current()->indexSet_free_block_list()); 189 Compile::current()->set_indexSet_free_block_list(block); 190 set_block(i,&_empty_block); 191} 192 193//------------------------------lrg_union-------------------------------------- 194// Compute the union of all elements of one and two which interfere with 195// the RegMask mask. If the degree of the union becomes exceeds 196// fail_degree, the union bails out. The underlying set is cleared before 197// the union is performed. 198 199uint IndexSet::lrg_union(uint lr1, uint lr2, 200 const uint fail_degree, 201 const PhaseIFG *ifg, 202 const RegMask &mask ) { 203 IndexSet *one = ifg->neighbors(lr1); 204 IndexSet *two = ifg->neighbors(lr2); 205 LRG &lrg1 = ifg->lrgs(lr1); 206 LRG &lrg2 = ifg->lrgs(lr2); 207#ifdef ASSERT 208 assert(_max_elements == one->_max_elements, "max element mismatch"); 209 check_watch("union destination"); 210 one->check_watch("union source"); 211 two->check_watch("union source"); 212#endif 213 214 // Compute the degree of the combined live-range. The combined 215 // live-range has the union of the original live-ranges' neighbors set as 216 // well as the neighbors of all intermediate copies, minus those neighbors 217 // that can not use the intersected allowed-register-set. 218 219 // Copy the larger set. Insert the smaller set into the larger. 220 if (two->count() > one->count()) { 221 IndexSet *temp = one; 222 one = two; 223 two = temp; 224 } 225 226 clear(); 227 228 // Used to compute degree of register-only interferences. Infinite-stack 229 // neighbors do not alter colorability, as they can always color to some 230 // other color. (A variant of the Briggs assertion) 231 uint reg_degree = 0; 232 233 uint element; 234 // Load up the combined interference set with the neighbors of one 235 IndexSetIterator elements(one); 236 while ((element = elements.next()) != 0) { 237 LRG &lrg = ifg->lrgs(element); 238 if (mask.overlap(lrg.mask())) { 239 insert(element); 240 if( !lrg.mask().is_AllStack() ) { 241 reg_degree += lrg1.compute_degree(lrg); 242 if( reg_degree >= fail_degree ) return reg_degree; 243 } else { 244 // !!!!! Danger! No update to reg_degree despite having a neighbor. 245 // A variant of the Briggs assertion. 246 // Not needed if I simplify during coalesce, ala George/Appel. 247 assert( lrg.lo_degree(), "" ); 248 } 249 } 250 } 251 // Add neighbors of two as well 252 IndexSetIterator elements2(two); 253 while ((element = elements2.next()) != 0) { 254 LRG &lrg = ifg->lrgs(element); 255 if (mask.overlap(lrg.mask())) { 256 if (insert(element)) { 257 if( !lrg.mask().is_AllStack() ) { 258 reg_degree += lrg2.compute_degree(lrg); 259 if( reg_degree >= fail_degree ) return reg_degree; 260 } else { 261 // !!!!! Danger! No update to reg_degree despite having a neighbor. 262 // A variant of the Briggs assertion. 263 // Not needed if I simplify during coalesce, ala George/Appel. 264 assert( lrg.lo_degree(), "" ); 265 } 266 } 267 } 268 } 269 270 return reg_degree; 271} 272 273//---------------------------- IndexSet() ----------------------------- 274// A deep copy constructor. This is used when you need a scratch copy of this set. 275 276IndexSet::IndexSet (IndexSet *set) { 277#ifdef ASSERT 278 _serial_number = _serial_count++; 279 set->check_watch("copied", _serial_number); 280 check_watch("initialized by copy", set->_serial_number); 281 _max_elements = set->_max_elements; 282#endif 283 _count = set->_count; 284 _max_blocks = set->_max_blocks; 285 if (_max_blocks <= preallocated_block_list_size) { 286 _blocks = _preallocated_block_list; 287 } else { 288 _blocks = 289 (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); 290 } 291 for (uint i = 0; i < _max_blocks; i++) { 292 BitBlock *block = set->_blocks[i]; 293 if (block == &_empty_block) { 294 set_block(i, &_empty_block); 295 } else { 296 BitBlock *new_block = alloc_block(); 297 memcpy(new_block->words(), block->words(), sizeof(uint32) * words_per_block); 298 set_block(i, new_block); 299 } 300 } 301} 302 303//---------------------------- IndexSet::initialize() ----------------------------- 304// Prepare an IndexSet for use. 305 306void IndexSet::initialize(uint max_elements) { 307#ifdef ASSERT 308 _serial_number = _serial_count++; 309 check_watch("initialized", max_elements); 310 _max_elements = max_elements; 311#endif 312 _count = 0; 313 _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block; 314 315 if (_max_blocks <= preallocated_block_list_size) { 316 _blocks = _preallocated_block_list; 317 } else { 318 _blocks = (IndexSet::BitBlock**) arena()->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); 319 } 320 for (uint i = 0; i < _max_blocks; i++) { 321 set_block(i, &_empty_block); 322 } 323} 324 325//---------------------------- IndexSet::initialize()------------------------------ 326// Prepare an IndexSet for use. If it needs to allocate its _blocks array, it does 327// so from the Arena passed as a parameter. BitBlock allocation is still done from 328// the static Arena which was set with reset_memory(). 329 330void IndexSet::initialize(uint max_elements, Arena *arena) { 331#ifdef ASSERT 332 _serial_number = _serial_count++; 333 check_watch("initialized2", max_elements); 334 _max_elements = max_elements; 335#endif // ASSERT 336 _count = 0; 337 _max_blocks = (max_elements + bits_per_block - 1) / bits_per_block; 338 339 if (_max_blocks <= preallocated_block_list_size) { 340 _blocks = _preallocated_block_list; 341 } else { 342 _blocks = (IndexSet::BitBlock**) arena->Amalloc_4(sizeof(IndexSet::BitBlock**) * _max_blocks); 343 } 344 for (uint i = 0; i < _max_blocks; i++) { 345 set_block(i, &_empty_block); 346 } 347} 348 349//---------------------------- IndexSet::swap() ----------------------------- 350// Exchange two IndexSets. 351 352void IndexSet::swap(IndexSet *set) { 353#ifdef ASSERT 354 assert(_max_elements == set->_max_elements, "must have same universe size to swap"); 355 check_watch("swap", set->_serial_number); 356 set->check_watch("swap", _serial_number); 357#endif 358 359 for (uint i = 0; i < _max_blocks; i++) { 360 BitBlock *temp = _blocks[i]; 361 set_block(i, set->_blocks[i]); 362 set->set_block(i, temp); 363 } 364 uint temp = _count; 365 _count = set->_count; 366 set->_count = temp; 367} 368 369//---------------------------- IndexSet::dump() ----------------------------- 370// Print this set. Used for debugging. 371 372#ifndef PRODUCT 373void IndexSet::dump() const { 374 IndexSetIterator elements(this); 375 376 tty->print("{"); 377 uint i; 378 while ((i = elements.next()) != 0) { 379 tty->print("L%d ", i); 380 } 381 tty->print_cr("}"); 382} 383#endif 384 385#ifdef ASSERT 386//---------------------------- IndexSet::tally_iteration_statistics() ----------------------------- 387// Update block/bit counts to reflect that this set has been iterated over. 388 389void IndexSet::tally_iteration_statistics() const { 390 _total_bits += count(); 391 392 for (uint i = 0; i < _max_blocks; i++) { 393 if (_blocks[i] != &_empty_block) { 394 _total_used_blocks++; 395 } else { 396 _total_unused_blocks++; 397 } 398 } 399} 400 401//---------------------------- IndexSet::print_statistics() ----------------------------- 402// Print statistics about IndexSet usage. 403 404void IndexSet::print_statistics() { 405 long total_blocks = _total_used_blocks + _total_unused_blocks; 406 tty->print_cr ("Accumulated IndexSet usage statistics:"); 407 tty->print_cr ("--------------------------------------"); 408 tty->print_cr (" Iteration:"); 409 tty->print_cr (" blocks visited: %d", total_blocks); 410 tty->print_cr (" blocks empty: %4.2f%%", 100.0*_total_unused_blocks/total_blocks); 411 tty->print_cr (" bit density (bits/used blocks): %4.2f%%", (double)_total_bits/_total_used_blocks); 412 tty->print_cr (" bit density (bits/all blocks): %4.2f%%", (double)_total_bits/total_blocks); 413 tty->print_cr (" Allocation:"); 414 tty->print_cr (" blocks allocated: %d", _alloc_new); 415 tty->print_cr (" blocks used/reused: %d", _alloc_total); 416} 417 418//---------------------------- IndexSet::verify() ----------------------------- 419// Expensive test of IndexSet sanity. Ensure that the count agrees with the 420// number of bits in the blocks. Make sure the iterator is seeing all elements 421// of the set. Meant for use during development. 422 423void IndexSet::verify() const { 424 assert(!member(0), "zero cannot be a member"); 425 uint count = 0; 426 uint i; 427 for (i = 1; i < _max_elements; i++) { 428 if (member(i)) { 429 count++; 430 assert(count <= _count, "_count is messed up"); 431 } 432 } 433 434 IndexSetIterator elements(this); 435 count = 0; 436 while ((i = elements.next()) != 0) { 437 count++; 438 assert(member(i), "returned a non member"); 439 assert(count <= _count, "iterator returned wrong number of elements"); 440 } 441} 442#endif 443 444//---------------------------- IndexSetIterator() ----------------------------- 445// Create an iterator for a set. If empty blocks are detected when iterating 446// over the set, these blocks are replaced. 447 448IndexSetIterator::IndexSetIterator(IndexSet *set) { 449#ifdef ASSERT 450 if (CollectIndexSetStatistics) { 451 set->tally_iteration_statistics(); 452 } 453 set->check_watch("traversed", set->count()); 454#endif 455 if (set->is_empty()) { 456 _current = 0; 457 _next_word = IndexSet::words_per_block; 458 _next_block = 1; 459 _max_blocks = 1; 460 461 // We don't need the following values when we iterate over an empty set. 462 // The commented out code is left here to document that the omission 463 // is intentional. 464 // 465 //_value = 0; 466 //_words = NULL; 467 //_blocks = NULL; 468 //_set = NULL; 469 } else { 470 _current = 0; 471 _value = 0; 472 _next_block = 0; 473 _next_word = IndexSet::words_per_block; 474 475 _max_blocks = set->_max_blocks; 476 _words = NULL; 477 _blocks = set->_blocks; 478 _set = set; 479 } 480} 481 482//---------------------------- IndexSetIterator(const) ----------------------------- 483// Iterate over a constant IndexSet. 484 485IndexSetIterator::IndexSetIterator(const IndexSet *set) { 486#ifdef ASSERT 487 if (CollectIndexSetStatistics) { 488 set->tally_iteration_statistics(); 489 } 490 // We don't call check_watch from here to avoid bad recursion. 491 // set->check_watch("traversed const", set->count()); 492#endif 493 if (set->is_empty()) { 494 _current = 0; 495 _next_word = IndexSet::words_per_block; 496 _next_block = 1; 497 _max_blocks = 1; 498 499 // We don't need the following values when we iterate over an empty set. 500 // The commented out code is left here to document that the omission 501 // is intentional. 502 // 503 //_value = 0; 504 //_words = NULL; 505 //_blocks = NULL; 506 //_set = NULL; 507 } else { 508 _current = 0; 509 _value = 0; 510 _next_block = 0; 511 _next_word = IndexSet::words_per_block; 512 513 _max_blocks = set->_max_blocks; 514 _words = NULL; 515 _blocks = set->_blocks; 516 _set = NULL; 517 } 518} 519 520//---------------------------- List16Iterator::advance_and_next() ----------------------------- 521// Advance to the next non-empty word in the set being iterated over. Return the next element 522// if there is one. If we are done, return 0. This method is called from the next() method 523// when it gets done with a word. 524 525uint IndexSetIterator::advance_and_next() { 526 // See if there is another non-empty word in the current block. 527 for (uint wi = _next_word; wi < (unsigned)IndexSet::words_per_block; wi++) { 528 if (_words[wi] != 0) { 529 // Found a non-empty word. 530 _value = ((_next_block - 1) * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word); 531 _current = _words[wi]; 532 533 _next_word = wi+1; 534 535 return next(); 536 } 537 } 538 539 // We ran out of words in the current block. Advance to next non-empty block. 540 for (uint bi = _next_block; bi < _max_blocks; bi++) { 541 if (_blocks[bi] != &IndexSet::_empty_block) { 542 // Found a non-empty block. 543 544 _words = _blocks[bi]->words(); 545 for (uint wi = 0; wi < (unsigned)IndexSet::words_per_block; wi++) { 546 if (_words[wi] != 0) { 547 // Found a non-empty word. 548 _value = (bi * IndexSet::bits_per_block) + (wi * IndexSet::bits_per_word); 549 _current = _words[wi]; 550 551 _next_block = bi+1; 552 _next_word = wi+1; 553 554 return next(); 555 } 556 } 557 558 // All of the words in the block were empty. Replace 559 // the block with the empty block. 560 if (_set) { 561 _set->free_block(bi); 562 } 563 } 564 } 565 566 // These assignments make redundant calls to next on a finished iterator 567 // faster. Probably not necessary. 568 _next_block = _max_blocks; 569 _next_word = IndexSet::words_per_block; 570 571 // No more words. 572 return 0; 573} 574