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