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

    36 int 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

    65 int 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

    96 void 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 //=============================================================================

   110 const RegMask RegMask::Empty(

   111 # define BODY(I) 0,

   112   FORALL_BODY

   113 # undef BODY

   114   0

   115 );

   116 

   117 //=============================================================================

   118 bool 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 

   123 int 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.

   146 OptoReg::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

   160 void 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

   172 void 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-------------------------------

   183 bool 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

   202 int 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.

   218 int 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.

   242 static 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.

   247 OptoReg::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

   261 void 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

   289 void 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--------------------------------

   317 bool 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.

   343 int 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

   378 bool 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

   391 uint 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------------------------------------------

   405 void 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