1 /*
2 * Copyright (c) 1998, 2005, 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 // 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
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 };
|
1 /*
2 * Copyright (c) 1998, 2010, 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
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
|