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
34 IndexSet::BitBlock IndexSet::_empty_block = IndexSet::BitBlock();
35
36 #ifdef ASSERT
37 // Initialize statistics counters
38 uint IndexSet::_alloc_new = 0;
39 uint IndexSet::_alloc_total = 0;
40
41 long IndexSet::_total_bits = 0;
42 long IndexSet::_total_used_blocks = 0;
43 long IndexSet::_total_unused_blocks = 0;
44
45 // Per set, or all sets operation tracing
46 int IndexSet::_serial_count = 1;
47 #endif
48
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 };
60
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 };
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
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 };*/
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
119 void 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
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());
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
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 }
179
180 //---------------------------- IndexSet::free_block() -------------------------
181 // Add a BitBlock to the free list.
182
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 }
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
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
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
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 }
302
303 //---------------------------- IndexSet::initialize() -----------------------------
304 // Prepare an IndexSet for use.
305
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;
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
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;
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
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
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
373 void 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
389 void 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
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 }
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
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 }
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
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;
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
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;
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
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];
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 }