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