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 #ifndef SHARE_VM_OPTO_INDEXSET_HPP
26 #define SHARE_VM_OPTO_INDEXSET_HPP
27
28 #include "memory/allocation.hpp"
29 #include "memory/resourceArea.hpp"
30 #include "opto/compile.hpp"
31 #include "opto/regmask.hpp"
32
33 // This file defines the IndexSet class, a set of sparse integer indices.
34 // This data structure is used by the compiler in its liveness analysis and
35 // during register allocation.
36
37 //-------------------------------- class IndexSet ----------------------------
38 // An IndexSet is a piece-wise bitvector. At the top level, we have an array
39 // of pointers to bitvector chunks called BitBlocks. Each BitBlock has a fixed
40 // size and is allocated from a shared free list. The bits which are set in
41 // each BitBlock correspond to the elements of the set.
42
43 class IndexSet : public ResourceObj {
44 friend class IndexSetIterator;
45
46 public:
47 // When we allocate an IndexSet, it starts off with an array of top level block
48 // pointers of a set length. This size is intended to be large enough for the
49 // majority of IndexSets. In the cases when this size is not large enough,
50 // a separately allocated array is used.
51
52 // The length of the preallocated top level block array
53 enum { preallocated_block_list_size = 16 };
54
55 // Elements of a IndexSet get decomposed into three fields. The highest order
56 // bits are the block index, which tell which high level block holds the element.
57 // Within that block, the word index indicates which word holds the element.
58 // Finally, the bit index determines which single bit within that word indicates
59 // membership of the element in the set.
60
61 // The lengths of the index bitfields
62 enum { bit_index_length = 5,
63 word_index_length = 3,
64 block_index_length = 8 // not used
65 };
66
67 // Derived constants used for manipulating the index bitfields
68 enum {
69 bit_index_offset = 0, // not used
70 word_index_offset = bit_index_length,
71 block_index_offset = bit_index_length + word_index_length,
72
73 bits_per_word = 1 << bit_index_length,
74 words_per_block = 1 << word_index_length,
75 bits_per_block = bits_per_word * words_per_block,
76
77 bit_index_mask = right_n_bits(bit_index_length),
78 word_index_mask = right_n_bits(word_index_length)
79 };
80
81 // These routines are used for extracting the block, word, and bit index
82 // from an element.
83 static uint get_block_index(uint element) {
84 return element >> block_index_offset;
85 }
86 static uint get_word_index(uint element) {
87 return mask_bits(element >> word_index_offset,word_index_mask);
88 }
89 static uint get_bit_index(uint element) {
90 return mask_bits(element,bit_index_mask);
91 }
92
93 //------------------------------ class BitBlock ----------------------------
94 // The BitBlock class is a segment of a bitvector set.
95
96 class BitBlock : public ResourceObj {
97 friend class IndexSetIterator;
98 friend class IndexSet;
99
100 private:
101 // All of BitBlocks fields and methods are declared private. We limit
102 // access to IndexSet and IndexSetIterator.
103
104 // A BitBlock is composed of some number of 32 bit words. When a BitBlock
105 // is not in use by any IndexSet, it is stored on a free list. The next field
106 // is used by IndexSet to mainting this free list.
107
108 union {
109 uint32_t _words[words_per_block];
110 BitBlock *_next;
111 } _data;
112
113 // accessors
114 uint32_t* words() { return _data._words; }
115 void set_next(BitBlock *next) { _data._next = next; }
116 BitBlock *next() { return _data._next; }
117
118 // Operations. A BitBlock supports four simple operations,
119 // clear(), member(), insert(), and remove(). These methods do
120 // not assume that the block index has been masked out.
121
122 void clear() {
123 memset(words(), 0, sizeof(uint32_t) * words_per_block);
124 }
125
126 bool member(uint element) {
127 uint word_index = IndexSet::get_word_index(element);
128 uint bit_index = IndexSet::get_bit_index(element);
129
130 return ((words()[word_index] & (uint32_t)(0x1 << bit_index)) != 0);
131 }
132
133 bool insert(uint element) {
134 uint word_index = IndexSet::get_word_index(element);
135 uint bit_index = IndexSet::get_bit_index(element);
136
137 uint32_t bit = (0x1 << bit_index);
138 uint32_t before = words()[word_index];
139 words()[word_index] = before | bit;
140 return ((before & bit) != 0);
141 }
142
143 bool remove(uint element) {
144 uint word_index = IndexSet::get_word_index(element);
145 uint bit_index = IndexSet::get_bit_index(element);
146
147 uint32_t bit = (0x1 << bit_index);
148 uint32_t before = words()[word_index];
149 words()[word_index] = before & ~bit;
150 return ((before & bit) != 0);
151 }
152 };
153
154 //-------------------------- BitBlock allocation ---------------------------
155 private:
156
157 // All IndexSets share an arena from which they allocate BitBlocks. Unused
158 // BitBlocks are placed on a free list.
159
160 // The number of BitBlocks to allocate at a time
161 enum { bitblock_alloc_chunk_size = 50 };
162
163 static Arena *arena() { return Compile::current()->indexSet_arena(); }
164
165 static void populate_free_list();
166
167 public:
168
169 // Invalidate the current free BitBlock list and begin allocation
170 // from a new arena. It is essential that this method is called whenever
171 // the Arena being used for BitBlock allocation is reset.
172 static void reset_memory(Compile* compile, Arena *arena) {
173 compile->set_indexSet_free_block_list(NULL);
174 compile->set_indexSet_arena(arena);
175
176 // This should probably be done in a static initializer
177 _empty_block.clear();
178 }
179
180 private:
181 friend class BitBlock;
182 // A distinguished BitBlock which always remains empty. When a new IndexSet is
183 // created, all of its top level BitBlock pointers are initialized to point to
184 // this.
185 static BitBlock _empty_block;
186
187 //-------------------------- Members ------------------------------------------
188
189 // The number of elements in the set
190 uint _count;
191
192 // Our top level array of bitvector segments
193 BitBlock **_blocks;
194
195 BitBlock *_preallocated_block_list[preallocated_block_list_size];
196
197 // The number of top level array entries in use
198 uint _max_blocks;
199
200 // Our assertions need to know the maximum number allowed in the set
201 #ifdef ASSERT
202 uint _max_elements;
203 #endif
204
205 // The next IndexSet on the free list (not used at same time as count)
206 IndexSet *_next;
207
208 public:
209 //-------------------------- Free list operations ------------------------------
210 // Individual IndexSets can be placed on a free list. This is done in PhaseLive.
211
212 IndexSet *next() {
213 #ifdef ASSERT
214 if( VerifyOpto ) {
215 check_watch("removed from free list?", ((_next == NULL) ? 0 : _next->_serial_number));
216 }
217 #endif
218 return _next;
219 }
220
221 void set_next(IndexSet *next) {
222 #ifdef ASSERT
223 if( VerifyOpto ) {
224 check_watch("put on free list?", ((next == NULL) ? 0 : next->_serial_number));
225 }
226 #endif
227 _next = next;
228 }
229
230 private:
231 //-------------------------- Utility methods -----------------------------------
232
233 // Get the block which holds element
234 BitBlock *get_block_containing(uint element) const {
235 assert(element < _max_elements, "element out of bounds");
236 return _blocks[get_block_index(element)];
237 }
238
239 // Set a block in the top level array
240 void set_block(uint index, BitBlock *block) {
241 #ifdef ASSERT
242 if( VerifyOpto )
243 check_watch("set block", index);
244 #endif
245 _blocks[index] = block;
246 }
247
248 // Get a BitBlock from the free list
249 BitBlock *alloc_block();
250
251 // Get a BitBlock from the free list and place it in the top level array
252 BitBlock *alloc_block_containing(uint element);
253
254 // Free a block from the top level array, placing it on the free BitBlock list
255 void free_block(uint i);
256
257 public:
258 //-------------------------- Primitive set operations --------------------------
259
260 void clear() {
261 #ifdef ASSERT
262 if( VerifyOpto )
263 check_watch("clear");
264 #endif
265 _count = 0;
266 for (uint i = 0; i < _max_blocks; i++) {
267 BitBlock *block = _blocks[i];
268 if (block != &_empty_block) {
269 free_block(i);
270 }
271 }
272 }
273
274 uint count() const { return _count; }
275
276 bool is_empty() const { return _count == 0; }
277
278 bool member(uint element) const {
279 return get_block_containing(element)->member(element);
280 }
281
282 bool insert(uint element) {
283 #ifdef ASSERT
284 if( VerifyOpto )
285 check_watch("insert", element);
286 #endif
287 if (element == 0) {
288 return 0;
289 }
290 BitBlock *block = get_block_containing(element);
291 if (block == &_empty_block) {
292 block = alloc_block_containing(element);
293 }
294 bool present = block->insert(element);
295 if (!present) {
296 _count++;
297 }
298 return !present;
299 }
300
301 bool remove(uint element) {
302 #ifdef ASSERT
303 if( VerifyOpto )
304 check_watch("remove", element);
305 #endif
306
307 BitBlock *block = get_block_containing(element);
308 bool present = block->remove(element);
309 if (present) {
310 _count--;
311 }
312 return present;
313 }
314
315 //-------------------------- Compound set operations ------------------------
316 // Compute the union of all elements of one and two which interfere
317 // with the RegMask mask. If the degree of the union becomes
318 // exceeds fail_degree, the union bails out. The underlying set is
319 // cleared before the union is performed.
320 uint lrg_union(uint lr1, uint lr2,
321 const uint fail_degree,
322 const class PhaseIFG *ifg,
323 const RegMask &mask);
324
325
326 //------------------------- Construction, initialization -----------------------
327
328 IndexSet() {}
329
330 // This constructor is used for making a deep copy of a IndexSet.
331 IndexSet(IndexSet *set);
332
333 // Perform initialization on a IndexSet
334 void initialize(uint max_element);
335
336 // Initialize a IndexSet. If the top level BitBlock array needs to be
337 // allocated, do it from the proffered arena. BitBlocks are still allocated
338 // from the static Arena member.
339 void initialize(uint max_element, Arena *arena);
340
341 // Exchange two sets
342 void swap(IndexSet *set);
343
344 //-------------------------- Debugging and statistics --------------------------
345
346 #ifndef PRODUCT
347 // Output a IndexSet for debugging
348 void dump() const;
349 #endif
350
351 #ifdef ASSERT
352 void tally_iteration_statistics() const;
353
354 // BitBlock allocation statistics
355 static julong _alloc_new;
356 static julong _alloc_total;
357
358 // Block density statistics
359 static julong _total_bits;
360 static julong _total_used_blocks;
361 static julong _total_unused_blocks;
362
363 // Sanity tests
364 void verify() const;
365
366 static int _serial_count;
367 int _serial_number;
368
369 // Check to see if the serial number of the current set is the one we're tracing.
370 // If it is, print a message.
371 void check_watch(const char *operation, uint operand) const {
372 if (IndexSetWatch != 0) {
373 if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
374 tty->print_cr("IndexSet %d : %s ( %d )", _serial_number, operation, operand);
375 }
376 }
377 }
378 void check_watch(const char *operation) const {
379 if (IndexSetWatch != 0) {
380 if (IndexSetWatch == -1 || _serial_number == IndexSetWatch) {
381 tty->print_cr("IndexSet %d : %s", _serial_number, operation);
382 }
383 }
384 }
385
386 public:
387 static void print_statistics();
388
389 #endif
390 };
391
392
393 //-------------------------------- class IndexSetIterator --------------------
394 // An iterator for IndexSets.
395
396 class IndexSetIterator {
397 friend class IndexSet;
398
399 public:
400
401 // We walk over the bits in a word in chunks of size window_size.
402 enum { window_size = 5,
403 window_mask = right_n_bits(window_size),
404 table_size = (1 << window_size) };
405
406 // For an integer of length window_size, what is the first set bit?
407 static const uint8_t _first_bit[table_size];
408
409 // For an integer of length window_size, what is the second set bit?
410 static const uint8_t _second_bit[table_size];
411
412 private:
413 // The current word we are inspecting
414 uint32_t _current;
415
416 // What element number are we currently on?
417 uint _value;
418
419 // The index of the next word we will inspect
420 uint _next_word;
421
422 // A pointer to the contents of the current block
423 uint32_t *_words;
424
425 // The index of the next block we will inspect
426 uint _next_block;
427
428 // A pointer to the blocks in our set
429 IndexSet::BitBlock **_blocks;
430
431 // The number of blocks in the set
432 uint _max_blocks;
433
434 // If the iterator was created from a non-const set, we replace
435 // non-canonical empty blocks with the _empty_block pointer. If
436 // _set is NULL, we do no replacement.
437 IndexSet *_set;
438
439 // Advance to the next non-empty word and return the next
440 // element in the set.
441 uint advance_and_next();
442
443
444 public:
445
446 // If an iterator is built from a constant set then empty blocks
447 // are not canonicalized.
448 IndexSetIterator(IndexSet *set);
449 IndexSetIterator(const IndexSet *set);
450
451 // Return the next element of the set. Return 0 when done.
452 uint next() {
453 uint current = _current;
454 if (current != 0) {
455 uint value = _value;
456 while (mask_bits(current,window_mask) == 0) {
457 current >>= window_size;
458 value += window_size;
459 }
460
461 uint advance = _second_bit[mask_bits(current,window_mask)];
462 _current = current >> advance;
463 _value = value + advance;
464 return value + _first_bit[mask_bits(current,window_mask)];
465 } else {
466 return advance_and_next();
467 }
468 }
469 };
470
471 #endif // SHARE_VM_OPTO_INDEXSET_HPP