1 /**
2 * Copyright 2024 Huawei Technologies Co., Ltd
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 #include "pipeline/jit/pi/utils/bitmap.h"
17
18 namespace mindspore {
19 namespace pijit {
20
Iter(const BitMap * map,bool begin)21 BitMap::Iter::Iter(const BitMap *map, bool begin) {
22 data_ = map->data() + (begin ? 0 : map->count());
23 end_ = map->data() + map->count();
24 offset_ = static_cast<size_t>(data_ - map->data()) << shf;
25 NextOne();
26 }
27
operator ++()28 BitMap::Iter &BitMap::Iter::operator++() {
29 size_t tail = offset_ & static_cast<size_t>(mod);
30 size_t mask = (*data_) >> (tail + 1);
31 if (tail == mod || mask == 0) {
32 offset_ = offset_ - tail + CountTrailingZeros(0);
33 data_++;
34 NextOne();
35 } else {
36 offset_ += CountTrailingZeros(mask) + 1;
37 }
38 return *this;
39 }
40
NextOne()41 void BitMap::Iter::NextOne() {
42 while (data_ != end_) {
43 offset_ += CountTrailingZeros(*data_);
44 if (*data_ != 0) {
45 break;
46 }
47 ++data_;
48 }
49 }
50
51 // logic and, operator &=()
And(const BitMap & o)52 void BitMap::And(const BitMap &o) {
53 const size_t siz = std::min(count(), o.count());
54 for (size_t i = 0; i < siz; ++i) {
55 data()[i] &= o.data()[i];
56 }
57 }
58
59 // logic or, operator |=()
Or(const BitMap & o)60 void BitMap::Or(const BitMap &o) {
61 const size_t siz = std::min(count(), o.count());
62 for (size_t i = 0; i < siz; ++i) {
63 data()[i] |= o.data()[i];
64 }
65 }
66
OrWithChange(const BitMap & o)67 bool BitMap::OrWithChange(const BitMap &o) {
68 const size_t siz = std::min(count(), o.count());
69 bool change = false;
70 for (size_t i = 0; i < siz; ++i) {
71 auto a = data()[i];
72 auto b = a | o.data()[i];
73 data()[i] = b;
74 change |= a != b;
75 }
76 return change;
77 }
78
Diff(const BitMap & o)79 void BitMap::Diff(const BitMap &o) {
80 const size_t siz = std::min(count(), o.count());
81 for (size_t i = 0; i < siz; ++i) {
82 data()[i] &= ~o.data()[i];
83 }
84 }
85
CountBits() const86 size_t BitMap::CountBits() const {
87 const unsigned *begin = reinterpret_cast<const unsigned *>(data());
88 const unsigned *end = reinterpret_cast<const unsigned *>(data() + count());
89 return std::accumulate(begin, end, 0, [](size_t c, unsigned i) { return c + PopCount(i); });
90 }
91
92 } // namespace pijit
93 } // namespace mindspore
94