Fri, 12 Feb 2010 15:27:36 -0800
Merge
1 /*
2 * Copyright 1998-2004 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
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.
29 #include "incls/_precompiled.incl"
30 #include "incls/_indexSet.cpp.incl"
32 //-------------------------------- Initializations ------------------------------
34 IndexSet::BitBlock IndexSet::_empty_block = IndexSet::BitBlock();
36 #ifdef ASSERT
37 // Initialize statistics counters
38 uint IndexSet::_alloc_new = 0;
39 uint IndexSet::_alloc_total = 0;
41 long IndexSet::_total_bits = 0;
42 long IndexSet::_total_used_blocks = 0;
43 long IndexSet::_total_unused_blocks = 0;
45 // Per set, or all sets operation tracing
46 int IndexSet::_serial_count = 1;
47 #endif
49 // What is the first set bit in a 5 bit integer?
50 const 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 };
61 // What is the second set bit in a 5 bit integer?
62 const 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 };
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.
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 };
96 const 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 };*/
115 //---------------------------- IndexSet::populate_free_list() -----------------------------
116 // Populate the free BitBlock list with a batch of BitBlocks. The BitBlocks
117 // are 32 bit aligned.
119 void IndexSet::populate_free_list() {
120 Compile *compile = Compile::current();
121 BitBlock *free = (BitBlock*)compile->indexSet_free_block_list();
123 char *mem = (char*)arena()->Amalloc_4(sizeof(BitBlock) *
124 bitblock_alloc_chunk_size + 32);
126 // Align the pointer to a 32 bit boundary.
127 BitBlock *new_blocks = (BitBlock*)(((uintptr_t)mem + 32) & ~0x001F);
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 }
136 compile->set_indexSet_free_block_list(free);
138 #ifdef ASSERT
139 if (CollectIndexSetStatistics) {
140 _alloc_new += bitblock_alloc_chunk_size;
141 }
142 #endif
143 }
146 //---------------------------- IndexSet::alloc_block() ------------------------
147 // Allocate a BitBlock from the free list. If the free list is empty,
148 // prime it.
150 IndexSet::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());
165 block->clear();
166 return block;
167 }
169 //---------------------------- IndexSet::alloc_block_containing() -------------
170 // Allocate a new BitBlock and put it into the position in the _blocks array
171 // corresponding to element.
173 IndexSet::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 }
180 //---------------------------- IndexSet::free_block() -------------------------
181 // Add a BitBlock to the free list.
183 void 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 }
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.
199 uint 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
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.
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 }
226 clear();
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;
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 }
270 return reg_degree;
271 }
273 //---------------------------- IndexSet() -----------------------------
274 // A deep copy constructor. This is used when you need a scratch copy of this set.
276 IndexSet::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 }
303 //---------------------------- IndexSet::initialize() -----------------------------
304 // Prepare an IndexSet for use.
306 void 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;
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 }
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().
330 void 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;
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 }
349 //---------------------------- IndexSet::swap() -----------------------------
350 // Exchange two IndexSets.
352 void 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
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 }
369 //---------------------------- IndexSet::dump() -----------------------------
370 // Print this set. Used for debugging.
372 #ifndef PRODUCT
373 void IndexSet::dump() const {
374 IndexSetIterator elements(this);
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
385 #ifdef ASSERT
386 //---------------------------- IndexSet::tally_iteration_statistics() -----------------------------
387 // Update block/bit counts to reflect that this set has been iterated over.
389 void IndexSet::tally_iteration_statistics() const {
390 _total_bits += count();
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 }
401 //---------------------------- IndexSet::print_statistics() -----------------------------
402 // Print statistics about IndexSet usage.
404 void 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 }
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.
423 void 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 }
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
444 //---------------------------- IndexSetIterator() -----------------------------
445 // Create an iterator for a set. If empty blocks are detected when iterating
446 // over the set, these blocks are replaced.
448 IndexSetIterator::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;
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;
475 _max_blocks = set->_max_blocks;
476 _words = NULL;
477 _blocks = set->_blocks;
478 _set = set;
479 }
480 }
482 //---------------------------- IndexSetIterator(const) -----------------------------
483 // Iterate over a constant IndexSet.
485 IndexSetIterator::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;
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;
513 _max_blocks = set->_max_blocks;
514 _words = NULL;
515 _blocks = set->_blocks;
516 _set = NULL;
517 }
518 }
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.
525 uint 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];
533 _next_word = wi+1;
535 return next();
536 }
537 }
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.
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];
551 _next_block = bi+1;
552 _next_word = wi+1;
554 return next();
555 }
556 }
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 }
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;
571 // No more words.
572 return 0;
573 }