1 /*
2 * Copyright (c) 1997, 2020, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "opto/ad.hpp"
27 #include "opto/chaitin.hpp"
28 #include "opto/compile.hpp"
29 #include "opto/matcher.hpp"
30 #include "opto/node.hpp"
31 #include "opto/regmask.hpp"
32 #include "utilities/population_count.hpp"
33 #include "utilities/powerOfTwo.hpp"
34
35 //------------------------------dump-------------------------------------------
36
37 #ifndef PRODUCT
dump(int r,outputStream * st)38 void OptoReg::dump(int r, outputStream *st) {
39 switch (r) {
40 case Special: st->print("r---"); break;
41 case Bad: st->print("rBAD"); break;
42 default:
43 if (r < _last_Mach_Reg) st->print("%s", Matcher::regName[r]);
44 else st->print("rS%d",r);
45 break;
46 }
47 }
48 #endif
49
50
51 //=============================================================================
52 const RegMask RegMask::Empty;
53
54 //=============================================================================
is_vector(uint ireg)55 bool RegMask::is_vector(uint ireg) {
56 return (ireg == Op_VecA || ireg == Op_VecS || ireg == Op_VecD ||
57 ireg == Op_VecX || ireg == Op_VecY || ireg == Op_VecZ );
58 }
59
num_registers(uint ireg)60 int RegMask::num_registers(uint ireg) {
61 switch(ireg) {
62 case Op_VecZ:
63 return SlotsPerVecZ;
64 case Op_VecY:
65 return SlotsPerVecY;
66 case Op_VecX:
67 return SlotsPerVecX;
68 case Op_VecD:
69 return SlotsPerVecD;
70 case Op_RegD:
71 case Op_RegL:
72 #ifdef _LP64
73 case Op_RegP:
74 #endif
75 return 2;
76 case Op_VecA:
77 assert(Matcher::supports_scalable_vector(), "does not support scalable vector");
78 return SlotsPerVecA;
79 default:
80 // Op_VecS and the rest ideal registers.
81 assert(ireg == Op_VecS || !is_vector(ireg), "unexpected, possibly multi-slot register");
82 return 1;
83 }
84 }
85
num_registers(uint ireg,LRG & lrg)86 int RegMask::num_registers(uint ireg, LRG &lrg) {
87 int n_regs = num_registers(ireg);
88
89 // assigned is OptoReg which is selected by register allocator
90 OptoReg::Name assigned = lrg.reg();
91 assert(OptoReg::is_valid(assigned), "should be valid opto register");
92
93 if (lrg.is_scalable() && OptoReg::is_stack(assigned)) {
94 n_regs = lrg.scalable_reg_slots();
95 }
96 return n_regs;
97 }
98
99 static const uintptr_t zero = uintptr_t(0); // 0x00..00
100 static const uintptr_t all = ~uintptr_t(0); // 0xFF..FF
101 static const uintptr_t fives = all/3; // 0x5555..55
102
103 // only indices of power 2 are accessed, so index 3 is only filled in for storage.
104 static const uintptr_t low_bits[5] = { fives, // 0x5555..55
105 all/0xF, // 0x1111..11,
106 all/0xFF, // 0x0101..01,
107 zero, // 0x0000..00
108 all/0xFFFF }; // 0x0001..01
109
110 // Clear out partial bits; leave only bit pairs
clear_to_pairs()111 void RegMask::clear_to_pairs() {
112 assert(valid_watermarks(), "sanity");
113 for (unsigned i = _lwm; i <= _hwm; i++) {
114 uintptr_t bits = _RM_UP[i];
115 bits &= ((bits & fives) << 1U); // 1 hi-bit set for each pair
116 bits |= (bits >> 1U); // Smear 1 hi-bit into a pair
117 _RM_UP[i] = bits;
118 }
119 assert(is_aligned_pairs(), "mask is not aligned, adjacent pairs");
120 }
121
is_misaligned_pair() const122 bool RegMask::is_misaligned_pair() const {
123 return Size() == 2 && !is_aligned_pairs();
124 }
125
is_aligned_pairs() const126 bool RegMask::is_aligned_pairs() const {
127 // Assert that the register mask contains only bit pairs.
128 assert(valid_watermarks(), "sanity");
129 for (unsigned i = _lwm; i <= _hwm; i++) {
130 uintptr_t bits = _RM_UP[i];
131 while (bits) { // Check bits for pairing
132 uintptr_t bit = uintptr_t(1) << find_lowest_bit(bits); // Extract low bit
133 // Low bit is not odd means its mis-aligned.
134 if ((bit & fives) == 0) return false;
135 bits -= bit; // Remove bit from mask
136 // Check for aligned adjacent bit
137 if ((bits & (bit << 1U)) == 0) return false;
138 bits -= (bit << 1U); // Remove other halve of pair
139 }
140 }
141 return true;
142 }
143
144 // Return TRUE if the mask contains a single bit
is_bound1() const145 bool RegMask::is_bound1() const {
146 if (is_AllStack()) return false;
147
148 for (unsigned i = _lwm; i <= _hwm; i++) {
149 uintptr_t v = _RM_UP[i];
150 if (v != 0) {
151 // Only one bit allowed -> v must be a power of two
152 if (!is_power_of_2(v)) {
153 return false;
154 }
155
156 // A single bit was found - check there are no bits in the rest of the mask
157 for (i++; i <= _hwm; i++) {
158 if (_RM_UP[i] != 0) {
159 return false;
160 }
161 }
162 // Done; found a single bit
163 return true;
164 }
165 }
166 // No bit found
167 return false;
168 }
169
170 // Return TRUE if the mask contains an adjacent pair of bits and no other bits.
is_bound_pair() const171 bool RegMask::is_bound_pair() const {
172 if (is_AllStack()) return false;
173
174 assert(valid_watermarks(), "sanity");
175 for (unsigned i = _lwm; i <= _hwm; i++) {
176 if (_RM_UP[i] != 0) { // Found some bits
177 unsigned int bit_index = find_lowest_bit(_RM_UP[i]);
178 if (bit_index != _WordBitMask) { // Bit pair stays in same word?
179 uintptr_t bit = uintptr_t(1) << bit_index; // Extract lowest bit from mask
180 if ((bit | (bit << 1U)) != _RM_UP[i]) {
181 return false; // Require adjacent bit pair and no more bits
182 }
183 } else { // Else its a split-pair case
184 assert(is_power_of_2(_RM_UP[i]), "invariant");
185 i++; // Skip iteration forward
186 if (i > _hwm || _RM_UP[i] != 1) {
187 return false; // Require 1 lo bit in next word
188 }
189 }
190
191 // A matching pair was found - check there are no bits in the rest of the mask
192 for (i++; i <= _hwm; i++) {
193 if (_RM_UP[i] != 0) {
194 return false;
195 }
196 }
197 // Found a bit pair
198 return true;
199 }
200 }
201 // True for the empty mask, too
202 return true;
203 }
204
205 // Test for a single adjacent set of ideal register's size.
is_bound(uint ireg) const206 bool RegMask::is_bound(uint ireg) const {
207 if (is_vector(ireg)) {
208 if (is_bound_set(num_registers(ireg)))
209 return true;
210 } else if (is_bound1() || is_bound_pair()) {
211 return true;
212 }
213 return false;
214 }
215
216 // Check that whether given reg number with size is valid
217 // for current regmask, where reg is the highest number.
is_valid_reg(OptoReg::Name reg,const int size) const218 bool RegMask::is_valid_reg(OptoReg::Name reg, const int size) const {
219 for (int i = 0; i < size; i++) {
220 if (!Member(reg - i)) {
221 return false;
222 }
223 }
224 return true;
225 }
226
227 // Find the lowest-numbered register set in the mask. Return the
228 // HIGHEST register number in the set, or BAD if no sets.
229 // Works also for size 1.
find_first_set(LRG & lrg,const int size) const230 OptoReg::Name RegMask::find_first_set(LRG &lrg, const int size) const {
231 if (lrg.is_scalable()) {
232 // For scalable vector register, regmask is SlotsPerVecA bits aligned.
233 assert(is_aligned_sets(SlotsPerVecA), "mask is not aligned, adjacent sets");
234 } else {
235 assert(is_aligned_sets(size), "mask is not aligned, adjacent sets");
236 }
237 assert(valid_watermarks(), "sanity");
238 for (unsigned i = _lwm; i <= _hwm; i++) {
239 if (_RM_UP[i]) { // Found some bits
240 // Convert to bit number, return hi bit in pair
241 return OptoReg::Name((i<<_LogWordBits) + find_lowest_bit(_RM_UP[i]) + (size - 1));
242 }
243 }
244 return OptoReg::Bad;
245 }
246
247 // Clear out partial bits; leave only aligned adjacent bit pairs
clear_to_sets(const unsigned int size)248 void RegMask::clear_to_sets(const unsigned int size) {
249 if (size == 1) return;
250 assert(2 <= size && size <= 16, "update low bits table");
251 assert(is_power_of_2(size), "sanity");
252 assert(valid_watermarks(), "sanity");
253 uintptr_t low_bits_mask = low_bits[size >> 2U];
254 for (unsigned i = _lwm; i <= _hwm; i++) {
255 uintptr_t bits = _RM_UP[i];
256 uintptr_t sets = (bits & low_bits_mask);
257 for (unsigned j = 1U; j < size; j++) {
258 sets = (bits & (sets << 1U)); // filter bits which produce whole sets
259 }
260 sets |= (sets >> 1U); // Smear 1 hi-bit into a set
261 if (size > 2) {
262 sets |= (sets >> 2U); // Smear 2 hi-bits into a set
263 if (size > 4) {
264 sets |= (sets >> 4U); // Smear 4 hi-bits into a set
265 if (size > 8) {
266 sets |= (sets >> 8U); // Smear 8 hi-bits into a set
267 }
268 }
269 }
270 _RM_UP[i] = sets;
271 }
272 assert(is_aligned_sets(size), "mask is not aligned, adjacent sets");
273 }
274
275 // Smear out partial bits to aligned adjacent bit sets
smear_to_sets(const unsigned int size)276 void RegMask::smear_to_sets(const unsigned int size) {
277 if (size == 1) return;
278 assert(2 <= size && size <= 16, "update low bits table");
279 assert(is_power_of_2(size), "sanity");
280 assert(valid_watermarks(), "sanity");
281 uintptr_t low_bits_mask = low_bits[size >> 2U];
282 for (unsigned i = _lwm; i <= _hwm; i++) {
283 uintptr_t bits = _RM_UP[i];
284 uintptr_t sets = 0;
285 for (unsigned j = 0; j < size; j++) {
286 sets |= (bits & low_bits_mask); // collect partial bits
287 bits = bits >> 1U;
288 }
289 sets |= (sets << 1U); // Smear 1 lo-bit into a set
290 if (size > 2) {
291 sets |= (sets << 2U); // Smear 2 lo-bits into a set
292 if (size > 4) {
293 sets |= (sets << 4U); // Smear 4 lo-bits into a set
294 if (size > 8) {
295 sets |= (sets << 8U); // Smear 8 lo-bits into a set
296 }
297 }
298 }
299 _RM_UP[i] = sets;
300 }
301 assert(is_aligned_sets(size), "mask is not aligned, adjacent sets");
302 }
303
304 // Assert that the register mask contains only bit sets.
is_aligned_sets(const unsigned int size) const305 bool RegMask::is_aligned_sets(const unsigned int size) const {
306 if (size == 1) return true;
307 assert(2 <= size && size <= 16, "update low bits table");
308 assert(is_power_of_2(size), "sanity");
309 uintptr_t low_bits_mask = low_bits[size >> 2U];
310 assert(valid_watermarks(), "sanity");
311 for (unsigned i = _lwm; i <= _hwm; i++) {
312 uintptr_t bits = _RM_UP[i];
313 while (bits) { // Check bits for pairing
314 uintptr_t bit = uintptr_t(1) << find_lowest_bit(bits);
315 // Low bit is not odd means its mis-aligned.
316 if ((bit & low_bits_mask) == 0) {
317 return false;
318 }
319 // Do extra work since (bit << size) may overflow.
320 uintptr_t hi_bit = bit << (size-1); // high bit
321 uintptr_t set = hi_bit + ((hi_bit-1) & ~(bit-1));
322 // Check for aligned adjacent bits in this set
323 if ((bits & set) != set) {
324 return false;
325 }
326 bits -= set; // Remove this set
327 }
328 }
329 return true;
330 }
331
332 // Return TRUE if the mask contains one adjacent set of bits and no other bits.
333 // Works also for size 1.
is_bound_set(const unsigned int size) const334 bool RegMask::is_bound_set(const unsigned int size) const {
335 if (is_AllStack()) return false;
336 assert(1 <= size && size <= 16, "update low bits table");
337 assert(valid_watermarks(), "sanity");
338 for (unsigned i = _lwm; i <= _hwm; i++) {
339 if (_RM_UP[i] != 0) { // Found some bits
340 unsigned bit_index = find_lowest_bit(_RM_UP[i]);
341 uintptr_t bit = uintptr_t(1) << bit_index;
342 if (bit_index + size <= BitsPerWord) { // Bit set stays in same word?
343 uintptr_t hi_bit = bit << (size - 1);
344 uintptr_t set = hi_bit + ((hi_bit-1) & ~(bit-1));
345 if (set != _RM_UP[i]) {
346 return false; // Require adjacent bit set and no more bits
347 }
348 } else { // Else its a split-set case
349 // All bits from bit to highest bit in the word must be set
350 if ((all & ~(bit-1)) != _RM_UP[i]) {
351 return false;
352 }
353 i++; // Skip iteration forward and check high part
354 // The lower bits should be 1 since it is split case.
355 uintptr_t set = (bit >> (BitsPerWord - size)) - 1;
356 if (i > _hwm || _RM_UP[i] != set) {
357 return false; // Require expected low bits in next word
358 }
359 }
360
361 // A matching set found - check there are no bits in the rest of the mask
362 for (i++; i <= _hwm; i++) {
363 if (_RM_UP[i] != 0) {
364 return false;
365 }
366 }
367 // Done - found a bit set
368 return true;
369 }
370 }
371 // True for the empty mask, too
372 return true;
373 }
374
375 // UP means register only, Register plus stack, or stack only is DOWN
is_UP() const376 bool RegMask::is_UP() const {
377 // Quick common case check for DOWN (any stack slot is legal)
378 if (is_AllStack())
379 return false;
380 // Slower check for any stack bits set (also DOWN)
381 if (overlap(Matcher::STACK_ONLY_mask))
382 return false;
383 // Not DOWN, so must be UP
384 return true;
385 }
386
387 // Compute size of register mask in bits
Size() const388 uint RegMask::Size() const {
389 uint sum = 0;
390 assert(valid_watermarks(), "sanity");
391 for (unsigned i = _lwm; i <= _hwm; i++) {
392 sum += population_count(_RM_UP[i]);
393 }
394 return sum;
395 }
396
397 #ifndef PRODUCT
dump(outputStream * st) const398 void RegMask::dump(outputStream *st) const {
399 st->print("[");
400
401 RegMaskIterator rmi(*this);
402 if (rmi.has_next()) {
403 OptoReg::Name start = rmi.next();
404
405 OptoReg::dump(start, st); // Print register
406 OptoReg::Name last = start;
407
408 // Now I have printed an initial register.
409 // Print adjacent registers as "rX-rZ" instead of "rX,rY,rZ".
410 // Begin looping over the remaining registers.
411 while (rmi.has_next()) {
412 OptoReg::Name reg = rmi.next(); // Get a register
413
414 if (last + 1 == reg) { // See if they are adjacent
415 // Adjacent registers just collect into long runs, no printing.
416 last = reg;
417 } else { // Ending some kind of run
418 if (start == last) { // 1-register run; no special printing
419 } else if (start+1 == last) {
420 st->print(","); // 2-register run; print as "rX,rY"
421 OptoReg::dump(last, st);
422 } else { // Multi-register run; print as "rX-rZ"
423 st->print("-");
424 OptoReg::dump(last, st);
425 }
426 st->print(","); // Seperate start of new run
427 start = last = reg; // Start a new register run
428 OptoReg::dump(start, st); // Print register
429 } // End of if ending a register run or not
430 } // End of while regmask not empty
431
432 if (start == last) { // 1-register run; no special printing
433 } else if (start+1 == last) {
434 st->print(","); // 2-register run; print as "rX,rY"
435 OptoReg::dump(last, st);
436 } else { // Multi-register run; print as "rX-rZ"
437 st->print("-");
438 OptoReg::dump(last, st);
439 }
440 if (is_AllStack()) st->print("...");
441 }
442 st->print("]");
443 }
444 #endif
445