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