1 /*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "compiler_internals.h"
18 #include "dex_file-inl.h"
19
20 namespace art {
21
22 // TODO: profile to make sure this is still a win relative to just using shifted masks.
23 static uint32_t check_masks[32] = {
24 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010,
25 0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200,
26 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
27 0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000,
28 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000,
29 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
30 0x40000000, 0x80000000 };
31
ArenaBitVector(ArenaAllocator * arena,unsigned int start_bits,bool expandable,OatBitMapKind kind)32 ArenaBitVector::ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits,
33 bool expandable, OatBitMapKind kind)
34 : arena_(arena),
35 expandable_(expandable),
36 kind_(kind),
37 storage_size_((start_bits + 31) >> 5),
38 storage_(static_cast<uint32_t*>(arena_->Alloc(storage_size_ * sizeof(uint32_t),
39 ArenaAllocator::kAllocGrowableBitMap))) {
40 DCHECK_EQ(sizeof(storage_[0]), 4U); // Assuming 32-bit units.
41 }
42
43 /*
44 * Determine whether or not the specified bit is set.
45 */
IsBitSet(unsigned int num)46 bool ArenaBitVector::IsBitSet(unsigned int num) {
47 DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
48
49 unsigned int val = storage_[num >> 5] & check_masks[num & 0x1f];
50 return (val != 0);
51 }
52
53 // Mark all bits bit as "clear".
ClearAllBits()54 void ArenaBitVector::ClearAllBits() {
55 memset(storage_, 0, storage_size_ * sizeof(uint32_t));
56 }
57
58 // Mark the specified bit as "set".
59 /*
60 * TUNING: this could have pathologically bad growth/expand behavior. Make sure we're
61 * not using it badly or change resize mechanism.
62 */
SetBit(unsigned int num)63 void ArenaBitVector::SetBit(unsigned int num) {
64 if (num >= storage_size_ * sizeof(uint32_t) * 8) {
65 DCHECK(expandable_) << "Attempted to expand a non-expandable bitmap to position " << num;
66
67 /* Round up to word boundaries for "num+1" bits */
68 unsigned int new_size = (num + 1 + 31) >> 5;
69 DCHECK_GT(new_size, storage_size_);
70 uint32_t *new_storage =
71 static_cast<uint32_t*>(arena_->Alloc(new_size * sizeof(uint32_t),
72 ArenaAllocator::kAllocGrowableBitMap));
73 memcpy(new_storage, storage_, storage_size_ * sizeof(uint32_t));
74 // Zero out the new storage words.
75 memset(&new_storage[storage_size_], 0, (new_size - storage_size_) * sizeof(uint32_t));
76 // TOTO: collect stats on space wasted because of resize.
77 storage_ = new_storage;
78 storage_size_ = new_size;
79 }
80
81 storage_[num >> 5] |= check_masks[num & 0x1f];
82 }
83
84 // Mark the specified bit as "unset".
ClearBit(unsigned int num)85 void ArenaBitVector::ClearBit(unsigned int num) {
86 DCHECK_LT(num, storage_size_ * sizeof(uint32_t) * 8);
87 storage_[num >> 5] &= ~check_masks[num & 0x1f];
88 }
89
90 // Copy a whole vector to the other. Sizes must match.
Copy(ArenaBitVector * src)91 void ArenaBitVector::Copy(ArenaBitVector* src) {
92 DCHECK_EQ(storage_size_, src->GetStorageSize());
93 memcpy(storage_, src->GetRawStorage(), sizeof(uint32_t) * storage_size_);
94 }
95
96 // Intersect with another bit vector. Sizes and expandability must be the same.
Intersect(const ArenaBitVector * src)97 void ArenaBitVector::Intersect(const ArenaBitVector* src) {
98 DCHECK_EQ(storage_size_, src->GetStorageSize());
99 DCHECK_EQ(expandable_, src->IsExpandable());
100 for (unsigned int idx = 0; idx < storage_size_; idx++) {
101 storage_[idx] &= src->GetRawStorageWord(idx);
102 }
103 }
104
105 /*
106 * Union with another bit vector. Sizes and expandability must be the same.
107 */
Union(const ArenaBitVector * src)108 void ArenaBitVector::Union(const ArenaBitVector* src) {
109 DCHECK_EQ(storage_size_, src->GetStorageSize());
110 DCHECK_EQ(expandable_, src->IsExpandable());
111 for (unsigned int idx = 0; idx < storage_size_; idx++) {
112 storage_[idx] |= src->GetRawStorageWord(idx);
113 }
114 }
115
116 // Count the number of bits that are set.
NumSetBits()117 int ArenaBitVector::NumSetBits() {
118 unsigned int count = 0;
119
120 for (unsigned int word = 0; word < storage_size_; word++) {
121 count += __builtin_popcount(storage_[word]);
122 }
123 return count;
124 }
125
126 /*
127 * Mark specified number of bits as "set". Cannot set all bits like ClearAll
128 * since there might be unused bits - setting those to one will confuse the
129 * iterator.
130 */
SetInitialBits(unsigned int num_bits)131 void ArenaBitVector::SetInitialBits(unsigned int num_bits) {
132 DCHECK_LE(((num_bits + 31) >> 5), storage_size_);
133 unsigned int idx;
134 for (idx = 0; idx < (num_bits >> 5); idx++) {
135 storage_[idx] = -1;
136 }
137 unsigned int rem_num_bits = num_bits & 0x1f;
138 if (rem_num_bits) {
139 storage_[idx] = (1 << rem_num_bits) - 1;
140 }
141 }
142
143 } // namespace art
144