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