Mercurial > jdk8-mips64-public > hotspot / file comparison

comparison: src/share/vm/opto/indexSet.cpp

src/share/vm/opto/indexSet.cpp

changeset 0
f90c822e73f8
child 6876
710a3c8b516e
equal deleted inserted replaced
-1:000000000000 0:f90c822e73f8
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 }

Mercurial Repository: jdk8-mips64-public/hotspot

mercurial