1 /*
   2  * Copyright (c) 1997, 2022, 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 "memory/allocation.inline.hpp"
  27 #include "opto/addnode.hpp"
  28 #include "opto/connode.hpp"
  29 #include "opto/convertnode.hpp"
  30 #include "opto/memnode.hpp"
  31 #include "opto/mulnode.hpp"
  32 #include "opto/phaseX.hpp"
  33 #include "opto/subnode.hpp"
  34 #include "utilities/powerOfTwo.hpp"
  35 
  36 // Portions of code courtesy of Clifford Click
  37 
  38 
  39 //=============================================================================
  40 //------------------------------hash-------------------------------------------
  41 // Hash function over MulNodes.  Needs to be commutative; i.e., I swap
  42 // (commute) inputs to MulNodes willy-nilly so the hash function must return
  43 // the same value in the presence of edge swapping.
  44 uint MulNode::hash() const {
  45   return (uintptr_t)in(1) + (uintptr_t)in(2) + Opcode();
  46 }
  47 
  48 //------------------------------Identity---------------------------------------
  49 // Multiplying a one preserves the other argument
  50 Node* MulNode::Identity(PhaseGVN* phase) {
  51   const Type *one = mul_id();  // The multiplicative identity
  52   if( phase->type( in(1) )->higher_equal( one ) ) return in(2);
  53   if( phase->type( in(2) )->higher_equal( one ) ) return in(1);
  54 
  55   return this;
  56 }
  57 
  58 //------------------------------Ideal------------------------------------------
  59 // We also canonicalize the Node, moving constants to the right input,
  60 // and flatten expressions (so that 1+x+2 becomes x+3).
  61 Node *MulNode::Ideal(PhaseGVN *phase, bool can_reshape) {
  62   Node* in1 = in(1);
  63   Node* in2 = in(2);
  64   Node* progress = NULL;        // Progress flag
  65 
  66   // This code is used by And nodes too, but some conversions are
  67   // only valid for the actual Mul nodes.
  68   uint op = Opcode();
  69   bool real_mul = (op == Op_MulI) || (op == Op_MulL) ||
  70                   (op == Op_MulF) || (op == Op_MulD);
  71 
  72   // Convert "(-a)*(-b)" into "a*b".
  73   if (real_mul && in1->is_Sub() && in2->is_Sub()) {
  74     if (phase->type(in1->in(1))->is_zero_type() &&
  75         phase->type(in2->in(1))->is_zero_type()) {
  76       set_req(1, in1->in(2));
  77       set_req(2, in2->in(2));
  78       PhaseIterGVN* igvn = phase->is_IterGVN();
  79       if (igvn) {
  80         igvn->_worklist.push(in1);
  81         igvn->_worklist.push(in2);
  82       }
  83       in1 = in(1);
  84       in2 = in(2);
  85       progress = this;
  86     }
  87   }
  88 
  89   // convert "max(a,b) * min(a,b)" into "a*b".
  90   if ((in(1)->Opcode() == max_opcode() && in(2)->Opcode() == min_opcode())
  91       || (in(1)->Opcode() == min_opcode() && in(2)->Opcode() == max_opcode())) {
  92     Node *in11 = in(1)->in(1);
  93     Node *in12 = in(1)->in(2);
  94 
  95     Node *in21 = in(2)->in(1);
  96     Node *in22 = in(2)->in(2);
  97 
  98     if ((in11 == in21 && in12 == in22) ||
  99         (in11 == in22 && in12 == in21)) {
 100       set_req(1, in11);
 101       set_req(2, in12);
 102       PhaseIterGVN* igvn = phase->is_IterGVN();
 103       if (igvn) {
 104         igvn->_worklist.push(in1);
 105         igvn->_worklist.push(in2);
 106       }
 107       in1 = in(1);
 108       in2 = in(2);
 109       progress = this;
 110     }
 111   }
 112 
 113   const Type* t1 = phase->type(in1);
 114   const Type* t2 = phase->type(in2);
 115 
 116   // We are OK if right is a constant, or right is a load and
 117   // left is a non-constant.
 118   if( !(t2->singleton() ||
 119         (in(2)->is_Load() && !(t1->singleton() || in(1)->is_Load())) ) ) {
 120     if( t1->singleton() ||       // Left input is a constant?
 121         // Otherwise, sort inputs (commutativity) to help value numbering.
 122         (in(1)->_idx > in(2)->_idx) ) {
 123       swap_edges(1, 2);
 124       const Type *t = t1;
 125       t1 = t2;
 126       t2 = t;
 127       progress = this;            // Made progress
 128     }
 129   }
 130 
 131   // If the right input is a constant, and the left input is a product of a
 132   // constant, flatten the expression tree.
 133   if( t2->singleton() &&        // Right input is a constant?
 134       op != Op_MulF &&          // Float & double cannot reassociate
 135       op != Op_MulD ) {
 136     if( t2 == Type::TOP ) return NULL;
 137     Node *mul1 = in(1);
 138 #ifdef ASSERT
 139     // Check for dead loop
 140     int op1 = mul1->Opcode();
 141     if ((mul1 == this) || (in(2) == this) ||
 142         ((op1 == mul_opcode() || op1 == add_opcode()) &&
 143          ((mul1->in(1) == this) || (mul1->in(2) == this) ||
 144           (mul1->in(1) == mul1) || (mul1->in(2) == mul1)))) {
 145       assert(false, "dead loop in MulNode::Ideal");
 146     }
 147 #endif
 148 
 149     if( mul1->Opcode() == mul_opcode() ) {  // Left input is a multiply?
 150       // Mul of a constant?
 151       const Type *t12 = phase->type( mul1->in(2) );
 152       if( t12->singleton() && t12 != Type::TOP) { // Left input is an add of a constant?
 153         // Compute new constant; check for overflow
 154         const Type *tcon01 = ((MulNode*)mul1)->mul_ring(t2,t12);
 155         if( tcon01->singleton() ) {
 156           // The Mul of the flattened expression
 157           set_req_X(1, mul1->in(1), phase);
 158           set_req_X(2, phase->makecon(tcon01), phase);
 159           t2 = tcon01;
 160           progress = this;      // Made progress
 161         }
 162       }
 163     }
 164     // If the right input is a constant, and the left input is an add of a
 165     // constant, flatten the tree: (X+con1)*con0 ==> X*con0 + con1*con0
 166     const Node *add1 = in(1);
 167     if( add1->Opcode() == add_opcode() ) {      // Left input is an add?
 168       // Add of a constant?
 169       const Type *t12 = phase->type( add1->in(2) );
 170       if( t12->singleton() && t12 != Type::TOP ) { // Left input is an add of a constant?
 171         assert( add1->in(1) != add1, "dead loop in MulNode::Ideal" );
 172         // Compute new constant; check for overflow
 173         const Type *tcon01 = mul_ring(t2,t12);
 174         if( tcon01->singleton() ) {
 175 
 176         // Convert (X+con1)*con0 into X*con0
 177           Node *mul = clone();    // mul = ()*con0
 178           mul->set_req(1,add1->in(1));  // mul = X*con0
 179           mul = phase->transform(mul);
 180 
 181           Node *add2 = add1->clone();
 182           add2->set_req(1, mul);        // X*con0 + con0*con1
 183           add2->set_req(2, phase->makecon(tcon01) );
 184           progress = add2;
 185         }
 186       }
 187     } // End of is left input an add
 188   } // End of is right input a Mul
 189 
 190   return progress;
 191 }
 192 
 193 //------------------------------Value-----------------------------------------
 194 const Type* MulNode::Value(PhaseGVN* phase) const {
 195   const Type *t1 = phase->type( in(1) );
 196   const Type *t2 = phase->type( in(2) );
 197   // Either input is TOP ==> the result is TOP
 198   if( t1 == Type::TOP ) return Type::TOP;
 199   if( t2 == Type::TOP ) return Type::TOP;
 200 
 201   // Either input is ZERO ==> the result is ZERO.
 202   // Not valid for floats or doubles since +0.0 * -0.0 --> +0.0
 203   int op = Opcode();
 204   if( op == Op_MulI || op == Op_AndI || op == Op_MulL || op == Op_AndL ) {
 205     const Type *zero = add_id();        // The multiplicative zero
 206     if( t1->higher_equal( zero ) ) return zero;
 207     if( t2->higher_equal( zero ) ) return zero;
 208   }
 209 
 210   // Code pattern on return from a call that returns an __Value.  Can
 211   // be optimized away if the return value turns out to be an oop.
 212   if (op == Op_AndX &&
 213       in(1) != NULL &&
 214       in(1)->Opcode() == Op_CastP2X &&
 215       in(1)->in(1) != NULL &&
 216       phase->type(in(1)->in(1))->isa_oopptr() &&
 217       t2->isa_intptr_t()->_lo >= 0 &&
 218       t2->isa_intptr_t()->_hi <= MinObjAlignmentInBytesMask) {
 219     return add_id();
 220   }
 221 
 222   // Either input is BOTTOM ==> the result is the local BOTTOM
 223   if( t1 == Type::BOTTOM || t2 == Type::BOTTOM )
 224     return bottom_type();
 225 
 226 #if defined(IA32)
 227   // Can't trust native compilers to properly fold strict double
 228   // multiplication with round-to-zero on this platform.
 229   if (op == Op_MulD) {
 230     return TypeD::DOUBLE;
 231   }
 232 #endif
 233 
 234   return mul_ring(t1,t2);            // Local flavor of type multiplication
 235 }
 236 
 237 MulNode* MulNode::make(Node* in1, Node* in2, BasicType bt) {
 238   switch (bt) {
 239     case T_INT:
 240       return new MulINode(in1, in2);
 241     case T_LONG:
 242       return new MulLNode(in1, in2);
 243     default:
 244       fatal("Not implemented for %s", type2name(bt));
 245   }
 246   return NULL;
 247 }
 248 
 249 
 250 //=============================================================================
 251 //------------------------------Ideal------------------------------------------
 252 // Check for power-of-2 multiply, then try the regular MulNode::Ideal
 253 Node *MulINode::Ideal(PhaseGVN *phase, bool can_reshape) {
 254   // Swap constant to right
 255   jint con;
 256   if ((con = in(1)->find_int_con(0)) != 0) {
 257     swap_edges(1, 2);
 258     // Finish rest of method to use info in 'con'
 259   } else if ((con = in(2)->find_int_con(0)) == 0) {
 260     return MulNode::Ideal(phase, can_reshape);
 261   }
 262 
 263   // Now we have a constant Node on the right and the constant in con
 264   if (con == 0) return NULL;   // By zero is handled by Value call
 265   if (con == 1) return NULL;   // By one  is handled by Identity call
 266 
 267   // Check for negative constant; if so negate the final result
 268   bool sign_flip = false;
 269 
 270   unsigned int abs_con = uabs(con);
 271   if (abs_con != (unsigned int)con) {
 272     sign_flip = true;
 273   }
 274 
 275   // Get low bit; check for being the only bit
 276   Node *res = NULL;
 277   unsigned int bit1 = abs_con & (0-abs_con);       // Extract low bit
 278   if (bit1 == abs_con) {           // Found a power of 2?
 279     res = new LShiftINode(in(1), phase->intcon(log2i_exact(bit1)));
 280   } else {
 281     // Check for constant with 2 bits set
 282     unsigned int bit2 = abs_con - bit1;
 283     bit2 = bit2 & (0 - bit2);          // Extract 2nd bit
 284     if (bit2 + bit1 == abs_con) {    // Found all bits in con?
 285       Node *n1 = phase->transform(new LShiftINode(in(1), phase->intcon(log2i_exact(bit1))));
 286       Node *n2 = phase->transform(new LShiftINode(in(1), phase->intcon(log2i_exact(bit2))));
 287       res = new AddINode(n2, n1);
 288     } else if (is_power_of_2(abs_con + 1)) {
 289       // Sleezy: power-of-2 - 1.  Next time be generic.
 290       unsigned int temp = abs_con + 1;
 291       Node *n1 = phase->transform(new LShiftINode(in(1), phase->intcon(log2i_exact(temp))));
 292       res = new SubINode(n1, in(1));
 293     } else {
 294       return MulNode::Ideal(phase, can_reshape);
 295     }
 296   }
 297 
 298   if (sign_flip) {             // Need to negate result?
 299     res = phase->transform(res);// Transform, before making the zero con
 300     res = new SubINode(phase->intcon(0),res);
 301   }
 302 
 303   return res;                   // Return final result
 304 }
 305 
 306 //------------------------------mul_ring---------------------------------------
 307 // Compute the product type of two integer ranges into this node.
 308 const Type *MulINode::mul_ring(const Type *t0, const Type *t1) const {
 309   const TypeInt *r0 = t0->is_int(); // Handy access
 310   const TypeInt *r1 = t1->is_int();
 311 
 312   // Fetch endpoints of all ranges
 313   jint lo0 = r0->_lo;
 314   double a = (double)lo0;
 315   jint hi0 = r0->_hi;
 316   double b = (double)hi0;
 317   jint lo1 = r1->_lo;
 318   double c = (double)lo1;
 319   jint hi1 = r1->_hi;
 320   double d = (double)hi1;
 321 
 322   // Compute all endpoints & check for overflow
 323   int32_t A = java_multiply(lo0, lo1);
 324   if( (double)A != a*c ) return TypeInt::INT; // Overflow?
 325   int32_t B = java_multiply(lo0, hi1);
 326   if( (double)B != a*d ) return TypeInt::INT; // Overflow?
 327   int32_t C = java_multiply(hi0, lo1);
 328   if( (double)C != b*c ) return TypeInt::INT; // Overflow?
 329   int32_t D = java_multiply(hi0, hi1);
 330   if( (double)D != b*d ) return TypeInt::INT; // Overflow?
 331 
 332   if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints
 333   else { lo0 = B; hi0 = A; }
 334   if( C < D ) {
 335     if( C < lo0 ) lo0 = C;
 336     if( D > hi0 ) hi0 = D;
 337   } else {
 338     if( D < lo0 ) lo0 = D;
 339     if( C > hi0 ) hi0 = C;
 340   }
 341   return TypeInt::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));
 342 }
 343 
 344 
 345 //=============================================================================
 346 //------------------------------Ideal------------------------------------------
 347 // Check for power-of-2 multiply, then try the regular MulNode::Ideal
 348 Node *MulLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 349   // Swap constant to right
 350   jlong con;
 351   if ((con = in(1)->find_long_con(0)) != 0) {
 352     swap_edges(1, 2);
 353     // Finish rest of method to use info in 'con'
 354   } else if ((con = in(2)->find_long_con(0)) == 0) {
 355     return MulNode::Ideal(phase, can_reshape);
 356   }
 357 
 358   // Now we have a constant Node on the right and the constant in con
 359   if (con == CONST64(0)) return NULL;  // By zero is handled by Value call
 360   if (con == CONST64(1)) return NULL;  // By one  is handled by Identity call
 361 
 362   // Check for negative constant; if so negate the final result
 363   bool sign_flip = false;
 364   julong abs_con = uabs(con);
 365   if (abs_con != (julong)con) {
 366     sign_flip = true;
 367   }
 368 
 369   // Get low bit; check for being the only bit
 370   Node *res = NULL;
 371   julong bit1 = abs_con & (0-abs_con);      // Extract low bit
 372   if (bit1 == abs_con) {           // Found a power of 2?
 373     res = new LShiftLNode(in(1), phase->intcon(log2i_exact(bit1)));
 374   } else {
 375 
 376     // Check for constant with 2 bits set
 377     julong bit2 = abs_con-bit1;
 378     bit2 = bit2 & (0-bit2);          // Extract 2nd bit
 379     if (bit2 + bit1 == abs_con) {    // Found all bits in con?
 380       Node *n1 = phase->transform(new LShiftLNode(in(1), phase->intcon(log2i_exact(bit1))));
 381       Node *n2 = phase->transform(new LShiftLNode(in(1), phase->intcon(log2i_exact(bit2))));
 382       res = new AddLNode(n2, n1);
 383 
 384     } else if (is_power_of_2(abs_con+1)) {
 385       // Sleezy: power-of-2 -1.  Next time be generic.
 386       julong temp = abs_con + 1;
 387       Node *n1 = phase->transform( new LShiftLNode(in(1), phase->intcon(log2i_exact(temp))));
 388       res = new SubLNode(n1, in(1));
 389     } else {
 390       return MulNode::Ideal(phase, can_reshape);
 391     }
 392   }
 393 
 394   if (sign_flip) {             // Need to negate result?
 395     res = phase->transform(res);// Transform, before making the zero con
 396     res = new SubLNode(phase->longcon(0),res);
 397   }
 398 
 399   return res;                   // Return final result
 400 }
 401 
 402 //------------------------------mul_ring---------------------------------------
 403 // Compute the product type of two integer ranges into this node.
 404 const Type *MulLNode::mul_ring(const Type *t0, const Type *t1) const {
 405   const TypeLong *r0 = t0->is_long(); // Handy access
 406   const TypeLong *r1 = t1->is_long();
 407 
 408   // Fetch endpoints of all ranges
 409   jlong lo0 = r0->_lo;
 410   double a = (double)lo0;
 411   jlong hi0 = r0->_hi;
 412   double b = (double)hi0;
 413   jlong lo1 = r1->_lo;
 414   double c = (double)lo1;
 415   jlong hi1 = r1->_hi;
 416   double d = (double)hi1;
 417 
 418   // Compute all endpoints & check for overflow
 419   jlong A = java_multiply(lo0, lo1);
 420   if( (double)A != a*c ) return TypeLong::LONG; // Overflow?
 421   jlong B = java_multiply(lo0, hi1);
 422   if( (double)B != a*d ) return TypeLong::LONG; // Overflow?
 423   jlong C = java_multiply(hi0, lo1);
 424   if( (double)C != b*c ) return TypeLong::LONG; // Overflow?
 425   jlong D = java_multiply(hi0, hi1);
 426   if( (double)D != b*d ) return TypeLong::LONG; // Overflow?
 427 
 428   if( A < B ) { lo0 = A; hi0 = B; } // Sort range endpoints
 429   else { lo0 = B; hi0 = A; }
 430   if( C < D ) {
 431     if( C < lo0 ) lo0 = C;
 432     if( D > hi0 ) hi0 = D;
 433   } else {
 434     if( D < lo0 ) lo0 = D;
 435     if( C > hi0 ) hi0 = C;
 436   }
 437   return TypeLong::make(lo0, hi0, MAX2(r0->_widen,r1->_widen));
 438 }
 439 
 440 //=============================================================================
 441 //------------------------------mul_ring---------------------------------------
 442 // Compute the product type of two double ranges into this node.
 443 const Type *MulFNode::mul_ring(const Type *t0, const Type *t1) const {
 444   if( t0 == Type::FLOAT || t1 == Type::FLOAT ) return Type::FLOAT;
 445   return TypeF::make( t0->getf() * t1->getf() );
 446 }
 447 
 448 //=============================================================================
 449 //------------------------------mul_ring---------------------------------------
 450 // Compute the product type of two double ranges into this node.
 451 const Type *MulDNode::mul_ring(const Type *t0, const Type *t1) const {
 452   if( t0 == Type::DOUBLE || t1 == Type::DOUBLE ) return Type::DOUBLE;
 453   // We must be multiplying 2 double constants.
 454   return TypeD::make( t0->getd() * t1->getd() );
 455 }
 456 
 457 //=============================================================================
 458 //------------------------------Value------------------------------------------
 459 const Type* MulHiLNode::Value(PhaseGVN* phase) const {
 460   const Type *t1 = phase->type( in(1) );
 461   const Type *t2 = phase->type( in(2) );
 462   const Type *bot = bottom_type();
 463   return MulHiValue(t1, t2, bot);
 464 }
 465 
 466 const Type* UMulHiLNode::Value(PhaseGVN* phase) const {
 467   const Type *t1 = phase->type( in(1) );
 468   const Type *t2 = phase->type( in(2) );
 469   const Type *bot = bottom_type();
 470   return MulHiValue(t1, t2, bot);
 471 }
 472 
 473 // A common routine used by UMulHiLNode and MulHiLNode
 474 const Type* MulHiValue(const Type *t1, const Type *t2, const Type *bot) {
 475   // Either input is TOP ==> the result is TOP
 476   if( t1 == Type::TOP ) return Type::TOP;
 477   if( t2 == Type::TOP ) return Type::TOP;
 478 
 479   // Either input is BOTTOM ==> the result is the local BOTTOM
 480   if( (t1 == bot) || (t2 == bot) ||
 481       (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
 482     return bot;
 483 
 484   // It is not worth trying to constant fold this stuff!
 485   return TypeLong::LONG;
 486 }
 487 
 488 //=============================================================================
 489 //------------------------------mul_ring---------------------------------------
 490 // Supplied function returns the product of the inputs IN THE CURRENT RING.
 491 // For the logical operations the ring's MUL is really a logical AND function.
 492 // This also type-checks the inputs for sanity.  Guaranteed never to
 493 // be passed a TOP or BOTTOM type, these are filtered out by pre-check.
 494 const Type *AndINode::mul_ring( const Type *t0, const Type *t1 ) const {
 495   const TypeInt *r0 = t0->is_int(); // Handy access
 496   const TypeInt *r1 = t1->is_int();
 497   int widen = MAX2(r0->_widen,r1->_widen);
 498 
 499   // If either input is a constant, might be able to trim cases
 500   if( !r0->is_con() && !r1->is_con() )
 501     return TypeInt::INT;        // No constants to be had
 502 
 503   // Both constants?  Return bits
 504   if( r0->is_con() && r1->is_con() )
 505     return TypeInt::make( r0->get_con() & r1->get_con() );
 506 
 507   if( r0->is_con() && r0->get_con() > 0 )
 508     return TypeInt::make(0, r0->get_con(), widen);
 509 
 510   if( r1->is_con() && r1->get_con() > 0 )
 511     return TypeInt::make(0, r1->get_con(), widen);
 512 
 513   if( r0 == TypeInt::BOOL || r1 == TypeInt::BOOL ) {
 514     return TypeInt::BOOL;
 515   }
 516 
 517   return TypeInt::INT;          // No constants to be had
 518 }
 519 
 520 const Type* AndINode::Value(PhaseGVN* phase) const {
 521   // patterns similar to (v << 2) & 3
 522   if (AndIL_shift_and_mask_is_always_zero(phase, in(1), in(2), T_INT, true)) {
 523     return TypeInt::ZERO;
 524   }
 525 
 526   return MulNode::Value(phase);
 527 }
 528 
 529 //------------------------------Identity---------------------------------------
 530 // Masking off the high bits of an unsigned load is not required
 531 Node* AndINode::Identity(PhaseGVN* phase) {
 532 
 533   // x & x => x
 534   if (in(1) == in(2)) {
 535     return in(1);
 536   }
 537 
 538   Node* in1 = in(1);
 539   uint op = in1->Opcode();
 540   const TypeInt* t2 = phase->type(in(2))->isa_int();
 541   if (t2 && t2->is_con()) {
 542     int con = t2->get_con();
 543     // Masking off high bits which are always zero is useless.
 544     const TypeInt* t1 = phase->type(in(1))->isa_int();
 545     if (t1 != NULL && t1->_lo >= 0) {
 546       jint t1_support = right_n_bits(1 + log2i_graceful(t1->_hi));
 547       if ((t1_support & con) == t1_support)
 548         return in1;
 549     }
 550     // Masking off the high bits of a unsigned-shift-right is not
 551     // needed either.
 552     if (op == Op_URShiftI) {
 553       const TypeInt* t12 = phase->type(in1->in(2))->isa_int();
 554       if (t12 && t12->is_con()) {  // Shift is by a constant
 555         int shift = t12->get_con();
 556         shift &= BitsPerJavaInteger - 1;  // semantics of Java shifts
 557         int mask = max_juint >> shift;
 558         if ((mask & con) == mask)  // If AND is useless, skip it
 559           return in1;
 560       }
 561     }
 562   }
 563   return MulNode::Identity(phase);
 564 }
 565 
 566 //------------------------------Ideal------------------------------------------
 567 Node *AndINode::Ideal(PhaseGVN *phase, bool can_reshape) {
 568   // pattern similar to (v1 + (v2 << 2)) & 3 transformed to v1 & 3
 569   Node* progress = AndIL_add_shift_and_mask(phase, T_INT);
 570   if (progress != NULL) {
 571     return progress;
 572   }
 573 
 574   // Special case constant AND mask
 575   const TypeInt *t2 = phase->type( in(2) )->isa_int();
 576   if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape);
 577   const int mask = t2->get_con();
 578   Node *load = in(1);
 579   uint lop = load->Opcode();
 580 
 581   // Masking bits off of a Character?  Hi bits are already zero.
 582   if( lop == Op_LoadUS &&
 583       (mask & 0xFFFF0000) )     // Can we make a smaller mask?
 584     return new AndINode(load,phase->intcon(mask&0xFFFF));
 585 
 586   // Masking bits off of a Short?  Loading a Character does some masking
 587   if (can_reshape &&
 588       load->outcnt() == 1 && load->unique_out() == this) {
 589     if (lop == Op_LoadS && (mask & 0xFFFF0000) == 0 ) {
 590       Node* ldus = load->as_Load()->convert_to_unsigned_load(*phase);
 591       ldus = phase->transform(ldus);
 592       return new AndINode(ldus, phase->intcon(mask & 0xFFFF));
 593     }
 594 
 595     // Masking sign bits off of a Byte?  Do an unsigned byte load plus
 596     // an and.
 597     if (lop == Op_LoadB && (mask & 0xFFFFFF00) == 0) {
 598       Node* ldub = load->as_Load()->convert_to_unsigned_load(*phase);
 599       ldub = phase->transform(ldub);
 600       return new AndINode(ldub, phase->intcon(mask));
 601     }
 602   }
 603 
 604   // Masking off sign bits?  Dont make them!
 605   if( lop == Op_RShiftI ) {
 606     const TypeInt *t12 = phase->type(load->in(2))->isa_int();
 607     if( t12 && t12->is_con() ) { // Shift is by a constant
 608       int shift = t12->get_con();
 609       shift &= BitsPerJavaInteger-1;  // semantics of Java shifts
 610       const int sign_bits_mask = ~right_n_bits(BitsPerJavaInteger - shift);
 611       // If the AND'ing of the 2 masks has no bits, then only original shifted
 612       // bits survive.  NO sign-extension bits survive the maskings.
 613       if( (sign_bits_mask & mask) == 0 ) {
 614         // Use zero-fill shift instead
 615         Node *zshift = phase->transform(new URShiftINode(load->in(1),load->in(2)));
 616         return new AndINode( zshift, in(2) );
 617       }
 618     }
 619   }
 620 
 621   // Check for 'negate/and-1', a pattern emitted when someone asks for
 622   // 'mod 2'.  Negate leaves the low order bit unchanged (think: complement
 623   // plus 1) and the mask is of the low order bit.  Skip the negate.
 624   if( lop == Op_SubI && mask == 1 && load->in(1) &&
 625       phase->type(load->in(1)) == TypeInt::ZERO )
 626     return new AndINode( load->in(2), in(2) );
 627 
 628   return MulNode::Ideal(phase, can_reshape);
 629 }
 630 
 631 //=============================================================================
 632 //------------------------------mul_ring---------------------------------------
 633 // Supplied function returns the product of the inputs IN THE CURRENT RING.
 634 // For the logical operations the ring's MUL is really a logical AND function.
 635 // This also type-checks the inputs for sanity.  Guaranteed never to
 636 // be passed a TOP or BOTTOM type, these are filtered out by pre-check.
 637 const Type *AndLNode::mul_ring( const Type *t0, const Type *t1 ) const {
 638   const TypeLong *r0 = t0->is_long(); // Handy access
 639   const TypeLong *r1 = t1->is_long();
 640   int widen = MAX2(r0->_widen,r1->_widen);
 641 
 642   // If either input is a constant, might be able to trim cases
 643   if( !r0->is_con() && !r1->is_con() )
 644     return TypeLong::LONG;      // No constants to be had
 645 
 646   // Both constants?  Return bits
 647   if( r0->is_con() && r1->is_con() )
 648     return TypeLong::make( r0->get_con() & r1->get_con() );
 649 
 650   if( r0->is_con() && r0->get_con() > 0 )
 651     return TypeLong::make(CONST64(0), r0->get_con(), widen);
 652 
 653   if( r1->is_con() && r1->get_con() > 0 )
 654     return TypeLong::make(CONST64(0), r1->get_con(), widen);
 655 
 656   return TypeLong::LONG;        // No constants to be had
 657 }
 658 
 659 const Type* AndLNode::Value(PhaseGVN* phase) const {
 660   // patterns similar to (v << 2) & 3
 661   if (AndIL_shift_and_mask_is_always_zero(phase, in(1), in(2), T_LONG, true)) {
 662     return TypeLong::ZERO;
 663   }
 664 
 665   return MulNode::Value(phase);
 666 }
 667 
 668 //------------------------------Identity---------------------------------------
 669 // Masking off the high bits of an unsigned load is not required
 670 Node* AndLNode::Identity(PhaseGVN* phase) {
 671 
 672   // x & x => x
 673   if (in(1) == in(2)) {
 674     return in(1);
 675   }
 676 
 677   Node *usr = in(1);
 678   const TypeLong *t2 = phase->type( in(2) )->isa_long();
 679   if( t2 && t2->is_con() ) {
 680     jlong con = t2->get_con();
 681     // Masking off high bits which are always zero is useless.
 682     const TypeLong* t1 = phase->type( in(1) )->isa_long();
 683     if (t1 != NULL && t1->_lo >= 0) {
 684       int bit_count = log2i_graceful(t1->_hi) + 1;
 685       jlong t1_support = jlong(max_julong >> (BitsPerJavaLong - bit_count));
 686       if ((t1_support & con) == t1_support)
 687         return usr;
 688     }
 689     uint lop = usr->Opcode();
 690     // Masking off the high bits of a unsigned-shift-right is not
 691     // needed either.
 692     if( lop == Op_URShiftL ) {
 693       const TypeInt *t12 = phase->type( usr->in(2) )->isa_int();
 694       if( t12 && t12->is_con() ) {  // Shift is by a constant
 695         int shift = t12->get_con();
 696         shift &= BitsPerJavaLong - 1;  // semantics of Java shifts
 697         jlong mask = max_julong >> shift;
 698         if( (mask&con) == mask )  // If AND is useless, skip it
 699           return usr;
 700       }
 701     }
 702 
 703     // Check if this is part of an inline type test
 704     if (con == markWord::inline_type_pattern && in(1)->is_Load() &&
 705         phase->type(in(1)->in(MemNode::Address))->is_inlinetypeptr() &&
 706         phase->type(in(1)->in(MemNode::Address))->is_ptr()->offset() == oopDesc::mark_offset_in_bytes()) {
 707       assert(EnableValhalla, "should only be used for inline types");
 708       return in(2); // Obj is known to be an inline type
 709     }
 710   }
 711   return MulNode::Identity(phase);
 712 }
 713 
 714 //------------------------------Ideal------------------------------------------
 715 Node *AndLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 716   // pattern similar to (v1 + (v2 << 2)) & 3 transformed to v1 & 3
 717   Node* progress = AndIL_add_shift_and_mask(phase, T_LONG);
 718   if (progress != NULL) {
 719     return progress;
 720   }
 721 
 722   // Special case constant AND mask
 723   const TypeLong *t2 = phase->type( in(2) )->isa_long();
 724   if( !t2 || !t2->is_con() ) return MulNode::Ideal(phase, can_reshape);
 725   const jlong mask = t2->get_con();
 726 
 727   Node* in1 = in(1);
 728   int op = in1->Opcode();
 729 
 730   // Are we masking a long that was converted from an int with a mask
 731   // that fits in 32-bits?  Commute them and use an AndINode.  Don't
 732   // convert masks which would cause a sign extension of the integer
 733   // value.  This check includes UI2L masks (0x00000000FFFFFFFF) which
 734   // would be optimized away later in Identity.
 735   if (op == Op_ConvI2L && (mask & UCONST64(0xFFFFFFFF80000000)) == 0) {
 736     Node* andi = new AndINode(in1->in(1), phase->intcon(mask));
 737     andi = phase->transform(andi);
 738     return new ConvI2LNode(andi);
 739   }
 740 
 741   // Masking off sign bits?  Dont make them!
 742   if (op == Op_RShiftL) {
 743     const TypeInt* t12 = phase->type(in1->in(2))->isa_int();
 744     if( t12 && t12->is_con() ) { // Shift is by a constant
 745       int shift = t12->get_con();
 746       shift &= BitsPerJavaLong - 1;  // semantics of Java shifts
 747       const jlong sign_bits_mask = ~(((jlong)CONST64(1) << (jlong)(BitsPerJavaLong - shift)) -1);
 748       // If the AND'ing of the 2 masks has no bits, then only original shifted
 749       // bits survive.  NO sign-extension bits survive the maskings.
 750       if( (sign_bits_mask & mask) == 0 ) {
 751         // Use zero-fill shift instead
 752         Node *zshift = phase->transform(new URShiftLNode(in1->in(1), in1->in(2)));
 753         return new AndLNode(zshift, in(2));
 754       }
 755     }
 756   }
 757 
 758   return MulNode::Ideal(phase, can_reshape);
 759 }
 760 
 761 LShiftNode* LShiftNode::make(Node* in1, Node* in2, BasicType bt) {
 762   switch (bt) {
 763     case T_INT:
 764       return new LShiftINode(in1, in2);
 765     case T_LONG:
 766       return new LShiftLNode(in1, in2);
 767     default:
 768       fatal("Not implemented for %s", type2name(bt));
 769   }
 770   return NULL;
 771 }
 772 
 773 //=============================================================================
 774 
 775 static bool const_shift_count(PhaseGVN* phase, Node* shiftNode, int* count) {
 776   const TypeInt* tcount = phase->type(shiftNode->in(2))->isa_int();
 777   if (tcount != NULL && tcount->is_con()) {
 778     *count = tcount->get_con();
 779     return true;
 780   }
 781   return false;
 782 }
 783 
 784 static int maskShiftAmount(PhaseGVN* phase, Node* shiftNode, int nBits) {
 785   int count = 0;
 786   if (const_shift_count(phase, shiftNode, &count)) {
 787     int maskedShift = count & (nBits - 1);
 788     if (maskedShift == 0) {
 789       // Let Identity() handle 0 shift count.
 790       return 0;
 791     }
 792 
 793     if (count != maskedShift) {
 794       shiftNode->set_req(2, phase->intcon(maskedShift)); // Replace shift count with masked value.
 795       PhaseIterGVN* igvn = phase->is_IterGVN();
 796       if (igvn) {
 797         igvn->rehash_node_delayed(shiftNode);
 798       }
 799     }
 800     return maskedShift;
 801   }
 802   return 0;
 803 }
 804 
 805 //------------------------------Identity---------------------------------------
 806 Node* LShiftINode::Identity(PhaseGVN* phase) {
 807   int count = 0;
 808   if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaInteger - 1)) == 0) {
 809     // Shift by a multiple of 32 does nothing
 810     return in(1);
 811   }
 812   return this;
 813 }
 814 
 815 //------------------------------Ideal------------------------------------------
 816 // If the right input is a constant, and the left input is an add of a
 817 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0
 818 Node *LShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
 819   int con = maskShiftAmount(phase, this, BitsPerJavaInteger);
 820   if (con == 0) {
 821     return NULL;
 822   }
 823 
 824   // Left input is an add?
 825   Node *add1 = in(1);
 826   int add1_op = add1->Opcode();
 827   if( add1_op == Op_AddI ) {    // Left input is an add?
 828     assert( add1 != add1->in(1), "dead loop in LShiftINode::Ideal" );
 829 
 830     // Transform is legal, but check for profit.  Avoid breaking 'i2s'
 831     // and 'i2b' patterns which typically fold into 'StoreC/StoreB'.
 832     if( con < 16 ) {
 833       // Left input is an add of the same number?
 834       if (add1->in(1) == add1->in(2)) {
 835         // Convert "(x + x) << c0" into "x << (c0 + 1)"
 836         return new LShiftINode(add1->in(1), phase->intcon(con + 1));
 837       }
 838 
 839       // Left input is an add of a constant?
 840       const TypeInt *t12 = phase->type(add1->in(2))->isa_int();
 841       if( t12 && t12->is_con() ){ // Left input is an add of a con?
 842         // Compute X << con0
 843         Node *lsh = phase->transform( new LShiftINode( add1->in(1), in(2) ) );
 844         // Compute X<<con0 + (con1<<con0)
 845         return new AddINode( lsh, phase->intcon(t12->get_con() << con));
 846       }
 847     }
 848   }
 849 
 850   // Check for "(x>>c0)<<c0" which just masks off low bits
 851   if( (add1_op == Op_RShiftI || add1_op == Op_URShiftI ) &&
 852       add1->in(2) == in(2) )
 853     // Convert to "(x & -(1<<c0))"
 854     return new AndINode(add1->in(1),phase->intcon( -(1<<con)));
 855 
 856   // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits
 857   if( add1_op == Op_AndI ) {
 858     Node *add2 = add1->in(1);
 859     int add2_op = add2->Opcode();
 860     if( (add2_op == Op_RShiftI || add2_op == Op_URShiftI ) &&
 861         add2->in(2) == in(2) ) {
 862       // Convert to "(x & (Y<<c0))"
 863       Node *y_sh = phase->transform( new LShiftINode( add1->in(2), in(2) ) );
 864       return new AndINode( add2->in(1), y_sh );
 865     }
 866   }
 867 
 868   // Check for ((x & ((1<<(32-c0))-1)) << c0) which ANDs off high bits
 869   // before shifting them away.
 870   const jint bits_mask = right_n_bits(BitsPerJavaInteger-con);
 871   if( add1_op == Op_AndI &&
 872       phase->type(add1->in(2)) == TypeInt::make( bits_mask ) )
 873     return new LShiftINode( add1->in(1), in(2) );
 874 
 875   return NULL;
 876 }
 877 
 878 //------------------------------Value------------------------------------------
 879 // A LShiftINode shifts its input2 left by input1 amount.
 880 const Type* LShiftINode::Value(PhaseGVN* phase) const {
 881   const Type *t1 = phase->type( in(1) );
 882   const Type *t2 = phase->type( in(2) );
 883   // Either input is TOP ==> the result is TOP
 884   if( t1 == Type::TOP ) return Type::TOP;
 885   if( t2 == Type::TOP ) return Type::TOP;
 886 
 887   // Left input is ZERO ==> the result is ZERO.
 888   if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
 889   // Shift by zero does nothing
 890   if( t2 == TypeInt::ZERO ) return t1;
 891 
 892   // Either input is BOTTOM ==> the result is BOTTOM
 893   if( (t1 == TypeInt::INT) || (t2 == TypeInt::INT) ||
 894       (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
 895     return TypeInt::INT;
 896 
 897   const TypeInt *r1 = t1->is_int(); // Handy access
 898   const TypeInt *r2 = t2->is_int(); // Handy access
 899 
 900   if (!r2->is_con())
 901     return TypeInt::INT;
 902 
 903   uint shift = r2->get_con();
 904   shift &= BitsPerJavaInteger-1;  // semantics of Java shifts
 905   // Shift by a multiple of 32 does nothing:
 906   if (shift == 0)  return t1;
 907 
 908   // If the shift is a constant, shift the bounds of the type,
 909   // unless this could lead to an overflow.
 910   if (!r1->is_con()) {
 911     jint lo = r1->_lo, hi = r1->_hi;
 912     if (((lo << shift) >> shift) == lo &&
 913         ((hi << shift) >> shift) == hi) {
 914       // No overflow.  The range shifts up cleanly.
 915       return TypeInt::make((jint)lo << (jint)shift,
 916                            (jint)hi << (jint)shift,
 917                            MAX2(r1->_widen,r2->_widen));
 918     }
 919     return TypeInt::INT;
 920   }
 921 
 922   return TypeInt::make( (jint)r1->get_con() << (jint)shift );
 923 }
 924 
 925 //=============================================================================
 926 //------------------------------Identity---------------------------------------
 927 Node* LShiftLNode::Identity(PhaseGVN* phase) {
 928   int count = 0;
 929   if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaLong - 1)) == 0) {
 930     // Shift by a multiple of 64 does nothing
 931     return in(1);
 932   }
 933   return this;
 934 }
 935 
 936 //------------------------------Ideal------------------------------------------
 937 // If the right input is a constant, and the left input is an add of a
 938 // constant, flatten the tree: (X+con1)<<con0 ==> X<<con0 + con1<<con0
 939 Node *LShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
 940   int con = maskShiftAmount(phase, this, BitsPerJavaLong);
 941   if (con == 0) {
 942     return NULL;
 943   }
 944 
 945   // Left input is an add?
 946   Node *add1 = in(1);
 947   int add1_op = add1->Opcode();
 948   if( add1_op == Op_AddL ) {    // Left input is an add?
 949     // Avoid dead data cycles from dead loops
 950     assert( add1 != add1->in(1), "dead loop in LShiftLNode::Ideal" );
 951 
 952     // Left input is an add of the same number?
 953     if (add1->in(1) == add1->in(2)) {
 954       // Convert "(x + x) << c0" into "x << (c0 + 1)"
 955       return new LShiftLNode(add1->in(1), phase->intcon(con + 1));
 956     }
 957 
 958     // Left input is an add of a constant?
 959     const TypeLong *t12 = phase->type(add1->in(2))->isa_long();
 960     if( t12 && t12->is_con() ){ // Left input is an add of a con?
 961       // Compute X << con0
 962       Node *lsh = phase->transform( new LShiftLNode( add1->in(1), in(2) ) );
 963       // Compute X<<con0 + (con1<<con0)
 964       return new AddLNode( lsh, phase->longcon(t12->get_con() << con));
 965     }
 966   }
 967 
 968   // Check for "(x>>c0)<<c0" which just masks off low bits
 969   if( (add1_op == Op_RShiftL || add1_op == Op_URShiftL ) &&
 970       add1->in(2) == in(2) )
 971     // Convert to "(x & -(1<<c0))"
 972     return new AndLNode(add1->in(1),phase->longcon( -(CONST64(1)<<con)));
 973 
 974   // Check for "((x>>c0) & Y)<<c0" which just masks off more low bits
 975   if( add1_op == Op_AndL ) {
 976     Node *add2 = add1->in(1);
 977     int add2_op = add2->Opcode();
 978     if( (add2_op == Op_RShiftL || add2_op == Op_URShiftL ) &&
 979         add2->in(2) == in(2) ) {
 980       // Convert to "(x & (Y<<c0))"
 981       Node *y_sh = phase->transform( new LShiftLNode( add1->in(2), in(2) ) );
 982       return new AndLNode( add2->in(1), y_sh );
 983     }
 984   }
 985 
 986   // Check for ((x & ((CONST64(1)<<(64-c0))-1)) << c0) which ANDs off high bits
 987   // before shifting them away.
 988   const jlong bits_mask = jlong(max_julong >> con);
 989   if( add1_op == Op_AndL &&
 990       phase->type(add1->in(2)) == TypeLong::make( bits_mask ) )
 991     return new LShiftLNode( add1->in(1), in(2) );
 992 
 993   return NULL;
 994 }
 995 
 996 //------------------------------Value------------------------------------------
 997 // A LShiftLNode shifts its input2 left by input1 amount.
 998 const Type* LShiftLNode::Value(PhaseGVN* phase) const {
 999   const Type *t1 = phase->type( in(1) );
1000   const Type *t2 = phase->type( in(2) );
1001   // Either input is TOP ==> the result is TOP
1002   if( t1 == Type::TOP ) return Type::TOP;
1003   if( t2 == Type::TOP ) return Type::TOP;
1004 
1005   // Left input is ZERO ==> the result is ZERO.
1006   if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1007   // Shift by zero does nothing
1008   if( t2 == TypeInt::ZERO ) return t1;
1009 
1010   // Either input is BOTTOM ==> the result is BOTTOM
1011   if( (t1 == TypeLong::LONG) || (t2 == TypeInt::INT) ||
1012       (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1013     return TypeLong::LONG;
1014 
1015   const TypeLong *r1 = t1->is_long(); // Handy access
1016   const TypeInt  *r2 = t2->is_int();  // Handy access
1017 
1018   if (!r2->is_con())
1019     return TypeLong::LONG;
1020 
1021   uint shift = r2->get_con();
1022   shift &= BitsPerJavaLong - 1;  // semantics of Java shifts
1023   // Shift by a multiple of 64 does nothing:
1024   if (shift == 0)  return t1;
1025 
1026   // If the shift is a constant, shift the bounds of the type,
1027   // unless this could lead to an overflow.
1028   if (!r1->is_con()) {
1029     jlong lo = r1->_lo, hi = r1->_hi;
1030     if (((lo << shift) >> shift) == lo &&
1031         ((hi << shift) >> shift) == hi) {
1032       // No overflow.  The range shifts up cleanly.
1033       return TypeLong::make((jlong)lo << (jint)shift,
1034                             (jlong)hi << (jint)shift,
1035                             MAX2(r1->_widen,r2->_widen));
1036     }
1037     return TypeLong::LONG;
1038   }
1039 
1040   return TypeLong::make( (jlong)r1->get_con() << (jint)shift );
1041 }
1042 
1043 //=============================================================================
1044 //------------------------------Identity---------------------------------------
1045 Node* RShiftINode::Identity(PhaseGVN* phase) {
1046   int count = 0;
1047   if (const_shift_count(phase, this, &count)) {
1048     if ((count & (BitsPerJavaInteger - 1)) == 0) {
1049       // Shift by a multiple of 32 does nothing
1050       return in(1);
1051     }
1052     // Check for useless sign-masking
1053     if (in(1)->Opcode() == Op_LShiftI &&
1054         in(1)->req() == 3 &&
1055         in(1)->in(2) == in(2)) {
1056       count &= BitsPerJavaInteger-1; // semantics of Java shifts
1057       // Compute masks for which this shifting doesn't change
1058       int lo = (-1 << (BitsPerJavaInteger - ((uint)count)-1)); // FFFF8000
1059       int hi = ~lo;               // 00007FFF
1060       const TypeInt* t11 = phase->type(in(1)->in(1))->isa_int();
1061       if (t11 == NULL) {
1062         return this;
1063       }
1064       // Does actual value fit inside of mask?
1065       if (lo <= t11->_lo && t11->_hi <= hi) {
1066         return in(1)->in(1);      // Then shifting is a nop
1067       }
1068     }
1069   }
1070   return this;
1071 }
1072 
1073 //------------------------------Ideal------------------------------------------
1074 Node *RShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1075   // Inputs may be TOP if they are dead.
1076   const TypeInt *t1 = phase->type(in(1))->isa_int();
1077   if (!t1) return NULL;        // Left input is an integer
1078   const TypeInt *t3;  // type of in(1).in(2)
1079   int shift = maskShiftAmount(phase, this, BitsPerJavaInteger);
1080   if (shift == 0) {
1081     return NULL;
1082   }
1083 
1084   // Check for (x & 0xFF000000) >> 24, whose mask can be made smaller.
1085   // Such expressions arise normally from shift chains like (byte)(x >> 24).
1086   const Node *mask = in(1);
1087   if( mask->Opcode() == Op_AndI &&
1088       (t3 = phase->type(mask->in(2))->isa_int()) &&
1089       t3->is_con() ) {
1090     Node *x = mask->in(1);
1091     jint maskbits = t3->get_con();
1092     // Convert to "(x >> shift) & (mask >> shift)"
1093     Node *shr_nomask = phase->transform( new RShiftINode(mask->in(1), in(2)) );
1094     return new AndINode(shr_nomask, phase->intcon( maskbits >> shift));
1095   }
1096 
1097   // Check for "(short[i] <<16)>>16" which simply sign-extends
1098   const Node *shl = in(1);
1099   if( shl->Opcode() != Op_LShiftI ) return NULL;
1100 
1101   if( shift == 16 &&
1102       (t3 = phase->type(shl->in(2))->isa_int()) &&
1103       t3->is_con(16) ) {
1104     Node *ld = shl->in(1);
1105     if( ld->Opcode() == Op_LoadS ) {
1106       // Sign extension is just useless here.  Return a RShiftI of zero instead
1107       // returning 'ld' directly.  We cannot return an old Node directly as
1108       // that is the job of 'Identity' calls and Identity calls only work on
1109       // direct inputs ('ld' is an extra Node removed from 'this').  The
1110       // combined optimization requires Identity only return direct inputs.
1111       set_req_X(1, ld, phase);
1112       set_req_X(2, phase->intcon(0), phase);
1113       return this;
1114     }
1115     else if (can_reshape &&
1116              ld->Opcode() == Op_LoadUS &&
1117              ld->outcnt() == 1 && ld->unique_out() == shl)
1118       // Replace zero-extension-load with sign-extension-load
1119       return ld->as_Load()->convert_to_signed_load(*phase);
1120   }
1121 
1122   // Check for "(byte[i] <<24)>>24" which simply sign-extends
1123   if( shift == 24 &&
1124       (t3 = phase->type(shl->in(2))->isa_int()) &&
1125       t3->is_con(24) ) {
1126     Node *ld = shl->in(1);
1127     if (ld->Opcode() == Op_LoadB) {
1128       // Sign extension is just useless here
1129       set_req_X(1, ld, phase);
1130       set_req_X(2, phase->intcon(0), phase);
1131       return this;
1132     }
1133   }
1134 
1135   return NULL;
1136 }
1137 
1138 //------------------------------Value------------------------------------------
1139 // A RShiftINode shifts its input2 right by input1 amount.
1140 const Type* RShiftINode::Value(PhaseGVN* phase) const {
1141   const Type *t1 = phase->type( in(1) );
1142   const Type *t2 = phase->type( in(2) );
1143   // Either input is TOP ==> the result is TOP
1144   if( t1 == Type::TOP ) return Type::TOP;
1145   if( t2 == Type::TOP ) return Type::TOP;
1146 
1147   // Left input is ZERO ==> the result is ZERO.
1148   if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
1149   // Shift by zero does nothing
1150   if( t2 == TypeInt::ZERO ) return t1;
1151 
1152   // Either input is BOTTOM ==> the result is BOTTOM
1153   if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1154     return TypeInt::INT;
1155 
1156   if (t2 == TypeInt::INT)
1157     return TypeInt::INT;
1158 
1159   const TypeInt *r1 = t1->is_int(); // Handy access
1160   const TypeInt *r2 = t2->is_int(); // Handy access
1161 
1162   // If the shift is a constant, just shift the bounds of the type.
1163   // For example, if the shift is 31, we just propagate sign bits.
1164   if (r2->is_con()) {
1165     uint shift = r2->get_con();
1166     shift &= BitsPerJavaInteger-1;  // semantics of Java shifts
1167     // Shift by a multiple of 32 does nothing:
1168     if (shift == 0)  return t1;
1169     // Calculate reasonably aggressive bounds for the result.
1170     // This is necessary if we are to correctly type things
1171     // like (x<<24>>24) == ((byte)x).
1172     jint lo = (jint)r1->_lo >> (jint)shift;
1173     jint hi = (jint)r1->_hi >> (jint)shift;
1174     assert(lo <= hi, "must have valid bounds");
1175     const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1176 #ifdef ASSERT
1177     // Make sure we get the sign-capture idiom correct.
1178     if (shift == BitsPerJavaInteger-1) {
1179       if (r1->_lo >= 0) assert(ti == TypeInt::ZERO,    ">>31 of + is  0");
1180       if (r1->_hi <  0) assert(ti == TypeInt::MINUS_1, ">>31 of - is -1");
1181     }
1182 #endif
1183     return ti;
1184   }
1185 
1186   if( !r1->is_con() || !r2->is_con() )
1187     return TypeInt::INT;
1188 
1189   // Signed shift right
1190   return TypeInt::make( r1->get_con() >> (r2->get_con()&31) );
1191 }
1192 
1193 //=============================================================================
1194 //------------------------------Identity---------------------------------------
1195 Node* RShiftLNode::Identity(PhaseGVN* phase) {
1196   const TypeInt *ti = phase->type(in(2))->isa_int(); // Shift count is an int.
1197   return (ti && ti->is_con() && (ti->get_con() & (BitsPerJavaLong - 1)) == 0) ? in(1) : this;
1198 }
1199 
1200 //------------------------------Value------------------------------------------
1201 // A RShiftLNode shifts its input2 right by input1 amount.
1202 const Type* RShiftLNode::Value(PhaseGVN* phase) const {
1203   const Type *t1 = phase->type( in(1) );
1204   const Type *t2 = phase->type( in(2) );
1205   // Either input is TOP ==> the result is TOP
1206   if( t1 == Type::TOP ) return Type::TOP;
1207   if( t2 == Type::TOP ) return Type::TOP;
1208 
1209   // Left input is ZERO ==> the result is ZERO.
1210   if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1211   // Shift by zero does nothing
1212   if( t2 == TypeInt::ZERO ) return t1;
1213 
1214   // Either input is BOTTOM ==> the result is BOTTOM
1215   if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1216     return TypeLong::LONG;
1217 
1218   if (t2 == TypeInt::INT)
1219     return TypeLong::LONG;
1220 
1221   const TypeLong *r1 = t1->is_long(); // Handy access
1222   const TypeInt  *r2 = t2->is_int (); // Handy access
1223 
1224   // If the shift is a constant, just shift the bounds of the type.
1225   // For example, if the shift is 63, we just propagate sign bits.
1226   if (r2->is_con()) {
1227     uint shift = r2->get_con();
1228     shift &= (2*BitsPerJavaInteger)-1;  // semantics of Java shifts
1229     // Shift by a multiple of 64 does nothing:
1230     if (shift == 0)  return t1;
1231     // Calculate reasonably aggressive bounds for the result.
1232     // This is necessary if we are to correctly type things
1233     // like (x<<24>>24) == ((byte)x).
1234     jlong lo = (jlong)r1->_lo >> (jlong)shift;
1235     jlong hi = (jlong)r1->_hi >> (jlong)shift;
1236     assert(lo <= hi, "must have valid bounds");
1237     const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1238     #ifdef ASSERT
1239     // Make sure we get the sign-capture idiom correct.
1240     if (shift == (2*BitsPerJavaInteger)-1) {
1241       if (r1->_lo >= 0) assert(tl == TypeLong::ZERO,    ">>63 of + is 0");
1242       if (r1->_hi < 0)  assert(tl == TypeLong::MINUS_1, ">>63 of - is -1");
1243     }
1244     #endif
1245     return tl;
1246   }
1247 
1248   return TypeLong::LONG;                // Give up
1249 }
1250 
1251 //=============================================================================
1252 //------------------------------Identity---------------------------------------
1253 Node* URShiftINode::Identity(PhaseGVN* phase) {
1254   int count = 0;
1255   if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaInteger - 1)) == 0) {
1256     // Shift by a multiple of 32 does nothing
1257     return in(1);
1258   }
1259 
1260   // Check for "((x << LogBytesPerWord) + (wordSize-1)) >> LogBytesPerWord" which is just "x".
1261   // Happens during new-array length computation.
1262   // Safe if 'x' is in the range [0..(max_int>>LogBytesPerWord)]
1263   Node *add = in(1);
1264   if (add->Opcode() == Op_AddI) {
1265     const TypeInt *t2 = phase->type(add->in(2))->isa_int();
1266     if (t2 && t2->is_con(wordSize - 1) &&
1267         add->in(1)->Opcode() == Op_LShiftI) {
1268       // Check that shift_counts are LogBytesPerWord.
1269       Node          *lshift_count   = add->in(1)->in(2);
1270       const TypeInt *t_lshift_count = phase->type(lshift_count)->isa_int();
1271       if (t_lshift_count && t_lshift_count->is_con(LogBytesPerWord) &&
1272           t_lshift_count == phase->type(in(2))) {
1273         Node          *x   = add->in(1)->in(1);
1274         const TypeInt *t_x = phase->type(x)->isa_int();
1275         if (t_x != NULL && 0 <= t_x->_lo && t_x->_hi <= (max_jint>>LogBytesPerWord)) {
1276           return x;
1277         }
1278       }
1279     }
1280   }
1281 
1282   return (phase->type(in(2))->higher_equal(TypeInt::ZERO)) ? in(1) : this;
1283 }
1284 
1285 //------------------------------Ideal------------------------------------------
1286 Node *URShiftINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1287   int con = maskShiftAmount(phase, this, BitsPerJavaInteger);
1288   if (con == 0) {
1289     return NULL;
1290   }
1291 
1292   // We'll be wanting the right-shift amount as a mask of that many bits
1293   const int mask = right_n_bits(BitsPerJavaInteger - con);
1294 
1295   int in1_op = in(1)->Opcode();
1296 
1297   // Check for ((x>>>a)>>>b) and replace with (x>>>(a+b)) when a+b < 32
1298   if( in1_op == Op_URShiftI ) {
1299     const TypeInt *t12 = phase->type( in(1)->in(2) )->isa_int();
1300     if( t12 && t12->is_con() ) { // Right input is a constant
1301       assert( in(1) != in(1)->in(1), "dead loop in URShiftINode::Ideal" );
1302       const int con2 = t12->get_con() & 31; // Shift count is always masked
1303       const int con3 = con+con2;
1304       if( con3 < 32 )           // Only merge shifts if total is < 32
1305         return new URShiftINode( in(1)->in(1), phase->intcon(con3) );
1306     }
1307   }
1308 
1309   // Check for ((x << z) + Y) >>> z.  Replace with x + con>>>z
1310   // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z".
1311   // If Q is "X << z" the rounding is useless.  Look for patterns like
1312   // ((X<<Z) + Y) >>> Z  and replace with (X + Y>>>Z) & Z-mask.
1313   Node *add = in(1);
1314   const TypeInt *t2 = phase->type(in(2))->isa_int();
1315   if (in1_op == Op_AddI) {
1316     Node *lshl = add->in(1);
1317     if( lshl->Opcode() == Op_LShiftI &&
1318         phase->type(lshl->in(2)) == t2 ) {
1319       Node *y_z = phase->transform( new URShiftINode(add->in(2),in(2)) );
1320       Node *sum = phase->transform( new AddINode( lshl->in(1), y_z ) );
1321       return new AndINode( sum, phase->intcon(mask) );
1322     }
1323   }
1324 
1325   // Check for (x & mask) >>> z.  Replace with (x >>> z) & (mask >>> z)
1326   // This shortens the mask.  Also, if we are extracting a high byte and
1327   // storing it to a buffer, the mask will be removed completely.
1328   Node *andi = in(1);
1329   if( in1_op == Op_AndI ) {
1330     const TypeInt *t3 = phase->type( andi->in(2) )->isa_int();
1331     if( t3 && t3->is_con() ) { // Right input is a constant
1332       jint mask2 = t3->get_con();
1333       mask2 >>= con;  // *signed* shift downward (high-order zeroes do not help)
1334       Node *newshr = phase->transform( new URShiftINode(andi->in(1), in(2)) );
1335       return new AndINode(newshr, phase->intcon(mask2));
1336       // The negative values are easier to materialize than positive ones.
1337       // A typical case from address arithmetic is ((x & ~15) >> 4).
1338       // It's better to change that to ((x >> 4) & ~0) versus
1339       // ((x >> 4) & 0x0FFFFFFF).  The difference is greatest in LP64.
1340     }
1341   }
1342 
1343   // Check for "(X << z ) >>> z" which simply zero-extends
1344   Node *shl = in(1);
1345   if( in1_op == Op_LShiftI &&
1346       phase->type(shl->in(2)) == t2 )
1347     return new AndINode( shl->in(1), phase->intcon(mask) );
1348 
1349   // Check for (x >> n) >>> 31. Replace with (x >>> 31)
1350   Node *shr = in(1);
1351   if ( in1_op == Op_RShiftI ) {
1352     Node *in11 = shr->in(1);
1353     Node *in12 = shr->in(2);
1354     const TypeInt *t11 = phase->type(in11)->isa_int();
1355     const TypeInt *t12 = phase->type(in12)->isa_int();
1356     if ( t11 && t2 && t2->is_con(31) && t12 && t12->is_con() ) {
1357       return new URShiftINode(in11, phase->intcon(31));
1358     }
1359   }
1360 
1361   return NULL;
1362 }
1363 
1364 //------------------------------Value------------------------------------------
1365 // A URShiftINode shifts its input2 right by input1 amount.
1366 const Type* URShiftINode::Value(PhaseGVN* phase) const {
1367   // (This is a near clone of RShiftINode::Value.)
1368   const Type *t1 = phase->type( in(1) );
1369   const Type *t2 = phase->type( in(2) );
1370   // Either input is TOP ==> the result is TOP
1371   if( t1 == Type::TOP ) return Type::TOP;
1372   if( t2 == Type::TOP ) return Type::TOP;
1373 
1374   // Left input is ZERO ==> the result is ZERO.
1375   if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
1376   // Shift by zero does nothing
1377   if( t2 == TypeInt::ZERO ) return t1;
1378 
1379   // Either input is BOTTOM ==> the result is BOTTOM
1380   if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1381     return TypeInt::INT;
1382 
1383   if (t2 == TypeInt::INT)
1384     return TypeInt::INT;
1385 
1386   const TypeInt *r1 = t1->is_int();     // Handy access
1387   const TypeInt *r2 = t2->is_int();     // Handy access
1388 
1389   if (r2->is_con()) {
1390     uint shift = r2->get_con();
1391     shift &= BitsPerJavaInteger-1;  // semantics of Java shifts
1392     // Shift by a multiple of 32 does nothing:
1393     if (shift == 0)  return t1;
1394     // Calculate reasonably aggressive bounds for the result.
1395     jint lo = (juint)r1->_lo >> (juint)shift;
1396     jint hi = (juint)r1->_hi >> (juint)shift;
1397     if (r1->_hi >= 0 && r1->_lo < 0) {
1398       // If the type has both negative and positive values,
1399       // there are two separate sub-domains to worry about:
1400       // The positive half and the negative half.
1401       jint neg_lo = lo;
1402       jint neg_hi = (juint)-1 >> (juint)shift;
1403       jint pos_lo = (juint) 0 >> (juint)shift;
1404       jint pos_hi = hi;
1405       lo = MIN2(neg_lo, pos_lo);  // == 0
1406       hi = MAX2(neg_hi, pos_hi);  // == -1 >>> shift;
1407     }
1408     assert(lo <= hi, "must have valid bounds");
1409     const TypeInt* ti = TypeInt::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1410     #ifdef ASSERT
1411     // Make sure we get the sign-capture idiom correct.
1412     if (shift == BitsPerJavaInteger-1) {
1413       if (r1->_lo >= 0) assert(ti == TypeInt::ZERO, ">>>31 of + is 0");
1414       if (r1->_hi < 0)  assert(ti == TypeInt::ONE,  ">>>31 of - is +1");
1415     }
1416     #endif
1417     return ti;
1418   }
1419 
1420   //
1421   // Do not support shifted oops in info for GC
1422   //
1423   // else if( t1->base() == Type::InstPtr ) {
1424   //
1425   //   const TypeInstPtr *o = t1->is_instptr();
1426   //   if( t1->singleton() )
1427   //     return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift );
1428   // }
1429   // else if( t1->base() == Type::KlassPtr ) {
1430   //   const TypeKlassPtr *o = t1->is_klassptr();
1431   //   if( t1->singleton() )
1432   //     return TypeInt::make( ((uint32_t)o->const_oop() + o->_offset) >> shift );
1433   // }
1434 
1435   return TypeInt::INT;
1436 }
1437 
1438 //=============================================================================
1439 //------------------------------Identity---------------------------------------
1440 Node* URShiftLNode::Identity(PhaseGVN* phase) {
1441   int count = 0;
1442   if (const_shift_count(phase, this, &count) && (count & (BitsPerJavaLong - 1)) == 0) {
1443     // Shift by a multiple of 64 does nothing
1444     return in(1);
1445   }
1446   return this;
1447 }
1448 
1449 //------------------------------Ideal------------------------------------------
1450 Node *URShiftLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1451   int con = maskShiftAmount(phase, this, BitsPerJavaLong);
1452   if (con == 0) {
1453     return NULL;
1454   }
1455 
1456   // We'll be wanting the right-shift amount as a mask of that many bits
1457   const jlong mask = jlong(max_julong >> con);
1458 
1459   // Check for ((x << z) + Y) >>> z.  Replace with x + con>>>z
1460   // The idiom for rounding to a power of 2 is "(Q+(2^z-1)) >>> z".
1461   // If Q is "X << z" the rounding is useless.  Look for patterns like
1462   // ((X<<Z) + Y) >>> Z  and replace with (X + Y>>>Z) & Z-mask.
1463   Node *add = in(1);
1464   const TypeInt *t2 = phase->type(in(2))->isa_int();
1465   if (add->Opcode() == Op_AddL) {
1466     Node *lshl = add->in(1);
1467     if( lshl->Opcode() == Op_LShiftL &&
1468         phase->type(lshl->in(2)) == t2 ) {
1469       Node *y_z = phase->transform( new URShiftLNode(add->in(2),in(2)) );
1470       Node *sum = phase->transform( new AddLNode( lshl->in(1), y_z ) );
1471       return new AndLNode( sum, phase->longcon(mask) );
1472     }
1473   }
1474 
1475   // Check for (x & mask) >>> z.  Replace with (x >>> z) & (mask >>> z)
1476   // This shortens the mask.  Also, if we are extracting a high byte and
1477   // storing it to a buffer, the mask will be removed completely.
1478   Node *andi = in(1);
1479   if( andi->Opcode() == Op_AndL ) {
1480     const TypeLong *t3 = phase->type( andi->in(2) )->isa_long();
1481     if( t3 && t3->is_con() ) { // Right input is a constant
1482       jlong mask2 = t3->get_con();
1483       mask2 >>= con;  // *signed* shift downward (high-order zeroes do not help)
1484       Node *newshr = phase->transform( new URShiftLNode(andi->in(1), in(2)) );
1485       return new AndLNode(newshr, phase->longcon(mask2));
1486     }
1487   }
1488 
1489   // Check for "(X << z ) >>> z" which simply zero-extends
1490   Node *shl = in(1);
1491   if( shl->Opcode() == Op_LShiftL &&
1492       phase->type(shl->in(2)) == t2 )
1493     return new AndLNode( shl->in(1), phase->longcon(mask) );
1494 
1495   // Check for (x >> n) >>> 63. Replace with (x >>> 63)
1496   Node *shr = in(1);
1497   if ( shr->Opcode() == Op_RShiftL ) {
1498     Node *in11 = shr->in(1);
1499     Node *in12 = shr->in(2);
1500     const TypeLong *t11 = phase->type(in11)->isa_long();
1501     const TypeInt *t12 = phase->type(in12)->isa_int();
1502     if ( t11 && t2 && t2->is_con(63) && t12 && t12->is_con() ) {
1503       return new URShiftLNode(in11, phase->intcon(63));
1504     }
1505   }
1506   return NULL;
1507 }
1508 
1509 //------------------------------Value------------------------------------------
1510 // A URShiftINode shifts its input2 right by input1 amount.
1511 const Type* URShiftLNode::Value(PhaseGVN* phase) const {
1512   // (This is a near clone of RShiftLNode::Value.)
1513   const Type *t1 = phase->type( in(1) );
1514   const Type *t2 = phase->type( in(2) );
1515   // Either input is TOP ==> the result is TOP
1516   if( t1 == Type::TOP ) return Type::TOP;
1517   if( t2 == Type::TOP ) return Type::TOP;
1518 
1519   // Left input is ZERO ==> the result is ZERO.
1520   if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1521   // Shift by zero does nothing
1522   if( t2 == TypeInt::ZERO ) return t1;
1523 
1524   // Either input is BOTTOM ==> the result is BOTTOM
1525   if (t1 == Type::BOTTOM || t2 == Type::BOTTOM)
1526     return TypeLong::LONG;
1527 
1528   if (t2 == TypeInt::INT)
1529     return TypeLong::LONG;
1530 
1531   const TypeLong *r1 = t1->is_long(); // Handy access
1532   const TypeInt  *r2 = t2->is_int (); // Handy access
1533 
1534   if (r2->is_con()) {
1535     uint shift = r2->get_con();
1536     shift &= BitsPerJavaLong - 1;  // semantics of Java shifts
1537     // Shift by a multiple of 64 does nothing:
1538     if (shift == 0)  return t1;
1539     // Calculate reasonably aggressive bounds for the result.
1540     jlong lo = (julong)r1->_lo >> (juint)shift;
1541     jlong hi = (julong)r1->_hi >> (juint)shift;
1542     if (r1->_hi >= 0 && r1->_lo < 0) {
1543       // If the type has both negative and positive values,
1544       // there are two separate sub-domains to worry about:
1545       // The positive half and the negative half.
1546       jlong neg_lo = lo;
1547       jlong neg_hi = (julong)-1 >> (juint)shift;
1548       jlong pos_lo = (julong) 0 >> (juint)shift;
1549       jlong pos_hi = hi;
1550       //lo = MIN2(neg_lo, pos_lo);  // == 0
1551       lo = neg_lo < pos_lo ? neg_lo : pos_lo;
1552       //hi = MAX2(neg_hi, pos_hi);  // == -1 >>> shift;
1553       hi = neg_hi > pos_hi ? neg_hi : pos_hi;
1554     }
1555     assert(lo <= hi, "must have valid bounds");
1556     const TypeLong* tl = TypeLong::make(lo, hi, MAX2(r1->_widen,r2->_widen));
1557     #ifdef ASSERT
1558     // Make sure we get the sign-capture idiom correct.
1559     if (shift == BitsPerJavaLong - 1) {
1560       if (r1->_lo >= 0) assert(tl == TypeLong::ZERO, ">>>63 of + is 0");
1561       if (r1->_hi < 0)  assert(tl == TypeLong::ONE,  ">>>63 of - is +1");
1562     }
1563     #endif
1564     return tl;
1565   }
1566 
1567   return TypeLong::LONG;                // Give up
1568 }
1569 
1570 //=============================================================================
1571 //------------------------------Value------------------------------------------
1572 const Type* FmaDNode::Value(PhaseGVN* phase) const {
1573   const Type *t1 = phase->type(in(1));
1574   if (t1 == Type::TOP) return Type::TOP;
1575   if (t1->base() != Type::DoubleCon) return Type::DOUBLE;
1576   const Type *t2 = phase->type(in(2));
1577   if (t2 == Type::TOP) return Type::TOP;
1578   if (t2->base() != Type::DoubleCon) return Type::DOUBLE;
1579   const Type *t3 = phase->type(in(3));
1580   if (t3 == Type::TOP) return Type::TOP;
1581   if (t3->base() != Type::DoubleCon) return Type::DOUBLE;
1582 #ifndef __STDC_IEC_559__
1583   return Type::DOUBLE;
1584 #else
1585   double d1 = t1->getd();
1586   double d2 = t2->getd();
1587   double d3 = t3->getd();
1588   return TypeD::make(fma(d1, d2, d3));
1589 #endif
1590 }
1591 
1592 //=============================================================================
1593 //------------------------------Value------------------------------------------
1594 const Type* FmaFNode::Value(PhaseGVN* phase) const {
1595   const Type *t1 = phase->type(in(1));
1596   if (t1 == Type::TOP) return Type::TOP;
1597   if (t1->base() != Type::FloatCon) return Type::FLOAT;
1598   const Type *t2 = phase->type(in(2));
1599   if (t2 == Type::TOP) return Type::TOP;
1600   if (t2->base() != Type::FloatCon) return Type::FLOAT;
1601   const Type *t3 = phase->type(in(3));
1602   if (t3 == Type::TOP) return Type::TOP;
1603   if (t3->base() != Type::FloatCon) return Type::FLOAT;
1604 #ifndef __STDC_IEC_559__
1605   return Type::FLOAT;
1606 #else
1607   float f1 = t1->getf();
1608   float f2 = t2->getf();
1609   float f3 = t3->getf();
1610   return TypeF::make(fma(f1, f2, f3));
1611 #endif
1612 }
1613 
1614 //=============================================================================
1615 //------------------------------hash-------------------------------------------
1616 // Hash function for MulAddS2INode.  Operation is commutative with commutative pairs.
1617 // The hash function must return the same value when edge swapping is performed.
1618 uint MulAddS2INode::hash() const {
1619   return (uintptr_t)in(1) + (uintptr_t)in(2) + (uintptr_t)in(3) + (uintptr_t)in(4) + Opcode();
1620 }
1621 
1622 //------------------------------Rotate Operations ------------------------------
1623 
1624 Node* RotateLeftNode::Identity(PhaseGVN* phase) {
1625   const Type* t1 = phase->type(in(1));
1626   if (t1 == Type::TOP) {
1627     return this;
1628   }
1629   int count = 0;
1630   assert(t1->isa_int() || t1->isa_long(), "Unexpected type");
1631   int mask = (t1->isa_int() ? BitsPerJavaInteger : BitsPerJavaLong) - 1;
1632   if (const_shift_count(phase, this, &count) && (count & mask) == 0) {
1633     // Rotate by a multiple of 32/64 does nothing
1634     return in(1);
1635   }
1636   return this;
1637 }
1638 
1639 const Type* RotateLeftNode::Value(PhaseGVN* phase) const {
1640   const Type* t1 = phase->type(in(1));
1641   const Type* t2 = phase->type(in(2));
1642   // Either input is TOP ==> the result is TOP
1643   if (t1 == Type::TOP || t2 == Type::TOP) {
1644     return Type::TOP;
1645   }
1646 
1647   if (t1->isa_int()) {
1648     const TypeInt* r1 = t1->is_int();
1649     const TypeInt* r2 = t2->is_int();
1650 
1651     // Left input is ZERO ==> the result is ZERO.
1652     if (r1 == TypeInt::ZERO) {
1653       return TypeInt::ZERO;
1654     }
1655     // Rotate by zero does nothing
1656     if (r2 == TypeInt::ZERO) {
1657       return r1;
1658     }
1659     if (r1->is_con() && r2->is_con()) {
1660       juint r1_con = (juint)r1->get_con();
1661       juint shift = (juint)(r2->get_con()) & (juint)(BitsPerJavaInteger - 1); // semantics of Java shifts
1662       return TypeInt::make((r1_con << shift) | (r1_con >> (32 - shift)));
1663     }
1664     return TypeInt::INT;
1665   } else {
1666     assert(t1->isa_long(), "Type must be a long");
1667     const TypeLong* r1 = t1->is_long();
1668     const TypeInt*  r2 = t2->is_int();
1669 
1670     // Left input is ZERO ==> the result is ZERO.
1671     if (r1 == TypeLong::ZERO) {
1672       return TypeLong::ZERO;
1673     }
1674     // Rotate by zero does nothing
1675     if (r2 == TypeInt::ZERO) {
1676       return r1;
1677     }
1678     if (r1->is_con() && r2->is_con()) {
1679       julong r1_con = (julong)r1->get_con();
1680       julong shift = (julong)(r2->get_con()) & (julong)(BitsPerJavaLong - 1); // semantics of Java shifts
1681       return TypeLong::make((r1_con << shift) | (r1_con >> (64 - shift)));
1682     }
1683     return TypeLong::LONG;
1684   }
1685 }
1686 
1687 Node* RotateLeftNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1688   const Type* t1 = phase->type(in(1));
1689   const Type* t2 = phase->type(in(2));
1690   if (t2->isa_int() && t2->is_int()->is_con()) {
1691     if (t1->isa_int()) {
1692       int lshift = t2->is_int()->get_con() & 31;
1693       return new RotateRightNode(in(1), phase->intcon(32 - (lshift & 31)), TypeInt::INT);
1694     } else if (t1 != Type::TOP) {
1695       assert(t1->isa_long(), "Type must be a long");
1696       int lshift = t2->is_int()->get_con() & 63;
1697       return new RotateRightNode(in(1), phase->intcon(64 - (lshift & 63)), TypeLong::LONG);
1698     }
1699   }
1700   return NULL;
1701 }
1702 
1703 Node* RotateRightNode::Identity(PhaseGVN* phase) {
1704   const Type* t1 = phase->type(in(1));
1705   if (t1 == Type::TOP) {
1706     return this;
1707   }
1708   int count = 0;
1709   assert(t1->isa_int() || t1->isa_long(), "Unexpected type");
1710   int mask = (t1->isa_int() ? BitsPerJavaInteger : BitsPerJavaLong) - 1;
1711   if (const_shift_count(phase, this, &count) && (count & mask) == 0) {
1712     // Rotate by a multiple of 32/64 does nothing
1713     return in(1);
1714   }
1715   return this;
1716 }
1717 
1718 const Type* RotateRightNode::Value(PhaseGVN* phase) const {
1719   const Type* t1 = phase->type(in(1));
1720   const Type* t2 = phase->type(in(2));
1721   // Either input is TOP ==> the result is TOP
1722   if (t1 == Type::TOP || t2 == Type::TOP) {
1723     return Type::TOP;
1724   }
1725 
1726   if (t1->isa_int()) {
1727     const TypeInt* r1 = t1->is_int();
1728     const TypeInt* r2 = t2->is_int();
1729 
1730     // Left input is ZERO ==> the result is ZERO.
1731     if (r1 == TypeInt::ZERO) {
1732       return TypeInt::ZERO;
1733     }
1734     // Rotate by zero does nothing
1735     if (r2 == TypeInt::ZERO) {
1736       return r1;
1737     }
1738     if (r1->is_con() && r2->is_con()) {
1739       juint r1_con = (juint)r1->get_con();
1740       juint shift = (juint)(r2->get_con()) & (juint)(BitsPerJavaInteger - 1); // semantics of Java shifts
1741       return TypeInt::make((r1_con >> shift) | (r1_con << (32 - shift)));
1742     }
1743     return TypeInt::INT;
1744   } else {
1745     assert(t1->isa_long(), "Type must be a long");
1746     const TypeLong* r1 = t1->is_long();
1747     const TypeInt*  r2 = t2->is_int();
1748     // Left input is ZERO ==> the result is ZERO.
1749     if (r1 == TypeLong::ZERO) {
1750       return TypeLong::ZERO;
1751     }
1752     // Rotate by zero does nothing
1753     if (r2 == TypeInt::ZERO) {
1754       return r1;
1755     }
1756     if (r1->is_con() && r2->is_con()) {
1757       julong r1_con = (julong)r1->get_con();
1758       julong shift = (julong)(r2->get_con()) & (julong)(BitsPerJavaLong - 1); // semantics of Java shifts
1759       return TypeLong::make((r1_con >> shift) | (r1_con << (64 - shift)));
1760     }
1761     return TypeLong::LONG;
1762   }
1763 }
1764 
1765 // Given an expression (AndX shift mask) or (AndX mask shift),
1766 // determine if the AndX must always produce zero, because the
1767 // the shift (x<<N) is bitwise disjoint from the mask #M.
1768 // The X in AndX must be I or L, depending on bt.
1769 // Specifically, the following cases fold to zero,
1770 // when the shift value N is large enough to zero out
1771 // all the set positions of the and-mask M.
1772 //   (AndI (LShiftI _ #N) #M) => #0
1773 //   (AndL (LShiftL _ #N) #M) => #0
1774 //   (AndL (ConvI2L (LShiftI _ #N)) #M) => #0
1775 // The M and N values must satisfy ((-1 << N) & M) == 0.
1776 // Because the optimization might work for a non-constant
1777 // mask M, we check the AndX for both operand orders.
1778 bool MulNode::AndIL_shift_and_mask_is_always_zero(PhaseGVN* phase, Node* shift, Node* mask, BasicType bt, bool check_reverse) {
1779   if (mask == NULL || shift == NULL) {
1780     return false;
1781   }
1782   const TypeInteger* mask_t = phase->type(mask)->isa_integer(bt);
1783   const TypeInteger* shift_t = phase->type(shift)->isa_integer(bt);
1784   if (mask_t == NULL || shift_t == NULL) {
1785     return false;
1786   }
1787   BasicType shift_bt = bt;
1788   if (bt == T_LONG && shift->Opcode() == Op_ConvI2L) {
1789     bt = T_INT;
1790     Node* val = shift->in(1);
1791     if (val == NULL) {
1792       return false;
1793     }
1794     if (val->Opcode() == Op_LShiftI) {
1795       shift_bt = T_INT;
1796       shift = val;
1797     }
1798   }
1799   if (shift->Opcode() != Op_LShift(shift_bt)) {
1800     if (check_reverse &&
1801         (mask->Opcode() == Op_LShift(bt) ||
1802          (bt == T_LONG && mask->Opcode() == Op_ConvI2L))) {
1803       // try it the other way around
1804       return AndIL_shift_and_mask_is_always_zero(phase, mask, shift, bt, false);
1805     }
1806     return false;
1807   }
1808   Node* shift2 = shift->in(2);
1809   if (shift2 == NULL) {
1810     return false;
1811   }
1812   const Type* shift2_t = phase->type(shift2);
1813   if (!shift2_t->isa_int() || !shift2_t->is_int()->is_con()) {
1814     return false;
1815   }
1816 
1817   jint shift_con = shift2_t->is_int()->get_con() & ((shift_bt == T_INT ? BitsPerJavaInteger : BitsPerJavaLong) - 1);
1818   if ((((jlong)1) << shift_con) > mask_t->hi_as_long() && mask_t->lo_as_long() >= 0) {
1819     return true;
1820   }
1821 
1822   return false;
1823 }
1824 
1825 // Given an expression (AndX (AddX v1 (LShiftX v2 #N)) #M)
1826 // determine if the AndX must always produce (AndX v1 #M),
1827 // because the shift (v2<<N) is bitwise disjoint from the mask #M.
1828 // The X in AndX will be I or L, depending on bt.
1829 // Specifically, the following cases fold,
1830 // when the shift value N is large enough to zero out
1831 // all the set positions of the and-mask M.
1832 //   (AndI (AddI v1 (LShiftI _ #N)) #M) => (AndI v1 #M)
1833 //   (AndL (AddI v1 (LShiftL _ #N)) #M) => (AndL v1 #M)
1834 //   (AndL (AddL v1 (ConvI2L (LShiftI _ #N))) #M) => (AndL v1 #M)
1835 // The M and N values must satisfy ((-1 << N) & M) == 0.
1836 // Because the optimization might work for a non-constant
1837 // mask M, and because the AddX operands can come in either
1838 // order, we check for every operand order.
1839 Node* MulNode::AndIL_add_shift_and_mask(PhaseGVN* phase, BasicType bt) {
1840   Node* add = in(1);
1841   Node* mask = in(2);
1842   if (add == NULL || mask == NULL) {
1843     return NULL;
1844   }
1845   int addidx = 0;
1846   if (add->Opcode() == Op_Add(bt)) {
1847     addidx = 1;
1848   } else if (mask->Opcode() == Op_Add(bt)) {
1849     mask = add;
1850     addidx = 2;
1851     add = in(addidx);
1852   }
1853   if (addidx > 0) {
1854     Node* add1 = add->in(1);
1855     Node* add2 = add->in(2);
1856     if (add1 != NULL && add2 != NULL) {
1857       if (AndIL_shift_and_mask_is_always_zero(phase, add1, mask, bt, false)) {
1858         set_req_X(addidx, add2, phase);
1859         return this;
1860       } else if (AndIL_shift_and_mask_is_always_zero(phase, add2, mask, bt, false)) {
1861         set_req_X(addidx, add1, phase);
1862         return this;
1863       }
1864     }
1865   }
1866   return NULL;
1867 }