1 /*
2 * Copyright (C) 2014 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 <iomanip>
18
19 #include "resource_mask.h"
20
21 #include "base/bit_utils.h"
22 #include "base/arena_allocator.h"
23 #include "base/logging.h"
24
25 namespace art {
26
27 namespace { // anonymous namespace
28
29 constexpr ResourceMask kNoRegMasks[] = {
30 kEncodeNone,
31 kEncodeHeapRef,
32 kEncodeLiteral,
33 kEncodeDalvikReg,
34 ResourceMask::Bit(ResourceMask::kFPStatus),
35 ResourceMask::Bit(ResourceMask::kCCode),
36 };
37 // The 127-bit is the same as CLZ(masks_[1]) for a ResourceMask with only that bit set.
38 static_assert(kNoRegMasks[127-ResourceMask::kHeapRef].Equals(
39 kEncodeHeapRef), "kNoRegMasks heap ref index unexpected");
40 static_assert(kNoRegMasks[127-ResourceMask::kLiteral].Equals(
41 kEncodeLiteral), "kNoRegMasks literal index unexpected");
42 static_assert(kNoRegMasks[127-ResourceMask::kDalvikReg].Equals(
43 kEncodeDalvikReg), "kNoRegMasks dalvik reg index unexpected");
44 static_assert(kNoRegMasks[127-ResourceMask::kFPStatus].Equals(
45 ResourceMask::Bit(ResourceMask::kFPStatus)), "kNoRegMasks fp status index unexpected");
46 static_assert(kNoRegMasks[127-ResourceMask::kCCode].Equals(
47 ResourceMask::Bit(ResourceMask::kCCode)), "kNoRegMasks ccode index unexpected");
48
49 template <size_t special_bit>
OneRegOneSpecial(size_t reg)50 constexpr ResourceMask OneRegOneSpecial(size_t reg) {
51 return ResourceMask::Bit(reg).Union(ResourceMask::Bit(special_bit));
52 }
53
54 // NOTE: Working around gcc bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61484 .
55 // This should be a two-dimensions array, kSingleRegMasks[][32] and each line should be
56 // enclosed in an extra { }. However, gcc issues a bogus "error: array must be initialized
57 // with a brace-enclosed initializer" for that, so we flatten this to a one-dimensional array.
58 constexpr ResourceMask kSingleRegMasks[] = {
59 #define DEFINE_LIST_32(fn) \
60 fn(0), fn(1), fn(2), fn(3), fn(4), fn(5), fn(6), fn(7), \
61 fn(8), fn(9), fn(10), fn(11), fn(12), fn(13), fn(14), fn(15), \
62 fn(16), fn(17), fn(18), fn(19), fn(20), fn(21), fn(22), fn(23), \
63 fn(24), fn(25), fn(26), fn(27), fn(28), fn(29), fn(30), fn(31)
64 // NOTE: Each line is 512B of constant data, 3KiB in total.
65 DEFINE_LIST_32(ResourceMask::Bit),
66 DEFINE_LIST_32(OneRegOneSpecial<ResourceMask::kHeapRef>),
67 DEFINE_LIST_32(OneRegOneSpecial<ResourceMask::kLiteral>),
68 DEFINE_LIST_32(OneRegOneSpecial<ResourceMask::kDalvikReg>),
69 DEFINE_LIST_32(OneRegOneSpecial<ResourceMask::kFPStatus>),
70 DEFINE_LIST_32(OneRegOneSpecial<ResourceMask::kCCode>),
71 #undef DEFINE_LIST_32
72 };
73
SingleRegMaskIndex(size_t main_index,size_t sub_index)74 constexpr size_t SingleRegMaskIndex(size_t main_index, size_t sub_index) {
75 return main_index * 32u + sub_index;
76 }
77
78 // The 127-bit is the same as CLZ(masks_[1]) for a ResourceMask with only that bit set.
79 static_assert(kSingleRegMasks[SingleRegMaskIndex(127-ResourceMask::kHeapRef, 0)].Equals(
80 OneRegOneSpecial<ResourceMask::kHeapRef>(0)), "kSingleRegMasks heap ref index unexpected");
81 static_assert(kSingleRegMasks[SingleRegMaskIndex(127-ResourceMask::kLiteral, 0)].Equals(
82 OneRegOneSpecial<ResourceMask::kLiteral>(0)), "kSingleRegMasks literal index unexpected");
83 static_assert(kSingleRegMasks[SingleRegMaskIndex(127-ResourceMask::kDalvikReg, 0)].Equals(
84 OneRegOneSpecial<ResourceMask::kDalvikReg>(0)), "kSingleRegMasks dalvik reg index unexpected");
85 static_assert(kSingleRegMasks[SingleRegMaskIndex(127-ResourceMask::kFPStatus, 0)].Equals(
86 OneRegOneSpecial<ResourceMask::kFPStatus>(0)), "kSingleRegMasks fp status index unexpected");
87 static_assert(kSingleRegMasks[SingleRegMaskIndex(127-ResourceMask::kCCode, 0)].Equals(
88 OneRegOneSpecial<ResourceMask::kCCode>(0)), "kSingleRegMasks ccode index unexpected");
89
90 // NOTE: arraysize(kNoRegMasks) multiplied by 32 due to the gcc bug workaround, see above.
91 static_assert(arraysize(kSingleRegMasks) == arraysize(kNoRegMasks) * 32, "arraysizes unexpected");
92
93 constexpr ResourceMask kTwoRegsMasks[] = {
94 #define TWO(a, b) ResourceMask::Bit(a).Union(ResourceMask::Bit(b))
95 // NOTE: 16 * 15 / 2 = 120 entries, 16 bytes each, 1920B in total.
96 TWO(0, 1),
97 TWO(0, 2), TWO(1, 2),
98 TWO(0, 3), TWO(1, 3), TWO(2, 3),
99 TWO(0, 4), TWO(1, 4), TWO(2, 4), TWO(3, 4),
100 TWO(0, 5), TWO(1, 5), TWO(2, 5), TWO(3, 5), TWO(4, 5),
101 TWO(0, 6), TWO(1, 6), TWO(2, 6), TWO(3, 6), TWO(4, 6), TWO(5, 6),
102 TWO(0, 7), TWO(1, 7), TWO(2, 7), TWO(3, 7), TWO(4, 7), TWO(5, 7), TWO(6, 7),
103 TWO(0, 8), TWO(1, 8), TWO(2, 8), TWO(3, 8), TWO(4, 8), TWO(5, 8), TWO(6, 8), TWO(7, 8),
104 TWO(0, 9), TWO(1, 9), TWO(2, 9), TWO(3, 9), TWO(4, 9), TWO(5, 9), TWO(6, 9), TWO(7, 9),
105 TWO(8, 9),
106 TWO(0, 10), TWO(1, 10), TWO(2, 10), TWO(3, 10), TWO(4, 10), TWO(5, 10), TWO(6, 10), TWO(7, 10),
107 TWO(8, 10), TWO(9, 10),
108 TWO(0, 11), TWO(1, 11), TWO(2, 11), TWO(3, 11), TWO(4, 11), TWO(5, 11), TWO(6, 11), TWO(7, 11),
109 TWO(8, 11), TWO(9, 11), TWO(10, 11),
110 TWO(0, 12), TWO(1, 12), TWO(2, 12), TWO(3, 12), TWO(4, 12), TWO(5, 12), TWO(6, 12), TWO(7, 12),
111 TWO(8, 12), TWO(9, 12), TWO(10, 12), TWO(11, 12),
112 TWO(0, 13), TWO(1, 13), TWO(2, 13), TWO(3, 13), TWO(4, 13), TWO(5, 13), TWO(6, 13), TWO(7, 13),
113 TWO(8, 13), TWO(9, 13), TWO(10, 13), TWO(11, 13), TWO(12, 13),
114 TWO(0, 14), TWO(1, 14), TWO(2, 14), TWO(3, 14), TWO(4, 14), TWO(5, 14), TWO(6, 14), TWO(7, 14),
115 TWO(8, 14), TWO(9, 14), TWO(10, 14), TWO(11, 14), TWO(12, 14), TWO(13, 14),
116 TWO(0, 15), TWO(1, 15), TWO(2, 15), TWO(3, 15), TWO(4, 15), TWO(5, 15), TWO(6, 15), TWO(7, 15),
117 TWO(8, 15), TWO(9, 15), TWO(10, 15), TWO(11, 15), TWO(12, 15), TWO(13, 15), TWO(14, 15),
118 #undef TWO
119 };
120 static_assert(arraysize(kTwoRegsMasks) == 16 * 15 / 2, "arraysize of kTwoRegsMasks unexpected");
121
TwoRegsIndex(size_t higher,size_t lower)122 constexpr size_t TwoRegsIndex(size_t higher, size_t lower) {
123 return (higher * (higher - 1)) / 2u + lower;
124 }
125
CheckTwoRegsMask(size_t higher,size_t lower)126 constexpr bool CheckTwoRegsMask(size_t higher, size_t lower) {
127 return ResourceMask::Bit(lower).Union(ResourceMask::Bit(higher)).Equals(
128 kTwoRegsMasks[TwoRegsIndex(higher, lower)]);
129 }
130
CheckTwoRegsMaskLine(size_t line,size_t lower=0u)131 constexpr bool CheckTwoRegsMaskLine(size_t line, size_t lower = 0u) {
132 return (lower == line) ||
133 (CheckTwoRegsMask(line, lower) && CheckTwoRegsMaskLine(line, lower + 1u));
134 }
135
CheckTwoRegsMaskTable(size_t lines)136 constexpr bool CheckTwoRegsMaskTable(size_t lines) {
137 return lines == 0 ||
138 (CheckTwoRegsMaskLine(lines - 1) && CheckTwoRegsMaskTable(lines - 1u));
139 }
140
141 static_assert(CheckTwoRegsMaskTable(16), "two regs masks table check failed");
142
143 } // anonymous namespace
144
GetMask(const ResourceMask & mask)145 const ResourceMask* ResourceMaskCache::GetMask(const ResourceMask& mask) {
146 // Instead of having a deduplication map, we shall just use pre-defined constexpr
147 // masks for the common cases. At most one of the these special bits is allowed:
148 constexpr ResourceMask kAllowedSpecialBits = ResourceMask::Bit(ResourceMask::kFPStatus)
149 .Union(ResourceMask::Bit(ResourceMask::kCCode))
150 .Union(kEncodeHeapRef).Union(kEncodeLiteral).Union(kEncodeDalvikReg);
151 const ResourceMask* res = nullptr;
152 // Limit to low 32 regs and the kAllowedSpecialBits.
153 if ((mask.masks_[0] >> 32) == 0u && (mask.masks_[1] & ~kAllowedSpecialBits.masks_[1]) == 0u) {
154 // Check if it's only up to two registers.
155 uint32_t low_regs = static_cast<uint32_t>(mask.masks_[0]);
156 uint32_t low_regs_without_lowest = low_regs & (low_regs - 1u);
157 if (low_regs_without_lowest == 0u && IsPowerOfTwo(mask.masks_[1])) {
158 // 0 or 1 register, 0 or 1 bit from kAllowedBits. Use a pre-defined mask.
159 size_t index = (mask.masks_[1] != 0u) ? CLZ(mask.masks_[1]) : 0u;
160 DCHECK_LT(index, arraysize(kNoRegMasks));
161 res = (low_regs != 0) ? &kSingleRegMasks[SingleRegMaskIndex(index, CTZ(low_regs))]
162 : &kNoRegMasks[index];
163 } else if (IsPowerOfTwo(low_regs_without_lowest) && mask.masks_[1] == 0u) {
164 // 2 registers and no other flags. Use predefined mask if higher reg is < 16.
165 if (low_regs_without_lowest < (1u << 16)) {
166 res = &kTwoRegsMasks[TwoRegsIndex(CTZ(low_regs_without_lowest), CTZ(low_regs))];
167 }
168 }
169 } else if (mask.Equals(kEncodeAll)) {
170 res = &kEncodeAll;
171 }
172 if (res != nullptr) {
173 DCHECK(res->Equals(mask))
174 << "(" << std::hex << std::setw(16) << mask.masks_[0]
175 << ", "<< std::hex << std::setw(16) << mask.masks_[1]
176 << ") != (" << std::hex << std::setw(16) << res->masks_[0]
177 << ", "<< std::hex << std::setw(16) << res->masks_[1] << ")";
178 return res;
179 }
180
181 // TODO: Deduplicate. (At least the most common masks.)
182 void* mem = allocator_->Alloc(sizeof(ResourceMask), kArenaAllocLIRResourceMask);
183 return new (mem) ResourceMask(mask);
184 }
185
186 } // namespace art
187