1
|
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 |
};
|