Mercurial > hg > graal-compiler
annotate src/share/vm/opto/indexSet.hpp @ 1722:effb55808a18
Merge
author | johnc |
---|---|
date | Wed, 18 Aug 2010 17:44:33 -0400 |
parents | c18cbe5936b8 |
children | f95d63e2154a |
rev | line source |
---|---|
0 | 1 /* |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
2 * Copyright (c) 1998, 2005, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
0 | 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 }; |