1/*
2 * Copyright (c) 1997, 2019, 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/compile.hpp"
28#include "opto/matcher.hpp"
29#include "opto/node.hpp"
30#include "opto/regmask.hpp"
31#include "utilities/population_count.hpp"
32
33#define RM_SIZE _RM_SIZE /* a constant private to the class RegMask */
34
35//------------------------------dump-------------------------------------------
36
37#ifndef PRODUCT
38void 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//=============================================================================
52const RegMask RegMask::Empty(
53# define BODY(I) 0,
54 FORALL_BODY
55# undef BODY
56 0
57);
58
59//=============================================================================
60bool RegMask::is_vector(uint ireg) {
61 return (ireg == Op_VecS || ireg == Op_VecD ||
62 ireg == Op_VecX || ireg == Op_VecY || ireg == Op_VecZ );
63}
64
65int RegMask::num_registers(uint ireg) {
66 switch(ireg) {
67 case Op_VecZ:
68 return 16;
69 case Op_VecY:
70 return 8;
71 case Op_VecX:
72 return 4;
73 case Op_VecD:
74 case Op_RegD:
75 case Op_RegL:
76#ifdef _LP64
77 case Op_RegP:
78#endif
79 return 2;
80 }
81 // Op_VecS and the rest ideal registers.
82 return 1;
83}
84
85// Clear out partial bits; leave only bit pairs
86void RegMask::clear_to_pairs() {
87 assert(valid_watermarks(), "sanity");
88 for (int i = _lwm; i <= _hwm; i++) {
89 int bits = _A[i];
90 bits &= ((bits & 0x55555555)<<1); // 1 hi-bit set for each pair
91 bits |= (bits>>1); // Smear 1 hi-bit into a pair
92 _A[i] = bits;
93 }
94 assert(is_aligned_pairs(), "mask is not aligned, adjacent pairs");
95}
96
97bool RegMask::is_misaligned_pair() const {
98 return Size() == 2 && !is_aligned_pairs();
99}
100
101bool RegMask::is_aligned_pairs() const {
102 // Assert that the register mask contains only bit pairs.
103 assert(valid_watermarks(), "sanity");
104 for (int i = _lwm; i <= _hwm; i++) {
105 int bits = _A[i];
106 while (bits) { // Check bits for pairing
107 int bit = bits & -bits; // Extract low bit
108 // Low bit is not odd means its mis-aligned.
109 if ((bit & 0x55555555) == 0) return false;
110 bits -= bit; // Remove bit from mask
111 // Check for aligned adjacent bit
112 if ((bits & (bit<<1)) == 0) return false;
113 bits -= (bit<<1); // Remove other halve of pair
114 }
115 }
116 return true;
117}
118
119// Return TRUE if the mask contains a single bit
120bool RegMask::is_bound1() const {
121 if (is_AllStack()) return false;
122 return Size() == 1;
123}
124
125// Return TRUE if the mask contains an adjacent pair of bits and no other bits.
126bool RegMask::is_bound_pair() const {
127 if (is_AllStack()) return false;
128 int bit = -1; // Set to hold the one bit allowed
129 assert(valid_watermarks(), "sanity");
130 for (int i = _lwm; i <= _hwm; i++) {
131 if (_A[i]) { // Found some bits
132 if (bit != -1) return false; // Already had bits, so fail
133 bit = _A[i] & -(_A[i]); // Extract 1 bit from mask
134 if ((bit << 1) != 0) { // Bit pair stays in same word?
135 if ((bit | (bit<<1)) != _A[i])
136 return false; // Require adjacent bit pair and no more bits
137 } else { // Else its a split-pair case
138 if(bit != _A[i]) return false; // Found many bits, so fail
139 i++; // Skip iteration forward
140 if (i > _hwm || _A[i] != 1)
141 return false; // Require 1 lo bit in next word
142 }
143 }
144 }
145 // True for both the empty mask and for a bit pair
146 return true;
147}
148
149// Test for a single adjacent set of ideal register's size.
150bool RegMask::is_bound(uint ireg) const {
151 if (is_vector(ireg)) {
152 if (is_bound_set(num_registers(ireg)))
153 return true;
154 } else if (is_bound1() || is_bound_pair()) {
155 return true;
156 }
157 return false;
158}
159
160// only indicies of power 2 are accessed, so index 3 is only filled in for storage.
161static int low_bits[5] = { 0x55555555, 0x11111111, 0x01010101, 0x00000000, 0x00010001 };
162
163// Find the lowest-numbered register set in the mask. Return the
164// HIGHEST register number in the set, or BAD if no sets.
165// Works also for size 1.
166OptoReg::Name RegMask::find_first_set(const int size) const {
167 assert(is_aligned_sets(size), "mask is not aligned, adjacent sets");
168 assert(valid_watermarks(), "sanity");
169 for (int i = _lwm; i <= _hwm; i++) {
170 if (_A[i]) { // Found some bits
171 // Convert to bit number, return hi bit in pair
172 return OptoReg::Name((i<<_LogWordBits) + find_lowest_bit(_A[i]) + (size - 1));
173 }
174 }
175 return OptoReg::Bad;
176}
177
178// Clear out partial bits; leave only aligned adjacent bit pairs
179void RegMask::clear_to_sets(const int size) {
180 if (size == 1) return;
181 assert(2 <= size && size <= 16, "update low bits table");
182 assert(is_power_of_2(size), "sanity");
183 assert(valid_watermarks(), "sanity");
184 int low_bits_mask = low_bits[size>>2];
185 for (int i = _lwm; i <= _hwm; i++) {
186 int bits = _A[i];
187 int sets = (bits & low_bits_mask);
188 for (int j = 1; j < size; j++) {
189 sets = (bits & (sets<<1)); // filter bits which produce whole sets
190 }
191 sets |= (sets>>1); // Smear 1 hi-bit into a set
192 if (size > 2) {
193 sets |= (sets>>2); // Smear 2 hi-bits into a set
194 if (size > 4) {
195 sets |= (sets>>4); // Smear 4 hi-bits into a set
196 if (size > 8) {
197 sets |= (sets>>8); // Smear 8 hi-bits into a set
198 }
199 }
200 }
201 _A[i] = sets;
202 }
203 assert(is_aligned_sets(size), "mask is not aligned, adjacent sets");
204}
205
206// Smear out partial bits to aligned adjacent bit sets
207void RegMask::smear_to_sets(const int size) {
208 if (size == 1) return;
209 assert(2 <= size && size <= 16, "update low bits table");
210 assert(is_power_of_2(size), "sanity");
211 assert(valid_watermarks(), "sanity");
212 int low_bits_mask = low_bits[size>>2];
213 for (int i = _lwm; i <= _hwm; i++) {
214 int bits = _A[i];
215 int sets = 0;
216 for (int j = 0; j < size; j++) {
217 sets |= (bits & low_bits_mask); // collect partial bits
218 bits = bits>>1;
219 }
220 sets |= (sets<<1); // Smear 1 lo-bit into a set
221 if (size > 2) {
222 sets |= (sets<<2); // Smear 2 lo-bits into a set
223 if (size > 4) {
224 sets |= (sets<<4); // Smear 4 lo-bits into a set
225 if (size > 8) {
226 sets |= (sets<<8); // Smear 8 lo-bits into a set
227 }
228 }
229 }
230 _A[i] = sets;
231 }
232 assert(is_aligned_sets(size), "mask is not aligned, adjacent sets");
233}
234
235// Assert that the register mask contains only bit sets.
236bool RegMask::is_aligned_sets(const int size) const {
237 if (size == 1) return true;
238 assert(2 <= size && size <= 16, "update low bits table");
239 assert(is_power_of_2(size), "sanity");
240 int low_bits_mask = low_bits[size>>2];
241 assert(valid_watermarks(), "sanity");
242 for (int i = _lwm; i <= _hwm; i++) {
243 int bits = _A[i];
244 while (bits) { // Check bits for pairing
245 int bit = bits & -bits; // Extract low bit
246 // Low bit is not odd means its mis-aligned.
247 if ((bit & low_bits_mask) == 0) return false;
248 // Do extra work since (bit << size) may overflow.
249 int hi_bit = bit << (size-1); // high bit
250 int set = hi_bit + ((hi_bit-1) & ~(bit-1));
251 // Check for aligned adjacent bits in this set
252 if ((bits & set) != set) return false;
253 bits -= set; // Remove this set
254 }
255 }
256 return true;
257}
258
259// Return TRUE if the mask contains one adjacent set of bits and no other bits.
260// Works also for size 1.
261int RegMask::is_bound_set(const int size) const {
262 if (is_AllStack()) return false;
263 assert(1 <= size && size <= 16, "update low bits table");
264 assert(valid_watermarks(), "sanity");
265 int bit = -1; // Set to hold the one bit allowed
266 for (int i = _lwm; i <= _hwm; i++) {
267 if (_A[i] ) { // Found some bits
268 if (bit != -1)
269 return false; // Already had bits, so fail
270 bit = _A[i] & -_A[i]; // Extract low bit from mask
271 int hi_bit = bit << (size-1); // high bit
272 if (hi_bit != 0) { // Bit set stays in same word?
273 int set = hi_bit + ((hi_bit-1) & ~(bit-1));
274 if (set != _A[i])
275 return false; // Require adjacent bit set and no more bits
276 } else { // Else its a split-set case
277 if (((-1) & ~(bit-1)) != _A[i])
278 return false; // Found many bits, so fail
279 i++; // Skip iteration forward and check high part
280 // The lower (32-size) bits should be 0 since it is split case.
281 int clear_bit_size = 32-size;
282 int shift_back_size = 32-clear_bit_size;
283 int set = bit>>clear_bit_size;
284 set = set & -set; // Remove sign extension.
285 set = (((set << size) - 1) >> shift_back_size);
286 if (i > _hwm || _A[i] != set)
287 return false; // Require expected low bits in next word
288 }
289 }
290 }
291 // True for both the empty mask and for a bit set
292 return true;
293}
294
295// UP means register only, Register plus stack, or stack only is DOWN
296bool RegMask::is_UP() const {
297 // Quick common case check for DOWN (any stack slot is legal)
298 if (is_AllStack())
299 return false;
300 // Slower check for any stack bits set (also DOWN)
301 if (overlap(Matcher::STACK_ONLY_mask))
302 return false;
303 // Not DOWN, so must be UP
304 return true;
305}
306
307// Compute size of register mask in bits
308uint RegMask::Size() const {
309 uint sum = 0;
310 assert(valid_watermarks(), "sanity");
311 for (int i = _lwm; i <= _hwm; i++) {
312 sum += population_count(_A[i]);
313 }
314 return sum;
315}
316
317#ifndef PRODUCT
318void RegMask::dump(outputStream *st) const {
319 st->print("[");
320 RegMask rm = *this; // Structure copy into local temp
321
322 OptoReg::Name start = rm.find_first_elem(); // Get a register
323 if (OptoReg::is_valid(start)) { // Check for empty mask
324 rm.Remove(start); // Yank from mask
325 OptoReg::dump(start, st); // Print register
326 OptoReg::Name last = start;
327
328 // Now I have printed an initial register.
329 // Print adjacent registers as "rX-rZ" instead of "rX,rY,rZ".
330 // Begin looping over the remaining registers.
331 while (1) { //
332 OptoReg::Name reg = rm.find_first_elem(); // Get a register
333 if (!OptoReg::is_valid(reg))
334 break; // Empty mask, end loop
335 rm.Remove(reg); // Yank from mask
336
337 if (last+1 == reg) { // See if they are adjacent
338 // Adjacent registers just collect into long runs, no printing.
339 last = reg;
340 } else { // Ending some kind of run
341 if (start == last) { // 1-register run; no special printing
342 } else if (start+1 == last) {
343 st->print(","); // 2-register run; print as "rX,rY"
344 OptoReg::dump(last, st);
345 } else { // Multi-register run; print as "rX-rZ"
346 st->print("-");
347 OptoReg::dump(last, st);
348 }
349 st->print(","); // Seperate start of new run
350 start = last = reg; // Start a new register run
351 OptoReg::dump(start, st); // Print register
352 } // End of if ending a register run or not
353 } // End of while regmask not empty
354
355 if (start == last) { // 1-register run; no special printing
356 } else if (start+1 == last) {
357 st->print(","); // 2-register run; print as "rX,rY"
358 OptoReg::dump(last, st);
359 } else { // Multi-register run; print as "rX-rZ"
360 st->print("-");
361 OptoReg::dump(last, st);
362 }
363 if (rm.is_AllStack()) st->print("...");
364 }
365 st->print("]");
366}
367#endif
368