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