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