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 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 */ 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". 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 */ 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". 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. 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. 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 */ 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. 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 */ 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
