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