arena_bit_vector.h revision 862a76027076c341c26aa6cd4a30a7cdd6dc2143
1862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee/* 2862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Copyright (C) 2013 The Android Open Source Project 3862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 4862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 5862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * you may not use this file except in compliance with the License. 6862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * You may obtain a copy of the License at 7862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 8862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * http://www.apache.org/licenses/LICENSE-2.0 9862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * 10862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Unless required by applicable law or agreed to in writing, software 11862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * distributed under the License is distributed on an "AS IS" BASIS, 12862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * See the License for the specific language governing permissions and 14862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * limitations under the License. 15862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee */ 16862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 17862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#ifndef ART_SRC_COMPILER_DEX_COMPILER_ARENA_BIT_VECTOR_H_ 18862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#define ART_SRC_COMPILER_DEX_COMPILER_ARENA_BIT_VECTOR_H_ 19862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 20862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include <stdint.h> 21862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include <stddef.h> 22862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include "compiler_enums.h" 23862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#include "arena_allocator.h" 24862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 25862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeenamespace art { 26862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 27862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee// Type of growable bitmap for memory tuning. 28862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeenum OatBitMapKind { 29862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapMisc = 0, 30862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapUse, 31862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapDef, 32862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapLiveIn, 33862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapBMatrix, 34862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapDominators, 35862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapIDominated, 36862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapDomFrontier, 37862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapPhi, 38862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapTmpBlocks, 39862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapInputBlocks, 40862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapRegisterV, 41862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapTempSSARegisterV, 42862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapNullCheck, 43862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapTmpBlockV, 44862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kBitMapPredecessors, 45862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee kNumBitMapKinds 46862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee}; 47862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 48862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee/* 49862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * Expanding bitmap, used for tracking resources. Bits are numbered starting 50862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee * from zero. All operations on a BitVector are unsynchronized. 51862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee */ 52862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbeeclass ArenaBitVector { 53862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 54862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 55862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee class Iterator { 56862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee public: 57862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee Iterator(ArenaBitVector* bit_vector) 58862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee : p_bits_(bit_vector), 59862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_storage_(bit_vector->GetRawStorage()), 60862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_index_(0), 61862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bit_size_(p_bits_->storage_size_ * sizeof(uint32_t) * 8) {}; 62862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 63862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int Next(); // Returns -1 when no next. 64862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 65862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new(size_t size, ArenaAllocator* arena) { 66862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return arena->NewMem(sizeof(ArenaBitVector::Iterator), true, 67862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator::kAllocGrowableBitMap); 68862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 69862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void operator delete(void* p) {}; // Nop. 70862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 71862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 72862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector* const p_bits_; 73862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* const bit_storage_; 74862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t bit_index_; // Current index (size in bits). 75862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const uint32_t bit_size_; // Size of vector in bits. 76862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee }; 77862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 78862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaBitVector(ArenaAllocator* arena, unsigned int start_bits, bool expandable, 79862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee OatBitMapKind kind = kBitMapMisc); 80862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ~ArenaBitVector() {}; 81862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 82862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void* operator new( size_t size, ArenaAllocator* arena) { 83862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee return arena->NewMem(sizeof(ArenaBitVector), true, ArenaAllocator::kAllocGrowableBitMap); 84862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee } 85862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee static void operator delete(void* p) {}; // Nop. 86862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 87862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void SetBit(unsigned int num); 88862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void ClearBit(unsigned int num); 89862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void MarkAllBits(bool set); 90862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void DebugBitVector(char* msg, int length); 91862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool IsBitSet(unsigned int num); 92862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void ClearAllBits(); 93862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void SetInitialBits(unsigned int num_bits); 94862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Copy(ArenaBitVector* src); 95862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Intersect(const ArenaBitVector* src2); 96862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee void Union(const ArenaBitVector* src); 97862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool Equal(const ArenaBitVector* src); 98862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee int NumSetBits(); 99862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 100862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t GetStorageSize() const { return storage_size_; } 101862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee bool IsExpandable() const { return expandable_; } 102862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t GetRawStorageWord(size_t idx) const { return storage_[idx]; } 103862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* GetRawStorage() { return storage_; } 104862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 105862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee private: 106862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee ArenaAllocator* const arena_; 107862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const bool expandable_; // expand bitmap if we run out? 108862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee const OatBitMapKind kind_; // for memory use tuning. 109862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t storage_size_; // current size, in 32-bit words. 110862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee uint32_t* storage_; 111862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee}; 112862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 113862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 114862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee} // namespace art 115862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee 116862a76027076c341c26aa6cd4a30a7cdd6dc2143buzbee#endif // ART_SRC_COMPILER_DEX_COMPILER_ARENA_BIT_VECTOR_H_ 117